Differentially Private Distributed Constrained Optimization

Abstract

Many resource allocation problems can be formulated as an optimization problem whose constraints contain sensitive information about participating users. This paper concerns solving this kind of optimization problem in a distributed manner while protecting the privacy of user information. Without privacy considerations, existing distributed algorithms normally consist in 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.

Submitted to the IEEE Transactions on Automatic Control

References in corpus (3)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• How To Break Anonymity of the Netflix Prize Dataset
• Privately Solving Linear Programs

Cited by in corpus (44)

• DP-ADMM: ADMM-based Distributed Learning with Differential Privacy
• Privacy-Preserving Distributed Optimization via Subspace Perturbation: A General Framework
• Privacy-preserving Distributed Machine Learning via Local Randomization and ADMM Perturbation
• Improving the Privacy and Accuracy of ADMM-Based Distributed Algorithms
• Privacy-preserving Incremental ADMM for Decentralized Consensus Optimization
• Differential Privacy of Populations in Routing Games
• Optimality of the Laplace Mechanism in Differential Privacy
• Private Learning on Networks: Part II
• Customized Local Differential Privacy for Multi-Agent Distributed Optimization
• Communication-efficient Distributed Multi-resource Allocation
• Distributed Differentially Private Computation of Functions with Correlated Noise
• Differentially Private ADMM for Convex Distributed Learning: Improved Accuracy via Multi-Step Approximation
• Differentially Private Collaborative Intrusion Detection Systems For VANETs
• Privacy-preserving Decentralized Optimization via Decomposition
• The Value of Collaboration in Convex Machine Learning with Differential Privacy
• Improved Differentially Private Decentralized Source Separation for fMRI Data
• A Privacy-Preserving Distributed Control of Optimal Power Flow
• Differentially Private Convex Optimization with Feasibility Guarantees
• Differentially Private Distributed Computation via Public-Private Communication Networks
• Private and Robust Distributed Nonconvex Optimization via Polynomial Approximation
• ADMM Based Privacy-preserving Decentralized Optimization
• Local Differential Privacy in Decentralized Optimization
• Composition Properties of Bayesian Differential Privacy
• Privacy-Preserving Distributed Zeroth-Order Optimization
• Mechanism Design for Demand Management in Energy Communities
• Design of Privacy-Preserving Dynamic Controllers
• Recycled ADMM: Improve Privacy and Accuracy with Less Computation in Distributed Algorithms
• A Novel Cryptography-Based Privacy-Preserving Decentralized Optimization Paradigm
• A Communication-efficient Local Differentially Private Algorithm in Federated Optimization
• Realistic Differentially-Private Transmission Power Flow Data Release
• Privacy-Preserving Distributed Optimal Power Flow with Partially Homomorphic Encryption
• System Design Approach for Control of Differentially Private Dynamical Systems
• Distributed Algorithms that Solve Boolean Equations with Local and Differential Privacies
• Privacy-Preserving Distributed Processing: Metrics, Bounds, and Algorithms
• A Private and Finite-Time Algorithm for Solving a Distributed System of Linear Equations
• Initial-Value Privacy of Linear Dynamical Systems
• Bounding the l_2 sensitivity for positive linear observers
• Distributed Mechanism Design for Network Resource Allocation Problems
• Privacy-Utility Trade-Offs Against Limited Adversaries
• Asymptotic Properties of Primal-Dual Algorithm for Distributed Stochastic Optimization Over Random Networks
• Privacy-Preserving Decentralized Multi-Agent Cooperative Optimization -- Paradigm Design and Privacy Analysis
• Nash equilibrium of multi-agent graphical game with a privacy information encrypted learning algorithm
• Differentially private Nash equilibrium seeking for networked aggregative games
• Approximately Truthful Multi-Agent Optimization Using Cloud-Enforced Joint Differential Privacy