論文の概要: Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization
- arxiv url: http://arxiv.org/abs/2311.00181v2
- Date: Sun, 24 Mar 2024 01:13:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-27 02:35:50.852796
- Title: Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization
- Title（参考訳）: Smoothed Online Quadratic Optimization における両世界のベストプラクティス
- Authors: Neelkamal Bhuyan, Debankur Mukherjee, Adam Wierman,
- Abstract要約: 各ラウンド$t$において、プレイヤーが2次的打撃コストと2次攻撃コストに応じてアクション$x_tをプレイし、アクションを切り替えるための2乗$ell$-normコストを加算する、スムーズなオンライン最適化(SOQO)問題について検討する。
この問題クラスは、スマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインと強いつながりを持っています。
本稿では, 最適に近い性能を同時に達成しつつ, 強健な対角性能を得るベスト・オブ・ザ・ワールドス・アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 9.449153668916098
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the smoothed online quadratic optimization (SOQO) problem where, at each round $t$, a player plays an action $x_t$ in response to a quadratic hitting cost and an additional squared $\ell_2$-norm cost for switching actions. This problem class has strong connections to a wide range of application domains including smart grid management, adaptive control, and data center management, where switching-efficient algorithms are highly sought after. We study the SOQO problem in both adversarial and stochastic settings, and in this process, perform the first stochastic analysis of this class of problems. We provide the online optimal algorithm when the minimizers of the hitting cost function evolve as a general stochastic process, which, for the case of martingale process, takes the form of a distribution-agnostic dynamic interpolation algorithm (LAI). Next, we present the stochastic-adversarial trade-off by proving an $\Omega(T)$ expected regret for the adversarial optimal algorithm in the literature (ROBD) with respect to LAI and, a sub-optimal competitive ratio for LAI in the adversarial setting. Finally, we present a best-of-both-worlds algorithm that obtains a robust adversarial performance while simultaneously achieving a near-optimal stochastic performance.
- Abstract（参考訳）: オンライン2次最適化(SOQO)問題について検討し、各ラウンドの$t$において、プレイヤーが2次打込みコストと2次打込みコストに応じてアクション$x_t$をプレイし、さらに2次打込みコストとして$\ell_2$-normを加算する。
この問題クラスは、スイッチング効率の高いアルゴリズムが要求されるスマートグリッド管理、適応制御、データセンター管理など、幅広いアプリケーションドメインに強く結びついている。
本稿では, 対角的, 確率的双方においてSOQO問題について検討し, このプロセスにおいて, この種の問題の最初の確率論的解析を行う。
本稿では,打撃コスト関数の最小化が一般的な確率過程として進化する際のオンライン最適アルゴリズムについて,マルティンゲール過程の場合,分布に依存しない動的補間アルゴリズム(LAI)の形式を採る。
次に、LAIに関する文献(ROBD)における対向最適アルゴリズムに対する$\Omega(T)$期待の後悔を証明し、対向的な設定におけるLAIの準最適競合比を示す。
最後に,確率的に近い確率的性能を同時に達成しつつ,強健な対角性能を得るベスト・オブ・ザ・ワールドスアルゴリズムを提案する。
関連論文リスト
- Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback [34.7178680288326]
Stradi et al.(2024) は、マルコフ決定過程に制約のある最初のベスト・オブ・ボス・ワールドズ・アルゴリズムを提案した。
本稿では,CMDPにおける帯域幅フィードバックを用いたベスト・オブ・ワールドズ・アルゴリズムを提案する。
本アルゴリズムは政策最適化手法に基づいており, 占有率に基づく手法よりも効率的である。
論文 参考訳（メタデータ） (2024-10-03T07:44:40Z) - Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
本稿では,次数$tildemathcalO(mathrmpoly(H)sqrtSAT)$の残差を求めるアルゴリズムを提案する。
提案したアルゴリズムと分析は、占有対策によって与えられる典型的なツールを完全に回避する。
論文 参考訳（メタデータ） (2024-07-08T08:06:45Z) - Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。
我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
論文 参考訳（メタデータ） (2024-01-04T00:57:33Z) - Stochastic Optimal Control Matching [53.156277491861985]
最適制御のための新しい反復拡散最適化(IDO)技術である最適制御マッチング(SOCM)を導入する。
この制御は、一致するベクトル場に適合しようとすることで、最小二乗問題を通じて学習される。
実験により,本アルゴリズムは最適制御のための既存のすべての IDO 手法よりも低い誤差を実現する。
論文 参考訳（メタデータ） (2023-12-04T16:49:43Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳（メタデータ） (2021-07-02T16:21:52Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - 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) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Constrained Multiagent Rollout and Multidimensional Assignment with the
Auction Algorithm [0.0]
本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。
提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。
コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
論文 参考訳（メタデータ） (2020-02-18T07:09:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。