2026/08/05 by Elad Hazan
Mathematics · #math.OC
arxiv created 2026/08/05 · arxiv updated 2026/08/06
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.