On the Benefits of Weight Normalization for Overparameterized Matrix Sensing

2025/10/01 by Wei, Yudong, Zhang, Liang, Li, Bingcong +1
#FOS: Computer and information sciences #FOS: Electrical engineering #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Signal Processing (eess.SP) #electronic engineering #information engineering

paper · doi:10.48550/arxiv.2510.01175

Abstract

While normalization techniques are widely used in deep learning, their theoretical understanding remains relatively limited. In this work, we establish the benefits of (generalized) weight normalization (WN) applied to the overparameterized matrix sensing problem. We prove that WN with Riemannian optimization achieves linear convergence, yielding an exponential speedup over standard methods that do not use WN. Our analysis further demonstrates that both iteration and sample complexity improve polynomially as the level of overparameterization increases. To the best of our knowledge, this work provides the first characterization of how WN leverages overparameterization for faster convergence in matrix sensing.

Citations

• Global Convergence of Gradient EM for Over-Parameterized Gaussian Mixtures
• PoLAR: Polar-Decomposed Low-Rank Adapter Representation
• Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization
• On the Crucial Role of Initialization for Matrix Factorization
• Optimization and Generalization Guarantees for Weight Normalization
• DoRA: Weight-Decomposed Low-Rank Adaptation
• Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion
• Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization
• How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization
• Convergence of Alternating Gradient Descent for Matrix Factorization
• Optimizing Orthogonalized Tensor Deflation via Random Tensor Theory
• The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing
• Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensing
• Factorization Approach for Low-complexity Matrix Completion Problems: Exponential Number of Spurious Solutions and Failure of Gradient Methods
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization
• LoRA: Low-Rank Adaptation of Large Language Models
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements
• On the computational and statistical complexity of over-parameterized matrix sensing
• Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learning
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Implicit Regularization and Convergence for Weight Normalization
• Implicit Regularization in Deep Matrix Factorization
• Layer Normalization
• Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep Neural Networks
• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• A Riemannian geometry for low-rank matrix completion
• Fixed-rank matrix factorizations and Riemannian low-rank optimization
• Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements\n via Convex Programming
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming
• Collaborative Filtering in a Non-Uniform World: Learning with the Weighted Trace Norm
• A Simpler Approach to Matrix Completion
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

Related

• How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization
• Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing
• The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing
• Implicit Regularization Makes Overparameterized Asymmetric Matrix Sensing Robust to Perturbations
• On the computational and statistical complexity of over-parameterized matrix sensing