# "Active-set complexity" of proximal gradient: How long does it take to find the sparsity pattern?

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Dec 2017.

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

- [Implicit differentiation for fast hyperparameter selection in non-smooth convex learning](https://mlsanity.com/paper/2105.01637/) (2021)
- [Accelerating Frank-Wolfe via Averaging Step Directions](https://mlsanity.com/paper/2205.11794/) (2022)
- [Screening for a Reweighted Penalized Conditional Gradient Method](https://mlsanity.com/paper/2107.01106/) (2021)
- [Faster Accelerated First-order Methods for Convex Optimization with Strongly Convex Function Constraints](https://mlsanity.com/paper/2212.11143/) (2022)
- [Reducing Discretization Error in the Frank-Wolfe Method](https://mlsanity.com/paper/2304.01432/) (2023)
- [Complexity of Classical Acceleration for ℓ1-Regularized PageRank](https://mlsanity.com/paper/2602.21138/) (2026)
- [Trajectory-Restricted Optimization Conditions and Geometry-Aware Linear Convergence](https://mlsanity.com/paper/2604.17067/) (2026)

## Abstract (arXiv)

Proximal gradient methods have been found to be highly effective for solving minimization problems with non-negative constraints or L1-regularization. Under suitable nondegeneracy conditions, it is known that these algorithms identify the optimal sparsity pattern for these types of problems in a finite number of iterations. However, it is not known how many iterations this may take. We introduce the notion of the "active-set complexity", which in these cases is the number of iterations before an algorithm is guaranteed to have identified the final sparsity pattern. We further give a bound on the active-set complexity of proximal gradient methods in the common case of minimizing the sum of a strongly-convex smooth function and a separable convex non-smooth function.