# A Fast and Scalable Polyatomic Frank-Wolfe Algorithm for the LASSO

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Dec 2021.

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

- [Robust face recognition based on the wing loss and the ℓ1 regularization](https://mlsanity.com/paper/2503.18652/) (2025)

## Abstract (arXiv)

We propose a fast and scalable Polyatomic Frank-Wolfe (P-FW) algorithm for the resolution of high-dimensional LASSO regression problems. The latter improves upon traditional Frank-Wolfe methods by considering generalized greedy steps with polyatomic (i.e. linear combinations of multiple atoms) update directions, hence allowing for a more efficient exploration of the search space. To preserve sparsity of the intermediate iterates, we re-optimize the LASSO problem over the set of selected atoms at each iteration. For efficiency reasons, the accuracy of this re-optimization step is relatively low for early iterations and gradually increases with the iteration count. We provide convergence guarantees for our algorithm and validate it in simulated compressed sensing setups. Our experiments reveal that P-FW outperforms state-of-the-art methods in terms of runtime, both for FW methods and optimal first-order proximal gradient methods such as the Fast Iterative Soft-Thresholding Algorithm (FISTA).