論文の概要: Exploiting Curvature in Online Convex Optimization with Delayed Feedback

• arxiv url: http://arxiv.org/abs/2506.07595v1
• Date: Mon, 09 Jun 2025 09:49:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-10 16:33:10.897665
• Title: Exploiting Curvature in Online Convex Optimization with Delayed Feedback
• Title（参考訳）: 遅延フィードバックを用いたオンライン凸最適化における爆発曲率
• Authors: Hao Qiu, Emmanuel Esposito, Mengxiao Zhang,
• Abstract要約: 曲面損失と遅延フィードバックを用いたオンライン凸最適化問題について検討する。 次数$minsigma_maxln T, sqrtd_mathrmtot$を後悔する規則化リーダの変種を提案する。 次に、exp-concave損失を検討し、適応的な学習率チューニングで遅延を処理するためにOnline Newton Stepアルゴリズムを拡張した。
• 参考スコア（独自算出の注目度）: 6.390468088226495
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work, we study the online convex optimization problem with curved losses and delayed feedback. When losses are strongly convex, existing approaches obtain regret bounds of order $d_{\max} \ln T$, where $d_{\max}$ is the maximum delay and $T$ is the time horizon. However, in many cases, this guarantee can be much worse than $\sqrt{d_{\mathrm{tot}}}$ as obtained by a delayed version of online gradient descent, where $d_{\mathrm{tot}}$ is the total delay. We bridge this gap by proposing a variant of follow-the-regularized-leader that obtains regret of order $\min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$, where $\sigma_{\max}$ is the maximum number of missing observations. We then consider exp-concave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning, achieving regret $\min\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\}$ where $n$ is the dimension. To our knowledge, this is the first algorithm to achieve such a regret bound for exp-concave losses. We further consider the problem of unconstrained online linear regression and achieve a similar guarantee by designing a variant of the Vovk-Azoury-Warmuth forecaster with a clipping trick. Finally, we implement our algorithms and conduct experiments under various types of delay and losses, showing an improved performance over existing methods.
• Abstract（参考訳）: 本研究では,曲面損失と遅延フィードバックを用いたオンライン凸最適化問題について検討する。 損失が強い凸である場合、既存のアプローチでは、$d_{\max} \ln T$ の残差境界が得られ、$d_{\max}$ は最大遅延であり、$T$ は時間水平線である。 しかし、多くの場合、この保証は$\sqrt{d_{\mathrm{tot}}}$よりもはるかに悪い。 このギャップを埋めるには、次数$\min\{\sigma_{\max}\ln T, \sqrt{d_{\mathrm{tot}}}\}$, $\sigma_{\max}$は欠測数の最大値である。 次に、exp-concaveの損失を考え、Online Newton Stepアルゴリズムを拡張して、適応的な学習率チューニングで遅延を処理し、後悔の$\min\{d_{\max} n\ln T, \sqrt{d_{\mathrm{tot}}}\}$をデメンテーションとする。 我々の知る限りでは、これはexp-concave損失に対するこのような後悔の束縛を達成した最初のアルゴリズムである。 さらに、制約のないオンライン線形回帰の問題を考慮し、クリッピングトリックでVovk-Azoury-Warmuth予測器の変種を設計することで、同様の保証を実現する。 最後に,アルゴリズムを実装し,様々な遅延と損失を伴って実験を行い,既存の手法よりも性能が向上したことを示す。

関連論文リスト

• Full Swap Regret and Discretized Calibration [18.944031222413294]
  構造化正規形式ゲームにおけるスワップ後悔の最小化問題について検討する。 我々は、Emphfullスワップリ後悔の最小化という新しいオンライン学習問題を導入する また、これらのツールをオンライン予測問題に適用し、校正誤差を補正する。
  論文  参考訳（メタデータ） (2025-02-13T13:49:52Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Improved Dynamic Regret for Online Frank-Wolfe [54.690867216880356]
  オンライン凸最適化のための効率的なプロジェクションフリーアルゴリズムであるFrank-Wolfe (OFW) の動的後悔について検討する。 本稿では,FWの高速収束率をオフライン最適化からオンライン最適化に拡張することにより,OFWの動的後悔境界の改善を導出する。
  論文  参考訳（メタデータ） (2023-02-11T07:19:51Z)
• Online Convex Optimization with Stochastic Constraints: Zero Constraint Violation and Bandit Feedback [0.0]
  本稿では,O(sqrtT)$期待後悔とゼロ制約違反を保証できるドリフト・プラス・ペナルティアルゴリズムの変種を提案する。 我々のアルゴリズムは、バニラドリフト・プラス・ペナルティ法とは対照的に、時間地平線の長さが$T$である。
  論文  参考訳（メタデータ） (2023-01-26T18:04:26Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Asynchronous Stochastic Optimization Robust to Arbitrary Delays [54.61797739710608]
  遅延勾配の最適化を考えると、ステップt$毎に、アルゴリズムは古い計算を使って更新する - d_t$ for arbitrary delay $d_t gradient。 本実験は,遅延分布が歪んだり重くなったりした場合のアルゴリズムの有効性とロバスト性を示す。
  論文  参考訳（メタデータ） (2021-06-22T15:50:45Z)
• Online Strongly Convex Optimization with Unknown Delays [30.931538196386672]
  オンライン凸最適化の問題点を未知の遅延で検討する。 まず、OGDの遅延変形を強凸関数に拡張する。 我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
  論文  参考訳（メタデータ） (2021-03-21T10:16:15Z)
• 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)

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

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