論文の概要: Online Prediction in Sub-linear Space
- arxiv url: http://arxiv.org/abs/2207.07974v1
- Date: Sat, 16 Jul 2022 16:15:39 GMT
- ステータス: 処理完了
- システム内更新日: 2022-07-20 07:37:37.372719
- Title: Online Prediction in Sub-linear Space
- Title（参考訳）: 準線形空間におけるオンライン予測
- Authors: Binghui Peng and Fred Zhang
- Abstract要約: 我々は、専門家のアドバイスによるオンライン学習のための最初のサブ線形空間とサブ線形後悔アルゴリズムを提供する。
また,任意の線形後悔アルゴリズムの線形メモリ下限を適応的逆数に対して証明することにより,(強い)適応的逆数と難解な逆数との分離を実証する。
- 参考スコア（独自算出の注目度）: 15.773280101995676
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We provide the first sub-linear space and sub-linear regret algorithm for
online learning with expert advice (against an oblivious adversary), addressing
an open question raised recently by Srinivas, Woodruff, Xu and Zhou (STOC
2022). We also demonstrate a separation between oblivious and (strong) adaptive
adversaries by proving a linear memory lower bound of any sub-linear regret
algorithm against an adaptive adversary. Our algorithm is based on a novel pool
selection procedure that bypasses the traditional wisdom of leader selection
for online learning, and a generic reduction that transforms any weakly
sub-linear regret $o(T)$ algorithm to $T^{1-\alpha}$ regret algorithm, which
may be of independent interest. Our lower bound utilizes the connection of
no-regret learning and equilibrium computation in zero-sum games, leading to a
proof of a strong lower bound against an adaptive adversary.
- Abstract（参考訳）: 我々は,Srinivas,Woodruff,Xu,Zhou (STOC 2022) が最近提起したオープンな疑問に対処するため,オンライン学習のための最初のサブ線形空間とサブ線形後悔アルゴリズムを提供する。
また,任意の線形後悔アルゴリズムの線形メモリ下限を適応的逆数に対して証明することにより,(強い)適応的逆数との分離を示す。
我々のアルゴリズムは、オンライン学習における従来のリーダー選択の知恵をバイパスする新しいプール選択法と、弱いサブ線形後悔$o(T)$アルゴリズムから$T^{1-\alpha$後悔アルゴリズムへ変換する一般的な還元法に基づいている。
我々の下界はゼロサムゲームにおける非回帰学習と平衡計算の接続を利用しており、適応的敵に対する強い下界の証明につながる。
関連論文リスト
- Smoothed Online Learning is as Easy as Statistical Learning [77.00766067963195]
この設定では、最初のオラクル効率、非回帰アルゴリズムを提供する。
古典的な設定で関数クラスが学習可能な場合、文脈的包帯に対するオラクル効率のよい非回帰アルゴリズムが存在することを示す。
論文 参考訳（メタデータ） (2022-02-09T19:22:34Z) - Dynamic Regret for Strongly Adaptive Methods and Optimality of Online
KRR [13.165557713537389]
我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。
我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
論文 参考訳（メタデータ） (2021-11-22T21:52:47Z) - Stochastic Online Linear Regression: the Forward Algorithm to Replace
Ridge [24.880035784304834]
オンラインリッジ回帰とフォワードアルゴリズムに対して高い確率的後悔境界を導出する。
これにより、オンライン回帰アルゴリズムをより正確に比較し、有界な観測と予測の仮定を排除できる。
論文 参考訳（メタデータ） (2021-11-02T13:57:53Z) - Online estimation and control with optimal pathlength regret [52.28457815067461]
オンライン学習アルゴリズムを設計する際の自然なゴールは、入力シーケンスの時間的変動の観点から、アルゴリズムの後悔を束縛することである。
OCOや盗賊など、さまざまなオンライン学習問題に対して、データ依存の「病的」後悔境界が最近取得されている。
論文 参考訳（メタデータ） (2021-10-24T22:43:15Z) - Strongly Adaptive OCO with Memory [49.319621885036035]
本稿では,メモリを用いたオンライン学習のための適応型アルゴリズムを提案する。
このアルゴリズムは,線形時間変化システムの制御に強い適応性を持つリセットバウンドをもたらす。
論文 参考訳（メタデータ） (2021-02-02T17:26:08Z) - Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。
各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。
我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
論文 参考訳（メタデータ） (2021-01-31T16:49:07Z) - Logarithmic Regret for Adversarial Online Control [56.12283443161479]
対数的後悔を伴う最初のアルゴリズムを任意対数外乱列に対して与える。
我々のアルゴリズムと分析はオフライン制御法の特徴を利用してオンライン制御問題を(遅延)オンライン学習に還元する。
論文 参考訳（メタデータ） (2020-02-29T06:29:19Z) - Online Learning with Imperfect Hints [72.4277628722419]
オンライン学習において,不完全な方向ヒントを用いたアルゴリズムを開発し,ほぼ一致している。
我々のアルゴリズムはヒントの品質を損なうものであり、後悔の限界は常に相関するヒントの場合と隠れない場合とを補間する。
論文 参考訳（メタデータ） (2020-02-11T23:06:09Z) - A Modern Introduction to Online Learning [15.974402990630402]
オンライン学習(オンライン学習)とは、最悪の場合における後悔の最小化の枠組みを指す。
凸損失を伴うオンライン学習のための一階と二階のアルゴリズムを提示する。
論文 参考訳（メタデータ） (2019-12-31T08:16:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。