Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Given a dataset consisting of $n$ users, where each user $i$ has a sequence $(x^i_1, y^i_1), \ldots, (x^i_m, y^i_m)$ of $m$ samples, the goal of this paper is to investigate differentially private learning in three settings: central-pure ($\epsilon$-DP), central-approximate (($\epsilon, \delta$)-DP), and local-pure.

Using results on correlated sampling, global stability, and private selection algorithms, the authors built efficient algorithms for the three above-mentioned settings. The key idea is to have each user first "learn" insights from their $m$ samples (and obtain a local hypothesis candidate), and then use DP selection algorithm (e.g., the Exponential Mechanism) to find the best hypothesis. Finally, the authors give lower bounds for the three DP models.
main_review: Overall, I think the authors made a great contribution towards the problem of differentially private learning where each user has $m$ samples. I like the comprehensive results and the systematic investigation of the problem. 


Some (minor) issues:
- Practicality: while from a theoretical point of view, the paper made significant contribution, it is unclear to me how practical the algorithms are. For example, how to learn a hypothesis from samples, how to encode hypotheses into the DP selection algorithms. It would be great if the authors can explain them more clearly and even provide corresponding code.
- The relationship between item-level and user-level: in this paper, item-level DP means each user has only one item. But more commonly, item-level DP assumes each user has some number of items, but the definition of neighborhood Is different (only one item is different). I understand that the authors might want to avoid confusion, but this could still confuse those who are familiar with DP. A better way of presentation could be changing item-level and user-level to single-value setting and multi-value setting, and clarifying the difference between item-level and user-level protection (e.g., in the graph setting, item-level definition protects the existence of an edge, while user-level definition protects the existence of a node). 
- Theorems 2 and 3 both mention the local model: Theorem 3 should be in the central model?
- SQ is not spelled out.


Disclaimer: I am outside of the NeurIPS community and haven't read a lot NeurIPS papers. This paper is a clear acceptance for me, but I cannot rank it among other papers.


limitations_and_societal_impact: N/A: In Checklist, the authors said they describe the limitations in Section 5; but Section 5 only includes conclusions and several open questions for future work. The authors did not mark any potential negative societal impacts.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The setting in the paper is PAC learning with user-level DP, where the main difference from previous works is that each user may have many examples (instead of only a single example).
The main result is that it is possible to learn [(epsilon,delta)-DP] with a small number of users as long as each user has sufficiently many samples.
Another main result is epsilon-DP learner in the local model.
Moreover, the authors provide nearly matching lower bounds. 
main_review: Significance: It seems like the paper discusses some fundamental questions in Learning with DP guarantees. The results are significant and interesting.
It seems like the techniques introduced in the paper might be of independent interest.
It is hard for me to fully understand the motivation of this setting, due to some lack of knowledge of previous results.

Clarity and relation to prior work: The paper is very clear and easy to follow. Also, the literature review is thorough.

It was quite hard for me to check some proofs, due to lack of previous technical background. 
I tend to accept the paper, but I will keep my confidence low.
limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies user level differential privacy in the setting of PAC learning. They study both central and local model of differential privacy and both approximate and exact differential privacy. In the central model, they show that they only need log(1/\delta)\epsilon users and Ldim^O(1) samples per users to guarantee (\epsilon, \delta)  differential privacy whereas in the item level DP, one needs Ldim^O(1) samples.  They also provide nearly matching lower bounds on the number of users.
main_review: I think the paper studies an interesting problem of DP guarantees for user level setting in the PAC model. Generally, there is a lot of interest in differentially privacy and it would be of interest to the community. This paper obtains the first bounds in the user level model in PAC setting. It shows an interesting result that we only require users  depending on epsilon, delta for (epsilon, delta) DP independent of the Littlestone dimension and the number of samples depend on the Littlestone dimension. This paper builds on existing connections between global stability and differential privacy and additionally, uses the technique of correlated sampling. This idea of using correlated sampling in this setting seems interesting to me. The paper is mostly well written.

Some questions - 

1) I don’t understand the statement in line 35 “One way to understand this problem is to artificially limit the number of training examples contributed by each user.” when the later statement says that DP cost is less when each user has large number of samples.
2) Is this the first paper studying user level DP in the PAC learning setting?
3) The authors mention that there is a gap between user level and item level privacy in the local model. What is the relationship between SQ-dim and PRdim? The authors mention that SQ-dim can be bigger. Is it always lower bounded by PRdim?
4) Is there any general connection or relationship that one can obtain between the user level and item level bounds?
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies user-level privacy for any privately PAC learnable class in the setting where each user holds more than one training example. It first shows that for any online learnable class (with finite Littlestone dimension), it's possible to learn the class with an (\eps,\delta)-DP algorithm using only O(\log(1/\delta)/\eps) users. Then it gives sample complexity of a generic \eps-DP learner in both the local and the central models. Finally, it shows that we can take any efficient SQ algorithm and turn it into an efficient learner in the user-level setting. The protocols are based on a novel connection between correlated sampling and DP learning.
main_review: This is a well-written paper. I enjoy reading it. Protecting user-level privacy has raised much attention recently, and it's timely research. I particularly like the idea of exploiting the shared randomness between users, which is handled by using correlated sampling. It's nontrivial to connect the correlated sampling technique with DP learning. The theoretical results and algorithms are sound. My only question is in Algorithm 1, how do you select A? Can it be any learners satisfying that A's output consists only of hypotheses with (\alpha, \beta/k)-accuracy? 

Minor comment: A type in line 35 ``artifically''
limitations_and_societal_impact: The paper discussed the limitations and proposed several open questions.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This work tackles the problem of PAC learning with user-level privacy guarantees. The paper's primary contribution is a nearly tight characterisation of the number of users required when the learning is via an 1) $\epsilon$-DP and 2) $(\epsilon,\delta)$-DP algorithm. At the core of the paper is the idea that users can share randomness before the sampling stage. This insight allows for the learnability of all online learnable classes, with much fewer users(exponentially fewer in terms of $d$).
main_review: The paper is quite well written. The work presents a creative and original connection between correlated sampling and DP learning. The implications of the assumption are explored in-depth. 
limitations_and_societal_impact: Yes, the authors have adequately discussed the limitations and the societal impact.
review_title: null

Meta-review: All the reviewers greatly appreciate the significance and novelty of this work, with some minor issues raised. For example, 
- making the statement of some theorems more clear, 
- motivating this work better, 
- explaining the practicality, 

and so on. Please try the best to address these issues in the final version
Decision: Accept (Poster)