Implicit regularization and solution uniqueness in over-parameterized matrix sensing

Abstract

We consider whether algorithmic choices in over-parameterized linear matrix factorization introduce implicit regularization. We focus on noiseless matrix sensing over rank-$r$ positive semi-definite (PSD) matrices in ${\mathbb{R}}^{n\times n}$, with a sensing mechanism that satisfies restricted isometry properties (RIP). The algorithm we study is \emph{factored gradient descent}, where we model the low-rankness and PSD constraints with the factorization $U{U}^{\top }$, for $U\in {\mathbb{R}}^{n\times r}$. Surprisingly, recent work argues that the choice of $r\le n$ is not pivotal: even setting $U\in {\mathbb{R}}^{n\times n}$ is sufficient for factored gradient descent to find the rank-$r$ solution, which suggests that operating over the factors leads to an implicit regularization. In this contribution, we provide a different perspective to the problem of implicit regularization. We show that under certain conditions, the PSD constraint by itself is sufficient to lead to a unique rank-$r$ matrix recovery, without implicit or explicit low-rank regularization. \emph{I.e.}, under assumptions, the set of PSD matrices, that are consistent with the observed data, is a singleton, regardless of the algorithm used.

12 pages

References in corpus (9)

• Characterizing Implicit Bias in Terms of Optimization Geometry
• On the Power of Over-parametrization in Neural Networks with Quadratic Activation
• Spurious Local Minima are Common in Two-Layer ReLU Neural Networks
• When is a Convolutional Filter Easy To Learn?
• Theory of Deep Learning III: explaining the non-overfitting puzzle
• The loss landscape of overparameterized neural networks
• Theoretical properties of the global optimizer of two layer neural network
• IHT dies hard: Provable accelerated Iterative Hard Thresholding
• Provable quantum state tomography via non-convex methods

Cited by in corpus (1)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview