Statistical Indistinguishability of Learning Algorithms

Alkis Kalavasis, Amin Karbasi, Shay Moran, Grigoris Velegkas
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:15586-15622, 2023.

Abstract

When two different parties use the same learning rule on their own data, how can we test whether the distributions of the two outcomes are similar? In this paper, we study the similarity of outcomes of learning rules through the lens of the Total Variation (TV) distance of distributions. We say that a learning rule is TV indistinguishable if the expected TV distance between the posterior distributions of its outputs, executed on two training data sets drawn independently from the same distribution, is small. We first investigate the learnability of hypothesis classes using TV indistinguishable learners. Our main results are information-theoretic equivalences between TV indistinguishability and existing algorithmic stability notions such as replicability and approximate differential privacy. Then, we provide statistical amplification and boosting algorithms for TV indistinguishable learners.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-kalavasis23a, title = {Statistical Indistinguishability of Learning Algorithms}, author = {Kalavasis, Alkis and Karbasi, Amin and Moran, Shay and Velegkas, Grigoris}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {15586--15622}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/kalavasis23a/kalavasis23a.pdf}, url = {https://proceedings.mlr.press/v202/kalavasis23a.html}, abstract = {When two different parties use the same learning rule on their own data, how can we test whether the distributions of the two outcomes are similar? In this paper, we study the similarity of outcomes of learning rules through the lens of the Total Variation (TV) distance of distributions. We say that a learning rule is TV indistinguishable if the expected TV distance between the posterior distributions of its outputs, executed on two training data sets drawn independently from the same distribution, is small. We first investigate the learnability of hypothesis classes using TV indistinguishable learners. Our main results are information-theoretic equivalences between TV indistinguishability and existing algorithmic stability notions such as replicability and approximate differential privacy. Then, we provide statistical amplification and boosting algorithms for TV indistinguishable learners.} }
Endnote
%0 Conference Paper %T Statistical Indistinguishability of Learning Algorithms %A Alkis Kalavasis %A Amin Karbasi %A Shay Moran %A Grigoris Velegkas %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-kalavasis23a %I PMLR %P 15586--15622 %U https://proceedings.mlr.press/v202/kalavasis23a.html %V 202 %X When two different parties use the same learning rule on their own data, how can we test whether the distributions of the two outcomes are similar? In this paper, we study the similarity of outcomes of learning rules through the lens of the Total Variation (TV) distance of distributions. We say that a learning rule is TV indistinguishable if the expected TV distance between the posterior distributions of its outputs, executed on two training data sets drawn independently from the same distribution, is small. We first investigate the learnability of hypothesis classes using TV indistinguishable learners. Our main results are information-theoretic equivalences between TV indistinguishability and existing algorithmic stability notions such as replicability and approximate differential privacy. Then, we provide statistical amplification and boosting algorithms for TV indistinguishable learners.
APA
Kalavasis, A., Karbasi, A., Moran, S. & Velegkas, G.. (2023). Statistical Indistinguishability of Learning Algorithms. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:15586-15622 Available from https://proceedings.mlr.press/v202/kalavasis23a.html.

Related Material