Algorithmic Regularization in Over-parameterized Matrix Recovery

By Yuanzhi Li, Tengyu Ma, Hongyang Zhang. 2017

31 citations recorded by the source corpus.

We study the problem of recovering a low-rank matrix $X^\star$ from linear measurements using an over-parameterized model. We parameterize the rank-$r$ matrix $X^\star$ by $UU^\top$ where $U\in \mathbb{R}^{d\times d}$ is a square matrix, whereas the number of linear measurements is much less than $d^2$. We show that with $\tilde{O}(dr^{2})$ random linear measurements, the gradient descent on the squared loss, starting from a small initialization, recovers $X^\star$ approximately in $\tilde{O}(\sqrt{r})$ iterations. The results solve the conjecture of Gunasekar et al. under the restricted isometry property, and demonstrate that the training algorithm can provide an implicit regularization for non-linear matrix factorization models.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training, 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 Artificial Intelligence

In Computational Mechanics

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data (2018, background): “Recent studies are on SGD for different tasks, such as logistic regression [27] and matrix factorization [11, 19, 16].”
Fixup Initialization: Residual Learning Without Normalization (2019, methodology): “e spatial dimension of the largest feature maps. 5 Published as a conference paper at ICLR 2019 Our initialization and network design is consistent with recent theoretical work Hardt & Ma (2016); Li et al. (2018), which, in much more simpliﬁed settings such as linearized residual nets and quadra”
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.”
Just Interpolate: Kernel "Ridgeless" Regression Can Generalize (2018, methodology): “Our analysis can then be viewed in the light of recent work on implicit regularization of optimization procedures (Yao et al., 2007; Neyshabur et al., 2014; Gunasekar et al., 2017; Li et al., 2017).”
Implicit Bias of Gradient Descent on Linear Convolutional Networks (2018, background): “…and even with homogeneous polynomials, the characterization is not as crisp when other loss functions are used, e.g., with a squared loss and matrix factorization (a homogeneous degree two polynomial representation), the implicit bias is much more fragile Gunasekar et al. [2017], Li et al. [2017].”
Beyond Linearization: On Quadratic and Higher-Order Approximation of Wide Neural Networks (2019, background): “A large body of work Li et al. (2017); Nacson et al. (2019); Gunasekar et al. (2018b,a, 2017); Woodworth et al. (2019) shows that asymptotically gradient descent converges to a max-margin solution with a strong regularization eﬀect, unlike the NTK regularization 1 .”
Characterizing Implicit Bias in Terms of Optimization Geometry (2018, background): “Li et al. (2017), later proved the conjecture under additional assumption that the measurements X n satisﬁes certain restricted isometry property (RIP) .”
Training Over-parameterized Deep ResNet Is almost as Easy as Training a Two-layer Network (2019, result): “A result with similar ﬂavor [Li et al., 2017] has also been obtained for the matrix sensing problem.”
On the Power of Over-parametrization in Neural Networks with Quadratic Activation (2018, background): “A line of research tries to explain this phenomenon by studying the implicit regularization from stochastic gradient descent algorithm (Hardt et al., 2015; Pensia et al., 2018; Mou et al., 2017; Brutzkus et al., 2017; Li et al., 2017).”
Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margin (2019, background): “…a variety of new perspectives for studying generalization in deep learning, such as implicit or algorithmic regularization [Gunasekar et al., 2017, Li et al., 2017, Soudry et al., 2018, Gunasekar et al., 2018], new analyses of interpolating classiﬁers [Belkin et al., 2018, Liang and Rakhlin,…”