# A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Aug 2026.

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

- [Local LMO is Secretly a Projection Method!](https://mlsanity.com/paper/2609.33383/) (2026)
- [Lower Bounds for Randomized Linear-Oracle Optimization over Strongly Convex Sets](https://mlsanity.com/paper/2610.13590/) (2026)

## Abstract (arXiv)

We consider minimizing a smooth, strongly convex function over a convex set. Projected gradient descent is known to converge linearly in this setting, but each iteration requires a projection onto the feasible set, which may be computationally expensive. We show that when the feasible set is smooth, projection can be replaced by one gradient computation and a single supporting-tangent computation per iteration, while preserving linear convergence. Moreover, the required tangent can be approximated to sufficient accuracy using widetilde O(d) membership-oracle queries, where d is the ambient dimension. Previously, projection-free linear convergence was known only for polyhedral sets or for sets that are both smooth and strongly convex.