# Parameter-free Locally Accelerated Conditional Gradients

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 44 references that are in the map.
- First posted on arXiv 12 Feb 2021.

## Builds on (most cited first, 25 of 25)

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD](https://mlsanity.com/paper/1801.02982/) (2018)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [The Approximate Duality Gap Technique: A Unified Theory of First-Order Methods](https://mlsanity.com/paper/1712.02485/) (2017)
- [On Acceleration with Noise-Corrupted Gradients](https://mlsanity.com/paper/1805.12591/) (2018)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization](https://mlsanity.com/paper/2002.11860/) (2020)
- [Linearly Convergent Frank-Wolfe with Backtracking Line-Search](https://mlsanity.com/paper/1806.05123/) (2018)
- [Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functions](https://mlsanity.com/paper/1504.05002/) (2015)
- [Polytope conditioning and linear convergence of the Frank-Wolfe algorithm](https://mlsanity.com/paper/1512.06142/) (2015)
- [Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity](https://mlsanity.com/paper/2006.00558/) (2020)
- [Faster Projection-free Convex Optimization over the Spectrahedron](https://mlsanity.com/paper/1605.06203/) (2016)
- [Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes](https://mlsanity.com/paper/1605.06492/) (2016)
- [Lazifying Conditional Gradient Algorithms](https://mlsanity.com/paper/1610.05120/) (2016)
- [Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/1906.07867/) (2019)
- [Self-Concordant Analysis of Frank-Wolfe Algorithms](https://mlsanity.com/paper/2002.04320/) (2020)
- [Restarting Frank-Wolfe: Faster Rates Under H"olderian Error Bounds](https://mlsanity.com/paper/1810.02429/) (2018)
- [Projection-Free Adaptive Gradients for Large-Scale Optimization](https://mlsanity.com/paper/2009.14114/) (2020)
- [Nearly optimal first-order methods for convex optimization under gradient norm measure: An adaptive regularization approach](https://mlsanity.com/paper/1912.12004/) (2019)
- [Second-order Conditional Gradient Sliding](https://mlsanity.com/paper/2002.08907/) (2020)
- [Blended Conditional Gradients: the unconditioning of conditional gradients](https://mlsanity.com/paper/1805.07311/) (2018)
- [Limited Memory Kelley's Method Converges for Composite Convex and Submodular Objectives](https://mlsanity.com/paper/1807.07531/) (2018)
- [The condition of a function relative to a polytope](https://mlsanity.com/paper/1802.00271/) (2018)

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

- [Linear Bandits on Uniformly Convex Sets](https://mlsanity.com/paper/2103.05907/) (2021)
- [Linearization Algorithms for Fully Composite Optimization](https://mlsanity.com/paper/2302.12808/) (2023)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [Accelerated Frank-Wolfe Algorithms: Complementarity Conditions and Sparsity](https://mlsanity.com/paper/2511.02821/) (2025)
- [Zero-order Parameter-free Optimization for LMO-based Methods: Novel Approach for Efficient Fine-tuning](https://mlsanity.com/paper/2606.14970/) (2026)

## Abstract (arXiv)

Projection-free conditional gradient (CG) methods are the algorithms of choice for constrained optimization setups in which projections are often computationally prohibitive but linear optimization over the constraint set remains computationally feasible. Unlike in projection-based methods, globally accelerated convergence rates are in general unattainable for CG. However, a very recent work on Locally accelerated CG (LaCG) has demonstrated that local acceleration for CG is possible for many settings of interest. The main downside of LaCG is that it requires knowledge of the smoothness and strong convexity parameters of the objective function. We remove this limitation by introducing a novel, Parameter-Free Locally accelerated CG (PF-LaCG) algorithm, for which we provide rigorous convergence guarantees. Our theoretical results are complemented by numerical experiments, which demonstrate local acceleration and showcase the practical improvements of PF-LaCG over non-accelerated algorithms, both in terms of iteration count and wall-clock time.