# First-Order Sparse Convex Optimization: Better Rates with Sparse Updates

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 26 references that are in the map.
- First posted on arXiv 23 Jun 2025.

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

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Conditional Gradient Methods](https://mlsanity.com/paper/2211.14103/) (2022)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Sparse recovery by reduced variance stochastic approximation](https://mlsanity.com/paper/2006.06365/) (2020)
- [Improved Complexities of Conditional Gradient-Type Methods with Applications to Robust Matrix Recovery Problems](https://mlsanity.com/paper/1802.05581/) (2018)
- [Fast Stochastic Algorithms for Low-rank and Nonsmooth Matrix Problems](https://mlsanity.com/paper/1809.10477/) (2018)
- [On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization](https://mlsanity.com/paper/2012.10469/) (2020)
- [Faster Projection-Free Augmented Lagrangian Methods via Weak Proximal Oracle](https://mlsanity.com/paper/2210.13968/) (2022)

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

- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)

## Abstract (arXiv)

It was recently established that for convex optimization problems with sparse optimal solutions (be it entry-wise sparsity or matrix rank-wise sparsity) it is possible to design first-order methods with linear convergence rates that depend on an improved mixed-norm condition number of the form fracβ1sα2, where β1 is the ℓ1-Lipschitz continuity constant of the gradient, α2 is the ℓ2-quadratic growth constant, and s is the sparsity of optimal solutions. However, beyond the improved convergence rate, these methods are unable to leverage the sparsity of optimal solutions towards improving the runtime of each iteration as well, which may still be prohibitively high for high-dimensional problems. In this work, we establish that linear convergence rates which depend on this improved condition number can be obtained using only sparse updates, which may result in overall significantly improved running times. Moreover, our methods are considerably easier to implement.