본문으로 건너뛰기

10. Gradient descent와 line search — 방향과 보폭을 나누어 생각하기

// CORE 4/7 — gradient descent, exact line search, backtracking, Armijo, Wolfe, momentum, Nesterov

Gradient descent는 가장 기본적인 1차 최적화 알고리즘입니다. 핵심은 방향과 보폭을 분리해서 생각하는 것입니다.

Gradient Descent​

업데이트는 다음과 같습니다.

xk+1=xk−αk∇f(xk).x_{k+1}=x_k-\alpha_k\nabla f(x_k).

−∇f(xk)-\nabla f(x_k)는 내려가는 방향이고, αk\alpha_k는 step size입니다. 방향이 맞아도 보폭이 너무 크면 튕겨 나가고, 너무 작으면 지나치게 느립니다.

exact line search는 현재 방향 pkp_k를 정한 뒤, 그 직선 위에서 objective가 가장 작아지는 step size를 찾습니다.

αk=arg⁡min⁡α>0f(xk+αpk).\alpha_k=\arg\min_{\alpha>0} f(x_k+\alpha p_k).

개념적으로 깔끔하지만, 매 반복마다 1차원 최적화 문제를 정확히 풀어야 하므로 비쌀 수 있습니다.

Backtracking​

backtracking은 큰 step에서 시작해 조건을 만족할 때까지 줄입니다.

  1. 초기 α\alpha를 잡는다.
  2. 충분히 감소하지 않으면 α←ρα\alpha\leftarrow\rho\alpha로 줄인다.
  3. 충분히 감소하면 이동한다.

여기서 0<ρ<10<\rho<1입니다. exact line search보다 싸고 robust합니다.

Armijo condition​

Armijo condition은 “예상한 만큼은 내려갔는가”를 확인합니다.

f(xk+αpk)≤f(xk)+c1α∇f(xk)⊤pk.f(x_k+\alpha p_k)\le f(x_k)+c_1\alpha\nabla f(x_k)^\top p_k.

오른쪽은 linear prediction에 여유를 둔 감소량입니다. pkp_k가 descent direction이면 ∇f(xk)⊤pk<0\nabla f(x_k)^\top p_k<0이므로 오른쪽은 f(xk)f(x_k)보다 작습니다.

Wolfe condition​

Wolfe condition은 Armijo의 충분 감소 조건에 curvature condition을 더합니다.

∇f(xk+αpk)⊤pk≥c2∇f(xk)⊤pk.\nabla f(x_k+\alpha p_k)^\top p_k\ge c_2\nabla f(x_k)^\top p_k.

너무 작은 step도 막기 위한 조건입니다. BFGS 같은 quasi-Newton 방법에서는 Wolfe line search가 자주 쓰입니다.

Momentum​

Momentum은 이전 이동 방향을 누적합니다.

vk+1=βvk+∇f(xk),xk+1=xk−αvk+1.v_{k+1}=\beta v_k+\nabla f(x_k),\qquad x_{k+1}=x_k-\alpha v_{k+1}.

긴 골짜기에서는 gradient가 좌우로 흔들리는데, momentum은 일관된 방향을 누적해 더 빠르게 전진하게 만듭니다.

Nesterov​

Nesterov momentum은 먼저 momentum으로 한 발 앞을 본 뒤 그 위치의 gradient를 계산합니다.

vk+1=βvk+∇f(xk−αβvk),v_{k+1}=\beta v_k+\nabla f(x_k-\alpha\beta v_k), xk+1=xk−αvk+1.x_{k+1}=x_k-\alpha v_{k+1}.

직관은 “관성으로 갈 위치를 미리 보고 조정한다”입니다. 딥러닝 최적화에서 자주 쓰이는 가속 아이디어입니다.

선택 기준​

방법장점주의점
fixed step구현 쉬움step tuning 필요
exact line search이론적으로 깔끔매 반복 비용 큼
backtrackingrobust, 구현 쉬움함수 평가 여러 번 필요
Armijo/Wolfe수렴 이론과 잘 맞음parameter 선택 필요
momentum/Nesterov골짜기에서 빠름진동 가능

다음: Newton과 quasi-Newton