論文の概要: Solution-aware vs global ReLU selection: partial MILP strikes back for DNN verification

• arxiv url: http://arxiv.org/abs/2507.23197v1
• Date: Thu, 31 Jul 2025 02:43:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-01 17:19:09.00928
• Title: Solution-aware vs global ReLU selection: partial MILP strikes back for DNN verification
• Title（参考訳）: 解認識対グローバルReLU選択:部分MILP攻撃をDNN検証に戻す
• Authors: Yuke Liao, Blaise Genest, Kuldeep Meel, Shaan Aryaman,
• Abstract要約: em (countable かつ uncountable, 複数形 ems) Em Global ReLU score (sf GS) 短いタイムアウトで$alpha,beta$-CROWNを呼び出し、簡単にインスタンスを解決し、部分MILPは、非常に正確で効率的な検証を生成する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: To handle complex instances, we revisit a divide-and-conquer approach to break down the complexity: instead of few complex BaB calls, we rely on many small {\em partial} MILP calls. The crucial step is to select very few but very important ReLUs to treat using (costly) binary variables. The previous attempts were suboptimal in that respect. To select these important ReLU variables, we propose a novel {\em solution-aware} ReLU scoring ({\sf SAS}), as well as adapt the BaB-SR and BaB-FSB branching functions as {\em global} ReLU scoring ({\sf GS}) functions. We compare them theoretically as well as experimentally, and {\sf SAS} is more efficient at selecting a set of variables to open using binary variables. Compared with previous attempts, SAS reduces the number of binary variables by around 6 times, while maintaining the same level of accuracy. Implemented in {\em Hybrid MILP}, calling first $\alpha,\beta$-CROWN with a short time-out to solve easier instances, and then partial MILP, produces a very accurate yet efficient verifier, reducing by up to $40\%$ the number of undecided instances to low levels ($8-15\%$), while keeping a reasonable runtime ($46s-417s$ on average per instance), even for fairly large CNNs with 2 million parameters.
• Abstract（参考訳）: 複雑なインスタンスを扱うために、複雑なBaB呼び出しを少なくする代わりに、多くの小さなMILP呼び出しに依存します。 重要なステップは、(コストがかかる)バイナリ変数を使用するために、非常に少ないが非常に重要なReLUを選択することです。 以前の試みは、その点において最適以下であった。 これらの重要なReLU変数を選択するために、新しいReLUスコアリング({\sf SAS})を提案するとともに、BaB-SRおよびBaB-FSB分岐関数を {\em Global} ReLUスコアリング({\sf GS})関数として適用する。 理論的にも実験的にも比較し、より効率的にバイナリ変数の集合を選択することができる。 以前の試行と比較すると、SASは同じレベルの精度を維持しながら、バイナリ変数の数を約6倍削減する。 最初に$\alpha,\beta$-CROWNを呼び出し、簡単にインスタンスを解決し、そして部分MILPは、非常に正確で効率的な検証器を生成します。

関連論文リスト

• From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
  以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。 実現可能な最小二乗の設定において、新しい最上界を創出する。 我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
  論文  参考訳（メタデータ） (2025-04-06T18:39:45Z)
• LDC-MTL: Balancing Multi-Task Learning through Scalable Loss Discrepancy Control [30.689399230097667]
  マルチタスク学習(MTL)は、複数のタスクを同時に学習する能力に広く採用されている。 両レベル最適化の観点から定式化されたMDLの簡易かつスケーラブルな損失分散制御手法であるLCC-MTLを提案する。 i)粗損失前正規化,(ii)細粒度損失分散制御のための二値式,(iii)$mathcalO(1)$時間とメモリのみを必要とするスケーラブルな一階二値アルゴリズムである。
  論文  参考訳（メタデータ） (2025-02-12T17:18:14Z)
• Bayes beats Cross Validation: Efficient and Accurate Ridge Regression via Expectation Maximization [3.061662434597098]
  本稿では,正規化ハイパーパラメータである$lambda$について,LOOCV(Left-out-out Cross-validation)よりも高速に計算できる手法を提案する。 提案手法は,比較的穏やかな条件下で,十分大きな$n$に対して,一意の最適解を求めることが保証されている。
  論文  参考訳（メタデータ） (2023-10-29T01:13:55Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。 注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。 本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
  論文  参考訳（メタデータ） (2023-06-30T08:34:29Z)
• Near-Optimal Non-Convex Stochastic Optimization under Generalized Smoothness [21.865728815935665]
  2つの最近の研究は、$O(epsilon-3)$サンプル複雑性を確立し、$O(epsilon)$-定常点を得る。 しかし、どちらも$mathrmploy(epsilon-1)$という大きなバッチサイズを必要とする。 本研究では,STORMアルゴリズムの単純な変種を再検討することにより,従来の2つの問題を同時に解決する。
  論文  参考訳（メタデータ） (2023-02-13T00:22:28Z)
• On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure [77.60508571062958]
  マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。 アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。 サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
  論文  参考訳（メタデータ） (2022-11-28T08:40:12Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。 また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
  論文  参考訳（メタデータ） (2020-07-15T03:25:24Z)
• Fractional ridge regression: a fast, interpretable reparameterization of ridge regression [0.0]
  リッジ回帰(RR)は、線形回帰における係数のL2-ノルムをペナライズする正規化手法である。 我々は、FRRを解くアルゴリズムと、Pythonのオープンソースソフトウェア実装を提供する。
  論文  参考訳（メタデータ） (2020-05-07T03:12:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。