Accelerating Stochastic Gradient Descent using Predictive Variance Reduction

[Abstract]

SGD의 본질적인 분산 때문에 느리고 점진적으로 수렴하는 단점을 해결하고자 이 논문에서는 SVRG라고 불리는 explicit한 분산 감소 방법을 제안한다. smooth하고 strongly convex한 함수에 대해서는 SDCA, SAG와 같은 수렴속도를 증명했다. SDCA, SAG와의 차이점은 gradient를 저장할 필요가 없다.

[1] Introduction

머신러닝에서 푸는 문제는 주로

$\min P(w), P(w):=\frac{1}{n}\sum_{i=1}^n\psi_i(w)$

의 형태이다. (주로 $\psi$는 loss function이다) 주로 이를 풀기 위해 SGD를 사용하는데, 일반적인 형태는

$w^{(t)}=w^{(t-1)}-\eta_tg_t(w^{(t-1)}, \xi_t)$

이다. SGD는 분산 때문에 computation과 convergence 사이에 trade-off가 있는데, 이를 개선하기 위해 여러 연구가 있었다. SDCA와 SAG가 대표적인데, 이들은 이전의 gradient를 저장하기 때문에 딥러닝같은 복잡한 문제에는 적합하지 않다. 이 논문에서 제안하는 방법은

gradient를 저장하지 않아도 되고, 따라서 SDCA나 SAG가 적용하지 못하는 복잡한 문제에 적용할 수 있다.
SGD의 분산 감소와 직접적으로 연결될 수 있는 증명을 제시한다.
nonconvex 최적화에도 적용될 수 있다.

는 장점을 갖고 있다.

[2] Stochastic Variance Reduced Gradient

이 논문에서 제안하는 방법에서는 지정된 시간마다 $\tilde{w}$를 저장한다. 그리고 평균 gradient $\tilde{\mu}$ 또한 저장한다. 이 논문에서 제안하는 update rule은 다음과 같다.

$w^{(t)}=w^{(t-1)}-\eta_t(\triangledown\psi_i(w^{(t-1)})-\triangledown\psi_{i_t}(\tilde{w})+\tilde{\mu})$

SGD와는 다르게 이 방법에 있는 learning rate $\eta_t$는 decay 할 필요가 없고, 따라서 수렴 속도를 높여준다. gradient 계산이 끝나고 나서 $\tilde{w_s}$를 정하는 옵션에는 두 가지가 있는데,

$\tilde{w_s}=w_m$으로 정하는 방법
$t\in {0, \cdots , m-1}$에서 랜덤으로 선택된 $t$에 대해 $\tilde{w_s}=w_t$으로 선택하는 방법

이 있다. practical하게는 첫번째 방법을 쓰지만, 이 논문에서는 분석에서 두번째 방법을 사용했다.

[3] Analysis

우선 모든 $\psi_i(w)$는 convex하고 $P(w)$는 strongly convex하다고 한다.

[Thm 1]

$w_* =\arg\min_w P(w)$라고 하자. $m$이 충분히 커서

$\alpha = \frac{1}{\gamma\eta(1-2L\eta)m}+\frac{2L\eta}{1-2L\eta}\lt 1$

이면, 평균에서 다음과 같은 기하 수렴을 갖게 된다.

$\mathbb{E}P(\tilde{w_s})\le \mathbb{E}P(w_* )+\alpha^s[P(\tilde{w_* })-P(w_* )]$

이 수렴도를 SAG나 SDCA와 비교해보자. condition number가 $\frac{L}{\gamma}=n$인 사례를 생각해 보면 batch gradient descent에서는 정확도 $\epsilon$을 얻기 위해 반복 당 $n\ln(\frac{1}{\epsilon})$의 복잡도가 나온다. 그러나 SVRG는 $n\ln(\frac{1}{\epsilon})$의 복잡도가 나온다. 이 복잡도들은 SAG나 SDCA와 비슷한 수준이며, SVRG가 더 직관적이므로 더 낫다.

SVRG는 smooth하지만 strongly convex 하지 않은 경우에도 적용될 수 있는데, 수렴도는 $O(\frac{1}{T})$로, SGD의 수렴도인 $O(\frac{1}{\sqrt{T}})$보다 개선되었다. 인공신경망같은 nonconvex 문제에 SVRG를 이용하려면 local minimum에 가까운 $\tilde{w_0}$에서부터 시작하는 것이 좋다. 그러면 그 이후에 빠르게 수렴할 수 있다.

[4] SDCA as Variance Reduction

SDCA와 SAG는 분산 감소라는 측면에서 SVRG와 연결되어 있다. SDCA에서는 dual variable $\alpha_i^* =-\frac{1}{\lambda n}\triangledown\phi_i(w_* )$, $w^{(t)}=\sum_{i=1}^n\alpha_i^{(t)}$를 이용해서 analysis 한다. SDCA도 SVRG와 비슷하게 $\eta_t$가 $0$으로 가지 않아도 분산이 수렴한다.

[5] Experiments

Experiments에서는 SVRG를 SGD와 SDCA와 convex한 환경, nonconvex인 환경에서 비교하였다. SVRG의 weight는 SGD를 1번(convex), 10번(nonconvex) 돌려서 초기화 하였다. convex 문제에서 SGD보다는 확실히 좋았고, SDCA와는 비슷했지만 분산 감소 면에서는 SVRG가 더 좋았다. nonconvex에서는 SGD보다는 확실히 좋았고, SDCA와의 비교에서는 좋은 것도 있었고 나쁜 것도 있었다. 그런데 SVRG가 더 안정적으로 수렴하는 것처럼 보인다. SDCA와 SAG는 neural network에는 적용이 불가능하다.

SAGA 논문에서는 이 논문이 SAG가 분산 감소를 해준다고 하지만, 자세한 설명은 없다고 나와있음.