論文の概要: Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization
- arxiv url: http://arxiv.org/abs/2408.12209v1
- Date: Thu, 22 Aug 2024 08:35:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-23 14:43:27.613517
- Title: Zeroth-Order Stochastic Mirror Descent Algorithms for Minimax Excess Risk Optimization
- Title（参考訳）: 極小超過リスク最適化のためのゼロ階確率ミラーDescentアルゴリズム
- Authors: Zhihao Gu, Zi Xu,
- Abstract要約: 滑らかかつ非滑らかなMEROに対してゼロ階ミラー降下(ZO-SMD)アルゴリズムを提案する。
提案アルゴリズムは, 最適収束率$mathcalOleft (1/sqrttright)$と$mathcalOleft (1/sqrttright)$を, 滑らかかつ非滑らかなMEROの最適化誤差$で収束することが証明された。
- 参考スコア（独自算出の注目度）: 3.802030070947573
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The minimax excess risk optimization (MERO) problem is a new variation of the traditional distributionally robust optimization (DRO) problem, which achieves uniformly low regret across all test distributions under suitable conditions. In this paper, we propose a zeroth-order stochastic mirror descent (ZO-SMD) algorithm available for both smooth and non-smooth MERO to estimate the minimal risk of each distrbution, and finally solve MERO as (non-)smooth stochastic convex-concave (linear) minimax optimization problems. The proposed algorithm is proved to converge at optimal convergence rates of $\mathcal{O}\left(1/\sqrt{t}\right)$ on the estimate of $R_i^*$ and $\mathcal{O}\left(1/\sqrt{t}\right)$ on the optimization error of both smooth and non-smooth MERO. Numerical results show the efficiency of the proposed algorithm.
- Abstract（参考訳）: ミニマックス超過リスク最適化(MERO)問題は、従来の分散ロバスト最適化(DRO)問題の新たなバリエーションであり、適切な条件下での全てのテスト分布に対する一様に低い後悔を実現する。
本稿では,スムーズかつ非スムーズなMEROにおいて,各分散の最小リスクを推定するために,ゼロ階確率鏡降下(ZO-SMD)アルゴリズムを提案する。
提案アルゴリズムは、R_i^*$ と $\mathcal{O}\left(1/\sqrt{t}\right)$ の最適収束率で収束することが証明された。
計算結果は,提案アルゴリズムの効率性を示す。
関連論文リスト
- Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
複素勾配問題に対する2つの分散化ZO推定器を提案する。
我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
論文 参考訳（メタデータ） (2024-10-03T15:04:01Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。
私たちの分析は単純だが強力だ。
Goldstein-subdifferential set, これは最近の進歩を可能にする。
非滑らかな非最適化
論文 参考訳（メタデータ） (2023-07-10T11:56:04Z) - Efficient Stochastic Approximation of Minimax Excess Risk Optimization [36.68685001551774]
我々はMEROを直接対象とする効率的な近似手法を開発した。
最小リスクの推定誤差に起因するバイアスが制御下にあることを示す。
また,各分布から抽出したサンプルの量が異なる場合の現実的シナリオについても検討し,分布依存収束率を導出する手法を提案する。
論文 参考訳（メタデータ） (2023-05-31T02:21:11Z) - Near-Optimal Algorithms for Making the Gradient Small in Stochastic
Minimax Optimization [14.719077076351377]
本研究では,スムーズなミニマックス最適化のための準定常点を求める問題について検討する。
Recursive IteratioNRAINと呼ばれる新しいアルゴリズムは凸凹と強凹の両方のケースを実現する。
論文 参考訳（メタデータ） (2022-08-11T16:55:26Z) - Mirror Descent Strikes Again: Optimal Stochastic Convex Optimization
under Infinite Noise Variance [17.199063087458907]
我々は一様凸ミラーマップのクラスを用いてミラーDescentアルゴリズムの収束率を定量化する。
このアルゴリズムは明確な勾配クリッピングや正規化を必要としない。
我々は,1次オラクルのみを用いた他のアルゴリズムでは改善率を達成できないことを示す情報理論の下界を補完する。
論文 参考訳（メタデータ） (2022-02-23T17:08:40Z) - 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) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Exploiting Higher Order Smoothness in Derivative-free Optimization and
Continuous Bandits [99.70167985955352]
強凸関数のゼロ次最適化問題について検討する。
予測勾配降下アルゴリズムのランダム化近似を考察する。
その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-14T10:42:23Z) - Convergence of adaptive algorithms for weakly convex constrained
optimization [59.36386973876765]
モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。
我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
論文 参考訳（メタデータ） (2020-06-11T17:43:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。