論文の概要: Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions
- arxiv url: http://arxiv.org/abs/2609.27932v1
- Date: Sat, 22 Aug 2026 09:46:54 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-28 05:09:56.013977
- Title: Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions
- Title（参考訳）: 入力次元と出力次元でW[1]ハードパラメータをパラメータ化した2元量子ニューラルネットワークトレーニング
- Abstract要約: 2-QNNT が W[1]-ハードパラメータ化$+$ であることを証明する。
D_k=((r,(r)):0le rle k$で、全ての入力がそのターゲットに等しい。
これらの入力の全てのニューロンは、活性化プロファイルとして$k+1$しか持たない。
- 参考スコア（独自算出の注目度）: 7.764443932311498
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Ganian et al. (ICLR 2026) proved that quantized neural network training is fixed-parameter tractable when parameterized jointly by architecture treewidth, input dimension $α$, and output dimension $ω$, and left open whether $α+ω$ alone yields fixed-parameter tractability. We prove that 2-QNNT is W[1]-hard parameterized by $α+ω$. The hardness already holds with zero error on $D_k=\{(ξ^{(r)},ξ^{(r)}):0\le r\le k\}$, where every input equals its target, $|D_k|=α=ω=k+1$, and the examples form a coordinatewise prefix chain. It also holds when every non-source bias is fixed to zero. Under the Exponential Time Hypothesis, no algorithm runs in $f(α+ω)|I|^{o(α+ω)}$ for any computable $f$. The reduction starts from DAG edge-disjoint paths, converts edge capacity to vertex capacity with a directed line graph, and normalizes the result into a valid layered architecture. The key structural step is a one-flip routing equivalence: on the prefix-chain inputs, nonnegative binary weights make every activation monotone, and each required output transition has a weight-one predecessor making the same transition. Iterating this relation backward extracts a path from the unique changing input, while different transitions yield vertex-disjoint paths. In particular, every neuron on these inputs has only $k+1$ possible activation profiles.
- Abstract（参考訳）: Ganian et al (ICLR 2026) は、アーキテクチャツリー幅、入力次元$α$、出力次元$ω$でパラメータ化されると、量子化されたニューラルネットワークのトレーニングが固定パラメータ抽出可能であることを証明した。
2-QNNT が W[1]-ハードパラメータ化され、$α+ω$ であることが証明される。
ハードネスは、既に$D_k=\{(\^{(r)} 上のゼロ誤差で成り立つ:0\le r\le k\}$ では、全ての入力がそのターゲットと等しい、$|D_k|=α=ω=k+1$ であり、その例は座標的なプレフィックスチェーンを形成する。
また、すべての非ソースバイアスが0に固定されている場合にも有効である。
指数時間仮説の下では、任意の計算可能な$f$に対して$f(α+ω)|I|^{o(α+ω)}$で走るアルゴリズムは存在しない。
削減はDAGエッジ分離パスから始まり、エッジキャパシティを有向線グラフで頂点キャパシティに変換し、その結果を有効な階層化アーキテクチャに標準化する。
主要な構造的ステップは1フリップのルーティング等価性であり、プレフィックスチェーン入力では、非負のバイナリウェイトはすべてのアクティベーションモノトンを作り、各出力遷移は、同じ遷移を行うウェイトワン前駆体を持つ。
この関係を反復すると、一意に変化する入力から経路を抽出し、異なる遷移は頂点非随伴経路を生成する。
特に、これらの入力上の全てのニューロンは、活性化プロファイルとして$k+1$しか持たない。
関連論文リスト
- Automatic Differentiation from Scratch: How PyTorch Computes Gradients in Physics-Informed Neural Networks [0.0]
PyTorchの自動微分(AD)エンジンは、物理インフォームドニューラルネットワーク(PINN)トレーニングの勾配を計算する。
本稿では,PyTorchがPINNトレーニングの勾配を計算する方法を示す。
論文 参考訳（メタデータ） (2026-06-13T11:24:13Z) - Wavelet Variance Equipartition as a Threshold for World-Model Quality and Quantum Kernel TN-Simulability [0.0]
我々はウェーブレットスケーリング指数$$を臨界診断として同定する。
振幅符号化された量子カーネルの古典的シミュラビリティのシャープな遷移境界として$=1/2$を確立する。
この分散は、厳密には$Var[X] = (d-2)$としてスケールする。
論文 参考訳（メタデータ） (2026-05-12T05:41:12Z) - Architecture Shape Governs QNN Trainability: Jacobian Null Space Growth and Parameter Efficiency [3.1094222618006664]
トレーニング容易性はアーキテクチャ形状が$(N,L)$で,固定$E$で大きく変化することを示す。
ヤコビアン$J$と一致する係数の構造的階数不足をその原因となるメカニズムとして同定する。
論文 参考訳（メタデータ） (2026-05-07T09:52:45Z) - Emergence and scaling laws in SGD learning of shallow neural networks [64.48316762675141]
等方性ガウスデータに基づいてP$ニューロンを持つ2層ニューラルネットワークを学習するためのオンライン勾配降下(SGD)の複雑さについて検討した。
平均二乗誤差(MSE)を最小化するために,学生2層ネットワークのトレーニングのためのSGDダイナミックスを高精度に解析する。
論文 参考訳（メタデータ） (2025-04-28T16:58:55Z) - On encoded quantum gate generation by iterative Lyapunov-based methods [0.0]
本稿では,量子ゲート生成の符号化問題について述べる。
emphReference Input Generation Algorithm (RIGA) はこの研究で一般化されている。
論文 参考訳（メタデータ） (2024-09-02T10:41:15Z) - Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。
本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
論文 参考訳（メタデータ） (2024-04-29T15:04:07Z) - 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) - Transformers as Support Vector Machines [54.642793677472724]
自己アテンションの最適化幾何と厳密なSVM問題との間には,形式的等価性を確立する。
勾配降下に最適化された1層変圧器の暗黙バイアスを特徴付ける。
これらの発見は、最適なトークンを分離し選択するSVMの階層としてのトランスフォーマーの解釈を刺激していると信じている。
論文 参考訳（メタデータ） (2023-08-31T17:57:50Z) - Bounding the Width of Neural Networks via Coupled Initialization -- A
Worst Case Analysis [121.9821494461427]
2層ReLUネットワークに必要なニューロン数を著しく削減する方法を示す。
また、事前の作業を改善するための新しい下位境界を証明し、ある仮定の下では、最善を尽くすことができることを証明します。
論文 参考訳（メタデータ） (2022-06-26T06:51:31Z) - High-dimensional Asymptotics of Feature Learning: How One Gradient Step
Improves the Representation [89.21686761957383]
2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。
我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
論文 参考訳（メタデータ） (2022-05-03T12:09:59Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。