# Stochastic Conditional Gradient++

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Feb 2019.

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

- [Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noise](https://mlsanity.com/paper/2506.04192/) (2025)
- [Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimization](https://mlsanity.com/paper/2102.11050/) (2021)
- [Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning](https://mlsanity.com/paper/2105.14024/) (2021)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Interpretable Neural Networks with Frank-Wolfe: Sparse Relevance Maps and Relevance Orderings](https://mlsanity.com/paper/2110.08105/) (2021)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [When Should a Leader Act Suboptimally? The Role of Inferability in Repeated Stackelberg Games](https://mlsanity.com/paper/2310.00468/) (2023)
- [Accelerating LMO-Based Optimization via Implicit Gradient Transport](https://mlsanity.com/paper/2605.05577/) (2026)

## Abstract (arXiv)

In this paper, we consider the general non-oblivious stochastic optimization where the underlying stochasticity may change during the optimization procedure and depends on the point at which the function is evaluated. We develop Stochastic Frank-Wolfe++ (SFW++ ), an efficient variant of the conditional gradient method for minimizing a smooth non-convex function subject to a convex body constraint. We show that SFW++  converges to an ε-first order stationary point by using O(1/ε3) stochastic gradients. Once further structures are present, SFW++'s theoretical guarantees, in terms of the convergence rate and quality of its solution, improve. In particular, for minimizing a convex function, SFW++  achieves an ε-approximate optimum while using O(1/ε2) stochastic gradients. It is known that this rate is optimal in terms of stochastic gradient evaluations. Similarly, for maximizing a monotone continuous DR-submodular function, a slightly different form of SFW++ , called Stochastic Continuous Greedy++ (SCG++ ), achieves a tight [(1-1/e)OPT -ε] solution while using O(1/ε2) stochastic gradients. Through an information theoretic argument, we also prove that SCG++ 's convergence rate is optimal. Finally, for maximizing a non-monotone continuous DR-submodular function, we can achieve a [(1/e)OPT -ε] solution by using O(1/ε2) stochastic gradients. We should highlight that our results and our novel variance reduction technique trivially extend to the standard and easier oblivious stochastic optimization settings for (non-)covex and continuous submodular settings.