論文の概要: Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit
- arxiv url: http://arxiv.org/abs/2406.01581v1
- Date: Mon, 3 Jun 2024 17:56:58 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-05 21:41:25.384997
- Title: Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit
- Title（参考訳）: ニューラルネットワークによる情報理論限界近傍のSGDを用いた低次元多項式の学習
- Authors: Jason D. Lee, Kazusato Oko, Taiji Suzuki, Denny Wu,
- Abstract要約: 単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。
SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
- 参考スコア（独自算出の注目度）: 75.4661041626338
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of gradient descent learning of a single-index target function $f_*(\boldsymbol{x}) = \textstyle\sigma_*\left(\langle\boldsymbol{x},\boldsymbol{\theta}\rangle\right)$ under isotropic Gaussian data in $\mathbb{R}^d$, where the link function $\sigma_*:\mathbb{R}\to\mathbb{R}$ is an unknown degree $q$ polynomial with information exponent $p$ (defined as the lowest degree in the Hermite expansion). Prior works showed that gradient-based training of neural networks can learn this target with $n\gtrsim d^{\Theta(p)}$ samples, and such statistical complexity is predicted to be necessary by the correlational statistical query lower bound. Surprisingly, we prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ of arbitrary polynomial link function with a sample and runtime complexity of $n \asymp T \asymp C(q) \cdot d\mathrm{polylog} d$, where constant $C(q)$ only depends on the degree of $\sigma_*$, regardless of information exponent; this dimension dependence matches the information theoretic limit up to polylogarithmic factors. Core to our analysis is the reuse of minibatch in the gradient computation, which gives rise to higher-order information beyond correlational queries.
- Abstract（参考訳）: 単一インデックス対象関数 $f_*(\boldsymbol{x}) = \textstyle\sigma_*\left(\langle\boldsymbol{x},\boldsymbol{\theta}\rangle\right)$ の勾配勾配勾配学習の問題を研究する。
前回の研究では、ニューラルネットワークの勾配に基づくトレーニングが、$n\gtrsim d^{\Thetaでこのターゲットを学習できることが示されている。
(p)}$サンプルとそのような統計的複雑さは相関的な統計的クエリーの下限によって予測される。
驚くべきことに、SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプルと実行時複雑性が$n \asymp T \asymp Cの任意の多項式リンク関数の$f_*$を学習する。
(q) \cdot d\mathrm{polylog} d$, where constant $C
(q)$は情報指数に関係なく$\sigma_*$の次数にのみ依存する。
我々の分析の核となるのは、勾配計算におけるミニバッチの再利用であり、相関クエリ以上の高次情報をもたらす。
関連論文リスト
- Sample and Computationally Efficient Robust Learning of Gaussian Single-Index Models [37.42736399673992]
シングルインデックスモデル (SIM) は $sigma(mathbfwast cdot mathbfx)$ という形式の関数であり、$sigma: mathbbR to mathbbR$ は既知のリンク関数であり、$mathbfwast$ は隠れ単位ベクトルである。
適切な学習者が$L2$-error of $O(mathrmOPT)+epsilon$。
論文 参考訳（メタデータ） (2024-11-08T17:10:38Z) - Near-Optimal and Tractable Estimation under Shift-Invariance [0.21756081703275998]
そのような信号のクラスは、非常にリッチである:$mathbbCn$ 上のすべての指数振動を含み、合計$s$ である。
このクラスの統計複雑性は、$(delta)$-confidence $ell$-ballの半径2乗最小マックス周波数によって測定されるが、$s$-sparse信号のクラス、すなわち$Oleft(slog(en) + log(delta-1)right) cdot log(en/s)とほぼ同じであることを示す。
論文 参考訳（メタデータ） (2024-11-05T18:11:23Z) - Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。
2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
論文 参考訳（メタデータ） (2024-06-17T17:59:17Z) - Learning Hierarchical Polynomials with Three-Layer Neural Networks [56.71223169861528]
3層ニューラルネットワークを用いた標準ガウス分布における階層関数の学習問題について検討する。
次数$k$s$p$の大規模なサブクラスの場合、正方形損失における階層的勾配によるトレーニングを受けた3層ニューラルネットワークは、テストエラーを消すためにターゲット$h$を学習する。
この研究は、3層ニューラルネットワークが複雑な特徴を学習し、その結果、幅広い階層関数のクラスを学ぶ能力を示す。
論文 参考訳（メタデータ） (2023-11-23T02:19:32Z) - 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) - Neural Networks Efficiently Learn Low-Dimensional Representations with
SGD [22.703825902761405]
SGDで訓練されたReLU NNは、主方向を回復することで、$y=f(langleboldsymbolu,boldsymbolxrangle) + epsilon$という形の単一インデックスターゲットを学習できることを示す。
また、SGDによる近似低ランク構造を用いて、NNに対して圧縮保証を提供する。
論文 参考訳（メタデータ） (2022-09-29T15:29:10Z) - Neural Networks can Learn Representations with Gradient Descent [68.95262816363288]
特定の状況下では、勾配降下によって訓練されたニューラルネットワークは、カーネルメソッドのように振る舞う。
実際には、ニューラルネットワークが関連するカーネルを強く上回ることが知られている。
論文 参考訳（メタデータ） (2022-06-30T09:24:02Z) - 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) - Learning (Very) Simple Generative Models Is Hard [45.13248517769758]
我々は,$mathbbRdtobbRd'$の出力座標が$mathrmpoly(d)$ニューロンを持つ一層ReLUネットワークである場合でも,リアルタイムアルゴリズムが問題を解決可能であることを示す。
我々の証明の鍵となる要素は、コンパクトに支持されたピースワイズ線形関数$f$をニューラルネットワークで束ねたスロープで構築することであり、$mathcalN(0,1)$のプッシュフォワードは$mathcalのすべての低度モーメントと一致する。
論文 参考訳（メタデータ） (2022-05-31T17:59:09Z) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳（メタデータ） (2020-07-09T07:09:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。