Research map / Federated learning and privacy / Differential privacy
Differentially Private Decentralized Learning with Random Walks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes the differential privacy guarantees of decentralized learning where a model is passed along a random walk over a graph, giving closed-form privacy amplification-by-iteration bounds that depend on the full spectrum of the transition matrix.
Problem
Privacy guarantees of decentralized learning via random walk (token-passing) algorithms, where model updates leak information to neighboring nodes, and how privacy depends on graph structure.
Approach
Applies privacy amplification by iteration (Feldman et al., 2018) to random-walk decentralized SGD, deriving per-pair privacy bounds that use all singular values of the graph transition matrix rather than only the spectral gap used by prior gossip analyses (Cyffers et al.), yielding tighter accounting on expander-like graphs.
Key results
- Privacy bounds for random walk algorithms use the entire transition-matrix spectrum; on expander graphs such as the exponential graph, random walk uniformly outperforms gossip privacy loss for all node pairs.
- Random walk offers smaller privacy loss for close nodes than gossip but higher loss for distant nodes, per the authors' comparison.
- Authors state accuracy gains over Local DP-SGD comparable to Cyffers and Bellet (2022) on complete graph, extended to expander and geometric graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use random-walk learning instead of gossip | Decentralized learning · Exponential graph | privacy loss | Helped |
| use random-walk learning instead of gossip | Decentralized learning · Graphs above the spectral threshold | privacy loss | Helped |
| use random-walk learning instead of gossip | Decentralized learning · Close node pairs | privacy loss | Helped |
| use random-walk learning instead of gossip | Decentralized learning · Distant node pairs | privacy loss | Hurt |
| use random-walk learning instead of gossip at the same communication level | Decentralized learning · Strongly convex optimization | convergence error | No clear effect |
| use random-walk learning instead of Muffliato | Decentralized learning · Houses dataset at fixed mean privacy | privacy loss | Helped |
| use random-walk learning instead of Local DP-SGD | Decentralized learning · Expander and geometric graphs | accuracy | Helped |
| use a 2D-grid rather than a well-connected expander graph | Random-walk learning · 2D-grid | privacy amplification | Hurt |
Surprising findings
- Privacy loss for random walk remains near local DP on poorly connected graphs such as the 2D-grid, showing little amplification.
Limitations
- Token passing is sequential and less parallelizable than gossip.
- Privacy bounds are complex and degrade linearly with the number of times a node shares its gradient; poorly connected graphs see little amplification.
- Convergence step size as stated depends on unknown x*; the Theorem 2 statement had a typo regarding the sensitivity dependence.
Experimental setup
Datasets: Facebook ego graph Davis Southern women social network houses dataset synthetic graphs (expander, geometric, ring, 2D-grid, complete)
Benchmarks: houses dataset Facebook ego graph Davis Southern women graph
Metrics: privacy loss (epsilon) mean squared error to optimum accuracy
Baselines: Local DP-SGD Muffliato (gossip-based private averaging) Cyffers et al. gossip privacy analysis
Builds on: privacy amplification by iteration Muffliato Even 2023 SGD convergence analysis Cyffers and Bellet 2022 network DP
Closest papers by meaning
- Mitigating the Privacy–Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy (NeurIPS 2025 · similarity 0.91)
- The Privacy Power of Correlated Noise in Decentralized Learning (ICML 2024 · similarity 0.91)
- Revisiting Differentially Private Algorithms for Decentralized Online Learning (ICML 2025 · similarity 0.89)
- Privacy Attacks in Decentralized Learning (ICML 2024 · similarity 0.88)
- Private and Federated Stochastic Convex Optimization: Efficient Strategies for Centralized Systems (ICML 2024 · similarity 0.87)
- Subgraph Federated Learning via Spectral Methods (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.