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.
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$.
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