論文の概要: The Complexity of ReLU Network Synthesis from a Parameter Multiset
- arxiv url: http://arxiv.org/abs/2611.04074v2
- Date: Wed, 04 Nov 2026 10:44:06 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-06 03:25:57.739497
- Title: The Complexity of ReLU Network Synthesis from a Parameter Multiset
- Title（参考訳）: パラメータ多重集合によるReLUネットワーク合成の複雑さ
- Abstract要約: パラメータ値が事前に与えられたとき、ReLUネットワークを構築するのがどれほど難しいか尋ねる。
問題は、境界内のReLUネットワークのグラフを選択して、その数値をそのエッジとバイアスに配置して、ターゲットに合うかどうかである。
- 参考スコア（独自算出の注目度）: 3.114745697185681
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We ask how hard it is to build a ReLU network when its parameter values are given in advance. An instance supplies an appropriate encoding of a target behavior, a multiset of rational numbers, and a bound on the number of neurons (output included). The question is whether one can choose the graph of a ReLU network within the bound, and place the numbers on its edges and biases so that it meets the target. This separates the numbers from the architecture. Matching two labeled examples exactly is already $\mathsf{NP}$-complete, so we ask what changes when the target must hold on every input or on average. Agreeing with a Boolean circuit on every Boolean input is $Σ_2^{\mathsf P}$-complete, already for four neurons. Agreeing with a given ReLU network on every real input lies in $\mathsf{DP}$ for every fixed neuron bound and is $\mathsf{DP}$-complete for three neurons. Approximating a ReLU network on the unit cube within absolute error one everywhere is $Σ_2^{\mathsf P}$-complete, even with no hidden neurons and all numbers equal and positive. Deciding whether some network has expected squared loss at most a threshold is $\mathsf{NP}^{\mathsf{PP}}$-complete for uniform Boolean inputs. For uniform inputs on the unit cube and for standard Gaussian inputs with a positive threshold, the same holds for two neurons when a positive risk gap, given in binary and possibly exponentially small, separates yes from no instances. Without a gap, the cube version is complete for guessing a polynomial-length string, then comparing a sum of exponentially many rationals with a threshold, all computable in polynomial time from the input and the guess.
- Abstract（参考訳）: パラメータ値が事前に与えられたとき、ReLUネットワークを構築するのがどれほど難しいか尋ねる。
インスタンスは、対象の振る舞いの適切なエンコーディング、有理数の多重集合、ニューロンの数(出力を含む)のバウンドを提供する。
問題は、境界内のReLUネットワークのグラフを選択して、その数値をそのエッジとバイアスに配置して、ターゲットに合うかどうかである。
これにより、番号はアーキテクチャから分離される。
2つのラベル付き例を正確にマッチングすることは、すでに$\mathsf{NP}$-completeである。
ブール回路を全てのブール入力に集積すると、既に4つのニューロンに対して$Σ_2^{\mathsf P}$完全となる。
与えられたReLUネットワークを任意の実入力に集約すると、固定されたニューロン境界に対して$\mathsf{DP}$となり、3つのニューロンに対して$\mathsf{DP}$-completeとなる。
絶対誤差で単位立方体上のReLUネットワークを至るところで近似するのは$Σ_2^{\mathsf P}$完全である。
あるネットワークが少なくとも閾値で2乗損失を期待しているかどうかを決定することは、均一なブール入力に対して$\mathsf{NP}^{\mathsf{PP}}$-completeである。
単位立方体上の一様入力と正の閾値を持つ標準ガウス入力の場合、正のリスクギャップが二進数で指数関数的に小さい場合、同じことが2つのニューロンに対して成り立つ。
ギャップがなければ、立方体バージョンは多項式長の文字列を推測し、指数関数的に多くの有理数の和としきい値を比較して、入力と推測から多項式時間で計算できる。
関連論文リスト
- A concentration result for multilayer feedforward neural networks [0.0]
我々は,第1層のニューロンに$n$,第1層のニューロンに1つのニューロン,第2層のニューロンに1つのニューロン(出力ニューロン)を配置した,任意の固定価格の多層フィードフォワード人工ニューラルネットワークを検討する。
すべての$varepsilon > 0$に対して、出力ニューロンの値が $[- varepsilon, + varepsilon]$ の確率は 1 となり、$n$ は無限大になる。
論文 参考訳（メタデータ） (2026-08-15T17:31:46Z) - Compressed Computation under $L^4$ Loss is likely Computation in Superposition [0.7128080962281788]
本稿では,50個のニューロンを持つ単層ReLUネットワークを用いた重ね合わせ計算モデルについて検討する。
損失$L4$でトレーニングすると、重ね合わせですべての機能を計算しているように見えるソリューションが生まれる。
ネットワークは、各特徴をニューロン上にスパースバイナリコードワードを割り当て、それをエンコーダの擬似逆数で復号する。
論文 参考訳（メタデータ） (2026-07-06T08:33:51Z) - Matching the Statistical Query Lower Bound for $k$-Sparse Parity Problems with Sign Stochastic Gradient Descent [83.85536329832722]
我々は、2層完全連結ニューラルネットワーク上での符号勾配降下(SGD)による$k$スパースパリティ問題を解く。
このアプローチは、$d$次元ハイパーキューブ上での$k$スパースパリティ問題を効率的に解くことができることを示す。
次に、符号SGDを持つトレーニングニューラルネットワークが、この優れたネットワークを効果的に近似し、小さな統計的誤差で$k$-parity問題を解く方法を示す。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳（メタデータ） (2023-11-23T02:19:32Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Training Fully Connected Neural Networks is $\exists\mathbb{R}$-Complete [4.170994234169557]
InpiricalRiskmization(英語版)として知られる、与えられたデータポイントのセットに可能な限り適合する2層完全連結ニューラルネットワークの重みとバイアスを求める問題を考察する。
任意のデータポイントが有理である場合でも、いくつかのインスタンスを最適に訓練できるウェイトとして、任意の大きな次数の代数数が必要であることを証明します。
この結果、Basu, Mianjy, Mukherjee [ICLR 2018]のような検索アルゴリズムは、$mathsfNP=existsでない限り、複数の出力次元を持つネットワークでは不可能である。
論文 参考訳（メタデータ） (2022-04-04T10:28:11Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - A case where a spindly two-layer linear network whips any neural network
with a fully connected input layer [24.132345589750592]
勾配降下によるスパース目標を効率的に学習するために,スパース入力層が必要であることを示す。
驚くべきことに、同じタイプの問題は、単純な2層線形ニューラルネットワークによって大幅に効率良く解決できる。
論文 参考訳（メタデータ） (2020-10-16T20:49:58Z) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳（メタデータ） (2020-07-09T07:09:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。