mlsanityData to 14 Oct 2026

Zeroth and First Order Stochastic Frank-Wolfe Algorithms for Constrained Optimization

arXiv 2107.06534 ↗First posted 14 Jul 2021math.OC cs.LG eess.SPcited by 6

Not on the map. Why?

Abstract (arXiv)

This paper considers stochastic convex optimization problems with two sets of constraints: (a) deterministic constraints on the domain of the optimization variable, which are difficult to project onto; and (b) deterministic or stochastic constraints that admit efficient projection. Problems of this form arise frequently in the context of semidefinite programming as well as when various NP-hard problems are solved approximately via semidefinite relaxation. Since projection onto the first set of constraints is difficult, it becomes necessary to explore projection-free algorithms, such as the stochastic Frank-Wolfe (FW) algorithm. On the other hand, the second set of constraints cannot be handled in the same way, and must be incorporated as an indicator function within the objective function, thereby complicating the application of FW methods. Similar problems have been studied before; however, they suffer from slow convergence rates. This work, equipped with momentum based gradient tracking technique, guarantees fast convergence rates on par with the best-known rates for problems without the second set of constraints. Zeroth-order variants of the proposed algorithms are also developed and again improve upon the state-of-the-art rate results. We further propose the novel trimmed FW variants that enjoy the same convergence rates as their classical counterparts, but are empirically shown to require significantly fewer calls to the linear minimization oracle speeding up the overall algorithm. The efficacy of the proposed algorithms is tested on relevant applications of sparse matrix estimation, clustering via semidefinite relaxation, and uniform sparsest cut problem.

Key facts. Cited by 6 papers in the map (data through 14 Oct 2026). Builds on 36 of its 79 references that are in the map. First posted on arXiv 14 Jul 2021.

Builds on

36 of 79 references.

References · 36

  1. 2017ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Modelscited by 666
  2. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 306
  3. 2018Semidefinite relaxations for certifying robustness to adversarial examplescited by 179
  4. 2018Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimizationcited by 111
  5. 2020Lipschitz constant estimation of Neural Networks via sparse polynomial optimizationcited by 87
  6. 2018On the Ineffectiveness of Variance Reduced Optimization for Deep Learningcited by 48
  7. 2018Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximizationcited by 47
  8. 2019Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimizationcited by 47
  9. 2014Faster Rates for the Frank-Wolfe Method over Strongly-Convex Setscited by 44
  10. 2016Stochastic Frank-Wolfe Methods for Nonconvex Optimizationcited by 41
  11. 2016Variance-Reduced and Projection-Free Stochastic Optimizationcited by 40
  12. 2018Zeroth-order Nonconvex Stochastic Optimization: Handling Constraints, High-Dimensionality and Saddle-Pointscited by 37
24 more
  1. 2019One Sample Stochastic Frank-Wolfecited by 32
  2. 2018A Frank-Wolfe Framework for Efficient and Effective Adversarial Attackscited by 29
  3. 2016Clustering subgaussian mixtures by semidefinite programmingcited by 19
  4. 2019Efficient Projection-Free Online Methods with Stochastic Recursive Gradientcited by 19
  5. 2015An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completioncited by 15
  6. 2018Hierarchical Clustering with Structural Constraintscited by 15
  7. 2018Towards Gradient Free and Projection Free Stochastic Optimizationcited by 15
  8. 2018A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programmingcited by 14
  9. 2020Accelerated Stochastic Gradient-free and Projection-free Methodscited by 12
  10. 2020Conservative Stochastic Optimization with Expectation Constraintscited by 11
  11. 2019A Conditional Gradient-Based Augmented Lagrangian Frameworkcited by 10
  12. 2019Stochastic Frank-Wolfe for Composite Convex Minimizationcited by 9
  13. 2015A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimizationcited by 8
  14. 2016Lazifying Conditional Gradient Algorithmscited by 8
  15. 2018Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimizationcited by 8
  16. 2018Frank-Wolfe with Subsampling Oraclecited by 6
  17. 2014Stability and Performance Limits of Adaptive Primal-Dual Networkscited by 4
  18. 2017Conditional Accelerated Lazy Stochastic Gradient Descentcited by 4
  19. 2019Communication-Censored Distributed Stochastic Gradient Descentcited by 4
  20. 2019Almost surely constrained convex optimizationcited by 3
  21. 2020Conditional gradient methods for stochastically constrained convex minimizationcited by 3
  22. 2014Scalable Semidefinite Relaxation for Maximum A Posterior Estimationcited by 2
  23. 2014Complexity Issues and Randomization Strategies in Frank-Wolfe Algorithms for Machine Learningcited by 1
  24. 2015Random Multi-Constraint Projection: Stochastic Gradient Methods for Convex Optimization with Many Constraintscited by 1

Built on by

Cited by year (2026 to 14 Oct)

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

6 papers.

  1. 2025Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Ordercited by 9
  2. 2021Projection-Free Algorithm for Stochastic Bi-level Optimizationcited by 8
  3. 2022Lazy Queries Can Reduce Variance in Zeroth-order Optimizationcited by 2
  4. 2022Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimizationcited by 1
  5. 2025Communication-Efficient Zero-Order and First-Order Federated Learning Methods over Wireless Networkscited by 1
  6. 2026Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimizationcited by 1