Private optimization without constraint violations

Andres Munoz, Umar Syed, Sergei Vassilvtiskii, Ellen Vitercik
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:2557-2565, 2021.

Abstract

We study the problem of differentially private optimization with linear constraints when the right-hand-side of the constraints depends on private data. This type of problem appears in many applications, especially resource allocation. Previous research provided solutions that retained privacy but sometimes violated the constraints. In many settings, however, the constraints cannot be violated under any circumstances. To address this hard requirement, we present an algorithm that releases a nearly-optimal solution satisfying the constraints with probability 1. We also prove a lower bound demonstrating that the difference between the objective value of our algorithm’s solution and the optimal solution is tight up to logarithmic factors among all differentially private algorithms. We conclude with experiments demonstrating that our algorithm can achieve nearly optimal performance while preserving privacy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-munoz21a, title = { Private optimization without constraint violations }, author = {Munoz, Andres and Syed, Umar and Vassilvtiskii, Sergei and Vitercik, Ellen}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {2557--2565}, year = {2021}, editor = {Banerjee, Arindam and Fukumizu, Kenji}, volume = {130}, series = {Proceedings of Machine Learning Research}, month = {13--15 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v130/munoz21a/munoz21a.pdf}, url = {https://proceedings.mlr.press/v130/munoz21a.html}, abstract = { We study the problem of differentially private optimization with linear constraints when the right-hand-side of the constraints depends on private data. This type of problem appears in many applications, especially resource allocation. Previous research provided solutions that retained privacy but sometimes violated the constraints. In many settings, however, the constraints cannot be violated under any circumstances. To address this hard requirement, we present an algorithm that releases a nearly-optimal solution satisfying the constraints with probability 1. We also prove a lower bound demonstrating that the difference between the objective value of our algorithm’s solution and the optimal solution is tight up to logarithmic factors among all differentially private algorithms. We conclude with experiments demonstrating that our algorithm can achieve nearly optimal performance while preserving privacy. } }
Endnote
%0 Conference Paper %T Private optimization without constraint violations %A Andres Munoz %A Umar Syed %A Sergei Vassilvtiskii %A Ellen Vitercik %B Proceedings of The 24th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2021 %E Arindam Banerjee %E Kenji Fukumizu %F pmlr-v130-munoz21a %I PMLR %P 2557--2565 %U https://proceedings.mlr.press/v130/munoz21a.html %V 130 %X We study the problem of differentially private optimization with linear constraints when the right-hand-side of the constraints depends on private data. This type of problem appears in many applications, especially resource allocation. Previous research provided solutions that retained privacy but sometimes violated the constraints. In many settings, however, the constraints cannot be violated under any circumstances. To address this hard requirement, we present an algorithm that releases a nearly-optimal solution satisfying the constraints with probability 1. We also prove a lower bound demonstrating that the difference between the objective value of our algorithm’s solution and the optimal solution is tight up to logarithmic factors among all differentially private algorithms. We conclude with experiments demonstrating that our algorithm can achieve nearly optimal performance while preserving privacy.
APA
Munoz, A., Syed, U., Vassilvtiskii, S. & Vitercik, E.. (2021). Private optimization without constraint violations . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:2557-2565 Available from https://proceedings.mlr.press/v130/munoz21a.html.

Related Material