論文の概要: Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- arxiv url: http://arxiv.org/abs/2610.41927v1
- Date: Fri, 30 Oct 2026 15:54:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-02 22:05:31.799703
- Title: Variance Reduction for Decentralized Stochastic Optimization with Multiple Local Updates
- Title（参考訳）: 複数の局所更新による分散確率最適化のばらつき低減
- Abstract要約: 本稿では,分散の低減と複数の局所的な更新を融合した,原始双対型分散最適化アルゴリズムを提案する。
我々の知る限り、複数の局所的な更新を伴う分散最適化を期待する最初の線形収束保証を確立する。
- 参考スコア（独自算出の注目度）: 9.530815102146425
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multiple local updates are widely used in decentralized optimization to enhance communication efficiency, often in conjunction with stochastic gradients when exact gradient computation is costly. However, such algorithms generally converge only to a neighborhood of the optimum, whose size depends on the stepsize and the variance of gradient noise. Variance reduction has been incorporated into ADMM-based methods to achieve exact convergence in expectation, but their stepsizes typically scale inversely with both the square root of the network size and the cube of the number of local updates, leading to slow convergence as the network size or the number of local updates increases. In this paper, we propose a novel primal-dual-based decentralized optimization algorithm that integrates variance reduction with multiple local updates, with a stepsize independent of the network size and inversely proportional to the number of local updates (rather than its cube), thereby enabling significantly larger stepsizes and faster convergence. Moreover, to the best of our knowledge, we establish the first linear convergence guarantee in expectation for decentralized optimization with multiple local updates under stochastic gradients in the strongly convex setting. Beyond the theoretical guarantee, the proposed method exchanges only one variable per round, halving the communication cost compared with gradient-tracking-based methods. Numerical experiments further demonstrate its advantages in convergence speed and accuracy.
- Abstract（参考訳）: 複数の局所的な更新は、通信効率を高めるために分散化された最適化に広く使われ、しばしば正確な勾配計算がコストがかかるときの確率的勾配と連動する。
しかし、そのようなアルゴリズムは一般に、ステップサイズと勾配ノイズのばらつきに依存する最適の近傍にのみ収束する。
予測の正確な収束を達成するために、ADMMベースの手法にばらつき低減法が組み込まれているが、そのステップサイズは通常、ネットワークサイズの平方根とローカル更新数の立方体の両方で逆スケールし、ネットワークサイズやローカル更新の数が増えるにつれて収束が遅くなる。
本稿では,ネットワークサイズに依存しないステップサイズと,ローカル更新数(立方体ではなく)に比例したステップサイズで分散低減と複数のローカル更新を一体化して,より大きなステップサイズと高速収束を実現する,プリミティブデュアル型分散最適化アルゴリズムを提案する。
さらに,我々の知識を最大限に活用するために,強い凸条件下での確率勾配の下で複数の局所的な更新を伴う分散最適化を期待する最初の線形収束保証を確立する。
理論的な保証の他に、提案手法は1ラウンドあたり1変数のみを交換し、勾配追従法と比較して通信コストを半減させる。
数値実験は、収束速度と精度の利点をさらに示している。
関連論文リスト
- Accelerated Decentralized Stochastic Gradient Descent for Strongly Convex Optimization [8.185454167395326]
我々は,Nesterov型原始双対とマルチラウンド高速ゴシップ平均化を組み合わせた分散アルゴリズムであるemphMulti-Gossip Accelerated DSGD (MG-ADSGD)を提案する。
キーとなるアイデアは、ゴシップ深さをミニバッチサイズに結合することで、追加の通信ラウンドがコンセンサス精度を向上し、勾配分散を低減することである。
論文 参考訳（メタデータ） (2026-06-05T17:51:11Z) - Local adapt-then-combine algorithms for distributed nonsmooth optimization: Achieving provable communication acceleration [50.67878993903822]
通信効率のよいAdapt-Then-Combine (ATC) フレームワークであるFlexATCを提案する。
ローカル更新がATCベースの分散アルゴリズムの通信高速化につながることを示すのはこれが初めてである。
論文 参考訳（メタデータ） (2026-02-18T02:47:05Z) - Incremental Quasi-Newton Methods with Faster Superlinear Convergence
Rates [50.36933471975506]
各成分関数が強く凸であり、リプシッツ連続勾配とヘシアンを持つ有限和最適化問題を考える。
最近提案されたインクリメンタル準ニュートン法は、BFGSの更新に基づいて、局所的な超線形収束率を達成する。
本稿では、対称ランク1更新をインクリメンタルフレームワークに組み込むことにより、より効率的な準ニュートン法を提案する。
論文 参考訳（メタデータ） (2024-02-04T05:54:51Z) - On the Communication Complexity of Decentralized Bilevel Optimization [40.45379954138305]
本稿では,更新戦略の同時および交互化に基づく2つの新しい分散二段階勾配勾配アルゴリズムを提案する。
我々のアルゴリズムは既存の手法よりも高速な収束率と通信コストを抑えることができる。
このような理論的な結果は、不均一な環境での軽微な仮定で達成されたのはこれが初めてである。
論文 参考訳（メタデータ） (2023-11-19T14:56:26Z) - On Accelerating Distributed Convex Optimizations [0.0]
本稿では,分散マルチエージェント凸最適化問題について検討する。
提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。
実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
論文 参考訳（メタデータ） (2021-08-19T13:19:54Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳（メタデータ） (2021-06-08T15:54:44Z) - The Gradient Convergence Bound of Federated Multi-Agent Reinforcement
Learning with Efficient Communication [20.891460617583302]
連立学習パラダイムにおける協調的意思決定のための独立強化学習(IRL)の検討
FLはエージェントとリモート中央サーバ間の過剰な通信オーバーヘッドを生成する。
本稿では,システムの実用性向上のための2つの高度な最適化手法を提案する。
論文 参考訳（メタデータ） (2021-03-24T07:21:43Z) - ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。
我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。
有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文 参考訳（メタデータ） (2020-08-28T14:46:56Z) - Differentially Private ADMM for Convex Distributed Learning: Improved
Accuracy via Multi-Step Approximation [10.742065340992525]
Alternating Direction Method of Multipliers (ADMM) は分散学習において一般的な計算方法である。
トレーニングデータが機密性のある場合には、交換されたイテレートが深刻なプライバシー上の懸念を引き起こす。
本稿では,様々な凸学習問題に対する精度の向上を図った分散ADMMを提案する。
論文 参考訳（メタデータ） (2020-05-16T07:17:31Z) - Communication-Efficient Distributed Stochastic AUC Maximization with
Deep Neural Networks [50.42141893913188]
本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。
我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。
いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
論文 参考訳（メタデータ） (2020-05-05T18:08:23Z) - A Unified Theory of Decentralized SGD with Changing Topology and Local
Updates [70.9701218475002]
分散通信方式の統一収束解析を導入する。
いくつかの応用に対して普遍収束率を導出する。
私たちの証明は弱い仮定に依存している。
論文 参考訳（メタデータ） (2020-03-23T17:49:15Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。