Implicit Regularization in Matrix Sensing via Mirror Descent

Abstract

We study discrete-time mirror descent applied to the unregularized empirical risk in matrix sensing. In both the general case of rectangular matrices and the particular case of positive semidefinite matrices, a simple potential-based analysis in terms of the Bregman divergence allows us to establish convergence of mirror descent -- with different choices of the mirror maps -- to a matrix that, among all global minimizers of the empirical risk, minimizes a quantity explicitly related to the nuclear norm, the Frobenius norm, and the von Neumann entropy. In both cases, this characterization implies that mirror descent, a first-order algorithm minimizing the unregularized empirical risk, recovers low-rank matrices under the same set of assumptions that are sufficient to guarantee recovery for nuclear-norm minimization. When the sensing matrices are symmetric and commute, we show that gradient descent with full-rank factorized parametrization is a first-order approximation to mirror descent, in which case we obtain an explicit characterization of the implicit bias of gradient flow as a by-product.

References in corpus (14)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• A Simpler Approach to Matrix Completion
• Guaranteed Matrix Completion via Non-convex Factorization
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Characterizing Implicit Bias in Terms of Optimization Geometry
• Regularization Techniques for Learning with Matrices
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• Implicit Regularization in Deep Learning May Not Be Explainable by Norms
• Large Deviations of Vector-valued Martingales in 2-Smooth Normed Spaces
• Provable Efficient Online Matrix Completion via Non-convex Stochastic Gradient Descent
• Implicit Regularization for Optimal Sparse Recovery
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• The Statistical Complexity of Early-Stopped Mirror Descent
• Nearly Minimax-Optimal Rates for Noisy Sparse Phase Retrieval via Early-Stopped Mirror Descent