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

• arxiv url: http://arxiv.org/abs/2610.27440v1
• Date: Tue, 20 Oct 2026 00:41:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-21 21:58:47.561351
• Title: Learning-Theoretic Foundation for General Coded Computing: The Adversarial Setting
• Title（参考訳）: 一般符号化コンピューティングのための学習理論の基礎--逆設定
• Abstract要約: アドリヤ労働者は、分散コンピューティングシステムにおいて深刻な課題を提起する。 我々は、汎用符号化コンピューティング(GCC)の逆向きに堅牢な拡張を開発する。 最悪ケースの終端近似誤差に非漸近的境界を導出する。
• 参考スコア（独自算出の注目度）: 15.178727194172161
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Adversarial workers pose a severe challenge in distributed computing systems by returning corrupted outputs that can substantially distort the recovered computations. Coded computing addresses this threat by introducing redundancy across worker assignments. Existing exact and approximate coded-computing methods typically handle adversarial outputs by explicitly locating and correcting or removing erroneous evaluations, which adds significant computational overhead at the master node. Moreover, existing analyses do not characterize how the recovery error scales with the number of workers and the adversarial budget. In this paper, we develop an adversarially robust extension of general coded computing (GCC), a learning-theoretic approximate coded-computing framework that designs the encoder and decoder by minimizing an upper bound on the end-to-end recovery error. Rather than identifying corrupted workers, the proposed method uses smoothness regularization to limit the influence of their outputs. The resulting encoder and decoder can be implemented using smoothing splines with linear master-side complexity. We derive a non-asymptotic bound on the worst-case end-to-end approximation error by decomposing it into three components: (1) the encoder approximation error, (2) the decoder reconstruction error under fully honest results, and (3) the adversarial perturbation error. For maximum of $q\geq 1$ adversarial workers among $N$ workers results in a worst-case error of order $\mathcal{O}((q/N)^{6/5})$ with appropriate selection of smoothness parameter, demonstrating that the approximation error vanishes asymptotically whenever the number of adversaries grows sublinearly with the network size. Experiments on scalar computation and neural-network inference are consistent with the predicted convergence behavior.
• Abstract（参考訳）: 逆ワーカは、復元された計算を実質的に歪ませることができる腐敗した出力を返すことによって、分散コンピューティングシステムにおいて深刻な課題を提起する。 Coded Computingは、労働者の割り当てに冗長性を導入することで、この脅威に対処する。 既存の正確で近似的な符号付き計算法は、通常、不正な評価を明示的に位置付けし、修正し、削除することで、敵の出力を処理し、マスターノードでかなりの計算オーバーヘッドを発生させる。 さらに, 既存分析では, 作業者数や敵の予算に応じて, 回復誤差がどのようにスケールするかを特徴付けていない。 本稿では,エンコーダとデコーダを設計する学習理論的近似符号化計算フレームワークである一般符号化コンピューティング(GCC)の逆向きに堅牢な拡張を開発し,エンド・ツー・エンド・リカバリ誤差の上限を最小化して,デコーダとエンコーダを設計する。 破損した労働者を識別する代わりに、スムーズな正規化を用いて出力の影響を抑える手法を提案する。 結果として得られるエンコーダとデコーダは、線形マスターサイドの複雑さを持つスムーズなスプラインを使用して実装することができる。 本研究では,(1)エンコーダ近似誤差,(2)デコーダ再構成誤差,(3)逆摂動誤差の3つの成分に分解することで,最悪ケースの終端近似誤差の非漸近的境界を導出する。 最大$q\geq 1$の逆ワーカが$N$のワーカの中で最悪のケースエラーとなる。$\mathcal{O}((q/N)^{6/5})$はスムーズなパラメータの適切な選択を伴う。 スカラー計算とニューラルネットワーク推論の実験は、予測収束挙動と一致している。

関連論文リスト

• Learning-Theoretic Foundation for General Coded Computing: The Straggler Setting [21.347076448562863]
  コードコンピューティングは、分散コンピューティングシステムにおけるストラグリングワーカーの影響を軽減するための強力なパラダイムとして登場した。 General Coded Computing (GCC) は、コード化された計算をエンドツーエンドの平均二乗誤差損失によって定式化する。 2つの相補的なストラグラー体制の下で理論的性能を確立する。
  論文  参考訳（メタデータ） (2026-08-28T22:18:22Z)
• Reconstruction of detector error model for quantum error correction [6.505803823301456]
  本稿では,実験症候群統計を直接離散的物理ハイパーグラフに変換するための一貫した枠組みを提案する。 本研究では, 高次から低次まで, 絶対的な統計的分散が線形に蓄積されるような, 密度コードにおける正確な連続パラメータ抽出が, テキスト分散カスケードによって制限されていることを示す。 これは、現実的な量子ハードウェアにおいて、非常に相関性の高いノイズを特徴付け、デコードするための実践的なアプローチを提供する。
  論文  参考訳（メタデータ） (2026-06-15T06:51:48Z)
• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。 汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。 MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
  論文  参考訳（メタデータ） (2024-07-19T08:29: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)
• Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes [59.61248760134937]
  本稿では,$tildeO(sqrtT+zeta)$を後悔するアルゴリズムを提案する。 提案アルゴリズムは、最近開発された線形文脈帯域からの不確実性重み付き最小二乗回帰に依存する。 本稿では,提案アルゴリズムをエピソディックなMDP設定に一般化し,まず汚職レベル$zeta$への付加的依存を実現する。
  論文  参考訳（メタデータ） (2022-12-12T15:04:56Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Coded Distributed Computing with Partial Recovery [56.08535873173518]
  部分回復型符号化計算(CCPR)と呼ばれる新しい符号化行列ベクトル乗法を導入する。 CCPRは計算時間と復号化の複雑さを減らし、精度と計算速度のトレードオフを可能にする。 次に、この手法をより一般的な計算タスクの分散実装に拡張し、部分的回復を伴う符号化通信方式を提案する。
  論文  参考訳（メタデータ） (2020-07-04T21:34:49Z)
• Age-Based Coded Computation for Bias Reduction in Distributed Learning [57.9123881133818]
  コード計算は、分散学習の高速化に使用することができる。 勾配ベクトルの部分回復は、各反復時の計算時間をさらに短縮することができる。 重なり合う行動が時間とともに相関すると、推定バイアスが特に顕著になる。
  論文  参考訳（メタデータ） (2020-06-02T17:51:11Z)

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

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