Implicit Regularization in Matrix Sensing via Mirror Descent

Fan Wu, Patrick Rebeschini

Introduction

In the fields of signal processing and machine learning, matrix sensing presents a fundamental challenge: reconstructing a high-dimensional, low-rank matrix—such as a collaborative filtering table or a compressed image—from a limited number of linear measurements.

Traditionally, researchers have tackled this problem using two primary approaches. The first is explicit regularization, which involves adding a penalty term like the nuclear norm to the objective function to force the solution to be low-rank. The second is factorization, which re-parameterizes the matrix as a product of two smaller matrices ($X = UV^\top$). While factorization inherently limits the rank, it transforms a convex problem into a complex, non-convex one.

This paper investigates a third, highly compelling phenomenon: implicit regularization. The authors ask whether running a simple algorithm on the raw, unregularized problem can allow the algorithm's own internal logic to bias it toward the correct low-rank solution. While this implicit bias has been observed empirically for Gradient Descent, the theoretical mathematics explaining why and under what conditions it works have remained elusive, particularly for general rectangular matrices. This work reveals that Mirror Descent (MD), a classic first-order optimization algorithm, possesses a hidden talent for finding low-rank solutions in matrix sensing without any explicit regularization.

Methodology

Unlike standard Gradient Descent, which navigates in a straight line within Euclidean space, Mirror Descent adapts to the underlying geometry of the problem using a construct known as a mirror map.

The authors' key technical contributions center on these maps and their analysis:

  • Spectral Mirror Maps: The researchers employ the spectral hypentropy map for general rectangular matrices and the spectral entropy map for positive semidefinite (PSD) matrices. These maps act directly on the singular values (or eigenvalues) of the matrix.
  • Potential-Based Analysis: Rather than relying on complex KKT optimality conditions, the authors utilize a potential function based on Bregman divergence. This approach allows them to track how the algorithm's iterates systematically move closer to the set of global minimizers.
  • First-Order Approximation: They demonstrate that the popular method of Gradient Descent on factorized matrices ($X = UU^\top$) is effectively a first-order approximation of Mirror Descent utilizing a spectral entropy map.

As a theoretical work, the paper validates its claims not with large-scale real-world datasets, but through rigorous simulations. These include synthetic Gaussian sensing matrices to test Restricted Isometry Property (RIP) conditions, randomly sampled low-rank matrices to verify recovery guarantees, and matrix completion simulations to test the algorithm's ability to reconstruct missing entries.

Key Insights and Results

By choosing specific mirror maps, the authors prove that Mirror Descent naturally converges to matrices that minimize the nuclear norm, matching the recovery guarantees of much more complex or computationally intensive methods.

The "Chameleon" Property and RIP

Mirror Descent acts as an interpolator. By tuning a single parameter ($\beta$), the algorithm can shift its implicit bias from minimizing the Frobenius norm (standard Euclidean distance) to minimizing the nuclear norm (a standard proxy for rank). Strikingly, the authors show that Mirror Descent recovers low-rank matrices under the Restricted Isometry Property (RIP)—the exact same condition required for explicit nuclear norm minimization. This proves that MD is just as powerful as hard-coded regularization, providing the first recovery guarantees for an implicit regularization-based algorithm in general rectangular matrix sensing without requiring extra assumptions beyond standard convex optimization.

The Role of Initialization

In the PSD case, the scale of the initialization ($\alpha I$) acts as a critical control knob. Starting very close to zero ($\alpha \to 0$) biases the algorithm toward the nuclear norm (low rank). Conversely, a massive initialization ($\alpha \to \infty$) biases the algorithm toward maximizing the nuclear norm.

Bridging Mirror Descent and Gradient Descent

The paper successfully provides a theoretical bridge between Mirror Descent and Gradient Descent on factorized models. Numerical simulations show that Mirror Descent and factorized Gradient Descent track each other almost perfectly when measurements are plentiful. This suggests that the "magic" low-rank recovery frequently observed in deep learning might simply be Gradient Descent approximating the behavior of Mirror Descent.

Limitations and Future Work

While theoretically profound, the approach has practical limitations. Mirror Descent carries a high computational overhead per iteration, requiring a Singular Value Decomposition (SVD) or a matrix exponential at every step, whereas factorized Gradient Descent only requires simple matrix multiplications. Furthermore, while the paper proves the limit of where the algorithm converges, it does not provide a detailed rate of convergence.

Finally, the error bounds depend logarithmically on the initialization parameters ($\alpha, \beta$). While theoretically sound, achieving high precision in practice might require uncomfortably small parameter values. The authors suggest that future work should focus on developing faster versions of these mirror-like updates that maintain the same beneficial implicit bias without the heavy computational price tag of SVD.

Summary updated

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.
BibTeX
@inproceedings{wu2021implicit,
  author = {Fan Wu and Patrick Rebeschini},
  title = {{Implicit Regularization in Matrix Sensing via Mirror Descent}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=3h1iwXmYVVJ},
}
Figure