On the computational and statistical complexity of over-parameterized matrix sensing

Abstract

We consider solving the low rank matrix sensing problem with Factorized Gradient Descend (FGD) method when the true rank is unknown and over-specified, which we refer to as over-parameterized matrix sensing. If the ground truth signal ${\mathbf{X}}^{\ast }\in {\mathbb{R}}^{d\ast d}$ is of rank $r$, but we try to recover it using $\mathbf{F}{\mathbf{F}}^{\top }$ where $\mathbf{F}\in {\mathbb{R}}^{d\ast k}$ and $k>r$, the existing statistical analysis falls short, due to a flat local curvature of the loss function around the global maxima. By decomposing the factorized matrix $\mathbf{F}$ into separate column spaces to capture the effect of extra ranks, we show that $\Vert {\mathbf{F}}_t{\mathbf{F}}_t-{\mathbf{X}}^{\ast }{\Vert }_F^2$ converges to a statistical error of $\tilde{\mathcal{O}}(kd{\sigma }^2/n)$ after $\tilde{\mathcal{O}}(\frac{{\sigma }_r}{\sigma }\sqrt{\frac{n}{d}})$ number of iterations where ${\mathbf{F}}_t$ is the output of FGD after $t$ iterations, ${\sigma }^2$ is the variance of the observation noise, ${\sigma }_r$ is the $r$-th largest eigenvalue of ${\mathbf{X}}^{\ast }$, and $n$ is the number of sample. Our results, therefore, offer a comprehensive picture of the statistical and computational complexity of FGD for the over-parameterized matrix sensing problem.

References in corpus (8)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Quantum state tomography via compressed sensing
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?

Cited by in corpus (4)

• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
• Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery
• Towards Understanding Generalization via Decomposing Excess Risk Dynamics