Revisiting Model-Agnostic Private Learning: Faster Rates and Active Learning

Chong Liu, Yuqing Zhu, Kamalika Chaudhuri, Yu-Xiang Wang
Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, PMLR 130:838-846, 2021.

Abstract

The Private Aggregation of Teacher Ensembles (PATE) framework is one of the most promising recent approaches in differentially private learning. Existing theoretical analysis shows that PATE consistently learns any VC-classes in the realizable setting, but falls short in explaining its success in more general cases where the error rate of the optimal classifier is bounded away from zero. We fill in this gap by introducing the Tsybakov Noise Condition (TNC) and establish stronger and more interpretable learning bounds. These bounds provide new insights into when PATE works and improve over existing results even in the narrower realizable setting. We also investigate the compelling idea of using active learning for saving privacy budget. The novel components in the proofs include a more refined analysis of the majority voting classifier — which could be of independent interest — and an observation that the synthetic “student” learning problem is nearly realizable by construction under the Tsybakov noise condition.

Cite this Paper

BibTeX
@InProceedings{pmlr-v130-liu21c, title = { Revisiting Model-Agnostic Private Learning: Faster Rates and Active Learning }, author = {Liu, Chong and Zhu, Yuqing and Chaudhuri, Kamalika and Wang, Yu-Xiang}, booktitle = {Proceedings of The 24th International Conference on Artificial Intelligence and Statistics}, pages = {838--846}, 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/liu21c/liu21c.pdf}, url = {https://proceedings.mlr.press/v130/liu21c.html}, abstract = { The Private Aggregation of Teacher Ensembles (PATE) framework is one of the most promising recent approaches in differentially private learning. Existing theoretical analysis shows that PATE consistently learns any VC-classes in the realizable setting, but falls short in explaining its success in more general cases where the error rate of the optimal classifier is bounded away from zero. We fill in this gap by introducing the Tsybakov Noise Condition (TNC) and establish stronger and more interpretable learning bounds. These bounds provide new insights into when PATE works and improve over existing results even in the narrower realizable setting. We also investigate the compelling idea of using active learning for saving privacy budget. The novel components in the proofs include a more refined analysis of the majority voting classifier — which could be of independent interest — and an observation that the synthetic “student” learning problem is nearly realizable by construction under the Tsybakov noise condition. } }
Endnote
%0 Conference Paper %T Revisiting Model-Agnostic Private Learning: Faster Rates and Active Learning %A Chong Liu %A Yuqing Zhu %A Kamalika Chaudhuri %A Yu-Xiang Wang %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-liu21c %I PMLR %P 838--846 %U https://proceedings.mlr.press/v130/liu21c.html %V 130 %X The Private Aggregation of Teacher Ensembles (PATE) framework is one of the most promising recent approaches in differentially private learning. Existing theoretical analysis shows that PATE consistently learns any VC-classes in the realizable setting, but falls short in explaining its success in more general cases where the error rate of the optimal classifier is bounded away from zero. We fill in this gap by introducing the Tsybakov Noise Condition (TNC) and establish stronger and more interpretable learning bounds. These bounds provide new insights into when PATE works and improve over existing results even in the narrower realizable setting. We also investigate the compelling idea of using active learning for saving privacy budget. The novel components in the proofs include a more refined analysis of the majority voting classifier — which could be of independent interest — and an observation that the synthetic “student” learning problem is nearly realizable by construction under the Tsybakov noise condition.
APA
Liu, C., Zhu, Y., Chaudhuri, K. & Wang, Y.. (2021). Revisiting Model-Agnostic Private Learning: Faster Rates and Active Learning . Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 130:838-846 Available from https://proceedings.mlr.press/v130/liu21c.html.

Related Material