# Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Nov 2017.

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

- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [Compression-aware Training of Neural Networks using Frank-Wolfe](https://mlsanity.com/paper/2205.11921/) (2022)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [Communication-Efficient Decentralized Online Continuous DR-Submodular Maximization](https://mlsanity.com/paper/2208.08681/) (2022)
- [A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization](https://mlsanity.com/paper/2302.09766/) (2023)
- [Decision-Focused Evaluation of Worst-Case Distribution Shift](https://mlsanity.com/paper/2407.03557/) (2024)
- [Online Learning for Non-monotone Submodular Maximization: From Full Information to Bandit Feedback](https://mlsanity.com/paper/2208.07632/) (2022)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [Improved Regret Bounds for Online Submodular Maximization](https://mlsanity.com/paper/2106.07836/) (2021)
- [Don't Be Greedy, Just Relax! Pruning LLMs via Frank-Wolfe](https://mlsanity.com/paper/2510.13713/) (2025)
- [Submodular Maximization via Taylor Series Approximation](https://mlsanity.com/paper/2101.07423/) (2021)
- [One Gradient Frank-Wolfe for Decentralized Online Convex and Submodular Optimization](https://mlsanity.com/paper/2210.16790/) (2022)
- [Decomposable Submodular Maximization in Federated Setting](https://mlsanity.com/paper/2402.00138/) (2024)
- [Online Orthogonal Dictionary Learning Based on Frank-Wolfe Method](https://mlsanity.com/paper/2103.01484/) (2021)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Approximate Frank-Wolfe Algorithms over Graph-structured Support Sets](https://mlsanity.com/paper/2107.00472/) (2021)
- [Stochastic Submodular Maximization via Polynomial Estimators](https://mlsanity.com/paper/2303.09960/) (2023)
- [High Probability Bounds for Stochastic Continuous Submodular Maximization](https://mlsanity.com/paper/2303.11937/) (2023)
- [Discrete and Continuous Difference of Submodular Minimization](https://mlsanity.com/paper/2506.07952/) (2025)
- [Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization](https://mlsanity.com/paper/2604.03419/) (2026)

## Abstract (arXiv)

In this paper, we study the problem of textitconstrained and textitstochastic continuous submodular maximization. Even though the objective function is not concave (nor convex) and is defined in terms of an expectation, we develop a variant of the conditional gradient method, called alg, which achieves a textittight approximation guarantee. More precisely, for a monotone and continuous DR-submodular function and subject to a textitgeneral convex body constraint, we prove that alg achieves a [(1-1/e)OPT -eps] guarantee (in expectation) with O(1/eps3) stochastic gradient computations. This guarantee matches the known hardness results and closes the gap between deterministic and stochastic continuous submodular maximization. By using stochastic continuous optimization as an interface, we also provide the first (1-1/e) tight approximation guarantee for maximizing a textitmonotone but stochastic submodular textitset function subject to a general matroid constraint.