# Differentiable Submodular Maximization

arXiv: https://arxiv.org/abs/1803.01785 · HTML: https://mlsanity.com/paper/1803.01785/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2018.

## Built on by (most cited first, 19 of 19)

- [DC3: A learning method for optimization with hard constraints](https://mlsanity.com/paper/2104.12225/) (2021)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [Enforcing Policy Feasibility Constraints through Differentiable Projection for Energy Optimization](https://mlsanity.com/paper/2105.08881/) (2021)
- [Leaving the Nest: Going Beyond Local Loss Functions for Predict-Then-Optimize](https://mlsanity.com/paper/2305.16830/) (2023)
- [The Perils of Learning Before Optimizing](https://mlsanity.com/paper/2106.10349/) (2021)
- [Decision-Focused Learning without Differentiable Optimization: Learning Locally Optimized Decision Losses](https://mlsanity.com/paper/2203.16067/) (2022)
- [Learning Neural Set Functions Under the Optimal Subset Oracle](https://mlsanity.com/paper/2203.01693/) (2022)
- [Assessing SATNet's Ability to Solve the Symbol Grounding Problem](https://mlsanity.com/paper/2312.11522/) (2023)
- [Diff-Explainer: Differentiable Convex Optimization for Explainable Multi-hop Inference](https://mlsanity.com/paper/2105.03417/) (2021)
- [Adversarially Robust Learning for Security-Constrained Optimal Power Flow](https://mlsanity.com/paper/2111.06961/) (2021)
- [Ensuring DNN Solution Feasibility for Optimization Problems with Convex Constraints and Its Application to DC Optimal Power Flow Problems](https://mlsanity.com/paper/2112.08091/) (2021)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)
- [Minimax Optimization: The Case of Convex-Submodular](https://mlsanity.com/paper/2111.01262/) (2021)
- [Enhancing Neural Subset Selection: Integrating Background Information into Set Representations](https://mlsanity.com/paper/2402.03139/) (2024)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Deep Generative Models with Hard Linear Equality Constraints](https://mlsanity.com/paper/2502.05416/) (2025)
- [HFS: Holistic Query-Aware Frame Selection for Efficient Video Understanding](https://mlsanity.com/paper/2512.11534/) (2025)
- [Lipschitz Multiscale Deep Equilibrium Models: A Theoretically Guaranteed and Accelerated Approach](https://mlsanity.com/paper/2602.03297/) (2026)
- [Advancing Optimal Subset Oracle via Learning Relaxation of Neural Set Functions](https://mlsanity.com/paper/2607.11555/) (2026)

## Abstract (arXiv)

We consider learning of submodular functions from data. These functions are important in machine learning and have a wide range of applications, e.g. data summarization, feature selection and active learning. Despite their combinatorial nature, submodular functions can be maximized approximately with strong theoretical guarantees in polynomial time. Typically, learning the submodular function and optimization of that function are treated separately, i.e. the function is first learned using a proxy objective and subsequently maximized. In contrast, we show how to perform learning and optimization jointly. By interpreting the output of greedy maximization algorithms as distributions over sequences of items and smoothening these distributions, we obtain a differentiable objective. In this way, we can differentiate through the maximization algorithms and optimize the model to work well with the optimization algorithm. We theoretically characterize the error made by our approach, yielding insights into the tradeoff of smoothness and accuracy. We demonstrate the effectiveness of our approach for jointly learning and optimizing on synthetic maximum cut data, and on real world applications such as product recommendation and image collection summarization.