Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This work fits the single-hidden-layer neural network to data generated by a teacher network with Gaussian parameters. Conclusion is drawn from experimental results that SGD with automated width selection has both sample and query complexity scaling linearly with the input dimension and width, which complies with the information-theoretic sample complexity bounds and is significantly more computationally efficient than the worst-case query lower bound suggests.

strength_and_weaknesses: **Strength**
- It’s of value to empirically measure both the sample complexity and the iteration complexity for learning with neural network of algorithms as simple as SGD. This work further simplifies the dynamic by running simulations on the data generated from a teacher single-hidden-layer Relu network and learning with a student single-hidden-layer Relu network whose width is automatically chosen. The motivation for this setup is straightforward to bring up the gap between the theoretical worst-case guarantees and the empirical performance in expectation. 
- The results also showcase the efficiency of SGD in training single-hidden-layer NNs, which may applies to NNs with more advanced structures. The experiments are designed in a well-organized way, and so are the results shown.

**Weakness**
Though many theoretical results were established for single-hidden-layer NNs, and it may be the reason why this work focuses on this simple structure: to directly contrast the results from the theory side and the practice side, results in this work may not bring sufficient insight why SGD trains NNs well  to the deep learning community.

clarity,_quality,_novelty_and_reproducibility: The paper is written with good clarity. Comments on quality and novelty are summarized in Strength/Weakness. I didn’t check the reproducibility but I’d like to believe the results are reproducible.


summary_of_the_review: This work focuses on a the open question that how well SGD trains NNs in terms of its sample and query complexity and draws a conclusion matching our expectiaion on empirical performance v.s. theoretical bounds . However, it's heavily limited by the overly simplified NN sturcture and the insufficient insight that could be drawn from the experimets. So I recommand a reject/weak reject.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper tries to show that SGD is effective in learning a ReLU teacher network. The results seem to suggest that the sample complexity is linear in input dimension and width. 
strength_and_weaknesses: strength:

a) The goal of the paper is well-motived.

weaknesses:

a) The title of the paper over claims the purpose of the paper. It only focuses on learning a ReLU teacher network, rather than provides general validation for SGD

b) Even though the current theoretical results only provide worse-case guarantees, I am not fully convinced that the experiments in this paper can illustrate the expected error of an algorithm for the following reasons: i) experiments can only validates some cases and the experiments in the paper are not extensive; ii) there are many versions of SGD, which can hugely affect the results. For example, the paper uses Adam stepsizes, and other stepsize schemes may lead to totally different observationsi. 

c)  I also suggest to try networks with more layers.

d) The writing needs improvement. There are same sentences in the abstract and introduction. 
clarity,_quality,_novelty_and_reproducibility: I believe the work is original. The paper is easy to read. 
summary_of_the_review: See above. 


-----------------------------------------------------------------
I read authors' response and I will keep my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper empirically studies fitting single-hidden-layer neural networks where data is also generated by single-hidden-layer ReLU teacher networks. This paper demonstrates that stochastic gradient descent (SGD) with automated width selection attains small expected errors for a specific experiment setting.   They finally claim that this result further suggests that SGD nearly achieves the information-theoretic sample complexity bounds.
strength_and_weaknesses: Strength:
1. Well organized, and the message is clear
2. the explanation of synthetic experiments is comprehensive. I believe that the result is reproducible.

Weakness:
1. This paper only conducts experiments for a specific case. In particular, they assume that the teacher network has independent Gaussian weights. Therefore, this is only a special case of the ReLU data-generating process.

2. There are no theoretical results. If one wants to claim that SGD can nearly achieve the information-theoretic sample complexity bounds under a certain condition, one would better derive some rigorous upper bound for the proposed algorithm. 
clarity,_quality,_novelty_and_reproducibility: This paper is clear. However, the novelty of this paper may be limited given Jeon &Van Roy (2022).
summary_of_the_review: This paper empirically studies fitting single-hidden-layer neural networks where data is also generated by single-hidden-layer ReLU teacher networks. Since there are only some simple experiments for two-layer NN on the synthetic data, this paper would better be viewed as an extended appendix of Jeon &Van Roy (2022). I highly recommend the authors add some theoretical results, even for some special cases.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper empirically demonstrates that SGD learns single-hidden-layer neural networks with near-optimal sample complexity efficiently which matches the theoretical bound of an optimal learner in JV22, while according to theoretically lower bounds achieving the optimal sample complexity is intractable in the worst case. 
strength_and_weaknesses: Strength:
The experimental results are solid with adequate details.

Weaknesses:
1, the title is somewhat ambiguous and over-selling. The scope of experiements is focused on learning single-hidden-layer neural networks, I suggest changing the title to be more specific, for example "SGD learns single-hidden-layer neural networks efficiently".
2, the main result of this paper is empirically showing that SGD learns single-hidden-layer neural networks efficiently. However, this is not surprising because SGD is known to generalize well on large-scale neural networks. Re-showing this phenomenon empirically on toy models doesn't feel interesting to me. It would be interersting to prove it theoretically though.

Question:
Can you give more details on how you generate the parameters of teacher networks? If all the weights are iid Gaussian, is the resulting teacher network still "random"? In particular, in the single-hidden-layer setting, there are works on the infinite width limit of such random neural networks. I'm concerned that the empirical results only applies to the class of fucntions "favored" by random neural networks, which might be very different from practical fucntions we care about.
clarity,_quality,_novelty_and_reproducibility: The paper is well-written and easy to follow. However I believe the title can be improved.

summary_of_the_review: The empirically results are solid but not significant enough in my opinion, thus I lean to rejection.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper experimentally investigate the statistical/computational efficiency of training neural network by stochastic gradient descent and compare the results by the information theoretic sample complexity lower bound obtained by existing theoretical study (Jeon & Van Roy (2022)).

It is indeed important to investigate the practical efficiency of neural network and validity of some theoretical justification. On the other hand, the main concern raised by the reviewers is that this paper gives no new theoretical work and it is basically rechecking the known results on a toy model. In that sense, this paper lacks its novelty. It is expected that the paper would contain more novel insights so that it could be accepted. Another concern pointed out some reviewers is that the title is overselling because the paper only investigates a very specific two layer neural network. This concern also indicates that the scope of the numerical investigation in this paper is so narrow that it does not give a general insight to the community.
justification_for_why_not_higher_score: As I have written in "Summary, Strengths And Weaknesses", this paper lacks its novelty. It requires more novel investigation so that this paper would be accepted. The writing is also not satisfactory. The organization of the paper and quality of its presentation can be much improved.
Decision: Reject