論文の概要: On Computable Online Learning

• arxiv url: http://arxiv.org/abs/2302.04357v1
• Date: Wed, 8 Feb 2023 22:09:06 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-10 17:24:43.805336
• Title: On Computable Online Learning
• Title（参考訳）: 計算可能オンライン学習について
• Authors: Niki Hasrati and Shai Ben-David
• Abstract要約: 我々は、Littlestone次元がc-online学習の最適誤り境界をもはや特徴づけていないことを示す。 c-online 学習は不適切な CPAC 学習と同じくらい困難であることを示す。
• 参考スコア（独自算出の注目度）: 8.655294504286635
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We initiate a study of computable online (c-online) learning, which we analyze under varying requirements for "optimality" in terms of the mistake bound. Our main contribution is to give a necessary and sufficient condition for optimal c-online learning and show that the Littlestone dimension no longer characterizes the optimal mistake bound of c-online learning. Furthermore, we introduce anytime optimal (a-optimal) online learning, a more natural conceptualization of "optimality" and a generalization of Littlestone's Standard Optimal Algorithm. We show the existence of a computational separation between a-optimal and optimal online learning, proving that a-optimal online learning is computationally more difficult. Finally, we consider online learning with no requirements for optimality, and show, under a weaker notion of computability, that the finiteness of the Littlestone dimension no longer characterizes whether a class is c-online learnable with finite mistake bound. A potential avenue for strengthening this result is suggested by exploring the relationship between c-online and CPAC learning, where we show that c-online learning is as difficult as improper CPAC learning.
• Abstract（参考訳）: 計算可能なオンライン学習(c-online)の研究を開始し、ミスバウンドの観点から「最適性」の様々な要件の下で分析する。 我々の主な貢献は、最適なc-online学習に必要な条件を与え、Littlestone次元がc-online学習の最適誤り境界をもはや特徴づけていないことを示すことである。 さらに,anytime optimal (a-optimal) オンライン学習,"optimality"のより自然な概念化,littlestoneの標準最適アルゴリズムの一般化について紹介する。 本稿では,a-optimal と optimal online learning の計算分離の存在を示し,a-optimal online learning の計算がより困難であることを証明した。 最後に、最適性の要件のないオンライン学習を考察し、計算可能性の弱い概念の下で、リトルストーン次元の有限性は、クラスが有限な誤り境界を持つc-online学習可能かどうかをもはや特徴づけないことを示す。 c-online 学習と CPAC 学習の関係を探索し,c-online 学習が不適切な CPAC 学習と同じくらい困難であることが示唆された。

関連論文リスト

• Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems [4.9826534303287335]
  本稿では,2つの基本的な最適化設定のための学習強化アルゴリズムフレームワークを提案する。 コンケーブ目的のオンラインパッキングでは、アドバイスと最先端のオンラインアルゴリズムを切り替える、単純だが包括的な戦略を提示します。 我々のアルゴリズムは、アドバイスが正確であるとき、そしてアドバイスが間違っていても、最先端の古典的オンラインアルゴリズムと同等のパフォーマンスを維持しながら、不可能な結果を破ることを示した。
  論文  参考訳（メタデータ） (2024-11-13T04:27:25Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  後悔は$Thetaleft(mfrac12cdotfrac11-2-Tright)$で半直線的に成長するので、指数関数的に$Theta(sqrtm)$に収束する。 これらの調査結果は、限定的なオンライン学習と最適化の利点を浮き彫りにしている。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives [4.9826534303287335]
  本稿では,線形制約付きオンラインパッキング問題に対する単純な学習拡張アルゴリズムの導入と解析を行う。 さらに、このような単純なブラックボックス解が最適である場合に必要かつ十分な条件を理解するという問題を提起する。
  論文  参考訳（メタデータ） (2024-06-05T18:39:28Z)
• Discounted Adaptive Online Learning: Towards Better Regularization [5.5899168074961265]
  敵対的非定常環境におけるオンライン学習について検討する。 適応的アルゴリズム(例:Optimal)を提案し,適応的でないベースラインを広く改良する。 また、(Gibbs and Candes, 2021)スタイルのオンライン共形予測問題についても検討する。
  論文  参考訳（メタデータ） (2024-02-05T04:29:39Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。 まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。 オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
  論文  参考訳（メタデータ） (2023-07-07T21:39:25Z)
• Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization [66.35750142827898]
  本稿では,オンラインCO問題に対するポリシー最適化手法に関する最初の体系的研究について述べる。 我々は、オンラインCO問題は、潜在マルコフ決定過程(LMDP)として自然に定式化でき、自然政策勾配(NPG)に収束することを示す。 さらに,本理論はカリキュラム学習の利点を解説し,強力なサンプリングポリシーを見出すことができ,流通シフトを低減できることを示した。
  論文  参考訳（メタデータ） (2022-02-11T03:17:15Z)
• Adversaries in Online Learning Revisited: with applications in Robust Optimization and Adversarial training [55.30970087795483]
  オンライン学習における「敵対的」の概念を再考し、堅牢な最適化と敵対的なトレーニング問題を解決することに動機づけられます。 我々は,想像遊びを用いた多種多様な問題クラスに対する一般的なアプローチを確立する。
  論文  参考訳（メタデータ） (2021-01-27T14:23:06Z)
• Self-Directed Online Machine Learning for Topology Optimization [58.920693413667216]
  自己指向型オンライン学習最適化は、ディープニューラルネットワーク(DNN)と有限要素法(FEM)計算を統合している。 本アルゴリズムは, コンプライアンスの最小化, 流体構造最適化, 伝熱促進, トラス最適化の4種類の問題によって検証された。 その結果, 直接使用法と比較して計算時間を2～5桁削減し, 実験で検証した全ての最先端アルゴリズムより優れていた。
  論文  参考訳（メタデータ） (2020-02-04T20:00:28Z)

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

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