SCALABLE PRIVATE LEARNING WITH PATE
The rapid adoption of machine learning has increased concerns about the privacy implications of machine learning models trained on sensitive data, such as medical records or other personal information. To address those concerns, one promising approach is Private Aggregation of Teacher Ensembles, or PATE, which transfers to a "student" model the knowledge of an ensemble of "teacher" models, with intuitive privacy provided by training teachers on disjoint data and strong privacy guaranteed by noisy aggregation of teachers' answers. However, PATE has so far been evaluated only on simple classification tasks like MNIST, leaving unclear its utility when applied to larger-scale learning tasks and real-world datasets. In this work, we show how PATE can scale to learning tasks with large numbers of output classes and uncurated, imbalanced training data with errors. For this, we introduce new noisy aggregation mechanisms for teacher ensembles that are more selective and add less noise, and prove their tighter differential-privacy guarantees. Our new mechanisms build on two insights: the chance of teacher consensus is increased by using more concentrated noise and, lacking consensus, no answer need be given to a student. The consensus answers used are more likely to be correct, offer better intuitive privacy, and incur lower-differential privacy cost. Our evaluation shows our mechanisms improve on the original PATE on all measures, and scale to larger tasks with both high utility and very strong privacy (ε < 1.0).
This paper considers the problem of private learning and uses the PATE framework to achieve differential privacy. The dataset is partitioned and multiple learning algorithms produce so-called teacher classifiers. The labels produced by the teachers are aggregated in a differentially private manner and the aggregated labels are then used to train a student classifier, which forms the final output. The novelty of this work is a refined aggregation process, which is improved in three ways:
a) Gaussian instead of Laplace noise is used to achieve differential privacy.
b) Queries to the aggregator are "filtered" so that the limited privacy budget is only expended on queries where the teachers are confident and the student is uncertain or wrong.
c) A data-dependent privacy analysis is used to attain sharper bounds on the privacy loss with each query.
I think this is a nice modular framework form private learning, with significant refinements relative to previous work that make the algorithm more practical. On this basis, I think the paper should be accepted. However, I think some clarification is needed with regard to item c above:
Theorem 2 gives a data-dependent privacy guarantee. That is, if there is one label backed by a clear majority of teachers, then the privacy loss (as measured by Renyi divergence) is low. This data-dependent privacy guarantee is likely to be much tighter than the data-independent guarantee.
However, since the privacy guarantee now depends on the data, it is itself sensitive information. How is this issue resolved? If the final privacy guarantee is data-dependent, then this is very different to the way differential privacy is usually applied. This would resemble the "privacy odometer" setting of Rogers-Roth-Ullman-Vadhan [ https://arxiv.org/abs/1605.08294 ]. 
Another way to resolve this would be to have an output-dependent privacy guarantee. That is, the privacy guarantee would depend only on public information, rather than the private data. The widely-used "sparse vector" technique [ http://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf#page=59 ] does this.
In any case, this is an important issue that needs to be clarified, as it is not clear to me how this is resolved.
The algorithm in this work is similar to the so-called median mechanism [ https://www.cis.upenn.edu/~aaroth/Papers/onlineprivacy.pdf ] and private multiplicative weights [ http://mrtz.org/papers/HR10mult.pdf ]. These works also involve a "student" being trained using sensitive data with queries being answered in a differentially private manner. And, in particular, these works also filter out uninformative queries using the sparse vector technique. It would be helpful to add a comparison.