論文の概要: Distributed Learning and Democratic Embeddings: Polynomial-Time Source
Coding Schemes Can Achieve Minimax Lower Bounds for Distributed Gradient
Descent under Communication Constraints
- arxiv url: http://arxiv.org/abs/2103.07578v1
- Date: Sat, 13 Mar 2021 00:04:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-18 07:47:21.192622
- Title: Distributed Learning and Democratic Embeddings: Polynomial-Time Source
Coding Schemes Can Achieve Minimax Lower Bounds for Distributed Gradient
Descent under Communication Constraints
- Title(参考訳): 分散学習と民主的埋め込み:通信制約下での分散グラディエントに最小限の低境界を達成できる多項式時間音源符号化方式
- Authors: Rajarshi Saha, Mert Pilanci, Andrea J. Goldsmith
- Abstract要約: 我々は、n次元ユークリッド空間においてベクトルを圧縮する問題を考える。
数値化器の被覆効率が次元独立であるか、あるいは非常に弱い対数依存であるという意味では、民主主義的および民主的に近いソースコーディングスキームが(ほぼ)最適であることを示す。
分散最適化アルゴリズムDGD-DEFを提案する。このアルゴリズムは,提案した符号化戦略を用いて,(ほぼ)定数要素内における最小収束率を実現する。
- 参考スコア(独自算出の注目度): 46.17631511884969
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this work, we consider the distributed optimization setting where
information exchange between the computation nodes and the parameter server is
subject to a maximum bit-budget. We first consider the problem of compressing a
vector in the n-dimensional Euclidean space, subject to a bit-budget of R-bits
per dimension, for which we introduce Democratic and Near-Democratic
source-coding schemes. We show that these coding schemes are (near) optimal in
the sense that the covering efficiency of the resulting quantizer is either
dimension independent, or has a very weak logarithmic dependence. Subsequently,
we propose a distributed optimization algorithm: DGD-DEF, which employs our
proposed coding strategy, and achieves the minimax optimal convergence rate to
within (near) constant factors for a class of communication-constrained
distributed optimization algorithms. Furthermore, we extend the utility of our
proposed source coding scheme by showing that it can remarkably improve the
performance when used in conjunction with other compression schemes. We
validate our theoretical claims through numerical simulations.
Keywords: Fast democratic (Kashin) embeddings, Distributed optimization,
Data-rate constraint, Quantized gradient descent, Error feedback.
- Abstract(参考訳): 本研究では,計算ノードとパラメータサーバ間の情報交換を最大ビット予算で行う分散最適化について考察する。
まず, n-次元ユークリッド空間においてベクトルを圧縮する問題を考える。
これらの符号化スキームは、結果の量子化器の被覆効率が次元独立であるか、あるいは非常に弱い対数依存であるという意味で(ほぼ)最適であることを示す。
そこで,本稿では,分散最適化アルゴリズムDGD-DEFを提案する。DGD-DEFは,提案した符号化戦略を用いて,通信制約のある分散最適化アルゴリズムのクラスに対して,(ほぼ)定数要素内における最小収束率を実現する。
さらに,提案手法が他の圧縮方式と併用することで,性能を著しく向上できることを示すことにより,提案手法の有用性を拡大する。
数値シミュレーションにより理論的主張を検証する。
キーワード:fast democratic (kashin)埋め込み、分散最適化、データレート制約、量子化勾配降下、エラーフィードバック。
関連論文リスト
- Q-SHED: Distributed Optimization at the Edge via Hessian Eigenvectors
Quantization [5.404315085380945]
ニュートン型(NT)法は、DO問題における堅牢な収束率の実現要因として提唱されている。
インクリメンタルなヘッセン固有ベクトル量子化に基づく新しいビット割り当て方式を特徴とする、DOのための元のNTアルゴリズムであるQ-SHEDを提案する。
Q-SHEDはコンバージェンスに必要な通信ラウンド数を最大60%削減できることを示す。
論文 参考訳(メタデータ) (2023-05-18T10:15:03Z) - Gradient Sparsification for Efficient Wireless Federated Learning with
Differential Privacy [25.763777765222358]
フェデレートラーニング(FL)により、分散クライアントは、生データを互いに共有することなく、機械学習モデルを協調的にトレーニングできる。
モデルのサイズが大きくなるにつれて、送信帯域の制限によるトレーニングのレイテンシが低下し、個人情報が劣化すると同時に、差分プライバシ(DP)保護を使用する。
我々は、収束性能を犠牲にすることなく、トレーニング効率を向上させるために、FLフレームワーク無線チャネルのスペース化を提案する。
論文 参考訳(メタデータ) (2023-04-09T05:21:15Z) - On Model Compression for Neural Networks: Framework, Algorithm, and
Convergence Guarantee [10.783153208561469]
本稿では,低ランク近似と重み近似の2つのモデル圧縮手法に焦点を当てた。
本稿では,非最適化の新たな視点から,モデル圧縮のための全体論的なフレームワークを提案する。
論文 参考訳(メタデータ) (2023-03-13T02:14:42Z) - 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) - Distributed Sketching for Randomized Optimization: Exact
Characterization, Concentration and Lower Bounds [54.51566432934556]
我々はヘシアンの形成が困難である問題に対する分散最適化法を検討する。
ランダム化されたスケッチを利用して、問題の次元を減らし、プライバシを保ち、非同期分散システムにおけるストラグラーレジリエンスを改善します。
論文 参考訳(メタデータ) (2022-03-18T05:49:13Z) - DESTRESS: Computation-Optimal and Communication-Efficient Decentralized
Nonconvex Finite-Sum Optimization [43.31016937305845]
インターネット・オブ・シング、ネットワークセンシング、自律システム、有限サム最適化のための分散アルゴリズムのためのフェデレーション学習。
非有限サム最適化のためのDecentralized STochastic Recursive MethodDESTRESSを開発した。
詳細な理論的および数値的な比較は、DESTRESSが事前の分散アルゴリズムにより改善されていることを示している。
論文 参考訳(メタデータ) (2021-10-04T03:17:41Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Adaptive Subcarrier, Parameter, and Power Allocation for Partitioned
Edge Learning Over Broadband Channels [69.18343801164741]
パーティショニングエッジ学習(PARTEL)は、無線ネットワークにおいてよく知られた分散学習手法であるパラメータサーバトレーニングを実装している。
本稿では、いくつかの補助変数を導入してParticleELを用いてトレーニングできるディープニューラルネットワーク(DNN)モデルについて考察する。
論文 参考訳(メタデータ) (2020-10-08T15:27:50Z) - Resource Allocation via Model-Free Deep Learning in Free Space Optical
Communications [119.81868223344173]
本稿では,自由空間光学(FSO)通信におけるチャネルフェージング効果の緩和のための資源配分の一般的な問題について検討する。
本フレームワークでは,FSO資源割り当て問題を解決する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-07-27T17:38:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。