論文の概要: The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification

• arxiv url: http://arxiv.org/abs/2006.14076v2
• Date: Thu, 22 Oct 2020 21:45:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-17 09:32:41.966386
• Title: The Convex Relaxation Barrier, Revisited: Tightened Single-Neuron Relaxations for Neural Network Verification
• Title（参考訳）: 対流緩和障壁の再検討:ニューラルネットワーク検証のための強化された単一ニューロン緩和
• Authors: Christian Tjandraatmadja and Ross Anderson and Joey Huchette and Will Ma and Krunal Patel and Juan Pablo Vielma
• Abstract要約: 我々は,ReLUニューロンに対する新たな凸緩和法により,伝搬最適化と線形最適化に基づくニューラルネットワーク検証アルゴリズムの有効性を向上する。 ニューラルネットワーク検証のための2時間アルゴリズムを設計する。リラクゼーションのフルパワーを活用する線形プログラミングベースのアルゴリズムと、既存のアプローチを一般化する高速な伝搬アルゴリズムである。
• 参考スコア（独自算出の注目度）: 11.10637926254491
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We improve the effectiveness of propagation- and linear-optimization-based neural network verification algorithms with a new tightened convex relaxation for ReLU neurons. Unlike previous single-neuron relaxations which focus only on the univariate input space of the ReLU, our method considers the multivariate input space of the affine pre-activation function preceding the ReLU. Using results from submodularity and convex geometry, we derive an explicit description of the tightest possible convex relaxation when this multivariate input is over a box domain. We show that our convex relaxation is significantly stronger than the commonly used univariate-input relaxation which has been proposed as a natural convex relaxation barrier for verification. While our description of the relaxation may require an exponential number of inequalities, we show that they can be separated in linear time and hence can be efficiently incorporated into optimization algorithms on an as-needed basis. Based on this novel relaxation, we design two polynomial-time algorithms for neural network verification: a linear-programming-based algorithm that leverages the full power of our relaxation, and a fast propagation algorithm that generalizes existing approaches. In both cases, we show that for a modest increase in computational effort, our strengthened relaxation enables us to verify a significantly larger number of instances compared to similar algorithms.
• Abstract（参考訳）: 我々は,ReLUニューロンに対する新たな凸緩和法により,伝搬最適化と線形最適化に基づくニューラルネットワーク検証アルゴリズムの有効性を向上する。 ReLUの単変量入力空間のみに焦点をあてる以前の単一ニューロン緩和とは異なり、本手法はReLUより前のアフィン前活性化関数の多変量入力空間を考える。 部分モジュラリティと凸幾何学の結果を用いて、この多変量入力がボックス領域上にあるとき、最も厳密な凸緩和を明示的に記述する。 本研究は, 自然凸緩和障壁として提案されている単変量-入出力緩和よりも, 凸緩和がかなり強いことを示す。 緩和を説明するには指数関数的な不等式を必要とするが、線形時間に分離できるため、必要に応じて最適化アルゴリズムに効率的に組み込むことができる。 この新たな緩和に基づいて、ニューラルネットワーク検証のための2つの多項式時間アルゴリズムを設計する: 緩和の完全なパワーを利用する線形プログラミングベースのアルゴリズムと、既存のアプローチを一般化する高速な伝播アルゴリズムである。 いずれの場合も,計算量の増加を控えめに考えると,強化された緩和により,類似アルゴリズムに比べてインスタンス数が有意に多いことの検証が可能となる。

関連論文リスト

• Convex Relaxations of ReLU Neural Networks Approximate Global Optima in Polynomial Time [45.72323731094864]
  本稿では,2層ReLULUネットワーク間における重み減衰と凸緩和の最適性ギャップについて検討する。 私たちの研究は、なぜローカルメソッドがうまく機能するのかを理解することに新たな光を当てています。
  論文  参考訳（メタデータ） (2024-02-06T01:29:35Z)
• Using Linear Regression for Iteratively Training Neural Networks [4.873362301533824]
  ニューラルネットワークの重みとバイアスを学習するための単純な線形回帰に基づくアプローチを提案する。 このアプローチは、より大きく、より複雑なアーキテクチャに向けられている。
  論文  参考訳（メタデータ） (2023-07-11T11:53:25Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Shuffled linear regression through graduated convex relaxation [12.614901374282868]
  シャッフル線形回帰問題は、入力と出力の対応が不明なデータセットにおける線形関係を復元することを目的としている。 この問題は、調査データを含む広範囲のアプリケーションで発生する。 後最大化目的関数に基づく線形回帰をシャッフルする新しい最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-30T17:33:48Z)
• DeepSplit: Scalable Verification of Deep Neural Networks via Operator Splitting [70.62923754433461]
  入力摂動に対するディープニューラルネットワークの最悪の性能を分析することは、大規模な非最適化問題の解決につながる。 解析解を持つ小さなサブプロブレムに分割することで,問題の凸緩和を直接高精度に解ける新しい手法を提案する。
  論文  参考訳（メタデータ） (2021-06-16T20:43:49Z)
• Scaling the Convex Barrier with Sparse Dual Algorithms [141.4085318878354]
  本稿では,ニューラルネットワークバウンダリングのための2つの新しい2重アルゴリズムを提案する。 どちらの方法も新しい緩和の強さを回復する: 厳密さと線形分離オラクル。 実行時間のほんの一部で、既製のソルバよりも優れた境界を得ることができます。
  論文  参考訳（メタデータ） (2021-01-14T19:45:17Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。 このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。 また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
  論文  参考訳（メタデータ） (2020-10-13T08:02:38Z)
• Activation Relaxation: A Local Dynamical Approximation to Backpropagation in the Brain [62.997667081978825]
  活性化緩和(AR)は、バックプロパゲーション勾配を力学系の平衡点として構成することで動機付けられる。 我々のアルゴリズムは、正しいバックプロパゲーション勾配に迅速かつ堅牢に収束し、単一のタイプの計算単位しか必要とせず、任意の計算グラフで操作できる。
  論文  参考訳（メタデータ） (2020-09-11T11:56:34Z)

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

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