Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the issue of learning and refutation in the setting of non-interactive local differential privacy. It provides a characterization of the sample complexity of agnostic PAC learning for non-interactive LDP protocols and shows the equivalence of learning and refutation in the setting of agnostic learning. 

strengths_and_weaknesses: I am not an expert in this field.  I believe that the results in this paper are mathematically sound.  The presentation is well-organized and also the topic about learning and refutation in the LDP setting is very interesting. 

One minor: some mistakes in the definition of learning problem Page 1
questions:  I have some one major concern:

(1)What is the relation of the refutation in this paper to that in Vadhan [2017]? I found that they are different but could not see the direct equivalence.

limitations: It needs some more detailed explanation of the relationship to the similar issues in the literature.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies two tasks, learning and refutation, in non-interactive local differential privacy. It proves the same lower bounds of the sample complexity of agnostic PAC learning for both tasks, which matches the upper bound proved in the previous work. Consequently, the paper shows the equivalence between learning and refutation in the agnostic setting.
strengths_and_weaknesses: ### Strengths
The result is solid and complete. It closes the gap between upper bound and lower bound of sample complexity for learning and refutation, in the setting of agnostic PAC learning and non-interactive local differential privacy.

### Weaknesses
The proof could be more hierarchical.

Minor issue:
1. Typo: In lemma 8, m_{v, x} -> m_{a, x}
questions: As the paper is studied for the finite concept class, one question is whether the result could be extended to the infinite concept class setting.
limitations: Yes, the paper describes several open problems as the future work.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Setting and main contributions:
The paper is about the tasks of learning and refutation concept classes in the local differential privacy (LDP) model (which is a model with strong privacy guarantees for users, even from the central party).

The first main result is closing an open question of showing a lower bound on the sample complexity for agnostic learning. This gives a full characterization of these models, as upper bounds for learning and refutation, and a lower bound for refutation were obtained by Edmonds, Nikolov, and Ullman (STOC20).

The second main contribution is in the realizable model: an LDP protocol with upper bounds on the sample complexity for learning and refutation, and also a lower bound on refutation.
strengths_and_weaknesses: The paper studies fundamental questions regarding learning for the important privacy model - LDP.
The contributions are significant.

The first contribution closes the gap in the literature on learning and refutation in the agnostic model. 
Specifically, I find the technique for proving the lower bound very elegant. 
The idea of working with the difference matrix seems interesting and may be of independent interest, in my opinion.

In the second contribution, the authors define a quantity, eta(C,alpha), that quantifies the sample complexity in the realizable case. The lower bound idea is similar to the agnostic case when working with the "right" quantity eta(C,alpha).

I recommend accepting the paper.
questions: -
limitations: -
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the sample complexity of learning and refutation in the model of non-interactive local differential privacy (LDP). In a non-interactive LDP protocol, all users sends a message to the server once, simultaneously and independently. In the agnostic setting, the authors show that learning and refutation are equivalent (up to a logarithmic approximation) wrt sample complexity. The main result gives a lower bound on the sample complexity in terms of the "approximate $\gamma_2$ norm" of a matrix associated with the concept class, which in conjunction with earlier work by Edmonds et al. (2019) shows this equivalence. In the realizable setting, the authors show that refutation implies learning.

strengths_and_weaknesses: The paper resolves an open question for lower bounds in the agnostic case in the non-interactive LDP setting. The presentation in certain parts can be improved. In particular, deferring some of the full proofs to the appendix and including some intuition for the two main quantities that appears in the statements of theorems, viz., $\gamma_2$ and $\eta$ can make the presentation better. Also the reader can benefit from a separate Contributions section with pointers to the main statements.

questions: * Why is the approximate $\gamma_2$ norm not defined in the main text? Given that this norm features extensively, a definition in the main text is desirable.

* In Lemma 9,  the $\bullet$ operator is not defined.

* Why is the realizable refutation setting more difficult than the agnostic case?

* What is a good intuition for the definition of the quantity $\eta(\mathcal{C},\alpha)$ in Definition 13 that features in the bounds in Theorem 2 for the realizable case?




limitations: The authors do not address any potential negative societial impact of the work and I reckon there is none.
review_title: null

Meta-review: metareview: This paper provides a characterization of the sample complexity of agnostic learning under local differential privacy (LDP) and show that it is equivalent to refutation. The mathematical insights from the paper might be valuable in future research. It is a clean contribution, with positive feedback from all reviewers. 
confidence: Certain
Decision: Accept