論文の概要: Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations

• arxiv url: http://arxiv.org/abs/2406.11828v1
• Date: Mon, 17 Jun 2024 17:59:17 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-18 13:04:25.322044
• Title: Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations
• Title（参考訳）: 多様な特徴の総和:計算難易度とリッジ結合のための効率的な勾配に基づく学習
• Authors: Kazusato Oko, Yujin Song, Taiji Suzuki, Denny Wu,
• Abstract要約: 目的関数 $f_*:mathbbRdtomathbbR$ を加法構造で学習する際の計算複雑性について検討する。 2層ニューラルネットワークの勾配学習により,$f_*$の大規模なサブセットを効率的に学習できることを実証した。
• 参考スコア（独自算出の注目度）: 40.77319247558742
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the computational and sample complexity of learning a target function $f_*:\mathbb{R}^d\to\mathbb{R}$ with additive structure, that is, $f_*(x) = \frac{1}{\sqrt{M}}\sum_{m=1}^M f_m(\langle x, v_m\rangle)$, where $f_1,f_2,...,f_M:\mathbb{R}\to\mathbb{R}$ are nonlinear link functions of single-index models (ridge functions) with diverse and near-orthogonal index features $\{v_m\}_{m=1}^M$, and the number of additive tasks $M$ grows with the dimensionality $M\asymp d^\gamma$ for $\gamma\ge 0$. This problem setting is motivated by the classical additive model literature, the recent representation learning theory of two-layer neural network, and large-scale pretraining where the model simultaneously acquires a large number of "skills" that are often localized in distinct parts of the trained network. We prove that a large subset of polynomial $f_*$ can be efficiently learned by gradient descent training of a two-layer neural network, with a polynomial statistical and computational complexity that depends on the number of tasks $M$ and the information exponent of $f_m$, despite the unknown link function and $M$ growing with the dimensionality. We complement this learnability guarantee with computational hardness result by establishing statistical query (SQ) lower bounds for both the correlational SQ and full SQ algorithms.
• Abstract（参考訳）: 対象関数 $f_*:\mathbb{R}^d\to\mathbb{R}$ と加法構造を持つ加法構造、すなわち $f_*(x) = \frac{1}{\sqrt{M}}\sum_{m=1}^M f_m(\langle x, v_m\rangle)$, ここで $f_1,f_2,...,f_M:\mathbb{R}\to\mathbb{R}$ は単射モデル(尾根関数)の非線形リンク関数で、多様でほぼ直交的な指数を持つ$\{v_m\}_{m=1}^M$ と、加法タスク $M$M は$M の次元で成長する。 この問題は、古典的な加法モデル文学、最近の2層ニューラルネットワークの表現学習理論、および訓練されたネットワークの異なる部分にしばしば局所化される多数の「スキル」を同時に取得する大規模事前学習によって動機付けられている。 本研究では,2層ニューラルネットワークの勾配勾配勾配勾配学習により,未知のリンク関数とM$の次元で増大するにもかかわらず,M$のタスク数とf_m$の情報指数に依存する多項式統計および計算の複雑さを効果的に学習できることを証明した。 我々は,この学習可能性保証を,相関SQアルゴリズムと完全SQアルゴリズムの双方に対して,統計的クエリ(SQ)の下限を確立することにより,計算難易度結果と補完する。

関連論文リスト

• 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)
• On the Complexity of Learning Sparse Functions with Statistical and Gradient Queries [25.03801392644285]
  一般的な製品分布に対するスパース関数のサポートを学習するために,$mathsfDLQ$のクエリ複雑性を厳密に評価する。 正方形損失の場合、$mathsfDLQ$は、$mathsfSQ$よりも潜在的にずっと悪い相関統計クエリ$(mathsfCSQ)$-の複雑さと一致する。 また、$mathsfDLQ$が2層学習の複雑さを正確に記述することで、(確率的な)勾配勾配で学習をキャプチャできることを示す。
  論文  参考訳（メタデータ） (2024-07-08T05:30:34Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の等方的ガウスデータの下で勾配降下学習の問題を考察する。 SGDアルゴリズムで最適化された2層ニューラルネットワークは、サンプル付き任意のリンク関数の$f_*$を学習し、実行時の複雑さは$n asymp T asymp C(q) cdot dであることを示す。
  論文  参考訳（メタデータ） (2024-06-03T17:56:58Z)
• 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)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
  2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。 過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
  論文  参考訳（メタデータ） (2020-07-09T07:09:28Z)
• Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation [30.137884459159107]
  連続状態と行動空間を用いた強化学習において,Q$関数を効率よく学習する方法を考える。 我々は、$epsilon$-Schmidt $Q$-functionと$widetildeO(frac1epsilonmax(d1, d_2)+2)$のサンプル複雑性を求める単純な反復学習アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-06-11T00:55:35Z)

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

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