論文の概要: Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning

• arxiv url: http://arxiv.org/abs/2506.00135v1
• Date: Fri, 30 May 2025 18:11:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 01:42:09.154629
• Title: Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
• Title（参考訳）: オンライン学習とトランスダクティブオンライン学習における誤りとEMM Oracleコールのトレードオフ
• Authors: Idan Attias, Steve Hanneke, Arvind Ramaswami,
• Abstract要約: 学習者が経験的リスク最小化(Empirical Risk Minimization, ERM)や弱一貫性オラクルによってのみ概念クラスと対話する場合, オンライン学習とトランスダクティブオンライン学習を学習する。
• 参考スコア（独自算出の注目度）: 17.389446817000945
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online and transductive online learning when the learner interacts with the concept class only via Empirical Risk Minimization (ERM) or weak consistency oracles on arbitrary instance subsets. This contrasts with standard online models, where the learner knows the entire class. The ERM oracle returns a hypothesis minimizing loss on a given subset, while the weak consistency oracle returns a binary signal indicating whether the subset is realizable by some concept. The learner is evaluated by the number of mistakes and oracle calls. In the standard online setting with ERM access, we prove tight lower bounds in both realizable and agnostic cases: $\Omega(2^{d_{VC}})$ mistakes and $\Omega(\sqrt{T 2^{d_{LD}}})$ regret, where $T$ is the number of timesteps and $d_{LD}$ is the Littlestone dimension. We further show that existing online learning results with ERM access carry over to the weak consistency setting, incurring an additional $O(T)$ in oracle calls. We then consider the transductive online model, where the instance sequence is known but labels are revealed sequentially. For general Littlestone classes, we show that optimal realizable and agnostic mistake bounds can be achieved using $O(T^{d_{VC}+1})$ weak consistency oracle calls. On the negative side, we show that limiting the learner to $\Omega(T)$ weak consistency queries is necessary for transductive online learnability, and that restricting the learner to $\Omega(T)$ ERM queries is necessary to avoid exponential dependence on the Littlestone dimension. Finally, for certain concept classes, we reduce oracle calls via randomized algorithms while maintaining similar mistake bounds. In particular, for Thresholds on an unknown ordering, $O(\log T)$ ERM queries suffice; for $k$-Intervals, $O(T^3 2^{2k})$ weak consistency queries suffice.
• Abstract（参考訳）: 我々は,学習者が経験的リスク最小化(Empirical Risk Minimization,ERM)や,任意のインスタンスサブセット上での弱一貫性オラクルを通じてのみ,概念クラスと対話する場合に,オンライン学習とトランスダクティブオンライン学習を学習する。 これは、学習者がクラス全体を知っている標準的なオンラインモデルとは対照的である。 ERMオラクルは与えられた部分集合の損失を最小限に抑える仮説を返し、弱い一貫性のオラクルは部分集合がある概念によって実現可能であるかどうかを示すバイナリ信号を返す。 学習者は誤りの数や宣誓供述書の呼び出し数によって評価される。 ERM アクセスを伴う標準的なオンライン設定では、実現可能かつ非依存なケースにおいて、厳密な下限を証明している: $\Omega(2^{d_{VC}})$ミスと $\Omega(\sqrt{T 2^{d_{LD}}})$残念なことに、$T$ はタイムステップの数であり、$d_{LD}$ はリトルストーン次元である。 さらに、ERMアクセスによる既存のオンライン学習結果が、O(T)$のオーラルコールを付加して、弱い一貫性設定へと続くことを示す。 次に、インスタンスシーケンスが知られているが、ラベルが順次明らかにされる、トランスダクティブオンラインモデルについて考察する。 一般のLittlestoneクラスに対して、最適実現可能かつ非依存的な誤り境界は、$O(T^{d_{VC}+1})$弱整合オラクル呼び出しによって達成できることを示す。 負の面では、学習者を$\Omega(T)$弱一貫性クエリに制限することは、トランスダクティブオンライン学習に必要であり、学習者を$\Omega(T)$ERMクエリに制限することは、リトルストーン次元への指数的依存を避けるために必要であることを示す。 最後に、ある概念クラスに対して、類似の誤り境界を維持しながら、ランダム化アルゴリズムによるオラクル呼び出しを減らす。 特に、未知の順序に関するThresholdsの場合、$O(\log T)$ ERM query suffice; for $k$-Intervals, $O(T^3 2^{2k})$ weak consistency query suffice。

関連論文リスト

• Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning [28.184175745050474]
  本稿では,教師付き学習オラクルの選択が強化学習アルゴリズムの計算複雑性に与える影響について検討する。 まず、標準的なエピソード・アクセス・モデルにおいて、2コンテキスト回帰を最小のオラクルとみなす。 第二に、より強いリセットアクセスモデルにおいて、一文回帰を最小に近いオラクルとみなす。 第3に、我々はLow-Rank MDPに焦点を絞り、Block MDP設定の類似のオラクルが不十分であることを示す暗号的証拠を与えます。
  論文  参考訳（メタデータ） (2025-02-12T18:47:13Z)
• Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
  乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。 結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
  論文  参考訳（メタデータ） (2024-11-04T00:39:52Z)
• Oracle-Efficient Hybrid Online Learning with Unknown Distribution [16.73555330791045]
  有限VCクラスに対して$tildeO(Tfrac34)$,$tildeO(Tfracp+1p+2)$に対して$alpha$fat-shattering dimensionを持つクラスに対して$tildeO(Tfracp+1p+2)$という,計算効率のよいオンライン予測器が存在することを示す。 すると、結果が$K$変更で分布をシフトするシナリオにまで拡張され、$tildeO(Tfrac45Kfrac15)が返り咲く。
  論文  参考訳（メタデータ） (2024-01-27T22:45:02Z)
• Simple online learning with consistent oracle [55.43220407902113]
  オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
  論文  参考訳（メタデータ） (2023-08-15T21:50:40Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries [29.598518028635716]
  オンライン学習の最悪のケース分析を超越した,オラクル効率のアルゴリズムについて検討する。 このスムーズな分析設定のために,本研究は,スムーズな相手を持つオンライン学習のための最初のオラクル効率のアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2022-02-17T09:49:40Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  オンライン学習モデルにおいて、予測者がインスタンスの分類を控える可能性のある選択的分類について検討する。 私たちが考慮している設定の健全な2つの側面は、データが不可避である可能性があるため、データは不可避である可能性があるということです。 smash$tildeO(T1-mu)$ over abstention against Adaptive adversaries. smash$tildeO(T1-mu)$ incurring smash$tildeO(T1-mu)$ over abstention。
  論文  参考訳（メタデータ） (2021-10-27T08:00:53Z)
• Online Continual Adaptation with Active Self-Training [69.5815645379945]
  本研究では,ラベルなしサンプルと限定ラベルのアクティブクエリの両方を用いて,学習者が変化に継続的に適応することを目的としたオンライン環境を提案する。 Online Self-Adaptive Mirror Descent (OSAMD)は、未ラベルのデータからオンラインの自己学習を可能にするオンライン教師学生構造を採用している。 我々は,OSAMDが実世界とシミュレーションデータの両方に限定されたラベルを持つ環境変化下で,好意的な後悔を達成していることを示す。
  論文  参考訳（メタデータ） (2021-06-11T17:51:25Z)

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

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