# Smooth over-parameterized solvers for non-smooth structured optimization

arXiv: https://arxiv.org/abs/2205.01385 · HTML: https://mlsanity.com/paper/2205.01385/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 80 references that are in the map.
- First posted on arXiv 3 May 2022.

## Builds on (most cited first, 16 of 16)

- [Characterizing Implicit Bias in Terms of Optimization Geometry](https://mlsanity.com/paper/1802.08246/) (2018)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Implicit Regularization for Optimal Sparse Recovery](https://mlsanity.com/paper/1909.05122/) (2019)
- [On the Implicit Bias of Initialization Shape: Beyond Infinitesimal Mirror Descent](https://mlsanity.com/paper/2102.09769/) (2021)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [Exponentiated Gradient Meets Gradient Descent](https://mlsanity.com/paper/1902.01903/) (2019)
- [Celer: a Fast Solver for the Lasso with Dual Extrapolation](https://mlsanity.com/paper/1802.07481/) (2018)
- [Convergence Rates of Gradient Methods for Convex Optimization in the Space of Measures](https://mlsanity.com/paper/2105.08368/) (2021)
- [Mirrorless Mirror Descent: A Natural Derivation of Mirror Descent](https://mlsanity.com/paper/2004.01025/) (2020)
- [Smooth Bilevel Programming for Sparse Regularization](https://mlsanity.com/paper/2106.01429/) (2021)
- [On Quasi-Newton Forward--Backward Splitting: Proximal Calculus and Convergence](https://mlsanity.com/paper/1801.08691/) (2018)
- [Estimating Traffic and Anomaly Maps via Network Tomography](https://mlsanity.com/paper/1407.1660/) (2014)
- [Efficient Smoothed Concomitant Lasso Estimation for High Dimensional Regression](https://mlsanity.com/paper/1606.02702/) (2016)
- [Generalized Conditional Gradient with Augmented Lagrangian for Composite Minimization](https://mlsanity.com/paper/1901.01287/) (2019)
- [Local Linear Convergence Analysis of Primal-Dual Splitting Methods](https://mlsanity.com/paper/1705.01926/) (2017)
- [Adapting Regularized Low Rank Models for Parallel Architectures](https://mlsanity.com/paper/1702.02241/) (2017)

## Built on by (most cited first, 11 of 11)

- [spred: Solving L1 Penalty with SGD](https://mlsanity.com/paper/2210.01212/) (2022)
- [Deep Weight Factorization: Sparse Learning Through the Lens of Artificial Symmetries](https://mlsanity.com/paper/2502.02496/) (2025)
- [Smoothing the Edges: Smooth Optimization for Sparse Regularization using Hadamard Overparametrization](https://mlsanity.com/paper/2307.03571/) (2023)
- [Type-II Saddles and Probabilistic Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.13093/) (2023)
- [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023)
- [A Unified Framework for Entropy Search and Expected Improvement in Bayesian Optimization](https://mlsanity.com/paper/2501.18756/) (2025)
- [Learning Multi-Index Models with Hyper-Kernel Ridge Regression](https://mlsanity.com/paper/2510.02532/) (2025)
- [Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks](https://mlsanity.com/paper/2406.02769/) (2024)
- [Optimization Insights into Deep Diagonal Linear Networks](https://mlsanity.com/paper/2412.16765/) (2024)
- [Entropic Mirror Descent for Linear Systems: Polyak's Stepsize and Implicit Bias](https://mlsanity.com/paper/2505.02614/) (2025)
- [Theoretical Analysis of Sparse Optimization with Reparameterization, Weight Decay, and Adaptive Learning Rate](https://mlsanity.com/paper/2605.25134/) (2026)

## Abstract (arXiv)

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.