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 work provides lower bounds in the noise free setting for learning two hidden layer networks in the Gaussian space. Basically, the whole concept is to embed hard problems over the uniform in hypercube to the Gaussian space. This is not something new, this has been done before in [1] for proving lower bound in the agnostic learning halfspaces over the Gaussian distribution. In contrast, this work provides noise-free lower bounds. They provide a super-polynomial SQ lower bound, a cryptographic lower bound under the LWR assumption. Moreover, they also provide lower bounds for the query model which is more powerful than the PAC learning model. 

The whole concept is the following: To embed hard problems from the hypercube to the Gaussian space, we can use a similar idea like in [1], i.e., using the sign function. The DV lift basically does that by adding 2 more hidden layers (with ReLU components). So, a hard problem with L-Layers can provide lower bounds for L+2 layers in Gaussian space.

The authors decrease the number of layers from +2 Layers to +1. To do that, first they show a way to do it using a very large network, basically, they start from an exponential construction Eq.(11) and then they decrease it to $d^m$ by make the network more sparse, using the distributional properties of the Gaussian. They introduce some error in the construction but they show that this is indeed very small. After that the hardness proofs follow from a reduction.



[1] Adam Klivans and Pravesh Kothari. Embedding hard learning problems into gaussian space.
strengths_and_weaknesses: # Pros
1. This is good result. The authors provide lower bounds under several assumptions/models. 
2. This work is very well-written. Checked almost all the proofs and the claims are sound.

# Cons
Not really a con just a comment. The lower bounds are for 2-hidden layer networks where there are results for 1-hidden layer networks for the CSQ model. [GGJ+20],[DKKZ20] Basically, the trade-off is stronger model and 2-hidden layer instead of 1. In general, I would expect stronger lower bounds for 2-hidden layer network. 


Overall, I recommend for acceptance.
questions: Some presentation suggestions:
I would suggest the authors to add after section 1.2 lines 197 some more intuition about the construction and the idea that they use to decrease the size of the network. 
Some fullstops and commas in equations are missing, i.e., eq. 2.
limitations: everything is good.
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: The authors prove statistical query lower bounds for learning polynomial-sized neural networks with two hidden layers. The bound is superpolynomial in the input dimension $d$ (or the query tolerance is negligible in $d$). No cryptographic assumptions are needed for these bounds to hold. The authors also show that, under the learning with rounding with polynomial modulus cryptographic assumption, no polynomial-time algorithm can learn neural networks with two hidden layers from Gaussian examples. The result is extended to neural networks with one hidden layer over the uniform distribution on the boolean hypercube. 
strengths_and_weaknesses: The paper is well-written and the review of the related work is thorough. A great deal of effort has been put into making sure that the paper is clear and accessible for a wide audience, particularly in the technical overview. This paper is a bit outside my expertise, but the results and techniques used are interesting and could be of independent interest. I believe this paper is relevant to the learning theory community.
questions: ### Suggestions

A conclusion should be included in the main body were the paper to be accepted. If there is room, a table comparing different lower bounds setting and contrasting the current paper with related work would be a great addition. 
limitations: Limitations: yes

Impact: N/A
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: The paper establishes hardness of learning neural networks with Gaussian inputs under various assumptions:
- statistical query learning, two hidden layers;
- cryptographic hardness of learning with rounding, two hidden layers;
- label query learning, existence of a family of pseudo-random functions, any fixed number of hidden layers.

The main tool for obtaining these results is a modified Danieli-Vardy transform (2021) that maps a Boolean example (x, y) to a Gaussian example (z, y') while remaining in the realizability setup.
strengths_and_weaknesses: **Strengths**
- A solid theoretical work that establishes new hardness results for the now ubiquitous neural networks.

**Weaknesses**
- The paper does not explicitly indicate the limitations of the results. For example, lines 67-68 say that "Theorem 1.1 rules out almost all known approaches for provably learning neural networks", but the most well-known approach to learn neural networks---SGD---is not ruled out by Thm 1.1.
questions: No questions
limitations: See weaknesses above.
review_title: null

Meta-review: metareview: This work provides lower bounds in the noise free setting for learning two hidden layer networks in the Gaussian space. Overall it is a fundamental result well within the scope of Neurips, continuing a solid line of work and I cannot see any reason for rejection.

The authors have engaged with the reviewers, and have committed to make minor revisions and clarifications which I am sure they will do.
confidence: Certain
Decision: Accept