論文の概要: Decentralized Riemannian Algorithm for Nonconvex Minimax Problems
- arxiv url: http://arxiv.org/abs/2302.03825v1
- Date: Wed, 8 Feb 2023 01:42:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-09 17:44:01.637169
- Title: Decentralized Riemannian Algorithm for Nonconvex Minimax Problems
- Title（参考訳）: 非凸ミニマックス問題に対する分散リーマンアルゴリズム
- Authors: Xidong Wu, Zhengmian Hu and Heng Huang
- Abstract要約: ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
- 参考スコア（独自算出の注目度）: 82.50374560598493
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The minimax optimization over Riemannian manifolds (possibly nonconvex
constraints) has been actively applied to solve many problems, such as robust
dimensionality reduction and deep neural networks with orthogonal weights
(Stiefel manifold). Although many optimization algorithms for minimax problems
have been developed in the Euclidean setting, it is difficult to convert them
into Riemannian cases, and algorithms for nonconvex minimax problems with
nonconvex constraints are even rare. On the other hand, to address the big data
challenges, decentralized (serverless) training techniques have recently been
emerging since they can reduce communications overhead and avoid the bottleneck
problem on the server node. Nonetheless, the algorithm for decentralized
Riemannian minimax problems has not been studied. In this paper, we study the
distributed nonconvex-strongly-concave minimax optimization problem over the
Stiefel manifold and propose both deterministic and stochastic minimax methods.
The local model is non-convex strong-concave and the Steifel manifold is a
non-convex set. The global function is represented as the finite sum of local
functions. For the deterministic setting, we propose DRGDA and prove that our
deterministic method achieves a gradient complexity of $O( \epsilon^{-2})$
under mild conditions. For the stochastic setting, we propose DRSGDA and prove
that our stochastic method achieves a gradient complexity of
$O(\epsilon^{-4})$. The DRGDA and DRSGDA are the first algorithms for
distributed minimax optimization with nonconvex constraints with exact
convergence. Extensive experimental results on the Deep Neural Networks (DNNs)
training over the Stiefel manifold demonstrate the efficiency of our
algorithms.
- Abstract（参考訳）: リーマン多様体上のミニマックス最適化(おそらく非凸制約)は、ロバスト次元の縮小や直交重みを持つディープニューラルネットワーク(スティフェル多様体)のような多くの問題を解決するために積極的に適用されてきた。
ユークリッド環境ではミニマックス問題の最適化アルゴリズムが数多く開発されているが、それらをリーマンケースに変換することは困難であり、非凸制約付きミニマックス問題のアルゴリズムはさらに稀である。
一方で、ビッグデータの課題に対処するために、通信オーバーヘッドを削減し、サーバノードのボトルネック問題を回避するために、分散(サーバーレス)トレーニング技術が最近登場している。
それでも分散リーマンミニマックス問題のアルゴリズムは研究されていない。
本稿では,スタイフェル多様体上の分散非凸強凸ミニマックス最適化問題を研究し,決定論的および確率的ミニマックス法を提案する。
局所モデルは非凸強凸であり、ステイフェル多様体は非凸集合である。
大域関数は局所関数の有限和として表現される。
決定論的設定のために、DRGDAを提案し、決定論的手法が穏やかな条件下で$O( \epsilon^{-2})$の勾配複雑性を達成することを証明した。
確率的設定に対しては、DSSGDAを提案し、我々の確率的手法が$O(\epsilon^{-4})$の勾配複雑性を達成することを証明する。
DRGDAとDRSGDAは、厳密な収束を伴う非凸制約を持つ分散ミニマックス最適化のための最初のアルゴリズムである。
stiefel多様体上のディープニューラルネットワーク(dnns)トレーニングに関する広範な実験結果から,アルゴリズムの効率性が証明された。
関連論文リスト
- Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。
我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文 参考訳（メタデータ） (2024-08-21T20:14:54Z) - 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) - Can Decentralized Stochastic Minimax Optimization Algorithms Converge
Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。
本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-24T02:19:39Z) - Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax
Problems [39.197569803430646]
最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。
近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
論文 参考訳（メタデータ） (2023-04-21T11:38:41Z) - Decentralized Weakly Convex Optimization Over the Stiefel Manifold [28.427697270742947]
我々は分散環境でスティーフェル多様体に焦点をあて、$nMn log-1)$のエージェントの連結ネットワークをテストする。
そこで本研究では,nMn log-1 以下の自然ステーションを強制的に強制する分散下位段階法 (DRSM)$ という手法を提案する。
論文 参考訳（メタデータ） (2023-03-31T02:56:23Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - On Riemannian Gradient-Based Methods for Minimax Problems [24.199289678553896]
ミニマックス問題を解くためのリーマン的手法のクラスを提案する。
我々はRGDAが$tildeO(kappa4eps-3)$であることを示す。
また、Acc-RSGDAが$tildeO(kappa4eps-3)$に対してより低いサンプル複雑性を実現することも示しています。
論文 参考訳（メタデータ） (2020-10-13T00:54:00Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。