Characterizing the Accuracy-Communication-Privacy Trade-Off in Distributed Stochastic Convex Optimization
Abstract
We consider the problem of differentially private stochastic convex optimization (DP-SCO) in a distributed setting with $M$ clients, where each of them has a local dataset of $N$ i.i.d. data samples from an underlying data distribution. The objective is to design an algorithm to minimize a convex population loss using a collaborative effort across $M$ clients, while ensuring the privacy of the local datasets. In this work, we investigate the accuracy-communication-privacy trade-off for this problem. We establish matching converse and achievability results using a novel lower bound and a new algorithm for distributed DP-SCO based on Vaidya’s plane cutting method. Thus, our results provide a complete characterization of the accuracy-communication-privacy trade-off for DP-SCO in the distributed setting.
Cite
Text
Salgia et al. "Characterizing the Accuracy-Communication-Privacy Trade-Off in Distributed Stochastic Convex Optimization." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.Markdown
[Salgia et al. "Characterizing the Accuracy-Communication-Privacy Trade-Off in Distributed Stochastic Convex Optimization." Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, 2025.](https://mlanthology.org/aistats/2025/salgia2025aistats-characterizing/)BibTeX
@inproceedings{salgia2025aistats-characterizing,
title = {{Characterizing the Accuracy-Communication-Privacy Trade-Off in Distributed Stochastic Convex Optimization}},
author = {Salgia, Sudeep and Pavlovic, Nikola and Chi, Yuejie and Zhao, Qing},
booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics},
year = {2025},
pages = {4285-4293},
volume = {258},
url = {https://mlanthology.org/aistats/2025/salgia2025aistats-characterizing/}
}