arXiv cs.AI· Brian Yarbrough, Jesse Wayment, Jingbo Wang, Philip E. Par\'{e}, Shreyas Sundaram·· 3 小时前AI 评分41
Fit-LRP：拟合线性松弛到多面体，用于非凸区域的神经网络验证
Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions
AI 导读
Fit-LRP 框架通过求解一系列小型低维线性规划，在由多面体并集表示的非凸域上精确优化仿射边界，可无缝增强 LiRPA 与 α,β-CROWN 分支定界算法的最终优化步骤。在 ARCH-COMP 与神经 Lyapunov 基准上，Fit-LRP 将最难区域的分支减少 47 倍，最坏情况验证时间缩短 15 倍；配合区域划分，单 CPU 验证速度比 GPU 上的 α,β-CROWN 快 6.1 倍。
正文 · 原文
Abstract:State-of-the-art neural network verifiers evaluate linear relaxations over axis-aligned bounding boxes. However, verification domains in cyber-physical systems are rarely boxes. Reachability specifications, obstacle-avoidance constraints, and neural Lyapunov certificates typically yield oblique or non-convex polyhedral regions, over which box-based bounds become extremely loose. This paper proposes Fit-LRP (Fitting Linear Relaxations to Polytopes), a framework the implements exact optimization of affine bounds over non-convex domains (represented by unions of polytopes) by solving a sequence of small, low-dimensional linear programs. Our approach seamlessly enhances the final optimization step of LiRPA and $\alpha,\! \beta$-CROWN branch-and-bound (BaB) algorithms. In BaB verification, approximating oblique constraints with axis-aligned splits causes severe combinatorial blowup and risks non-termination. By optimizing the final affine bound of a nonlinear function over the exact polyhedral state-space constraints our method eliminates box-induced over-approximations, enabling earlier search-tree pruning. On ARCH-COMP and neural Lyapunov benchmarks, Fit-LRP reduces branching on the hardest region by $47\times$, cuts worst-case verification time by $15\times$, and with region-wise partitioning, verifies on a single CPU $6.1\times$ faster than $\alpha,\! \beta$-CROWN on a GPU.
| Subjects: | Machine Learning (cs.LG); Artificial Intelligence (cs.AI); Systems and Control (eess.SY); Optimization and Control (math.OC) |
| ACM classes: | I.2; F.3.1; G.1.6 |
| Cite as: | arXiv:2611.16003 [cs.LG] |
| (or arXiv:2611.16003v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2611.16003 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Brian Yarbrough [view email]
[v1]
Wed, 11 Nov 2026 21:05:13 UTC (170 KB)
来源：arXiv cs.AI · arxiv.org