Introduction
Matrix sensing is a fundamental task in machine learning, aimed at recovering a low-rank, positive semi-definite (PSD) matrix from limited linear measurements. In practice, the exact rank $r_A$ of the target matrix is often unknown, leading practitioners to use overparameterized models where the model rank $r$ exceeds $r_A$. While overparameterization is a cornerstone of modern deep learning, it traditionally introduces a "curse" in matrix sensing: standard Gradient Descent (GD) slows to a sublinear $O(1/t)$ convergence rate.
This work provides the first theoretical proof that Weight Normalization (WN), when combined with Riemannian optimization, transforms overparameterization from a hindrance into an advantage. By decoupling the matrix into direction and magnitude, the proposed method achieves linear convergence, accelerating as the level of overparameterization increases.
Methodology: Generalized Weight Normalization
The authors propose a generalized WN scheme for matrices, inspired by the decoupling of weights in neural networks into a unit vector and a scalar. They decompose the matrix variable $Y$ into:
- Direction ($X$): An orthonormal basis constrained to a Stiefel manifold ($X^\top X = I$).
- Magnitude ($\Theta$): A symmetric matrix representing the scale.
Optimization is performed using Riemannian Gradient Descent (RGD). Unlike Euclidean updates, RGD updates the direction $X$ along the manifold's curved surface, followed by a "retraction" to maintain orthonormality. The magnitude $\Theta$ is updated via standard GD. This decoupling allows the algorithm to navigate the complex loss landscape more effectively than standard methods.
Theoretical and Empirical Insights
The core contribution of this research is the demonstration that WN-aided RGD achieves an exponential speedup over standard GD.
Overparameterization as a Catalyst
Contrary to the "curse" observed in standard GD, the authors prove that both iteration and sample complexity improve as the model rank $r$ increases. This suggests that extra model capacity actually smoothens the optimization landscape.
Two-Phase Trajectory and Incremental Learning
The optimization process follows a distinct two-phase path. Initially, the model escapes various saddle points where gradients are near zero. Subsequently, it enters a linear phase, converging rapidly to the global optimum. During this process, the model exhibits "incremental learning," recovering the target matrix's components sequentially (e.g., rank-1, then rank-2).
Key Results
The theoretical findings are supported by extensive experiments on synthetic data, CIFAR-10 image reconstruction, and structured image sensing.
- Linear Convergence: While standard GD is limited by a sublinear rate, WN-aided RGD achieves a linear rate of $\exp(-O(t))$.
- Performance Gains: As shown in Figure 2, RGD consistently outperforms GD across different condition numbers ($\kappa$) and overparameterization levels ($r$). Notably, RGD's convergence accelerates as $r$ increases.
- Robustness: The method maintains linear convergence even in noisy environments, with error floors proportional to the noise level $\mathcal{O}(\xi^2)$.
In image reconstruction tests, RGD with WN produced clear, accurate images in 100 iterations, whereas standard GD remained blurry even after 200 iterations, further validating the efficiency of the proposed approach.
Conclusion and Future Directions
This paper establishes that Weight Normalization is a powerful tool for overparameterized matrix sensing, offering significant computational advantages. While the current theory focuses on Riemannian optimization for symmetric PSD matrices, future work could extend these insights to broader non-convex problems like tensor decomposition or deep non-linear networks. Additionally, bridging the gap between Riemannian updates and the hybrid Euclidean-Riemannian methods used in standard deep learning libraries remains an open challenge.
Summary updated