Source-linked AI summary
cpSGD: Communication-efficient and differentially-private distributed SGD
Naman Agarwal, Ananda Theertha Suresh, Felix Yu, Sanjiv Kumar, H. Brendan Mcmahan
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.
Method
The paper combines random rotation and high-probability sensitivity with a discrete Binomial mechanism for differentially private distributed mean estimation.
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.
Takeaways & Limitations
The proposed approach jointly supports communication efficiency and differential privacy, while the Binomial mechanism provides nearly Gaussian utility with fewer representation bits.
Takeaways & Limitations
The tightness of the Binomial-mechanism analysis and the effects of neural-network topology, over-parameterization, and optimization algorithms remain open questions.
Abstract
from arXiv · showhide
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.
- 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.
- 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.
- 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.
- 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.
- 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.
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.
- Definitions: 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.
- 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.
- 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.
- High-probability sensitivity: 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.
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.
- 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.
- 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.
- 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.
- 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.
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.
- 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.
- 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.
- 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.
- 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.
- 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.
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.
- 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.
- Binomial mechanism: The Binomial mechanism achieves the same privacy and error as the full-precision Gaussian mechanism with a finite representation.
- Randomized rotation: Random rotation reduces the leading communication term and improves the privacy guarantee by lowering the relevant sensitivity after quantization.
- Randomized rotation: Random rotation uses public randomness to transform client vectors, applies the protocol in rotated space, and maps the estimate back to the original basis.
- Randomized rotation: If d = O(nε2), the rotated Binomial method matches Gaussian privacy and utility with O(nd log log(nd/δε)) total communication.
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.
- Results: The models attain different accuracy levels depending on communication cost and privacy parameter ε.
- Experimental setting: One training epoch ensures each sample is used at most once, so per-batch ε equals overall ε in this setting.
- Future directions: Future work includes tightening the Binomial analysis, improving privacy accounting with a moments accountant, and studying model topology and optimization effects.
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.
- Using the condition γL ≤ 1, the analysis rearranges the resulting inequality and sums it over all iterations.
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: The Binomial mechanism releases f(D) plus centered, scaled Binomial noise and analyzes privacy through ℓ_q sensitivities for q ∈ {1, 2, ∞}.
- High-probability event: The proof constructs a high-probability event controlling deviations of the binomial counts from their mean and verifies several conditions on that event.
- Concentration tools: Bernstein’s inequality controls concentration of sums involving independent binomial variables, while Efron–Stein bounds variance through coordinate replacements.
- Sensitivity reduction: Scaling the released quantity changes the sensitivity by the reciprocal scale, allowing the proof to reduce to unit scale before analyzing the Binomial noise.
- Privacy bound: The privacy argument compares probabilities under neighboring data sets and bounds the resulting likelihood-ratio exponent using the auxiliary lemmas.
C High probability sensitivity Proof
The proof establishes (ε, δ + δ′)-differential privacy by comparing outputs on neighboring data sets through a coupling argument.
- The proof considers any two neighboring data sets and any measurable output event.
- A coupling of the relevant random variables is used to compare their joint behavior.
- The argument derives its cases from the coupling condition and the existing (ε, δ)-differential privacy guarantee.
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: log(k + m) bits suffice because the protocol transmits integers in the range [0, k + m).
- Mean Square Error: The proof establishes the protocol’s mean-square-error bound using independence and unbiasedness of the estimator.
- Mean Square Error: The theorem’s parameter choices for m, p, and k yield the stated MSE bound.
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.
- Privacy guarantee: πsk(Bin(m, p)) is (ε, 2δ)-differentially private under the conditions supplied by Theorem 3 and the preceding privacy theorem.
- Randomized quantization: Each value is assigned to a bin and randomized between adjacent bin indices according to its position within the bin.
- Coupling construction: Couplings are constructed by separating coordinates with matching and differing bin indices and sampling the associated random variables accordingly.
- Coupling construction: The coupling preserves the relevant marginal distributions, while shared coordinates remain equal across the neighboring data sets.
- Sensitivity bounds: Bernstein’s inequality and a union bound provide high-probability bounds for the ℓ1 and ℓ2 sensitivity analyses.
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.
- Differential Privacy: 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.
- Differential Privacy: The rotated protocol provides (ε, 3δ)-differential privacy.
- 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.
- Mean Square Error: The final MSE argument combines the base protocol’s guarantee with the fact that the rotation lies in the good-rotation set.