論文の概要: Communication-Efficient Distributed SVD via Local Power Iterations
- arxiv url: http://arxiv.org/abs/2002.08014v4
- Date: Fri, 4 Jun 2021 08:37:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-30 13:35:42.842041
- Title: Communication-Efficient Distributed SVD via Local Power Iterations
- Title（参考訳）: ローカル電力イテレーションによる通信効率の高い分散svd
- Authors: Xiang Li, Shusen Wang, Kun Chen, Zhihua Zhang
- Abstract要約: 通信効率を向上させるために,texttLocalPower というアルゴリズムを開発した。
texttLocalPower の有効性を示す実験を行った。
- 参考スコア（独自算出の注目度）: 33.95814240875917
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study distributed computing of the truncated singular value decomposition
problem. We develop an algorithm that we call \texttt{LocalPower} for improving
communication efficiency. Specifically, we uniformly partition the dataset
among $m$ nodes and alternate between multiple (precisely $p$) local power
iterations and one global aggregation. In the aggregation, we propose to weight
each local eigenvector matrix with orthogonal Procrustes transformation (OPT).
As a practical surrogate of OPT, sign-fixing, which uses a diagonal matrix with
$\pm 1$ entries as weights, has better computation complexity and stability in
experiments. We theoretically show that under certain assumptions
\texttt{LocalPower} lowers the required number of communications by a factor of
$p$ to reach a constant accuracy. We also show that the strategy of
periodically decaying $p$ helps obtain high-precision solutions. We conduct
experiments to demonstrate the effectiveness of \texttt{LocalPower}.
- Abstract（参考訳）: 停止特異値分解問題の分散計算について検討する。
我々は,通信効率を向上させるために,texttt{LocalPower} と呼ぶアルゴリズムを開発した。
具体的には、データセットを$m$ノードに一様に分割し、複数の(以前は$p$)ローカルパワーイテレーションと1つのグローバルアグリゲーションの間で代用します。
本研究では,各固有ベクトル行列を直交プロクルス変換(opt)により重み付けする手法を提案する。
OPTの実用的なサロゲートとして、$\pm 1$エントリを重みとして対角行列を使用する符号固定は、実験において計算複雑性と安定性が向上する。
理論的には、ある仮定の下では、texttt{LocalPower} は一定精度に達するために必要な通信回数を$p$の係数で減少させる。
また、周期的に崩壊する$p$の戦略が高精度な解を得るのに役立つことを示す。
我々は, \texttt{localpower} の有効性を示す実験を行う。
関連論文リスト
- Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。
我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
論文 参考訳（メタデータ） (2024-09-04T03:41:44Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
与えられた分布を平均で最もよく近似するRUMを求める一般化時間アルゴリズムを求める。
我々の理論的結果は、実世界のデータセットに効果的でスケール可能なものを得るという、実践的な結果も得られます。
論文 参考訳（メタデータ） (2023-05-22T17:43:34Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - An Improved Analysis of Gradient Tracking for Decentralized Machine
Learning [34.144764431505486]
トレーニングデータが$n$エージェントに分散されるネットワーク上での分散機械学習を検討する。
エージェントの共通の目標は、すべての局所損失関数の平均を最小化するモデルを見つけることである。
ノイズのない場合、$p$を$mathcalO(p-1)$から$mathcalO(p-1)$に改善します。
論文 参考訳（メタデータ） (2022-02-08T12:58:14Z) - DoCoM: Compressed Decentralized Optimization with Near-Optimal Sample
Complexity [25.775517797956237]
本稿では,Douubly Compressed Momentum-assisted tracking algorithm $ttDoCoM$ for communicationを提案する。
我々のアルゴリズムは、実際にいくつかの最先端のアルゴリズムより優れていることを示す。
論文 参考訳（メタデータ） (2022-02-01T07:27:34Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - 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) - FedPower: Privacy-Preserving Distributed Eigenspace Estimation [38.17106202734679]
我々は,フェデレートラーニング(FL)フレームワーク内で,textsfFedPowerと呼ばれるアルゴリズムのクラスを提案する。
textsfFedPowerは、複数のローカルパワーイテレーションとグローバルアグリゲーションステップを交互に行うことで、よく知られたパワーメソッドを活用する。
ガウス雑音, 並列化, ローカルマシンのランダムサンプリングの影響に応じて, 異なる解釈可能な項からなるテキストfFedPowerの収束境界を提供する。
論文 参考訳（メタデータ） (2021-03-01T02:33:20Z) - Debiasing Distributed Second Order Optimization with Surrogate Sketching
and Scaled Regularization [101.5159744660701]
分散第2次最適化において、標準的な戦略は、データの小さなスケッチやバッチに基づいて、多くの局所的な見積もりを平均化することである。
本稿では,分散二階法における収束率の理論的および実証的改善を両立させるため,局所的な推定を嫌悪する新しい手法を提案する。
論文 参考訳（メタデータ） (2020-07-02T18:08:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。