論文の概要: Random Parameter Noise Does Not Make Exact ReLU Verification Easy
- arxiv url: http://arxiv.org/abs/2607.14375v1
- Date: Wed, 15 Jul 2026 21:26:20 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-17 17:01:32.917799
- Title: Random Parameter Noise Does Not Make Exact ReLU Verification Easy
- Title（参考訳）: ランダムパラメータノイズは、厳密なReLU検証を容易にするものではない
- Authors: Mojtaba Soltanalian,
- Abstract要約: 逆スムースドモデルにおけるReLUネットワークの正確な検証について検討する。
標準的な仮定である$mathrmNPnotsubseteqmathrmBPP$ では,ネットワークサイズ,ビット複雑性,各ベースインスタンスの逆ノイズレベルにランニングタイムを埋め込むような,健全かつ完全検証器が存在しないことを示す。
- 参考スコア（独自算出の注目度）: 14.270378035741404
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study exact verification of ReLU networks in an adversarial smoothed model. Every network weight and bias is independently perturbed by Gaussian noise, clipped to $[-2,2]$, and rounded to the exact dyadic grid determined by the input bit complexity. We show that, under the standard assumption $\mathrm{NP}\not\subseteq\mathrm{BPP}$, there is no sound and complete verifier whose expected running time is polynomial in network size, bit complexity, and inverse noise level for every base instance. The conclusion already holds at the fixed noise level $σ_\star=2^{-11}$ for one-hidden-layer networks over a unit box, with hidden fan-in at most three and base coefficients in $[-1,1]$. The proof combines an exact gap embedding with a quantitative robustness argument. For every E3SAT formula $Φ$ with $m$ clauses, a four-ReLU-per-clause construction satisfies $\max_{x\in[0,1]^n} g_Φ(x)=(m-\operatorname{unsat}(Φ))/3$, and coordinatewise threshold rounding never decreases the objective. A weighted parameter-sensitivity inequality and Gaussian concentration then show that a verification gap linear in $m$ survives the aggregate perturbation of all coefficients with probability at least $1-e^{-m/8}$. The proof includes clipping, exact dyadic rounding, output-layer perturbations, polynomial-bit sampling of the rounded Gaussian law, and the conversion from expected smoothed running time to a BPP algorithm. Computational checks test the exact identity and illustrate the different scaling of extensive and constant gaps; they are diagnostics rather than evidence for the complexity theorem. The result concerns worst-case base networks in the stated absolute-noise model, but it shows that parameter nondegeneracy alone does not yield a universal smoothed-polynomial guarantee for exact verification.
- Abstract（参考訳）: 逆スムースドモデルにおけるReLUネットワークの正確な検証について検討する。
ネットワークの重みとバイアスはガウスノイズによって独立に乱れ、$[-2,2]$にクリップされ、入力ビットの複雑さによって決定される正確なダイアドグリッドに丸められる。
標準的な仮定である $\mathrm{NP}\not\subseteq\mathrm{BPP}$ では、期待される実行時間がネットワークサイズ、ビット複雑性、すべてのベースインスタンスに対する逆ノイズレベルであるような、音と完全検証器は存在しない。
この結論は、固定ノイズレベル $σ_\star=2^{-11}$ において、ユニットボックス上の1つの隠れた層ネットワークに対して既に成立しており、隠れたファンインは3つあり、ベース係数は$[-1,1]$である。
この証明は、正確なギャップ埋め込みと定量的ロバストネスの議論を組み合わせたものである。
任意の E3SAT 公式に対して、$m$ の節付き $ $ に対して、 4-ReLU-per-clause 構成は $\max_{x\in[0,1]^n} g_*(x)=(m-\operatorname{unsat}(\))/3$ を満たす。
重み付けされたパラメータ感度の不等式とガウス濃度は、$m$の検証ギャップが少なくとも1-e^{-m/8}$の確率を持つ全ての係数の集合摂動を生き残ることを示す。
この証明には、クリッピング、正確なダイアドラウンド、出力層摂動、丸いガウス法則の多項式ビットサンプリング、期待される滑らかな実行時間からBPPアルゴリズムへの変換が含まれる。
計算チェックは、正確なアイデンティティを検証し、広範囲で一定のギャップのスケーリングを図示する;それらは複雑さの定理の証拠というよりは診断である。
その結果、絶対ノイズモデルにおける最悪のケースベースネットワークが関係するが、パラメータ非退化だけでは、正確な検証のための普遍的なスムーズなポリノミカル保証が得られないことを示す。
関連論文リスト
- Saturation Makes Quantization Error Additive: A Coverage Model with a Certificate [0.0]
混合精度量子化は、モデルのどの部分がより高い精度を維持するかを決定する必要がある。
本研究は, 層単位での定量化による損失を, 層ごとの感性や, 対方向の感性から再現可能であることを示す。
本稿では, 測定値の差分プロファイルである$f(S)=cbigl (1-prod_iin S (1-a_i)bigr)$を, その$L$適合ブレークレートから数パーセント以内まで再現する。
論文 参考訳（メタデータ） (2026-07-14T02:08:33Z) - A law of robustness for two-layer neural networks with arbitrary weights [0.0]
Bubeck、Li、Nagarajは、一般的なデータでは、ノイズラベルに適合する$m$のニューロンを持つ任意の2層ニューラルネットワークは、リプシッツ定数を持つ必要があると推測した。
予想法則を1つの対数係数まで証明し、特にReLUネットワークにおいて連続的な片方向線形活性化を行う。
論文 参考訳（メタデータ） (2026-07-08T17:44:15Z) - Decoherence as Defence and the Magnitude of Noise Regularisation: A Rigorous N -Qubit Theory of Stochastic Quantum Neural Networks for Adversarially Robust Network Intrusion Detection [0.0]
マスター方程式とそのベクトル化されたリウビリアンによる$N$-qubitの定式化を与える。
エンフェデコヒーレンス・コントラクションの定理、すなわち強度の非分極チャネルを証明します。
このロバスト性は、アタックタイムの収縮ではなく、ノイズの変形したトレーニング境界から生じることを示す。
論文 参考訳（メタデータ） (2026-06-23T07:06:56Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
低忠実度状態におけるノイズランダム量子回路の測定結果の分布について検討する。
十分に弱くユニタリな局所雑音に対して、一般的なノイズ回路インスタンスの出力分布$p_textnoisy$間の相関(線形クロスエントロピーベンチマークで測定)は指数関数的に減少する。
ノイズが不整合であれば、出力分布は、正確に同じ速度で均一分布の$p_textunif$に近づく。
論文 参考訳（メタデータ） (2021-11-29T19:26:28Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳（メタデータ） (2020-12-31T18:24:41Z) - Why Are Convolutional Nets More Sample-Efficient than Fully-Connected
Nets? [33.51250867983687]
標準学習アルゴリズムにおいて、証明可能なサンプル複雑性のギャップを示すことができる自然なタスクを示す。
単一の対象関数を示し、可能なすべての分布について、$O(1)$対$Omega(d2/varepsilon)$ギャップを学習する。
同様の結果が$ell$回帰およびAdamやAdaGradといった適応型トレーニングアルゴリズムに対して達成される。
論文 参考訳（メタデータ） (2020-10-16T17:15:39Z) - Denoising modulo samples: k-NN regression and tightness of SDP
relaxation [5.025654873456756]
サンプルの値が$f(x_i)$で一様誤差率$O(fraclog nn)frac1d+2)$を高い確率で保持する2段階のアルゴリズムを導出する。
サンプル $f(x_i)$ の見積もりは、その後、関数 $f$ の見積もりを構築するために使われる。
論文 参考訳（メタデータ） (2020-09-10T13:32:46Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。