Differentiable Greedy Algorithm for Monotone Submodular Maximization: Guarantees, Gradient Estimators, and Applications

Shinsaku SakaueAISTATS 2021 · OpenReview

Abstract

Motivated by, e.g., sensitivity analysis and end-to-end learning, the demand for differentiable optimization algorithms has been increasing. This paper presents a theoretically guaranteed differentiable greedy algorithm for monotone submodular function maximization. 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$-extendible system constraints. We then present how to efficiently compute gradient estimators of any expected output-dependent quantities. We demonstrate the usefulness of our method by instantiating it for various applications.

Introduction

Submodular function maximization is a cornerstone of discrete optimization, essential for tasks such as data summarization, sensor placement, and viral marketing. In many real-world scenarios, these functions depend on continuous parameters $\theta$ (e.g., edge probabilities in a social network). Two critical tasks arise: sensitivity analysis, which examines how changes in $\theta$ affect the output, and decision-focused learning, which aims to train models to predict $\theta$ to maximize the final objective.

However, the standard greedy algorithm is a discrete process, making its output non-differentiable with respect to $\theta$. While heuristics like "softmax" replacements exist, they often lack theoretical guarantees and computational efficiency. This paper introduces "Smoothed Greedy," a framework that maintains strong approximation guarantees while enabling efficient gradient estimation for end-to-end learning.

Methodology: The Smoothed Greedy Algorithm

The core innovation is the replacement of deterministic selection with a stochastic process based on regularized optimization. In each step $k$, instead of picking the element $u \in U_k$ with the highest marginal gain $f_S(u, \theta)$, the algorithm selects an element according to a probability distribution $p_k(\theta)$. This distribution is the solution to a regularized optimization problem: $p_k(\theta) = \text{argmax}_{p \in \Delta^{n_k}} \{ \langle g_k(\theta), p \rangle - \Omega_k(p) \}$. For instance, using an entropy term for $\Omega_k$ leads to a softmax distribution.

Algorithm 1: The Smoothed Greedy framework replaces deterministic selection with a stochastic policy $p_k(\theta)$ based on regularized marginal gains.

Theoretical Guarantees

The authors prove that Smoothed Greedy achieves an approximation ratio of $(1 - 1/e) - \delta K$ for cardinality constraints and $1/(\kappa+1) - \delta K$ for $\kappa$-extendible systems, where $\delta$ represents the smoothing cost. This ensures solution quality is preserved despite the randomization.

Gradient Estimation and Variance Reduction

To differentiate through the algorithm without the exponential cost of unrolling, the score function method (REINFORCE) is employed. This allows for gradient estimation of expected outputs via sampling. To stabilize training, a variance reduction technique using baseline correction is implemented, which is vital for high-dimensional parameter spaces.

Experimental Evaluation

The framework was evaluated on tasks including synthetic bipartite influence maximization and movie recommendation using the MovieLens 100K dataset. In the MovieLens setup, the goal was to select a set of movies to satisfy a large user group, comparing Smoothed Greedy against standard "two-stage" learning and continuous relaxation methods.

Key Results

Experiments demonstrate that Smoothed Greedy, particularly the variance-reduced version (VR-SG-100), outperforms state-of-the-art continuous relaxation methods in terms of objective value on test data. As shown in the results table, VR-SG-100 consistently achieves the highest scores across budget sizes $K=5, 10, 20$.

Experimental results on MovieLens 100K for different budget sizes $K$. Smoothed Greedy (SG) and its variance-reduced (VR) variants consistently outperform continuous and two-stage baselines.

Beyond performance, the method is computationally efficient. For a budget of $K=20$, Smoothed Greedy was significantly faster than continuous relaxation (~3.77s vs ~6.11s per update). The smoothing parameter $\epsilon$ serves as a tunable trade-off between theoretical optimality and the smoothness of the gradient landscape.

Conclusion

Smoothed Greedy bridges the gap between discrete greedy heuristics and continuous deep learning pipelines. By providing a differentiable layer with rigorous theoretical bounds, it enables the integration of combinatorial optimization into end-to-end learning systems. Future work may address the variance challenges associated with small smoothing parameters and the handling of non-differentiable submodular functions.

Summary updated

Abstract

Motivated by, e.g., sensitivity analysis and end-to-end learning, the demand for differentiable optimization algorithms has been increasing. This paper presents a theoretically guaranteed differentiable greedy algorithm for monotone submodular function maximization. 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$-extendible system constraints. We then present how to efficiently compute gradient estimators of any expected output-dependent quantities. We demonstrate the usefulness of our method by instantiating it for various applications.
BibTeX
@inproceedings{sakaue2021differentiable,
  author = {Shinsaku Sakaue},
  title = {{Differentiable Greedy Algorithm for Monotone Submodular Maximization: Guarantees, Gradient Estimators, and Applications}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=JCpm_wt0AC},
}
Figure