論文の概要: Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth
Channel and Vulnerability
- arxiv url: http://arxiv.org/abs/2210.08371v1
- Date: Sat, 15 Oct 2022 20:44:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-18 21:43:14.184467
- Title: Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth
Channel and Vulnerability
- Title（参考訳）: 1次法のスケッチ:低帯域チャネルと脆弱性の効率的なアルゴリズム
- Authors: Zhao Song, Yitan Wang, Zheng Yu, Lichen Zhang
- Abstract要約: 本稿では,大規模分散学習環境における一階法のための新しいスケッチ手法を提案する。
スケッチ手法を適用した後も勾配漏れの問題が残っていることを示す。
その結果,勾配情報にランダムノイズを加えることで,アルゴリズムが微分プライベートになることを厳格に証明した。
- 参考スコア（独自算出の注目度）: 22.90127105925077
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Sketching is one of the most fundamental tools in large-scale machine
learning. It enables runtime and memory saving via randomly compressing the
original large problem onto lower dimensions. In this paper, we propose a novel
sketching scheme for the first order method in large-scale distributed learning
setting, such that the communication costs between distributed agents are saved
while the convergence of the algorithms is still guaranteed. Given gradient
information in a high dimension $d$, the agent passes the compressed
information processed by a sketching matrix $R\in \R^{s\times d}$ with $s\ll
d$, and the receiver de-compressed via the de-sketching matrix $R^\top$ to
``recover'' the information in original dimension. Using such a framework, we
develop algorithms for federated learning with lower communication costs.
However, such random sketching does not protect the privacy of local data
directly. We show that the gradient leakage problem still exists after applying
the sketching technique by showing a specific gradient attack method. As a
remedy, we prove rigorously that the algorithm will be differentially private
by adding additional random noises in gradient information, which results in a
both communication-efficient and differentially private first order approach
for federated learning tasks. Our sketching scheme can be further generalized
to other learning settings and might be of independent interest itself.
- Abstract（参考訳）: スケッチは、大規模機械学習における最も基本的なツールの1つである。
実行時とメモリの節約は、元の大きな問題を低次元にランダムに圧縮することで実現できる。
本稿では,分散エージェント間の通信コストを削減しつつ,アルゴリズムの収束が保証されるような,大規模分散学習環境における一階法のための新しいスケッチ手法を提案する。
高次元$d$ の勾配情報が与えられたとき、エージェントはスケッチ行列 $r\in \r^{s\times d}$ で処理された圧縮情報を $s\ll d$ で渡し、受信者は元の次元の情報をデスケッチ行列 $r^\top$ to ```recover'' でデ圧縮する。
このようなフレームワークを用いて,より少ない通信コストで連携学習を行うアルゴリズムを開発した。
しかし、このようなランダムなスケッチは、ローカルデータのプライバシーを直接保護しない。
また,特定の勾配攻撃法を提示することにより,スケッチ手法を適用して,勾配漏洩問題が存在することを示す。
そこで我々は,このアルゴリズムが勾配情報にランダムノイズを加えることで,通信効率と差分プライベートな第1次学習課題に対するアプローチを両立させることにより,そのアルゴリズムが微分プライベートになることを厳密に証明する。
私たちのスケッチは、他の学習設定にさらに一般化することができ、独立した興味を持つかもしれません。
関連論文リスト
- Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳（メタデータ） (2023-05-30T16:05:44Z) - Sketchy: Memory-efficient Adaptive Regularization with Frequent
Directions [22.09320263962004]
ディープラーニング(DL)学習タスクにおけるKronecker-factored gradient covariance matrixのスペクトルは、小さなリード固有空間に集中している。
本稿では,行列プレコンディショナを維持するためのメモリと計算要求を低減させる汎用的手法について述べる。
ShampooやAdamと競合する手法で、第2の瞬間を追跡するにはサブ線形メモリしか必要ありません。
論文 参考訳（メタデータ） (2023-02-07T21:50:06Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。
我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
論文 参考訳（メタデータ） (2022-10-14T01:42:05Z) - Large Scale Private Learning via Low-rank Reparametrization [77.38947817228656]
本稿では、大規模ニューラルネットワークに微分プライベートSGDを適用する際の課題を解決するために、再パラメータ化方式を提案する。
BERTモデルにディファレンシャルプライバシを適用し、4つの下流タスクで平均精度が8,3.9%に達するのはこれが初めてである。
論文 参考訳（メタデータ） (2021-06-17T10:14:43Z) - Learning-Augmented Sketches for Hessians [54.97773807211337]
第二次手法の文脈でヘッセンの学習スケッチを設計する方法を紹介します。
学習したスケッチは,「学習されていない」スケッチと比較して,重要な問題に対する近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-02-24T14:50:59Z) - BEAR: Sketching BFGS Algorithm for Ultra-High Dimensional Feature
Selection in Sublinear Memory [13.596664481933875]
現在の大規模スケッチアルゴリズムは、スケッチされた領域における不可逆的な衝突とノイズの蓄積により、メモリ精度のトレードオフが低いことを示す。
我々はBEARを開発し、著名なブロイデン=フレッチャー=ゴールドファーブ=シャノン(BFGS)アルゴリズムに2階勾配を格納することで余分な衝突を避ける。
実世界のデータセットの実験により、BEARは1次スケッチアルゴリズムと同一の分類精度を達成するために最大で3桁のメモリスペースを必要とすることが示された。
論文 参考訳（メタデータ） (2020-10-26T18:31:27Z) - Learning the Positions in CountSketch [51.15935547615698]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習アルゴリズムを提案する。
このアルゴリズムは, 従来よりも低階近似の精度を向上し, 初めて$k$-meansクラスタリングのような他の問題に適用できることを示す。
論文 参考訳（メタデータ） (2020-07-20T05:06:29Z) - A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
差別化プライバシ(DP)は、正式な証明可能な保証を通じて、プライバシとユーティリティのトレードオフを説明する魅力的なプライバシ定義である。
本稿では,回帰,分類,密度推定など,多数の機械学習タスクをサポートするプライベートスケッチを提案する。
このスケッチは,局所性に敏感なハッシュをインデックス化して,効率的なワンパスアルゴリズムで構築したランダムな一致テーブルで構成されている。
論文 参考訳（メタデータ） (2020-06-16T17:47:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。