PaperlayerView exact revision on arXiv

Source-linked AI summary

UVeQFed: Universal Vector Quantization for Federated Learning

Nir Shlezinger, Mingzhe Chen, Yonina C. Eldar, H. Vincent Poor, Shuguang Cui

arXiv:2006.03262v3cs.LGcs.ITstat.ML

TL;DR

Federated learning must transfer many updated model parameters over throughput-constrained uplinks. UVeQFed applies universal vector quantization with dithered lattice quantization, and its quantization error is mitigated by federated averaging while its asymptotic decay rate matches unquantized local SGD.

  • Problem

    Federated learning faces the challenge of transferring many updated model parameters over a throughput-constrained uplink channel.

  • Method

    UVeQFed uses universal vector quantization and a dithered lattice quantization encoding-decoding strategy for federated learning.

  • Results

    UVeQFed's quantization error is mitigated by federated averaging, its distortion vanishes by averaging, and its asymptotic decay rate matches unquantized local SGD.

  • Takeaways & Limitations

    Federated averaging can mitigate UVeQFed's quantization error while preserving the asymptotic decay rate of unquantized local SGD.

  • Takeaways & Limitations

    UVeQFed models the uplink as a bit-limited pipeline, which may not accurately reflect wireless communication and feasible hardware requirements.

Abstract

from arXiv · show

Traditional deep learning models are trained at a centralized server using labeled data samples collected from end devices or users. Such data samples often include private information, which the users may not be willing to share. Federated learning (FL) is an emerging approach to train such learning models without requiring the users to share their possibly private labeled data. In FL, each user trains its copy of the learning model locally. The server then collects the individual updates and aggregates them into a global model. A major challenge that arises in this method is the need of each user to efficiently transmit its learned model over the throughput limited uplink channel. In this work, we tackle this challenge using tools from quantization theory. In particular, we identify the unique characteristics associated with conveying trained models over rate-constrained channels, and propose a suitable quantization scheme for such settings, referred to as universal vector quantization for FL (UVeQFed). We show that combining universal vector quantization methods with FL yields a decentralized training system in which the compression of the trained models induces only a minimum distortion. We then theoretically analyze the distortion, showing that it vanishes as the number of users grows. We also characterize the convergence of models trained with the traditional federated averaging method combined with UVeQFed to the model which minimizes the loss function. Our numerical results demonstrate the gains of UVeQFed over previously proposed methods in terms of both distortion induced in quantization and accuracy of the resulting aggregated model.

I. INTRODUCTION

Federated learning keeps labeled data local but must transmit model updates over throughput-constrained uplinks. UVeQFed applies universal vector quantization to reduce aggregation distortion while preserving convergence and accuracy under tight bit budgets.

  • Federated learning trains models locally and iteratively aggregates users’ updates into a global network, avoiding transmission of private labeled data.
  • Large model updates create a major uplink challenge because users must transmit many parameters over throughput-constrained channels.
  • Existing sparsification and scalar-quantization approaches can be suboptimal because random gradient discarding may cause dominant distortion and scalar quantization underperforms vector quantization.
  • UVeQFed uses subtractive dithered lattice quantization without requiring knowledge of model-update distributions, while exploiting shared local randomness.
  • Its quantization error is mitigated by federated averaging and includes a term that vanishes as the number of users grows, regardless of users’ data-generating statistical models.
  • For strongly convex and smooth objectives, UVeQFed federated averaging converges at order 1/t, while experiments show more accurate global models and faster convergence at two and four bits per sample.

II. SYSTEM MODEL

The system uses federated averaging to train a shared model while users transmit finite-bit quantized updates over throughput-limited uplinks. Limited bit budgets induce distortion that can impair global-model updates, motivating quantization methods designed for this setting.

  • Federated averaging shares the server’s current model, has each user retrain it locally, and aggregates the resulting model updates.
  • Users must send finite-bit representations of their model updates because uplink throughput is typically more limited than downlink throughput.
  • The server decodes users’ codewords and uses them to estimate the weighted average needed for global-model updating.
  • Small bit budgets induce quantization distortion that can severely degrade the server’s ability to update its model.
  • Existing sparsification and probabilistic scalar-quantization approaches can remain separated from the finite-bit distortion limit characterized by rate-distortion theory.
  • This motivates efficient vector-quantization methods tailored to conveying model updates for federated learning.

B. Problem Formulation

The paper formulates bit-constrained federated learning around shared, distribution-agnostic encoding and common randomness, then proposes UVeQFed using subtractive dithered lattice quantization.

  • B. Problem Formulation: The design goal is an encoding-decoding system that mitigates quantization errors’ effect on accurately recovering the updated model.
  • B. Problem Formulation: All users share one encoding function, while the quantizer operates without prior knowledge of the model-update distribution.
  • B. Problem Formulation: The server and users share common randomness, such as a seed, to generate matching dither realizations.
  • III. UVEQFED: UVeQFed applies universal subtractive dithered lattice quantization to each model update using the same procedure for every user.
  • A. Quantization Scheme: A lattice is generated by a nonsingular matrix, and its quantizer maps each vector to the nearest lattice point.
  • A. Quantization Scheme: The encoder normalizes and partitions updates, dithers sub-vectors, lattice-quantizes them, and losslessly entropy-codes the discrete outputs.
  • III. UVEQFED: The scheme’s distortion is not deterministically tied to individual updates, allowing averaging to reduce its effect.
  • A. Quantization Scheme: The decoder reverses entropy coding, subtracts the dither, reconstructs the full update, and computes the aggregated global model.

B. Discussion

UVeQFed combines distribution-independent dithered vector quantization with federated averaging to reduce distortion, while retaining relatively simple implementation and explicit channel-model limitations.

  • UVeQFed’s main novel aspect is using subtractive dithered lattice quantization within a simple architecture with feasible hardware requirements.
  • The quantization error’s statistical characterization does not depend on the model-update distribution, enabling analysis of its interaction with federated averaging.
  • The distortion vanishes by averaging regardless of the model-update values under the considered system model.
  • The bit-limited uplink model may not accurately represent noisy, shared wireless channels; direct task-based joint source-channel coding is left for future work.
  • For L = 1 and ζ = 1, the encoder matches QSGD, while dither subtraction yields an error term independent of the model updates.
  • Using vector quantizers with L > 1 can further improve quantization accuracy and jointly combine dimensionality reduction with quantization.
  • Distributed source-coding alternatives can improve compression or reconstruction fidelity but require joint-distribution knowledge and user-specific encoders, violating A1-A2.
  • Higher-dimensional lattices typically improve representation accuracy at the cost of increased complexity, whose projection cost grows linearly with m for finite small L.

IV. PERFORMANCE ANALYSIS

The performance analysis studies UVeQFed’s distortion and convergence under conventional local SGD training for federated averaging.

  • The analysis characterizes UVeQFed’s distortion and studies global-model convergence under conventional local SGD training.

A. Local SGD

This section describes local SGD updates and UVeQFed’s quantization-error analysis for transmitting model updates. The analysis shows that distortion can decrease with more participating users and iterations.

  • Local SGD: Each user performs τ SGD iterations before sending its updated model to the server.The local procedure uses a learning rate η_t and stochastic sample indices; the section focuses on one stochastic gradient per time instance.
  • Quantization Error Bound: Theorem 1 characterizes UVeQFed’s distortion, with the bit dependence represented through the lattice moment σ̄^2_L.The cited discussion contrasts this characterization with previous FL quantizers whose dependence on the number of bits is not explicit.
  • Quantization Error Bound: 2-fold lower distortion than conventional probabilistic scalar quantizers such as QSGD is obtained through subtractive-dither decoding, even when scalar quantizers use L = 1.The reduction is attributed to subtracting the dither during decoding.
  • Local SGD: The server recovers quantized model updates and uses them to update the global model.The recovered vector is denoted ˆh^(k), and the resulting global update combines the recovered local models.
  • Quantization Error Bound: Theorem 2’s distance bound relies on independence between subtractive-dithered quantization error and the quantized value.This independence enables a rigorous upper bound on the distance between the recovered model and the desired model.

C. FL Convergence Analysis

The convergence analysis studies UVeQFed with federated averaging under standard smoothness, strong-convexity, and stochastic-gradient assumptions. It establishes O(1/t) convergence while identifying dimensionality and participation limits.

  • Assumptions: The analysis permits statistically heterogeneous user data rather than requiring identical data distributions.The heterogeneity gap ψ tends toward zero for common-distribution data and remains positive for heterogeneous data.
  • Convergence guarantee: Theorem 3 establishes convergence for UVeQFed with local SGD under AS1–AS3 and a specified diminishing step size.The assumptions include smooth, strongly convex local objectives and stochastic-gradient conditions.
  • Convergence guarantee: O(1/t) convergence is achieved by UVeQFed with local SGD, matching the stated order for FL without quantization constraints.The objective difference from the optimum decays to zero at least as quickly as 1/t up to a constant.
  • Scope and limitations: The quantization contribution to coefficient b grows with the number of model parameters through M.The analysis also notes that larger model dimensionality typically slows FL convergence.
  • Empirical comparison: Empirically, UVeQFed converges to more accurate global models than probabilistic scalar quantizers on both i.i.d. and heterogeneous datasets.The cited comparison is reported for FL using these two data settings.
  • Scope and limitations: Analysis of UVeQFed with partial node participation and channel coding is left for future work.The text identifies partial participation as a way to reduce uplink communication load but does not analyze it here.

V. NUMERICAL EVALUATIONS

The numerical evaluations compare UVeQFed with prior quantization methods on distortion and federated-learning convergence. UVeQFed generally provides more accurate representations and faster, more accurate convergence across data distributions, rates, and datasets.

  • B. FL Convergence: UVeQFed translates reduced quantization distortion into improved trained-model accuracy and faster convergence relative to prior methods.The comparison includes QSGD, random-rotation uniform quantization, and random subsampling followed by three-bit quantization.
  • A. Quantization Error: UVeQFed achieves lower quantization distortion than previously proposed methods for both independent and correlated data.The comparisons use equal overall bit rates and evaluate synthetic matrix data across quantization rates R.
  • A. Quantization Error: Vector quantization outperforms scalar quantization, with larger gains when quantized entries are correlated.The result is attributed to jointly encoding multiple samples and exploiting statistical correlation with fixed lattice regions.
  • B. FL Convergence: UVeQFed with L = 2 achieves the most rapid and accurate convergence among the MNIST schemes at R = 2 and R = 4.At R = 4, its convergence profile is within a minor gap of federated averaging without quantization.
  • B. FL Convergence: The gains are more dominant at R = 2, and UVeQFed with L = 1 generally outperforms QSGD across the considered setups.The reported convergence improvements are linked to reduced quantization distortion.

VI. CONCLUSIONS

The paper concludes that UVeQFed applies universal vector quantization to communication-limited federated learning. Its theoretical and numerical analyses show reduced distortion and convergence behavior comparable in asymptotic rate to unquantized local SGD.

  • VI. CONCLUSIONS: UVeQFed uses universal vector quantization to mitigate limited communication in federated learning.The scheme is based on a dithered lattice quantization encoding-decoding strategy.
  • VI. CONCLUSIONS: Federated averaging mitigates UVeQFed’s quantization error as the number of users grows.The conclusion states that the analysis characterizes this error reduction theoretically.
  • VI. CONCLUSIONS: UVeQFed has the same asymptotic convergence decay rate as unquantized local SGD.This is the paper’s theoretical convergence characterization.
  • VI. CONCLUSIONS: At the same number of bits, UVeQFed achieves more accurate model-update recovery than previously proposed schemes.The numerical study evaluates non-synthetic MNIST and CIFAR-10 data sets.
  • VI. CONCLUSIONS: Reduced distortion is translated into improved convergence on MNIST and CIFAR-10.The conclusion connects update-recovery accuracy with the resulting federated-learning training behavior.

APPENDIX

The appendix establishes the statistical properties of subtractive dithered quantization errors and uses them to represent and analyze the quantized federated-learning update. It then derives the desired global-model relation through expectation arguments.

  • Appendix: Subtractive dithering makes the quantization error zero-mean, independent of the quantized value, and uniformly distributed over the lattice’s fundamental region.These properties hold regardless of the statistical model of the quantized model update.
  • Appendix: The quantized global-model update is decomposed into the desired model update and an additive quantization-noise term.The appendix uses decoding and model-recovery steps to obtain this representation.
  • Appendix: Expectation arguments exploit independent sample indices and zero-mean quantization errors to derive the update identities used in the theorem proofs.The derivation invokes the law of total expectation and the fact that stochastic gradients average to the full gradient.

C. Proof of Theorem 3

The proof models subtractive-dither quantization as additional noise in federated learning, then compares a virtual SGD-like sequence with the actual FL weights. Under the stated assumptions and step-size conditions, it derives a convergence bound.

  • C. Proof of Theorem 3: Subtractive dithering permits the quantization contribution to be incorporated rigorously as additive noise in the FL update.The resulting noise is zero-mean and independent of the model update, enabling the proof’s expectation arguments.
  • C. Proof of Theorem 3: A virtual sequence is constructed to behave almost like mini-batch SGD while remaining within bounded distance of the FL model weights.It coincides with the FL weights at integer multiples of the aggregation interval τ.
  • C. Proof of Theorem 3: The virtual-sequence recursion bounds its expected distance from the optimal weights using the assumptions on the objective and gradient noise.Expression (C.4) provides the recursive distance bound, which is refined using Lemmas C.1 and C.2.
  • C. Proof of Theorem 3: Choosing a non-increasing step size satisfying η_t ≤ 1/(4ρ_s) and η_t ≤ 2η_{t+τ} yields the required recursive bounds.The proof uses η_t = β/(t+γ) with parameters selected to satisfy these conditions.
  • C. Proof of Theorem 3: Under these settings, the model-weight error decays at a polynomial rate bounded by δ_t ≤ ν/(t+γ).The proof establishes the bound by induction and then combines it with smoothness and strong convexity to prove the theorem.

3) Deferred Proofs:

This section provides deferred proofs for intermediate lemmas used in the analysis. The derivations rely on independence, uniform sampling, assumptions, and substitutions into preceding inequalities.

  • The proof of Lemma C.1 uses independence between quantization noise and stochastic gradients to derive the stated relation.
  • Uniform random-index sampling makes the expected stochastic gradient equal to the full gradient, with AS1 supplying the required condition.
  • The UVeQFed quantization error is bounded in the subsequent derivation, completing the relevant step of the proof.
  • The proof of Lemma C.2 separates the case t = t0 from t > t0, where t0 is the largest multiple of τ not exceeding t.
  • Assumption AS1 and the bound ηt0 ≤ ηt−τ ≤ 2ηt support the derivation, and substituting the resulting inequality proves the lemma.
Loading 2006.03262v3…