Source-linked AI summary
The Marginal Value of Adaptive Gradient Methods in Machine Learning
Ashia C. Wilson, Rebecca Roelofs, Mitchell Stern, Nathan Srebro, Benjamin Recht
TL;DR
The paper examines whether increasingly popular adaptive optimizers generalize as well as non-adaptive methods, especially when overparameterization permits multiple solutions. It combines a binary-classification construction with deep-learning experiments and finds that adaptive methods can generalize substantially worse despite equal or better training performance. The authors conclude that optimizer choice and tuning deserve renewed scrutiny, while noting uncertainty about adaptive methods in optimization-free applications.
Problem
The generalization and out-of-sample behavior of adaptive gradient methods remains poorly understood, although they are widely used for deep learning.
Method
The paper constructs an overparameterized binary-classification example and evaluates adaptive and non-adaptive methods on deep-learning models.
Results
Adaptive methods can approach 50% test error in the constructed problem and generally generalize worse than non-adaptive methods in experiments, even with equal or lower training loss.
Takeaways & Limitations
Optimizer choice influences the solutions and generalization behavior obtained in overparameterized learning, and tuning adaptive methods can improve their performance.
Takeaways & Limitations
The paper leaves open why adaptive methods remain popular and whether their dynamics are well matched to GANs and Q-learning, which are not optimization problems.
Abstract
from arXiv · showhide
Adaptive optimization methods, which perform local optimization with a metric constructed from the history of iterates, are becoming increasingly popular for training deep neural networks. Examples include AdaGrad, RMSProp, and Adam. We show that for simple overparameterized problems, adaptive methods often find drastically different solutions than gradient descent (GD) or stochastic gradient descent (SGD). We construct an illustrative binary classification problem where the data is linearly separable, GD and SGD achieve zero test error, and AdaGrad, Adam, and RMSProp attain test errors arbitrarily close to half. We additionally study the empirical generalization capability of adaptive methods on several state-of-the-art deep learning models. We observe that the solutions found by adaptive methods generalize worse (often significantly worse) than SGD, even when these solutions have better training performance. These results suggest that practitioners should reconsider the use of adaptive methods to train neural networks.
1 Introduction
Adaptive methods can select solutions with substantially different generalization behavior from non-adaptive methods in overparameterized learning. The paper combines a theoretical construction with experiments showing worse held-out performance despite competitive training behavior.
- Overparameterization makes optimizer choice capable of dramatically changing the learned model.
- AdaGrad, RMSProp, and Adam can misclassify new binary-classification data with probability arbitrarily close to half, despite linear separability.
- SGD achieves zero error on new data in the same binary-classification example.
- Numerical experiments find that SGD and momentum outperform adaptive methods on development/test sets across evaluated models and tasks, even at equal or lower training loss.
- The paper challenges the view that adaptive methods require less tuning and proposes a learning-rate and decay-tuning scheme that performs well on the studied tasks.
2 Background
The paper situates adaptive optimization within stochastic and momentum-based methods, emphasizing that adaptive algorithms alter the local geometry using iterate history. It connects this design choice to the broader question of how optimization algorithms influence generalization.
- Optimization methods: Stochastic gradient methods compute updates using gradients evaluated on data batches.
- Optimization methods: Stochastic momentum methods introduce a second family of techniques intended to accelerate training, including heavy-ball and Nesterov methods.
- Adaptive methods: Adaptive methods construct a local distance measure from the full sequence of iterates, distinguishing them from standard stochastic and momentum formulations.
- Adaptive methods: Adaptive preconditioners typically use diagonal entries based on square roots of combinations of past gradient components, whereas SGD corresponds to H_k = I.
- Generalization: Generalization concerns performance on a broader population, often measured with a loss different from the training objective, such as classification error instead of cross-entropy.
- Related work: Prior work links optimization choices, stability, implicit regularization, and minimizer geometry to differences in generalization.
3 The potential perils of adaptivity
In overparameterized least-squares classification, non-adaptive methods converge to the minimum-Euclidean-norm, maximum-margin solution, while adaptive methods can select much simpler low-ℓ∞-norm solutions with poor generalization. A constructed separable problem makes this contrast explicit: AdaGrad predicts every unseen example positive, whereas SGD makes no errors under a stated class-balance condition.
- Setup: When d > n and zero training loss is attainable, infinitely many global minimizers exist, so the algorithm determines which solution is learned.The central question is how these solutions perform on unseen data.
- 3.1 Non-adaptive methods: Non-adaptive methods initialized in the row span of X converge to the unique minimum-Euclidean-norm solution, which also has the largest margin.This includes GD, SGD, momentum SGD, Nesterov’s method, and conjugate gradient.
- 3.2 Adaptive methods: Adaptive methods can converge instead to solutions with low ℓ∞ norm rather than low ℓ2 norm.For a condition X sign(X^T y) = cy, AdaGrad, Adam, and RMSProp converge from w0 = 0 to a solution proportional to sign(X^T y).
- 3.3 Adaptivity can overfit: The example illustrates that adaptive methods can find solutions with arbitrarily poor out-of-sample error despite the existence of a perfectly generalizing solution.The construction is deliberately extreme but shares sparse-feature and overfitting characteristics with common machine-learning instances.
- 3.3 Adaptivity can overfit: The constructed data use one class-label feature, two constant features, and example-specific features that are useless outside the training set.The example can be represented in finite dimension 6n, comparable to contemporary overparameterized settings.
- 3.3 Adaptivity can overfit: AdaGrad labels every unseen example positive, whereas SGD makes no errors whenever n+ > n−/3.Both conclusions follow from how their selected solutions interact with the only features shared by a new test point.
4 Deep Learning Experiments
The experiments compare SGD and heavy ball with AdaGrad, RMSProp, and Adam across four deep learning problems, using controlled architectures, repeated runs, fixed budgets, and hyperparameter tuning. Adaptive methods often progress faster initially or attain lower training loss, yet non-adaptive methods generally achieve better development or test performance.
- Experimental setup: Four problems—CIFAR-10, War and Peace character-level language modeling, and discriminative and generative Penn Treebank parsing—were evaluated with minimal architectural and preprocessing changes.The study compares SGD and heavy ball against AdaGrad, RMSProp, and Adam across these tasks.
- Experimental setup: Five random initializations and fixed epoch budgets were used, with settings selected by peak development performance when a development set was available.For CIFAR-10, settings were selected by the lowest training loss at the end of the fixed budget.
- Overall findings: Adaptive methods generalize worse than non-adaptive methods even when their training loss is equal to or lower.This pattern is reported as a primary finding across the experiments.
- Overall findings: Adaptive methods often make faster initial training progress, but their development or test performance quickly plateaus.The CIFAR-10 results show adaptive methods initially ahead, followed by SGD and heavy ball surpassing them on test error from epoch 50 onward.
- Hyperparameter tuning: Tuning Adam’s initial learning rate and decay scheme significantly improved its results over default settings in all evaluated cases.The study recommends development-based decay when a development set is available; it produced results comparable to or better than fixed decay.
- Convolutional Neural Network: 7.65 ± 0.14% test error was achieved by SGD, compared with 9.60 ± 0.19% for RMSProp on CIFAR-10.The best non-adaptive result was lower than the best adaptive result.
- Character-Level Language Modeling: 1.212 ± 0.001 was SGD’s lowest test loss in character-level language modeling, while RMSProp closely trailed SGD and adaptive methods showed greater sensitivity to initialization.Some RMSProp configurations reduced training loss below SGD’s but produced erratic test behavior.
- Constituency Parsing: SGD achieved the best overall development performance in constituency parsing, while Adam’s default configuration trained best by run end but performed worse than tuned Adam on development data.In another parsing result, Adam achieved the worst development perplexities despite a strong training curve.
5 Conclusion
The conclusion reports that adaptive methods were not advantageous in the experiments, while acknowledging uncertainty about whether their dynamics may suit optimization-free applications. It identifies understanding these possibilities as future work.
- Conclusion: The experiments did not find adaptive methods advantageous for machine learning, despite Adam’s continuing popularity.The authors hope their step-size tuning suggestions make standard stochastic gradient methods easier to use.
- Conclusion: GANs and Q-learning with function approximation are identified as applications where adaptive methods may be especially popular because they are not solving optimization problems.The authors suggest Adam’s dynamics might be well matched to these iterative search procedures, but do not establish this explanation.
- Conclusion: Determining which explanation is correct and why remains an open direction for future work.
A Full details of the minimum norm solution from Section 3.3
The appendix derives the minimum-norm solution using the kernel trick by expressing the solution through the data matrix, labels, and inverse Gram matrix. It reduces the coefficients by label class and solves the resulting system.
- Kernel-trick derivation: The minimum-norm solution is written as w_SGD = X^T α, with α = K^-1y and K = XX^T.This is the kernel-trick representation used for the derivation.
- Kernel-trick derivation: The appendix provides the relevant kernel-matrix entries for matching and opposing labels.The listed cases distinguish i = j from i ≠ j and same from opposite labels.
- Kernel-trick derivation: The coefficients are parameterized by two values, α+ for positive labels and α− for negative labels.This label-based parameterization reduces the solution to a smaller system of equations.
- Kernel-trick derivation: The resulting system is solved to obtain equation (3.2).
B Differences between Torch, DyNet, and Tensorflow
The appendix records framework-specific default hyperparameters and implementation details for the optimization algorithms used in the experiments. Heavy ball uses a constant momentum value across the reported framework implementations.
- Framework defaults: Table 3 lists the default algorithm hyperparameters for the deep learning frameworks used in the experiments.
- Framework implementations: Heavy ball is implemented through nonzero default momentum in Torch and separately from ordinary SGD in TensorFlow and DyNet.
- Framework implementations: β = 0.9 is used as the constant momentum for the heavy ball experiments.
C Data-generating distribution
The data-generating construction extends the separation between SGD and AdaGrad from a non-i.i.d. example to an i.i.d. distribution. As the tolerance shrinks, SGD's error approaches zero while AdaGrad's approaches 1 − p.
- C Data-generating distribution: The distribution is uniform over N examples, and the training set contains n i.i.d. draws from it.N is chosen large enough that repeated training examples are unlikely.
- C Data-generating distribution: Conditioned on no repeated training examples, SGD learns a perfect classifier while AdaGrad correctly classifies training examples but predicts ˆy = 1 for all unseen points.The two methods therefore have different conditional population errors despite fitting the training set.
- C Data-generating distribution: The unconditional errors are obtained by combining the no-repeat case with trivial conditional-error bounds when repeats occur.The resulting bounds are stated separately for SGD and AdaGrad.
- C Data-generating distribution: N ≥ n2 suffices for SGD error at most ϵ and for AdaGrad error at least (1 − p)(1 − ϵ).These bounds use the tolerance ϵ and the distribution size N.
- C Data-generating distribution: As ϵ → 0, SGD error tends to 0 and AdaGrad error tends to 1 − p, matching the original non-i.i.d. result.The conclusion follows because the choice of ϵ is arbitrary.
Cifar-10
The CIFAR-10 section records the tested hyperparameter settings for AdaGrad and RMSProp and notes that Torch defaults for several methods were outside the tested range.
- Cifar-10: AdaGrad was evaluated at step sizes 0.1, 0.05, 0.01, 0.0075, and 0.005, with 0.01 designated best by default.The listed values define the tested AdaGrad grid.
- Cifar-10: RMSProp was evaluated at step sizes 0.005, 0.001, 0.0005, 0.0003, and 0.0001, with 0.0003 designated best.The listed values define the tested RMSProp grid.
- Cifar-10: Torch default step sizes for SGD, HB, and RMSProp were outside the range tested.The defaults were 0.001 for SGD and HB and 0.01 for RMSProp.
War & Peace
The War & Peace experiments specify tested step sizes and fixed-decay settings, while RMSProp was unavailable in the DyNet version used.
- War & Peace: SGD and HB were each tested with step sizes 2, 1, 0.5, 0.25, and 0.125, with 1 marked best.Both methods share the same tested grid and selected value.
- War & Peace: AdaGrad was tested with step sizes 0.4, 0.2, 0.1, 0.05, and 0.025, with 0.05 marked best.The selected value is part of the listed AdaGrad grid.
- War & Peace: Fixed-decay settings varied decay frequencies over {10, 20, 40, 80, 120, 160, ∞} and decay amounts over {0.1, 0.5, 0.8, 0.9}.The experiment selected from both parameter sets.
- War & Peace: RMSProp was not implemented in DyNet at the time of writing and was therefore unavailable for the experiment.This is an implementation boundary of the reported comparison.