Solving Linear Programs with Differential Privacy

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.