論文の概要: Gradient Coding through Iterative Block Leverage Score Sampling

• arxiv url: http://arxiv.org/abs/2308.03096v1
• Date: Sun, 6 Aug 2023 12:22:12 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-08 16:38:21.468895
• Title: Gradient Coding through Iterative Block Leverage Score Sampling
• Title（参考訳）: 繰り返しブロックレバレッジスコアサンプリングによるグラディエント符号化
• Authors: Neophytos Charalambides, Mert Pilanci, Alfred Hero
• Abstract要約: 変換したデータのサンプリングサブセットに対応するために,$ell$-subspace埋め込みのためのレバレッジスコアサンプリングスケッチを一般化する。 これを用いて、一階法に対する近似符号付き計算手法を導出する。
• 参考スコア（独自算出の注目度）: 40.37097343584523
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We generalize the leverage score sampling sketch for $\ell_2$-subspace embeddings, to accommodate sampling subsets of the transformed data, so that the sketching approach is appropriate for distributed settings. This is then used to derive an approximate coded computing approach for first-order methods; known as gradient coding, to accelerate linear regression in the presence of failures in distributed computational networks, \textit{i.e.} stragglers. We replicate the data across the distributed network, to attain the approximation guarantees through the induced sampling distribution. The significance and main contribution of this work, is that it unifies randomized numerical linear algebra with approximate coded computing, while attaining an induced $\ell_2$-subspace embedding through uniform sampling. The transition to uniform sampling is done without applying a random projection, as in the case of the subsampled randomized Hadamard transform. Furthermore, by incorporating this technique to coded computing, our scheme is an iterative sketching approach to approximately solving linear regression. We also propose weighting when sketching takes place through sampling with replacement, for further compression.
• Abstract（参考訳）: 我々は、$\ell_2$-subspace埋め込みのためのレバレッジスコアサンプリングスケッチを一般化し、変換されたデータのサンプリングサブセットを適合させる。 この手法は、分散計算ネットワークにおける障害の存在下で線形回帰を加速するために、勾配符号化と呼ばれる一階法のための近似符号付き計算手法を導出するために用いられる。 我々は、分散ネットワーク上でデータを複製し、誘導サンプリング分布を通して近似を保証する。 この研究の意義と大きな貢献は、ランダム化された数値線形代数を近似符号化計算で統一し、一様サンプリングによって誘導された$\ell_2$-subspace 埋め込みを達成することである。 均一サンプリングへの移行は、サブサンプルランダム化アダマール変換の場合のように、ランダムプロジェクションを適用することなく行われる。 さらに,この手法を符号化計算に組み込むことにより,線形回帰を近似的に解く反復的スケッチ手法を提案する。 また,さらなる圧縮のために,サンプリングと置換によるスケッチを行う場合の重み付けも提案する。

関連論文リスト

• A Historical Trajectory Assisted Optimization Method for Zeroth-Order Federated Learning [24.111048817721592]
  フェデレートラーニングは分散勾配降下技術に大きく依存している。 勾配情報が得られない状況では、勾配をゼロ次情報から推定する必要がある。 勾配推定法を改善するための非等方的サンプリング法を提案する。
  論文  参考訳（メタデータ） (2024-09-24T10:36:40Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  本論文では,乗算器の交互方向法に基づく分散サンプリング手法を提案する。 我々は,アルゴリズムの収束に関する理論的保証と,その最先端性に関する実験的証拠の両方を提供する。 シミュレーションでは,線形回帰タスクとロジスティック回帰タスクにアルゴリズムを配置し,その高速収束を既存の勾配法と比較した。
  論文  参考訳（メタデータ） (2024-01-29T02:08:40Z)
• Iterative Sketching for Secure Coded Regression [66.53950020718021]
  分散線形回帰を高速化する手法を提案する。 具体的には、方程式の系の基礎をランダムに回転させ、次にサブサンプルブロックを回転させ、情報を同時に確保し、回帰問題の次元を小さくする。
  論文  参考訳（メタデータ） (2023-08-08T11:10:42Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Smpling (AIS)は、抽出可能な分布から重み付けされたサンプルを合成する。 本稿では,alpha$-divergencesに対する定数レートAISアルゴリズムとその効率的な実装を提案する。
  論文  参考訳（メタデータ） (2023-06-27T08:15:28Z)
• Samplet basis pursuit: Multiresolution scattered data approximation with sparsity constraints [0.0]
  我々は,$ell_1$-regularization を用いたサンプルト座標における分散データ近似について検討する。 Riesz isometry を用いて、標本を再現されたカーネルヒルベルト空間に埋め込む。 組込みサンプルベースに対してスパースな信号のクラスは、カーネル翻訳の基盤に関してスパースな信号のクラスよりもかなり大きいと論じる。
  論文  参考訳（メタデータ） (2023-06-16T21:20:49Z)
• Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks [5.672132510411465]
  テンソルを任意のテンソルネットワーク(TN)形式に分解するためのサンプリングベース交互最小二乗(ALS)アルゴリズムの開発方法について述べる。 特徴抽出実験において、サンプリングフレームワークを用いた2つのテンソル分解アルゴリズムを実装し、テストする。
  論文  参考訳（メタデータ） (2022-10-07T21:46:26Z)
• Approximate sampling and estimation of partition functions using neural networks [0.0]
  本研究では, 可変オートエンコーダ (VAE) をいかに応用できるかを示す。 論理を逆転させ、正規化まで特定された複雑で難解な潜在分布を仮定して、VAEを単純かつトラクタブルな分布に適合するように訓練する。 この手順は、トレーニングデータやマルコフ連鎖モンテカルロサンプリングを使わずに近似を構成する。
  論文  参考訳（メタデータ） (2022-09-21T15:16:45Z)
• Spatially Adaptive Inference with Stochastic Feature Sampling and Interpolation [72.40827239394565]
  スパースサンプリングされた場所のみの機能を計算することを提案する。 次に、効率的な手順で特徴写像を密に再構築する。 提案したネットワークは、様々なコンピュータビジョンタスクの精度を維持しながら、かなりの計算を省くために実験的に示されている。
  論文  参考訳（メタデータ） (2020-03-19T15:36:31Z)
• Distributed Sketching Methods for Privacy Preserving Regression [54.51566432934556]
  ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。 従来のスケッチ手法に対する新しい近似保証を導出し、分散スケッチにおけるパラメータ平均化の精度を解析する。 大規模実験によるサーバレスコンピューティングプラットフォームにおける分散スケッチのパフォーマンスについて説明する。
  論文  参考訳（メタデータ） (2020-02-16T08:35:48Z)

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

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