Gram-Gauss-Newton Method: Learning Overparameterized Neural Networks for Regression Problems

Abstract

First-order methods such as stochastic gradient descent (SGD) are currently the standard algorithm for training deep neural networks. Second-order methods, despite their better convergence rate, are rarely used in practice due to the prohibitive computational cost in calculating the second-order information. In this paper, we propose a novel Gram-Gauss-Newton (GGN) algorithm to train deep neural networks for regression problems with square loss. Our method draws inspiration from the connection between neural network optimization and kernel regression of neural tangent kernel (NTK). Different from typical second-order methods that have heavy computational cost in each iteration, GGN only has minor overhead compared to first-order methods such as SGD. We also give theoretical results to show that for sufficiently wide neural networks, the convergence rate of GGN is \emph{quadratic}. Furthermore, we provide convergence guarantee for mini-batch GGN algorithm, which is, to our knowledge, the first convergence result for the mini-batch version of a second-order method on overparameterized neural networks. Preliminary experiments on regression tasks demonstrate that for training standard networks, our GGN algorithm converges much faster and achieves better performance than SGD.

References in corpus (25)

• Adam: A Method for Stochastic Optimization
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• On the Variance of the Adaptive Learning Rate and Beyond
• On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima
• Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation
• Optimizing Neural Networks with Kronecker-factored Approximate Curvature
• On Exact Computation with an Infinitely Wide Neural Net
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Revisiting Small Batch Training for Deep Neural Networks
• Train faster, generalize better: Stability of stochastic gradient descent
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks
• Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Fixup Initialization: Residual Learning Without Normalization
• The Anisotropic Noise in Stochastic Gradient Descent: Its Behavior of Escaping from Sharp Minima and Regularization Effects
• Fast Approximate Natural Gradient Descent in a Kronecker-factored Eigenbasis
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
• Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpoints
• Accelerated Gradient Descent Escapes Saddle Points Faster than Gradient Descent
• Practical Gauss-Newton Optimisation for Deep Learning
• Efficient Subsampled Gauss-Newton and Natural Gradient Methods for Training Neural Networks

Cited by in corpus (18)

• GraphNorm: A Principled Approach to Accelerating Graph Neural Network Training
• Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks
• Convergence of Adversarial Training in Overparametrized Neural Networks
• A Theoretical Framework for Target Propagation
• Optimal Rates for Averaged Stochastic Gradient Descent under Neural Tangent Kernel Regime
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation
• Efficient Subsampled Gauss-Newton and Natural Gradient Methods for Training Neural Networks
• When Does Preconditioning Help or Hurt Generalization?
• Any Target Function Exists in a Neighborhood of Any Sufficiently Wide Random Network: A Geometrical Perspective
• Provable Regret Bounds for Deep Online Learning and Control
• Scalable Derivative-Free Optimization for Nonlinear Least-Squares Problems
• Rethinking Gauss-Newton for learning over-parameterized models
• Appearance of Random Matrix Theory in Deep Learning
• TENGraD: Time-Efficient Natural Gradient Descent with Exact Fisher-Block Inversion
• Understanding Modern Techniques in Optimization: Frank-Wolfe, Nesterov's Momentum, and Polyak's Momentum
• A Modular Analysis of Provable Acceleration via Polyak's Momentum: Training a Wide ReLU Network and a Deep Linear Network
• Research of Damped Newton Stochastic Gradient Descent Method for Neural Network Training
• Understanding Approximate Fisher Information for Fast Convergence of Natural Gradient Descent in Wide Neural Networks