[draft] Optimization Variants

Gradient Descent Variants

---

• loss.backward()

  • 매개변수의 gradients 계산

• Optimizer.step()

  • 매개변수 갱신

• step size == learning rate

---

Gradient Descent Optimization Algorithms (BGD vs SGD)

• Neural network의 weight을 조절하는 방법은 보통 Gradient Descent를 사용

• BGD (Batch Gradient Descent)

  • 1 step = whole traing data(batch)에 대해 Loss 계산
  • 너무 많은 계산량이 필요

• SGD (Stochastic Gradient Descent, 또는 Naive SGD)

  • batch가 아닌 batch의 일부(mini-batch)에 대해 Loss 계산
  • batch에 비해 정확성이 떨어질 수는 있으나, 계산속도가 훨씬 빠르고, step이 반복될수록 대개 batch의 결과와 유사하게 수렴한다.
  • batch에 비해 local minima에 빠지지 않고 더 좋은 방향으로 수렴할 가능성이 있다.
  • Learning Rate가 slowly decreased(annealing) 할 때, BGD와 같이 수렴함

• Momentum

  • Gradient Descent의 과정에서 '관성'을 고려한다.
  • Momentum = accumulated gradient (가속도를 계속 더하면 속도)
  • gamma = decay parameter(momentum)
  • time step t에서의 이동 벡터가 v(t)일 때, v(t) = gamma * v(t_previous) + gradient_step(theta)
  • theta_next = theta - v(t)
  • gamma는 momentum의 정도를 나타내는 term으로, 보통 0.9로 사용
  • SGD가 Oscilation(진동)문제를 겪을 때 효과적인 방법이다.
  • Local minima를 빠져나올 수 있게 된다.
  • Smoothing 효과가 있다.
  • 과거 이동 벡터를 변수별로 저장해야 하므로, 변수에 대한 메모리가 기존의 두 배로 필요하게 된다.

• Nesterov Momentum (NAG, Nestrov Accelerated Gradient)

  • Momentum을 기반으로 변형한 방법이다.
  • 기존 Momentum이 현재 위치에서의 gradient step과 momentum step을 독립적으로 계산했다면, NAG는 momentum step을 먼저 이동한 위치에서 gradient step을 수행한다.
  • time step t에서의 이동 벡터가 v(t)일 때, v(t) = gamma * v(t_previous) + gradient_step(theta - gamma * v(t_previous))
  • theta_next = theta - v(t)
  • 기존 Momentum 방식이 멈춰야 할 시점에서 관성에 의해 멈추지 않는 단점을 보완해, 모멘텀으로 먼저 이동한 후 어떤 방식으로 이동할 지 결정하는 방식으로 제동을 건다.

• Adagrad (Adaptive Gradient)

  • 각 변수마다 step size를 다르게 설정해서 이동하는 방식
  • 지금까지 많이 변화하지 않은 변수들은 step size를 크게 하고, 많이 변화했던 변수들은 step size를 작게 하는 방법
  • 변수마다의 변화도는 변수마다 accumulate two norm gradient
  • 많이 변화한 변수들은 optimum에 있을 확률이 높기에 세밀하게 변화하고, 많이 변화하지 않은 변수들은 optimum까지 더 많이 변화할 확률이 높기에 더 급격하게 변화하는 방식
  • G(t) = gradient의 제곱 누적합, G(t) = G(t_previous) + gradient(theta)^2
    • per-parameter sum of squared gradients
  • theta_next = theta - step_size/root(G(t) + epsilon) * gradient(theta)
  • 분모가 0이 되는 것을 방지(prevent numerical stability)하기 위해 더해주는 변수 = epsilon
  • 학습을 진행하면서 step size decay를 신경쓰지 않아도 되는 장점 (보통 0.01로 설정한 후 자동으로 수행)
  • 학습을 계속 진행할 때 G(t)가 무한정 커지면서 step size가 지나치게 줄어든다는 문제점

• RMSProp

  • Adagrad를 기반으로 변형한 방법이다.
  • Adagrad 방법이 무한정 커지는 단점을 개선하기 위해, G(t) 계산의 합을 지수이동평균으로 대체하는 방법이다.
  • 지수이동평균이란 최근 값을 더 잘 반영하기 위해, 최근 값과 이전 값에 각각 가중치를 주어 계산하는 방법이다.
  • gamma = alpha parameter of RMSprop function = decay(smooth) rate
  • gamma는 보통 0.9, 0.99, 0.999로 쓴다.
  • G(t) = gamma * G(t_previous) + (1 - gamma) * gradient(theta)^2
  • alpha * A + (1-alpha) * B = Convex combination

• Adam (Adaptive Moment Estimation)

  • RMSProp기법(Decaying accumulated gradient)에 Momentum기법(moving average)을 더한 방식
    • 즉, Decaying Accumulated gradient with momentum
  • standard한 방법
  • momentum(t) = beta1 * momentum(t_previous) + (1 - beta1) * gradient(theta)
  • RMSProp(t) = beta2 * RMSProp(t_previous) + (1 - beta2) * gradient(theta)^2
  • theta(t) = theta - step_size * momentum(t_previous) / root(RMSProp(t_previous) + epsilon)

• SGD의 변형 First-order-optimization

  • Adagrad, RMSProp, Adam ...
  • Momentum, Nestrov Momentum

• Implementation in Pytorch

  • SGD function
    • SGD (params, lr, weight_decay, dampening)
    • Momentum, NAG (momentum(float), nesterov(boolean))
  • Adagrad function
    • Adagrad (params, lr, lr_decay, weight_decay, initial_Accumulator_value, eps)
  • RMSProp function
    • RMSprop(params, lr, alpha, eps, weight_decay, momentum, centered)
  • Adam function
    • Adam(params, lr, betas(,), eps, weight_decay, amsgrad)

• per-parameter adaptive learning rate methods는 learning rate 자체를 변경하는 것이 아님

• Learning Rate Annealing (LR 담금질)

  • lr_scheduler.StepLR(optimizer, step_size, gamma)
    • the more step, the less Learning-rate
  • lr_scheduler.MultiStepLR(optimizer, milestones, gamma)
    • milestones = [], specify the epochs when we reduce the lr
  • lr_scheduler.ExponentialLR(optimizer, gamma)
    • decay every epoch

• second order method

  • two gradient를 사용하며, 특히 weight 수가 많을 때 쓰지 않는다.
  • Newton Rapson Method는 Taylor Series에 기반하여 loss를 approximate한다.
  • First order method와 비교해서 minima search가 빠르지만, Hessian Matrix를 계산하는 것이 비생산적이다.