論文の概要: Approximate Gradient Coding with Optimal Decoding
- arxiv url: http://arxiv.org/abs/2006.09638v4
- Date: Fri, 6 Aug 2021 05:30:47 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 20:18:06.982399
- Title: Approximate Gradient Coding with Optimal Decoding
- Title（参考訳）: 最適復号による近似勾配符号化
- Authors: Margalit Glasgow, Mary Wootters
- Abstract要約: 分散最適化問題では、グラデーションコーディングと呼ばれる手法が、ストラグリングマシンの効果を軽減するために用いられている。
近年の研究では、データの複製係数が低すぎる符号化スキームに関する近似勾配符号化について研究している。
拡張器グラフに基づく新しい近似勾配符号を導入し、各マシンが正確に2ブロックのデータポイントを受信する。
- 参考スコア（独自算出の注目度）: 22.069731881164895
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In distributed optimization problems, a technique called gradient coding,
which involves replicating data points, has been used to mitigate the effect of
straggling machines. Recent work has studied approximate gradient coding, which
concerns coding schemes where the replication factor of the data is too low to
recover the full gradient exactly. Our work is motivated by the challenge of
creating approximate gradient coding schemes that simultaneously work well in
both the adversarial and stochastic models. To that end, we introduce novel
approximate gradient codes based on expander graphs, in which each machine
receives exactly two blocks of data points. We analyze the decoding error both
in the random and adversarial straggler setting, when optimal decoding
coefficients are used. We show that in the random setting, our schemes achieve
an error to the gradient that decays exponentially in the replication factor.
In the adversarial setting, the error is nearly a factor of two smaller than
any existing code with similar performance in the random setting. We show
convergence bounds both in the random and adversarial setting for gradient
descent under standard assumptions using our codes. In the random setting, our
convergence rate improves upon block-box bounds. In the adversarial setting, we
show that gradient descent can converge down to a noise floor that scales
linearly with the adversarial error to the gradient. We demonstrate empirically
that our schemes achieve near-optimal error in the random setting and converge
faster than algorithms which do not use the optimal decoding coefficients.
- Abstract（参考訳）: 分散最適化問題において、データポイントの複製を含む勾配符号化と呼ばれる手法が、ストラグリングマシンの効果を軽減するために用いられている。
近年の研究では、データの複製係数が低すぎて完全な勾配を正確に回復できないような符号化スキームに関する近似勾配符号化が研究されている。
我々の研究は、逆モデルと確率モデルの両方で同時に機能する近似勾配符号化スキームを作成するという課題に動機づけられている。
そこで我々は,各マシンが正確に2ブロックのデータポイントを受信する拡張器グラフに基づく,新しい近似勾配符号を導入する。
最適復号係数を用いた場合,ランダムおよび逆ストラグラー設定における復号誤差を解析した。
ランダムな設定では、我々のスキームは複製係数で指数関数的に減衰する勾配の誤差を達成する。
逆の設定では、エラーは既存のどのコードよりも2倍近く小さく、ランダムな設定では同様の性能を持つ。
我々の符号を用いた標準仮定の下で、勾配降下のランダムおよび逆の設定において収束境界を示す。
ランダムな設定では、収束率はブロックボックス境界によって改善される。
逆方向設定では、勾配に対する逆方向誤差と線形にスケールするノイズフロアに勾配降下が収束できることが示される。
提案手法は, 最適復号係数を使用しないアルゴリズムよりも高速に, ランダム設定においてほぼ最適誤差が得られることを示す。
関連論文リスト
- A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
本研究では, 分散勾配降下アルゴリズムの挙動を, 敵対的腐敗の有無で解析する方法を示す。
汚職耐性の分散最適化アルゴリズムを設計するために、(怠慢な)ミラー降下からアイデアをどう使うかを示す。
MNISTデータセットの線形回帰、サポートベクトル分類、ソフトマックス分類に基づく実験は、我々の理論的知見を裏付けるものである。
論文 参考訳（メタデータ） (2024-07-19T08:29:12Z) - Compression of Structured Data with Autoencoders: Provable Benefit of
Nonlinearities and Depth [83.15263499262824]
勾配勾配勾配は入力のスパース構造を完全に無視する解に収束することを示す。
浅層構造にデノナイジング関数を付加することにより,スパースデータの圧縮におけるガウス性能の改善方法を示す。
CIFAR-10 や MNIST などの画像データセットに対して,本研究の成果を検証した。
論文 参考訳（メタデータ） (2024-02-07T16:32:29Z) - Over-the-Air Computation Aided Federated Learning with the Aggregation
of Normalized Gradient [12.692064367193934]
オーバー・ザ・エア(Over-the-air)は、フェデレートラーニング(FL)のための通信効率のよい解である。
このようなシステムでは、プライベート損失関数の反復手順を更新し、すべてのモバイルデバイスで送信する。
この問題を回避するため,局所勾配を正規化して増幅する手法を提案する。
論文 参考訳（メタデータ） (2023-08-17T16:15:47Z) - Fundamental Limits of Two-layer Autoencoders, and Achieving Them with
Gradient Methods [91.54785981649228]
本稿では,非線形二層型オートエンコーダについて述べる。
本結果は,人口リスクの最小化要因を特徴付け,その最小化要因が勾配法によって達成されることを示す。
符号アクティベーション関数の特別な場合において、この解析は、シャローオートエンコーダによるガウス音源の損失圧縮の基本的な限界を確立する。
論文 参考訳（メタデータ） (2022-12-27T12:37:34Z) - Nested Gradient Codes for Straggler Mitigation in Distributed Machine
Learning [21.319460501659666]
グラディエントコードは、一定数のストラグラーを許容するように設計されている。
フレキシブルなトラグラー数に許容できる勾配符号化方式を提案する。
適切なタスクスケジューリングと小さな追加シグナリングにより、作業者の負荷を実際のストラグラー数に適応させる。
論文 参考訳（メタデータ） (2022-12-16T16:56:51Z) - Lightweight Projective Derivative Codes for Compressed Asynchronous
Gradient Descent [6.055286666916789]
本稿では, 偏微分自体を符号化し, さらに, 導出語に対して損失圧縮を行うことにより, 符号を最適化するアルゴリズムを提案する。
この符号化理論の適用性は、勾配降下に基づく学習アルゴリズムにおいてノイズは許容可能であり、時には有用である、という最適化研究における観測事実の幾何学的帰結である。
論文 参考訳（メタデータ） (2022-01-31T04:08:53Z) - Stochastic Compositional Gradient Descent under Compositional
constraints [13.170519806372075]
目的関数と制約関数が凸であり,関数の合成として表される制約最適化問題について検討する。
この問題は、公平な分類/回帰とキューシステムの設計に生じる。
提案手法は最適かつ実現可能な解をほぼ確実に見つけることが保証されている。
論文 参考訳（メタデータ） (2020-12-17T05:38:37Z) - Gaussian MRF Covariance Modeling for Efficient Black-Box Adversarial
Attacks [86.88061841975482]
我々は,ゼロオーダーのオラクルにのみアクセス可能なブラックボックス設定において,逆例を生成する問題について検討する。
我々はこの設定を用いて、FGSM(Fast Gradient Sign Method)のブラックボックス版と同様に、高速な1ステップの敵攻撃を見つける。
提案手法はクエリを少なくし,現在の技術よりも攻撃成功率が高いことを示す。
論文 参考訳（メタデータ） (2020-10-08T18:36:51Z) - Cogradient Descent for Bilinear Optimization [124.45816011848096]
双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。
一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。
本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
論文 参考訳（メタデータ） (2020-06-16T13:41:54Z) - Communication-Efficient Gradient Coding for Straggler Mitigation in
Distributed Learning [17.454251607446555]
サーバがワーカマシン間で勾配計算を分散するグラデーションベースのメソッドの分散実装では、2つの制限を克服する必要がある。
Ye氏とAbe氏(ICML 2018)は、ワーカ毎の計算負荷、ワーカ毎の通信オーバーヘッド、ストラグラートレランスの基本的なトレードオフを特徴付ける、コーディング理論のパラダイムを提案した。
これらの欠点を克服するための通信効率のよい勾配符号化フレームワークを開発した。
論文 参考訳（メタデータ） (2020-05-14T17:57:13Z) - Variance Reduction with Sparse Gradients [82.41780420431205]
SVRGやSpiderBoostのような分散還元法では、大きなバッチ勾配と小さなバッチ勾配が混在している。
我々は、新しい空間演算子:ランダムトップk演算子を導入する。
我々のアルゴリズムは、画像分類、自然言語処理、スパース行列分解など様々なタスクにおいて、一貫してSpiderBoostより優れています。
論文 参考訳（メタデータ） (2020-01-27T08:23:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。