論文の概要: Acceleration in Distributed Optimization Under Similarity
- arxiv url: http://arxiv.org/abs/2110.12347v1
- Date: Sun, 24 Oct 2021 04:03:00 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-31 17:22:33.203801
- Title: Acceleration in Distributed Optimization Under Similarity
- Title（参考訳）: 類似性を考慮した分散最適化の高速化
- Authors: Ye Tian, Gesualdo Scutari, Tianyu Cao, Alexander Gasnikov
- Abstract要約: 集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
- 参考スコア（独自算出の注目度）: 72.54787082152278
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study distributed (strongly convex) optimization problems over a network
of agents, with no centralized nodes. The loss functions of the agents are
assumed to be similar, due to statistical data similarity or otherwise. In
order to reduce the number of communications to reach a solution accuracy, we
proposed a preconditioned, accelerated distributed method. An
$\varepsilon$-solution is achieved in
$\tilde{\mathcal{O}}\big(\sqrt{\frac{\beta/\mu}{(1-\rho)}}\log1/\varepsilon\big)$
number of communications steps, where $\beta/\mu$ is the relative condition
number between the global and local loss functions, and $\rho$ characterizes
the connectivity of the network. This rate matches (up to poly-log factors) for
the first time lower complexity communication bounds of distributed
gossip-algorithms applied to the class of problems of interest. Numerical
results show significant communication savings with respect to existing
accelerated distributed schemes, especially when solving ill-conditioned
problems.
- Abstract（参考訳）: 集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
エージェントの損失関数は、統計データの類似性などにより類似していると仮定される。
解決精度を達成するための通信数を削減するため,プリコンディショナブルで高速化された分散手法を提案する。
$\varepsilon$-solutionは$\tilde{\mathcal{O}}\big(\sqrt{\frac{\beta/\mu}{(1-\rho)}}\log1/\varepsilon\big)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)低い複雑性の通信境界と一致する。
数値計算の結果,既存の分散スキーム,特に条件の悪い問題を解く場合において,通信の節約効果が顕著であることがわかった。
関連論文リスト
- Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
通信ネットワークのノード間で分散的に格納された凸関数の総和を最小化するタスクについて検討する。
この問題を解決するのに必要な分散通信数と(サブ)漸進計算の下位境界が確立されている。
我々は,これらの下界に適合する最初の最適アルゴリズムを開発し,既存の最先端技術と比較して理論性能を著しく向上させる。
論文 参考訳（メタデータ） (2024-05-28T10:28:45Z) - Rate Analysis of Coupled Distributed Stochastic Approximation for Misspecified Optimization [0.552480439325792]
パラメトリックな特徴を持つ不完全な情報を持つ分散最適化問題として$n$のエージェントを考える。
本稿では,各エージェントが未知パラメータの現在の信念を更新する分散近似アルゴリズムを提案する。
アルゴリズムの性能に影響を与える因子を定量的に解析し、決定変数の平均二乗誤差が$mathcalO(frac1nk)+mathcalOleft(frac1sqrtn (1-rho_w)right)frac1k1.5で有界であることを証明する。
論文 参考訳（メタデータ） (2024-04-21T14:18:49Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization [36.777745196161035]
本稿では,分散合成(平滑+非平滑)最適化のための通信効率の良いMG-Skipを提案する。
MG-Skipは通信の複雑さを最適に達成し,非滑らかなセットアップにおけるローカル更新の利点を確認する。
論文 参考訳（メタデータ） (2023-12-19T05:13:16Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Distributed gradient-based optimization in the presence of dependent
aperiodic communication [4.34720256795424]
反復分散最適化アルゴリズムは、グローバルな目的を最小化/最大化するために、時間とともに相互に通信する複数のエージェントを含む。
信頼できない通信網の存在下では、受信したデータの鮮度を測定するAOI( Age-of-Information)は、大きくなり、アルゴリズムの収束を妨げる可能性がある。
AoIプロセスに付随する確率変数が有限な第一モーメントを持つ確率変数に支配されている場合、収束が保証されることを示す。
論文 参考訳（メタデータ） (2022-01-27T06:44:04Z) - High-Dimensional Inference over Networks: Linear Convergence and
Statistical Guarantees [20.701475313495884]
エージェントネットワーク上の疎線形回帰を非指向グラフとしてモデル化し,サーバノードを持たない。
分布予測勾配追跡に基づくアルゴリズムの収束率と統計的保証を解析する。
論文 参考訳（メタデータ） (2022-01-21T01:26:08Z) - On Accelerating Distributed Convex Optimizations [0.0]
本稿では,分散マルチエージェント凸最適化問題について検討する。
提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。
実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
論文 参考訳（メタデータ） (2021-08-19T13:19:54Z) - Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
与えられたサブ最適度$epsilon0$は、$Omegabigのマスター/ワーカーネットワークで達成されることを示す。
次に,ネットワークの下位の型(ログオーバまで)に適合するアルゴリズムを提案する。
頑健なロジスティック回帰問題に対して提案アルゴリズムの有効性を評価する。
論文 参考訳（メタデータ） (2021-07-22T14:25:16Z) - A Linearly Convergent Algorithm for Decentralized Optimization: Sending
Less Bits for Free! [72.31332210635524]
分散最適化手法は、中央コーディネータを使わずに、機械学習モデルのデバイス上でのトレーニングを可能にする。
ランダム化圧縮演算子を適用し,通信ボトルネックに対処する新しいランダム化一階法を提案する。
本手法は,ベースラインに比べて通信数の増加を伴わずに問題を解くことができることを示す。
論文 参考訳（メタデータ） (2020-11-03T13:35:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。