3장. 경사하강법의 수렴

다변수 미적분 5장에서 경사하강법 $\mathbf x_{k+1} = \mathbf x_k - \eta\nabla f(\mathbf x_k)$를 배웠습니다. 이 장에서는 “얼마나 빨리 수렴하는가”를 정확히 따집니다. 학습률을 얼마로 잡아야 안전한지, 몇 번 반복하면 오차가 얼마로 줄어드는지, 길쭉한 골짜기에서 왜 느려지는지를 2장의 $L$, $m$, $\kappa$로 답합니다. 논문의 “converges at rate $O(1/k)$”, “linear convergence”를 읽을 수 있게 됩니다.

3.1 하강 보조정리

정리 3.1 (하강 보조정리). $f$가 $L$-매끄러우면(헤세 행렬의 고윳값 $\le L$) 모든 $\mathbf x, \mathbf y$에 대해

함수가 이차함수보다 빨리 휘지 않는다는 뜻입니다. 1장의 1계 조건(접평면이 아래)과 짝을 이루어, 이번에는 이차함수가 위에서 덮습니다.

따름정리 3.2. $\eta \le 1/L$로 경사하강법을 한 번 하면

증명. 정리 3.1에 $\mathbf y - \mathbf x = -\eta\nabla f$를 넣으면 $f(\mathbf x_{k+1}) \le f(\mathbf x_k) - \eta\|\nabla f\|^2 + \frac{L\eta^2}{2}\|\nabla f\|^2$이고, $\eta \le 1/L$이면 $L\eta^2/2 \le \eta/2$입니다. □

그러므로 학습률이 $1/L$ 이하이면 매 단계 함숫값이 반드시 줄어듭니다. 그래디언트가 클수록 많이 줄어듭니다.

3.2 수렴 속도

정리 3.3 (볼록). $f$가 볼록이고 $L$-매끄러우며 $\eta = 1/L$이면

오차가 $1/k$에 비례해 줄어듭니다. 오차를 $\varepsilon$ 이하로 만드는 데 약 $L\|\mathbf x_0 - \mathbf x^*\|^2/(2\varepsilon)$번이 필요합니다. 이를 $O(1/k)$ 수렴이라 씁니다. ($O$는 “상수배를 빼면 이만큼”이라는 뜻입니다.)

정리 3.4 (강볼록). $f$가 $m$-강볼록이고 $L$-매끄러우며 $\eta = 1/L$이면

오차가 매번 일정한 비율로 줄어드는 것을 선형 수렴(linear convergence)이라 합니다. 로그 눈금으로 그리면 직선이 되기 때문에 붙은 이름입니다. 정확도의 자릿수 하나를 얻는 데 약 $\kappa\ln10 \approx 2.3\kappa$번이 듭니다.

$O(1/k)$와 선형 수렴의 차이는 큽니다. 오차를 $10^{-6}$로 줄이려면 $O(1/k)$는 약 $10^6$번 단위가 필요하지만, $\kappa = 10$인 선형 수렴은 약 $140$번이면 됩니다.

3.3 이차함수에서 정확히 보기

$f(\mathbf x) = \frac12\mathbf x^\top A\mathbf x$($A$의 고윳값 $m = \lambda_1 \le \dots \le \lambda_n = L$)이면 경사하강법은

이고, 고유벡터 방향 성분은 매번 $(1 - \eta\lambda_i)$배가 됩니다.

• 모든 $i$에서 $|1 - \eta\lambda_i| < 1$, 곧 $0 < \eta < 2/L$이어야 수렴합니다. 이 범위를 넘으면 가장 가파른 방향에서 진동하며 발산합니다.
• 가장 느린 방향의 수축률 $\max_i|1 - \eta\lambda_i|$를 가장 작게 하는 학습률은 $\eta^* = \frac{2}{m + L}$이고, 그때 수축률은 $\dfrac{\kappa - 1}{\kappa + 1}$입니다.

예제 3.5. $f = x^2 + 50y^2$($\lambda = 2, 100$, $\kappa = 50$). $\eta < 2/100 = 0.02$이어야 수렴하고, 최적 학습률 $\eta^* = 2/102$에서 수축률은 $49/51 \approx 0.96$입니다. $y$ 방향은 가파르고 $x$ 방향은 완만해서, 학습률을 $y$에 맞추면 $x$ 방향으로 아주 느리게 갑니다. 경로는 골짜기 벽 사이를 지그재그로 오갑니다.

3.4 학습률 정하기: 직선 탐색

$L$을 모를 때는 매 단계 학습률을 고릅니다.

알고리즘 3.6 (되돌아가기 직선 탐색, backtracking line search). $\eta$를 큰 값에서 시작해, 아르미호 조건(Armijo condition)

이 성립할 때까지 $\eta \leftarrow \eta/2$로 줄입니다.

따름정리 3.2에 따라 $\eta \le 1/L$이면 조건이 반드시 성립하므로, 몇 번 줄이면 멈춥니다. 딥러닝에서는 함숫값을 매번 정확히 계산하기 비싸서 직선 탐색 대신 학습률 스케줄(5장)을 씁니다.

3.5 이 장의 요약

• $\eta \le 1/L$이면 매 단계 $f$가 $\frac\eta2\|\nabla f\|^2$ 이상 줄어듭니다.
• 볼록: $O(1/k)$. 강볼록: 선형 수렴 $(1 - 1/\kappa)^k$.
• 이차함수: $\eta < 2/L$에서 수렴, 최적 $\eta = 2/(m + L)$, 수축률 $(\kappa - 1)/(\kappa + 1)$.
• 조건수가 크면 지그재그로 느려집니다.

쓰이는 곳. 최적화 논문의 수렴 정리(“Theorem: with step size 1/L, the iterates satisfy…”), 딥러닝의 학습률 선택과 발산(손실이 NaN이 되는 현상), 대규모 언어 모델의 “learning rate warmup” 논의, 물리 시뮬레이션의 에너지 최소화, 공학의 반복 설계 최적화가 이 장의 분석을 씁니다.

문제

0.1

1/12
2/3

0.32

0.99