Solving Positive Linear Programs with Differential Privacy

Alina Ene, Huy Nguyen, Ta Duy Nguyen, Adrian Vladu
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:28040-28057, 2026.

Abstract

We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-ene26a, title = {Solving Positive Linear Programs with Differential Privacy}, author = {Ene, Alina and Nguyen, Huy and Nguyen, Ta Duy and Vladu, Adrian}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {28040--28057}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/ene26a/ene26a.pdf}, url = {https://proceedings.mlr.press/v306/ene26a.html}, abstract = {We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.} }
Endnote
%0 Conference Paper %T Solving Positive Linear Programs with Differential Privacy %A Alina Ene %A Huy Nguyen %A Ta Duy Nguyen %A Adrian Vladu %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-ene26a %I PMLR %P 28040--28057 %U https://proceedings.mlr.press/v306/ene26a.html %V 306 %X We study differentially private approximation algorithms for positive linear programs (LPs with nonnegative coefficients and variables), focusing on the fundamental families of packing, covering, and mixed packing-covering formulations. We focus on the high-sensitivity, constraint-private regime of Hsu-Roth-Roughgarden-Ullman (ICALP 2014), where neighboring instances may differ by an arbitrary single constraint, so one cannot hope to approximately satisfy every constraint under privacy. We give private solvers that return approximate solutions while violating only a controlled number of constraints. Our algorithms improve the prior instance-dependent guarantees, and also yield new data-independent bounds that depend only on the dimension. Our techniques involve a dense multiplicative weights update method developed from a regularized dual viewpoint, which we analyze in a way that exploits structure specific to positive LPs.
APA
Ene, A., Nguyen, H., Nguyen, T.D. & Vladu, A.. (2026). Solving Positive Linear Programs with Differential Privacy. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:28040-28057 Available from https://proceedings.mlr.press/v306/ene26a.html.

Related Material