論文の概要: Most Neural Networks Are Almost Learnable
- arxiv url: http://arxiv.org/abs/2305.16508v3
- Date: Tue, 24 Oct 2023 19:36:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-26 20:43:01.236577
- Title: Most Neural Networks Are Almost Learnable
- Title（参考訳）: ほとんどのニューラルネットワークがほぼ学習可能
- Authors: Amit Daniely, Nathan Srebro, Gal Vardi
- Abstract要約: 固定された$epsilon>0$とdeep $i$に対して、深さ$i$のランダムなXavierネットワークを学習するポリ時間アルゴリズムが存在することを示す。
このアルゴリズムは時間とサンプルの複雑さが$(bard)mathrmpoly(epsilon-1)$であり、$bar d$はネットワークのサイズである。
シグモイドやReLU様の活性化の場合、境界は$(bard)mathrmpolylog(eps)に改善できる。
- 参考スコア（独自算出の注目度）: 52.40331776572531
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a PTAS for learning random constant-depth networks. We show that
for any fixed $\epsilon>0$ and depth $i$, there is a poly-time algorithm that
for any distribution on $\sqrt{d} \cdot \mathbb{S}^{d-1}$ learns random Xavier
networks of depth $i$, up to an additive error of $\epsilon$. The algorithm
runs in time and sample complexity of
$(\bar{d})^{\mathrm{poly}(\epsilon^{-1})}$, where $\bar d$ is the size of the
network. For some cases of sigmoid and ReLU-like activations the bound can be
improved to $(\bar{d})^{\mathrm{polylog}(\epsilon^{-1})}$, resulting in a
quasi-poly-time algorithm for learning constant depth random networks.
- Abstract（参考訳）: ランダムな定数深度ネットワークを学習するためのPTASを提案する。
固定された$\epsilon>0$とdeep $i$に対して、$\sqrt{d} \cdot \mathbb{S}^{d-1}$の任意の分布に対して、dep $i$のランダムなXavierネットワークを$\epsilon$の加算誤差まで学習するポリ時間アルゴリズムが存在することを示す。
このアルゴリズムは(\bar{d})^{\mathrm{poly}(\epsilon^{-1})}$の時間とサンプルの複雑さで動作し、ここで$\bar d$はネットワークのサイズである。
Sigmoid や ReLU のような活性化の場合、境界は $(\bar{d})^{\mathrm{polylog}(\epsilon^{-1})}$ に改善され、定数深度ランダムネットワークを学習するための準ポリ時間アルゴリズムが生成される。
関連論文リスト
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models [39.33814194788341]
潜在変数モデル学習の課題について検討する。
このような応用により、暗黙のモーメント計算のための一般化されたアルゴリズムを開発した。
一般的なアルゴリズムを利用して, 以下のモデルに対する初等学習者を得る。
論文 参考訳（メタデータ） (2024-11-23T23:13:24Z) - Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians [7.04316974339151]
本研究では,サンプルが未知の集合に落下した場合にのみ,分布パラメータの推定を行う。
我々は,PAC学習から,正・負のサンプルによるPAC学習まで,独立したツールを開発する。
論文 参考訳（メタデータ） (2024-10-02T15:21:07Z) - 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) - A faster and simpler algorithm for learning shallow networks [10.595936992218856]
ラベル付き例から、$k$ReLUアクティベーションの線形結合を学習する、よく研究された問題を再考する。
ここでは、アルゴリズムのよりシンプルなワンステージバージョンが十分であることを示し、そのランタイムは、わずか$(d/varepsilon)O(k2)$である。
論文 参考訳（メタデータ） (2023-07-24T03:04:10Z) - 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) - 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) - Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
2層ニューラルネットワークを学習する際の降下のダイナミクスについて考察する。
過度にパラメータ化された2層ニューラルネットワークは、タンジェントサンプルを用いて、ほとんどの地上で勾配損失を許容的に学習できることを示す。
論文 参考訳（メタデータ） (2020-07-09T07:09:28Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。