Differentially Private Distributed Convex Optimization via Functional Perturbation

By Erfan Nozari, Pavankumar Tallapragada, Jorge Cortés. 2015

173 citations recorded by the source corpus.

We study a class of distributed convex constrained optimization problems where a group of agents aim to minimize the sum of individual objective functions while each desires that any information about its objective function is kept private. We prove the impossibility of achieving differential privacy using strategies based on perturbing the inter-agent messages with noise when the underlying noise-free dynamics are asymptotically stable. This justifies our algorithmic solution based on the perturbation of individual functions with Laplace noise. To this end, we establish a general framework for differentially private handling of functional data. We further design post-processing steps that ensure the perturbed functions regain the smoothness and convexity properties of the original functions while preserving the differentially private guarantees of the functional perturbation step. This methodology allows us to use any distributed coordination algorithm to solve the optimization problem on the noisy functions. Finally, we explicitly bound the magnitude of the expected distance between the perturbed and true optimizers which leads to an upper bound on the privacy-accuracy tradeoff curve. Simulations illustrate our results.

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

Federated learning of predictive models from federated Electronic Health Records (2018, background): “[ 9–11] Two well-known examples of privacy breaches are the Netflix Prize and the Massachusetts Group Insurance Commission (GIC) medical records database.”
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].”
ADMM Based Privacy-Preserving Decentralized Optimization (2017, background): “To enable privacy preservation in decentralized optimization, one commonly used approach is differential privacy [19]– [21], which adds carefully-designed noise to exchanged states or objective functions to cover sensitive information.”