論文の概要: Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition

• arxiv url: http://arxiv.org/abs/2104.06718v1
• Date: Wed, 14 Apr 2021 09:22:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-15 13:26:10.657862
• Title: Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition
• Title（参考訳）: ラグランジアン分解によるニューラルネットワーク検証のための分岐境界の改良
• Authors: Alessandro De Palma, Rudy Bunel, Alban Desmaison, Krishnamurthy Dvijotham, Pushmeet Kohli, Philip H.S. Torr, M. Pawan Kumar
• Abstract要約: ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
• 参考スコア（独自算出の注目度）: 161.09660864941603
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We improve the scalability of Branch and Bound (BaB) algorithms for formally proving input-output properties of neural networks. First, we propose novel bounding algorithms based on Lagrangian Decomposition. Previous works have used off-the-shelf solvers to solve relaxations at each node of the BaB tree, or constructed weaker relaxations that can be solved efficiently, but lead to unnecessarily weak bounds. Our formulation restricts the optimization to a subspace of the dual domain that is guaranteed to contain the optimum, resulting in accelerated convergence. Furthermore, it allows for a massively parallel implementation, which is amenable to GPU acceleration via modern deep learning frameworks. Second, we present a novel activation-based branching strategy. By coupling an inexpensive heuristic with fast dual bounding, our branching scheme greatly reduces the size of the BaB tree compared to previous heuristic methods. Moreover, it performs competitively with a recent strategy based on learning algorithms, without its large offline training cost. Finally, we design a BaB framework, named Branch and Dual Network Bound (BaDNB), based on our novel bounding and branching algorithms. We show that BaDNB outperforms previous complete verification systems by a large margin, cutting average verification times by factors up to 50 on adversarial robustness properties.
• Abstract（参考訳）: ニューラルネットワークの入力出力特性を正式に証明するために,分岐境界(BaB)アルゴリズムのスケーラビリティを向上する。 まず,ラグランジアン分解に基づく新しい境界アルゴリズムを提案する。 これまでの研究では、BABツリーの各ノードでの緩和を解いたり、より弱い緩和を構築して効率よく解けるようにしてきたが、不必要に弱い境界に繋がった。 我々の定式化は最適化を最適を含むことが保証される双対領域の部分空間に制限し、加速収束をもたらす。 さらに、現代的なディープラーニングフレームワークを通じてGPUアクセラレーションに対応可能な、非常に並列な実装も可能だ。 第2に,新たなアクティベーションベースの分岐戦略を提案する。 安価なヒューリスティックと高速な双対境界を結合することで、この分岐方式は以前のヒューリスティック法に比べてbab木のサイズを大幅に削減する。 さらに、大規模なオフライントレーニングコストを伴わずに、学習アルゴリズムに基づく最近の戦略と競争的に機能する。 最後に,新しいバウンディングと分岐アルゴリズムに基づいて,分岐ネットワーク境界(BaDNB)と呼ばれるBaBフレームワークを設計する。 BaDNBは従来の完全検証システムよりも大きなマージンで優れており, 対向ロバスト性に関する要因によって平均検証時間を最大50に短縮している。

関連論文リスト

• Neural Network Verification with Branch-and-Bound for General Nonlinearities [63.39918329535165]
  ブランチ・アンド・バウンド(BaB)は、ニューラルネットワーク(NN)検証において最も効果的な手法の一つである。 我々は、一般的な非線形性にBaBを実行し、一般的なアーキテクチャでNNを検証する汎用フレームワークGenBaBを開発した。 我々は、Sigmoid、Tanh、Sine、GeLUなどの活性化機能を持つNNを含む幅広いNNの検証におけるGenBaBの有効性を実証する。
  論文  参考訳（メタデータ） (2024-05-31T17:51:07Z)
• FOBNN: Fast Oblivious Binarized Neural Network Inference [12.587981899648419]
  高速な双対型ニューラルネットワーク推論フレームワークであるFOBNNを開発した。 具体的には、二項化畳み込みニューラルネットワークをカスタマイズして、難解な推論を強化し、二項化畳み込みのための2つの高速アルゴリズムを設計し、制約されたコストで実験的にネットワーク構造を最適化する。
  論文  参考訳（メタデータ） (2024-05-06T03:12:36Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。 FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。 我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
  論文  参考訳（メタデータ） (2023-03-17T02:01:11Z)
• On Model Compression for Neural Networks: Framework, Algorithm, and Convergence Guarantee [21.818773423324235]
  本稿では,低ランク近似と重み近似の2つのモデル圧縮手法に焦点を当てた。 本稿では,非最適化の新たな視点から,モデル圧縮のための全体論的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-03-13T02:14:42Z)
• Neural Network Branch-and-Bound for Neural Network Verification [26.609606492971967]
  本稿では,効率的な分岐戦略を設計するための新しい機械学習フレームワークを提案する。 グラフ入力として検証したいネットワークを直接扱う2つのグラフニューラルネットワーク(GNN)を学習する。 我々のGNNモデルは、より大きな未確認ネットワーク上での厳しい特性に対してよく一般化されていることを示す。
  論文  参考訳（メタデータ） (2021-07-27T14:42:57Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Efficient Computation Reduction in Bayesian Neural Networks Through Feature Decomposition and Memorization [10.182119276564643]
  本稿では,計算コストを削減するため,効率的なBNN推論フローを提案する。 計算の約半分は従来の手法と比べて取り除くことができる。 We implement our approach in Verilog and synthesise it with 45 $nm$ FreePDK technology。
  論文  参考訳（メタデータ） (2020-05-08T05:03:04Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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