論文の概要: Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials

• arxiv url: http://arxiv.org/abs/2307.12840v2
• Date: Tue, 25 Jul 2023 17:25:03 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-26 19:41:41.467634
• Title: Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials
• Title（参考訳）: シュール多項式を用いた1Hidden-Layer ReLUネットワークの学習
• Authors: Ilias Diakonikolas and Daniel M. Kane
• Abstract要約: 正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
• 参考スコア（独自算出の注目度）: 50.90125395570797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $\mathbb{R}^d$ with respect to the square loss. Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/\epsilon)^{O(k)}$, where $\epsilon>0$ is the target accuracy. Prior work had given an algorithm for this problem with complexity $(dk/\epsilon)^{h(k)}$, where the function $h(k)$ scales super-polynomially in $k$. Interestingly, the complexity of our algorithm is near-optimal within the class of Correlational Statistical Query algorithms. At a high-level, our algorithm uses tensor decomposition to identify a subspace such that all the $O(k)$-order moments are small in the orthogonal directions. Its analysis makes essential use of the theory of Schur polynomials to show that the higher-moment error tensors are small given that the lower-order ones are.
• Abstract（参考訳）: 正方形損失に関して、標準ガウス分布の$\mathbb{R}^d$における$k$ReLUアクティベーションの線形結合をPAC学習する問題について検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/\epsilon)^{O(k)}$,$\epsilon>0$を目標精度とする効率的なアルゴリズムである。 以前の研究では、複雑性 $(dk/\epsilon)^{h(k)}$ というアルゴリズムが与えられたが、ここでは関数 $h(k)$ は超多項的に $k$ でスケールする。 興味深いことに、我々のアルゴリズムの複雑さは相関統計クエリアルゴリズムのクラス内でほぼ最適である。 高レベルでは、我々のアルゴリズムはテンソル分解を用いて、すべての$O(k)$-次モーメントが直交方向に小さい部分空間を識別する。 その解析はシューア多項式の理論を本質的に利用し、下階のテンソルを仮定すると、高モーメント誤差テンソルは小さいことを示す。

関連論文リスト

• Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
  潜在変数モデル学習の課題について検討する。 このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。 一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
  論文  参考訳（メタデータ） (2024-11-23T23:13:24Z)
• 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)
• Near-Optimal Bounds for Learning Gaussian Halfspaces with Random Classification Noise [50.64137465792738]
  この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。 我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
  論文  参考訳（メタデータ） (2023-07-13T18:59:28Z)
• 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)
• Robust Sparse Mean Estimation via Sum of Squares [42.526664955704746]
  本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。 我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
  論文  参考訳（メタデータ） (2022-06-07T16:49:54Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。 構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
  論文  参考訳（メタデータ） (2020-12-14T18:14:08Z)
• Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
  ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
  論文  参考訳（メタデータ） (2020-06-22T17:53:54Z)

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

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