REVIEW 4 major objections 4 minor 22 references
On Polynomial Stochastic Barrier Functions: Bernstein Versus Sum-of-Squares
T0 review · 4 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper's central claim is that stochastic barrier function synthesis, normally solved as a sum-of-squares semidefinite program, can be cast as a linear program using Bernstein polynomial relaxations, and that this linear program is…
desk verdict A genuinely new LP formulation for stochastic barrier certificates, honestly shown to underperform SoS in practice, but the asymptotic completeness theorem is asserted more than proven. 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 load-bearing object is the Bernstein polynomial relaxation: for a polynomial a(x) on [0,1]^D, the smallest Bernstein coefficient $\beta$ satisfies $\beta$ <= inf a(x), with an error term that converges linearly as the basis degree m+ grows. Around that fact the paper builds affine transformation matrices T that map arbitrary hyperrectangles to [0,1]^D, a dynamics matrix F whose columns hold the coefficients of f_j(x)^{i_j}, and a noise moment matrix E[Gamma] whose entries are products of binomial coefficients and moments of p(v). Together these turn the four SBF constraints—non-negativity, unsafety, initial condition, and the one-step expectation decrease—into the linear inequalities (9a)-(9c) and (12). The named matrices are what carry the argument from the continuous inequalities to a finite LP.
What would settle it
The most direct falsifier is a counterexample to Theorem 8: a polynomial stochastic system with hyperrectangular X, Xs, Xu, and X0 for which the LP's optimal safety bound, computed at increasing m and m+, converges to a value strictly below the true optimal SBF bound from exact polynomial search. A weaker but practical test is a smooth non-rectangular safe set, such as a disk, over-approximated by boxes: if the Bernstein certificate is far looser than an SoS certificate and the gap does not close as the boxes shrink, then the advertised LP advantage is confined to the rectangular cases the paper already restricts itself to.
Extended reading notes
Core claim
The central discovery is that all four stochastic barrier constraints become linear inequalities in the power-basis coefficients of B(x) when the regions X, Xs, Xu, and X0 are unions of hyperrectangles. The mechanism is the Bernstein coefficient bound: after an affine map sends each hyperrectangle to [0,1]^D, the minimum Bernstein coefficient of the transformed polynomial is a lower bound on the polynomial over the box, and the error decays as the Bernstein degree grows. For the expectation constraint, the paper expands E[B(f(x)+v)] into a product of a dynamics matrix F and a noise moment matrix E[Gamma], then applies the same Bernstein bounding. The result, Theorem 8, states that SBF synthesis is a linear program and that as m and m+ go to infinity the LP solution is the optimal SBF, making the Bernstein approach asymptotically complete. The same paper then reports that on its linear contractive test systems the Bernstein LP is not competitive with SoS, often returning a safety bound of zero on the harder environments while SoS returns meaningful bounds.
Load-bearing premise
The Bernstein LP assumes every region of interest—ambient, safe, unsafe, and initial—is a union of hyperrectangles; for curved or slanted semi-algebraic sets, box over-approximation is required and can loosen the certificate so much that the linear program's guarantee loses practical meaning.
Editorial extensions
If this is right
- Safety certificates for polynomial stochastic systems can in principle be synthesized with linear programming, avoiding semidefinite solvers and their numerical fragility.
- The asymptotic completeness result means that, for hyperrectangular regions, higher-degree Bernstein certificates do not lose expressiveness in the limit: the LP's optimum approaches the true optimal barrier.
- The convergence-rate comparison predicts that Bernstein relaxations should need fewer degree increments than SoS to tighten a given bound, but only if the resulting constraint count stays manageable.
- In practice the LP is currently viable mainly for low dimensions and simple environments; the paper's adaptive subdivision algorithm is the proposed mechanism to push it further.
- The paper's negative empirical result transfers to any polynomial relaxation that pays for tightness with an explosion in regional constraints, not just SBF synthesis.
Reading between the lines
- A natural next experiment is to warm-start the Bernstein LP from a low-degree solution and use Algorithm 1's robustness scores to refine only the worst regions; the paper suggests this but does not report how much constraint reduction it achieves.
- For curved safe sets, box over-approximation is the stated fallback; a coordinate transform that straightens the set (as Remark 1 permits) might rescue the LP's tightness, but no evidence is given either way.
- Since the empirical comparison uses linear contractive dynamics with Gaussian noise, the ranking could shift for nonlinear f or heavy-tailed noise, where the noise moment matrix is more expensive to form and SoS may also degrade.
- The theoretical convergence comparison is worst-case; a direct head-to-head of Bernstein subdivision versus SoS multiplier lifting on identical budgets of decision variables could show whether the practical gap is fundamental or a solver artifact.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a Bernstein-polynomial formulation for stochastic barrier function (SBF) synthesis, replacing the sum-of-squares (SoS) semidefinite program with a linear program (LP). It claims that the LP formulation is asymptotically complete as the template degree m and the Bernstein degree m+ grow, compares convergence rates of Bernstein and SoS relaxations, and reports experiments showing that the Bernstein approach underperforms SoS in practice. The manuscript is written for IEEE Control Systems Letters and includes reproducible code.
Significance. If the completeness claim is established, the LP formulation would be an interesting alternative for SBF synthesis in low-dimensional hyperrectangular settings, and the honest empirical negative result is a useful cautionary data point for the control verification community. The paper clearly separates theoretical and practical contributions, provides reproducible code, and gives a fair experimental comparison. However, the central theoretical claim, Theorem 8, is proved only by a one-sentence sketch, and the problem definition leaves the expectation constraint ill-posed when the noise has unbounded support. These issues are load-bearing because they concern the validity of the proposed LP as a certificate and the claimed convergence to the optimal SBF.
major comments (4)
- [Definition 2 and Eq. (2d)] The domain of B is stated as X, but constraint (2d) evaluates B(f(x)+v) at points f(x)+v that can lie outside X. For the Gaussian noise used in Section VII, f(X)+supp(v) is unbounded, so the expression B(f(x)+v) is not defined under the given domain restriction. This affects Lemmas 6 and 7 and Theorem 8, which all rely on (2d). The paper should either define B as a polynomial on all of R^D, or add an explicit assumption that B is extended to a set containing f(X)+supp(v), and the completeness proof must then control the behavior of B outside X.
- [Theorem 8] The proof of asymptotic completeness is a single sentence citing Theorem 4 and the Weierstrass Approximation Theorem. This does not establish convergence of the LP optima. To prove the claim, one must show that any feasible SBF can be approximated by polynomials that satisfy the Bernstein coefficient inequalities (9) and (12) for sufficiently large m and m+, and that the objective value converges. Theorem 4 only bounds the range of a fixed polynomial, while Weierstrass gives uniform approximation on a compact set; neither controls the expectation constraint in (2d) when the noise is unbounded. Additionally, Bernstein lower bounds converge to the infimum from below, so feasibility of β≥0 requires a positive margin on constraints that are tight at the optimum. No Slater-type or strict-positivity condition is stated. Without these steps, the claimed asymptotic completeness is unsubstantiated.
- [Lemma 7 and Eq. (12)] The derivation of E[B(f(x)+v)] = (F E[Γ] b)(x) assumes that the required moments of v exist and that the expectation of the composed polynomial is computed exactly. The assumption in Section II only says 'finite moments,' which is ambiguous: if p(v) has only finitely many finite moments, then E[Γ] may contain infinite or undefined entries for high enough polynomial degrees. The manuscript should state precisely how many moments of v are required as a function of m and the degrees of the f_i, and verify that this condition is satisfied by the noise distributions used in the experiments. Without this, the equality in Lemma 7 is not a well-defined mathematical statement for general p(v).
- [Remark 1 and Theorem 8 scope] Theorem 8 is stated for 'System (1)' and 'the optimal SBF' without qualification, but the Bernstein construction in Section IV applies only when X, X_s, X_u, and X_0 are unions of hyperrectangles, as Remark 1 acknowledges. For general semi-algebraic sets, which Problem 1 allows, the method requires box over-approximations that can destroy tightness of the safety certificate. The theorem should be restricted to the hyperrectangular case, or the completeness claim must be formulated relative to box-approximated regions. As written, the theorem overstates the scope of the method.
minor comments (4)
- [Section III, Proposition 2] The text after Proposition 2 and in Corollary 3 refers to 'Theorem 2' when the statement being used is Proposition 2; the cross-reference should be corrected.
- [Section V.A] The text says the Bernstein bounds converge 'linearly with respect to m+, i.e., δ∝1/m+', but Theorem 4 gives the error bound as δ/(m+)^2. If the δ in Theorem 4 is not constant, the stated rate is ambiguous and should be made precise, since the comparison with the SoS rate depends on this.
- [Algorithm 1] The loop condition in line 2 exits when constraints(n) >= c_max, but the surrounding text says the goal is to keep the number of constraints below c_max. The algorithm then returns best(O), which may have more than c_max constraints. The stopping criterion and the meaning of the returned node should be clarified.
- [Section II, Approach Overview] There is a typo: 'aribitrary' should be 'arbitrary'.
Circularity Check
No circularity: the Bernstein LP derivation depends on external theorems (Garloff range enclosure, Weierstrass approximation) and the empirical results are measurements, not fits.
full rationale
The paper's central claim, Theorem 8, is that Bernstein relaxations turn SBF synthesis into an LP that is asymptotically complete. This claim rests on Theorem 4, Garloff's convergent range-enclosure theorem, and the Weierstrass approximation theorem, both external published results; it is not supported by a parameter fitted to the target output or by the authors' own prior work. Constraints (9) and (12) are constructed algebraically from affine coordinate changes, Bernstein basis conversion, and the expectation of the composed polynomial, with no step that presupposes the safety bound being produced. The paper's self-citations appear only as background and related work and do not carry the load of the main derivation. The negative empirical finding, namely that Bernstein relaxations underperform SoS in practice, is a direct measurement reported in Table I and is therefore not an artifact of circular reasoning. A possible concern is that the proof sketch for asymptotic completeness does not fully justify convergence of LP optima or handle unbounded noise support, but that is a rigor or completeness issue, not a circularity issue, because the cited ingredients are independent of the conclusion being derived.
Assumptions & free parameters
assumptions (5)
- standard math Garloff's theorem (Theorem 4 of [8]): Bernstein coefficients give monotone convergent lower and upper bounds for a polynomial over [0,1]^d.
- standard math Putinar's Positivstellensatz / SoS representation (Proposition 2 and [17]): nonnegativity on a semi-algebraic set can be certified by an SoS decomposition with Lagrange multipliers.
- standard math Weierstrass Approximation Theorem: polynomials are dense in continuous functions on compact intervals.
- domain assumption The SBF certificate theorem from [2] (Theorem 1 in the paper): if B satisfies constraints (2a)-(2d), then the safety probability is at least 1 - (eta + K*gamma).
- domain assumption The system model: f is polynomial and the noise v has finite moments, allowing the expectation in constraint (2d) to be represented as a matrix-vector product.
Cite this review
Pith. "Pith review of On Polynomial Stochastic Barrier Functions: Bernstein Versus Sum-of-Squares." pith.science (2026). https://pith.science/paper/4FSY3DWI
@misc{pith2026250609164,
author = {Pith},
title = {Pith review of: On Polynomial Stochastic Barrier Functions: Bernstein Versus Sum-of-Squares},
year = {2026},
howpublished = {\url{https://pith.science/paper/4FSY3DWI}},
note = {Machine review of arXiv:2506.09164}
}
read the original abstract
Stochastic Barrier Functions (SBFs) certify the safety of stochastic systems by formulating a functional optimization problem, which state-of-the-art methods solve using Sum-of-Squares (SoS) polynomials. This work focuses on polynomial SBFs and introduces a new formulation based on Bernstein polynomials and provides a comparative analysis of its theoretical and empirical performance against SoS methods. We show that the Bernstein formulation leads to a linear program (LP), in contrast to the semi-definite program (SDP) required for SoS, and that its relaxations exhibit favorable theoretical convergence properties. However, our empirical results reveal that the Bernstein approach struggles to match SoS in practical performance, exposing an intriguing gap between theoretical advantages and real-world feasibility.
Reference graph
Works this paper leans on
-
[1]
A framework for worst-case and stochastic safety verification using barrier certificates,
S. Prajna, A. Jadbabaie, and G. J. Pappas, “A framework for worst-case and stochastic safety verification using barrier certificates,”IEEE Trans. on Automatic Control, vol. 52, no. 8, pp. 1415–1428, 2007
work page 2007
-
[2]
A barrier function approach to finite-time stochastic system verification and control,
C. Santoyo, M. Dutreix, and S. Coogan, “A barrier function approach to finite-time stochastic system verification and control,”Automatica, vol. 125, p. 109439, 2021
2021
-
[3]
Safety certification for stochastic systems via neural barrier functions,
F. B. Mathiesen, S. C. Calvert, and L. Laurenti, “Safety certification for stochastic systems via neural barrier functions,”IEEE Control Systems Letters, vol. 7, pp. 973–978, 2022
work page 2022
-
[4]
Piecewise stochastic barrier functions,
R. Mazouz, F. B. Mathiesen, L. Laurenti, and M. Lahijanian, “Piecewise stochastic barrier functions,”arXiv preprint arXiv:2404.16986, 2024
arXiv 2024
-
[5]
Formal synthesis of stochastic systems via control barrier certificates,
P. Jagtap, S. Soudjani, and M. Zamani, “Formal synthesis of stochastic systems via control barrier certificates,”IEEE Transactions on Automatic Control, vol. 66, no. 7, pp. 3097–3110, 2020
work page 2020
-
[6]
Some np-complete problems in quadratic and nonlinear programming,
K. G. Murty and S. N. Kabadi, “Some np-complete problems in quadratic and nonlinear programming,” Tech. Rep., 1985
work page 1985
-
[7]
A nullstellensatz and a positivstellensatz in semialgebraic geometry,
G. Stengle, “A nullstellensatz and a positivstellensatz in semialgebraic geometry,”Mathematische Annalen, vol. 207, pp. 87–97, 1974
work page 1974
-
[8]
Convergent bounds for the range of multivariate polynomials,
J. Garloff, “Convergent bounds for the range of multivariate polynomials,” inInt. Symp. on Interval Mathematics. Springer, 1985, pp. 37–56
work page 1985
Show all 22 references
-
[9]
Linear relaxations of polynomial positivity for polynomial lyapunov function synthesis,
M. A. Ben Sassi, S. Sankaranarayanan, X. Chen, and E. Ábrahám, “Linear relaxations of polynomial positivity for polynomial lyapunov function synthesis,”IMA Journal of Mathematical Control and Information, vol. 33, no. 3, pp. 723–756, 2016
2016
-
[10]
Formal abstraction of general stochastic systems via noise partitioning,
J. Skovbekk, L. Laurenti, E. Frew, and M. Lahijanian, “Formal abstraction of general stochastic systems via noise partitioning,”IEEE Control Systems Letters, vol. 7, pp. 3711–3716, 2023
2023
-
[11]
Abstraction-based synthesis for stochastic systems with omega-regular objectives,
M. Dutreix, J. Huh, and S. Coogan, “Abstraction-based synthesis for stochastic systems with omega-regular objectives,”Nonlinear Analysis: Hybrid Systems, vol. 45, p. 101204, 2022
2022
-
[12]
Efficiency through uncertainty: Scalable formal synthesis for stochastic hybrid systems,
N. Cauchi, L. Laurenti, M. Lahijanian, A. Abate, M. Kwiatkowska, and L. Cardelli, “Efficiency through uncertainty: Scalable formal synthesis for stochastic hybrid systems,” inProceedings of the 22nd ACM int. conf. on hybrid systems: computation and control, 2019, pp. 240–251
2019
-
[13]
A unifying perspective for safety of stochastic systems: From barrier functions to finite abstractions,
L. Laurenti and M. Lahijanian, “A unifying perspective for safety of stochastic systems: From barrier functions to finite abstractions,”arXiv preprint arXiv:2310.01802, 2023
2023 arXiv
-
[14]
Learning control policies for stochastic systems with reach-avoid guarantees,
Ð. Žikeli ´c, M. Lechner, T. A. Henzinger, and K. Chatterjee, “Learning control policies for stochastic systems with reach-avoid guarantees,” in AAAI Conf. on AI, vol. 37, no. 10, 2023, pp. 11 926–11 935
2023
-
[15]
Fast verification of control barrier functions via linear programming,
E. Pond and M. Hale, “Fast verification of control barrier functions via linear programming,”IFAC-PapersOnLine, vol. 56, no. 2, pp. 10 595– 10 600, 2023
2023
-
[16]
Counterexample to global convergence of dsos and sdsos hierarchies,
C. Josz, “Counterexample to global convergence of dsos and sdsos hierarchies,”arXiv preprint arXiv:1707.02964, 2017
2017 arXiv
-
[17]
On the complexity of putinar’s positivstel- lensatz,
J. Nie and M. Schweighofer, “On the complexity of putinar’s positivstel- lensatz,”J. of Complexity, vol. 23, no. 1, pp. 135–150, 2007
2007
-
[18]
Safety guarantees for neural network dynamic systems via stochastic barrier functions,
R. Mazouz, K. Muvvala, A. Ratheesh Babu, L. Laurenti, and M. Lahi- janian, “Safety guarantees for neural network dynamic systems via stochastic barrier functions,”Advances in Neural Information Processing Systems, vol. 35, pp. 9672–9686, 2022
2022
-
[19]
Semidefinite programming,
L. Vandenberghe and S. Boyd, “Semidefinite programming,”SIAM review, vol. 38, no. 1, pp. 49–95, 1996
1996
-
[20]
Über die analytische darstellbarkeit sogenannter willkür- licher functionen einer reellen veränderlichen,
K. Weierstrass, “Über die analytische darstellbarkeit sogenannter willkür- licher functionen einer reellen veränderlichen,”Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften zu Berlin, vol. 2, no. 633-639, p. 364, 1885
-
[21]
S. P. Boyd and L. Vandenberghe,Convex optimization. Cambridge university press, 2004
2004
-
[22]
The bernstein algorithm,
J. Garloff, “The bernstein algorithm,”Interval computations, vol. 2, no. 6, pp. 154–168, 1993
1993
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.