論文の概要: Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes
- arxiv url: http://arxiv.org/abs/2406.02939v1
- Date: Wed, 5 Jun 2024 04:54:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-06 19:59:32.885572
- Title: Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes
- Title（参考訳）: Adaptive Stepsizes を用いた分散ミニマックス最適化のためのニア最適収束の実現
- Authors: Yan Huang, Xiang Li, Yipeng Shen, Niao He, Jinming Xu,
- Abstract要約: 分散ミニマックス問題に直接適応的手法を適用することで,非収束性が得られることを示す。
追跡追跡プロトコルを用いた分散分散分散ミニマックス法であるD-AdaSTを提案する。
- 参考スコア（独自算出の注目度）: 22.022674600775993
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we show that applying adaptive methods directly to distributed minimax problems can result in non-convergence due to inconsistency in locally computed adaptive stepsizes. To address this challenge, we propose D-AdaST, a Distributed Adaptive minimax method with Stepsize Tracking. The key strategy is to employ an adaptive stepsize tracking protocol involving the transmission of two extra (scalar) variables. This protocol ensures the consistency among stepsizes of nodes, eliminating the steady-state error due to the lack of coordination of stepsizes among nodes that commonly exists in vanilla distributed adaptive methods, and thus guarantees exact convergence. For nonconvex-strongly-concave distributed minimax problems, we characterize the specific transient times that ensure time-scale separation of stepsizes and quasi-independence of networks, leading to a near-optimal convergence rate of $\tilde{\mathcal{O}} \left( \epsilon ^{-\left( 4+\delta \right)} \right)$ for any small $\delta > 0$, matching that of the centralized counterpart. To our best knowledge, D-AdaST is the first distributed adaptive method achieving near-optimal convergence without knowing any problem-dependent parameters for nonconvex minimax problems. Extensive experiments are conducted to validate our theoretical results.
- Abstract（参考訳）: 本稿では,分散ミニマックス問題に適応的手法を直接適用することにより,局所的に計算された適応段階における不整合による非収束が生じることを示す。
そこで我々はD-AdaSTを提案する。D-AdaSTはStepsize Trackingを用いた分散適応ミニマックス法である。
鍵となる戦略は、2つの余分な(スカラー)変数の送信を含む適応的なステップサイズ追跡プロトコルを使用することである。
このプロトコルは、ノードの段差間の整合性を保証し、バニラ分散適応法に存在するノード間の段差の調整の欠如による定常誤差を排除し、正確な収束を保証する。
非凸-強凸分散ミニマックス問題に対しては、ステップサイズの時間スケールの分離とネットワークの準独立性を保証し、ほぼ最適収束率$\tilde{\mathcal{O}} \left( \epsilon ^{-\left(4+\delta \right)} \right)$を任意の小さな$\delta > 0$に対して設定する。
我々の知る限り、D-AdaSTは非凸ミニマックス問題に対する問題依存パラメータを知らずにほぼ最適収束を達成する最初の分散適応手法である。
我々の理論結果を検証するために大規模な実験を行った。
関連論文リスト
- Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax
Problems [39.197569803430646]
最小限の最適化は、敵対的ネットワーク(GAN)や敵対的トレーニングなど、多くの機械学習タスクにおいて重要な役割を果たす。
近年,ミニマックス問題の解法として多種多様な最適化手法が提案されているが,そのほとんどは分散設定を無視している。
論文 参考訳（メタデータ） (2023-04-21T11:38:41Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - TiAda: A Time-scale Adaptive Algorithm for Nonconvex Minimax
Optimization [24.784754071913255]
適応的手法は、パラメータに依存しない方法でハエの段差を調整する能力を示した。
非凹極小問題に対する勾配上昇の電流収束解析にはパラメータの注意深くチューニングが必要である。
論文 参考訳（メタデータ） (2022-10-31T17:05:36Z) - DR-DSGD: A Distributionally Robust Decentralized Learning Algorithm over
Graphs [54.08445874064361]
本稿では,分散環境下での正規化された分散ロバストな学習問題を解くことを提案する。
Kullback-Liebler正規化関数をロバストなmin-max最適化問題に追加することにより、学習問題を修正されたロバストな問題に還元することができる。
提案アルゴリズムは, 最低分布検定精度を最大10%向上できることを示す。
論文 参考訳（メタデータ） (2022-08-29T18:01:42Z) - Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and
Beyond [63.59034509960994]
シャッフルに基づく変種(ミニバッチと局所ランダムリシャッフル)について検討する。
ポリアック・ロジャシエヴィチ条件を満たす滑らかな函数に対して、これらのシャッフル型不変量(英語版)(shuffling-based variants)がそれらの置換式よりも早く収束することを示す収束境界を得る。
我々は, 同期シャッフル法と呼ばれるアルゴリズムの修正を提案し, ほぼ均一な条件下では, 下界よりも収束速度が速くなった。
論文 参考訳（メタデータ） (2021-10-20T02:25:25Z) - Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax
Problems [80.46370778277186]
大規模凸凹型ミニマックス問題は、ゲーム理論、堅牢なトレーニング、生成的敵ネットワークのトレーニングなど、多くの応用で発生する。
通信効率のよい分散外グレードアルゴリズムであるLocalAdaSientを開発した。
サーバモデル。
等質な環境と異質な環境の両方において,その有効性を実証する。
論文 参考訳（メタデータ） (2021-06-18T09:42:05Z) - An improved convergence analysis for decentralized online stochastic
non-convex optimization [17.386715847732468]
本稿では,GT-Loakjasiewics(GT-Loakjasiewics)と呼ばれる手法が,GT-Loakjasiewics(GT-Loakjasiewics)が現在の収束率を満たすことを示す。
結果はすぐに適用できるだけでなく、現在知られている最高の収束率にも適用できる。
論文 参考訳（メタデータ） (2020-08-10T15:29:13Z) - Balancing Rates and Variance via Adaptive Batch-Size for Stochastic
Optimization Problems [120.21685755278509]
本研究は,ステップサイズの減衰が正確な収束に必要であるという事実と,一定のステップサイズがエラーまでの時間でより速く学習するという事実のバランスをとることを目的とする。
ステップサイズのミニバッチを最初から修正するのではなく,パラメータを適応的に進化させることを提案する。
論文 参考訳（メタデータ） (2020-07-02T16:02:02Z) - Adaptive Gradient Methods Converge Faster with Over-Parameterization
(but you should do a line-search) [32.24244211281863]
データを補間するのに十分なパラメータ化モデルを用いて、スムーズで凸的な損失を簡易に設定する。
一定のステップサイズと運動量を持つ AMSGrad がより高速な$O(1/T)$レートで最小値に収束することを証明する。
これらの手法により,タスク間の適応勾配法の収束と一般化が向上することを示す。
論文 参考訳（メタデータ） (2020-06-11T21:23:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。