PaperlayerView exact revision on arXiv

Source-linked AI summary

cpSGD: Communication-efficient and differentially-private distributed SGD

Naman Agarwal, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, H. Brendan Mcmahan

arXiv:1805.10559v1stat.MLcs.CRcs.LG

TL;DR

The paper addresses the gap between communication-efficient distributed learning and rigorous client privacy. It combines randomized rotation with a discrete Binomial mechanism to obtain both properties. For ε = O(1) and n ≈ d, the method matches Gaussian privacy and error with O(log log(nd)) bits per client per coordinate, while the Binomial analysis improves prior bounds.

  • Problem

    Communication-efficient distributed learning methods lack known privacy guarantees, while standard privacy mechanisms incur high communication costs for mobile clients.

    Source: §1.1 · p. 2

  • Method

    The paper combines random rotation and high-probability sensitivity with a discrete Binomial mechanism for differentially private distributed mean estimation.

    Source: §1.4 · p. 5

  • Results

    For ε = O(1) and n ≈ d, the method achieves Gaussian-equivalent privacy and error with O(log log(nd)) bits per client per coordinate.

    Source: §1.4 · p. 5

  • Takeaways & Limitations

    The proposed approach jointly supports communication efficiency and differential privacy, while the Binomial mechanism provides nearly Gaussian utility with fewer representation bits.

    Source: §1.4 · p. 5

    The tightness of the Binomial-mechanism analysis and the effects of neural-network topology, over-parameterization, and optimization algorithms remain open questions.

    Source: §6 · p. 13

Abstract

from arXiv · show

Distributed stochastic gradient descent is an important subroutine in distributed learning. A setting of particular interest is when the clients are mobile devices, where two important concerns are communication efficiency and the privacy of the clients. Several recent works have focused on reducing the communication cost or introducing privacy guarantees, but none of the proposed communication efficient methods are known to be privacy preserving and none of the known privacy mechanisms are known to be communication efficient. To this end, we study algorithms that achieve both communication efficiency and differential privacy. For $d$ variables and $n \approx d$ clients, the proposed method uses $O(\log \log(nd))$ bits of communication per client per coordinate and ensures constant privacy. We also extend and improve previous analysis of the \emph{Binomial mechanism} showing that it achieves nearly the same utility as the Gaussian mechanism, while requiring fewer representation bits, which can be of independent interest.

1 Introduction

Distributed SGD faces a joint communication and privacy challenge, especially for mobile clients. The paper develops communication-efficient differentially private mechanisms based on randomized rotation and Binomial noise, with improved analysis and low communication.

Motivation

  • Gradient transmission can bottleneck distributed learning, particularly for mobile clients with expensive uplink communication.Quantization and sparsification reduce communication cost, but their privacy guarantees are unclear.Source: §1.1 · p. 2, §1.2 · p. 2, §1.3 · p. 3

Optimization analysis

  • The SGD convergence analysis relates performance to gradient-estimation mean square error and bias, motivating distributed mean estimation as the central subproblem.Smaller gradient-estimation mean square error yields better convergence in the stated analysis.Source: §1.2 · p. 3

Privacy and communication

  • Direct Gaussian-noise privacy mechanisms require n·d real values, while discrete Binomial noise supports efficient transmission and secure aggregation.The Binomial mechanism also avoids floating-point representation issues and has bounded, analyzable communication complexity.Source: §1.3 · p. 4, §1.4 · p. 5

Binomial mechanism

  • N ≥ 8 log(2/δ)/ε^2 suffices for small ε, implying Binomial and Gaussian mechanisms have identical performance as ε → 0.The paper presents this as an improvement over the previous requirement N ≥ 64 log(2/δ)/ε^2.Source: §1.4 · pp. 4–5

Core approach

  • Random rotation combined with high-probability sensitivity significantly improves differentially private distributed mean estimation.Clients and the server generate a shared random orthogonal matrix for the rotated protocol.Source: §1.4 · p. 5

Main guarantee

  • For ε = O(1), the proposed distributed mean estimation algorithm matches Gaussian privacy and error while reducing communication.When d ≈ n, communication is n·d·log(log(nd)/δ) bits per SGD round.Source: §1.4 · p. 5

2 Differential privacy

The paper defines differential privacy through neighboring datasets and query sensitivity, then introduces high-probability sensitivity for randomized queries. A private mechanism composed with such a query remains private with an additional δ term.

Definitions

  • Differential privacy requires similar output distributions for neighboring datasets under every measurable event.The mechanism is evaluated on datasets differing in one user’s information.Source: §2.1 · p. 5
  • Sensitivity measures how much a query can change between neighboring datasets in a chosen ℓq norm.The paper considers output spaces in Rd and uses mean square error to measure mechanism error.Source: §2.1 · pp. 5–6

Gaussian mechanism

  • The Gaussian mechanism adds Gaussian noise calibrated to an ℓ2 sensitivity bound and provides an error bound proportional to d · σ2.Its noise is isotropic with covariance σ2Id.Source: §2.1 · p. 6

High-probability sensitivity

  • High-probability sensitivity couples outputs on neighboring datasets so their distance satisfies specified bounds except with probability δ′.The definition preserves the original marginal distributions of the randomized query outputs.Source: §2.2 · p. 6
  • Composing an (ε, δ)-private mechanism with a (ΔQ, δ′)-sensitive randomized query yields (ε, δ + δ′)-differential privacy.This composition lemma enables privacy analysis when sensitivity is bounded only with high probability.Source: §2.2 · p. 6

3 Binomial Mechanism

The Binomial mechanism releases discretized, independently perturbed coordinates and extends its privacy analysis to d dimensions. Its utility approaches the Gaussian mechanism as the quantization scale decreases, while its privacy depends on multiple sensitivity norms.

Mechanism

  • The Binomial mechanism releases a discretized query by adding scaled Binomial noise independently to each coordinate.It is parameterized by N, p, and quantization scale s.Source: §3 · p. 7

Analysis

  • The d-dimensional analysis exploits local rotation invariance near the mean because the Binomial distribution is not globally rotation invariant.This extends the earlier one-dimensional analysis to arbitrary p and multiple dimensions.Source: §3 · p. 7

Guarantees

  • For p = 1/2, the mechanism’s error is d · s2 · Np(1 −p), under the theorem’s sensitivity conditions.The theorem states privacy using Δ1, Δ2, and Δ∞ bounds and constants bp, cp, and dp.Source: §3 · p. 7

Design considerations

  • Unlike the Gaussian mechanism, Binomial privacy depends on Δ2, Δ∞, and Δ1 because discretization introduces additional sensitivity terms.The quantization scale s helps normalize the noise when integer resolution would otherwise be too coarse.Source: §3 · p. 7

Empirical comparison

  • As the scale is reduced, the Binomial mechanism’s error-versus-privacy trade-off approaches that of the Gaussian mechanism.The comparison is shown in Figure 1 across different scales.Source: §3 · pp. 7–8, Figure 1 · p. 8

4 Distributed mean estimation (DME)

Distributed mean estimation is used as the analytical building block for distributed SGD: its MSE controls convergence, while its communication and privacy bounds transfer to the learning algorithm. The protocols assume bounded client-vector norms and support simultaneous independent communication.

Analytical reduction

  • Smaller gradient-estimation MSE yields better convergence, so the analysis focuses on DME error and privacy guarantees.Convergence follows from the stated SGD reduction through Corollary 1.Source: §4 · p. 8

Guarantee transfer

  • Communication bounds for SGD follow from the communication cost of estimating gradient means, while privacy bounds follow through composition across rounds.Client sampling can further tighten privacy through standard privacy amplification results.Source: §4 · p. 8

DME formulation

  • Distributed mean estimation computes the mean of client-held vectors and underlies distributed PCA, clustering, and gradient descent.For gradient descent, each client vector is instantiated as a gradient at the current round.Source: §4 · p. 8

Distributed SGD

  • Distributed SGD sends client gradient estimates to a server, which aggregates them to update the global model.At each round, the server broadcasts the current model and samples clients for gradient transmission.Source: §4 · p. 8

Assumptions

  • The analysis assumes each client vector has bounded ℓ2 norm, an assumption commonly enforced through client-side gradient clipping.The paper states that its results also hold for all gradients without statistical assumptions.Source: §4 · pp. 8–9, §4.2 · p. 9

Communication model

  • The DME protocols are simultaneous and independent, with clients transmitting functions of their local vectors to a central estimator.Both private and public randomness are allowed; public randomness can be emulated by communicating a random seed.Source: §4.1 · p. 9, §4.2 · p. 9

5 Results for distributed mean estimation (DME)

The section develops quantized Binomial mechanisms for private distributed mean estimation and shows that randomized rotation substantially reduces their communication cost while preserving Gaussian-level utility and privacy under stated conditions.

Gaussian mechanism

  • The Gaussian baseline provides an unbiased mean estimate but requires n · d real numbers for communication.Source: §5.1 · p. 10

Binomial mechanism

  • The Binomial mechanism stochastically quantizes each coordinate, adds scaled Binomial noise, and lets the server subtract the noise bias for an unbiased estimate.Source: §5.2 · p. 11
  • The Binomial mechanism achieves the same privacy and error as the full-precision Gaussian mechanism with a finite representation.Source: §5.2 · p. 12

Randomized rotation

  • Random rotation reduces the leading communication term and improves the privacy guarantee by lowering the relevant sensitivity after quantization.Source: §5.3 · p. 12
  • Random rotation uses public randomness to transform client vectors, applies the protocol in rotated space, and maps the estimate back to the original basis.Source: §5.3 · p. 12
  • If d = O(nε2), the rotated Binomial method matches Gaussian privacy and utility with O(nd log log(nd/δε)) total communication.Source: §5.3 · p. 13

6 Discussion

The discussion evaluates the methods in a large-scale MNIST setting with one epoch of training and varying communication and privacy parameters, while identifying open theoretical and practical questions.

Experimental setting

  • The experiment trains a three-layer ReLU model on infinite MNIST using 25M data points and 25M clients, with 10,000 clients participating per step.Source: §6 · p. 13

Results

  • The models attain different accuracy levels depending on communication cost and privacy parameter ε.Source: §6 · p. 13

Experimental setting

  • One training epoch ensures each sample is used at most once, so per-batch ε equals overall ε in this setting.Source: §6 · p. 13

Future directions

  • Future work includes tightening the Binomial analysis, improving privacy accounting with a moments accountant, and studying model topology and optimization effects.Source: §6 · p. 13

A Proof of biased SGD

The proof adapts a standard SGD argument to account for bias in the gradient estimates and derives the convergence inequality by rearranging and summing over iterations.

  • The proof defines δ_t as the difference between the estimated gradient and the true gradient at the preceding iterate.Source: A Proof of biased SGD · p. 17
  • Using the condition γL ≤ 1, the analysis rearranges the resulting inequality and sums it over all iterations.Source: A Proof of biased SGD · p. 17

B Binomial Mechanism - Proof of Theorem 1

The proof establishes privacy for the multidimensional Binomial mechanism by controlling likelihood ratios on a high-probability event and applying concentration inequalities to independent binomial variables.

Mechanism and sensitivities

High-probability event

Concentration tools

Sensitivity reduction

Privacy bound

C High probability sensitivity Proof

The proof establishes (ε, δ + δ′)-differential privacy by comparing outputs on neighboring data sets through a coupling argument.

D Application of Binomial Mechanism to Distributed Mean Estimation - Proof of Theorem 3

Theorem 3 proves communication, mean-square-error, and sensitivity guarantees for the protocol using binomial randomization.

Communication complexity

Mean Square Error

Differential Privacy

The differential-privacy proof analyzes bin-based randomized quantization on neighboring data sets, establishes high-probability sensitivity bounds, and composes the protocol with the binomial mechanism.

Sensitivity bounds

  • The protocol is analyzed on neighboring data sets that differ in one client, with sensitivity measured in ℓ1, ℓ2, and ℓ∞ norms.Source: Differential Privacy · p. 24

Privacy guarantee

  • πsk(Bin(m, p)) is (ε, 2δ)-differentially private under the conditions supplied by Theorem 3 and the preceding privacy theorem.Source: Differential Privacy · p. 24

Randomized quantization

  • Each value is assigned to a bin and randomized between adjacent bin indices according to its position within the bin.Source: Differential Privacy · p. 25

Coupling construction

  • Couplings are constructed by separating coordinates with matching and differing bin indices and sampling the associated random variables accordingly.Source: Differential Privacy · p. 25
  • The coupling preserves the relevant marginal distributions, while shared coordinates remain equal across the neighboring data sets.Source: Differential Privacy · p. 26

Sensitivity bounds

E Quantization with Rotation

The rotation-based protocol transfers the quantization mechanism to rotated data and combines privacy and error guarantees over good rotation matrices.

Differential Privacy

  • The proof defines good rotations as a subset of d × d orthonormal matrices and analyzes the protocol separately on that set.Source: Differential Privacy · p. 28
  • For a rotated neighboring data set, the privacy analysis integrates the quantization mechanism’s guarantee over rotation matrices and accounts for rotations outside the good set.Source: Differential Privacy · p. 28
  • The rotated protocol provides (ε, 3δ)-differential privacy.Source: Differential Privacy · p. 28

Mean Square Error

  • The total change to any individual client vector is bounded by 2D in ℓ2 norm, yielding a total MSE bound of at most 4D^2.Source: Differential Privacy · p. 28
  • The final MSE argument combines the base protocol’s guarantee with the fact that the rotation lies in the good-rotation set.Source: Differential Privacy · p. 28

Related papers

Loading 1805.10559v1…