論文の概要: Distributed Extra-gradient with Optimal Complexity and Communication Guarantees

• arxiv url: http://arxiv.org/abs/2308.09187v1
• Date: Thu, 17 Aug 2023 21:15:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-21 15:27:59.002429
• Title: Distributed Extra-gradient with Optimal Complexity and Communication Guarantees
• Title（参考訳）: 最適複雑性と通信保証を備えた分散超勾配
• Authors: Ali Ramezani-Kebrya and Kimon Antonakopoulos and Igor Krawczuk and Justin Deschenaux and Volkan Cevher
• Abstract要約: 複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
• 参考スコア（独自算出の注目度）: 60.571030754252824
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider monotone variational inequality (VI) problems in multi-GPU settings where multiple processors/workers/clients have access to local stochastic dual vectors. This setting includes a broad range of important problems from distributed convex minimization to min-max and games. Extra-gradient, which is a de facto algorithm for monotone VI problems, has not been designed to be communication-efficient. To this end, we propose a quantized generalized extra-gradient (Q-GenX), which is an unbiased and adaptive compression method tailored to solve VIs. We provide an adaptive step-size rule, which adapts to the respective noise profiles at hand and achieve a fast rate of ${\mathcal O}(1/T)$ under relative noise, and an order-optimal ${\mathcal O}(1/\sqrt{T})$ under absolute noise and show distributed training accelerates convergence. Finally, we validate our theoretical results by providing real-world experiments and training generative adversarial networks on multiple GPUs.
• Abstract（参考訳）: 複数のプロセッサ/ワーカー/クライアントが局所確率的双対ベクトルにアクセス可能なマルチGPU設定におけるモノトン変分不等式(VI)問題を考察する。 この設定は、分散凸最小化からmin-maxやゲームまで、幅広い重要な問題を含んでいる。 モノトーンvi問題のデファクトアルゴリズムであるextreme-gradientは、通信効率が良いように設計されていない。 そこで本研究では,VIの解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配(Q-GenX)を提案する。 本稿では,各ノイズプロファイルに適応し,相対雑音下では${\mathcal O}(1/T)$,絶対雑音下では${\mathcal O}(1/\sqrt{T})$,絶対雑音下ではオーダー最適の${\mathcal O}(1/\sqrt{T})$を実現し,分散トレーニングが収束を促進する適応的なステップサイズルールを提案する。 最後に,実世界実験を行い,複数のgpu上で生成型逆ネットワークを訓練することにより,理論結果を検証する。

関連論文リスト

• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Variance-reduced accelerated methods for decentralized stochastic double-regularized nonconvex strongly-concave minimax problems [7.5573375809946395]
  我々は、ピアツーピア通信により、$m$のコンピューティングエージェントのネットワークが協調すると考えている。 我々のアルゴリズムフレームワークは、二変数のコンセンサス制約を取り除くために、アグラジアン乗算器を導入している。 我々の知る限りでは、これはNCSCミニマックス問題に対する収束保証を、原始変数と双対変数の両方に適用する一般の非正規化器で提供する最初の研究である。
  論文  参考訳（メタデータ） (2023-07-14T01:32:16Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• Private optimization in the interpolation regime: faster rates and hardness results [9.405458160620533]
  プライベートでない凸最適化では、勾配法は非補間法よりも、全てのサンプル損失を同時に最小化する解が存在するという問題にはるかに早く収束する。 プライベートサンプルの複雑さは指数関数的に改善した(近辺)。
  論文  参考訳（メタデータ） (2022-10-31T05:18:27Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  構成問題の複雑さを軽減するために,MSVR (Multi-block-probe Variance Reduced) という新しい手法を提案する。 本研究の結果は, 試料の複雑さの順序や強靭性への依存など, 様々な面で先行して改善された。
  論文  参考訳（メタデータ） (2022-07-18T12:03:26Z)
• Decentralized Gossip-Based Stochastic Bilevel Optimization over Communication Networks [42.76623191830371]
  本稿では,ゴシップに基づく分散二段階最適化アルゴリズムを提案する。 エージェントはネットワークと外部の両方の問題を一度に解くことができる。 我々のアルゴリズムは最先端の効率とテスト精度を達成する。
  論文  参考訳（メタデータ） (2022-06-22T06:38:54Z)
• Distributed stochastic proximal algorithm with random reshuffling for non-smooth finite-sum optimization [28.862321453597918]
  非滑らかな有限サム最小化は機械学習の基本的な問題である。 本稿では,確率的リシャフリングを用いた分散近位勾配アルゴリズムを開発し,その問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-11-06T07:29:55Z)
• Local AdaGrad-Type Algorithm for Stochastic Convex-Concave Minimax Problems [80.46370778277186]
  大規模凸凹型ミニマックス問題は、ゲーム理論、堅牢なトレーニング、生成的敵ネットワークのトレーニングなど、多くの応用で発生する。 通信効率のよい分散外グレードアルゴリズムであるLocalAdaSientを開発した。 サーバモデル。 等質な環境と異質な環境の両方において,その有効性を実証する。
  論文  参考訳（メタデータ） (2021-06-18T09:42:05Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  テュバコフ雑音の存在下でのハーフスペースの学習可能性について検討する。 真半空間に関して誤分類誤差$epsilon$を達成するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2020-06-11T14:25:02Z)
• A conditional one-output likelihood formulation for multitask Gaussian processes [0.0]
  マルチタスクガウス過程(MTGP)は多出力回帰問題に対するガウスプロセスフレームワークの解である。 本稿では,マルチタスク学習を簡略化する新しい手法を提案する。 現状の美術品と計算的に競合していることが示される。
  論文  参考訳（メタデータ） (2020-06-05T14:59:06Z)

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

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