# Linearly Convergent Frank-Wolfe with Backtracking Line-Search

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2018.

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

- [A Conditional Gradient-based Method for Simple Bilevel Optimization with Convex Lower-level Problem](https://mlsanity.com/paper/2206.08868/) (2022)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [Parameter-free Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/2102.06806/) (2021)
- [First-Order Methods for Convex Optimization](https://mlsanity.com/paper/2101.00935/) (2021)
- [Projection-Free Online Convex Optimization via Efficient Newton Iterations](https://mlsanity.com/paper/2306.11121/) (2023)
- [Scalable Frank-Wolfe on Generalized Self-concordant Functions via Simple Steps](https://mlsanity.com/paper/2105.13913/) (2021)
- [Scalable DC Optimization via Adaptive Frank-Wolfe Algorithms](https://mlsanity.com/paper/2507.17545/) (2025)
- [Adaptive Conditional Gradient Descent](https://mlsanity.com/paper/2510.11440/) (2025)
- [Boosting Variational Inference With Locally Adaptive Step-Sizes](https://mlsanity.com/paper/2105.09240/) (2021)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Nonlinear Distributionally Robust Optimization](https://mlsanity.com/paper/2306.03202/) (2023)
- [Practical and Performant Enhancements for Maximization of Algebraic Connectivity](https://mlsanity.com/paper/2511.08694/) (2025)
- [Lloyd's K-Means Clustering Algorithm Is Frank-Wolfe in Disguise](https://mlsanity.com/paper/2607.25190/) (2026)

## Abstract (arXiv)

Structured constraints in Machine Learning have recently brought the Frank-Wolfe (FW) family of algorithms back in the spotlight. While the classical FW algorithm has poor local convergence properties, the Away-steps and Pairwise FW variants have emerged as improved variants with faster convergence. However, these improved variants suffer from two practical limitations: they require at each iteration to solve a 1-dimensional minimization problem to set the step-size and also require the Frank-Wolfe linear subproblems to be solved exactly. In this paper, we propose variants of Away-steps and Pairwise FW that lift both restrictions simultaneously. The proposed methods set the step-size based on a sufficient decrease condition, and do not require prior knowledge of the objective. Furthermore, they inherit all the favorable convergence properties of the exact line-search version, including linear convergence for strongly convex functions over polytopes. Benchmarks on different machine learning problems illustrate large performance gains of the proposed variants.