論文の概要: DEED: A General Quantization Scheme for Communication Efficiency in Bits
- arxiv url: http://arxiv.org/abs/2006.11401v1
- Date: Fri, 19 Jun 2020 21:38:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-19 05:16:00.577144
- Title: DEED: A General Quantization Scheme for Communication Efficiency in Bits
- Title（参考訳）: DEED:ビット間の通信効率の一般的な量子化方式
- Authors: Tian Ye, Peijun Xiao and Ruoyu Sun
- Abstract要約: 分散最適化では、通信を減らすための一般的な手法は量子化である。
量子化スキームに適用可能な不正確な降下に関する一般的な分析フレームワークを提供する。
また、量子化スキームDoubleを提案する。
勾配と誤差低減(DEED)
- 参考スコア（独自算出の注目度）: 14.274085532399098
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In distributed optimization, a popular technique to reduce communication is
quantization. In this paper, we provide a general analysis framework for
inexact gradient descent that is applicable to quantization schemes. We also
propose a quantization scheme Double Encoding and Error Diminishing (DEED).
DEED can achieve small communication complexity in three settings:
frequent-communication large-memory, frequent-communication small-memory, and
infrequent-communication (e.g. federated learning). More specifically, in the
frequent-communication large-memory setting, DEED can be easily combined with
Nesterov's method, so that the total number of bits required is $\tilde{O}(
\sqrt{\kappa} \log 1/\epsilon )$, where $\tilde{O}$ hides numerical constant
and $\log \kappa$ factors. In the frequent-communication small-memory setting,
DEED combined with SGD only requires $\tilde{O}( \kappa \log 1/\epsilon)$
number of bits in the interpolation regime. In the infrequent communication
setting, DEED combined with Federated averaging requires a smaller total number
of bits than Federated Averaging. All these algorithms converge at the same
rate as their non-quantized versions, while using a smaller number of bits.
- Abstract（参考訳）: 分散最適化では、通信を減らす一般的な手法は量子化である。
本稿では、量子化スキームに適用可能な不正確な勾配降下に関する一般的な分析フレームワークを提供する。
また、量子化方式であるDouble Encoding and Error Diminishing (DEED)を提案する。
DEEDは、頻繁なコミュニケーションの大メモリ、頻繁なコミュニケーション小メモリ、頻繁なコミュニケーション小メモリ(フェデレーション学習など)という3つの設定で小さな通信複雑性を実現することができる。
具体的には、頻繁に通信される大きなメモリ設定では、DEEDはNesterovの手法と簡単に組み合わせることができるので、必要なビットの総数は$\tilde{O}( \sqrt{\kappa} \log 1/\epsilon )$であり、$\tilde{O}$は数値定数と$\log \kappa$ factorを隠す。
頻繁なスモールメモリ設定では、deedとsgdを組み合わせると、補間処理において$\tilde{o}( \kappa \log 1/\epsilon)$のビットしか必要なくなる。
頻繁な通信環境では、フェデレート平均化と組み合わせたDEEDはフェデレーション平均化よりも少ない総ビット数を必要とする。
これらのアルゴリズムはすべて、より少ないビット数で、非量子化バージョンと同じ速度で収束する。
関連論文リスト
- CORE: Common Random Reconstruction for Distributed Optimization with
Provable Low Communication Complexity [110.50364486645852]
コミュニケーションの複雑さは、トレーニングをスピードアップし、マシン番号をスケールアップする上で、大きなボトルネックになっています。
本稿では,機械間で送信される情報を圧縮するための共通Om REOmを提案する。
論文 参考訳（メタデータ） (2023-09-23T08:45:27Z) - Cooperative Multi-Agent Reinforcement Learning: Asynchronous
Communication and Linear Function Approximation [77.09836892653176]
マルコフ決定過程の設定におけるマルチエージェント強化学習について検討した。
本稿では非同期通信が可能な値に基づく証明可能な効率的なアルゴリズムを提案する。
我々は、コラボレーションによってパフォーマンスを改善するために、最小の$Omega(dM)$通信の複雑さが必要であることを示す。
論文 参考訳（メタデータ） (2023-05-10T20:29:29Z) - Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still
Impractical, Quantum Distributed Algorithms [0.0]
確率の高い分散計算の量子ConGEST-CLIQUEモデルに2つのアルゴリズムを提案する。
従来のCONGEST-CLIQUEモデルでは、既知のアルゴリズムよりもラウンドとメッセージの複雑さが低い。
Groverの検索アルゴリズムの分散バージョンを使用して三角形探索を高速化する既存のフレームワークは、スピードアップのコアにある。
論文 参考訳（メタデータ） (2023-04-06T02:18:52Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳（メタデータ） (2023-03-03T18:23:20Z) - Qompress: Efficient Compilation for Ququarts Exploiting Partial and
Mixed Radix Operations for Communication Reduction [1.4549546367684196]
2つの量子ビットを1つの4状態のクアンフクォートにエンコードする。
我々は、キュービットとクォートの両方からなる任意の混合基数系上で、キュービットを効率的にルーティングするために、キュービットコンパイルスキームを拡張した。
論文 参考訳（メタデータ） (2023-03-01T16:57:30Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。
異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。
我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
論文 参考訳（メタデータ） (2022-06-07T18:00:01Z) - Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
集中ノードを持たないエージェントネットワーク上での分散(強い凸)最適化問題について検討する。
$varepsilon$-solutionは$tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$通信ステップ数で達成される。
この速度は、関心のクラスに適用される分散ゴシップ-アルゴリズムの、初めて(ポリログ因子まで)より低い複雑性の通信境界と一致する。
論文 参考訳（メタデータ） (2021-10-24T04:03:00Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
N$マシンは$sum_i = 1N f_i (x)$という関数の和を最小化することを目的としている。
我々の主な成果は、$N$マシンによって送信され受信される必要がある全ビット数に関する最初の完全に条件のない境界を提供する。
我々は、$Omega(Nd log d / Nvarepsilon)$ total bits をマシン間で通信し、$sum_i = 1N の最小値に対する加算 $epsilon$-approximation を見つける必要があることを示した。
論文 参考訳（メタデータ） (2020-10-16T08:10:02Z) - Trading T gates for dirty qubits in state preparation and unitary synthesis [0.0]
古典的数のリストで指定された任意の次元-$N$純量子状態を作成するための量子アルゴリズムを提案する。
我々のスキームは、$mathcalO(fracNlambda+lambdalogfracNepsilonlogNepsilon)$を使用して、Tゲートコストを$mathcalO(fracNlambda+lambdalogfracNepsilon)$に削減します。
論文 参考訳（メタデータ） (2018-12-03T18:24:32Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。