論文の概要: The Complexity of Verifying Feedforward Neural Networks in Quantised Settings

• arxiv url: http://arxiv.org/abs/2605.29537v1
• Date: Thu, 28 May 2026 07:52:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-30 02:45:56.038737
• Title: The Complexity of Verifying Feedforward Neural Networks in Quantised Settings
• Title（参考訳）: 量子設定におけるフィードフォワードニューラルネットワークの検証の複雑さ
• Authors: Eric Alsmann, Martin Lange, Marco Sälzer,
• Abstract要約: 量子化設定におけるニューラルネットワーク検証の計算複雑性について検討する。 固定演算精度を持つ量子化FNNに対して、LPおよびBV仕様の検証はNP完全であることを示す。 BV仕様の動的量子化FNNに対して、我々は、以前に知られていたPSPACE-hardnessの結果を補完する上限を確立する。
• 参考スコア（独自算出の注目度）: 7.742297876120561
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate the computational complexity of neural network verification in quantised settings. We distinguish three classes of Feedforward Neural Networks (FNNs): rational FNNs with exact rational weights, quantised FNNs whose weights come from a finite-width arithmetic, and dynamically quantised FNNs in which rational networks are evaluated with respect to a given finite-width arithmetic. We consider two types of specifications used in the literature. Linear programming (LP) specifications are conjunctions of linear constraints, while bit-vector (BV) specifications allow reasoning at the bit level and can express non-linear constraints. Our results give a complexity landscape of these verification problems. For quantised FNNs with fixed arithmetic precision, we show that verification under both LP and BV specifications remains NP-complete, matching the complexity of the rational case. For dynamically quantised FNNs with BV specifications, we establish upper bounds, complementing a previously known PSPACE-hardness result.
• Abstract（参考訳）: 量子化設定におけるニューラルネットワーク検証の計算複雑性について検討する。 フィードフォワードニューラルネットワーク(FNN)の3つのクラスを区別する: 正確な有理重みを持つ有理FNN、有限幅演算から重みを求める量子FNN、与えられた有限幅演算に対して有理ネットワークを評価する動的量子FNN。 文献に用いた2種類の仕様について考察する。 線形プログラミング(LP)仕様は線形制約の結合であり、ビットベクトル(BV)仕様はビットレベルでの推論を許容し、非線形制約を表現できる。 この結果から,これらの検証問題を複雑に捉えた。 固定演算精度を持つ量子化FNNの場合、LPおよびBV仕様の下での検証はNP完全であり、有理ケースの複雑さと一致することを示す。 BV仕様の動的量子化FNNに対して、我々は、以前に知られていたPSPACE-hardnessの結果を補完する上限を確立する。

関連論文リスト

• Generalization Bounds of Spiking Neural Networks via Rademacher Complexity [58.338455812259724]
  スパイキングニューラルネットワーク(SNN)は、ニューロモルフィックコンピューティングと計算における大きな可能性のために、バイオインスパイアされたモデルの1つとして注目を集めている。 近年の進歩は、発火を伴うSNNのラデマッハ複雑性が指数関数によって上界化されるような、励起依存的でアーキテクチャ関連の一般化が明らかにされている。 理論的には、Rademacher複雑性を通したいくつかの統合ファイアスキームによるSNNの一般化境界について検討する。
  論文  参考訳（メタデータ） (2026-04-26T14:24:48Z)
• On Integer Programming for the Binarized Neural Network Verification Problem [3.342097413151171]
  バイナリ化ニューラルネットワーク(BNN)は、バイナリウェイトとアクティベーション機能を備えたフィードフォワードニューラルネットワークである。 検証問題は、与えられた入力の小さな摂動がBNNによって誤って分類される可能性があるかどうかを判断しようとする。
  論文  参考訳（メタデータ） (2025-10-01T23:43:18Z)
• On the Hardness of Training Deep Neural Networks Discretely [0.0]
  ニューラルネットワークトレーニング(NNT)の硬さは,ネットワーク深度に大きく影響している。 具体的には、標準仮定の下では、D-NNTは、固定次元とデータセットサイズを持つインスタンスであってもクラスNPに含まれていないことを示す。 これらの結果を2層ネットワーク上でのD-NNTのNP硬度下界の包括的リストで補完する。
  論文  参考訳（メタデータ） (2024-12-17T16:20:29Z)
• An Automata-Theoretic Approach to Synthesizing Binarized Neural Networks [13.271286153792058]
  量子ニューラルネットワーク(QNN)が開発され、二項化ニューラルネットワーク(BNN)は特殊なケースとしてバイナリ値に制限されている。 本稿では,指定された特性を満たすBNNの自動合成手法を提案する。
  論文  参考訳（メタデータ） (2023-07-29T06:27:28Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  データ分布が適切に分離された場合、DNNは分類のためのベイズ最適テスト誤差を達成できることを示す。 よりスムーズな関数との補間により、より一般化できることを示す。
  論文  参考訳（メタデータ） (2023-05-30T19:37:44Z)
• Power and limitations of single-qubit native quantum neural networks [5.526775342940154]
  量子ニューラルネットワーク(QNN)は、機械学習、化学、最適化の応用を確立するための主要な戦略として登場した。 量子ニューラルネットワークのデータ再アップロードの表現能力に関する理論的枠組みを定式化する。
  論文  参考訳（メタデータ） (2022-05-16T17:58:27Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。 接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
  論文  参考訳（メタデータ） (2022-05-11T17:43:54Z)
• Bounding the Complexity of Formally Verifying Neural Networks: A Geometric Approach [1.9493449206135296]
  ReLUニューラルネットワーク(NN)の複雑さを正式に検証することを検討する。 本稿では,2つの異なるNNに対して,検証問題は2種類の制約を満たすことを示す。 両方のアルゴリズムは、NNパラメータをハイパープレーンを用いてNNアーキテクチャの効果に効率的に変換する。
  論文  参考訳（メタデータ） (2020-12-22T00:29:54Z)
• Toward Trainability of Quantum Neural Networks [87.04438831673063]
  量子ニューラルネットワーク(QNN)は、量子スピードアップを達成するために古典的ニューラルネットワークの一般化として提案されている。 QNNのトレーニングには、入力キュービット数に指数関数的に勾配速度がなくなるため、非常に大きなボトルネックが存在する。 木テンソルとステップ制御された構造を持つQNNを二分分類に適用し,ランダムな構造を持つQNNと比較してより高速な収束率と精度を示す。
  論文  参考訳（メタデータ） (2020-11-12T08:32:04Z)
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks [80.55378250013496]
  勾配勾配降下法によりトレーニングされたニューラルネットワークが、トレーニング分布の支持の外で学んだことを外挿する方法について検討する。 グラフニューラルネットワーク(GNN)は、より複雑なタスクでいくつかの成功を収めている。
  論文  参考訳（メタデータ） (2020-09-24T17:48:59Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。 マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。 マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
  論文  参考訳（メタデータ） (2020-06-15T17:06:17Z)

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

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