Discrete and Continuous Difference of Submodular Minimization

Thank you for your positive review and helpful feedback. We address below your comments and questions.

1- Results on the proposed algorithm's running time

We report the average running time of the compared methods on the integer least squares experiment (Section 5.1) in Figure 4. 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). We 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.

The 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}).

2- Relation to regularized submodular optimization [1][2]

The 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.

Thank you for your valuable feedback. We address below your comments and questions.

1- Explain the claim "The results can be easily extended to unequal $k_i$'s"

The extension to unequal k_i’s follows directly, though the notation becomes more cumbersome. The key modifications are:
- 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}$.
- 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.
- 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)$.

2- Comparison with the DCA variants of El Halabi et al. (2023)

Please refer to our response to Reviewer 3rHC (3rd item), where we include a clear comparison between the DCA variants.

3- The paper is hard to follow.

We 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?

4- This work appears to build on established ideas without introducing a significant departure from prior research.

All 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.

That 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:

1. One factor that makes our results appear “straightforward” is the use of simpler and cleaner notation. For 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.
2. 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.
3. 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.
4. 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).
5. 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).
6. 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.

5- Clarification on Theoretical Guarantees and Computational Complexity of DS Algorithm

Our 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. The 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). The 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.

Thank you for your positive review. We will improve the writing of the introduction.

Thank you for your valuable feedback. We address below your questions.

1- Distinguishing novel contributions from background

Our 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.

Standard 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. For further discussion on the technical novelty of our results, see our response to Reviewer eVr5 (4th item).

2- Extension of the DR submodular reduction to DS functions & Cost of the submodular set function reduction and empirical comparison

The 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. This 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.

We 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. See also our response to Reviewer Ecvy (6th item) for a discussion of the theoretical complexity of the two approaches. We will add a brief explanation in the main text.

3- Relation to (El Halabi et al., 2023) & Theoretical and empirical comparison with their DCA variants

El 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.

They 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. Both 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. Our 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.

Our 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.

We 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. We report their performance on integer least squares (ILS) in Figure 5 and running times in Figure 6. Similarly, Figure 7 and Figure 8 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$. DCA-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. In 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.

We 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.

Thank you for your positive review and helpful feedback. We address below your comments and questions.

1 - Extension of theoretical guarantees to continuous domains

Theorem 4.5 extends to continuous domains as follows:
Let $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:
a) $F(\tilde{x}^{t+1}) \leq F(\tilde{x}^t) + \epsilon_x$
b) 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$.
c) Number of iterations is at most $(F(\tilde{x}^0) - F^*)/\epsilon$.
However, 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.

2- Define "best" DS decomposition and clarify its infeasiblility

By 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.

Like 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.

Seshadhri, C., & Vondrák, J. (2014). “Is submodularity testable?” Algorithmica, 69(1), 1-25.

3- Impact of loose bounds on $\alpha$ and $\beta$

Looser 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'$, taking $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.

*Typo on line 373: $L_{F^t_\downarrow} \to L_{f^t_\downarrow}$

4- Revise the sentence on line 241 (right) to be more accurate.

We 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."

5- Theoretical results seem straightforward extensions of existing work

See our response to Reviewer eVr5 (4th item), where we clarify the novel aspects of our theoretical results.

6- Why is the direct approach better than set function reduction?

As 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.
This 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.

Thank you for your other suggestions. We will incorporate them in our revision.