# Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization

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

## Key facts

- Cited by 26 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2020.

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

- [A Geometric Analysis of Neural Collapse with Unconstrained Features](https://mlsanity.com/paper/2105.02375/) (2021)
- [The Lazy Neuron Phenomenon: On Emergence of Activation Sparsity in Transformers](https://mlsanity.com/paper/2210.06313/) (2022)
- [Robust Training under Label Noise by Over-parameterization](https://mlsanity.com/paper/2202.14026/) (2022)
- [Early Stopping for Deep Image Prior](https://mlsanity.com/paper/2112.06074/) (2021)
- [Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptation](https://mlsanity.com/paper/2406.04112/) (2024)
- [Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery](https://mlsanity.com/paper/2109.11154/) (2021)
- [The Law of Parsimony in Gradient Descent for Learning Deep Linear Networks](https://mlsanity.com/paper/2306.01154/) (2023)
- [Robustness in deep learning: The good (width), the bad (depth), and the ugly (initialization)](https://mlsanity.com/paper/2209.07263/) (2022)
- [Self-Validation: Early Stopping for Single-Instance Deep Generative Priors](https://mlsanity.com/paper/2110.12271/) (2021)
- [Guiding Neural Collapse: Optimising Towards the Nearest Simplex Equiangular Tight Frame](https://mlsanity.com/paper/2411.01248/) (2024)
- [Robust Implicit Regularization via Weight Normalization](https://mlsanity.com/paper/2305.05448/) (2023)
- [Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recovery](https://mlsanity.com/paper/2102.02969/) (2021)
- [A Validation Approach to Over-parameterized Matrix and Image Recovery](https://mlsanity.com/paper/2209.10675/) (2022)
- [Adaptive and Implicit Regularization for Matrix Completion](https://mlsanity.com/paper/2208.05640/) (2022)
- [Continuous Representation Methods, Theories, and Applications: An Overview and Perspectives](https://mlsanity.com/paper/2505.15222/) (2025)
- [Efficient Compression of Overparameterized Deep Models through Low-Dimensional Learning Dynamics](https://mlsanity.com/paper/2311.05061/) (2023)
- [Optimal Eye Surgeon: Finding Image Priors through Sparse Generators at Initialization](https://mlsanity.com/paper/2406.05288/) (2024)
- [Con4m: Context-aware Consistency Learning Framework for Segmented Time Series Classification](https://mlsanity.com/paper/2408.00041/) (2024)
- [Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery](https://mlsanity.com/paper/2106.09211/) (2021)
- [Removing grid structure in angle-resolved photoemission spectra via deep learning method](https://mlsanity.com/paper/2210.11200/) (2022)
- [MCDIP-ADMM: Overcoming Overfitting in DIP-based CT reconstruction](https://mlsanity.com/paper/2304.03895/) (2023)
- [AIR-Net: Adaptive and Implicit Regularization Neural Network for Matrix Completion](https://mlsanity.com/paper/2110.07557/) (2021)
- [Implicit Bias of Projected Subgradient Method Gives Provable Robust Recovery of Subspaces of Unknown Codimension](https://mlsanity.com/paper/2201.09079/) (2022)
- [Training-set-free two-stage deep learning for spectroscopic data de-noising](https://mlsanity.com/paper/2402.18830/) (2024)
- [Coordinated Sparse Recovery of Label Noise](https://mlsanity.com/paper/2404.04800/) (2024)
- [Theoretical Analysis of Sparse Optimization with Reparameterization, Weight Decay, and Adaptive Learning Rate](https://mlsanity.com/paper/2605.25134/) (2026)

## Abstract (arXiv)

Recent advances have shown that implicit bias of gradient descent on over-parameterized models enables the recovery of low-rank matrices from linear measurements, even with no prior knowledge on the intrinsic rank. In contrast, for robust low-rank matrix recovery from grossly corrupted measurements, over-parameterization leads to overfitting without prior knowledge on both the intrinsic rank and sparsity of corruption. This paper shows that with a double over-parameterization for both the low-rank matrix and sparse corruption, gradient descent with discrepant learning rates provably recovers the underlying matrix even without prior knowledge on neither rank of the matrix nor sparsity of the corruption. We further extend our approach for the robust recovery of natural images by over-parameterizing images with deep convolutional networks. Experiments show that our method handles different test images and varying corruption levels with a single learning pipeline where the network width and termination conditions do not need to be adjusted on a case-by-case basis. Underlying the success is again the implicit bias with discrepant learning rates on different over-parameterized parameters, which may bear on broader applications.