Many private machine learning systems rely on one trusted server. Clients send raw updates, and the server adds noise before releasing anything. If that server is dishonest, the privacy guarantee disappears. Serverless "gossip" learning, where each device averages its model only with its graph neighbors, removes the server. It reaches server-level accuracy only through one specific trick: neighboring nodes add noise that is secretly paired so that it cancels when the whole network averages. That trick was proven only for messages sent as exact real numbers. Real peer-to-peer links send a few bits per coordinate. Rounding a noisy message is a non-linear operation, so it breaks the cancellation. We propose a gossip protocol in which the paired noise is drawn on the same integer grid the messages are rounded to, and is added after rounding, so it cancels exactly. Rounding errors are carried forward in a local memory instead of being counted as privacy noise.
The payoff is a clean question that nobody in the supplied literature has asked: how many bits per coordinate does removing the trusted server cost? Our central prediction is that the answer is governed by the ratio between the large canceling noise, which hides a node from its neighbors, and the small non-canceling noise that actually buys the formal privacy guarantee. Above that bit budget, accuracy should be the same as unquantized serverless training at the same privacy level. Below it, no scheme in this family can keep up. If this holds, "quantization-invariant convergence" gets a precise meaning in the private regime. Private training never converges exactly. The target is instead that quantization adds nothing to the error that privacy already forces.
Where the two literatures stand
Work on quantized decentralized optimization has shown that coarse messages need not limit accuracy. Three ingredients do this. Shrinking the quantization range over time is one (Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization; Distributed Optimization with Finite Bit Adaptive Quantization reports exact linear convergence at 3 bits per message). Logarithmic grids are another (Log-Scale Quantization in Distributed First-Order Methods). The third is error feedback, meaning nodes send differences and keep what rounding discarded in a local buffer. Differential Error Feedback for Communication-Efficient Decentralized Learning (DEF-ATC) matches uncompressed accuracy at about 2.4 bits per component. None of these papers treats privacy. We reuse error feedback as the method-supplying ingredient.
On the trust side, the motivating result is The Privacy Power of Correlated Noise in Decentralized Learning (DECOR). In DECOR, neighbors $i$ and $j$ share a secret seed. Node $i$ adds $+v_{ij}$ and node $j$ adds $-v_{ij}$, plus a small independent residual noise. The pairs cancel in the network average, and the protocol matches the accuracy of a trusted-server scheme on any connected graph. Optimizing Privacy-Utility Trade-off in Decentralized Learning with Generalized Correlated Noise (CorN-DSGD) generalizes the pairs to a network-wide noise covariance chosen by a semidefinite program. Both papers assume messages are exact real numbers.
The research file points out that if messages are rounded, $Q(x_i+v_{ij})+Q(x_j-v_{ij})\neq x_i+x_j$. That observation is the gap we attack.
Three bridging papers constrain the design:
- Subspace perturbation. ADQSP uses rounding error itself as privacy noise through a floor $\Delta_{\min}$ on the grid width. The result is a hard toggle: with $\Delta_{\min}>0$ it has differential privacy and an error floor, and with $\Delta_{\min}=0$ it converges exactly with no differential privacy. We read this as a warning against letting quantization error double as privacy noise.
- Initialization masking. Communication efficient privacy-preserving distributed optimization using adaptive differential quantization reaches a mean squared error of about $10^{-10}$ with a 1-bit quantizer. It hides private data only by masking the initial state, against passive adversaries, and gives no formal $(\epsilon,\delta)$ guarantee.
- Quantization as privacy. Quantization enabled Privacy Protection in Decentralized Stochastic Optimization gets $(0,\delta)$ privacy from a stochastic three-level quantizer. It settles only in a neighborhood of the optimum set by the level $r$.
Finally, The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation supplies our noise primitive: discrete Gaussian noise on integers, with privacy accounting after rounding. It requires a central server running secure aggregation, which is the very trust we are removing.
Core Claim
Correlated-noise gossip survives coarse quantization if three roles are kept apart:
- the signal is rounded, with error feedback, onto a grid of width $\Delta$;
- the canceling noise and the private residual noise are drawn as integers on that same grid and added after rounding;
- the grid never shrinks below the scale of the residual noise.
Concretely, node $i$ at round $t$ sends
$$m_i^t=\mathrm{round}\!\left(\frac{x_i^t+e_i^t}{\Delta}\right)+z_i^t+\sum_{j\in N(i)} s_{ij}\,v_{ij}^t,\qquad e_i^{t+1}=x_i^t+e_i^t-\Delta\,\mathrm{round}\!\left(\frac{x_i^t+e_i^t}{\Delta}\right).$$
The symbols are:
- $x_i^t$ is the node's model after its local gradient step;
- $e_i^t$ is its rounding memory;
- $z_i^t$ is independent discrete Gaussian noise with standard deviation $\sigma_{dp}/\Delta$ in grid units;
- $v_{ij}^t$ is discrete Gaussian noise with standard deviation $\sigma_{cor}/\Delta$, generated from the seed shared by $i$ and $j$;
- $s_{ij}=-s_{ji}\in\{\pm1\}$ is the sign that makes each pair cancel;
- $N(i)$ is the set of neighbors of $i$.
The receiver rescales by $\Delta$ and mixes as usual. Because the canceling terms are integers added after rounding, $\sum_i m_i^t$ equals $\sum_i \mathrm{round}(\cdot)+\sum_i z_i^t$ exactly. The error-feedback memory keeps rounding from biasing the network average over time, as in DEF-ATC. Privacy against curious or colluding neighbors comes only from $z$ and the uncanceled part of $v$. It is accounted with discrete Gaussian Rényi bounds.
The bit cost is the crux, and we state it as a prediction. A third-party neighbor does not know $v_{ij}$. The message therefore carries entropy of order $\log_2$ of the canceling noise's spread in grid units. This suggests a lower bound of roughly
$$b \;\gtrsim\; \log_2\!\left(\frac{\sigma_{cor}}{\max(\Delta,\sigma_{dp})}\right)$$
bits per coordinate for any protocol that hides nodes by canceling noise. We expect our construction to reach this bound within a constant.
The prediction implies that naive schemes pay more. With stochastic unbiased rounding applied to the already-noisy message, the rounding step must scale with the full message range, which is dominated by $\sigma_{cor}$. That rounding noise does not cancel, so it reintroduces the independent-noise penalty that DECOR was built to remove.
Research Program
The program has four parts.
Privacy analysis under continual observation. We will prove that error-feedback rounding increases the sensitivity of each release by at most one grid step per coordinate. We will then extend the linear state-space sensitivity analysis of Differential Privacy Analysis of Decentralized Gossip Averaging under Varying Threat Models, which shows squared sensitivity growing as $O(T)$ for unquantized gossip, to include the rounding memory. This yields $(\epsilon,\delta)$ guarantees under DECOR's secret-seed threat model, including sets of colluding neighbors.
Convergence analysis. We will prove that, above the bit threshold, the optimality gap of our protocol equals that of unquantized DECOR plus a term controlled by $\Delta$. The term enters through error feedback rather than accumulating.
Bit-cost bound. We will make the entropy lower bound rigorous for pairwise and covariance-based canceling noise.
Bit-aware noise design. We will pose a variant of the CorN-DSGD covariance program that minimizes the required bits subject to privacy against a given colluding set, instead of minimizing utility loss alone. Because the program is tractable only up to about 100 nodes, this part is restricted to that scale.
Baselines
Naive references. The do-nothing reference point is uncompressed, non-private gossip SGD. It fixes the best reachable accuracy. The naive private reference is independent local noise followed by standard stochastic rounding. For this family, DECOR reports that local noise "lost nearly 10 accuracy points" on MNIST at low privacy budgets.
Main target: unquantized DECOR. The strongest existing method on our question is DECOR run with 32-bit floats. On MNIST with a one-hidden-layer network it "stayed within 1% of the centralized accuracy baseline." Beating it means matching that accuracy, at the same accounted $\epsilon$, graph, and gradient budget, while sending $b\le 4$ bits per coordinate.
Direct competitor: naive quantized DECOR. We run DECOR messages through two off-the-shelf quantizers, deterministic rounding and unbiased stochastic rounding, at each $b\in\{1,2,3,4,8,16\}$. Here we must win outright at low $b$. At 16 bits we expect a tie, and we will report it.
Covariance-based noise. CorN-DSGD is the stronger continuous-valued variant on sparse graphs. For it, no reported result found on Lacuna for numerical MNIST or a9a values. We rerun it on Erdős–Rényi graphs with $p\le0.4$ at up to 100 nodes.
Quantization-as-privacy schemes. These are the ternary scheme of Quantization enabled Privacy Protection and ADQSP with $\Delta_{\min}>0$. To compare them fairly, we convert their guarantees to a common $(\epsilon,\delta)$ where possible and tune their levels to the same budget. Where conversion is not possible, we report the attack results described below.
Server-based upper reference. The distributed discrete Gaussian mechanism with a central server shows what trusting a server buys at under 16 bits.
Ablations. Two ablations isolate the key ingredient. One keeps grid-aligned noise but removes error feedback. The other keeps error feedback but adds the canceling noise before rounding.
Fairness conditions. All methods get the same data partitions, graphs, step-size search grid, and number of gradient evaluations. Every method is charged total transmitted bits, including entropy-coded size.
Why not just…?
Why not just quantize DECOR's messages at 8 or 16 bits? This is a real threat when bandwidth is loose. At 16 bits the non-canceling rounding residual is tiny, and the precedent that 16-bit discretization matches server-level accuracy (Distributed Discrete Gaussian) suggests it will work. Our claim is confined to the 1–4 bit regime that DEF-ATC and DOFiBAQ show is enough without privacy. The bit sweep settles the question. If naive quantized DECOR matches us at 4 bits, the alignment ingredient adds nothing, and we will narrow the contribution to the bit-cost bound.
Why not just use unbiased stochastic rounding, since its errors average out? They average out only as independent noise. Its step size must span the whole noisy message, which is dominated by $\sigma_{cor}$, so its variance grows with $\sigma_{cor}^2/4^b$ and does not cancel. This is the independent-noise penalty DECOR removes. The stochastic-rounding arm of the naive-DECOR baseline measures this directly.
Why not just mask the initial state once, as in QADMM, and pay no per-round noise bits? That scheme gets remarkable precision from 1 bit, but it has no formal guarantee under repeated observation. We will run a neighbor-reconstruction attack, in which colluding neighbors isolate a node and invert its updates, against it and against our protocol. We will also report accounted $\epsilon$ for ours. If the attack fails against masking at our graph sizes, we will say so.
Why not just keep the server and use secure aggregation? That changes the trust model rather than meeting it. Collusion or manipulation by the aggregator (Beyond Inferring Class Representatives) and the lack of servers in mesh settings are exactly what we target. We include it only as an upper reference.
Proposed Experiments
Datasets and graphs. Tasks are regularized logistic regression on a9a and a one-hidden-layer network on MNIST, the settings DECOR and CorN-DSGD use. Graphs are rings, Erdős–Rényi graphs with $p\in\{0.2,0.4\}$, and 30-node geometric graphs, with $n$ from 30 to 100. Privacy budgets are $\epsilon\in[3,40]$, the range CorN-DSGD uses. Metrics are test loss and accuracy, optimality gap, accounted $\epsilon$, total bits to reach a target loss, and deep-leakage-from-gradients (DLG) reconstruction error on MNIST.
Decisive checks. Four results decide the proposal:
- At $b\le4$, naive quantized DECOR should show an error floor that grows with $\sigma_{cor}$, while our protocol tracks unquantized DECOR.
- Sweeping $\sigma_{cor}/\sigma_{dp}$, the smallest $b$ that matches unquantized accuracy should grow as $\log_2$ of that ratio. A flat or linear trend would falsify the bound.
- Each ablation should fail in its predicted way. Without error feedback there should be drift in the average. With noise added before rounding there should be a floor that grows with the local-noise level.
- The bit-aware covariance should reduce bits per coordinate relative to pairwise DECOR at equal privacy against a fixed colluding set on sparse graphs.
References
- Fast Convergence Rates of Distributed Subgradient Methods With Adaptive Quantization
- Distributed Optimization with Finite Bit Adaptive Quantization for Efficient Communication and Precision Enhancement
- Log-Scale Quantization in Distributed First-Order Methods: Gradient-Based Learning From Distributed Data
- Differential Error Feedback for Communication-Efficient Decentralized Learning
- The Privacy Power of Correlated Noise in Decentralized Learning
- Optimizing Privacy-Utility Trade-off in Decentralized Learning with Generalized Correlated Noise
- Adaptive Differentially Quantized Subspace Perturbation (ADQSP): A Unified Framework for Privacy-Preserving Distributed Average Consensus
- Communication efficient privacy-preserving distributed optimization using adaptive differential quantization
- Quantization Enabled Privacy Protection in Decentralized Stochastic Optimization
- The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation
- Differential Privacy Analysis of Decentralized Gossip Averaging under Varying Threat Models
- Beyond Inferring Class Representatives: User-Level Privacy Leakage From Federated Learning