🔢 mathematics

Sum of Squares Submodularity

This paper introduces a hierarchy of algebraic conditions called $t$ -sum of squares submodularity that can be efficiently verified via semidefinite programming to certify set function submodularity, offering new tools for discrete optimization applications such as regression, maximization, and decomposition.

Original authors: Anna Deza, Georgina Hall

Published 2026-06-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Anna Deza, Georgina Hall

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Diminishing Returns" Rule

Imagine you are a farmer deciding which crops to plant. You have a rule called Submodularity, which is a fancy way of describing diminishing returns.

The Rule: Adding a new crop to a small, empty field gives you a huge boost in harvest. But adding that same crop to a field that is already packed full of other crops gives you a much smaller boost.
Why it matters: This rule appears everywhere: in economics (buying more of the same item), machine learning (picking the most informative data points), and network design. Because it follows this rule, computers can solve problems involving these functions very quickly.

The Problem: Sometimes, you have a complex function (a mathematical recipe) and you want to know: "Does this recipe follow the Diminishing Returns rule?"
If the recipe is simple (like a straight line or a simple curve), you can check this easily. But if the recipe is complex (involving many variables mixed together in complicated ways), checking if it follows the rule is computationally impossible for a computer to do in a reasonable amount of time. It's like trying to find a single specific grain of sand on a beach by looking at every grain one by one.

The Solution: The "Sum of Squares" Ladder

The authors of this paper introduce a new tool called $t$ -sum of squares (sos) submodularity. Think of this as a ladder with many rungs, where each rung is labeled with a number $t$ .

The Ladder Concept: Instead of trying to prove the rule holds perfectly (which is too hard), they check if the function satisfies a "simpler" version of the rule.
The Rungs ( $t$ ):
- Rung 0 ( $t=0$ ): The easiest check. If a function passes this, it definitely follows the Diminishing Returns rule.
- Rung 1, 2, 3...: As you go up the ladder, the checks get stricter and more complex.
- The Magic: If a function passes any rung of the ladder, it is guaranteed to follow the Diminishing Returns rule.
The Speed: Checking if a function passes a specific rung (for a fixed $t$ ) is easy for a computer. It turns the problem into a standard math puzzle (a "semidefinite program") that modern computers can solve quickly, even for large problems.

The Trade-off:

If a function is simple, it might pass the bottom rung ( $t=0$ ).
If a function is complex, it might need to go up to a higher rung ( $t=10$ or $t=100$ ) to be certified.
The paper proves that if you go high enough up the ladder, every function that follows the Diminishing Returns rule will eventually be caught.

How They Built the Ladder

The authors didn't just guess; they built a rigorous mathematical framework:

Algebraic Certificates: They translated the "Diminishing Returns" rule into algebra (equations). They showed that if you can write a specific part of the equation as a "Sum of Squares" (like $A^2 + B^2 + C^2$ ), then the rule holds. Since squares are always positive, this guarantees the rule is satisfied.
Equivalent Views: They proved that looking at the problem from different angles (using different algebraic formulas) leads to the same result. It's like looking at a statue from the front, side, and back; they all describe the same object.
Preserving the Rule: They showed that if you take two functions that pass the ladder test and mix them together (add them or scale them), the new mix still passes the test. This is crucial for building complex models.

Real-World Applications (What They Did With It)

The paper demonstrates three specific ways this ladder helps solve real problems:

1. Fitting Data (Submodular Regression)

The Scenario: You have messy data (like sales numbers) and want to find a mathematical curve that fits the data and follows the Diminishing Returns rule.
The Old Way: Previous methods required a lot of manual tweaking and guessing, or they used "black box" neural networks that were hard to tune and sometimes gave inconsistent results.
The New Way: The authors use their ladder. They tell the computer: "Find the best curve that fits the data and passes the $t$ -sos test."
Result: This is a "convex" problem, meaning the computer finds the best possible answer automatically without needing a human to guess parameters. In tests, this method predicted future data better than the old methods, especially when the data was noisy.

2. Measuring "Almost" Submodularity (Approximate Maximization)

The Scenario: Sometimes a function doesn't perfectly follow the Diminishing Returns rule, but it's close. We want to know how close it is. This "closeness" is called the submodularity ratio.
The Problem: Calculating this ratio exactly is impossible for complex functions.
The New Way: The authors use the ladder to find a guaranteed lower bound. They can say, "This function is at least 80% submodular," with mathematical certainty.
Result: This helps algorithms make better decisions when picking the best items (like selecting the best sensors for a network) even when the data isn't perfect.

3. Breaking Down Complex Problems (Difference of Submodular Optimization)

The Scenario: Some problems involve a function that is the difference between two Diminishing Returns functions (e.g., Profit = Revenue - Cost). This is hard to solve.
The Old Way: Computers use a standard method to break these down, but it often gets stuck in a "local minimum" (a small hill that looks like the top, but isn't).
The New Way: The authors use the ladder to find a better way to break the function down into its two parts.
Result: By using this smarter breakdown, the computer finds much better solutions (higher profits, lower costs) than the standard method, though it takes a bit more computing time.

Summary

The paper builds a mathematical ladder that allows computers to efficiently verify if complex functions follow the "Diminishing Returns" rule. By climbing this ladder, they can:

Fit data to these rules automatically and accurately.
Measure how close a messy function is to following the rule.
Solve difficult optimization problems by finding better ways to break them apart.

It connects two worlds: Discrete Optimization (making choices between distinct options) and Real Algebraic Geometry (using advanced polynomial math), creating a bridge that makes hard problems solvable.

Technical Summary: Sum of Squares Submodularity

Problem Statement

Submodularity is a fundamental structural property of set functions, encoding the notion of diminishing returns. It is central to optimization theory, appearing in economics, machine learning, and operations research, and is often termed "discrete convexity." While unconstrained minimization of submodular functions is solvable in polynomial time, and maximization under cardinality constraints admits a $(1 - 1/e)$ -approximation via the greedy algorithm, testing whether a general set function is submodular is computationally intractable. Specifically, for set functions of degree $d \ge 4$ , the decision problem is co-NP-complete (Crama 1989; Gallo and Simeone 1989).

This hardness motivates the need for tractable sufficient conditions for certifying submodularity. Existing approaches often rely on problem-specific heuristics or require extensive manual tuning. The paper addresses the gap between the fundamental discrete structure of submodularity and the tools of real algebraic geometry, specifically Sum of Squares (SOS) hierarchies, to provide a systematic, algebraic framework for certification.

Methodology

The authors introduce $t$ -sum of squares (sos) submodularity, a hierarchy of sufficient algebraic conditions indexed by an integer $t$ . The methodology relies on the correspondence between set functions and their multilinear extensions (MLEs), which are multilinear polynomials.

Core Definitions

Multilinear Extension (MLE): A set function $f: 2^\Omega \to \mathbb{R}$ is uniquely represented by a multilinear polynomial $F \in \mathbb{R}[x_1, \dots, x_n]$ such that $F(\mathbf{1}_S) = f(S)$ for all $S \subseteq \Omega$ .
Algebraic Characterization: Submodularity is characterized by the non-positivity of the second-order mixed partial derivatives of the MLE on the Boolean hypercube $\{0, 1\}^n$ (i.e., $\frac{\partial^2 F}{\partial x_i \partial x_j} \le 0$ ).
$t$ -sos Submodularity: A set function $f$ is $t$ -sos submodular if, for all $i \neq j$ , the polynomial $-\frac{\partial^2 F}{\partial x_i \partial x_j}$ is a sum of squares of polynomials of degree at most $t$ , modulo the ideal $I_2[x_{-i,j}] = \langle x_k^2 - x_k \mid k \neq i, j \rangle$ . This ideal enforces the Boolean constraints $x_k \in \{0, 1\}$ .

Computational Framework

Checking $t$ -sos submodularity is reduced to a Semidefinite Program (SDP). For a fixed $t$ and ground set size $n$ , the verification involves solving an SDP with $n(n-1)/2$ constraints, where the size of each constraint matrix is polynomial in $n$ (specifically $\sum_{k=0}^t \binom{n-2}{k}$ ).

The paper establishes several equivalent algebraic characterizations of $t$ -sos submodularity corresponding to the seven standard definitions of submodularity (e.g., diminishing returns, lattice inequalities). While these characterizations are algebraically equivalent, the authors demonstrate that the second-order formulation (based on mixed partial derivatives) yields the smallest SDP representation, making it the most computationally efficient.

Key Contributions

1. Theoretical Foundations

Hierarchy Construction: The paper defines $t$ -sos submodularity as a hierarchy where any $t$ -sos submodular function is submodular. Conversely, any submodular function of degree $d$ is $t$ -sos submodular for sufficiently large $t$ (specifically $t = \lceil \frac{n+d-5}{2} \rceil$ ).
Complexity Gap Analysis:
- For degrees $d < 4$ , submodularity and $t$ -sos submodularity coincide for small $t$ (e.g., $t=0$ for $d=2$ , $t=1$ for $d=3$ ). This aligns with the fact that submodularity testing is polynomial for $d \le 3$ .
- For $d=4$ , the paper constructs a submodular function that requires $t \approx n/2$ to be certified as $t$ -sos submodular, reflecting the inherent hardness of the problem.
Preservation Properties: The authors identify operations that preserve $t$ -sos submodularity (nonnegative weighted sums, complementation, restriction, contraction) and those that do not (partial minimization, convolution, monotonization), noting that the latter can drastically increase the required $t$ .

2. Applications

The paper demonstrates the utility of $t$ -sos submodularity in three distinct areas:

Submodular Regression: The authors propose fitting $t$ -sos submodular polynomials to data via SDP. Unlike existing methods (e.g., neural network-based approaches or heuristic shell mixtures), this approach requires minimal manual tuning (only polynomial degree $k$ and SOS degree $t$ ) and guarantees a submodular output. Empirical results show superior generalization error on noisy data compared to unconstrained polynomial regression and state-of-the-art neural methods.
Approximate Submodular Maximization: For maximizing approximately submodular functions, the greedy algorithm's performance depends on the submodularity ratio $\gamma^*$ . Computing $\gamma^*$ is NP-hard. The paper provides a systematic SDP-based procedure to derive lower bounds on $\gamma^*$ using $t$ -sos submodularity, improving upon spectral bounds in numerical experiments.
Difference-of-Submodular (DS) Optimization: DS optimization problems ( $\min g - h$ ) are solved via the Submodular-Supermodular Procedure (SSP). The quality of the solution depends on the specific DS decomposition. The authors propose an SDP to find an irreducible decomposition (maximizing the curvature of the submodular component $h$ ) that leads to significantly better local optima compared to trivial decompositions, albeit with increased computation time.

Results

Theoretical: The paper provides a complete classification of when submodularity coincides with $t$ -sos submodularity based on the degree of the set function. It proves that for $d \ge 4$ , the gap between the two concepts can be large, necessitating high levels of the hierarchy.
Empirical:
- In regression tasks, the $t$ -sos approach outperforms both unconstrained polynomial regression and the FlexSubNet neural network method in terms of test RMSE on synthetic submodular data.
- In DS optimization, using the SOS-derived irreducible decomposition reduced the average relative optimality gap by approximately 10–15 percentage points compared to the trivial decomposition across various problem sizes ( $n=10, 15, 20$ ).
- The SDP-based lower bounds for the submodularity ratio were tighter than existing spectral bounds.

Significance and Claims

The paper claims to build a new bridge between discrete optimization and real algebraic geometry. By connecting SOS-based algebraic certificates to submodularity, the authors provide a tractable, systematic framework for certifying and exploiting submodular structure where traditional combinatorial checks fail.

The significance lies in:

Tractability: Transforming a co-NP-complete verification problem into a polynomial-time SDP check (for fixed $t$ ).
Systematic Approach: Replacing ad-hoc, problem-specific insights for deriving bounds or decompositions with a unified algebraic framework.
Practical Utility: Demonstrating that enforcing algebraic submodularity constraints improves performance in regression and optimization tasks without the instability of non-convex neural network training.

The authors remain modest regarding the limitations, acknowledging that while the hierarchy is complete (any submodular function is eventually $t$ -sos submodular), the computational cost grows with $t$ and $n$ , and the method is currently most effective for low-degree functions or when moderate values of $t$ suffice. Future work is suggested in extending these results to unconstrained minimization via the Lasserre hierarchy and establishing formal statistical guarantees for the regression approach.