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

• URL: http://arxiv.org/abs/2006.08857v1
• Date: Tue, 16 Jun 2020 01:21:22 GMT
• Title: Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Authors: Chong You, Zhihui Zhu, Qing Qu, Yi Ma
• Abstract summary: We show that 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. 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.
• Score: 46.22605476383572
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Recovery Guarantees of Unsupervised Neural Networks for Inverse Problems trained with Gradient Descent [0.6522338519818377]
  We show that convergence and recovery guarantees for generic loss functions hold true when trained through gradient flow. We also show that the discretization only affects the overparametrization bound for a two-layer DIP network by a constant.
  arXiv  Detail & Related papers  (2024-03-08T15:45:13Z)
• A Validation Approach to Over-parameterized Matrix and Image Recovery [29.29430943998287]
  We consider the problem of recovering a low-rank matrix from several random linear measurements. We show that the proposed validation approach can also be efficiently used for image prior, an an image with a deep network.
  arXiv  Detail & Related papers  (2022-09-21T22:01:23Z)
• Memory-Efficient Backpropagation through Large Linear Layers [107.20037639738433]
  In modern neural networks like Transformers, linear layers require significant memory to store activations during backward pass. This study proposes a memory reduction approach to perform backpropagation through linear layers.
  arXiv  Detail & Related papers  (2022-01-31T13:02:41Z)
• Robust Depth Completion with Uncertainty-Driven Loss Functions [60.9237639890582]
  We introduce uncertainty-driven loss functions to improve the robustness of depth completion and handle the uncertainty in depth completion. Our method has been tested on KITTI Depth Completion Benchmark and achieved the state-of-the-art robustness performance in terms of MAE, IMAE, and IRMSE metrics.
  arXiv  Detail & Related papers  (2021-12-15T05:22:34Z)
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery [37.05862765171643]
  We consider a robust factorization of a low-rank matrix with no prior knowledge on the rank. We show that our particular design of diminishing the size of the matrix effectively prevents overfitting under overized models.
  arXiv  Detail & Related papers  (2021-09-23T05:54:46Z)
• Implicit Regularization of Sub-Gradient Method in Robust Matrix Recovery: Don't be Afraid of Outliers [6.320141734801679]
  We show that a simple sub-gradient method converges to the true low-rank solution efficiently. We also build upon a new notion of restricted isometry property, called sign-RIP, to prove the robustness of the method.
  arXiv  Detail & Related papers  (2021-02-05T02:52:00Z)
• Learning Mixtures of Low-Rank Models [89.39877968115833]
  We study the problem of learning computational mixtures of low-rank models. We develop an algorithm that is guaranteed to recover the unknown matrices with near-optimal sample. In addition, the proposed algorithm is provably stable against random noise.
  arXiv  Detail & Related papers  (2020-09-23T17:53:48Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)
• Tomographic Auto-Encoder: Unsupervised Bayesian Recovery of Corrupted Data [4.725669222165439]
  We propose a new probabilistic method for unsupervised recovery of corrupted data. Given a large ensemble of degraded samples, our method recovers accurate posteriors of clean values. We test our model in a data recovery task under the common setting of missing values and noise.
  arXiv  Detail & Related papers  (2020-06-30T16:18:16Z)
• Corruption-robust exploration in episodic reinforcement learning [76.19192549843727]
  We study multi-stage episodic reinforcement learning under adversarial corruptions in both the rewards and the transition probabilities of the underlying system. Our framework yields efficient algorithms which attain near-optimal regret in the absence of corruptions. Notably, our work provides the first sublinear regret guarantee which any deviation from purely i.i.d. transitions in the bandit-feedback model for episodic reinforcement learning.
  arXiv  Detail & Related papers  (2019-11-20T03:49:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.