論文の概要: Adversarially Batched Online Learning
- arxiv url: http://arxiv.org/abs/2611.17500v1
- Date: Thu, 12 Nov 2026 20:45:51 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-16 18:43:16.257626
- Title: Adversarially Batched Online Learning
- Title(参考訳): 逆バッチ型オンライン学習
- Abstract要約: 本研究は,帯域幅,オンライン最適化,専門家の助言による予測,反対の帯域幅の4つの問題に対するモデルについて検討する。
バンドにとって、相対的バッチ成長に基づく普遍的な複雑性尺度を特定し、ギャップ依存的境界とギャップ非依存的後悔の両方を確立する。
残りの3例について、最適後悔はバッチ長列の2ノルムによって強く特徴づけられることを示す。
- 参考スコア(独自算出の注目度): 5.070542698701157
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce adversarially batched online learning, where the learner may update its decision rule only at a restricted set of time steps. Equivalently, the time horizon is partitioned into batches, within which the learner must use a fixed policy. We study this model for four canonical problems: stochastic bandits, online convex optimization, prediction with expert advice, and adversarial bandits. For stochastic bandits, we identify a universal complexity measure based on relative batch growth and establish both gap-dependent and gap-independent regret bounds. We show that the multiplicative penalty relative to the standard gap-dependent complexity can grow superlinearly in batch hardness. For the remaining three, we show that the optimal regret is tightly characterized by the 2-norm of the batch-length sequence. The upper bound is achieved by a batch-oblivious learner who does not know the batch structure, via a generic adaptive doubling trick tailored to this complexity measure. In contrast, the lower bound holds even for batch-aware learners.
- Abstract(参考訳): 逆バッチオンライン学習を導入し、学習者は制限された時間ステップでのみ決定ルールを更新できる。
同様に、時間水平線はバッチに分割され、そこでは学習者が一定のポリシーを使わなければならない。
このモデルは,確率的包帯,オンライン凸最適化,専門家の助言による予測,および敵の包帯の4つの正準問題に対して検討する。
確率的包帯について、相対的バッチ成長に基づく普遍的複雑性尺度を特定し、ギャップ依存的およびギャップ非依存的後悔境界を確立する。
本稿では,標準的なギャップ依存複雑性に対する乗法的ペナルティが,バッチ硬度において超直線的に増加することを示す。
残りの3例について、最適後悔はバッチ長列の2ノルムによって強く特徴づけられることを示す。
上限は、バッチ構造を知らないバッチ公開学習者によって達成される。
対照的に、下位境界はバッチ対応の学習者でさえ保持する。
関連論文リスト
- Online Learning with Gradient-Variation Interval Regret [54.59204826681113]
そこで本研究では,勾配変動を伴う時間間隔のリフレッシュなスケーリングを実現するオンライン学習アルゴリズムを提案する。
提案手法では, よりシンプルで効率的な2層オンラインアンサンブル構造を用いて, 高い理論的保証を実現する。
論文 参考訳(メタデータ) (2026-06-02T16:16:45Z) - Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。
我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
論文 参考訳(メタデータ) (2023-07-05T13:52:10Z) - Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [6.1866042321432175]
我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。
完全i.d.の場合、我々の後悔の限界は加速の結果から期待される速度と一致し、オンラインからバッチへの変換によって最適に加速された速度を回復する。
論文 参考訳(メタデータ) (2023-03-06T16:41:57Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-28T08:25:26Z) - Between Stochastic and Adversarial Online Convex Optimization: Improved
Regret Bounds via Smoothness [2.628557920905129]
我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。
この目的を達成するために、損失系列に関連する2つの重要な量を導入し、累積分散と対角変動と呼ぶ。
完全な i.d. の場合、我々の境界は加速の結果から期待される速度と一致し、完全に反対の場合、ミニマックスの後悔と一致するように優雅に劣化する。
論文 参考訳(メタデータ) (2022-02-15T16:39:33Z) - Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳(メタデータ) (2022-02-09T19:22:34Z) - Minimax Optimal Quantile and Semi-Adversarial Regret via
Root-Logarithmic Regularizers [31.102181563065844]
量子的(そしてより一般的には、KL)後悔は、最高の個人専門家と競争する目標を緩和し、敵対的なデータに関して、ほとんどの専門家と競争するだけである。
最近では、半対人パラダイム(Bilodeau、Negrea、Roy 2020)は、完全に対人的でも対人的でもないデータを考えることによって、対人的オンライン学習の代替緩和を提供する。
我々は、FTRLと別個のルート対数正規化器を併用したFTRLを用いて、両方のパラダイムにおいて最小限の後悔を達成し、どちらも正規Hedgeの変種と解釈できる。
論文 参考訳(メタデータ) (2021-10-27T22:38:52Z) - Instance-Dependent Complexity of Contextual Bandits and Reinforcement
Learning: A Disagreement-Based Perspective [104.67295710363679]
古典的なマルチアームバンディット問題において、インスタンス依存アルゴリズムは、ベストとセカンドベストのアーム間のギャップで「容易」な問題のパフォーマンスを向上させる。
我々は、インスタンス依存の後悔境界を得るのに十分かつ必要である複雑性尺度のファミリーを導入する。
次に、可能な限りギャップに適応する新しいオラクル効率アルゴリズムを導入し、最悪の場合にはミニマックスレートを得る。
論文 参考訳(メタデータ) (2020-10-07T01:33:06Z) - Sequential Batch Learning in Finite-Action Linear Contextual Bandits [40.01661188919779]
有限作用集合を持つ線形文脈帯域における逐次バッチ学習問題について検討する。
この問題は、実用アプリケーションにおいて、多くのパーソナライズされたシーケンシャルな意思決定問題のよりきめ細かい定式化を提供する。
論文 参考訳(メタデータ) (2020-04-14T06:47:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。