Venue: NeurIPS 2022 Conference

Reviews:

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: The paper considers the tasks of adversarial robustness and explores the difference between omniscient adversary, and the computationally bounded adversary. It constructs several learning tasks demonstrating the difference  between informatic theoretic and efficient learning.
strengths_and_weaknesses: I did not find anything wrong with the paper, but I haven't understood its arguments either due to my limited knowledge of this area.
questions: Do the results work also for infinite (and in particular, uncountable) domains? Such as learning something from real-numbered observations? Specially the number of parameters needs to be reconsidered here due to space filling curves.

I'm sorry for such an uninformative review; it did not match my knowledge and I don't have the time to understand the relevant context.
limitations: -
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 the computational benefits of overparametrization in standard and robust learning. The paper suggests that there are learning tasks where overparametrization is needed from a computationally efficient, standard and robust, learning. 

More specifically, as I understand it,  the paper shows in Theorem 1 (Part 1) that there are learning tasks where “efficient” standard learning and “efficient” robust learning require polynomial (in the input/instance size) overparameterization. 

In Theorem 1 Part 2, the paper shows that there are robust learning tasks such that there are efficient underparameterized learners against computationally bounded adversaries, but overparamertization is needed when the adversary is computationally unbounded (even for information-theoretically efficient robust learners). 

The result indicates that there is a statistical-computational tradeoff between efficient robust learning and inefficient robust learning.

strengths_and_weaknesses: I find the main result of the paper interesting. The gaps established in this work are polynomial (as opposed to exponential), but I think that’s still interesting from a practical perspective. The paper is rigorous and formal in its treatment of the definition of “efficient” learning, which is nice. The paper is clear and well-written.


questions: In Theorem 1 Part 1, by checking Theorem 11, it seems that the sample complexity is also polynomially larger. I wonder if it is possible to obtain a result where the efficient learner only needs overparamterization but no increase in sample complexity compared to the information-theoretic learner.

limitations:  It might be good to reflect on the results of the paper, and discuss their practical implications, and any future directions that might be good to address from this work.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work studies whether there exist any learning tasks that are computationally bounded robust learning need to have more model parameters than non-robust learning; and whether such tasks can be done with fewer model parameters for polynomial-time adversaries compared with information-theoretic adversaries. The author gives positive answers to both of the questions by leveraging cryptography and coding theory.
strengths_and_weaknesses: The questions asked by the work are interesting and novel to the best of my knowledge. Such studies would be helpful for the robust adversarial learning community. 
The writing needs to have more structure improvement. However, since I’m not familiar with cryptography and coding theory, I’m not able to judge whether the technical idea is novel or sound.
questions: 1. Missing formal definition of $L(\cdot,\lambda)$.
2. In the main paper top of page 6 you discuss theorem 32, which is a restatement of theorem 13, and would be good to state theorem 13 before discussing it. In the statement of construction 10, you mention theorem 20 which also does not appear in the main paper. 
3. Personally I did not find it’s helpful to give construction 10 and 14 in detail in the main paper.  It’d be helpful to combine theorem 11, 12, 13, 15, 16 with their discussion or comments instead of isolating them separately.
4. It seems to me that the argument of computational perspective on page 5 line 154-164 has a similar idea as the robustness on page 6 line 169-177, and I did not find any arguments regarding why $\alpha<\beta$, but this should be an important criterion in theorem 1. Can you claim what would happen if I replace $\beta$ with $\alpha$ in argument line 169-177?

limitations: Yes
review_title: null

Meta-review: metareview: This paper studies the computational benefits of overparametrization in standard and robust learning. The paper suggests that there are learning tasks where overparametrization is needed from a computationally efficient, standard and robust, learning.
In Theorem 1 Part 2, the paper shows that there are robust learning tasks such that there are efficient underparameterized learners against computationally bounded adversaries, but overparamertization is needed when the adversary is computationally unbounded (even for information-theoretically efficient robust learners).
The result indicates that there is a statistical-computational tradeoff between efficient robust learning and inefficient robust learning.

The referees are leaning towards acceptance and that is also my recommendation,
confidence: Less certain
Decision: Accept