# Smooth Bilevel Programming for Sparse Regularization

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 68 references that are in the map.
- First posted on arXiv 2 Jun 2021.

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

- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [How to Escape Saddle Points Efficiently](https://mlsanity.com/paper/1703.00887/) (2017)
- [Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares](https://mlsanity.com/paper/1410.2596/) (2014)
- [Gap Safe screening rules for sparsity enforcing penalties](https://mlsanity.com/paper/1611.05780/) (2016)
- [First-order methods almost always avoid saddle points: the case of vanishing step-sizes](https://mlsanity.com/paper/1906.07772/) (2019)
- [Celer: a Fast Solver for the Lasso with Dual Extrapolation](https://mlsanity.com/paper/1802.07481/) (2018)
- [Fast Optimal Transport Averaging of Neuroimaging Data](https://mlsanity.com/paper/1503.08596/) (2015)
- [On the saddle point problem for non-convex optimization](https://mlsanity.com/paper/1405.4604/) (2014)
- [GAP Safe screening rules for sparse multi-task and multi-class models](https://mlsanity.com/paper/1506.03736/) (2015)
- [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)

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

- [A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse](https://mlsanity.com/paper/2112.04660/) (2021)
- [Incremental Learning in Diagonal Linear Networks](https://mlsanity.com/paper/2208.14673/) (2022)
- [Benchopt: Reproducible, efficient and collaborative optimization benchmarks](https://mlsanity.com/paper/2206.13424/) (2022)
- [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)
- [Smooth over-parameterized solvers for non-smooth structured optimization](https://mlsanity.com/paper/2205.01385/) (2022)
- [Type-II Saddles and Probabilistic Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/2303.13093/) (2023)
- [Remove Symmetries to Control Model Expressivity and Improve Optimization](https://mlsanity.com/paper/2408.15495/) (2024)
- [Implicit regularization in AI meets generalized hardness of approximation in optimization -- Sharp results for diagonal linear networks](https://mlsanity.com/paper/2307.07410/) (2023)
- [Precise asymptotics of reweighted least-squares algorithms for linear diagonal networks](https://mlsanity.com/paper/2406.02769/) (2024)
- [Hard labels sampled from sparse targets mislead rotation invariant algorithms](https://mlsanity.com/paper/2603.20967/) (2026)
- [DUET: Decentralized Bilevel Optimization without Lower-Level Strong Convexity](https://mlsanity.com/paper/2606.21153/) (2026)
- [Enhancing Privacy in Decentralized Min-Max Optimization: A Differentially Private Approach](https://mlsanity.com/paper/2508.07505/) (2025)
- [Theoretical Analysis of Sparse Optimization with Reparameterization, Weight Decay, and Adaptive Learning Rate](https://mlsanity.com/paper/2605.25134/) (2026)

## Abstract (arXiv)

Iteratively reweighted least square (IRLS) is a popular approach to solve sparsity-enforcing regression problems in machine learning. State of the art approaches are more efficient but typically rely on specific coordinate pruning schemes. In this work, we show how a surprisingly simple reparametrization of IRLS, coupled with a bilevel resolution (instead of an alternating scheme) is able to achieve top performances on a wide range of sparsity (such as Lasso, group Lasso and trace norm regularizations), regularization strength (including hard constraints), and design matrices (ranging from correlated designs to differential operators). Similarly to IRLS, our method only involves linear systems resolutions, but in sharp contrast, corresponds to the minimization of a smooth function. Despite being non-convex, we show that there is no spurious minima and that saddle points are "ridable", so that there always exists a descent direction. We thus advocate for the use of a BFGS quasi-Newton solver, which makes our approach simple, robust and efficient. We perform a numerical benchmark of the convergence speed of our algorithm against state of the art solvers for Lasso, group Lasso, trace norm and linearly constrained problems. These results highlight the versatility of our approach, removing the need to use different solvers depending on the specificity of the ML problem under study.