TL;DR
This paper investigates whether the minimum norm solution, often sought by standard gradient descent, is always the best for generalization in over-parameterized models. The authors demonstrate through theoretical analysis and empirical experiments that adaptive optimization methods can find solutions with better generalization performance, even if these solutions have larger weight norms, challenging the notion that minimum norm is the sole indicator of good generalization.
What Problem Does This Paper Address?
Training deep neural networks (DNNs) often involves navigating a complex optimization landscape. While Stochastic Gradient Descent (SGD) is a workhorse, it requires careful hyperparameter tuning. Adaptive methods like AdaGrad and Adam aim to automate this tuning by adjusting learning rates based on past gradients. However, a key question is how these adaptive methods compare to standard SGD in terms of generalization, especially in over-parameterized settings where models have more parameters than data points. Previous work (Wilson et al., 2017) suggested that SGD, by converging to a minimum norm solution, might generalize better than adaptive methods in certain linear regression scenarios. This paper aims to further explore this conjecture, questioning whether the minimum norm solution is indeed always the best for generalization and whether adaptive methods can offer advantages.
Methods
The authors employ a two-pronged approach:
- Theoretical Analysis: They analyze the behavior of gradient descent and adaptive methods (specifically AdaGrad) in simplified linear regression settings, both under-parameterized and over-parameterized. They derive closed-form solutions for the iterates of these algorithms to understand their convergence properties and the nature of the solutions they find.
- Empirical Evaluation: They conduct experiments on various datasets and neural network architectures, comparing the generalization performance of plain gradient descent against adaptive methods like AdaGrad, Adam, and RMSProp. They also introduce a modified counterexample to further probe the differences in generalization behavior.
Datasets
The paper uses the following datasets for training and evaluation:
- MNIST
- CIFAR-10
- CIFAR-100
Key Insights and Ideas
- Minimum Norm is Not Always Best: The paper strongly suggests that the minimum norm solution, which plain gradient descent often finds in over-parameterized settings, is not necessarily the best for generalization. Adaptive methods can find solutions with larger weight norms that generalize better.
- Adaptive Methods Can Outperform: Contrary to some prior findings, the authors demonstrate that adaptive methods can indeed outperform plain gradient descent in terms of generalization accuracy, especially in specific counterexamples designed to highlight these differences.
- Hyperparameter Tuning Remains Crucial: Despite the promise of adaptive methods, the paper reinforces that they still require significant hyperparameter tuning to achieve their best performance, similar to or even more so than plain gradient descent.
- The "Who is Better" Question is Nuanced: The superiority of adaptive versus non-adaptive methods is problem- and data-dependent, making a universal claim difficult.
Key Results
- Linear Regression Theory: In under-parameterized linear regression, both gradient descent and AdaGrad converge to the same solution. However, in over-parameterized linear regression, gradient descent converges to the minimum norm solution, while AdaGrad converges to a different point.
- Counterexample Performance: In a carefully constructed counterexample, an adaptive method (a variant of AdaGrad) was shown to generalize better than plain gradient descent, particularly when the margin between classes was small.
- DNN Experiments: Across various datasets (MNIST, CIFAR-10, CIFAR-100) and network architectures (CNNs, ResNets, MobileNets), the authors observed that adaptive methods (Adam, RMSProp) often performed similarly to or better than SGD in terms of accuracy. While AdaGrad itself didn't always perform as well, its variants and other adaptive methods showed competitive generalization.
- Weight Norms: In some DNN experiments, adaptive methods converged to solutions with larger weight norms (up to 2x) but achieved comparable or better generalization accuracy than plain gradient descent.
Limitations and Future Work
- Hyperparameter Tuning: The paper emphasizes that adaptive methods, while aiming for automatic tuning, still require careful hyperparameter selection, and the search space can be extensive.
- Theoretical Guarantees: While theoretical analysis is provided for linear regression, extending these guarantees to complex DNNs remains an open challenge.
- Understanding Non-Adaptive Superiority: The paper notes that in some DNN simulations, non-adaptive methods showed slight superiority, and this phenomenon is not fully understood and warrants further investigation.
- Regularization Effects: The authors suggest that L2-norm regularization might act as an "equalizer," forcing both adaptive and non-adaptive methods to converge to similar solutions, which is an area for future research.
- Generalization of Adaptive Methods: The paper highlights that while adaptive methods can achieve better generalization, the exact reasons and conditions under which this occurs, especially in complex architectures, require deeper exploration.
Summary updated