Convergence rates for sums-of-squares hierarchies with correlative sparsity

Milan Korda, Victor Magron, Rodolfo Rios-ZertucheMath. Program 2023 · DOI · OpenReview

TL;DR

This paper introduces and analyzes "sparse" versions of sums-of-squares (SOS) hierarchies for polynomial optimization. The key takeaway is that these sparse methods achieve polynomial convergence rates that depend on the structure of the problem's sparsity graph (specifically, the largest clique size) rather than the ambient dimension, potentially outperforming dense methods for certain problems.

What Problem Does This Paper Address?

Polynomial optimization problems (POPs) are notoriously difficult, often falling into the NP-hard category. A common approach to tackle these problems is using sums-of-squares (SOS) hierarchies, which provide a sequence of increasingly accurate lower bounds on the global minimum of a polynomial. These hierarchies are based on powerful theoretical results like the Putinar and Schmüdgen Positivstellensätze. However, the computational cost of these hierarchies grows rapidly with the number of variables (ambient dimension) and the degree of the polynomials involved. This paper addresses the challenge of reducing this computational burden by exploiting "correlative sparsity" – a structure where polynomials depend on specific subsets of variables. The goal is to develop sparse SOS hierarchies that are computationally cheaper and achieve comparable or better convergence rates than their dense counterparts.

Methods

The authors develop sparse versions of both the Schmüdgen and Putinar SOS hierarchies. The core idea is to adapt existing techniques, particularly those related to Jackson kernels and approximation theory, to handle the variable separation introduced by sparsity. They leverage "running intersection property" for sets of variables associated with different polynomials, which is crucial for decomposing the problem. The analysis involves deriving explicit convergence rates for these sparse hierarchies, showing they depend on the size of the largest clique in the sparsity graph rather than the ambient dimension. This is achieved through careful analysis of approximation properties of specialized kernels and by adapting proofs from prior work on dense hierarchies.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Sparsity is Key: The paper demonstrates that exploiting correlative sparsity can lead to significant computational advantages in polynomial optimization.
  • Dimension Independence (Almost): The convergence rates of the sparse hierarchies depend on the structure of the sparsity graph (largest clique size), not directly on the ambient dimension. This is a crucial insight, as it suggests that for problems with limited "interdependence" between variables, sparse methods can be much more efficient.
  • Surprising Performance: The authors show that sparse SOS hierarchies can asymptotically outperform dense ones, even for a fixed computation time, provided the largest clique size is sufficiently small compared to the ambient dimension. This is a non-intuitive result that highlights the power of exploiting problem structure.
  • Unified Framework: The paper provides a unified analysis for both Schmüdgen and Putinar type sparse hierarchies, offering a comprehensive view of their convergence properties.

Key Results

The paper establishes polynomial convergence rates for sparse Schmüdgen and Putinar SOS hierarchies. The key quantitative result is that these rates depend on the size of the largest clique in the sparsity graph, denoted by $J$, rather than the ambient dimension $n$. Specifically, the authors show that for certain conditions, the computational complexity of the sparse methods scales with powers of $J$ and the degree, rather than $n$. This leads to the conclusion that sparse methods can be more efficient than dense methods when $J$ is significantly smaller than $n$. For instance, Proposition 3 shows that the ratio of sparse to dense computational complexity tends to zero if $n$ is large enough compared to $|J_j|(|J_j| + 3)$.

Limitations and Future Work

The paper focuses on theoretical convergence rates and does not provide empirical results or comparisons on specific large-scale problems. The analysis relies on specific assumptions about the problem structure (e.g., the running intersection property) and the properties of the polynomials involved. Future work could involve extending these results to more general sparsity patterns, exploring practical implementations of these sparse hierarchies, and conducting empirical studies to validate the theoretical advantages on real-world applications. The paper also mentions the potential for these methods to tackle problems in areas like quantum correlations and robustness certification, suggesting these as avenues for future research.

Summary updated

Abstract

This work derives upper bounds on the convergence rate of the moment-sum-of-squares hierarchy with correlative sparsity for global minimization of polynomials on compact basic semialgebraic sets. The main conclusion is that both sparse hierarchies based on the Schm\"udgen and Putinar Positivstellens\"atze enjoy a polynomial rate of convergence that depends on the size of the largest clique in the sparsity graph but not on the ambient dimension. Interestingly, the sparse bounds outperform the best currently available bounds for the dense hierarchy when the maximum clique size is sufficiently small compared to the ambient dimension and the performance is measured by the running time of an interior point method required to obtain a bound on the global minimum of a given accuracy.
BibTeX
@article{korda2023convergence,
  author = {Milan Korda and Victor Magron and Rodolfo Rios-Zertuche},
  title = {{Convergence rates for sums-of-squares hierarchies with correlative sparsity}},
  journal = {Math. Program.},
  year = {2023},
  doi = {10.1007/s10107-024-02071-6},
}
Figure