When Does Preconditioning Help or Hurt Generalization?

Abstract

While second order optimizers such as natural gradient descent (NGD) often speed up optimization, their effect on generalization has been called into question. This work presents a more nuanced view on how the \textit{implicit bias} of first- and second-order methods affects the comparison of generalization properties. We provide an exact asymptotic bias-variance decomposition of the generalization error of overparameterized ridgeless regression under a general class of preconditioner $\mathbf{P}$, and consider the inverse population Fisher information matrix (used in NGD) as a particular example. We determine the optimal $\mathbf{P}$ for both the bias and variance, and find that the relative generalization performance of different optimizers depends on the label noise and the "shape" of the signal (true parameters): when the labels are noisy, the model is misspecified, or the signal is misaligned with the features, NGD can achieve lower risk; conversely, GD generalizes better than NGD under clean labels, a well-specified model, or aligned signal. Based on this analysis, we discuss several approaches to manage the bias-variance tradeoff, and the potential benefit of interpolating between GD and NGD. We then extend our analysis to regression in the reproducing kernel Hilbert space and demonstrate that preconditioned GD can decrease the population risk faster than GD. Lastly, we empirically compare the generalization error of first- and second-order optimizers in neural network experiments, and observe robust trends matching our theoretical analysis.

arXiv comment42 pages

References in corpus (50)

• Adam: A Method for Stochastic Optimization
• Distilling the Knowledge in a Neural Network
• Language Models are Few-Shot Learners
• Do Deep Nets Really Need to be Deep?
• Understanding deep learning requires rethinking generalization
• Exact solutions to the nonlinear dynamics of learning in deep linear neural networks
• Benign Overfitting in Linear Regression
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• Improving Generalization Performance by Switching from Adam to SGD
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Generalization Properties of Learning with Random Features
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Gradient Descent with Early Stopping is Provably Robust to Label Noise for Overparameterized Neural Networks
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• What Can ResNet Learn Efficiently, Going Beyond Kernels?
• The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
• Generalisation error in learning with random features and the hidden manifold model
• Asymptotic behavior of unregularized and ridge-regularized high-dimensional robust regression estimators : rigorous results
• Does data interpolation contradict statistical optimality?
• Diverse Neural Network Learns True Target Functions
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Do We Need Zero Training Loss After Achieving Zero Training Error?
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Kernel and Rich Regimes in Overparametrized Models
• Three Mechanisms of Weight Decay Regularization
• Optimal Rates for Multi-pass Stochastic Gradient Methods
• Universal Statistics of Fisher Information in Deep Neural Networks: Mean Field Approach
• Gradient Dynamics of Shallow Univariate ReLU Networks
• Statistical Optimality of Stochastic Gradient Descent on Hard Learning Problems through Multiple Passes
• Stochastic Mirror Descent on Overparameterized Nonlinear Models: Convergence, Implicit Regularization, and Generalization
• Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems
• Stochastic Gradient/Mirror Descent: Minimax Optimality and Implicit Regularization
• Distillation $\approx$ Early Stopping? Harvesting Dark Knowledge Utilizing Anisotropic Information Retrieval For Overparameterized Neural Network
• On Learning Over-parameterized Neural Networks: A Functional Approximation Perspective
• Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks
• On the number of variables to use in principal component regression
• The Dynamics of Learning: A Random Matrix Approach
• Asymptotics of Ridge (less) Regression under General Source Condition
• Metric-Free Natural Gradient for Joint-Training of Boltzmann Machines
• Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• Practical Riemannian Neural Networks
• A Continuous-Time View of Early Stopping for Least Squares
• Limitations of Lazy Training of Two-layers Neural Networks
• The Normalization Method for Alleviating Pathological Sharpness in Wide Neural Networks
• Sharp Asymptotics and Optimal Performance for Inference in Binary Models
• To Each Optimizer a Norm, To Each Norm its Generalization
• Gradient Descent in RKHS with Importance Labeling
• Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods

Cited by in corpus (6)

• Asymptotics of Ridge (less) Regression under General Source Condition
• On the Optimal Weighted ${\ell }_2$ Regularization in Overparameterized Linear Regression
• An Unconstrained Layer-Peeled Perspective on Neural Collapse
• Analyzing Monotonic Linear Interpolation in Neural Network Loss Landscapes
• Training Efficiency and Robustness in Deep Learning
• Depth Without the Magic: Inductive Bias of Natural Gradient Descent