論文の概要: Turing-Universal Learners with Optimal Scaling Laws

• arxiv url: http://arxiv.org/abs/2111.05321v1
• Date: Tue, 9 Nov 2021 18:44:35 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-10 14:47:19.435158
• Title: Turing-Universal Learners with Optimal Scaling Laws
• Title（参考訳）: 最適スケーリング法則を用いたチューリング・ユニバーサル学習者
• Authors: Preetum Nakkiran
• Abstract要約: 我々は,全ての学習アルゴリズムにおいて,最適な分布依存率を実現する「ユニバーサル学習者」アルゴリズムの存在を観察する。 構成そのものは、レヴィンの普遍探索の単純な拡張である(Levin, 1973)
• 参考スコア（独自算出の注目度）: 2.7485183218472016
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: For a given distribution, learning algorithm, and performance metric, the rate of convergence (or data-scaling law) is the asymptotic behavior of the algorithm's test performance as a function of number of train samples. Many learning methods in both theory and practice have power-law rates, i.e. performance scales as $n^{-\alpha}$ for some $\alpha > 0$. Moreover, both theoreticians and practitioners are concerned with improving the rates of their learning algorithms under settings of interest. We observe the existence of a "universal learner", which achieves the best possible distribution-dependent asymptotic rate among all learning algorithms within a specified runtime (e.g. $O(n^2)$), while incurring only polylogarithmic slowdown over this runtime. This algorithm is uniform, and does not depend on the distribution, and yet achieves best-possible rates for all distributions. The construction itself is a simple extension of Levin's universal search (Levin, 1973). And much like universal search, the universal learner is not at all practical, and is primarily of theoretical and philosophical interest.
• Abstract（参考訳）: 与えられた分布、学習アルゴリズム、およびパフォーマンスメトリックについて、収束率(またはデータスケーリング則)は、列車サンプルの数の関数としてのアルゴリズムのテスト性能の漸近的挙動である。 理論と実践の両方における多くの学習手法は、パワーローレート、すなわち、ある$\alpha > 0$に対して、n^{-\alpha}$としてのパフォーマンススケールを持つ。 さらに、理論家も実践者も、興味のある設定下での学習アルゴリズムの速度向上に関心を持っている。 特定ランタイム(例えば$O(n^2)$)内の全ての学習アルゴリズムにおいて、最適な分布依存漸近速度を達成するとともに、このランタイム上での多言語的スローダウンのみを発生させる「ユニバーサル学習者」の存在を観察する。 このアルゴリズムは均一であり、分布に依存しないが、全ての分布に対して最良の確率を達成する。 構成そのものは、レヴィンの普遍探索の単純な拡張である(levin, 1973)。 そして、普遍的な探索と同様に、普遍的な学習者は全く実践的ではなく、主に理論的、哲学的な関心事である。

関連論文リスト

• Achieving More with Less: A Tensor-Optimization-Powered Ensemble Method [53.170053108447455]
  アンサンブル学習(英: Ensemble learning)は、弱い学習者を利用して強力な学習者を生み出す方法である。 我々は、マージンの概念を活かした滑らかで凸な目的関数を設計し、強力な学習者がより差別的になるようにした。 そして、我々のアルゴリズムを、多数のデータセットの10倍の大きさのランダムな森林や他の古典的な手法と比較する。
  論文  参考訳（メタデータ） (2024-08-06T03:42:38Z)
• Efficient Discrepancy Testing for Learning with Distribution Shift [17.472049019016524]
  局所的な一致距離をテストするための証明可能なアルゴリズムの最初のセットを提供する。 結果は、最近導入されたTestable Learning with Distribution Shiftモデルにおいて、新しい効率的な学習アルゴリズムの幅広いセットを示唆している。
  論文  参考訳（メタデータ） (2024-06-13T17:51:10Z)
• A Competitive Algorithm for Agnostic Active Learning [5.4579367210379335]
  アクティブな学習のための最も一般的なアルゴリズムは、不一致係数と呼ばれるパラメータでその性能を表現する。 我々は、任意の二進仮説クラス$H$と分布$D_X$ over$X$に対して最適なアルゴリズムと競合するアルゴリズムを得る。 我々のアルゴリズムの$O(log |H|)$オーバーヘッドよりは、NPハードである。
  論文  参考訳（メタデータ） (2023-10-28T19:01:16Z)
• 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)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• A Boosting Approach to Reinforcement Learning [59.46285581748018]
  複雑度が状態数に依存しない意思決定プロセスにおける強化学習のための効率的なアルゴリズムについて検討する。 このような弱い学習手法の精度を向上させることができる効率的なアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-08-22T16:00:45Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• A Theory of Universal Learning [26.51949485387526]
  普遍的な学習の確率は3つしかないことを示す。 任意の概念クラスの学習曲線は指数的あるいは任意に遅い速度で減衰することを示す。
  論文  参考訳（メタデータ） (2020-11-09T15:10:32Z)
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension [124.7752517531109]
  一般値関数近似を用いた効率の良い強化学習アルゴリズムを確立する。 我々のアルゴリズムは、$d$が複雑性測度である場合、$widetildeO(mathrmpoly(dH)sqrtT)$の後悔の限界を達成することを示す。 我々の理論は線形値関数近似によるRLの最近の進歩を一般化し、環境モデルに対する明示的な仮定をしない。
  論文  参考訳（メタデータ） (2020-05-21T17:36:09Z)
• Complete Dictionary Learning via $\ell_p$-norm Maximization [10.82081111170268]
  完全な辞書学習問題に対する $ell_p$-norm (p>2,p in mathbbN$) アプローチの族について検討する。 これらの定式化のグローバルな最大化器は、ガウスノイズが存在する場合でも、高い確率で真の辞書に非常に近いことを示す。 実験により、$ell_p$ベースのアプローチは、従来のアプローチよりも高い計算効率とロバスト性を享受できることが示される。
  論文  参考訳（メタデータ） (2020-02-24T02:33:01Z)

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

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