Deterministic Gradient Descent
Convergence Proofs for Unconstrained Optimization
References: Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., Springer, 2006, Ch. 3; Amir Beck, First-Order Methods in Optimization, SIAM, 2017.
이 장에서는 확률적 gradient나 constraint가 없는 결정론적 무제약 최적화 문제만 다룬다. Convexity와 strong convexity의 정의 및 기본 성질은 알고 있다고 가정하고, gradient descent에 필요한 감소성, 수렴성, 수렴속도를 모두 직접 증명한다. 별도의 언급이 없으면 $f:\mathbb{R}^n\rightarrow\mathbb{R}$는 미분 가능하고 아래로 유계이며, gradient는 $L$-Lipschitz continuous하다고 가정한다.
Problem and Algorithm
다음 문제를 생각한다.
\[\min_{x\in\mathbb{R}^n} f(x).\]고정 step size $\alpha>0$를 사용하는 gradient descent는
\[x_{k+1}=x_k-\alpha\nabla f(x_k)\]로 정의된다. 앞으로 $g_k=\nabla f(x_k)$, $f_k=f(x_k)$로 쓴다. 분석의 출발점은 1장에서 증명한 Descent Lemma이다.
\[f(y)\leq f(x)+\nabla f(x)^T(y-x)+\frac{L}{2}\lVert y-x\rVert^2.\]Lemma: one-step inequality
$f$가 $L$-smooth이면 gradient descent의 매 iteration에서
\[f_{k+1} \leq f_k - \alpha\left(1-\frac{L\alpha}{2}\right) \lVert g_k\rVert^2\]가 성립한다.
Proof
Descent Lemma에 $x=x_k$와 $y=x_{k+1}$을 대입하면
\[f_{k+1} \leq f_k + g_k^T(x_{k+1}-x_k) + \frac{L}{2}\lVert x_{k+1}-x_k\rVert^2.\]Gradient descent update에서 $x_{k+1}-x_k=-\alpha g_k$이므로
\[\begin{aligned} f_{k+1} &\leq f_k + g_k^T(-\alpha g_k) + \frac{L}{2}\lVert-\alpha g_k\rVert^2 \\ &= f_k - \alpha\lVert g_k\rVert^2 + \frac{L\alpha^2}{2}\lVert g_k\rVert^2 \\ &= f_k - \alpha\left(1-\frac{L\alpha}{2}\right) \lVert g_k\rVert^2. \end{aligned}\]따라서 one-step inequality가 성립한다. $\square$
편의를 위해
\[c_\alpha=\alpha\left(1-\frac{L\alpha}{2}\right)\]라 두면 $0<\alpha<2/L$에서 $c_\alpha>0$이다.
Nonconvex Objective
Theorem: 감소성과 gradient norm의 수렴
$f$가 아래로 유계이고 $\nabla f$가 $L$-Lipschitz continuous라고 하자. $0<\alpha<2/L$이면 gradient descent는
\[f_{k+1}\leq f_k-c_\alpha\lVert g_k\rVert^2\]을 만족한다. 따라서 ${f_k}$는 단조 감소하여 어떤 유한한 값으로 수렴하고,
\[\sum_{k=0}^{\infty}\lVert g_k\rVert^2<\infty, \qquad \lim_{k\rightarrow\infty}\lVert g_k\rVert=0\]이다.
Proof
one-step inequality와 $c_\alpha>0$에서 첫 번째 부등식이 바로 나온다. $f_{\inf}=\inf_x f(x)>-\infty$라 하고 $k=0$부터 $N-1$까지 합하면
\[c_\alpha\sum_{k=0}^{N-1}\lVert g_k\rVert^2 \leq f_0-f_N \leq f_0-f_{\inf}.\]$N\rightarrow\infty$로 보내면 음이 아닌 항들의 무한합이 유한하므로 각 항은 $0$으로 가야 한다. 따라서 $\lVert g_k\rVert\rightarrow 0$이다. 또한 $f_k$는 단조 감소하고 아래로 유계이므로 실수 수열의 단조수렴정리에 의해 수렴한다. $\square$
Corollary: 비볼록 stationarity complexity
위 증명의 유한합 부등식으로부터 모든 $K\geq 1$에 대해
\[\min_{0\leq k<K}\lVert g_k\rVert^2 \leq \frac{f_0-f_{\inf}}{Kc_\alpha}\]를 얻는다. 특히 $\alpha=1/L$이면 $c_\alpha=1/(2L)$이므로
\[\min_{0\leq k<K}\lVert g_k\rVert^2 \leq \frac{2L(f_0-f_{\inf})}{K}.\]따라서 어떤 iteration에서 $\lVert\nabla f(x_k)\rVert\leq\varepsilon$을 보장하려면
\[K\geq\frac{2L(f_0-f_{\inf})}{\varepsilon^2}\]이면 충분하다. 즉 gradient norm 기준 iteration complexity는 $\mathcal{O}(1/\varepsilon^2)$이다.
Corollary: accumulation point의 정지성
${x_k}$의 부분수열 $x_{k_j}$가 $\bar{x}$로 수렴한다고 하자. $\nabla f$는 연속이고 $\nabla f(x_k)\rightarrow 0$이므로
\[\nabla f(\bar{x}) =\lim_{j\rightarrow\infty}\nabla f(x_{k_j}) =0.\]따라서 모든 accumulation point는 stationary point이다. 다만 비볼록 함수에서는 이 점이 local minimum인지, saddle point인지, local maximum인지까지는 보장하지 않는다. 또한 위 정리는 gradient norm의 수렴을 보일 뿐, ${x_k}$ 자체가 반드시 하나의 점으로 수렴한다는 결론은 주지 않는다.
Convex Smooth Objective를 위한 보조정리
Convex한 $L$-smooth 함수에서는 gradient가 단순히 Lipschitz일 뿐 아니라 co-coercive하다. 이 성질은 반복점의 수렴과 목적함수 수렴속도를 증명하는 핵심이다.
Lemma: co-coercivity
$f$가 convex이고 $\nabla f$가 $L$-Lipschitz continuous이면 모든 $x,y\in\mathbb{R}^n$에 대해
\[\left(\nabla f(x)-\nabla f(y)\right)^T(x-y) \geq \frac{1}{L}\lVert\nabla f(x)-\nabla f(y)\rVert^2\]가 성립한다.
Proof
함수
\[h(z)=f(z)-\nabla f(y)^Tz\]를 정의하자. $h$는 convex이고 $L$-smooth이며 $\nabla h(y)=0$이므로 $y$는 $h$의 global minimizer이다. $z=x-(1/L)\nabla h(x)$에 Descent Lemma를 적용하면
\[h(z)\leq h(x)-\frac{1}{2L}\lVert\nabla h(x)\rVert^2.\]$h(y)\leq h(z)$이므로
\[f(x)-f(y)-\nabla f(y)^T(x-y) \geq \frac{1}{2L}\lVert\nabla f(x)-\nabla f(y)\rVert^2.\]$x$와 $y$를 바꾼 부등식을 더하면 함수값 항이 소거되어
\[\left(\nabla f(x)-\nabla f(y)\right)^T(x-y) \geq \frac{1}{L}\lVert\nabla f(x)-\nabla f(y)\rVert^2\]를 얻는다. $\square$
Convex Objective
이 절에서는 minimizer가 존재한다고 가정하고 해집합을 $X^\star=\operatorname{argmin}f$라 쓴다.
Theorem: 반복점의 수렴
$f$가 convex이고 $L$-smooth하며 $X^\star\neq\varnothing$이라고 하자. $0<\alpha<2/L$이면 gradient descent의 반복점 수열 ${x_k}$는 $X^\star$의 어떤 점으로 수렴한다.
Proof
임의의 $x^\star\in X^\star$에 대해 $\nabla f(x^\star)=0$이다. Co-coercivity를 $x=x_k$, $y=x^\star$에 적용하면
\[g_k^T(x_k-x^\star)\geq\frac{1}{L}\lVert g_k\rVert^2.\]따라서
\[\begin{aligned} \lVert x_{k+1}-x^\star\rVert^2 &=\lVert x_k-x^\star-\alpha g_k\rVert^2 \\ &=\lVert x_k-x^\star\rVert^2 -2\alpha g_k^T(x_k-x^\star) +\alpha^2\lVert g_k\rVert^2 \\ &\leq\lVert x_k-x^\star\rVert^2 -\alpha\left(\frac{2}{L}-\alpha\right)\lVert g_k\rVert^2. \end{aligned}\]그러므로 ${x_k}$는 모든 $x^\star\in X^\star$에 대해 Fej'er monotone하고 유계이다. 유계 수열이므로 적어도 하나의 convergent subsequence $x_{k_j}\rightarrow\bar{x}$가 존재한다. 앞 절에서 $\nabla f(x_k)\rightarrow 0$을 보였고 gradient가 연속이므로 $\nabla f(\bar{x})=0$이다. Convexity에 의해 $\bar{x}\in X^\star$이다.
이제 Fej'er monotonicity를 $x^\star=\bar{x}$에 적용하면 ${\lVert x_k-\bar{x}\rVert}$는 수렴하는 수열이다. 그런데 부분수열 $x_{k_j}\rightarrow\bar{x}$가 존재하므로 그 거리 수열의 부분수열은 $0$으로 간다. 전체 거리 수열의 극한도 $0$이어야 하므로 $x_k\rightarrow\bar{x}$이다. $\square$
Theorem: 목적함수의 $\mathcal{O}(1/k)$ 수렴
$f$가 convex이고 $L$-smooth하며 $x^\star\in X^\star$라고 하자. $\alpha=1/L$이면 모든 $K\geq1$에 대해
\[f(x_K)-f^\star \leq \frac{L\lVert x_0-x^\star\rVert^2}{2K}.\]Proof
Convexity와 $\alpha=1/L$을 사용하면
\[f_k-f^\star\leq g_k^T(x_k-x^\star)\]이고, one-step inequality는
\[f_{k+1}\leq f_k-\frac{1}{2L}\lVert g_k\rVert^2\]를 준다. 두 부등식을 결합하면
\[f_{k+1}-f^\star \leq g_k^T(x_k-x^\star)-\frac{1}{2L}\lVert g_k\rVert^2.\]한편 반복식에서
\[\begin{aligned} \lVert x_k-x^\star\rVert^2-\lVert x_{k+1}-x^\star\rVert^2 &=\frac{2}{L}g_k^T(x_k-x^\star)-\frac{1}{L^2}\lVert g_k\rVert^2. \end{aligned}\]따라서
\[f_{k+1}-f^\star \leq \frac{L}{2}\left( \lVert x_k-x^\star\rVert^2-\lVert x_{k+1}-x^\star\rVert^2 \right).\]$k=0$부터 $K-1$까지 합하면 우변이 telescope되어
\[\sum_{k=0}^{K-1}\left(f_{k+1}-f^\star\right) \leq\frac{L}{2}\lVert x_0-x^\star\rVert^2.\]$\alpha=1/L$에서 ${f_k}$는 단조 감소하므로
\[K\left(f(x_K)-f^\star\right) \leq \sum_{k=0}^{K-1}\left(f_{k+1}-f^\star\right).\]두 부등식을 결합하면 원하는 결과를 얻는다. $\square$
Corollary: gradient norm bound
Convexity는 필요하지 않지만 $f$가 아래로 유계이면 Descent Lemma로부터
\[f\left(x-\frac{1}{L}\nabla f(x)\right) \leq f(x)-\frac{1}{2L}\lVert\nabla f(x)\rVert^2\]이다. 좌변은 $f^\star$ 이상이므로
\[\lVert\nabla f(x)\rVert^2\leq2L\left(f(x)-f^\star\right).\]이를 위의 convex rate에 적용하면
\[\lVert\nabla f(x_K)\rVert \leq \frac{L\lVert x_0-x^\star\rVert}{\sqrt{K}}\]를 얻는다.
Strongly Convex Objective
Definition: strong convexity
미분 가능한 함수 $f:\mathbb{R}^n\rightarrow\mathbb{R}$가 어떤 $\mu>0$에 대하여 모든 $x,y\in\mathbb{R}^n$에서
\[f(y) \geq f(x) + \nabla f(x)^T(y-x) + \frac{\mu}{2}\lVert y-x\rVert^2\]를 만족하면 $f$를 $\mu$-strongly convex function이라 한다. 즉 strong convexity는 convexity의 first-order lower bound에 양의 quadratic curvature를 추가한 조건이다. 이는
\[x\longmapsto f(x)-\frac{\mu}{2}\lVert x\rVert^2\]가 convex인 것과 동치이다. $f$가 두 번 연속 미분 가능하면
\[\nabla^2f(x)\succeq\mu I \qquad \text{for every }x\in\mathbb{R}^n\]와 동치이다. $f$가 동시에 $L$-smooth이면 Hessian eigenvalue가 $[\mu,L]$에 있으므로 $0<\mu\leq L$이다.
Minimizer $x^\star$가 존재하면 $\nabla f(x^\star)=0$이므로 strong convexity의 정의에서
\[f(x) \geq f(x^\star) + \frac{\mu}{2}\lVert x-x^\star\rVert^2\]를 얻는다. 따라서 minimizer는 유일하다. 이하에서는 $f$가 $\mu$-strongly convex이고 $L$-smooth하다고 가정한다.
Lemma: Polyak–Łojasiewicz inequality
Strong convexity로부터
\[\lVert\nabla f(x)\rVert^2 \geq 2\mu\left(f(x)-f^\star\right)\]가 성립한다.
Proof
Strong convexity에 의해 모든 $y$에 대해
\[f(y)\geq f(x)+\nabla f(x)^T(y-x)+\frac{\mu}{2}\lVert y-x\rVert^2.\]우변을 $y$에 대해 최소화하면 $y=x-(1/\mu)\nabla f(x)$이고 최솟값은
\[f(x)-\frac{1}{2\mu}\lVert\nabla f(x)\rVert^2\]이다. 따라서
\[f^\star\geq f(x)-\frac{1}{2\mu}\lVert\nabla f(x)\rVert^2\]이고 항을 정리하면 결과를 얻는다. $\square$
Theorem: 목적함수의 linear convergence
$\alpha=1/L$이면
\[f(x_k)-f^\star \leq \left(1-\frac{\mu}{L}\right)^k \left(f(x_0)-f^\star\right).\]Proof
one-step inequality와 PL inequality를 차례로 사용하면
\[\begin{aligned} f_{k+1}-f^\star &\leq f_k-f^\star-\frac{1}{2L}\lVert g_k\rVert^2 \\ &\leq\left(1-\frac{\mu}{L}\right)(f_k-f^\star). \end{aligned}\]이 부등식을 $k$번 반복하면 결과가 나온다. $\square$
앞에서 얻은 quadratic-growth bound
\[f(x_k)-f^\star\geq\frac{\mu}{2}\lVert x_k-x^\star\rVert^2\]과 결합하면 반복점에 대해서도
\[\lVert x_k-x^\star\rVert^2 \leq \frac{2}{\mu} \left(1-\frac{\mu}{L}\right)^k \left(f(x_0)-f^\star\right)\]를 얻는다. Condition number $\kappa=L/\mu$를 사용하면 목적함수 오차를 $\varepsilon$ 이하로 만드는 데 필요한 iteration 수는
\[K=\mathcal{O}\left(\kappa\log\frac{1}{\varepsilon}\right)\]이다.
Quadratic Objective의 정확한 분석
다음의 positive-definite quadratic problem을 생각한다.
\[f(x)=\frac{1}{2}x^TQx-b^Tx, \qquad Q=Q^T\succ0.\]최적점은 $x^\star=Q^{-1}b$이고 $\nabla f(x)=Qx-b$이다. 오차 $e_k=x_k-x^\star$를 정의하면
\[e_{k+1}=(I-\alpha Q)e_k.\]$Q=U\Lambda U^T$를 eigendecomposition하고 $z_k=U^Te_k$라 두면 각 성분은
\[(z_{k+1})_i=(1-\alpha\lambda_i)(z_k)_i\]를 만족한다. 따라서 모든 초기점에서 수렴할 필요충분조건은
\[\max_i\lvert1-\alpha\lambda_i\rvert<1,\]즉
\[0<\alpha<\frac{2}{\lambda_{\max}(Q)}\]이다. 최악의 contraction factor
\[q(\alpha)=\max_i\lvert1-\alpha\lambda_i\rvert\]를 최소화하려면 양 끝 eigenvalue에서의 크기를 같게 만들어야 하므로
\[1-\alpha\lambda_{\min} =-(1-\alpha\lambda_{\max}).\]이를 풀면
\[\alpha^\star=\frac{2}{\lambda_{\min}+\lambda_{\max}}, \qquad q(\alpha^\star)=\frac{\kappa-1}{\kappa+1},\]여기서 $\kappa=\lambda_{\max}/\lambda_{\min}$이다. 이는 ill-conditioned problem에서 gradient descent가 느려지는 이유를 정확히 보여준다.
What Is and Is Not Guaranteed
| Assumption | Step Size | Guaranteed Result |
|---|---|---|
| $L$-smooth, lower bounded | $0<\alpha<2/L$ | $f_k$ decreases, $\lVert\nabla f(x_k)\rVert\rightarrow0$, best gradient norm squared is $\mathcal{O}(1/k)$ |
| Convex, $L$-smooth, minimizer exists | $0<\alpha<2/L$ | $x_k$ converges to a minimizer |
| Convex, $L$-smooth | $\alpha=1/L$ | $f(x_k)-f^\star=\mathcal{O}(1/k)$ |
| $\mu$-strongly convex and $L$-smooth | $\alpha=1/L$ | $f(x_k)-f^\star\leq(1-\mu/L)^k(f(x_0)-f^\star)$ |
| Positive-definite quadratic | $0<\alpha<2/\lambda_{\max}$ | Exact spectral convergence; optimal fixed step is $2/(\lambda_{\min}+\lambda_{\max})$ |
가장 중요한 한계는 비볼록 문제에서 gradient descent가 일반적으로 stationary point까지만 보장한다는 점이다. Global minimum 수렴은 convexity와 해의 존재 같은 추가 구조가 있어야 하며, 선형 수렴에는 strong convexity 또는 그에 준하는 error-bound 조건이 필요하다.