論文の概要: Capacity-Constrained Online Convex Optimization with Delayed Feedback

• arxiv url: http://arxiv.org/abs/2606.11711v1
• Date: Wed, 10 Jun 2026 06:37:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-11 16:42:38.32858
• Title: Capacity-Constrained Online Convex Optimization with Delayed Feedback
• Title（参考訳）: 遅延フィードバックを用いた容量制約付きオンライン凸最適化
• Authors: Alexander Ryabchenko, Idan Attias, Daniel M. Roy,
• Abstract要約: 容量制約下での遅延オンライン凸最適化(OCO)について検討した。 1次フィードバックの場合、容量$C = (log T)$ sufficesで標準遅延OCOレートを対数係数まで回復できることがわかった。 包帯フィードバックの場合、後悔率は$(1 + _textmax/C)$で変調される。
• 参考スコア（独自算出の注目度）: 58.59385794080679
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online learning with delayed feedback typically assumes that the learner can track all pending rounds until their feedback arrives. In practice, tracking resources are finite, and feedback from untracked rounds is permanently lost. In this paper, we study delayed online convex optimization (OCO) under a hard capacity constraint, where at most $C$ pending rounds can be tracked at any time. To model delay information, we introduce a semi-clairvoyant model that refines the clairvoyant assumption from prior work: rather than requiring delays to be known at prediction time, the learner observes delay expirations online, consistent with the classical unconstrained delayed setting. Our approach proceeds via a reduction to a novel ``delayed and weighted'' OCO problem, using a scheduler that randomizes tracking decisions and importance-weights the resulting observations. For this base problem, we propose and analyze Delayed-Weighted FTRL and its bandit analogue, establishing regret bounds that explicitly characterize the interaction between time-varying weights and delayed feedback. Combining these base learners with our schedulers yields the first regret guarantees for capacity-constrained OCO under convex and strongly convex losses, for both first-order and bandit feedback. For first-order feedback, capacity $C = Ω(\log T)$ suffices to recover standard delayed OCO rates up to logarithmic factors. For bandit feedback, the regret rates are modulated by powers of $(1 + σ_{\text{max}}/C)$, where $σ_{\text{max}}$ is the maximum number of pending observations at any time. This allows the regret bound to degrade gracefully when $C < σ_{\text{max}}$, while remaining sublinear.
• Abstract（参考訳）: 遅延したフィードバックによるオンライン学習は通常、学習者がフィードバックが到着するまで、保留中のラウンドをすべて追跡できると仮定する。 実際には、トラッキングリソースは有限であり、追跡されていないラウンドからのフィードバックは永久に失われる。 本稿では,遅延オンライン凸最適化 (OCO) を,最大で$C$の保留ラウンドをいつでも追跡できるハードキャパシティ制約下で検討する。 遅延情報をモデル化するために,学習者は予測時に遅延を知っておくのではなく,古典的制約のない遅延設定と整合して遅延有効期限をオンラインで観察する。 我々のアプローチは、追跡決定をランダムにし、結果の観測を重要度重み付けするスケジューラを使用して、'遅延と重み付け'という新しいOCO問題に還元することで進みます。 本研究では, 遅延重み付きFTRLとその帯域幅の類似性について検討し, 時間変化重みと遅延フィードバックとの相互作用を明示的に特徴付ける後悔境界を確立する。 これらのベースラーナーとスケジューラを組み合わせることで、第一次と第二次の両方のフィードバックに対して、コンベックスと強い凸損失下での容量制約OCOに対する最初の後悔の保証が得られる。 1次フィードバックでは、キャパシティ$C = Ω(\log T)$ sfitss to recovery standard delay OCO rate to to logarithmic factors。 包帯フィードバックの場合、後悔率は$(1 + σ_{\text{max}}/C)$で変調されるが、$σ_{\text{max}}$はいつでも保留中の観測の最大数である。 これにより、サブ線形のままの$C < σ_{\text{max}}$で、後悔は優雅に分解される。

関連論文リスト

• Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions [13.10320454140084]
  不安定な環境下での線形デュエルバンディットについて検討した。 本稿では,事前予約情報から事前予約後のコンテキストを予測する学習近似器を統合する用語を提案する。 本分析では, 従来の作業に典型的な乗算劣化を回避し, 汚損と遅延の間に付加的なコスト構造を明らかにした。
  論文  参考訳（メタデータ） (2026-05-03T07:19:05Z)
• Capacity-Constrained Online Learning with Delays: Scheduling Frameworks and Regret Trade-offs [60.7808741738461]
  我々は,遅れたフィードバックのために,過去のラウンドを同時に追跡できる回数を制限する,斬新な「透明さ」の下で,難解な遅延を伴うオンライン学習について研究する。 我々のアルゴリズムは、全てのキャパシティレベルにおいてミニマックスの後悔を達成し、性能は最適以下のキャパシティで優雅に低下する。
  論文  参考訳（メタデータ） (2025-03-25T17:20:39Z)
• Revisiting Multi-Agent Asynchronous Online Optimization with Delays: the Strongly Convex Case [14.550539239345582]
  複数エージェントの非同期オンライン最適化を遅延で再検討し、各ラウンドで決定を下すにはエージェントの1つだけがアクティブになる。 本稿では,従来のフォロー・ザ・リーダーアルゴリズムであるFTDLの遅延型を提案する。
  論文  参考訳（メタデータ） (2025-03-13T03:49:25Z)
• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• 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)
• Delayed Feedback in Generalised Linear Bandits Revisited [5.349852254138085]
  一般化線形包帯における遅延報酬の現象を理論的に研究する。 遅延フィードバックに対する楽観的なアルゴリズムの自然な適応は、遅延に対するペナルティが地平線から独立であるような後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2022-07-21T23:35:01Z)
• Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
  オンライン凸最適化の問題点を未知の遅延で検討する。 まず、OGDの遅延変形を強凸関数に拡張する。 我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
  論文  参考訳（メタデータ） (2021-03-21T10:16:15Z)

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

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