Source-linked AI summary
An Exact Quantized Decentralized Gradient Descent Algorithm
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ramtin Pedarsani
TL;DR
Decentralized consensus optimization faces communication bottlenecks as agents exchange local variables over many iterations. The paper proposes QDGD, which combines local information with quantized neighbor messages, and proves vanishing consensus error under customary quantizer conditions.
Problem
Repeated exchanges among decentralized agents create a communication bottleneck, especially as input dimension grows.
Source: §I · p. 1Method
QDGD updates local decision variables by combining local information with quantized messages received from neighboring agents.
Source: §VII · pp. 9–10Results
QDGD achieves vanishing consensus error in mean-squared sense under customary quantizer conditions.
Source: §VII · p. 10Takeaways & Limitations
Numerical studies verify the theoretical results for QDGD.
Source: §VII · p. 10
Abstract
from arXiv · showhide
We consider the problem of decentralized consensus optimization, where the sum of $n$ smooth and strongly convex functions are minimized over $n$ distributed agents that form a connected network. In particular, we consider the case that the communicated local decision variables among nodes are quantized in order to alleviate the communication bottleneck in distributed optimization. We propose the Quantized Decentralized Gradient Descent (QDGD) algorithm, in which nodes update their local decision variables by combining the quantized information received from their neighbors with their local information. We prove that under standard strong convexity and smoothness assumptions for the objective function, QDGD achieves a vanishing mean solution error under customary conditions for quantizers. To the best of our knowledge, this is the first algorithm that achieves vanishing consensus error in the presence of quantization noise. Moreover, we provide simulation results that show tight agreement between our derived theoretical convergence rate and the numerical results.
I. INTRODUCTION
The paper addresses communication limits in decentralized consensus optimization by introducing QDGD, which combines local information with quantized neighbor messages. Under stated quantizer conditions, it proves vanishing solution error and frames the consensus problem over a connected network.
II. PROBLEM FORMULATION
- The problem is to minimize the sum of local costs over a connected network, with each agent knowing only its own cost function.The formulation assumes strongly convex, smooth local objectives and requires agents’ decision variables to agree.Source: §I · p. 1, §II · p. 2
I. INTRODUCTION
- Limited bandwidth makes repeated exchanges of high-dimensional information a major communication bottleneck in decentralized optimization.The paper notes that the communication burden can substantially slow convergence, particularly as input dimension grows.Source: §I · p. 1
- Earlier quantized optimization methods include guarantees within an error depending on network size and quantization levels.Other cited work studies convergence within a non-vanishing error.Source: §I · p. 1
- QDGD combines local information with quantized neighbor messages and achieves vanishing mean solution error under unbiased, variance-bounded quantizers, including a class with input-proportional variance.The authors describe it as the first decentralized gradient-based algorithm with vanishing consensus error despite non-vanishing quantization noise; simulations on synthetic and real data corroborate the theory.Source: §I · p. 2
II. PROBLEM FORMULATION
- Agents exchange randomly quantized local decision variables instead of exact values, reducing communication burden while adding noise to received information.The central challenge is convergence to the optimum when agents access only quantized versions of their neighbors’ variables.Source: §I · p. 1, §II · p. 2
III. QDGD ALGORITHM
QDGD combines quantized neighbor information with local variables and gradients to solve decentralized optimization. Under the stated convexity, smoothness, quantizer, and network conditions, its iterates approach the optimum despite persistent quantization noise, with a trade-off between convergence rate and the required iteration count.
III. QDGD ALGORITHM
- Each node combines quantized neighbor vectors with its local variable and gradient, while α sets the gradient step and ε controls averaging.Diminishing α and averaging with ε are used to control randomness from quantized exchanges.Source: §III · p. 3
IV. CONVERGENCE ANALYSIS
- Under strong convexity, smoothness, and unbiased bounded-variance quantization, QDGD’s local iterates approach the global optimum as closely as desired.The guarantee applies with the stated weight-matrix conditions and sufficiently many iterations.Source: §IV · pp. 3–4
- QDGD converges in expectation to the optimum even though quantization noise does not vanish over time.The paper contrasts this with vanilla DGD, which converges only to a neighborhood under quantization noise.Source: §III · p. 3, §IV · p. 4
- Choosing δ near 1/2 gives a faster convergence rate but raises the minimum iteration requirement; choosing δ near 0 reverses that trade-off.The lower bound on required iterations increases as δ approaches 1/2.Source: §IV · p. 4
- The convergence bound balances quantization variance against network mixing, favoring more neighbor weight when variance is small and more local weight when it is large.The two choices respectively reduce (1−β)^−2 and ∥W−WD∥^2 in the stated bound.Source: §IV · p. 4
A. Proof of Theorem 1
The proof analyzes QDGD through a penalized version of the consensus problem. It establishes convergence to that problem’s solution, bounds the gap to the original constrained optimum, and combines the two bounds to obtain Theorem 1.
A. Proof of Theorem 1
- For suitable step sizes and sufficiently many iterations, QDGD’s expected deviation from the penalized problem’s solution vanishes sublinearly.The proof attributes this to an expected descent direction that is an unbiased estimator of the penalized objective’s gradient.Source: A. Proof of Theorem 1 · p. 5
- The proof bounds the difference between the constrained optimum and the penalized problem’s optimum, with the bound applying for sufficiently small α and large T.This connects convergence to the penalized solution with approximation of the original problem.Source: A. Proof of Theorem 1 · p. 5
- Combining the two lemmas for T≥T0 yields the stated bound for each node and completes the proof of Theorem 1.The proof first rewrites the update and consensus constraint in matrix form and introduces a quadratic penalty.Source: A. Proof of Theorem 1 · pp. 4–5
B. Extension to more quantizers
QDGD is extended to unbiased quantizers whose variance scales with the squared input norm, with a low-precision quantizer as an example. Under this variance condition, QDGD retains the convergence rate of the earlier result, though the iteration threshold can be larger.
B. Extension to more quantizers
- The extension assumes an unbiased quantizer with variance bounded proportionally to the squared norm of its input.Quantizations are carried out independently across distributed nodes.Source: B. Extension to more quantizers · p. 5
- The low-precision quantizer is an example satisfying the input-proportional variance condition.Its tuning parameter s sets the number of quantization levels; larger s reduces variance but increases communication cost.Source: B. Extension to more quantizers · p. 6
- The gradient sparsifier is another example quantizer, selecting each coordinate with probability q_i and outputting either x_i/q_i or zero.The minimum selection probability q_min appears in its variance bound.Source: B. Extension to more quantizers · p. 6
- QDGD converges at the same rate under input-proportional variance as in Theorem 1, but its iteration threshold is generally larger.The condition allows quantization variance to scale with the squared norm of the quantizer input.Source: B. Extension to more quantizers · pp. 5–6
V. OPTIMAL QUANTIZATION LEVEL FOR REDUCING OVERALL COMMUNICATION COST
This section studies how quantization levels trade per-round communication against the iterations needed to reach a target accuracy. In the least-squares experiment, s*=77 yields the smallest total communication cost among the tested levels.
V. OPTIMAL QUANTIZATION LEVEL FOR REDUCING OVERALL COMMUNICATION COST
- More quantization levels reduce variance and the iterations needed for target accuracy, but increase the communication cost of each round.The overall cost is the product of the number of iterations and the communication cost per iteration.Source: §V · pp. 6–7
- The section estimates total communication across agents by combining iterations to reach a target relative error with the expected cost of transmitting a quantized vector.The low-precision quantizer's expected vector cost is represented for two sparsity regimes of its tuning parameter s.Source: §V · p. 7
- s*=77 induces the smallest total communication cost among the tested quantization levels s≥1.The passage reports that the average total cost need not vary monotonically with the number of levels.Source: §V · p. 7, Table I · p. 7
VI. NUMERICAL EXPERIMENTS
The numerical experiments evaluate QDGD on decentralized quadratic minimization and examine how quantization noise and graph connectivity affect relative error. The reported convergence closely follows the theoretical upper bound, while sparser graphs show larger deviation at a fixed iteration count.
A. Decentralized quadratic minimization
- Error scales linearly with quantization noise variance, does not plateau at a non-vanishing residual, and closely follows the theoretical upper bound.Figure 1 compares the relative optimal squared error for σ²∈{2, 20, 200} with the order of the upper bound.Source: A. Decentralized quadratic minimization · p. 8, Figure 1 · p. 8
- At fixed iteration counts, deviation from the optimum increases as the graph becomes sparser, while QDGD guarantees consensus to the optimum for connected graphs.Figure 2 varies connectivity ratio across p_c∈{0.35, 0.5, 1}.Source: A. Decentralized quadratic minimization · p. 8, Figure 2 · p. 8
- 0.1108 and 0.0634 were the relative errors eT1/e0 and eT2/e0 for σ²=200 at T1=800 and T2=3200, respectively.The reported ratio eT2/eT1≈0.57 is upper bounded by the theoretical comparison in the passage.Source: Figure 1 · p. 8, A. Decentralized quadratic minimization · p. 8
B. Decentralized ridge regression
The section evaluates QDGD on decentralized ridge and logistic regression, compares its logistic-regression behavior with quantized DGD, and concludes with its convergence result and open communication questions.
B. Decentralized ridge regression
- The ridge-regression experiment uses 5,000 handwritten-digit samples, 50 agents, and 16 features, and compares δ values 0.175 and 0.275.The graph is Erdős–Rényi with edge probability 0.25 and quantization level s=1.Source: B. Decentralized ridge regression · p. 9, Figure 3 · p. 9
- With s=1 and δ=0.275, the ridge-regression study compares Erdős–Rényi connectivity ratios 0.25 and 0.45 with complete and cycle graphs.Fig. 4 presents the resulting convergence rates.Source: B. Decentralized ridge regression · p. 9, Figure 4 · p. 9
C. Logistic regression
- QDGD can approach the global optimum to any desired optimality gap, whereas naive quantized DGD converges only to a neighborhood.The comparison uses logistic regression; Fig. 5 also varies the quantization level.Source: C. Logistic regression · p. 9, Figure 5 · p. 10
- Larger quantization levels give smaller loss within a fixed number of iterations in the logistic-regression comparison.The paper attributes this to less noisy quantizers providing more accurate neighbor models.Source: C. Logistic regression · p. 9
VII. CONCLUSION
- QDGD combines quantized neighbor messages with local information through proper averaging and achieves vanishing mean-squared consensus error under customary quantizer conditions.The conclusion reports numerical studies as verification of the theoretical results.Source: §VII · pp. 9–10
- A fundamental trade-off between convergence rate and communication, including the minimum bits for a target rate, remains a future research question.The conclusion also identifies low-complexity, near-optimal source coding and methods for convex or non-convex objectives as future directions.Source: §VII · p. 10
APPENDIX A PROOF OF LEMMA 1
The proof treats the QDGD update as stochastic gradient descent on a penalty objective, then bounds its expected deviation using strong convexity, smoothness, and quantization-noise control.
APPENDIX A PROOF OF LEMMA 1
- The recursive bound is established for nonnegative sequences with δ in [0, 1/2), after a sufficient iteration threshold.The proof applies the recurrence repeatedly and controls the exponential term relative to the sublinear term.Source: Appendix A · p. 10
- In expression (50), setting δ = 1/2 results in a constant term, which is therefore non-vanishing; this finding does not specify a required range for δ.Source: Appendix A · p. 10
- The update's gradient estimate is unbiased, so QDGD can be viewed as stochastic gradient descent on h_α with step size ε.The proof derives the estimate from the conditional expectation given the system history.Source: Appendix A · p. 11
- Strong convexity and bounded quantization noise let the proof bound expected squared deviation from the minimizer of h_α.The argument combines the deviation bound with smoothness of h_α and a recursion over iterations.Source: Appendix A · p. 11
APPENDIX B PROOF OF LEMMA 2
The proof relates gradient descent on the penalty objective to its minimizer, then uses that comparison to bound the behavior of the local iterates.
APPENDIX B PROOF OF LEMMA 2
- Gradient descent with unit step size on the penalty objective generates the sequence used to compare QDGD with the penalty minimizer.The proof states that this sequence converges exponentially when the step-size condition is satisfied.Source: Appendix B · p. 11
- The proof contrasts this penalty-based sequence with the cited DGD result, which converges to an O-neighborhood of the optimum.The DGD comparison is attributed to.Source: Appendix B · p. 12
- For the specified parameter choice, the proof bounds the deviation using terms that decay exponentially.It denotes the right-hand-side bound by B1(T) and uses exponential decay of e1(T) and e2(T).Source: Appendix B · p. 12
APPENDIX C PROOF OF THEOREM 2
The proof of Theorem 2 adapts the earlier convergence analysis to an input-norm-scaled quantization-variance assumption and bounds the resulting error.
APPENDIX C PROOF OF THEOREM 2
- The proof revisits the earlier iterate-error bound after replacing the constant variance assumption with Assumption 5.Assumption 5 specifies an unbiased quantizer whose variance is bounded proportionally to the input's squared norm.Source: Appendix C · pp. 12–13
- A bounded optimum is used to bound the minimizer of the penalty objective, and the resulting estimate feeds into the theorem's error bound.The proof applies Lemma 3 and combines the resulting bound with Lemma 2.Source: Appendix C · p. 13