PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergence guarantees for RMSProp and ADAM in non-convex optimization and an empirical comparison to Nesterov acceleration

Soham De, Anirbit Mukherjee, Enayat Ullah

arXiv:1807.06766v3cs.LGmath.OCstat.ML

TL;DR

RMSProp and ADAM lacked convergence guarantees for smooth non-convex optimization, while their generalization relative to momentum methods remained uncertain. The paper proves criticality guarantees and runtime bounds, then empirically compares adaptive methods with NAG. It finds that ADAM can match or outperform NAG when β1 is tuned near 1, while the theory and experiments remain subject to stated assumptions and unresolved rate limitations.

  • Problem

    RMSProp and ADAM lacked theoretical justification for non-convex optimization, and their relative training and generalization performance versus momentum methods remained unclear.

  • Method

    The paper proves convergence guarantees and runtime bounds for RMSProp and ADAM, then evaluates them against NAG across autoencoder and image-classification experiments.

  • Results

    ADAM with β1 = 0.99 matches or outperforms carefully tuned NAG and RMSProp in many experiments, while performance is sensitive to β1.

  • Takeaways & Limitations

    Adaptive methods’ empirical performance depends strongly on momentum tuning, and offline deterministic convergence behavior should not be inferred from online optimization results.

  • Takeaways & Limitations

    The deterministic ADAM analysis remains open to tighter convergence rates, and stochastic RMSProp convergence requires an additional gradient-sign assumption.

Abstract

from arXiv · show

RMSProp and ADAM continue to be extremely popular algorithms for training neural nets but their theoretical convergence properties have remained unclear. Further, recent work has seemed to suggest that these algorithms have worse generalization properties when compared to carefully tuned stochastic gradient descent or its momentum variants. In this work, we make progress towards a deeper understanding of ADAM and RMSProp in two ways. First, we provide proofs that these adaptive gradient algorithms are guaranteed to reach criticality for smooth non-convex objectives, and we give bounds on the running time. Next we design experiments to empirically study the convergence and generalization properties of RMSProp and ADAM against Nesterov's Accelerated Gradient method on a variety of common autoencoder setups and on VGG-9 with CIFAR-10. Through these experiments we demonstrate the interesting sensitivity that ADAM has to its momentum parameter $β_1$. We show that at very high values of the momentum parameter ($β_1 = 0.99$) ADAM outperforms a carefully tuned NAG on most of our experiments, in terms of getting lower training and test losses. On the other hand, NAG can sometimes do better when ADAM's $β_1$ is set to the most commonly used value: $β_1 = 0.9$, indicating the importance of tuning the hyperparameters of ADAM to get better generalization performance. We also report experiments on different autoencoders to demonstrate that NAG has better abilities in terms of reducing the gradient norms, and it also produces iterates which exhibit an increasing trend for the minimum eigenvalue of the Hessian of the loss function at the iterates.

1 Introduction

The paper addresses missing non-convex convergence guarantees for widely used adaptive methods and uncertainty about their generalization relative to momentum methods. It combines theoretical guarantees for RMSProp and ADAM with experiments comparing them against NAG.

  • Motivation: Adaptive methods such as RMSProp and ADAM are popular because NAG, HB, and SGD are sensitive to step size, momentum, and batch size, while preconditioning is believed to ease tuning.This motivation concerns practical optimization of neural networks, where adaptive methods use gradient-history-based transformations.
  • Open questions: RMSProp and ADAM lacked theoretical justification for non-convex optimization with exact gradients, despite deterministic settings arising from large batches and variance reduction.The paper frames this as a central open question for adaptive gradient methods.
  • Contributions: The paper provides runtime bounds showing deterministic RMSProp and ADAM reach approximate criticality on smooth non-convex objectives, with stochastic RMSProp covered under an additional assumption.This is presented as the first convergence guarantee for standard adaptive neural-network training heuristics, to the authors’ knowledge.
  • Scope of theory: Theoretical convergence in offline deterministic optimization cannot be inferred directly from counterexamples for ADAM and RMSProp in online convex optimization.The paper explicitly describes the deterministic ADAM result as incomparable to the stochastic-framework counterexample in [36].
  • Empirical results: Experiments compare RMSProp and ADAM with NAG on MNIST autoencoders and CIFAR-10 VGG-9, finding that ADAM with β1 = 0.99 matches or outperforms carefully tuned NAG and RMSProp in training and test loss.RMSProp also fails to generalize soon as autoencoder size increases, with the same behavior appearing in sufficiently large mini-batch networks.
  • Empirical results: The experiments show that tuning ADAM’s β1 closer to 1 can close the generalization gap with NAG and HB observed at standard momentum values.The paper contrasts this controlled finding with prior results where NAG generalized better than ADAM even after tuning β1 [26].

2 Notations and Pseudocodes

This section states the smoothness assumption used in the proofs and introduces the pseudocode-level inputs and updates for NAG, RMSProp, and ADAM. It also defines the square-root Penrose inverse used by the adaptive methods.

  • Assumptions: The proofs assume that the non-convex objective is L-smooth, a standard optimization regularity condition.The section formally introduces L-smoothness before presenting the convergence analysis.
  • Notation: The section introduces the square root of a diagonal matrix’s Penrose inverse as a technical operation used in the adaptive-gradient definitions.This definition supports the coordinatewise transformations underlying the algorithms.
  • NAG: NAG uses a step size α and momentum µ to update a velocity from the gradient evaluated at a momentum-shifted iterate.Its pseudocode accepts an initial point and access to a possibly noisy gradient oracle.
  • RMSProp: RMSProp takes β2, α, and a positive diagonal-shift vector ξ, initializes v0 = 0, and recursively updates its gradient-square accumulator.The supplied pseudocode specifies deterministic gradient access and the accumulator update, though the displayed update is truncated.
  • ADAM: ADAM takes β1, β2, α, and ξ, initializes first- and second-moment estimates to zero, and recursively updates them from each gradient.The pseudocode exposes the two momentum parameters and gradient oracle used by the algorithm.

3 Convergence Guarantees for ADAM and RMSProp

The paper establishes convergence-to-criticality guarantees for stochastic and deterministic RMSProp and deterministic ADAM under explicit assumptions, while identifying technical conditions and open rate limitations.

  • Stochastic RMSProp: Theorem 3.1 guarantees stochastic RMSProp reaches an ϵ-critical point in finite time under smoothness, bounded gradients, a minimizer, and same-orthant stochastic gradients.The guarantee controls the minimum expected squared gradient norm over the first T iterates; the sign condition need only hold on visited points.
  • Deterministic RMSProp: Deterministic RMSProp converges to criticality under smoothness, bounded gradients, and a minimizer, using a constant step length involving the ξ shift.The no-ξ variant instead requires additional objective and step-size assumptions and weakens the rate to T = O(1/ϵ^4).
  • Deterministic RMSProp: The no-ξ deterministic RMSProp variant removes the ξ parameter but incurs weaker convergence rates under stronger assumptions on the objective and step-size modulation.Its guarantee reaches an iterate with gradient norm at most ϵ within T = O(1/ϵ^4) steps.
  • Deterministic ADAM: The ADAM analysis is motivated by determining when convergence is possible despite negative results about ADAM, and it shows the bias-correction factor 1/(1 − β1^t) arises naturally.The discussion distinguishes the theorem’s convergence regime from broader claims about ADAM.
  • Deterministic ADAM: Theorem 3.4 guarantees deterministic ADAM reaches an ϵ-critical iterate when β1 and ξ satisfy explicit bounds, with step sizes chosen accordingly.A stated bound gives T = 9Lσ^2ϵ^-6[f(x2) − f(x*)], while the authors note that tightening this rate remains open.

4 Experimental setup

The experiments compare ADAM and RMSProp with NAG on controlled ReLU autoencoders and VGG-9, using varying network sizes and full-batch or mini-batch datasets.

  • Experimental design: The study compares ADAM and RMSProp with NAG on fully connected ReLU autoencoders with shared weights and on VGG-9 for CIFAR-10.The full-batch experiments use mini-MNIST, while mini-batch experiments use full MNIST and CIFAR-10.
  • Autoencoder architecture: Each autoencoder uses ℓ weight matrices, 2ℓ bias vectors, 2ℓ−1 hidden layers, and squared reconstruction loss.The encoder uses ReLU activations and tied decoder weights in the specified architecture.
  • Motivation: The autoencoder setting is motivated by prior work reporting good MNIST reconstruction from RMSProp on two-layer ReLU autoencoders.The paper notes that comparisons with other methods in regression settings have been relatively limited.
  • Autoencoder architecture: The controlled architecture fixes every layer width to h, enabling depth and width comparisons without added confounding factors.Weights use Glorot initialization, biases are zero-initialized, and no regularization is used.
  • Experimental protocol: The experiments run for 10^5 iterations and select hyperparameters by the lowest training loss at the end of training.The autoencoder experiments use MNIST and vary network depth ℓ and width h.

5 Experimental Results

The experiments show that ξ and momentum substantially affect adaptive-method behavior. ADAM with β1 near 1 often achieves the best losses, while NAG generally reduces gradient norms more effectively and shows a stronger Hessian-eigenvalue trend.

  • 5.1 RMSProp and ADAM are sensitive to choice of ξ: The ξ parameter strongly affects adaptive methods: increasing ξ helps ADAM obtain lower gradient norms and test losses but can worsen training loss.The plotted hyperparameters other than ξ are optimally tuned.
  • 5.2 Tracking λmin(Hessian) of the loss function: NAG gradually increases the minimum Hessian eigenvalue while reducing gradient norms, whereas RMSProp and ADAM reach higher eigenvalues and smaller gradient norms faster but then stagnate.The trend favors NAG, but RMSProp and ADAM achieve better actual gradient-norm and eigenvalue values in the representative experiment.
  • 5.3 Comparing performance in the full-batch setting: ADAM with β1 closer to 1 achieves lower training and test losses than the other algorithms in the full-batch autoencoder experiments.At β1 = 0.9, ADAM can be comparable to or slightly worse than NAG, whereas performance sharply improves as β1 approaches 1.
  • 5.4 Corroborating the full-batch behaviors in the mini-batch setting: In mini-batch experiments, increasing momentum improves both ADAM and NAG across test loss, training loss, and gradient-norm reduction, with the effect more pronounced than in full-batch training.For larger networks, ADAM with β1 near 1 obtains significantly lower test losses than NAG.
  • 5.4 Corroborating the full-batch behaviors in the mini-batch setting: NAG generally obtains the lowest gradient norms, while ADAM with large momentum obtains the best training error on sufficiently large networks.Mini-batching can help NAG outperform ADAM on small networks.

6 Conclusion

The paper concludes that it provides the first convergence-to-criticality guarantees for RMSProp and ADAM in their commonly used non-convex setting. Its experiments show that ξ and momentum choices materially affect performance, with ADAM often strongest when β1 is close to 1.

  • 6 Conclusion: The work presents the first theoretical guarantees of convergence to criticality for RMSProp and ADAM when optimizing smooth non-convex objectives.The guarantees include runtime bounds for deterministic RMSProp and ADAM, and for stochastic RMSProp under an additional assumption.
  • 6 Conclusion: Experiments show that ξ significantly influences adaptive-method performance and that ADAM often surpasses NAG when β1 is very close to 1.The study uses controllable textbook autoencoder architectures to examine adaptivity and momentum.

A.1 Proving stochastic RMSProp (Proof of Theorem 3.1)

The stochastic RMSProp proof analyzes the adaptive update under unbiased, bounded-variance stochastic gradients and derives an iteration bound for reaching approximate criticality.

  • A.1 Proving stochastic RMSProp: The adaptive accumulator is analyzed through a recursion for v_t, with auxiliary variables introduced to bound the preconditioned gradient terms.The proof uses σ_t to control the largest gradient norm encountered up to time t.
  • A.1 Proving stochastic RMSProp: The proof bounds the change in the smooth objective between consecutive iterates using the RMSProp update and conditional expectations over the stochastic gradient.The argument invokes L-smoothness and separately analyzes the adaptive middle term.
  • A.1 Proving stochastic RMSProp: The stochastic RMSProp update uses a preconditioner V_t and a stochastic gradient g_t, with E[g_t] = ∇f(x_t) and E[||g_t||^2] ≤ σ_f^2.The analysis conditions on the history H_t of previous iterates.
  • A.1 Proving stochastic RMSProp: Summing the smoothness inequality over iterations, averaging, and choosing the step length yields a guarantee that stochastic RMSProp reaches ε-criticality within a bounded number of iterations.The final bound follows after substituting the optimized step-length choice.
  • A.1 Proving stochastic RMSProp: The argument establishes nonnegativity of the key cross terms under the stated sign condition on component gradients.This sign condition ensures the relevant products of gradient components are nonnegative.

A.2 Proving deterministic RMSProp - the version with standard speed (Proof of Theorem 3.2)

The proof establishes that deterministic RMSProp reaches an approximate critical point in finite time under smoothness-based conditions, using a constant step length and a decrease argument.

  • Assumptions and conclusion: The theorem’s finite-time guarantee depends on smoothness, accumulator bounds, and the chosen perturbation and step-size parameters.The proof uses L-smoothness and explicitly constructs positive step lengths under these conditions.
  • Accumulator and update bounds: The analysis bounds the evolution of the squared-gradient accumulator and related quantities to control RMSProp’s update direction.The recursion for vt and bounds involving gradient norms support the subsequent descent argument.
  • Criticality guarantee: For sufficiently large T, RMSProp finds an iterate xresult with ∥∇f(xresult)∥2 ≤ ϵ2.The guarantee follows by averaging the descent inequality over iterations and selecting the minimum gradient norm.
  • Step-length construction: A constant step length α = (1−β2)ξ is selected to obtain sufficient decrease in the objective.The proof substitutes this step length into the smoothness bound and derives the stopping condition.
  • Descent argument: The proof derives a per-iteration decrease in function value by analyzing the update as a quadratic in the step length.The quadratic’s minimum supplies a candidate step length and a sufficient decrease bound.

C Effect of the ξ parameter on adaptive gradient algorithms

The experiments vary ξ while holding other hyperparameters fixed, showing that the perturbation parameter materially affects adaptive-method performance.

  • Effect of ξ: Changing ξ can alter ADAM and RMSProp convergence and generalization even when other hyperparameters remain fixed.The experiment uses a one-hidden-layer, 1000-node network with the remaining settings fixed at values tuned for default ξ.
  • Experimental control: The ξ experiments isolate the perturbation parameter’s influence on adaptive gradient algorithms.The reported setup keeps learning rate and momentum or decay parameters unchanged while varying ξ.

D.1 Additional full-batch experiments on 22 × 22 sized images

Across additional full-batch MNIST architectures and input dimensions, ADAM with β1 = 0.99 generally converges faster and generalizes better than NAG, while NAG can outperform β1 = 0.9.

  • Additional architectures: Across almost all additional architectures, ADAM with β1 = 0.99 reaches lower training losses and better generalization than NAG.The accompanying figures report training loss, test loss, and gradient norms across varied network architectures.
  • Input-dimension variation: The input-dimension tests resize 22 × 22 MNIST images to 17 × 17 and 12 × 12 using bilinear interpolation.This tests whether the reported optimizer comparison extends beyond the original input dimension.
  • 17 × 17 inputs: On 17 × 17 inputs, ADAM with β1 = 0.99 converges fastest and generalizes best, whereas NAG outperforms ADAM with β1 = 0.9.The result uses a three-layer network with 1000 hidden nodes per layer.
  • 12 × 12 inputs: On 12 × 12 inputs, the same pattern holds: β1 = 0.99 gives ADAM the fastest convergence and best generalization, while NAG beats β1 = 0.9.These experiments use a three-layer network with 1000 hidden nodes in each layer.

D.3 Additional mini-batch experiments on 22 × 22 sized images

Mini-batch experiments on 22 × 22 MNIST images show that most full-batch findings extend to additional architectures with batch size 100.

  • Mini-batch extension: Most full-batch optimizer comparisons extend to mini-batches of size 100 across additional neural-network architectures.Figure 11 reports training loss, test loss, and training-set gradient norms for the mini-batch experiments.
  • Evaluation setup: The mini-batch evaluation uses the full MNIST dataset with 22 × 22 inputs and tracks training loss, test loss, and gradient norms.The figure organizes these metrics by rows for the additional architectures.

E Image Classification on Convolutional Neural Nets

The VGG-9 CIFAR-10 experiment examines whether ADAM’s momentum sensitivity extends to image classification. With approximately equal loss, ADAM at β1 = 0.99 generalizes as well as NAG and better than ADAM at β1 = 0.9.

  • ADAM with β1 = 0.99 generalizes as well as NAG and better than ADAM with β1 = 0.9 while attaining approximately the same loss value.Tuning β1 helped close ADAM’s generalization gap with NAG on VGG-9 trained with CIFAR-10.
  • The experiment trains a VGG-9 convolutional network on CIFAR-10, which contains 10 classes, using seven convolutional and two fully connected layers.The convolutional layers use 64, 64, 128, 128, 256, 256, and 256 filters of size 3 × 3, with batch normalization and ReLU activations.
Loading 1807.06766v3…