  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 apply to the DC program corresponding to DS minimization. We extend existing
convergence properties of DCA, and connect them to convergence properties on
the DS problem. Our results on DCA match the theoretical guarantees satisfied
by existing DS algorithms, while providing a more complete characterization of
convergence properties. In the case of CDCA, we obtain a stronger local
minimality guarantee. Our numerical results show that our proposed algorithms
outperform existing baselines on two applications: speech corpus selection and
feature selection.
