Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced

By Simon Shaolei Du, Wei Hu, Jason D. Lee. 2018

284 citations recorded by the source corpus.

We study the implicit regularization imposed by gradient descent for learning multi-layer homogeneous functions including feed-forward fully connected and convolutional deep neural networks with linear, ReLU or Leaky ReLU activation. We rigorously prove that gradient flow (i.e. gradient descent with infinitesimal step size) effectively enforces the differences between squared norms across different layers to remain invariant without any explicit regularization. This result implies that if the weights are initially small, gradient flow automatically balances the magnitudes of all layers. Using a discretization argument, we analyze gradient descent with positive step size for the non-convex low-rank asymmetric matrix factorization problem without any regularization. Inspired by our findings for gradient flow, we prove that gradient descent with step sizes $\eta_t = O\left(t^{-\left( \frac12+\delta\right)} \right)$ ($0<\delta\le\frac12$) automatically balances two low-rank factors and converges to a bounded global optimum. Furthermore, for rank-$1$ asymmetric matrix factorization we give a finer analysis showing gradient descent with constant step size converges to the global minimum at a globally linear rate. We believe that the idea of examining the invariance imposed by first order algorithms in learning homogeneous models could serve as a fundamental building block for studying optimization for learning deep models.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Optimization & Training

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 Computational Theory and Mathematics

In Optimization & Training

Citations in the corpus

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).”
Gradient Descent Provably Optimizes Over-parameterized Neural Networks (2018, methodology): “We believe combing our proof idea with the discovery of balancedness between layers in Du et al. [2018a] is a promising approach.”
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “It has only been established for problems involving shallow (two layer) models, e.g. matrix factorization (Ge et al. (2016); Du et al. (2018a)).”
On Exact Computation with an Infinitely Wide Neural Net (2019, methodology): “This is inspired by Du et al. [2018a] in which authors showed that if one applies gradient ﬂow, then at any training time t , the diﬀerence between the squared Frobenius norm of the weight matrix at time t and that at initialization is same for all layers.”
Gradient Descent Maximizes the Margin of Homogeneous Neural Networks (2019, background): “Motivated by the aforementioned results on regularization path [Rosset et al., 2004, Wei et al., 2018], we assume Full Homogeneity instead of Partial Homogeneity.”
Exponential Convergence Time of Gradient Descent for One-Dimensional Deep Linear Neural Networks (2018, methodology): “One of the most common initialization methods for neural networks is Xavier initialization [Glorot and Bengio, 2010], which in the setting of Eq. (1) corresponds to choosing each entry of each d × d matrix Wi independently from a zero-mean distribution with variance 1/d (usually uniform or Gaussian)”
Gradient descent aligns the layers of deep linear networks (2018, background): “Lastly, for ReLU networks, Du et al. (2018) show that gradient ﬂow does not change the diﬀerence between squared Frobenius norms of any two layers.”
Trained Transformers Learn Linear Models In-Context (2023, methodology): “Random initializations that induce this balancedness condition have been utilized in a number of theoretical works on deep linear networks [DHL18; ACH18; Aro+19; Azu+21].”
Gradient Starvation: A Learning Proclivity in Neural Networks (2020, background): “in which W ∈ Rdl×dl−1 is a weight matrix drawn from N (0, I) and γ is a scaling factor to ensure that norm of each h(l−1) is preserved at initialization (See [28] for a formal treatment).”
Pruning neural networks without any data by iteratively conserving synaptic flow (2020, methodology): “This invariance has been noticed before by [40] as a form of implicit regularization and used to explain the empirical phenomenon that trained multi-layer models can have similar layer-wise magnitudes.”
Fine-Tuning can Distort Pretrained Features and Underperform Out-of-Distribution (2022, unknown): “Gradient flows can be thought of as a continuous time analogue of gradient based methods and have been extensively studied in recent years as a way to understand gradient based methods (Gunasekar et al., 2017; Arora et al., 2018; Du et al., 2018).”
Understanding self-supervised Learning Dynamics without Contrastive Pairs (2021, background): “We note that similar weight balancing dynamics has been discovered in multi-layer linear networks and matrix factorization (Arora et al., 2018; Du et al., 2018).”
Training Neural Networks as Learning Data-adaptive Kernels: Provable Representation and Approximation Benefits (2019, methodology): “First, we present a simple version of the result ﬁrstly proved in Maennel et al. (2018); Du et al. (2018a).”
Implicit Bias of Gradient Descent for Wide Two-layer Neural Networks Trained with the Logistic Loss (2020, background): “The principle behind the initialization on D is illustrated on Figure 4 and is related to well-known properties of homogeneous models (Du et al., 2018).”
Width Provably Matters in Optimization for Deep Linear Neural Networks (2019, methodology): “A series of recent papers used trajectory-based methods to analyze gradient descent for shallow neural networks under strong data assumptions (Tian, 2017; Soltanolkotabi, 2017; Brutzkus & Globerson, 2017; Li & Yuan, 2017; Zhong et al., 2017; Zhang et al., 2018; Du et al., 2018c;d).”
NETT: solving inverse problems with deep neural networks (2018, background): “particular, in [35] a regularizer has been proposed that distinguishes the distributions of desired images and noisy images.”
Implicit Regularization in Deep Matrix Factorization (2019, background): “For non-linear neural networks, the topic has thus far been studied empirically ( e.g. in [37, 52, 29, 26, 38]), with theoretical analyses being somewhat scarce (see [15, 41] for some of the few observations that have been derived).”
Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization (2021, methodology): “This result explains the empirical phenomena observed in prior work, and conﬁrms that gradient descent with a constant learning rate still enjoys the auto-balancing property as argued in Du et al. [2018].”