Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification

• URL: http://arxiv.org/abs/2507.05405v1
• Date: Mon, 07 Jul 2025 18:45:53 GMT
• Title: Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification
• Abstract summary: We present a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets.<n>With negligible computational overhead, $textttPT-LiRPA$ exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output.
• Score: 83.25968588249776
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present $\textbf{P}$robabilistically $\textbf{T}$ightened $\textbf{Li}$near $\textbf{R}$elaxation-based $\textbf{P}$erturbation $\textbf{A}$nalysis ($\texttt{PT-LiRPA}$), a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets. In detail, we show that with negligible computational overhead, $\texttt{PT-LiRPA}$ exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output, reducing the computational cost of formal verification tools while providing probabilistic guarantees on verification soundness. Extensive experiments on standard formal verification benchmarks, including the International Verification of Neural Networks Competition, show that our $\texttt{PT-LiRPA}$-based verifier improves robustness certificates by up to 3.31X and 2.26X compared to related work. Importantly, our probabilistic approach results in a valuable solution for challenging competition entries where state-of-the-art formal verification methods fail, allowing us to provide answers with high confidence (i.e., at least 99%).

Related papers

• Probabilistic Verification of Recurrent Neural Networks for Single and Multi-Agent Reinforcement Learning [7.340828059560292]
  Existing verification tools rely on restrictive modeling assumptions or coarse over-approximations of hidden state space.<n>We propose $textbfRNN$ $textbfPro$babilistic $textbfVe$rification ($texttRNN-ProVe$), a probabilistic framework that $textitestimates the likelihood$ of undesired behaviors in RNN-based policies.<n>Experiments on partially observable single-agent and cooperative multi-agent tasks show that $texttRNN-ProVe$ yields more quantitative,
  arXiv  Detail & Related papers  (2026-05-14T12:22:54Z)
• Hierarchical End-to-End Taylor Bounds for Complete Neural Network Verification [10.685380941330687]
  Reachability analysis of neural networks seeks to compute or bound the set of outputs attainable over a given input domain.<n>Existing approaches exploit at most second-order information and do not systematically leverage higher-order information.<n>We introduce textscHiTaB, a novel verification framework that exploits second-order smoothness through both the Hessian, $nabla2 f$, and its Lipschitz constant, $L_nabla2 f$.
  arXiv  Detail & Related papers  (2026-05-11T14:16:13Z)
• Federated Language Models Under Bandwidth Budgets: Distillation Rates and Conformal Coverage [12.805268849262243]
  Training a language model on data scattered across bandwidth-limited nodes that cannot be centralized is a setting that arises in clinical networks, enterprise knowledge bases, and scientific consortia.<n>We study the regime in which data must remain distributed across nodes, and ask what statistical guarantees are in principle achievable under explicit bandwidth budgets.
  arXiv  Detail & Related papers  (2026-05-11T05:01:43Z)
• $V_1$: Unifying Generation and Self-Verification for Parallel Reasoners [69.66089681814013]
  $V_$ is a framework that unifies generation and verification through efficient pairwise ranking.<n>$V_$-Infer improves Pass@1 by up to $10%$ over pointwise verification.<n>$V_$-PairRL achieves $7$--$9%$ test-time scaling gains over standard RL and pointwise joint training.
  arXiv  Detail & Related papers  (2026-03-04T17:22:16Z)
• Scalable and Reliable State-Aware Inference of High-Impact N-k Contingencies [4.588028371034407]
  Exhaustive evaluation of all outage combinations using AC power-flow or ACOPF is infeasible in routine operation.<n>This paper proposes a scalable, state-aware contingency inference framework designed to directly generate high-impact $N!-!k$ outage scenarios.
  arXiv  Detail & Related papers  (2026-02-10T06:55:59Z)
• On the Probabilistic Learnability of Compact Neural Network Preimage Bounds [71.59148070050212]
  In this work, we adopt a novel probabilistic perspective, aiming to deliver solutions with high-confidence guarantees and bounded error.<n>We introduce $textbfR$andom $textbfF$orest $textbfPro$perty $textbfVe$rifier ($texttRF-ProVe$), a method that exploits an ensemble of randomized decision trees to generate candidate input regions satisfying a desired output property.<n>Our theoretical derivations offer formal statistical guarantees on region purity and global coverage, providing a practical, scalable solution for computing
  arXiv  Detail & Related papers  (2025-11-10T16:56:51Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Optimal and Feasible Contextuality-based Randomness Generation [4.2126604059714685]
  Semi-measurement-independent randomness generation protocols based on Kochen-Specker contextuality offer attractive features.<n>We show that a single qubit is non-contextual, i.e., the qubit correlations can be explained by a non-contextual hidden variable (NCHV) model.<n>We point out possible attacks by quantum and general consistent (non-signalling) adversaries for certain classes of contextuality tests.
  arXiv  Detail & Related papers  (2024-12-28T12:11:07Z)
• SPLITZ: Certifiable Robustness via Split Lipschitz Randomized Smoothing [8.471466670802817]
  SPLITZ is a practical and novel approach to provide certifiable robustness to adversarial examples.<n> Motivation for SPLITZ comes from the observation that many standard deep networks exhibit heterogeneity in Lipschitz constants.<n>We show that SPLITZ consistently improves on existing state-of-the-art approaches in the MNIST, CIFAR-10 and ImageNet datasets.
  arXiv  Detail & Related papers  (2024-07-03T05:13:28Z)
• A Specialized Semismooth Newton Method for Kernel-Based Optimal Transport [92.96250725599958]
  Kernel-based optimal transport (OT) estimators offer an alternative, functional estimation procedure to address OT problems from samples. We show that our SSN method achieves a global convergence rate of $O (1/sqrtk)$, and a local quadratic convergence rate under standard regularity conditions.
  arXiv  Detail & Related papers  (2023-10-21T18:48:45Z)
• On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks [13.2844023993979]
  Federated learning (FL) is a widely employed distributed paradigm for collaboratively machine learning models from multiple clients without sharing local data. In this paper, we show that FedAvg converges to a global minimum at a global rate at a global focus.
  arXiv  Detail & Related papers  (2023-10-09T07:56:56Z)
• Expressive Losses for Verified Robustness via Convex Combinations [67.54357965665676]
  We study the relationship between the over-approximation coefficient and performance profiles across different expressive losses. We show that, while expressivity is essential, better approximations of the worst-case loss are not necessarily linked to superior robustness-accuracy trade-offs.
  arXiv  Detail & Related papers  (2023-05-23T12:20:29Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  This paper proposes a theoretical and computational framework for training and robustness verification of implicit neural networks. We introduce a related embedded network and show that the embedded network can be used to provide an $ell_infty$-norm box over-approximation of the reachable sets of the original network. We apply our algorithms to train implicit neural networks on the MNIST dataset and compare the robustness of our models with the models trained via existing approaches in the literature.
  arXiv  Detail & Related papers  (2022-08-08T03:13:24Z)
• The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning [34.630300910399036]
  We characterize the fundamental communication cost required to obtain the best accuracy under $varepsilon$ central DP. Our results show that $tildeOleft( min(n2varepsilon2, d) right)$ bits per client are both sufficient and necessary. This provides a significant improvement relative to state-of-the-art SecAgg distributed DP schemes.
  arXiv  Detail & Related papers  (2022-03-07T22:56:09Z)
• Distributed Sparse Feature Selection in Communication-Restricted Networks [6.9257380648471765]
  We propose and theoretically analyze a new distributed scheme for sparse linear regression and feature selection. In order to infer the causal dimensions from the whole dataset, we propose a simple, yet effective method for information sharing in the network.
  arXiv  Detail & Related papers  (2021-11-02T05:02:24Z)
• Scalable Lipschitz Residual Networks with Convex Potential Flows [120.27516256281359]
  We show that using convex potentials in a residual network gradient flow provides a built-in $1$-Lipschitz transformation. A comprehensive set of experiments on CIFAR-10 demonstrates the scalability of our architecture and the benefit of our approach for $ell$ provable defenses.
  arXiv  Detail & Related papers  (2021-10-25T07:12:53Z)
• Certifiably Robust Interpretation via Renyi Differential Privacy [77.04377192920741]
  We study the problem of interpretation robustness from a new perspective of Renyi differential privacy (RDP) First, it can offer provable and certifiable top-$k$ robustness. Second, our proposed method offers $sim10%$ better experimental robustness than existing approaches. Third, our method can provide a smooth tradeoff between robustness and computational efficiency.
  arXiv  Detail & Related papers  (2021-07-04T06:58:01Z)
• Beta-CROWN: Efficient Bound Propagation with Per-neuron Split Constraints for Complete and Incomplete Neural Network Verification [151.62491805851107]
  We develop $beta$-CROWN, a bound propagation based verifier that can fully encode per-neuron splits. $beta$-CROWN is close to three orders of magnitude faster than LP-based BaB methods for robustness verification. By terminating BaB early, our method can also be used for incomplete verification.
  arXiv  Detail & Related papers  (2021-03-11T11:56:54Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  adversary-resilient distributed optimization, in which. machines can independently compute gradients, and cooperate. Our algorithm is based on a new concentration technique, and its sample complexity. It is very practical: it improves upon the performance of all prior methods when no. setting machines are present.
  arXiv  Detail & Related papers  (2020-12-28T17:19:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.