Sum of Squares Submodularity

Anna Deza and Georgina Hall · 2025

Read Sum of Squares Submodularity by Anna Deza and Georgina Hall (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24550.txt.

Introduction

Anna Deza and Georgina Hall, two authors, link two fields of optimization. Submodular functions show diminishing returns: later additions help less. Testing if a set function is submodular is known to be hard. Sum of squares methods certify that polynomials are never negative. The pair blend the two into a new ladder of tests.

Each rung of the ladder is a stronger algebraic test. For a fixed rung, a semidefinite program checks the test fast. That check runs in time polynomial in the ground set size. They give equal forms of the test and operations that keep it. They also sort when the test matches submodularity exactly. Three uses follow: regression, ratio bounds, and splitting hard functions. The work bridges discrete optimization and real algebraic geometry.

Catalog record

CREATORAnna Deza and Georgina Hall
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE120 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-24550

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sum of Squares Submodularity Anna Deza and Georgina Hall Abstract We introduce the notion of t t -sum of squares (sos) submodularity , which is a hierarchy, indexed by t t , of sufficient algebraic conditions for certifying submodularity of set functions. We show that, for fixed t t , each level of the hierarchy can be verified via a semidefinite program of size polynomial in n n , the size of the ground set of the set function. This is particularly relevant given existing hardness results around testing whether a set function is submodular ( Crama 1989 ) . We derive several equivalent algebraic characterizations of t t -sos submodularity and identify submodularity-preserving operations that also preserve t t -sos submodularity. We further present a complete classification of the cases for which submodularity and t t -sos submodularity coincide, as well as examples of t t -sos-submodular functions. We demonstrate the usefulness of t t -sos submodularity through three applications: (i) a new convex approach to submodular regression, involving minimal manual tuning; (ii) a systematic procedure to derive lower bounds on the submodularity ratio in approximate submodular maximization, and (iii) improved difference-of-submodular decompositions for difference-of-submodular optimization. Overall, our work builds a new bridge between discrete optimization and real algebraic geometry by connecting sum of squares–based algebraic certificates to a fundamental discrete structure, submodularity. Keywords: submodularity, sum of squares polynomials, approximate submodularity, submodular regression, difference of submodular optimization 1 Preliminaries To make this paper self-contained, we review some topics relating to submodularity, set functions, and sum of squares polynomials, which are used throughout the paper. 1.1 Submodular functions Let \Omega be a set of cardinality n and let 2^{\Omega} be its power set, that is, the set of all subsets of \Omega . A set function is a function f:2^{\Omega}\rightarrow\mathbb{R}. An example of a set function is the cut function of a graph G=(V,E) for |V|=n , which maps a subset S of nodes to the number of edges between S and V\backslash S . Submodularity is a property of set functions, with many equivalent definitions, which we give now. Definition 1 . ( Nemhauser et al. 1978 , Proposition 2.1) . A set function f:2^{\Omega}\rightarrow\mathbb{R} is submodular if any one of the seven equivalent conditions below hold: (i) f(S)+f(T)\geq f(S\cup T)+f(S\cap T),~\forall S,T\subseteq\Omega. (ii) f(S\cup\{i\})-f(S)\geq f(T\cup\{i\})-f(T),~\forall S,T\subseteq\Omega such that S\subseteq T and i\notin T . (iii) f(S\cup\{i\})-f(S)\geq f(S\cup\{i,j\})-f(S\cup\{j\}),~\forall S\in\Omega,~i,j\in\Omega\backslash S,~i\neq j . (iv) f(T)\leq f(S)+\sum_{i\in T\backslash S}(f(S\cup\{i\})-f(S))-\sum_{i\in S\backslash T}(f(S\cup T)-f(S\cup T\backslash\{i\})),~\forall S,T\subseteq\Omega. (v) f(T)\leq f(S)+\sum_{i\in T\backslash S}(f(S\cup\{i\})-f(S)),~\forall S\subseteq T\subseteq\Omega . (vi) f(T)\leq f(S)-\sum_{i\in S\backslash T}(f(S)-f(S\backslash\{i\})),~\forall T\subseteq S\subseteq\Omega . (vii) f(T)\leq f(S)-\sum_{i\in S\backslash T}(f(S)-f(S\backslash i))+\sum_{i\in T\backslash S}(f(S\cap T\cup\{i\})-f(S\cap T)),~\forall S,T\subseteq\Omega. The cut function is a submodular function (see Section 1.2 ). The functions for which the inequalities in the definitions hold with equality are modular functions . Obviously, any modular function is submodular, and it can be shown that any modular function is of the form \sum_{i\in\Omega}c_{i} , for \{c_{i}\}_{i\in\Omega}\in\mathbb{R} . Of all the definitions given above, (i) is typically used as the “canonical” definition, despite (ii) being the definition that encodes the diminishing returns property, as discussed in the introduction. Definition (iii) is widely known as well. Definitions (iv) - (vii) appear considerably less in the literature, though we shall see that (v) is convenient for one of the applications we consider. 1.2 Multilinear extensions of set functions There is a one-to-one correspondence between set functions over \Omega and multilinear polynomials in n variables, through the multilinear extension of a set function. Before defining this polynomial, we introduce some relevant notation. Let x\mathrel{\mathop{:}}=(x_{1},\ldots,x_{n}) and denote by \mathbb{R}[x] the set of polynomials in variables x with coefficients in \mathbb{R}. For any p\in\mathbb{R}[x], we use \deg(p) to denote the degree of p . A polynomial in \mathbb{R}[x] is said to be multilinear if all of its monomials contain only variables that are to the power of at most 1. For example, the polynomial x_{1}x_{2}+x_{2}-1 is multilinear, whereas x_{1}^{2}+x_{1}x_{2} is not. By definition, the degree of any multilinear polynomial in \mathbb{R}[x] is less than or equal to n . Furthermore, the derivative of a multilinear polynomial with respect to coordinate i does not depend on x_{i} . Throughout, we use 1_{S} for the indicator function of a set S. We now define the multilinear extension of a set function. Definition 2 . The multilinear extension (MLE) F of a set function f:2^{\Omega}\rightarrow\mathbb{R} is the unique multilinear polynomial in \mathbb{R}[x] satisfying F(1_{S})=f(S) for all S\subseteq\Omega. In the remainder, we maintain the convention of using lowercase letters for set functions (e.g., f,g ) and uppercase letters (e.g., F,G ) for their MLEs. Existence of the MLE is straightforward by noting that the polynomial F(x)=\sum_{T\subseteq\Omega}f(T)\prod_{i\in T}x_{i}\prod_{i\notin T}(1-x_{i}) is multilinear. One can equivalently write (see, e.g., ( Grabisch et al. 2000 ) ) F(x)=\sum_{T\subseteq\Omega}a(T)\prod_{i\in T}x_{i},\text{ where }a(T)=\sum_{S\subseteq T}(-1)^{t-s}f(S). A proof of uniqueness can be found in ( Owen 1972 ) . This result enables us to define the degree , \deg(f) , of a set function f , which is none other than the degree of its multilinear extension. As an example, one can check that the MLE of the cut function introduced above is F(x_{1},\ldots,x_{n})=\sum_{1\leq i<j\leq n}A_{ij}(x_{i}-2x_{i}x_{j}+x_{j}), where A_{ij} is entry (i,j) of the adjacency matrix A of G . Therefore, the cut function has degree 2 . The equivalence between set functions and multilinear polynomials implies that Definition 1 , which involves a set function f , has a counterpart involving its MLE, F . For x,y\in\mathbb{R}^{n} , we denote by x\circ y the component-wise multiplication of x and y , that is, x\circ y=(x_{1}y_{1},\ldots,x_{n}y_{n}). Proposition 3 . Let f:2^{\Omega}\rightarrow\mathbb{R} be a set function and let F be its multilinear extension. We have that f is submodular if and only if any one of the following seven equivalent conditions holds: (i’) F(x)+F(y)\geq F(x+y-x\circ y)+F(x\circ y),\forall x,y\in\{0,1\}^{n} . (ii’) \frac{\partial F(x)}{\partial x_{i}}\geq\frac{\partial F(y)}{\partial x_{i}},~\forall x,y\in\{0,1\}^{n} such that x\leq y , ~\forall i=1,\ldots,n . (iii’) \frac{\partial^{2}F(x)}{\partial x_{i}\partial x_{j}}\leq 0,\forall x\in\{0,1\}^{n},\forall i,j=1,\ldots,n. (iv’) F(x)-F(y)+\sum_{i=1}^{n}y_{i}(1-x_{i})\cdot\frac{\partial F(x)}{\partial x_{i}}-\sum_{i=1}^{n}x_{i}(1-y_{i})\cdot\frac{\partial F(x+y-x\circ y)}{\partial x_{i}}\geq 0,~\forall x,y\in\{0,1\}^{n} . (v’) F(x)-F(y)+\sum_{i=1}^{n}(y_{i}-x_{i})\cdot\frac{\partial F(x)}{\partial x_{i}}\geq 0,~\forall x,y\in\{0,1\}^{n}\text{ such that }x\leq y. (vi’) F(y)-F(x)-\sum_{i=1}^{n}(y_{i}-x_{i})\cdot\frac{\partial F(y)}{\partial x_{i}}\geq 0,~\forall x,y\in\{0,1\}^{n}\text{ such that }x\leq y. (vii’) F(y)-F(x)-\sum_{i=1}^{n}y_{i}(1-x_{i})\frac{\partial F(y)}{\partial x_{i}}+\sum_{i=1}^{n}x_{i}(1-y_{i})\frac{\partial F(x\circ y)}{\partial x_{i}}\geq 0,~\forall x,y\in\{0,1\}^{n}. The proof of this proposition is straightforward: it involves showing that (i^{\prime}) (resp. (ii^{\prime}) - (vii^{\prime}) ) is equivalent to (i) (resp. (ii) - (vii) ), by translating set function operations into algebraic ones via the indicator function, and making use of a property of the derivative of a multilinear polynomial given in Appendix A.1 . It is ommitted for brevity. Conditions (ii^{\prime})-(iii^{\prime}) and, by extension, (ii)-(iii) are referred to as the first and second order characterizations of submodularity, due to the presence of the first and second-order derivatives. They are folklore in the submodularity literature ( Topkis 1978 ) . A zero-th order characterization of submodularity exists as well, though it does not quite correspond to (i^{\prime}) . It is given by F(x)+F(y)\geq F(\max\{x,y\})+F(\min\{x,y\}),\forall x,y\in\{0,1\}^{n}. We replace this condition by (i^{\prime}) (which seems to be new, though quite elementary) in order to operate within the set of polynomials. Indeed, F(\max\{x,y\})+F(\min\{x,y\}) is not a polynomial, and using the zero-th order characterization from the literature would prevent

Read the complete text