How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization

Nuoya Xiong, Lijun Ding, Simon S. Du

Abstract

While over-parameterization is often a boon for neural network optimization, this research demonstrates that it can be a "curse" in the context of matrix sensing. Specifically, for symmetric matrix sensing, over-parameterization causes gradient descent (GD) to slow from an exponential convergence rate to a sublinear one ($\Omega(1/T^2)$). We show that this bottleneck is tied to the symmetry of the model. By adopting an asymmetric parameterization and leveraging factor imbalance, linear convergence can be restored. Additionally, we address the sensitivity of these models to initialization scale—the "curse of initialization"—by proposing a simple modification that achieves fast convergence regardless of the starting point.

Introduction

Matrix sensing—the recovery of a low-rank matrix from linear measurements—is a fundamental problem in signal processing and machine learning. In practice, the true rank $r$ of the target matrix is often unknown, leading practitioners to use a model rank $k > r$. This over-parameterization is generally expected to simplify the optimization landscape. However, empirical evidence has long suggested that GD becomes significantly slower in this regime. This paper provides a rigorous theoretical explanation for this phenomenon and offers algorithmic solutions to bypass these bottlenecks.

The Curse of Symmetry

In symmetric matrix sensing, the model is typically parameterized as $M = XX^\top$. When the search rank $k$ matches the true rank $r$, GD converges exponentially fast. However, when $k > r$, the "redundant" dimensions in $X$ converge to zero much more slowly than the "signal" dimensions converge to the ground truth. This disparity drags the overall convergence rate down to a sublinear $\Omega(1/T^2)$.

Figure 1: Loss curves and comparisons showing the slowdown in over-parameterized symmetric cases (a, b) and the recovery of speed using asymmetric models (c).

The Asymmetric Advantage

The authors prove that the slowdown is a direct consequence of the symmetry constraint. By switching to an asymmetric parameterization $M = FG^\top$, even when the target matrix is symmetric, the optimization dynamics change fundamentally. In the asymmetric case, the model can achieve linear convergence, which is exponentially faster than the symmetric counterpart.

A key insight is the role of factor imbalance. Contrary to traditional wisdom that suggests keeping $F$ and $G$ balanced ($F^\top F \approx G^\top G$), the researchers find that allowing or even encouraging imbalance allows the model to stay in a high-speed learning regime.

The Curse of Initialization and a Faster Method

While asymmetric models are faster, they introduce a new challenge: sensitivity to the initialization scale $\alpha$. Smaller initializations lead to a prolonged "plateau" phase before rapid convergence begins. This "curse of initialization" means that standard GD still faces practical speed limits.

To solve this, the authors propose a "Simple and Fast Convergence Method." By introducing a one-step modification to the GD update that intentionally intensifies factor imbalance, they achieve a convergence rate that is independent of $\alpha$. This effectively recovers the high performance of the exact-parameterized case even in highly over-parameterized settings.

Figure 2: Analysis of initialization scale (alpha) in exact (a) vs. over-parameterized (b) cases, and the performance of the proposed method (c) in overcoming the initialization bottleneck.

Conclusion

This work highlights a critical counter-example to the "more is better" philosophy of over-parameterization. In symmetric matrix sensing, extra capacity creates optimization traps that can only be escaped by breaking symmetry or managing factor imbalance. These findings provide a new theoretical lens for understanding the dynamics of low-rank matrix recovery and suggest practical algorithmic improvements for large-scale optimization.

Summary updated

BibTeX
@inproceedings{xiong2024how,
  author = {Nuoya Xiong and Lijun Ding and Simon S. Du},
  title = {{How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=xGvPKAiOhq},
}
Figure