# Solving Linear Programs with Differential Privacy

arXiv: https://arxiv.org/abs/2507.10946 · HTML: https://mlsanity.com/paper/2507.10946/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Fast-MWEM: Private Data Release in Sublinear Time](https://mlsanity.com/paper/2602.03732/) (2026)

## Abstract (arXiv)

We study the problem of solving linear programs of the form Ax≤ b, x≥0 with differential privacy. For homogeneous LPs Ax≥0, we give an efficient (ε,δ)-differentially private algorithm which with probability at least 1-β finds in polynomial time a solution that satisfies all but O(fracd2εlog2fracdδβ√logfrac1ρ0) constraints, for problems with margin ρ0>0. This improves the bound of O(fracd5εlog1.5frac1ρ0polylog(d,frac1δ,frac1β)) by [Kaplan-Mansour-Moran-Stemmer-Tur, STOC '25]. For general LPs Ax≤ b, x≥0 with potentially zero margin, we give an efficient (ε,δ)-differentially private algorithm that w.h.p drops O(fracd4εlog2.5fracdδ√log dU) constraints, where U is an upper bound for the entries of A and b in absolute value. This improves the result by Kaplan et al. by at least a factor of d5. Our techniques build upon privatizing a rescaling perceptron algorithm by [Hoberg-Rothvoss, IPCO '17] and a more refined iterative procedure for identifying equality constraints by Kaplan et al.