경사 하강법 (Gradient Descent)

정의

경사 하강법 (Gradient Descent, GD) 은 미분 가능한 목적 함수 f(x) 의 1차 도함수 (gradient) 방향으로 반복 이동하며 극소값 (local minimum) 을 찾는 1차 최적화 알고리즘. 머신러닝 / 딥러닝 학습의 핵심 엔진.

문제 상황과 동기

f(x) 가 복잡하여 closed-form 해 (grad f = 0) 를 구할 수 없음. 특히 고차원 (d >> 1) 에서는 Newton 법 (Hessian 필요) 이 현실적으로 불가능.

• Naive (grid search): 차원당 그리드 M -> M^d. d=1000 이면 천문학적.
• Gradient Descent: grad f 만 있으면 O(d) 반복. 차원에 선형적.

핵심 통찰: 함수가 국소적으로 선형 근사 가능하다면, 반대 방향으로 가면 함수값이 감소한다.

시각화

핵심 아이디어

x_{t+1} = x_t - eta * grad f(x_t)

• eta (learning rate / step size): 한 step 의 크기
• grad f(x_t): x_t 에서의 gradient (가장 가파른 증가 방향)
• -grad f(x_t): 가장 가파른 감소 방향

Convex 함수: 전역 최소로 수렴 보장. Non-convex: saddle point / local min 에 빠질 수 있음.

알고리즘

1. 초기 x0, learning rate eta 설정
2. for t = 0, 1, ... until convergence:
3.   g = grad f(x_t)
4.   x_{t+1} = x_t - eta * g
5.   if ||g|| < eps: break
6. return x_t

구현

// Gradient descent: f(x,y) = x^2 + 2y^2 (convex)
#include <bits/stdc++.h>
using namespace std;
int main() {
  double x = 3.0, y = 2.0;
  double lr = 0.1;
  int max_iter = 100;
  for (int i = 0; i < max_iter; i++) {
      double gx = 2 * x;
      double gy = 4 * y;
      x -= lr * gx;
      y -= lr * gy;
      cout << i << " " << x << " " << y << " "
           << (x*x + 2*y*y) << "\n";
  }
}

# Gradient descent: f(x,y) = x^2 + 2y^2
x, y = 3.0, 2.0
lr = 0.1
for i in range(100):
  gx, gy = 2*x, 4*y
  x -= lr * gx
  y -= lr * gy
  print(i, f"{x:.6f}", f"{y:.6f}", f"{x*x + 2*y*y:.6f}")

0 2.400000 1.200000 8.640000
1 1.920000 0.720000 4.723200
2 1.536000 0.432000 2.613888
...
98 0.000694 0.000014 4.894e-07
99 0.000555 0.000008 3.187e-07

복잡도

변형 / 활용

머신러닝 (Linear Regression, Logistic Regression, Neural Network), 최적제어, 로봇 공학.

수렴 분석 (Convex Case)

f(x) = x^2 + 2y^2 은 strongly convex (Hessian = diag(2,4) > 0). GD 는 linear rate 로 수렴:

||x_t - x*|| <= c^t * ||x_0 - x*||,   c = max(|1 - eta*L|, |1 - eta*mu|)

• L = 4 (최대 eigenvalue), mu = 2 (최소 eigenvalue)
• eta = 0.1 -> c = max(0.6, 0.8) = 0.8
• 100 step 후 오차: 0.8^100 ~ 2e-10

함정

1. Learning Rate 선택

eta 가 너무 크면 발산, 너무 작으면 수렴 느림. 보통 0.01 ~ 0.001 에서 시작.

2. Saddle Point

고차원에서는 local min 보다 saddle point 가 문제. grad f = 0 이지만 극소가 아님. momentum / Adam 으로 완화.

3. Feature Scaling

차원 간 scale 이 다르면 gradient 방향이 왜곡됨. 모든 feature 를 같은 scale 로 정규화 필요.

BOJ 연습 문제

참고

• 휴리스틱
• 담금질 기법