# Flat minima generalize for low-rank matrix recovery

arXiv: https://arxiv.org/abs/2203.03756 · HTML: https://mlsanity.com/paper/2203.03756/

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 65 references that are in the map.
- First posted on arXiv 7 Mar 2022.

## Builds on (most cited first, 30 of 35)

- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Sharpness-Aware Minimization for Efficiently Improving Generalization](https://mlsanity.com/paper/2010.01412/) (2020)
- [On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minima](https://mlsanity.com/paper/1609.04836/) (2016)
- [Averaging Weights Leads to Wider Optima and Better Generalization](https://mlsanity.com/paper/1803.05407/) (2018)
- [Visualizing the Loss Landscape of Neural Nets](https://mlsanity.com/paper/1712.09913/) (2017)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Big Transfer (BiT): General Visual Representation Learning](https://mlsanity.com/paper/1912.11370/) (2019)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Exploring Generalization in Deep Learning](https://mlsanity.com/paper/1706.08947/) (2017)
- [Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data](https://mlsanity.com/paper/1703.11008/) (2017)
- [Sharp Minima Can Generalize For Deep Nets](https://mlsanity.com/paper/1703.04933/) (2017)
- [Entropy-SGD: Biasing Gradient Descent Into Wide Valleys](https://mlsanity.com/paper/1611.01838/) (2016)
- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [Implicit Regularization in Matrix Factorization](https://mlsanity.com/paper/1705.09280/) (2017)
- [Train longer, generalize better: closing the generalization gap in large batch training of neural networks](https://mlsanity.com/paper/1705.08741/) (2017)
- [Three Factors Influencing Minima in SGD](https://mlsanity.com/paper/1711.04623/) (2017)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balanced](https://mlsanity.com/paper/1806.00900/) (2018)
- [A Bayesian Perspective on Generalization and Stochastic Gradient Descent](https://mlsanity.com/paper/1710.06451/) (2017)
- [No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysis](https://mlsanity.com/paper/1704.00708/) (2017)
- [Theoretical insights into the optimization landscape of over-parameterized shallow neural networks](https://mlsanity.com/paper/1707.04926/) (2017)
- [A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case](https://mlsanity.com/paper/1910.01635/) (2019)
- [How do infinite width bounded norm networks look in function space?](https://mlsanity.com/paper/1902.05040/) (2019)
- [Revisiting Small Batch Training for Deep Neural Networks](https://mlsanity.com/paper/1804.07612/) (2018)
- [Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization](https://mlsanity.com/paper/2106.14289/) (2021)
- [Compressive sensing with un-trained neural networks: Gradient descent finds the smoothest approximation](https://mlsanity.com/paper/2005.03991/) (2020)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programming](https://mlsanity.com/paper/1310.0807/) (2013)
- [ROP: Matrix recovery via rank-one projections](https://mlsanity.com/paper/1310.5791/) (2013)

## Built on by (most cited first, 28 of 28)

- [Understanding the Generalization Benefit of Normalization Layers: Sharpness Reduction](https://mlsanity.com/paper/2206.07085/) (2022)
- [Dichotomy of Early and Late Phase Implicit Biases Can Provably Induce Grokking](https://mlsanity.com/paper/2311.18817/) (2023)
- [Sharpness Minimization Algorithms Do Not Only Minimize Sharpness To Achieve Better Generalization](https://mlsanity.com/paper/2307.11007/) (2023)
- [Catapults in SGD: spikes in the training loss and their impact on generalization through feature learning](https://mlsanity.com/paper/2306.04815/) (2023)
- [Improving Convergence and Generalization Using Parameter Symmetries](https://mlsanity.com/paper/2305.13404/) (2023)
- [Sparse identification of nonlinear dynamics and Koopman operators with Shallow Recurrent Decoder Networks](https://mlsanity.com/paper/2501.13329/) (2025)
- [Loss Spike in Training Neural Networks](https://mlsanity.com/paper/2305.12133/) (2023)
- [Linear Recursive Feature Machines provably recover low-rank matrices](https://mlsanity.com/paper/2401.04553/) (2024)
- [How to escape sharp minima with random perturbations](https://mlsanity.com/paper/2305.15659/) (2023)
- [The Inductive Bias of Flatness Regularization for Deep Matrix Factorization](https://mlsanity.com/paper/2306.13239/) (2023)
- [Tilted Sharpness-Aware Minimization](https://mlsanity.com/paper/2410.22656/) (2024)
- [Zeroth-Order Optimization Finds Flat Minima](https://mlsanity.com/paper/2506.05454/) (2025)
- [On Statistical Properties of Sharpness-Aware Minimization: Provable Guarantees](https://mlsanity.com/paper/2302.11836/) (2023)
- [Simplicity Bias via Global Convergence of Sharpness Minimization](https://mlsanity.com/paper/2410.16401/) (2024)
- [Regularization Implies balancedness in the deep linear network](https://mlsanity.com/paper/2511.01137/) (2025)
- [Flat Minima and Generalization: Insights from Stochastic Convex Optimization](https://mlsanity.com/paper/2511.03548/) (2025)
- [Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens](https://mlsanity.com/paper/2410.18858/) (2024)
- [Convergence Dynamics of Over-Parameterized Score Matching for a Single Gaussian](https://mlsanity.com/paper/2511.22069/) (2025)
- [Low-Rank Adaptation Redux for Large Models](https://mlsanity.com/paper/2604.21905/) (2026)
- [Sharpness of Minima in Deep Matrix Factorization](https://mlsanity.com/paper/2509.25783/) (2025)
- [Generalization at the Edge of Stability](https://mlsanity.com/paper/2604.19740/) (2026)
- [Probability Distribution Learning and Its Application in Deep Learning](https://mlsanity.com/paper/2406.05666/) (2024)
- [Flatness After All?](https://mlsanity.com/paper/2506.17809/) (2025)
- [R'enyi Sharpness: A Novel Sharpness that Strongly Correlates with Generalization](https://mlsanity.com/paper/2510.07758/) (2025)
- [Does Sparse Connectivity Improve Generalization? Convolutional Networks Below the Edge of Stability](https://mlsanity.com/paper/2603.04807/) (2026)
- [Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing](https://mlsanity.com/paper/2303.14244/) (2023)
- [Flatness-Aware Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2510.02174/) (2025)
- [Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics](https://mlsanity.com/paper/2606.31390/) (2026)

## Abstract (arXiv)

Empirical evidence suggests that for a variety of overparameterized nonlinear models, most notably in neural network training, the growth of the loss around a minimizer strongly impacts its performance. Flat minima -- those around which the loss grows slowly -- appear to generalize well. This work takes a step towards understanding this phenomenon by focusing on the simplest class of overparameterized nonlinear models: those arising in low-rank matrix recovery. We analyze overparameterized matrix and bilinear sensing, robust PCA, covariance matrix estimation, and single hidden layer neural networks with quadratic activation functions. In all cases, we show that flat minima, measured by the trace of the Hessian, exactly recover the ground truth under standard statistical assumptions. For matrix completion, we establish weak recovery, although empirical evidence suggests exact recovery holds here as well. We conclude with synthetic experiments that illustrate our findings and discuss the effect of depth on flat solutions.