Sum of squares submodularity

We introduce the notion of t-sum of squares (sos) submodularity, which is a hierarchy, indexed by t, of sufficient algebraic conditions for certifying submodularity of set functions. We show that, for fixed t, each level of the hierarchy can be verified via a semidefinite program of size polynomial in 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-sos submodularity and identify submodularity-preserving operations that also preserve t-sos submodularity. We further present a complete classification of the cases for which submodularity and t-sos submodularity coincide, as well as examples of t-sos-submodular functions. We demonstrate the usefulness of 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 maximisation, and (iii) improved difference-of-submodular decompositions for difference-of-submodular optimisation.

Papers/Articles

Georgina Hall is an Assistant Professor of Decision Sciences at INSEAD. Her research focuses on convex relaxations of NP-hard problems, particularly those that arise in polynomial optimisation and problems on graphs. Prior to joining INSEAD in 2019, she was a postdoctoral student at INRIA. She completed her PhD in Operations Research and Financial Engineering at Princeton University in 2018. She is the recipient of the 2018 INFORMS Optimization Society Young Researcher’s Prize and the 2020 Information Theory Society Paper Award, among other awards.

For more information about the ESD Seminar, please email esd_invite@sutd.edu.sg