論文の概要: Online Strongly Convex Optimization with Unknown Delays

• arxiv url: http://arxiv.org/abs/2103.11354v1
• Date: Sun, 21 Mar 2021 10:16:15 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-23 14:14:41.280636
• Title: Online Strongly Convex Optimization with Unknown Delays
• Title（参考訳）: 未知の遅延を伴うオンラインコンベックス最適化
• Authors: Yuanyu Wan, Wei-Wei Tu, Lijun Zhang
• Abstract要約: オンライン凸最適化の問題点を未知の遅延で検討する。 まず、OGDの遅延変形を強凸関数に拡張する。 我々は、$d$が最大遅延である$O(dlog T)$のより良い後悔の境界を確立します。
• 参考スコア（独自算出の注目度）: 30.931538196386672
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the problem of online convex optimization with unknown delays, in which the feedback of a decision arrives with an arbitrary delay. Previous studies have presented a delayed variant of online gradient descent (OGD), and achieved the regret bound of $O(\sqrt{T+D})$ by only utilizing the convexity condition, where $D$ is the sum of delays over $T$ rounds. In this paper, we further exploit the strong convexity to improve the regret bound. Specifically, we first extend the delayed variant of OGD for strongly convex functions, and establish a better regret bound of $O(d\log T)$, where $d$ is the maximum delay. The essential idea is to let the learning rate decay with the total number of received feedback linearly. Furthermore, we consider the more challenging bandit setting, and obtain similar theoretical guarantees by incorporating the classical multi-point gradient estimator into our extended method. To the best of our knowledge, this is the first work that solves online strongly convex optimization under the general delayed setting.
• Abstract（参考訳）: 本研究では,決定のフィードバックが任意の遅延で到着する,未知の遅延を伴うオンライン凸最適化の問題について検討する。 これまでの研究では、オンライン勾配降下(英語版) (ogd) の遅延変種を示しており、d$ は$t$ のラウンドに対する遅延の和である凸条件のみを利用することで、o(\sqrt{t+d})$ の後悔の限界を達成した。 本稿では,この強い凸性を利用して,後悔関係を改善する。 具体的には、まず、強い凸関数に対するOGDの遅延変形を拡張し、$O(d\log T)$のより良い後悔境界を確立し、$d$が最大の遅延である。 基本的なアイデアは、受信したフィードバックの総数を直線的に学習率を減衰させることである。 さらに,提案手法に古典的多点勾配推定器を組み込むことにより,より困難な帯域設定を考察し,同様の理論的保証を得る。 私たちの知る限りでは、これは一般的な遅延設定の下で、オンラインの強い凸最適化を解決する最初の仕事です。

関連論文リスト

• Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling [73.5602474095954]
  マルコフサンプリングの遅延更新による近似スキームの非漸近的性能について検討した。 我々の理論的な発見は、幅広いアルゴリズムの遅延の有限時間効果に光を当てた。
  論文  参考訳（メタデータ） (2024-02-19T03:08:02Z)
• 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)
• Non-stationary Online Convex Optimization with Arbitrary Delays [50.46856739179311]
  本稿では,非定常環境における遅延オンライン凸最適化(OCO)について検討する。 まず, 遅延勾配の勾配降下ステップを, 到着順に応じて行う単純なアルゴリズム, DOGDを提案する。 DOGDが達成した動的後悔境界を$O(sqrtbardT(P_T+1))$に削減する改良アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2023-05-20T07:54:07Z)
• 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)
• Procrastinated Tree Search: Black-box Optimization with Delayed, Noisy, and Multi-fidelity Feedback [11.064341598231195]
  ブラックボックス最適化問題では,評価やシミュレーションオラクルのフィードバックによってのみ機能にアクセス可能な未知の目的関数を最大化することを目的としている。 ProCrastinated Tree Search (PCTS) と呼ばれる階層的楽観木探索(HOO)の汎用的拡張を提案する。 我々は,PCTSの遅延,雑音,多面的フィードバックによる後悔を定量化する汎用的証明手法を提案する。
  論文  参考訳（メタデータ） (2021-10-14T08:55:41Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  大規模最適化問題を解決する最も広く使われている手法の1つは、分散非同期勾配勾配(DASGD)である。 DASGDは同じ遅延仮定の下で大域的最適実装モデルに収束することを示す。
  論文  参考訳（メタデータ） (2021-07-06T21:59:49Z)
• Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
  我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。 離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
  論文  参考訳（メタデータ） (2021-02-07T14:47:19Z)
• Projection-free Online Learning over Strongly Convex Sets [24.517908972536432]
  我々は,強い凸集合に対するオンライン学習の特別な事例について検討し,OWが一般凸集合の損失に対して$O(T2/3)$よりも良い後悔の限界を享受できることを最初に証明した。 一般凸集合に対する$O(sqrtT)$の後悔境界と強凸集合に対する$O(sqrtT)$の後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2020-10-16T05:42:50Z)
• Adapting to Delays and Data in Adversarial Multi-Armed Bandits [7.310043452300736]
  決定時に利用可能な情報のみを用いてステップサイズを調整するExp3アルゴリズムの変種を分析する。 我々は、観測された(最悪の場合ではなく)遅延や損失のシーケンスに適応する後悔の保証を得る。
  論文  参考訳（メタデータ） (2020-10-12T20:53:52Z)
• Efficient Optimistic Exploration in Linear-Quadratic Regulators via Lagrangian Relaxation [107.06364966905821]
  線形2次レギュレータ(LQR)設定における探索・探索ジレンマについて検討した。 有限 MDP に対する楽観的アルゴリズムで用いられる拡張値反復アルゴリズムに着想を得て,Oulq の楽観的最適化を緩和することを提案する。 我々は、少なくとも$Obig(log (1/epsilon)big)$ Riccati方程式を解くことで、$epsilon$-OptimisticControllerを効率的に計算できることを示した。
  論文  参考訳（メタデータ） (2020-07-13T16:30:47Z)

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

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