no. 16 · Tuesday 17 November 2026
Convergence rates of moment–SOS hierarchies with correlative sparsity via gluing and projection
Abstract
This paper studies convergence rates of moment–SOS hierarchies with correlative sparsity. Following the method proposed in~\cite{tran}, we bound the Hausdorff distance between the set of sparse truncated moment sequences and sparse truncated pseudo-moment sequences. The central step is a quantitative gluing lemma on a clique tree: local moment errors and separator discrepancies in total variation control the error of a joint approximating measure. Over hypercube, polynomial kernels give the convergence rates $O((\log_2r)^3/r^2)$ for the correlative sparse quadratic module and $O(r^{-2})$ for the correlative sparse preordering, where the certificate degree is $2r$. On compact basic semialgebraic sets, slack variable lifting and global atom projection yield $O((\log_2r)^{3\Lo/2}/r^{\Lo})$ and $O(r^{-\Lo})$ with a Łojasiewicz exponent $0<\Lo \le1$. These bounds hold for fixed-degree Hausdorff distances and polynomial objective gaps. We also extend to result to the correlative sparse quadratic-module rate for scalar objectives with clique-local polynomial matrix constraints.
- fields
- Optimization and Control