# Distributed Online Private Learning of Convex Nondecomposable Objectives

arXiv: https://arxiv.org/abs/2206.07944 · HTML: https://mlsanity.com/paper/2206.07944/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 58 references that are in the map.
- First posted on arXiv 16 Jun 2022.

## Builds on (most cited first, 14 of 14)

- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization](https://mlsanity.com/paper/1404.6264/) (2014)
- [Achieving Geometric Convergence for Distributed Optimization over Time-Varying Graphs](https://mlsanity.com/paper/1607.03218/) (2016)
- [Push-Pull Gradient Methods for Distributed Optimization in Networks](https://mlsanity.com/paper/1810.06653/) (2018)
- [Distributed Online Optimization in Dynamic Environments Using Mirror Descent](https://mlsanity.com/paper/1609.02845/) (2016)
- [Distributed Online Convex Optimization with Time-Varying Coupled Inequality Constraints](https://mlsanity.com/paper/1903.04277/) (2019)
- [Differentially Private Distributed Optimization](https://mlsanity.com/paper/1401.2596/) (2014)
- [Differentially Private Distributed Online Learning](https://mlsanity.com/paper/1505.06556/) (2015)
- [Differentially Private Distributed Convex Optimization via Functional Perturbation](https://mlsanity.com/paper/1512.00369/) (2015)
- [Achieving Linear Convergence in Distributed Asynchronous Multi-agent Optimization](https://mlsanity.com/paper/1803.10359/) (2018)
- [Decentralized Online Learning with Kernels](https://mlsanity.com/paper/1710.04062/) (2017)
- [AsySPA: An Exact Asynchronous Algorithm for Convex Optimization Over Digraphs](https://mlsanity.com/paper/1808.04118/) (2018)
- [Distributed Optimization over Directed Graphs with Row Stochasticity and Constraint Regularity](https://mlsanity.com/paper/1806.07081/) (2018)
- [Bolt-on Differential Privacy for Scalable Stochastic Gradient Descent-based Analytics](https://mlsanity.com/paper/1606.04722/) (2016)

## Built on by (most cited first, 4 of 4)

- [Locally Differentially Private Online Federated Learning With Correlated Noise](https://mlsanity.com/paper/2411.18752/) (2024)
- [Privacy-Preserving Distributed Optimization and Learning](https://mlsanity.com/paper/2403.00157/) (2024)
- [Locally Differentially Private Distributed Online Learning with Guaranteed Optimality](https://mlsanity.com/paper/2306.14094/) (2023)
- [Near-Optimal Reinforcement Learning with Shuffle Differential Privacy](https://mlsanity.com/paper/2411.11647/) (2024)

## Abstract (arXiv)

We deal with a general distributed constrained online learning problem with privacy over time-varying networks, where a class of nondecomposable objectives are considered. Under this setting, each node only controls a part of the global decision, and the goal of all nodes is to collaboratively minimize the global cost over a time horizon T while guarantees the security of the transmitted information. For such problems, we first design a novel generic algorithm framework, named as DPSDA, of differentially private distributed online learning using the Laplace mechanism and the stochastic variants of dual averaging method. Note that in the dual updates, all nodes of DPSDA employ the noise-corrupted gradients for more generality. Then, we propose two algorithms, named as DPSDA-C and DPSDA-PS, under this framework. In DPSDA-C, the nodes implement a circulation-based communication in the primal updates so as to alleviate the disagreements over time-varying undirected networks. In addition, for the extension to time-varying directed ones, the nodes implement the broadcast-based push-sum dynamics in DPSDA-PS, which can achieve average consensus over arbitrary directed networks. Theoretical results show that both algorithms attain an expected regret upper bound in O( √T ) when the objective function is convex, which matches the best utility achievable by cutting-edge algorithms. Finally, numerical experiment results on both synthetic and real-world datasets verify the effectiveness of our algorithms.