論文の概要: Online Convex Optimization with Switching Cost and Delayed Gradients
- arxiv url: http://arxiv.org/abs/2310.11880v1
- Date: Wed, 18 Oct 2023 11:06:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-19 16:58:49.383057
- Title: Online Convex Optimization with Switching Cost and Delayed Gradients
- Title（参考訳）: 切り替えコストと遅延勾配を考慮したオンライン凸最適化
- Authors: Spandan Senapati, Rahul Vaze
- Abstract要約: オンラインアルゴリズムは、前の目的関数の勾配情報のみを用いて、その動作を選択することができる。
2次切替コストのOCO問題の競合比は、少なくとも4(L + 5) + frac16(L + 5)mu$である。
2次・線形切替コストの最適競争比率は、制限情報設定において根本的に異なると結論付けている。
- 参考スコア（独自算出の注目度）: 7.903539618132858
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the online convex optimization (OCO) problem with quadratic and
linear switching cost in the limited information setting, where an online
algorithm can choose its action using only gradient information about the
previous objective function. For $L$-smooth and $\mu$-strongly convex objective
functions, we propose an online multiple gradient descent (OMGD) algorithm and
show that its competitive ratio for the OCO problem with quadratic switching
cost is at most $4(L + 5) + \frac{16(L + 5)}{\mu}$. The competitive ratio upper
bound for OMGD is also shown to be order-wise tight in terms of $L,\mu$. In
addition, we show that the competitive ratio of any online algorithm is
$\max\{\Omega(L), \Omega(\frac{L}{\sqrt{\mu}})\}$ in the limited information
setting when the switching cost is quadratic. We also show that the OMGD
algorithm achieves the optimal (order-wise) dynamic regret in the limited
information setting. For the linear switching cost, the competitive ratio upper
bound of the OMGD algorithm is shown to depend on both the path length and the
squared path length of the problem instance, in addition to $L, \mu$, and is
shown to be order-wise, the best competitive ratio any online algorithm can
achieve. Consequently, we conclude that the optimal competitive ratio for the
quadratic and linear switching costs are fundamentally different in the limited
information setting.
- Abstract（参考訳）: 制約情報設定において,オンライン凸最適化(OCO)問題を2次・線形切替コストで考慮し,従来の目的関数の勾配情報のみを用いて,オンラインアルゴリズムでその動作を選択する。
L$-smooth と $\mu$-strongly convex objective function に対して、オンライン多重勾配降下法(OMGD)アルゴリズムを提案し、OCO問題の2次切替コストに対する競合比が少なくとも 4(L + 5) + \frac{16(L + 5)}{\mu}$ であることを示す。
OMGD の競合比上界は、$L,\mu$ の点で順序的に厳密であることも示される。
さらに、オンラインアルゴリズムの競合比率は、スイッチングコストが二次的である場合の限られた情報設定において$\max\{\omega(l), \omega(\frac{l}{\sqrt{\mu}})\}$であることが示される。
また,OMGDアルゴリズムは限られた情報設定において最適(順序的に)動的後悔を実現することを示す。
線形切替コストについては、omgdアルゴリズムの競合比上限が問題インスタンスの経路長と二乗経路長の両方に依存することが示され、l, \mu$ に加えて順序的に、オンラインアルゴリズムが達成できる最高の競合比が示される。
その結果,2次切替コストと線形切替コストの最適競争比率は,制限情報設定において根本的に異なることがわかった。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。
この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。
本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-10-31T22:59:23Z) - Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms [11.029788598491077]
エネルギーとサステナビリティの交差点で発生した問題を捉えるオンライン問題の一群である,スイッチングコストによるオンライン変換について検討する。
本稿では,この問題の決定論的および決定論的変異に対して,競合的(ロバストな)しきい値に基づくアルゴリズムを導入する。
そこで我々は,ブラックボックスのアドバイスを活かした学習強化アルゴリズムを提案し,平均ケース性能を著しく向上させた。
論文 参考訳（メタデータ） (2023-10-31T16:34:49Z) - Smoothed Online Convex Optimization Based on Discounted-Normal-Predictor [68.17855675511602]
円滑なオンライン凸最適化(SOCO)のためのオンライン予測戦略について検討する。
提案アルゴリズムは,各区間の切替コストで適応的後悔を最小限に抑えることができることを示す。
論文 参考訳（メタデータ） (2022-05-02T08:48:22Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Online Optimization with Feedback Delay and Nonlinear Switching Cost [16.975704972827305]
我々は,学習者が$k$-round $textitdelayed feedback$$を入力したオンライン最適化のバリエーションについて検討する。
新たな反復正規化オンラインバランスド Descent (iROBD) アルゴリズムは,O(L2k)$の一定次元自由競争比を持つことを示す。
論文 参考訳（メタデータ） (2021-10-29T21:55:01Z) - 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) - Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。
離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
論文 参考訳（メタデータ） (2021-02-07T14:47:19Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。