論文の概要: Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities

• arxiv url: http://arxiv.org/abs/2302.07615v2
• Date: Sat, 30 Mar 2024 15:00:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-02 16:13:48.299280
• Title: Similarity, Compression and Local Steps: Three Pillars of Efficient Communications for Distributed Variational Inequalities
• Title（参考訳）: 類似性・圧縮・局所ステップ:分散変分不等式のための効率的なコミュニケーションの3つの柱
• Authors: Aleksandr Beznosikov, Martin Takáč, Alexander Gasnikov,
• Abstract要約: 変分不等式は平衡探索から逆学習まで様々な応用で用いられている。 ほとんどの分散アプローチには、通信コストというボトルネックがあります。 通信ラウンドの総数と1ラウンドのコストを削減する3つの主要な手法は、ローカル関数の類似性、送信された情報の圧縮、ローカル更新である。 本稿では,通信複雑性の理論的保証が最良であり,分散変動不等式に対する他の手法よりもはるかに優れていることを示す。
• 参考スコア（独自算出の注目度）: 91.12425544503395
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variational inequalities are a broad and flexible class of problems that includes minimization, saddle point, and fixed point problems as special cases. Therefore, variational inequalities are used in various applications ranging from equilibrium search to adversarial learning. With the increasing size of data and models, today's instances demand parallel and distributed computing for real-world machine learning problems, most of which can be represented as variational inequalities. Meanwhile, most distributed approaches have a significant bottleneck - the cost of communications. The three main techniques to reduce the total number of communication rounds and the cost of one such round are the similarity of local functions, compression of transmitted information, and local updates. In this paper, we combine all these approaches. Such a triple synergy did not exist before for variational inequalities and saddle problems, nor even for minimization problems. The methods presented in this paper have the best theoretical guarantees of communication complexity and are significantly ahead of other methods for distributed variational inequalities. The theoretical results are confirmed by adversarial learning experiments on synthetic and real datasets.
• Abstract（参考訳）: 変分不等式(英: variational inequality)は、極小化、サドル点、固定点問題を含む、広範かつ柔軟な問題のクラスである。 そのため、平衡探索から逆学習まで様々な応用で変分不等式が用いられている。 データやモデルのサイズが大きくなるにつれて、今日のインスタンスは現実の機械学習問題に対して並列コンピューティングと分散コンピューティングを必要とし、そのほとんどは変分不等式として表現できる。 一方、ほとんどの分散アプローチは通信コストという大きなボトルネックを抱えています。 通信ラウンドの総数と1ラウンドのコストを削減する3つの主要な手法は、ローカル関数の類似性、送信された情報の圧縮、ローカル更新である。 本稿では,これらすべてのアプローチを組み合わせる。 このような三重シナジーは、変分不等式やサドル問題、あるいは最小化問題に対しても以前には存在しなかった。 本稿では,通信複雑性の理論的保証が最良であり,分散変動不等式に対する他の手法よりもはるかに優れていることを示す。 理論的結果は、合成データセットと実データセットの逆学習実験によって確認される。

関連論文リスト

• Accelerated Stochastic ExtraGradient: Mixing Hessian and Gradient Similarity to Reduce Communication in Distributed and Federated Learning [50.382793324572845]
  分散コンピューティングはデバイス間の通信を伴うため、効率性とプライバシという2つの重要な問題を解決する必要がある。 本稿では,データ類似性とクライアントサンプリングのアイデアを取り入れた新しい手法について分析する。 プライバシー問題に対処するために,付加雑音の手法を適用し,提案手法の収束への影響を解析する。
  論文  参考訳（メタデータ） (2024-09-22T00:49:10Z)
• Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updates [28.700663352789395]
  分散変分不等式問題(VIP)に対する通信効率の良い局所訓練手法の統一収束解析を提供する。 提案手法は,いくつかの新しい局所学習アルゴリズムの提案と解析を可能にする推定値に関する一般的な鍵となる仮定に基づいている。 異種データにおける分散変分不等式を解くために,通信複雑性の向上を図った最初の局所降下偏差アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-08T10:58:46Z)
• SARAH-based Variance-reduced Algorithm for Stochastic Finite-sum Cocoercive Variational Inequalities [137.6408511310322]
  有限サムコヒーレンシブ変分不等式の問題を考える。 強い単調な問題に対しては、この方法を用いて解への線形収束を達成することができる。
  論文  参考訳（メタデータ） (2022-10-12T08:04:48Z)
• Compression and Data Similarity: Combination of Two Techniques for Communication-Efficient Solving of Distributed Variational Inequalities [137.6408511310322]
  本稿では、圧縮とデータ類似性という2つの一般的なアプローチの組み合わせについて考察する。 この相乗効果は, 分散分散単調変分不等式の解法において, それぞれ別々に行う方法よりも効果的であることを示す。
  論文  参考訳（メタデータ） (2022-06-19T16:38:56Z)
• Distributed Newton-Type Methods with Communication Compression and Bernoulli Aggregation [11.870393751095083]
  曲率情報に対する同調圧縮と集約機構について検討する。 適応しきい値処理やベルヌーイ集約といった新しい3PC機構は、通信の低減と時折ヘッセン計算を必要とする。 全ての方法について、高速条件数非依存の局所線型および/または超線型収束率を導出する。
  論文  参考訳（メタデータ） (2022-06-07T21:12:21Z)
• Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
  この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。 通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。 我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
  論文  参考訳（メタデータ） (2022-02-06T13:14:02Z)
• Distributed Methods with Compressed Communication for Solving Variational Inequalities, with Theoretical Guarantees [115.08148491584997]
  本稿では,MASHA1 と MASHA2 の圧縮通信による変分不等式とサドル点問題の解法について理論的に検討した。 新しいアルゴリズムは双方向圧縮をサポートし、バッチの設定や、クライアントの部分的な参加を伴うフェデレーション学習のために修正することもできる。
  論文  参考訳（メタデータ） (2021-10-07T10:04:32Z)

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

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