Difference of Submodular Minimization via DC Programming

arXiv:2305.11046v2 Announce Type: replace
Abstract: Minimizing the difference of two submodular (DS) functions is a problem that naturally occurs in various machine learning problems. Although it is well known that a DS problem can be equivalently formulated as the minimization of the difference of two convex (DC) functions, existing algorithms do not fully exploit this connection. A classical algorithm for DC problems is called the DC algorithm (DCA). We introduce variants of DCA and its complete form (CDCA) that we …

abstract algorithms arxiv cs.dm cs.ds cs.lg difference functions machine machine learning math.oc programming stat.ml type via