Solving Positive Linear Programs with Differential Privacy

Alina Ene, Huy L. Nguyen, Ta Duy Nguyen, Adrian Vladu · 2026

Read Solving Positive Linear Programs with Differential Privacy by Alina Ene, Huy L. Nguyen, Ta Duy Nguyen, Adrian Vladu (2026) 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-2604-26838.txt.

Introduction

Ene and three colleagues build differentially private solvers for positive linear programs, covering packing, covering, and mixed forms. They work in the high-sensitivity constraint-private regime, where near instances differ by one free constraint and no solver can meet each constraint. Their solvers return near solutions while breaking only a set number of constraints, beating past instance-dependent bounds and adding new bounds that hinge only on size. The method builds on dense multiplicative weights from a regularized dual view.

Catalog record

CREATORAlina Ene, Huy L. Nguyen, Ta Duy Nguyen, Adrian Vladu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74358
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.26838

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Solving Positive Linear Programs with Differential Privacy Alina Ene, Huy L. Nguyen, Ta Duy Nguyen, Adrian Vladu Abstract We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs. 1 Introduction Positive linear programs (LPs)—most notably packing, covering and mixed packing-covering LPs—play a central role in machine learning and computer science, where they are used to model optimization problems with all non-negative variables and constraints. Packing LPs which arise in problems such as resource usage maximization subject to capacity constraints, have a wide range of applications including ad allocation, bandwidth allocation and fractional matching, while covering LPs seen in problems such as cost minimization subject to covering requirements naturally model facility location relaxations, set cover, etc. Mixed packing-covering LPs combining both types of constraints appear in network flow control, learning with budget and fair allocation problems. A key reason for the importance of this class of LPs is that they admit fast approximation algorithms, including multiplicative weights update, primal-dual methods, which scale to massive datasets common in modern ML systems. In many scenarios, linear programs directly involve users’ sensitive data such as health or financial information. For example, in a packing LP for bandwidth allocation, each constraint may encode a user’s capacity or usage limit while in a covering LP modeling minimum-cost provisioning of services, each user’s constraint may represent a personal service requirement. In such cases, solving the LP requires the algorithm designer to pay particular attention to protecting the users’ private information. This is where differential privacy proves its usefulness. Differential privacy provides a principled framework for protecting users in this context by ensuring that the output of an LP-solving algorithm does not change significantly when the input LP differs by one constraint. Research on solving linear programs under differential privacy dates back to Hsu et al. 2014 and has since been extended to broader settings and related problems, including private learning of subspaces and halfspaces Bun et al. 2015 ; Beimel et al. 2019 ; Kaplan et al. 2020 ; Gao and Sheffet 2021 ; Ben-Eliezer et al. 2022 , which are fundamental learning theory problems. A key challenge in privately solving linear programs is an inherent impossibility result: it is not possible to simultaneously guarantee differential privacy and satisfy all constraints. Indeed, the addition or removal of a single constraint can change an LP from feasible to infeasible or vice versa, revealing sensitive information. Consequently, any differentially private algorithm must allow for the violation or removal of some constraints. Characterizing upper bounds on the number of constraints that must be dropped to preserve privacy has therefore become a central question in this line of work, including this paper. To address this challenge, Hsu et al. 2014 introduces a general framework for approximately solving linear programs under differential privacy. However, in this work, explicit constraint-private algorithms and performance guarantees are provided only for the fractional set cover problem. Moreover, the resulting bounds are instance-dependent: the number of constraints that must be dropped depends on properties of the problem such as the optimal objective value. More recent works by Kaplan et al. 2024 ; Ene et al. 2025 develop algorithmic approaches for solving general LPs exactly. These methods achieve data-independent guarantees, but incur high-degree polynomial dependence on the problem dimension, which can be overly pessimistic for structured instances such as positive LPs. In this work, we revisit the problem of solving linear programs with differential privacy, focusing on the class of positive LPs, including packing, covering and mixed packing-covering LPs. We propose new approximation algorithms for solving these problems as well as new analysis that can exploit their structure to improve the number of constraints that are violated due to privacy. 1.1 Our contribution We focus on constraint-private LPs where neighboring inputs can differ by a single constraint. This is the most challenging setting among the various scenarios introduced by Hsu et al. 2014 , for which guarantees for private approximation algorithms are not well understood. We give constraint-private algorithms that output solutions satisfying all constraints of the LP approximately, except for a bounded number of constraints. We provide upper bounds on the number of constraints that might be violated, distinguishing between two types of guarantee: one that only depends on the problem dimension and one that involves data-dependent properties, specific to the LP given as input. Our results are stated in the following theorem (precise statements are given in subsequent sections). Theorem 1 . (cf. Theorems 5 and 9 ) Given the approximation factor \alpha\in(0,1) , there exist (\varepsilon,\delta) -differentially private algorithms that output a solution to a packing (covering) LP given by constraints Ax\leq 1 (respectively, Ax\geq 1 ) for A\in\mathbb{R}_{\geq 0}^{n\times d} . With high probability, the output solution satisfies Ax\leq 1+\alpha (respectively, Ax\geq 1-\alpha ), except for at most s constraints where, s=\widetilde{O}\left(\frac{\left(A_{\max}\mathsf{OPT}\right)^{1.5}}{\alpha^{2}\varepsilon}\right),\text{ or }s=\widetilde{O}\left(\frac{d^{1.5}}{\alpha^{3.5}\varepsilon}\right), where \mathsf{OPT} is the optimal objective of the LP and A_{\max} denotes the maximum entry of A . Theorem 2 . (cf. Theorem 10 ) Given the approximation factor \alpha\in(0,1) , there exist (\varepsilon,\delta) -differentially private algorithms that output a solution to a mixed packing-covering LP given by constraints Px\leq 1,Cx\geq 1 where P\in\mathbb{R}_{\geq 0}^{p\times d},C\in\mathbb{R}_{\geq 0}^{c\times d} . With high probability, the output solution satisfies Px\leq 1+\alpha,Cx\geq 1-\alpha , except for at most s constraints where, \displaystyle s \displaystyle=\widetilde{O}\left(\frac{P_{\max}C_{\max}\sqrt{P_{\max}+C_{\max}}V^{2.5}}{\alpha^{4.5}\varepsilon}\right),\text{ or }s=\widetilde{O}\left(\frac{d^{3}}{\alpha^{6}\varepsilon}\right), and V=1^{\top}x for some feasible solution x , P_{\max},C_{\max} denote the maximum entries of P and C , respectively. In these theorems statements, the \widetilde{O} -notation hides logarithmic factors that depend on n,d,\delta , the success probability and the range of the input. Comparison with Hsu et al. 2014 . While Hsu et al. 2014 provide a general framework to solve constraint-private LPs, explicit bounds are only provided for fractional set cover problem for which an explicit private oracle can be constructed. For this problem where A_{\max}=1 , the number of violated constraints given by Hsu et al. 2014 ’s algorithm is \widetilde{O}\left(\frac{\mathsf{OPT}^{2}}{\alpha^{2}\varepsilon}\right) . By comparison, for this problem, our algorithm gives a bound of \widetilde{O}\left(\frac{\mathsf{OPT}^{1.5}}{\alpha^{2}\varepsilon}\right) . This is an improvement by a factor \mathsf{OPT}^{0.5} . At the same time, our work goes beyond this instance-specific bound and provides an upper bound of \widetilde{O}\left(\frac{d^{1.5}}{\alpha^{3.5}\varepsilon}\right) . This bound improves the former when \mathsf{OPT}\gg\frac{d}{\alpha} . Comparison with Kaplan et al. 2024 ; Ene et al. 2025 . These works focus on solving general LPs with high precision with differential privacy, i.e, achieving \log -dependence instead of polynomial dependence on \frac{1}{\alpha} . At the same time, their solvers incur high degree polynomial dependence on the dimension. Specifically, Kaplan

Read the complete text