Summary
This work studies differentially private prediction. It has two major contributions:
a) Prediction corresponds to being given an initial labeled training set, and then subsequently making predictions on other data points based on it. This paper shows that differentially private prediction can be performed on an unbounded number of queries, with strong accuracy guarantees, with the initial training set sample complexity scaling only as a polynomial in the VC dimension of the hypothesis class. Prior work either studied prediction for a small number of queries or studied the more stringent task of private PAC learning where significantly stronger lower bounds are known (PAC learning asks for the release of an entire model as opposed to predictions alone).
b) Since queries correspond to data points, they are usually sensitive user information. The authors formalize a model of privacy (similar to joint differential privacy) that gives a meaningful notion of privacy for these data points, even when adversaries can choose the queries adaptively. Their algorithms satisfy this notion of privacy.
Strengths
This paper makes a valuable and somewhat surprising discovery by proving that differentially private prediction can be performed on an unbounded number of queries, with no training set sample complexity dependence on the number of queries! They leverage standard techniques such as sparse vector in clever ways to do so. They operate in rounds, and use queries themselves as data points for future rounds, calling upon techniques from the semi-supervised differentially private learning literature . Their results suggest new ways to get around lower bounds for differential privacy.
Their algorithms involve reducing private prediction to non-private PAC learning, and while their techniques are not yet practical in many cases (because of time complexity), their reduction can be readily extended to any non-private learning algorithm, and hence there is lots of potential for future work to come up with ways to make their techniques more practical.
Weaknesses
One (minor) drawback is that the notion of privacy defined for the adaptively chosen queries is (necessarily) not as strong as would be nice since the label for a data point needs to depend on the data point to achieve any reasonable notion of accuracy (since otherwise you can only do something like randomized response).
Questions
1) The reasoning for the use of LabelBoost didnt entirely make sense to me- the stated reason was that the predictions provided during a round are not consistent with any concept in the hypothesis class. However, it’s not immediately clear to me that this is a problem- for example, using agnostic (non-private) learning algorithms may get around this issue (at the expense of worse sample complexity dependence on the accuracy parameter). More explanation of this would be useful.
2) The comment about their model of prediction, in principle, allowing memorization was interesting. It’s not clear that this is true- it seems like memorizing something in the training set would affect future predictions which would affect the adversary’s views. Would love more clarification on this.
3) Is there a simple (eps, 0)- version of this algorithm? It’s not clear to me that approx DP is necessary (sparse vector by itself is pure DP, though a variant is used in this paper).
4) The diagrams in the privacy proofs are a little too convoluted to be useful to the reader. I don’t have great suggestions on how to simplify them, but the privacy proofs by themselves are relatively simple, and I’m not sure the diagrams make them simpler to understand.
5) Some minor comments:
a) In Algorithm LabelBoost step 4, ‘choose’ based on exponential mechanism is not well defined since the score function is not specified (it can be inferred from context that it’s the negative of empirical risk) but specifying would be good.
b) In Claim E.4 don’t you need to account for the fact that the function labeling the sample is not the real function, but rather the one chosen by LabelBoost? Specifically, Claim E.3 is about a function with 0 sample error, whereas LabelBoost will incur some error, and hence I think you want a version of claim E.3 where sample error is bounded by alpha.
c) On page 8, where it says ‘using standard privacy amplification arguments, BetweenThresholds can be modified to allow for c times of outputting bot before halting)’, I think you mean privacy composition.
Rating
9: Very Strong Accept: Technically flawless paper with groundbreaking impact on at least one area of AI/ML and excellent impact on multiple areas of AI/ML, with flawless evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Limitations
Limitations adequately addressed.