Gradient Methods for Submodular Maximization

Abstract

In this paper, we study the problem of maximizing continuous submodular functions that naturally arise in many learning applications such as those involving utility functions in active learning and sensing, matrix approximations and network inference. Despite the apparent lack of convexity in such functions, we prove that stochastic projected gradient methods can provide strong approximation guarantees for maximizing continuous submodular functions with convex constraints. More specifically, we prove that for monotone continuous DR-submodular functions, all fixed points of projected gradient ascent provide a factor $1/2$ approximation to the global maxima. We also study stochastic gradient and mirror methods and show that after $\mathcal{O}(1/{\epsilon }^2)$ iterations these methods reach solutions which achieve in expectation objective values exceeding $(\frac{\text{OPT}}{2}-\epsilon )$. An immediate application of our results is to maximize submodular functions that are defined stochastically, i.e. the submodular function is defined as an expectation over a family of submodular functions with an unknown distribution. We will show how stochastic gradient methods are naturally well-suited for this setting, leading to a factor $1/2$ approximation when the function is monotone. In particular, it allows us to approximately maximize discrete, monotone submodular optimization problems via projected gradient descent on a continuous relaxation, directly connecting the discrete and continuous domains. Finally, experiments on real data demonstrate that our projected gradient methods consistently achieve the best utility compared to other continuous baselines while remaining competitive in terms of computational effort.

References in corpus (4)

• Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• Submodular Functions: from Discrete to Continous Domains
• A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns

Cited by in corpus (12)

• Online Continuous Submodular Maximization
• Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization
• Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
• Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
• One Sample Stochastic Frank-Wolfe
• Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization
• Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
• Distributionally Robust Submodular Maximization
• Defending Elections Against Malicious Spread of Misinformation
• Maximizing Monotone DR-submodular Continuous Functions by Derivative-free Optimization
• Scalable Projection-Free Optimization
• Minimax Optimization: The Case of Convex-Submodular