Discrete and Continuous Difference of Submodular Minimization

George Orfanides, Tim Hoheisel, Marwa El Halabi
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:47302-47338, 2025.

Abstract

Submodular functions, defined on continuous or discrete domains, arise in numerous applications. We study the minimization of the difference of 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-orfanides25a, title = {Discrete and Continuous Difference of Submodular Minimization}, author = {Orfanides, George and Hoheisel, Tim and El Halabi, Marwa}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {47302--47338}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/orfanides25a/orfanides25a.pdf}, url = {https://proceedings.mlr.press/v267/orfanides25a.html}, abstract = {Submodular functions, defined on continuous or discrete domains, arise in numerous applications. We study the minimization of the difference of 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.} }
Endnote
%0 Conference Paper %T Discrete and Continuous Difference of Submodular Minimization %A George Orfanides %A Tim Hoheisel %A Marwa El Halabi %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-orfanides25a %I PMLR %P 47302--47338 %U https://proceedings.mlr.press/v267/orfanides25a.html %V 267 %X Submodular functions, defined on continuous or discrete domains, arise in numerous applications. We study the minimization of the difference of 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.
APA
Orfanides, G., Hoheisel, T. & El Halabi, M.. (2025). Discrete and Continuous Difference of Submodular Minimization. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:47302-47338 Available from https://proceedings.mlr.press/v267/orfanides25a.html.

Related Material