[Abstract]

SAGA는 SAG와 SVRG의 뒤를 잇는데, 더 좋은 수렴도를 갖는다. SDCA와는 다르게 strongly convex가 아닌 문제도 바로 풀 수 있고, 문제의 본질적인 strong convexity에 적응할 수 있다.

[1] Introduction

함수 $f(x)$를 최소화하고 싶은데, $f(x)$는

이렇게 생겼다. 각 $f_i$는 convex하고 gradient가 $L$-Lipschitz continuous하다. 이 논문에서는 $f_i$들이 $\mu$-strongly convex한 경우와 $F(x)=f(x)+h(x)$인 경우(proximal gradient descent에서 봤던 모양)도 다룰 것이다.

[2] SAGA Algorithm

SAGA 알고리즘은 다음과 같다.

  1. $j$를 랜덤으로 뽑는다.
  2. $\phi_j^{k+1}=x^k$라고 하고, $f’_ j(\phi_j^{k+1})$를 테이블에 저장한다. 즉, 모든 $f$중 하나의 $f_j$의 gradient만을 구한다.
  3. $x$를 $f’_ j(\phi_j^{k+1}), f’_ j(\phi_j^k)$과 테이블에 있는 평균을 이용해 업데이트한다. 이고, 이다.

strongly convex일 때와 아닐 때의 수렴도는 각각 증명되어 있다. strongly convex가 아닌 경우에 $\gamma=\frac{1}{3L}$를 사용할 경우, SAGA는 자동적으로 strong convexity $\mu\gt 0$에 적응한다. strongly convex가 아닌 문제에서는 정규화 항($\lambda w^Tw$)을 통해 incremental gradient method들이 적용될 수 있는데, SAGA에서는 $\lambda$의 조정을 피할 수 있다. 아마 $h$함수로 뺄 수 있다는 뜻인듯?

SAGA : midpoint between SAG and SVRG/S2GD

SVRG에서는 SGD의 분산을 관찰해서 step size가 0으로 수렴해야만 전체도 수렴한다는 것을 알고, 상수 step size를 사용하기 위해 SGD에 분산 감소 접근법을 사용하여 선형 수렴도를 얻었다. SVRG 논문에서는 SAG도 분산 감소를 하지만, 어떻게 그런 맥락이 나왔는지는 설명하지 않았는데 이 논문에서 그 연결고리를 설명할 것이다.

$\mathbb{E}(X)=\theta_\alpha=\alpha(X-Y)+\mathbb{E}(Y)$으로 추정하고 $\theta_\alpha$의 분산을 줄이고 싶을 때, $\text{Var}(\theta_\alpha)=\alpha^2\left[\text{Var}(X)+\text{Var}(Y)-2\text{Cov}(X,Y)\right]$ 이므로 $X, Y$가 서로 높은 상관관계가 있다면 $X$의 분산에 비해 $\theta_\alpha$의 분산이 더 작다. $\alpha$가 $0$부터 $1$까지 증가할 때 분산은 증가하지만 bias는 감소한다.

$X$가 현재 선택된 gradient $f’_ j(x^k)$이고, $Y$가 과거에 저장된 gradient $f’_ j(\phi_j^k)$라고 하면, SAG는 $\alpha=\frac{1}{n}$이고, SAGA는 $\alpha=1$이다. SAGA는 bias가 없기 때문에 proximal operator를 사용할 수 있다. SVRG는 $Y=f’_ i(\tilde(x))$이다. SAG는 이전의 모든 gradient를 저장해야 하고, SVRG는 반복이 시작될 때 연산이 크다는 단점이 있다. SVRG는 안쪽 루프의 반복수 $m$을 파라미터로 지정해 줘야 한다.

Finito/MISO$\mu$

SAGA에서 $u^0=x^0+\gamma\sum_{i=1}^nf’_ i(x^0)$으로 놓으면 SAGA 알고리즘을 $u$에 대해 업데이트하는 것으로 바꿀 수 있다. Finito와 MISO$\mu$는 $x^{k+1}=\frac{1}{n}\sum_i\phi_i^k-\gamma\sum_{i=1}^nf’_ i(\phi_i^k)$로 업데이트 한다. step length는 $\gamma$이며, step size는 $\frac{1}{\mu n}$이다.

Finito에서의 $\bar{\phi}$에 대한 식은, $\bar{\phi}$를 $u$로 바꾸면 SAGA의 식과 같다. SAGA는 Finito와 MISO$\mu$과 비교했을 때 strongly convex를 요구하지 않고, 따라서 proximal operator를 사용할 수 있다. 또한 강력한 $\phi_i$값을 요구하지 않는다. Finito/MISO$\mu$는 $f_i$가 연산량이 많을 때 유용하게 쓰일 수 있다.

SDCA

SDCA는 원래 $f_i$의 convex conjugate를 사용하는데, 여기서는 SAGA와의 연결고리를 설명하기 위해 primal값만을 사용하는 방법을 소개한다. 이 방법은 MISO$\mu$방법과도 비슷하다. 이 방법은 dual variable을 사용하는 방법과 결과가 똑같다. 아마도 이런 말.. 이부분 내용 이해는 하지 못했음 이 방법은 각각의 $f_i$가 그냥 convex이기만 할 때, strongly convex한 정규화 텀으로 인해 전체 $f$의 strongly convex함이 유도된다. 그러나 이 정규화 텀을 각 $f_i$에 고르게 넣으면 각 $f_i$가 strongly convex 하도록 바꿀 수 있으며, 그렇게 나온 방법은 Finito와 SDCA의 중간에 있다.

[5] Theory

[Thm 1]

$x^* $가 optimal solution이고,

($T$는 Lyapunov function) 으로 정의하자. $\gamma=\frac{1}{2(\mu n+L)}, c=\frac{1}{2\gamma(1-\gamma\mu)n}, \kappa=\frac{1}{\gamma\mu}$라고 하면,

를 얻을 수 있다.

[Cor 1]

이므로, $\mu(n-0.5)\le\mu n$을 사용하면

를 얻을 수 있다.

[6] Experiments

MNIST, COVTYPE, IJCNN1, MILLIONSONG 데이터셋에 실험을 했는데, Finito가 성능은 가장 좋지만 expensive하다. SVRG는 epoch 단위에서는 빠르게 수렴하지만, epoch당 gradient evaluation이 다른 방법에 비해 2배이기 때문에, 가장 좋다고 말할 수 없다. SAGA는 non-permuted Finito와 SDCA와 성능이 비슷하다. 결론은, 수렴도 보다는 각 문제에 대한 성질과 잘 맞는 optimizer를 사용해야 한다.

incremental gradient methods는 SGD와 같은 것임
step lenght는 뭐지?
proximal operator?