Research map / Optimization / Implicit bias and generalization
How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization
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.
Shows that GD on over-parameterized symmetric matrix factorization slows to Omega(1/T^2), while asymmetric parameterization with imbalanced initialization gives exact linear convergence, and a one-step rebalancing trick removes the initialization-scale dependence.
Problem
Gradient descent for low-rank matrix sensing becomes much slower when the search rank k exceeds the true rank r (over-parameterization), and the convergence behavior in that regime was not rigorously characterized.
Approach
Proves a sublinear Omega(1/T^2) lower bound for symmetric over-parameterized GD, then shows that asymmetric FG^T parameterization with imbalanced initialization (F scale alpha, G scale alpha/3) yields exact linear convergence at rate exp(-Omega(alpha^2 T)), and a one-time rescaling step that intensifies imbalance removes the alpha dependence.
Key results
- Symmetric over-parameterized GD has a lower bound ||X_tX_t^T - M*||_F^2 >= (c alpha^2/(eta sigma_r n t))^2, i.e. Omega(1/T^2), versus exp(-Omega(T)) in exact parameterization.
- Asymmetric imbalanced-initialized GD converges linearly at exp(-Omega(alpha^2 T)) in the over-parameterized case, implying asymmetric parameterization is exponentially faster than symmetric for symmetric matrix sensing.
- A one-step rescaling that intensifies imbalance yields linear convergence at a rate independent of the initialization scale alpha.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use symmetric over-parameterization (k > r) instead of exact parameterization (k = r) | GD for symmetric matrix sensing · Symmetric matrix sensing | convergence rate: exp(-Ω(T)) -> Ω(1/T^2) | Hurt |
| Use asymmetric parameterization FGᵀ instead of symmetric parameterization XXᵀ | GD for symmetric matrix sensing · Symmetric matrix sensing | convergence rate: Ω(1/T^2) -> exp(-Ω(α²T)) | Helped |
| Use asymmetric over-parameterization (k > r) instead of symmetric over-parameterization | GD for symmetric matrix sensing · Symmetric matrix sensing | convergence rate: Ω(1/T^2) -> exp(-Ω(α²T)) | Helped |
| Use asymmetric parameterization with k = r instead of k > r | GD for asymmetric matrix sensing · Asymmetric matrix sensing | convergence rate: exp(-Ω(α²T)) -> exp(-Ω(T)) | Helped |
| Initialize F and G imbalanced, with F₀ scale α and G₀ scale α/3 | GD with asymmetric parameterization · Asymmetric matrix factorization | convergence rate: α⁴/36(1-4ηα²)^(2t) ≤ ‖FₜGₜᵀ - Σ‖²_F ≤ 4n·(1-ηα²/4)^(t-T₁) | Helped |
| Increase the imbalance with a one-step transformation at T^(3) | GD with asymmetric over-parameterization · Asymmetric matrix sensing, k > r | convergence rate: exp(-Ω(α²T)) -> exp(-Ω(t-T^(3))) | Helped |
| Use symmetric over-parameterization instead of asymmetric parameterization | GD for matrix sensing · Symmetric matrix sensing, k > r | convergence rate: exp(-Ω(α²T)) -> Ω(1/T^2) | Hurt |
Surprising findings
- Asymmetric parameterization can be exponentially faster than symmetric parameterization even when the target matrix is positive semi-definite.
- Imbalance between F and G, rather than balance, is the key ingredient for fast convergence, contrary to prior work emphasizing balancing.
Limitations
- Requires RIP with small constant (delta roughly O~(1/sqrt(kr))) and small initialization scale alpha, with polynomial dependence on condition number.
- Convergence rate of base asymmetric result depends on initialization scale alpha, and the paper shows this dependence is unavoidable in the worst case.
- Results are for gradient descent on L2 loss only, and the rebalancing step relies on knowing the neighborhood of the optimum.
Experimental setup
Metrics: reconstruction error ||FG^T - M*||_F^2 convergence rate
Baselines: symmetric parameterization GD exact-parameterization GD balancing regularization
Builds on: Soltanolkotabi et al. 2023 implicit regularization of GD in matrix sensing Tong et al. auto-balancing analysis Stöger and Soltanolkotabi small random initialization
Closest papers by meaning
- The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing (ICML 2023 · similarity 0.91)
- Globally Q-linear Gauss-Newton Method for Overparameterized Non-convex Matrix Sensing (NeurIPS 2024 · similarity 0.89)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.88)
- Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery (ICML 2025 · similarity 0.88)
- Block Acceleration Without Momentum: On Optimal Stepsizes of Block Gradient Descent for Least-Squares (ICML 2024 · similarity 0.87)
- Risk Bounds of Accelerated SGD for Overparameterized Linear Regression (ICLR 2024 · similarity 0.87)
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.