DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.65

Solving Linear Programs with Differential Privacy

Authors: Alina Ene, Huy Le Nguyen, Ta Duy Nguyen, and Adrian Vladu

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract

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.

Cite as

Alina Ene, Huy Le Nguyen, Ta Duy Nguyen, and Adrian Vladu. Solving Linear Programs with Differential Privacy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 65:1-65:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ene_et_al:LIPIcs.APPROX/RANDOM.2025.65,
  author =	{Ene, Alina and Le Nguyen, Huy and Nguyen, Ta Duy and Vladu, Adrian},
  title =	{{Solving Linear Programs with Differential Privacy}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{65:1--65:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.65},
  URN =		{urn:nbn:de:0030-drops-244315},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.65},
  annote =	{Keywords: Differential Privacy, Linear Programming}
}

Search Results

Documents authored by Vladu, Adrian

Solving Linear Programs with Differential Privacy

Abstract

Cite as

Thanks for your feedback!

Could not send message