-
Variance Reduction Algorithms and Catalyst Acceleration
서론 본 글에서는 단순히 convex function $f$를 최소화 하는 것이 아니라, 이들의 합인 $F = \frac{1}{n} \sum_{i=1}^n f_i(x)$ 를 최소화하는 알고리즘에 대해서 알아보고, 이에 Catalyst를 적용해보겠습니다. 이와 같은 형식의 함수 $F$는 Logistic Regression 등 Machine Learning에서 등장합니다. 원래는 $F$에 추가적인 “proximal function”이 있어, $F = \frac{1}{n} \sum_{i=1}^n f_i(x) + \psi(x)$ 형태를 가지나 (예를 들어 $l_1$ regularization) 여기서는 편의상 $\psi$에 대한 논의를 생략하겠습니다. 글의 순서는 대략적으로 다음과 같습니다. $F$를 최소화하는 알고리즘이 발전한 과정의 큰 흐름에 대해서...
-
Heavy-light Decomposition With Globally Balanced Binary Trees
Table Of Contents Prerequisite Introduction Main Idea Implementation Benchmark Prerequisite Segment tree - Tutorial on cp-algorithms Heavy-light decomposition - Tutorial on cp-algorithms Introduction 안녕하세요, Aeren입니다! 다음 문제를 생각해봅시다. Monoid $(T,+)$와 $(L,+)$, left monoid action $\ast(\ast):(L,T)\rightarrow T$, tree $G=(V,E)$와 각 node의 가중치 $W:V\rightarrow T$이 주어진다. 다음 연산들을 수행하라. $u,v\in V$이 주어진다. $u$와 $v$를 잇는 유일한 path $P$에 대하여 $\sum_{w\in P}W(w)$의 값을 출력한다. $u,v\in V$와 $f\in L$이 주어진다. $u$와 $v$를 잇는 유일한 path $P$에 대하여 각 $w\in...
-
Union Find의 시간 복잡도 증명
Union Find Union Find 또는 Disjoint Set이라고 불리는 자료구조는 여러 개의 원소를 포함하고 있는 집합들을 다루는 자료구조이다. 초기에, $N$개의 원소들과 $N$개의 집합들이 만들어져 있고, 각각의 집합은 서로 다른 원소 하나씩을 가지고 있다. 이 위에 다음과 같은 두 개의 연산을 할 수 있다. Union(x, y) : 원소 x가 속한 집합과, 원소 y가 속한 집합을 합친다. Find(x) : 원소 x가 어떤 집합에 속해있는지 반환한다. 보통 x가 속해있는 집합의 대표 원소 하나를 반환한다. struct dsu { dsu() {...
-
Li Chao Tree의 Lazy Propagation
개요 리차오 트리는 직선들을 관리하는 동적 세그먼트 트리의 일종으로, Convex Hull Trick 등등에서 쓰이는 자료구조입니다. 다른 세그먼트 트리와 마찬가지로 리차오 트리에도 레이지 프로퍼게이션을 적용할 수 있지만, 이에 대해서는 잘 알려져 있지 않습니다. 이 글에서는 리차오 트리에 레이지 프로퍼게이션을 적용한 확장 연산들과 그 활용에 대해 소개합니다. 리차오 트리 좌표 범위가 $N$일 때, 기본적인 리차오 트리는 다음과 같은 연산들을 할 수 있습니다. insert(a,b) : 새로운 직선 $y=ax+b$를 삽입한다. $O(\log{N})$ get(x) : 주어진 $x$좌표에서 $y$좌표의 최솟값을 구한다. $O(\log{N})$...
-
다양한 생성함수와 그 응용 (1)
개요 어떤 주어진 성질을 만족하는 것의 가짓수를 세는 문제를 연구하는 학문을 조합론이라 하며, PS 분야 뿐만 아니라 통계학, 수리물리학 등 다양한 분야에서 중요하게 다루어진다. 일반적으로, PS 분야에서 조합론 문제는 Dynamic Programming 테크닉을 이용하여 효율적으로 해결할 수 있다. 하지만, DP 수열을 정의하는 점화식을 알아내는 작업은 조합론의 영역이지만, 그렇게 정의된 DP 수열을 빠르고 효율적으로 계산하는 작업은 알고리즘의 영역에 속한다. 본 글은, 후자의 알고리즘 문제를 해결하는 좋은 방법에 대하여 수학적으로 기술한다. 점화식 형태로 정의된 수열이 주어질...