論文の概要: Optimal Algorithms for Decentralized Stochastic Variational Inequalities

• arxiv url: http://arxiv.org/abs/2202.02771v2
• Date: Sun, 2 Apr 2023 11:46:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-05 01:43:35.080542
• Title: Optimal Algorithms for Decentralized Stochastic Variational Inequalities
• Title（参考訳）: 分散確率変分不等式に対する最適アルゴリズム
• Authors: Dmitry Kovalev, Aleksandr Beznosikov, Abdurakhmon Sadiev, Michael Persiianov, Peter Richt\'arik, Alexander Gasnikov
• Abstract要約: この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。 通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。 我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
• 参考スコア（独自算出の注目度）: 113.43047601775453
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variational inequalities are a formalism that includes games, minimization, saddle point, and equilibrium problems as special cases. Methods for variational inequalities are therefore universal approaches for many applied tasks, including machine learning problems. This work concentrates on the decentralized setting, which is increasingly important but not well understood. In particular, we consider decentralized stochastic (sum-type) variational inequalities over fixed and time-varying networks. We present lower complexity bounds for both communication and local iterations and construct optimal algorithms that match these lower bounds. Our algorithms are the best among the available literature not only in the decentralized stochastic case, but also in the decentralized deterministic and non-distributed stochastic cases. Experimental results confirm the effectiveness of the presented algorithms.
• Abstract（参考訳）: 変分不等式は、特別な場合としてゲーム、最小化、鞍点、平衡問題を含む形式論である。 したがって、変分不等式法は、機械学習問題を含む多くの応用タスクに対して普遍的なアプローチである。 この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。 特に、固定および時間変化ネットワークに対する分散確率変動不等式(sum-type)を考える。 通信と局所的な繰り返しの両方に対してより低い複雑性境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。 我々のアルゴリズムは、分散化確率論だけでなく、分散化決定論や非分散化確率論においても最も優れた文献である。 実験により,提案アルゴリズムの有効性が確認された。

関連論文リスト

• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。 この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。 我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
  論文  参考訳（メタデータ） (2024-05-28T10:28:45Z)
• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  本稿では,分散勾配勾配(D-SGDA)アルゴリズムの一般化境界の複雑さについて検討する。 本研究は,D-SGDAの一般化における各因子の影響を解析した。 また、最適凸凹設定を得るために一般化とバランスをとる。
  論文  参考訳（メタデータ） (2023-10-31T11:27:01Z)
• Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates [28.700663352789395]
  分散変分不等式問題(VIP)に対する通信効率の良い局所訓練手法の統一収束解析を提供する。 提案手法は,いくつかの新しい局所学習アルゴリズムの提案と解析を可能にする推定値に関する一般的な鍵となる仮定に基づいている。 異種データにおける分散変分不等式を解くために,通信複雑性の向上を図った最初の局所降下偏差アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-08T10:58:46Z)
• Can Decentralized Stochastic Minimax Optimization Algorithms Converge Linearly for Finite-Sum Nonconvex-Nonconcave Problems? [56.62372517641597]
  分散化されたミニマックス最適化は、幅広い機械学習に応用されているため、ここ数年で活発に研究されている。 本稿では,非コンカブ問題に対する2つの新しい分散化ミニマックス最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-24T02:19:39Z)
• Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities [91.12425544503395]
  変分不等式は平衡探索から逆学習まで様々な応用で用いられている。 ほとんどの分散アプローチには、通信コストというボトルネックがあります。 通信ラウンドの総数と1ラウンドのコストを削減する3つの主要な手法は、ローカル関数の類似性、送信された情報の圧縮、ローカル更新である。 本稿では,通信複雑性の理論的保証が最良であり,分散変動不等式に対する他の手法よりもはるかに優れていることを示す。
  論文  参考訳（メタデータ） (2023-02-15T12:11:27Z)
• Distributed Stochastic Optimization under a General Variance Condition [13.911633636387059]
  分散最適化は最近、大規模な機械学習問題の解決に効果があるとして、大きな注目を集めている。 我々は、古典的フェデレーション平均化(Avg)を再考し、滑らかな非対象関数に対して、緩やかな分散しか持たない収束結果を確立する。 ほぼ1つの定常収束点も勾配条件の下で成立する。
  論文  参考訳（メタデータ） (2023-01-30T05:48:09Z)
• A Penalty-Based Method for Communication-Efficient Decentralized Bilevel Programming [14.35928967799696]
  本稿では,分散化ネットワーク上での双方向プログラミング問題の解法として,ペナルティ関数に基づく分散化アルゴリズムを提案する。 提案アルゴリズムの重要な特徴は,ペナルティ関数の過度勾配の推定である。 我々の理論的枠組みは、様々な凸条件下での原問題の最適解に漸近的でない収束を保証する。
  論文  参考訳（メタデータ） (2022-11-08T08:39:30Z)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  我々は、不均一(非IID)で多くのデバイスに分散する問題データを持つ領域上での分散変分不等式(VIs)を考察する。 我々は、完全に分散化された計算の設定を網羅する計算ネットワークについて、非常に一般的な仮定を行う。 理論的には, モノトン, モノトンおよび非モノトンセッティングにおける収束速度を理論的に解析する。
  論文  参考訳（メタデータ） (2021-06-15T17:45:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。