Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 57 of its 89 references that are in the map. First posted on arXiv 6 Jan 2025.
Builds on
57 of 89 references.
References · 57
- 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
- 2019Advances and Open Problems in Federated Learningcited by 3,021
- 2016Federated Learning: Strategies for Improving Communication Efficiencycited by 1,461
- 2019Deep Leakage from Gradientscited by 1,004
- 2017Differentially Private Federated Learning: A Client Level Perspectivecited by 451
- 2019FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantizationcited by 349
- 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
- 2018Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergencescited by 237
- 2019Private Stochastic Convex Optimization with Optimal Ratescited by 183
- 2020Federated Learning with Compression: Unified Analysis and Sharp Guaranteescited by 159
- 2018cpSGD: Communication-efficient and differentially-private distributed SGDcited by 157
- 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 152
38 more
- 2020Is Local SGD Better than Minibatch SGD?cited by 151
- 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
- 2016Distributed Mean Estimation with Limited Communicationcited by 134
- 2018Differentially Private Empirical Risk Minimization Revisited: Faster and More Generalcited by 127
- 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 106
- 2014Preserving Statistical Validity in Adaptive Data Analysiscited by 102
- 2021Private Stochastic Convex Optimization: Optimal Rates in ℓ1 Geometrycited by 83
- 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
- 2021Learning with User-Level Privacycited by 72
- 2020Breaking the Communication-Privacy-Accuracy Trilemmacited by 68
- 2021Adaptive Quantization of Model Updates for Communication-Efficient Federated Learningcited by 60
- 2015Communication Complexity of Distributed Convex Learning and Optimizationcited by 59
- 2020An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applicationscited by 57
- 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
- 2015Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequalitycited by 50
- 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
- 2021Differentially Private Stochastic Optimization: New Results in Convex and Non-Convex Settingscited by 45
- 2015Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimizationcited by 41
- 2021DAdaQuant: Doubly-adaptive quantization for communication-efficient Federated Learningcited by 40
- 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
- 2018Graph Oracle Models, Lower Bounds, and Gaps for Parallel Stochastic Optimizationcited by 34
- 2022SoteriaFL: A Unified Framework for Private Federated Learning with Communication Compressioncited by 34
- 2022Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compressioncited by 33
- 2021The Min-Max Complexity of Distributed Stochastic Convex Optimization with Intermittent Communicationcited by 30
- 2020Communication-Efficient Distributed Deep Learning: A Comprehensive Surveycited by 25
- 2022Towards Efficient Communications in Federated Learning: A Contemporary Surveycited by 24
- 2014Differentially Private Distributed Optimizationcited by 23
- 2020Fisher information under local differential privacycited by 22
- 2023Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimationcited by 22
- 2021FedPAGE: A Fast Local Stochastic Gradient Method for Communication-Efficient Federated Learningcited by 19
- 2020Private and Communication-Efficient Edge Learning: A Sparse Differential Gaussian-Masking Distributed SGD Approachcited by 18
- 2014Private Multiplicative Weights Beyond Linear Queriescited by 17
- 2022Differentially Private Generalized Linear Models Revisitedcited by 17
- 2021DESTRESS: Computation-Optimal and Communication-Efficient Decentralized Nonconvex Finite-Sum Optimizationcited by 16
- 2020Local SGD With a Communication Overhead Depending Only on the Number of Workerscited by 13
- 2023User-level Differentially Private Stochastic Convex Optimization: Efficient Algorithms with Optimal Ratescited by 12
- 2014Optimality guarantees for distributed statistical estimationcited by 9
- 2019The Communication Complexity of Optimizationcited by 9
50 most cited of 57 All 57 (JSON)
Built on by
Citing papers per year: 2025: 1.
1 paper.