論文の概要: On the Power of Differentiable Learning versus PAC and SQ Learning

• arxiv url: http://arxiv.org/abs/2108.04190v1
• Date: Mon, 9 Aug 2021 17:25:06 GMT
• ステータス: 処理完了
• システム内更新日: 2021-08-10 16:13:05.932165
• Title: On the Power of Differentiable Learning versus PAC and SQ Learning
• Title（参考訳）: PACとSQ学習に対する微分学習の力について
• Authors: Emmanuel Abbe, Pritish Kamath, Eran Malach, Colin Sandon, Nathan Srebro
• Abstract要約: 本研究では,ミニバッチ勾配降下(SGD)による人口減少の学習力と,実証的損失のバッチ・グラディエント・Descent(GD)について検討した。 SGDとGDは、常に統計的クエリ(SQ)で学習をシミュレートできるが、それを超える能力は勾配計算の精度$rho$に依存する。
• 参考スコア（独自算出の注目度）: 46.161371858592666
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the power of learning via mini-batch stochastic gradient descent (SGD) on the population loss, and batch Gradient Descent (GD) on the empirical loss, of a differentiable model or neural network, and ask what learning problems can be learnt using these paradigms. We show that SGD and GD can always simulate learning with statistical queries (SQ), but their ability to go beyond that depends on the precision $\rho$ of the gradient calculations relative to the minibatch size $b$ (for SGD) and sample size $m$ (for GD). With fine enough precision relative to minibatch size, namely when $b \rho$ is small enough, SGD can go beyond SQ learning and simulate any sample-based learning algorithm and thus its learning power is equivalent to that of PAC learning; this extends prior work that achieved this result for $b=1$. Similarly, with fine enough precision relative to the sample size $m$, GD can also simulate any sample-based learning algorithm based on $m$ samples. In particular, with polynomially many bits of precision (i.e. when $\rho$ is exponentially small), SGD and GD can both simulate PAC learning regardless of the mini-batch size. On the other hand, when $b \rho^2$ is large enough, the power of SGD is equivalent to that of SQ learning.
• Abstract（参考訳）: 我々は,小バッチ確率勾配勾配降下(SGD)による学習が人口減少に与える影響と,モデルやニューラルネットワークの実証的損失に関するバッチ勾配降下(GD)について検討し,これらのパラダイムを用いてどのような学習問題を学べるかを問う。 SGDとGDは、常に統計的クエリ(SQ)で学習をシミュレートできるが、それを超える能力は、ミニバッチサイズ$b$(SGDの場合)とサンプルサイズ$m$(GDの場合)に対する勾配計算の精度$\rho$(GDの場合)に依存する。 例えば$b \rho$が十分小さい場合、SGDはSQ学習を超えてサンプルベースの学習アルゴリズムをシミュレートできるため、その学習能力はPAC学習と同等である。 同様に、サンプルサイズ$m$に対して十分な精度で、サンプルベースの学習アルゴリズムを$m$サンプルに基づいてシミュレートすることもできる。 特に、多項式的に多くの精度(すなわち)を持つ。 $\rho$が指数関数的に小さい場合、SGDとGDはどちらもミニバッチサイズに関係なくPAC学習をシミュレートできる。 一方、$b \rho^2$ が十分大きい場合、SGD のパワーは SQ 学習と同等である。

関連論文リスト

• Online Learning and Information Exponents: On The Importance of Batch size, and Time/Complexity Tradeoffs [24.305423716384272]
  我々は,1パス勾配勾配(SGD)を有する2層ニューラルネットワークの繰り返し時間に対するバッチサイズの影響について検討した。 大規模なバッチで勾配更新を行うことで、サンプル全体の複雑さを変えることなく、トレーニング時間を最小化できることが示される。 低次元常微分方程式(ODE)のシステムにより、トレーニングの進捗を追跡できることを示す。
  論文  参考訳（メタデータ） (2024-06-04T09:44:49Z)
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge [0.704590071265998]
  オンラインQ-ラーニング手法のサンプル複雑性について,動的知識が利用可能であったり,効率的に学習できたりした場合に検討する。 我々は,$f$の完全知識の下で,$tildemathcalO(textPoly(H)sqrtSAT)$ regretを達成する楽観的なQ-ラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-19T19:53:58Z)
• Smoothing the Landscape Boosts the Signal for SGD: Optimal Sample Complexity for Learning Single Index Models [43.83997656986799]
  1つのインデックスモデル $sigma(wstar cdot x)$ を、$d$次元の等方的ガウス分布に関して学習するタスクに焦点を当てる。 スムーズな損失のオンラインSGDは、$n gtrsim dkstar/2$サンプルで$wstar$を学習する。
  論文  参考訳（メタデータ） (2023-05-18T01:10:11Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• On the Power of Multitask Representation Learning in Linear MDP [61.58929164172968]
  本稿では,線形マルコフ決定過程(MDP)におけるマルチタスク表現学習の統計的メリットについて分析する。 簡単な最小二乗アルゴリズムが $tildeO(H2sqrtfrackappa MathcalC(Phi)2 kappa dNT+frackappa dn) というポリシーを学ぶことを証明した。
  論文  参考訳（メタデータ） (2021-06-15T11:21:06Z)
• Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model [3.749193647980305]
  本稿では,一連の状態対応機能を有するマルコフ決定プロセス(MDP)について考察する。 モデルに基づくアプローチ(resp.$Q-learning)が、高い確率で$varepsilon$-Optimalポリシーを確実に学習することを示す。
  論文  参考訳（メタデータ） (2021-05-28T17:49:39Z)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。 計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
  論文  参考訳（メタデータ） (2021-02-12T14:22:05Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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