論文の概要: 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 Effective Number of Linear Regions in Shallow Univariate ReLU Networks: Convergence Guarantees and Implicit Bias [50.84569563188485]
  我々は、ラベルが$r$のニューロンを持つターゲットネットワークの符号によって決定されるとき、勾配流が方向収束することを示す。 我々の結果は、標本サイズによらず、幅が$tildemathcalO(r)$である、緩やかなオーバーパラメータ化をすでに維持しているかもしれない。
  論文  参考訳（メタデータ） (2022-05-18T16:57:10Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions [93.18238573921629]
  GAN(Generative Adversarial Network)は、高複雑で実世界の分布を学習する上で最も成功したネットワークの一つである。 本稿では,GANが実際の分布画像に対して階層的に効率的に学習する方法について述べる。
  論文  参考訳（メタデータ） (2021-06-04T17:33:29Z)
• Conditional physics informed neural networks [85.48030573849712]
  固有値問題のクラス解を推定するための条件付きPINN(物理情報ニューラルネットワーク)を紹介します。 一つのディープニューラルネットワークが、問題全体に対する偏微分方程式の解を学習できることが示される。
  論文  参考訳（メタデータ） (2021-04-06T18:29:14Z)
• Self-Regularity of Non-Negative Output Weights for Overparameterized Two-Layer Neural Networks [16.64116123743938]
  我々は、Sigmoid, rectified linear unit (ReLU) を用いた2層ニューラルネットワークの探索問題を考える。 そして、その境界を利用して、Emphfat-shattering dimensionを通じてそのようなネットワークの保証を確立する。 特に、我々の境界はサンプルの複雑さも良い(低次数$$d$のポリノミアル)。
  論文  参考訳（メタデータ） (2021-03-02T17:36:03Z)
• No-Regret Reinforcement Learning with Heavy-Tailed Rewards [11.715649997214125]
  重み付き報酬の学習の難しさが遷移確率の学習の難しさを左右することを示した。 我々のアルゴリズムは自然に深層強化学習アプリケーションに一般化する。 全てのアルゴリズムは、合成MDPと標準RLベンチマークの両方でベースラインを上回ります。
  論文  参考訳（メタデータ） (2021-02-25T10:25:57Z)
• Pareto GAN: Extending the Representational Power of GANs to Heavy-Tailed Distributions [6.356866333887868]
  既存のGANアーキテクチャは,重み付き分布の挙動にマッチする作業が不十分であることを示す。 我々は, 極値理論とニューラルネットワークの機能的性質を用いて, 敵対的特徴の挙動に適合する分布を学習する。
  論文  参考訳（メタデータ） (2021-01-22T14:06:02Z)
• Vector-output ReLU Neural Network Problems are Copositive Programs: Convex Analysis of Two Layer Networks and Polynomial-time Algorithms [29.975118690758126]
  2層ベクトル無限ReLUニューラルネットワークトレーニング問題の半出力グローバル双対について述べる。 特定の問題のクラスに対して正確であることが保証されるソリューションを提供する。
  論文  参考訳（メタデータ） (2020-12-24T17:03:30Z)

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

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