論文の概要: Scaling the Convex Barrier with Sparse Dual Algorithms

• arxiv url: http://arxiv.org/abs/2101.05844v2
• Date: Tue, 26 Jan 2021 14:36:42 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-29 00:48:40.846318
• Title: Scaling the Convex Barrier with Sparse Dual Algorithms
• Title（参考訳）: スパース双対アルゴリズムによる凸障壁のスケーリング
• Authors: Alessandro De Palma, Harkirat Singh Behl, Rudy Bunel, Philip H.S. Torr, M. Pawan Kumar
• Abstract要約: 本稿では,ニューラルネットワークバウンダリングのための2つの新しい2重アルゴリズムを提案する。 どちらの方法も新しい緩和の強さを回復する: 厳密さと線形分離オラクル。 実行時間のほんの一部で、既製のソルバよりも優れた境界を得ることができます。
• 参考スコア（独自算出の注目度）: 141.4085318878354
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tight and efficient neural network bounding is crucial to the scaling of neural network verification systems. Many efficient bounding algorithms have been presented recently, but they are often too loose to verify more challenging properties. This is due to the weakness of the employed relaxation, which is usually a linear program of size linear in the number of neurons. While a tighter linear relaxation for piecewise-linear activations exists, it comes at the cost of exponentially many constraints and currently lacks an efficient customized solver. We alleviate this deficiency by presenting two novel dual algorithms: one operates a subgradient method on a small active set of dual variables, the other exploits the sparsity of Frank-Wolfe type optimizers to incur only a linear memory cost. Both methods recover the strengths of the new relaxation: tightness and a linear separation oracle. At the same time, they share the benefits of previous dual approaches for weaker relaxations: massive parallelism, GPU implementation, low cost per iteration and valid bounds at any time. As a consequence, we can obtain better bounds than off-the-shelf solvers in only a fraction of their running time, attaining significant formal verification speed-ups.
• Abstract（参考訳）: 厳密で効率的なニューラルネットワークバウンディングは、ニューラルネットワーク検証システムのスケーリングに不可欠である。 近年、多くの効率的な境界アルゴリズムが提示されているが、より難しい特性を検証するにはゆるすぎることが多い。 これは、通常ニューロン数に線形な大きさの線形プログラムである、使用済みの緩和の弱さによるものである。 分割線形活性化に対するより厳密な線形緩和が存在するが、指数関数的に多くの制約を伴い、現在効率的なカスタマイズされた解法が欠けている。 2つの新しい双対アルゴリズムを提案することにより、この欠陥を緩和する: 1つは、小さなアクティブな双対変数のセットで、もう1つは、Frank-Wolfe型オプティマイザの間隔を利用して、線形メモリコストのみを発生させる。 どちらの方法も新しい緩和の強さを回復する: 厳密さと線形分離オラクル。 同時に、大規模な並列処理、GPU実装、イテレーション当たりの低コスト、常に有効なバウンダリといった、緩和の弱さに対する、以前の2つのアプローチのメリットを共有している。 その結果,実行時間のほんの一部で,既定のソルバよりも優れた境界が得られるようになり,形式的な検証速度が向上した。

関連論文リスト

• A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints [1.5498250598583487]
  伝統的な数学的プログラミングの解法は制約付き最小化問題を解くのに長い計算時間を必要とする。 ペナルティに基づくガードレールアルゴリズム(PGA)を提案する。
  論文  参考訳（メタデータ） (2024-05-03T10:37:34Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Zonotope Domains for Lagrangian Neural Network Verification [102.13346781220383]
  我々は、ディープニューラルネットワークを多くの2層ニューラルネットワークの検証に分解する。 我々の手法は線形プログラミングとラグランジアンに基づく検証技術の両方により改善された境界を与える。
  論文  参考訳（メタデータ） (2022-10-14T19:31:39Z)
• LinSyn: Synthesizing Tight Linear Bounds for Arbitrary Neural Network Activation Functions [4.03308187036005]
  LinSyn は任意の任意の活性化関数に対して厳密な境界を達成する最初のアプローチである。 提案手法は,2～5倍の出力バウンダリと4倍以上の信頼性を達成できることを示す。
  論文  参考訳（メタデータ） (2022-01-31T17:00:50Z)
• DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splitting [70.62923754433461]
  入力摂動に対するディープニューラルネットワークの最悪の性能を分析することは、大規模な非最適化問題の解決につながる。 解析解を持つ小さなサブプロブレムに分割することで,問題の凸緩和を直接高精度に解ける新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-16T20:43:49Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification [11.10637926254491]
  我々は,ReLUニューロンに対する新たな凸緩和法により,伝搬最適化と線形最適化に基づくニューラルネットワーク検証アルゴリズムの有効性を向上する。 ニューラルネットワーク検証のための2時間アルゴリズムを設計する。リラクゼーションのフルパワーを活用する線形プログラミングベースのアルゴリズムと、既存のアプローチを一般化する高速な伝搬アルゴリズムである。
  論文  参考訳（メタデータ） (2020-06-24T22:16:58Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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