{"id":"285efe2b-8c7f-48df-9060-c36bd09aac95","arxiv_id":"1908.05689","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"This paper proposes a perturbed sample average approximation for stochastic polynomial optimization, solved via Lasserre Moment-SOS relaxations, and proves the relaxation is tight exactly when the moment matrix is rank one.","lead":"Polynomial optimization problems with randomness are usually solved by averaging samples, but the averaged problem can become unbounded. This paper adds a small norm penalty to the sample average and solves it with Moment-SOS semidefinite relaxations, reporting better optimizers in several examples.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2 is sound, but the paper never bridges the perturbed SAA (3.2) to the true problem (1.3): the choice of epsilon is unprincipled and the numerical examples hand-pick it.","rationale":"I read the paper in good faith. The main theorem, Theorem 3.2, is a clean and correct statement about the relationship between tightness of the moment relaxation and the rank-one property of its minimizer; I do not see a flaw in its proof. The more serious issue is whether the proposed algorithm actually solves the original stochastic polynomial optimization problem (1.3). The reader's weakest assumption identifies exactly this: the paper assumes, without proof or quantification, that a suitable small epsilon exists such that the perturbed sample average problem (3.2) approximates the true problem (1.3). My stress-test confirms this concern and sharpens it. The numerical tables show that the minimal feasible epsilon* from (3.5) is often too small to induce a rank-one tight relaxation, and the epsilons that work are chosen ad hoc, sometimes much larger than epsilon*. No theoretical bound links epsilon to the bias in the returned minimizer, and no practical rule is given for choosing epsilon without knowing the true solution. This does not refute the theorem, nor does it show the method never works; it means the paper's central practical claim is not established. The reader's verdict of CONDITIONAL is therefore appropriate, and my read does not change it.","tokens_in":17340,"tokens_out":8944,"duration_ms":90496,"concrete_test":"Run a controlled experiment on Example 4.5 (or a randomized ensemble with known v*): fix N, draw i.i.d. samples, and scan epsilon over a log grid from 1e-12 to 1. For each epsilon, solve (3.3), record the rank-one gap |<f_N,y*> - f_N(u)|, the error ||u - v*||, and the objective gap f(u) - fmin. Then determine the set of epsilon values for which (i) (3.3) is solvable, (ii) the rank-one gap is below 1e-6, and (iii) ||u - v*|| is below a tolerance such as 0.05. If this set is empty for some sample sizes, or if its location shifts wildly with the sample realization and cannot be predicted from f_N alone, the practical claim fails; if the set is nonempty and stable, the pragmatic use of PSAA is supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.2 is internally correct: for a fixed epsilon, the moment relaxation (3.3) is tight iff its minimizer has rank-one moment matrix, and then u=pi(y*) solves the perturbed problem (3.2). The load-bearing gap is the step from this theorem to the paper's practical claim that Algorithm 3.1 gives reliable minimizers of the original stochastic problem (1.3). Nothing in the paper controls, for any chosen epsilon, the distance between the solution set of (3.2) and that of (1.3); the uniform-convergence argument cited in Section 1 applies to f_N -> f, not to f_N + epsilon||[x]|| -> f. The numerical evidence does not close this gap. In Examples 4.5-4.6, the 'minimal feasible' epsilon* computed from (3.5) yields relaxations with rank-one gaps |<f_N,y*> - f_N(u)| of order 1e+2 and objective gaps |<f_N,y*> - fmin| of order 1e+2 (Tables 6 and 8), whereas the reported good results use ad hoc larger epsilons such as 0.1 or 0.05. Algorithm 3.1 gives no rule for selecting this larger epsilon, and the tables choose epsilon case-by-case, typically after knowing the true minimizer v*. Thus the claimed practical advantage rests on an unstated assumption that a 'usable' epsilon interval exists and can be located without prior knowledge of the true solution.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a perturbed sample average approximation (PSAA) model for stochastic polynomial optimization, in which the sampled objective f_N(x) is replaced by f_N(x) + ε‖[x]_{2d}‖ over a semialgebraic feasible set K. The authors study properties of this perturbed problem and of its Lasserre-type moment relaxation: Theorem 3.2 characterizes tightness of the relaxation by the rank-one condition on the moment matrix of its minimizer, and Theorem 3.3 asserts solvability for large ε. They present Algorithm 3.1, which chooses a small ε, solves the moment relaxation (3.3), and outputs the projection u of the minimizer. The numerical section compares PSAA with the classical SAA (ε=0) on seven examples with various distributions, reporting that PSAA often returns minimizers close to the true optimizer while the plain SAA may be unsolvable or return poor solutions.","tokens_in":17661,"tokens_out":7372,"duration_ms":66270,"significance":"If the proposed method delivered guaranteed or even well-controlled approximations to the original stochastic problem (1.3), it would be a valuable addition to the toolbox for nonconvex stochastic polynomial optimization. The central theoretical observation, Theorem 3.2, is correct and is proved by a clean argument: for fixed ε, tightness of the moment relaxation is equivalent to rank(M_d[y*]) = 1, in which case the projection is a global minimizer of (3.2). This is a useful structural result. However, the practical significance of the paper hangs on an unsupported bridge between the perturbed sample problem (3.2) and the true problem (1.3), and the paper states no error bound, no convergence rate, and no principled rule for selecting ε. The numerical experiments, though suggestive, use hand-picked values of ε and deterministic or single-path sample constructions. The contribution is therefore best viewed as a heuristic proposal with one clean correctness statement, while the claimed practical advantage over classical SAA is not yet established.","major_comments":[{"comment":"The paper never provides a quantitative relationship between the solution set of the perturbed sample problem (3.2) and that of the original stochastic problem (1.3). The uniform-convergence argument quoted in Section 1 applies to the plain sample average f_N converging to f, not to f_N + ε‖[x]_{2d}‖ converging to f. For any fixed ε > 0, the objective in (3.2) approximates f + ε‖[x]_{2d}‖, whose minimizer can differ from the minimizer of f; conversely, too small an ε may leave (3.3) unbounded below. Algorithm 3.1 offers no rule for balancing these two effects. This is a load-bearing gap, because the paper's conclusion that Algorithm 3.1 gives reliable minimizers of (1.3) rests entirely on the unstated assumption that a usable ε interval exists and can be found without prior knowledge of the true solution.","section":"Section 3, Eq. (3.2)"},{"comment":"The proof of Theorem 3.3 asserts that Q(g)_{2d} is a closed cone whenever K has nonempty interior, citing [23, Theorem 3.49]. Nonempty interior of K is by itself not sufficient for closedness of the truncated quadratic module; known closedness results require additional conditions, typically archimedeanity of the full quadratic module. Since this theorem is used to guarantee that (3.3) and (3.4) have optimizers for large ε, the statement needs either a corrected proof under explicit sufficient assumptions or a revised argument that does not depend on this closedness claim.","section":"Theorem 3.3"},{"comment":"The numerical results do not support the implicit message that the value ε* defined in (3.5) is a useful 'minimal feasible' perturbation. In Table 6, case III, the relaxation at ε* has |⟨f_N, y*⟩ − f_N(u)| = 5.30e+01, and in Table 8, case II, the corresponding gap is 1.13e+02, showing that the moment relaxation is far from tight at ε*. The successful entries in these tables use larger values (0.1 and 0.05) that are chosen on an ad hoc, case-by-case basis and are not derived from (3.5) or any other stated rule. Thus the experiments demonstrate only that the method can work when ε is tuned after the fact, not that Algorithm 3.1 as written provides a reliable way to select ε.","section":"Section 4, Examples 4.5-4.6 (Tables 6 and 8)"},{"comment":"The experimental design does not substantiate the claimed practical advantage in a statistical sense. In Examples 4.1 and 4.2, sample averages are constructed deterministically to have a prescribed deviation from the expectation, rather than being drawn randomly; in Examples 4.5-4.7, the tables report a single sample path per case. No repeated trials, confidence intervals, or sensitivity analysis over ε are presented. Consequently, the tables establish that the method succeeds on a few hand-picked instances and parameter choices, but they do not constitute evidence that the algorithm reliably outperforms the classical SAA for typical or worst-case sample realizations.","section":"Section 4, Examples 4.1-4.7"}],"minor_comments":[{"comment":"The word 'semidefintie' appears to be a typo for 'semidefinite'.","section":"Section 2, paragraph before Eq. (2.4)"},{"comment":"The text says 'The set of all y satisfying linear matrix inequalities in (3.3) is just the cone S(g)_{2d}', but the constraint y0 = 1 is also present, so the relevant set is S(g)_{2d} ∩ {y0 = 1}.","section":"Section 3, after Eq. (3.3)"},{"comment":"The expression 'for the choice ǫ > ‖f_N − [x]_d^T [x]_d‖' is ambiguous: the left norm is a scalar assigned to ε, while the right-hand side must be the norm of a coefficient vector (or a polynomial norm), not the Euclidean norm of a monomial vector. Please clarify the norm being used.","section":"Theorem 3.3, proof"},{"comment":"The instruction 'If (3.3) is infeasible' is imprecise, since (3.3) is feasible whenever K is nonempty. The intended condition is likely that (3.3) is unbounded below or does not have a minimizer.","section":"Algorithm 3.1, Step 2"}],"recommendation":"major_revision","confidential_remarks":"The paper is clearly written and Theorem 3.2 is a correct, clean characterization. The main weakness is the missing error analysis connecting (3.2) to (1.3), together with numerical evidence that is tuned rather than systematic. I see no sign of misrepresentation, but the claimed practical advantage is not supported as it stands. A revision that supplies a theoretical guarantee (e.g., a bound in terms of ε and N, or a sharp selection rule for ε) and a more systematic empirical study would be needed to make the paper acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's the short version: this paper has one genuinely correct and useful theorem, but it overclaims what that theorem buys them. Theorem 3.2 says the moment relaxation (3.3) of the perturbed SAA (3.2) is tight iff its minimizer has rank-one moment matrix, and in that case the projection solves (3.2). I checked the proof; it's sound and the strict convexity for epsilon > 0 is the key.\n\nWhat's new: the PSAA model (adding epsilon times the norm of the monomial vector to the sample average) and its dual. That's a natural regularization but I don't recall it in the SAA literature, and the paper shows it can fix the unbounded-below problem that plain SAA hits in polynomial examples. That's a real, though narrow, contribution.\n\nThe soft spot is the gap between (3.2) and the true problem (1.3). The theorem is conditional on a fixed epsilon and says nothing about whether the perturbed solution tracks the true minimizer as N grows. Uniform convergence of f_N to f doesn't survive adding a fixed epsilon norm term—you're solving a different problem. The paper never quantifies the bias or gives a principled rule for choosing epsilon. The epsilon* in (3.5) is only the smallest value that makes the dual feasible; in Tables 6 and 8 it produces gaps of order 1e+2, while the good columns use hand-picked larger values like 0.1 or 0.05. That makes the numerical evidence look selected after knowing the answer. I also note Theorem 3.3 relies on closedness of the truncated quadratic module, which may need an archimedean assumption; that's a side issue but worth a look.\n\nThe numerics are proof-of-concept at best: they choose sample averages by hand rather than running random trials. That's acceptable for a short paper, but it doesn't support robust claims of practical advantage.\n\nBottom line: I'd send this to peer review. The main theorem is correct and the regularization idea is worth publishing, but the paper needs a revision that either proves a bound on the perturbation bias or explicitly limits its claims to the regularized problem. If a referee asks for an error analysis, that's the right call.","headline":"A correct tightness theorem for a regularized SAA scheme, but the paper never shows the perturbation tracks the true stochastic optimum, and the numerics hand-pick epsilon.","tokens_in":18153,"tokens_out":4317,"would_cite":false,"duration_ms":40398,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C22","90C31","65K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A norm perturbation makes sample-average polynomial optimization reliably solvable.","keywords":["stochastic polynomial optimization","sample average approximation","moment relaxations","sum-of-squares relaxations","semidefinite programming","nonconvex stochastic optimization","perturbation regularization"],"falsifier":"Take a stochastic polynomial optimization with known expectation $f$, generate many independent sample sets, and for each set choose $\\epsilon$ by solving (3.5); if the returned points $u$ stay bounded away from the true minimizer $v^*$ as the sample size grows, the practical claim that PSAA recovers reliable minimizers would fail.","tokens_in":17132,"feed_emoji":"🎲","tokens_out":7270,"duration_ms":66315,"temperature":0.7,"pith_summary":"This paper proposes a perturbation sample average approximation (PSAA) model: instead of minimizing the sample average $f_N(x)$ directly, minimize $f_N(x) + \\epsilon\\|[x]_{2d}\\|$ over the same feasible set, with a small $\\epsilon > 0$, and solve it with Moment-SOS relaxations. The paper's central claim is that this perturbation cures a known failure mode of sample average approximation—the sampled problem can be unbounded below even when the true expectation problem is well posed—and that the moment relaxation is tight exactly when the moment matrix of its minimizer has rank one. In that case, the projection of the relaxed minimizer is a global minimizer of the perturbed problem. Numerical experiments on polynomial objectives with uniform, normal, Poisson, Bernoulli, and geometric noise show the perturbed model returning reliable minimizers where the unperturbed sample average model fails. A sympathetic reader would care because this gives nonconvex stochastic polynomial optimization a route through semidefinite programming without assuming convexity or gradient information.","feed_headline":"Small perturbation rescues sample-average polynomial optimization","feed_subtitle":"A rank-one moment matrix certifies a global minimizer, rescuing cases where unperturbed sampling breaks down.","key_machinery":"The central object is the perturbed sample average approximation (PSAA): minimize $f_N(x) + \\epsilon\\|[x]_{2d}\\|$ subject to $g_i(x) \\ge 0$, where $[x]_{2d}$ is the vector of all monomials up to degree $2d$ and $\\epsilon > 0$ is chosen small. The workhorse is the moment relaxation (3.3), a semidefinite program over truncated moment sequences $y$ with $y_0 = 1$, moment matrix $M_d[y] \\succeq 0$, and localizing matrices $L_{g_i}^{(d)}[y] \\succeq 0$. The norm term $\\epsilon\\|y\\|$ makes the relaxed objective strictly convex, which forces uniqueness of the minimizer and enables the rank-one characterization. Its dual (3.4) has a clear reading: it finds the largest $\\gamma$ such that $f_N - \\gamma$ lies in the truncated quadratic module $Q(g)_{2d}$ up to a small polynomial perturbation $p$ with $\\|\\operatorname{vec}(p)\\| \\le \\epsilon$.","core_discovery":"The paper establishes Theorem 3.2: for $\\epsilon > 0$, the moment relaxation (3.3) of the perturbed sample average problem (3.2) is tight if and only if the moment matrix $M_d[y^*]$ of its minimizer has rank one; when this rank-one condition holds, $u = \\pi(y^*)$ is a minimizer of (3.2). The proof runs through strict convexity: for $\\epsilon > 0$ the objective of (3.3) is strictly convex, so the minimizer is unique, and if the point returned by the relaxation is genuinely a feasible point of (3.2), its moment matrix factors as $[u]_d [u]_d^T$, giving rank one. Conversely, tightness forces the relaxed minimizer to coincide with the lifted point generated by a minimizer of (3.2), whose moment matrix is rank one. The paper also shows (Theorem 3.3) that when the feasible set has nonempty interior, a sufficiently large $\\epsilon$ makes both the primal relaxation and its dual feasible with equal optimal values, and it defines the minimal such $\\epsilon$ as the solution of an auxiliary semidefinite program (3.5).","pith_inferences":["A testable extension is to treat $\\epsilon$ as a tuning parameter and measure the bias-variance trade-off across many independent sample realizations; the paper demonstrates individual cases but does not quantify the distribution of the distance $\\|u - v^*\\|$.","The $\\epsilon\\|y\\|$ term acts like a Tikhonov regularizer in moment space, not in decision space; this suggests the method will be most valuable exactly when the unperturbed sample average is ill-posed, and less so when the sample average is already well behaved.","One could ask whether the rank-one condition holds asymptotically as $N \\to \\infty$ and $\\epsilon \\to 0$ at an appropriate joint rate; the paper does not address this limit, and a positive answer would sharpen the practical promise of the method."],"forward_implications":["For any instance where the relaxed minimizer has rank-one moment matrix, the method certifies a global minimizer of the perturbed problem (3.2) and extracts it from the first moments.","The perturbation regularizes sample-average problems that are unbounded from below: for large enough $\\epsilon$, the relaxation always has a minimizer, so degenerate samples no longer make the model unsolvable.","The minimal useful $\\epsilon$ can be chosen by solving the auxiliary problem (3.5), which gives the smallest norm perturbation making the dual feasible.","Because the pipeline is polynomial arithmetic plus semidefinite programming, it applies to nonconvex objectives and to discrete sample distributions without gradient evaluations."],"supporting_citations":[{"why":"Introduces the Moment-SOS hierarchy for polynomial optimization that the paper uses to solve the sample-average problem.","marker":"[18]"},{"why":"Supplies the sample-average approximation convergence properties that motivate solving the sampled problem and justify the perturbation model.","marker":"[39]"},{"why":"Provides the detection result used to conclude that a rank-one moment matrix means the relaxed solution is the lifted point $[u]_{2d}$.","marker":"[13]"},{"why":"Provides flat truncation certification used in the same rank-one argument.","marker":"[26]"},{"why":"Establishes the duality between the moment cone and the truncated quadratic module, used in Theorem 3.3.","marker":"[23]"},{"why":"Gives the Positivstellensatz for compact semialgebraic sets, which underpins the representation of positive polynomials in the quadratic module.","marker":"[34]"}],"fun_headline_variants":["Tiny perturbation makes polynomial optimization tight","Rank-one moment matrix certifies global minimizer","Perturbation rescues sample-average optimization","Strict convexity yields tight moment relaxations"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a small parameter $\\epsilon$ exists for which the perturbed sample-average problem is a faithful stand-in for the original expectation problem; the paper assumes this closeness without proving it, and the bias introduced by $\\epsilon\\|[x]_{2d}\\|$ is not quantified.","fun_headline_variants_meta":{"raw":{"variants":["Tiny perturbation makes polynomial optimization tight","Rank-one moment matrix certifies global minimizer","Perturbation rescues sample-average optimization","Strict convexity yields tight moment relaxations"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000403,"raw_usage":{"total_tokens":2031,"prompt_tokens":810,"completion_tokens":1221,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":426,"completion_tokens_details":{"reasoning_tokens":1176}},"tokens_in":426,"tokens_out":1221,"duration_ms":8058,"temperature":1.0,"reasoning_tokens":1176,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:07:20.430249+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a stochastic polynomial optimization with known expectation $f$, generate many independent sample sets, and for each set choose $\\epsilon$ by solving (3.5); if the returned points $u$ stay bounded away from the true minimizer $v^*$ as the sample size grows, the practical claim that PSAA recovers reliable minimizers would fail.","supporting_citations":[{"cited_title":"Lasserre, Global optimization with polynomials and the problem of moments, SIAM J","cited_arxiv_id":null,"evidence_quote":"Introduces the Moment-SOS hierarchy for polynomial optimization that the paper uses to solve the sample-average problem."},{"cited_title":"Shapiro, D","cited_arxiv_id":null,"evidence_quote":"Supplies the sample-average approximation convergence properties that motivate solving the sampled problem and justify the perturbation model."},{"cited_title":"Henrion and J","cited_arxiv_id":null,"evidence_quote":"Provides the detection result used to conclude that a rank-one moment matrix means the relaxed solution is the lifted point $[u]_{2d}$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides flat truncation certification used in the same rank-one argument."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the duality between the moment cone and the truncated quadratic module, used in Theorem 3.3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Positivstellensatz for compact semialgebraic sets, which underpins the representation of positive polynomials in the quadratic module."}],"review_version":1}