Smooth over-parameterized solvers for non-smooth structured optimization
From MaRDI portal
Abstract: Non-smooth optimization is a core ingredient of many imaging or machine learning pipelines. Non-smoothness encodes structural constraints on the solutions, such as sparsity, group sparsity, low-rank and sharp edges. It is also the basis for the definition of robust loss functions and scale-free functionals such as square-root Lasso. Standard approaches to deal with non-smoothness leverage either proximal splitting or coordinate descent. These approaches are effective but usually require parameter tuning, preconditioning or some sort of support pruning. In this work, we advocate and study a different route, which operates a non-convex but smooth over-parametrization of the underlying non-smooth optimization problems. This generalizes quadratic variational forms that are at the heart of the popular Iterative Reweighted Least Squares (IRLS). Our main theoretical contribution connects gradient descent on this reformulation to a mirror descent flow with a varying Hessian metric. This analysis is crucial to derive convergence bounds that are dimension-free. This explains the efficiency of the method when using small grid sizes in imaging. Our main algorithmic contribution is to apply the Variable Projection (VarPro) method which defines a new formulation by explicitly minimizing over part of the variables. This leads to a better conditioning of the minimized functional and improves the convergence of simple but very efficient gradient-based methods, for instance quasi-Newton solvers. We exemplify the use of this new solver for the resolution of regularized regression problems for inverse problems and supervised learning, including total variation prior and non-convex regularizers.
Recommendations
Cites work
- scientific article; zbMATH DE number 6388313 (Why is no real title available?)
- scientific article; zbMATH DE number 3790208 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A proximal point analysis of the preconditioned alternating direction method of multipliers
- A variational approach to remove outliers and impulse noise
- Adapting regularized low-rank models for parallel architectures
- Adaptive restart for accelerated gradient schemes
- Algorithms for Separable Nonlinear Least Squares Problems
- An algorithm for total variation minimization and applications
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Approximation accuracy, gradient methods, and error bound for structured convex optimization
- Convergence rates of gradient methods for convex optimization in the space of measures
- Convex multi-task feature learning
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Gap safe screening rules for sparsity enforcing penalties
- Generalized Projection Operators in Banach Spaces: Properties and Applications
- Generalized conditional gradient with augmented Lagrangian for composite minimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Image recovery via total variation minimization and related problems
- Inverse problems in spaces of measures
- Iterative Methods for Total Variation Denoising
- Iteratively reweighted least squares minimization for sparse recovery
- Lasso, fractional norm and structured sparse estimation using a Hadamard product parametrization
- Local linear convergence analysis of primal-dual splitting methods
- Locally adaptive regression splines
- Matrix completion and low-rank SVD via fast alternating least squares
- Mirror descent and nonlinear projected subgradient methods for convex optimization.
- Model Selection and Estimation in Regression with Grouped Variables
- Nonlinear total variation based noise removal algorithms
- On quasi-Newton forward-backward splitting: proximal calculus and convergence
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Optimization with sparsity-inducing penalties
- Regularizers for structured sparsity
- Robust principal component analysis?
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Safe Feature Elimination in Sparse Supervised Learning
- Schur complements and its applications to symmetric nonnegative and \(Z\)-matrices
- Separable nonlinear least squares: the variable projection method and its applications
- Single-exponential bounds for the smallest singular value of Vandermonde matrices in the sub-Rayleigh regime
- Sparse image and signal processing. Wavelets, curvelets, morphological diversity
- Sparse regularization on thin grids. I: The \textsc{Lasso}.
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Square-root lasso: pivotal recovery of sparse signals via conic programming
- The Differentiation of Pseudo-Inverses and Nonlinear Least Squares Problems Whose Variables Separate
- Towards a Mathematical Theory of Super‐resolution
- Trace norm regularization: reformulations, algorithms, and multi-task learning
- Two-Point Step Size Gradient Methods
- Variable metric forward-backward splitting with applications to monotone inclusions in duality
- Variational Analysis
- \(\chi^{2}\)-confidence sets in high-dimensional regression
Cited in
(4)
This page was built for publication: Smooth over-parameterized solvers for non-smooth structured optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6110460)
