Differentiable Greedy Submodular Maximization: Guarantees, Gradient Estimators, and Applications

Abstract

Motivated by, e.g., sensitivity analysis and end-to-end learning, the demand for differentiable optimization algorithms has been significantly increasing. In this paper, we establish a theoretically guaranteed versatile framework that makes the greedy algorithm for monotone submodular function maximization differentiable. We smooth the greedy algorithm via randomization, and prove that it almost recovers original approximation guarantees in expectation for the cases of cardinality and $\kappa$-extensible system constrains. We also show how to efficiently compute unbiased gradient estimators of any expected output-dependent quantities. We demonstrate the usefulness of our framework by instantiating it for various applications.

References in corpus (8)

• Categorical Reparameterization with Gumbel-Softmax
• The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables
• REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models
• Task-based End-to-end Model Learning in Stochastic Optimization
• Monte Carlo Gradient Estimation in Machine Learning
• Learning with Differentiable Perturbed Optimizers
• Online Continuous Submodular Maximization: From Full-Information to Bandit Feedback
• Differentiable Greedy Networks