A Linearly Convergent Projection-Free Algorithm for Smooth Convex Sets
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.04321
curl -X POST /api/v1/records/arxiv/2608.04321/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.04321/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'