Online Continuous Submodular Maximization

Abstract

In this paper, we consider an online optimization process, where the objective functions are not convex (nor concave) but instead belong to a broad class of continuous submodular functions. We first propose a variant of the Frank-Wolfe algorithm that has access to the full gradient of the objective functions. We show that it achieves a regret bound of $O(\sqrt{T})$ (where $T$ is the horizon of the online optimization problem) against a $(1-1/e)$-approximation to the best feasible solution in hindsight. However, in many scenarios, only an unbiased estimate of the gradients are available. For such settings, we then propose an online stochastic gradient ascent algorithm that also achieves a regret bound of $O(\sqrt{T})$ regret, albeit against a weaker $1/2$-approximation to the best feasible solution in hindsight. We also generalize our results to $\gamma$-weakly submodular functions and prove the same sublinear regret bounds. Finally, we demonstrate the efficiency of our algorithms on a few problem instances, including non-convex/non-concave quadratic programs, multilinear extensions of submodular set functions, and D-optimal design.

Accepted by AISTATS 2018

References in corpus (8)

• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• A Linearly Convergent Conditional Gradient Algorithm with Applications to Online and Stochastic Optimization
• Submodular Functions: from Discrete to Continous Domains
• Gradient Methods for Submodular Maximization
• Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments
• Efficient Regret Minimization in Non-Convex Games
• Stochastic Submodular Maximization: The Case of Coverage Functions

Cited by in corpus (13)

• Submodularity in Action: From Machine Learning to Signal Processing Applications
• Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
• Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
• Stochastic Conditional Gradient++
• Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
• Multi-Point Bandit Algorithms for Nonstationary Online Nonconvex Optimization
• Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints
• Black Box Submodular Maximization: Discrete and Continuous Settings
• Online DR-Submodular Maximization with Stochastic Cumulative Constraints
• Defending Elections Against Malicious Spread of Misinformation
• Differentially Private Online Submodular Optimization
• An Exact Method for Constrained Maximization of the Conditional Value-at-Risk of a Class of Stochastic Submodular Functions
• Scalable Projection-Free Optimization