Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization

Sudeep Salgia, Nikola Pavlovic, Yuejie Chi, Qing Zhao
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:4285-4293, 2025.

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 this Paper

BibTeX
@InProceedings{pmlr-v258-salgia25a, 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}, pages = {4285--4293}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/salgia25a/salgia25a.pdf}, url = {https://proceedings.mlr.press/v258/salgia25a.html}, 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.} }
Endnote
%0 Conference Paper %T Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization %A Sudeep Salgia %A Nikola Pavlovic %A Yuejie Chi %A Qing Zhao %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-salgia25a %I PMLR %P 4285--4293 %U https://proceedings.mlr.press/v258/salgia25a.html %V 258 %X 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.
APA
Salgia, S., Pavlovic, N., Chi, Y. & Zhao, Q.. (2025). Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:4285-4293 Available from https://proceedings.mlr.press/v258/salgia25a.html.

Related Material