論文の概要: Breaking the Complexity Barrier in Compositional Minimax Optimization
- arxiv url: http://arxiv.org/abs/2308.09604v1
- Date: Fri, 18 Aug 2023 14:57:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-21 12:49:15.447475
- Title: Breaking the Complexity Barrier in Compositional Minimax Optimization
- Title(参考訳): 合成ミニマックス最適化における複雑性バリアの破壊
- Authors: Jin Liu, Xiaokang Pan, Junwen Duan, Hongdong Li, Youqi Li, Zhe Qu
- Abstract要約: 合成のミニマックス最適化は、機械学習にまたがる重要な課題であるが、未探索の課題である。
現在のテクニックは、最適以下の複雑さを示すか、大きなバッチサイズに大きく依存する。
本稿では,Nested STOchastic Recursive Momentum (NSTORM)を提案する。
- 参考スコア(独自算出の注目度): 50.10952609321302
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Compositional minimax optimization is a pivotal yet under-explored challenge
across machine learning, including distributionally robust training and policy
evaluation for reinforcement learning. Current techniques exhibit suboptimal
complexity or rely heavily on large batch sizes. This paper proposes Nested
STOchastic Recursive Momentum (NSTORM), attaining the optimal sample complexity
of $O(\kappa^3/\epsilon^3)$ for finding an $\epsilon$-accurate solution.
However, NSTORM requires low learning rates, potentially limiting
applicability. Thus we introduce ADAptive NSTORM (ADA-NSTORM) with adaptive
learning rates, proving it achieves the same sample complexity while
experiments demonstrate greater effectiveness. Our methods match lower bounds
for minimax optimization without large batch requirements, validated through
extensive experiments. This work significantly advances compositional minimax
optimization, a crucial capability for distributional robustness and policy
evaluation
- Abstract(参考訳): 合成のミニマックス最適化は、分散的に堅牢なトレーニングと強化学習のためのポリシー評価を含む、機械学習における重要かつ未探索の課題である。
現在のテクニックは、最適以下の複雑さを示すか、大きなバッチサイズに大きく依存する。
本稿では,ネスト付き確率的再帰的運動量(nstorm)を提案する。これは,$\epsilon$-accurate 解を求めるために,$o(\kappa^3/\epsilon^3)$の最適なサンプル複雑性を実現する。
しかし、NSTORMは低い学習率を必要とし、適用性を制限する可能性がある。
そこで,適応学習率を持つADAptive NSTORM(ADA-NSTORM)を導入し,実験結果がより有効であることを示す。
提案手法は, 大規模なバッチ要求を伴わずに最小限の最適化を行うために, 広範囲な実験により検証した。
この研究は、分散ロバスト性および政策評価の重要な能力である構成最小最適化を著しく向上させる
関連論文リスト
- Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling [0.0]
本研究では、連続緩和による勾配に基づく更新と準量子アナリング(QQA)を組み合わせた別のアプローチを提案する。
数値実験により,本手法はiSCOと学習型解法に匹敵する性能を有する汎用解法であることが示された。
論文 参考訳(メタデータ) (2024-09-02T12:55:27Z) - SPABA: A Single-Loop and Probabilistic Stochastic Bilevel Algorithm Achieving Optimal Sample Complexity [5.046146134689904]
SPABAを実装する際には,双レベル最適化と単レベル最適化の間に複雑性解析のギャップがないことが示されている。
本稿では,複雑性解析の状況を改善するために,他の2ループあるいはネストした2レベルアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-05-29T05:36:03Z) - Maximize to Explore: One Objective Function Fusing Estimation, Planning,
and Exploration [87.53543137162488]
我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。
textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。
様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
論文 参考訳(メタデータ) (2023-05-29T17:25:26Z) - Debiasing Conditional Stochastic Optimization [15.901623717313493]
本稿では,ポートフォリオ選択や強化学習,堅牢な学習など,さまざまな応用をカバーする条件因果最適化(CSO)問題について検討する。
有限変量変量CSO問題に対する新しいアルゴリズムを開発し、既存の結果を大幅に改善する。
我々は,本手法が他の最適化問題と同様の課題に対処するための有用なツールとなる可能性があると考えている。
論文 参考訳(メタデータ) (2023-04-20T19:19:55Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳(メタデータ) (2022-11-14T12:32:18Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳(メタデータ) (2022-11-03T12:40:24Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳(メタデータ) (2022-10-08T08:26:22Z) - Minimization of Stochastic First-order Oracle Complexity of Adaptive
Methods for Nonconvex Optimization [0.0]
一階オラクル(SFO)の複雑さの下限と上限を最小化するという意味で、重要なバッチサイズが存在することを証明した。
また、SFOの複雑性が下界と上界に適合するために必要な条件についても検討し、理論的結果を支持する数値的な結果を提供する。
論文 参考訳(メタデータ) (2021-12-14T04:55:04Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳(メタデータ) (2020-03-30T10:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。