論文の概要: Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization
- arxiv url: http://arxiv.org/abs/2410.22297v1
- Date: Tue, 29 Oct 2024 17:47:22 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-30 13:40:02.585483
- Title: Shuffling Gradient-Based Methods for Nonconvex-Concave Minimax Optimization
- Title（参考訳）: 非凸凹最小値最適化のための勾配法シャッフル法
- Authors: Quoc Tran-Dinh, Trang H. Tran, Lam M. Nguyen,
- Abstract要約: 我々は非線形ミニマックス問題に対処する新しい勾配法を開発した。
提案手法は,他の手法と同等の結果が得られることを示す。
- 参考スコア（独自算出の注目度）: 20.093236438944718
- License:
- Abstract: This paper aims at developing novel shuffling gradient-based methods for tackling two classes of minimax problems: nonconvex-linear and nonconvex-strongly concave settings. The first algorithm addresses the nonconvex-linear minimax model and achieves the state-of-the-art oracle complexity typically observed in nonconvex optimization. It also employs a new shuffling estimator for the "hyper-gradient", departing from standard shuffling techniques in optimization. The second method consists of two variants: semi-shuffling and full-shuffling schemes. These variants tackle the nonconvex-strongly concave minimax setting. We establish their oracle complexity bounds under standard assumptions, which, to our best knowledge, are the best-known for this specific setting. Numerical examples demonstrate the performance of our algorithms and compare them with two other methods. Our results show that the new methods achieve comparable performance with SGD, supporting the potential of incorporating shuffling strategies into minimax algorithms.
- Abstract（参考訳）: 本稿では,非凸線と非凸線という2種類のミニマックス問題に対処するシャッフル勾配に基づく新しい手法を開発することを目的とする。
最初のアルゴリズムは非凸線形ミニマックスモデルに対処し、非凸最適化でよく見られる最先端のオラクルの複雑さを実現する。
また、最適化における標準的なシャッフル技術から離れ、"ハイパーグラディエント"のための新しいシャッフル推定器も採用している。
第2の方法は、半シャッフルスキームと完全シャッフルスキームの2つの変種からなる。
これらの変種は非凸強凸ミニマックス設定に取り組む。
私たちは、それらのオラクルの複雑性境界を標準的な仮定の下で確立し、私たちの最良の知識は、この特定の設定で最もよく知られている。
数値的な例はアルゴリズムの性能を示し、他の2つの手法と比較する。
提案手法は,SGDと同等の性能を示し,シャッフル戦略をミニマックスアルゴリズムに組み込む可能性を支持する。
関連論文リスト
- Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
本稿では,アルゴリズムが検索対象関数の雑音評価にのみアクセス可能な2次スムーズかつ強い凸関数を最適化する問題を考察する。
本研究は, ミニマックス単純後悔率について, 一致した上界と下界を発達させることにより, 初めて厳密な評価を行ったものである。
論文 参考訳（メタデータ） (2024-06-28T02:56:22Z) - Optimal Guarantees for Algorithmic Reproducibility and Gradient
Complexity in Convex Optimization [55.115992622028685]
以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。
最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
論文 参考訳（メタデータ） (2023-10-26T19:56:52Z) - Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax
Problems [39.197569803430646]
最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。
近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
論文 参考訳（メタデータ） (2023-04-21T11:38:41Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Efficient Methods for Structured Nonconvex-Nonconcave Min-Max
Optimization [98.0595480384208]
定常点に収束する一般化外空間を提案する。
このアルゴリズムは一般の$p$ノルド空間だけでなく、一般の$p$次元ベクトル空間にも適用される。
論文 参考訳（メタデータ） (2020-10-31T21:35:42Z) - Conditional Gradient Methods for Convex Optimization with General Affine
and Nonlinear Constraints [8.643249539674612]
本稿では,一般アフィンおよび非線形制約を用いた凸最適化問題に対する条件勾配法を提案する。
まず、スムーズかつ構造化された非滑らかな関数制約凸最適化に対して、$cal O (1/epsilon2)$の反復複雑性を達成できる新しい制約外挿条件勾配(CoexCG)法を提案する。
さらに,制約外挿法と二重正規化条件勾配法(CoexDurCG)の新たな変種を開発した。
論文 参考訳（メタデータ） (2020-06-30T23:49:38Z) - Hybrid Variance-Reduced SGD Algorithms For Nonconvex-Concave Minimax
Problems [26.24895953952318]
我々は,非ガンスミニマックス問題のクラスを解くアルゴリズムを開発した。
また、単一または2つのミニバッチ誘導体でも機能する。
論文 参考訳（メタデータ） (2020-06-27T03:05:18Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved
Complexities [21.13934071954103]
本稿では,非インワンテキスト変数 Descent に対する決定論的アルゴリズムを提案する。
SGC仮定の下では,アルゴリズムの複雑さが既存のアルゴリズムの複雑さと一致していることが示される。
結果はオラクル・テキストZO-GDMSAで示され、数値実験により理論的結果が裏付けられる。
論文 参考訳（メタデータ） (2020-01-22T00:05:14Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。