論文の概要: Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees
- arxiv url: http://arxiv.org/abs/2408.12505v1
- Date: Thu, 22 Aug 2024 16:00:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-23 13:12:21.494770
- Title: Stochastic Compositional Minimax Optimization with Provable Convergence Guarantees
- Title（参考訳）: 確率収束保証を用いた確率的構成最小値最適化
- Authors: Yuyang Deng, Fuli Qiao, Mehrdad Mahdavi,
- Abstract要約: 合成ミニマックス問題は、機械学習において存在するが、このクラスの問題の収束に関してのみ確立されている。
本稿では,ミニマックス損失を合成構造で最適化するミニマックス問題の形式的定義を提案する。
- 参考スコア（独自算出の注目度）: 14.301500851291989
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic compositional minimax problems are prevalent in machine learning, yet there are only limited established on the convergence of this class of problems. In this paper, we propose a formal definition of the stochastic compositional minimax problem, which involves optimizing a minimax loss with a compositional structure either in primal , dual, or both primal and dual variables. We introduce a simple yet effective algorithm, stochastically Corrected stOchastic gradient Descent Ascent (CODA), which is a descent ascent type algorithm with compositional correction steps, and establish its convergence rate in aforementioned three settings. In the presence of the compositional structure in primal, the objective function typically becomes nonconvex in primal due to function composition. Thus, we consider the nonconvex-strongly-concave and nonconvex-concave settings and show that CODA can efficiently converge to a stationary point. In the case of composition on the dual, the objective function becomes nonconcave in the dual variable, and we demonstrate convergence in the strongly-convex-nonconcave and convex-nonconcave setting. In the case of composition on both variables, the primal and dual variables may lose convexity and concavity, respectively. Therefore, we anaylze the convergence in weakly-convex-weakly-concave setting. We also give a variance reduction version algorithm, CODA+, which achieves the best known rate on nonconvex-strongly-concave and nonconvex-concave compositional minimax problem. This work initiates the theoretical study of the stochastic compositional minimax problem on various settings and may inform modern machine learning scenarios such as domain adaptation or robust model-agnostic meta-learning.
- Abstract（参考訳）: 確率的合成ミニマックス問題は機械学習で広く用いられているが、この種の問題の収束に関してのみ確立されている。
本稿では,主成分,双対変数,あるいは主成分,双対変数のいずれにおいても,構成構造を用いて最小値の損失を最適化する確率的構成最小値問題の形式的定義を提案する。
構成補正ステップを持つ降下昇降型アルゴリズムである、確率論的に補正された stOchastic gradient Descent Ascent (CODA) という単純なアルゴリズムを導入し、上記の3つの設定で収束率を確立する。
主成分の組成構造の存在下では、目的関数は典型的には機能組成によって主成分の非凸となる。
したがって、非凸凸・非凸凹の設定を考慮し、CODAが定常点に効率的に収束できることを示す。
双対上の合成の場合、目的関数は双対変数において非凸となり、強凸非凸および凸非凹の設定における収束を示す。
両方の変数の合成の場合、原始変数と双対変数はそれぞれ凸度と凹度を失う。
したがって、弱凸弱凸凸凸集合における収束を解析する。
また,非凸凸と非凸凸凹の合成ミニマックス問題において,最もよく知られた値が得られる分散低減バージョンCODA+を提案する。
この研究は、様々な設定における確率的合成ミニマックス問題の理論的研究を開始し、ドメイン適応や頑健なモデルに依存しないメタラーニングのような現代の機械学習シナリオを知らせる可能性がある。
関連論文リスト
- Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization [20.093236438944718]
我々は非線形ミニマックス問題に対処する新しい勾配法を開発した。
提案手法は,他の手法と同等の結果が得られることを示す。
論文 参考訳（メタデータ） (2024-10-29T17:47:22Z) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T02:19:39Z) - Decentralized gradient descent maximization method for composite
nonconvex strongly-concave minimax problems [7.5573375809946395]
定常的非平滑項の両方にフォーカスできるNCSCミニマックス問題を解くための最初の試みを行う。
提案アルゴリズムは,ミニマックス問題の新たな再構成に基づいて設計されている。
論文 参考訳（メタデータ） (2023-04-05T13:54:43Z) - Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization [108.35402316802765]
本稿では,新しい一階最適化アルゴリズムであるAcceleratedGradient-OptimisticGradient (AG-OG) Ascentを提案する。
我々はAG-OGが様々な設定に対して最適収束率(定数まで)を達成することを示す。
アルゴリズムを拡張して設定を拡張し、bi-SC-SCとbi-C-SCの両方で最適な収束率を達成する。
論文 参考訳（メタデータ） (2022-10-31T17:59:29Z) - FEDNEST: Federated Bilevel, Minimax, and Compositional Optimization [53.78643974257301]
多くの現代のML問題は、ミニマックスと合成最適化を仮定したネストされた双レベルプログラミングに該当する。
我々は、一般的なネスト問題に対処するフェデレーション付き交互勾配法を提案する。
論文 参考訳（メタデータ） (2022-05-04T17:48:55Z) - Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax
Problems [80.46370778277186]
大規模凸凹型ミニマックス問題は、ゲーム理論、堅牢なトレーニング、生成的敵ネットワークのトレーニングなど、多くの応用で発生する。
通信効率のよい分散外グレードアルゴリズムであるLocalAdaSientを開発した。
サーバモデル。
等質な環境と異質な環境の両方において,その有効性を実証する。
論文 参考訳（メタデータ） (2021-06-18T09:42:05Z) - Stability and Generalization of Stochastic Gradient Methods for Minimax
Problems [71.60601421935844]
多くの機械学習問題は、GAN(Generative Adversarial Networks)のようなミニマックス問題として定式化できる。
ミニマックス問題に対するトレーニング勾配法から例を包括的に一般化解析する。
論文 参考訳（メタデータ） (2021-05-08T22:38:00Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax
Problems [26.24895953952318]
我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。
また、単一または2つのミニバッチ誘導体でも機能する。
論文 参考訳（メタデータ） (2020-06-27T03:05:18Z) - Inexact and Stochastic Generalized Conditional Gradient with Augmented
Lagrangian and Proximal Step [2.0196229393131726]
我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。
これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。
ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
論文 参考訳（メタデータ） (2020-05-11T14:52:16Z) - Global Convergence and Variance-Reduced Optimization for a Class of
Nonconvex-Nonconcave Minimax Problems [39.13924898972611]
非minimaxewicz問題は、生成的対向ネットワークと対向学習の応用において頻繁に現れる。
一定の大きさのGDAアルゴリズムは凸設定でも潜在的に分岐する可能性がある。
AGDAアルゴリズムは、サブレートに達する速度でグローバルに収束する。
論文 参考訳（メタデータ） (2020-02-22T04:20:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。