- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper examines the expressivity and exact optimization of deep submodular functions (DSFs). It identifies expressivity limitations that persist regardless of depth and establishes two structural regimes for exact cardinality-constrained maximization. It also shows how extending the composition rules enables the representation of all normalized monotone submodular functions, with potentially exponential size. Synthetic experiments and applications to feature and data selection illustrate the optimization results.
Critical strengths
S1: The paper explicitly shows that the curvature obstruction and optimization hardness depend on different graph properties, with and bipartite examples going in opposite directions.
S2: Pairing the junction-tree algorithm with a matching ETH lower bound is more than an upper bound alone, and the disjoint-support regime is a meaningful case that stays tractable even at high width.
Critical weaknesses
W1: The novelty is limited, as several key results look like adaptations of standard tools. For instance, the CP-Hessian result appears to follow from the chain rule, the odd-cycle characterization seems to come directly from classical results that CP and DNN cones coincide for graphs with no odd cycle of length ≥ 5 (Kogan & Berman; Berman & Shaked-Monderer). Moreover, junction-tree DP for bounded treewidth, and ETH lower bounds via standard reductions, are well-known techniques.
W2: Accuracy gains over stronger baselines are mixed. Group caps improve markedly over modular selection on ISOLET, but remain below dense pairwise selection at all three reported budgets. The corresponding paired intervals include zero or reach zero. On HAR at k=40, group caps reduce to the modular candidate and underperform the random-group mean. These results suggest dataset- and budget-dependent usefulness rather than consistent superiority.
W3: The writing is dense and the paper tries to do too much. It packs expressivity, two complexity regimes, a hardness bound, a universality construction and three experiments into the main text, which pushes most of the substance into the appendix. Undefined acronyms, such as CP, effective support, modular tail, in the abstract make it hard to read.
Questions for authors
NA.
3 comments
Response to Reviewer 9WEr (Part 2/2)
W2 Accuracy against stronger baselines
W2. Accuracy gains over stronger baselines are mixed. Group caps improve markedly over modular selection on ISOLET, but remain below dense pairwise selection at all three reported budgets. The corresponding paired intervals include zero or reach zero. On HAR at k=40, group caps reduce to the modular candidate and underperform the random-group mean. These results suggest dataset- and budget-dependent usefulness rather than consistent superiority.
Response
We add a stronger exactly solvable objective in the revision, which restructures trained DSFs into disjoint trees. These trees exceed dense pairwise selection on HAR with paired intervals above zero, and they attain at least its accuracy at all six budgets. Group caps are the simplest objective in the disjoint regime, with one cap per group. Section 6.2 uses them to show that learned groups capture redundancy while keeping exact solvability. The restructured trees keep this exactness and add learned nonlinear interactions. To build them, we fit depth-2 DSFs with overlapping supports to training-split subset utilities. We then group features by the negative Hessian of each fit and refit a disjoint computation tree on these groups. The comparison in Table R1 shows three results.
- HAR: The trees exceed dense pairwise selection by 3.28, 8.75 and 3.90 points, with all three intervals above zero. At , where group caps and dense pairwise selection both reduce to the modular candidate, the tree is 8.75 points above both.
- ISOLET: The trees match dense pairwise selection at all three budgets, with differences of +0.03 to +2.30 points.
- Exact solvability: Greedy is exact for every restructured tree by Corollary 4.5, while dense pairwise selection has no such guarantee.
Section 6.2, Appendix J.10 and Table 7 of the revised manuscript report this comparison.
Table R1: Test accuracy (%) of the common linear classifier of Section 6.2 on the features selected by dense pairwise selection and by the restructured trees, with the paired difference (pp) and its 95% bootstrap interval.
| Dataset | Dense pairwise | Restructured tree | Difference [95% CI] | |
|---|---|---|---|---|
| HAR | 20 | 87.55 | 90.82 | +3.28 [+0.90, +6.02] |
| HAR | 40 | 85.07 | 93.82 | +8.75 [+3.77, +15.03] |
| HAR | 80 | 90.53 | 94.43 | +3.90 [+1.79, +6.21] |
| ISOLET | 25 | 82.42 | 84.72 | +2.30 [−0.08, +4.79] |
| ISOLET | 43 | 89.03 | 89.75 | +0.72 [−1.14, +2.53] |
| ISOLET | 86 | 92.11 | 92.14 | +0.03 [−1.03, +1.06] |
W3 Writing density
W3. The writing is dense and the paper tries to do too much. It packs expressivity, two complexity regimes, a hardness bound, a universality construction and three experiments into the main text, which pushes most of the substance into the appendix. Undefined acronyms, such as CP, effective support, modular tail, in the abstract make it hard to read.
Response
Thanks for this suggestion. We refined the abstract, the introduction, Sections 3 and 4 and the appendix so that the paper is easier to read and its results form one line of argument.
- Abstract: It now defines CP and replaces the other undefined terms with plain descriptions.
- Introduction: It poses the two questions that the paper answers, namely which interactions DSFs cannot represent and which dependencies an exact optimizer must reconcile. It links each contribution to the question it answers and to its section.
- Sections 3 and 4: New sentences connect consecutive results and restate the main results in plain words. Section 4.1 also adds an intuition paragraph and a worked example (Example 4.2), so the main text shows how the DP works on a small case.
- Appendix A: A notation table makes each symbol easy to look up.
Dear Reviewer,
Thanks for your time and constructive feedback. As the discussion period closes in one day, we want to confirm whether our responses have addressed your concerns.
We would be happy to clarify any remaining questions. Thank you again for your time and consideration.
Best regards,
The Authors
Response to Reviewer 9WEr (Part 1/2)
We thank the reviewer for the detailed feedback. We have revised the paper accordingly and addressed each of the raised weaknesses in detail below. The main revisions are marked in blue in the revised manuscript.
W1 Novelty relative to classic tools
Response
Thanks for naming these tools. Lemma 3.1 applies the chain rule, the matrix part of Corollary 3.3 is the Kogan–Berman theorem [1], and Theorems 4.1 and 4.3 apply junction-tree DP and a standard ETH reduction to DSFs. However, these tools supply single steps. Our main results come from a graph view of DSFs and from arguments that the tools do not provide.
1. A graph view of DSFs. Prior work shows that the DSF composition guarantees submodularity, that depth enlarges the class without making it universal, and that concave extensions support learning and maximization [2, 3, 4]. Depth alone therefore certifies neither representability nor tractability. We show that graphs built from a DSF supply both answers. For expressivity, odd cycles of length at least five in the Hessian support graph decide whether a curvature obstruction exists (Corollary 3.3). For optimization, the effective treewidth governs the cost of exact maximization (Theorems 4.1 and 4.3). Our analysis also shows that the two answers depend on different graph properties. Five-cycle supports carry a curvature obstruction yet have effective treewidth two, whereas bipartite supports carry none yet give NP-hard maximization (Section 4.3).
2. Arguments beyond the tools. Each tool supplies one step, and we prove the main results with further arguments.
[1] Kogan and Berman. Characterization of Completely Positive Graphs. Discrete Mathematics, 1993.
[2] Bilmes and Bai. Deep Submodular Functions. arXiv:1701.08939, 2017.
[3] Dolhansky and Bilmes. Deep Submodular Functions: Definitions and Learning. NeurIPS, 2016.
[4] Bai et al. Submodular Maximization via Gradient Ascent: The Case of Deep Submodular Functions. NeurIPS, 2018.