論文の概要: On Riemannian Gradient-Based Methods for Minimax Problems
- arxiv url: http://arxiv.org/abs/2010.06097v4
- Date: Mon, 25 Apr 2022 21:33:03 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-07 23:22:16.015715
- Title: On Riemannian Gradient-Based Methods for Minimax Problems
- Title（参考訳）: ミニマックス問題に対するリーマン勾配法について
- Authors: Feihu Huang, Shangqian Gao
- Abstract要約: ミニマックス問題を解くためのリーマン的手法のクラスを提案する。
我々はRGDAが$tildeO(kappa4eps-3)$であることを示す。
また、Acc-RSGDAが$tildeO(kappa4eps-3)$に対してより低いサンプル複雑性を実現することも示しています。
- 参考スコア（独自算出の注目度）: 24.199289678553896
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In the paper, we study a class of useful minimax optimization problems on
Riemanian manifolds and propose a class of Riemanian gradient-based methods to
solve these minimax problems. Specifically, we propose a Riemannian gradient
descent ascent (RGDA) algorithm for the deterministic minimax optimization.
Moreover, we prove that our RGDA has a sample complexity of
$O(\kappa^2\epsilon^{-2})$ for finding an $\epsilon$-stationary point of the
nonconvex strongly-concave minimax problems, where $\kappa$ denotes the
condition number. At the same time, we introduce a Riemannian stochastic
gradient descent ascent (RSGDA) algorithm for the stochastic minimax
optimization. In the theoretical analysis, we prove that our RSGDA can achieve
a sample complexity of $O(\kappa^4\epsilon^{-4})$. To further reduce the sample
complexity, we propose an accelerated Riemannian stochastic gradient descent
ascent (Acc-RSGDA) algorithm based on the variance-reduced technique. We prove
that our Acc-RSGDA algorithm achieves a lower sample complexity of
$\tilde{O}(\kappa^{4}\epsilon^{-3})$. Extensive experimental results on the
robust distributional optimization and Deep Neural Networks (DNNs) training
over Stiefel manifold demonstrate efficiency of our algorithms.
- Abstract（参考訳）: 本稿では、リーマン多様体上の有用なミニマックス最適化問題のクラスを考察し、これらのミニマックス問題を解くためのリーマン勾配に基づく手法のクラスを提案する。
具体的には,決定論的最小値最適化のためのRGDAアルゴリズムを提案する。
さらに、我々の rgda は、非凸強凸ミニマックス問題の $\epsilon$-stationary point を見つけるために $o(\kappa^2\epsilon^{-2}) のサンプル複雑性を持つことを証明し、ここで $\kappa$ は条件数を表す。
同時に, 確率的ミニマックス最適化のために, リーマン確率勾配勾配降下上昇 (rsgda) アルゴリズムを導入する。
理論解析において、我々のRSGDAが$O(\kappa^4\epsilon^{-4})$のサンプル複雑性を達成できることを示す。
サンプルの複雑さをさらに軽減するために,分散還元法に基づくRiemann的確率勾配勾配上昇(Acc-RSGDA)アルゴリズムを提案する。
acc-rsgdaアルゴリズムは、$\tilde{o}(\kappa^{4}\epsilon^{-3})$という低いサンプル複雑性を達成することを証明します。
stiefel多様体上のロバスト分布最適化とディープニューラルネットワーク(dnns)トレーニングに関する広範な実験結果から,アルゴリズムの効率性が証明された。
関連論文リスト
- Solving a Class of Non-Convex Minimax Optimization in Federated Learning [84.98927714326908]
ミニマックス問題は、機械学習のトレーニングから大規模学習まで、機械学習アプリケーション全体にわたって発生する。
本稿では,非ミニマックス問題 (emphi) に対するアルゴリズムのクラスを提案し,複雑性を$varepsilon-6)$に減らした。
我々は、FedSGDA-Mが$O(kappa2-3)$と$O(kappa2-3)$の最もよく知られた通信量を持つことを示す。
論文 参考訳（メタデータ） (2023-10-05T15:48:41Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - Accelerated Proximal Alternating Gradient-Descent-Ascent for Nonconvex
Minimax Machine Learning [12.069630105460766]
AltGDA(Alternating Table-descentascent)は、様々な機械学習アプリケーションで広く使われている計算最適化アルゴリズムである。
本論文では,最小限の最適化問題を解くために,単一ループの高速なループ勾配計算アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-22T04:33:27Z) - AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax
Optimization [104.96004056928474]
本稿では,非コンケーブ最小値問題に対する高速適応勾配降下法を提案する。
我々は,本手法が,ミニバッチサイズが$O(kappa2.5epsilon-3)$のより低いサンプル複雑性に達することを示す。
論文 参考訳（メタデータ） (2021-06-30T14:47:09Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。