論文の概要: Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data
- arxiv url: http://arxiv.org/abs/2005.07866v1
- Date: Sat, 16 May 2020 04:15:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-02 13:07:08.756061
- Title: Byzantine-Resilient SGD in High Dimensions on Heterogeneous Data
- Title（参考訳）: 異種データの高次元ビザンチン耐性SGD
- Authors: Deepesh Data and Suhas Diggavi
- Abstract要約: ビザンチン攻撃下での主作業者アーキテクチャにおける分散勾配降下(SGD)について検討した。
我々のアルゴリズムは、最大で$frac14$のビザンティン労働者を許容できる。
- 参考スコア（独自算出の注目度）: 10.965065178451104
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study distributed stochastic gradient descent (SGD) in the master-worker
architecture under Byzantine attacks. We consider the heterogeneous data model,
where different workers may have different local datasets, and we do not make
any probabilistic assumptions on data generation. At the core of our algorithm,
we use the polynomial-time outlier-filtering procedure for robust mean
estimation proposed by Steinhardt et al. (ITCS 2018) to filter-out corrupt
gradients. In order to be able to apply their filtering procedure in our {\em
heterogeneous} data setting where workers compute {\em stochastic} gradients,
we derive a new matrix concentration result, which may be of independent
interest.
We provide convergence analyses for smooth strongly-convex and non-convex
objectives. We derive our results under the bounded variance assumption on
local stochastic gradients and a {\em deterministic} condition on datasets,
namely, gradient dissimilarity; and for both these quantities, we provide
concrete bounds in the statistical heterogeneous data model. We give a
trade-off between the mini-batch size for stochastic gradients and the
approximation error. Our algorithm can tolerate up to $\frac{1}{4}$ fraction
Byzantine workers. It can find approximate optimal parameters in the
strongly-convex setting exponentially fast and reach to an approximate
stationary point in the non-convex setting with a linear speed, thus, matching
the convergence rates of vanilla SGD in the Byzantine-free setting.
We also propose and analyze a Byzantine-resilient SGD algorithm with gradient
compression, where workers send $k$ random coordinates of their gradients.
Under mild conditions, we show a $\frac{d}{k}$-factor saving in communication
bits as well as decoding complexity over our compression-free algorithm without
affecting its convergence rate (order-wise) and the approximation error.
- Abstract（参考訳）: ビザンチン攻撃下での主作業者アーキテクチャにおける分散確率勾配降下(SGD)について検討した。
我々は、異なるワーカーが異なるローカルデータセットを持つかもしれない異種データモデルを検討し、データ生成に関する確率論的仮定をしない。
アルゴリズムのコアでは,Steinhardt et al. (ITCS 2018) が提案した多項式時間外乱フィルタ法を用いて劣化勾配をフィルタする。
労働者が「em確率」勾配を計算する「emヘテロジニアス」データセットにフィルタリング手順を適用するために、新たな行列濃度結果が導出され、独立した興味を持つ可能性がある。
滑らかな強凸および非凸対象に対する収束解析を行う。
我々は, 局所確率勾配の有界分散仮定と, 勾配の相似性, およびこれらの量に対して, 統計的不均一なデータモデルに具体的な有界性を与えるという条件の下で, 結果の導出を行う。
確率勾配に対するミニバッチサイズと近似誤差とのトレードオフを与える。
我々のアルゴリズムは最大$\frac{1}{4}$ fraction byzantine workersを許容できる。
強凸設定において近似最適パラメータは指数関数的に高速で、非凸設定における近似定常点に線形速度で到達し、したがってビザンツ自由設定におけるバニラSGDの収束率と一致する。
また,傾斜圧縮を伴うビザンチン耐性sgdアルゴリズムの提案と解析を行い,その勾配のランダム座標をk$で送信する。
軽度条件下では,通信ビットの$\frac{d}{k}$-factorセーブと,その収束率(オーダーワイド)と近似誤差に影響を与えることなく,圧縮自由アルゴリズム上のデコード複雑性を示す。
関連論文リスト
- Byzantine-resilient Federated Learning With Adaptivity to Data Heterogeneity [54.145730036889496]
本稿では、ビザンツの悪意ある攻撃データの存在下でのグラディエント・ラーニング(FL)を扱う。
Average Algorithm (RAGA) が提案され、ロバストネスアグリゲーションを活用してデータセットを選択することができる。
論文 参考訳（メタデータ） (2024-03-20T08:15:08Z) - Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
構造密度の重み付き雑音によるクリップ最適化問題を考察する。
勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。
得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
論文 参考訳（メタデータ） (2023-11-07T17:39:17Z) - Robust Stochastic Optimization via Gradient Quantile Clipping [6.2844649973308835]
グラディエントDescent(SGD)のための量子クリッピング戦略を導入する。
通常のクリッピングチェーンとして、グラデーション・ニュー・アウトリージを使用します。
本稿では,Huberiles を用いたアルゴリズムの実装を提案する。
論文 参考訳（メタデータ） (2023-09-29T15:24:48Z) - Federated Learning Using Variance Reduced Stochastic Gradient for
Probabilistically Activated Agents [0.0]
本稿では,各エージェントが各反復において任意の選択の確率を持つような最適解に対して,分散低減と高速収束率の両方を達成する2層構造を持つフェデレートラーニング(FL)のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-10-25T22:04:49Z) - Convergence of First-Order Methods for Constrained Nonconvex
Optimization with Dependent Data [7.513100214864646]
収束$tildeO(t-1/4)$とMoreautildeO(vareps-4)$がスムーズな非最適化のために最悪の場合の複雑性を示す。
適応的なステップサイズと最適収束度を持つ投影勾配法に基づく従属データに対する最初のオンライン非負行列分解アルゴリズムを得る。
論文 参考訳（メタデータ） (2022-03-29T17:59:10Z) - Differentiable Annealed Importance Sampling and the Perils of Gradient
Noise [68.44523807580438]
Annealed importance sample (AIS) と関連するアルゴリズムは、限界推定のための非常に効果的なツールである。
差別性は、目的として限界確率を最適化する可能性を認めるため、望ましい性質である。
我々はメトロポリス・ハスティングスのステップを放棄して微分可能アルゴリズムを提案し、ミニバッチ計算をさらに解き放つ。
論文 参考訳（メタデータ） (2021-07-21T17:10:14Z) - Faster Convergence of Stochastic Gradient Langevin Dynamics for
Non-Log-Concave Sampling [110.88857917726276]
我々は,非log-concaveとなる分布のクラスからサンプリングするために,勾配ランゲヴィンダイナミクス(SGLD)の新たな収束解析を行う。
我々のアプローチの核心は、補助的時間反転型マルコフ連鎖を用いたSGLDのコンダクタンス解析である。
論文 参考訳（メタデータ） (2020-10-19T15:23:18Z) - Byzantine-Resilient High-Dimensional Federated Learning [10.965065178451104]
我々は、悪意のある/ビザンツ人クライアントの存在下で、局所的な反復を伴う勾配CV降下(SGD)を採用する。
クライアントは独自の勾配ベクトルのサブセットを取得してイテレーションを更新し、その後、ネットと通信する。
我々のアルゴリズムは、ローカルデータセットを用いた最初のビザンチン耐性アルゴリズムと分析であると信じている。
論文 参考訳（メタデータ） (2020-06-22T03:54:36Z) - Carath\'eodory Sampling for Stochastic Gradient Descent [79.55586575988292]
本稿では,Tchakaloff と Carath'eodory の古典的な結果から着想を得た手法を提案する。
我々は、測定値の低減を行う降下ステップを適応的に選択する。
これをBlock Coordinate Descentと組み合わせることで、測定の削減を極めて安価に行えるようにします。
論文 参考訳（メタデータ） (2020-06-02T17:52:59Z) - Improved guarantees and a multiple-descent curve for Column Subset
Selection and the Nystr\"om method [76.73096213472897]
我々は,データ行列のスペクトル特性を利用して近似保証を改良する手法を開発した。
我々のアプローチは、特異値減衰の既知の速度を持つデータセットのバウンダリが大幅に向上する。
RBFパラメータを変更すれば,改良された境界線と多重発振曲線の両方を実データセット上で観測できることが示される。
論文 参考訳（メタデータ） (2020-02-21T00:43:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。