Research map / Federated learning and privacy / Differential privacy
Revisiting Differentially Private Algorithms for Decentralized Online Learning
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.
Proposes PD-FTGL, a differentially private decentralized online convex optimization algorithm with (ε,0)-DP over all T rounds via block-decoupled accelerated gossip and tree-based aggregation, plus a projection-free variant PD-OCG.
Problem
Differentially private decentralized online convex optimization (D-OCO): existing private algorithms only give (εT,0)-DP over T rounds, have suboptimal dependence on network size and spectral gap, and require costly projections over complex constraints.
Approach
Combines a blocking update mechanism with accelerated gossip whose communication is block-decoupled, so the decisions are functions of partial sums amenable to tree-based private aggregation; a projection-free variant replaces projections with Frank-Wolfe steps.
Key results
- PD-FTGL achieves (ε,0)-DP over all T rounds with regret Õ(n(ρ^{-1/4}+ε^{-1}ρ^{1/4})√T) for convex and Õ(n(ρ^{-1/2}+ε^{-1})) for strongly convex functions, nearly matching non-private lower bounds when ε=Ω(√ρ).
- The projection-free PD-OCG achieves Õ(n(T^{3/4}+ε^{-1}T^{1/4})) and Õ(n(T^{2/3}+ε^{-1})) regret for convex and strongly convex functions.
- In experiments on letter and poker with n=9 complete graph and ε=10, PD-FTGL and PD-OCG attain much lower average loss than PD-OGD, and PD-FTGL runs faster than PD-OGD.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use tree-based private aggregation and block-decoupled accelerated gossip | PD-FTGL · D-OCO, convex functions | regret bound: O(n5/4ρ−1/2ϵ−1√T) -> eO(n(ρ−1/4 + ϵ−1ρ1/4)√T) | Helped |
| Use tree-based private aggregation and block-decoupled accelerated gossip | PD-FTGL · D-OCO, strongly convex functions | regret bound: eO(n3/2(ρϵ)−1) -> eO(n(ρ−1/2 + ϵ−1)) | Helped |
| Replace projection steps with conditional-gradient linear optimization steps | PD-FTGL, yielding PD-OCG · Projection-free D-OCO, convex functions | regret bound: eO(n(ρ−1/4 + ϵ−1ρ1/4)√T) -> eO(n(T3/4 + ϵ−1T1/4)) | Hurt |
| Replace projection steps with conditional-gradient linear optimization steps | PD-FTGL, yielding PD-OCG · Projection-free D-OCO, strongly convex functions | regret bound: eO(n(ρ−1/2 + ϵ−1)) -> eO(n(T2/3 + ϵ−1)) | Hurt |
| Use PD-FTGL instead of PD-OGD | Decentralized online multiclass classification · letter | average loss | Helped |
| Use PD-OCG instead of PD-OGD | Decentralized online multiclass classification · letter | average loss | Helped |
| Use PD-FTGL instead of PD-OGD | Decentralized online multiclass classification · poker | average loss | Helped |
| Use PD-OCG instead of PD-OGD | Decentralized online multiclass classification · poker | average loss | Helped |
| Use the projection-free variant instead of PD-FTGL | Decentralized online multiclass classification · letter | average loss | Hurt |
| Use the projection-free variant instead of PD-FTGL | Decentralized online multiclass classification · poker | average loss | Hurt |
| Use PD-FTGL instead of PD-OGD | Decentralized online multiclass classification · letter | runtime | Helped |
| Use PD-OCG instead of PD-FTGL | Decentralized online multiclass classification · letter | runtime | Helped |
Surprising findings
- Privacy cost becomes nearly negligible: the ε^{-1} term does not multiply ρ^{-1/4} or ρ^{-1/2}, so (ε,0)-DP is nearly free for ε=Ω(√ρ).
Limitations
- Unknown whether PD-FTGL is nearly optimal for all privacy levels; no general DP lower bounds for D-OCO exist.
- Projection-free variant has worse regret (T^{3/4}, T^{2/3}) than the projection-based algorithm.
- Experiments are limited to simulated multiclass classification on two LIBSVM datasets.
Experimental setup
Datasets: letter (LIBSVM, replicated 10n times, T=150000) poker (LIBSVM, replicated n times, T=1000000)
Benchmarks: letter poker
Metrics: average loss runtime regret bound
Baselines: PD-OGD (Li et al. 2018) Ene et al. 2021 projection-free private OCO
Builds on: FTRL tree-based private aggregation (Smith & Thakurta 2013) accelerated gossip (Liu & Morse 2011) D-FTGL (Wan et al. 2024) blocking update mechanism (Wan et al. 2020) conditional gradient (Frank-Wolfe)
Closest papers by meaning
- The Privacy Power of Correlated Noise in Decentralized Learning (ICML 2024 · similarity 0.90)
- Differentially Private Decentralized Learning with Random Walks (ICML 2024 · similarity 0.89)
- Private Online Learning via Lazy Algorithms (NeurIPS 2024 · similarity 0.88)
- Mitigating the Privacy–Utility Trade-off in Decentralized Federated Learning via f-Differential Privacy (NeurIPS 2025 · similarity 0.88)
- Improved Differentially Private and Lazy Online Convex Optimization: Lower Regret without Smoothness Requirements (ICML 2024 · similarity 0.88)
- Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups (NeurIPS 2024 · similarity 0.88)
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.