論文の概要: Online Learning with Limited Information in the Sliding Window Model

• arxiv url: http://arxiv.org/abs/2601.03533v1
• Date: Wed, 07 Jan 2026 02:45:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-08 18:12:46.119105
• Title: Online Learning with Limited Information in the Sliding Window Model
• Title（参考訳）: スライディングウィンドウモデルにおける限定情報を用いたオンライン学習
• Authors: Vladimir Braverman, Sumegha Garg, Chen Wang, David P. Woodruff, Samson Zhou,
• Abstract要約: 我々はスライディングウィンドウモデルにおける専門家の問題を考える。 それぞれのインターバルについて、$sqrtn|mathcalI|textpolylog(nT)$ regret with $2$ query and only $textpolylog(nT)$ bits of memoryを示す。
• 参考スコア（独自算出の注目度）: 65.6372644972066
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by recent work on the experts problem in the streaming model, we consider the experts problem in the sliding window model. The sliding window model is a well-studied model that captures applications such as traffic monitoring, epidemic tracking, and automated trading, where recent information is more valuable than older data. Formally, we have $n$ experts, $T$ days, the ability to query the predictions of $q$ experts on each day, a limited amount of memory, and should achieve the (near-)optimal regret $\sqrt{nW}\text{polylog}(nT)$ regret over any window of the last $W$ days. While it is impossible to achieve such regret with $1$ query, we show that with $2$ queries we can achieve such regret and with only $\text{polylog}(nT)$ bits of memory. Not only are our algorithms optimal for sliding windows, but we also show for every interval $\mathcal{I}$ of days that we achieve $\sqrt{n|\mathcal{I}|}\text{polylog}(nT)$ regret with $2$ queries and only $\text{polylog}(nT)$ bits of memory, providing an exponential improvement on the memory of previous interval regret algorithms. Building upon these techniques, we address the bandit problem in data streams, where $q=1$, achieving $n T^{2/3}\text{polylog}(T)$ regret with $\text{polylog}(nT)$ memory, which is the first sublinear regret in the streaming model in the bandit setting with polylogarithmic memory; this can be further improved to the optimal $\mathcal{O}(\sqrt{nT})$ regret if the best expert's losses are in a random order.
• Abstract（参考訳）: ストリーミングモデルにおけるエキスパート問題に関する最近の研究に触発されて,スライディングウィンドウモデルにおけるエキスパート問題を考える。 スライディングウインドウモデルは、交通監視、疫病追跡、自動取引などのアプリケーションを取り込む、よく研究されたモデルである。 正式には、$n$のエキスパート、$T$day、毎日$q$のエキスパートの予測をクエリする機能、限られた量のメモリを持ち、(ほぼ)最適に後悔する$\sqrt{nW}\text{polylog}(nT)$を、過去$W$dayのあらゆるウィンドウで実行すべきである。 このような後悔を1ドルクエリで達成することは不可能ですが、$2ドルのクエリでは、そのような後悔を達成でき、メモリのビットを$\text{polylog}(nT)$でしか達成できません。 我々のアルゴリズムはウィンドウのスライディングに最適であるだけでなく、$\sqrt{n|\mathcal{I}|}\text{polylog}(nT)$ regret with $2$ query and only $\text{polylog}(nT)$ bits of memory を達成した日毎の$\mathcal{I}$も示す。 データストリームでは、$q=1$で$n T^{2/3}\text{polylog}(T)$ regret with $\text{polylog}(nT)$ memoryというバンドレート設定におけるストリーミングモデルにおける最初のサブ線形後悔であり、最適な$\mathcal{O}(\sqrt{nT})$ regretにさらに改善することができる。

関連論文リスト

• Online Inverse Linear Optimization: Efficient Logarithmic-Regret Algorithm, Robustness to Suboptimality, and Lower Bound [25.50155563108198]
  ラウンド単位の複雑さが$T$に依存しない最初の対数-回帰法を提案する。 我々の方法は極めて単純であり、オンラインニュートンステップ(ONS)を適切なexp-concave損失関数に適用する。 また、$Omega(n)$ の下限を示し、$O(nln T)$ 境界が $O(ln T)$ 係数まで固であることを示す。
  論文  参考訳（メタデータ） (2025-01-24T09:19:15Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• Logarithmic Regret from Sublinear Hints [76.87432703516942]
  自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。 また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
  論文  参考訳（メタデータ） (2021-11-09T16:50:18Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。 損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
  論文  参考訳（メタデータ） (2021-03-02T06:53:44Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  我々は,バンディットフィードバックを用いてオンライン学習を学習する。 learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。 我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。 ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
  論文  参考訳（メタデータ） (2021-02-15T08:16:51Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
  論文  参考訳（メタデータ） (2020-06-16T13:01:33Z)

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

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