論文の概要: General Coded Computing in a Probabilistic Straggler Regime

• arxiv url: http://arxiv.org/abs/2502.00645v1
• Date: Sun, 02 Feb 2025 03:24:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-05 14:53:43.071359
• Title: General Coded Computing in a Probabilistic Straggler Regime
• Title（参考訳）: 確率的ストラグラーレジームにおける一般符号計算
• Authors: Parsa Moradi, Mohammad Ali Maddah-Ali,
• Abstract要約: 近年,正確な計算を近似計算に置き換える一般計算関数のための新しい符号化計算方式が出現している。 本稿では、一般的な符号化コンピューティングの文脈において、各サーバが他のサーバとは独立して確率$p$のストラグラーになるという、現実的に重要なシナリオについて論じる。 既存の2つの一般符号計算スキームの平均近似誤差は、少なくとも$mathcalO(log3_frac1p(N)cdotN-3)$の速度で0に収束することを示す。
• 参考スコア（独自算出の注目度）: 15.960546024967327
• License:
• Abstract: Coded computing has demonstrated promising results in addressing straggler resiliency in distributed computing systems. However, most coded computing schemes are designed for exact computation, requiring the number of responding servers to exceed a certain recovery threshold. Additionally, these schemes are tailored for highly structured functions. Recently, new coded computing schemes for general computing functions, where exact computation is replaced with approximate computation, have emerged. In these schemes, the availability of additional results corresponds to more accurate estimation of computational tasks. This flexibility introduces new questions that need to be addressed. This paper addresses the practically important scenario in the context of general coded computing, where each server may become a straggler with a probability $p$, independently from others. We theoretically analyze the approximation error of two existing general coded computing schemes: Berrut Approximate Coded Computing (BACC) and Learning Theoretic Coded Computing (LeTCC). Under the probabilistic straggler configuration, we demonstrate that the average approximation error for BACC and LeTCC converge to zero with the rate of at least $\mathcal{O}(\log^3_{\frac{1}{p}}(N)\cdot{N^{-3}})$ and $\mathcal{O}(\log^4_{\frac{1}{p}}(N)\cdot{N^{-2}})$, respectively. This is perhaps surprising, as earlier results does not indicate a convergence when the number of stragglers scales with the total number of servers $N$. However, in this case, despite the average number of stragglers being $Np$, the independence of servers in becoming stragglers allows the approximation error to converge to zero. These theoretical results are validated through experiments on various computing functions, including deep neural networks.
• Abstract（参考訳）: 符号化コンピューティングは、分散コンピューティングシステムにおけるストラグラーレジリエンスに対処する上で有望な結果を示している。 しかし、ほとんどの符号化された計算方式は正確な計算のために設計されており、応答するサーバの数が一定の回復しきい値を超える必要がある。 さらに、これらのスキームは高度に構造化された関数に適合する。 近年,正確な計算を近似計算に置き換える一般計算関数のための新しい符号化計算方式が出現している。 これらのスキームでは、追加結果の可用性は計算タスクのより正確な推定に対応している。 この柔軟性は、対処すべき新しい質問をもたらします。 本稿では、一般的な符号化コンピューティングの文脈において、各サーバが他のサーバとは独立して確率$p$のストラグラーになるという、現実的に重要なシナリオについて論じる。 本稿では,Berrut Approximate Coded Computing (BACC) とLearning Theoretic Coded Computing (LeTCC) の2つの一般的な計算方式の近似誤差を理論的に解析する。 BACC と LeTCC の平均近似誤差は少なくとも $\mathcal{O}(\log^3_{\frac{1}{p}}(N)\cdot{N^{-3}})$ と $\mathcal{O}(\log^4_{\frac{1}{p}}(N)\cdot{N^{-2}})$ の速度でゼロに収束することを示した。 以前の結果は、トラグラーの数がサーバの総数$N$でスケールした場合の収束を示していないため、これはおそらく驚くべきことである。 しかし、この場合、平均的なストラグラー数が$Np$であるにもかかわらず、ストラグラーとなる際のサーバの独立性は近似誤差をゼロに収束させる。 これらの理論的結果は、ディープニューラルネットワークを含む様々なコンピューティング機能の実験を通じて検証される。

関連論文リスト

• General Coded Computing: Adversarial Settings [15.839621757142597]
  本稿では,汎用計算の基盤を築き,多種多様な計算を扱うための符号化計算の適用性を拡張した。 提案手法は, 汎用フレームワークにおいて, 最大数の対向サーバにおいて, 最適対向ロバスト性を実現することができることを示す。
  論文  参考訳（メタデータ） (2025-02-12T01:50:12Z)
• Coded Computing for Resilient Distributed Computing: A Learning-Theoretic Framework [15.703073293718953]
  本稿では,学習理論の原理を統合し,機械学習アプリケーションにシームレスに適応するフレームワークを開発することを目的とした,符号化コンピューティングのための新しい基盤を提案する。 提案手法では, 推定誤差の平均は$mathcalO(S3 N-3)$と$mathcalO(Sfrac85Nfrac-35)$の2乗誤差で, ノイズのない, ノイズの多い計算条件で減衰することを示した。
  論文  参考訳（メタデータ） (2024-06-01T05:01:25Z)
• On Hardware-efficient Inference in Probabilistic Circuits [5.335146727090435]
  本研究は,PC用専用近似計算フレームワークを提案する。 我々はAddition As Intを活用し、単純なハードウェア要素による線形PC計算を実現した。 理論的近似誤差解析と誤り補償機構を提案する。
  論文  参考訳（メタデータ） (2024-05-22T13:38:47Z)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  本稿では,低速な計算ノードに対して堅牢で,線形演算の近似計算と精度の両立が可能な分散コンピューティングフレームワークを提案する。 本稿では,復号化のための計算複雑性を低く保ちながら,実数値データを扱うための逐次復号アルゴリズムを提案する。 大規模行列乗算やブラックボックス最適化など,様々な文脈において,このフレームワークの潜在的な応用を実証する。
  論文  参考訳（メタデータ） (2023-09-01T18:02:04Z)
• Computationally Efficient Approximations for Matrix-based Renyi's Entropy [33.72108955447222]
  最近開発された行列ベースのRenyiのエントロピーは、データ内の情報の計測を可能にする。 そのような量の計算には、PSD行列の$G$上のトレース演算子を$alpha$(つまり$tr(Galpha)$)の電力とする。 我々は、この新しいエントロピー汎函数に対する計算学的に効率的な近似を示し、その複雑性を$O(n2)$よりもはるかに小さくすることができる。
  論文  参考訳（メタデータ） (2021-12-27T14:59:52Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。 $varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。 この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
  論文  参考訳（メタデータ） (2021-10-24T04:03:00Z)
• The Separation Capacity of Random Neural Networks [78.25060223808936]
  標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。 我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
  論文  参考訳（メタデータ） (2021-07-31T10:25:26Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。 BACCは計算複雑性が低い数値的に安定であることが証明されている。 特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
  論文  参考訳（メタデータ） (2020-09-17T14:23:38Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  部分回復型符号化計算(CCPR)と呼ばれる新しい符号化行列ベクトル乗法を導入する。 CCPRは計算時間と復号化の複雑さを減らし、精度と計算速度のトレードオフを可能にする。 次に、この手法をより一般的な計算タスクの分散実装に拡張し、部分的回復を伴う符号化通信方式を提案する。
  論文  参考訳（メタデータ） (2020-07-04T21:34:49Z)

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

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