論文の概要: 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)を考える。
通信と局所的な繰り返しの両方に対してより低い複雑性境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。
我々のアルゴリズムは、分散化確率論だけでなく、分散化決定論や非分散化確率論においても最も優れた文献である。
実験により,提案アルゴリズムの有効性が確認された。
関連論文リスト
- 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 [31.914106871373857]
分散変分不等式問題(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 [137.6408511310322]
変分不等式は平衡探索から逆学習まで様々な応用で使われている。
ほとんどの分散アプローチには、通信コストという大きなボトルネックがあります。
通信ラウンドの総数と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]
バイレベルプログラミングは、その幅広い応用のために、最近この文献で注目を集めている。
基礎となる双レベル最適化問題は、1台のマシンか、星型ネットワークに接続された複数のマシンのどちらかによって解決される。
本稿では,このクラスの最適化問題を理論的に保証したペナルティ関数に基づく分散アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-11-08T08:39:30Z) - Decentralized Local Stochastic Extra-Gradient for Variational
Inequalities [125.62877849447729]
我々は、不均一(非IID)で多くのデバイスに分散する問題データを持つ領域上での分散変分不等式(VIs)を考察する。
我々は、完全に分散化された計算の設定を網羅する計算ネットワークについて、非常に一般的な仮定を行う。
理論的には, モノトン, モノトンおよび非モノトンセッティングにおける収束速度を理論的に解析する。
論文 参考訳(メタデータ) (2021-06-15T17:45:51Z) - Second-Order Guarantees in Centralized, Federated and Decentralized
Nonconvex Optimization [64.26238893241322]
単純なアルゴリズムは、多くの文脈において優れた経験的結果をもたらすことが示されている。
いくつかの研究は、非最適化問題を研究するための厳密な分析的正当化を追求している。
これらの分析における重要な洞察は、摂動が局所的な降下アルゴリズムを許容する上で重要な役割を担っていることである。
論文 参考訳(メタデータ) (2020-03-31T16:54:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。