mlsanityData to 7 Oct 2026

Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets

arXiv 2107.00472 ↗First posted 29 Jun 2021math.OC cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

43 of 80 references.

References · 43

  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  2. 2015On the Global Linear Convergence of Frank-Wolfe Optimization Variantscited by 76
  3. 2014On Iterative Hard Thresholding Methods for High-dimensional M-Estimationcited by 53
  4. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  5. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 42
  6. 2015Network Lasso: Clustering and Optimization in Large Graphscited by 42
  7. 2016Variance-Reduced and Projection-Free Stochastic Optimizationcited by 40
  8. 2018Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Pointscited by 36
  9. 2019Sinkhorn Barycenters with Free Support via Frank-Wolfe Algorithmcited by 27
  10. 2017Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gapcited by 21
  11. 2015Frank-Wolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guaranteescited by 20
  12. 2021Complexity of Linear Minimization and Projection on Some Setscited by 19
31 more
  1. 2013New Analysis and Results for the Frank-Wolfe Methodcited by 17
  2. 2020Projection Efficient Subgradient Method and Optimal Nonsmooth Frank-Wolfe Methodcited by 17
  3. 2017Linear Convergence of a Frank-Wolfe Type Algorithm over Trace-Norm Ballscited by 15
  4. 2013Conditional Gradient Algorithms for Norm-Regularized Smooth Convex Optimizationcited by 13
  5. 2013Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimizationcited by 13
  6. 2014Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraintscited by 13
  7. 2018Linearly Convergent Frank-Wolfe with Backtracking Line-Searchcited by 13
  8. 2017A Unified Optimization View on Generalized Matching Pursuit and Frank-Wolfecited by 12
  9. 2017Efficient Online Linear Optimization with Approximation Algorithmscited by 12
  10. 2018Online Improper Learning with an Approximation Oraclecited by 11
  11. 2015Barrier Frank-Wolfe for Marginal Inferencecited by 10
  12. 2015Polytope conditioning and linear convergence of the Frank-Wolfe algorithmcited by 9
  13. 2015New Perspectives on k-Support and Cluster Normscited by 9
  14. 2016Linear-memory and Decomposition-invariant Linearly Convergent Conditional Gradient Algorithm for Structured Polytopescited by 9
  15. 2019Stochastic Frank-Wolfe for Composite Convex Minimizationcited by 9
  16. 2020Boosting Frank-Wolfe by Chasing Gradientscited by 9
  17. 2020Revisiting Frank-Wolfe for Polytopes: Strict Complementarity and Sparsitycited by 9
  18. 2021Frank-Wolfe with a Nearest Extreme Point Oraclecited by 8
  19. 2017Fast Rates for Bandit Optimization with Upper-Confidence Frank-Wolfecited by 7
  20. 2018On Matching Pursuit and Coordinate Descentcited by 7
  21. 2014Generalized Conditional Gradient for Sparse Estimationcited by 6
  22. 2017Combinatorial Penalties: Which structures are preserved by convex relaxations?cited by 6
  23. 2018Frank-Wolfe with Subsampling Oraclecited by 6
  24. 2015The restricted strong convexity revisited: Analysis of equivalence to error bound and quadratic growthcited by 4
  25. 2017Learning Infinite RBMs with Frank-Wolfecited by 4
  26. 2014Tight convex relaxations for sparse matrix factorizationcited by 3
  27. 2016Fitting Spectral Decay with the k-Support Normcited by 3
  28. 2019Blended Matching Pursuitcited by 3
  29. 2020Safe Screening for the Generalized Conditional Gradient Methodcited by 3
  30. 2014Approximation Algorithms for Model-Based Compressive Sensingcited by 2
  31. 2013Group-Sparse Model Selection: Hardness and Relaxationscited by 1

Built on by

Not cited yet.