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

We study convex optimization problems over a compact convex set where projections are expensive but a linear minimization oracle (LMO) is available.

We propose the adaptive conditional gradient sliding method (AdCGS), a projection-free and line-search-free method that retains Nesterov's acceleration with adaptive stepsizes based on local Lipschitz estimates.

AdCGS combines an accelerated outer scheme with an LMO-based inner routine.

It reuses gradients across multiple LMO calls to reduce gradient evaluations, while controlling the subproblem inexactness via a prescribed accuracy level coupled with adaptive stepsizes.

We prove accelerated rates for convex objective functions, matching projection-based methods, without relying on a projection oracle.

For locally strongly convex objective functions, we further establish linear convergence without additional geometric assumptions on the constraint set, such as polytopes or strongly convex sets.

Experiments on constrained $\ell_p$ regression, logistic regression, and least-squares problems demonstrate that AdCGS improves over projection-free baselines and provides competitive performance when projections are inexpensive.