# Frank-Wolfe with a Nearest Extreme Point Oracle

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 3 Feb 2021.

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

- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle](https://mlsanity.com/paper/1309.5550/) (2013)
- [New Analysis and Results for the Frank-Wolfe Method](https://mlsanity.com/paper/1307.0873/) (2013)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [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)
- [Locally Accelerated Conditional Gradients](https://mlsanity.com/paper/1906.07867/) (2019)
- [Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergence](https://mlsanity.com/paper/2006.01719/) (2020)
- [Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexity](https://mlsanity.com/paper/1912.01467/) (2019)
- [Logarithmic Regret for Online Gradient Descent Beyond Strong Convexity](https://mlsanity.com/paper/1802.04623/) (2018)
- [On the von Neumann and Frank-Wolfe Algorithms with Away Steps](https://mlsanity.com/paper/1507.04073/) (2015)

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

- [Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programming](https://mlsanity.com/paper/2309.00203/) (2023)
- [Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound](https://mlsanity.com/paper/2501.14349/) (2025)
- [A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimization](https://mlsanity.com/paper/2202.04296/) (2022)
- [Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Loss](https://mlsanity.com/paper/2402.08180/) (2024)
- [Bandit and Delayed Feedback in Online Structured Prediction](https://mlsanity.com/paper/2502.18709/) (2025)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Non-Stationary Online Structured Prediction with Surrogate Losses](https://mlsanity.com/paper/2510.07086/) (2025)
- [Complexities of Weak Proximal Oracle Methods for Composite Convex Optimization](https://mlsanity.com/paper/2609.24423/) (2026)

## Abstract (arXiv)

We consider variants of the classical Frank-Wolfe algorithm for constrained smooth convex minimization, that instead of access to the standard oracle for minimizing a linear function over the feasible set, have access to an oracle that can find an extreme point of the feasible set that is closest in Euclidean distance to a given vector. We first show that for many feasible sets of interest, such an oracle can be implemented with the same complexity as the standard linear optimization oracle. We then show that with such an oracle we can design new Frank-Wolfe variants which enjoy significantly improved complexity bounds in case the set of optimal solutions lies in the convex hull of a subset of extreme points with small diameter (e.g., a low-dimensional face of a polytope). In particular, for many 0--1 polytopes, under quadratic growth and strict complementarity conditions, we obtain the first linearly convergent variant with rate that depends only on the dimension of the optimal face and not on the ambient dimension.