- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper improves upon on a line of work of learning shallow ReLU networks in a dimension-independent way of Gaussian data. The authors describe an algorithm, and prove that it able to learn a neuron shallow ReLU network on standard Gaussian data in dimension within average error . This algorithm is polynomial in and , although its dependence on is left undescribed.
Critical strengths
The technical results of the paper are interesting and novel. The statement of the main result is easy to understand, and enough information is included in the paper to verify that the proof is correct.
Critical weaknesses
Overall, I found the proof difficult to follow in many places. Specifically, the following issues are present:
- The writing is significantly more terse than it needs to be. Including more details would help the reader.
- The argument is not clearly structured in a way that is easy to follow; many of the intermediary results are not clearly motivated. The proof sketches help with this, but they go into too much technical detail and are only understandable after reading the full proof. A significant and specific issue here is that the algorithm is not described in any form until Section 6.
Questions for authors
I have no questions for the authors.
2 comments
Thank you for your response. I am satisfied with the changes made.
Earlier algorithm, motivated proof steps, and explicit stopping guarantees
Thank you for the review and the concrete suggestions on presentation. Page references below are to the revision.
Weakness 1: The writing is too terse, and more proof detail would help.
We expanded Section 6 (pp. 9–10) around the implication needed for stopping: if the current projection still leaves substantial label variation unexplained, at least one test must succeed. Thus a failed search certifies that little variation remains, which is then converted into a proper network approximation. The full algorithm now appears on p. 3, before these lemmas.
The quantitative check is as follows. On the event of accurate moment estimates and successful power iterations, residual variance above v=ε/128 forces a population moment of norm >8λj. Estimation error below λj and power iteration produce an image of norm >7λj/2, above the acceptance threshold 2λj. Therefore stopping because every test fails certifies residual variance at most v.
The rank bound is geometric: a learned subspace of larger dimension than the target subspace contains a unit vector orthogonal to the target subspace, forcing subspace error to equal one. This contradicts the established bound below one. The proof also handles termination at the dimension cap. Rotation and the parameter net supply a candidate of squared error at most ε/16; independent validation returns squared error below ε/2. The proof sets δ′=δ/[3(k+1)], giving total failure bound (2k+1)δ′<δ.
Section 5.1 (p. 9) also expands the rotation intuition: conditional on a shared Gaussian component, the two outputs are independent with the same distribution, so their expected squared difference is twice the conditional variance.
Weakness 2: The intermediate results lack motivation, the overview is too technical, and the algorithm appears too late.
We moved the full pseudocode from Section 6 (submission, p. 9) to Section 1.2 (revision, p. 3). It now follows the conceptual overview and parameter-choice explanation on p. 2. The algorithm has three stages:
Sections 3-5 (pp. 5-9) explain these stages beside the lemmas. Table 1 now stays within Related Work (p. 3), preserving the overview's reading order; Table 2 (p. 10) collects parameter choices. Theorem 1 also bounds g(k)≤2Cwk3 for an absolute constant Cw (Appendix E, p. 19).