論文の概要: Correlation Aware Sparsified Mean Estimation Using Random Projection
- arxiv url: http://arxiv.org/abs/2310.18868v1
- Date: Sun, 29 Oct 2023 01:45:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-31 15:52:57.337909
- Title: Correlation Aware Sparsified Mean Estimation Using Random Projection
- Title（参考訳）: ランダム投影を用いた相関認識平均推定
- Authors: Shuli Jiang, Pranay Sharma, Gauri Joshi
- Abstract要約: Rand-$k$スペーシフィケーションは、通信コストを削減するために一般的に使用されるテクニックである。
最近提案されたRand-$k$-Spatial estimatorはサーバのクロスクライアント相関情報を利用してRand-$k$のパフォーマンスを改善する。
クライアントベクトルをランダムな$k$-次元部分空間に投影することにより、Rand-$k$の符号化を一般化する、より柔軟な符号化復号法を提案する。
- 参考スコア（独自算出の注目度）: 22.15205399599895
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We study the problem of communication-efficient distributed vector mean
estimation, a commonly used subroutine in distributed optimization and
Federated Learning (FL). Rand-$k$ sparsification is a commonly used technique
to reduce communication cost, where each client sends $k < d$ of its
coordinates to the server. However, Rand-$k$ is agnostic to any correlations,
that might exist between clients in practical scenarios. The recently proposed
Rand-$k$-Spatial estimator leverages the cross-client correlation information
at the server to improve Rand-$k$'s performance. Yet, the performance of
Rand-$k$-Spatial is suboptimal. We propose the Rand-Proj-Spatial estimator with
a more flexible encoding-decoding procedure, which generalizes the encoding of
Rand-$k$ by projecting the client vectors to a random $k$-dimensional subspace.
We utilize Subsampled Randomized Hadamard Transform (SRHT) as the projection
matrix and show that Rand-Proj-Spatial with SRHT outperforms Rand-$k$-Spatial,
using the correlation information more efficiently. Furthermore, we propose an
approach to incorporate varying degrees of correlation and suggest a practical
variant of Rand-Proj-Spatial when the correlation information is not available
to the server. Experiments on real-world distributed optimization tasks
showcase the superior performance of Rand-Proj-Spatial compared to
Rand-$k$-Spatial and other more sophisticated sparsification techniques.
- Abstract（参考訳）: 本稿では,分散最適化とFederated Learning(FL)においてよく使われるサブルーチンである,通信効率のよい分散ベクトル平均推定の問題について検討する。
rand-$k$ sparsification は、各クライアントがサーバに$k < d$ の座標を送信する通信コストを削減するために一般的に使用されるテクニックである。
しかし、rand-$k$は、実際のシナリオにおいてクライアント間で存在するであろういかなる相関にも無関係である。
最近提案された rand-$k$-spatial estimator はサーバのクライアント間の相関情報を利用して rand-$k$ のパフォーマンスを改善する。
しかし、rand-$k$-spatialのパフォーマンスは最適ではない。
我々はRand-Proj-Spatial estimatorを提案し、Rand-$k$の符号化をランダムな$k$次元部分空間に投影することで一般化する。
サブサンプリングランダム化アダマール変換(SRHT)を投影行列とし,Rand-Proj-SpatialがRand-$k$-Spatialより効率よくRand-$k$-Spatialより優れていることを示す。
さらに,サーバに相関情報が得られない場合に,様々な相関度を組み込む手法を提案し,Rand-Proj-Spatialの実用的な変種を提案する。
実世界の分散最適化タスクの実験では、rand-proj-spatial と rand-$k$-spatial および他のより洗練されたスパーシフィケーション技術と比較して優れた性能を示す。
関連論文リスト
- Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
Transfer $Q*$は、ベースラインモデルを通してターゲット報酬$r$の最適値関数を推定する。
提案手法は, 従来のSoTA法で観測された準最適差を著しく低減する。
論文 参考訳（メタデータ） (2024-05-30T21:36:12Z) - Contextual Linear Optimization with Bandit Feedback [35.692428244561626]
文脈線形最適化(CLO)は、ランダムコスト係数の不確実性を低減するために予測的文脈特徴を用いる。
我々は,帯域幅フィードバックを用いたCLOのためのオフライン学習アルゴリズムのクラスについて検討する。
IERMに対する高速な後悔境界を示し、不特定モデルクラスと最適化推定の柔軟な選択を可能にする。
論文 参考訳（メタデータ） (2024-05-26T13:27:27Z) - DASA: Delay-Adaptive Multi-Agent Stochastic Approximation [64.32538247395627]
我々は,N$エージェントが並列に動作し,中央サーバと通信することで,一般的な近似問題を高速化することを目的とした設定を考える。
遅延とストラグラーの効果を軽減するために,マルチエージェント近似のための遅延適応アルゴリズムである textttDASA を提案する。
論文 参考訳（メタデータ） (2024-03-25T22:49:56Z) - HiRE: High Recall Approximate Top-$k$ Estimation for Efficient LLM
Inference [68.59839755875252]
HiREは2つの新しいコンポーネントから構成される: (i) (i) (i) (i) (i) (i) (i) (i) (i) (i) (ii) DA-TOP-$k$: 効率的なマルチデバイス近似トップ-k$演算子) (i) (i) (i) (i) (i) (i) (i) DA-TOP-$k$演算子) 。
我々は、10億のパラメータモデルにおいて、HiREがソフトマックスとフィードフォワード層の両方に適用され、ほぼ一致した事前学習と下流の精度を実現し、1台のTPUv5eデバイスで1.47Times$の推論遅延を高速化することを示した。
論文 参考訳（メタデータ） (2024-02-14T18:04:36Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Smoothed $f$-Divergence Distributionally Robust Optimization [5.50764401597583]
我々は、特別な種類の分布完全ロバスト最適化(DRO)の定式化が理論的優位性をもたらすと論じる。
DROは、Wasserstein または L'evy-Prokhorov (LP) 距離で滑らかなKullback Leibler (KL) の発散に基づく曖昧性集合を用いる。
論文 参考訳（メタデータ） (2023-06-24T19:22:01Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳（メタデータ） (2023-05-30T16:05:44Z) - Generalized Differentiable RANSAC [95.95627475224231]
$nabla$-RANSACは、ランダム化された堅牢な推定パイプライン全体を学ぶことができる、微分可能なRANSACである。
$nabla$-RANSACは、精度という点では最先端のシステムよりも優れているが、精度は低い。
論文 参考訳（メタデータ） (2022-12-26T15:13:13Z) - Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
本稿では,フェデレートラーニング手法を用いて,オーバー・ザ・エアラーニングのための低複雑さデバイススケジューリングアルゴリズムのクラスを開発する。
最先端の提案方式と比較すると,提案方式は極めて低効率なシステムである。
提案手法の有効性は,CIFARデータセットを用いた実験により確認した。
論文 参考訳（メタデータ） (2022-06-14T08:14:14Z) - Federated Stochastic Primal-dual Learning with Differential Privacy [15.310299472656533]
差分プライバシ(FedSPDDP)を用いた新しいフェデレーション原始双対アルゴリズムを提案する。
分析の結果、データサンプリング戦略とPCPはデータのプライバシを高めることができる一方で、ローカルなSGDステップが多ければ多いほど、プライバシリークが増大する可能性が示唆された。
提案アルゴリズムの実用性能を評価する実験結果を示す。
論文 参考訳（メタデータ） (2022-04-26T13:10:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。