mlsanityData to 7 Oct 2026

Frank-Wolfe with a Nearest Extreme Point Oracle

arXiv 2102.02029 ↗First posted 3 Feb 2021math.OC cs.LG stat.MLcited by 8

Not on the map. Why?

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.

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

Builds on

15 of 30 references.

References · 15

  1. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  2. 2016Variance-Reduced and Projection-Free Stochastic Optimizationcited by 40
  3. 2013The Complexity of Large-scale Convex Programming under a Linear Optimization Oraclecited by 27
  4. 2013New Analysis and Results for the Frank-Wolfe Methodcited by 17
  5. 2017Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Ballscited by 15
  6. 2015Linearly Convergent Away-Step Conditional Gradient for Non-strongly Convex Functionscited by 12
  7. 2015Polytope conditioning and linear convergence of the Frank-Wolfe algorithmcited by 9
  8. 2016Faster Projection-free Convex Optimization over the Spectrahedroncited by 9
  9. 2016Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopescited by 9
  10. 2020Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsitycited by 9
  11. 2019Locally Accelerated Conditional Gradientscited by 8
  12. 2020Spectral Frank-Wolfe Algorithm: Strict Complementarity and Linear Convergencecited by 8
3 more
  1. 2019Linear Convergence of Frank-Wolfe for Rank-One Matrix Recovery Without Strong Convexitycited by 7
  2. 2018Logarithmic Regret for Online Gradient Descent Beyond Strong Convexitycited by 4
  3. 2015On the von Neumann and Frank-Wolfe Algorithms with Away Stepscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 1; 2023: 1; 2024: 1; 2025: 3; 2026: 1.

8 papers.

  1. 2023Generalization Bound and Learning Methods for Data-Driven Projections in Linear Programmingcited by 10
  2. 2022A Projection-free Algorithm for Constrained Stochastic Multi-level Composition Optimizationcited by 8
  3. 2024Online Structured Prediction with Fenchel--Young Losses and Improved Surrogate Regret for Online Multiclass Classification with Logistic Losscited by 7
  4. 2025Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Boundcited by 7
  5. 2025Bandit and Delayed Feedback in Online Structured Predictioncited by 1
  6. 2021Approximate Frank-Wolfe Algorithms over Graph-structured Support Setscited by 0
  7. 2025Non-Stationary Online Structured Prediction with Surrogate Lossescited by 0
  8. 2026Complexities of Weak Proximal Oracle Methods for Composite Convex Optimizationcited by 0