Adam: A Method for Stochastic Optimization

Summary

Strengths

1. Complete, cheap and directly implementable algorithm

   Algorithm 1 and Sec. 2 (p.2)

   Algorithm 1 specifies every quantity and default ($\alpha=10^{-3}$, $\beta_1=0.9$, $\beta_2=0.999$, $\epsilon=10^{-8}$). It needs $O(d)$ extra memory and elementwise operations only. The efficient ordering in Sec. 2 reproduces Algorithm 1 to $2.2\times10^{-16}$ once $\hat\epsilon=\epsilon\sqrt{1-\beta_2^t}$ (check 12).

2. Correct and well-motivated bias correction

   Sec. 3, eqs. (1)-(4) (p.3); Sec. 6.4, Fig. 4 (p.8)

   Eqs. (1)-(4) are verified symbolically: $(1-\beta)\sum_i\beta^{t-i} = 1-\beta^t$. Monte Carlo gives $E[\hat v_1]=4.2599\pm0.0135$ vs. true 4.25, while the uncorrected $E[v_1]=0.00426$ (check 07). The correction is the paper's main technical novelty over RMSProp. Its necessity for $\beta_2\to1$ is supported by the mechanism behind Fig. 4: uncorrected first steps grow as $(1-\beta_1)/\sqrt{1-\beta_2}$, i.e. 3.162α at the defaults and 10α at $\beta_2=0.9999$ (check 15).

3. Clean unification with AdaGrad and RMSProp

   Sec. 5 (p.4-5)

   The limit $\lim_{\beta_2\to1}\hat v_t = t^{-1}\sum_i g_i^2$ holds symbolically for t=1..6. Numerically it matches to a relative error of 4.89e-12. Trajectories approach AdaGrad in proportion to $1-\beta_2$ (check 14). The contrast with RMSProp (momentum on the rescaled gradient, no bias correction) states clearly what is new.

4. Elegant and correct AdaMax derivation

   Sec. 7.1, eqs. (6)-(12), Algorithm 2 (p.8-9)

   The $\ell_p\to\ell_\infty$ limit in eqs. (8)-(11) and the recursion $u_t=\max(\beta_2u_{t-1},|g_t|)$ in eq. (12) check out. The recursion equals the max formula to 1.6e-61, and the p-norm expression converges monotonically, with relative error 4.52e-9 at $p=10^4$ (check 11).

5. Useful practitioner intuition about step scale and invariance

   Sec. 2.1 (p.2-3)

   Sec. 2.1 frames $\alpha$ as a trust-region radius and $\hat m/\sqrt{\hat v}$ as a signal-to-noise ratio. This gives concrete guidance for setting $\alpha$. Invariance to scalar and diagonal gradient rescaling is exact for $\epsilon=0$, with trajectories identical to 4.2e-16 (check 13). For typical gradient sequences the steps stay near $\alpha$ (e.g. 2.66α for a spike with the defaults, check 09).

6. Experiments cover diverse settings and several baselines

   Sec. 6.1-6.4, Figs. 1-4 (p.5-8)

   The experiments span convex dense and sparse problems (MNIST and IMDB BoW logistic regression), non-convex MLPs with and without dropout, a CNN on CIFAR-10 and a VAE. They compare against SGD-Nesterov, AdaGrad, RMSProp, AdaDelta and SFO. On a synthetic sparse BoW proxy we saw the same qualitative pattern as Fig. 1 (right): adaptive methods reached final training NLL 0.0333 (Adam) and 0.0280 (AdaGrad) vs. 0.2224 for SGD-Nesterov (check 16, inconclusive as evidence about the actual figure).

Weaknesses

1. Theorem 4.1 / Corollary 4.2 are false as stated

   major · Sec. 4, Theorem 4.1 and Corollary 4.2 (p.4); Appendix Theorem 10.5 (p.13-15)

   We simulated the online problem of Reddi, Kale & Kumar (ICLR 2018): $f_t(x)=3x$ if $t\bmod3=1$ else $-x$ on $X=[-1,1]$. It satisfies every hypothesis (gradients ≤3, bounded iterates, $\gamma=0<1$, $\alpha_t=\alpha/\sqrt t$). Adam's average regret $R(T)/T$ is 0.68612, 0.66812 and 0.66692 at $T=10^3, 10^5, 3\cdot10^6$, converging to 2/3 rather than 0, and the iterates go to the worst point $x=+1$. At $T=3\cdot10^6$ the regret $2.00\times10^6$ exceeds the Theorem 4.1 right-hand side $1.40\times10^5$ (check 01). Without projection (convex barrier instead) the value was 0.69052, and bias correction changed $R(T)$ only in the 5th significant digit.

   The claim that the regret bound is 'comparable to the best known results' (abstract, p.1) and the transfer of the Duchi et al. $O(\log d\sqrt T)$ rate to Adam (p.4) therefore have no support. Fix: withdraw the theorem, or prove a bound for a modified algorithm. One option is to enforce a non-decreasing $\sqrt{t\hat v_t}/\alpha$, e.g. by using $\max_{s\le t}\hat v_s$.

2. Telescoping step of the proof needs a monotonicity that does not hold

   major · Appendix 10.1, proof of Theorem 10.5 (p.14 to first display of p.15)

   Bounding $\sum_t(\theta_t-\theta^*)^2(\sqrt{\hat v_t}/\alpha_t-\sqrt{\hat v_{t-1}}/\alpha_{t-1})$ by $D_\infty^2\sqrt{T\hat v_T}/\alpha$ requires every bracket to be non-negative. The assumptions do not guarantee this. On the check-01 gradient sequence, 13329 of 20000 brackets are negative ($\beta_2=0.9$), and for a periodic spike 19980 of 20000 are negative. With iterates chosen inside the assumed bounded set, the sum exceeds the claimed bound by factors of 1.23 to 4039.54 (check 02). This is the root cause of the counterexample in check 01.

3. Lemma 10.3 is false and the proof of Lemma 10.4 is invalid

   major · Appendix 10.1, Lemma 10.3 (p.12), Lemma 10.4 (p.13)

   Lemma 10.3, $\sum_t\sqrt{g_{t,i}^2/t}\le2G_\infty\|g_{1:T,i}\|_2$, is dimensionally inconsistent: the LHS scales like $g$ and the RHS like $g^2$. It fails already at the induction base: $T=1$, $G_\infty=g_1=1/4$ gives LHS 1/4 > RHS 1/8. It also fails for $G_\infty=1$ at $T=31$ (4.027245195 > 4.013599479) (check 03). A valid replacement via Cauchy-Schwarz adds a $\sqrt{\log T}$ factor to the second term.

   The statement of Lemma 10.4 held in all 36 of our examples (max ratio 0.311). However, its proof uses $\sum_{j}t\gamma^j\le1/(1-\gamma)^2$, which gives 5274.4 vs. 27.819 at $t=1000$. The bound the proof actually reaches (with an extra $G_\infty$ and $(1-\gamma)^2$) differs from the statement and is itself violated, e.g. 0.087994 > 0.078685 (check 04).

4. Constant term of the regret bound is unjustified and inconsistent

   major · Appendix p.15 (last three displays); Theorem 4.1 (p.4); Theorem 10.5 (p.14)

   The third term $D_\infty^2G_\infty\sqrt{1-\beta_2}/(2\alpha(1-\beta_1)(1-\lambda)^2)$ relies on $\sqrt{\hat v_t}\le G_\infty\sqrt{1-\beta_2}$. This fails for constant gradients, where $\hat v_t=G_\infty^2$. At $\lambda=0.9$ the true sum is 2.696964e4 vs. the stated term 1.581139e4. Without the $\sqrt{1-\beta_2}$ factor the bound holds. The final display on p.15 has $2\alpha\beta_1(1-\lambda)^2$ where Theorem 4.1 has $2\alpha(1-\beta_1)(1-\lambda)^2$, and it is exceeded for all three tested $\lambda$ (check 05). Theorem 4.1 also uses $D$ where the per-coordinate argument yields $D_\infty$.

5. Theory analyses a different algorithm from the one proposed and tested

   major · Sec. 4 (p.4) vs. Algorithm 1 (p.2); Appendix p.14; Sec. 6.1 (p.5)

   Theorem 4.1 requires $\alpha_t=\alpha/\sqrt t$, a decaying $\beta_{1,t}=\beta_1\lambda^{t-1}$ and bounded iterates. Algorithm 1 uses constant $\alpha$ and $\beta_1$ and has no projection, so boundedness is assumed about the algorithm's output rather than enforced. The proof applies the correction $1-\beta_1^t$ to a moment built with $\beta_{1,t}$, which is biased: $\hat m/E[g]=1.939168$ at $t=5$ for $\lambda=0.9$. The correct factor is $1-\prod_k\beta_{1,k}$ (check 08). This effect is negligible for $\lambda=1-10^{-8}$ (2.7e-7), but the analysed method is not fully specified, and Sec. 6.1 never says whether $\beta_1$ was decayed. The paper should state precisely which variant each result applies to.

6. Explicit step-size bounds in Sec. 2.1 and for AdaMax are not upper bounds

   major · Sec. 2.1 (p.2-3); Sec. 7.1, end (p.9)

   Sec. 2.1 states $|\Delta_t|\le\alpha(1-\beta_1)/\sqrt{1-\beta_2}$ (3.1623α at the defaults), or $\le\alpha$ in the other case. Algorithm 1 with $\epsilon=0$ reaches 5.7812α at the defaults (the supremum tends to 7.27α). It reaches 1.8282α for $\beta_1=0.99,\beta_2=0.999$ (claimed ≤1) and 996.66α for $\beta_1=0.9,\beta_2=0.8$, which Algorithm 1 permits. A single spike after 999 small gradients already gives 1.0846α > α (check 09).

   The AdaMax claim $|\Delta_t|\le\alpha$ (p.9) is exceeded too: 1.009091α at the defaults, 1.899429α at $\beta_2=0.95$, and unbounded when $\beta_1\ge\beta_2$ (check 10). The one-hot sparse case is not the worst case, contrary to the text. Fix: state the closed-form supremum, which requires $\beta_1^2<\beta_2$ (resp. $\beta_1<\beta_2$ for AdaMax), and keep 'approximately bounded' as intuition.

7. Empirical evidence is thin and overstated

   major · Sec. 1 (p.2), Sec. 6 (p.5-8), Sec. 8 (p.10), Figs. 1-3

   The only protocol given is that hyper-parameters 'are searched over a dense grid' (p.5). The grids are not listed, each curve is a single run with no seeds or error bars, only training cost is reported (no held-out metrics), and no code is released. Figures 1-4 therefore cannot be regenerated (checks 16, 18).

   Several sentences claim more than the figures show. p.2 says 'our method consistently outperforms other methods', while Sec. 6.3 (p.7) concedes a 'marginal improvement' over SGD on the CNN. p.6 says the performance is 'consistent with our theoretical findings in sections 2 and 4', and p.10 that 'the experiments confirm the analysis on the rate of convergence in convex problems'. Training-cost curves from single runs cannot confirm a regret bound, and that bound is false (check 01). Fix: report grids, several seeds with spread, test metrics and code, and soften these sentences.

8. Regret bound is vacuous for the suggested $\lambda$

   minor · Sec. 4, text before Theorem 4.1 (p.4)

   Taken at face value with $G=D=1$ and the defaults, the constant term is 1.58114e18 for the suggested $\lambda=1-10^{-8}$ (p.4). The bound beats the trivial $TGD$ only for $T\ge1.581\times10^{18}$, or $2.35\times10^8$ at $\lambda=0.999$ (check 06). Even a corrected theorem would need to discuss this dependence on $(1-\lambda)^{-2}$. (Check 06 confirms $\gamma=0.8104<1$ at the defaults.)

9. Bias-correction residual $\zeta$ and $\epsilon$ effects not quantified

   minor · Sec. 3, eq. (4) (p.3); Abstract; Sec. 6.3 (p.7)

   Eq. (4) says $\zeta$ 'can be kept small' under non-stationarity. With a linearly drifting second moment ($E[g_t^2]=1+0.02t$) and $\beta_2=0.999$, the corrected $\hat v_t$ underestimates by 32.444% at $t=100$ and 39.760% at $t=1000$ (6.0% for $\beta_2=0.9$) (check 07). This qualifies the abstract's 'appropriate for non-stationary objectives'.

   Similarly, the abstract's invariance claim holds only when $|g|\gg\epsilon$. At gradient scale $10^{-6}$ the trajectories deviate by 3.839e-3 (check 13), which is exactly the regime Sec. 6.3 describes, where $\epsilon$ dominates.

10. Notational slips and undefined symbols

    minor · Sec. 2 (p.2), Sec. 3 (p.3), Sec. 5 (p.5), Sec. 7.2 (p.9)

    • $\hat\epsilon$ in the efficient form (p.2) is never defined. Equivalence to Algorithm 1 needs $\hat\epsilon=\epsilon\sqrt{1-\beta_2^t}$; with $\hat\epsilon=\epsilon$ the trajectories differ by 3.663e-3 at gradient scale $10^{-6}$ (check 12).
    • p.3 attributes the choice of decay rate in the $v_t$ derivation to $\beta_1$; it should be $\beta_2$.
    • p.3 says the problem arises for 'a small value of $\beta_2$', and p.2 speaks of small decay rates with the βs close to 1. The problem actually arises for $\beta_2$ close to 1, i.e. small $1-\beta_2$ (check 15).
    • The AdaGrad formula on p.5 writes $\sum_{i=1}^t g_t^2$ instead of $g_i^2$ (check 14).
    • Sec. 7.2 reuses $\beta_2$ for a different decay.

11. Bibliographic inaccuracies

    minor · References (p.10-11)

    • Kingma & Welling is dated '2nd ICLR, 2013'; the 2nd ICLR was in 2014.
    • Zinkevich (2003), which underpins Sec. 4, has no venue (ICML 2003).
    • Tieleman & Hinton (2012) is a Coursera lecture slide cited as a technical report, so no formal specification of RMSProp is available to readers.
    • Ruppert (1988) could not be located (check 17).

Questions for the authors

1. Given the reproduced counterexample (check 01), which satisfies every hypothesis of Theorem 4.1, which additional assumption or algorithmic change (e.g. a non-decreasing $\sqrt{t\hat v_t}$, or using $\max_{s\le t}\hat v_s$) do you propose so that an $O(\sqrt T)$ regret bound holds, and does it cover Algorithm 1 as used in Sec. 6?

2. Lemma 10.3 fails at T=1 for $G_\infty<1/2$. What was the intended statement? Does the corrected version (with a $\sqrt{\log T}$ factor) still give $R(T)/T\to0$ in combination with a fixed telescoping step?

3. In the Sec. 6.1 experiments that use $\alpha_t=\alpha/\sqrt t$, was $\beta_{1,t}$ also decayed, and with which $\lambda$ and which bias-correction factor?

4. What grids were searched for each optimizer, how many seeds were run, and how much do the curves in Figs. 1-3 vary across seeds? Do the rankings hold on held-out loss or accuracy?

5. What value of $\hat\epsilon$ does the efficient implementation (p.2) use, and were the experiments run with Algorithm 1 or the efficient form?

Verification

References

23 references checked

• Kingma & Welling 2013, Auto-Encoding Variational Bayes, 'The 2nd International Conference on Learning Representations (ICLR), 2013'

  Year/venue mismatch: the 2nd ICLR took place in 2014; arXiv:1312.6114 was submitted 20 Dec 2013 (verified on arxiv.org). Should read ICLR 2014 (or arXiv 2013).

• Zinkevich 2003, Online convex programming and generalized infinitesimal gradient ascent

  Incomplete entry: no venue given. The work is ICML 2003 (found at cdn.aaai.org/ICML/2003/ICML03-120.pdf). Load-bearing for Section 4; content matches the citation (online convex programming framework, regret).

• Tieleman & Hinton 2012, Lecture 6.5 - RMSProp, COURSERA, 'Technical report'

  Mis-typed as a technical report: it is an unpublished Coursera lecture slide deck (Lecture 6e, 'rmsprop: Divide the gradient by a running average of its recent magnitude'). Content supports the RMSProp description, but readers cannot consult a formal specification (e.g. no bias correction, no epsilon).

• Ruppert 1988, Efficient estimations from a slowly convergent Robbins-Monro process, Cornell technical report

  Could not be located online (Crossref returned unrelated works); existence not verified, though it is a widely cited technical report. Not load-bearing (cited for Polyak-Ruppert averaging in Section 7.2).

• Duchi et al. 2011 (cited on p.4 for O(log d sqrt(T)) vs O(sqrt(dT)))

  The reference supports the claim for AdaGrad (their Section 1.2 example gives an O(log d) factor for sparse features), but the paper states that 'their results ... also apply to Adam', which depends on Theorem 4.1; checks 01-05 show that theorem and its proof do not hold as stated, so this transfer is unsupported.

Suggestions

• Replace Sec. 4 and Appendix 10.1 with a correct result. Either restrict the claim to a modified algorithm whose effective step $\alpha_t/\sqrt{\hat v_t}$ is non-increasing, and prove it, or remove the regret claim from the abstract and conclusion.

• Correct Lemma 10.3 (e.g. via Cauchy-Schwarz, accepting a $\sqrt{\log T}$ factor), align the statement and proof of Lemma 10.4, and make the constants in Theorems 4.1 and 10.5 and the final display on p.15 agree ($D$ vs. $D_\infty$, $\beta_1$ vs. $1-\beta_1$, the $\sqrt{1-\beta_2}$ factor).

• If $\beta_{1,t}$ decays, use the bias correction $1-\prod_{k\le t}\beta_{1,k}$ and state explicitly which algorithm variant each theoretical and empirical result refers to.

• Replace the inequalities in Sec. 2.1 and Sec. 7.1 by the exact supremum of $|\hat m_t|/\sqrt{\hat v_t}$ (resp. $|m_t|/u_t$), state the needed condition $\beta_1^2<\beta_2$ (resp. $\beta_1<\beta_2$), and present 'approximately bounded by α' as typical-case intuition.

• Release code. List the hyper-parameter grids per optimizer, report several seeds with confidence bands and held-out metrics, and add wall-clock comparisons.

• Soften 'consistently outperforms' (p.2) and 'the experiments confirm the analysis on the rate of convergence' (p.10) to match Fig. 3 and the status of the theory.

• Define $\hat\epsilon=\epsilon\sqrt{1-\beta_2^t}$ in the efficient form, and qualify the invariance claim in the abstract with $|g|\gg\epsilon$.

• Quantify $\zeta$ in eq. (4) for a simple drift model and discuss the trade-off in the choice of $\beta_2$ for non-stationary objectives. Fix the $\beta_1/\beta_2$ slips on p.2-3 and the index typo on p.5.

• Update the bibliography: Kingma & Welling (ICLR 2014), Zinkevich (ICML 2003), Tieleman & Hinton (lecture slides).

Scope of this review