# Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 43 of its 80 references that are in the map.
- First posted on arXiv 29 Jun 2021.

## Builds on (most cited first, 30 of 43)

- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Network Lasso: Clustering and Optimization in Large Graphs](https://mlsanity.com/paper/1507.00280/) (2015)
- [Variance-Reduced and Projection-Free Stochastic Optimization](https://mlsanity.com/paper/1602.02101/) (2016)
- [Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Points](https://mlsanity.com/paper/1809.06474/) (2018)
- [Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithm](https://mlsanity.com/paper/1905.13194/) (2019)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees](https://mlsanity.com/paper/1506.02681/) (2015)
- [Complexity of Linear Minimization and Projection on Some Sets](https://mlsanity.com/paper/2101.10040/) (2021)
- [New Analysis and Results for the Frank-Wolfe Method](https://mlsanity.com/paper/1307.0873/) (2013)
- [Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Method](https://mlsanity.com/paper/2010.01848/) (2020)
- [Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Balls](https://mlsanity.com/paper/1708.02105/) (2017)
- [Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization](https://mlsanity.com/paper/1311.5750/) (2013)
- [Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimization](https://mlsanity.com/paper/1302.2325/) (2013)
- [Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints](https://mlsanity.com/paper/1407.0088/) (2014)
- [A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfe](https://mlsanity.com/paper/1702.06457/) (2017)
- [Linearly Convergent Frank-Wolfe with Backtracking Line-Search](https://mlsanity.com/paper/1806.05123/) (2018)
- [Efficient Online Linear Optimization with Approximation Algorithms](https://mlsanity.com/paper/1709.03093/) (2017)
- [Online Improper Learning with an Approximation Oracle](https://mlsanity.com/paper/1804.07837/) (2018)
- [Barrier Frank-Wolfe for Marginal Inference](https://mlsanity.com/paper/1511.02124/) (2015)
- [Polytope conditioning and linear convergence of the Frank-Wolfe algorithm](https://mlsanity.com/paper/1512.06142/) (2015)
- [Boosting Frank-Wolfe by Chasing Gradients](https://mlsanity.com/paper/2003.06369/) (2020)
- [Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsity](https://mlsanity.com/paper/2006.00558/) (2020)
- [New Perspectives on k-Support and Cluster Norms](https://mlsanity.com/paper/1512.08204/) (2015)
- [Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopes](https://mlsanity.com/paper/1605.06492/) (2016)
- [Stochastic Frank-Wolfe for Composite Convex Minimization](https://mlsanity.com/paper/1901.10348/) (2019)
- [Frank-Wolfe with a Nearest Extreme Point Oracle](https://mlsanity.com/paper/2102.02029/) (2021)

## Abstract (arXiv)

In this paper, we consider approximate Frank-Wolfe (FW) algorithms to solve convex optimization problems over graph-structured support sets where the linear minimization oracle (LMO) cannot be efficiently obtained in general. We first demonstrate that two popular approximation assumptions (additive and multiplicative gap errors) are not applicable in that no cheap gap-approximate LMO oracle exists. Thus, approximate dual maximization oracles (DMO) are proposed, which approximate the inner product rather than the gap. We prove that the standard FW method using a δ-approximate DMO converges as O((1-δ) √s/δ) in the worst case, and as O(L/(δ2 t)) over a δ-relaxation of the constraint set. Furthermore, when the solution is on the boundary, a variant of FW converges as O(1/t2) under the quadratic growth assumption. Our empirical results suggest that even these improved bounds are pessimistic, showing fast convergence in recovering real-world images with graph-structured sparsity.