Iterative regularization for convex regularizers
arXiv:2006.09859
Abstract
We study iterative regularization for linear models, when the bias is convex but not necessarily strongly convex. We characterize the stability properties of a primal-dual gradient based approach, analyzing its convergence in the presence of worst case deterministic noise. As a main example, we specialize and illustrate the results for the problem of robust sparse recovery. Key to our analysis is a combination of ideas from regularization theory and optimization in the presence of errors. Theoretical results are complemented by experiments showing that state-of-the-art performances can be achieved with considerable computational speed-ups.
References in corpus (13)
- A Convergence Theory for Deep Learning via Over-Parameterization
- Convergence Rates of Inexact Proximal-Gradient Methods for Convex Optimization
- Early stopping and non-parametric regression: An optimal data-dependent stopping rule
- Characterizing Implicit Bias in Terms of Optimization Geometry
- Geometry of Optimization and Implicit Regularization in Deep Learning
- Sparse Recovery via Differential Inclusions
- A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
- Implicit Regularization for Optimal Sparse Recovery
- Iterative regularization via dual diagonal descent
- Don't relax: early stopping for convex regularization
- The Statistical Complexity of Early-Stopped Mirror Descent
- Implicit Regularization of Accelerated Methods in Hilbert Spaces
- Gradient descent in a generalised Bregman distance framework