Basic of Optimization Algorithm
Descent, Convergence, and the Descent Lemma
References: Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., Springer, 2006, Ch. 2-3; Amir Beck, First-Order Methods in Optimization, SIAM, 2017.
수치적 최적화 알고리즘은 현재 점에서 얻을 수 있는 함수값과 미분 정보를 이용해 새로운 점을 만들고, 이 과정을 반복하여 해에 접근한다. 이 장에서는 개별 알고리즘을 배우기 전에 거의 모든 반복 최적화 방법에서 공통으로 사용하는 언어를 정리한다. 특히 목적함수가 감소한다는 것과 반복점이 수렴한다는 것이 왜 서로 다른 개념인지 살펴보고, 매끄러운 함수의 감소량을 정량적으로 제어하는 Descent Lemma를 유도한다.
최적화 알고리즘의 기본 형태
먼저 다음의 무제약 최적화 문제를 생각한다.
\[\min_{x\in\mathbb{R}^n} f(x).\]반복 최적화 알고리즘은 초기점 $x_0$에서 시작하여 점들의 수열 ${x_k}$를 생성한다. 대표적인 line-search 방법은
\[x_{k+1}=x_k+\alpha_k d_k\]의 형태를 갖는다. 여기서 $d_k$는 이동 방향(direction), $\alpha_k>0$는 이동 크기(step size)이다. 알고리즘을 분석할 때는 다음 세 질문을 분리해서 보아야 한다.
- $d_k$는 목적함수를 줄일 수 있는 방향인가?
- 실제로 선택한 $\alpha_k$가 $f(x_{k+1})<f(x_k)$를 보장하는가?
- 이렇게 만든 수열 ${x_k}$가 원하는 해 또는 정지점으로 수렴하는가?
첫 번째와 두 번째는 한 번의 iteration에서 일어나는 감소성(descent property)에 관한 질문이고, 세 번째는 무한히 많은 iteration의 결과를 다루는 수렴성(convergence)에 관한 질문이다.
감소성의 정의
Descent direction
$f:\mathbb{R}^n\rightarrow\mathbb{R}$가 미분 가능하다고 하자. 점 $x$에서 방향 $d$가
\[\nabla f(x)^T d<0\]을 만족하면 $d$를 $x$에서의 descent direction이라고 한다. Taylor 전개를 사용하면
\[f(x+\alpha d)=f(x)+\alpha\nabla f(x)^T d+o(\alpha)\]이므로, $d$가 descent direction이면 충분히 작은 $\alpha>0$에 대해 $f(x+\alpha d)<f(x)$가 성립한다. 가장 기본적인 선택은 steepest-descent direction
\[d=-\nabla f(x)\]이며, $\nabla f(x)\neq 0$이면 $\nabla f(x)^Td=-\lVert\nabla f(x)\rVert^2<0$이므로 항상 descent direction이다.
Monotone decrease와 sufficient decrease
반복점이
\[f(x_{k+1})\leq f(x_k)\]를 만족하면 목적함수 값의 수열 ${f(x_k)}$가 단조 감소한다고 한다. 그러나 단순한 감소만으로는 한 iteration에서 얼마나 진전했는지 알 수 없다. 예를 들어 감소량이 지나치게 빠르게 $0$으로 줄면 알고리즘은 최적점이 아닌 곳에서도 사실상 멈출 수 있다.
따라서 수렴 증명에서는 보통 어떤 $c>0$와 진전량 $r_k\geq 0$에 대해
\[f(x_k)-f(x_{k+1})\geq c r_k\]와 같은 sufficient decrease 조건을 사용한다. $r_k$가 $\lVert\nabla f(x_k)\rVert^2$처럼 정지성(stationarity)을 측정하는 양이면, 목적함수의 누적 감소량을 통해 gradient가 $0$으로 가는지를 분석할 수 있다.
수렴성의 정의
최적화에서는 서로 다른 대상을 두고 모두 “수렴한다”고 표현하므로 무엇이 수렴하는지 명시해야 한다.
반복점의 수렴
어떤 $x^\star$에 대해
\[\lim_{k\rightarrow\infty}\lVert x_k-x^\star\rVert=0\]이면 반복점 수열 ${x_k}$가 $x^\star$로 수렴한다고 한다. 이는 가장 강하고 직접적인 형태의 수렴이다.
목적함수 값의 수렴
\[\lim_{k\rightarrow\infty}f(x_k)=f^\star\]이면 목적함수 값이 수렴한다고 한다. $f(x_k)$의 수렴만으로 $x_k$ 자체의 수렴이 보장되지는 않는다. 같은 함수값을 갖는 점이 여러 개이거나 수열이 하나의 level set 위에서 계속 움직일 수 있기 때문이다.
정지성으로의 수렴
미분 가능한 무제약 문제에서는 보통
\[\lim_{k\rightarrow\infty}\lVert\nabla f(x_k)\rVert=0\]을 보이는 것을 일차적인 수렴 목표로 삼는다. 다만 $\nabla f(x^\star)=0$은 $x^\star$가 정지점이라는 뜻일 뿐, 일반적인 비볼록 문제에서는 local minimum임을 보장하지 않는다. 반면 $f$가 convex이면 모든 정지점은 global minimum이다.
또한 $f(x_k)$가 단조 감소하고 아래로 유계이면 실수 수열 ${f(x_k)}$는 어떤 값으로 수렴한다. 하지만 이 사실만으로는 그 극한값이 $f^\star$인지, $\nabla f(x_k)$가 $0$으로 가는지 알 수 없다. 감소성과 수렴성을 구분해야 하는 이유가 바로 여기에 있다.
수렴속도
$e_k=\lVert x_k-x^\star\rVert$를 $k$번째 iteration의 오차라고 하자. 충분히 큰 $k$에 대해
\[e_{k+1}\leq C e_k^p\]를 만족하는 $C>0$가 존재하면 수렴 차수(order)를 $p$라고 한다.
- $p=1$이고 $0<C<1$이면 linear convergence이다.
- $e_{k+1}/e_k\rightarrow 0$이면 superlinear convergence이다.
- $p=2$이면 quadratic convergence이다.
수렴성은 결국 해에 도달하는지를 말하고, 수렴속도는 오차가 iteration마다 얼마나 빠르게 줄어드는지를 말한다. 실제 알고리즘 비교에서는 한 iteration의 비용도 함께 고려해야 하므로, 빠른 수렴 차수가 항상 짧은 실행 시간을 의미하는 것은 아니다.
L-Smooth Functions
미분 가능한 함수 $f:\mathbb{R}^n\rightarrow\mathbb{R}$에 대하여 어떤 $L>0$가 존재하여 모든 $x,y\in\mathbb{R}^n$에 대해
\[\lVert\nabla f(y)-\nabla f(x)\rVert\leq L\lVert y-x\rVert\]가 성립하면 $f$를 $L$-smooth function이라 한다. 즉 $f$가 $L$-smooth하다는 것은 gradient $\nabla f$가 $L$-Lipschitz continuous하다는 뜻이다. 상수 $L$을 smoothness constant라 하며, 이 조건은 함수값 자체가 Lipschitz continuous하다는 조건과는 다르다.
$L$-smoothness는 gradient의 변화율, 즉 함수의 곡률이 전역적으로 제한되어 있다는 의미이다. $f$가 두 번 연속 미분 가능하면 다음 Hessian bound와 동치이다.
\[\lVert\nabla^2 f(x)\rVert_2\leq L \qquad \text{for every }x\in\mathbb{R}^n.\]따라서 Hessian의 모든 eigenvalue $\lambda_i(\nabla^2f(x))$는
\[\left\lvert\lambda_i(\nabla^2f(x))\right\rvert\leq L\]을 만족한다. 특히 $f$가 convex이면 $0\preceq\nabla^2f(x)\preceq LI$로 쓸 수 있다.
Descent Lemma
정리
$f$가 미분 가능하고 $\nabla f$가 $L$-Lipschitz continuous이면 모든 $x,y\in\mathbb{R}^n$에 대해
\[f(y)\leq f(x)+\nabla f(x)^T(y-x)+\frac{L}{2}\lVert y-x\rVert^2\]가 성립한다. 즉 $f(y)$는 $x$에서의 일차 Taylor 근사와 이차 오차항으로 위에서 제한된다.
증명
$d=y-x$라 두고 $g(t)=f(x+td)$를 정의하면 미적분학의 기본정리에 의해
\[f(y)-f(x)=\int_0^1\nabla f(x+td)^T d\,dt\]이다. 우변에 $\nabla f(x)^Td$를 더하고 빼면
\[f(y)-f(x) =\nabla f(x)^Td +\int_0^1\left(\nabla f(x+td)-\nabla f(x)\right)^Td\,dt.\]Cauchy–Schwarz 부등식과 Lipschitz 조건을 적용하면
\[\begin{aligned} \left(\nabla f(x+td)-\nabla f(x)\right)^Td &\leq \lVert\nabla f(x+td)-\nabla f(x)\rVert\lVert d\rVert \\ &\leq Lt\lVert d\rVert^2. \end{aligned}\]따라서
\[f(y)-f(x) \leq \nabla f(x)^Td+\int_0^1Lt\lVert d\rVert^2dt =\nabla f(x)^Td+\frac{L}{2}\lVert d\rVert^2\]이고, $d=y-x$를 대입하면 정리의 부등식을 얻는다.
Gradient Descent에 적용
gradient descent의 한 iteration
\[x_{k+1}=x_k-\alpha\nabla f(x_k)\]에 Descent Lemma를 적용하자. $y=x_k-\alpha\nabla f(x_k)$를 대입하면
\[f(x_{k+1}) \leq f(x_k)-\alpha\left(1-\frac{L\alpha}{2}\right) \lVert\nabla f(x_k)\rVert^2\]을 얻는다. 따라서 $0<\alpha<2/L$이면 $\nabla f(x_k)\neq 0$인 모든 점에서 목적함수가 감소한다. 특히 $0<\alpha\leq 1/L$이면
\[f(x_{k+1}) \leq f(x_k)-\frac{\alpha}{2}\lVert\nabla f(x_k)\rVert^2\]라는 sufficient-decrease 조건을 얻는다.
$f$가 아래로 유계이고 하한을 $f_{\inf}$라 하면, 위 부등식을 $k=0$부터 $N-1$까지 더하여
\[\frac{\alpha}{2}\sum_{k=0}^{N-1}\lVert\nabla f(x_k)\rVert^2 \leq f(x_0)-f(x_N) \leq f(x_0)-f_{\inf}\]를 얻는다. $N\rightarrow\infty$로 보내면 gradient norm의 제곱합이 유한하므로
\[\lVert\nabla f(x_k)\rVert\rightarrow 0\]이다. 이 논증은 Descent Lemma가 단순히 목적함수의 감소만 보이는 도구가 아니라, 충분한 감소량을 누적하여 알고리즘의 정지점 수렴을 증명하는 핵심 도구임을 보여준다.
Summary
이 장의 핵심은 다음과 같다. descent direction은 한 점에서 목적함수를 줄일 수 있는 방향이고, sufficient decrease는 실제 iteration에서 정량적인 감소량을 보장한다. 목적함수 값의 감소 또는 수렴은 반복점과 gradient의 수렴을 자동으로 보장하지 않는다. $L$-Lipschitz gradient 가정 아래 Descent Lemma는 함수값을 이차 상한으로 제어하며, 이를 gradient descent에 적용하면 $0<\alpha<2/L$에서 감소성을, $0<\alpha\leq 1/L$에서 gradient norm이 $0$으로 가는 충분한 감소 부등식을 얻을 수 있다.