Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations

By Yuanzhi Li, Tengyu Ma, Hongyang Zhang. 2017

328 citations recorded by the source corpus.

Subfields: Scaling & Learning Theory, Statistical 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 Scaling & Learning Theory

In Statistical Learning Theory

Citations in the corpus

The Surprising Simplicity of the Early-Time Learning Dynamics of Neural Networks (2020, background): “…has also been studied in various settings, suggesting a bias towards large-margin, low-norm, or low-rank solutions [Gunasekar et al., 2017, 2018, Soudry et al., 2018, Li et al., 2018, Ji and Telgarsky, 2019a,b, Arora et al., 2019a, Lyu and Li, 2019, Chizat and Bach, 2020, Razin and Cohen, 2020].”
LoRA: Low-Rank Adaptation of Large Language Models (2021, background): “A lot of machine learning problems have certain intrinsic low-rank structure [7, 13, 23, 24].”
Feature Purification: How Adversarial Training Performs Robust Deep Learning (2020, background): “oretical studies are rather limited in this direction: Most of the works only focus on the case when the training data is spherical Gaussian or require heavy initialization using tensor decomposition [14, 18, 20, 33, 49, 52, 55, 57, 84, 86, 93, 95, 99, 105, 107], which might fail to capture the spec”
What Can ResNet Learn Efficiently, Going Beyond Kernels? (2019, neutral): “1;xi10 h w 2;xi10 +hw 2;xi10 h w;xi10)2 over w;w 2Rd. Unfortunately, the underlying optimization process is highly non-convex and it remains unclear how to minimize it eciently. Using matrix sensing [29], one can eciently learn such H(x) in sample complexity Oe(d5). 3 Implicit Hierarchical Learning ”
PowerSGD: Practical Low-Rank Gradient Compression for Distributed Optimization (2019, methodology): “Low-rank methods Recent works argue that in modern over-parameterized deep networks, the ﬁnal model learnt has a ‘low stable rank’ (Martin & Mahoney, 2018; Li et al., 2018).”
A Convergence Analysis of Gradient Descent for Deep Linear Neural Networks (2018, background): “oach is a direct analysis of the trajectories taken by the optimizer. Various papers (e.g. Brutzkus and Globerson (2017); Li and Yuan (2017); Zhong et al. (2017); Tian (2017); Brutzkus et al. (2018); Li et al. (2018); Du et al. (2018c;b); Liao et al. (2018)) have recently adopted this strategy, but ”
Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks (2019, methodology): “…established that ﬁrst-order methods can automatically ﬁnd minimum-norm/maximum-margin solutions that ﬁt the data in the settings of logistic regression, deep linear networks, and symmetric matrix factorization (Soudry et al., 2018; Gunasekar et al., 2018a,b; Ji & Telgarsky, 2018; Li et al., 2018b).”
Theoretical Insights Into the Optimization Landscape of Over-Parameterized Shallow Neural Networks (2017, background): “Finally, the recent paper [31] proves that gradient descent when initialized at zero can lead to training errors close to (but not equal to) zero.”
A Generalization Theory of Gradient Descent for Learning Over-parameterized Deep ReLU Networks (2019, background): “A bunch of papers (Gunasekar et al., 2017; Soudry et al., 2017; Ji and Telgarsky, 2018; Gunasekar et al., 2018a,b; Nacson et al., 2018; Li et al., 2018b) have studied implicit regularization/bias of GD, stochastic gradient descent (SGD) or mirror descent for matrix factorization, logistic…”
On the Margin Theory of Feedforward Neural Networks (2018, methodology): “…works have shown that gradient descent ﬁnds the minimum norm solution ﬁtting the data for problems including logistic regression, linearized neural networks, and matrix factorization (Soudry et al., 2018; Gunasekar et al., 2018b; Li et al., 2018; Gunasekar et al., 2018a; Ji & Telgarsky, 2018).”
Kernel and Rich Regimes in Overparametrized Models (2019, background): “For example, analytic and/or empirical results suggest that gradient descent on deep linear convolutional networks implicitly biases toward minimizing the Lp bridge penalty, for p = 2/depth ≤ 1, in the frequency domain [13]; on an infinite width single input ReLU network infinitesimal weight decay b”
Backward Feature Correction: How Deep Learning Performs Deep Learning (2020, background): “For such reason, it is not surprising that most existing theoretical works on the efficient learning regime of neural networks either focus on (1) two-layer networks [9, 10, 12, 22, 23, 36, 41, 41, 42, 46, 50, 51, 53, 54, 56, 58, 61] which do not have any hierarchical structure, or (2) a multi-layer”
Towards Understanding the Spectral Bias of Deep Learning (2019, background): “A series of papers (Gunasekar et al., 2017; Soudry et al., 2018; Gunasekar et al., 2018a,b; Nacson et al., 2018; Li et al., 2018; Jacot et al., 2020) studied implicit bias problem, aiming to figure out when there are multiple optimal solutions of a training objective function, what kind of nice prop”
Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path? (2018, background): “As discussed in Section 4.2, there is a rich literature which studies global optimality of nonconvex low-rank factorization formulations such as the Burer-Monteiro factorization in the overparametrized regime [5, 15–17].”
Why do Larger Models Generalize Better? A Theoretical Perspective via the XOR Problem (2018, background): “Over-parameterization has also been studied for quadratic activation functions (Soltanolkotabi et al., 2018; Du & Lee, 2018; Li et al., 2018).”
Reconciling modern machine learning and the bias-variance trade-off (2018, background): “That the test risk improves beyond the interpolation threshold is compatible with the conjectured “small norm” inductive biases of the common training algorithms for neural networks [14, 16].”