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

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

## 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 (most cited first, 30 of 36)

- [ZOO: Zeroth Order Optimization based Black-box Attacks to Deep Neural Networks without Training Substitute Models](https://mlsanity.com/paper/1708.03999/) (2017)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [Semidefinite relaxations for certifying robustness to adversarial examples](https://mlsanity.com/paper/1811.01057/) (2018)
- [Zeroth-Order Stochastic Variance Reduction for Nonconvex Optimization](https://mlsanity.com/paper/1805.10367/) (2018)
- [Lipschitz constant estimation of Neural Networks via sparse polynomial optimization](https://mlsanity.com/paper/2004.08688/) (2020)
- [On the Ineffectiveness of Variance Reduced Optimization for Deep Learning](https://mlsanity.com/paper/1812.04529/) (2018)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Improved Zeroth-Order Variance Reduced Algorithms and Analysis for Nonconvex Optimization](https://mlsanity.com/paper/1910.12166/) (2019)
- [Faster Rates for the Frank-Wolfe Method over Strongly-Convex Sets](https://mlsanity.com/paper/1406.1305/) (2014)
- [Stochastic Frank-Wolfe Methods for Nonconvex Optimization](https://mlsanity.com/paper/1607.08254/) (2016)
- [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)
- [One Sample Stochastic Frank-Wolfe](https://mlsanity.com/paper/1910.04322/) (2019)
- [A Frank-Wolfe Framework for Efficient and Effective Adversarial Attacks](https://mlsanity.com/paper/1811.10828/) (2018)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [Efficient Projection-Free Online Methods with Stochastic Recursive Gradient](https://mlsanity.com/paper/1910.09396/) (2019)
- [An Extended Frank-Wolfe Method with "In-Face" Directions, and its Application to Low-Rank Matrix Completion](https://mlsanity.com/paper/1511.02204/) (2015)
- [Hierarchical Clustering with Structural Constraints](https://mlsanity.com/paper/1805.09476/) (2018)
- [Towards Gradient Free and Projection Free Stochastic Optimization](https://mlsanity.com/paper/1810.03233/) (2018)
- [A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming](https://mlsanity.com/paper/1804.08544/) (2018)
- [Accelerated Stochastic Gradient-free and Projection-free Methods](https://mlsanity.com/paper/2007.12625/) (2020)
- [Conservative Stochastic Optimization with Expectation Constraints](https://mlsanity.com/paper/2008.05758/) (2020)
- [A Conditional Gradient-Based Augmented Lagrangian Framework](https://mlsanity.com/paper/1901.04013/) (2019)
- [Stochastic Frank-Wolfe for Composite Convex Minimization](https://mlsanity.com/paper/1901.10348/) (2019)
- [A Smooth Primal-Dual Optimization Framework for Nonsmooth Composite Convex Minimization](https://mlsanity.com/paper/1507.06243/) (2015)
- [Lazifying Conditional Gradient Algorithms](https://mlsanity.com/paper/1610.05120/) (2016)
- [Generalized Stochastic Frank-Wolfe Algorithm with Stochastic "Substitute" Gradient for Structured Convex Optimization](https://mlsanity.com/paper/1807.07680/) (2018)
- [Frank-Wolfe with Subsampling Oracle](https://mlsanity.com/paper/1803.07348/) (2018)
- [Stability and Performance Limits of Adaptive Primal-Dual Networks](https://mlsanity.com/paper/1408.3693/) (2014)
- [Conditional Accelerated Lazy Stochastic Gradient Descent](https://mlsanity.com/paper/1703.05840/) (2017)

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

- [Leveraging Coordinate Momentum in SignSGD and Muon: Memory-Optimized Zero-Order](https://mlsanity.com/paper/2506.04430/) (2025)
- [Projection-Free Algorithm for Stochastic Bi-level Optimization](https://mlsanity.com/paper/2110.11721/) (2021)
- [Lazy Queries Can Reduce Variance in Zeroth-order Optimization](https://mlsanity.com/paper/2206.07126/) (2022)
- [Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization](https://mlsanity.com/paper/2202.13212/) (2022)
- [Communication-Efficient Zero-Order and First-Order Federated Learning Methods over Wireless Networks](https://mlsanity.com/paper/2508.08013/) (2025)
- [Adaptive Lipschitz-Free Conditional Gradient Methods for Stochastic Composite Nonconvex Optimization](https://mlsanity.com/paper/2603.06369/) (2026)

## 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.