Revisiting Differentially Private Algorithms for Decentralized Online Learning

Xiaoyu Wang, Wenhao Yang, Chang Yao, Mingli Song, Yuanyu WanICML 2025 · OpenReview

Executive Summary

This paper introduces PD-FTGL, the first decentralized online learning algorithm to achieve strong $(\epsilon, 0)$-differential privacy over all $T$ rounds while nearly matching the optimal performance (regret) of non-private versions. By combining a novel block-decoupled communication strategy with tree-based privacy techniques, the authors demonstrate that privacy in decentralized learning can often be achieved "nearly for free."

The Challenge of Private Decentralized Learning

In Decentralized Online Convex Optimization (D-OCO), a network of learners collaborates to minimize a global loss function by making local decisions and communicating with neighbors. While decentralized setups naturally offer a baseline level of privacy by keeping data localized, they remain vulnerable to sophisticated attacks that can leak sensitive information from model updates.

Existing attempts to integrate Differential Privacy (DP)—the gold standard for data protection—into this setting have encountered three major roadblocks:

  1. Privacy Decay: Most current algorithms only guarantee privacy for a single round. Over $T$ rounds, the privacy protection weakens significantly, degrading to $(\epsilon T, 0)$-DP.
  2. Performance Gap: Adding sufficient noise to protect privacy typically destroys the algorithm's "regret" (a measure of how much better the learner could have performed with the benefit of hindsight).
  3. Computational Cost: Many algorithms require expensive "projection" steps to keep decisions within a feasible set. This becomes a severe bottleneck for complex, high-dimensional problems.

Proposed Methods: PD-FTGL and PD-OCG

To overcome these limitations, the authors propose two main algorithms:

  • PD-FTGL (Private Decentralized Follow-the-Generalized-Leader): As the core contribution, this algorithm uses a blocking update mechanism that divides the $T$ rounds into $L$ blocks. Within each block, it employs an accelerated gossip strategy to help learners reach a consensus quickly.
  • Tree-based Private Aggregation: To maintain strong privacy over time, the authors adapt a classical "tree-based" method for adding noise. The key innovation is block-decoupled communication. Standard decentralized methods couple every round together, making it impossible to use tree-based DP. By decoupling the communication between blocks, the authors can inject noise much more efficiently.
  • PD-OCG (Private Decentralized Online Conditional Gradient): This is a projection-free variant. Instead of relying on expensive projections, it uses simpler linear optimization steps (the Frank-Wolfe or Conditional Gradient method), making it significantly faster for complex constraints.

Datasets and Evaluation

The researchers evaluated their algorithms using two standard benchmarks from the LIBSVM repository:

Dataset Statistics
  • Letter: A dataset for character recognition with 15,000 examples and 16 features.
  • Poker: A much larger dataset for poker hand classification with 1,000,000 examples and 10 features.

These datasets were scaled up (creating $10n$ or $n$ copies) to simulate a large-scale decentralized environment with $n=9$ learners.

Key Results and Insights

Regret Bounds Comparison
  • Privacy "Nearly for Free": The authors prove that if the privacy parameter $\epsilon$ is sufficiently large relative to the network's connectivity (specifically, $\epsilon = \Omega(\sqrt{\rho})$ where $\rho$ is the spectral gap), their private algorithm's regret nearly matches the best possible non-private algorithm.
  • Regret Bounds: As shown in the theoretical analysis, for convex functions, PD-FTGL achieves a regret bound of $\widetilde{O}(n(\rho^{-1/4}+\epsilon^{-1}\rho^{1/4})\sqrt{T})$, and for strongly convex functions, it achieves $\widetilde{O}(n (\rho^{-1/2}+\epsilon^{-1}))$. These bounds represent a significant improvement over the previous state-of-the-art for private decentralized learning.
  • Decoupling is Key: The critical breakthrough is realizing that standard gossip iterations are too "tangled" for standard DP tools. Forcing communication into discrete, decoupled blocks allows the application of tree-based aggregation, keeping the total noise scale logarithmic rather than linear in $T$.
  • Empirical Performance and Efficiency: In experiments on the letter and poker datasets, both PD-FTGL and PD-OCG consistently demonstrated much lower average loss than the existing baseline (PD-OGD). Furthermore, while the projection-free PD-OCG has slightly higher loss than PD-FTGL, it is significantly faster to run, confirming its utility for computationally constrained environments.

Limitations and Future Directions

The authors identify a few areas for further exploration:

  • Lower Bounds: While their results nearly match non-private lower bounds, it remains an open question whether these bounds are truly optimal for any privacy level $\epsilon$. Establishing a general lower bound for D-OCO with DP is a difficult theoretical challenge.
  • Oblivious vs. Adaptive Adversaries: The current work assumes a standard adversary. The authors suggest that "lazy" optimization techniques might further improve regret if the adversary is "oblivious" (i.e., decides all loss functions before the game starts).
  • Network Topology: While the algorithm works on various graphs, performance is still tied to the spectral gap $\rho$. Finding ways to further reduce this dependency would make the algorithms even more robust for poorly connected networks.

Summary updated

Abstract

Although the differential privacy (DP) of decentralized online learning has garnered considerable attention recently, existing algorithms are unsatisfactory due to their inability to achieve $(\epsilon, 0)$-DP over all $T$ rounds, recover the optimal regret in the non-private case, and maintain the lightweight computation under complex constraints. To address these issues, we first propose a new decentralized online learning algorithm satisfying $(\epsilon, 0)$-DP over $T$ rounds, and show that it can achieve $\widetilde{O}(n(\rho^{-1/4}+\epsilon^{-1}\rho^{1/4})\sqrt{T})$ and $\widetilde{O}(n (\rho^{-1/2}+\epsilon^{-1}))$ regret bounds for convex and strongly convex functions respectively, where $n$ is the number of local learners and $\rho$ is the spectral gap of the communication matrix. As long as $\epsilon=\Omega(\sqrt{\rho})$, these bounds nearly match existing lower bounds in the non-private case, which implies that $(\epsilon, 0)$-DP of decentralized online learning may be ensured nearly for free. Our key idea is to design a block-decoupled accelerated gossip strategy that can be incorporated with the classical tree-based private aggregation, and also enjoys a faster average consensus among local learners. Furthermore, we develop a projection-free variant of our algorithm to keep the efficiency under complex constraints. As a trade-off, the above regret bounds degrade to $\widetilde{O}(n(T^{3/4}+\epsilon^{-1}T^{1/4}))$ and $\widetilde{O}(n(T^{2/3}+\epsilon^{-1}))$ respectively, which however are even better than the existing private centralized projection-free online algorithm.
BibTeX
@inproceedings{wang2025revisiting,
  author = {Xiaoyu Wang and Wenhao Yang and Chang Yao and Mingli Song and Yuanyu Wan},
  title = {{Revisiting Differentially Private Algorithms for Decentralized Online Learning}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=12oD7HIckz},
}
Figure