Differential Privacy of Decentralized Learning: Centralized Rate Conditions and Nearly Tight Guarantees

Antti Koskela; Tejas Kulkarni

cs.LGMay 26, 2025

Differential Privacy of Decentralized Learning: Centralized Rate Conditions and Nearly Tight Guarantees

Authors: Antti Koskela, Tejas Kulkarni

Organizations: Nokia Bell Labs

Abstract

We analyze the differential privacy of gossip averaging on a graph with independent Gaussian noise at every node, as seen by a subset of observing nodes. We characterize the privacy loss of any sensitive node over multiple gossip steps as that of a Gaussian mechanism whose sensitivity is the solution to a binary quadratic problem with a coefficient matrix determined by the gossip matrix. We recognize this matrix as a Toeplitz matrix plus a small correction, and show that its Toeplitz symbol controls how the DP guarantees grow with the number of steps. Under a computable condition on the Toeplitz symbol, the privacy guarantee matches that of a trusted central aggregator, and we give a utility bound for strongly convex learning problems that similarly matches the centralized case. Finally, we give numerical recipes for upper and lower bounds on the DP guarantees. On realistic test cases, the two bounds agree to within a few percent.

Figures & tables

Figure 1: Fraction of observer-target pairs violating the symbol condition ( 4.5 ) on Erdős–Rényi graphs

G(50,p)

200

graphs per

p

. Solid: observer adjacent to the target (

i\in N_{j}

), dashed: non-adjacent (

i\notin\bar{N}_{j}

Figure 2: Bounds on the scaled sensitivity

\Delta_{T}(j\to i)^{2}/T

versus

T

for the

10\times 10

2D grid (

n=100

), worst-case pair

(i,j)

. Upper bounds: spectral, entrywise ( Bellet et al., 2026 ) , certified SDP and certified triangle SDP. Lower bounds: constant sign vector and sign iteration with local search.

Figure 3: As Figure 2 , for the ring

C_{50}

(

n=50

Figure 4: As Figure 2 , for the Erdős–Rényi graph

G(n,p)

with

n=50

and

p=0.3

with Metropolis–Hastings normalization.

Figure 5: Test accuracy vs. training epochs on MNIST classification with

n=50

nodes and i.i.d. distributed data, comparing our decentralized DP method against the centralized DP baseline and Allouah et al. (2024) under

(\varepsilon,\delta)

-DP single-node view for

\delta=10^{-5}

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Quantity	Type	Cost
Spectral bound $T\lambda_{\max}(M)$	upper bound	one eigenvalue
Entrywise-absolute $U_{T}^{\rm abs}$	upper bound	$O(T^{2})$
Elliptope SDP at shifted dual	upper bound	SDP $+$ one eigenvalue
Triangle SDP	upper bound ( $d=1$ only)	SDP $+$ one eigenvalue
Constant sign vector $L_{T}^{\mathbf{1}}$	lower bound	$O(T^{2})$
Sign iteration $+$ one-flip $L_{T}^{\rm sign}$	lower bound	$O(T^{2})$ per sweep

Appendix

Table 1: List of numerical methods considered in Section 6 .

Figure 6: Final test accuracy versus privacy budget (

\varepsilon

) on the 2D

10\times 10

grid topology. Our method and that of Bellet et al. (2026) achieve identical utility, but their privacy accounting gives different

\varepsilon

values for the same algorithm, illustrating the impact of tighter analysis on the privacy-utility tradeoff.

Differential Privacy

Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.

See all 278 papers

Privacy Preserving Gossip Learning
Sep 13, 2026Erkan Bayram, Mohamed-Ali Belabbas, Tamer BaşarContinual Learning Decentralized Learning
University of Illinois Urbana Champaign, IL, USA
Communication-Efficient Distributed Learning with Differential Privacy
Apr 2, 2026Xiaoxing Ren, Yuwen Ma, Nicola Bastianello +3Communication-Efficient Distributed Training Differentially Private Federated Learning
School of Civil and Environmental Engineering, Cornell University, Ithaca, New York, United States. · Department of Electronic and Electrical Engineering, University College London, London WC1E 7JE, United Kingdom. · School of Electrical Engineering and Computer Science, and Digital Futures, KTH Royal Institute of Technology, Stockholm, Sweden. +4
Certification-Based Differentially Private Learning
Sep 30, 2026Mihnea Ghitu, Matthew WickerAbstract Interpretation Privacy-Preserving ML
Department of Computing Imperial College London London, United Kingdom

Sep 13, 2026J/K move · Enter open · S save

Privacy Preserving Gossip Learning

Erkan Bayram, Mohamed-Ali Belabbas, Tamer Başar

University of Illinois Urbana Champaign, IL, USA

Continual Learning Decentralized Learning Privacy-Preserving ML Differential Privacy

Open paper AskPDF arXiv

We propose a decentralized privacy-preserving learning algorithm in which each agent holds a single private sample and a shared model. Samples are learned sequentially, and each update must preserve the endpoint mappings at previously learned samples while protecting private data. This gives each agent three roles: (i) a learner that updates the model parameters, (ii) a teacher whose sample is learned at the current iteration, and (iii) a protected agent whose sample has already been learned. We build on Tuning without Forgetting (TwF) method to preserve previously learned mappings and show that TwF provides an indistinguishability guarantee for the learner whenever the set of protected agents contains another sample with the same label. For the teacher, we formulate a minimax optimal control problem that models the differential privacy noise as a worst-case disturbance to prevent performance loss while maintaining the same level of privacy for the gradient. For the protected agents, we compute the projections locally and aggregate them using a private push-sum gossip protocol. We prove geometric convergence of the decentralized gossip algorithm and of the distributed projection for TwF.

Abstract

Differential Privacy

Explore similar work

Privacy Preserving Gossip Learning

Communication-Efficient Distributed Learning with Differential Privacy

Certification-Based Differentially Private Learning