Abstract
Polynomial optimization problems often arise in sequences indexed by dimension, and it is of interest to compute bounds on the optimal values of all problems in the sequence. Examples include certifying inequalities between symmetric functions or graph homomorphism densities that hold over vectors and graphs of all sizes, and computing the value of mean-field games viewed as limits of games with a growing number of players. In this paper, we study such any-dimensional polynomial problems using the theory of representation stability, and we develop a systematic framework to produce hierarchies of bounds for their limiting optimal values in terms of finite-dimensional polynomial optimization problems. Our bounds are obtained by solving finite-dimensional polynomial optimization problems (or their relaxations). These bounds converge at explicit rates, and they follow as a consequence of new de Finetti-type theorems pertaining to sequences of random arrays projecting onto each other in different ways. We apply our framework to produce new bounds on problems arising in a number of application domains such as mean-field games, extremal graph theory, and symmetric function theory, and we illustrate our methods via numerical experiments.
The Challenge of Infinite-Dimensional Scaling
Polynomial optimization problems (POPs) are a cornerstone of computational mathematics, yet they are notoriously NP-hard. This complexity is compounded when problems are defined across a sequence of dimensions $n$. In fields like extremal combinatorics, one might seek to prove an inequality for graphs of all possible sizes, or in symmetric function theory, certify that a polynomial remains non-negative regardless of the number of variables.
Finding the limiting optimal value ($u_\infty$) as $n \to \infty$ is generally undecidable. While standard techniques like Sum-of-Squares (SOS) can bound a POP in a fixed dimension, they do not naturally extend to the infinite-dimensional limit. This paper addresses this gap by asking: how can we systematically construct a sequence of finite-dimensional problems whose optimal values provide guaranteed, converging lower bounds on the infinite-dimensional limit?
Methodology: Representation Stability and de Finetti Theorems
The authors utilize representation stability to study how group representations stabilize as dimension grows. The framework involves three key steps:
- Formalizing Sequences: Problems are categorized by how variables relate across dimensions—for example, through "zero-padding" a vector or "duplicating" its entries. These are termed freely-described POPs.
- Generalized de Finetti Theorems: The authors generalize the classical de Finetti theorem, which states that infinite exchangeable sequences are mixtures of i.i.d. sequences. Using category theory, they define random actions that project high-dimensional measures onto lower-dimensional ones.
- Constructing Lower Bounds: By mapping the intractable freely-described problem to a freely-symmetrized problem, the authors create a fixed-dimensional polynomial cost function. Solving this finite-dimensional problem yields a strict lower bound ($\ell_n$) on the infinite-dimensional limit.
Key Results and Numerical Validation
The framework provides explicit, non-asymptotic convergence rates: $O(1/n)$ for duplication-based sequences and $O(1/\sqrt{n})$ for zero-padding-based sequences.
Numerical experiments, such as those involving mean-field games, validate these theoretical rates. As shown in the figures, the gap between the computed upper bounds ($u_n$) and lower bounds ($\ell_n$) closes as $n$ increases, with the error $u_n - \ell_n$ tracking closely with the predicted theoretical bounds.
Beyond convergence rates, a significant advantage of this approach is its ability to bypass Sum-of-Squares limitations. The authors successfully proved the non-negativity of a specific degree-6 symmetric function that is not a sum-of-squares for any $n \ge 2$, a task where traditional algebraic geometry relaxations would fail.
Conclusion and Future Directions
This work bridges representation stability and probability to offer a powerful new tool for any-dimensional optimization. Future research may explore the tightness of the $O(1/\sqrt{n})$ rate, as empirical evidence suggests faster convergence in practice. Additionally, identifying problem classes that exhibit finite-step convergence and extending the framework to representations of groups beyond permutations (such as Lie groups) remain promising avenues for expanding the reach of these generalized de Finetti theorems.
Summary updated