Research map / Learning theory and algorithms / Matrix and tensor methods
Globally Q-linear Gauss-Newton Method for Overparameterized Non-convex Matrix Sensing
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an approximated Gauss-Newton (AGN) method for overparameterized non-convex low-rank matrix sensing and proves global Q-linear convergence from random initialization.
Problem
Overparameterized non-convex low-rank matrix sensing: gradient descent and preconditioned variants slow down near saddle points and converge only sub-linearly or R-linearly with condition-number dependence.
Approach
Approximates Gauss-Newton updates via minimum-norm least-squares solutions on the unified factor formulation X=[U;V] (with RIP approximation), using two half-steps per iteration; the authors show ScaledGD(λ)/PrecGD are Levenberg-Marquardt-type variants and that AGN's objective decrease near saddles is Θ(1) rather than o(ε).
Key results
- AGN reaches Q-linear global convergence from random initialization with a factor independent of the condition number, versus R-linear for PrecGD and sub-linear/slow for GD.
- On 100x100 matrices with κ=10, AGN takes 27.24 s versus 87.12 s for PrecGD and 55.87 s for ScaledGD(λ); GD exceeds 500 s.
- On 500x500 matrices with κ=10, AGN takes 617.58 s versus 1979.45 s for PrecGD and 1218.83 s for ScaledGD(λ).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use AGN instead of GD | Overparameterized LRMS · Overparameterized LRMS | iteration complexity: κ11 log(κ2/n) + κ10 log(κ6/ε) -> log(1/ε) | Helped |
| Use AGN instead of ScaledGD(λ) | Overparameterized LRMS · Overparameterized LRMS | iteration complexity: log κ · log(κn) + log(1/ε) -> log(1/ε) | Helped |
| Use AGN instead of PrecGD | Matrix sensing · Matrix sensing, 100 × 100, κ = 10 | time (seconds): 87.12 -> 27.24 | Helped |
| Use AGN instead of ScaledGD(λ) | Matrix sensing · Matrix sensing, 500 × 500, κ = 50 | time (seconds): 1258.71 -> 632.24 | Helped |
| Use asymmetric parameterization instead of symmetric parameterization (ablation) | AGN for symmetric matrix sensing · Symmetric LRMS | relative error | Helped |
| Use AGN instead of GD near saddle points | Overparameterized LRMS · Saddle-point vicinity | objective function decrease: o(ε) -> Θ(1) | Helped |
| Use AGN instead of PrecGD near saddle points | Overparameterized LRMS · Saddle-point vicinity | objective function decrease: o(ε) -> Θ(1) | Helped |
Surprising findings
- Symmetric parameterization of AGN with constant step size may fail to be a descent method in overparameterized settings, requiring the asymmetric parameterization instead.
Limitations
- May be less effective than gradient descent for general problems without low-rank structure because it requires solving a least-squares problem per step.
- Saddle point analysis is limited to rank-1 M with zero RIP constant.
- Global convergence proof relies on RIP assumptions and random Gaussian initialization with small scale.
Experimental setup
Datasets: synthetic random low-rank matrices with Gaussian sensing operators
Benchmarks: synthetic overparameterized asymmetric matrix sensing (n=100, r=5, d=15) runtime comparison on 100x100 and 500x500 matrices
Metrics: relative error iteration count computational time in seconds gradient norm
Baselines: GD PrecGD ScaledGD(λ)
Builds on: ScaledGD PrecGD Levenberg-Marquardt Gauss-Newton
Closest papers by meaning
- How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization (ICLR 2024 · similarity 0.89)
- The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing (ICML 2023 · similarity 0.88)
- On the Benefits of Weight Normalization for Overparameterized Matrix Sensing (ICLR 2026 · similarity 0.88)
- Over-parametrization via Lifting for Low-rank Matrix Sensing: Conversion of Spurious Solutions to Strict Saddle Points (ICML 2023 · similarity 0.88)
- Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery (ICML 2025 · similarity 0.86)
- The Nuclear Route: Sharp Asymptotics of ERM in Overparameterized Quadratic Networks (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.