# Discrete and Continuous Difference of Submodular Minimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 50 references that are in the map.
- First posted on arXiv 9 Jun 2025.

## Builds on (most cited first, 19 of 19)

- [Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning](https://mlsanity.com/paper/2208.11580/) (2022)
- [On the Global Linear Convergence of Frank-Wolfe Optimization Variants](https://mlsanity.com/paper/1511.05932/) (2015)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [GuidedQuant: Large Language Model Quantization via Exploiting End Loss Guidance](https://mlsanity.com/paper/2505.07004/) (2025)
- [Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains](https://mlsanity.com/paper/1606.05615/) (2016)
- [Submodular Functions: from Discrete to Continous Domains](https://mlsanity.com/paper/1511.00394/) (2015)
- [Continuous DR-submodular Maximization: Structure and Algorithms](https://mlsanity.com/paper/1711.02515/) (2017)
- [Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap](https://mlsanity.com/paper/1711.01660/) (2017)
- [Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications](https://mlsanity.com/paper/1408.2051/) (2014)
- [Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Sets](https://mlsanity.com/paper/2210.05965/) (2022)
- [Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization](https://mlsanity.com/paper/1805.09480/) (2018)
- [Near-optimal Approximate Discrete and Continuous Submodular Function Minimization](https://mlsanity.com/paper/1909.00171/) (2019)
- [Decomposition Polyhedra of Piecewise Linear Functions](https://mlsanity.com/paper/2410.04907/) (2024)
- [Fast First-Order Methods for Monotone Strongly DR-Submodular Maximization](https://mlsanity.com/paper/2111.07990/) (2021)
- [A Simple Effective Heuristic for Embedded Mixed-Integer Quadratic Programming](https://mlsanity.com/paper/1509.08416/) (2015)
- [A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns](https://mlsanity.com/paper/1606.08362/) (2016)
- [Difference of Submodular Minimization via DC Programming](https://mlsanity.com/paper/2305.11046/) (2023)
- [On Constrained Mixed-Integer DR-Submodular Minimization](https://mlsanity.com/paper/2211.07726/) (2022)

## Abstract (arXiv)

Submodular functions, defined on continuous or discrete domains, arise in numerous applications. We study the minimization of the difference of two submodular (DS) functions, over both domains, extending prior work restricted to set functions. We show that all functions on discrete domains and all smooth functions on continuous domains are DS. For discrete domains, we observe that DS minimization is equivalent to minimizing the difference of two convex (DC) functions, as in the set function case. We propose a novel variant of the DC Algorithm (DCA) and apply it to the resulting DC Program, obtaining comparable theoretical guarantees as in the set function case. The algorithm can be applied to continuous domains via discretization. Experiments demonstrate that our method outperforms baselines in integer compressive sensing and integer least squares.