{"ID":2844081,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.11656","arxiv_id":"2511.11656","title":"On the Probabilistic Learnability of Compact Neural Network Preimage Bounds","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.","short_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 t...","url_abs":"https://arxiv.org/abs/2511.11656","url_pdf":"https://arxiv.org/pdf/2511.11656v1","authors":"[\"Luca Marzari\",\"Manuele Bicego\",\"Ferdinando Cicalese\",\"Alessandro Farinelli\"]","published":"2025-11-10T16:56:51Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.AI\"]","methods":"[]","has_code":false}