경사 하강법 (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 에 빠질 수 있음.

알고리즘

반복 갱신 흐름:

flowchart LR
    Init["x0 초기화, eta 설정"] --> Grad["gradient g = grad f(x)"]
    Grad --> Update["x = x - eta * g"]
    Update --> Check{"수렴 조건 충족?"}
    Check -->|"No"| Grad
    Check -->|"Yes"| Result["x 반환"]

수렴 조건 예시: ||g|| < eps 또는 |f(x_t) - f(x_{t-1})| < eps.

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: MSE loss 의 gradient 는 X^T(Xw - y), GD 로 최소화
• Logistic Regression: log loss 의 gradient, closed-form 없음 -> GD 필수
• Neural Network: backpropagation 으로 gradient 계산 + SGD/Adam 으로 갱신
• 최적제어, 로봇 공학: 목적함수 (에너지, 오차) 최소화

학습률 스케줄링

학습률을 고정하지 않고 훈련 진행에 따라 조절:

수렴 분석 (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 (Hessian 최대 eigenvalue = Lipschitz 상수)
• mu = 2 (Hessian 최소 eigenvalue = strong convexity 상수)
• eta = 0.1 일 때: c = max(|1 - 0.4|, |1 - 0.2|) = max(0.6, 0.8) = 0.8
• 100 step 후 오차: 0.8^100 ≈ 2e-10

최적 eta = 2/(L+mu) = 2/6 ≈ 0.333 이면 c = (L-mu)/(L+mu) = 2/6 ≈ 0.333 으로 수렴 최대화.

함정

1. Learning Rate 선택

eta 가 너무 크면 발산, 너무 작으면 수렴 느림.

eta 크다: x 가 최소점을 넘어 진동 또는 발산
eta 작다: 수렴하지만 iteration 이 너무 많이 필요
적정 eta: f(x) 의 Lipschitz 상수 L 에 대해 eta <= 1/L 이면 수렴 보장 (convex smooth)

실용적 시작점: eta = 0.01 ~ 0.001. Grid search 또는 learning rate finder (lr_find) 활용.

2. Saddle Point

고차원 최적화에서는 local minimum 보다 saddle point (모든 방향으로 gradient 가 0 이지만 극소가 아닌 지점) 가 훨씬 많음. Gradient 가 0 이어도 수렴했다고 단정 금물.

Momentum 이나 Adam 을 쓰면 saddle point 탈출이 더 쉬움. SGD 의 노이즈도 saddle 탈출에 도움.

3. Feature Scaling

차원 간 scale 이 다르면 gradient 방향이 왜곡됨: 값이 큰 차원으로 지나치게 편향.

예: x1 범위 [0, 1000], x2 범위 [0, 1]
gradient 는 x1 방향으로 훨씬 크게 계산 -> eta 선택 어려움, 수렴 느림

해결: StandardScaler (zero mean, unit variance) 또는 MinMaxScaler 적용.

4. Vanishing / Exploding Gradient

깊은 신경망에서 gradient 가 역전파 시 지수적으로 작아지거나 (vanishing) 커짐 (exploding). 대응:

• Batch Normalization
• Gradient Clipping (exploding 방지)
• ResNet 스킵 연결 (vanishing 완화)

5. 수렴 판정의 어려움

||grad|| < eps 는 필요 조건이지 충분 조건이 아님. saddle point 에서도 성립. 실무에서는 validation loss 가 더 이상 감소하지 않는 지점 (early stopping) 을 사용.

수렴 속도 비교

f(x) = x^2 + 2y^2 (strongly convex, L=4, mu=2):

BOJ 연습 문제

GD vs 다른 최적화 기법

GD 는 미분 가능한 고차원 연속 최적화에서 사실상 표준.

참고

• 휴리스틱
• 담금질 기법
• Cauchy, “Methode generale pour la resolution des systemes d’equations” (1847)
• Rumelhart, Hinton, Williams, “Learning representations by back-propagating errors” (1986)