2026-07-23T17:30:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24431 2025-12-12T15:01:49Z ddc:004 open_access

Solving Linear Programs with Differential Privacy Ene, Alina Le Nguyen, Huy Nguyen, Ta Duy Vladu, Adrian Differential Privacy Linear Programming 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(d²/ε log²(d/(δβ))√{log 1/ρ₀}) constraints, for problems with margin ρ₀ > 0. This improves the bound of O(d⁵/ε log^{1.5} 1/ρ₀ polylog(d,1/δ,1/β)) 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(d⁴/ε log^{2.5} d/δ √{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 d⁵. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alina Ene and Huy Le Nguyen and Ta Duy Nguyen and Adrian Vladu 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.65 urn:nbn:de:0030-drops-244315 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.65 eng https://creativecommons.org/licenses/by/4.0/legalcode