論文の概要: Best of Both Worlds: Stochastic and Adversarial Convex Function Chasing
- arxiv url: http://arxiv.org/abs/2311.00181v1
- Date: Tue, 31 Oct 2023 22:59:23 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-02 15:34:31.728526
- Title: Best of Both Worlds: Stochastic and Adversarial Convex Function Chasing
- Title（参考訳）: 両世界のベスト:確率的および逆向きの凸関数追跡
- Authors: Neelkamal Bhuyan, Debankur Mukherjee, Adam Wierman
- Abstract要約: 我々は,CFC問題と敵環境について検討し,両環境における性能保証を同時に達成するアルゴリズムを提案する。
最適に近い性能を同時に達成しつつ、頑健な対角性能が得られるベスト・オブ・ザ・ワールドズアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 10.619901778151334
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Convex function chasing (CFC) is an online optimization problem in which
during each round $t$, a player plays an action $x_t$ in response to a hitting
cost $f_t(x_t)$ and an additional cost of $c(x_t,x_{t-1})$ for switching
actions. We study the CFC problem in stochastic and adversarial environments,
giving algorithms that achieve performance guarantees simultaneously in both
settings. Specifically, we consider the squared $\ell_2$-norm switching costs
and a broad class of quadratic hitting costs for which the sequence of
minimizers either forms a martingale or is chosen adversarially. This is the
first work that studies the CFC problem using a stochastic framework. We
provide a characterization of the optimal stochastic online algorithm and,
drawing a comparison between the stochastic and adversarial scenarios, we
demonstrate that the adversarial-optimal algorithm exhibits suboptimal
performance in the stochastic context. Motivated by this, we provide a
best-of-both-worlds algorithm that obtains robust adversarial performance while
simultaneously achieving near-optimal stochastic performance.
- Abstract（参考訳）: コンベックス関数追跡(CFC)は、各ラウンド$t$の間、プレイヤーが攻撃コスト$f_t(x_t)$と追加コスト$c(x_t,x_{t-1})$に応じてアクション$x_t$をプレイするオンライン最適化問題である。
確率的, 対角的環境におけるCFC問題について検討し, 両設定で同時に性能保証を実現するアルゴリズムを提案する。
具体的には、二乗の$\ell_2$-norm スイッチングコストと、最小化器の列がマルティンゲールを形成するか、逆向きに選択される幅広い二次打撃コストを考える。
これは確率的フレームワークを用いてCFC問題を研究する最初の研究である。
本稿では, 最適確率オンラインアルゴリズムの特徴と, 確率的シナリオと敵対的シナリオの比較から, 逆最適化アルゴリズムが確率的文脈において準最適性能を示すことを示す。
そこで本研究では,最適に近い確率的性能を同時に達成しながら,頑健な対向性能を得る最善の両世界アルゴリズムを提案する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。