論文の概要: From Local Pseudorandom Generators to Hardness of Learning
- arxiv url: http://arxiv.org/abs/2101.08303v1
- Date: Wed, 20 Jan 2021 20:07:47 GMT
- ステータス: 翻訳完了
- システム内更新日: 2021-03-22 01:33:23.547200
- Title: From Local Pseudorandom Generators to Hardness of Learning
- Title（参考訳）: 局所擬似乱数生成器から学習困難まで
- Authors: Amit Daniely and Gal Vardi
- Abstract要約: 局所擬似乱数発生器の存在に関する十分に研究された仮定の下で学習の硬度の結果を証明します。
結果は以下のとおりである: $omega(1)$ halfspaces の交点を学習するハードネス、$omega(1)$ 項を持つ dnf 公式、および $omega(1)$ 隠れニューロンを持つ relu ネットワーク。
- 参考スコア（独自算出の注目度）: 43.47952928399709
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove hardness-of-learning results under a well-studied assumption on the
existence of local pseudorandom generators. As we show, this assumption allows
us to surpass the current state of the art, and prove hardness of various basic
problems, with no hardness results to date.
Our results include: hardness of learning shallow ReLU neural networks under
the Gaussian distribution and other distributions; hardness of learning
intersections of $\omega(1)$ halfspaces, DNF formulas with $\omega(1)$ terms,
and ReLU networks with $\omega(1)$ hidden neurons; hardness of weakly learning
deterministic finite automata under the uniform distribution; hardness of
weakly learning depth-$3$ Boolean circuits under the uniform distribution, as
well as distribution-specific hardness results for learning DNF formulas and
intersections of halfspaces. We also establish lower bounds on the complexity
of learning intersections of a constant number of halfspaces, and ReLU networks
with a constant number of hidden neurons. Moreover, our results imply the
hardness of virtually all improper PAC-learning problems (both
distribution-free and distribution-specific) that were previously shown hard
under other assumptions.
- Abstract（参考訳）: 本研究では,ローカル擬似乱数生成器の存在を前提として,学習の難しさを実証する。
我々が示すように、この仮定は、現在の芸術の状態を超越し、様々な基本的な問題の困難さを証明し、今日までハードネスの結果は得られない。
Our results include: hardness of learning shallow ReLU neural networks under the Gaussian distribution and other distributions; hardness of learning intersections of $\omega(1)$ halfspaces, DNF formulas with $\omega(1)$ terms, and ReLU networks with $\omega(1)$ hidden neurons; hardness of weakly learning deterministic finite automata under the uniform distribution; hardness of weakly learning depth-$3$ Boolean circuits under the uniform distribution, as well as distribution-specific hardness results for learning DNF formulas and intersections of halfspaces.
また、一定の数のハーフスペースの学習交叉と、一定の数の隠れニューロンを持つReLUネットワークの複雑さの低い境界を確立する。
さらに,本研究の結果は,これまで他の仮定では困難であった,事実上不適切なPAC学習問題(分布自由と分布特化の両方)の難しさを示唆している。
関連論文リスト
- On the Hardness of Learning One Hidden Layer Neural Networks [14.341197440301576]
我々は、$mathbbRd$からの入力でReLUニューラルネットワークの隠れ層を学習する問題を考察する。
この学習問題は、ニューラルネットワークのサイズが$d$である場合でも、標準的な暗号的仮定の下では困難であることを示す。
論文 参考訳（メタデータ） (2024-10-04T14:48:13Z) - Hardness of Learning Neural Networks under the Manifold Hypothesis [3.2635082758250693]
多様体仮説は、高次元データが低次元多様体上または近辺にあると仮定する。
多様体仮説に基づく学習の難しさについて検討する。
データ多様体の体積に関する追加の仮定は、これらの基本的な制限を緩和することを示します。
論文 参考訳（メタデータ） (2024-06-03T15:50:32Z) - Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。
一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
論文 参考訳（メタデータ） (2023-05-28T19:40:46Z) - Computational Complexity of Learning Neural Networks: Smoothness and
Degeneracy [52.40331776572531]
ガウス入力分布下での学習深度3$ReLUネットワークはスムーズな解析フレームワークにおいても困難であることを示す。
この結果は, 局所擬似乱数発生器の存在についてよく研究されている。
論文 参考訳（メタデータ） (2023-02-15T02:00:26Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。
これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文 参考訳（メタデータ） (2022-10-22T19:07:26Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
この研究は、局所量子回路の出力分布の学習可能性に関する広範な評価を提供する。
ハイブリッド量子古典アルゴリズムを含む多種多様な学習アルゴリズムにおいて、深度$d=omega(log(n))$ Clifford回路に関連する生成的モデリング問題さえも困難であることを示す。
論文 参考訳（メタデータ） (2022-07-07T08:04:15Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - Forward Super-Resolution: How Can GANs Learn Hierarchical Generative
Models for Real-World Distributions [66.05472746340142]
生成ネットワーク(GAN)は、複雑で現実世界の分布を学習する上で最も成功したネットワークの一つである。
本稿では,GANが実写画像の分布を効率的に学習する方法について述べる。
論文 参考訳（メタデータ） (2021-06-04T17:33:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。