DEED: A General Quantization Scheme for Communication Efficiency in Bits

• URL: http://arxiv.org/abs/2006.11401v1
• Date: Fri, 19 Jun 2020 21:38:44 GMT
• Title: DEED: A General Quantization Scheme for Communication Efficiency in Bits
• Abstract summary: In distributed optimization, a popular technique to reduce communication is quantization. We provide a general analysis framework for inexact descent that is applicable to quantization schemes. We also propose a quantization scheme Double. gradient and Error Diminishing (DEED)
• Score: 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.

Related papers

• Quantum ring all-reduce: communication and privacy advantages for distributed learning [0.0]
  Machine learning models have scaled to unprecedented sizes, making training across distributed devices the de facto standard in the field.<n>In this work, we explore how quantum communications can make distributed training both more communication-efficient and information-theoretically private, for both classical and quantum learning models.<n>We present a quantum version that reduces per-link online communication by a provably optimal factor of two using pre-shared entanglement and superdense coding, without requiring the learning model or gradient to change.
  arXiv  Detail & Related papers  (2026-06-18T15:13:55Z)
• BPDQ: Bit-Plane Decomposition Quantization on a Variable Grid for Large Language Models [56.504879072674015]
  We propose Bit-Plane Decomposition Quantization (BPDQ), which constructs a variable quantization grid via bit-planes and scalar coefficients.<n>BPDQ enables serving Qwen2.5-72B on a single GTX 3090 with 83.85% GSM8K accuracy (vs. 90.83% at 16-bit)
  arXiv  Detail & Related papers  (2026-02-04T02:54:37Z)
• Space-Bounded Communication Complexity of Unitaries [7.120902966697645]
  We study space-bounded communication complexity for unitary implementation in distributed quantum processors.<n>For general $n$-qubit unitaries, we improve upon the trivial $O(4n)$ communication bound.<n>For special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity.
  arXiv  Detail & Related papers  (2025-11-06T10:35:28Z)
• Minimally Universal Parity Quantum Computing [0.559239450391449]
  In parity quantum computing, multi-qubit logical gates are implemented by single-qubit rotations on a suitably encoded state involving auxiliary qubits. Here, we demonstrate that the answer is one, if the number of logical qubits is even, and two otherwise. This leads to a variety of different universal parity gate sets corresponding to different numbers of auxiliary qubits.
  arXiv  Detail & Related papers  (2025-04-04T16:05:34Z)
• Achievable rates in non-asymptotic bosonic quantum communication [0.9999629695552193]
  We find easily computable lower bounds on the non-asymptotic capacities of Gaussian channels. We design the first algorithm capable of computing the trace distance between two Gaussian states up to a fixed precision.
  arXiv  Detail & Related papers  (2025-02-08T11:12:26Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations. It requires the pairwise calculation of a utility metric, which has quadratic complexity. We propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.
  arXiv  Detail & Related papers  (2024-02-06T18:59:30Z)
• A Proximal Gradient Method With Probabilistic Multi-Gossip Communications for Decentralized Composite Optimization [49.17384566985762]
  We propose a communication-efficient method MG-Skip for decentralized composite (smooth + nonsmooth) optimization.<n>For any undirected and connected networks, MG-Skip allows for the multi-gossip communications to be skipped in most iterations in the strongly convex setting.<n> MG-Skip achieves provable communication acceleration, thereby validating the advantages of local updates in the nonsmooth setting.
  arXiv  Detail & Related papers  (2023-12-19T05:13:16Z)
• CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexity [110.50364486645852]
  Communication complexity has become a major bottleneck for speeding up training and scaling up machine numbers. We propose Common Om REOm, which can be used to compress information transmitted between machines.
  arXiv  Detail & Related papers  (2023-09-23T08:45:27Z)
• Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation [77.09836892653176]
  We study multi-agent reinforcement learning in the setting of episodic Markov decision processes. We propose a provably efficient algorithm based on value that enable asynchronous communication. We show that a minimal $Omega(dM)$ communication complexity is required to improve the performance through collaboration.
  arXiv  Detail & Related papers  (2023-05-10T20:29:29Z)
• Mind the $\tilde{\mathcal{O}}$: Asymptotically Better, but Still Impractical, Quantum Distributed Algorithms [0.0]
  We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability. The algorithms achieve a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. An existing framework for using distributed version of Grover's search algorithm to accelerate triangle finding lies at the core of the speedup.
  arXiv  Detail & Related papers  (2023-04-06T02:18:52Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• Qompress: Efficient Compilation for Ququarts Exploiting Partial and Mixed Radix Operations for Communication Reduction [1.4549546367684196]
  We consider automatically encoding two qubits into one four-state quemphquart via a emphcompression scheme. We extend qubit compilation schemes to efficiently route qubits on an arbitrary mixed-radix system consisting of both qubits and ququarts.
  arXiv  Detail & Related papers  (2023-03-01T16:57:30Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• SAGDA: Achieving $\mathcal{O}(\epsilon^{-2})$ Communication Complexity in Federated Min-Max Learning [9.001405567602745]
  We show that SAGDA achieves a linear speedup in terms of both the number of clients and local update steps. We also advance the current understanding on communication complexity of the standard FSGDA method for federated min-max learning.
  arXiv  Detail & Related papers  (2022-10-02T20:04:50Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. An $varepsilon$-solution is achieved in $tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$ number of communications steps. This rate matches (up to poly-log factors) for the first time lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest.
  arXiv  Detail & Related papers  (2021-10-24T04:03:00Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  This work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: circuits and Turing machines.
  arXiv  Detail & Related papers  (2021-07-28T04:28:55Z)
• Towards Tight Communication Lower Bounds for Distributed Optimisation [30.134447658488057]
  We consider a standard distributed optimisation setting where $N$ machines aim to jointly minimise the sum of the functions $sum_i = 1N f_i (x)$. Our main result provides the first fully unconditional bounds on total number of bits which need to be sent and received by the $N$ machines. We show that $Omega( Nd log d / Nvarepsilon)$ total bits need to be communicated between the machines to find an additive $epsilon$-approximation to the minimum of $sum_i = 1N
  arXiv  Detail & Related papers  (2020-10-16T08:10:02Z)
• Trading T gates for dirty qubits in state preparation and unitary synthesis [0.0]
  We present a quantum algorithm for preparing any dimension-$N$ pure quantum state specified by a list of $N$ classical numbers. Our scheme uses $mathcalO(fracNlambda+lambdalogfracNepsilonlogfraclogNepsilon)$ to reduce the T-gate cost to $mathcalO(fracNlambda+lambdalogfracNepsilonlogfraclogNepsilon)$
  arXiv  Detail & Related papers  (2018-12-03T18:24:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.