論文の概要: Strongly Adaptive Online Learning with Time-Varying Movement Costs

• arxiv url: http://arxiv.org/abs/2610.32740v1
• Date: Fri, 23 Oct 2026 14:54:13 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-27 01:38:06.587516
• Title: Strongly Adaptive Online Learning with Time-Varying Movement Costs
• Title（参考訳）: 時間変動移動コストによるオンライン学習の高度適応化
• Abstract要約: 我々は,OCO(Online Convex Optimization)に対する時間変動移動コストの強い適応的後悔について検討した。 このフレームワークは、環境と切り替え決定のコストが時間とともに変動する複雑なシーケンシャルな意思決定問題を捉えます。 遅れたフィードバックの下で、最初に強く適応的な保証を確立する。
• 参考スコア（独自算出の注目度）: 18.95079821752574
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study strongly adaptive regret for Online Convex Optimization (OCO) with time-varying movement costs, a setting that evaluates a learner's performance over arbitrary sub-intervals. This framework captures complex sequential decision-making problems where both the environment and the cost of switching decisions fluctuate over time. We propose a novel algorithm which, for any interval $[a,b] \subseteq [T]$, achieves a data-dependent regret bound of $ \widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right) $, where $D$ is the diameter of the decision domain, $P_{[a,b]}$ is the path length of the comparator sequence over $[a,b]$, $g_t$ is the gradient of the loss, and $λ_t$ is the movement-cost coefficient at round $t$. Key to our approach is a novel reduction to sleeping experts with movement costs, a previously unexplored variant that is of independent interest. As a result of this development, we further establish the first strongly-adaptive guarantees under delayed feedback. Our approach also naturally extends to OCO with time-varying memory, where we obtain strongly-adaptive guarantees which improve the best-known bounds.
• Abstract（参考訳）: 本研究は,オンライン凸最適化(OCO, Online Convex Optimization, OCO)の時間変動移動コストに対する強い適応的後悔について考察する。 このフレームワークは、環境と切り替え決定のコストが時間とともに変動する複雑なシーケンシャルな意思決定問題を捉えます。 任意の間隔において$[a,b] \subseteq [T]$が$ \widetilde{\mathcal{O}}\left( \sqrt{(D^2+DP_{[a,b]})\sum_{t \in [a,b]}(\|g_t\|^2+λ_t\|g_t\|)} \right)$,$D$が決定領域の直径、$P_{[a,b]}$が$[a,b]のコンパレータ列のパス長、$g_t$が損失の勾配、$λ_t$が損失の係数である。 われわれのアプローチの鍵となるのは、睡眠の専門家が運動コストで新規に減らすことだ。 この開発の結果,遅延フィードバックの下では,最初の強適応保証が確立される。 また,本手法は時間変化メモリを用いてOCOに自然に拡張し,最もよく知られたバウンダリを改善するための強適応保証を得る。

関連論文リスト

• Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
  オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。 長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
  論文  参考訳（メタデータ） (2026-09-30T21:03:03Z)
• Dynamic Regret in Online Convex Optimization with Indicator Switching Costs [8.708728702853966]
  本研究では, オンライン凸最適化における動的後悔について, インセンティブの切り替えコストを用いて検討する。 動的後悔に対するこれらのテクニックの直接的な拡張は、確実に失敗し、異なるアプローチを動機付けていることを示す。
  論文  参考訳（メタデータ） (2026-09-24T21:08:40Z)
• Convex Optimization with Nested Evolving Feasible Sets (CONES) under Time-Varying Loss Functions [5.533296779866529]
  損失関数を$f_t'$sに拡張して、時間とともに変更できるようにします。 サブリニアなオンラインアルゴリズムはいつでも、運動コストが$left(log Tright)$であることを示す。
  論文  参考訳（メタデータ） (2026-09-10T08:13:27Z)
• Nested Convex-Body Chasing for Online Optimization with Evolving Feasible Sets [0.0]
  ネストした縮小可能な領域を2つの設定でオンライン最適化する。 懸念されている最小限の試験と累積余剰試験は、後悔の保証を保っている。 決定論的リセット可能なネスト付き凸体チェッカーは運動を制限する。
  論文  参考訳（メタデータ） (2026-08-29T06:01:56Z)
• Parameter-free Dynamic Regret: Time-varying Movement Costs, Delayed Feedback, and Memory [18.95079821752574]
  移動コストを伴う非拘束型オンライン凸最適化(OCO)における動的後悔について検討した。 我々の主な貢献は、この設定に対する最初のコンパレータ適応動的後悔を確立する新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2026-02-06T17:50:22Z)
• A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees [58.59385794080679]
  本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。 バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
  論文  参考訳（メタデータ） (2026-02-02T18:17:34Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Non-stationary Delayed Online Convex Optimization: From Full-information to Bandit Setting [71.82716109461967]
  遅延勾配が利用できる全情報ケースに対して Mild-OGD というアルゴリズムを提案する。 ミルド-OGDのダイナミックな後悔は、順番の仮定の下で$O(sqrtbardT(P_T+1))$で自動的に束縛されることを示す。 Mild-OGDのバンディット版も開発し,損失値の遅れのみを考慮に入れた,より困難なケースについて検討した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• Online Convex Optimization with Continuous Switching Constraint [78.25064451417082]
  連続的なスイッチング制約を伴うオンライン凸最適化の問題を紹介する。 強い凸関数の場合、後悔境界は$O(log T)$ for $S=Omega(log T)$、$O(minT/exp(S)+S,T)$ for $S=O(log T)$に改善できることを示す。
  論文  参考訳（メタデータ） (2021-03-21T11:43:35Z)

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

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