Solving Linear Programs with Differential Privacy
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915390043455488 |
|---|---|
| author | Ene, Alina Nguyen, Huy Le Nguyen, Ta Duy Vladu, Adrian |
| author_facet | Ene, Alina Nguyen, Huy Le Nguyen, Ta Duy Vladu, Adrian |
| contents | We study the problem of solving linear programs of the form $Ax\le b$, $x\ge0$ with differential privacy. For homogeneous LPs $Ax\ge0$, we give an efficient $(ε,δ)$-differentially private algorithm which with probability at least $1-β$ finds in polynomial time a solution that satisfies all but $O(\frac{d^{2}}ε\log^{2}\frac{d}{δβ}\sqrt{\log\frac{1}{ρ_{0}}})$ constraints, for problems with margin $ρ_{0}>0$. This improves the bound of $O(\frac{d^{5}}ε\log^{1.5}\frac{1}{ρ_{0}}\mathrm{poly}\log(d,\frac{1}δ,\frac{1}β))$ by [Kaplan-Mansour-Moran-Stemmer-Tur, STOC '25]. For general LPs $Ax\le b$, $x\ge0$ with potentially zero margin, we give an efficient $(ε,δ)$-differentially private algorithm that w.h.p drops $O(\frac{d^{4}}ε\log^{2.5}\frac{d}δ\sqrt{\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^{5}$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_10946 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving Linear Programs with Differential Privacy Ene, Alina Nguyen, Huy Le Nguyen, Ta Duy Vladu, Adrian Data Structures and Algorithms We study the problem of solving linear programs of the form $Ax\le b$, $x\ge0$ with differential privacy. For homogeneous LPs $Ax\ge0$, we give an efficient $(ε,δ)$-differentially private algorithm which with probability at least $1-β$ finds in polynomial time a solution that satisfies all but $O(\frac{d^{2}}ε\log^{2}\frac{d}{δβ}\sqrt{\log\frac{1}{ρ_{0}}})$ constraints, for problems with margin $ρ_{0}>0$. This improves the bound of $O(\frac{d^{5}}ε\log^{1.5}\frac{1}{ρ_{0}}\mathrm{poly}\log(d,\frac{1}δ,\frac{1}β))$ by [Kaplan-Mansour-Moran-Stemmer-Tur, STOC '25]. For general LPs $Ax\le b$, $x\ge0$ with potentially zero margin, we give an efficient $(ε,δ)$-differentially private algorithm that w.h.p drops $O(\frac{d^{4}}ε\log^{2.5}\frac{d}δ\sqrt{\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^{5}$. 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. |
| title | Solving Linear Programs with Differential Privacy |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.10946 |