acceptodds
Under review as a conference paper at ICLR 2027

Expressivity Limits and Exactly Solvable Regimes of Deep Submodular Functions

Abstract

Deep Submodular Functions (DSFs) compose modular maps and concave activations through nonnegative layers. Depth strictly enlarges the class, but no depth reaches all submodular functions, and even shallow DSFs can be hard to maximize. We show that composition rules impose all-depth expressivity constraints, while support organization provides structural certificates for exact cardinality-constrained maximization. On the expressivity side, we prove that DSF extensions built from activations that are on have completely positive negative Hessians at every interior point, regardless of depth. This curvature restriction is stronger than concavity and lattice-submodularity and yields smooth functions outside this extension class. A curvature support graph admits such a non-CP witness if and only if it contains an odd cycle of length at least five. For set functions, a clique-overcount inequality recovers the known exclusion of the graphic matroid rank of and lifts it to every matroid with an minor. On the optimization side, bounded effective treewidth permits exact junction-tree dynamic programming at any depth, and its single-exponential dependence on width is necessary under the Exponential Time Hypothesis. Computation trees with disjoint child supports and no external modular tail form a second, incomparable exact regime that stays tractable at maximal effective width. Curvature obstruction and optimization hardness obey different graph conditions. Finally, we overcome the discrete expressivity obstruction by allowing controlled sums and inf-convolution of shallow atoms. This enlarged composition class represents every normalized monotone submodular function, with submodular intermediates and possibly exponential size. The expressivity gap therefore lies in the composition rules, not in the components. Feature-selection objectives learned from data instantiate both exact regimes, and taxonomy-based data selection on CIFAR-100 complements them.

Primary area:
optimization
Keywords:
submodular optimization, deep submodular functions

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_9WErOpenReview ↗
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 C5C_5 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
AuthorsOpenReview ↗

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

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.

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.

  • Theorem 3.2. The chain rule places DSF curvature in the CP cone, while concavity and continuous lattice-submodularity place it only in the larger DNN cone [4]. This containment alone excludes no monotone function, since a quadratic with a non-CP negative Hessian is concave and lattice-submodular but decreases far from the origin. We compose this quadratic with bounded saturating maps, which keeps it monotone, concave and lattice-submodular on the whole orthant (Appendix C).
  • Corollary 3.3. The Kogan–Berman theorem characterizes matrices. Excluding functions also requires the curvature to stay on the given graph at every point of the orthant, and our construction in Theorem 3.2 guarantees this (Appendix C.4).
  • Theorem 3.6 and Corollary 3.7. The K4K_4 inequality is discrete and uses none of the four tools. Our proof writes each concave activation, on the finitely many values it takes, as a nonnegative combination of the identity and truncations, and shows that every truncation preserves the inequality at every depth (Appendix D). The inequality explains the known exclusion of the rank function of M(K4)M(K_4) [2] and extends it to every matroid with an M(K4)M(K_4) minor.
  • Theorems 4.1 and 4.3. Theorem 4.3 shows that the treewidth dependence of Theorem 4.1 is necessary, already for depth-one DSFs with unit-cap pairwise factors. The two theorems thus give matching upper and lower bounds in the effective treewidth.
  • Corollaries 4.4 and 4.5. Junction-tree DP is exponential in the effective treewidth, and Example 4.6 attains effective treewidth n−1n-1. We show that budget merging and greedy remain exact there, because the budget tables of disjoint subtrees are concave.

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

AuthorsOpenReview ↗

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 k=40k=40, 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.

DatasetkkDense pairwiseRestructured treeDifference [95% CI]
HAR2087.5590.82+3.28 [+0.90, +6.02]
HAR4085.0793.82+8.75 [+3.77, +15.03]
HAR8090.5394.43+3.90 [+1.79, +6.21]
ISOLET2582.4284.72+2.30 [−0.08, +4.79]
ISOLET4389.0389.75+0.72 [−1.14, +2.53]
ISOLET8692.1192.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

Reviewer_tgJoOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies the expressive power of Deep Submodular Functions and their exact maximization under cardinality constraints. It shows that the negative Hessian of a smooth DSF extension must be completely positive, and establishes a K₄ clique-overcount inequality for discrete DSFs. It also identifies two settings that allow exact optimization: bounded effective treewidth and computation trees with disjoint child supports. Finally, the authors show that adding controlled inf-convolution allows the representation of any normalized monotone submodular function.

I am less familiar with effective supports and effective clique hypergraphs, which limits my confidence in assessing some of the technical details.

Critical strengths

The completely positive Hessian condition is an interesting result. It connects the nonnegative structure of DSFs with the difference between the CP and DNN cones and gives a necessary condition for representability at any depth.

The two tractable settings are also useful. One relies on local factorization through bounded treewidth, while the other uses disjoint supports and discrete concavity to allocate the budget.

Critical weaknesses

The real-data experiments do not clearly demonstrate the benefit of deep nonlinear compositions. The tree objectives on HAR and ISOLET are depth-one pairwise models, and the grouped capped objectives are also shallow SCMMs. It would be helpful to include an example where the higher-layer nonlinearities actually affect the objective.

The relevance of the expressivity results to approximate fitting is unclear. The CP-Hessian result assumes C² activations, and the discrete inequality requires exact pairwise additivity. What happens when pairwise redundancy is small but nonzero? Do these obstructions still imply a nonzero approximation error?

I also found the algorithmic sections difficult to follow. More intuition and a small worked example would help explain effective supports, effective clique hypergraphs, and the DP states.

Questions for authors

How do the proposed solvers compare with Lazier Than Lazy Greedy in runtime and objective value?

Are there small instances where the overhead of the dynamic programs makes them slower than greedy or exhaustive search?

When effective treewidth is large, how does the runtime compare with exhaustive search, including preprocessing? In which settings should we expect a practical advantage?

6 comments
AuthorsOpenReview ↗

Response to Reviewer tgJo (Part 1/4)

We thank the reviewer for the thoughtful and constructive feedback. We have revised the paper accordingly and addressed each of the raised weaknesses and questions in detail below. The main revisions are marked in blue in the revised manuscript.

W1 Higher-layer nonlinearities on real data

W1. The real-data experiments do not clearly demonstrate the benefit of deep nonlinear compositions. The tree objectives on HAR and ISOLET are depth-one pairwise models, and the grouped capped objectives are also shallow SCMMs. It would be helpful to include an example where the higher-layer nonlinearities actually affect the objective.

Response

The revision adds trained three-level DSFs on HAR and ISOLET, and their higher-layer nonlinearities both change the objective and improve its fit to real data. Making the upper levels linear lowers held-out R2R^2 by up to 0.16 and changes up to 61% of the selected features at a single budget. We fit depth-2 DSFs to training-split subset utilities, group features by the negative Hessian of each fit, and refit disjoint computation trees with two or three levels on these groups, for which greedy is exact by Corollary 4.5. With the tree chosen per budget on the training split, the selected features match or exceed the accuracy of dense pairwise selection, a depth-one objective over all feature pairs, at all six budgets and exceed it on HAR by 3.28 to 8.75 points. To isolate the upper nonlinearities, we retrain each three-level tree from the same initial weights with the same recipe but with its top one or two levels made linear, and compare the two versions in two ways.

  • Fit: Making the top level linear lowers held-out R2R^2 by 0.03 to 0.07, and making the top two levels linear lowers it by 0.11 to 0.16, with all twelve intervals above zero.
  • Selection: Making the top level linear changes 16% to 31% of the selected features at individual budgets, and making the top two levels linear changes 30% to 61%, so the upper nonlinearities decide which features are chosen.

Table R1 reports both comparisons. Section 6.2, Appendix J.10 and Tables 6 to 8 of the revised manuscript report them together with the comparison to dense pairwise selection.

The revision also adds Example 4.2 to Section 4.1, which works through Figure 1 by hand and gives a small case in which the upper nonlinearities change the optimum. In this seven-element network, element 4 feeds both upper nodes through the shared first-level node u2u_2. With the upper caps, the best pair at k=2k=2 is {1,6}\{1,6\} with value 6. Without them, every optimal pair contains element 4, which then counts fully in both upper nodes and gives value 7 together with element 1.

Table R1: Upper-level ablation of the three-level trees for each dataset and number KK of first-level groups. R2R^2 loss is the drop in held-out utility R2R^2 when the given levels are made linear, with paired 95% tt intervals over five fit seeds, and "changed" is the share of selected features that differ from the full tree, averaged over the three budgets.

DatasetKKFull tree R2R^2Linear levelsR2R^2 loss [95% CI]Changed
HAR640.971top0.052 [0.046, 0.059]23%
top two0.128 [0.115, 0.141]36%
HAR1280.949top0.060 [0.039, 0.080]24%
top two0.140 [0.116, 0.164]38%
HAR2560.915top0.061 [0.050, 0.072]28%
top two0.148 [0.137, 0.160]47%
ISOLET640.978top0.029 [0.024, 0.034]21%
top two0.106 [0.103, 0.109]34%
ISOLET1280.969top0.049 [0.042, 0.055]24%
top two0.134 [0.125, 0.143]41%
ISOLET2560.953top0.069 [0.060, 0.077]29%
top two0.163 [0.155, 0.171]46%
AuthorsOpenReview ↗

Response to Reviewer tgJo (Part 2/4)

W2 Approximate fitting

W2. The relevance of the expressivity results to approximate fitting is unclear. The CP-Hessian result assumes C² activations, and the discrete inequality requires exact pairwise additivity. What happens when pairwise redundancy is small but nonzero? Do these obstructions still imply a nonzero approximation error?

Response

Thanks for this question about small but nonzero redundancy. Yes, both obstructions still imply a nonzero approximation error. They now give explicit lower bounds on the distance to every DSF, so they apply directly to approximate fitting. Neither bound needs exact pairwise additivity or C2C^2 activations. The three results below give these bounds, the first two for every depth and the third exactly at depth one.

  1. Discrete obstruction: Theorem 3.6 now states the inequality ∑T∈Tρf(T)≤ρf(V)+∑{e,e′}ρf({e,e′})\sum_{T\in\mathcal T}\rho_f(T)\le\rho_f(V)+\sum_{\{e,e'\}}\rho_f(\{e,e'\}) for every DSF cube trace ff on V=E(K4)V=E(K_4) at any depth, so pairwise redundancy enters only as a linear slack. Property P, the submitted statement, is its case of zero pairwise redundancy. The coefficients have total absolute value 44 and rM(K4)r_{M(K_4)} violates the inequality by one, hence ∥f−rM(K4)∥∞≥1/44\|f-r_{M(K_4)}\|_\infty\ge 1/44 for every DSF ff. For small nonzero redundancy, the target (1−ε) rM(K4)+εmin⁡(∣A∣,1)(1-\varepsilon)\,r_{M(K_4)}+\varepsilon\min(|A|,1), whose pairwise redundancies all equal ε\varepsilon, stays at distance at least (1−13ε)+/44(1-13\varepsilon)_+/44 from every DSF. Section 3.3 and Appendix D of the revised manuscript give the statement and a self-contained proof.
  2. Continuous obstruction: The new Proposition 3.4 is a distributional form of the CP condition. For every copositive matrix CC and every nonnegative smooth test function ψ\psi with compact support, every DSF extension GG of any depth whose activations are continuous at zero satisfies −∫G ⟨C,∇2ψ⟩ dx≥0-\int G\,\langle C,\nabla^2\psi\rangle\,dx\ge0. A target FF with ⟨C,−∇2F⟩≤−δ\langle C,-\nabla^2F\rangle\le-\delta on the support of ψ\psi therefore stays at sup-distance at least δ∫ψ dx /∫∣⟨C,∇2ψ⟩∣ dx\delta\int\psi\,dx\,/\int|\langle C,\nabla^2\psi\rangle|\,dx from every such GG. Applied to the witness of Theorem 3.2, this gives a positive distance at every depth without differentiability of the activations (Section 3.2 and Appendix C.5).
  3. Exact distance at depth one: For depth-one DSFs and five values of ε\varepsilon from 0 to 0.1, a finite linear program gives the distance (4−5ε)/17(4-5\varepsilon)/17 to the same target, for example 0.2350.235 at ε=0\varepsilon=0 and 0.2060.206 at ε=0.1\varepsilon=0.1. Its dual certificate is checked in exact rational arithmetic. For depths two to four, a column-generation search over DSFs finds none closer than 3/16=0.18753/16=0.1875 at ε=0\varepsilon=0, so added depth stays near the depth-one value. Appendix D of the revised manuscript reports these values.

W3 Worked example

W3. I also found the algorithmic sections difficult to follow. More intuition and a small worked example would help explain effective supports, effective clique hypergraphs, and the DP states.

Response

Thanks for this suggestion. The revision adds an intuition paragraph to Section 4.1 and a worked example, Example 4.2, on the seven-element network of Figure 1. Together they explain the three concepts mentioned in the comment.

  • Effective supports: A new sentence after Definition 2.2 states that E(u)E(u) holds the inputs with positive-weight paths to uu. In the example, the two upper nodes have effective supports {1,…,5}\{1,\dots,5\} and {3,…,7}\{3,\dots,7\}.
  • Effective clique hypergraph: Its hyperedges are the effective supports of all nonlinear nodes. In the example, all five hyperedges lie inside the two upper supports, which form the bags of a junction tree with separator {3,4,5}\{3,4,5\}.
  • DP states: Each top-layer node reads only its effective support, so two bags interact only through their shared elements. The child bag therefore passes the root one value per separator assignment and budget, and it summarizes its 32 bag assignments by 8 separator assignments.

At k=2k=2, the DP returns the optimum 6 at {1,6}\{1,6\}, while greedy first picks element 4 and stops at 5.

AuthorsOpenReview ↗

Response to Reviewer tgJo (Part 3/4)

Q1 Comparison with Lazier Than Lazy Greedy

Q1. How do the proposed solvers compare with Lazier Than Lazy Greedy in runtime and objective value?

Response

On the three objectives below, the exact solvers run in the same millisecond range as stochastic greedy (Lazier Than Lazy Greedy [1]) and return the optimum, while stochastic greedy with ε=0.1\varepsilon=0.1 stays 0.7% to 20% below it. Section 6.3 and Table 11 of the revised manuscript add stochastic greedy to the CIFAR-100 comparison, with all solvers timed in one job on one core. Appendix J.13 and Table 12 of the revised manuscript extend the comparison to two further objectives, so that Table R1 covers three objectives with increasing overlap between supports.

  • CIFAR-100 taxonomy caps (n=50,000n=50{,}000 images, Section 6.3): The supports are disjoint, and the exact solver is the heap merge of class marginals.
  • Learned trees (HAR with n=561n=561 features and ISOLET with n=617n=617, Section 6.2): These are the three-level disjoint trees with K=128K=128 first-level groups, solved by the budget-splitting DP.
  • Planted overlap (n=201n=201): Coverage blocks overlap with effective treewidth 2 and are planted so that the greedy choice is suboptimal. JT-DP solves this objective.

The gap of stochastic greedy grows with the overlap between supports, from 0.7% on CIFAR-100 to 1.6% to 4.2% on the learned trees and 12% to 20% on the planted instance, while every exact solver stays below 32 ms. For the learned trees, the other group counts K∈{64,256}K\in\{64,256\} give gaps of 1.4% to 5.6%. A smaller ε\varepsilon narrows the gap only partly, since ε=0.01\varepsilon=0.01 still leaves 0.38% to 18% at up to 103 ms.

Table R1: Median selection time of the exact solver and of stochastic greedy (ε=0.1\varepsilon=0.1) at each budget kk, and how far the value of stochastic greedy falls below the proven optimum. These gaps are means over 20 stochastic-greedy seeds, with the median over the five fitted trees for HAR and ISOLET and over the five planted instances.

ObjectivennkkExact solver (ms)Stochastic greedy (ms)Stochastic greedy below optimum (%)
CIFAR-100 taxonomy caps50,0005008.45.70.74
10008.69.30.67
Learned tree, HAR561205.81.73.41
405.82.82.26
805.84.91.63
Learned tree, ISOLET617256.02.04.17
436.03.03.49
866.15.32.41
Planted overlap, width 22011014.412.720.43
2017.418.417.58
4022.236.114.39
8031.468.411.79

[1] Mirzasoleiman et al. Lazier Than Lazy Greedy. AAAI, 2015.


Q2 Overhead on small instances

Q2. Are there small instances where the overhead of the dynamic programs makes them slower than greedy or exhaustive search?

Response

Yes. On small instances the DP is slower than greedy and often slower than exhaustive search, but only by a few milliseconds. In exchange it returns a certified optimum, which greedy misses in more than half of the cells. The comparison covers 144 cells of small band-structured instances, where each cell fixes n≤32n\le32, an effective treewidth of at most 7 and k≤6k\le6. Each cell has five seeds, the times include preprocessing, and every solver runs on one CPU core. The measurements show three results.

  • Runtime overhead: The DP is slower than greedy in every cell, by a median factor of 2.2, and slower than exhaustive search beyond timing noise in 88 cells. Its median time is at most 7.3 ms in every cell and at most 3.9 ms above greedy.
  • Solution quality: Greedy misses the optimum in 79 of the 144 cells, by up to 14%, while the DP returns a proven optimum in every cell.
  • Scaling with nn: Exhaustive search is competitive here only because the instances are tiny, since its cost grows with the number (nk)\binom nk of candidate sets. At n=40n=40 the DP is already faster than exhaustive search in 561 of the 592 cells with k≥3k\ge3 and width up to 28 in which a solver finishes (our reply to Q3).
Reviewer_ZGSoOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper presents a theoretical investigation into Deep Submodular Functions, focusing on expressivity bounds and exact cardinality constrained maximization regimes.

Key contributions include:

  1. Expressivity Constraints: It proves that smooth continuous extensions of DSFs have completely positive (CP) negative Hessians across all depths, separating them from general monotone concave lattice-submodular functions (specifically via five-cycle C5C_5 curvature obstructions). Establishes a K4K_4 clique-overcount inequality (PP) that extends the non-representability of the graphic matroid rank M(K4)M(K_4) to any matroid with an M(K4)M(K_4) minor.
  2. Solvable Optimization Regimes: Identifies two distinct exact optimization settings: a. Junction-tree dynamic programming (JT-DP) for bounded effective treewidth ww, incurring O(∣T∣2w+1k2)O(|\mathcal{T}|2^{w+1}k^2) runtime (shown to be optimal under ETH up to subexponential factors in ww). b. Disjoint computation trees, which enable exact linear-time marginal-gain greedy optimization and O(k)O(k) DP budget-splitting regardless of width.
  3. Controlled Composition: Shows that universality over normalized monotone submodular functions (MonSub\text{MonSub}) is recovered by combining shallow SCMM atoms via nonnegative sums and controlled inf-convolution.
  4. Empirical Validation: Demonstrates the regimes on synthetic instances, feature selection (UCI HAR, ISOLET), and taxonomy-based data selection on CIFAR-100.
Critical strengths
  1. Rigorous and Comprehensive Theory: Resolves several open theoretical questions regarding DSF expressivity across arbitrary depths. The CP-matrix perspective and the K_4$ minor extension provide deep mathematical clarity.
  2. Tractable Regimes Characterization: Identifying disjoint computation trees as an exact regime that escapes worst-case treewidth hardness (effective width n−1n-1) is a clean, valuable result.
Critical weaknesses
  1. Practicability of the Universal Class (CDSFCDSF): The recursive inf-convolution construction (Theorem 5.2) can yield representations of exponential size O(2n)O(2^n), limiting its practical applicability for learning. 2.Gap Between Learned Models and Hard Constraints: Enforcing strict effective treewidth or disjoint support topologies during standard backpropagation gradient-based learning remains non-trivial and is only partially addressed via heuristics (e.g., Chow-Liu trees, correlation clustering).
Questions for authors
  1. How efficiently can the disjoint support topology or bounded treewidth constraints be enforced during continuous end to end learning of DSFs from continuous embeddings?
  2. Can the controlled inf-convolution construction(Theorem 5.2) be approximated with polynomial sized expressions under bounded approximation guarantees?
3 comments
AuthorsOpenReview ↗

Response to Reviewer ZGSo (Part 1/2)

We thank the reviewer for the insightful and positive evaluation of our work. We revised the paper accordingly and addressed the concerns in detail below. The main revisions are marked in blue in the revised manuscript.

W1 & Q2 Size and approximation of the controlled composition class

W1. Practicability of the Universal Class: The recursive inf-convolution construction (Theorem 5.2) can yield representations of exponential size, limiting its practical applicability for learning.

Q2. Can the controlled inf-convolution construction (Theorem 5.2) be approximated with polynomial sized expressions under bounded approximation guarantees?

Response

Yes. Members of the class with polynomially many nodes approximate every normalized monotone submodular function within a factor O(nlog⁡n)O(\sqrt n\log n), and no class with polynomial-size descriptions reaches a constant factor. Exponential size is therefore needed only for exact representation, where every class needs it. In practice one learns compact DSFs of fixed size, as in Section 6.2, and Theorem 5.2 serves to locate the expressivity gap of Section 3 in the composition rules. The following three results support this answer.

  1. Exact representation needs exponential size for every class. Knuth's construction [1] gives at least 2(n⌊n/2⌋)/(2n)2^{\binom{n}{\lfloor n/2\rfloor}/(2n)} distinct matroids on nn labeled elements. Their rank functions are normalized monotone submodular, so any exact encoding of this class needs at least (n⌊n/2⌋)/(2n)≥2n/(2n(n+1))\binom{n}{\lfloor n/2\rfloor}/(2n)\ge 2^n/(2n(n+1)) bits for some member.

  2. Polynomial size suffices for a factor O(nlog⁡n)O(\sqrt n\log n), and no compact class reaches a constant factor. For every normalized monotone submodular ff, polynomially many value queries construct weights c∈R+nc\in\mathbb R_+^n such that f^(A)=∑i∈Aci\hat f(A)=\sqrt{\sum_{i\in A}c_i} satisfies f^(A)≤f(A)≤O(nlog⁡n),f^(A)\hat f(A)\le f(A)\le O(\sqrt n\log n)\\,\hat f(A) for all AA, with factor n+1\sqrt{n+1} for matroid rank functions [2]. This f^\hat f is a single depth-one DSF with nn weights and hence a member of the class of Theorem 5.2. A constant factor is out of reach for every class with polynomial-length descriptions, because some matroid rank functions have no poly(n)\mathrm{poly}(n)-space representation within a factor o~(n1/3)\tilde o(n^{1/3}) [3]. The same barrier holds for learning, since no algorithm learns monotone submodular functions within a factor o(n1/3/log⁡n)o(n^{1/3}/\log n) from polynomially many samples or value queries [3].

  3. Structured targets have exact expressions of polynomial size. The exponential size in Theorem 5.2 comes from writing the recursion as a tree. Each step of the recursion splits on one element into two branches, so the tree has 3⋅2n−53\cdot2^n-5 nodes for every target. Many branches compute the same function, and storing each distinct subexpression once removes this repetition. For the uniform matroid rank min⁡(∣A∣,k)\min(|A|,k), for example, every branch has the form min⁡(∣A∣,k−j)\min(|A|,k-j), so each level holds at most k+1k+1 distinct nodes. Table R1 counts the nodes of both forms for a uniform matroid and for the graphic matroids of two graph families, and every expression was checked against its target on all subsets. The shared form grows linearly, by 26 nodes for each rung added to a ladder graph and by 70 nodes for each K4K_4 added to a chain, while the tree form doubles with each added edge. In these runs the edges enter the recursion one rung or one K4K_4 at a time, following a path decomposition of the graph.

Table R1: Node counts of the exact controlled expression of Theorem 5.2 in tree form and with identical subexpressions shared. A ladder graph with mm rungs joins two paths of mm vertices by mm rungs and has n=3m−2n=3m-2 edges. A chain of tt copies of K4K_4 glues consecutive copies along one edge and has n=5t+1n=5t+1 edges.

TargetnnTree formShared form
Uniform matroid U(6,12)U(6,12)1212,283172
Ladder graph, 3 rungs737949
Ladder graph, 4 rungs103,06775
Ladder graph, 5 rungs1324,571101
Ladder graph, 6 rungs16196,603127
Chain of one K4K_4618767
Chain of two K4K_4116,139137
Chain of three K4K_416196,603207

[1] Knuth. The Asymptotic Number of Geometries. Journal of Combinatorial Theory, Series A, 1974.

[2] Goemans et al. Approximating Submodular Functions Everywhere. SODA, 2009.

[3] Balcan and Harvey. Submodular Functions: Learnability, Structure, and Optimization. SIAM Journal on Computing, 2018.

AuthorsOpenReview ↗

Response to Reviewer ZGSo (Part 2/2)

W2 & Q1 Enforcing structure during end-to-end learning

W2. Gap Between Learned Models and Hard Constraints: Enforcing strict effective treewidth or disjoint support topologies during standard backpropagation gradient-based learning remains non-trivial and is only partially addressed via heuristics (e.g., Chow-Liu trees, correlation clustering).

Q1. How efficiently can the disjoint support topology or bounded treewidth constraints be enforced during continuous end to end learning of DSFs from continuous embeddings?

Response

Both constraints can be enforced exactly during end-to-end gradient training, with no projection step. Disjoint trees learned from continuous feature embeddings train in a median of 76 to 184 s per model on CPU and match the accuracy of the two-stage route of Section 6.2 at all six budgets. Bounded treewidth holds for every value of the weights once each term reads only one bag, so backpropagation keeps it at every step. The mentioned heuristics, Chow–Liu trees and correlation clustering, only choose the structure, and the exactness guarantees hold for whichever structure they choose. The two points below describe how each constraint is built into training.

1. Disjoint support topology:

Each feature and each internal node carries a 32-dimensional embedding, and its parent is a softmax over prototypes of the next level. The temperature anneals from 1 to 0.01 over the first 70% of training while gradients pass through the assignment. The assignment is then rounded to its argmax, and the remaining steps train the hard tree. The result is a disjoint computation tree by construction, so greedy is exact for whichever tree training selects (Corollary 4.5). Each model trains in a single run of 24,000 steps on 16 CPU cores, without fitting a dense DSF first.

Table R1 compares these trees with the two-stage route, which fits a dense DSF and then restructures it along its Hessian. Every difference lies within 0.82 points, and all twelve paired intervals over five fit seeds contain zero, so learning the tree end to end costs no measurable accuracy. Appendix J.10 and Table 9 of the revised manuscript describe this experiment.

Table R1: Test accuracy (%) of the two-stage route and of end-to-end disjoint trees with learned feature embeddings or with fixed ones (the top singular vectors of the standardized training features, followed by a learned linear map). Differences (pp) are to the two-stage route, with paired 95% tt intervals over five fit seeds.

DatasetkTwo-stageLearned emb.Difference [95% CI]Fixed emb.Difference [95% CI]
HAR2090.8291.48+0.66 [−1.25, +2.57]90.00−0.82 [−2.52, +0.88]
HAR4093.8293.70−0.12 [−0.74, +0.50]93.02−0.80 [−2.07, +0.47]
HAR8094.4394.45+0.02 [−1.66, +1.70]94.13−0.30 [−1.34, +0.75]
ISOLET2584.7284.00−0.72 [−2.98, +1.55]84.59−0.13 [−2.00, +1.74]
ISOLET4389.7589.43−0.32 [−1.81, +1.17]89.45−0.30 [−1.64, +1.05]
ISOLET8692.1491.46−0.68 [−1.69, +0.33]91.82−0.32 [−0.80, +0.16]

2. Bounded treewidth:

We fix a tree decomposition of the ground set and let each term of a sum of DSFs read only the elements of one bag. The effective treewidth is then at most the bag size minus one, so Theorem 4.1 applies to the trained model. The Chow–Liu objective of Section 6.2 is the width-one case.

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

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

We thank all reviewers for their thoughtful and constructive feedback. We have incorporated the suggested results, examples and clarifications into the revised manuscript, with the main revisions highlighted in blue. Below, we summarize our core contributions and the major updates introduced during the rebuttal.

Core contributions

  1. DSF limits hold at every depth: Every smooth DSF extension has a completely positive (CP) negative Hessian, a sum of terms vv⊤vv^\top with v≥0v\ge0. Concavity and submodularity allow more general curvature. This curvature condition and a K4K_4 inequality keep some smooth monotone submodular functions and the rank function of every matroid with an M(K4)M(K_4) minor at an explicit distance from every DSF.
  2. Exact optimization depends on how node inputs overlap: Junction-tree DP is exact at any depth, in time exponential only in the treewidth of the graph that links inputs read by a common node. Under ETH this dependence is necessary. Greedy is exact on trees whose sibling nodes read disjoint inputs and whose modular terms all lie inside the tree, even at maximal treewidth. The curvature obstruction depends instead on odd cycles of length at least five, so expressivity and hardness follow different graph properties.
  3. The expressivity gap lies in the composition rules: Nonnegative sums and controlled inf-convolution of single concave-over-modular atoms represent every normalized monotone submodular function. The limits of item 1 therefore come from how DSFs combine their parts, and richer composition rules remove them.

Major updates of results during rebuttal

  • Section 6.2, Figure 2 & Appendix J.10: Restructuring trained DSFs into disjoint trees along their Hessian makes greedy exact. The restructured trees match or exceed dense pairwise selection at all six budgets, by 3.28 to 8.75 points on HAR (addressing tgJo's W1 and 9WEr's W2).
  • Appendix J.10 & Table 8: The upper-level nonlinearities shape the learned objective. Making them linear in three-level trees lowers held-out R2R^2 by up to 0.16 (addressing tgJo's W1).
  • Appendix J.10 & Table 9: End-to-end training can impose the exactly solvable structure. Disjoint trees trained end to end stay within 0.82 points of the two-stage route (addressing ZGSo's W2 & Q1).
  • Section 3.3 & Appendix D: Theorem 3.6 now states a linear K4K_4 inequality, with Property P as its zero-redundancy case. It gives ∥f−rM(K4)∥∞≥1/44\|f-r_{M(K_4)}\|_\infty\ge 1/44 for every DSF, and the bound persists under small nonzero redundancy (addressing tgJo's W2).
  • Section 3.2 & Appendix C.5: The new Proposition 3.4 (distributional curvature obstruction) covers activations that are only continuous at zero and gives an explicit distance bound at every depth (addressing tgJo's W2).
  • Section 6.3 & Table 11: Stochastic greedy (Lazier Than Lazy Greedy) joins the CIFAR-100 comparison. Over three values of ε\varepsilon, it stays 0.4% to 1.5% below the optimum, which the exact heap merge reaches in 8 to 9 ms (addressing tgJo's Q1).
  • Section 4.1 & Appendix J.5: JT-DP, timed with preprocessing included, is faster than exhaustive search in 561 of the 592 cells with k≥3k\ge3 and effective treewidth up to 28 in which a solver finishes (addressing tgJo's Q3).

Major updates of discussions and clarifications during rebuttal

  • Section 4.1 & Example 4.2: We add an intuition paragraph and a worked example on Figure 1. The example shows effective supports, bags, the DP table and a budget at which greedy is suboptimal (addressing tgJo's W3 and 9WEr's W3).
  • Abstract, Section 1 & Appendix A: We refine the abstract, define CP and describe the other technical terms in plain words where they first appear. Appendix A adds a notation table (addressing 9WEr's W3).
  • Section 3.1: We compare CP negative Hessians with the larger DNN cone implied by concavity and continuous lattice-submodularity. Theorem 3.2 turns the gap between the two cones into excluded functions (addressing 9WEr's W1).
  • Section 5: We add approximation with polynomial size. A depth-one DSF already approximates every normalized monotone submodular function within a factor O(nlog⁡n)O(\sqrt n\log n) (addressing ZGSo's W1 & Q2).

We believe these revisions address the reviewers' concerns and strengthen our manuscript. The individual responses below provide the full tables and details for each point.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.