Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
arXiv:2006.08857
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.
References in corpus (17)
- Beyond a Gaussian Denoiser: Residual Learning of Deep CNN for Image Denoising
- The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Low-rank optimization for semidefinite convex problems
- Variational Denoising Network: Toward Blind Noise Modeling and Removal
- How Does Learning Rate Decay Help Modern Neural Networks?
- Global Optimality in Low-rank Matrix Optimization
- Denoising and Regularization via Exploiting the Structural Bias of Convolutional Generators
- Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?
- Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements
- Undersampled Phase Retrieval with Outliers
- Implicit Regularization for Optimal Sparse Recovery
- CycleISP: Real Image Restoration via Improved Data Synthesis
- Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
- Learning Rate Annealing Can Provably Help Generalization, Even for Convex Problems
- On implicit regularization: Morse functions and applications to matrix factorization
- Hadamard Wirtinger Flow for Sparse Phase Retrieval