PaperlayerView exact revision on arXiv

Source-linked AI summary

ADAM: A METHOD FOR STOCHASTIC OPTIMIZATION

arXiv:1412.6980v9

TL;DR

Stochastic objective function은 효율적인 gradient 기반 최적화를 요구하며, 특히 대규모·고차원 machine-learning 문제에서 그러하다. Adam은 adaptive first- 및 second-moment 기반 learning rate로 이를 해결하며, 실험 결과 다양한 non-convex optimization 문제에서 강건하고 폭넓게 적합한 것으로 나타난다.

  • 문제

    Stochastic objective function은 대규모·고차원 환경에서 효율적인 gradient 기반 최적화를 필요로 한다.

  • 방법

    Adam은 first-order gradient와 gradient의 first 및 second moment 추정값으로 계산한 adaptive per-parameter learning rate를 사용한다.

  • 결과

    실험 결과 Adam은 다양한 model과 dataset에서 다른 방법을 일관되게 능가하며, 폭넓은 non-convex optimization 문제에서 강건한 것으로 나타난다.

  • 시사점 및 한계

    Adam은 간단하고 memory-efficient한 optimizer로, 대규모 dataset 또는 고차원 parameter space를 다루는 machine-learning 문제에 적합하다.

  • 시사점 및 한계

    Sparse gradient에서는 신뢰할 수 있는 second-moment 추정값을 위해 작은 β2가 필요할 수 있으므로, 초기 step이 과도하게 커지는 것을 막으려면 initialization-bias correction이 중요하다.

Abstract

from arXiv · show

1 서론

서론은 Adam을 일차 gradient와 적은 메모리만 필요로 하는 효율적인 stochastic optimization method로 제시한다. gradient moment에서 adaptive learning rate를 도출하고, AdaGrad와 RMSProp에 연관된 장점을 결합하며, 여러 model과 dataset에서 일관된 성능을 보인다고 보고한다.

  • 동기: Stochastic gradient-based optimization은 미분 가능한 scalar objective를 다루며, 과학과 공학에서는 gradient descent가 비교적 효율적인 접근법을 제공한다.서론에서는 이러한 문제를 parameterized objective function의 maximization 또는 minimization으로 규정한다.
  • 기여: Adam은 일차 gradient와 적은 메모리만 필요로 하면서, 일차 및 이차 moment 추정값으로부터 parameter별 adaptive learning rate를 계산한다.명칭은 adaptive moment estimation에서 유래한다.
  • 기여: Adam은 sparse gradient에서 AdaGrad의 효과성과 RMSProp의 adaptive learning-rate 동작을 결합하도록 설계되었다.서론에서는 AdaGrad 와 RMSProp을 동기를 제공한 method로 지목한다.
  • 범위와 주장: Adam은 large-scale, high-dimensional machine learning에 다목적으로 사용할 수 있는 방법으로 제시되며, 다양한 model과 dataset에서 일관된 실증적 개선을 보였다고 보고된다.또한 논문은 initialization bias correction technique을 소개하고 online convex programming에서 Adam의 convergence를 분석한다.

2 알고리즘

Adam은 stochastic gradient의 first- 및 second-moment estimate를 적응적으로 갱신해 미분 가능한 noisy objective의 기댓값을 최소화한다. Bias correction은 0으로 초기화할 때 발생하는 편향을 보정하며, normalized update는 유효 step을 base stepsize α에 대해 대략 bounded하게 유지한다.

  • 2 알고리즘: Adam은 연속적인 timestep에 걸쳐 관측된 실현값을 사용해 미분 가능한 확률적 objective의 기대값을 최소화한다.무작위 minibatch 또는 다른 원천을 평가할 때 stochasticity가 발생할 수 있다.
  • 2 ALGORITHM: 이 알고리즘은 β1과 β2로 제어되는 exponential moving averages로 gradient와 squared gradient를 유지해 first 및 second raw moment를 추정한다.두 평균이 모두 0에서 시작하므로 Adam은 초기 편향이 0을 향하는 현상을 보정한다.
  • 2 알고리즘: Adam의 정규화된 update는 일반적으로 유효 크기가 α로 대략 제한되며, 현재 parameter 값 주변에 trust region을 설정한다.따라서 많은 machine-learning model에서는 α의 적절한 scale을 사전에 비교적 쉽게 결정할 수 있다.

3 초기화 편향 보정

Adam은 exponential moving average에서 초기화 편향을 보정하기 위해, 기대 second-moment 추정값이 실제 second moment와 어떻게 다른지 유도한 뒤 그 결과로 얻은 영 초기화 인자로 나눈다. 이 보정은 sparse gradients에서 특히 중요하다. 이 경우 작은 β2가 필요하지만, 그렇지 않으면 초기 step이 지나치게 커지기 때문이다.

  • 3 초기화 편향 보정: Adam은 제곱된 stochastic gradients의 exponential moving average로부터 second-moment 초기화 편향 보정을 유도하며, first-moment 유도도 이와 유사하다.running estimate는 영으로 초기화되므로, 초기 기대값은 실제 second raw moment와 같지 않다.
  • 3 초기화 편향 보정: (1 − β2^t)로 나누면 second-moment running average를 영으로 초기화하여 발생한 편향이 보정된다.이 보정은 영 초기화 항을 분리한 뒤 Adam의 algorithm에 도입된다.
  • 3 초기화 편향 보정: sparse gradients에서는 신뢰할 수 있는 second-moment 추정값을 얻으려면 작은 β2로 많은 gradient를 평균해야 한다.초기화 편향 보정이 없으면, 같은 작은 β2 설정에서 초기 step이 훨씬 커진다.

4 수렴 분석

분석에서는 Adam을 online-learning 알고리즘으로 보고, gradient와 iterate가 bounded라는 가정하에 regret 보장을 확립한다. 또한 adaptive method가 sparse feature의 이점을 얻으며, 첫 번째 모멘트 계수를 감쇠하는 것이 수렴에 중요함을 보인다.

  • Adam은 Zinkevich (2003)의 online-learning framework에서 분석되며, 알려지지 않은 convex cost function열에 대한 regret를 통해 성능을 평가한다.
  • gradient와 parameter distance가 bounded이고 β1, β2 조건이 적절하면, Theorem 4.1은 Adam에 가장 잘 알려진 general convex online-learning bound에 필적하는 regret bound를 부여한다.이 정리는 learning rate가 감쇠하고 β1,t가 exponentially decaying일 때 적용된다.
  • gradient가 bounded인 sparse data에서는 Adam의 summation term이 generic upper bound보다 substantially smaller일 수 있으며, 이는 Duchi et al. (2011)의 feature setting과 같다.이들의 expected-norm 결과도 Adam에 적용된다.
  • Adam과 Adagrad 같은 adaptive method는 O(log d)의 dependence를 달성할 수 있어, non-adaptive method의 O(√d)보다 향상된다.
  • β1,t를 0을 향해 감쇠하는 것은 이론적 분석에 중요하며, training 후반에 momentum을 줄이면 수렴이 개선될 수 있다는 empirical finding과도 일치한다.
  • 이 분석은 gradient와 parameter distance가 bounded일 때 Adam의 average regret가 converges함을 증명한다.이 결과는 Theorem 4.1에서 따른다.

5 관련 연구

Adam은 RMSProp, AdaGrad 및 curvature-adaptive stochastic optimizer들과 관련되지만, moment 기반 update, bias correction, memory profile에서 차이를 보인다. 또한 data-geometry-adaptive preconditioner를 통해 natural gradient descent와 유사하다.

  • Adam은 RMSProp 및 AdaGrad와 직접적으로 관련되며, 일차 정보에서 curvature를 추정해 stepsize를 설정하는 vSGD, AdaDelta, natural Newton method와도 연관된다.
  • Natural gradient descent: Adam은 preconditioner가 data geometry에 맞춰 조정되므로 natural gradient descent (NGD)와 유사하며, b_vt는 Fisher의 diagonal을 근사한다.
  • SFO: SFO는 minibatch quasi-Newton method지만, memory가 minibatch partition 수에 따라 선형으로 증가해 memory-constrained GPU에서는 실행이 불가능한 경우가 많다.
  • RMSProp: momentum을 사용하는 RMSProp과 달리 Adam은 gradient의 first moment와 second moment의 running average로 update를 추정하고 bias correction을 포함한다.momentum을 사용하는 RMSProp은 대신 rescaled gradient에 momentum을 적용하며, RMSProp에는 bias correction이 없다.
  • AdaGrad: AdaGrad는 β1 = 0, infinitesimal (1 − β2), annealed α를 적용한 Adam에 해당하지만, bias correction이 없으면 이 대응은 성립하지 않는다.bias correction이 없으면 β2가 1에 가까워질 때 무한히 큰 bias와 parameter update가 발생한다.

6 실험

logistic regression, multilayer network, deep CNN 전반의 실험에서 Adam이 sparse-feature 문제와 실제 deep-learning 문제 모두에 효과적임을 보인다. 장점은 model에 따라 달라진다. Adam은 specialized optimizer와 대등하거나 더 우수한 성능을 보이는 반면, CNN의 거동은 second-moment estimate의 한계를 드러낸다.

  • 실험 설정: 평가는 공통 initialization과 dense hyper-parameter search로 선택한 최적 설정을 사용해 logistic regression, multilayer fully connected network, deep CNN을 다룬다.Adam을 실제 deep-learning 문제에서 평가하기 위해 대규모 model과 dataset을 사용했다.
  • Logistic regression: MNIST logistic regression에서 Adam은 momentum을 사용한 SGD와 유사하게 수렴하며, 두 방법 모두 Adagrad보다 빠르게 수렴한다.실험은 minibatch 크기 128을 사용하고 convex objective에서 optimizer를 비교해 local minimum에 대한 우려를 배제한다.
  • Logistic regression: 희소한 IMDB bag-of-words feature에서 Adam은 Adagrad만큼 빠르게 수렴하고 Nesterov momentum을 사용한 SGD보다 빠르게 수렴하며, dropout noise의 유무와 관계없이 이러한 결과를 보인다.Adagrad는 SGD보다 큰 차이로 우수한 성능을 보이는 반면, Adam은 Adagrad와 수렴 속도가 대등하다. 이는 Adam이 sparse feature를 활용한다는 해석과 일치한다.
  • Multilayer neural network: Adam은 dropout을 적용했을 때 다른 stochastic first-order method보다 더 나은 수렴을 보이며, deterministic multilayer-network objective에서는 SFO보다 빠르게 학습한다.stochastic regularization으로 subfunction이 nondeterministic해지자 SFO는 수렴에 실패했다.
  • Convolutional neural network: CNN에서는 초기 training 단계 이후 Adam과 SGD가 Adagrad보다 훨씬 빠르게 수렴한다. 이는 Adam의 second-moment estimate가 소실되어 ϵ에 의해 지배되기 때문이다.이는 초기 cost 감소가 유사하게 빠르다는 점과 대조되며, second-moment estimate가 CNN cost geometry를 제대로 포착하지 못함을 나타낸다.
  • Bias correction: VAE training에서 Adam은 hyper-parameter 설정 전반에 걸쳐 RMSProp과 대등하거나 더 우수한 성능을 보이며, β2가 1에 가까울 때 bias correction이 초기 불안정성을 방지한다.최상의 결과는 bias correction과 작은 (1−β2) 값을 사용했을 때 얻어졌으며, 특히 optimization 후반부에 gradient가 더 희소해질수록 효과적이었다.

7 확장

확장은 Adam을 AdaMax로 일반화한다. AdaMax는 infinity-norm limit에서 도출되며, 더 단순하고 안정적이며 parameter change가 bounded인 update를 제공한다. 또한 stochastic approximation에서 generalization을 향상하기 위해 iterate 또는 parameter를 평균내는 방법을 제안한다.

  • AdaMax: AdaMax는 Lp-norm update rule에서 p →∞ 극한을 취해 얻는, 놀라울 만큼 단순하고 안정적인 Adam 변형이다.유한한 큰 p를 사용하는 변형은 수치적으로 불안정할 수 있는 반면, AdaMax는 infinity norm을 사용하므로 norm estimate에 initialization-bias correction이 필요하지 않다.
  • AdaMax: AdaMax는 bias-corrected first-moment estimate를 gradient의 exponentially weighted infinity norm으로 나누어 parameter를 update한다.Norm estimate는 ut ← max(β2 · ut−1, |gt|)를 따르며, parameter update에는 mt/ut를 사용한다.
  • AdaMax: AdaMax는 parameter update의 magnitude를 |∆t| ≤α로 bound한다.따라서 AdaMax는 Adam보다 더 단순한 update-magnitude bound를 갖는다.
  • Parameter averaging: Stochastic approximation에서는 마지막 iterate가 noisy하므로 averaging이 generalization을 향상할 수 있다.이 논문은 Polyak-Ruppert averaging과, 최근 parameter value에 더 큰 weight를 부여하는 대안적 exponential moving average를 설명하며, 후자에는 initialization-bias correction을 적용할 수 있다.

8 결론

Adam은 대규모 데이터셋과 고차원 parameter space를 위한 단순하고 계산 효율적인 stochastic optimization algorithm으로 제시된다. AdaGrad의 sparse gradient 처리 능력과 RMSProp의 non-stationary objective 대응 능력을 결합하며, 실험 결과는 convex convergence analysis와 non-convex optimization 전반에서의 강건성을 뒷받침한다.

  • 8 결론: Adam은 stochastic objective function의 gradient-based optimization을 위한 단순하고 계산 효율적인 algorithm이다.대규모 데이터셋 및/또는 고차원 parameter space를 포함하는 machine learning 문제를 대상으로 한다.
  • 8 결론: Adam은 sparse gradient를 처리하는 AdaGrad의 능력과 non-stationary objective를 처리하는 RMSProp의 능력을 결합한다.이 방법은 구현이 간단하고 적은 memory만 필요로 한다.
  • 8 결론: 실험은 convex 문제에 대한 convergence-rate analysis를 확인하며, Adam이 강건하고 광범위한 non-convex optimization 문제에 적합함을 보여준다.

10 부록

부록에서는 Adam의 regret guarantee를 증명하는 데 사용되는 convexity lemma와 bounded-gradient assumption을 전개한다. 이어서 Adam의 update를 convex regret analysis에 대입하고 그 결과 항을 bound하여 theorem을 도출한다.

  • 10 부록: 부록에서는 함수를 tangent hyperplane으로 lower-bound하는 convexity lemma를 수립하여 Adam의 update rule을 통한 regret analysis를 가능하게 한다.주요 증명에서는 tangent-hyperplane 항에 Adam update를 대입한다.
  • 10 부록: Supporting lemma는 ∥g_t∥_2 ≤ G 및 ∥g_t∥_∞ ≤ G_∞인 bounded gradients를 가정하고, β_2 및 decaying β_1,t 아래에서 running-average 항을 분석한다.Theorem은 추가로 bounded parameter distance와 β_1,t = β_1λ^(t−1), λ ∈ (0, 1)을 가정한다.
  • 10 부록: 증명에서는 auxiliary lemma를 coordinate-wise로 적용하고, Young’s inequality와 arithmetic-geometric-series bound를 사용한 뒤, 차원과 iteration에 걸쳐 합산하여 Adam의 regret bound를 얻는다.유도 과정에서는 먼저 각 coordinate의 update contribution을 bound한 다음, 그 결과로 얻은 upper bound를 aggregate한다.
Loading 1412.6980v9…