Expressivity Limits and Exactly Solvable Regimes of Deep Submodular Functions

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 $C^2$ on $(0,\infty )$ 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 $K_4$ and lifts it to every matroid with an $M(K_4)$ 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.