Differentially Private Distributed Optimization

By Zhenqi Huang, Sayan Mitra, Nitin H. Vaidya. 2014

307 citations recorded by the source corpus.

In distributed optimization and iterative consensus literature, a standard problem is for N agents to minimize a function f over a subset of Euclidean space, where the cost function is expressed as a sum Σ fi. In this paper, we study the private distributed optimization problem (PDOP) with the additional requirement that the cost function of the individual agents should remain differentially private. The adversary attempts to infer information about the private cost functions from the messages that the agents exchange. Achieving differential privacy requires that any change of an individual's cost function only results in unsubstantial changes in the statistics of the messages. We propose a class of iterative algorithms for solving PDOP, which achieves differential privacy and convergence to a common value. Our analysis reveals the dependence of the achieved accuracy and the privacy levels on the the parameters of the algorithm. We observe that to achieve ε-differential privacy the accuracy of the algorithm has the order of O(1/ε2).

Subfields: Artificial Intelligence, Computer Networks and Communications, Privacy & Security, Mathematical Optimization

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

In Privacy & Security

In Mathematical Optimization

Citations in the corpus

Privacy Amplification by Decentralization (2020, methodology): “In LDP, random perturbations are performed locally by each user, making it convenient to design private versions of fully de-centralized algorithms in this model (see e.g., Huang et al., 2015; Bellet et al., 2018; Li et al., 2018; Cheng et al., 2019; Zhang et al., 2018; Xu et al., 2020).”
Personalized and Private Peer-to-Peer Machine Learning (2017, methodology): “Existing approaches for privacy-preserving distributed learning (see e.g., Pathak et al., 2010; Rajkumar and Agarwal, 2012; Shokri and Shmatikov, 2015; Huang et al., 2015) rely on a central (sometimes trusted) server, assume the local data distribution is the same for all users and/or are designed t”
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).”
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 Online Learning (2018, unknown): “, [7], [8], [9]).”
Differentially Private Distributed Convex Optimization via Functional Perturbation (2015, methodology): “Of more relevance to our paper are recent works [17]–[19] that are focused on differentially private distributed optimization problems for multi-agent systems.”
Secure and Privacy-Preserving Consensus (2017, methodology): “ng and control systems such as power systems and wireless sensor networks. To address the pressing need for privacy and security in consensus, recently, several solutions have been proposed [6], [7], [8], [9], [10], [11], [12], [13]. Most of these approaches use the idea of obfuscation to mask the t”
Differentially private distributed convex optimization via objective perturbation (2016, background): “More closely related to our present work are efforts [16]–[18] on differentially private distributed optimization for networked systems, where the sensitive information are the objective functions in [16], the optimization constraints in [17], and the agents’ states in [18].”
Differentially private average consensus: Obstructions, trade-offs, and optimal algorithm design (2015, unknown): “O C ] 2 8 Fe b 20 17 et al., 2012, 2014, Wang et al., 2014], estimation [Ny and Pappas, 2014], and optimization [Han et al., 2014, Huang et al., 2015, Nozari et al., 2017].”
Preserving privacy between features in distributed estimation (2017, background): “In distributed supervised learning, private approaches have been much less studied and focus mainly on the setting where data are horizontally partitioned (Huang et al., 2015; Zhang & Zhu, 2016).”
Differentially Private Distributed Constrained Optimization (2014, background): “In their formulation, the private user information is encodedin the individual cost functions and can be interpreted as user preferences.”
Differentially Private Distributed Online Learning (2015, background): “Besides, Huang et al. [14] is closely related to our work.”
DP-ADMM: ADMM-Based Distributed Learning With Differential Privacy (2018, background): “Among the works on distributed learning with differential privacy, most of them focus on subgradient-based algorithms [35]–[38] and only a few works consider ADMMbased methods [1], [2], [17]–[19].”
Differentially private cloud-based multi-agent optimization with constraints (2015, background): “In [11], the authors solve a distributed optimization problem in which the agents’ objective functions must be kept private.”
ADMM Based Privacy-Preserving Decentralized Optimization (2017, methodology): “Comparison with the algorithm in [19] We then compared our approach with the differentialprivacy based privacy-preserving optimization algorithm in [19].”