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

Chong You, Zhihui Zhu, Qing Qu, Yi Ma

Introduction

Robust recovery aims to reconstruct structured signals, such as low-rank matrices or natural images, from data corrupted by heavy, sparse noise. Traditional approaches rely on explicit prior knowledge—like the exact rank of a matrix or the sparsity level of the noise—and require meticulous tuning of regularization parameters ($\lambda$). While over-parameterized models like the Deep Image Prior (DIP) have emerged as powerful alternatives that don't require explicit priors, they suffer from a significant drawback: they eventually overfit the noise. This necessitates "early stopping," a heuristic that is difficult to implement in practice without knowing the ground truth.

This paper introduces a "double over-parameterization" framework that leverages the implicit bias of gradient descent to achieve stable, robust recovery without the need for early stopping or manual hyperparameter tuning.

Methodology: Double Over-parameterization

The core innovation lies in parameterizing both the signal and the corruption. For a low-rank matrix $X$, the authors use a factorized form $X = UU^\top$. For natural images, the signal is represented by a deep convolutional network $\phi(\theta)$. Crucially, the sparse corruption $s$ is also over-parameterized using a Hadamard product formulation: $s = g \circ g - h \circ h$.

The "secret sauce" of this approach is the use of discrepant learning rates. Instead of a single global learning rate, the signal parameters ($\theta$ or $U$) and the noise parameters ($g, h$) are updated using different step sizes. The ratio between these learning rates, denoted as $\alpha$, dictates the balance between signal reconstruction and noise rejection.

Key Insights: Learning Rate as a Regularizer

A profound theoretical insight of this work is that the ratio of learning rates $\alpha$ acts as an implicit regularization parameter. Specifically, the authors prove that $\alpha$ is inversely proportional to the regularization weight ($\lambda \approx 1/\alpha$) in a corresponding convex optimization problem. This allows researchers to control the "strength" of the model's prior simply by adjusting how fast different components learn, rather than adding explicit penalty terms to the loss function.

Impact of the learning rate ratio $\alpha$ on recovery error, demonstrating its role as an implicit regularizer.

As shown in the figure above, there is an optimal range for $\alpha$ where the recovery error for both the signal ($X_*$) and the noise ($S_*$) is minimized.

Experimental Results and Stability

The proposed method was evaluated on synthetic Robust PCA tasks and standard image datasets corrupted with "salt-and-pepper" noise (up to 70%).

Robust Matrix and Image Recovery

In Robust PCA, the method successfully recovered low-rank matrices even with 50% corruption, matching the performance of state-of-the-art convex solvers. In image recovery tasks, the method consistently outperformed standard DIP and its variants. For example, on an F16 jet image with 50% corruption, the proposed method achieved a PSNR of 31.60 dB, significantly higher than the 29.07 dB achieved by DIP-$\ell_1$.

Robust recovery performance for matrices (left) and images (right) showing stability over iterations.

Eliminating Early Stopping

Perhaps the most significant result is the stability of the learning process. Unlike traditional DIP, which sees a sharp decline in PSNR as it begins to "memorize" noise, the double over-parameterization approach reaches a steady state. As seen in the performance curves, the PSNR remains high and stable even after hundreds of thousands of iterations, effectively eliminating the need for the "early stopping" hack.

Conclusion

By combining double over-parameterization with discrepant learning rates, this framework provides a robust, stable, and theoretically grounded method for signal recovery. The discovery that learning rate ratios can serve as implicit regularizers opens new avenues for designing self-regularizing neural networks that are less sensitive to noise and require less manual intervention.

Summary updated

Abstract

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.
BibTeX
@inproceedings{you2020robust,
  author = {Chong You and Zhihui Zhu and Qing Qu and Yi Ma},
  title = {{Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
}
Figure