On the Probabilistic Learnability of Compact Neural Network Preimage Bounds

• URL: http://arxiv.org/abs/2511.11656v1
• Date: Mon, 10 Nov 2025 16:56:51 GMT
• Title: On the Probabilistic Learnability of Compact Neural Network Preimage Bounds
• Authors: Luca Marzari, Manuele Bicego, Ferdinando Cicalese, Alessandro Farinelli,
• Abstract summary: 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
• Score: 71.59148070050212
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Although recent provable methods have been developed to compute preimage bounds for neural networks, their scalability is fundamentally limited by the #P-hardness of the problem. In this work, we adopt a novel probabilistic perspective, aiming to deliver solutions with high-confidence guarantees and bounded error. To this end, we investigate the potential of bootstrap-based and randomized approaches that are capable of capturing complex patterns in high-dimensional spaces, including input regions where a given output property holds. In detail, we introduce $\textbf{R}$andom $\textbf{F}$orest $\textbf{Pro}$perty $\textbf{Ve}$rifier ($\texttt{RF-ProVe}$), a method that exploits an ensemble of randomized decision trees to generate candidate input regions satisfying a desired output property and refines them through active resampling. Our theoretical derivations offer formal statistical guarantees on region purity and global coverage, providing a practical, scalable solution for computing compact preimage approximations in cases where exact solvers fail to scale.

Related papers

• Practical Global and Local Bounds in Gaussian Process Regression via Chaining [4.500208956289746]
  We propose a chaining-based framework for estimating upper and lower bounds on the expected extreme values over unseen data.<n>We also develop a novel method for local uncertainty quantification at specified inputs.
  arXiv  Detail & Related papers  (2025-11-12T09:30:01Z)
• Approximate Algorithms for Verifying Differential Privacy with Gaussian Distributions [2.9748898344267776]
  We introduce a novel approach to approximating probability distributions of loop-free programs that sample from both discrete and continuous distributions.<n>Our verification algorithm is based on computing probabilities to any desired precision by combining integral approximations, and tail probability bounds.
  arXiv  Detail & Related papers  (2025-09-10T17:37:56Z)
• Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification [83.25968588249776]
  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.
  arXiv  Detail & Related papers  (2025-07-07T18:45:53Z)
• Tight Certified Robustness via Min-Max Representations of ReLU Neural Networks [9.771011198361865]
  The reliable deployment of neural networks in control systems requires rigorous robustness guarantees. In this paper, we obtain tight robustness certificates over convex representations of ReLU neural networks.
  arXiv  Detail & Related papers  (2023-10-07T21:07:45Z)
• Provable Preimage Under-Approximation for Neural Networks (Full Version) [27.519993407376862]
  We propose an efficient anytime algorithm for generating symbolic under-approximations of the preimage of any polyhedron output set for neural networks. Empirically, we validate the efficacy of our method across a range of domains, including a high-dimensional MNIST classification task. We present a sound and complete algorithm for the former, which exploits our disjoint union of polytopes representation to provide formal guarantees.
  arXiv  Detail & Related papers  (2023-05-05T16:55:27Z)
• Semantic Strengthening of Neuro-Symbolic Learning [85.6195120593625]
  Neuro-symbolic approaches typically resort to fuzzy approximations of a probabilistic objective. We show how to compute this efficiently for tractable circuits. We test our approach on three tasks: predicting a minimum-cost path in Warcraft, predicting a minimum-cost perfect matching, and solving Sudoku puzzles.
  arXiv  Detail & Related papers  (2023-02-28T00:04:22Z)
• Super-resolution GANs of randomly-seeded fields [68.8204255655161]
  We propose a novel super-resolution generative adversarial network (GAN) framework to estimate field quantities from random sparse sensors. The algorithm exploits random sampling to provide incomplete views of the high-resolution underlying distributions. The proposed technique is tested on synthetic databases of fluid flow simulations, ocean surface temperature distributions measurements, and particle image velocimetry data.
  arXiv  Detail & Related papers  (2022-02-23T18:57:53Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  We study the reward-free RL problem, where an agent aims to thoroughly explore the environment without any pre-specified reward function. We tackle this problem under the context of function approximation, leveraging powerful function approximators. We establish the first provably efficient reward-free RL algorithm with kernel and neural function approximators.
  arXiv  Detail & Related papers  (2021-10-19T07:26:33Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  We propose an efficient method for computing the partition function or MAP estimate in a pairwise MRF. We extend semidefinite relaxations from the typical binary MRF to the full multi-class setting, and develop a compact semidefinite relaxation that can again be solved efficiently using the solver.
  arXiv  Detail & Related papers  (2020-12-04T15:36:29Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)
• On Bayesian Search for the Feasible Space Under Computationally Expensive Constraints [0.0]
  We propose a novel acquisition function that combines the probability that a solution lies at the boundary between feasible and infeasible spaces. Experiments confirmed the efficacy of the proposed function.
  arXiv  Detail & Related papers  (2020-04-23T10:22:32Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  We propose a new distribution alignment method based on a log-likelihood ratio statistic and normalizing flows. We experimentally verify that minimizing the resulting objective results in domain alignment that preserves the local structure of input domains.
  arXiv  Detail & Related papers  (2020-03-26T22:10:04Z)
• Distributionally Robust Chance Constrained Programming with Generative Adversarial Networks (GANs) [0.0]
  A novel generative adversarial network (GAN) based data-driven distributionally robust chance constrained programming framework is proposed. GAN is applied to fully extract distributional information from historical data in a nonparametric and unsupervised way. The proposed framework is then applied to supply chain optimization under demand uncertainty.
  arXiv  Detail & Related papers  (2020-02-28T00:05:22Z)

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.