{"id":"e0609f2a-5785-47a7-bc24-43b8f540b155","arxiv_id":"2501.09385","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"Generalized moment problems solved by moment-SOS hierarchies have polynomial convergence rates for both optimal values and feasibility sets under S-fullness, dual attainment, and Archimedean conditions.","lead":"This paper proves that moment-sum-of-squares approximations of generalized moment problems converge at a polynomial rate, with rates adapting to the geometry of the feasible set. It also shows the approximate optimal measures converge to the true optimal measure when the true optimum is unique, and applies the bounds to symmetric tensor decomposition.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2.4's ε-perturbation step fails for objectives with negative maximum: the choice ε ≤ f_i,max/(h_i·w)_max is impossible when f_i,max<0, so the stated κ is not derived for arbitrary continuous f.","rationale":"The reader's verdict is CONDITIONAL, and I agree. The reader's weakest_assumption identifies Assumption 1.9 (dual optimum attainment) as the key applicability condition, which is a genuine concern, but the more immediate correctness risk is the ε-choice gap for negative f_i,max in the proof of Theorem 2.4. The central claim is Theorem A/Corollary 2.5 for arbitrary continuous f, and the proof of the rate constant has a step that is impossible when f_i,max<0. This is not a disagreement with consensus; it is an internal derivation gap in the proof as written. It is repairable and does not affect the tensor applications because their objectives are nonnegative; hence the paper should remain CONDITIONAL rather than be rejected. The proposed one-instance test settles whether Theorem 2.4's constant is merely mis-derived or whether the theorem statement fails for admissible data.","tokens_in":26607,"tokens_out":12958,"duration_ms":134223,"concrete_test":"Take the polynomial optimization instance S=[-1,1], f(x)=x−2, h=1, t=1, K={0}; it satisfies Assumptions 1.3 (w=1), 1.9 (v*=−3), and 2.1. Recompute the proof of Theorem 2.4 and check whether any ε>0 can satisfy the step leading to (2.12). Then either derive the correct constant by choosing ε=(f_i,max+||v*||_1 h*_{i,max}−δ)/(h_i·w)_max and verify the resulting κ, or compute d*−d*_ℓ exactly for this POP and test the claimed bound with κ from (2.9). If the bound holds, the theorem needs a corrected proof and constant; if it fails, Theorem 2.4 as stated is false for admissible data.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Theorem 2.4, the proof constructs v_ε = v* − ε w and needs an upper bound on q_i,max. The displayed chain (2.12) ends with q_i,max ≤ 2 f_i,max + ||v*||_1 h*_{i,max}, justified by 'choosing ε ≤ f_i,max/(h_i·w)_max'. If the continuous objective f_i has negative maximum on S_i, the right-hand side is negative, so no ε>0 satisfies that choice; the inequality is not derived. Assumptions 1.3, 1.9, and 2.1 do not restrict f to nonnegative functions, so the main convergence-rate theorem is not proven for an allowed class of inputs. The source is the attempt to absorb ε(h_i·w)_max into f_i,max. A repairable route is to split α_i = f_i,max + ||v*||_1 h*_{i,max}; dual feasibility gives f_i,max ≥ h_i·v*(x*) ≥ −||v*||_1 h*_{i,max}, hence α_i ≥ 0, but α_i can vanish, so neither the old nor the obvious repaired choice ε ≤ α_i/(h_i·w)_max is always positive. When α_i = 0 the q_i,max and q_i,min are both of order ε, so the ratio is bounded and one can still get a rate, but with different constants. Thus κ in (2.9) is not the constant actually established; Corollary 2.5 and Theorem 2.11 inherit the gap. The tensor applications use nonnegative objectives Ψ, so they are not affected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops convergence-rate theory for Moment-Sum-of-Squares relaxations of countable Generalized Moment Problems with vector measures. Under S-fullness, dual optimum attainment, and Archimedean assumptions, it claims polynomial rates for the convergence of optimal values (Theorem 2.4 / Corollary 2.5), for the Hausdorff distance between truncated feasibility sets (Theorem 2.11), and for the weak-* convergence of canonical optimizers (Theorem 2.13). The framework is then applied to symmetric tensor decomposition, with separate treatments of positive and signed decompositions and explicit O(ell^{-2}) bounds in Theorems 3.2 and 3.7.","tokens_in":26883,"tokens_out":22788,"duration_ms":234580,"significance":"If the main results hold, the paper provides a unified quantitative convergence theory for a broad class of GMPs, with rates adapting to the geometry of the underlying semialgebraic sets through effective Positivstellensatz exponents. The tensor decomposition application is a genuine strength: the authors verify the structural assumptions for both positive and signed decompositions, provide explicit rates, and their numerical examples illustrate finite convergence in practice. The proofs are analytic rather than machine-checked, but the constants are expressed in terms of identifiable objects (the dual optimizer v*, the S-fullness witness w, and imported effective Positivstellensatz bounds) rather than fitted parameters, and the statements are falsifiable through the predicted polynomial rates.","major_comments":[{"comment":"The proof's choice of epsilon is invalid for objectives with f_i,max <= 0. In (2.12), the inequality q_i,max <= 2 f_i,max + ||v*||_1 h*_{i,max} requires choosing epsilon <= f_i,max/(h_i . w)_max, and no positive epsilon exists when f_i,max is zero or negative. Assumptions 1.3, 1.9, and 2.1 do not restrict f to nonnegative functions, so the theorem is not proven for the stated class of objectives. The constant kappa in (2.9) can even be negative, for example with a single constraint h=1, t=1, and f=-10, where the formula gives kappa = -10 gamma^theta. The gap is repairable by replacing f_i,max with max(f_i,max,0) or by balancing epsilon against ell, but the resulting constant differs from (2.9); as written, Theorem A and Corollary 2.5 are not established for arbitrary continuous or polynomial objectives. The tensor applications use nonnegative Psi and are not affected.","section":"Theorem 2.11, proof"},{"comment":"The proof of Theorem 2.11 applies Theorem 2.4 to every f in R_k with ||f||_A = 1 in order to use the forward direction of Lemma 2.10. However, Theorem 2.4 requires Assumption 1.9 for the GMP with that specific objective, and the assumptions of Theorem 2.11 do not imply dual attainment for all such f. S-fullness gives strong duality but not attainment; indeed Assumption 1.9 is introduced precisely because attainment is not automatic. Thus the value-gap bound needed for Lemma 2.10 is not established for all f, and the Hausdorff bound does not follow as written. A repair would be to impose a uniform dual-attainment condition on the unit ball of R_k or to prove the value-gap bound by a direct primal argument.","section":"Lemma 2.10 / Theorem 2.11"},{"comment":"Lemma 2.10 explicitly assumes that p*_ell is attained for every f in R_k, and Theorem 2.11 invokes this lemma without proving attainment. The truncated feasible set is not automatically compact: the restriction of the S-fullness witness w to J_ell need not belong to (K_ell)^*, because an extension of u_ell to K has arbitrary nonnegative components outside J_ell, and elements of L_ell are pseudo-moment functionals that need not be representable by measures. Consequently, the compactness argument for F in Lemma 1.4 does not transfer to the truncated feasible set. The authors should either prove boundedness and attainment for the truncated problems or modify Lemma 2.10 to work with epsilon-optimal points instead of exact optimizers.","section":"Lemma 2.10 / Theorem 2.11"}],"minor_comments":[{"comment":"The unresolved macro '/suppress L' appears in Theorem 2.3 and Theorem 2.11, for instance as 'theta = 1/(2.5n/suppress L)' and 'gamma = gamma'(n,g) deg(p)^{-3.5n/suppress L}'. This should be replaced by the intended Lojasiewicz exponent so that the claimed explicit constants are actually readable.","section":"Throughout"},{"comment":"The constant kappa in Theorem 3.2 appears to omit the factor t . w = F_0 and the power gamma^2 that would follow from Theorem 2.4 when theta = 2; please reconcile the displayed bound with (2.9).","section":"Theorem 3.2"},{"comment":"The narrative says that the relaxation (3.5)_ell is solved, but the displayed optimization problem is the augmented formulation (3.15); the text should identify the actual program being solved.","section":"Example 3.9"},{"comment":"The appeal to [41, Theorem 2.2.11] for generic uniqueness of truncated minimizers is terse; a sentence explaining why the singular normal set has measure zero and how this yields uniqueness of the truncated minimizer would improve readability.","section":"Remark 3.4 and Remark 3.8"},{"comment":"The running title 'THE EFFECTIVE COUNT ABLE GENERALIZED MOMENT PROBLEM' contains a spacing typo; 'countable' should appear as one word.","section":"Abstract and header"}],"recommendation":"major_revision","confidential_remarks":"The main theorems are broader than what the current proofs support, but the gaps appear repairable and the tensor section is more robust because its objectives are nonnegative and the structural assumptions are verified there. I would not reject on this basis; the authors should be asked to repair the epsilon argument in Theorem 2.4 and to clarify or strengthen the assumptions behind Theorem 2.11."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper gives genuinely new convergence rates for Moment-SoS relaxations of countable GMPs on vectors of measures, including Hausdorff convergence of feasibility sets and weak-* convergence of optimizers. That goes beyond prior work like Schlosser–Tacchi–Lazarev, which had rates only for specific applications. The tensor decomposition section is well done: the GMP formulations are sensible, the dual attainment proofs (Propositions 3.1 and 3.6) are careful, and the numerical examples look plausible.\n\nThe soft spot is in the main theorem. In the proof of Theorem 2.4, equation (2.12) bounds q_i,max by absorbing ε(h_i·w)_max into f_i,max, which requires ε ≤ f_i,max/(h_i·w)_max. If f_i has negative maximum on S_i, that inequality is impossible, and the paper never assumes f_i ≥ 0. So Corollary 2.5 as stated overclaims. The tensor applications use nonnegative Ψ, so they are safe, and a repair exists by splitting α_i = f_i,max + ||v*||_1 h*_{i,max} and handling the vanishing case separately. But as written, the constant κ in (2.9) is not derived for negative f_i,max. That is a load-bearing gap, but not a fatal one.\n\nTwo smaller complaints. The constants κ and κ' inherit unknown Lojasiewicz data through the effective Positivstellensatz, so 'effective' is less explicit than the title implies. And the numerical section doesn't ship code or data; it's illustrative, and the examples actually show finite exactness rather than the polynomial rates.\n\nThe citation pattern is fair; the build on [39] is explicit.\n\nVerdict: send it to a serious referee. The core ideas are right, the framework is useful, and the tensor part is solid. The referee should ask for a corrected proof of Theorem 2.4 and an explicit statement about the sign of f. If that gets fixed, I'd be happy to see it in print.","headline":"New general Moment-SoS rates for countable GMPs, with a real proof gap for negative objectives in the main theorem; the tensor application part is solid.","tokens_in":27480,"tokens_out":5907,"would_cite":false,"duration_ms":55857,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["44A60","90C22","15A69","14P10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves explicit polynomial convergence rates for Moment-SoS relaxations of countable generalized moment problems, with rates that adapt to the underlying geometry and apply to optima, feasibility sets, and symmetric tensor…","keywords":["Generalized moment problem","Moment-SoS relaxations","convergence rates","Positivstellensatz","symmetric tensor decomposition","S-fullness","countable moment constraints","Hausdorff distance"],"falsifier":"Take a concrete countable GMP on the unit ball that satisfies S-fullness and the Archimedean condition, write down its dual maximizer $v^*$, and compute the relaxation gap $d^* - d^*_\\ell$ for increasing $\\ell$; the theorem predicts $d^* - d^*_\\ell \\le \\kappa\\ell^{-2}$ with $\\kappa$ given by (2.9), so a single instance whose gap is asymptotically larger than any constant times $\\ell^{-2}$ would refute the main bound.","tokens_in":26341,"feed_emoji":"🧮","tokens_out":13414,"duration_ms":124362,"temperature":0.7,"pith_summary":"This paper establishes explicit polynomial convergence rates for the Moment-Sum-of-Squares (Moment-SoS) hierarchy applied to the Generalized Moment Problem with countably many moment constraints on vectors of measures. Under three structural conditions — S-fullness, attainment of the dual optimum, and an Archimedean quadratic module — the gap between the true optimum and the $\\ell$-th relaxation optimum decays no slower than $\\kappa\\ell^{-\\theta}$, with an exponent $\\theta$ determined by the geometry of the underlying semi-algebraic sets. The same rate bounds the Hausdorff distance between the truncated feasibility sets, and canonical relaxation optimizers converge weak$^*$ to the unique optimal measure when it exists. Applied to symmetric tensor decomposition on the unit ball, the results give explicit $\\ell^{-2}$ error bounds.","feed_headline":"Moment relaxations converge at rate ℓ^{-θ} for countable GMPs","feed_subtitle":"The same rate controls objective values and feasibility sets, and tensor decomposition gains explicit bounds.","key_machinery":"The argument hangs on a perturbed dual feasible point. Starting from a maximizer $v^*$ of the dual GMP, the paper forms $v_\\varepsilon = v^* - \\varepsilon w$ using the strictly positive vector $w$ supplied by S-fullness; then $q = f - h \\cdot v_\\varepsilon$ is a strictly positive polynomial, and an effective Positivstellensatz guarantees membership in the truncated quadratic module once $\\ell \\ge \\max_i \\gamma_i (q_{i,\\max}/q_{i,\\min})^{1/\\theta_i}$. Since $v_\\varepsilon$ is feasible for the $\\ell$-th dual relaxation, weak duality and strong duality sandwich the gap as $d^* - d^*_\\ell \\le \\varepsilon\\, t \\cdot w$; choosing $\\varepsilon$ against the degree bound gives $\\kappa\\ell^{-\\theta}$. For the feasibility-set statement, the machinery is a weighted moment norm embedding measures into a Banach space whose dual is the space of real-analytic functions with norm $\\|f\\|_A = \\sum_\\alpha \\alpha! |f_\\alpha|$, together with a separation argument that converts uniform value bounds into Hausdorff-distance bounds.","core_discovery":"The paper's central claim is that the Moment-SoS relaxation sequence for a countable generalized moment problem and its dual are quantitatively close to the true problem: $0 \\le p^* - p^*_\\ell \\le d^* - d^*_\\ell \\le \\kappa\\ell^{-\\theta}$ for all sufficiently large $\\ell$, and $\\rho_H(F^{(k)}, L^{(k)}_\\ell) \\le \\kappa'\\ell^{-\\theta}$ for fixed $k$. The constants $\\kappa, \\kappa'$ are explicit functions of the data — the strictly positive vector $w$ from S-fullness, the dual maximizer $v^*$, the cost function, and the geometry of the sets — and $\\theta$ is the exponent available from an effective Positivstellensatz for the geometry at hand. A third theorem says that when the true optimum has a unique minimizing measure, every sequence of canonical relaxation optimizers converges to it in the weak$^*$ topology. The authors verify the hypotheses for positive and real symmetric tensor decomposition and derive the concrete bound $\\theta = 2$ on the unit ball.","pith_inferences":["Left implicit is that the same proof template should transfer to optimal control problems once controllability is used to verify Assumption 1.9; the missing piece is a practical way to bound $\\|v^*\\|_1$ and the support of $v^*$ from controllability data.","The Hausdorff-distance result suggests a stopping criterion that value bounds alone cannot provide: monitor the distance from the current pseudo-moment cone to the truncated moment cone to certify how close the relaxation is to true feasibility.","If the generic-uniqueness remarks for tensor decomposition are turned into a theorem, the weak$^*$-convergence result would turn the examples' finite-order exactness into a guarantee that the nuclear-norm heuristic recovers the minimal decomposition.","The paper's examples show the bounds can be pessimistic; an inference is that the true worst-case exponent may be higher for structured data, and identifying the sharp exponent is a natural next problem."],"forward_implications":["For every countable GMP satisfying Assumptions 1.3, 1.9, and 2.1, the objective gap $p^* - p^*_\\ell$ (and $d^* - d^*_\\ell$) is bounded by $\\kappa\\ell^{-\\theta}$, upgrading qualitative convergence to a polynomial worst-case rate.","The same exponent $\\theta$ controls the Hausdorff distance between the true truncated moment cone $F^{(k)}$ and the relaxed pseudo-moment cone $L^{(k)}_\\ell$, so the geometry of feasible moment sequences converges at a polynomial rate, not just the optimal value.","If the GMP has a unique minimizer, every sequence of canonical relaxation optimizers converges weak$^*$ to it, so low-order moments of computed solutions are certified close to those of the true optimizer.","For symmetric tensor decomposition on the unit ball, the verified hypotheses give $\\theta = 2$ with explicit constants, for both positive decompositions (Theorem 3.2) and real decompositions with a total-variation constraint (Theorem 3.7).","The rate is geometry-adaptive: changing the semi-algebraic sets changes $\\theta$, because $\\theta$ is inherited from the effective Positivstellensatz for that particular set."],"supporting_citations":[{"why":"Supplies the strong-duality theorem for linear programs over topological vector spaces used to prove $p^* = d^*$ under S-fullness.","marker":"[2]"},{"why":"Supplies the effective Positivstellensatz with explicit constants and the exponent $\\theta$, the engine that turns strict positivity into membership in the truncated quadratic module.","marker":"[4]"},{"why":"Establishes the Moment-SoS relaxation for GMPs and its qualitative convergence, the framework this paper makes quantitative.","marker":"[25]"},{"why":"Provides the Positivstellensatz that identifies the quadratic-module dual with positive measures under the Archimedean condition.","marker":"[34]"},{"why":"Provides the representation theorem that lets the paper work with linear functionals on polynomials instead of measures.","marker":"[37]"},{"why":"Supplies the effective bound with exponent $\\theta = 2$ for the unit ball, which the tensor-decomposition theorems invoke.","marker":"[43]"}],"fun_headline_variants":["Countable GMP relaxations get explicit ℓ^{-θ} rates","Moment-SoS converges at rate ℓ^{-θ} for countable GMPs","Explicit convergence rates for generalized moment relaxations","Tensor decomposition gets effective Moment-SoS error bounds","Unique minimizer implies weak-* convergence in Moment-SoS"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is Assumption 1.9: the dual problem (1.3) must attain its supremum at some finite vector $v^*$, because the proof constructs the perturbed feasible point $v_\\varepsilon = v^* - \\varepsilon w$ from that maximizer; if no dual optimizer exists, the explicit $\\kappa\\ell^{-\\theta}$ bound cannot even be stated.","fun_headline_variants_meta":{"raw":{"variants":["Countable GMP relaxations get explicit ℓ^{-θ} rates","Moment-SoS converges at rate ℓ^{-θ} for countable GMPs","Explicit convergence rates for generalized moment relaxations","Tensor decomposition gets effective Moment-SoS error bounds","Unique minimizer implies weak-* convergence in Moment-SoS"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000715,"raw_usage":{"total_tokens":3218,"prompt_tokens":954,"completion_tokens":2264,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":570,"completion_tokens_details":{"reasoning_tokens":2177}},"tokens_in":570,"tokens_out":2264,"duration_ms":17032,"temperature":1.0,"reasoning_tokens":2177,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:07:32.473822+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a concrete countable GMP on the unit ball that satisfies S-fullness and the Archimedean condition, write down its dual maximizer $v^*$, and compute the relaxation gap $d^* - d^*_\\ell$ for increasing $\\ell$; the theorem predicts $d^* - d^*_\\ell \\le \\kappa\\ell^{-2}$ with $\\kappa$ given by (2.9), so a single instance whose gap is asymptotically larger than any constant times $\\ell^{-2}$ would refute the main bound.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the strong-duality theorem for linear programs over topological vector spaces used to prove $p^* = d^*$ under S-fullness."},{"cited_title":"Baldi and B","cited_arxiv_id":null,"evidence_quote":"Supplies the effective Positivstellensatz with explicit constants and the exponent $\\theta$, the engine that turns strict positivity into membership in the truncated quadratic module."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the Moment-SoS relaxation for GMPs and its qualitative convergence, the framework this paper makes quantitative."},{"cited_title":"Putinar , Positive polynomials on compact semi-algebraic sets , Indiana University Mathe- matics Journal, 42 (1993), pp","cited_arxiv_id":null,"evidence_quote":"Provides the Positivstellensatz that identifies the quadratic-module dual with positive measures under the Archimedean condition."},{"cited_title":"Rudin , Real and Complex Analysis , Mathematics series, McGraw-Hill, 1987","cited_arxiv_id":null,"evidence_quote":"Provides the representation theorem that lets the paper work with linear functionals on polynomials instead of measures."},{"cited_title":"Slot , Sum-of-squares hierarchies for polynomial optimization a nd the Christoffel–Darboux Kernel, SIAM Journal on Optimization, 32 (2022), p","cited_arxiv_id":null,"evidence_quote":"Supplies the effective bound with exponent $\\theta = 2$ for the unit ball, which the tensor-decomposition theorems invoke."}],"review_version":1}