10.3 1차 최적화 방법

실습 · 연습문제 2개

Heavy ball momentum 구현하기 heavy-ball

Heavy ball 방법은 속도 v\mathbf{v}에 과거 gradient를 누적한다.

vk+1=β vk−η ∇f(xk),xk+1=xk+vk+1,v0=0.\mathbf{v}_{k+1} = \beta\,\mathbf{v}_k - \eta\,\nabla f(\mathbf{x}_k), \qquad \mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{v}_{k+1}, \qquad \mathbf{v}_0 = \mathbf{0}.

함수 heavy_ball(grad, x0, lr, beta, steps)를 완성한다. grad는 점을 받아 gradient를 반환하는 함수다. 반환값은 시작점을 포함한 모든 반복점을 쌓은 배열로, shape은 (steps + 1, n)이다.

테스트는 다음을 확인한다.

  • beta = 0이면 경사하강과 같다.
  • 처음 두 step이 식과 같다.
  • 조건수가 100인 이차함수에서, Polyak의 최적 파라미터 η=4/(L+μ)2\eta = 4/(\sqrt{L} + \sqrt{\mu})^2, β=((κ−1)/(κ+1))2\beta = \big((\sqrt{\kappa} - 1)/(\sqrt{\kappa} + 1)\big)^2를 쓰면 같은 정확도에 도달하는 데 필요한 step 수가 경사하강(η=2/(L+μ)\eta = 2/(L + \mu))보다 5배 이상 적다.
  • β=0.9\beta = 0.9일 때 학습률이 2(1+β)/L2(1 + \beta)/L보다 조금 작으면 수렴하고 조금 크면 발산한다.

이차함수에서 GD의 최대 안정 학습률 max-stable-lr

이차함수

f(x)=12x⊤Hx−b⊤xf(\mathbf{x}) = \frac{1}{2}\mathbf{x}^\top\mathbf{H}\mathbf{x} - \mathbf{b}^\top\mathbf{x}

(H\mathbf{H}는 대칭 양의 정부호)에 학습률 η\eta의 경사하강을 적용한다. 두 함수를 완성한다.

  1. gd_quadratic(H, b, x0, lr, steps): x0\mathbf{x}_0에서 시작해 xk+1=xk−η ∇f(xk)\mathbf{x}_{k+1} = \mathbf{x}_k - \eta\,\nabla f(\mathbf{x}_k)를 steps번 반복한 x\mathbf{x}를 반환한다. ∇f(x)=Hx−b\nabla f(\mathbf{x}) = \mathbf{H}\mathbf{x} - \mathbf{b}다.
  2. max_stable_lr(H): 어떤 시작점에서든 GD가 최솟점 H−1b\mathbf{H}^{-1}\mathbf{b}로 수렴하는 학습률의 상한 ηmax⁡\eta_{\max}를 반환한다. η<ηmax⁡\eta < \eta_{\max}이면 수렴하고 η>ηmax⁡\eta > \eta_{\max}이면 (일반적인 시작점에서) 발산해야 한다.

테스트는 대각이 아닌 H\mathbf{H}에서도 ηmax⁡\eta_{\max}의 0.99배로는 수렴하고 1.01배로는 발산하는지 확인한다.

힌트: 오차 ek=xk−H−1b\mathbf{e}_k = \mathbf{x}_k - \mathbf{H}^{-1}\mathbf{b}는 ek+1=(I−ηH)ek\mathbf{e}_{k+1} = (\mathbf{I} - \eta\mathbf{H})\mathbf{e}_k를 따른다. H\mathbf{H}의 고유벡터 방향마다 오차가 (1−ηλi)(1 - \eta\lambda_i)배가 된다. 모든 ii에서 ∣1−ηλi∣<1\lvert 1 - \eta\lambda_i \rvert < 1이 되는 조건을 구한다.