Privately Solving Linear Programs
This work addresses the challenge of privacy-preserving optimization for applications involving sensitive data, representing a foundational step in the field.
The paper tackles the problem of solving linear programs under differential privacy by defining several classes of private linear programs and providing efficient solvers based on multiplicative weights or impossibility results for each class.
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.