論文の概要: Fast Rates for Nonparametric Online Learning: From Realizability to
Learning in Games
- arxiv url: http://arxiv.org/abs/2111.08911v1
- Date: Wed, 17 Nov 2021 05:24:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-18 14:15:20.415592
- Title: Fast Rates for Nonparametric Online Learning: From Realizability to
Learning in Games
- Title（参考訳）: 非パラメトリックオンライン学習の高速化 - ゲームにおける実現可能性から学習へ-
- Authors: Constantinos Daskalakis and Noah Golowich
- Abstract要約: 本稿では,仮説クラスの逐次的脂肪散乱次元の観点から,ほぼ最適誤差を導出する固有学習アルゴリズムを提案する。
この結果は、適切な学習者が準最適誤り境界を達成できるかどうかという疑問に答える。
実数値(回帰)設定では、最適誤り境界は不適切な学習者にさえ知られていなかった。
- 参考スコア（独自算出の注目度）: 36.969021834291745
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study fast rates of convergence in the setting of nonparametric online
regression, namely where regret is defined with respect to an arbitrary
function class which has bounded complexity. Our contributions are two-fold:
- In the realizable setting of nonparametric online regression with the
absolute loss, we propose a randomized proper learning algorithm which gets a
near-optimal mistake bound in terms of the sequential fat-shattering dimension
of the hypothesis class. In the setting of online classification with a class
of Littlestone dimension $d$, our bound reduces to $d \cdot {\rm poly} \log T$.
This result answers a question as to whether proper learners could achieve
near-optimal mistake bounds; previously, even for online classification, the
best known mistake bound was $\tilde O( \sqrt{dT})$. Further, for the
real-valued (regression) setting, the optimal mistake bound was not even known
for improper learners, prior to this work.
- Using the above result, we exhibit an independent learning algorithm for
general-sum binary games of Littlestone dimension $d$, for which each player
achieves regret $\tilde O(d^{3/4} \cdot T^{1/4})$. This result generalizes
analogous results of Syrgkanis et al. (2015) who showed that in finite games
the optimal regret can be accelerated from $O(\sqrt{T})$ in the adversarial
setting to $O(T^{1/4})$ in the game setting.
To establish the above results, we introduce several new techniques,
including: a hierarchical aggregation rule to achieve the optimal mistake bound
for real-valued classes, a multi-scale extension of the proper online
realizable learner of Hanneke et al. (2021), an approach to show that the
output of such nonparametric learning algorithms is stable, and a proof that
the minimax theorem holds in all online learnable games.
- Abstract（参考訳）: 非パラメトリックオンライン回帰の設定における収束の速さ、すなわち、複雑性が有界な任意の関数クラスに対して後悔が定義される場合について検討する。
絶対損失を伴う非パラメトリックオンライン回帰(nonparametric online regression)の実現可能設定において、我々は、仮説クラスの逐次的脂肪分散次元の観点で、ほぼ最適の誤りを生じさせる確率的固有学習アルゴリズムを提案する。
リトルストーン次元 $d$ のクラスを持つオンライン分類の設定において、我々の境界は $d \cdot {\rm poly} \log t$ となる。
この結果は、適切な学習者がほぼ最適の誤り境界を達成できるかどうかという疑問に答える。以前はオンライン分類においても、最もよく知られた誤り境界は$\tilde O( \sqrt{dT})$であった。
さらに、実数値(回帰)設定では、この作業に先立って、不適切な学習者には最適な誤り境界が知られていなかった。
以上の結果を用いて,Littlestone 次元$d$の汎用バイナリゲームに対して,各プレイヤーが後悔する$\tilde O(d^{3/4} \cdot T^{1/4})$に対して独立学習アルゴリズムを示す。
この結果は、Syrgkanis et al. (2015) の類似の結果を一般化し、有限ゲームにおいて最適な後悔は、対数設定で$O(\sqrt{T})$からゲーム設定で$O(T^{1/4})$に加速できることを示した。
上記の結果を確立するために,実数値クラスにバウンドする最適誤りを達成するための階層的集約ルール,hannekeらオンライン実現可能な学習者のマルチスケール拡張(2021年),非パラメトリック学習アルゴリズムの出力が安定であることを示すアプローチ,オンライン学習可能なすべてのゲームにおいてminimax定理が成立する証拠など,いくつかの新しい手法を導入する。
関連論文リスト
- Model Selection for Average Reward RL with Application to Utility Maximization in Repeated Games [1.9161424760743742]
平均報酬RL設定のためのオンラインモデル選択アルゴリズムを提案する。
モデル選択の追加コストは、モデルクラスの数である$M$でのみ線形にスケールすることを示す。
また,学習者の後悔度を低く抑えることで,$m*$への指数的依存が避けられないことを示す。
論文 参考訳（メタデータ） (2024-11-09T05:03:10Z) - Agnostic Smoothed Online Learning [5.167069404528051]
本稿では,$mu$の事前知識を必要とせずに,オンライン学習を円滑に行うためのサブ線形後悔を保証するアルゴリズムを提案する。
R-Coverは、次元$d$を持つ関数クラスに対して、適応的後悔$tilde O(sqrtdT/sigma)$を持つ。
論文 参考訳（メタデータ） (2024-10-07T15:25:21Z) - Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。
一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
論文 参考訳（メタデータ） (2024-06-10T23:23:52Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-02-09T19:22:34Z) - Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。
我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。
そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
論文 参考訳（メタデータ） (2021-12-06T08:27:54Z) - Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。
ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。
本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
論文 参考訳（メタデータ） (2021-06-06T19:08:53Z) - Localization, Convexity, and Star Aggregation [0.0]
オフセットラデマッハ複体は、正方形損失に対する鋭く線形依存的な上界を示すことが示されている。
統計的設定では、オフセット境界は一定の均一な凸性を満たす任意の損失に一般化可能であることを示す。
論文 参考訳（メタデータ） (2021-05-19T00:47:59Z) - Optimal Dynamic Regret in Exp-Concave Online Learning [28.62891856368132]
我々は、オンライン学習におけるZinkevich(2003)スタイルの動的後悔最小化の問題を検討する。
不適切な学習が許されるたびに、Strongly Adaptive のオンライン学習者は $tilde O(d3.5n1/3C_n2/3 vee dlog n)$ の動的後悔を達成する。
経路の長さ) 学習者が事前に知ることができない任意のコンパレータのシーケンス。
論文 参考訳（メタデータ） (2021-04-23T21:36:51Z) - Online Learning with Imperfect Hints [72.4277628722419]
オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。
我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
論文 参考訳（メタデータ） (2020-02-11T23:06:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。