REVIEW 2 major objections 4 minor 1 cited by
Convergence rates for polynomial optimization on set products
T0 review · 2 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper proves that the sum-of-squares relaxation hierarchy on the product of two unit spheres converges to the global minimum at an explicit quadratic rate.
desk verdict Solid extension of the kernel method to the bi-sphere, with a real but likely cosmetic Gegenbauer index bug that must be fixed before the main proof is fully supported. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the perturbed product kernel $K_{2t}((x,y),(x',y');\lambda) = C_{2t}(x,x';\lambda)\,C_{2t}(y,y';\lambda)$, where each factor is the Christoffel–Darboux kernel of the unit sphere with eigenvalues $\lambda_k$ taken from a univariate sum of squares. The product kernel lies in the Schmüdgen preordering $T(X)_{4t}$ for each fixed second argument, so the associated integral operator sends nonnegative polynomials to certificates (property P2); because $\lambda_0=1$ it preserves constants (P1); and its action on a degree-$d$ polynomial is $K_{2t}q = \sum_{k+s\leq d} \lambda_k \lambda_s q_{k,s}$, so the distance from the identity is a sum of products of eigenvalue deviations, bounded by Bernoulli's identity. The harmonic constant $\gamma(S^{n-1})_d$ controls the sup-norm size of each bivariate harmonic block.
What would settle it
To test the core rate, take small parameters such as $n=3$, $d=2$ and $t=\lceil 2 n d \sqrt{d}\rceil$, solve for the minimal possible value of $\sum_{k=1}^d (1-\lambda_k)$ over univariate sums of squares of degree $2t$ with $\lambda_0=1$ and $1/2\le\lambda_k\le1$, and compare it with $n^2 d^3/t^2$; a value above the bound would falsify Lemma 6 and break the proof of Theorem 3.
Extended reading notes
Core claim
The paper's central claim is Theorem 3: for $X = S^{n-1} \times S^{n-1}$ and any polynomial $q$ of degree $d$, for every $t \geq 2 n d \sqrt{d}$, one has $q_{\min} - \mathrm{lb}(q,T(X))_{2t} \leq (8 n^2 d^3 \binom{d+2}{2} \gamma(S^{n-1})_d^2 / t^2)(q_{\max}-q_{\min})$. Since the two sphere equalities make the preordering and the quadratic module coincide, the same rate also covers Putinar-type bounds. The proof constructs a linear operator from a product of two perturbed Christoffel–Darboux kernels that maps nonnegative polynomials into the certificate cone, fixes constants, and is within $O(1/t^2)$ of the identity on degree-$d$ polynomials. The paper then extends this result to products of $m$ spheres and to arbitrary products of sets that admit kernel rates, and applies the bi-sphere rate to the order-2 quantum Wasserstein distance hierarchy.
Load-bearing premise
The quadratic rate rests on a quoted, unproved eigenvalue-perturbation bound for the Christoffel–Darboux kernel (Lemma 6, from [FF21]), and the quantum Wasserstein application adds the assumption that the dual moment problem is attained at a bounded tuple.
Editorial extensions
If this is right
- On the bi-sphere, the Schmüdgen-type and Putinar-type hierarchies both achieve a certified $O(1/t^2)$ convergence rate, with constants polynomial in $n$ and $d$, instead of the general $O(1/t^c)$ available for arbitrary compact semialgebraic sets.
- For products of $m$ spheres, the same quadratic rate holds with explicit constant $m^{2m} n^2 d^3 \binom{d+m}{m} \gamma(S^{n-1})_d^m$, at certificate degree $2mt$.
- Any two sets that each admit a kernel-based convergence rate yield a product set with a convergence rate governed by the slower factor; the proof lists spheres, balls, simplices and hypercubes as admissible factors.
- The moment hierarchy for the order-2 quantum Wasserstein distance satisfies $0 \leq W_2^2(\rho,\nu) - W_2^2(\rho,\nu)_{2t} \leq \kappa(n,\rho,\nu)/t^2$ for $t \geq 32n$, assuming the dual is attained at a bounded tuple.
- The same rates transfer to upper-bound hierarchies and to generalized moment problems supported on set products, as the paper's closing discussion notes.
Reading between the lines
- Theorem 9's hypotheses are effectively a black-box interface: any future factor set with its own kernel rate can be slotted into product rate statements, so the method is likely to cover mixed products such as a sphere times a hypercube even though the paper does not spell that example out.
- The bounded-dual assumption in Theorem 11 looks removable in practice: the primal is always feasible by spectral decompositions, so a perturbation or regularization of the dual might yield a rate under weaker conditions.
- A numerical scan of small instances, such as $n=3$, $d=2$ on the bi-sphere, could show whether the threshold $t \geq 2 n d \sqrt{d}$ is tight or merely sufficient, which would help users set relaxation orders efficiently.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Schmüdgen-type Lasserre hierarchy for polynomial optimization on Cartesian products of compact basic semialgebraic sets, focusing on the bi-sphere S^{n-1} × S^{n-1}. The main result (Theorem 3) claims an O(1/t^2) convergence rate with explicit constants for the lower bounds lb(q,T(X))_{2t} for every polynomial q of degree d and every t ≥ 2 n d sqrt(d), using the polynomial kernel method: a product of two perturbed Christoffel–Darboux kernels, whose coefficients come from a univariate sum of squares in Gegenbauer polynomials. The proof follows the strategy of Fang–Fawzi, Slot, and Laurent–Slot. Extensions are given to products of m spheres (Theorem 8) and to products of distinct sets for which similar rates are already known (Theorem 9). The final section applies the bi-sphere rate, after a complex-to-real change of variables, to a moment-SOS hierarchy for the order-2 quantum Wasserstein distance, obtaining an O(1/t^2) rate under an explicit bounded-dual-attainment assumption (Theorem 11).
Significance. If the results are correct, the paper gives a genuine extension of the known O(1/t^2) rate for the sphere to a product of spheres, with explicit, degree- and dimension-dependent constants and no fitted parameters. The transposition of these rates to the quantum Wasserstein hierarchy is new and, together with the general recipe in Theorem 9, is likely to be useful for other product-set problems. The main proof is built from external, citable lemmas rather than from opaque compactness arguments, which is a strength. The significance is conditional: the central kernel construction must be fixed before the main theorem can be relied upon, and the quantum application has an additional nonstandard assumption (bounded dual attainment) that is stated but limits the scope.
major comments (2)
- [Section 3.1, Eq. (12) and Lemma 6] The proof of property (P2) requires that, for each fixed x', the polynomial C_{2t}(x,x';λ) = ∑_{k=0}^{2t} λ_k G^{(n-1)}_k(x·x') is a sum of squares in x. The manuscript invokes Lemma 6 for this statement, but Lemma 6 supplies a univariate sum of squares in the basis G^{(n)}_k, not G^{(n-1)}_k. Under the definitions in Section 2, G^{(n)} and G^{(n-1)} are different Gegenbauer families; for example, on the unit circle (n=2), Eq. (12) needs the Chebyshev-type family G^{(1)}_k, whereas Lemma 6 would supply an SOS in the Legendre-type family G^{(2)}_k. A sum of squares in one Gegenbauer basis does not automatically remain a sum of squares after replacing the basis by another one. Since property (P2) is load-bearing for the derivation of Theorem 3, the proof is incomplete as written. Please restate Lemma 6 with the same Gegenbauer parameter as Eq. (12) (or change Eq. (12) accordingly) and verify that the [FF21] result transfers to that basis. The same index ambiguity appears in Lemma 5, whose statement uses G^n_k(1) while its proof uses G^{(n-1)}_k(1).
- [Section 4.2 and Theorem 11] The rate theorem used for the quantum Wasserstein part, Theorem 3, concerns the preordering T(X) and its truncations. However, the real hierarchy (45) is defined through the one-sided truncated quadratic module T^R(XRe)_{2t} = { σ + q1(1-||a||^2-||b||^2) + q2(1-||c||^2-||d||^2) }, without the product of the two defining constraints. The proof cites [GLS22, Lemma 33] for an equivalence between complex and real cones, but it does not spell out why a certificate in the preordering used by Theorem 3 can be converted into a certificate in this smaller quadratic-module cone under the moment constraints, or why the optimal values of the two relaxations coincide. Without that step, the O(1/t^2) bound for the hierarchy (39)/(42) does not follow directly from Theorem 3. Please provide the precise statement of the cited equivalence for the truncated cones used here, or prove the needed transfer.
minor comments (4)
- [Theorem 9, Eq. (32)] The subscript of lb in Eq. (32) appears to be off by a factor of two relative to the convention in Eq. (6), where lb(q,T(X))_t is defined using T(X)_{2t}. The proof establishes membership in T(X)_{d1(t)+d2(t)}, so the lower bound should be indexed by (d1(t)+d2(t))/2, not by d1(t)+d2(t). As written, the statement and proof use inconsistent relaxation orders.
- [Lemma 5] Lemma 5 is stated for d,n ≥ 3, but Theorem 3 and Lemma 6 do not exclude n = 2. The harmonic constant γ(S^{n-1})_d is also meaningful for the circle; please state the range of validity explicitly or explain why n ≥ 3 suffices for the applications.
- [Section 4.3, item 3] The manuscript states that the maximum hmax of the entries of the four matrix polynomials involved in the equality constraints is equal to 2. On the real bi-sphere, entries such as a_i a_j + b_i b_j or c_i d_j - d_i c_j are bounded by 1, not by 2; the value 2 is a valid upper bound after a trivial normalization, but it should not be claimed as an exact maximum.
- [Throughout] Several small typos should be corrected: in Section 2, the kernel map is written 'C : S^{n-1} × S^{n-1} : R' and should have an arrow; in Section 4.3, the displayed polynomial for the Slater point omits the squares in ||a||, ||b||, ||c||, ||d|| and has unbalanced parentheses; and in Theorem 8 the lower-bound subscript appears as 'mt' in one place and '2mt' in the proof, which should be made consistent.
Circularity Check
No circular derivation in the main rate theorem; the quantum application's CM25 self-citation is not the source of the rate.
full rationale
The derivation of the central Theorem 3 is not circular. The rate is produced by the standard polynomial-kernel pipeline: a product kernel K_{2t}=C(x,x';lambda)C(y,y';lambda) is constructed, and the three operator properties (P1)-(P3) are checked. Property (P2) uses Lemma 4 from [Slo22] plus the fact that lambda is an SOS coefficient vector supplied by Lemma 6 from [FF21]; property (P3) uses the harmonic constant bound of Lemma 5, whose proof is adapted from [Slo22]. These are external results, not self-citations, and no parameter is fitted to data. The constants in (23) are explicit and depend only on n and d. The quantum Wasserstein application in Section 4 cites [CM25], a preprint coauthored by the present author, for the equivalence between W2^2 and the moment problem (37) and for the qualitative convergence of hierarchy (39). That self-citation is load-bearing only for identifying the problem and its hierarchy, not for the O(1/t^2) rate: Theorem 11 is obtained by combining Lemma 10 from [GM25] with Theorem 3 and the extra bounded-dual-attainment assumption. Hence the rate claim does not reduce to the cited self work. A separate technical caveat, not a circularity: Lemma 6 as stated supplies an SOS in G^{(n)} while the kernel (12) is expanded in G^{(n-1)}; if the index convention is not reconciled, the (P2) step is unsupported, but this is a correctness/verification gap, not a self-referential derivation.
Assumptions & free parameters
free parameters (1)
- Bounded dual norm M = ||Lambda||_1 + ||Gamma||_1 =
assumed finite, not quantified
assumptions (7)
- standard math Schmüdgen's Positivstellensatz: every polynomial positive on a compact basic semialgebraic set belongs to the preordering.
- standard math Putinar's Positivstellensatz for Archimedean quadratic modules.
- standard math Lemma 6 (from FF21): for every t >= 2 n d sqrt(d) there exists a univariate SOS eigenvalue sequence lambda with lambda_0=1, 1/2 <= lambda_k <= 1 and sum_{k=1}^d (1-lambda_k) <= n^2 d^3 / t^2.
- standard math Lemma 4 (from Slo22): if a kernel slice lies in a cone Q at each fixed second argument, then the kernel operator maps nonnegative polynomials into Q.
- domain assumption The dual of the quantum Wasserstein moment problem (38) is attained at a bounded tuple.
- ad hoc to paper The one-sided real quadratic module T^R(X_Re)_{2t} in (45) is an appropriate cone for applying the preordering-based rate from Theorem 3.
- domain assumption For equality constraints, the preordering and the quadratic module coincide.
Cite this review
Pith. "Pith review of Convergence rates for polynomial optimization on set products." pith.science (2026). https://pith.science/paper/JY2O3FQO
@misc{pith2026250518580,
author = {Pith},
title = {Pith review of: Convergence rates for polynomial optimization on set products},
year = {2026},
howpublished = {\url{https://pith.science/paper/JY2O3FQO}},
note = {Machine review of arXiv:2505.18580}
}
abstract
We consider polynomial optimization problems on Cartesian products of basic compact semialgebraic sets. The solution of such problems can be approximated as closely as desired by hierarchies of semidefinite programming relaxations, based on classical sums of squares certificates due to Putinar and Schm\"udgen. When the feasible set is the bi-sphere, i.e., the Cartesian product of two unit spheres, we show that the hierarchies based on the Schm\"udgen-type certificates converge to the global minimum of the objective polynomial at a rate in $O(1/t^2)$, where $t$ is the relaxation order. Our proof is based on the polynomial kernel method. We extend this result to arbitrary sphere products and give a general recipe to obtain convergence rates for polynomial optimization over products of distinct sets. Eventually, we rely on our results for the bi-sphere to analyze the speed of convergence of a semidefinite programming hierarchy approximating the order $2$ quantum Wasserstein distance.
Forward citations
Cited by 1 Pith paper
-
Convergence rates of Sum-of-Hermitian-Squares Hierarchies for the Pauli algebra
Explicit convergence rates for noncommutative SOS hierarchies on the Pauli algebra are bounded using smallest roots of Krawtchouk polynomials.
Reference graph
Works this paper leans on
-
[1]
Order p quantum W asserstein distances from couplings
Emily Beatty and Daniel Stilck França. Order p quantum W asserstein distances from couplings. arXiv preprint arXiv:2402.16477 , 2024
arXiv 2024
-
[2]
Alexander Taveira Blomenhofer and Monique Laurent. Moment-sos and spectral hierarchies for polynomial optimization on the sphere and quantum de finetti theorems. arXiv preprint arXiv:2412.13191 , 2024
arXiv 2024
-
[3]
On the effective Putinar's Positivstellensatz and moment approximation
Lorenzo Baldi and Bernard Mourrain. On the effective Putinar's Positivstellensatz and moment approximation . Mathematical Programming , 200(1):71--103, 2023
work page 2023
-
[4]
Degree bounds for Putinar’s Positivstellensatz on the hypercube
Lorenzo Baldi and Lucas Slot. Degree bounds for Putinar’s Positivstellensatz on the hypercube . SIAM Journal on Applied Algebra and Geometry , 8(1):1--25, 2024
work page 2024
-
[5]
Approximating the order 2 quantum Wasserstein distance using the moment-SOS hierarchy
Saroj Prasad Chhatoi and Victor Magron. Approximating the order 2 quantum Wasserstein distance using the moment-SOS hierarchy . forthcoming , 2025
work page 2025
-
[6]
The quantum Wasserstein distance of order 1
Giacomo De Palma, Milad Marvian, Dario Trevisan, and Seth Lloyd. The quantum Wasserstein distance of order 1 . IEEE Transactions on Information Theory , 67(10):6627--6643, 2021
2021
-
[7]
Distinguishing separable and entangled states
Andrew C Doherty, Pablo A Parrilo, and Federico M Spedalieri. Distinguishing separable and entangled states. Physical Review Letters , 88(18):187904, 2002
work page 2002
-
[8]
The sum-of-squares hierarchy on the sphere and applications in quantum information theory
Kun Fang and Hamza Fawzi. The sum-of-squares hierarchy on the sphere and applications in quantum information theory. Mathematical Programming , 190(1):331--360, 2021
work page 2021
Show all 38 references
-
[9]
Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube
Sander Gribling, Etienne de Klerk, and Juan Vera. Revisiting the convergence rate of the Lasserre hierarchy for polynomial optimization over the hypercube . arXiv preprint arXiv:2505.00544 , 2025
2025
-
[10]
Bounding the separable rank via polynomial optimization
Sander Gribling, Monique Laurent, and Andries Steenkamp. Bounding the separable rank via polynomial optimization. Linear Algebra and its Applications , 648:1--55, 2022
2022
-
[11]
The Effective Generalized Moment Problem
Lucas Gamertsfelder and Bernard Mourrain. The Effective Generalized Moment Problem . arXiv preprint arXiv:2501.09385 , 2025
2025 arXiv
-
[12]
The Moment-SOS Hierarchy: Lectures In Probability, Statistics, Computational Geometry, Control And Nonlinear PDEs , volume 4
Didier Henrion, Milan Korda, and Jean Bernard Lasserre. The Moment-SOS Hierarchy: Lectures In Probability, Statistics, Computational Geometry, Control And Nonlinear PDEs , volume 4. World Scientific, 2020
2020
-
[13]
Optimality conditions for homogeneous polynomial optimization on the unit sphere
Lei Huang. Optimality conditions for homogeneous polynomial optimization on the unit sphere. Optimization Letters , 17(5):1263--1270, 2023
2023
-
[14]
Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets
Milan Korda and Didier Henrion. Convergence rates of moment-sum-of-squares hierarchies for volume approximation of semialgebraic sets. Optimization Letters , 12:435--442, 2018
2018
-
[15]
Convergence rates of moment-sum-of-squares hierarchies for optimal control problems
Milan Korda, Didier Henrion, and Colin N Jones. Convergence rates of moment-sum-of-squares hierarchies for optimal control problems. Systems & Control Letters , 100:1--5, 2017
2017
-
[16]
Convergence rates for sums-of-squares hierarchies with correlative sparsity
Milan Korda, Victor Magron, and Rodolfo Rios-Zertuche. Convergence rates for sums-of-squares hierarchies with correlative sparsity. Mathematical Programming , 209(1):435--473, 2025
2025
-
[17]
Global optimization with polynomials and the problem of moments
Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on optimization , 11(3):796--817, 2001
2001
-
[18]
A new look at nonnegativity on closed sets and polynomial optimization
Jean B Lasserre. A new look at nonnegativity on closed sets and polynomial optimization. SIAM Journal on Optimization , 21(3):864--885, 2011
2011
-
[19]
A hierarchy of eigencomputations for polynomial optimization on the sphere
Benjamin Lovitz and Nathaniel Johnston. A hierarchy of eigencomputations for polynomial optimization on the sphere. arXiv preprint arXiv:2310.17827 , 2023
2023 arXiv
-
[20]
An effective version of Schm \"u dgen’s Positivstellensatz for the hypercube
Monique Laurent and Lucas Slot. An effective version of Schm \"u dgen’s Positivstellensatz for the hypercube . Optimization Letters , 17(3):515--530, 2023
2023
-
[21]
An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization
Monique Laurent and Lucas Slot. An Overview of Convergence Rates for Sum of Squares Hierarchies in Polynomial Optimization . arXiv preprint arXiv:2408.04417 , 2024
2024 arXiv
-
[22]
On the complexity of Putinar--Vasilescu's Positivstellensatz
Ngoc Hoang Anh Mai and Victor Magron. On the complexity of Putinar--Vasilescu's Positivstellensatz . Journal of Complexity , 72:101663, 2022
2022
-
[23]
Magron and J
V. Magron and J. Wang. Sparse Polynomial Optimization: theory and practice . WORLD SCIENTIFIC (EUROPE), 2023
2023
-
[24]
Michael A. Nielsen. A geometric approach to quantum circuit lower bounds. Quantum Info. Comput. , 6(3):213–262, May 2006
2006
-
[25]
Optimality conditions and finite convergence of lasserre's hierarchy
Jiawang Nie. Optimality conditions and finite convergence of lasserre's hierarchy. Mathematical programming , 146:97--121, 2014
2014
-
[26]
Moment and Polynomial Optimization
Jiawang Nie. Moment and Polynomial Optimization . SIAM, 2023
2023
-
[27]
On the complexity of Putinar's Positivstellensatz
Jiawang Nie and Markus Schweighofer. On the complexity of Putinar's Positivstellensatz . Journal of Complexity , 23(1):135--150, 2007
2007
-
[28]
Positive polynomials on compact semi-algebraic sets
Mihai Putinar. Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal , 42(3):969--984, 1993
1993
-
[29]
Introduction to Radon transforms , volume 160
Boris Rubin. Introduction to Radon transforms , volume 160. Cambridge University Press, 2015
2015
-
[30]
The K -moment problem for compact semi-algebraic sets
Konrad Schm\"udgen. The K -moment problem for compact semi-algebraic sets. Mathematische Annalen , 289:203--206, 1991
1991
-
[31]
On the complexity of S chm \"u dgen's P ositivstellensatz
Markus Schweighofer. On the complexity of S chm \"u dgen's P ositivstellensatz. Journal of Complexity , 20(4):529--543, 2004
2004
-
[32]
Sum-of-squares hierarchies for binary polynomial optimization
Lucas Slot and Monique Laurent. Sum-of-squares hierarchies for binary polynomial optimization. Mathematical Programming , 197(2):621--660, 2023
2023
-
[33]
Sum-of-squares hierarchies for polynomial optimization and the C hristoffel-- D arboux kernel
Lucas Slot. Sum-of-squares hierarchies for polynomial optimization and the C hristoffel-- D arboux kernel. SIAM Journal on Optimization , 32(4):2612--2635, 2022
2022
-
[34]
Specialized effective Positivstellens \"a tze for improved convergence rates of the moment-SOS hierarchy
Corbinian Schlosser and Matteo Tacchi. Specialized effective Positivstellens \"a tze for improved convergence rates of the moment-SOS hierarchy . IEEE Control Systems Letters , 2024
2024
-
[35]
Orthogonal P olynomials
G Szeg \"o . Orthogonal P olynomials. 1975. American Mathematical Society , 1975
1975
-
[36]
Tchakaloff
V. Tchakaloff. Formules de cubatures mécaniques à coefficients non négatifs. Bulletin des Sciences Mathématiques , 81:123--134, 1957
1957
-
[37]
Semidefinite programming
Lieven Vandenberghe and Stephen Boyd. Semidefinite programming. SIAM review , 38(1):49--95, 1996
1996
-
[38]
Summability of Fourier orthogonal series for Jacobi weight functions on the simplex in R ^ d
Yuan Xu. Summability of Fourier orthogonal series for Jacobi weight functions on the simplex in R ^ d . Proceedings of the American Mathematical Society , 126(10):3027--3036, 1998
1998
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.