論文の概要: Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting

• arxiv url: http://arxiv.org/abs/2608.28910v1
• Date: Fri, 28 Aug 2026 22:18:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-01 18:31:30.782645
• Title: Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting
• Title（参考訳）: 一般符号化コンピューティングのための学習理論の基礎:ストラグラー設定
• Abstract要約: コードコンピューティングは、分散コンピューティングシステムにおけるストラグリングワーカーの影響を軽減するための強力なパラダイムとして登場した。 General Coded Computing (GCC) は、コード化された計算をエンドツーエンドの平均二乗誤差損失によって定式化する。 2つの相補的なストラグラー体制の下で理論的性能を確立する。
• 参考スコア（独自算出の注目度）: 21.347076448562863
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Coded computing has emerged as a powerful paradigm for mitigating the impact of straggling workers in distributed computing systems. However, existing coded-computing schemes are predominantly designed for the exact recovery of highly structured computations, such as polynomial evaluation and matrix multiplication, and typically rely on strict recovery thresholds. These assumptions significantly limit their applicability to modern machine-learning workloads, particularly deep neural networks (DNNs), whose computations generally lack rigid algebraic structure and, in many applications, require only accurate approximations rather than exact recovery. To address this gap, we revisit coded computing from a learning-theoretic perspective and introduce General Coded Computing (GCC). Rather than adopting existing algebraic tools, GCC formulates coded computing through a natural end-to-end mean-squared error loss that directly measures the discrepancy between the desired computations and their recovered estimates. By deriving suitable upper bounds and restricting the encoder and decoder to a reproducing kernel Hilbert space (RKHS) with mild smoothness constraints, we show that both the encoder and decoder admit specific representations as linear combinations of RKHS kernel functions. This representation allows the corresponding coefficients to be computed efficiently. Moreover, this framework enables us to establish theoretical performance guarantees for GCC under two complementary straggler regimes. In the worst-case setting with $N$ worker nodes, and at most $S$ stragglers, we show that the end-to-end loss decays at least at rate $O(S^3N^{-3})$ for standard configurations. We then study a probabilistic setting in which each worker independently straggles with probability $p$. We prove that the expected loss can still converge at rate $O(\log_{1/p}^3(N)N^{-3})$.
• Abstract（参考訳）: コードコンピューティングは、分散コンピューティングシステムにおけるストラグリングワーカーの影響を軽減するための強力なパラダイムとして登場した。 しかし、既存の符号計算スキームは主に多項式評価や行列乗算のような高度に構造化された計算の正確な回復のために設計されており、典型的には厳密な回復しきい値に依存している。 これらの仮定は、現代の機械学習ワークロード、特にディープニューラルネットワーク(DNN)への適用性を著しく制限する。 このギャップに対処するため、学習理論の観点からコーデックコンピューティングを再考し、一般コーデックコンピューティング(GCC)を導入する。 既存の代数的ツールを採用するのではなく、GCCは、所望の計算と得られた推定値との差を直接測定する自然なエンドツーエンドの平均2乗誤差損失を通じて、コーデックコンピューティングを定式化する。 適切な上界の導出と、再生するカーネルヒルベルト空間(RKHS)に対するエンコーダとデコーダの制限により、エンコーダとデコーダの両方がRKHSカーネル関数の線形結合として特定の表現を許容していることが示される。 この表現により、対応する係数を効率的に計算することができる。 さらに, この枠組みにより, 2つの相補的なストラグラー体制の下で, GCCの理論的性能保証を確立することが可能となる。 ワーカノードが$N$で、少なくとも$S$ストラグラーで最悪の場合、標準構成では少なくとも$O(S^3N^{-3})$でエンド・ツー・エンドの損失は減少する。 次に、各作業者が独立に確率$p$で発散する確率的設定について研究する。 期待損失は、それでも$O(\log_{1/p}^3(N)N^{-3})$で収束できることを示す。

関連論文リスト

• Search as Computation Allocation [52.080489413778]
  多くのアルゴリズムは、決定を返す前に内部リソースを使い、その端末出力の品質によってのみ評価される。 終端計算割当問題などの手順を定式化する。 ベルマン方程式は、固定予算の下での最適割り当て、価格計算、正確な認証を特徴付ける。
  論文  参考訳（メタデータ） (2026-07-30T08:45:14Z)
• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Riemannian Optimization in Modular Systems [0.006486143522483092]
  バックプロパゲーションアルゴリズムは、ニューラルネットワークの成功に有効である。 実証的な成功にもかかわらず、それに対する強い理論的理解は欠如している。 我々は、収束特性を定量化できる構成可能なリーマン加群の枠組みを開発する。
  論文  参考訳（メタデータ） (2026-03-04T00:47:29Z)
• General Coded Computing: Adversarial Settings [15.839621757142597]
  本稿では,汎用計算の基盤を築き,多種多様な計算を扱うための符号化計算の適用性を拡張した。 提案手法は, 汎用フレームワークにおいて, 最大数の対向サーバにおいて, 最適対向ロバスト性を実現することができることを示す。
  論文  参考訳（メタデータ） (2025-02-12T01:50:12Z)
• General Coded Computing in a Probabilistic Straggler Regime [15.960546024967327]
  近年,正確な計算を近似計算に置き換える一般計算関数のための新しい符号化計算方式が出現している。 本稿では、一般的な符号化コンピューティングの文脈において、各サーバが他のサーバとは独立して確率$p$のストラグラーになるという、現実的に重要なシナリオについて論じる。 既存の2つの一般符号計算スキームの平均近似誤差は、少なくとも$mathcalO(log3_frac1p(N)cdotN-3)$の速度で0に収束することを示す。
  論文  参考訳（メタデータ） (2025-02-02T03:24:05Z)
• 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)
• Randomized Polar Codes for Anytime Distributed Machine Learning [66.46612460837147]
  本稿では,低速な計算ノードに対して堅牢で,線形演算の近似計算と精度の両立が可能な分散コンピューティングフレームワークを提案する。 本稿では,復号化のための計算複雑性を低く保ちながら,実数値データを扱うための逐次復号アルゴリズムを提案する。 大規模行列乗算やブラックボックス最適化など,様々な文脈において,このフレームワークの潜在的な応用を実証する。
  論文  参考訳（メタデータ） (2023-09-01T18:02:04Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Robust Training and Verification of Implicit Neural Networks: A Non-Euclidean Contractive Approach [64.23331120621118]
  本稿では,暗黙的ニューラルネットワークのトレーニングとロバスト性検証のための理論的および計算的枠組みを提案する。 組込みネットワークを導入し、組込みネットワークを用いて、元のネットワークの到達可能な集合の超近似として$ell_infty$-normボックスを提供することを示す。 MNISTデータセット上で暗黙的なニューラルネットワークをトレーニングするためにアルゴリズムを適用し、我々のモデルの堅牢性と、文献における既存のアプローチを通じてトレーニングされたモデルを比較する。
  論文  参考訳（メタデータ） (2022-08-08T03:13:24Z)
• Random Alloy Codes and the Fundamental Limits of Coded Distributed Tensors [1.8130068086063333]
  ストラグラーや他の障害は、全体の完了時間に深刻な影響を与える可能性がある。 符号化コンピューティングにおける最近の研究は、コード化されたタスクでストラグラーを緩和するための新しい戦略を提供する。 この厳密な定義は、失敗の確率を直接最適化しないことを示す。
  論文  参考訳（メタデータ） (2022-02-07T19:20:00Z)
• 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)
• Predictive Coding Approximates Backprop along Arbitrary Computation Graphs [68.8204255655161]
  我々は、コア機械学習アーキテクチャを予測的符号化に翻訳する戦略を開発する。 私たちのモデルは、挑戦的な機械学習ベンチマークのバックプロップと同等に機能します。 本手法は,ニューラルネットワークに標準機械学習アルゴリズムを直接実装できる可能性を高める。
  論文  参考訳（メタデータ） (2020-06-07T15:35:47Z)

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

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