論文の概要: Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
- arxiv url: http://arxiv.org/abs/2605.07155v1
- Date: Fri, 08 May 2026 02:41:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-11 19:43:38.756475
- Title: Regret-Oracle Complexity Tradeoffs in Agnostic Online Learning
- Title（参考訳）: アグノスティックオンライン学習におけるレグレト・オラクルの複雑さのトレードオフ
- Authors: Idan Attias, Steve Hanneke, Arvind Ramaswami,
- Abstract要約: 従来のオンライン学習は、LittlestoneのStandard Optimal Algorithm(SOA)をベースラーナーとして利用して、実現可能な設定に還元することで、古典的に解決される。
私たちはSOAを、オフラインの実証的なリスク最小化のオラクルを通じてのみ概念クラスにアクセスする、実現可能なベースラーナーに置き換えます。
提案アルゴリズムは,クエリの総複雑性を$O(Td_mathrmVC+1)$に減らし,ほぼ最適の後悔を完全保存することを示した。
- 参考スコア（独自算出の注目度）: 37.15283418677639
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Agnostic online learning is classically solved via a reduction to the realizable setting, utilizing Littlestone's Standard Optimal Algorithm (SOA) as a base learner. However, the SOA is computationally intractable to execute even for a single round. To overcome this barrier, recent work in oracle-efficient online learning replaces the SOA with a realizable base learner that accesses the concept class exclusively through an offline empirical risk minimization (ERM) oracle. While such agnostic learners achieve near-optimal expected regret, they suffer from a doubly-exponential oracle complexity of $O\big(T^{2^{O(d_\mathrm{LD})}}\big)$, where $d_\mathrm{LD}$ is the Littlestone dimension and $T$ is the number of rounds. In this work, we significantly improve this oracle complexity while relying on an even weaker primitive: a weak-consistency oracle, which merely decides whether a given labeled dataset is realizable. At the core of our approach is an adaptive and dynamic agnostic-to-realizable reduction that actively prunes non-realizable label sequences on the fly. By using the VC dimension ($d_\mathrm{VC}$) to bound the number of dynamically maintained active paths, our algorithm reduces the total query complexity down to $O(T^{d_\mathrm{VC}+1})$ while perfectly preserving near-optimal expected regret. Crucially, this dynamic pruning also yields a memory reduction over the standard reduction. Furthermore, we formally quantify the regret--oracle complexity tradeoff, providing upper bounds that smoothly interpolate between restricted query budgets and attainable expected regret. We complement these with lower bounds proving that any learner restricted to $Q = o(\sqrt{T})$ queries must suffer an expected regret of $Ω(T/Q)$.
- Abstract（参考訳）: 従来のオンライン学習は、LittlestoneのStandard Optimal Algorithm(SOA)をベースラーナーとして利用して、実現可能な設定に還元することで、古典的に解決される。
しかし、SOAは1ラウンドでも実行でき、計算的に難解です。
この障壁を克服するために、近年のオラクル効率のよいオンライン学習における作業は、オフラインの経験的リスク最小化(ERM)オラクルを通じてのみコンセプトクラスにアクセスする、実現可能なベースラーナーによってSOAを置き換える。
そのような非依存的な学習者は、ほぼ最適に期待された後悔を達成できるが、それらは$O\big(T^{2^{O(d_\mathrm{LD})}}\big)$の二重排他的オラクル複雑性に悩まされる。
この研究では、より弱いプリミティブ、すなわち、ラベル付きデータセットが実現可能であるかどうかを単に決定する弱い一貫性のオラクルに依存しながら、このオラクルの複雑さを著しく改善する。
このアプローチのコアとなるのは、適応的で動的に不可知-実現可能な還元であり、これは、実現不可能なラベルシーケンスをオンザフライで積極的に引き起こす。
VC次元(d_\mathrm{VC}$)を動的に維持されるアクティブパスの数に限定することにより、我々のアルゴリズムはクエリの総複雑性を$O(T^{d_\mathrm{VC}+1})$に減らし、ほぼ最適に予測される後悔を完全に保存する。
重要なことに、このダイナミックプルーニングは、標準のリダクションよりもメモリの削減をもたらす。
さらに、我々は、制限されたクエリ予算と予測可能な後悔を円滑に補間する上限を提供するため、後悔とおかしな複雑さのトレードオフを正式に定量化します。
我々はこれらを下限で補完し、学習者が$Q = o(\sqrt{T})$クエリに制限された場合、$Ω(T/Q)$を期待して後悔しなければならないことを示す。
関連論文リスト
- Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation [21.36054923028733]
大規模環境での強化学習(RL)は、しばしば深刻な計算ボトルネックに悩まされる。
我々は,$O(Hloglog T)$呼び出しのみを必要としながら,最適な$tildeO(sqrtT)$後悔境界を達成する新しいアルゴリズムを提案する。
このオラクルの複雑さは状態空間と作用空間のサイズとは全く無関係である。
論文 参考訳（メタデータ） (2026-05-01T04:32:23Z) - Swap Regret Minimization Through Response-Based Approachability [66.39400409563976]
オンライン最適化において,スワップ後悔という異なる概念を最小化することの問題点を考察する。
我々は、一般凸集合に対して$O(d3/2 sqrtT)$リニアスワップ後悔を保証し、集合が中央対称であるときに$O(d sqrtT)$を保証し、より単純で効率的なアルゴリズムを開発する。
論文 参考訳（メタデータ） (2026-02-05T23:43:25Z) - Oracle-Efficient Combinatorial Semi-Bandits [38.838934613131535]
エージェントがベースアームのサブセットを選択し、個別のフィードバックを受け取るという半帯域問題について検討する。
我々は,厳格な後悔の保証を維持しつつ,オラクル呼び出しを大幅に削減するオラクル効率の高いフレームワークを提案する。
論文 参考訳（メタデータ） (2025-10-24T13:07:08Z) - Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning [17.389446817000945]
学習者が経験的リスク最小化(Empirical Risk Minimization, ERM)や弱一貫性オラクルによってのみ概念クラスと対話する場合, オンライン学習とトランスダクティブオンライン学習を学習する。
論文 参考訳（メタデータ） (2025-05-30T18:11:58Z) - 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) - Simple online learning with consistent oracle [55.43220407902113]
オンライン学習は、学習アルゴリズムが、どの時点でも、今まで見てきたすべての例に一致する関数をクラスから与えることができる、という、一貫性のあるオラクルを通じてのみクラスにアクセスすることができるモデルであると考えている。
論文 参考訳（メタデータ） (2023-08-15T21:50:40Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。