Adaptive Conditional Gradient Sliding: Projection-Free and Line-Search-Free Acceleration

Summary

Studies convex optimization over a compact convex set where projections are expensive but a linear minimization oracle (LMO) is available. Proposes the adaptive conditional gradient sliding method (AdCGS): projection-free and line-search-free, retaining Nesterov acceleration with adaptive stepsizes based on local Lipschitz estimates. Combines an accelerated outer scheme with an LMO-based inner routine, reusing gradients across multiple LMO calls to cut gradient evaluations, and controlling subproblem inexactness via a prescribed accuracy level coupled with the adaptive stepsizes. Proves accelerated rates for convex objectives matching projection-based methods, without any projection oracle; for locally strongly convex objectives establishes linear convergence without extra geometric assumptions on the constraint set (no polytopes/strongly-convex-set requirements). Experiments on constrained ell_p regression, logistic regression, and least squares show AdCGS improves over projection-free baselines and is competitive when projections are cheap.

Keywords

optimization · conditional gradient · Frank-Wolfe · projection-free · Nesterov acceleration · adaptive stepsizes

Topics

optimization, convex optimization, Frank-Wolfe, projection-free

Research notes

• User-supplied arXiv link on 2026-09-29: https://arxiv.org/abs/2601.20443
• Single author: Shota Takahashi.
• Submitted 2026-01-28 (v1), last revised 2026-07-22 (v2), math.OC.
• Relevant to the collection's optimization/algorithm entries as a projection-free acceleration method.