Differentially Private Distributed Constrained Optimization

By Shuo Han, Ufuk Topcu, George Pappas. 2014

294 citations recorded by the source corpus.

Many resource allocation problems can be formulated as an optimization problem whose constraints contain sensitive information about participating users. This paper concerns a class of resource allocation problems whose objective function depends on the aggregate allocation (i.e., the sum of individual allocations); in particular, we investigate distributed algorithmic solutions that preserve the privacy of participating users. Without privacy considerations, existing distributed algorithms normally consist of a central entity computing and broadcasting certain public coordination signals to participating users. However, the coordination signals often depend on user information, so that an adversary who has access to the coordination signals can potentially decode information on individual users and put user privacy at risk. We present a distributed optimization algorithm that preserves differential privacy, which is a strong notion that guarantees user privacy regardless of any auxiliary information an adversary may have. The algorithm achieves privacy by perturbing the public signals with additive noise, whose magnitude is determined by the sensitivity of the projection operation onto user-specified constraints. By viewing the differentially private algorithm as an implementation of stochastic gradient descent, we are able to derive a bound for the suboptimality of the algorithm. We illustrate the implementation of our algorithm via a case study of electric vehicle charging. Specifically, we derive the sensitivity and present numerical simulations for the algorithm. Through numerical simulations, we are able to investigate various aspects of the algorithm when being used in practice, including the choice of step size, number of iterations, and the trade-off between privacy level and suboptimality.

Subfields: Artificial Intelligence, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

The Value of Collaboration in Convex Machine Learning with Differential Privacy (2019, background): “However, in those studies, if the privacy budget had been scaled inversely proportional to the total number of iterations, privacy guarantees would be maintained over the entire horizon but performance would deteriorate with increasing total number of iterations, as in [29].”
Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms (2018, methodology): “Several differentially private distributed algorithms have been proposed, including (Hale & Egerst-edty, 2015; Huang et al., 2015; Han et al., 2017; Zhang & Zhu, 2017; Bellet et al., 2017).”
Differentially private distributed convex optimization via objective perturbation (2016, methodology): “In [17], on the other hand, a constantvariance noise is used but the algorithm is terminated after a finite number of steps.”
Uplink Communication Efficient Differentially Private Sparse Optimization With Feature-Wise Distributed Data (2018, background): “…2011; Kifer, Smith, and Thakurta 2012; Bassily, Smith, and Thakurta 2014; Talwar, Thakurta, and Zhang 2014; Jain and Thakurta 2013; Kasiviswanathan and Jin 2016) and sample-wise distributed datasets (Huang, Mitra, and Vaidya 2015; Nozari, Tallapragada, and Cortés 2016; Han, Topcu, and Pappas 2017).”
Differentially Private Distributed Convex Optimization via Functional Perturbation (2015, background): “Similar observations can be made in the scenario considered in [18], where the agents’ local constraints are the sensitive information (instead of the objective function).”