A Dynamical View on Optimization Algorithms of Overparameterized Neural Networks

Abstract

When equipped with efficient optimization algorithms, the over-parameterized neural networks have demonstrated high level of performance even though the loss function is non-convex and non-smooth. While many works have been focusing on understanding the loss dynamics by training neural networks with the gradient descent (GD), in this work, we consider a broad class of optimization algorithms that are commonly used in practice. For example, we show from a dynamical system perspective that the Heavy Ball (HB) method can converge to global minimum on mean squared error (MSE) at a linear rate (similar to GD); however, the Nesterov accelerated gradient descent (NAG) may only converges to global minimum sublinearly. Our results rely on the connection between neural tangent kernel (NTK) and finite over-parameterized neural networks with ReLU activation, which leads to analyzing the limiting ordinary differential equations (ODE) for optimization algorithms. We show that, optimizing the non-convex loss over the weights corresponds to optimizing some strongly convex loss over the prediction error. As a consequence, we can leverage the classical convex optimization theory to understand the convergence behavior of neural networks. We believe our approach can also be extended to other optimization algorithms and network architectures.

Accepted to AISTATS 2021

References in corpus (20)

• Adam: A Method for Stochastic Optimization
• ADADELTA: An Adaptive Learning Rate Method
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• A Convergence Theory for Deep Learning via Over-Parameterization
• A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights
• On Exact Computation with an Infinitely Wide Neural Net
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks
• Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• On Lazy Training in Differentiable Programming
• Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data
• Parseval Networks: Improving Robustness to Adversarial Examples
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• A Lyapunov Analysis of Momentum Methods in Optimization
• On the Convergence Rate of Training Recurrent Neural Networks
• Understanding the Acceleration Phenomenon via High-Resolution Differential Equations
• Finite Versus Infinite Neural Networks: an Empirical Study
• Accelerated First-Order Methods: Differential Equations and Lyapunov Functions
• Optimization Theory for ReLU Neural Networks Trained with Normalization Layers