7.86 경사 하강법의 원리와 구현

1. 기본 원리

경사 하강법(gradient descent)은 목적 함수 $f: \mathbb{R}^n \to \mathbb{R}$ 의 최소점을 찾기 위해, 현재 점에서 그래디언트의 음의 방향, 즉 함수가 가장 빠르게 감소하는 방향으로 반복적으로 이동하는 1차 최적화 알고리즘이다.

$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)$

여기서 $\alpha_k > 0$ 은 스텝 크기(step size) 또는 학습률(learning rate)이다. 탐색 방향 $\mathbf{d}_k = -\nabla f(\mathbf{x}_k)$ 가 하강 방향임은 다음으로부터 확인된다.

$\nabla f(\mathbf{x}_k)^T \mathbf{d}_k = -\lVert \nabla f(\mathbf{x}_k) \rVert^2 < 0 \quad (\nabla f(\mathbf{x}_k) \neq \mathbf{0})$

2. 최급경사 방향의 최적성

모든 단위 방향 $\mathbf{d}$ ( $\lVert \mathbf{d} \rVert = 1$ ) 중에서 방향 도함수 $D_{\mathbf{d}} f = \nabla f^T \mathbf{d}$ 를 최소화하는 방향은 코시-슈바르츠 부등식에 의해 다음과 같다.

$\mathbf{d}^* = -\frac{\nabla f(\mathbf{x}_k)}{\lVert \nabla f(\mathbf{x}_k) \rVert}$

이는 그래디언트의 음의 정규화 방향, 즉 최급경사 방향(steepest descent direction)이다. 경사 하강법은 매 반복에서 국소적으로 가장 빠른 감소를 추구하는 탐욕적(greedy) 전략이다.

3. 고정 학습률에서의 수렴 해석

3.1 리프시츠 연속 그래디언트 조건

$\nabla f$ 가 리프시츠 상수 $L > 0$ 으로 리프시츠 연속이면, 즉 모든 $\mathbf{x}, \mathbf{y}$ 에 대해

$\lVert \nabla f(\mathbf{x}) - \nabla f(\mathbf{y}) \rVert \leq L \lVert \mathbf{x} - \mathbf{y} \rVert$

이 성립하면, 고정 학습률 $\alpha = 1/L$ 에서 다음의 감소 부등식이 보장된다.

$f(\mathbf{x}_{k+1}) \leq f(\mathbf{x}_k) - \frac{1}{2L} \lVert \nabla f(\mathbf{x}_k) \rVert^2$

이 결과로부터 $\sum_{k=0}^{\infty} \lVert \nabla f(\mathbf{x}_k) \rVert^2 < \infty$ 이 성립하므로, $\lVert \nabla f(\mathbf{x}_k) \rVert \to 0$ 이 보장된다.

3.2 볼록 함수에서의 수렴률

$f$ 가 볼록이고 $\nabla f$ 가 $L$ -리프시츠 연속이면, $\alpha = 1/L$ 의 고정 학습률에서 다음의 수렴률이 성립한다.

$f(\mathbf{x}_k) - f(\mathbf{x}^*) \leq \frac{L \lVert \mathbf{x}_0 - \mathbf{x}^* \rVert^2}{2k}$

이는 $O(1/k)$ 의 수렴률로, $\epsilon$ -정확도를 달성하기 위해 $O(1/\epsilon)$ 회의 반복이 필요함을 의미한다.

3.3 강볼록 함수에서의 수렴률

$f$ 가 강볼록 매개변수 $\mu > 0$ 을 갖는 강볼록(strongly convex) 함수이면, 수렴률은 선형으로 향상된다.

$f(\mathbf{x}_k) - f(\mathbf{x}^*) \leq \left(1 - \frac{\mu}{L}\right)^k [f(\mathbf{x}_0) - f(\mathbf{x}^*)]$

수렴률은 조건수 $\kappa = L/\mu$ 에 의존하며, $\kappa$ 가 클수록 수렴이 느려진다. 이는 목적 함수의 등고선이 심하게 길쭉한 타원형일수록 지그재그 현상이 심해져 수렴이 저하되는 현상을 수학적으로 반영한다.

4. 이차 함수에서의 분석

이차 목적 함수 $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T\mathbf{A}\mathbf{x} - \mathbf{b}^T\mathbf{x}$ ( $\mathbf{A} \succ 0$ )에 대해 경사 하강법의 동역학을 정밀하게 분석할 수 있다. 오차 벡터 $\mathbf{e}_k = \mathbf{x}_k - \mathbf{x}^*$ 는 다음과 같이 전파된다.

$\mathbf{e}_{k+1} = (\mathbf{I} - \alpha \mathbf{A})\mathbf{e}_k$

수렴을 위한 필요 충분 조건은 $\mathbf{I} - \alpha \mathbf{A}$ 의 스펙트럼 반지름이 1 미만인 것이며, 이를 만족하는 $\alpha$ 의 범위는 $0 < \alpha < 2/\lambda_{\max}$ 이다. 최적 학습률은 수렴률을 최소화하는 값으로 다음과 같다.

$\alpha^* = \frac{2}{\lambda_{\min} + \lambda_{\max}}$

이때 수렴률은 다음과 같다.

$\rho = \frac{\kappa - 1}{\kappa + 1}$

조건수 $\kappa$ 가 1에 가까우면 한 번의 반복으로 거의 수렴하고, $\kappa \gg 1$ 이면 $\rho \approx 1$ 로 수렴이 극히 느려진다.

5. 구현 변형

5.1 고정 학습률

가장 단순한 구현으로, 모든 반복에서 동일한 $\alpha$ 를 사용한다. 구현이 간단하지만, 최적 학습률이 사전에 알려져 있지 않으면 시행착오가 필요하다. 리프시츠 상수 $L$ 의 추정이 가능하면 $\alpha = 1/L$ 이 안전한 선택이다.

5.2 직선 탐색 기반

매 반복에서 아르미요 역추적 또는 울프 조건을 만족하는 $\alpha_k$ 를 적응적으로 선택한다. 추가적인 함수 평가가 요구되지만, 학습률 선택에 대한 민감도가 감소한다.

5.3 학습률 감쇠(Learning Rate Decay)

반복에 따라 학습률을 점진적으로 감소시키는 스케줄이다.

$\alpha_k = \frac{\alpha_0}{1 + \beta k} \quad \text{또는} \quad \alpha_k = \alpha_0 \gamma^k, \quad 0 < \gamma < 1$

확률적 경사 하강법에서는 잡음의 영향을 줄이기 위해 감쇠 스케줄이 필수적이며, 수렴을 위한 로빈스-먼로(Robbins-Monro) 조건 $\sum \alpha_k = \infty$ , $\sum \alpha_k^2 < \infty$ 가 이론적 기반을 제공한다.

6. 그래디언트 계산의 구현

6.1 해석적 그래디언트

목적 함수의 그래디언트를 수학적으로 유도하여 직접 계산하는 방법이다. 정확하고 효율적이지만, 복잡한 함수에서는 유도가 어려울 수 있다.

6.2 수치 미분

유한 차분(finite difference)을 이용한 근사이다.

전방 차분: $\frac{\partial f}{\partial x_i} \approx \frac{f(\mathbf{x} + h\mathbf{e}_i) - f(\mathbf{x})}{h}$

중심 차분: $\frac{\partial f}{\partial x_i} \approx \frac{f(\mathbf{x} + h\mathbf{e}_i) - f(\mathbf{x} - h\mathbf{e}_i)}{2h}$

$n$ 개의 편미분을 구하기 위해 전방 차분은 $n$ 회, 중심 차분은 $2n$ 회의 추가 함수 평가가 필요하다. 스텝 크기 $h$ 의 선택은 절단 오차와 반올림 오차의 상충 관계에 의해 결정되며, 단정밀도에서는 $h \approx 10^{-4}$ , 배정밀도에서는 $h \approx 10^{-8}$ (전방 차분) 또는 $h \approx 10^{-5}$ (중심 차분)이 권장된다.

6.3 자동 미분

자동 미분(automatic differentiation)은 프로그램의 연산 그래프를 분석하여 정확한 도함수를 기계적으로 계산하는 기법이다. 수치 미분과 달리 근사 오차가 없으며, 해석적 유도의 수고를 피할 수 있다. 역방향 모드(reverse mode) 자동 미분은 그래디언트 계산의 비용이 함수 평가 비용의 상수배( $\leq 5$ 배)로 제한되어, 차원에 무관하게 효율적이다. 로봇 공학에서 CasADi, JAX 등의 프레임워크가 자동 미분을 지원한다.

7. 수렴 진단

경사 하강법의 수렴을 실시간으로 진단하기 위해 다음의 지표가 모니터링된다.

그래디언트 노름: $\lVert \nabla f(\mathbf{x}_k) \rVert$ 가 미리 설정된 허용 오차 $\epsilon$ 이하로 감소하면 수렴으로 판정한다.
목적 함수 변화: $\lvert f(\mathbf{x}_{k+1}) - f(\mathbf{x}_k) \rvert < \epsilon_f$ 이면 정체로 판단한다.
변수 변화: $\lVert \mathbf{x}_{k+1} - \mathbf{x}_k \rVert < \epsilon_x$ 이면 수렴으로 판정한다.

실용적으로는 이 세 기준을 복합적으로 적용하며, 최대 반복 횟수를 추가 종료 기준으로 설정한다.

8. 경사 하강법의 한계

선형 수렴: 최적해 근방에서 선형 수렴에 그치며, 뉴턴법의 이차 수렴에 비해 느리다.
조건수 민감성: 악조건(ill-conditioned) 문제에서 수렴이 극도로 느려진다.
안장점 문제: 비볼록 함수에서 안장점 근방에서의 정체가 발생할 수 있다.
지역 최적: 비볼록 문제에서 국소 최적해에 갇힐 수 있다.

이러한 한계에도 불구하고, 경사 하강법은 구현의 단순성, 낮은 메모리 요구량, 대규모 문제에 대한 확장성으로 인해 로봇 학습과 최적화의 기본 알고리즘으로 널리 사용된다.

9. 참고 문헌

Cauchy, A. (1847). “Méthode générale pour la résolution des systèmes d’équations simultanées.” Comptes Rendus de l’Académie des Sciences, 25, 536–538.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Springer.
Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.

version: 1.0