論文の概要: PRECISION: Decentralized Constrained Min-Max Learning with Low
Communication and Sample Complexities
- arxiv url: http://arxiv.org/abs/2303.02532v1
- Date: Sun, 5 Mar 2023 00:26:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-07 19:10:58.669245
- Title: PRECISION: Decentralized Constrained Min-Max Learning with Low
Communication and Sample Complexities
- Title（参考訳）: プレシジョン:低通信・サンプル複雑性を有する分散制約最小学習
- Authors: Zhuqing Liu, Xin Zhang, Songtao Lu, and Jia Liu
- Abstract要約: min-max最適化問題に対する適応型マルチエージェント学習手法を提案する。
また,反復回数を削減できるPrecisionというアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 25.153506493249854
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Recently, min-max optimization problems have received increasing attention
due to their wide range of applications in machine learning (ML). However, most
existing min-max solution techniques are either single-machine or distributed
algorithms coordinated by a central server. In this paper, we focus on the
decentralized min-max optimization for learning with domain constraints, where
multiple agents collectively solve a nonconvex-strongly-concave min-max saddle
point problem without coordination from any server. Decentralized min-max
optimization problems with domain constraints underpins many important ML
applications, including multi-agent ML fairness assurance, and policy
evaluations in multi-agent reinforcement learning. We propose an algorithm
called PRECISION (proximal gradient-tracking and stochastic recursive variance
reduction) that enjoys a convergence rate of $O(1/T)$, where $T$ is the maximum
number of iterations. To further reduce sample complexity, we propose
PRECISION$^+$ with an adaptive batch size technique. We show that the fast
$O(1/T)$ convergence of PRECISION and PRECISION$^+$ to an $\epsilon$-stationary
point imply $O(\epsilon^{-2})$ communication complexity and
$O(m\sqrt{n}\epsilon^{-2})$ sample complexity, where $m$ is the number of
agents and $n$ is the size of dataset at each agent. To our knowledge, this is
the first work that achieves $O(\epsilon^{-2})$ in both sample and
communication complexities in decentralized min-max learning with domain
constraints. Our experiments also corroborate the theoretical results.
- Abstract（参考訳）: 近年、機械学習(ML)の幅広い応用により、min-max最適化問題が注目されている。
しかし、既存のmin-maxソリューション技術のほとんどは、中央サーバによって調整されたシングルマシンまたは分散アルゴリズムである。
本稿では,複数のエージェントがサーバからの調整なしに,非凸凸凸のmin-maxサドル点問題を一括して解決する,ドメイン制約付き学習のための分散 min-max 最適化に着目した。
ドメイン制約を伴う分極最小最適化問題は、マルチエージェントMLフェアネス保証やマルチエージェント強化学習におけるポリシー評価など、多くの重要なMLアプリケーションを支える。
そこで本研究では, 収束率o(1/t)$を保ち, $t$を最大イテレーション数とする精度(近勾配追跡と確率再帰分散低減)というアルゴリズムを提案する。
サンプルの複雑さをさらに軽減するために,適応型バッチサイズ技術を用いてPreCISION$^+$を提案する。
高速な$O(1/T)$収束のPrecisionおよびPrecision$^+$ to an $\epsilon$-stationary point imply $O(\epsilon^{-2})$通信複雑性と$O(m\sqrt{n}\epsilon^{-2})$サンプル複雑性、$m$はエージェントの数、$n$は各エージェントのデータセットのサイズであることを示す。
私たちの知る限りでは、これはドメイン制約のある分散min-max学習においてサンプルと通信の複雑さの両方において、$o(\epsilon^{-2})$を達成する最初の仕事です。
我々の実験も理論結果と一致している。
関連論文リスト
- Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Optimal Decentralized Smoothed Online Convex Optimization [9.449153668916098]
マルチエージェントSmoothed Online Convex Optimization(SOCO)問題について検討し,通信グラフを通してN$エージェントが対話する。
そこで本研究では,マルチエージェントSOCOのための,真に分散化されたアルゴリズムACORDを提案する。
通信グラフが時間とともに任意かつ適応的に変化する場合でも,我々の結果は維持される。
論文 参考訳（メタデータ） (2024-11-13T05:59:04Z) - 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) - Variance-reduced accelerated methods for decentralized stochastic
double-regularized nonconvex strongly-concave minimax problems [7.5573375809946395]
我々は、ピアツーピア通信により、$m$のコンピューティングエージェントのネットワークが協調すると考えている。
我々のアルゴリズムフレームワークは、二変数のコンセンサス制約を取り除くために、アグラジアン乗算器を導入している。
我々の知る限りでは、これはNCSCミニマックス問題に対する収束保証を、原始変数と双対変数の両方に適用する一般の非正規化器で提供する最初の研究である。
論文 参考訳（メタデータ） (2023-07-14T01:32:16Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Decentralized Riemannian Algorithm for Nonconvex Minimax Problems [82.50374560598493]
ニューラルネットワークのためのミニマックスアルゴリズムは、多くの問題を解決するために開発された。
本稿では,2種類のミニマックスアルゴリズムを提案する。
そこで我々は, DRSGDAを提案し, 本手法が勾配を達成することを証明した。
論文 参考訳（メタデータ） (2023-02-08T01:42:45Z) - INTERACT: Achieving Low Sample and Communication Complexities in
Decentralized Bilevel Learning over Networks [24.02913189682224]
分散化された双方向最適化問題は、ネットワーク機械学習コミュニティで注目を集めている。
低サンプリングと通信の複雑さは、未調査のままである2つの基本的な課題である。
我々の研究は、ネットワーク上の分散化された二段階最適化問題を解決するために、低サンプリングと通信の複雑さの両方を初めて解決した。
論文 参考訳（メタデータ） (2022-07-27T04:19:28Z) - Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with
Near-Optimal Sample Complexity and Communication Complexity [13.100926925535578]
マルチエージェントオフポリシーTD学習のための2つの分散型TD補正(TDC)アルゴリズムを開発しています。
提案アルゴリズムは,エージェントの行動,ポリシー,報酬の完全なプライバシを保持し,サンプリングのばらつきと通信頻度を低減するためにミニバッチサンプリングを採用する。
論文 参考訳（メタデータ） (2021-03-24T12:48:08Z) - The Min-Max Complexity of Distributed Stochastic Convex Optimization
with Intermittent Communication [61.60069865891783]
間欠的通信環境における分散凸最適化(ログファクタまで)の分極的複雑性を解消する。
本稿では、最適なアルゴリズムを確立するための、一致した上限を持つ新しい下界を示す。
論文 参考訳（メタデータ） (2021-02-02T16:18:29Z) - Nonconvex Zeroth-Order Stochastic ADMM Methods with Lower Function Query
Complexity [109.54166127479093]
ゼロ次法(ゼロ次法、英: Zeroth-order method)は、機械学習問題を解決するための効果的な最適化手法のクラスである。
本稿では,非有限項問題を解くために,より高速なゼロ階交互勾配法乗算器 (MMADMM) を提案する。
我々は、ZOMMAD法が、$epsilon$-stationary pointを見つけるために、より低い関数$O(frac13nfrac1)$を達成することができることを示す。
同時に、より高速なゼロオーダーオンラインADM手法(M)を提案する。
論文 参考訳（メタデータ） (2019-07-30T02:21:43Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。