論文の概要: 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)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)低い複雑性の通信境界と一致する。
数値計算の結果,既存の分散スキーム,特に条件の悪い問題を解く場合において,通信の節約効果が顕著であることがわかった。
関連論文リスト
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in
Polynomial Time [54.01594785269913]
本稿では, 重み劣化と凸緩和に則った2層ReLUネットワーク間の最適性ギャップについて述べる。
トレーニングデータがランダムである場合、元の問題と緩和の間の相対的な最適性ギャップは、サンプルの勾配によって境界付けられることを示す。
論文 参考訳(メタデータ) (2024-02-06T01:29:35Z) - Compressed Regression over Adaptive Networks [58.79251288443156]
分散エージェントのネットワークによって達成可能な性能を導出し,通信制約や回帰問題を解消し,適応的に解決する。
エージェントによって最適化に必要なパラメータをオンラインで学習できる最適化アロケーション戦略を考案する。
論文 参考訳(メタデータ) (2023-04-07T13:41:08Z) - 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) - DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization [0.0]
DADAOは、L$-smooth と $mu$-strongly convex 関数の和を最小化する最初の分散化、高速化、非同期化、プライマリ化、一階述語アルゴリズムである。
我々のアルゴリズムは、$mathcalO(nsqrtchisqrtfracLmulog(frac1epsilon)$ localと$mathcalO(nsqrtchisqrtfracLmulog()のみを必要とすることを示す。
論文 参考訳(メタデータ) (2022-07-26T08:47:54Z) - 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) - Convergence Analysis of Nonconvex Distributed Stochastic Zeroth-order
Coordinate Method [3.860616339202303]
本稿では,$ZOn$局所コスト関数の合計により形成されるグローバルコスト関数を最小化する分散非最適化問題について検討する。
エージェントは問題を解くためにzo座標法を近似する。
論文 参考訳(メタデータ) (2021-03-24T03:07:46Z) - A Linearly Convergent Algorithm for Decentralized Optimization: Sending
Less Bits for Free! [72.31332210635524]
分散最適化手法は、中央コーディネータを使わずに、機械学習モデルのデバイス上でのトレーニングを可能にする。
ランダム化圧縮演算子を適用し,通信ボトルネックに対処する新しいランダム化一階法を提案する。
本手法は,ベースラインに比べて通信数の増加を伴わずに問題を解くことができることを示す。
論文 参考訳(メタデータ) (2020-11-03T13:35:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。