論文の概要: Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions
- arxiv url: http://arxiv.org/abs/2611.16003v1
- Date: Wed, 11 Nov 2026 21:05:13 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.272726
- Title: Fit-LRP: Fitting Linear Relaxations to Polytopes for Neural Network Verification over Non-Convex Regions
- Title(参考訳): Fit-LRP:非凸領域におけるニューラルネットワーク検証のためのポリトープへの線形緩和
- Abstract要約: 最先端のニューラルネットワーク検証器は、軸方向のバウンディングボックス上での緩和を評価する。
サイバー物理システムにおける検証ドメインは、まれにリーチリーチ斜めの制約である。
- 参考スコア(独自算出の注目度): 5.771703811611272
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 $α,\! β$-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 $α,\! β$-CROWN on a GPU.
- Abstract(参考訳): 最先端のニューラルネットワーク検証器は、軸方向のバウンディングボックス上での線形緩和を評価する。
しかし、サイバー物理システムにおける検証ドメインは滅多にボックスではない。
到達可能性仕様、障害物回避制約、神経リプノフ証明は一般に斜めまたは非凸多面体領域を生成し、ボックスベースの境界は極端に緩くなっている。
本稿では,低次元線形プログラムの列を解くことで,非凸領域上のアフィン境界の正確な最適化を実現するフレームワークであるFit-LRPを提案する。
我々のアプローチは、LiRPAと$α,\!の最終最適化ステップをシームレスに強化します。
β$-CROWNブランチ・アンド・バウンド(BaB)アルゴリズム。
BaB検証では、斜めの制約を軸方向の分割で近似すると、重度の組合せが爆発し、非終了のリスクが生じる。
厳密な多面体状態空間制約に対する非線形関数の最終アフィン境界を最適化することにより、ボックスによるオーバー近似を排除し、早期の探索木刈り込みを可能にする。
ARCH-COMPとニューラルなLyapunovベンチマークでは、Fit-LRPは最も難しいリージョンのブランチを47\times$に削減し、最悪のケースの検証時間を15\times$に削減し、リージョン単位でのパーティショニングにより、1つのCPUで6.1\times$が$α,\!
GPU上のβ$-CROWN。
関連論文リスト
- Convex-Concave Reinforcement Learning [12.326242110978853]
政策学習は、今日の政策学習の最も簡潔で高密度な応用の多くを推進している。
しかし、それが抱える中核的な問題は、直接的なポリシーパラメータ化の下でもリターンを最大化することです。
この一見非構造的な構造は実際には問題ではないことを示す。
論文 参考訳(メタデータ) (2026-10-06T20:59:21Z) - CLAD: Constrained Abstract Domain for Neural Network Verification [7.480478840881969]
制約付きラグランジアン抽象ドメイン(CLAD)を紹介する。
凸制約の組み合わせによって定義された入力領域上のニューラルネットワークの音響過度近似を計算する。
我々は,4つの畳み込みネットワーク上の1,944インスタンスにおけるCLADの評価を行った。
論文 参考訳(メタデータ) (2026-09-28T08:48:41Z) - Boundary-Adapted PINNs for Elliptic Dirichlet Problems: $H^2(Ω)$ A Priori Error Bounds with Application to Mean Escape Time Computation [14.109379170744546]
境界強化物理情報ニューラルネットワーク(PINN)を用いた楕円ディリクレ境界値問題(BVP)について検討する。
プリミティブエラーバウンダリを導出し、$$への依存を明確にします。
我々の証明はまた、ReQU および tanh ネットワークの高階微分の仮説空間に対して、新しい VC-次元境界を与える。
論文 参考訳(メタデータ) (2026-07-21T15:03:42Z) - Lower Bounds and Proximally Anchored SGD for Non-Convex Minimization Under Unbounded Variance [7.788141970705731]
勾配解析とその変種におけるBlum-Glady Oracle (Amax-0) 条件の弱さに対処する。
これらの下界に合わせるために、スムーズな勾配に対する統一的なアルゴリズムフレームワークであるProllyxima Anchor (ASTA) を考える。
論文 参考訳(メタデータ) (2026-04-17T18:15:51Z) - Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
本稿では,2層ReLULUネットワーク間における重み減衰と凸緩和の最適性ギャップについて検討する。
私たちの研究は、なぜローカルメソッドがうまく機能するのかを理解することに新たな光を当てています。
論文 参考訳(メタデータ) (2024-02-06T01:29:35Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳(メタデータ) (2021-04-14T09:22:42Z) - Fast and Complete: Enabling Complete Neural Network Verification with
Rapid and Massively Parallel Incomplete Verifiers [112.23981192818721]
BaB プロセス中に線形計画法 (LP) を置き換えるために, 逆モード線形緩和に基づく解析法 (LiRPA) を提案する。
LPとは異なり、LiRPAを適用すると、より弱い境界が得られ、分割時にサブドメインのコンフリクトをチェックすることもできない。
既存のLPベースのアプローチと比較して、桁違いのスピードアップを示す。
論文 参考訳(メタデータ) (2020-11-27T16:42:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。