論文の概要: Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks

• arxiv url: http://arxiv.org/abs/2006.12476v1
• Date: Mon, 22 Jun 2020 17:53:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-18 06:05:26.224317
• Title: Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks
• Title（参考訳）: PAC学習単層ReLUネットワークのためのアルゴリズムとSQ下界
• Authors: Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Nikos Zarifis
• Abstract要約: ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。 正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
• 参考スコア（独自算出の注目度）: 48.32532049640782
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of PAC learning one-hidden-layer ReLU networks with $k$ hidden units on $\mathbb{R}^d$ under Gaussian marginals in the presence of additive label noise. For the case of positive coefficients, we give the first polynomial-time algorithm for this learning problem for $k$ up to $\tilde{O}(\sqrt{\log d})$. Previously, no polynomial time algorithm was known, even for $k=3$. This answers an open question posed by~\cite{Kliv17}. Importantly, our algorithm does not require any assumptions about the rank of the weight matrix and its complexity is independent of its condition number. On the negative side, for the more general task of PAC learning one-hidden-layer ReLU networks with arbitrary real coefficients, we prove a Statistical Query lower bound of $d^{\Omega(k)}$. Thus, we provide a separation between the two classes in terms of efficient learnability. Our upper and lower bounds are general, extending to broader families of activation functions.
• Abstract（参考訳）: 我々は,加法ラベルノイズの存在下でのガウス限界の下で,$\mathbb{R}^d$で$k$の隠れ単位を持つ一層ReLUネットワークをPAC学習する問題について検討する。 正の係数の場合、この学習問題に対する最初の多項式時間アルゴリズムを$k$から$\tilde{O}(\sqrt{\log d})$に対して与える。 以前は多項式時間アルゴリズムは知られておらず、k=3$であった。 これは~\cite{Kliv17} で表される開問題に答える。 重要なことに、このアルゴリズムは重み行列の階数に関する仮定を一切必要とせず、その複雑性はその条件数に依存しない。 負の面では、任意の実係数を持つ一層ReLUネットワークをPACで学習するより一般的なタスクに対して、統計的クエリの下界が$d^{\Omega(k)}$であることを証明する。 そこで我々は,この2つのクラスを効率的な学習能力という観点から分離する。 我々の上界と下界は一般的であり、活性化関数のより広いファミリーに拡張されている。

関連論文リスト

• Agnostic Learning of Arbitrary ReLU Activation under Gaussian Marginals [10.850101961203752]
  正方形損失目標を持つガウスの辺縁部における任意のバイアスのReLU活性化(あるいはニューロン)を学習する問題を考察する。 我々の主な成果は時間統計クエリ(SQ)アルゴリズムであり、任意のバイアスに対して最初の定数係数近似を与える。 我々のアルゴリズムは、勾配降下に基づく既存のアルゴリズムから興味深い逸脱を示す。
  論文  参考訳（メタデータ） (2024-11-21T17:43:51Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Agnostically Learning Multi-index Models with Queries [54.290489524576756]
  本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。 クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
  論文  参考訳（メタデータ） (2023-12-27T15:50:47Z)
• A Doubly Robust Approach to Sparse Reinforcement Learning [19.68978899041642]
  エピソードスパークリニアマルコフ決定過程(SMDP)に対する新しい後悔アルゴリズムを提案する。 提案アルゴリズムは$tildeO(sigma-1_min s_star H sqrtN)$である。
  論文  参考訳（メタデータ） (2023-10-23T18:52:17Z)
• 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)
• 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)
• Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations [27.244958998196623]
  一般のReLUアクティベーションを用いた未知の深度2フィードフォワードニューラルネットワークを学習するための時間とサンプル効率のアルゴリズムを提案する。 特に、f(x) = amathsfTsigma(WmathsfTx+b)$, ここで$x$はガウス分布から引き出され、$sigma(t) := max(t,0)$はReLU活性化である。
  論文  参考訳（メタデータ） (2021-07-21T17:06:03Z)
• On Agnostic PAC Learning using $\mathcal{L}_2$-polynomial Regression and Fourier-based Algorithms [10.66048003460524]
  構造的性質を持つPAC学習問題を解析するためのプロキシとしてヒルベルト空間を用いたフレームワークを開発する。 0-1の損失を持つPAC学習はヒルベルト空間領域における最適化と同値であることを示す。
  論文  参考訳（メタデータ） (2021-02-11T21:28:55Z)
• 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)

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

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