Stochastic variance-reduced gradient (SVRG)

Stochastic variance reduction, SVR, 은 다음과 같은 objective를 최적화하는데 도움을 줄 수 있다.
$$
\begin{align}
f(w) = \frac{1}{n} \sum_{i=1}^{N} f_i (w)
\end{align}
$$
여기서 $f_i$ 는 한 데이터 포인트의 loss이다. SVRG의 대표적인 방법은 SVRG, SAGA, 그리고 그 변형들이 있다. 보통 SVR은 variance를 control variate을 통하여 줄인다. 여기서 control variate은 전통적으로 MC에서 variance를 줄이는 용도로 많이 사용되어 왔다. Random variable $X$ 가 있다고 가정해보자. 평균 $\mathbb{E}[X] = \bar{X}$ 을 통해서 $X$ 를 측정할수도 있지만, control variate을 사용할수도 있다. 만약에 $Y$ 는 $X$ 와 correlated 한 variable이면, 즉 $\text{Cov}[X, Y] > 0$, 우리는 $\bar{X}$를 다음 식을 통해서 측정할 수 있다:
$$
\begin{align}
Z = X – Y + \mathbb{E}[Y]
\end{align}
$$
위 estimate은 당연히 unbiased이다. $\mathbb{V}[Y] \leq 2 \text{Cov}[X, Y]$ 하면, $Z$ 의 variance는 $X$ 의 variance 보다 낮다. 놀랍게도, 위와 같은 방법들은 smooth strongly-convex optimization problem에서 linear convergence rate를 맛볼수 있다. control variate을 사용하는 방법중에 제일 간단한 SVRG는 어떻게 작동되는지 서술하겠다.

SVRG는 주기적으로 snapshot point $\tilde{w}$ 을 지정하고, full gradient $f'(\tilde{w})$ 을 계산한다. Snapshot point은 어느 지점에서나 지정해도 되지만, 보통 한 epoch끝나고 지정한다. SGD step은 $w_{k+1} = w_k – \alpha f_i ‘ (w_k)$ 을 통하여 update된다. 여기서 $f_i$ 는 한 batch의 gradient이고, $\alpha$ 는 learning rate이다. 반면에, SVRG update는 다음과 같다:
$$
\begin{align}
w_{k+1} = w_k – \alpha [f_i (w_k) – f_i ‘ (\tilde{w}) + f'(\tilde{w})]
\end{align}
$$
위에 서술한 바와 같이 $w_k$ 의 expectation은 동일하다. 그렇기 때문에 SVRG는 unbiased이다. 물론 unbiased 성질이 빠른 convergence에 중요하지는 않지만, 분석하는데 더 편리하다. SVRG의 하나의 단점은 $f'(\tilde{w})$ 이 모든 식에 등장하기 때문에, 연속된 steps들의 correlation이 높다. 또한, deep neural network에서 SVRG가 어떻게 적용되는지는 아직 의문점이 있다.

댓글 남기기

이 사이트는 스팸을 줄이는 아키스밋을 사용합니다. 댓글이 어떻게 처리되는지 알아보십시오.

Site Footer

Sliding Sidebar

%d 블로거가 이것을 좋아합니다: