Privately Solving Linear Programs

Abstract

In this paper, we initiate the systematic study of solving linear programs under differential privacy. The first step is simply to define the problem: to this end, we introduce several natural classes of private linear programs that capture different ways sensitive data can be incorporated into a linear program. For each class of linear programs we give an efficient, differentially private solver based on the multiplicative weights framework, or we give an impossibility result.

Cited by in corpus (15)

• Differentially Private Distributed Constrained Optimization
• Jointly Private Convex Programming
• Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism
• Privacy and Truthful Equilibrium Selection for Aggregative Games
• Customized Local Differential Privacy for Multi-Agent Distributed Optimization
• Privacy-preserving Q-Learning with Functional Noise in Continuous State Spaces
• Differential Private Noise Adding Mechanism and Its Application on Consensus
• Differentially Private Convex Optimization with Feasibility Guarantees
• Differential Privacy of Aggregated DC Optimal Power Flow Data
• Efficient, Noise-Tolerant, and Private Learning via Boosting
• Differentially Private Convex Optimization with Piecewise Affine Objectives
• Differentially Private Cloud-Based Multi-Agent Optimization with Constraints
• Private Optimization Without Constraint Violations
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
• Near Optimal Jointly Private Packing Algorithms via Dual Multiplicative Weight Update