Adam: 확률적 최적화를 위한 방법
Diederik P. Kingma* 암스테르담 대학교, OpenAI dpkingma@openai.com
Diederik P. Kingma* University of Amsterdam, OpenAI dpkingma@openai.comJimmy Lei Ba∗ 토론토 대학교 jimmy@psi.utoronto.ca
Jimmy Lei Ba∗ University of Toronto jimmy@psi.utoronto.ca우리는 1차 모멘트보다 낮은 차수의 모멘트에 대한 적응적 추정을 바탕으로, 확률적 목적함수의 1차 기울기 기반 최적화를 위한 알고리즘 Adam을 제안한다. 이 방법은 구현이 간단하고 계산적으로 효율적이며, 메모리 요구량이 적고, 기울기의 대각 스케일링(diagonal rescaling)에 대해 불변이며, 데이터 및/또는 매개변수 규모가 큰 문제에 특히 적합하다. 또한 이 방법은 비정상(non-stationary) 목적함수와 잡음이 매우 크거나 희소한 기울기를 갖는 문제에도 적합하다. 하이퍼파라미터는 직관적으로 해석할 수 있고, 일반적으로 튜닝이 거의 필요하지 않다. Adam의 영감이 된 관련 알고리즘들과의 몇 가지 연관성도 논의한다. 또한 알고리즘의 이론적 수렴 특성을 분석하고, 온라인 볼록 최적화(online convex optimization) 프레임워크에서 알려진 최선의 결과와 견줄 만한 수렴률에 대한 regret bound를 제시한다. 경험적 결과는 Adam이 실제로 잘 작동하며 다른 확률적 최적화 방법들보다 우수함을 보여준다. 마지막으로, 무한대 노름(infinity norm)을 기반으로 한 Adam의 변형인 AdaMax도 논의한다.
We introduce Adam, an algorithm for first-order gradient-based optimization of stochastic objective functions, based on adaptive estimates of lower-order moments. The method is straightforward to implement, is computationally efficient, has little memory requirements, is invariant to diagonal rescaling of the gradients, and is well suited for problems that are large in terms of data and/or parameters. The method is also appropriate for non-stationary objectives and problems with very noisy and/or sparse gradients. The hyper-parameters have intuitive interpretations and typically require little tuning. Some connections to related algorithms, on which Adam was inspired, are discussed. We also analyze the theoretical convergence properties of the algorithm and provide a regret bound on the convergence rate that is comparable to the best known results under the online convex optimization framework. Empirical results demonstrate that Adam works well in practice and compares favorably to other stochastic optimization methods. Finally, we discuss AdaMax, a variant of Adam based on the infinity norm.확률적 기울기 기반 최적화는 과학과 공학의 여러 분야에서 핵심적인 실용적 중요성을 지닌다. 이러한 분야의 많은 문제는 어떤 스칼라 매개변수화 목적함수를 그 매개변수에 대해 최대화하거나 최소화하는 최적화 문제로 정식화할 수 있다. 함수가 매개변수에 관해 미분 가능하다면, 경사하강법(gradient descent)은 비교적 효율적인 최적화 방법이다. 모든 매개변수에 대한 1차 편미분을 계산하는 데 필요한 계산 복잡도는 함수를 평가하는 데 드는 복잡도와 같기 때문이다. 목적함수는 종종 확률적이다. 예를 들어, 많은 목적함수는 서로 다른 데이터 부분표본에서 평가된 하위함수들의 합으로 구성되는데, 이 경우 각 하위함수에 대해 기울기 단계를 취함으로써 최적화를 더 효율적으로 수행할 수 있다. 즉, 확률적 경사하강법(stochastic gradient descent, SGD) 또는 상승법(ascent)을 사용할 수 있다. SGD는 효율적이고 효과적인 최적화 방법으로 입증되었으며, 딥러닝의 최근 발전(Deng et al., 2013; Krizhevsky et al., 2012; Hinton & Salakhutdinov, 2006; Hinton et al., 2012a; Graves et al., 2013)과 같은 많은 기계학습의 성공 사례에서 중심적인 역할을 해왔다. 목적함수의 잡음은 데이터 부분표본추출 외에도 dropout(Hinton et al., 2012b) 정규화와 같은 다른 원인에서 비롯될 수 있다. 이러한 모든 잡음이 있는 목적함수에 대해서는 효율적인 확률적 최적화 기법이 필요하다. 이 논문의 초점은 고차원 매개변수 공간을 갖는 확률적 목적함수의 최적화에 있다. 이런 경우 고차 최적화 방법은 적합하지 않으며, 본 논의는 1차 방법에 한정한다.
Stochastic gradient-based optimization is of core practical importance in many fields of science and engineering. Many problems in these fields can be cast as the optimization of some scalar parameterized objective function requiring maximization or minimization with respect to its parameters. If the function is differentiable w.r.t. its parameters, gradient descent is a relatively efficient optimization method, since the computation of first-order partial derivatives w.r.t. all the parameters is of the same computational complexity as just evaluating the function. Often, objective functions are stochastic. For example, many objective functions are composed of a sum of subfunctions evaluated at different subsamples of data; in this case optimization can be made more efficient by taking gradient steps w.r.t. individual subfunctions, i.e. stochastic gradient descent (SGD) or ascent. SGD proved itself as an efficient and effective optimization method that was central in many machine learning success stories, such as recent advances in deep learning (Deng et al., 2013; Krizhevsky et al., 2012; Hinton & Salakhutdinov, 2006; Hinton et al., 2012a; Graves et al., 2013). Objectives may also have other sources of noise than data subsampling, such as dropout (Hinton et al., 2012b) regularization. For all such noisy objectives, efficient stochastic optimization techniques are required. The focus of this paper is on the optimization of stochastic objectives with high-dimensional parameters spaces. In these cases, higher-order optimization methods are ill-suited, and discussion in this paper will be restricted to first-order methods.우리는 적은 메모리만 요구하면서 1차 기울기만으로도 작동하는 효율적인 확률적 최적화 방법 Adam을 제안한다. 이 방법은 기울기의 1차 및 2차 모멘트에 대한 추정으로부터 서로 다른 매개변수에 대해 개별적인 적응형 학습률을 계산하며, Adam이라는 이름은 adaptive moment estimation에서 유래했다. 우리의 방법은 최근 널리 쓰이는 두 방법의 장점을 결합하도록 설계되었다. 희소한 기울기(sparse gradients)에 강한 AdaGrad(Duchi et al., 2011)와 온라인 및 비정상 상황에서 잘 작동하는 RMSProp(Tieleman & Hinton, 2012)이 그것이며, 이들과 다른 확률적 최적화 방법들 사이의 중요한 연관성은 5장에서 명확히 밝힌다. Adam의 장점 가운데 몇 가지는 매개변수 업데이트의 크기가 기울기의 재스케일링(rescaling)에 대해 불변이라는 점, 스텝 크기가 하이퍼파라미터로 거의 상한이 정해진다는 점, 정지된 목적함수를 요구하지 않는다는 점, 희소한 기울기와 잘 작동한다는 점, 그리고 자연스럽게 스텝 크기 annealing의 한 형태를 수행한다는 점이다.
We propose Adam, a method for efficient stochastic optimization that only requires first-order gradients with little memory requirement. The method computes individual adaptive learning rates for different parameters from estimates of first and second moments of the gradients; the name Adam is derived from adaptive moment estimation. Our method is designed to combine the advantages of two recently popular methods: AdaGrad (Duchi et al., 2011), which works well with sparse gradients, and RMSProp (Tieleman & Hinton, 2012), which works well in on-line and non-stationary settings; important connections to these and other stochastic optimization methods are clarified in section 5. Some of Adam’s advantages are that the magnitudes of parameter updates are invariant to rescaling of the gradient, its stepsizes are approximately bounded by the stepsize hyperparameter, it does not require a stationary objective, it works with sparse gradients, and it naturally performs a form of step size annealing.∗동일 기여. 저자 순서는 Google Hangout에서 동전 던지기로 결정되었다.
∗Equal contribution. Author ordering determined by coin flip over a Google Hangout.알고리즘 1: 우리가 제안하는 확률적 최적화 알고리즘 Adam. 자세한 내용과, 조금 더 효율적이지만 덜 명확한 계산 순서는 2장을 보라. g2 t는 원소별 제곱 gt ⊙gt를 의미한다. 시험한 기계학습 문제들에 대한 좋은 기본 설정은 α = 0.001, β1 = 0.9, β2 = 0.999, ϵ = 10−8이다. 벡터에 대한 모든 연산은 원소별로 수행된다. βt 1과 βt 2는 각각 β1과 β2의 t제곱을 뜻한다. Require: α: 스텝 크기 Require: β1, β2 ∈[0, 1): 모멘트 추정의 지수 감쇠율 Require: f(θ): 매개변수 θ를 갖는 확률적 목적함수 Require: θ0: 초기 매개변수 벡터 m0 ←0 (1차 모멘트 벡터 초기화) v0 ←0 (2차 모멘트 벡터 초기화) t ←0 (시간 단계 초기화) while θt not converged do t ←t + 1 gt ←∇θft(θt−1) (t번째 시점의 확률적 목적함수에 대한 기울기 계산) mt ←β1 · mt−1 + (1 −β1) · gt (편향된 1차 모멘트 추정 업데이트) vt ←β2 · vt−1 + (1 −β2) · g2 t (편향된 2차 원시 모멘트 추정 업데이트) bmt ←mt/(1 −βt 1) (편향 보정된 1차 모멘트 추정 계산) bvt ←vt/(1 −βt 2) (편향 보정된 2차 원시 모멘트 추정 계산) θt ←θt−1 −α · bmt/(√bvt + ϵ) (매개변수 업데이트) end while return θt (결과 매개변수)
Algorithm 1: Adam, our proposed algorithm for stochastic optimization. See section 2 for details, and for a slightly more efficient (but less clear) order of computation. g2 t indicates the elementwise square gt ⊙gt. Good default settings for the tested machine learning problems are α = 0.001, β1 = 0.9, β2 = 0.999 and ϵ = 10−8. All operations on vectors are element-wise. With βt 1 and βt 2 we denote β1 and β2 to the power t. Require: α: Stepsize Require: β1, β2 ∈[0, 1): Exponential decay rates for the moment estimates Require: f(θ): Stochastic objective function with parameters θ Require: θ0: Initial parameter vector m0 ←0 (Initialize 1st moment vector) v0 ←0 (Initialize 2nd moment vector) t ←0 (Initialize timestep) while θt not converged do t ←t + 1 gt ←∇θft(θt−1) (Get gradients w.r.t. stochastic objective at timestep t) mt ←β1 · mt−1 + (1 −β1) · gt (Update biased first moment estimate) vt ←β2 · vt−1 + (1 −β2) · g2 t (Update biased second raw moment estimate) bmt ←mt/(1 −βt 1) (Compute bias-corrected first moment estimate) bvt ←vt/(1 −βt 2) (Compute bias-corrected second raw moment estimate) θt ←θt−1 −α · bmt/(√bvt + ϵ) (Update parameters) end while return θt (Resulting parameters)2장에서는 알고리즘과 그 업데이트 규칙의 성질을 설명한다. 3장에서는 초기화 편향 보정(initialization bias correction) 기법을 설명하고, 4장에서는 온라인 볼록 프로그래밍(online convex programming)에서의 Adam 수렴에 대한 이론적 분석을 제시한다. 경험적으로는 6장에서 보이듯이, 우리의 방법은 다양한 모델과 데이터셋에서 일관되게 다른 방법들을 능가한다. 종합하면, Adam은 대규모 고차원 기계학습 문제로 확장 가능한 범용적 알고리즘임을 보인다.
In section 2 we describe the algorithm and the properties of its update rule. Section 3 explains our initialization bias correction technique, and section 4 provides a theoretical analysis of Adam’s convergence in online convex programming. Empirically, our method consistently outperforms other methods for a variety of models and datasets, as shown in section 6. Overall, we show that Adam is a versatile algorithm that scales to large-scale high-dimensional machine learning problems.제안한 알고리즘 Adam의 의사코드는 알고리즘 1을 보라. f(θ)를 잡음이 있는 목적함수, 즉 매개변수 θ에 대해 미분 가능한 확률적 스칼라 함수라고 하자. 우리는 이 함수의 기대값 E[f(θ)]를 θ에 관해 최소화하는 데 관심이 있다. f1(θ), ..., , fT (θ)는 연속된 시점 1, ..., T에서의 이 확률적 함수의 실현값(realisation)을 뜻한다. 이러한 확률성은 데이터 포인트의 무작위 부분표본(minibatch)에서의 평가로부터 생기거나, 함수 고유의 잡음에서 비롯될 수 있다. gt = ∇θft(θ)로 표기하며, 이는 시점 t에서 평가된 ft의 θ에 대한 기울기, 즉 편미분 벡터이다.
See algorithm 1 for pseudo-code of our proposed algorithm Adam. Let f(θ) be a noisy objective function: a stochastic scalar function that is differentiable w.r.t. parameters θ. We are interested in minimizing the expected value of this function, E[f(θ)] w.r.t. its parameters θ. With f1(θ), ..., , fT (θ) we denote the realisations of the stochastic function at subsequent timesteps 1, ..., T. The stochasticity might come from the evaluation at random subsamples (minibatches) of datapoints, or arise from inherent function noise. With gt = ∇θft(θ) we denote the gradient, i.e. the vector of partial derivatives of ft, w.r.t θ evaluated at timestep t.알고리즘은 기울기(mt)와 제곱 기울기(vt)의 지수이동평균(exponential moving average)을 갱신하며, 하이퍼파라미터 β1, β2 ∈[0, 1) 는 이들 이동평균의 지수적 감쇠율을 제어한다. 이 이동평균은 기울기의 1차 모멘트(평균)와 2차 원시 모멘트(비중심 분산)의 추정치이다. 그러나 이들 이동평균은 0(벡터)으로 초기화되므로, 특히 초기 시점에서 그리고 감쇠율이 작을 때(즉, β들이 1에 가까울 때) 모멘트 추정치가 0 쪽으로 편향된다. 다행히도 이 초기화 편향은 쉽게 보정할 수 있으며, 그 결과 편향 보정 추정치 bmt와 bvt를 얻는다. 자세한 내용은 3절을 보라.
The algorithm updates exponential moving averages of the gradient (mt) and the squared gradient (vt) where the hyper-parameters β1, β2 ∈[0, 1) control the exponential decay rates of these moving averages. The moving averages themselves are estimates of the 1st moment (the mean) and the 2nd raw moment (the uncentered variance) of the gradient. However, these moving averages are initialized as (vectors of) 0’s, leading to moment estimates that are biased towards zero, especially during the initial timesteps, and especially when the decay rates are small (i.e. the βs are close to 1). The good news is that this initialization bias can be easily counteracted, resulting in bias-corrected estimates bmt and bvt. See section 3 for more details.알고리즘 1은 명료성을 다소 희생하는 대신 계산 순서를 바꾸면 효율성을 더 높일 수 있다. 예를 들어 루프의 마지막 세 줄을 다음 줄들로 대체할 수 있다: αt = α · p
Note that the efficiency of algorithm 1 can, at the expense of clarity, be improved upon by changing the order of computation, e.g. by replacing the last three lines in the loop with the following lines: αt = α · pAdam의 갱신 규칙에서 중요한 성질은 학습률(stepsize)을 신중하게 선택한다는 점이다. ϵ = 0이라고 가정하면, 시점 t에서 매개변수 공간에서의 유효한 이동량은 ∆t = α · bmt/√bvt 이다. 유효 학습률에는 두 개의 상한이 있다. 즉, (1 −β1) > √1 −β2 인 경우 |∆t| ≤α · (1 −β1)/√1 −β2 이고, |∆t| ≤α
An important property of Adam’s update rule is its careful choice of stepsizes. Assuming ϵ = 0, the effective step taken in parameter space at timestep t is ∆t = α · bmt/√bvt. The effective stepsize has two upper bounds: |∆t| ≤α · (1 −β1)/√1 −β2 in the case (1 −β1) > √1 −β2, and |∆t| ≤αICLR 2015에서 학회 논문으로 게재됨. 첫 번째 경우는 가장 심각한 희소성(sparsity) 상황에서만 발생한다. 즉, 현재 시점을 제외한 모든 시점에서 기울기가 0이었던 경우이다. 덜 희소한 경우에는 유효 학습률이 더 작아진다. (1 −β1) = √1 −β2 이면 | bmt/√bvt| < 1 이므로 |∆t| < α 이다. 더 일반적인 상황에서는 |E[g]/ p
Published as a conference paper at ICLR 2015 otherwise. The first case only happens in the most severe case of sparsity: when a gradient has been zero at all timesteps except at the current timestep. For less sparse cases, the effective stepsize will be smaller. When (1 −β1) = √1 −β2 we have that | bmt/√bvt| < 1 therefore |∆t| < α. In more common scenarios, we will have that bmt/√bvt ≈±1 since |E[g]/ pE[g2]| ≤1 이므로 bmt/√bvt ≈±1 이 된다. 각 시점에서 매개변수 공간에서 실제로 취해지는 이동의 크기는 대략 학습률 설정값 α로 상한이 정해지며, 즉 |∆t| ⪅α 이다. 이는 현재 매개변수 값 주변에 신뢰 영역(trust region)을 설정하는 것으로 이해할 수 있는데, 그 밖의 영역에서는 현재의 기울기 추정이 충분한 정보를 제공하지 못한다. 따라서 일반적으로 α의 적절한 스케일을 사전에 비교적 쉽게 정할 수 있다. 예를 들어 많은 머신러닝 모형에서는 좋은 최적점이 높은 확률로 매개변수 공간의 어떤 구역 안에 존재한다는 사실을 미리 알고 있는 경우가 많다. 실제로 매개변수에 대한 사전분포를 두는 일이 드물지 않다. α는 매개변수 공간에서의 이동 크기(의 상한)를 정하므로, θ0에서 출발해 일정 반복 횟수 안에 최적점에 도달할 수 있도록 α의 적절한 차수(order of magnitude)를 종종 추론할 수 있다. 용어를 약간 느슨하게 쓰자면, bmt/√bvt 를 신호대잡음비(signal-to-noise ratio, SNR)라고 부르겠다. SNR이 작을수록 유효 학습률 ∆t 는 0에 더 가까워진다. 이는 바람직한 성질인데, SNR이 작다는 것은 bmt의 방향이 진짜 기울기의 방향과 일치하는지에 대한 불확실성이 더 크다는 뜻이기 때문이다. 예를 들어 SNR 값은 보통 최적점에 가까워질수록 0에 가까워지며, 그에 따라 매개변수 공간에서의 유효한 이동도 더 작아진다. 이는 자동 냉각(automatic annealing)의 한 형태이다. 유효 학습률 ∆t 는 기울기의 스케일에도 불변이다. 기울기 g를 계수 c로 재스케일하면 bmt는 계수 c만큼, bvt는 계수 c2만큼 스케일되며, 이 둘은 서로 상쇄된다: (c · bmt)/(√ c2 · bvt) = bmt/√bvt.
E[g2]| ≤1. The effective magnitude of the steps taken in parameter space at each timestep are approximately bounded by the stepsize setting α, i.e., |∆t| ⪅α. This can be understood as establishing a trust region around the current parameter value, beyond which the current gradient estimate does not provide sufficient information. This typically makes it relatively easy to know the right scale of α in advance. For many machine learning models, for instance, we often know in advance that good optima are with high probability within some set region in parameter space; it is not uncommon, for example, to have a prior distribution over the parameters. Since α sets (an upper bound of) the magnitude of steps in parameter space, we can often deduce the right order of magnitude of α such that optima can be reached from θ0 within some number of iterations. With a slight abuse of terminology, we will call the ratio bmt/√bvt the signal-to-noise ratio (SNR). With a smaller SNR the effective stepsize ∆t will be closer to zero. This is a desirable property, since a smaller SNR means that there is greater uncertainty about whether the direction of bmt corresponds to the direction of the true gradient. For example, the SNR value typically becomes closer to 0 towards an optimum, leading to smaller effective steps in parameter space: a form of automatic annealing. The effective stepsize ∆t is also invariant to the scale of the gradients; rescaling the gradients g with factor c will scale bmt with a factor c and bvt with a factor c2, which cancel out: (c · bmt)/(√ c2 · bvt) = bmt/√bvt.3절에서 설명한 바와 같이, Adam은 초기화 편향 보정항을 사용한다. 여기서는 2차 모멘트 추정치에 대한 항을 유도하고, 1차 모멘트 추정치에 대한 유도는 완전히 동일하다. g를 확률적 목적함수 f의 기울기라고 하자. 또한 감쇠율 β2를 갖는 기울기 제곱의 지수이동평균을 사용하여 그 2차 원시 모멘트(비중심 분산)를 추정하고자 한다. 이후의 시점에서의 기울기를 g1, ..., gT 라고 하자. 각 기울기는 바탕이 되는 기울기 분포 gt ∼p(gt)에서의 하나의 표본이다. 지수이동평균의 초기값을 v0 = 0(0으로 이루어진 벡터)으로 두자. 먼저 시점 t에서의 지수이동평균 갱신식 vt = β2 · vt−1 + (1 −β2) · g2 t (여기서 g2 t 는 원소별 제곱 gt ⊙gt 을 의미한다)는 모든 이전 시점의 기울기에 대한 함수로 다음과 같이 쓸 수 있음을 보이자: vt = (1 −β2) i=1 βt−i 2 · g2 i (1)
As explained in section 2, Adam utilizes initialization bias correction terms. We will here derive the term for the second moment estimate; the derivation for the first moment estimate is completely analogous. Let g be the gradient of the stochastic objective f, and we wish to estimate its second raw moment (uncentered variance) using an exponential moving average of the squared gradient, with decay rate β2. Let g1, ..., gT be the gradients at subsequent timesteps, each a draw from an underlying gradient distribution gt ∼p(gt). Let us initialize the exponential moving average as v0 = 0 (a vector of zeros). First note that the update at timestep t of the exponential moving average vt = β2 · vt−1 + (1 −β2) · g2 t (where g2 t indicates the elementwise square gt ⊙gt) can be written as a function of the gradients at all previous timesteps: vt = (1 −β2) i=1 βt−i 2 · g2 i (1)시점 t에서 지수이동평균의 기대값 E[vt] 가 참된 2차 모멘트 E[g2 t ] 와 어떤 관계에 있는지 알아야 두 값 사이의 불일치를 보정할 수 있다. 식 (1)의 좌변과 우변에 기대값을 취하면:
We wish to know how E[vt], the expected value of the exponential moving average at timestep t, relates to the true second moment E[g2 t ], so we can correct for the discrepancy between the two. Taking expectations of the left-hand and right-hand sides of eq. (1):= E[g2 t ] · (1 −β2) i=1 βt−i 2 · g2 i i=1 βt−i 2 + ζ (3)
= E[g2 t ] · (1 −β2) i=1 βt−i 2 · g2 i i=1 βt−i 2 + ζ (3)= E[g2 t ] · (1 −βt 2) + ζ (4) 여기서 ζ = 0 은 참된 2차 모멘트 E[g2 i ] 가 정상적(stationary)일 때 성립한다. 그렇지 않은 경우에도 지수 감쇠율 β1은 과거 너무 먼 시점의 기울기에 지수이동평균이 작은 가중치를 부여하도록 선택할 수 있고, 또 그렇게 해야 하므로 ζ를 작게 유지할 수 있다. 남는 항은 (1 −βt 2) 인데, 이는 러닝 평균을 0으로 초기화했기 때문에 생긴다. 따라서 알고리즘 1에서는 이 항으로 나누어 초기화 편향을 보정한다.
= E[g2 t ] · (1 −βt 2) + ζ (4) where ζ = 0 if the true second moment E[g2 i ] is stationary; otherwise ζ can be kept small since the exponential decay rate β1 can (and should) be chosen such that the exponential moving average assigns small weights to gradients too far in the past. What is left is the term (1 −βt 2) which is caused by initializing the running average with zeros. In algorithm 1 we therefore divide by this term to correct the initialization bias.희소 기울기(sparse gradients)인 경우, 2차 모멘트를 신뢰성 있게 추정하려면 β2의 값을 작게 설정하여 많은 기울기에 대해 평균을 내야 한다. 그러나 바로 β2가 작은 경우에 초기화 편향을 보정하지 않으면 초기 단계의 이동이 훨씬 더 커진다.
In case of sparse gradients, for a reliable estimate of the second moment one needs to average over many gradients by chosing a small value of β2; however it is exactly this case of small β2 where a lack of initialisation bias correction would lead to initial steps that are much larger.우리는 (Zinkevich, 2003)에서 제안한 온라인 학습 프레임워크를 사용하여 Adam의 수렴을 분석한다. 임의의, 사전에 알 수 없는 볼록 비용함수 f1(θ), f2(θ),..., fT (θ) 의 수열을 생각하자. 각 시점 t에서 우리의 목표는 매개변수 θt 를 예측하고, 이전에는 알 수 없었던 비용함수 ft 에 대해 이를 평가하는 것이다. 수열의 성격을 미리 알 수 없으므로, 우리는 알고리즘을 후회(regret)로 평가한다. 즉, 온라인 예측 ft(θt) 와 가능한 집합 X 에서 이전 모든 단계에 대해 가장 좋은 고정점 매개변수 ft(θ∗) 사이의 차이를 모두 합한 값이다. 구체적으로, 후회는 다음과 같이 정의된다. 여기서 θ∗= arg minθ∈X PT t=1 ft(θ) 이다. 우리는 Adam이 O( √ t=1 [ft(θt) −ft(θ∗)] (5) 의 후회 상한을 가진다는 것을 보이고, 증명은 부록에 제시한다.
We analyze the convergence of Adam using the online learning framework proposed in (Zinkevich, 2003). Given an arbitrary, unknown sequence of convex cost functions f1(θ), f2(θ),..., fT (θ). At each time t, our goal is to predict the parameter θt and evaluate it on a previously unknown cost function ft. Since the nature of the sequence is unknown in advance, we evaluate our algorithm using the regret, that is the sum of all the previous difference between the online prediction ft(θt) and the best fixed point parameter ft(θ∗) from a feasible set X for all the previous steps. Concretely, the regret is defined as: where θ∗= arg minθ∈X PT t=1 ft(θ). We show Adam has O( √ t=1 [ft(θt) −ft(θ∗)] (5)T) 의 후회 상한을 가지며, 증명은 부록에 제시한다. 우리의 결과는 이 일반적인 볼록 온라인 학습 문제에 대해 현재 알려진 최선의 상한과 비교 가능하다. 또한 표기를 단순화하기 위해 몇 가지 정의를 사용한다. 여기서 gt ≜∇ft(θt) 이고, gt,i 는 그 i번째 성분이다. 또 g1:t,i ∈Rt 를 t까지의 모든 반복에서 i차원 기울기를 담은 벡터로 정의하자. 즉, g1:t,i = [g1,i, g2,i, · · · , gt,i] 이다. 아울러 γ ≜ β2 1 √β2 로 두자. 다음의
T) regret bound and a proof is given in the appendix. Our result is comparable to the best known bound for this general convex online learning problem. We also use some definitions simplify our notation, where gt ≜∇ft(θt) and gt,i as the ith element. We define g1:t,i ∈Rt as a vector that contains the ith dimension of the gradients over all iterations till t, g1:t,i = [g1,i, g2,i, · · · , gt,i]. Also, we define γ ≜ β2 1 √β2 . Our following2 및 1차 모멘트 러닝 평균 계수 β1,t 는 λ에 따라 지수적으로 감소하며, λ는 보통 1에 매우 가깝다. 예를 들어 1 −10−8 정도이다. 정리 4.1. 함수 ft 의 기울기가 유계라고 가정하자. 즉, 모든 θ ∈Rd 에 대해 ∥∇ft(θ)∥2 ≤G, ∥∇ft(θ)∥∞≤ G∞ 이고, Adam이 생성한 임의의 θt 사이의 거리가 유계라고 하자. 즉, m, n ∈{1, ..., T} 에 대해 ∥θn −θm∥2 ≤D, ∥θm −θn∥∞≤D∞ 이다. 또한 β1, β2 ∈[0, 1) 가 β2 1 √β2 < 1 을 만족한다고 하자. 학습률 αt = α √ 일 때 정리가 성립하며, β1,t = β1λt−1, λ ∈(0, 1) 로 두면 학습률이 t−1 t 의 비율로 감소하는 경우에도 성립한다. Adam은 모든 T ≥1 에 대해 다음의 보장을 만족한다.
2 and first moment running average coefficient β1,t decay exponentially with λ, that is typically close to 1, e.g. 1 −10−8. Theorem 4.1. Assume that the function ft has bounded gradients, ∥∇ft(θ)∥2 ≤G, ∥∇ft(θ)∥∞≤ G∞for all θ ∈Rd and distance between any θt generated by Adam is bounded, ∥θn −θm∥2 ≤D, ∥θm −θn∥∞≤D∞for any m, n ∈{1, ..., T}, and β1, β2 ∈[0, 1) satisfy β2 1 √β2 < 1. Let αt = α √ theorem holds when the learning rate αt is decaying at a rate of t−1 t and β1,t = β1λt−1, λ ∈(0, 1). Adam achieves the following guarantee, for all T ≥1.i=1 ∥g1:T,i∥2+
i=1 ∥g1:T,i∥2+우리의 정리 4.1은 데이터 특성이 희소하고 그래디언트가 bounded인 경우, 합산 항이 그 상한인 Pd i=1 ∥g1:T,i∥2 << dG∞ √보다 훨씬 작을 수 있음을 함의한다.
Our Theorem 4.1 implies when the data features are sparse and bounded gradients, the summation term can be much smaller than its upper bound Pd i=1 ∥g1:T,i∥2 << dG∞ √T 그리고 Pd i=1 p
T and Pd i=1 pT, 특히 함수 클래스와 데이터 특성이 (Duchi et al., 2011)의 1.2절에 제시된 형태인 경우에 그렇다. 그들이 기대값 E[Pd i=1 ∥g1:T,i∥2]에 대해 얻은 결과는 Adam에도 적용된다. 특히 Adam과 Adagrad와 같은 적응형 방법은 비적응형 방법의 O( √ dT)보다 개선된 O(log d √
T, in particular if the class of function and data features are in the form of section 1.2 in (Duchi et al., 2011). Their results for the expected value E[Pd i=1 ∥g1:T,i∥2] also apply to Adam. In particular, the adaptive method, such as Adam and Adagrad, can achieve O(log d √T)를 달성할 수 있다. β1,t를 0으로 감쇠시키는 것은 우리의 이론적 분석에서 중요하며, 이전의 실증적 발견과도 부합한다. 예를 들어 (Sutskever et al., 2013)은 학습 말기에 momentum 계수를 줄이면 수렴을 개선할 수 있다고 제안한다.
T), an improvement over O( √ dT) for the non-adaptive method. Decaying β1,t towards zero is important in our theoretical analysis and also matches previous empirical findings, e.g. (Sutskever et al., 2013) suggests reducing the momentum coefficient in the end of training can improve convergence.마지막으로, Adam의 평균 regret가 수렴함을 보일 수 있다. 보조정리 4.2. 함수 ft의 그래디언트가 모든 θ ∈Rd에 대해 ∥∇ft(θ)∥2 ≤G, ∥∇ft(θ)∥∞≤ G∞로 bounded이고, Adam이 생성한 임의의 θt 사이의 거리가 ∥θn −θm∥2 ≤D, ∥θm −θn∥∞≤D∞로 bounded라고 가정하자. 그러면 Adam은 모든 T ≥1에 대해 다음 보장을 만족한다. R(T)
Finally, we can show the average regret of Adam converges, Corollary 4.2. Assume that the function ft has bounded gradients, ∥∇ft(θ)∥2 ≤G, ∥∇ft(θ)∥∞≤ G∞for all θ ∈Rd and distance between any θt generated by Adam is bounded, ∥θn −θm∥2 ≤D, ∥θm −θn∥∞≤D∞for any m, n ∈{1, ..., T}. Adam achieves the following guarantee, for all T ≥1. R(T)이 결과는 정리 4.1과 Pd i=1 ∥g1:T,i∥2 ≤dG∞ √
This result can be obtained by using Theorem 4.1 and Pd i=1 ∥g1:T,i∥2 ≤dG∞ √T를 사용하면 얻을 수 있다. 따라서, limT →∞ R(T )
T. Thus, limT →∞ R(T )Adam과 직접적인 관련이 있는 최적화 방법으로는 RMSProp (Tieleman & Hinton, 2012; Graves, 2013)과 AdaGrad (Duchi et al., 2011)가 있으며, 이들 관계는 아래에서 논의한다. 그 밖의 stochastic optimization 방법으로는 vSGD (Schaul et al., 2012), AdaDelta (Zeiler, 2012), 그리고 1차 정보로 stepsize를 추정하는 Roux & Fitzgibbon (2010)의 natural Newton method가 있다
Optimization methods bearing a direct relation to Adam are RMSProp (Tieleman & Hinton, 2012; Graves, 2013) and AdaGrad (Duchi et al., 2011); these relationships are discussed below. Other stochastic optimization methods include vSGD (Schaul et al., 2012), AdaDelta (Zeiler, 2012) and the natural Newton method from Roux & Fitzgibbon (2010), all setting stepsizes by estimating curvatureICLR 2015에서 conference paper로 출판됨. Sum-of-Functions Optimizer (SFO) (Sohl-Dickstein et al., 2014)는 minibatch 기반의 quasi-Newton method이지만, (Adam과 달리) 데이터셋의 minibatch partition 개수에 선형인 메모리 요구량을 가지며, 이는 GPU와 같이 메모리가 제한된 시스템에서는 종종 비현실적이다. natural gradient descent (NGD) (Amari, 1998)와 마찬가지로, Adam은 데이터의 기하구조에 적응하는 preconditioner를 사용한다. bvt가 Fisher information matrix (Pascanu & Bengio, 2013)의 대각선에 대한 근사이기 때문이다. 그러나 Adam의 preconditioner는(AdaGrad와 마찬가지로) 대각 Fisher information matrix 근사의 역수의 제곱근으로 preconditioning하므로, 일반적인 NGD보다 적응이 더 보수적이다.
Published as a conference paper at ICLR 2015 from first-order information. The Sum-of-Functions Optimizer (SFO) (Sohl-Dickstein et al., 2014) is a quasi-Newton method based on minibatches, but (unlike Adam) has memory requirements linear in the number of minibatch partitions of a dataset, which is often infeasible on memory-constrained systems such as a GPU. Like natural gradient descent (NGD) (Amari, 1998), Adam employs a preconditioner that adapts to the geometry of the data, since bvt is an approximation to the diagonal of the Fisher information matrix (Pascanu & Bengio, 2013); however, Adam’s preconditioner (like AdaGrad’s) is more conservative in its adaption than vanilla NGD by preconditioning with the square root of the inverse of the diagonal Fisher information matrix approximation.RMSProp: Adam과 밀접하게 관련된 최적화 방법으로 RMSProp (Tieleman & Hinton, 2012)이 있다. momentum을 포함한 버전이 때때로 사용되기도 한다 (Graves, 2013). momentum이 있는 RMSProp과 Adam 사이에는 몇 가지 중요한 차이가 있다. momentum이 있는 RMSProp은 rescaled gradient에 대한 momentum을 사용하여 parameter update를 생성하는 반면, Adam의 업데이트는 gradient의 1차 및 2차 모멘트의 running average를 이용해 직접 추정된다. 또한 RMSProp에는 bias-correction term이 없다. 이는 β2 값이 1에 매우 가까운 경우, 특히 sparse gradients를 사용할 때 가장 중요하다. 이 경우 bias를 보정하지 않으면 매우 큰 stepsize가 발생하고 종종 발산하는데, 이는 6.4절에서 실증적으로도 보인다.
RMSProp: An optimization method closely related to Adam is RMSProp (Tieleman & Hinton, 2012). A version with momentum has sometimes been used (Graves, 2013). There are a few important differences between RMSProp with momentum and Adam: RMSProp with momentum generates its parameter updates using a momentum on the rescaled gradient, whereas Adam updates are directly estimated using a running average of first and second moment of the gradient. RMSProp also lacks a bias-correction term; this matters most in case of a value of β2 close to 1 (required in case of sparse gradients), since in that case not correcting the bias leads to very large stepsizes and often divergence, as we also empirically demonstrate in section 6.4.AdaGrad: sparse gradients에 잘 작동하는 알고리즘으로 AdaGrad (Duchi et al., 2011)가 있다. 기본 버전에서는 파라미터를 θt+1 = θt −α · gt/ qPt i=1 g2 t 로 갱신한다. β2를 1보다 무한소만큼 작은 값으로 선택하면 limβ2→1 bvt = t−1 · Pt i=1 g2 t 임에 유의하라. AdaGrad는 β1 = 0, 무한소인 (1 −β2), 그리고 α를 annealed version αt = α · t−1/2로 대체한 Adam의 버전에 해당한다. 즉, θt −α · t−1/2 · bmt/ p limβ2→1 bvt = θt −α · t−1/2 · gt/ q t−1 · Pt i=1 g2 t = θt −α · gt/ qPt i=1 g2 t 이다. 그러나 Adam과 Adagrad 사이의 이러한 직접 대응은 bias-correction term을 제거하면 성립하지 않는다. bias correction이 없으면 RMSProp처럼 β2가 1에 무한소만큼 가까울 때 bias가 무한히 커지고, parameter update도 무한히 커진다.
AdaGrad: An algorithm that works well for sparse gradients is AdaGrad (Duchi et al., 2011). Its basic version updates parameters as θt+1 = θt −α · gt/ qPt i=1 g2 t . Note that if we choose β2 to be infinitesimally close to 1 from below, then limβ2→1 bvt = t−1 · Pt i=1 g2 t . AdaGrad corresponds to a version of Adam with β1 = 0, infinitesimal (1 −β2) and a replacement of α by an annealed version αt = α · t−1/2, namely θt −α · t−1/2 · bmt/ p limβ2→1 bvt = θt −α · t−1/2 · gt/ q t−1 · Pt i=1 g2 t = θt −α · gt/ qPt i=1 g2 t . Note that this direct correspondence between Adam and Adagrad does not hold when removing the bias-correction terms; without bias correction, like in RMSProp, a β2 infinitesimally close to 1 would lead to infinitely large bias, and infinitely large parameter updates.제안한 방법을 실증적으로 평가하기 위해, logistic regression, multilayer fully connected neural networks, deep convolutional neural networks를 포함한 여러 널리 사용되는 machine learning model을 조사하였다. 대규모 model과 dataset을 사용하여, Adam이 실제 deep learning 문제를 효율적으로 해결할 수 있음을 보인다.
To empirically evaluate the proposed method, we investigated different popular machine learning models, including logistic regression, multilayer fully connected neural networks and deep convolutional neural networks. Using large models and datasets, we demonstrate Adam can efficiently solve practical deep learning problems.서로 다른 optimization algorithm을 비교할 때는 동일한 parameter initialization을 사용한다. learning rate와 momentum 같은 hyper-parameter는 촘촘한 grid search를 통해 탐색하며, 결과는 가장 좋은 hyper-parameter 설정을 사용해 보고한다.
We use the same parameter initialization when comparing different optimization algorithms. The hyper-parameters, such as learning rate and momentum, are searched over a dense grid and the results are reported using the best hyper-parameter setting.우리는 MNIST dataset을 이용한 L2-regularized multi-class logistic regression에 제안한 방법을 평가한다. Logistic regression은 잘 연구된 convex objective를 가지므로, local minimum 문제를 걱정하지 않고 서로 다른 optimizer를 비교하기에 적합하다. 우리의 logistic regression 실험에서 stepsize α는 1/ √ t에 맞추어 조정하였는데, 이는 4절의 이론적 예측과 일치한다. Logistic regression은 784차원 image vector에 대해 class label을 직접 분류한다. 우리는 minibatch size 128을 사용하여 Adam을 accelerated SGD with Nesterov momentum 및 Adagrad와 비교한다. Figure 1에 따르면, Adam은 momentum이 있는 SGD와 비슷한 수렴을 보였고, 둘 다 Adagrad보다 더 빨리 수렴했다.
We evaluate our proposed method on L2-regularized multi-class logistic regression using the MNIST dataset. Logistic regression has a well-studied convex objective, making it suitable for comparison of different optimizers without worrying about local minimum issues. The stepsize α in our logistic regression experiments is adjusted by 1/ √ t that matches with our theoratical prediction from section 4. The logistic regression classifies the class label directly on the 784 dimension image vectors. We compare Adam to accelerated SGD with Nesterov momentum and Adagrad using minibatch size of 128. According to Figure 1, we found that the Adam yields similar convergence as SGD with momentum and both converge faster than Adagrad.(Duchi et al., 2011)에서 논의한 바와 같이, Adagrad는 핵심 이론 결과 중 하나로 sparse features와 gradients를 효율적으로 처리할 수 있는 반면, SGD는 드문 feature를 학습하는 데는 성능이 낮다. stepsize에 1/ √ t 감쇠를 적용한 Adam은 이론적으로 Adagrad의 성능과 일치해야 한다. 우리는 (Maas et al., 2011)의 IMDB movie review dataset을 사용하여 sparse feature 문제를 살펴본다. 우리는 IMDB movie review를 가장 빈도가 높은 처음 10,000개 단어를 포함하는 bag-of-words (BoW) feature vector로 전처리한다. 각 review에 대한 10,000차원 BoW feature vector는 매우 sparse하다. (Wang & Manning, 2013)에서 제안한 바와 같이, BoW feature에 대해 50% dropout noise를 적용할 수 있다
As discussed in (Duchi et al., 2011), Adagrad can efficiently deal with sparse features and gradients as one of its main theoretical results whereas SGD is low at learning rare features. Adam with 1/ √ t decay on its stepsize should theoratically match the performance of Adagrad. We examine the sparse feature problem using IMDB movie review dataset from (Maas et al., 2011). We pre-process the IMDB movie reviews into bag-of-words (BoW) feature vectors including the first 10,000 most frequent words. The 10,000 dimension BoW feature vector for each review is highly sparse. As suggested in (Wang & Manning, 2013), 50% dropout noise can be applied to the BoW features duringMNIST Logistic Regression
MNIST Logistic RegressionAdaGrad SGDNesterov Adam training cost
AdaGrad SGDNesterov Adam training costAdagrad+dropout RMSProp+dropout SGDNesterov+dropout Adam+dropout training to prevent over-fitting. Figure 1에서 Adagrad는 dropout noise의 적용 여부와 무관하게 Nesterov momentum을 사용한 SGD보다 큰 폭으로 우수한 성능을 보인다. Adam은 Adagrad만큼 빠르게 수렴한다. Adam의 실증적 성능은 2절과 4절의 이론적 결과와 일치한다. Adagrad와 마찬가지로, Adam은 sparse features의 이점을 활용하여 일반적인 momentum SGD보다 더 빠른 수렴 속도를 얻을 수 있다.
Adagrad+dropout RMSProp+dropout SGDNesterov+dropout Adam+dropout training to prevent over-fitting. In figure 1, Adagrad outperforms SGD with Nesterov momentum by a large margin both with and without dropout noise. Adam converges as fast as Adagrad. The empirical performance of Adam is consistent with our theoretical findings in sections 2 and 4. Similar to Adagrad, Adam can take advantage of sparse features and obtain faster convergence rate than normal SGD with momentum.다층 신경망(multi-layer neural network)은 비볼록(non-convex) 목적함수를 갖는 강력한 모델이다. 비록 우리의 수렴 분석은 비볼록 문제에는 적용되지 않지만, 실증적으로는 이러한 경우 Adam이 다른 방법보다 종종 더 우수한 성능을 보인다는 것을 확인하였다. 실험에서는 해당 분야의 기존 논문들과 일관되도록 모델을 설정하였으며, 각 1000개의 은닉 유닛을 가진 두 개의 완전연결 은닉층과 ReLU 활성화를 사용하는 신경망 모델을 minibatch size 128로 실험에 사용하였다.
Multi-layer neural network are powerful models with non-convex objective functions. Although our convergence analysis does not apply to non-convex problems, we empirically found that Adam often outperforms other methods in such cases. In our experiments, we made model choices that are consistent with previous publications in the area; a neural network model with two fully connected hidden layers with 1000 hidden units each and ReLU activation are used for this experiment with minibatch size of 128.먼저, 과적합(over-fitting)을 방지하기 위해 파라미터에 L2 weight decay를 적용한 표준 결정론적 cross-entropy 목적함수를 사용하여 여러 최적화 기법을 살펴보았다. 합함수(sum-of-functions, SFO) 방법(Sohl-Dickstein et al., 2014)은 최근 제안된 준뉴턴(quasi-Newton) 방법으로, minibatch 데이터에 적용할 수 있으며 다층 신경망 최적화에서 좋은 성능을 보였다. 우리는 이들의 구현을 사용하여 이러한 모델 학습에서 Adam과 비교하였다. Figure 2는 iteration 수와 wall-clock time 모두에서 Adam이 더 빠르게 진전함을 보여준다. 곡률 정보를 갱신하는 비용 때문에 SFO는 Adam보다 iteration당 5-10배 느리고, memory requirement는 minibatch 수에 비례하여 선형적으로 증가한다.
First, we study different optimizers using the standard deterministic cross-entropy objective function with L2 weight decay on the parameters to prevent over-fitting. The sum-of-functions (SFO) method (Sohl-Dickstein et al., 2014) is a recently proposed quasi-Newton method that works with minibatches of data and has shown good performance on optimization of multi-layer neural networks. We used their implementation and compared with Adam to train such models. Figure 2 shows that Adam makes faster progress in terms of both the number of iterations and wall-clock time. Due to the cost of updating curvature information, SFO is 5-10x slower per iteration compared to Adam, and has a memory requirement that is linear in the number minibatches.dropout과 같은 stochastic regularization 방법은 과적합(over-fitting)을 방지하는 효과적인 방법이며, 단순성 때문에 실제로도 자주 사용된다. SFO는 결정론적 subfunction을 가정하는데, 실제로 stochastic regularization이 포함된 cost function에서는 수렴하지 못했다. 우리는 dropout noise로 학습한 다층 신경망에서 Adam의 효과를 다른 stochastic first-order 방법들과 비교하였다. Figure 2가 우리의 결과를 보여주며, Adam이 다른 방법들보다 더 나은 수렴을 보였다.
Stochastic regularization methods, such as dropout, are an effective way to prevent over-fitting and often used in practice due to their simplicity. SFO assumes deterministic subfunctions, and indeed failed to converge on cost functions with stochastic regularization. We compare the effectiveness of Adam to other stochastic first order methods on multi-layer neural networks trained with dropout noise. Figure 2 shows our results; Adam shows better convergence than other methods.여러 층의 convolution, pooling, non-linear unit을 갖는 convolutional neural networks(CNNs)는 computer vision 과제에서 상당한 성공을 거두었다. 대부분의 fully connected neural net과 달리, CNN에서의 weight sharing은 서로 다른 층에서 매우 다른 gradient를 초래한다. 따라서 SGD를 적용할 때는 convolution 층에 더 작은 learning rate를 사용하는 경우가 많다. 우리는 deep CNN에서 Adam의 효과를 보인다. 우리의 CNN architecture는 5x5 convolution filter와 stride 2의 3x3 max pooling이 번갈아 나타나는 세 단계로 구성되며, 그 뒤에 1000개의 rectified linear hidden unit(ReLU’s)을 갖는 fully connected layer가 이어진다. 입력 이미지는 whitening으로 전처리되며, and
Convolutional neural networks (CNNs) with several layers of convolution, pooling and non-linear units have shown considerable success in computer vision tasks. Unlike most fully connected neural nets, weight sharing in CNNs results in vastly different gradients in different layers. A smaller learning rate for the convolution layers is often used in practice when applying SGD. We show the effectiveness of Adam in deep CNNs. Our CNN architecture has three alternating stages of 5x5 convolution filters and 3x3 max pooling with stride of 2 that are followed by a fully connected layer of 1000 rectified linear hidden units (ReLU’s). The input image are pre-processed by whitening, andMNIST 다층 신경망 + dropout -1
MNIST Multilayer Neural Network + dropout -1AdaGrad RMSProp SGDNesterov AdaDelta Adam training cost -2
AdaGrad RMSProp SGDNesterov AdaDelta Adam training cost -2CIFAR10 ConvNet 첫 3개 epoch
CIFAR10 ConvNet First 3 EpochesAdaGrad AdaGrad+dropout SGDNesterov SGDNesterov+dropout Adam Adam+dropout training cost
AdaGrad AdaGrad+dropout SGDNesterov SGDNesterov+dropout Adam Adam+dropout training costAdaGrad AdaGrad+dropout SGDNesterov SGDNesterov+dropout Adam Adam+dropout dropout noise는 input layer와 fully connected layer에 적용된다. minibatch size도 이전 실험과 마찬가지로 128로 설정하였다.
AdaGrad AdaGrad+dropout SGDNesterov SGDNesterov+dropout Adam Adam+dropout dropout noise is applied to the input layer and fully connected layer. The minibatch size is also set to 128 similar to previous experiments.흥미롭게도, Figure 3(왼쪽)에서 보이듯이 Adam과 Adagrad는 학습 초기 단계에서 모두 cost를 빠르게 낮추지만, Figure 3(오른쪽)에서 보이듯이 CNN에서는 결국 Adam과 SGD가 Adagrad보다 훨씬 더 빠르게 수렴한다. 우리는 두 번째 모멘트 추정치 bvt가 몇 개의 epoch 후 0으로 사라지고 algorithm 1의 ϵ에 의해 지배된다는 점을 관찰하였다. 따라서 두 번째 모멘트 추정치는 Section 6.2의 fully connected network와 비교할 때 CNN의 cost function 기하를 잘 근사하지 못한다. 반면 첫 번째 모멘트를 통해 minibatch variance를 줄이는 것이 CNN에서는 더 중요하며, 속도 향상에 기여한다. 그 결과, 이 특정 실험에서는 Adagrad가 다른 방법들보다 훨씬 느리게 수렴하였다. Adam은 momentum을 사용한 SGD보다 미세한 개선만 보였지만, SGD에서처럼 손으로 일일이 조정하는 대신 층별로 learning rate scale을 적응적으로 조절한다.
Interestingly, although both Adam and Adagrad make rapid progress lowering the cost in the initial stage of the training, shown in Figure 3 (left), Adam and SGD eventually converge considerably faster than Adagrad for CNNs shown in Figure 3 (right). We notice the second moment estimate bvt vanishes to zeros after a few epochs and is dominated by the ϵ in algorithm 1. The second moment estimate is therefore a poor approximation to the geometry of the cost function in CNNs comparing to fully connected network from Section 6.2. Whereas, reducing the minibatch variance through the first moment is more important in CNNs and contributes to the speed-up. As a result, Adagrad converges much slower than others in this particular experiment. Though Adam shows marginal improvement over SGD with momentum, it adapts learning rate scale for different layers instead of hand picking manually as in SGD.Published as a conference paper at ICLR 2015 β2=0.99 β2=0.999 β2=0.9999 β2=0.99 β2=0.999 β2=0.9999
Published as a conference paper at ICLR 2015 β2=0.99 β2=0.999 β2=0.9999 β2=0.99 β2=0.999 β2=0.9999Loss log10(α)
Loss log10(α)우리는 2장과 3장에서 설명한 bias correction term의 효과도 실증적으로 평가하였다. 5장에서 논의하듯이, bias correction term을 제거하면 momentum이 포함된 RMSProp(Tieleman & Hinton, 2012) 버전이 된다. 우리는 (Kingma & Welling, 2013)과 동일한 architecture를 가진 variational autoencoder(VAE)를 학습하면서 β1과 β2를 변화시켰다. 이 모델은 500개의 은닉 유닛을 갖는 단일 은닉층, softplus nonlinearities, 그리고 50차원 spherical Gaussian latent variable을 사용한다. 우리는 매우 넓은 범위의 hyper-parameter 조합, 즉 β1 ∈[0, 0.9], β2 ∈[0.99, 0.999, 0.9999], 그리고 log10(α) ∈[−5, ..., −1]을 반복적으로 실험하였다. 희소 gradient에 대한 강건성을 위해 1에 가까운 β2 값이 필요하지만, 이는 더 큰 초기화 편향을 초래한다. 따라서 이러한 느린 감쇠(slow decay) 상황에서는 bias correction term이 최적화에 미치는 부정적 영향을 막아 주므로 중요하다고 예상된다.
We also empirically evaluate the effect of the bias correction terms explained in sections 2 and 3. Discussed in section 5, removal of the bias correction terms results in a version of RMSProp (Tieleman & Hinton, 2012) with momentum. We vary the β1 and β2 when training a variational autoencoder (VAE) with the same architecture as in (Kingma & Welling, 2013) with a single hidden layer with 500 hidden units with softplus nonlinearities and a 50-dimensional spherical Gaussian latent variable. We iterated over a broad range of hyper-parameter choices, i.e. β1 ∈[0, 0.9] and β2 ∈[0.99, 0.999, 0.9999], and log10(α) ∈[−5, ..., −1]. Values of β2 close to 1, required for robustness to sparse gradients, results in larger initialization bias; therefore we expect the bias correction term is important in such cases of slow decay, preventing an adverse effect on optimization.Figure 4에서 보듯이, β2가 1에 가까운 값은 bias correction term이 없을 경우 학습 불안정을 실제로 초래했으며, 특히 학습 초기 몇 개의 epoch에서 그러했다. 가장 좋은 결과는 작은 (1−β2) 값과 bias correction을 함께 사용했을 때 얻어졌으며, 이는 hidden unit이 특정 패턴에 특화되면서 gradient가 더 희소해지는 최적화 후반부에서 더욱 뚜렷했다. 요약하면, Adam은 hyper-parameter 설정과 무관하게 RMSProp과 같거나 더 나은 성능을 보였다.
In Figure 4, values β2 close to 1 indeed lead to instabilities in training when no bias correction term was present, especially at first few epochs of the training. The best results were achieved with small values of (1−β2) and bias correction; this was more apparent towards the end of optimization when gradients tends to become sparser as hidden units specialize to specific patterns. In summary, Adam performed equal or better than RMSProp, regardless of hyper-parameter setting.Adam에서 개별 가중치의 업데이트 규칙은 현재 및 과거의 개별 gradient에 대한 (스케일된) L2 norm에 반비례하도록 gradient를 조정하는 것이다. 이 L2 norm 기반 업데이트 규칙은 Lp norm 기반 업데이트 규칙으로 일반화할 수 있다. 이러한 변형은 p가 클 때 수치적으로 불안정해진다. 그러나 특수한 경우 p →∞로 두면 놀라울 정도로 단순하고 안정적인 알고리즘이 도출된다. 이는 algorithm 2를 보라. 이제 이 알고리즘을 유도하겠다. Lp norm의 경우, 시간 t에서의 stepsize가 vt1/p에 반비례한다고 하자. 여기서: vt = βp 2vt−1 + (1 −βp 2)|gt|p (6) i=1 βp(t−i) 2 · |gi|p (7)
In Adam, the update rule for individual weights is to scale their gradients inversely proportional to a (scaled) L2 norm of their individual current and past gradients. We can generalize the L2 norm based update rule to a Lp norm based update rule. Such variants become numerically unstable for large p. However, in the special case where we let p →∞, a surprisingly simple and stable algorithm emerges; see algorithm 2. We’ll now derive the algorithm. Let, in case of the Lp norm, the stepsize at time t be inversely proportional to v1/p t , where: vt = βp 2vt−1 + (1 −βp 2)|gt|p (6) i=1 βp(t−i) 2 · |gi|p (7)Algorithm 2: 무한 노름(infinity norm)을 기반으로 한 Adam의 변형인 AdaMax. 자세한 내용은 7.1장을 보라. 시험한 machine learning 문제들에 대한 좋은 기본 설정은 α = 0.002, β1 = 0.9, β2 = 0.999이다. βt 1로는 β1의 t제곱을 뜻한다. 여기서 (α/(1 −βt 1))는 첫 번째 모멘트에 대한 bias-correction term이 포함된 learning rate이다. 벡터에 대한 모든 연산은 원소별(element-wise)로 수행된다. Require: α: Stepsize Require: β1, β2 ∈[0, 1): Exponential decay rates Require: f(θ): 파라미터 θ를 갖는 stochastic objective function Require: θ0: 초기 parameter vector m0 ←0 (1st moment vector 초기화) u0 ←0 (지수 가중 무한 노름 초기화) t ←0 (timestep 초기화) while θt not converged do t ←t + 1 gt ←∇θft(θt−1) (timestep t에서 stochastic objective에 대한 gradient 획득) mt ←β1 · mt−1 + (1 −β1) · gt (bias가 있는 first moment 추정치 갱신) ut ←max(β2 · ut−1, |gt|) (지수 가중 무한 노름 갱신) θt ←θt−1 −(α/(1 −βt 1)) · mt/ut (파라미터 갱신) end while return θt (최종 파라미터)
Algorithm 2: AdaMax, a variant of Adam based on the infinity norm. See section 7.1 for details. Good default settings for the tested machine learning problems are α = 0.002, β1 = 0.9 and β2 = 0.999. With βt 1 we denote β1 to the power t. Here, (α/(1 −βt 1)) is the learning rate with the bias-correction term for the first moment. All operations on vectors are element-wise. Require: α: Stepsize Require: β1, β2 ∈[0, 1): Exponential decay rates Require: f(θ): Stochastic objective function with parameters θ Require: θ0: Initial parameter vector m0 ←0 (Initialize 1st moment vector) u0 ←0 (Initialize the exponentially weighted infinity norm) t ←0 (Initialize timestep) while θt not converged do t ←t + 1 gt ←∇θft(θt−1) (Get gradients w.r.t. stochastic objective at timestep t) mt ←β1 · mt−1 + (1 −β1) · gt (Update biased first moment estimate) ut ←max(β2 · ut−1, |gt|) (Update the exponentially weighted infinity norm) θt ←θt−1 −(α/(1 −βt 1)) · mt/ut (Update parameters) end while return θt (Resulting parameters)감쇠항은 여기서 β2가 아니라 βp 2로 동등하게 매개변수화된다. 이제 p →∞로 보내고, ut = limp→∞(vt)1/p로 정의하면, 다음과 같다: ut = lim p→∞(vt)1/p = lim p→∞
Note that the decay term is here equivalently parameterised as βp 2 instead of β2. Now let p →∞, and define ut = limp→∞(vt)1/p, then: ut = lim p→∞(vt)1/p = lim p→∞= lim p→∞(1 −βp 2)1/p t X
= lim p→∞(1 −βp 2)1/p t X이는 다음과 같이 놀라울 정도로 단순한 재귀식에 대응한다: i=1 βp(t−i) 2 · |gi|p !1/p i=1 βp(t−i) 2 · |gi|p !1/p
Which corresponds to the remarkably simple recursive formula: i=1 βp(t−i) 2 · |gi|p !1/p i=1 βp(t−i) 2 · |gi|p !1/p= max βt−1 2 |g1|, βt−2 2 |g2|, . . . , β2|gt−1|, |gt| (11) ut = max(β2 · ut−1, |gt|) (12)이며 초기값은 u0 = 0이다. 이 경우에는 편의상 초기화 편향을 보정할 필요가 없다는 점에 주목하라. 또한 매개변수 업데이트의 크기에 대한 상한도 Adam보다 AdaMax에서 더 단순하며, 즉 |∆t| ≤α이다.
= max βt−1 2 |g1|, βt−2 2 |g2|, . . . , β2|gt−1|, |gt| (11) ut = max(β2 · ut−1, |gt|) (12) with initial value u0 = 0. Note that, conveniently enough, we don’t need to correct for initialization bias in this case. Also note that the magnitude of parameter updates has a simpler bound with AdaMax than Adam, namely: |∆t| ≤α.마지막 반복값은 확률적 근사 때문에 잡음이 있으므로, 평균화를 통해 더 나은 일반화 성능을 얻는 경우가 많다. 이전에 Moulines & Bach (2011)에서는 Polyak-Ruppert averaging (Polyak & Juditsky, 1992; Ruppert, 1988)이 표준 SGD의 수렴을 개선함이 보였으며, 여기서 ¯θt = 1 t Pn k=1 θk 이다. 또는 매개변수에 대해 지수이동평균(exponential moving average)을 사용할 수도 있는데, 이때 최근 매개변수 값에 더 큰 가중치를 부여한다. 이는 알고리즘 1과 2의 내부 루프에 한 줄만 추가하면 간단히 구현할 수 있으며, ¯θt ←β2 · ¯θt−1 +(1−β2)θt, ¯θ0 = 0으로 둔다. 초기화 편향은 추정량 bθt = ¯θt/(1 −βt 2)로 다시 보정할 수 있다.
Since the last iterate is noisy due to stochastic approximation, better generalization performance is often achieved by averaging. Previously in Moulines & Bach (2011), Polyak-Ruppert averaging (Polyak & Juditsky, 1992; Ruppert, 1988) has been shown to improve the convergence of standard SGD, where ¯θt = 1 t Pn k=1 θk. Alternatively, an exponential moving average over the parameters can be used, giving higher weight to more recent parameter values. This can be trivially implemented by adding one line to the inner loop of algorithms 1 and 2: ¯θt ←β2 · ¯θt−1 +(1−β2)θt, with ¯θ0 = 0. Initalization bias can again be corrected by the estimator bθt = ¯θt/(1 −βt 2).우리는 확률적 목적함수의 기울기 기반 최적화를 위한 단순하고 계산적으로 효율적인 알고리즘을 제안하였다. 우리의 방법은 대규모 데이터셋 및/또는 고차원 매개변수 공간을 갖는 머신러닝 문제를 목표로 한다.
We have introduced a simple and computationally efficient algorithm for gradient-based optimization of stochastic objective functions. Our method is aimed towards machine learning problems withPublished as a conference paper at ICLR 2015 이 방법은 최근 널리 쓰이는 두 최적화 방법의 장점을 결합한다. 하나는 희소한 기울기를 다루는 AdaGrad의 능력이고, 다른 하나는 비정상적 목적함수를 다루는 RMSProp의 능력이다. 이 방법은 구현이 간단하고 메모리 사용량도 적다. 실험 결과는 볼록 문제에서의 수렴 속도에 대한 분석을 확인해 주었다. 전반적으로, 우리는 Adam이 강건하며 머신러닝 분야의 다양한 비볼록 최적화 문제에 잘 적합하다는 것을 발견하였다.
Published as a conference paper at ICLR 2015 large datasets and/or high-dimensional parameter spaces. The method combines the advantages of two recently popular optimization methods: the ability of AdaGrad to deal with sparse gradients, and the ability of RMSProp to deal with non-stationary objectives. The method is straightforward to implement and requires little memory. The experiments confirm the analysis on the rate of convergence in convex problems. Overall, we found Adam to be robust and well-suited to a wide range of non-convex optimization problems in the field machine learning.이 논문은 아마도 Google Deepmind의 지원이 없었다면 존재하지 못했을 것이다. Adam이라는 이름을 만들어 준 Ivo Danihelka와 Tom Schaul에게 특별한 감사를 전한다. 원래 AdaMax 유도에서 오류를 찾아낸 Duke University의 Kai Fan에게도 감사한다. 이 연구의 실험 일부는 SURF Foundation의 지원을 받아 Dutch national e-infrastructure에서 수행되었다. Diederik Kingma는 Google European Doctorate Fellowship in Deep Learning의 지원을 받았다.
This paper would probably not have existed without the support of Google Deepmind. We would like to give special thanks to Ivo Danihelka, and Tom Schaul for coining the name Adam. Thanks to Kai Fan from Duke University for spotting an error in the original AdaMax derivation. Experiments in this work were partly carried out on the Dutch national e-infrastructure with the support of SURF Foundation. Diederik Kingma is supported by the Google European Doctorate Fellowship in Deep Learning.— 그림/표 위주 페이지 —
— 그림/표 위주 페이지 —
— 그림/표 위주 페이지 —
— 그림/표 위주 페이지 —
— 그림/표 위주 페이지 —