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

Sudeep Salgia, Nikola Pavlovic, Yuejie Chi, Qing Zhao · 2025

Read Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization by Sudeep Salgia, Nikola Pavlovic, Yuejie Chi, Qing Zhao (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-03222.txt.

Introduction

Sudeep Salgia, Nikola Pavlovic, Yuejie Chi, and Qing Zhao study a three-way trade-off in shared machine learning in this 2025 paper. Many clients, each holding private data, train one model together. The model should be accurate, cheap to communicate about, and safe for privacy.

The authors pin down exactly how these three goals limit each other. They prove a lower bound that no method can beat, then give a new method that reaches it. The method adapts a classic plane-cutting technique to the private, shared setting. Together, the bound and the method give a complete picture of what is possible for this kind of private joint training.

Catalog record

CREATORSudeep Salgia, Nikola Pavlovic, Yuejie Chi, Qing Zhao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-03222

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Characterizing the Accuracy-Communication-Privacy Trade-off in Distributed Stochastic Convex Optimization Sudeep Salgia, Nikola Pavlovic, Yuejie Chi, Qing Zhao Abstract We consider the problem of differentially private stochastic convex optimization (DP-SCO) in a distributed setting with M M clients, where each of them has a local dataset of N 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 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. Keywords: distributed convex optimization, differential privacy, communication complexity, trade-offs 1 Introduction We consider the problem of distributed stochastic convex optimization where M clients, with the aid of a central server, aim to collaboratively minimize a convex function of the form \displaystyle\mathcal{L}(x)=\mathbb{E}_{z\sim\mathcal{P}}[\ell(x;z)] (1) using their local datasets consisting of N i.i.d. samples from the distribution \mathcal{P} . Here x\in\mathcal{X} denotes the decision variable where \mathcal{X} is a convex, compact set and \ell(x;z) denotes the loss at point x using the datum z . We study this problem under the additional constraint of ensuring differential privacy ( Dwork et al. 2006 ) of the local datasets at each client. This problem arises in numerous settings and represents a typical scenario for Federated Learning (FL) ( McMahan et al. 2017 ) , which has emerged as the de facto approach for collaboratively training machine learning models using a large number of devices coordinated through a central server ( Kairouz et al. 2021 ; Wang et al. 2021 ) . Designing efficient algorithms for differentially private distributed stochastic convex optimization, also referred to as distributed DP-SCO, requires striking a careful balance between the primary objective of minimizing the optimization error and two competing desiderata — communication cost and privacy. Communication cost. There is a natural tension between the accuracy and the communication cost of a distributed learning algorithm, as achieving a lower optimization error entails the clients sharing more information, which results in higher communication costs. Communication between the participating clients and the coordinating server is well-known to be the primary bottleneck in distributed learning, particularly in the scenario where clients have bandwidth constraints ( Tang et al. 2020 ; Zhao et al. 2023 ) . The overall communication cost of a distributed SCO algorithm consists of two parts — the frequency of communication and the size of the message in each communication round. There has been a substantial effort towards designing communication-efficient algorithms in both non-private and private settings, either by reducing the frequency of communication ( McMahan et al. 2017 ; Khaled et al. 2020 ; Karimireddy et al. 2020 ; Gorbunov et al. 2021 ; Li et al. 2020 ; Li et al. 2022a ; Liu et al. 2022 ; Zhao et al. 2021 ) , or by using compression/quantization strategies to minimize the message sizes ( Konečný et al. 2016 ; Suresh et al. 2017 ; Agarwal et al. 2018 ; Hönig et al. 2022 ; Jhunjhunwala et al. 2021 ; Ding et al. 2021 ; Wang et al. 2020b ; Zong et al. 2021 ; Wang et al. 2024 ; Li et al. 2022b ) . Privacy. Often in various applications, the local data at participating agents contains sensitive information that should remain private and not become publicly available during the learning process. It has been shown that preventing the transfer of the actual data during the learning process is not sufficient to guarantee privacy of the local data and can leak private information during the training process ( Zhu et al. 2019 ) . Thus, it is desirable to provide formal guarantees to protect the private data ( Kairouz et al. 2021 ; Wang et al. 2021 ; Geyer et al. 2017 ) .In this work, we consider sophisticated privacy preserving techniques like differential privacy (DP) ( Dwork et al. 2006 ) to ensure the privacy of the local data. In a seminal work, Abadi et al. 2016 proposed the DP-SGD algorithm where they combined SGD with DP techniques to provide formal guarantees on the privacy of the dataset for training deep networks. Since then, numerous optimization algorithms have been proposed that ensure the privacy of the local dataset using DP. At a high level, DP ensures the privacy of the local datasets by introducing uncertainty into the output of the algorithm, which makes it difficult for an adversary to discern private information. This injection of additional uncertainty results in a natural trade-off between privacy and the accuracy of differentially private algorithms. Fundamental accuracy-communication-privacy trade-off. Existing studies largely focus on designing algorithms that aim to balance accuracy with one of the two desiderata which provides only a partial picture of the three-way trade-off among accuracy, communication, and privacy for the problem of distributed DP-SCO. Moreover, there lack studies that characterize the converse region of this three-way trade-off, leaving the question of the optimality of existing results open. In this work, we aim to study and characterize this three-way trade-off from first principles to provide a fresh perspective and new insights into this fundamental problem. 1.1 Main results We consider the problem of distributed stochastic convex optimization with M clients, each with a local dataset of N points, under the constraint of (\varepsilon_{\mathsf{DP}},\delta_{\mathsf{DP}}) differential privacy (See Section 2 for the precise definition). In this work, we provide a complete characterization of the accuracy-communication-privacy trade-off for this problem. The accuracy of an optimization algorithm refers to the sub-optimality gap or the excess risk and is measured as \mathcal{L}(\widehat{x})-\min_{x\in\mathcal{X}}\mathcal{L}(x) , where \widehat{x} denotes the output of the algorithm. We summarize the main results of our work below. • Lower bound on the accuracy-communication-privacy trade-off: We derive a novel lower bound on the accuracy of a distributed SCO algorithm as a function of its communication cost. Specifically, we establish that the error rate of any distributed SCO algorithm is at least \Omega\left(\sqrt{\frac{d^{2}}{MN\cdot\textsf{CC}}}\right) (ignoring other terms), where CC is the communication cost of the algorithm, measured as the total number of bits transmitted by each agent on average (See Section 2 for the precise definition) and d is the dimension of the decision variable. This implies that any algorithm with order-optimal accuracy incurs a communication cost of \Omega(d^{2}) bits. This is the first result that tightly characterizes the lower bound of communication complexity for any distributed optimization algorithm for general convex functions. When combined with existing lower bounds on the accuracy-privacy trade-off, the proposed bound characterizes the converse region of the accuracy-communication-privacy trade-off. In particular, our lower bound implies that the accuracy for any DP-SCO algorithm is at least \Omega\left(\sqrt{\frac{d^{2}}{MN\cdot\min\{\textsf{CC},dN\varepsilon_{\mathsf{DP}}^{2}\}}}\right) , where CC is the communication cost of the algorithm and \varepsilon_{\mathsf{DP}} is the differential privacy parameter. We establish the lower bound by showing that solving a convex optimization problem is at least as hard as solving d mean estimation problems. In contrast, existing lower bounds rely on the straightforward reduction of convex optimization to

Read the complete text