Differentially Private Linear Programming: Reduced Sub-Optimality and Guaranteed Constraint Satisfaction
Alexander Benvenuti, Brendan Bialy, Miriam Dennis, Matthew Hale · 2025
Read Differentially Private Linear Programming: Reduced Sub-Optimality and Guaranteed Constraint Satisfaction by Alexander Benvenuti, Brendan Bialy, Miriam Dennis, Matthew Hale (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-19315.txt.
Introduction
Alexander Benvenuti, Brendan Bialy, Miriam Dennis, and Matthew Hale add privacy to a workhorse math tool in 2025. Linear programming picks the best plan under a set of limits, and it runs many real decision systems. Yet sharing its answer can leak the private data that built it.
Their method scrambles the goals and limits in a way that carries a formal privacy proof. The scrambled problems always have answers, they show, and those answers still obey the true, private limits. That second point settles an open problem in the field. The cost of privacy, in lost quality, is bounded on paper. In tests, their method cut that loss by sixty-five percent against the best past method.
Catalog record
| CREATOR | Alexander Benvenuti, Brendan Bialy, Miriam Dennis, Matthew Hale |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-19315
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Differentially Private Linear Programming: Reduced Sub-Optimality and Guaranteed Constraint Satisfaction Alexander Benvenuti, Brendan Bialy, Miriam Dennis, Matthew Hale Abstract Linear programming is a fundamental tool in a wide range of decision systems. However, without privacy protections, sharing the solution to a linear program may reveal information about the underlying data used to formulate it, which may be sensitive. Therefore, in this paper we introduce an approach for protecting sensitive data while formulating and solving a linear program. First, we prove that this method perturbs objectives and constraints in a way that makes them differentially private. Then, we show that (i) privatized problems always have solutions, and (ii) their solutions satisfy the constraints in their corresponding original, non-private problems. The latter result solves an open problem in the literature. Next, we analytically bound the expected sub-optimality of solutions that is induced by privacy. Numerical simulations show that, under a typical privacy setup, the solution produced by our method yields a 65 % 65\% reduction in sub-optimality compared to the state of the art. 1 School of Electrical and Computer Engineering, Georgia Institute of Technology, Atlanta, GA, USA 2 Munitions Directorate, Air Force Research Laboratory, Eglin Air Force Base, FL, USA [email protected], [email protected], [email protected], [email protected] 1 Introduction Linear programming is used in a wide range of settings, including resource allocation, power systems, and transportation systems. In many modern systems, user data plays an increasing role in formulating such optimization problems. Sensitive information such as investor data, home power consumption, and travel routes may be use used to formulate these problems ( Markowitz 1952 ; Stott et al. 1979 ) , though sharing the solution to an optimization problem may leak this sensitive data ( Hsu et al. 2014b ) . As a result, interest has arisen in solving linear programs while both (i) preserving the privacy of the data used in the problem formulation and (ii) ensuring constraint satisfaction. In this paper we solve the open problem posed in ( Munoz et al. 2021 ) , namely, the privatization of data that is used to generate constraints when solving linear programs, while also maintaining feasibility of solutions with respect to the original, non-private constraints. For a problem with linear constraints Ax\leq b and cost c^{T}x , the work in ( Munoz et al. 2021 ) privatized the data that is used to generate b while also ensuring feasibility with respect to the original constraints. Then ( Munoz et al. 2021 ) named it as an open problem to simultaneously privatize the data that produces A and ensure satisfaction of the original, non-private constraints. We not only solve this open problem, but in fact go one step further by simultaneously privatizing the data that produces all three — A , b , and c — with guaranteed satisfaction of the original constraints. To produce a private linear program, we use differential privacy. Differential privacy is a statistical notion of privacy originally developed to protect entries in databases ( Dwork et al. 2006 ) , and it has seen wide use in the controls ( Le Ny and Pappas 2013 ; Cortés et al. 2016 ; Hawkins and Hale 2020 ; Yazdani et al. 2022 ) , planning ( Chen et al. 2023 ; Benvenuti et al. 2024b ) , and federated learning ( Geyer et al. 2017 ; Agarwal et al. 2021 ; Chen et al. 2022 ; Noble et al. 2022 ) communities for the strong guarantees that it provides. We use differential privacy in this work partly because of its immunity to post-processing ( Dwork and Roth 2014 ) , namely that arbitrary computations on private data do not weaken differential privacy. We consider linear programs in which the cost c^{T}x and constraint terms A and b can all depend on user data, and we use differential privacy to perturb each of these terms in order to protect the data that is used to generate them. The result is a privacy-preserving linear program. We then solve this optimization problem, which is simply a way of post-processing the privacy-preserving problem. Thus, the solution to the private problem preserves the privacy of the data used to formulate the problem, as do any downstream computations that use that solution. ( Hsu et al. 2014b ) ( Cummings et al. 2015 ) ( Dvorkin et al. 2020 ) ( Munoz et al. 2021 ) ( Benvenuti et al. 2024a ) This work Privatize A ✓ ✓ ✓ ✓ Privatize b ✓ ✓ ✓ ✓ ✓ Privatize c ✓ ✓ ✓ Satisfy Constraints ✓ ✓ ✓ Table 1: Comparison of differentially private linear programming approaches in the literature. As noted in ( Benvenuti et al. 2024a ) and ( Munoz et al. 2021 ) , common privacy mechanisms such as the Gaussian and Laplace mechanisms ( Dwork and Roth 2014 ) add noise with unbounded support. Such mechanisms can perturb constraints by arbitrarily large amounts, which can therefore cause the solution to a privatized problem to be infeasible with respect to the original constraints. Motivated by this challenge, we develop a new matrix truncated Laplace mechanism to privatize the data that produces A , and we use the truncated Laplace mechanism developed in ( Munoz et al. 2021 ; Geng et al. 2020 ) to privatize the data that produces b . This approach allows us to privatize the constraints such that they only become tighter, thereby ensuring that the solution to the private problem always satisfies the original, non-private constraints. Since the cost does not affect feasibility, we use the unbounded Laplace mechanism in ( Dwork and Roth 2014 ) to provide privacy for the cost. We then bound the accuracy of our method, which provides users with a tool to calibrate privacy based on its tradeoff with performance. To summarize, our contributions are: • We develop a differential privacy mechanism that simultaneously privatizes all terms in a linear program (Theorem 3.9 ). • We prove that a privatized problem produces a solution that is feasible with respect the constraints in the original, non-private problem (Theorem 3.10 ), which solves an open problem in the literature. • We bound the accuracy of our method, namely the increase/decrease in optimal cost, in terms of privacy parameters (Theorem 4.1 ). • We empirically compare the performance of our method to the state of the art and show that the solution produced by our method yields a 65\% reduction in sub-optimality relative to existing work (Section 5 ). 1.1 Related Work There exists substantial previous work on differential privacy in optimization, specifically looking at privacy for objective functions in distributed optimization ( Huang et al. 2015 ; Wang et al. 2016 ; Han et al. 2016 ; Nozari et al. 2016 ; Dobbe et al. 2018 ; Lv et al. 2020 ) . We differ from these works because we consider the constraints to also be sensitive, not just objectives. Privacy for optimization with linear constraints has been previously investigated in ( Hsu et al. 2014b ; Cummings et al. 2015 ; Dvorkin et al. 2020 ; Munoz et al. 2021 ; Benvenuti et al. 2024a ; Kaplan et al. 2024 ) . Both ( Hsu et al.