論文の概要: On the Complexity of Neural Computation in Superposition

• arxiv url: http://arxiv.org/abs/2409.15318v2
• Date: Fri, 18 Apr 2025 18:13:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-30 13:11:01.999825
• Title: On the Complexity of Neural Computation in Superposition
• Title（参考訳）: 重ね合わせにおけるニューラル計算の複雑さについて
• Authors: Micah Adler, Nir Shavit,
• Abstract要約: ニューラルネットワークがニューロンよりも多くの特徴を表現する能力である重ね合わせは、大規模モデルの効率の鍵であると考えられている。 本稿では、重ね合わせにおける計算の理論的基礎を考察し、明示的で証明可能な正しいアルゴリズムの複雑性境界を確立する。
• 参考スコア（独自算出の注目度）: 3.9803704378699103
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Superposition, the ability of neural networks to represent more features than neurons, is increasingly seen as key to the efficiency of large models. This paper investigates the theoretical foundations of computing in superposition, establishing complexity bounds for explicit, provably correct algorithms. We present the first lower bounds for a neural network computing in superposition, showing that for a broad class of problems, including permutations and pairwise logical operations, computing $m'$ features in superposition requires at least $\Omega(\sqrt{m' \log m'})$ neurons and $\Omega(m' \log m')$ parameters. This implies the first subexponential upper bound on superposition capacity: a network with $n$ neurons can compute at most $O(n^2 / \log n)$ features. Conversely, we provide a nearly tight constructive upper bound: logical operations like pairwise AND can be computed using $O(\sqrt{m'} \log m')$ neurons and $O(m' \log^2 m')$ parameters. There is thus an exponential gap between the complexity of computing in superposition (the subject of this work) versus merely representing features, which can require as little as $O(\log m')$ neurons based on the Johnson-Lindenstrauss Lemma. Our hope is that our results open a path for using complexity theoretic techniques in neural network interpretability research.
• Abstract（参考訳）: ニューラルネットワークがニューロンよりも多くの特徴を表現する能力である重ね合わせは、大規模モデルの効率の鍵であると考えられている。 本稿では、重ね合わせにおける計算の理論的基礎を考察し、明示的で証明可能な正しいアルゴリズムの複雑性境界を確立する。 重ね合わせにおけるニューラルネットワーク計算の最初の下位境界を示し、置換やペア論理演算を含む幅広い問題に対して、重ね合わせにおける$m'$の計算には、少なくとも$\Omega(\sqrt{m' \log m'})$のニューロンと$\Omega(m' \log m')$のパラメータが必要であることを示した。 例えば、$n$ニューロンを持つネットワークは、最大$O(n^2 / \log n)$特徴を計算できる。 逆に、ほぼ厳密な構成上界:ペアワイズのような論理演算と$O(\sqrt{m'} \log m')$ニューロンと$O(m' \log^2 m')$パラメータで計算できる。 したがって、重ね合わせ(この研究の主題)における計算の複雑さと単に特徴を表現することの間には指数的なギャップがあり、ジョンソン・リンデンシュトラウス・レムマに基づく$O(\log m')$ニューロンが必要とされる。 私たちの期待は、ニューラルネットワークの解釈可能性研究に複雑性理論技術を使うための道を開くことです。

関連論文リスト

• Neural Networks and (Virtual) Extended Formulations [5.762677915745415]
  私たちは、$P$を最適化するニューラルネットワークのサイズに対して、より低い境界を証明します。 我々は、$mathrmxc(P)$が任意のモノトーンや入力ニューラルネットワークのサイズの低い境界であることを示し、$P$を超える線形最適化問題を解く。
  論文  参考訳（メタデータ） (2024-11-05T11:12:11Z)
• Approximation of the Proximal Operator of the $\ell_\infty$ Norm Using a Neural Network [1.7265013728931]
  ニューラルネットワークを用いて,$textbfprox_alphacdot||infty(mathbfx)$を近似する。 ネットワークの新たな側面は、特徴選択プロセスにより、様々な長さのベクトルを受け入れることができることである。 特徴選択を使用しない「バニラニューラルネットワーク」よりも優れていることを示す。
  論文  参考訳（メタデータ） (2024-08-20T22:12:30Z)
• Mathematical Models of Computation in Superposition [0.9374652839580183]
  重ね合わせは、現在のAIシステムを機械的に解釈する上で深刻な課題となる。 重ね合わせにおけるエンフン計算の数学的モデルを提案し, 重ね合わせはタスクを効率的に遂行するのに有効である。 我々は、重ね合わせで計算を実装するニューラルネットワークを解釈する研究の潜在的な応用について、結論付けている。
  論文  参考訳（メタデータ） (2024-08-10T06:11:48Z)
• Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
  勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。 次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
  論文  参考訳（メタデータ） (2024-04-18T17:57:53Z)
• Memorization Capacity of Neural Networks with Conditional Computation [14.048989759890475]
  我々は,$O(sqrtn)$ニューロンを用いたニューラルネットワークを用いて,$n$の入力出力関係の集合を記憶できることを実証した。 条件付きReLUネットワークを用いて,入力あたりのO(log n)$演算のみを用いて同じタスクを実現できることを示す。
  論文  参考訳（メタデータ） (2023-03-20T16:33:17Z)
• Generalization and Stability of Interpolating Neural Networks with Minimal Width [37.908159361149835]
  補間系における勾配によって訓練された浅層ニューラルネットワークの一般化と最適化について検討する。 トレーニング損失数は$m=Omega(log4 (n))$ニューロンとニューロンを最小化する。 m=Omega(log4 (n))$のニューロンと$Tapprox n$で、テスト損失のトレーニングを$tildeO (1/)$に制限します。
  論文  参考訳（メタデータ） (2023-02-18T05:06:15Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• On the Optimal Memorization Power of ReLU Neural Networks [53.15475693468925]
  フィードフォワードReLUニューラルネットワークは、軽度の分離可能性仮定を満たす任意のN$ポイントを記憶することができることを示す。 このような大きなビットの複雑性を持つことは、サブ線形数のパラメータを記憶するのに必要であり、十分であることを示す。
  論文  参考訳（メタデータ） (2021-10-07T05:25:23Z)
• On the Provable Generalization of Recurrent Neural Networks [7.115768009778412]
  リカレントニューラルネットワーク(RNN)のトレーニングと一般化の分析 正規化条件を使わずに関数を学習する一般化誤差を証明した。 また、入力シーケンスのN-変数関数を学習するための新しい結果も証明する。
  論文  参考訳（メタデータ） (2021-09-29T02:06:33Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。 次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。 頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
  論文  参考訳（メタデータ） (2021-07-22T14:25:16Z)
• ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation [5.35599092568615]
  本稿では,線形整流ユニットを用いたニューラルネットワークのパワーについて検討する。 我々は,2つの基本最適化問題を$mathcalO(m2n2)$のニューラルネットワークで解くことができることを示した。
  論文  参考訳（メタデータ） (2021-02-12T17:23:34Z)
• Size and Depth Separation in Approximating Natural Functions with Neural Networks [52.73592689730044]
  本稿では,ReLUネットワークを用いた自然関数の近似におけるサイズと深さの利点を示す。 我々は、そのような結果が$O(d)$を超えることを証明するための複雑性理論上の障壁を示す。 また、サイズ$O(d)$のネットワークで近似できる明示的な自然関数も示している。
  論文  参考訳（メタデータ） (2021-01-30T21:30:11Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  離散確率測度が$N$原子と$n$実数値関数の集合で成り立つと、元の$N$原子の$n+1$の部分集合で支えられる確率測度が存在する。 我々は、負の円錐によるバリセンターの簡単な幾何学的特徴付けを与え、この新しい測度を「グリード幾何学的サンプリング」によって計算するランダム化アルゴリズムを導出する。 次に、その性質を研究し、それを合成および実世界のデータにベンチマークして、$Ngg n$ regimeにおいて非常に有益であることを示す。
  論文  参考訳（メタデータ） (2020-06-02T16:38:36Z)
• On the Modularity of Hypernetworks [103.1147622394852]
  構造化対象関数の場合、ハイパーネットワークにおけるトレーニング可能なパラメータの総数は、標準ニューラルネットワークのトレーニング可能なパラメータの数や埋め込み法よりも桁違いに小さいことを示す。
  論文  参考訳（メタデータ） (2020-02-23T22:51:52Z)

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

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