On the Optimization of Deep Networks: Implicit Acceleration by Overparameterization

By Sanjeev Arora, Nadav Cohen, Elad Hazan. 2018

563 citations recorded by the source corpus.

Conventional wisdom in deep learning states that increasing depth improves expressiveness but complicates optimization. This paper suggests that, sometimes, increasing depth can speed up optimization. The effect of depth on optimization is decoupled from expressiveness by focusing on settings where additional layers amount to overparameterization - linear neural networks, a well-studied model. Theoretical analysis, as well as experiments, show that here depth acts as a preconditioner which may accelerate convergence. Even on simple convex problems such as linear regression with $\ell_p$ loss, $p>2$, gradient descent can benefit from transitioning to a non-convex overparameterized objective, more than it would from some common acceleration schemes. We also prove that it is mathematically impossible to obtain the acceleration effect of overparametrization via gradients of any regularizer.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In Scaling & Learning Theory

Citations in the corpus

Train Large, Then Compress: Rethinking Model Size for Efficient Training and Inference of Transformers (2020, background): “One initial step in this direction is Arora et al. (2018a), who show that for deep linear neural networks, increasing depth can promote movement along directions already taken by the optimizer.”
Massively Multilingual Neural Machine Translation in the Wild: Findings and Challenges (2019, background): “A better theoretical understanding of the generalization ability of deep and wide models (Raghu et al., 2017; Arora et al., 2018), trainability challenges including exploding and vanishing gradients (Glo-rot and Bengio, 2010; Balduzzi et al., 2017) and empirical approaches to counter these…”
High-dimensional dynamics of generalization error in neural networks (2017, background): “A line of work has shown that the full gradient descent dynamics in fact converge to the low rank structure implied by these initialization conditions, in a wide range of settings beyond the student–teacher setting we consider here (Arora et al., 2018; Du et al., 2018; Ji & Telgarsky, 2019).”
Beyond English-Centric Multilingual Machine Translation (2020, methodology): “To that effect, we leverage progress in scaling (Kaplan et al., 2020; Arora et al., 2018) to train models that are over 50 times larger than current bilingual models with model parallelism (Huang et al.”
GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding (2020, background): “Scaling neural networks brings dramatic quality gains over a wide array of machine learning problems [1, 2, 3, 4, 5, 6].”
Compacter: Efficient Low-Rank Hypercomplex Adapter Layers (2021, background): “(2)If factors are over-parameterized, COMPACTER can be used for overcomplete knowledge distillation [24].”
Initialization and Regularization of Factorized Neural Layers (2021, methodology): “Alternatively, by setting r ¥ mintm,nu and/or including an inner matrix M P R , we can attempt to take advantage of improved optimization due to increased width (Du & Hu, 2019) and/or increased depth (Arora et al., 2018).”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, background): “The analysis of gradient flow is a stepping stone towards understanding discrete algorithms and this is the main topic of recent work (Arora et al., 2018; Du et al., 2018a).”
ELLE: Efficient Lifelong Pre-training for Emerging Data (2022, background): “, 2020) due to overparameterization (Arora et al., 2018).”
Knowledge Distillation: A Survey (2020, background): “…with good performance, especially in the real-world scenarios with large-scale data, because the over parameterization improves the generalization performance when new data is considered (Zhang et al. 2018; Brutzkus and Glober-son 2019; Allen-Zhu et al. 2019; Arora et al. 2018; Tu et al. 2020).”
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, methodology): “By (Theorem 1 and Claim 1 in) Arora et al. (2018), the weightsW1(τ), .”
Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks (2018, background): “…Anthony and Bartlett, 2009), a vast literature have recently studied the connection between the generalization performance of deep neural networks and their architectures (Neyshabur et al., 2015, 2017a,b; Bartlett et al., 2017; Golowich et al., 2017; Arora et al., 2018c; Allen-Zhu et al., 2018a).”
Meta-Learning with Warped Gradient Descent (2019, methodology): “Meta-learned preconditioning is closely related to parallel work on second-order optimisation methods for high dimensional non-convex loss surfaces (Nocedal & Wright, 2006; Saxe et al., 2013; Kingma & Ba, 2015; Arora et al., 2018).”
An Exponential Learning Rate Schedule for Deep Learning (2019, background): “This greatly extends previous analyses of effect of normalization schemes (Wu et al., 2018; Arora et al., 2018) for vanilla SGD.”
Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced (2018, background): “This result was known for linear networks [Arora et al., 2018], but the proof there relies on the entire network being linear while Theorem 2.2 only needs two consecutive layers to have no nonlinear activations in between.”
DO-Conv: Depthwise Over-Parameterized Convolutional Layer (2020, background): “Arora et al. [3] studied the role of over-parameterization in gradient descent based optimization.”
Heavy-Tailed Universality Predicts Trends in Test Accuracies for Very Large Pre-Trained Deep Neural Networks (2019, background): “, [2, 3, 4] and [5, 6, 7, 8, 9, 10, 11, 12, 13, 14], as well as much older [15, 16].”