경사하강법

1. 개요

경사하강법 Gradient Descent
분류	1차 반복 최적화 알고리즘
필요 정보	목적함수의 1차 기울기(gradient)
수렴 차수	선형(1차) — 강볼록 가정 하
최초 제안	코시(A. L. Cauchy), 1847년
대표 응용	기계학습 학습, 위상 최적화, 역문제

산에서 안개 속에 갇혔다면? 발밑에서 가장 가파른 내리막을 골라 한 걸음씩 내려가라. 골짜기가 하나뿐이라면 언젠간 도착한다.

경사하강법(gradient descent, 최급강하법)은 미분 가능한 목적함수 $f(\mathbf{x})$의 최솟값을 찾기 위해, 현재 위치에서의 기울기 $\nabla f$의 반대 방향으로 반복적으로 이동하는 1차 최적화 알고리즘이다. 갱신식은 민망할 정도로 단순하다.

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

여기서 $\eta_k > 0$가 스텝 크기(step size)이며, 기계학습 바닥에서는 학습률(learning rate)이라 부른다. 기울기가 함수값이 가장 빠르게 증가하는 방향이라는 사실 하나에서 알고리즘 전체가 유도되므로, 최급강하법(steepest descent)이라는 이름도 함께 쓴다.

이 조잡해 보이는 방법이 21세기 들어 세상에서 가장 많이 실행되는 수치 알고리즘 자리에 오른 이유는 명확하다. 2차 미분(기울기의 자코비안 행렬, 즉 헤시안)을 요구하지 않기 때문에 미지수가 수억 개여도 메모리가 버틴다. 뉴턴-랩슨법이 우아하지만 $n \times n$ 헤시안을 저장하고 분해해야 하는 것과 대조적이다.

2. 왜 기울기 반대 방향인가

$\mathbf{x}$ 근처에서 테일러 급수로 1차 전개하면

$$f(\mathbf{x} + \mathbf{d}) \approx f(\mathbf{x}) + \nabla f(\mathbf{x})^{\mathsf{T}} \mathbf{d}$$

이다. 이동 거리 $\|\mathbf{d}\|$를 고정한 채 우변을 최소화하는 방향은 코시-슈바르츠 부등식에 의해 $\mathbf{d} \propto -\nabla f$일 때다. 즉 경사하강 방향은 국소적으로 최선의 방향이다.

문제는 “국소적으로만” 최선이라는 것. 등고선이 길쭉한 타원인 계곡에서는 최급강하 방향이 계곡 축을 향하지 않고 벽을 향해 비스듬히 꽂히므로, 궤적이 지그재그로 튕기며 골짜기를 따라 기어간다. 이 지그재그가 경사하강법의 모든 고통의 근원이다.

3. 수렴 속도와 조건수

$f$가 $\mu$-강볼록이고 기울기가 $L$-립시츠 연속일 때, 고정 스텝 $\eta = 2/(L+\mu)$를 쓰면

$$\|\mathbf{x}_k - \mathbf{x}^*\| \le \left(\frac{\kappa - 1}{\kappa + 1}\right)^{k} \|\mathbf{x}_0 - \mathbf{x}^*\|$$

가 성립한다. 여기서 $\kappa = L/\mu$는 헤시안의 조건수다. 이 식이 말하는 바는 잔인하다.

• $\kappa = 1$(완벽한 원형 등고선)이면 수축률이 0, 즉 한 번에 도착한다.
• $\kappa = 1000$이면 수축률이 약 0.998이다. 오차를 10배 줄이는 데만 약 1150회의 반복이 필요하다($\ln 10 / \ln(1001/999)$).

수렴 차수 자체는 선형(1차)이라 뉴턴-랩슨법의 2차 수렴에 한참 못 미친다. 대신 반복 1회의 비용이 압도적으로 싸다. 그래서 실무 선택은 늘 “비싼 반복 적게 vs 싼 반복 많이”의 교환이며, 미지수가 커질수록 저울은 경사하강 쪽으로 기운다.

스텝 크기 선택도 만만치 않다. 2차 함수에서 $\eta > 2/L$이면 가장 큰 고유값 방향의 오차가 매 반복 $|1-\eta L| > 1$배로 커져 발산하고(일반 함수에서는 수렴 보장이 사라진다), 너무 작으면 기어간다. 매 반복 $\eta$를 적당히 찾아주는 것이 선탐색(line search)이며, 아르미호(Armijo, 1966) 조건이나 울프 조건을 만족하는 $\eta$를 백트래킹으로 찾는 방식이 표준이다.

다만 선탐색이 지그재그를 고쳐 주지는 않는다. 2차 함수에서 매번 정확한 최적 스텝을 고르는 최급강하법도 최악의 출발점에서는 함수값 오차가 매 반복 $((\kappa-1)/(\kappa+1))^2$배씩만 줄어든다(Akaike, 1959). 연속한 두 걸음이 서로 직교하면서 같은 두 방향을 번갈아 오가기 때문이다. 아래 검산 표에서 정확한 선탐색이 고정 최적 스텝과 반복 수까지 똑같이 나오는 것이 그 결과다.

4. 주요 변형

원본 경사하강법을 그대로 쓰는 경우는 요즘 거의 없다. 지그재그와 느린 수렴을 때우기 위한 개조판들이 사실상 표준이 됐다.

• 모멘텀(momentum, 폴랴크의 헤비볼 1964): 이전 이동 방향을 관성처럼 누적한다. $\mathbf{v}_{k+1} = \beta \mathbf{v}_k - \eta \nabla f$, $\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{v}_{k+1}$. 계곡 축 방향 성분은 누적되어 커지고, 벽에 부딪히는 진동 성분은 서로 상쇄된다. 최적 매개변수를 쓰면 2차 함수에서 반복 수가 $\sqrt{\kappa}$에 비례하게 줄지만, 이 가속은 2차 함수에서만 보장되고 일반 강볼록 함수에서는 보장되지 않는다.
• 네스테로프 가속(NAG, 1983): 관성으로 먼저 나아간 지점에서 기울기를 평가한다. 볼록 문제에서 함수값 수렴률을 $O(1/k)$에서 $O(1/k^2)$로, 강볼록에서는 반복 수의 $\kappa$ 의존성을 $\sqrt{\kappa}$로 개선한다. 상수배를 빼면 1차 방법이 이론적으로 도달 가능한 하한과 일치한다.
• 확률적 경사하강법(SGD): 뿌리는 로빈스-먼로(1951)의 확률적 근사법이다. 전체 데이터의 기울기 대신 무작위 소표본(미니배치)의 기울기를 쓴다. 한 걸음이 부정확해지는 대신 걸음 수를 수백 배 늘릴 수 있다. 부정확함이 오히려 얕은 국소최솟값을 탈출시키는 잡음 역할을 한다는 것이 재밌는 부수효과.¹
• 적응 학습률 계열: AdaGrad, RMSProp, Adam(킹마·바, 2015)은 좌표별로 과거 기울기 크기를 누적해 학습률을 자동 조절한다. 스케일이 제각각인 파라미터를 다룰 때 사실상 필수.
• 준-뉴턴법으로의 진화: 기울기 이력으로 헤시안 역행렬을 근사하면 BFGS, 메모리를 제한하면 L-BFGS다. 중규모 결정론적 문제에서는 여전히 최강자다.

5. 검산 — 조건수가 반복 수를 얼마나 먹나

$f(x,y) = \tfrac12(x^2 + \kappa y^2)$ 즉 $\mu = 1$, $L = \kappa$인 2차 함수에서 오차 $\|\mathbf{x}_k - \mathbf{x}^*\|$를 처음의 $10^{-6}$배로 줄이는 반복 수를 직접 세면 이렇다. 고정 스텝·정확한 선탐색은 최악 출발점 $(\kappa, 1)$, 나머지는 $(1,1)$에서 출발했다. 헤비볼은 $\eta = 4/(\sqrt L + \sqrt\mu)^2$, $\beta = ((\sqrt\kappa-1)/(\sqrt\kappa+1))^2$, 네스테로프는 $\eta = 1/L$, $\beta = (\sqrt\kappa-1)/(\sqrt\kappa+1)$이다.

$\kappa$	이론 상한	고정 $\eta = 2/(L+\mu)$	고정 $\eta = 1/L$	정확한 선탐색	헤비볼	네스테로프
10	69	69	128	69	27	43
100	691	691	1341	691	93	155
1000	6908	6908	13463	6908	315	508

읽을 것은 세 가지다. 첫째, 2차 함수에서는 위 수렴률 식이 부등식이 아니라 등식으로 맞아 이론값과 실측이 한 자리까지 같다. 둘째, 정확한 선탐색이 고정 최적 스텝보다 한 번도 빠르지 않다(위 Akaike의 결과). 셋째, 모멘텀 계열은 $\kappa$가 10배 될 때 반복 수가 약 $\sqrt{10} \approx 3.2$배만 는다 — 고정 스텝은 10배다. 스텝 경계도 확인했다. $\kappa = 100$에서 $\eta = 1.98/L$은 500회 뒤 오차가 $4\times10^{-5}$로 줄지만, $\eta = 2.02/L$은 같은 500회 뒤 $y$ 성분이 약 $2\times10^{4}$으로 폭주한다($|1 - 2.02| = 1.02$, $1.02^{500} \approx 2\times10^4$).

2차 함수가 목표라면 애초에 경사하강보다 켤레기울기법이 맞다. 같은 $\sqrt\kappa$ 의존성을 매개변수 튜닝 없이 얻고, 정확한 산술에서는 $n$번 안에 끝난다.

6. 시뮬레이션 분야에서의 활용

기계학습이 유명하지만, CAE 바닥에서도 경사하강 계열은 뼈대 알고리즘이다.

위상 최적화와 형상 최적화에서 설계변수는 수십만~수백만 개(요소마다 하나씩)에 달한다. 이 규모에서 헤시안은 논외이므로, 민감도 해석의 수반법(adjoint method)으로 기울기를 한 번의 추가 해석만에 뽑아낸 뒤 경사 기반 갱신으로 설계를 굴린다. “수반법 + 경사하강”이 현대 설계 최적화의 국룰 조합인 이유다.

역문제에서도 마찬가지다. 관측과 시뮬레이션의 잔차 제곱합을 목적함수로 놓고(최소자승법의 비선형 버전), 물성값이나 초기조건을 경사 기반으로 갱신한다. 물리 정보 신경망은 아예 지배방정식 잔차를 손실함수로 삼아 신경망 가중치를 경사하강으로 학습시키는 구조다.

기울기를 어떻게 구하느냐도 중요하다. 유한차분으로 구하면 설계변수 개수만큼 해석을 반복해야 하고 수치미분의 오차 문제까지 얹힌다. 그래서 현대 코드는 자동 미분이나 수반 방정식으로 기울기를 정확하게 뽑는다.

7. 한계

경사하강법은 국소 최적화기다. 볼록하지 않은 목적함수에서는 출발점이 도착점을 결정한다. 전역 최적해를 원하면 유전 알고리즘, 입자 군집 최적화, 담금질 모사 같은 전역 탐색기나 베이지안 최적화를 붙여야 한다.

고차원에서 진짜 골칫거리는 국소최솟값보다 안장점(saddle point)이라는 주장도 힘을 얻었다(Dauphin 외, 2014 — 무작위 행렬 이론과 신경망 실험에 근거한 경험적 논증이지 일반 정리는 아니다). 차원이 높을수록 임계점이 모든 방향으로 볼록할 확률은 급격히 낮아지므로, 대부분의 정체 구간은 안장점 근처의 평평한 고원이다. 모멘텀과 잡음이 여기서 탈출 도구로 기능한다.

부등식 제약이 붙으면 단순 경사하강은 그대로 쓸 수 없고, 사영(projection)을 얹거나 카루시-쿤-터커 조건을 만족하는 해법으로 넘어가야 한다. 목적함수가 미분 불가능하면 열화판인 열경사법(subgradient method)을 써야 하는데, 수렴률이 $O(1/\sqrt{k})$로 떨어진다. 미분 불가능한 부분이 $\ell_1$ 노름처럼 근접 연산자가 싼 항이라면 근접 경사법이 매끄러운 경우의 수렴률을 되찾아 준다. 이 모든 수렴 보장이 기대는 전제는 볼록 최적화 문서에 정리돼 있다.

8. 여담

코시가 1847년 천체 계산을 편하게 하려고 제안한 이 방법은² 150년 넘게 “가장 단순하지만 가장 느린 방법”이라는 다소 무시 섞인 평가를 받았다. 그러다 심층 학습이 미지수 수십억 개짜리 문제를 들고 오면서 상황이 뒤집혔다. 헤시안을 못 쓰는 규모에서는, 느린 1차 방법이 유일하게 실행 가능한 방법이기 때문이다. 알고리즘의 우열이 문제의 크기에 따라 뒤집힌 교과서적 사례다.³

9. 관련 문서

• 수치해석 · 카루시-쿤-터커 조건
• 뉴턴-랩슨법 · 준-뉴턴법
• 조건수 · 수렴성 · 테일러 급수 · 헤세 행렬
• 라인서치 · 울프 조건 · 켤레기울기법
• 확률적 경사하강법 · 근접 경사법 · 볼록 최적화 · 안장점
• 민감도 해석 · 자동 미분
• 위상 최적화 · 형상 최적화 · 역문제
• 유전 알고리즘 · 입자 군집 최적화 · 베이지안 최적화
• 물리 정보 신경망 · 최소자승법

10. Footnotes

1. 그래서 SGD의 잡음을 “버그가 아니라 기능”이라고 부른다. 결정론적 경사하강이 얌전히 빠져 죽을 웅덩이를 SGD는 덜덜 떨면서 기어 나온다. 다만 마지막 수렴 구간에서는 이 잡음이 방해가 되므로 학습률을 점차 줄여준다. ↩

2. 코시의 원논문은 Comptes Rendus 25권 536~538쪽, 세 쪽짜리 짧은 노트였다. 천체 궤도 계산에서 여러 관측식을 동시에 만족시키는 값을 찾는 실용적 필요에서 나온 것이지, 최적화 이론을 세우려던 게 아니었다. ↩

3. 비슷한 역전이 크리로프 부분공간법에서도 일어났다. 직접법인 가우스 소거법이 정확하지만, 미지수가 백만을 넘는 순간 “정확한 답을 우주 종말까지 계산할 것인가, 근사해를 오늘 받을 것인가”의 문제가 된다. ↩