論文の概要: A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees

• arxiv url: http://arxiv.org/abs/2602.02634v1
• Date: Mon, 02 Feb 2026 18:17:34 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-04 18:37:14.996342
• Title: A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees
• Title（参考訳）: 保証の改善によるオンライン凸最適化における遅延から即時フィードバックへの削減
• Authors: Alexander Ryabchenko, Idan Attias, Daniel M. Roy,
• Abstract要約: 本稿では,後悔を遅延非依存の学習項と遅延誘発のドリフト項に分解する連続時間モデルを提案する。 バンディット凸最適化では,最先端の1次数に適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。
• 参考スコア（独自算出の注目度）: 58.59385794080679
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a reduction-based framework for online learning with delayed feedback that recovers and improves upon existing results for both first-order and bandit convex optimization. Our approach introduces a continuous-time model under which regret decomposes into a delay-independent learning term and a delay-induced drift term, yielding a delay-adaptive reduction that converts any algorithm for online linear optimization into one that handles round-dependent delays. For bandit convex optimization, we significantly improve existing regret bounds, with delay-dependent terms matching state-of-the-art first-order rates. For first-order feedback, we recover state-of-the-art regret bounds via a simpler, unified analysis. Quantitatively, for bandit convex optimization we obtain $O(\sqrt{d_{\text{tot}}} + T^{\frac{3}{4}}\sqrt{k})$ regret, improving the delay-dependent term from $O(\min\{\sqrt{T d_{\text{max}}},(Td_{\text{tot}})^{\frac{1}{3}}\})$ in previous work to $O(\sqrt{d_{\text{tot}}})$. Here, $k$, $T$, $d_{\text{max}}$, and $d_{\text{tot}}$ denote the dimension, time horizon, maximum delay, and total delay, respectively. Under strong convexity, we achieve $O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\} + (T^2\ln T)^{\frac{1}{3}} {k}^{\frac{2}{3}})$, improving the delay-dependent term from $O(d_{\text{max}} \ln T)$ in previous work to $O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\})$, where $σ_{\text{max}}$ denotes the maximum number of outstanding observations and may be considerably smaller than $d_{\text{max}}$.
• Abstract（参考訳）: 本研究では,オンライン学習の遅延フィードバックを用いたリダクションベースのフレームワークを開発し,一次および二次凸最適化の既存の結果の回復と改善を行う。 提案手法では,遅延非依存の学習項と遅延非依存のドリフト項に後悔が分解される連続時間モデルを導入し,オンライン線形最適化のアルゴリズムをラウンド依存の遅延を扱うモデルに変換する遅延適応型還元法を提案する。 バンディット凸最適化では,最先端の1次レートに適合する遅延依存項を用いて,既存の残差境界を大幅に改善する。 1次フィードバックでは、より単純で統一的な分析により、最先端の後悔境界を復元する。 定量的に言えば、バンディット凸最適化のために$O(\sqrt{d_{\text{tot}}} + T^{\frac{3}{4}}\sqrt{k})$ regret, improve the delay-dependent term from $O(\min\{\sqrt{T d_{\text{max}}},(Td_{\text{tot}})^{\frac{1}{3}}\})$ $O(\sqrt{d_{\text{tot}}})$ ここで、$k$、$T$、$d_{\text{max}}$、$d_{\text{tot}}$は、それぞれ寸法、時間水平線、最大遅延、総遅延を表す。 強い凸性の下で、$O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\} + (T^2\ln T)^{\frac{1}{3}} {k}^{\frac{2}{3}})$, 遅延依存項を$O(d_{\text{max}} \ln T)$から$O(\min\{σ_{\text{max}} \ln T, \sqrt{d_{\text{tot}}}\})$へ改善する。

関連論文リスト

• Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting [22.208290858529672]
  帯域幅設定における遅延フィードバックによるオンライン非モジュール最適化について検討する。 本稿では,一点勾配推定器を用いた新しいDBGD-NF法を提案する。 また,ブロック更新機構を用いてDBGD-NFを拡張し,遅延と帯域幅フィードバックの結合効果を分離する。
  論文  参考訳（メタデータ） (2025-08-01T11:00:19Z)
• Exploiting Curvature in Online Convex Optimization with Delayed Feedback [6.390468088226495]
  曲面損失と遅延フィードバックを用いたオンライン凸最適化問題について検討する。 次数$minsigma_maxln T, sqrtd_mathrmtot$を後悔する規則化リーダの変種を提案する。 次に、exp-concave損失を検討し、適応的な学習率チューニングで遅延を処理するためにOnline Newton Stepアルゴリズムを拡張した。
  論文  参考訳（メタデータ） (2025-06-09T09:49:54Z)
• An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints [55.2480439325792]
  逆制約を伴うオンライン凸最適化(OCO)について検討する。 本稿では,損失関数と制約関数の予測にアルゴリズムがアクセス可能な設定に着目する。 以上の結果から,現在のO(sqrtT) $ regret と $ tildeO(sqrtT) $ cumulative constraint violation の改善が期待できることがわかった。
  論文  参考訳（メタデータ） (2024-12-11T03:06:42Z)
• Improved Regret for Bandit Convex Optimization with Delayed Feedback [50.46856739179311]
  遅延フィードバックを伴うバンド凸最適化(BCO)。 我々は,新しいアルゴリズムを開発し,一般にO(sqrtnT3/4+sqrtdT)$の後悔境界を満足していることを証明する。 提案アルゴリズムは,強い凸関数に対して$O((nT)2/3log/3T+dlog T)$に制限された後悔を改善することができることを示す。
  論文  参考訳（メタデータ） (2024-02-14T13:08:26Z)
• A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
  本稿では,Zimmert と Seldin [2020] のアルゴリズムを,フィードバックの遅れによる逆方向の多重武装バンディットに対して修正したチューニングを行う。 我々は,時間的遅れのある設定において,ほぼ最適の相反的後悔の保証を同時に達成する。 また,任意の遅延の場合に対するアルゴリズムの拡張も提案する。
  論文  参考訳（メタデータ） (2022-06-29T20:49:45Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• 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)

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

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