Pith. sign in

REVIEW 4 minor 39 references

Random Parameter Noise Does Not Make Exact ReLU Verification Easy

T0 review · 0 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Random parameter noise does not make exact ReLU verification computationally easy.

desk verdict A correct, careful conditional lower bound showing fixed small Gaussian coefficient noise does not give a universal smoothed-polynomial exact ReLU verifier; the exact E3SAT embedding holds up. read the letter →

arxiv 2607.14375 v1 pith:4CBNVM57 submitted 2026-07-15 cs.CC cs.LG

Mojtaba Soltanalian This is my paper · ORCID
classification cs.CCcs.LG MSC 68Q1768Q1568T07
keywords ReLUverificationsmoothedanalysisNPversusBPPE3SATembeddinggapreductionsGaussianconcentrationintegralityneuralnetwork
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks whether adding small Gaussian noise to every weight and bias of a ReLU network can guarantee that exact verification becomes easy on average. It answers negatively, conditionally: if NP is not contained in BPP, no sound and complete algorithm can verify every adversarially chosen base network in expected polynomial time, even when the noise level is fixed at 2^-11 and the network is a tiny one-hidden-layer net with fan-in at most three. The proof works by encoding E3SAT so that the maximum network output exactly equals (m-unsat(Φ))/3, giving a verification gap that grows linearly with the number of clauses, and then showing that this gap survives the aggregate perturbation of all coefficients with probability at least 1-e^{-m/8}. The upshot is that generic parameter nondegeneracy is not enough to make exact ReLU verification smoothed-polynomial in the worst case.

What carries the argument

The carrying object is the compact E3SAT embedding: three ReLU literal units per occurrence with weight ±1, bias ∓1/2, and output weight 2/3, plus one overflow unit with bias -1/3 and output weight -1. The exact identity max g_Φ = (m-unsat)/3, together with the threshold-rounding domination property, turns the NP-hard gap of E3SAT into a verification margin Γ = m/60 that is extensive (linear in m). The robustness transfer is a deterministic weighted Lipschitz inequality, sup_x |g_{θ'}(x) - g_θ(x)| ≤ Σ_q c_q|θ'_q - θ_q|, combined with Gaussian concentration for the D-Lipschitz function F(Z) = Σ c_q|Z_q|; at σ⋆ = 2^-11 this yields preservation probability at least 1-e^{-m/8}.

What would settle it

For any E3SAT formula with m clauses, build the four-ReLU-per-clause network and globally maximize it over the unit box using a rigorous MILP or exhaustive arrangement enumeration; if the maximum exceeds (m-unsat(Φ))/3 by any positive amount, Theorem 2 and hence the linear-margin argument fail. Conversely, the complexity theorem itself would be refuted by exhibiting a single sound-and-complete exact verifier whose expected running time is polynomial in s, B, and 1/σ on all instances of the construction at σ = 2^-11.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: if there existed a sound and complete exact algorithm whose expected bit-running time is polynomial in network size, bit complexity, and inverse noise level for every adversarial base instance with 2^{-B} ≤ σ, then NP ⊆ BPP. Equivalently, under NP not in BPP, no such verifier exists. The result already holds for one-hidden-layer ReLU networks on the unit box, hidden fan-in at most three, base coefficients in [-1,1], 4m+1 hidden units, and fixed noise σ⋆ = 2^{-11}. The engine is an exact gap embedding: every E3SAT formula Φ with m clauses maps to a network satisfying max_{x∈[0,1]^n} g_Φ(x) = (m-unsat(Φ))/3, and coordinatewise threshold rounding never decreases

Load-bearing premise

The entire argument rests on the exact identity max_x g_Φ(x) = (m-unsat(Φ))/3 and on the fact that threshold-rounding never decreases the objective: if even a small fractional gap existed, the linear verification margin Γ = m/60 would shrink and the fixed-noise preservation bound e^{-m/8} would no longer follow.

Editorial extensions

If this is right

  • Under NP not in BPP, there is no universal smoothed-polynomial exact verifier for ReLU networks in the stated perturb-and-round model, even at fixed noise 2^-11.
  • The hardness already occurs for one-hidden-layer networks with fan-in at most three and only 4m+1 ReLU units, so the obstruction is not architectural complexity.
  • Exact verification remains hard despite clipping, dyadic rounding, and independent perturbation of every parameter, including output-layer weights and biases.
  • A corollary of the proof is that any sound-and-complete polynomial expected-time verifier would put SAT in BPP, a concrete collapse that most complexity theorists disbelieve.
  • The result refutes the idea that generic parameter noise alone, without data-distribution or architectural assumptions, can guarantee smoothed-polynomial verification.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the transfer theorem is stated generally, similar fixed-noise lower bounds may be derivable from other gap-hard continuous optimization problems, such as MaxCut on unweighted graphs, offering a template for smoothed hardness more broadly.
  • The extensive-margin mechanism suggests that the decisive quantity is the ratio of logical gap to aggregate coefficient sensitivity, so verifier difficulty likely tracks how margins scale with network size rather than the raw noise level.
  • Since the input box and threshold are unperturbed and the noise is absolute and small, the result says little about trained networks with data-dependent margins; a natural empirical test is to measure label-change probabilities on real trained networks at σ≈2^-11 and compare them with the e^{-m/8} bound.
  • The fixed constant 2^-11 is conservative; the rational lower-bound calculations suggest the preservation exponent could be as large as 0.21m, so the qualitative statement is likely robust to significant constant improvements.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies exact ReLU network verification under an adversarial smoothed model in which every network weight and bias is independently perturbed by Gaussian noise, clipped to [-2,2], and rounded to the exact dyadic grid determined by the input bit complexity. The main result (Theorem 1) is a conditional lower bound: if NP is not contained in BPP, then no sound and complete exact verifier can have expected bit-running time polynomial in network size, bit complexity, and inverse noise level for every adversarial base instance. The proof combines an exact E3SAT embedding (four ReLUs per clause, zero integrality gap, extensive margin m/60), a weighted parameter-sensitivity inequality (Lemma 3), Gaussian concentration (Theorem 4), and a BPP conversion that includes polynomial-bit sampling of the rounded Gaussian law. The conclusion already holds at fixed noise level 2^{-11} for one-hidden-layer networks with bounded fan-in and base coefficients in [-1,1].

Significance. If the result holds, it resolves a natural smoothed-complexity question for exact verification: parameter nondegeneracy alone does not guarantee smoothed-polynomial exact verification for every adversarial base network. The paper is unusually quantitative and self-contained: explicit constants are supplied (sigma_star = 2^{-11}, preservation probability at least 1 - e^{-m/8}), and the proof is built from elementary, checkable steps. The reusable weighted-sensitivity transfer theorem (Theorem 4) is a methodological contribution beyond the specific E3SAT construction. The computational audits of the exact identity and the certificate scaling are clearly labeled as diagnostics rather than evidence, and the reproducibility package is a strength. The proof is internally consistent; my remaining concerns are local typographical issues.

minor comments (4)
  1. [Section 4.3 (proof of Theorem 4)] The sentence 'Combining (16) with Theorem 3' should refer to Lemma 3, not Theorem 3. The weighted sensitivity bound used here is Lemma 3; there is no Theorem 3 in the paper.
  2. [Section 3 (proof of Theorem 2)] The displayed inequality '1/3 max{0,1-D_C} >= 1-D_C/3' is false as written (e.g., D_C=0 gives 1/3 >= 1). It should read '1/3 max{0,1-D_C} >= 1/3 - D_C/3', or equivalently, for D_C <= 1, '= (1-D_C)/3'. The subsequent derivation uses the corrected form, so the conclusion is unaffected, but the printed inequality must be fixed.
  3. [Section 7] The phrase 'As noted in Theorem 5' should be 'As noted in Remark 5'; there is no Theorem 5. The reference is to the MAX-CUT remark in Remark 5.
  4. [Section 4.2 / Eq. (8)] The step 'the first two terms in (8) equal -V/3' uses the identity |x_i - 1/2| = 1/2 - delta_i, where delta_i = min{x_i, 1-x_i}. This substitution is not shown and may confuse readers; making it explicit would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified; the derivation is self-contained against external hardness and concentration results.

full rationale

The paper's central conditional hardness result is derived from an external NP-hardness source (Håstad's E3SAT inapproximability), an exact continuous embedding whose proof is fully written out in Section 3, and standard Gaussian concentration and CDF-computability results. Nothing is fitted to data and then renamed as a prediction: the single-parameter choice σ⋆=2^{-11} is derived from explicit rational bounds, not calibrated to outputs. The computational sections are explicitly labeled as diagnostics and play no role in the theorem's proof. There are no self-citations used as load-bearing evidence, and no uniqueness theorem is imported from the author's prior work. The most delicate step, Theorem 2's exact zero-integrality-gap identity, is an internally proven algebraic lemma rather than an assumption; its proof is given in the text and independently audited computationally. The conversion from expected running time to a BPP algorithm via Markov truncation and the total-variation sampling argument is standard and does not presuppose the conclusion. The limitations section discloses the scope of the model and does not conceal any dependence on the theorem's own output. Overall, no step in the derivation chain reduces to its own inputs or to an unverified self-citation.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on standard external theorems (Håstad's E3SAT gap, Gaussian concentration, Ko's polynomial-time computability of the normal CDF) and the stated complexity conjecture; no fitted parameters are used. The constants (σ*=2^-11, ε=1/40, padding 64) are explicit hand-chosen values that are not tuned to data. No invented entities are introduced.

free parameters (3)
  • σ⋆ = 2^{-11}
    Fixed noise level in the theorem statement; hand-chosen small enough to make the explicit inequality Λ≥52m/15 hold. Not fitted to data.
  • Håstad parameter ε = 1/40
    Chosen so the no-case maximum satisfiable fraction is 7/8+1/40=9/10, giving the 1/10 unsat gap. Explicit, not fitted.
  • padding copy factor = 64
    Disjoint copies ensure m≥64, simplifying the C≤23m and D²≤43m bounds. Explicit construction constant, not fitted.
assumptions (5)
  • domain assumption NP ⊄ BPP
    The theorem is conditional on this standard complexity conjecture, stated in the abstract and Section 1.
  • standard math Håstad's optimal E3SAT inapproximability (with ε=1/40 giving 9/10 max-satisfiable fraction in the no case)
    External NP-hard gap source used in Section 3.
  • standard math Gaussian concentration inequality for D-Lipschitz functions
    Used in Theorem 4 proof; cites Boucheron et al. 2013.
  • standard math Polynomial-time computability of the standard normal CDF in the bit model
    Used in Section C to sample the rounded Gaussian law; cites Ko 1991.
  • domain assumption Soundness/completeness and bit-complexity conventions for EXACT-RELU-VERIFY
    Defines the verifier model and polynomial-time charge; Section 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Random Parameter Noise Does Not Make Exact ReLU Verification Easy." pith.science (2026). https://pith.science/paper/4CBNVM57

@misc{pith2026260714375,
  author       = {Pith},
  title        = {Pith review of: Random Parameter Noise Does Not Make Exact ReLU Verification Easy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4CBNVM57}},
  note         = {Machine review of arXiv:2607.14375}
}
abstract

We study exact verification of ReLU networks in an adversarial smoothed model. Every network weight and bias is independently perturbed by Gaussian noise, clipped to $[-2,2]$, and rounded to the exact dyadic grid determined by the input bit complexity. We show that, under the standard assumption $\mathrm{NP}\not\subseteq\mathrm{BPP}$, there is no sound and complete verifier whose expected running time is polynomial in network size, bit complexity, and inverse noise level for every base instance. The conclusion already holds at the fixed noise level $\sigma_\star=2^{-11}$ for one-hidden-layer networks over a unit box, with hidden fan-in at most three and base coefficients in $[-1,1]$. The proof combines an exact gap embedding with a quantitative robustness argument. For every E3SAT formula $\Phi$ with $m$ clauses, a four-ReLU-per-clause construction satisfies $\max_{x\in[0,1]^n} g_\Phi(x)=(m-\operatorname{unsat}(\Phi))/3$, and coordinatewise threshold rounding never decreases the objective. A weighted parameter-sensitivity inequality and Gaussian concentration then show that a verification gap linear in $m$ survives the aggregate perturbation of all coefficients with probability at least $1-e^{-m/8}$. The proof includes clipping, exact dyadic rounding, output-layer perturbations, polynomial-bit sampling of the rounded Gaussian law, and the conversion from expected smoothed running time to a BPP algorithm. Computational checks test the exact identity and illustrate the different scaling of extensive and constant gaps; they are diagnostics rather than evidence for the complexity theorem. The result concerns worst-case base networks in the stated absolute-noise model, but it shows that parameter nondegeneracy alone does not yield a universal smoothed-polynomial guarantee for exact verification.

Figures

Figures reproduced from arXiv: 2607.14375 by the authors.

Figure 1
Figure 1. Exact algebra and exhaustive low-dimensional perturbation study. (a) The closed-form optimum in Theorem 2 versus independent global MILP solves. (b) Balanced preservation of satisfiable and extensively unsatisfiable labels for products of globally optimized three-input blocks. At σ = 0.042, preservation rises from 0.695 for one block to 0.991 for 128 blocks. At σ = 0.063, systematic side bias prevents convergence to… view at source ↗
Figure 2
Figure 2. The extensive verification gap is the fixed-noise mechanism. (a) With gap Γ = q/6, the weighted-certificate transition is essentially independent of the number of perturbed blocks. (b) With fixed gap Γ = 1/6, admissible noise shrinks as the network grows. (c) Empirical 50% transition scales: slope −0.00 for the extensive gap and −1.01 for the one-defect ablation, compared with q 0 and q −1 references. 8 Limitations … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references

  1. [1]

    Strong mixed-integer programming formulations for trained neural networks

    Ross Anderson, Joey Huchette, Will Ma, Christian Tjandraatmadja, and Juan Pablo Vielma. Strong mixed-integer programming formulations for trained neural networks. Mathematical Programming, 183:3--39, 2020

    2020

  2. [2]

    Concentration Inequalities: A Nonasymptotic Theory of Independence

    St\'ephane Boucheron, G\'abor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013

    2013

  3. [3]

    Rudy Bunel, Jingyue Lu, Ilker Turkaslan, Philip H. S. Torr, Pushmeet Kohli, and M. Pawan Kumar. Branch and bound for piecewise linear neural network verification. Journal of Machine Learning Research, 21(42):1--39, 2020

    2020

  4. [4]

    Computational complexity of learning neural networks: Smoothness and degeneracy

    Amit Daniely, Nathan Srebro, and Gal Vardi. Computational complexity of learning neural networks: Smoothness and degeneracy. In Advances in Neural Information Processing Systems, volume 36, 2023

    2023

  5. [5]

    Formal verification of piece-wise linear feed-forward neural networks

    R \"u diger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In Automated Technology for Verification and Analysis, pages 269--286, 2017

    2017

  6. [6]

    Complexity of injectivity and verification of ReLU neural networks (extended abstract)

    Vincent Froese, Moritz Grillo, and Martin Skutella. Complexity of injectivity and verification of ReLU neural networks (extended abstract). In Proceedings of the 38th Conference on Learning Theory, volume 291 of Proceedings of Machine Learning Research, pages 2188--2189, 2025

    2025

  7. [7]

    Parameterized hardness of zonotope containment and neural network verification

    Vincent Froese, Moritz Leo Grillo, Christoph Hertrich, and Moritz Stargalla. Parameterized hardness of zonotope containment and neural network verification. In International Conference on Learning Representations, 2026

    2026

  8. [8]

    Some optimal inapproximability results

    Johan H stad. Some optimal inapproximability results. Journal of the ACM, 48(4):798--859, 2001

    2001

Show all 39 references
  1. [9]

    Qi Huangfu and J. A. Julian Hall. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 10(1):119--142, 2018

    2018

  2. [10]

    Dill, Kyle Julian, and Mykel J

    Guy Katz, Clark Barrett, David L. Dill, Kyle Julian, and Mykel J. Kochenderfer. Reluplex: An efficient SMT solver for verifying deep neural networks. In Computer Aided Verification, pages 97--117, 2017

    2017

  3. [11]

    Johnson, Lukas Koller, Edoardo Manino, ThanhVu H

    Konstantin Kaulen, Tobias Ladner, Stanley Bak, Christopher Brix, Hai Duong, Thomas Flinkow, Taylor T. Johnson, Lukas Koller, Edoardo Manino, ThanhVu H. Nguyen, and Haoze Wu. The 6th international verification of neural networks competition ( VNN-COMP 2025): Summary and results...

    2025

  4. [12]

    Complexity Theory of Real Functions

    Ker-I Ko. Complexity Theory of Real Functions. Birkh \"a user Boston, 1991

    1991

  5. [13]

    o glin and Berthold V \

    Heiko R \"o glin and Berthold V \"o cking. Smoothed analysis of integer programming. Mathematical Programming, 110(1):21--56, 2007

    2007

  6. [14]

    A convex relaxation barrier to tight robustness verification of neural networks

    Hadi Salman, Greg Yang, Huan Zhang, Cho-Jui Hsieh, and Pengchuan Zhang. A convex relaxation barrier to tight robustness verification of neural networks. In Advances in Neural Information Processing Systems, volume 32, 2019

    2019

  7. [15]

    Reachability is NP -complete even for the simplest neural networks

    Marco S \"a lzer and Martin Lange. Reachability is NP -complete even for the simplest neural networks. In Reachability Problems, pages 149--164, 2021

    2021

  8. [16]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385--463, 2004

    2004

  9. [17]

    Xiao, and Russ Tedrake

    Vincent Tjeng, Kai Y. Xiao, and Russ Tedrake. Evaluating robustness of neural networks with mixed integer programming. In International Conference on Learning Representations, 2019

    2019

  10. [18]

    Oliphant, et al

    Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, et al. SciPy 1.0: Fundamental algorithms for scientific computing in Python. Nature Methods, 17:261--272, 2020

    2020

  11. [19]

    Zico Kolter

    Shiqi Wang, Huan Zhang, Kaidi Xu, Xue Lin, Suman Jana, Cho-Jui Hsieh, and J. Zico Kolter. -CROWN : Efficient bound propagation with per-neuron split constraints for neural network robustness verification. In Advances in Neural Information Processing Systems, volume 34, 2021

    2021

  12. [20]

    Spielman and Shang-Hua Teng , title =

    Daniel A. Spielman and Shang-Hua Teng , title =. Journal of the ACM , volume =. 2004 , doi =

    2004

  13. [21]

    Smoothed Analysis of Integer Programming , journal =

    Heiko R. Smoothed Analysis of Integer Programming , journal =. 2007 , doi =

    2007

  14. [22]

    Some Optimal Inapproximability Results , journal =

    Johan H. Some Optimal Inapproximability Results , journal =. 2001 , doi =

    2001

  15. [23]

    Dill and Kyle Julian and Mykel J

    Guy Katz and Clark Barrett and David L. Dill and Kyle Julian and Mykel J. Kochenderfer , title =. Computer Aided Verification , series =. 2017 , doi =

    2017

  16. [24]

    Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks , booktitle =

    R. Formal Verification of Piece-Wise Linear Feed-Forward Neural Networks , booktitle =. 2017 , doi =

    2017

  17. [25]

    Xiao and Russ Tedrake , title =

    Vincent Tjeng and Kai Y. Xiao and Russ Tedrake , title =. International Conference on Learning Representations , year =

  18. [26]

    Rudy Bunel and Jingyue Lu and Ilker Turkaslan and Philip H. S. Torr and Pushmeet Kohli and M. Pawan Kumar , title =. Journal of Machine Learning Research , volume =. 2020 , url =

    2020

  19. [27]

    Zico Kolter , title =

    Shiqi Wang and Huan Zhang and Kaidi Xu and Xue Lin and Suman Jana and Cho-Jui Hsieh and J. Zico Kolter , title =. Advances in Neural Information Processing Systems , volume =. 2021 , url =

    2021

  20. [28]

    Mathematical Programming , volume =

    Ross Anderson and Joey Huchette and Will Ma and Christian Tjandraatmadja and Juan Pablo Vielma , title =. Mathematical Programming , volume =. 2020 , doi =

    2020

  21. [29]

    Advances in Neural Information Processing Systems , volume =

    Hadi Salman and Greg Yang and Huan Zhang and Cho-Jui Hsieh and Pengchuan Zhang , title =. Advances in Neural Information Processing Systems , volume =. 2019 , url =

    2019

  22. [30]

    Reachability Is

    Marco S. Reachability Is. Reachability Problems , series =. 2021 , doi =

    2021

  23. [31]

    Proceedings of the 38th Conference on Learning Theory , series =

    Vincent Froese and Moritz Grillo and Martin Skutella , title =. Proceedings of the 38th Conference on Learning Theory , series =. 2025 , url =

    2025

  24. [32]

    Advances in Neural Information Processing Systems , volume =

    Amit Daniely and Nathan Srebro and Gal Vardi , title =. Advances in Neural Information Processing Systems , volume =. 2023 , url =

    2023

  25. [33]

    Johnson and Lukas Koller and Edoardo Manino and ThanhVu H

    Konstantin Kaulen and Tobias Ladner and Stanley Bak and Christopher Brix and Hai Duong and Thomas Flinkow and Taylor T. Johnson and Lukas Koller and Edoardo Manino and ThanhVu H. Nguyen and Haoze Wu , title =. arXiv preprint arXiv:2512.19007 , year =. doi:10.48550/arXiv.2512.1...

    doi

  26. [34]

    Concentration Inequalities: A Nonasymptotic Theory of Independence , publisher =

    St. Concentration Inequalities: A Nonasymptotic Theory of Independence , publisher =. 2013 , url =

    2013

  27. [35]

    1991 , doi =

    Ker-I Ko , title =. 1991 , doi =

    1991

  28. [36]

    Oliphant and others , title =

    Pauli Virtanen and Ralf Gommers and Travis E. Oliphant and others , title =. Nature Methods , volume =. 2020 , doi =

    2020

  29. [37]

    Qi Huangfu and J. A. Julian Hall , title =. Mathematical Programming Computation , volume =. 2018 , doi =

    2018

  30. [38]

    International Conference on Learning Representations , year =

    Vincent Froese and Moritz Leo Grillo and Christoph Hertrich and Moritz Stargalla , title =. International Conference on Learning Representations , year =

  31. [39]

    Huangfu and I

    Q. Huangfu and I. Galabova and M. Feldmeier and J. A. J. Hall , title =. 2026 , url =

    2026

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.