On Generalization of Adaptive Methods for Over-parameterized Linear Regression

Abstract

Over-parameterization and adaptive methods have played a crucial role in the success of deep learning in the last decade. The widespread use of over-parameterization has forced us to rethink generalization by bringing forth new phenomena, such as implicit regularization of optimization algorithms and double descent with training progression. A series of recent works have started to shed light on these areas in the quest to understand -- why do neural networks generalize well? The setting of over-parameterized linear regression has provided key insights into understanding this mysterious behavior of neural networks. In this paper, we aim to characterize the performance of adaptive methods in the over-parameterized linear regression setting. First, we focus on two sub-classes of adaptive methods depending on their generalization performance. For the first class of adaptive methods, the parameter vector remains in the span of the data and converges to the minimum norm solution like gradient descent (GD). On the other hand, for the second class of adaptive methods, the gradient rotation caused by the pre-conditioner matrix results in an in-span component of the parameter vector that converges to the minimum norm solution and the out-of-span component that saturates. Our experiments on over-parameterized linear regression and deep neural networks support this theory.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1811.07055

References in corpus (16)

• MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications
• ADADELTA: An Adaptive Learning Rate Method
• An overview of gradient descent optimization algorithms
• On the Convergence of Adam and Beyond
• A Convergence Theory for Deep Learning via Over-Parameterization
• The Marginal Value of Adaptive Gradient Methods in Machine Learning
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• No More Pesky Learning Rates
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Towards Optimal One Pass Large Scale Learning with Averaged Stochastic Gradient Descent
• Variants of RMSProp and Adagrad with Logarithmic Regret Bounds
• To understand deep learning we need to understand kernel learning
• On the Convergence Proof of AMSGrad and a New Version
• Classification vs regression in overparameterized regimes: Does the loss function matter?
• Global Convergence of Adaptive Gradient Methods for An Over-parameterized Neural Network
• Minnorm training: an algorithm for training over-parameterized deep neural networks