論文の概要: Dynamic Regret in Online Convex Optimization with Indicator Switching Costs

• arxiv url: http://arxiv.org/abs/2609.30556v1
• Date: Thu, 24 Sep 2026 21:08:40 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.141205
• Title: Dynamic Regret in Online Convex Optimization with Indicator Switching Costs
• Title（参考訳）: インジケータスイッチングコストを考慮したオンライン凸最適化における動的回帰
• Abstract要約: 本研究では, オンライン凸最適化における動的後悔について, インセンティブの切り替えコストを用いて検討する。 動的後悔に対するこれらのテクニックの直接的な拡張は、確実に失敗し、異なるアプローチを動機付けていることを示す。
• 参考スコア（独自算出の注目度）: 8.708728702853966
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study dynamic regret in online convex optimization with an \emph{indicator switching cost}: a fixed penalty incurred whenever two consecutive decisions differ. This captures startup overheads such as server activation, model deployment, and cache updates, and on a bounded domain it recovers norm-based movement costs as a special case. Existing guarantees for indicator costs handle only static comparators. We show that a direct extension of these techniques to dynamic regret provably fails, motivating a different approach. We propose a meta-learning framework: a set of randomized lazy FTRL base learners restarted at dyadic time scales, aggregated by a movement-aware master that mixes their proposal densities and samples actions via maximal coupling of consecutive mixtures. The resulting algorithm satisfies, in expectation, $\mathcal{R}^{\mathbf{1}}_T \le \tilde{\mathcal{O}}(\min\{\sqrt{T(S_T{+}1)},T^{2/3}(P_T+1)^{1/3}\})$, where $\mathcal{R}^{\mathbf{1}}_T$ is the dynamic regret plus the cumulative indicator switching cost, $S_T$ counts comparator switches, and $P_T$ is the comparator path length. The bound holds simultaneously for all sequences and requires no prior knowledge of $S_T$ or $P_T$: it is minimax-optimal (up to logarithmic factors) for tracking piecewise-constant comparators, and also captures frequently moving comparators with small total path length.
• Abstract（参考訳）: 我々は,オンライン凸最適化における動的後悔を,連続的な2つの決定が相違するたびに生じる固定的なペナルティである「emph{indicator switch cost}」を用いて研究した。 これにより、サーバアクティベーション、モデルデプロイメント、キャッシュ更新などの起動オーバーヘッドをキャプチャし、バウンドドメイン上では、特別なケースとして標準ベースのムーブメントコストを回復する。 既存のインジケータコスト保証は静的コンパレータのみを扱う。 動的後悔に対するこれらのテクニックの直接的な拡張は、確実に失敗し、異なるアプローチを動機付けていることを示す。 本稿では, メタラーニングフレームワークを提案する: ランダム化遅延FTRLベースラーナーの集合を, 連続した混合の最大結合により, それらの提案密度を混合し, 動作をサンプリングする動き認識マスターによって集約し, 動的時間スケールで再起動する。 結果のアルゴリズムは期待通り$\mathcal{R}^{\mathbf{1}}_T \le \tilde{\mathcal{O}}(\min\{\sqrt{T(S_T{+}1)},T^{2/3}(P_T+1)^{1/3}\})$, where $\mathcal{R}^{\mathbmathbf{1}}_T$ is the dynamic regret plus the cumulative indicator switching cost, $S_T$ counts comparator switches, $P_T$ is the comparator path length。 このバウンダリはすべてのシーケンスに対して同時に保持され、$S_T$や$P_T$の事前の知識を必要としない。

関連論文リスト

• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• 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)
• Non-stationary Projection-free Online Learning with Dynamic and Adaptive Regret Guarantees [36.746745619968024]
  本研究では,非定常プロジェクションフリーオンライン学習について検討し,動的後悔と適応的後悔を選択して評価を行った。 我々の結果は、プロジェクションフリーオンライン学習における最初の一般的な動的後悔境界であり、既存の$mathcalO(T3/4)$static regretを復元することができる。 本稿では,$tildemathcalO(tau3/4)$ アダプティブリフレッシュバウンドを長さ$tauの任意の間隔で達成するためのプロジェクションフリーな手法を提案する。
  論文  参考訳（メタデータ） (2023-05-19T15:02:10Z)
• 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)
• Revisiting Smoothed Online Learning [70.09792747315323]
  オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。 競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
  論文  参考訳（メタデータ） (2021-02-13T14:15:55Z)

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

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