Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
arXiv:1711.01660
Abstract
In this paper, we study the problem of \textit{constrained} and \textit{stochastic} 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 \textit{tight} approximation guarantee. More precisely, for a monotone and continuous DR-submodular function and subject to a \textit{general} convex body constraint, we prove that \alg achieves a $[(1-1/e)\text{OPT} -\eps]$ guarantee (in expectation) with $\mathcal{O}{(1/\eps^3)}$ 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 tight approximation guarantee for maximizing a \textit{monotone but stochastic} submodular \textit{set} function subject to a general matroid constraint.
References in corpus (12)
- Matrix Completion has No Spurious Local Minimum
- A Parallel Stochastic Approximation Method for Nonconvex Multi-Agent Optimization Problems
- Efficient approaches for escaping higher order saddle points in non-convex optimization
- The Landscape of Empirical Risk for Non-convex Losses
- Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
- On Graduated Optimization for Stochastic Non-Convex Problems
- Greed is Good: Near-Optimal Submodular Maximization via Greedy Optimization
- Gradient Methods for Submodular Maximization
- Submodular Functions: from Discrete to Continous Domains
- Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments
- Stochastic Submodular Maximization: The Case of Coverage Functions
- A Newton-Based Method for Nonconvex Optimization with Fast Evasion of Saddle Points