目標とする論文
Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent (Jin et al., 2017)
本記事の内容
対称論文のPreliminariesを理解するために必要な知識を調べた．
内容
定義等
l-smooth function
次を満たす関数．
|| \nabla f(x_1) - \nabla f(x_2) || \leq l || x_1 - x_2 || \ \forall x_1 , x_2
α-strongly convex matrix
次を満たす行列．
\lambda_{min}( \nabla ^ 2 f (x) ) \leq \alpha, \forall x.
ただし，$\lambda_{min}(\cdot)$は行列の固有値の一番小さいもの．
ρ-Hessian Lipschitz function
次を満たす行列
|| \nabla ^2 f(x_1) - \nabla ^2 f(x_2) || \leq \rho || x_1 - x_2 || \ \forall x_1 , x_2
ただし行列のノルムはスペクトルノルム．
スペクトルノルム
|| A || = \sup_{x \neq 0}{ \frac{||Ax||}{||x||} }
を行列$A$のスペクトルノルムと呼ぶ．
ε-second-order statinary point
$\rho$-Hessian Lipschitz function $f$について，次を満たすもの．
|| \nabla f(x) || \leq \epsilon \ \land \ \lambda_{min}( \nabla ^2 f (x) ) \geq -\sqrt{\rho \epsilon}
ε-suboptimal point
最適値( $f^* \equiv \min_y f(y) $ )に対して，$ f(x) \leq f^* + \epsilon $ となる$x$のこと．
定理等
定理1 ( Nesterov, 2004 )
$l$-smooth かつ $\alpha$-strongly convexな関数 $f$ があるとする．任意の$\epsilon>0$について，$\epsilon$-suboptimal pointを発見するために必要な繰り返しのオーダーは次のようになる．
- $\eta = 1 / l$ の時の勾配法(GD) : $O((l/\alpha)\cdot \log{((f(x_0)-f^*)/\epsilon))}$
- $\eta = 1 / l$ かつ $\theta = \sqrt{\alpha / l }$ の時の加速勾配法(AGD): $O(\sqrt{(l/\alpha)}\cdot \log{((f(x_0)-f^*)/\epsilon))}$
定理2 ( Jin et al., 2017 )
$l$- smooth かつ $\rho$-Hessian lipschitzな関数$f$があるとする．$\epsilon>0$について，$\epsilon$-second order stationary pointを高い確率で発見できるために必要な繰り返しのオーダーは次のようになる．
- perturbed GD ：
\tilde{O} \left( \frac{l(f(x_0) - f^*)}{\epsilon^2} \right)
ただし，$\tilde{O}(\cdot)$は多重対数項を無視する．
アルゴリズムとその違い．(Single-Loopのみ記載）
GD ( gradient descent )
必要繰り返し回数 : $O(1/\epsilon^2)$
到達点：First order stationary point
x[0], eta = input()
for t in [0,1,...]:
x[t+1] = x[t] - eta * f.gradient(x[t])
AGD ( accelerated gradient descent )
必要繰り返し回数 : $O(1/\epsilon^2)$
到達点：First order stationary point
x[0], eta, theta = input()
v[0] = 0
for t in [0,1,...]:
y[t+1] = x[t] + ( 1 - theta ) * v[t]
x[t+1] = y[t] - eta * f.gradient(x[t])
v[t+1] = x[t+1] - x[t]
Noisy GD
必要繰り返し回数 : $O(poly(d/\epsilon))$
到達点：Second order stationary point
Stochastic gradient oracle SG(w) について詳しく理解してから再掲．
Perturbed GD
必要繰り返し回数 : $\tilde{O}(1/\epsilon^2)$
到達点：Second order stationary point
x[0], eta, g_thres, g_noise, t_thres, t_noise, r, f_thres = input()
v[0] = 0
for t in [0,1,...]:
if f.gradient(x[t]) <= g_thres and t - t_noise > t_thres:
x_hat[t] = x[t]
t_noise = t
xi[y] = B0(r).sample_uniformly()
x[t] = x_hat[t] + xi[t]
if t - t_noise = t_thres and f(x[t]) - f(x_hat[t_noise]) > - f_thres:
return x_hat[t_noise]
x[t+1] = x[t] - eta * f.gradient(x[t])
Pertubed AGD (提案手法)
必要繰り返し回数 : $\tilde{O}(1/\epsilon^{7/4})$
到達点：Second order stationary point
参考文献
Jin, Chi, Praneeth Netrapalli, and Michael I. Jordan. "Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent." arXiv preprint arXiv:1711.10456 (2017).
Jin, Chi, et al. "How to Escape Saddle Points Efficiently." arXiv preprint arXiv:1703.00887 (2017).
Ge, Rong, et al. "Escaping from saddle points—online stochastic gradient for tensor decomposition." Conference on Learning Theory. 2015.
次回
定理１か定理２を証明した論文を紹介しようと思います．