Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets

Arun Ganesh, Abhradeep Thakurta, Jalaj Upadhyay
Proceedings of Thirty Sixth Conference on Learning Theory, PMLR 195:1730-1773, 2023.

Abstract

In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for sampling from the exponential mechanism, whose privacy analysis does not depend on convexity, and which can be stopped at anytime without compromising privacy, and ii) tight uniform stability guarantees for the exponential mechanism. As a direct consequence, we obtain optimal excess empirical and population risk guarantees for (strongly) convex losses under both pure and approximate differential privacy (DP). The framework allows us to design a DP uniform sampler from a Rashomon set. Rashomon sets are widely used in interpretable and robust machine learning, understanding variable importance, and characterizing fairness.

Cite this Paper

BibTeX
@InProceedings{pmlr-v195-ganesh23a, title = {Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets}, author = {Ganesh, Arun and Thakurta, Abhradeep and Upadhyay, Jalaj}, booktitle = {Proceedings of Thirty Sixth Conference on Learning Theory}, pages = {1730--1773}, year = {2023}, editor = {Neu, Gergely and Rosasco, Lorenzo}, volume = {195}, series = {Proceedings of Machine Learning Research}, month = {12--15 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v195/ganesh23a/ganesh23a.pdf}, url = {https://proceedings.mlr.press/v195/ganesh23a.html}, abstract = {In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for sampling from the exponential mechanism, whose privacy analysis does not depend on convexity, and which can be stopped at anytime without compromising privacy, and ii) tight uniform stability guarantees for the exponential mechanism. As a direct consequence, we obtain optimal excess empirical and population risk guarantees for (strongly) convex losses under both pure and approximate differential privacy (DP). The framework allows us to design a DP uniform sampler from a Rashomon set. Rashomon sets are widely used in interpretable and robust machine learning, understanding variable importance, and characterizing fairness.} }
Endnote
%0 Conference Paper %T Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets %A Arun Ganesh %A Abhradeep Thakurta %A Jalaj Upadhyay %B Proceedings of Thirty Sixth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2023 %E Gergely Neu %E Lorenzo Rosasco %F pmlr-v195-ganesh23a %I PMLR %P 1730--1773 %U https://proceedings.mlr.press/v195/ganesh23a.html %V 195 %X In this paper we provide an algorithmic framework based on Langevin diffusion (LD) and its corresponding discretizations that allow us to simultaneously obtain: i) An algorithm for sampling from the exponential mechanism, whose privacy analysis does not depend on convexity, and which can be stopped at anytime without compromising privacy, and ii) tight uniform stability guarantees for the exponential mechanism. As a direct consequence, we obtain optimal excess empirical and population risk guarantees for (strongly) convex losses under both pure and approximate differential privacy (DP). The framework allows us to design a DP uniform sampler from a Rashomon set. Rashomon sets are widely used in interpretable and robust machine learning, understanding variable importance, and characterizing fairness.
APA
Ganesh, A., Thakurta, A. & Upadhyay, J.. (2023). Universality of Langevin Diffusion for Private Optimization, with Applications to Sampling from Rashomon Sets. Proceedings of Thirty Sixth Conference on Learning Theory, in Proceedings of Machine Learning Research 195:1730-1773 Available from https://proceedings.mlr.press/v195/ganesh23a.html.

Related Material