The Moment-Sum-of-Squares Hierarchy

340 concepts239 papers1 proposal

Many fundamental problems across machine learning, control theory, and quantum mechanics boil down to optimizing a polynomial function over a set defined by polynomial inequalities. For instance, finding a hidden clique in a random graph, decomposing a high-dimensional tensor, or computing the optimal control law for a nonlinear system are all instances of polynomial optimization. Unfortunately, these problems are generally non-convex and NP-hard.

To bypass this intractability, researchers rely on a systematic framework known as the Moment-Sum-of-Squares (Moment-SOS) hierarchy (or the Lasserre hierarchy). The core insight of this framework is to replace a difficult, non-convex optimization problem over individual points with a sequence of convex, semidefinite programming (SDP) relaxations. By increasing the degree of the polynomials considered in these relaxations, we can systematically trade computational time for tighter approximations, eventually converging to the global optimum.

The Primal View: From Points to Measures

To understand why the hierarchy works, let us first look at the problem through its primal formulation. Suppose we want to minimize a polynomial $f(x)$ over a compact set $K$ defined by polynomial constraints.

Instead of searching for a single optimal point $x^* \in K$, imagine we search instead for a probability measure $\mu$ supported entirely on $K$. The original problem can be exactly rewritten as minimizing the expected value of $f(x)$ under this measure:

$$\min_{\mu} \mathbb{E}_{\mu}[f(x)] = \int_K f(x) d\mu(x)$$

Because the objective function and the constraints are now linear with respect to the measure $\mu$, this transformation turns a non-convex problem into a linear program. The catch is that the space of all probability measures is infinite-dimensional, making this program impossible to solve directly.

To make it tractable, we truncate the problem. A polynomial objective depends only on a finite combination of variables, meaning we do not need the full measure $\mu$; we only need its moments (e.g., $\mathbb{E}[x_1], \mathbb{E}[x_1^2], \mathbb{E}[x_1x_2]$) up to a certain degree. If we define a sequence of numbers $y = (y_\alpha)$ to represent these pseudo-moments, how do we guarantee that $y$ actually corresponds to a valid probability measure? This is the classical Markov moment problem, explored computationally by Jean B. Lasserre in works like Borel measures with a density on a compact semi-algebraic set.

The key insight is that if $y$ comes from a real measure, then the expectation of any squared polynomial must be non-negative: $\mathbb{E}_\mu[p(x)^2] \ge 0$. If we express $p(x)$ as a vector of coefficients $c$ times a vector of monomials $v_d(x)$ up to degree $d$, this expectation becomes a quadratic form:

$$\mathbb{E}_\mu[p(x)^2] = c^T \mathbb{E}_\mu[v_d(x)v_d(x)^T] c = c^T M_d(y) c \ge 0$$

where $M_d(y)$ is the moment matrix. Requiring $c^T M_d(y) c \ge 0$ for all $c$ is exactly equivalent to stating that $M_d(y)$ must be a positive semidefinite (PSD) matrix. By enforcing this PSD constraint alongside similar constraints for the boundary conditions (via localizing matrices), we obtain a standard semidefinite program (SDP) that can be solved efficiently in polynomial time.

The Dual View: Certifying Positivity via Sum-of-Squares

Every optimization problem has a dual. The dual of minimizing $f(x)$ over $K$ is maximizing a lower bound $\lambda$ such that $f(x) - \lambda \ge 0$ for all $x \in K$. Proving that a polynomial is globally non-negative is notoriously difficult (co-NP-hard). However, we can use a powerful algebraic proxy: if a polynomial can be written as a Sum of Squares (SOS) of other polynomials, it is guaranteed to be non-negative.

How do we check if a polynomial $p(x)$ of degree $2d$ is an SOS? We look for a PSD matrix $Q$ such that:

$$p(x) = v_d(x)^T Q v_d(x)$$

Expanding the right-hand side and matching the coefficients of each monomial with those of $p(x)$ yields a set of linear equations on the entries of $Q$. Finding a matrix $Q$ that is both PSD and satisfies these linear equations is, once again, a semidefinite program.

By leveraging algebraic certificates of positivity—such as Putinar's Positivstellensatz, studied in this context by Jean B. Lasserre et al. in Positivity and Optimization for Semi-Algebraic Functions—we can represent positive polynomials using weighted sums of squares. As we increase the allowed degree $2d$ of our SOS polynomials, our lower bounds tighten monotonically, asymptotically converging to the true global minimum.

Algorithmic Power in High-Dimensional Estimation

The Moment-SOS framework has transitioned from pure mathematics into a workhorse for algorithm design. In high-dimensional statistics, it has been instrumental in breaking long-standing computational barriers.

For instance, in Tensor Principal Component Analysis (PCA), traditional spectral methods fail when the signal-to-noise ratio drops below a certain threshold. Samuel B. Hopkins et al. demonstrated in Tensor principal component analysis via sum-of-square proofs that a low-degree SoS relaxation can recover hidden signals well below this traditional spectral barrier. Similarly, Samuel B. Hopkins et al. leveraged the hierarchy in Mixture models, robustness, and sum of squares proofs to design robust estimators for Gaussian mixture models, translating abstract algebraic proofs directly into polynomial-time algorithms.

Beyond statistics, the framework offers powerful tools for dynamical systems and control. By rephrasing nonlinear optimal control problems via occupation measures, Jean B. Lasserre et al. showed in Nonlinear optimal control synthesis via occupation measures how to approximate optimal value functions and synthesize near-optimal feedback control laws. This measure-centric approach allows engineers to compute guaranteed inner approximations of non-convex stability regions (Didier Henrion et al. in Inner Approximations for Polynomial Matrix Inequalities and Robust Stability Regions) and handle impulsive control problems (Magda Claeys et al. in Measures and LMI for impulsive optimal control with applications to space rendezvous problems).

Mapping the Limits of Computation

While the hierarchy guarantees convergence as the degree $d$ goes to infinity, the size of the resulting SDP grows combinatorially as $O(n^d)$. Therefore, the hierarchy is practically useful only for low degrees (such as $d=2$ or $d=4$). This limitation has turned the SoS hierarchy into the ultimate benchmark for understanding the boundary between statistical possibility and computational feasibility.

Remarkably, the limits of the SoS hierarchy often reflect the limits of all polynomial-time algorithms. James R. Lee et al. proved a fundamental equivalence in Lower bounds on the size of semidefinite programming relaxations, showing that any polynomial-sized SDP relaxation for constraint satisfaction problems is no more powerful than a low-degree SoS relaxation.

Consequently, proving that a low-degree SoS algorithm fails on a problem strongly suggests that the problem is computationally intractable for any efficient algorithm. For example, Raghu Meka et al. established tight lower bounds for the planted clique problem in Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique, while Tengyu Ma et al. demonstrated in Sum-of-Squares Lower Bounds for Sparse PCA that degree-4 SoS relaxations cannot bridge the statistical-computational gap in Sparse PCA. These lower bounds help map out the precise "information-theoretic vs. computational" trade-offs inherent in high-dimensional learning problems.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 254 papers
  2. Version 1 · 2026-10-04 · 354 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_semidefinite_programming_relaxation_ca9be9b9,
  title = {semidefinite programming relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semidefinite-programming-relaxation/rdr_ca9be9b9af29430b8a8d17584a828539},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_semidefinite_programming_relaxation_ca9be9b9_v2,
  title = {semidefinite programming relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/semidefinite-programming-relaxation/rdr_ca9be9b9af29430b8a8d17584a828539/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake