論文の概要: Optimal Learners for Realizable Regression: PAC Learning and Online Learning

• arxiv url: http://arxiv.org/abs/2307.03848v3
• Date: Wed, 02 Oct 2024 19:31:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-04 17:53:32.836473
• Title: Optimal Learners for Realizable Regression: PAC Learning and Online Learning
• Title（参考訳）: 実現可能な回帰のための最適学習者:PAC学習とオンライン学習
• Authors: Idan Attias, Steve Hanneke, Alkis Kalavasis, Amin Karbasi, Grigoris Velegkas,
• Abstract要約: 本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。 まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。 オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
• 参考スコア（独自算出の注目度）: 52.37726841759983
• License:
• Abstract: In this work, we aim to characterize the statistical complexity of realizable regression both in the PAC learning setting and the online learning setting. Previous work had established the sufficiency of finiteness of the fat shattering dimension for PAC learnability and the necessity of finiteness of the scaled Natarajan dimension, but little progress had been made towards a more complete characterization since the work of Simon (SICOMP '97). To this end, we first introduce a minimax instance optimal learner for realizable regression and propose a novel dimension that both qualitatively and quantitatively characterizes which classes of real-valued predictors are learnable. We then identify a combinatorial dimension related to the Graph dimension that characterizes ERM learnability in the realizable setting. Finally, we establish a necessary condition for learnability based on a combinatorial dimension related to the DS dimension, and conjecture that it may also be sufficient in this context. Additionally, in the context of online learning we provide a dimension that characterizes the minimax instance optimal cumulative loss up to a constant factor and design an optimal online learner for realizable regression, thus resolving an open question raised by Daskalakis and Golowich in STOC '22.
• Abstract（参考訳）: 本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。 従来の研究は、PAC学習性のための脂肪破砕次元の有限性の十分性と、スケールしたナタラジャン次元の有限性の必要性を確立していたが、Simon (SICOMP '97) の業績から、より完全な特徴付けに向けての進展はほとんどなかった。 この目的のために,まず,最小値のインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを定性的かつ定量的に特徴付ける新しい次元を提案する。 次に,実測可能な環境下でのEMM学習性を特徴付けるグラフ次元に関連する組合せ次元を同定する。 最後に、DS次元に関連する組合せ次元に基づいて学習可能性の必要条件を確立し、この文脈で十分かもしれないと推測する。 さらに、オンライン学習の文脈では、最小値インスタンスの最適累積損失を一定要素まで特徴付け、最適オンライン学習者を再現可能な回帰のために設計し、STOC '22でダスカラキスとゴロヴィチが提起したオープンな質問を解消する次元を提供する。

関連論文リスト

• A Combinatorial Characterization of Supervised Online Learnability [20.291598040396302]
  本稿では,任意だが有界な損失関数に対する仮説クラスのオンライン学習可能性について検討する。 連続最小次元と呼ばれる新しいスケール感性次元を与え、オンライン学習可能性の厳密な定量的評価を与えることを示す。
  論文  参考訳（メタデータ） (2023-07-07T20:11:07Z)
• Towards a Better Theoretical Understanding of Independent Subnetwork Training [56.24689348875711]
  独立サブネットワークトレーニング(IST)の理論的考察 ISTは、上記の問題を解決するための、最近提案され、非常に効果的である。 圧縮通信を用いた分散手法など,ISTと代替手法の基本的な違いを同定する。
  論文  参考訳（メタデータ） (2023-06-28T18:14:22Z)
• Learning Capacity: A Measure of the Effective Dimensionality of a Model [18.48866194756127]
  モデルの有効次元の尺度である「学習能力」と呼ばれる量について検討する。 学習能力は、(a)テスト損失と相関し、典型的なデータセットでトレーニングされた多くのディープネットワークのパラメータのごく一部であるため、複雑さの有用な概念であることを示す。
  論文  参考訳（メタデータ） (2023-05-27T02:27:27Z)
• Learnability, Sample Complexity, and Hypothesis Class Complexity for Regression Models [10.66048003460524]
  この研究はPACの基礎に触発され、既存の回帰学習問題に動機付けられている。 提案手法はEpsilon-Confidence Aough Correct (epsilon CoAC)で示され、Kullback Leibler divergence(相対エントロピー)を利用する。 これにより、学習者は異なる複雑性順序の仮説クラスを比較でき、それらの中から最小のエプシロンを最適に選択できる。
  論文  参考訳（メタデータ） (2023-03-28T15:59:12Z)
• Offline Reinforcement Learning with Differentiable Function Approximation is Provably Efficient [65.08966446962845]
  歴史的データを用いて意思決定戦略を最適化することを目的としたオフライン強化学習は、現実の応用に広く適用されている。 微分関数クラス近似(DFA)を用いたオフライン強化学習の検討から一歩踏み出した。 最も重要なことは、悲観的な適合Q-ラーニングアルゴリズムを解析することにより、オフライン微分関数近似が有効であることを示すことである。
  論文  参考訳（メタデータ） (2022-10-03T07:59:42Z)
• Annealing Optimization for Progressive Learning with Stochastic Approximation [0.0]
  計算資源が限られているアプリケーションのニーズを満たすために設計された学習モデルを導入する。 我々は,オンラインな勾配近似アルゴリズムとして定式化されたオンラインプロトタイプベースの学習アルゴリズムを開発した。 学習モデルは、教師なし、教師なし、強化学習に使用される、解釈可能で、徐々に成長する競争的ニューラルネットワークモデルと見なすことができる。
  論文  参考訳（メタデータ） (2022-09-06T21:31:01Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism [65.46524775457928]
  オフライン強化学習は、オフライン/歴史的データを活用して、シーケンシャルな意思決定戦略を最適化しようとしている。 線形モデル表現を用いたオフライン強化学習の統計的限界について検討する。
  論文  参考訳（メタデータ） (2022-03-11T09:00:12Z)
• Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity [51.476337785345436]
  有限水平マルコフ決定過程の文脈におけるQ-ラーニングの悲観的変種について検討する。 ほぼ最適サンプル複雑性を実現するために,分散再現型悲観的Q-ラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-02-28T15:39:36Z)
• Towards a combinatorial characterization of bounded memory learning [21.031088723668486]
  我々は,境界記憶学習を特徴付ける次元を開発する。 候補解に対して上界と下界の両方を証明します。 我々は、我々の特徴がより広いパラメータの体系で成り立つと推測する。
  論文  参考訳（メタデータ） (2020-02-08T09:04:21Z)

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

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