論文の概要: Communication-efficient distributed eigenspace estimation

• arxiv url: http://arxiv.org/abs/2009.02436v2
• Date: Fri, 30 Apr 2021 22:43:50 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-21 20:51:50.812437
• Title: Communication-efficient distributed eigenspace estimation
• Title（参考訳）: 通信効率のよい分散固有空間推定
• Authors: Vasileios Charisopoulos, Austin R. Benson, Anil Damle
• Abstract要約: 我々は,データ行列の先頭不変部分空間を計算するための通信効率のよい分散アルゴリズムを開発した。 提案アルゴリズムは局所解と参照解の間のプロクリスト距離を最小化する新しいアライメント方式を用いる。 本アルゴリズムは,集中型推定器と同様の誤差率を示す。
• 参考スコア（独自算出の注目度）: 31.69089186688224
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Distributed computing is a standard way to scale up machine learning and data science algorithms to process large amounts of data. In such settings, avoiding communication amongst machines is paramount for achieving high performance. Rather than distribute the computation of existing algorithms, a common practice for avoiding communication is to compute local solutions or parameter estimates on each machine and then combine the results; in many convex optimization problems, even simple averaging of local solutions can work well. However, these schemes do not work when the local solutions are not unique. Spectral methods are a collection of such problems, where solutions are orthonormal bases of the leading invariant subspace of an associated data matrix, which are only unique up to rotation and reflections. Here, we develop a communication-efficient distributed algorithm for computing the leading invariant subspace of a data matrix. Our algorithm uses a novel alignment scheme that minimizes the Procrustean distance between local solutions and a reference solution, and only requires a single round of communication. For the important case of principal component analysis (PCA), we show that our algorithm achieves a similar error rate to that of a centralized estimator. We present numerical experiments demonstrating the efficacy of our proposed algorithm for distributed PCA, as well as other problems where solutions exhibit rotational symmetry, such as node embeddings for graph data and spectral initialization for quadratic sensing.
• Abstract（参考訳）: 分散コンピューティングは、大量のデータを処理するために機械学習とデータサイエンスアルゴリズムをスケールアップする標準的な方法である。 このような環境では、マシン間の通信を避けることが、高性能を実現する上で最重要である。 既存のアルゴリズムの計算を分散するのではなく、各マシン上の局所解やパラメータ推定を計算し、結果を組み合わせることが一般的な手法であり、多くの凸最適化問題では、局所解の単純な平均化さえもうまく機能する。 しかし、これらのスキームは局所解が一意でない場合は機能しない。 スペクトル法はそのような問題の集合であり、解は関連するデータ行列の主不変部分空間の正規直交基底であり、これは回転と反射にのみ一意である。 本稿では,データ行列の先頭不変部分空間を計算するための通信効率のよい分散アルゴリズムを提案する。 提案アルゴリズムは,局所解と参照解とのプロクラステアン距離を最小化し,単一ラウンドの通信のみを必要とする新しいアライメント方式を用いる。 主成分分析(PCA)の重要事例について,本アルゴリズムは集中推定器と同様の誤差率を達成することを示す。 本稿では,分散PCAにおける提案アルゴリズムの有効性を示す数値実験と,グラフデータのノード埋め込みや2次センシングのスペクトル初期化など,解が回転対称性を示す問題について述べる。

関連論文リスト

• Distributed Linear Regression with Compositional Covariates [5.085889377571319]
  大規模合成データにおける分散スパースペナル化線形ログコントラストモデルに着目する。 2つの異なる制約凸最適化問題を解くために2つの分散最適化手法を提案する。 分散化されたトポロジでは、通信効率の高い正規化推定値を得るための分散座標ワイド降下アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2023-10-21T11:09:37Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap は、ワーッサーシュタイン空間の低次元構造を明らかにするための計算可能なアルゴリズムである。 我々は,LOT Wassmapが正しい埋め込みを実現し,サンプルサイズの増加とともに品質が向上することを示す。 また、LOT Wassmapがペア距離計算に依存するアルゴリズムと比較して計算コストを大幅に削減することを示す。
  論文  参考訳（メタデータ） (2023-02-14T22:12:16Z)
• On Accelerating Distributed Convex Optimizations [0.0]
  本稿では,分散マルチエージェント凸最適化問題について検討する。 提案アルゴリズムは, 従来の勾配偏光法よりも収束率を向上し, 線形収束することを示す。 実ロジスティック回帰問題の解法として,従来の分散アルゴリズムと比較して,アルゴリズムの性能が優れていることを示す。
  論文  参考訳（メタデータ） (2021-08-19T13:19:54Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• A Linearly Convergent Algorithm for Distributed Principal Component Analysis [12.91948651812873]
  本稿では,1時間スケール分散pcaアルゴリズムである分散sanger's algorithm(dsa)を提案する。 提案アルゴリズムは真の解の近傍に線形収束することを示した。
  論文  参考訳（メタデータ） (2021-01-05T00:51:14Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• FedPD: A Federated Learning Framework with Optimal Rates and Adaptivity to Non-IID Data [59.50904660420082]
  フェデレートラーニング(FL)は、分散データから学ぶための一般的なパラダイムになっています。 クラウドに移行することなく、さまざまなデバイスのデータを効果的に活用するために、Federated Averaging(FedAvg)などのアルゴリズムでは、"Computation then aggregate"(CTA)モデルを採用している。
  論文  参考訳（メタデータ） (2020-05-22T23:07:42Z)
• Optimization in Machine Learning: A Distribution Space Approach [16.038814087205143]
  本稿では,機械学習における最適化問題は,関数空間上の凸関数を最小化するものとして解釈されることが多い。 空間分布における凸最適化問題と同様に、適切な緩和によってそのような問題を再現する。 本研究では,混合分布に基づく数値アルゴリズムを開発し,分布空間で直接近似最適化を行う。
  論文  参考訳（メタデータ） (2020-04-18T13:38:06Z)
• Channel Assignment in Uplink Wireless Communication using Machine Learning Approach [54.012791474906514]
  本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。 我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。 計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
  論文  参考訳（メタデータ） (2020-01-12T15:54:20Z)

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

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