# Locally Differentially Private Gradient Tracking for Distributed Online Learning over Directed Graphs arXiv: https://arxiv.org/abs/2310.16105 ยท HTML: https://mlsanity.com/paper/2310.16105/ ## Key facts - Cited by 2 papers in the map (data through 14 Oct 2026). - Builds on 36 of its 73 references that are in the map. - First posted on arXiv 24 Oct 2023. ## Builds on (most cited first, 30 of 36) - [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019) - [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017) - [Differentially Private Federated Learning: A Client Level Perspective](https://mlsanity.com/paper/1712.07557/) (2017) - [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016) - [Distributed Stochastic Gradient Tracking Methods](https://mlsanity.com/paper/1805.11454/) (2018) - [Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent](https://mlsanity.com/paper/2102.05855/) (2021) - [An Improved Analysis of Gradient Tracking for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03836/) (2022) - [Collaborative Deep Learning in Fixed Topology Networks](https://mlsanity.com/paper/1706.07880/) (2017) - [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020) - [Smooth Loss Functions for Deep Top-k Classification](https://mlsanity.com/paper/1802.07595/) (2018) - [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018) - [A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning](https://mlsanity.com/paper/2110.09993/) (2021) - [Fast Convergence Rates for Distributed Non-Bayesian Learning](https://mlsanity.com/paper/1508.05161/) (2015) - [Differentially Private Distributed Optimization](https://mlsanity.com/paper/1401.2596/) (2014) - [Distributed Nonconvex Constrained Optimization over Time-Varying Digraphs](https://mlsanity.com/paper/1809.01106/) (2018) - [Tailoring Gradient Methods for Differentially-Private Distributed Optimization](https://mlsanity.com/paper/2202.01113/) (2022) - [A Survey on Semi-Supervised Learning for Delayed Partially Labelled Data Streams](https://mlsanity.com/paper/2106.09170/) (2021) - [Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking](https://mlsanity.com/paper/1808.02942/) (2018) - [A fast randomized incremental gradient method for decentralized non-convex optimization](https://mlsanity.com/paper/2011.03853/) (2020) - [Differentially Private Distributed Online Learning](https://mlsanity.com/paper/1505.06556/) (2015) - [Improving the Transient Times for Distributed Stochastic Gradient Methods](https://mlsanity.com/paper/2105.04851/) (2021) - [Linear convergence in optimization over directed graphs with row-stochastic matrices](https://mlsanity.com/paper/1611.06160/) (2016) - [Differentially Private Distributed Convex Optimization via Functional Perturbation](https://mlsanity.com/paper/1512.00369/) (2015) - [Distributed stochastic optimization with gradient tracking over strongly-connected networks](https://mlsanity.com/paper/1903.07266/) (2019) - [A Distributed Online Convex Optimization Algorithm with Improved Dynamic Regret](https://mlsanity.com/paper/1911.05050/) (2019) - [GTAdam: Gradient Tracking with Adaptive Momentum for Distributed Online Optimization](https://mlsanity.com/paper/2009.01745/) (2020) - [Quantized Distributed Gradient Tracking Algorithm with Linear Convergence in Directed Networks](https://mlsanity.com/paper/2104.03649/) (2021) - [Privacy Preservation in Distributed Subgradient Optimization Algorithms](https://mlsanity.com/paper/1512.08822/) (2015) - [A Robust Gradient Tracking Method for Distributed Optimization over Directed Networks](https://mlsanity.com/paper/2003.13980/) (2020) - [Quantization enabled Privacy Protection in Decentralized Stochastic Optimization](https://mlsanity.com/paper/2208.04845/) (2022) ## Built on by (most cited first, 2 of 2) - [Privacy-Preserving Distributed Optimization and Learning](https://mlsanity.com/paper/2403.00157/) (2024) - [Gradient Manipulation in Distributed Stochastic Gradient Descent with Strategic Agents: Truthful Incentives with Convergence Guarantees](https://mlsanity.com/paper/2603.27962/) (2026) ## Abstract (arXiv) Distributed online learning has been proven extremely effective in solving large-scale machine learning problems over streaming data. However, information sharing between learners in distributed learning also raises concerns about the potential leakage of individual learners' sensitive data. To mitigate this risk, differential privacy, which is widely regarded as the "gold standard" for privacy protection, has been widely employed in many existing results on distributed online learning. However, these results often face a fundamental tradeoff between learning accuracy and privacy. In this paper, we propose a locally differentially private gradient tracking based distributed online learning algorithm that successfully circumvents this tradeoff. We prove that the proposed algorithm converges in mean square to the exact optimal solution while ensuring rigorous local differential privacy, with the cumulative privacy budget guaranteed to be finite even when the number of iterations tends to infinity. The algorithm is applicable even when the communication graph among learners is directed. To the best of our knowledge, this is the first result that simultaneously ensures learning accuracy and rigorous local differential privacy in distributed online learning over directed graphs. We evaluate our algorithm's performance by using multiple benchmark machine-learning applications, including logistic regression of the "Mushrooms" dataset and CNN-based image classification of the "MNIST" and "CIFAR-10" datasets, respectively. The experimental results confirm that the proposed algorithm outperforms existing counterparts in both training and testing accuracies.