Discrete and Continuous Difference of Submodular Minimization
Authors: George Orfanides
Tim Hoheisel
Marwa El Halabi
Venue: ICML 2025 poster (2025)
Keywords: continuous and discrete submodular functions
Difference of submodular minimization
non-convex optimization
DC programming
DCA
Integer least squares
Integer Compressive sensing
Primary area: optimization->discrete_and_combinatorial_optimization
TL;DR: We extend results for minimizing the difference of submodular (DS) functions, from set functions to general functions over both discrete and continuous domains.

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.

Discrete and Continuous Difference of Submodular Minimization
George Orfanides
Tim Hoheisel
Marwa El Halabi
Abstract
literature focuses on set functions, which can be equivalently viewed as functions on X' {0, 13". Throughout, we make this identification and refer to them such. Submodular set functions can be minimized in polynomial time exactly up to arbitrary accuracy (Axelrod et al., 2020), and maximized approximately in polynomial time (Buchbinder et al., 2015).
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 do- mains, extending prior work restricted to set func- tions. We show that all functions on discrete do- mains and all smooth functions on continuous do- mains 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 novel variant of the DC Algorithm (DCA) and apply it to the resulting DC Program, obtaining comparable the- oretical 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 com- pressive sensing and integer least squares.
Beyond set functions, submodularity extends to general lattices like X' (Topkis, 1978). Bach (2019) extended re- sults from submodular set function minimization to general domains X. In particular, he provided two polynomial- time algorithms for submodular minimization with arbitrary accuracy on discrete domains, which are also applicable to continuous domains via discretization. Axelrod et al. (2020) later developed a faster algorithm for this problem. Bian et al. (2017b): Niazadeh al. (2020) extended results from submodular set function maximization to continuous domains, with Bian al. (2017b) giving deterministic 1 1/3-approximation, and Niazadeh et al. (2020) an optimal randomized /aaapproximation both in polynomial-tnn time.
In this paper, we extend this line of inquiry by generalizing DS set function minimization results to general domains X. However, unlike the special case where F' is submodular, Problem (1) in general cannot be solved efficiently, neither exactly approximately. Indeed, even for set functions, any constant-factor multiplicative approximation requires exponential time, and any positive polynomial-time com- putable multiplicative approximation is NP-Hard (lyer & Bilmes, 2012, Theorems 5. 5.2). Even obtaining a local minimum (Definition 4.3) is PLS complete (lyer & Bilmes, 2012, Section 5.3). Prior work (Narasimhan & Bilmes, 2005; Iyer & Bilmes, 2012: El Halabi et al., 2023) devel- oped descent algorithms for Problem (1) in the special case of set functions, which converge to local minimum of F.
1. Introduction
Many problems in machine learning require solving non- convex problem, with potentially mixed discrete and contin- uous variables. In this paper, we investigate a broad class of such problems that possess a special structure, namely the minimization of the difference of two submodular (DS) functions, over both continuous and discrete domains of the form X -IIh. Xr where each X4 S IR is compact:
min ZEX'
Hx)).
(1)
and where G and H are normalized submodular functions.
Minimizing DS set functions is equivalent to minimizing the difference of two convex (DC) functions, obtained by replacing each submodular function by its Lovász extension (Lovász, 1983). DC programs capture most well-behaved non-convex problems continuous domains. The DC algo- rithm (DCA) is a classical method to solve them (Le Thi & Pham Dinh, 2018). El Halabi et al. (2023) leverage this con- nection to minimize DS set functions by applying DCA vari- ants to the equivalent DC program. They also show that the submodular-superme
Submodularity is an important property which naturally occurs in variety of machine learning applications (Bilmes, 2022; Bach, 2013). Most of the submodular optimization
'Department of Mathematics and Statistics, McGill University, Montreal Samsung Al Lab, Montreal. Correspondence George Orfanides <gcorge.ortann ortanides @ maw..mmmiill.ca.. ca?>, Marwa Halabi <marwa.clhalable @ gomi..com>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
(SubSup) method of Narasimhan & Bilmes (2005) is special case of one of their variants.

---

Discrete and Continuous Difference of Submodular Minimization
We adopt similar approach here to solve Problem (1) for general discrete domains. We use the convex continuous extension introduced in Bach (2019) to reformulate the prob- lem as a DC program, then apply DCA variant, obtaining theoretical guarantees comparable to the set function case. As in Bach (2019), the algorithm is applicable to continuous domains via discretization. Our key contributions are:
2. Preliminaries
We introduce here our notation and relevant background. Given n E N. we let [n] [l.....,7 n) and [0 n] [0} J [n]. We use R R U {+o0} and E = ZU {+ The standard basis vectors for RR" and R=xm are denoted by ei, E [n] and Eig, i E [n]] j E [m]] respectively. The vectors of all ones and all zeros in IR" are denoted by 1 and 0 respectively. The support of a vector x E IR" is defined as supp(z) = {i 24 + #0.. For q > O. the fq-(quaaii- is given by |e]|| = (i= x// and the fo-pseudo-norm by |=>|oo = |supp [-) We conflate ||>||| with |z||oo for q 0. Given x. RR" x S y means that 2; S y; for all i [n].
We show that any function discrete domain and any smooth function on a continuous domain can be expressed as DS function, though finding a good DS decomposition can be challenging.
We highlight applications with natural DS objectives, such as quadratic programming and sparse learning.
We denote by (; and ||- the Frobenius inner prod- uct and norm respectively. We call X E Raxm row non- increasing if its rows are all non-increasing, i.e. Xig 2 X1,5+1 for all i E [m], j E [m - 1]. We denote by {o, (), [0, 11 and By
For discrete domains, we introduce an efficient DCA variant for Problem (1), which is descent method and converges to local minimum rate O(1/T)
the sets of row non- increasing matrices in (0, 1]mkm, [0, 1]mxm, and Raxm, respectively. Given a vector x E RT,, a non-increasing per- mutation p = (pi..... PPm) of satisfies pp. 2 Ip.4: for all E [m.. Similarly, a -on-incceasing permutation (p. q) ((11.9)) ...,.,)........ (Pum, (Pum:9um)) of matrix X E Rrxm satis- fies X2 X..0. 2 1p for all i E [um]. A non-increasing permutation (p. 9) of X E Raxm is called row-stable if it preserves the original order within rows when breaking ties, i.e., for any i.j E [nm] with i < J. if p; = Pj. then q < q--
We demonstrate that our method empirically outper- forms baselines on two applications: integer com- pressed sensing and integer least squares.
Additional Related Work Maehara & Murota (2015) proposed a discrete analogue of DCA for minimizing the difference of two discrete convex (discrete DC) functions G, H.H: -" - Z U {+ They also show that any func- tion F D - Z on finite D C Z" is the restriction of a discrete DC function to D, making discrete DC functions essentially equivalent to integer valued DS functions on discrete domains. However, obtaining a DS decomposition is easier, since a discrete DC function is a special case of DS functions. In Section 3.2, we provide examples of appli- cations which naturally have the form of Problem (1), but not of discrete DC program, even if we ignore the integer valued restriction. For further details, see Appendix B.2.
Throughout this paper, we consider a function F X + R detined on X II: X, the product of n compact subsets X₁ R. The set X; is typically finite set such as X = (0,..., k; 1} (discrete domain) or closed interval (continuous domain). We assume access to an evaluation oracle of F, which returns F(x) for any x E X' in time EOF. Whenever we state that F is differentiable on X, we mean that F is differentiable on an open set containing X'. We say that F is L-Lipschitz continuous on X' with respect to ||- Il. if [xx)) F(y)) I L|| - yll for all x, E X. When not specified, || || is the fg-norm.
Several works studied optimizing DR-submodular func- tions, a subclass of submodular functions which are concave along non-negative directions. For set functions, DR-submodularity is equivalent submodularity, but not for more general domains such as the integer lattice. Ene & Nguyen (2016) reduced DR- Subbuuuuu functions on a bounded integer lattice X' I[ (O...., Ky - 1}. to submodular set functions on a ground set of size (log(()). enabling the application of set-function results to this setting. Approximation algorithms with provable guarantees for maximizing continuous DR-submodular functions on contin- uous domains have also been proposed (Bian et al., 201 7a;;; Hassani et al., 2017; Mokhtari et al., 2017; Fazel & Sadeghi, 2023; Mualem & Feldman, 2023). Yu & Küçükkyvuz (2024) also gave a polynomial-time algorithm for DR- submodular minimization with mixed-integer variables over box and monotonicity constraints, with no dependence on k.
A function F' is normalized if F(z""u) = 0 where min is the smallest element in X, non-decreasing (non-increasing) if F()) < Fly) (F(z) 2 F(y)) for all x S y, and mono- tone if it is don-eecrga or non-increasing. We assume without loss of generality that F is normalized.
Submodularity
A function F is said to be submodular if
F(x) + +()) 2 ((min(xxy)) + F(max(z, v}), (2)
for all v,y E X, where the min and max applied component-wisee wise. We call F modular if Eq. (2) holds with equality, strictly submodular if the inequality is strict when- ever x and y are not comparable, and (strictly) supermodular if F is (strictly) submodular. A function F is modular iff it is separable (Topkis, 1978, Theorem 3.3).
2

---

Discrete and Continuous Difference of Submodular Minimization
An equivalent diminishing-return characterization of sub- modularity is that F is submodular iff for all E X, i E
Evaluating (1( takes Oor + r EOp) with r nk.
The value of (X) is invariant to the permutation choice.
[n].i j. dz, aj > 0 such that + a,e;, + azej E X,
We can define a bijection map θ {0. 10,1)4 (kx((-1)
[0
F(z+a,))-Fa)) F (atoo
(3)
k - 1 and its inverse as
Strict submodularity then corresponds to strict inequality in (3) (Topkis, 1978, Theorem 3.1-3.2). Other equivalent characterizations of submodularity hold for differentiable and twice-differemtiable F' (Topkis, 1978, Section 3). Proposition 2.1. Given F : X - R, where each X; is a closed interval, we have:
(X) X11,
(7a)
{ 1,
if S Zs:
θ (z) = X where X
(7b)
0, if > Ii
In the set function case, i.e., when k = 2, we have
{0, 1] (]nx(k=1) = {0, 13" and [o, 1] (b=x(( = [0, 1]", so
θ becomes the identity map, and fi reduces to the Lovász extension; see e.g. Bach (2013, Definition 3.1).
a) If F is differentiable on X, then F is submodular if all I E X. i, E [n], i i j. > O such that x + 0e, E X:
We list below some key properties of the extension. Items a-e, Item (general bound) are from Bach (2019), Item f follows directly from the definition of fu, and we prove the bound for non-decreasing F in Item g in Appendix D.
OF OF (x + aez). 0z:
(4)
dz;
b) If F is twice-differentiable on X. then F submodular for all x E x j:
Proposition 2.3. For a normalized function F : [0 k 1J" + IR and its continuous extension f4, we have;
OF
(x) 0. 0. i
(5)
dr,0z,
a) For all X E (0, (0.1)x((-1) ,,()) - F(O(X))
In both cases, F also strictly submodular if the inequali- ties are strict.
b) If F is submodular, then minge] F(z) min xe fX()..
On continuous domains, submodular functions can be con- vex, concave, or neither (Bach, 2019, Section 2.2). For n = 1, any function is modular and strictly submodulars since any x, y E R are comparable. (Strict) submodularity preserved under addition, positive scalar multiplication, and restriction (Bach, 2019, Section 2.1).
c) Given X E [0, (0.1]]x(k=1) and {u' Ti=0 as defined in Definition 2.2, let it E argmin (e(o:(k-1)m) F(y') and x = y",, then F(x) S fX).. We refer to this as rounding and denote it by x = Round (X).
d) f4 is convex iff F is submodular.
Submodular minimization Minimizing submodular set function F is equivalent to minimizing a convex continuous extension of F, called the Lovász extension (Lovász, 1983), on the hypercube [o, 1|". Bach (2019) extended this result to general submodular functions on X. To that end, he introduced a continuous extension of functions defined on X to the set of Radon probability measures on X. When X' IT= k; 1), this extension has simple, efficiently computable form (Bach, 2019, Section 4.1), given below. For simplicity, we assume all ky 's are equal to k.
e) Given X E Ry R aa non-increasing permutation
(p.4) X,, and {y' (k-1) defined as in Definition 2.2, define Y E (K-1( as Yp..q. = F(y')) - Fly² If F is submodular, then Y is subgradient of J at X.
D) IfF = G H, then S4 =4 -4- -h4.
8) F is submodular, then S4 is Lf, -Lpsschitz continu- with respect to the Frobenius norm, with Ln, S
v(k 1)m max,, i [F + e.) - -F(z)). If F is also non-decreasing, then Lj, S F((k - 1)1).
Definition 2.2. Given a normalized function F: [0 k 1]" + R, its continuous extension /1 ( - IR
defined as follows: Given X Ry (k-1) and (p. q) a non-increasing permutation of X, define y E [0: k 1]"
Bach (2019, Section 5) provided two polynomial-tine al- gorithms for minimizing submodular functions on discrete domains up arbitrary accuracy 2 0: one using projected subgradient method and the other using Frank- Wolfe (FW) method. When X = [0 k --1 1)"h both obtain an e-minimum in Ö(nkLL) /c)² EO,) time. Though FW is empirically faster; especially the pairwise FW variant of (Lacoste-Juliae & Jaggi, 2015a), which we use in our experiments (Sec- tion 5). Axelrod et al. (2020, Theorem 9) gave a faster
as 9d = and y' = -y-- + Cp, for E [(k - 1)m]. Then,
(k-1)m
f(()= = Σ
Xp (F(x²) F
(6)
1=1
For X e RR. (k-1)) we set fX() +00.
3

---

Discrete and Continuous Difference of Submodular Minimization
randomized algorithm with runtime Ö(n(kL, /e)² E0p), based on projected stochastic subgradient method.
b) If f(x²) f(x S e, then x' is an + ex-critical point of g h with ve dete, (are))(())))))))))))) (24) nh(x"))
[1 - f(x(t1) S 1672-1
DC Programming Given Euclidean space IE, let To(E) be the set of proper lower semi-continuous con-
vex functions from into R. For a set C S E, 6c the indicator function of C' taking value 0 on C
DCA is thus a descent method (up to eg) which converges (f(x²) - f(*+t)) I <) to a critical point with rate ((1/T).
and +00 outside Given a function f + R. its
We note that Item с is not specific to DCA, but instead follows from f(x²) 2
domain is defined dom f = E IE f(x) < +00).
For f E [B) 2 0, and x² dom f. the subdifferential of f at x² is defined by 0.f(29) =
3. Difference of Submodular functions
{y E E f(x)= 2 f(z") + (v, x0,--x") c, E }}, while af(x") stands for the exact subdifferential (e = 0). An element of the e-subdifferential is called an c-subgradient, or simply a subgradient when c 0.
We start by identifying which functions are expressible as DS functions, then highlight important applications where they naturally occur.
standard DC program takes the form
3.1. Representability
min f() == g(x) h(x)) =EE
(8)
The structure assumed in Problem (1) may seem arbitrary, but is in fact very general. particular, we prove that any function on a discrete domain and any smooth function on a continuous domain can be expressed as a DS function.
where g, h [E... We adopt the convention +00 (+00) +oo. The function f is called DC function.
DC-programs are generally non-convex and non- differentiable, A point x" is a global minimum of Problem (8) iff 0=h(x) S. 0.g(z) for all e 2 0 (Hiriart-Urruty, 1989, Theorem 4.4). However, checking this condition is generally infeasible (Pham Dinh & Le Thi, 1997). Instead, we are interested in notions of approximate stationarity. In particular, we say that a point x is an e-critical point of g - h if (z) n 0h(z) * O. Criticality depends on the choice of the DC decomposition - h of f (Le Thi & Pham Dinh, 2018, Section 1.1) and implies local minimality over restricted set (El Halabi et al.. 2023, Proposition 2.7).
Proposition 3.1. Given any normalized F X - R where each X, C R. is finite, there exists a decomposition F G where G, H X + R are normalized (strictly) submodular functions. functioon
Proof Sketch. We give a constructive proof, similar to the one in (Iyer & Bilmes, 2012, Lemma 3.1) for set functions. We choose normalized strictly submodular function H X' + R. then define G = F + |el H and И = |e| H. where a S and between the left and right hand sides of Ineq. (3) for F and fl respectively. We verify that G and H are normalized and submodular, using Ineq. (3). Choosing & < 0 as strict lower bound further guarantees strict submodularity. The full proof is given in Appendix E.
3
are lower bounds on the difference
Proposition 2.4. Les 0 and f 9- To(E). If x E E satisfy 0eg(x) n ah(x') + 0, then f(x) < [(x))e +
--K h with h E
DCA iteratively minimizes a convex majorant of (8), ob- tained by replacing at iteration & by its affine minorization h(x") + (v', x²), with y ah(x*). Starting from I² E dom 0g, DCA iterates are given by
Obtaining tight lower bounds a and / in the above proof requires exponential time in general, even for set functions (Iyer & Bilmes, 2012). We provide Example 3.2 valid choice for ii, for which a tight can be easily computed. For any F, we can use a -4 max [F(x)), which is often easy to lower bound. Though loose bounds a and 3 result in slower optimization, as explained in Appendix A.
y' ah(z')
(9a)
1+1 E argmin g(x) - (29,, x)). *ER
(9b)
Example 3.2. Let H R - R.. be the quadratic function ((x) = - 1, Jx, where J is the matrix of all ones, and define A X - R as Hxx) (z) Hinmin) Then, H is normalized strictly submodular function.
We list now some properties of DCA (Pham Dinh & Le Thi, 1997, Theorem 3), (El Halabi et al., 2023, Theorem 3.1).
Proposition 2.5. Given f g h with h (I) and a finite minimum f", let e, 2 O, and (x²), {v') be generated by DCA (9), where subproblem (9b) is solved up to accuracy cg. Then for all T E 14, we have:
Proof Sketch. By Proposition 2.1-b, H is strictly submodu- lar on any product of closed intervals. Since strict submodu- larity is preserved by restriction, H is also strictly submod- ular on X. The full proof is given in Appendix E.
a) f(x(+1) S $(xx)) 6x.

---

Discrete and Continuous Difference of Submodular Minimization
In the above example, we have (x + a4e)) (x)) (a age; + azfz) Ha + azez)= a;d; for any æ E X' K,, 0 > 0. When X' is discrete, we obtain tight lower bound B = d,d, where d,d, are the distances between the closest two points in Ri, X2 respectively, for some j + i.
ered in Maehara & Murota (2015) are essentially equivalent to integer valued DS functions on discrete domains.
3.2. Applications
As discussed in Section 3.1, Problem (1) covers most well behaved non-convex problems over discrete and continuous domains. Though finding good DS decomposition can be expensive in general. We give here examples of applications which naturally have the form of Problem (1).
The decomposition given in the proof of Proposition 3.1 can- not be applied to continuous domains. Indeed, if H is con- tinuous function, taking a; + or aj - 0 in inequality (3) yields 3 = 0. However, similar decomposition can be ob- tained in this case, if F satisfies some smoothness condition.
Proposition 3.3. Given any normalized F: X + R where each X; is closed interval, if F is differentiable and there exist LF 20 0 such that aF
Quadratic Programming Quadratic programs (QP) of the form milggex 2/0 Qr x; arise in numerous appli- cations. This form includes box constrained QP (BCQP), where X,'s are all closed intervals, as well as integer and mixed-integer BCQP, where some all X₂ S Z". Such problems are NP-Hard if the objective is non-convex (De An- gelis et al., 1997), or if some of the variables are discrete (Dinur et al., 1998).
8z. (x)
8F (x + aeş) 2 - Laa, dz,
for all x E x j.a > 0, x, + X,, then there exists a decomposition F G - H, where G,H: normalized (strictly) submodular functions.
H. : X + IR are
Proof Sketch. The proof is similar to that of Proposition 3.1.
We choose a normalized strictly submodular function H :
The objective in these QPs has a natural DS decompo- sition F = G- H. with G(x) = x Q== x + c and Hxx) x (-Q+)a, where Q mi, and Q+ max Q 0}. By Proposition 2.1-b, G' and H are submod- ular, since e x is modular. When X' is continuous, these QPs can also be written as DC programs, but this requires computing the minimum eigenvalue of Q
X' + R, which is differentiable and satisfies 8z: (x) att 0u. (Ir + aez) 2 Lg for some La > O, then define G F+ L and H === L Ly H. are normalized and submodular, using Proposition 2. Choosing LP >0 0 as strict lower bound further guarantees strict submodularity. The full proof is in Appendix E.
ad
We verify that G and
Sparse Learning Optimization problems of the form min {(x) + >||x=11%- where q E [0, 1), > 2 O, and is a smooth function, arise in sparse learning, where the goal is to learn sparse parameter vector from data. There, the loss i is often smooth and convex (c.g., square logistic loss), and the non-convex regularizer || promotes sparsity. The domain is often unbounded so X' can be set to ||=/||>> < R for some R 2 O, or X' C -" as in the integer compressed sensing problems we consider in Section 5.2. Using g < 1 makes the problem NP-Hard, even for continuous (Chen et al., 2017), but can be preferable to the convex (i-nomm, as it leads to fewer biasing artifacts (Fan & Li, 2001).
One sufficient condition for F to satisfy the assumption in Proposition 3.3 is for its gradient to be Lp-Lipschitz continuous with respect to the nnnorm, i.c., [[v - [F()) S Ly I| - vlli for all Lr y E X. It follows then that any twice continuously differentiable function on X is also DS function, with L,p = maxzex || || ((+))l)
(Beck, 2017, Theorem 5.12). In both cases, computing right Lipschitz constant LF has exponential complexity in general (Huang et al., 2023, Theorem 2.2). Though often one can casily derive a bound on Ly. The function in Exam- ple 3.2 is again a valid choice for HI where L = is tight.
Like DC functions, DS functions admit infinitely many DS decompositions. For the specific decompositions in Proposi- tions 3.1 and 3.3, the "best" one is arguably the one with the tightest a, 3 and LF. Lg. respectively. Finding the "best" DS decomposition in general is even more challenging, as it is unclear how to define "best". This question is explored for set functions in Brandenburg et al. (2024), who study the complexity of decomposing set function into a dif- ference of submodular set functions such that their Lovász extensions have as few pieces as possible.
Note that the regularizer ||=||, is modular since it is separable. Hence, these problems are instances of Problem (I), where a DS decomposition of é can be obtained as in Proposition 3.3. If E(x) = ||Ar bll we can use the same decomposition as in the QPs above, i.c. G(x) = x: T === x + x > |2 and H(x) x TT (-Q+) with Q = A A and e = -2A These problems cannot be written as DC programs even when X' is continuous, since || is not DC, as we prove in Proposition B.
We show in Appendix B.2 that the natural DS decomposition in both applications is not a discrete DC decomposition as defined in Maehara & Murota (2015) and cannot easily be adapted into one for general discrete domains, even when ignoring the integer-valued restriction.
In Appendix B, we discuss the connection between DS func- tions and related non-convex function classes. In particular, we note that DS functions on continuous domains are not necessarily DC, and that the discrete DC functions consid-
5

---

Discrete and Continuous Difference of Submodular Minimization
4. Difference of Submodular Minimization
Again by Proposition 4.1, if F is DS then F' is also DS. Moreover, given any minimizer x² of F', x² /(k 1) is i-minimizer of F. It is worth noting that Lipschitz continuity is not necessary for bounding the discretization error. We show in Appendix F.2 how to handle the function F(x) = ||= with q E [0, 1), on a domain where is not Lipschitz continuous.
In this section, we show that most well behaved instances of problem (I) can be reduced DS minimization over a bounded integer lattice IT= [0 K - I] for some k; N. Then, we address solving this special case.
4.1. Reduction to Integer Lattice Domain
We first obverse that submodularity is preserved by any separable monotone reparametrization. A special case of the following proposition is stated in Bach (2019, Section 2.1) with X' = X' and m strictly increasing.
4.2. Optimization over Integer Lattice
We now address solving Problem (1) for X = IT==,0
A; - 1]. For simplicity, we assume K; = k for all E [n]. for some
E N, i..., X [0 : k - 1] The re- sults can be easily extended to unequal k's. Since Prob- lem (1) is inapproximable, we will focus on obtaining ap- proximate local minimizers. Given x E X, we define the set of neighboring points of x in X' as Nx(x) == {a' E X 3i E [n)] x' = x + e.
Proposition 4.1. Given X' = IT= X,, II, X, with compact sets X. C IR, let F X' + R and m : X" - X be a monotone function such that [m([r]] my (x:). If F is submodular, then the function F" : X + R given by (z)))= = (x)( is submodular. Moreover, if m is strictly monotone, then submodular iff F' is submodular.
Definition 4.3. Given c 2 and x E X, we call x an c-local minimum of if F(x) S (x²) + e for all x' E (N)x)..
Proof Sketch. We observe that min(m(2), m(y)) max (mxx),, m(y) = mfmin y}) + mmmax {2, v))-
If X = {0, 1)", we recover the definition of a local mini- mum of set function.
The claim then follows by verifying that Eq. (2) holds. The full proof is given in Appendix F.1
A natural approach to solve Problem (1) is to reduce it to DS set function minimization, using the same reduction as in submodular minimization (Bach, 2019, Section 4.4), and then apply the algorithms of Narasimhan & Bilmes (2005); Iyer & Bilmes (2012); El Halabi et al. (2023). However, this strategy more expensive than solving the problem directly, even when F is submodular. We discuss this in Appendix C.
Discrete case For discrete domains, the desired reduction follows from Proposition 4. by noting that in this case ele- ments in X' can be uniquely mapped to elements in IT==100= [0: k 1] with K2- = |[&] via strictly increasing map.
Corollary 4.2. Minimizing any DS DS function F X + R. where each X, R is finite set, is equivalent to minimiz- ing a DS function on IT= (0: : k 1] with K;- = (x
Continuous relaxation We adopt a more direct approach to solve Problem (1), which generalizes the approach of El Halabi et al. (2023) for set functions. In particular, we relax the DS problem to an equivalent DC program, using the continuous extension (Definition 2.2) introduced in Bach (2019), then apply a variant of DCA to it.
Proof. For each E [n]. let X; = f -1) where elements are ordered in non-decreasing order, i.c.,
=) < #1 for all j E [0 k; - 2). Define the map m, [0: : k 1] + X; m²(j) =.. Then m, is a strictly increasing bijection. By Proposition 4.1, then the function F" 1T==100 00 K2 1] + R defined as F((x)= = F(m(z))
Recall that minimizing submodular function F is equiv- alent minimizing its continuous extension fi (Proposi- tion 2.3-b). We now observe that this equivalence continues to hold even when F is not submodular.
with [m[ = m. is DS function.
Continuous case We can convert continuous domains into discrete ones using discretization. We consider X' = [0, 1] wlog, since by Proposition+4 4.1 any DS function F defined on IT= (a., by] can be reduced to DS function F' on [0. 1]m by translating and scaling.
Proposition 444. For any normalized function F 10: k 11mh + R. we have
min F(x)= min =1(0:k=11-
xe 13 f(().
(10)
As done in Bach (2019, Section 5.1), given a function F [0, 1|" - R which is T.-Lipschitz continuous with respect to the lo and > 0, we define l [L/e] + and the
Moreover, if x is a minimizer of F then (x²) a minimizer of fu. and if X* is a minimizer of Ss then Roundy(X* is a minimizer of F.
function F": : [0: k- 11nd + R as F'(x)= = F(x 1)).
Then we have
Recall that θ is the bijection between {0, 1) (k-x and [0 : k - 1] defined in (7). The proof follows from the two properties of f; in Proposition 2.3-a,c, and is given in
min F(x))cc/25 min F(x) < min
F((x).
=
zE|0:k11"
6

---

Discrete and Continuous Difference of Submodular Minimization
Appendix F.3. By Proposition 2.3-f, Problem (1) is then equivalent to
single subgradient Y using local search step (lines 3- approximate local minimum of F without restarts. The algorithm maintains feasible solution x' to Problem (1) by rounding X or applying the map θ if X is integral. Rounding can optionally be applied in the latter case as well. Finding a common permutation on line 4 is always possible. Indeed, the binary matrix θ -='(z") differs from X at only one element: (i, + 1) if x' x² + e and (i, - 1) if ø' = of - EG. Thus, we can choose any row-stable non-increasing permutation (p: q) of X such that (pa+1, 0d411 = (1, 2f + 1) if क' = x² + e; and (pd-1 Qd-1) = (i, - 1) if x'
5), ensuring direct convergence
min Xe f((X) - (1)))-11)))) - (x)),
(11)
where IL, hy E (To(Ra((-1))) by Proposition 2.3-d.g, since G, H are submodular.
Algorithm 1 DCA with local search
1: e 2 0, T N. I E X, X = (x))
2: for l,. do
3: E' d'Eargunn &aaggin
F(x)
x² - -e,, where = | 11o-
4: Choose a common non-increasing permutation (p.9)
Computational complexity The cost of finding the best neighboring point o' is 2n EOp. Finding a valid permutation (p,q) on line 4 as discussed above costs ((n)). The corresponding subgradient Y can then be computed as described in Proposition 2.3-e in Onnk EOH). The subproblem on line is a convex problem which can be solved using projected subgradient method or FW methods. Furthermore, like the set function case, this subproblem is equivalent to a submodular minimization problem. Indeed, we show in Proposition F.4 that the term (Y', X)r corresponds to the continuous extension of the normalized modular function Hx) = Σ Ei=1 Ej=1
of X and 0z*(x") (preferably row-stable)
5: Choose Y (X*) corresponding to (p, ()
6: X E argmin x=|o.11xx(*>> 9x(X) (Y', X)F
if x E (0, 1)1 (xx)) then
7:
8:
x' = 0(8+11, X = X
9:
else
10:
x1+1_ = Round Founds(X(()))) (X(+1), X = (x+t))
11:
end if
12: if F(x")- - F(x(t1) Se then
13: Stop.
we Y Hence,
14: end if
by Proposition 2.3-b,f, the subproblem is equivalent to minimizing the submodular function F = G-GBB -GH'. We can thus obtain an integral Eg eg-solution X++1 E {0, 13 1)
15: end for
for any f 2 0, in (n /c)2 EOr:) time using the algorithm of Axelrod et al. (2020). Rounding can be skipped in this case, and X can be directly mapped to x1+1 via θ in O(nk). So the total cost per iteration of DCA-LS is ((n(kL /e))² EO r + nk BOH).
Algorithm Problem (11) is a DC program on E [=x((-1)) 1), with f = ft + 6 (o.1p((--))
g h, where 9 = 91 + +0 (0.Ip=<> and h hi. Applying the standard DCA (9) to it gives descent method (up <x) which con- verges critical point X of g- h by Proposition 2.5. A feasible solution x to Problem (1) can then be obtained by rounding, i.e., x= = Roundx(X")) E [0: k - 1|" which satisfies F(xT) & fXT)), as shown in Proposition 2.3-c.
The choice of DS decomposition for F' affects the runtime of DCA-LS. For instance, looser bounds a and , in the generic decomposition from Proposition 3. lead to a larger Lips- chitz constant LJ₃ and thus longer runtime (Appendix A),
However, even in the set functions case, xT. is not neces- sarily an approximate local minimum of F, as shown by El Halabi et al. (2023, Example F.1). To address this, the authors proposed two variants of standard DCA that do obtain an approximate local minimum of F. One variant, which generalizes the SubSup method of Narasimhan & Bilmes (2005), is too expensive, as it requires trying (n) subgradients per iteration. While the other variant checks at convergence if the rounded solution an approximate local minimum, and if not restarts DCA from the best neigh- boring point. Both can be generalized to our setting. We provide an extension of the second, more efficient, variant and its theoretical guarantees in Appendix I.
Theoretical guarantees Let F* be the minimum of Problem (1), Note that the minimum f = F of the DC program (11) is finite, and that (Y*), (X*+1) are standard DCA iterates. Proposition 2.5-a,b then apply to them. The following theorem relates DCA properties on Problem (11) to ones on Problem (1), showing that DCA-LS is a descent method (up to Eg) which converges to an (E + -ooal minimum of F in (11/c) iterations.
Theorem 4.5. Let (x*) be generated by Algorithm 1, where the subproblem on line 6 is solved up to accuracy e, 2 0. For all t [T], 2 we have:
We introduce a new efficient variant of DCA, DCA with local search (DCA-LS), in Algorithm 1, which selects a
a) F(zlt1) S F(x*) Ex.
7

---

Discrete and Continuous Difference of Submodular Minimization
( 1m be the vectors corresponding to the per- b) Let {yf 1i=0 mutation (p. 9) from line 4, defined as in Definition 2.2. If (p,9) 9) is stabltable and F(x') 1) S c, then
that modifying any coordinate i E [x]] to its previous or next value on the grid X; does not reduce F by more than + Eg. In the continuous case, assuming again X' = [0, 1 recall that F'(x)) = F(z/(k- 1)), where k = [L/ee] + for some é' > 0, and T. is the Lipschitz constant of F with respect to the 60 -norm. Let ह' = z' z²/(k- - 1). Then the local minimality guarantee on F* implies that:
F(x)) Fly') + ex for all E [0: (k - 1)m]-
c) Algorithm converges to an (e + -local minimum of F after at most (F(x²) - F iterations.
F( S F((" + +
Proof Sketch. Item a follows from Proposition 2.5-a and Proposition 2.3-a,c. Item follows from Proposition 2.5-b and Proposition 2.4, by observing that if (p. q) sta-eta then it is a common non-increasing permutation for X and | 1/__1) and thus Y is a common subgradient of h at all these points. The choice of (p, q) on line 4 also ensures the same holds for (="( even when (p: q) is not row-stable, Item then obtained by telescoping sums. The full proof is given in Appendix F.5.
This is only meaningful if > é c Eg. since the Lipschitz continuity of F already ensures F( F( + c L/(k - sé''.
k- S
{e-
5. Experiments
We evaluate our proposed method, DCA-LS (Algorithm 1), on two applications: integer least squares and integer compressive sensing, where X' C 2". We compare it with state-of-the-art baselines. We use Pairwise-FVy (Lacoste-Julien & Jaggi, 2015b) to solve the submodular minimization subproblem line 6. Results averaged over 100 runs shown in Figure 1, with error bars for standard deviations. Experimental setups for each application are de- scribed below, with additional details given in Appendix G. The code is available at https: / //g/ thub. com/ SamsungSA I.Mnnt
Restricting (p, q) to be row-stable is necessary ensure that it is also a non-increasing permutation of [0-1(y/ (r/") 1 which is needed for Item to hold, but not for Items a and c, as discussed in the proof sketch. In the set function case (k= 2), this restriction is unnecessary, since any non-increasing permutation of X E RT (n is trivially rtw-stable. DCA-LS can be modified to return a solution with stronger local minimality guarantee, where F(x")) F(x) + e + 6z for all x E X such that || x²1) 111 S c, for some N, by setting x² E | Se F(X). This
(k-1))
/ reaa f fsubmin.
5.1. Integer Least Squares
We consider the problem of recovering an integer- valued vector x² E X' from noisy linear measurements = Az + E, where A E Rmxx is a given mcasurement matrix with m 2 n, and & E R is a Gaussian noise vector & ~ NN I'I)). One approach for recovering integer least squares (ILS) problem
increases the cost of computing z' to EOp).
Theorem 4.5 generalizes the theoretical guarantees of El Ha- labi et al. (2023) to general discrete domains; recovering the same guarantees in the set function case. In Appendix I, we compare DCA-LS to an extension of the more efficient DCA variant from El Halabi et al. (2023), theoretically and empir- ically. We show that both variants have similar theoretical guarantees and computational complexity. In practice, how- ever, DCA-LS performs better in some settings, sometimes by large margin, but is often slower than DCA-Restart.
of is to solve minzex F(z) = ||Ar bl... This is an integer BCQP with Q = ATA and c = -2A b. Thus, we use the DS decom- position given in Section 3.2. IIS problems arise in many applications, including wireless communications (Damen et al., 2003), image processing (Blasinski et al., 2012), and neural network quantization (Frantar & Alistarh, 2022).
Other variants (with regularization, acceleration, complete DCA) explored in El Halabi et al. (2023) are also applica- ble here. When regularization is used, rounding becomes necessary, as explained in Section therein.
We sample æ² uniformly from X {-1, 2, 33" with n = 100, draw the entries of A i.i.d from (N, 1), and vary m from n to 2n. The noise variance 0² is set to achieve a target signal-to-noise ratio (SNRas) of 20 dB. We include as baselines ADMM (Takapoui et al., 2020), Optimal Brain Quantizer (OBQ) (Frantar & Alistarh, 2022), and the relax- and-round (RAR) heuristic which solves the relaxed prob- lem on 31, then rounds the solution to the nearest point in X. DCA-LS and ADMM are initialized with the RAR so- lution, and OBQ with the relaxed solution. We obtain an op- timal solution x= using Gurobi (Gurobi Optimization, LLC, 2024) by rewriting the problem as a binary QP. We report in Figure (top) three evaluation metries; recovery probability
Implications for non-integer domains When X' is gen- eral discrete or continuous domain, we can apply DCA-LS to the function F' obtained via the reductions discussed in Section 4.1. Theorem 4.5 then hold for F'.
In the discrete case, recall that Fx(x) = F(m(z)), where m is the map defined in the proof of Corollary 4.2. The guarantee that x' is an (e+ez) minimum of F" implies that m(x²) is an (c + -locll minimum of F, in the sense
8

---

Discrete and Continuous Difference of Submodular Minimization
0.1
Racoveyy Probadiliey
0.8
0.08
0.8
F8 Flo
Bit Frror Rate
0.6
0.06
0.0
0.68
ouod
0.4
H ADMM RAR
0.24
2 DCA-L5 Optinal
04
1.6
1.8
11/ /
m /
1.22
-8- DCA-LS
DCA-LS-LASSO
Cr
Recovery Probabiliy
Eatination Bieor
Support Erver
0.6
15
0.6
0.4
10-
0.4
0.2
5-
0.2
0.2
0.4
0.5
0.5
0.2
0.4
0.6
0.3
0.2
0.4
0.6
0.8
Figure 1: Performance results, averaged over 100 runs, for the integer least squares with SNRaB 20 dB, n 100 (top)
and for integer compressed sensing with SNR.n dB, n 256 and 26 [0.1n] (bottom).
(ratio of exactly recovered signals over number of runs), bit error rate BER ( ||e =²1lo/n, /n, and relative objective gap with respect to x². We also compared with Babai's nearest plane algorithm (Babai, 1986, 2nd procedure), but excluded here as it had worse objective gap and BER than all baselines, and similar recovery probability to ADMM.
entries i.i.d uniformly from {-1, 1]. The noise variance o² is to achieve SNRa of 8 dB. We consider as baselines orthogonal matching pursuit (OMP) (Pati et al., 1993) and variant of LASSO (Tibshirani, 1996) with the additional box constraint x E [j", solved using FISTA (Beck & Teboulle, 2009). Since both methods return solutions out- side of X, we round the solutions to the nearest vector X' As a non-convex method, the performance of DCA-LS is highly dependent on its initialization. We thus consider two different intialization, one with x = 0 (DCA-LS) and one with the solution from the box LASSO variant (DCA-LS- LASSO). We evaluate methods on three metrics; recovery probability, support error Supp(&))Auppl Asupp())=*)) and estima- tion error || x 12/2/ ||2/||==*112 where A is the symmetric difference. Figure (bottom) reports the best values, À is varied from 1 to 10-5 5 in DCA-LS and FISTA, and the sparsity of the OMP solution is varied from to [1.5s].
We observe that DCA-LS outperforms baselines on all met- rics, and performs on par with the optimal solution starting from m/n = 1.2. OBQ matches the performance of DCA- LS from m/n = 1.5, while ADMM and RAR are both considerably worse across all metrics. In Appendix H.1, we include results using larger n = 400, as well as another setup where we fix m = n and vary the SNR Gurobi cannot be used for n 400 as is too slow. DCA-LS out- performs other baselines on all metrics in these settings too.
5.2. Integer Compressed Sensing
DCA-LS and DCA-LS-LASSO significantly outperform baselines in recovery probability. While DCA-LSS outper- forms OMP in all metrics, it performs worse than LASSO in estimation and support errors for m/n < 0.6, but overtakes it after. DCA-LS-LASSO outperforms baselines on all met- rics, except for m/n (0.25, 0.4), where slightly lags be- hind LASSO in estimation and support errors. These corre- spond to cases where I² a x=. Indeed, recall that DCA-LS is descent method (up to <) so DCA-L.--LASS) is guaran- teed to obtain an objective value at least as good as LASSO. In Appendix H.3, we include results for 8 = 13 [0.05n] and for another setup where we fix m/n n 0.5 and vary the SNR We observe similar trends in these settings too.
We consider an integer compressed sensing problem, where the goal is to recover an s-sparse integer vector x² from noisy linear measurements with problem arises in applications like wireless communications, collaborative filtering, and error correcting codes (Fukshan- sky et al., 2019). The signal can be recovered by solving mingex F Fxx)= = ||rr - bll2 + A||=||e llo with À > 0. This is special case of the sparse learning problem in Section 3.2, with y 0. We use the same DS decomposition therein.
and < This
We set X = {-1, 0, 1)".
256, 26 |0.1nn]. and draw A i.i from (0, 1/m), with m varied from 26 to n. We choose a random support for " then sample its non-zero

---

Discrete and Continuous Difference of Submodular Minimization
Acknowledgements
Bilmes, J. Submodularity in machine learning and arti- ficial intelligence. arXiv preprint arXiv: 2202.00132, 2022. URL https: https://axxvv.ort haag//bb//aa 2202. 00132v2.
We thank Xiao-Wen Chang for helpful discussions. George Orfanides was partially supported by NSERC CREATE INTER-MATH-Al and Fonds de recherche du Québec Doctoral Research Scholarship B2X-326710.
Blasinski, H., Bulan, O., and Sharma, G. Per-colorant- channel color barcodes for mobile applications: An inter- ference cancellation framework. IEEE Transactions Image Processing. 22(4):1498-1555 2012
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Brandenburg, M.-C., Grillo, M., and Hertrich, C. Decom- position polyhedra of piecewise linear functions. arXiv 2024.
preprint
Buchbinder, N., Feldman, M., Seffi, J., and Schwartz, R. tight linear time (1/2)-aproximmaton for unconstrained submodular maximization. SIAM Journal on Computing, 44(():1384-14) 1402, 2015.
References
Axelrod, B., Liu, Y. P., and Sidford, A. Near-optimal ap- proximate discrete and continuous submodular function minimization. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 837- 853. SIAM, 2020.
Chen, Y., Ge, D., Wang, M., Wang. Z., Ye, Y., and Yin, H. Strong np-hardness for sparse optimization with con- cave penalty functions. In International Conference on Machine Learning, pp. 740-747. PMLR, 2017.
Babai, L. On lovász' lattice reduction and the nearest lattice point problem. Combinatorica, 6: 1-13, 1986.
Damen, M. O., El Gamal, H., and Caire, G. On maximum- likelihood detection and the search for the closest lattice point. IEEE Transactions on information theory, 49(10); 2389 2402, 2003.
Bach, F. Learning with submodular functions: convex optimization perspective. Foundations and Trends@ in Machine Learning, 6(2-3):145-377) 2013.
Bach, F. Submodular functions: from discrete continu- ous domains. Mathematical Programming, 175:419-459, 2019.
De Angelis, P. L.,, Pardalos, P. M., and Toraldo, G. Quadratic programming with box constraints. Developments in global optimization, pp. 73-93, 1997.
Beck, A. First-order methods in oplimization. SIAM, 2017.
de Oliveira, W. The abc of de programming. Set- Valued and Variational Analysis, 28:679-706, 2020.
Beck, A. and Guttmann-Bett N. Fom-a matlab toolbox of first-order methods for solving convex optimization problems. Optimization Methods and Software, 34(1): 172-193, 2019.
Dinur, I,, Kindler, G., and Safra, S. Approximating to within almost-polynomias factors is np-hard. In Proceed- ings 39th Annual Symposium on Foundations of Com- puter Science (Cat. No. 98CB36280), pp. 99-109. IEEE, 1998.
Beck, A. and Teboulle, M. A fast iterative shrinkage- thresholding algorithm for linear inverse problems. SIAM journal imaging sciences, 2(1): 2009.
El Halabi, M., Orfanides, G., and Hoheisel, T. Dif- ference of submodular minimization via DC program- ming. In Krause, A., Brunskill, E., Cho, K., En- gelhardt, B., Sabato, S., and Scarlett, J. (eds.), Pro- ceedings of the 40th International Conference on Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 9172-9201. PMLR, 23-29 Jul 2023.
Becker, S. Cosamp and omp for sparse re- covery. URL
co:00--cosamp-aaaa -owpaaam--add-a-a---a------ -o--p-p------------------------- Retrieved 2025-01-30.
Bian, A., Levy, K., Krause, A., and Buhmann, J. M. Con- tinuous dr-submodular maximization: Structure and algo- rithms. In Advances in Neural Information Processing Systems, pp. 486-496.6 496, 2017a.
mlr press/ html.
Ene, and Nguyen, H. reduction for optimizing lattice submodular functions with diminishing returns. arXiv preprint arXiv:1606.08366 2016.
Bian, A. A., Mirzasoleiman, B., Buhmann, J., and Krause, A. Guaranteed non-convex optimization: Submodular maximization over continuous domains. In Artificial Intelligence and Statisties, pp. 111-120. PMLR, 2017b.
Fan, J. and Li, R. Variable selection via nonconcave pe- nalized likelihood and its oracle properties. Journal of
10

---

Discrete and Continuous Difference of Submodular Minimization
the American statistical Association, 96(456):1348-366) 2001.
Le Thi, H. A. and Pham Dinh, T. De programming and dea: thirty years of developments. Mathematical Program- ming, 169(1):5-68, 2018.
Fazel, M. and Sadeghi, O. Fast first-order methods for mono- tone strongly dr-submodular maximization. In SIAM Conference on Applied and Computational Discrete Al- gorithms (ACDA23), pp. 169-179. SIAM, 2023.
Lovász, L. Submodular functions and convexity. In Mathe- matical Programming The State of the Art, pp. 235-257. Springer, 1983.
Frantar, E. and Alistarh, D. Optimal brain compression: A framework for accurate post-training quantization and pruning. Advances in Neural Information Processing Systems, 1514475-4488. 2022.
Machara, T. and Murota, K. A framework of discrete de programming by discrete convex analysis. Mathematical Programming, 152(():433 466446666,,6666 2015.
Mokhtari, A., Hassani, H., and Karbasi, A. Conditional gradient method for stochastic submodular maximization: Closing the gap. arXiv preprint arXiv:1711.0160 2017.
Fukshansky, L., Needell, D., and Sudakov, B. An algebraic perspective on integer sparse recovery. Applied Mathe- matics and Compulation, 340:31 14.31,2,,22 2019.
Mordukhovich, B. and Nam, N. M. An easy path to convex analysis and applications. Springer Nature, 2023.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL wttppp::///eet gurobi. com.
Mualem, L. and Feldman, M. Resolving the approxima- bility of offline and online non-monotone dr-submodular maximization over general convex sets. In Ruiz, F., Dy, J., and van de Meent, J.-W. (eds.), Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pp. 2542-2564. PMLR, 25-27 Apr 2023. http:: /tap:p::/pprooeeee /ttpppppcceng...cp// mlr. prisss/ v206 met.mmmalleee em2.3a html.
Hassani, H., Soltanolkotabi, M., and Karbasi, A. Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, pp. 5843-5853, 2017.
Hiriart-Urrute J.-B. From convex optimization to noncon- vex optimization. necessary and sufficient conditions for global optimality. In Nonsmooth optimizution and related topics, pp. 219-239. Springer, 1989.
Murota, K. Discrete convex analysis. Mathematical Pro- gramming, 83:313-377 1998.
Huang, J. W., Roberts, S. J., and Calliess, J.PP. On the sam- ple complexity of lipschitz constant estimation. Transac- fions on Machine Learning Research, 2023.
Murota, K. and Shioura, A. Relationship of m-/l-convex functions with discrete convex functions by miller and tavati-tardella. Discrete Applied Mathematics, 115(1-3): 151-176, 2001.
Iyer, R. and Bilmes, Algorithms for approximate min- imization of the difference between submodular func- tions, with applications. In Proceedings of the Twenty- Eighth Conference on Uncertainty in Artificial Intelli- gence, UAI'12, pp. 407-417, Arlington, Virginia, United States, 2012. AUAI Press. ISBN 978-0-9749039-8 9. URL http: //ll. acm. wrt/citationnnncoo////./////.ttt efm? id=3020652.3020655
Narasimhan, M. and Bilmes, J. A. A submodular- supermodular procedure with applications to discrimina- tive structure learning. In UAI '05, Proceedings of the 2 Conference in Uncertainty in Artificial Intelligence, Edinburgh, Scotland, July 26-29, 2005, pp. 404-412. AUAI Press, 2005, URL https / /ttpppttpptttt//eeeeeeeeeetteest org/ het//dlsppaysttticleeeeeaal....a jet.araaaaalsssppmpmmmmmammmmm htt.:/2arrrrceee.eoe1442eeeoooec 21.
Kim, J., Halabi, M. E., Park, W., Schaefer, C., Lee, D., Park, Y., Lee, J. W., and Song, H. O. Guidedquant: Large language model quantization via exploiting end loss guidance. In Proceedings of the 41th International Conference on Machine Learning, 2025.
Niazadeh, R., Roughgarden, T., and Wang, J. R. Optimal algorithms for continuous non-monotone submodular and dr- dr-submodular maximization. The Journal of Machine Learning Research, 21(1):49774497,, 2020.
Lacoste-Julien, and Jaggi, M. On the global linear conver- gence of wolfe optimization variants. In Advances in Neural Information Processing Systems, pp. 496-504, 2015a.
Pati, Y. C., Rezaiifar, R., and Krishnaprasad, P. S. Orthogo- nal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceed- ings of 27th Asilomar conference on signals, systems and computers, pp. 40-44. IEEE, 1993.
Jacoste-Julien. S. and Jaggi, M. On the global linear con- vergence of frank-wolfe optimization variants. Advances in neural information processing systems, 28, 2015b.

---

Discrete and Continuous Difference of Submodular Minimization
Pham Dinh, T. and Le Thi, H. A. Convex analysis approach to dc programming: theory, algorithms and applications. Acta mathematica vietnamica, 22(1):289-355 1997.
Takapoui, R., Moehle, N., Boyd, S., and Bemporad, A. A
simple effective heuristic for embedded mixed-integer quadratic programming. International journal of control, 93(1):2-12, 2020.
Tibshirani, R. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B: Statistical Methodology, 58(1):267-288, 1996.
Topkis, D. M. Minimizing a submodular function on a
lattice. Operutions research, 26(2):305-321, 1978.
Yu, Q. and Küęükyavuz, S. On constrained mixed-integer dr-submodular minimization. Mathematics of Operations Research, 2024.
12

---

Discrete and Continuous Difference of Submodular Minimization
A. Effect of looser and B bounds on performance
In this section, we discuss how the bounds a and in the generic decomposition given in Proposition 3.1 affect the runtime of Algorithm
As discussed in Section 4.2, the runtime of Algorithm particularly for solving the submodular minimization subproblem at each iteration i, depends on the Lipschitz constant Ly; of fi- Recall that f is the continuous extension of F = G H',
where H is the modular function whose continuous extension is (Y",))e X)F. The decomposition in Proposition 3.1 defines G = F + o H and H 3
H, for some normalized strietly submodular function H. Let Y y we can thus write
= fx() + (h2(()) -
Looser bounds a and 3 result in a larger Lipschitz constant stp and thus a longer runtime. To show that, we provide upper and lower bounds on b. which grow with lgl. For any X, X" E TRIx((-)) we have
1 - 1((') s ( + - (x*) EI X x'
$ (L1, + 2 - X'IIF
Hence, 1,g S 1. + +2 lng. Note that I, and Lng are independent of and (3. This upper bound indeed grows with lei 3
Since Y (X*), we know from Proposition 7-b Bach (2019) that h4 (x) 2 (Y*, X) for any X RT BBx(k-1) with equality if and only if y (X). We can thus write h2(') = (Y", X²),, or equivalently h2(x') = (8', X')p.
Taking X' = X we get
(s(()) =
- - f((')) + (h) -V x)=] 2 | (x) - (8' -x))1-11((x)) - -x(x))
Hence, for any X E RT (1x( have
[x(X) - ,(('91
1X- - 1
|o|| (x) - (X)
(f((X) f((X)
- eXx111l-
11X - -x
Choosing any X * X such that Y g (X), we get (x(( 0. Such X must exists, since otherwise 1F
(X) (Y*, X) for all X E R x and (X) Σl ΣØ= Y by Proposition F.4. Since H is strictly submodular, it can't be modular unless n otherwise Ineq (3) will not hold strictly. Then, this lower bound indeed also grows with We can thus conclude that L.g itself grows with 7
al
B. Connection to Related Non-convex Classes
In this section, we discuss the relation of DS functions to other related classes of non-convex functions, namely DC and discrete DC functions.
B. Relation to DC Functions
We remark that the class of DS functions is not subclass of DC functions. Since DC functions have continuous domains, it is evident that DS functions defined on discrete domains are not DC. For continuous domains, any univariate function which is not DC can serve as a counter-example, since as mentioned earlier when n = 1 any function is modular. The function F [0, 1] + R given by F(x) = 1 - vIx 1/2[ is one such example, given in de Oliveira (2020, Example 7). We provide below another counter-example for any n.
13

---

Discrete and Continuous Difference of Submodular Minimization
Proposition B.I. The function F : X + IR defined as F(a)) = | with q E [0, (F(x) | if = and where each &₂ is closed interval, is modular function but not DC function, whenever E int X.
Proof. We first note that F is separable function, hence it is modular. Next, we recall that convex functions are locally Lipschitz the interior of their domain (Mordukhovich & Nam, 2023, Corollary 2.27), i.c. for all x E int X' there exists neighborhood U of z such that F is Lipschitz continuous on U n int X. Since the difference of locally Lipschitz functions is also locally Lipschitz, DC functions are then also locally Lipschitz on the interior of their domain.
We show that F' is not locally Lipschitz at O E int X. and thus it cannot be DC. We show that there exists {a C X such unbounded. In particular, we take x² ee For any q [0, 1), we have |a"1l2
that {-*} + and [F(x"M|
F F(**))
(1/k)²
12-9.
|
1/k
Taking the limit as k oo, see [F(o")-((01
[F(lll ||
||z 1
-
00.
The function in Proposition B.I is used as sparsity regularizer in sparse learning problems, which we showed in Section 3.2 are instances of Problem (1).
B.2. Relation Discrete DC Functions
Next, we discuss the relation between DS functions on discrete domains and discrete DC functions considered in Maehara & Murota (2015). Therein, function F 2" - Σ called discrete DC if can be written as F G H, where G, H. : 2 E are L--convex or M functions. We recall the definitions of both types of functions, see e.g.. Murota (1998, Chap. 1, Eq. (1.33) and (1.45)).
Definition B.2 cL'-eonee A function F Z" - R is called -oovvee if it satisfies the discrete midpoint convexity; that is, for all x, y E Z", we have
x + y 2
r y
F(x)+F(v)) F(v) 2 F
+
(12)
2
Definition B.3 (MM*-convx). A function F g + R is called M4-convex if, for any z, E 2" and i E [n]] such that F2 > yes we have
F(x)+F()) 2 min(F(x ea) + Fly ex), min je(M),naa.
F(x- - -ec Fly + -e
(13)
c.--convex functions are proper subclass of submodular functions on Tn (Maehara & Murota, 2015, Section 2.1), while Mo-connex functions are proper subclass of supermodular functions 2d (Murota & Shioura, 2001, Theorem 3.8, Fxample 3.). It follows then that any discrete DC function is a DS function on Z². This is of course not surprising in light of Proposition 3.1 (which still holds for functions defined on 2"), Corollary B.4 is the analogue of Proposition 3.1 for discrete DC functions, which was stated in Maehara & Murota (2015, Corollary 3.9-1) for functions defined on finite subsets of Z
Corollary B.4. Given F : X + Z, where each X, C R is a finite set, there exists an L Lt discrete DC function F': 2m - Z such that F(x) = F' (x))) for all E X, where m I[ (0 ls 1] - X is bijection with k; = |
k; - 1] RR as F(x) (on)=F((m(( F(m(x)) where m II [0: k; - 1] + X' is the bijection defined in Corollary 4.2. Since F' is defined on finite subset of 2n, by Corollary 3.9-1 in Maehara & Murota (2015), there exists F' Z + Z such that F' = G' H', with L--vveexx functions
Proof. Given F: + R. where each X; C RR is a finite set, we define F: :
G", H² : =Z" + Z, and F=(=)= = F()) for all E 1T 0 K, 1] and F')z)= = 0 otherwise. We thus have for all at E X,
F(x) = =mm (im-1(x))
Since T.*_convxx functions are submodular on 2h and submodularity is preserved by restriction, then the restrictions Gix 1t'x x X + E of G', Ht' to X are submodular, and the restriction 1xx X' + E of F" to X' is a DS function with F Fxx = G2x- - H'xx Note however that F itself is not necessarily an I T discrete DC function, since I, c.o-vviyyy
14

---

Discrete and Continuous Difference of Submodular Minimization
preserved by restriction. Nevertheless, minimizing F on X' is equivalent minimizing F' on 2 if min F(x) which can be assumed wlog. The class of discrete DC functions, in particular I T, functions, is thus essentially equivalent to the class of integer valued DS functions discrete domains.
Applications which are DS but not discrete DC: In Section 3.2, we outlined two classes of applications which have natural DS objectives. We now show that both types of applications do not have natural discrete DC decomposition, for general discrete domains, even if we ignore the assumption in Maehara & Murota (2015) that F is integer valued.
For QPs of the form m F(z) } Qr + c cTar, x, F admits natural discrete DC decomposition, when 2t's are uniform finite sets. However, this not the case if X; a non-uniform finite set for some i, as in the integer least squares experiments consider in Section 5.1. Such cases also arise for example in non-uniform quantization of neural networks (Kim et al., 2025). To see this, note that any T,*-convex function F: Z - ZU { [+00} should satisfy for all y E dom F, 12 sty E dom F. If we're minimizing a quadratic over uniform grid, we can map from the uniform grid to 11 k. -1 1J and the resulting function will still be a quadratic. We can then easily decompose the objective into L La DC function, as we show in Proposition B.5. However, if the domain is a non-uniform grid, the resulting function is no longer quadratic.
Proposition B.5. Any quadratic objective F 2 + E defined as F(x) xx Qæ can be written as the difference of two La functions G(x) x (Q + D)æ and (x) -x ( (-Q+ D)x, where Q min(Q,0). Q mmx 0}, and D
diagonal matrix with D max - E, Qig 2, E, Q E, 0
Proof. Let V F be the L Hessian of (Maehara & Murota, 2015, Section 3.2), then F = Q + QT. To see this note that for any æ E 2n, i E [n]. we have:
((+ F(x) = c, Qr + x _Q + Qu-
(14)
Then for any + i, we get:
F(tF(() = F(x + + F(r+ee) (F(x + F(x))
(15)
Qe: + TQe
+Q (e]0x Qr x Qe, Qu)
(16)
Qij Q3
(17)
and thus
F)x()) = F(x + 1 + e.) F(x+ (F(z (Pbte) F(()) Σ Vij F(x)
(18)
= cTQ(2= +)+ 1) Qe: + Qii (c) Qr + x Qe, + Qu+)
Σ
F(x)
(19)
1
= =qqQ + T Σ + Qz)
(20)
2Q
(21)
Hence, V²F=++0
Similarly the L Hessian of G ((x) ( +DD and of H os V²H(x) Q+ - -QQ) + 2D. Note that for any j # i we have Gzz < 0 and (x) - 0. We also have
a
n
G(z))
(9 + Q77) +D 20..0. 2.
j=l
Similarly,
a
Σ
Vi) = Σ
(ot + + 2D 2 0.
1=1
Hence, by the Hessian characterization of L'-convexity (Maehara Murota, 2015, Theorem 3.7), G and H are L convex.
15

---

Discrete and Continuous Difference of Submodular Minimization
For sparse learning problems gin {(x) + >| where y E [0, 1), A 0, and é is smooth function, show below
that | is not discrete convex function.
Proposition B.6. The function f(x) = || 12- q E [0, 1) (when q = O, we let f = || 1lo). is not LA-convex nor M over 2
Proof. As a simple counterexample for the case q E (0, 1), take 7 = so that f Z - R, is given as f(x) = |0/ Taking
x and y = we have
x y 2
1) + f
x + y
f(x) f(y) 2
(22)
2
24 +022 2
(23)
which, for any q E [0, 1), is contradiction.
For 1, -o--ooitiittyyy definition simplifies to (the minimum over empty set is +-0)
f(x) + f()) 2 f(x 1) + f(x 1),
for all x > y. We again consider the counterexample x 2. = When & = 0, we have f(x) + f(y) = =10 f(r 1) far + 1) which contradicts the Ma-convexity definition.
Similarly, for q E (0, 1), we have: f(x) f(y) 2 + 0 < + 3 -f(x 1) + f(x + 1), where the inequality follows from the fact that [zc + y/8 < | + |u|%, which implies that 2 = |3 11a < 3 +
Of course, in both cases, we can still use the generic decomposition given in Maehara & Murota (2015, Corollary 3.9-1), this would yield G' and H with large Lipschitz constants, which would lead to slow optimization.
C. Reduction to set function case
In this section, we discuss the reduction of submodular minimization problem minge F(x) over the integer lattice X' [0: k 1 to the minimization of submodular set function over {0, 1)mx(k-1), given in Bach (2019, Section 4.4), As mentioned in Section 4.2, the same reduction can be used to reduce Problem (1) to DS set function minimization.
We define the map π {0, (x- {0, [0, 1] (k-1)
{ if there exists j 2. Xi.5' = 1,
7 (X),,
(24)
0
otherwise,
for all i E [m].j E [k 14-11,ice ie.. =(X) is the smallest row non-increasing matrix such that X S x(X). Given B, 2 0 for all i E [n). define the set-function F (0, 13 (k) - IR as
= F(X))F((((X))) + Σ B.IT((X);
XiIl1
(25)
where m(X);, X; are the tth rows of x(X),X, X, respectively. Then minimizing F is equivalent to minimizing F: mi F(X) = min 11th F(x). To ensure F is submodular, we choose B; >> 0 such that
FF() - F(x) S Σ B,la Wel.
(26)
for all x S E X' (Bach, 2019, Section 4.4). We thus reduced minimizing F to minimizing a submodular set function. Similarly, we can reduce Problem (1) with X [0: k - 11"d to the following DS set function minimization:
min
((X) - (()),
xe(0,1)-x(--1)
16

---

Discrete and Continuous Difference of Submodular Minimization
where G, H are submodular set functions defined as in (25).
However, discussed in Bach (2019, Section 4.4), this strategy adds extra parameters B; which are often unkown, and leads to slower optimization due to the larger Lipschitz constant L. of the continuous extension f, of F (which reduces to Lovász extension in this case). In particular, while we can bound Ly. S V(A 1)m max; B; (Proposition 2.3-g), the bound for f is (2k- - 3) times larger, i.e., J, S (2k: 3) (k - 1) max; B; The time complexity of both submodular minimization algorithms in Bach (2019, Section 5) and the one in Axelrod al. (2020) (the fastest known inexact submodular set function minimization algorithm) scales quadratically with the Lipschitz constant of the continuous extension: Ö(( "KL4 F² and /() FO respectively. Using the reduction F increases their complexity by at least a factor of O(P2). Moreover, the cost EO P of evaluating F can also be larger, if computed via Eq. (25) it incurs an additional ((k) time, i.e., HO2- = F + (mk)). This also applies in our setting, where is a DS function, since DCA-LS requires solving a submodular minimization at each iteration, which will be similarly slower using the reduction.
To validate this empirically, we compare the minimization of submodular quadratic function F with that of its reduction F:
1 n Qu, min P(x)= - 2 xc|-1.1j-
(27)
We set n 50 and construct a symmetric matrix Q E F=*= as follows: for i < j. draw Qu ~ UU-1// where Ui denotes the uniform distribution; and draw diagonal elements Q ~ Mo.1]- The resulting Q has non-positive off-diagonal entries, making F submodular by Proposition 2.1-a. This construction also helps ensure the minimizer is randomly located within the lattice D.
As discussed in Section 4.1, we can convert Problem (27) to submodular minimization problem over X' = [0: k: 11" by discretization. In particular, we define F' X' - R as F' (x) = F(m(()) with m : X + [-1, 1|", m. = k-1 23 1. Then F' is submodular by Proposition 4.
2
To apply the reduction, we must find positive B,'s which satisfy (26) for the function F'. One valid choice is to set B; B for all i [n], where B is the Lipschitz constant of F' with respect to the fi-norm. We start by bounding the Lipschitz constant of F over [-1, with respect to the nnomm. For all x E [- 1]", we have
[])() = ||Q=|1>> I |1@1|s>-><<11111 ||0||
S [|]]
(28)
Hence, F is T.-Lipschitz continuous with respect to the nnorr with I. = loc-sos which equal to the maximum -nnorm of the rows of Q. For any x, E X, we have
[F(x)) F'(1)) [F(m(x)) F(m(x))
(29)
< (z) -yy)l
(30)
2L
= || - v111.
(31)
k
Hence, 1" is Lipschitz continuous in the no-mr over [-1, 1]"d with constant B - We can now define the reduction F of F" as in (25). Then Problem (27) reduces to a submodular set-function minimization problem::
min F(X).
(32)
X X=(0,T]ax(--))
A minimizer X* of (32) yields a minimizer x² E X of F' by setting x" = (
We numerically compare minimizing F' and f over their respective domains to get minimizer of Problem (27). We minimize F' and F using pairwise FW, which we run for 200 iterations. Let á, X' denote the resulting solutions, where is obtained by applying θ to the output of pairwise FW with F. We test different discretization levels k: = 100, 200, 500 and initialize both methods at zero (i.e. 0 E RM for F' and 0 E (k=1( for F). For each value of k. we run 50 random trials. We evaluate the two approaches on three metrics: the relative objective gap between å and 7, the duality gap given in Bach (2019, Section 5.2), and the running time. Average results are shown in Figure 2. We observe that ă has a worse duality gap and objective value than è and a longer running time, after the same number of iterations. This confirms that minimizing F is significantly slower than minimizing F", both in terms of convergence speed (due to the larger Lipschitz constant L and per iteration runtime (due to the higher evaluation cost of F).
17

---

Discrete and Continuous Difference of Submodular Minimization
0.45
10'
10
(F(B) F(A))FF8))
0.35
Duality Gop
10
10
0.3
Thme
0.25
10"
10
0.2
16
100
200
300
400
500
100
200
300
400
500
100
200
300
100
500
Figure 2: Results averaged over 50 runs comparing the direct minimization of F on the lattice X (Lattice) and the minimization of its reduction F on {0, 1 1 (Reduction) on Problem (27).
D. Proofs of Section 2
D.1. Proof of Proposition 2.3-g
We prove here the bounds on the Lipschitz constant of the continuous extension submodular function given in Proposition 2.3-g. The general bound was stated in Bach (2019, Section 5.1), and follows directly from the definition of the subgradients (see Proposition 2.3-e).
Lemma D.1. Given a normalized submodular function F; [0: k ----1 1]" + R, its continuous extension fo is Ls, -Lipschitz continuous with respect to the Frobenius norm, with T. (k - 1)nB where B = max xte (F( If F is also non-decreasing, then Lsg- S. F((k 1)1).
Proof. For any X B let (p. 9) be non-increasing permutation of X and Y the corresponding subgradient of fi at X, defined as in Proposition 2.3-e. The bound for the general case follows directly by bounding the Frobenius norm of Y.
a(k-1)
1)
|
Σ
y2
ps.qz
1=1
1(k-1)
= Σ
(F(y") - F))
i=1
S n(k 1)
Moreover, if F is non-decreasing, then Yı 2 0 for all i,j. By telescoping sums, get:
n(k-1
|Y]|s S
Σ
pp..g
n(k-1)
Σ F(y²) -F()-11
= =F(y 1)) - F()9) F((k - 1)1) F(O).
Since F is normalized, then we have ||А|| < F((k 1)1).
E. Proofs of Section 3
E.1. Proofs of Proposition 3.1 and Example 3.2
Proposition 3.1. Given any normalized F : X - R where each X, C is finite, there exists a decomposition F= G H. where G, H X - are normalized (strictly) submodular functions.
18

---

Discrete and Continuous Difference of Submodular Minimization
Proof. We give a constructive proof, similar the one provided in Iyer & Bilmes (2012, Lemma 3.1) for functions.
Let a S 0 be any lower bound on how much F' violates Eq. (3), i.. for any X, + e [n]. and ai aj > 0 such that - a x + 03ez E X' we have
F(x + a,e.) - F(x) F(x + ase; ayez) F(x+ a.
(33)
Since F is finitely valued and defined on finitely many points, such a lower bound must exist. For example, we can use a' = -4 maxsex [F(z)]. Note that a < 0 unless F is already submodular, in which case we can take G F and H 0.
We now choose any normalized strictly submodular function H X + R. We provide an example in Example 3.2. H satisfies Eq. (3) with strict inequality. As each X; is finite, there exists such that
(s + a.e)) (xx)) Ha a. + ayez) + H( + ayez) 2 3.
(34)
whenever E X,i [n], and a4, aj > 0 are such that x + a,e, x + ajej EX.
We next construct G and H based on H. In particular, we define G F+ Inl fl and H |a| H. Since F and i B
+ normalized, G and H are also normalized. Also, И is strictly submodular, since multiplying by positive scalar preserves strict submodularity. We check that G is also submodular. For any Z E X, i e [m]. and a, aj > 0 such that 0,C, x + 0gez E X, we have
G(x +,,) G(x)- G(x + a,,; + tage)) + G(x + ajee)) = F(x + a.ee F(x) - F(x a,c; + tace)
|
+ F + +(fe)))))) + 3
(i [ + are) M()
H(x + ae;; + aaee,) H(x + aaee))
2a 3
(35)
Hence. is submodular by Equation (3). This yields the desired decomposition F= G H. with G and H normalized submodular functions. Choosing a < 0 which strictly satisfies the inequality (33) (which is again always possible), can further guarantee that G' is strictly submodular, since the inequality (35) will become strict too.
Example 3.2. Let H R -> TR. be the quadratic function H(x) = - - Jx. where J is the matrix of all ones, and define H X R as H (x) H(x)- - (Immn)) Then, is normalized strictly submodular function.
Proof. Since each X; is a compact subset of R. there exists an interval [a,, by] such that X; S. [a,, b,]. The function H is wwice-differentiable on I (a,, bi], and the Hessian of H has negative entries. Hence, it is strictly submodular on ||"_|[a; (a;, b,] by Proposition 2. lbb. Since strict submodularity is preserved by restricting to X, H is also strictly submodular. It is also normalized by definition.
E.2. Proof of Proposition 3.3
Proposition 3.3. Given any normalized F : X + where each X; is closed interval, if is differentiable and there OF dr. (x) az. (x + ae;) 2 -Loaffo for all X,i jjj 0, + a E Kz. then there exists
exist LF 2 0 such that 3F decomposition F = G
where G, H. X R are normalized (strictly) submodular functions.
Proof. The proof is again constructive. Note that Lp 0 unless F is already submodular, in which case can take G F and H- 0.
We now choose any normalized strictly submodular function H : X' + R, which is differentiable and there exists ي > 0 such that
an (2:
di
(x aej) Lga,
Ox:
Ox:
for all v E X, xxi j. >> 0 such that Jr + E Xz. We provide an example in Example 3.2.
We next construct G and H based on Q. In particular, we define G = F + 41 and H Le Since F and H are normalized, G and H are also normalized, Also, H strictly submodular, since multiplying by a positive scalar preserves
T.
T.
19

---

Discrete and Continuous Difference of Submodular Minimization
strict submodularity. We check that G is also submodular. For any x E x. [n], such that i + and 2y + Xz. have
0G Oz;
aG Ox;
OF
OF
LE OH
OH
22)
(x + ae,)
dzi (z)
(x + aej)
+
L Ox: (a)
(a aej))
θx;
dz;
LF L n O. L
-Lp +
(36)
Hence, is submodular by Proposition 2.1-a. This yields the desired decomposition F H, with and H normalized submodular functions. Choosing Lp > which satisfies the strict inequality 8u. (a:) - 0v,
OF
OF (a aej) -Laa, we can
further guarantee that G is strictly submodular, since the inequality (36) will become strict too.
F. Proofs of Section 4
F.I. Proof of Proposition 4.1
Proposition 4.1. Given X = TI=1,,,,7 = II, X, with compact sets X, X. C C, ; - R and m X" - X be a monotone function such that [m(x)]; = m²(xx). If F is submodular, then the function F' : X' + R given by Fx)x) = F(m(x)) is submodular. Moreover, if m strictly monotone, then F is submodular iff F is submodular.
Proof. For any monotone m, if F is submodular, then for any 2, y E X we have F'(min(z, v)) + F" (maxffx v)) F Fmm(min(2z; y})) + F (m((min(a, v))) ((mn((()),m + F ((mxx(((z),mm))) S (m(x)) + (m)())
(F submodular)
F') + (v).
Hence, F' is submodular. F is modular, the above inequality becomes an equality, implying that F' modular too.
Moreover if m is strictly monotone, m is invertible, and we may write Fly) = F'(mm=(() We show that the converse claim also true in this case. Indeed, since the inverse of strictly monotone function is again strictly monotone, we have by the first claim that if !" is (sub)modular then F' also msubarodular..
F.2 Discretization of non-Lipschitz function example
In Section 4.1, we assumed that the function F : [0, 1]" - is Lipschitz continuous to bound its discretization error. However, Lipschitz continuity is not always necessary. We show below how to handle example of non-Lipschitz continuous function. In particular, we consider function F [-B, B)" IK given by F(x) ((x) + ||>||] with g [0, 1), where L' [0, 1 + IR is a DS function L-Lipschitz continuous w.r.t the -orm. The modular function || is not Lipschitz continuous on the domain [-B, B)
We first observe that the function |x] satisfies a notion of Lipschitz continuity, for x +
Lemma F.I. The function F R + IR defined as F(x) = |x| with q E (0,1) satisfies
||yl
|x | < max lyl. |2130~1|y x/.
for every two scalars y + O of same sign.
Proof. We assume without loss of generality that |y]
2 |x||
>
0.
Let be the smallest integer such that 2'q 2 1. Note
that
y
| (2
1y/ 22
| 22
|x/9
+
|
1
Applying this relation recursively yields
|//
2
[x0 2"
2 2/ 2/ 9----11 by x
|y/
||01"
< 2/yy1-11
x/
(37)
y/
2 1
by 1/(21-1)))
20

---

Discrete and Continuous Difference of Submodular Minimization
where the first inequality follows by the mean value theorem with z scalar between x and y, and the 2nd inequality holds
since by definition of we have 2 1 S 2'q and thus |z|2"0-1 v 1y/
We shift and scale the function F to obtain function F' [o, 1j IR defined F'(x) = F 1)), which remains DS by Proposition 4.1.
Proposition F.2. Given q (0, > 0 and F : [0. 1 T defined as F(x) (((x) + || 1) where e: [0. 1]"h + R a DS function L- L-Lipschitz continuous w.r.I the too normm let k = 2 max{ [ [ +
and define the function F' [0 k 1 R as Fx)) = F(x/(k - 1)). Then F' DS and we have
min Fa(x') c/2 min F(x) S min F' =E(U,1|
(38)
o' r'Ej0:k-11n
se 10
The same also holds if O, with k 2[ +1.
Proof. Let Φ: : [0: k- 1]" + [0. 1]" denote the map (xx) = x/(k 1), so F'(x)) F(((2)). Since F is DS and Φ monotone, then F' is also DS by Proposition 4.1.
Let 10 + [0 k _ be defined for all E [0,1]" such that for each i E [m]. [T())]; ! if x; 1/2, and
if 24 + 1/2. Note that k: is an even number [T()))] = where <t() is the nearest point z; for in [0 : k \ - hence k-1
2 E [0 : k 1].
For any x [0, 10. let x' (xx) be the vector obtained from the above map. Note that for any i, if 1 then ((x²) = }
otherwise have [r; o(x))) S x-1 and (x(x)) - ! 2 k Let (3.) [(2r, 1)1%, we show that for all where I, 1/2, we have
(G,( - G((((()))))) < 4B 2 )- - c(+\).
اル are x(1) 1/2+1 1) which are equidistant from 1/2. Hence B(xx; - 1) and ((2((z)) 1) will always have the same sign, and max 1), B(20(x)) - 1)} 2 24
Note that the nearest points ((() to x; 1/2, for / in [0- k l||
By Lemma F.1, we thus have
(z,) G,(o(z))) < 2( 28 )- )0
BB(x, 1) B(20(2)) - 1) S 4B( 2B 10 -
Putting everything together we get:
F(x) F=xx'=='1111 (F(x) F(d(2())
= (xx ((((2())
Σ [G,(z)) - G((((a))))
2.$1/2
< L1 - 6(2')llo + +4B
2
2B
yo-1
Σ 10 - ا(x\)1
k-
11$1/2
< L
2B 4B
k-
y- n
k-1
k
L,
2B y1
<
+ 2n(
1
< 4 4 2'
The same bound holds for g = 0 by noting that B(2x; - 1) and ((2)(x))- -1) have the same support, hence || [B(xx; - 11 [2((()))) - 1)llo (no discretization error).
F.3. Proof of Proposition 4.4
Proposition 4.4. For any normalized function F: :00 k - 1]n + R, we have
min F(x) = min
fx).. X
(10)
#E 0|
21

---

Discrete and Continuous Difference of Submodular Minimization
Moreover, of is a minimizer of F then (x*) is a minimizer of S1. and if X* is a minimizer of J4 then Round minimizer of F.
Proof. Let x- be minimizer of F. By Proposition 2.3-a, we have F(x*) = f1(0-1(z*)), Since o '='(2") E [0, 11111(((111 then
min F(z) #E 1:K-1 11
Xe(o. 1e(0 fx().
min
Let X is a minimizer of 4. By Proposition 2.3-c, we have F(Round x( S fu(X*). Since Round (Xx) E [0
1 we have
min #c 0:k-1]" 1|" xe(0,11,
F(x)
min
f(().
F4. Continuous extension of a normalized modular function
In this section, we derive the form of normalized modular function and its continuous extension.
Lemma F.3. A function
[0: k - 11th - IR is modular and normalized iff there exists W (Rax((-1) such that
a
24 Way for all
F(x) ΣΣ
[0:k- -0:
(39)
Proof. We first recall that a function modular iff it separable under addition (Topkis, 1978, Theorem 3.3). (=) If F is modular, then it is separable under addition, i.e. there exist F, [0: k =(x)=Ea = (i(),) for any x E [0 k 1| As F is normalized, also have that F(() Σi=1 F:(0) =0
R. i E [m], such that
Now, define W E (=)( such that W = F. F, 1). for i E [m]. j E [k- - 1]. We thus obtain
F(x) = Σ P((x,) - F(0)
Σ P.(x,) Fi(O)
Σ
R((i) Feli 1)
(by telescoping sums)
1=
" 8
W.
(-) ) If there exists matrix W (=)(k=1) such that F(x) Ei= E Wiy, then F is separable under addition, and hence modular. Indeed, we can define the functions F; [0 k - 11 RR i E [n]. by Ff(x) = Σラ= Wij- Then F(x) Σm= P((x;) for any x E [0: k - 1j F is also normalized, since F(0) = 0.
Proposition F.4. A function F [0: A 11"d - R is modular and normalized, with F(x) = Ei E Wúj for all
I [0: k- 11"h iff its continuous extension fü is linear on its domain, with f1(X) XW, for all X E nx
Proof. Recall from Lemma E3, that F is modular and normalized iff it can be written as F(x) Σ E Wi for
some W E (k-1)
(#) ) If F' has a linear continuous extension such that fi(X) (W,X)p for all X E RTx((-1) for some W E 11-
Then, for any 10: k- 1)" let X 0-1 (1r). By Proposition 2.3-a and the definition of the e-1 (7b), we have that
a
カ-1
W Xay = a Ze
F(x) fx) (W,X)=
ΣΣ
ΣΣ Wyy-
(40)
1=1#=1
22

---

Discrete and Continuous Difference of Submodular Minimization
( Suppose F is modular and normalized. By Definition 2.2, the continuous extension of - F is equal to f4 on its domain. Since F and - F are submodular, then both fa and ff are convex by Proposition 2.3-d, which implies that f+ is affine on its domain. Since F is normalized, we have (0) F()) = 0 by Proposition 2.3-a, hence fi is linear on its domain, i.c. (X) = () r for all X E 1R (==((=1)) for some W' E R=x(k-1), By the above argument for the reverse direction, we must also have that W = W.
E55. Proof of Theorem 4.5
Before proving Theorem 4.5, we recall some properties of DCA that apply iterates of Algorithm 1.
Proposition F.S. Let ev 2 O, and {X*), {X'), (Y') be generated by Algorithm where the subproblem at line solved up to accuracy ex. Then for all N. we have:
a) [(x+1) ( s(X)) t..
b) ffX) - f((++)(() c, then X is an + ex-critical point of g - h with Y E Oete, n ah((').
Proof. Note that the iterates X Y are generated by DCA step from X with subproblem (9b) solved up to accuracy The proposition follows then directly from Proposition 2.5-a.b.
Theorem 4.5. Let {a²} } be generated by Algorithu I, where the subproblem on line 6 is solved up to accuracy cx 2 0. For all t E [T], 2 O, we have:
a) F F(a+tl) & F(x*)+
b) Let {v ( be the vectors corresponding to the permutation (p, q) from line 4, defined as in Definition 2.2. If (p, q) is row-stable and F(x')- - 1 1)= I e, then
F(x') S F(y') + + for all i E [0: (I: 1)m]-
c) Algorithm 1 converges to an (e + ex) loocll minimum of F after at most (F(x")- - F")/e iterations.
Proof. We first observe that for all E [T], we have:
F(x²) - F(x'((('))) = 1(X") - (xx=))=))((((((((((=)))>))))
(41)
Since by the extension property (Proposition 2.3-a), we have f(X++1)= = F(x*+1) and f f(X') = F(x'). And by rounding (Proposition 2.3-c), we have (X++1) S f(X++1). If X is integral and rounding is skipped, this still holds trivially since X X
(a) This follows from Proposition F.5-a and Eq. (41)
(b) If F(z*) F(x < e, then f(x*)-f(X ((*+)) S too, by Eq. (41). By Proposition F.5-b, we thus have Y' E Oete.g((") (x")).). We observe that by definition of y¹, if 4) is row-stable non-increasing permutation of X*, then it is also a non-increasing permutation e-'(y"), for all E [0: (k- 1)m]. Hence, Y' e a 'yy)) by Proposition 2.3-e, and y E Oete,g(X*) n0( Therefore, by Proposition 2.4 and Proposition 2.3-a,
F(xt)=
+ = F(ly') +
(42)
for any E [[k- 1)m].
(c) We first argue that Algorithm I converges (F(x*) F(xtt1) 2 t) after at most (F(x") - F*)/e iterations. By telescoping sums, we have ΣT=1 F(z²) - F(z(+1) F(x0) -F((T) < F(z") F". Hence,
min F(x²) ((x F(x0)) - F
(43)
-f[--1]
T
23

---

Discrete and Continuous Difference of Submodular Minimization
Taking T = (F(x²)) //e,,, we get that there exists some / [T such that
F(x') F(x*+1) - (F(x") F2) -
Since (p, q) is chosen on line 4 to be a common permutation of X and (z*), then by the same argument as in Item have at convergence F(x*)) S F(**)++ + e Eg. Since øf is the best neighboring point of x this implies that x' is an (e + eg) -loccl minimum of F.
G. Experimental Setup Additional Details
We provide here additional details the experimental setups used in Section 5. All methods were implemented in MATLAB. To solve the submodular minimization subproblem in DCA-LS (Algorithm 1-line 6), from Bach (2019), available at http:/ /www. di ens fr/- fbach/ httph//uummuuuuueeeeee la rr_m__lleee t drii_oniin niee zip. In both experiments, during each DCA iteration, we run pairwise FW for a maximum of 400 iterations, stopping earlier if the duality gap reaches 10- We warm start pairwise FW with the subproblem's 's solution from the previous DCA iteration.
the pairwise FW algorithm
To achieve a desired target (SNRan) of 2 O, we choose the noise variance o² using the following formula,
b
10 it
(44)
where 5' ~ (m, then set the noise vector to 5 = oe'.
G.1. Additional Details for Section 5.1
The RAR solution is obtained by first solving the relaxed least squares problem
x LS E argmin F(x) = ||Ar - bl12
(45)
=,(-1,3]"
then rounding .8 to the nearest point in X. We implement OBQ according to the pseudocode provided in Frantar & Alistarh (2022, Algorithm 3). But since in our setting we assume no access to x², we initialize OBQ with LSS For the ADMM approach of Takapoui al. (2020), we use the code from https: //g tig..b......... com cvvgrp/ horp/mm /mi qp_admm? rab-readme ov- file. In DCA-LS, we use maximum of T 50 outer iterations and
10-5
For 100, recall that we obtain optimal solution using Gurobi 10.0.1 (Gurobi Optimization, LLC, 2024). But since the domain X' = 2,,,0, has unevenly spaced integers, Gurobi cannot solve it directly. Instead, we reformulate the problem into an equivalent unconstrained binary quadratic program (UBQP)
min x. Un + dxx
(46)
20,1)22
where U AT d - ATMM++ 6 AM) and M E x= defined M L, 3 [3, 1], with denoting the Kronecker product. To see that the two problems equivalent, the map Mr 1 defines bijection between {0, 1] and X, and that the objective in (46) is equal to F(Mx II), without the constant terms.
G.2. Additional Details for Section 5.2
We solve the box constrained variant of Lasso
min EE [111
| - 6112 >||=||1,,
(47)
using the FISTA algorithm from Beck & Guttmann-Bedl (2019) with default parameter settings, i.e., 1000 maximum iterations and ||x - |*1| < 10-5 stopping criterion (for other parameters see https: /www tau ac 11/ /1/-beckk///// solvers/ fista). In DCA-LS, we use a maximum of T = 25 outer iterations, and set = 10-5, In DCA-LS, DCA-LS- LASSO, and FISTA, we use = 10 for ė E [0 5], and warm start with the solution of the previous value (in decreasing order). Our implementation of OMP is adapted from the one provided Becker. We run OMP for a maximum of [1.5s] iterations, stopping earlier if the residual reaches Ar bl|2 S ||
24

---

Discrete and Continuous Difference of Submodular Minimization
H. Additional Experiments
present here additional experimental results for the applications presented in Section 5.
H.1. Additional Integer Least Squares Experiments
Recovry Probubality
08
0.08
(F(a) PGA))
0.8
Bit Ervor Ract
0.6
0.4
0.06
RAR
AUMM
0.02
0.2
OBQ
-0- ICAALS
111
0.5
Reconey Prolabiilty
0.8
(FU)) Fle F(r (F
1.5
Bit Eevor Rate
0.2
0.6
0.15
0.2
0.05
Optinal
30
15
201
20
20
15
200
Rue
SNR
SN
0.25
1.5
Recoery Probubality
0.8
(8(()) (0(3)-((e)) ((
Bit Rate
0.6
0.15
0.4
0.1
ADMI ZAR
- OBQ
-0+ IXCA-LS
-0.5
15
20
25
30
S.V Rue
S.N Ran
SN Reu
Figure 3: Performance results, averaged 100 runs, for integer least squares experiments: Varying with 400 and
SNRaB 20 (top), varying SNRaB with m 100 (middle), and varying SNRaB with m 400 (bottom).
We repeat the integer least squares experiment from Section 5.1 with n 400. We also consider another setup where we fix m and vary the SNR,B. Performance results for both are reported Figure When using a signal of length n = 400, we compute the relative objective gap with respect to z², as is very time consuming to obtain x using Gurobi. We again observe that DCA-LS outperforms baselines on all metries. For 100, DCA-LS performs on par with the optimal solution x² starting from SNR 24 dB. OBQ matches the performance of DCA-LS from SNR = 26 dB onward. For 400 OBQ matches the performance of DCA-LS from SNR 24 dB. Note that the relative objective gap in this case can be negative, since the true signal R is not necessarily the optimal solution for the integer least squares problem. Indeed, we see that this is the case when the noise high; DCA-LS and OBQ obtain a better solution for SNR < 18 dB and 15 dB, respectively.
H.2. Times for Integer Least Squares Experiments
We report the average running time the compared methods on the integer least squares experiments from Section 5.1 and Appendix H.1 Figure 4. The reported times for DCA-LS and ADMM do not include the time for the RAR initialization, and for OBQ do not include the time for the relaxed solution initialization (which has similar time as RAR). We observe that
25

---

Discrete and Continuous Difference of Submodular Minimization
DCA-LS is significantly faster that the optimal Gurobi solver, even for the small problem instance (n 100 For the larger instance (n 400), Gurobi is already too slow to be practical. While our algorithm is slower than heuristic baselines, it remains efficient, with maximum runtime of 100 seconds for m = 400.
10p
10
107
Time (6)
Time (6)
10
10:2
ADMM
10
10
Optinal
10 1
10'9
1.2
1.4
1.61
1.8
1.2
1.4
1.01
1.8
11
m
10
10
9
10a
100
Time (6)
11P
Time (6)
10
10-2
10
10
10-4
10-47
15
25
15
20
25
30
SN Rus
SN
(c)
(d)
Figure 4: Running times (log-scale), averaged over 100 runs, for integer least squares experiments: (a) Varying with 100 and SNRan = 20, (b) varying m with = 400 and SNR = 20, (c) varying SNR and m 100, and (d) varying SNR and m = 400. Optimal solution is computed using Gurobi.
H.3. Additional Integer Compressed Sensing experiments
We repeat the integer compressed sensing experiment from Section 5.2, with another sparsity level s 13 [00005]] We also consider another setup where we fix m/n 0.5 and vary the SNRBB Performance results for both are reported in Figure 5. When varying the number of measurements for = 13, we again baselines and DCA-LS across all metrics. DCA-LS also outperforms the baselines in terms of recovery probability, but lags slightly behind in estimation сттоr and support eтror when m/n s 0.4. Similar trends emerge in the experiments where s = 13 and the amount of additive noise varied. Again, we see that DCA-LS-LASSO and DCA-LS outperform in terms of recovery probability, and when SNR 2 3, outperform in estimation error and support error. Interestingly, when we decrease the sparsity to s = 26, we see that DCA-LS recovers signals earlier than the baselines, but does not reach a 100% recovery rate once SNR, 20. Similar the experiment Section 5.2, we see that DCA-LS-LASSO significantly outperforms all other methods, especially in terms of recovery probability.
that DCA-LS-LASSE, outperforms all
H.4. Times for Integer Compressed Sensing Experiments
We report the average running time of the compared methods on the integer compressed sensing experiments from Section 5.2 and Appendix H.3 in Figure 6. For LASSO and DCA-LS, the reported times correspond the of running times for the 6 À values tried, À 0. 10-5, The reported time for DCA-LS-LASSO include the time for the LASSO initialization. We also report the running time of LASSO and DCA-LS for each À separately at m/n. Ry 0.2 and 0.5 (m = 50 and m = 123, respectively) with SNR&B in Figure 7.
We observe that DCA-LS and DCA-LS-LASSO are slower than baselines, but they remain efficient, with maximum total runtime of 37 seconds for DCA-L-S and ~ 71 seconds for DCA-LS-LASSO, for solving the problem for all 6
26

---

Discrete and Continuous Difference of Submodular Minimization
1.2
Reconeyy Probabiiity
0.8
Eacimation Ervor
Suppoot 10
06
0.5
0.4
0.4
DCA-LS-LASSO -B-DCA LS
0.25
LASSO
0.4
0.5
0.0
14-
12
0.8
Reconey Prolsshiitty
Betimitioon Brror
10
0.8
Support Eutor
0.4
0.4
0.2
10
20
16
Ras
Rus
8.N
30
Becorey Probattity
Bathnatton Eevor
Support Ervor
20
0.6
0.6
10
0.4
0.4
10
15 20
6
6
SN
Ras
SN
Figure 5: Performance results, averaged over 100 runs, for integer compressed sensing experiments with 256: Varying m with 13 [0.05m] and SNR dB (top), varying SNR with 13 [0.05m] and m/n 0.5 (middle), and varying SNRaB with 26- 001nn] and m/r 0.5 (bottom).
values. In terms of total runtime (Figure 6), DCA-LS-LASSO is faster than DCA-LS in some regimes: at high SNR with m/n = 0.5(for SNR 2 6 with = 13, and SNR 2 9 with 26), and for m/n n E (0.35, 0.75) with SNR = 8, but slower in others. In terms of individual runtime per À (Figure 7), DCA-LS-LASSS is faster than DCA-LS for 2 0.01.
also note that DCA-LS-LASSO's total runtime increases significantly when m/n 2 0.75. This likely because for small values, the influence of the 4--nrrm regularizer in LASSO is minimal, so DCA-LS-LASSO effectively initialized with least-squares solution, which can be worse than the σ0 0 initialization used in DCA-LS. Inspecting the À values that yielded the best performance for both OCA-LS-LASSE and DCA-LS, we found that they were always 2 0.01. So restricting À to this range would not impact performance. In Figure 8, we plot the sum of running times for only À = 1, 0, 0.01 with S = 8. With this restriction, DCA-LS-LASSO's total runtime no longer increases at m/n / Z 0.75, and is actually lower than DCA-LS for all m/n.
27

---

Discrete and Continuous Difference of Submodular Minimization
o-0
00000
Tine (6)
Time
-ONP
10
0.4
(b)
00
10a
$0
10
(8)
Time (6)
10
10-1
10
10
SNN Rai
S.N.
(C)
(d)
Figure 6: Running times (log-scale), summed over all X values and averaged over 100 runs, for integer compressed sensing experiments with n 256: (a) Varying with s 13 and SNRan 8. (b) varying m with 26 and SNRaB 8, (c) varying SNRa with = 13 and m/n 0.5, and (d) varying SNR1B with 26 and m/n 0.5.
Time (4)
10
Time
10
10
DCA-LS
DCA/LS LASSO
10
(a)
(b)
Time (6)
Time (5)
10-
10
10-4
10
10
10
(c)
(d)
Figure 7: Running times (log-scale) for each X, averaged over 100 runs, for integer compressed sensing experiments with 256 and SNRaa 8: (a) m/n Rs 0.2 and 13, (b) m/n Ro 0.5 and 13, (c) m/n as 0.2 and 26, and (d)
m/n x 0.5 and = 26.
28

---

Discrete and Continuous Difference of Submodular Minimization
109
10"
9-0 1000
Time (8)
Time (6)
10-2
10-2
TONP
LASSO
DCA-LS
4
0.2
0.4
0.8
0.2
0.4
0.8
m /
n
(b)
Figure 8: Running times (log-scale), summed À 1,,.1, and averaged 100 runs, for integer compressed
sensing experiments with 256: (a) Varying with 13 and SNRBB 8, and (b) varying with 26 and SNRBB 8.
29

---

Discrete and Continuous Difference of Submodular Minimization
I. DCA Variants Comparison
As discussed in Section 4.2, El Halabi et al. (2023) proposed two variants of standard DCA (9) for the special case of
Problem (I), where F is set function (X' {0. 1)"). Both monotonically decrease the objective F (up to 6,) and converge local minimum. In this section, we extend the more efficient of the two variants (Algorithm 2 therein) general discrete domains and compare it with proposed DCA variant (DCA-LS; Algorithm 1). We refer to this extension DCA-Restart, and present it in Algorithm 2.
Algorithm 2 DCA with restart
1: 2 0, é 2 e, 7 N, X [0, 11 (]1x(1111)
2: out=-,.... do
3: Choose Y (X*) (preferably corresponding to row-stable permutation)
4: X argmin, x xe(o.11;*(61) (X) - (Y X)F
5:
if f(x') - f(x++)) < then
x {0, 10, (xx((x1) then
6:
x' O(x"(
8:
else
9:
x' Round (X')
10:
end if
11:
ø' E argmin (ut) F(x)
12:
if F(x') S F(+)) + then
13:
Stop.
14:
else
15:
X = -x')
end if
end if
18: end for
Theoretical comparison Similar to the set function variant, DCA-Restart runs standard DCA (9) and, at convergence, checks if rounding the current iterate yields an approximate local minimum of F. If not, restarts from the best neighboring point. We show in Theorem I.1 that DCA-Restart satisfies the same theoretical guarantees DCA-LS (see Theorem 4.5). In particular, it also recovers the guarantees of El Halabi et al. (2023) in the special case of set functions.
Theorem I.1. Let {X*), fœ²} } be generated by Algorithm 2, where the subproblem on line 4 is solved up to accuracy cg 2 0.
For all E [T], 2 0, é' 2 we have:
a) ((X(1) 5(x) Eg.
b) Let (p,9) be the permutation used compule Yt in Proposition 2.3-e, and (k-1)m the vectors corresponding g), defined in Definition 2.2. If (p, q) is row-stable and ((xt)=f(X") Ji=0
then
F(x") S F(y") + + t for all i [0 (I: 1)m].
c) Algorithm 2 converges to an cllocal minimum of F after at most (f(x)) f*)/c iterations.
Proof. Note that between each restart (line 15), Algorithm 2 is simply running standard DCA (9), so Proposition 2.5 applies.
a) This holds between each restart by Proposition 2.5-a. Whenever the algorithm restarts, we have F(F*) < F(x*) e', i.c. x' is not an elloca minimum. In this case, we have
f(x++1) F(#') < F(xx)) -
(by Proposition 2.3-a)
< <((X)-- -
(by Proposition 2.3-a,c)
(48)
30

---

Discrete and Continuous Difference of Submodular Minimization
b) If - I e, then by Proposition 2.5-b, have Y de+e. ( nax()) If (p. g) is row-stable, then by definition of y². (p:g) q) is a common non-increasing permutation for X and Q (y'), for all i [0 (k 1)]] Hence, Y' E (1(())(1)))) by Proposition 2.3-e, and thus Y E (D+te.(((t)) - Therefore,
F f(x')
(by Proposition 2.3-a,c)
$ ff(0 +
(by Proposition 2.4)
Fly') t
(by Proposition 2.3-a)
for any E [(A: 1)m].
c) For any iteration & [7]. if the algorithm did not terminate, then either f(xx) f(X or F(*')< F(x*) é. In the second case, the algorithm restarts, then by Equation (48) we have f(Xt) f(X++) 2 since é' 2 We therefore have F(=")= - F(x') 2 tc, hence t < (f(x²) - /e. If the algorithm did terminate, then x' must be an é'llocal minimum of F.
DCA-Restart has similar computational cost per iteration as DCA-LSS. The only difference is that DCA-LS has an additional cost per iteration of O(nEOF) for the local search step (line 3) and O(nk) map X x++1 (line 8). In DCA-Restart, these operations are only done at convergence (f(X)) f(x*+1) I e), which in the worst can occur at every iteration. However, these differences have little impact the overall per-iteration cost, which is dominated by the cost of solving the subproblem. Indeed, the total cost per iteration in DCA-Restart is ((n(kL E + nk EO the same as in
DCA-LS. Moreover, the number of iterations for both variants is at most (f(x²) - f*) So, theoretically, both variants have very similar theoretical guarantees and runtime.
Empirical comparison We empirically compare DCA-LS to DCA-Restart on all experiments included in the paper. We use the same parameters T' and e, and the same subproblem solver (pairwise-FW) in DCA-Restart in DCA-LS; see Appendix G for how these set in each experiment. We choose e' 0, i.e., x' should be an exact local minimum if stops before reaching the maximum number of iterations. We also choose row-stable permutation (p, q) when computing Y
We report their performance on integer least squares (ILS) in Figure 9 and corresponding running times in Figure 10. Similarly, Figure 13 and Figure 14 show their performance and running times on integer compressed sensing (ICS). We also plot the number of DCA outer and inner iterations for ILS in Figures 11 and 12 and for ICS in Figures 16 and 17. The reported numbers of DCA inner iterations are the total number of inner iterations, i.e., iterations of pairwise-FW, summed over all outer iterations t. For ICS, the reported numbers of iterations and rumning times correspond to the sum over the 6 values of À tried, À = o.,, .., 10-5, We also report the running time for each X separately m/n as 0.2 and 0.5 (m = 50 and m = 123, respectively) with SNR = 8 in Figure 15. All results are again averaged over 100 runs, with error bars for standard deviations.
We observe that DCA-LS matches or outperforms Res-Restart on all experiments. The two variants perform similarly when initialized with a good solution (LASSO ICS, RAR in ILS); otherwise, DCA-LS performs better, sometimes by a large margin (see 4th row in Figure 13). In terms of runtime, DCA-Restart is generally faster both IIS and ICS. For both applications, DeA-Restart takes slightly more outer iterations to converge, but has lower per-iteration runtime, as evidenced by its smaller number of inner iterations. Intuitively, we expected each step of DCA-LS to decrease the objective more than in DCA- Restart, because of its more careful permutation choice, and thus to converge faster. In practice, this choice seems to lead to better solutions in some cases, but not significantly faster convergence, and comes at the cost of increased subproblem complexity. The slower convergence of pairwise-FW in DCA-LS may be due to the subgradients Y changing more between consecutive iterations, causing the subproblem's solution to vary more, and thus take longer to solve, given that we warm-start pairwise-FW with the previous iteration's 's solution. Overall, the choice between the two variants is problem dependent; for example, whether good initialization is available.
31

---

Discrete and Continuous Difference of Submodular Minimization
0.00
0.9
0.050
Howray Probabiity
Bi Error Itle
0.04
0.8
0.7-
0.03
0.4
(F())
0.3
0.4
DCA-LS Restant
0.01
0.3
0
0
1.2
1.4
1.6
1.8
1.2
1.4
1.6
1.8
1.2
14
1.6
1.8
10
0.04
Recweey Probabsiity
08
0.58
(F F(x)))/FPtt
Bis Erzoz Hade
0.6
0.02
0.4
0.4
0.01
0.2
+DDCA-SS O DCC-RReeer
0
1.
1.6
1.8
1.6
/
0.25
Recoeeyy Probalaity
0.8
(P(8) ((F
Bit Error Bate
0.2
0.4
0.1
0.05
+-DCNLS O-DCA-Revtrl
15
20
50
SN Rue
SNR
9NN Rus
0.25
0.3
0.2
Becoery Probatiity
(P(() ((()))
Bis Error Base
0.6
0.15
0.1
0.2
0.06
-0.2
--DCA-LS D-DCA-Rcstar
0
00.3
15
20
25
30
20
SN Rue
SNN
SN RNu
Figure 9: Performance results, averaged over 100 runs, for integer least squares experiments comparing two DCA variants:
Varying m with 100 and SNR 8 (first row), varying with 400 and SNR (second row), varying SNR with 100 (third row), and varying SNRaB with = 400 (fourth row).
32

---

Discrete and Continuous Difference of Submodular Minimization
DCAALS IXCA-Reston
2
1004
1.5
Tiue
Time
40
0.3
(a)
(b)
100
Time (4)
Thoo (x)
50
15
20
25
30
15
20
25
30
S.N Ran
8NN
(c)
(d)
Figure 10: Running times, averaged over 100 runs, for integer least squares experiments comparing two DCA variants: (a) Varying m with n 100 and SNRaB = 8, (b) varying m with 400 and SNRaB = 8, (c) varying SNRaB with m n 100, and (d) varying SNR with m = n 400.
Reeste
30
Ieerstons
[terations
20
15
2-
5
1.8
(a)
(b)
15
400
10
Iserations
Deeradoos
30
10
15
20
25
30
15
20
25
30
SN
SN Rai
(c)
(d)
Figure 11: Number of DCA iterations, averaged over 100 runs, for integer least squares experiments: (a) Varying m with
n = 100 and SNRaB 8, (b) varying m with n 400 and SNR 8, (c) varying SNR with m = n 100, and (d)
varying SNRB with m = n 400.
33

---

Discrete and Continuous Difference of Submodular Minimization
DCA-LS DCA Restart
8000g
Iterations
Iterations
G00D
4000
2000
1.2
1.6
1.4
11 /
(b)
110000
1200
100000
Luber Iterations
Iauer Iterstions
8000
8002
6000
400
200
2000
15
20
25
15
20
25
30
SMR
(c)
(d)
Figure 12: Number of DCA inner iterations, summed over all outer iterations t, averaged over 100 runs, for integer least
squares experiments: (a) Varying m with n 100 and SNR = 8, (b) varying m with n = 400 and SNR = 8, (c)
varying SNRBB with m n 100, and (d) varying SNRaB with m = a 400.
34

---

Discrete and Continuous Difference of Submodular Minimization
1.r
14
Reowery Probelatitty
Essimation Ervor
10
0.8
0.6
0.5
Support
DCAJ ASLO --DCA
0.2
0.2
LASSO
0.2
0.4
0.6
0.8
0.2
0.4
0.5
0.8
0.2
044
0.0
0.8
m
m
1.2
000
Recovey Probaltiity
0.8
Eatimation Ervor
0.5
Support
1.
0.4
0.6
10
0.5
0.0
12
Recovey Probsshiity
0.8
Betimattoon Brvor
10
Support Ervor
0.4
0.4
0.2
16
Ras
S.N Rus
8.N
30
Beorery Probattity
Eatimaation Bevor
Support Ereor
20
0.6
0.6
10
0.4
0.4
10
15 20
5
6
16
RaP
SNN Rus
8N
Figure 13: Performance results, averaged over 100 runs, for integer compressed sensing experiments comparing two DCA variants with 256: Varying with 13 and SNR (first row), varying m with 26 and SNR 8 (second row), varying SNR,a with m/n 0.5 and 13 (third row), and varying SNR with m m/n 0.5 and = 26 (fourth row).
35

---

Discrete and Continuous Difference of Submodular Minimization
100
DCA-Rcvaet
DCA-LS
DCA-RsaanLASS DGS LS LASSO
50
Tian
409
20
m
(a)
(b)
60
50
Time
30
10
SN Ran
SN
(c)
(d)
Figure 14: Running times, summed over all À values and averaged over 100 runs, for integer compressed sensing experiments
comparing two DCA variants with 256: (a) Varying with 13 and SNRaB = 8, (b) varying m with 26 and SNRus 8, (c) varying SNR with 8 = 13 and m/n 0.5, and (d) varying SNRas with 26 and m/n = 0.5.
25
15
A-Reateri
DCALS DCA-ReHnALA5OO
10
16
Time
Time
10.
10
10
(a)
(b)
25
20
20-
Thme [3)
15
Time
10
10-2
10-2
(c)
(d)
Figure 15: Running times for each X, averaged over 100 runs, for integer compressed sensing experiments comparing two
DCA variants with n = 256 and SNR 8: (a) m/n Rs 0.2 and 26, and (d) m/n n 0.5 and s 26.
13, (b) m/n 0.5 and s 13, (c) m/n 0.2 and
36

---

Discrete and Continuous Difference of Submodular Minimization
90
DCA DCA-Reraxt
DCAJLS
DCA ResarnLASSO
DCALS-LASSO
70
Ieerations
Iveratoos
40
40
20
0.4
0.2
0.8
(a)
(b)
70-
80
6
50
Iteestions
30
Itecations
30
20
20-
10
SNN Rue
SNN Ruo
(c)
(d)
Figure 16: Number of DCA iterations, summed over all À values and averaged over 100 runs, for integer compressed sensing experiments with 256: (a) Varying with 13 and SNR 8, and (b) varying with 26 and SNR1B (c) varying SN with 13 and m/n n 0.5, and (d) varying SNR with 8 26 and m/ 0.5
101
10t
Inzeer Herations
Ianer Herration
102
DCA-Roor
DUA-LS
DCA-ReGasLAASO
DCAJI S-1 AS9O
10
10a
0.4
0.4
(a)
(b)
10
Janer Itecaiion
Inner Iterations
10a
10a
10a
10a
10
0
10
15 20
SN
(c)
(d)
Figure 17: Number of DCA inner iterations (log-scale), summed over all outer iterations t and all À values, averaged over 100 runs, for integer compressed sensing experiments with n = 256: (a) Varying m with s = 13 and SNR = 8, and (b) varying m with 26 and SNR 8, (c) varying SNRI with s 13 and m/n 0.5, and (d) varying SNR with 26 and m m/n 0.5.
37


Reviews:
[{"review_id": "BI3xM6eML0", "reviewer": "Reviewer_Ecvy", "summary": "The paper investigates the minimization of difference-of-submodular (DS) functions over both discrete (products of finite sets) and continuous (products of intervals) domains. The authors establish that every function on a discrete domain and every smooth function on a continuous domain admits a DS decomposition.\n\nFor DS minimization over discrete domains, they show that the problem can be reduced to the case of having an integer lattice as domain. In the continuous setting, they approximate the problem by discretization and then reducing it to the integer lattice case approximatively. The key result is that DS minimization on an integer lattice is equivalent to minimizing a continuous extension (generalizing the Lovász extension), enabling the use of a difference-of-convex (DC) algorithm. This algorithm monotonically decreases function values and converges to a local minimum.\n\nThe authors validate their approach with experiments on integer least squares and integer compressive sensing, demonstrating improved performance over state-of-the-art methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and helpful feedback.  We address below your comments and questions.\n\n---\n**1 - Extension of theoretical guarantees to continuous domains**\n\nTheorem 4.5 extends to continuous domains as follows:\\\nLet $F'$ be defined as in Section 4.1, i.e., $F'(x) = F(x/(k-1))$ where $k = \\lceil L/\\epsilon' \\rceil + 1$ for some $\\epsilon'>0$. Let $\\tilde{x}^t = x^t/(k-1)$, where $x^t$ are Algorithm 1's iterates for $F'$. Then:\\\na) $F(\\tilde{x}^{t+1}) \\leq F(\\tilde{x}^t) + \\epsilon_x$\\\nb) At convergence: $F(\\tilde{x}^t) \\leq F(y^i/(k-1)) + \\epsilon + \\epsilon_x$ for all $i$. In particular, $F(\\tilde{x}^t) \\leq F(\\tilde{x}^t \\pm e_i/(k-1)) + \\epsilon + \\epsilon_x$.\\\nc) Number of iterations is at most $(F(\\tilde{x}^0) - F^*)/\\epsilon$. \\\nHowever, the second guarantee in (b) is meaningful only if $\\epsilon' > \\epsilon + \\epsilon_x$, as Lipschitz continuity of $F$ already implies $F(\\tilde{x}^t) \\leq F(\\tilde{x}^t \\pm \\tfrac{e_i}{k-1}) + \\epsilon'$. We will clarify this in the paper. \n\n---\n**2- Define \"best\" DS decomposition and clarify its infeasiblility** \n\nBy best DS decomposition, we meant the one with the tightest $\\alpha$ or $L_F$ in the proofs of Propositions 3.1 and 3.3. On lines 243-245 (1st col), we cite a reference showing that computing a tight $L_F$ is exponential hard. Computing the tightest $\\alpha$ also has exponential complexity, even for set functions. Indeed, we can test if $F$ is submodular, which has exponential complexity (Seshadhri & Vondrák, 2014), by computing $\\alpha = \\min_{i, j \\in V, S \\subseteq V \\setminus \\{i, j\\}} F(S \\cup i) - F(S) - F(S \\cup \\{i, j\\}) + F(S \\cup j)$ and checking if $\\alpha \\geq 0$. We will clarify this in the revision.\n\nLike DC functions, DS functions have infinitely many DS decompositions. Finding the \"best\" one is an even more difficult question, as it's unclear how to define \"best\". Thank you for the suggested reference, we will cite it. \n\nSeshadhri, C., & Vondrák, J. (2014). “Is submodularity testable?” Algorithmica, 69(1), 1-25.\n\n---\n**3- Impact of loose bounds on $\\alpha$ and $\\beta$**\n\nLooser bounds on $\\alpha$ and $\\beta$ lead to a DS decomposition where the continuous extensions of $G$ and $H$ have larger Lipschitz constants,slowing down optimization. As discussed in Section 4.2 (\"Computational complexity\"), the runtime of Algorithm 1, particularly for solving the submodular minimization at each iteration $t$, depends on the Lipschitz constant* $L_{f^t_\\downarrow}$ of $f^t_\\downarrow$, the continous extension  of $F^t = G - H^t = F + \\frac{\\alpha}{\\beta} \\tilde{H} - \\tilde{H}^t$. Here, $\\tilde{H}^t(x) = \\frac{\\beta}{\\alpha} H^t(x)$ is a modular approximation of $\\tilde{H}(x)$ satisfying $\\tilde{H}(x) \\geq \\tilde{H}(x^t) + \\tilde{H}^t(x) - \\tilde{H}^t(x^t)$. We can lower bound $L_{f^t\\_\\downarrow}$ by the Lipschitz constant of $F^t$: $L\\_{f^t_\\downarrow} \\geq \\max\\_{x, x'} \\frac{|F^t(x) - F^t(x')|}{\\\\|x - x'\\\\|\\_1}$. For example, for a non-decreasing function $F$ and $x  \\leq x'$, \ntaking $x' = x^t$ gives $|F^t(x) - F^t(x')| = |F(x) - F(x^t)| + \\frac{|\\alpha|}{\\beta} |(\\tilde{H}^t(x) - \\tilde{H}^t(x^t)) - (\\tilde{H}(x) - \\tilde{H}(x^t))|.$ Thus, a larger $\\frac{|\\alpha|}{\\beta}$ yields a larger $L_{f^t_\\downarrow}$. We will clarify this in our revision.\n\n*Typo on line 373: $L_{F^t_\\downarrow} \\to L_{f^t_\\downarrow}$\n\n---\n**4- Revise the sentence on line 241 (right) to be more accurate.**\n\nWe will revise the sentence to: \"We show in Appendix A.2 that the natural DS decomposition in both applications is not a discrete DC decomposition as defined in (Maehara & Murota, 2015) and cannot be easily adapted into one for general discrete domains, even when ignoring the integer-valued restriction.\" \n\n---\n**5- Theoretical results seem straightforward extensions of existing work**\n\nSee our response to **Reviewer eVr5 (4th item)**, where we clarify the novel aspects of our theoretical results.\n\n---\n**6- Why is the direct approach better than set function reduction?**\n\nAs discussed in (Bach, 2019, section 4.4), reducing a submodular function $F$ to a submodular set function $\\tilde{F}$ leads to slower optimization due to the larger Lipschitz constant $L_{\\tilde{f}\\_\\downarrow}$ of the continuous extension $\\tilde{f}\\_\\downarrow$  of $\\tilde{F}$. Specifically, while we can bound $L_{f\\_\\downarrow} \\leq \\sqrt{n k} \\max\\_i B_i$, the bound for $\\tilde{f}\\_\\downarrow$ is $k$ times larger, i.e., $L_{\\tilde{f}\\_\\downarrow} \\leq k \\sqrt{n k} \\max\\_i B_i$, where $B_i$ is defined in Eq. (26) in Appendix B.  \nThis affects submodular minimization algorithms in both (Bach, 2019) and (Axelrod et al., 2020), as their complexity scales with the Lipschitz constant. For example, Bach's algorithms have complexity $\\tilde{O}((\\frac{n k L_{f_\\downarrow}}{\\epsilon})^2 \\textnormal{EO}_F)$ when applied directly to $F$. Using the reduction to $\\tilde{F}$, this increases by $O(k^2)$ factor.\n\n---\nThank you for your other suggestions. We will incorporate them in our revision.", "claims_and_evidence": "The main claims of the paper are:\n- Any function on a discrete domain and any smooth function on a continuous domain can be expressed as a DS function.\n- One can (approximately, in the continuous case) reduce the problem to an integer lattice domain.\n- Minimizing a DS decomposition over an integer lattice domain is equivalent to minimizing a continuous extension.\n- The algorithm computes an approximate local minimum.\n- Applying a DC algorithm to integer least squares and integer compressive sensing improves performance over existing methods.\n\nThe first three claims are theoretical and well-supported. The paper also discusses the computational complexity and the theoretical guarantees of the algorithm’s output, which appear to be correct. The experiments further support the empirical claims.\n\nBelow are some minor issues:\n\n- It is not entirely clear whether the theoretical guarantees extend to a DS function over a continuous domain after discretization. While the single results put together suggest this should be the case, the paper would benefit from a formal theorem stating: The algorithm finds a local optimum with guarantee G in time T for the class of DS functions C.\n\n- The paper asserts that finding the best DS decomposition is generally infeasible, but it does not define what constitutes the \"best\" decomposition, nor does it provide strong support for this claim. The authors could strengthen this point by referencing literature.\n\n- After Proposition 3.1, the paper states: \"Obtaining tight lower bounds α and β in the above proof requires exponential time in general\" and \"Note that loose bounds on α and β would degrade performance.\" Both claims lack supporting argumentation. A brief explanation or reference would help clarify these statements.\n\n- On line 241 (right), the sentence \"We show in Appendix A.2 that both applications do not have a natural discrete DC decomposition.\" seems overly strong, as the authors only prove that a specific decomposition is not DC. A more precise formulation would improve accuracy.", "methods_and_evaluation_criteria": "The chosen problems (integer least squares and integer compressive sensing) to evaluate the performance of the proposed algorithm and the selected metrics (recovery probability and estimation error) appear reasonable. The competing algorithms seem to represent the state of the art, but I am not deeply familiar with the field or these specific methods.", "theoretical_claims": "The theoretical results appear sound and well-supported, and the proof sketches are reasonable. However, I did not verify all the proofs in detail.", "experimental_designs_or_analyses": "I read the experimental setup in the main paper and it appeared sound to me. But I did not validate any technical details and I am not an expert neither of the problems nor the methods.", "relation_to_broader_scientific_literature": "The paper is well-grounded in the existing literature and acknowledges prior results and ideas upon which it builds.", "essential_references_not_discussed": "As discussed in the Claims and Evidence section, the paper asserts that finding the best DS decomposition is generally infeasible, but it does not connect this claim to existing literature. The authors could reference works such as Decomposition Polyhedra of Piecewise Linear Functions (https://arxiv.org/abs/2410.04907), which explores the complexity of DS and DC decompositions.", "other_strengths_and_weaknesses": "I appreciate the idea of relating general DS functions to a DC function, and it is interesting that this approach seems to work better in practice than reducing the problem to the set function case and minimizing the Lovász extensions via a DC algorithm, as illustrated in the appendix. This together with the experiments showing better performance than exisiting methods for DS functions makes the paper a valuable contribution.\n\nFrom a theoretical perspective, the results don’t seem particularly profound, as they appear to be a straightforward extension of existing knowledge.", "other_comments_or_suggestions": "There are statements in the main paper where the proofs are deferred to the appendix, but no links are provided to direct the reader to the relevant proofs. As a result, readers must search through the appendix to find the proofs, even for key results such as Proposition 4.4 and 4.5. Including hyperlinks would make the paper more reader-friendly.\n\nFurther suggestions:\n\n- It would be helpful to define what a subgradient is.\n\n- For the definition of round, it could be clarified that the goal is to obtain the vector, not the index. This is only clear from the context, but the definition itself is somewhat ambiguous.\n\n- Providing some intuition and perhaps including a small illustration of an epsilon-subdifferential would be beneficial.\n\n - A sentence or two following Proposition 2.5, explaining the implications of the statement on the theoretical guarantees of the algorithm, would make it easier to understand its significance.", "questions_for_authors": "- Can you think of any theoretic justification why the attempt of translating the DS problem directly to a DC problem works better than reducing first to the set function case?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lRIEJo4PcV", "reviewer": "Reviewer_3rHC", "summary": "The minimization of a difference of submodular functions is studied, in a discrete and continuous setting. The discrete setting is more like a lattice that generalizes set optimization. A variant of the DC algorithm is developed that uses local search ideas. Experiments are performed to validate the algorithm.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We address below your questions.\n\n---\n\n**1- Distinguishing novel contributions from background**\n\nOur main contributions are outlined in the introduction (lines 61-74, 1st col). The DS minimization problem over general discrete and continuous domains $\\mathcal{X}$ (Problem 1) has not been studied before. Prior work only considered special cases, where $F$ is a set function ($\\mathcal{X} = \\{0,1\\}^n$), or is submodular ($H=0$). DS Minimization is significantly harder than submodular minimization, which is solvable in polynomial time, whereas even finding a local minimum or a polynomial approximation factor for DS minimization is provably hard. \n\nStandard DCA (Eq. 9) is not guaranteed to converge to an approximate local minimum, even for set functions (Section 4.2, lines 324- 333). Our DCA variant (Algorithm 1) differs by maintaining iterates for the original problem $x^t \\in [0:k-1]^n$, obtained by rounding the iterates of the relaxed problem $X^t \\in [0,1]_{\\downarrow}^{n \\times (k-1)}$, and by carefully choosing a subgradient $Y^t$ which ensures convergence to an approximate local minimum.\nFor further discussion on the technical novelty of our results, see our response to **Reviewer eVr5 (4th item)**. \n\n---\n\n**2-  Extension of the DR submodular reduction to DS functions & Cost of the submodular set function reduction and empirical comparison**\n\nThe reduction by Ene & Nguyen (2016) (line 092) applies only to DR-submodular functions, a subclass of submodular functions that are concave along nonnegative directions. For a DS function $F = G - H$, the submodular components $G$ and $H$ are not necessarily DR-submodular. \nThis reduction cannot be readily extended to general submodular functions. It relies on a carefully chosen map $M: \\{0,1\\}^t \\to [0:k-1]^n$, where $t \\leq 2 \\log k + 1 $, to construct an equivalent submodular set function $\\tilde{F}(X) = F(M(X))$ whose domain scales with $O(\\log k)$. when $F$ is not DR-submodular, $M$ does not preserve submodularity. \n\nWe discuss the general reduction for submodular functions (line 317) in Appendix B and compare its empirical performance. Our results show that the reduction approach is indeed slower than the direct approach used by Bach and us.\nSee also our response to **Reviewer Ecvy (6th item)** for a discussion of the theoretical complexity of the two approaches. \nWe will add a brief explanation in the main text.\n\n---\n\n**3- Relation to (El Halabi et al., 2023) & Theoretical and empirical comparison with their DCA variants**\n\nEl Halabi et al. (2023) study a special case of our DS minimization problem where $F$ is a **set** function ($\\mathcal{X} = \\{0,1\\}^n$); they do not consider continuous domains. \n\nThey proposed two DCA variants: One is infeasible, as it requires trying $O(n)$ subgradients per iteration, while the other (Algorithm 2 therein) restarts from the best neighboring point at convergence if the solution is not an approximate local minimum.\nBoth can be extended to general discrete domains similarly to our DCA variant. The main non-trivial change is the restriction of the permutation $(p,q)$ to be row-stable.\nOur DCA variant (Algorithm 1) instead selects a single subgradient using a local search step (lines 3-4), ensuring direct convergence to an approximate local minimum without restarts.\n\nOur theoretical guarantees (Theorem 4.5) generalize those of (El Halabi et al. 2023) to general discrete domains; recovering the same guarantees in the set function case. \n\nWe empirically compared our DCA variant (DCA-LS) to an extension of the more efficient DCA variant from El Halabi et al. (2023) (DCA-Restart) on all  experiments included in the paper. \nWe report their performance on integer least squares (ILS) in [Figure 5](https://tinyurl.com/Rebuttal-Fig5) and  running times in [Figure 6](https://tinyurl.com/Rebuttal-Fig6). Similarly, [Figure 7](https://tinyurl.com/Rebuttal-Fig7) and [Figure 8](https://tinyurl.com/Rebuttal-Fig8) show their performance and running times on integer compressive sensing (ICS). We plot running times for all $\\lambda$ values at $m/n =0.5$ and $0.2$. \nDCA-LS matches or outperforms DCA-Restart on all experiments. The two variants perform similarly when initialized with a good solution (LASSO in ICS, RAR in ILS), otherwise DCA-LS performs better, sometimes by a large margin. \nIn terms of runtime, DCA-Restart is faster on ILS and for some $m/n$ values in ICS, e.g., $m/n=0.5$, but slower for others, e.g., $m/n=0.2$. Thus, the choice between the two variants is problem dependent. \n\nWe will revise the paper to include these results and adjust the claim on line 343-344 (1st col), which originally stated that our DCA variant is more efficient than those in (El Halabi et al. 2023). This is only true for one of them. This claim was based on an earlier, less extensive comparison on an ICS experiment, where DCA-LS was both faster and performed better than DCA-Restart.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check. All proofs are relegated to appendix or results from other works.", "experimental_designs_or_analyses": "Yes. See strengths and weaknesses.", "relation_to_broader_scientific_literature": "Generalizes DS set function optimization to discrete domains of R^n. For continuous domains, there is a work of El Halabi et al. (2023). I'm unsure how the results in this paper are related to the former, although they do cite and discuss.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\n- Exposition is fairly easy to follow, even for someone unfamiliar with the area. Background and preliminary information goes until page 4. However, see weaknesses.\n- The problem setup is very general, which makes it difficult. Some natural applications are given, which motivate the work well.\n- The experimental results are convincing, although perhaps a natural baseline was left out. See weaknesses.\n\nWeaknesses:\n- Although much background information relevant to the problem studied is presented, I found it difficult to get a good idea of what is novel to this paper, and what is challenging about the variant that is studied. Such a good exposition of context is given that it becomes difficult to separate the contribution from the context. \nI think the algorithm developed (a DCA variant) is interesting. But I don't know enough to really judge its distance from standard DCA. The authors did not explain clearly was is different.\n- I didn't understand why the reduction discussed on line 092 for DR submodular functions, could not be extended to the case of DS functions on discrete domains. And then existing techniques from DS set optimization applied. A related issue is the reduction mentioned on line 317. The authors state that this reduction (line 317) is more expensive, but no justification is given in the main text. Also, I don't think the authors compared with this approach experimentally.", "other_comments_or_suggestions": "- Line 208: funcion -> function\n- Line 167: us -> use\n- The writing style is generally fine but it is a little informal. I kind of like that, because it means it wasn't written by an AI. But still, there were multiple examples of incomplete sentences (often starting with \"Though\"). Though is an informal shortening of although, and starts a subordinate clause that needs to be paired with a main clause. As in: \"Although I like cats, I like dogs better.\"", "questions_for_authors": "- See strengths and weaknesses.\n- Is the algorithm of El Halabi et al. (2023) compared, either theoretically or empirically? As this is also a variant of DCA, shouldn't it be a natural baseline?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "21NnNImVgg", "reviewer": "Reviewer_yXuG", "summary": "This paper considers the minimization of a difference of submodular functions (DS) in both the continuous and discrete domains. Unlike the submodular minimization problem, which can be solved in polynomial time, this problem cannot even be approximated efficiently. This paper accomplishes two main things: (i) It shows how broad the class of DS functions are by proving that many existing functions can be represented this way, although it is computationally hard to find a representation, and (ii) It provides an algorithm and proves that the algorithm returns an approximate local minimum (even finding a true local minimum is computationally hard. This algorithms builds upon the fact that the continuous extension of DS functions via their Lovasz extension is a difference of convex functions for which the DCA algorithm exists. This paper proposes a modified variant of the DCA algorithm. Finally, they include an experimental section where they compare their algorithm to existing alternatives on two different applications.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review. We will improve the writing of the introduction.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not thoroughly check correctness, but I did not notice any issues.", "experimental_designs_or_analyses": "Yes, the experiments looked reasonable to me.", "relation_to_broader_scientific_literature": "This paper is related to several existing related works that have studied special cases of this problem, e.g. Narasimhan and Bilmes [2005]. This work is of interest to the submodular optimization community.", "essential_references_not_discussed": "I did not notice any missing essential references.", "other_strengths_and_weaknesses": "Strengths\n- I think their problem statement is interesting, and even though it's minimization I think it is related to submodular maximization applications as well. In particular, I wonder if summarization objectives commonly found in submodular maximization papers where there is a diversity penalty can also be viewed in this sort of problem statement.\n- The problem is computationally challenging, but they were able to develop an algorithm that finds an approximate local optimum efficiently. This is an interesting type of algorithm, and maybe could be applied more broadly.\n- Their result is connected with convex optimization, and they build upon the existing DCA algorithm.\n- They provided an experimental section.\n\nWeaknesses\n- The algorithm may not be extremely novel, but this is fine in my opinion.\n- Some of the writing, in particular in the introduction, was a bit hard to interpret. E.g. \"developed algorithms for this special case, that monotonically decrease the objective value\" I did not understand when reading the introduction.", "other_comments_or_suggestions": "None", "questions_for_authors": "None", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ewVdZxekAp", "reviewer": "Reviewer_eVr5", "summary": "Submodular functions are commonly studied as set functions, which can be viewed as functions defined on the vertices of the hypercube $ \\\\{ 0,1 \\\\}^n$.   This paper, however, similar to some prior literature, considers an extension of submodularity, where functions are defined over cartesian products of compact subsets of $\\mathbb{R}$. They study the problem of minimizing the difference of these generalized submodular functions. For discrete domains, they propose an algorithm to solve DS via a reduction to integer lattice domains followed by their variant of DCA (difference of convex functions minimization algorithm), which converges to a local minimum at a rate of $O(1/k)$. They claim that with discretization, the same method applies to continuous domains as well.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback. We address below your comments and questions.\n\n---\n\n**1- Explain the claim \"The results can be easily extended to unequal $k_i$'s\"**\n\nThe extension to unequal k_i’s follows directly, though the notation becomes more cumbersome. The key modifications are:\\\n\t- The relaxed domain (i.e., the domain of the DC program in Eq. (11)) changes to $\\prod_{i=1}^n [0,1]\\_{\\downarrow}^{k_i -1}$.\\\n\t- The map $\\Theta$ is adjusted to map from $\\prod_{i=1}^n \\\\{0,1\\\\}\\_{\\downarrow}^{k_i -1}$ to $\\prod_{i=1}^n [0:k_i-1]$, with a similar definition.\\\n\t- The continuous extension is now defined on $\\prod_{i=1}^n \\mathbb{R}^{k_i -1}$, and the summation in Eq. (6) runs from $1$ to $\\sum_{i=1}^n (k_i - 1)$.\n\n---\n\n**2- Comparison with the DCA variants of El Halabi et al. (2023)**\n\nPlease refer to our response to **Reviewer 3rHC (3rd item)**, where we include a clear comparison between the DCA variants.\n\n---\n\n**3- The paper is hard to follow.**\n\nWe understand that the technical overhead may be challenging for readers, and we are happy to revise the paper to improve accessibility. Could you clarify which parts were hard to follow and suggest areas where clarity could be improved?\n\n---\n\n**4- This work appears to build on established ideas without introducing a significant departure from prior research.**\n\nAll reviewers seem to agree that the problem we address is interesting and well motivated, and that our results are valuable. We believe that achieving our results by extending existing results in a relatively simple way should not be seen as a weakness. \n\nThat said, we would like to clarify that while our results build on existing work, they did require novel ideas and proofs. In particular, the main challenges are the following:\n1. One factor that makes our results appear “straightforward” is the use of simpler and cleaner notation. \nFor example, we represent the input of the continuous extension as a matrix $X\\in [0,1]_{\\downarrow}^{n \\times (k-1)}$, instead of a list of vectors $X = (x_1, \\cdots, x_n) \\in [0: k-1]^n$ as in Bach and Axelrod. This change significantly simplified the presentation of the results. \n2. While the proof that any function on a discrete domain is a DS function (Proposition 3.1) is a straighforward extension of the set function result in (Iyer & Bilmes, 2012), the analogous result for continuous domains (Proposition 3.3) required leveraging an alternative definition of submodularity and relating it to function smoothness. \n3. Extending DCA (whether our variant or those in (El Halabi et al., 2023)) from set functions to general discrete functions is non-trivial. It required restricting the non-increasing permutation $(p,q)$ of $X^t$ to be row-stable, to ensure that it's a non-increasing permutation of $\\{\\Theta^{-1}(y^i)\\}\\_{i=1}^{(k-1)n}$ too. This is essential to guarantee local minimality (see proof of Theorem 4.5-b). This is not needed in the set function case ($k=2$), where any non-increasing permutation of $X \\in \\mathbb{R}_\\downarrow^{n \\times (k-1)}$ is row-stable.\n4. Our proposed DCA variant (Algorithm 1) introduces a novel approach for selecting the subgradient using the local search step (lines 3-4), which ensures direct convergence to an approximate local minimum. This improves performance in some settings compared to the variant (extended to general discrete domains) proposed in (El Halabi et al., 2023). For further details, please see our response to **Reviewer 3rHC (3rd item)**.\n5. Identifying important applications (Section 3.2) that have natural DS decompositions but are not DC, and do not have easy discrete DC decompositions, was also non-trivial. It required exploiting properties of DC functions (e.g., in Proposition A.1) and discrete DC functions (see Section A.2).\n6. Showing that Lipschitz continuity is not necessary for bounding the discretization error for continuous domains, as in the case of the $\\ell_q$-norm (Proposition G.2), is novel and its proof is non-trivial. We  believe that this result could be generalized to other similar functions. \n\n---\n\n**5- Clarification on Theoretical Guarantees and Computational Complexity of DS Algorithm**\n\nOur full DS algorithm is presented in Algorithm 1. Its theoretical guarantees are given in Theorem 4.5, and its computational complexity is discussed in the corresponding paragraph in Section 4.2. \nThe algorithm applies DCA to the DC Problem (11) using the DC decomposition given at the beginning of paragraph \"Algorithm\", while also maintaining iterates $x^t$ as the solution to the original DS Problem (1).\nThe iterates $X^t \\in [0,1]_{\\downarrow}^{n \\times (k-1)}$ are updated with DCA updates (see Eq. (9)), while iterates $x^t \\in [0:k-1]^n$ are obtained by rounding (line 7). As explained, the rounding step can be skipped if the solution of the subproblem $\\tilde{X}^t$ is integral.", "claims_and_evidence": "Claims like \"The results can be easily extended to unequal $k_i$s\" need some explanation.", "methods_and_evaluation_criteria": "Overall, Methods and Evaluation criteria seems fine. \n\nThis paper builds upon \"Difference of Submodular Minimization via DC Programming\" by El Halabi et al., so it should include a clear comparison between its DCA variant and those of Halabi et al. in this setting.", "theoretical_claims": "The main body of the paper includes only proof sketches and high-level ideas. They seemed sound, but I was not able to verify their correctness.", "experimental_designs_or_analyses": "The experiments compare their proposed algorithm for integer least squares problem (a special case of quadratic programs) and integer compressive sensing problem (a special case of Sparse Learning) with appropriate baselines for the respective problem.", "relation_to_broader_scientific_literature": "This paper extends the result of the paper \"Difference of Submodular Minimization via DC Programming\" by El Halabi et al. (2023) to the setting proposed in the paper \"Submodular functions: from discrete to continuous domains\" by Bach.", "essential_references_not_discussed": ".", "other_strengths_and_weaknesses": "The paper is hard to follow.\n\nThis work appears to build on established ideas without introducing a significant departure from prior research.", "other_comments_or_suggestions": ".", "questions_for_authors": "To my understanding, the paragraph Computational Complexity in Section 4 discusses the complexity of your DCA algorithm.\nCould you please specify the theoretical guarantees of your DS algorithm as a whole?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2XSZHwwCxe", "reviewer": "Reviewer_o1eG", "summary": "This paper explores the minimization of the difference of submodular (DS) functions over both discrete and continuous domains, extending prior work that was restricted to set functions. The authors introduce a new variant of the DC Algorithm (DCA) to minimize DS functions, providing theoretical guarantees comparable to previous work in the set function case. The study demonstrates that DS functions naturally arise in applications such as quadratic programming and sparse learning. The proposed method outperforms existing baselines in integer compressive sensing and integer least squares tasks. Experimental results show significant improvements in recovery probability and error rates.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review and helpful feedback. We address below your comments and questions.\n\n---\n\n**1- Results on the proposed algorithm's running time**\n\nWe report the average running time of the compared methods on the integer least squares experiment (Section 5.1) in  [Figure 4](https://drive.google.com/file/d/1qG4rhu3aBCSAeWfOMx_QJna69vjvDxxM/view). The reported times for DCA and ADMM do not include the time for the RAR initialization, and for OBQ do not include the time for the relaxed solution initialization (which has similar time as RAR).\nWe observe that our algorithm is significantly faster that the optimal Gurobi solver, even for the small problem instance ($n=100$). For the larger instance ($n=400$), Gurobi is already too slow to be practical. While our algorithm is slower than heuristic baselines, it remains efficient, with a maximum runtime of $100$ seconds for $m=n=400$. We will include these plots and this discussion in the revision.\n\nThe primary focus of our experiments was to demonstrate that our algorithm outperforms state-of-the-art baselines on challenging problems, rather than optimizing its computational efficiency. For example, the most computationally intensive part of our algorithm is computing subgradients of the continuous extensions, which requires evaluating successive marginals $F^t(y^{i-1} + e_{p_i}) - F^t(y^{i-1})$. In our current implementation, we compute these marginals by doing separate calls to $F^t$. This can be significantly sped up by reusing computation from evalutating $F^t(y^{i-1})$ when computing $F^t(y^{i-1} + e_{p_i}). \n\n---\n\n**2- Relation to regularized submodular optimization [1][2]**\n\nThe problem studied in [1][2] is that of maximizing the difference between a submodular set function and a modular set function over constraints. Our problem setup does not consider constraints. But the unconstrained version of that problem is indeed a special case of DS **set** function minimization. We will cite works on unconstrained regularized submodular set function optimization in the revision.", "claims_and_evidence": "The claims in the paper appear well-supported both theoretically and experimentally, with no evident problematic claims.", "methods_and_evaluation_criteria": "I think the proposed methods and evaluation criteria make sense for the problem and application at hand. The problem of minimizing the difference of submodular functions (DS functions) in both discrete and continuous domains is a well-defined and important one in optimization, with practical applications in areas like quadratic programming, sparse learning, and compressive sensing.", "theoretical_claims": "I have conducted a preliminary review of the theoretical proofs in the paper, and they appear to be correct. However, I should note that my examination was not exhaustive, and there remains a possibility that some details may have been overlooked.", "experimental_designs_or_analyses": "The authors should include more results regarding the running time of their algorithm to better demonstrate its efficiency.", "relation_to_broader_scientific_literature": "The problem addressed in this paper may be related to regularized submodular optimization, which involves optimizing a submodular function that is regularized by subtracting a linear or convex function [1][2].\n\n[1] Kazemi, Ehsan, et al. \"Regularized submodular maximization at scale.\" International Conference on Machine Learning. PMLR, 2021.\n\n[2] Cui, Shuang, et al. \"Constrained subset selection from data streams for profit maximization.\" Proceedings of the ACM Web Conference 2023. 2023.", "essential_references_not_discussed": "Please refer to the above.", "other_strengths_and_weaknesses": "N.A.", "other_comments_or_suggestions": "N.A.", "questions_for_authors": "Please refer to the above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies how to minimize a difference of submodular functions on discrete and continuous domains that go beyond the standard set function case. The authors provide a DC-type algorithm, which is natural for this problem, but nevertheless novel. The algorithm is analyzed theoretically and empirically.
Most of the reviewers agree that this is a solid contribution to ICML, with the more knowledgeable reviewers being the more positive ones. I therefore support this sentiment and recommend acceptance.
I urge the authors to take reviewer feedback seriously and revise the paper accordingly.
Decision: Accept (poster)