- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
The paper studies agnostic regression by a single ReLU under standard Gaussian coariates. It gives an SQ algorithm that returns a ReLU satisfying the same weight-norm constraint as the comparator and achieves risk at most . Assuming , its query count, inverse tolerance, and arithmetic cost are polynomial in , , , and for fixed . It further shows the bounded second moment assumption can be removed by a logarithmic increase in the queries.
The algorithm first constructs polynomially many subspaces of dimension at most two. For at least one, the expected squared norm of the optimal ReLU's gradient outside the subspace is . For each candidate subspace, it fits the labels using small cells in those coordinates and low-degree Hermite polynomials in the orthogonal coordinates. The gradient bound controls the error from truncating the Hermite expansion. From the fitted function, it selects additional directions using a derivative matrix. The proof shows that the space obtained from a useful candidate contains a nearly optimal ReLU satisfying the original norm constraint. The algorithm searches a parameter grid in each resulting space and compares the candidate losses.
Critical strengths
The main result is interesting. Under Gaussian inputs, the paper improves the approximation guarantee for agnostic learning of an arbitrarily biased ReLU from a constant factor to , while returning a single ReLU under the same weight-norm constraint. For fixed , the dimension exponent is independent of the additive accuracy . Achieving these guarantees together is a substantive improvement over the prior results.
Critical weaknesses
This paper appears to be AI-written with little human filtering. This not only hurts the flow and aesthetics, but also is misleading and confusing at times. For example:
- The sentence "The first theorem uses a known second-moment bound", sounds like it is describing how second moment method is used in its analysis. Instead, what the authors meant is "the first theorem assumes a known bound on second moment of ". The word choice of "use" is misleading.
- This paper uses for , while the latter is standard in the literature and less prone to be confused with, say, the number of samples. Also, who would name variables like and ?
- The technical overview reads GPT-like, in the sense that it only makes sense as a dense summary for those who already understood the approach. More on that below.
Overall, the presentation makes the paper substantially harder to understand than it needs to be, and the technical overview section therefore fails to serve its purpose. I am familiar with the prior work, yet the two paragraphs in Section 1.2 give me no useful intuition for the proof. It introduces heavy and non-standard terms like a histogram in , a weighted derivative matrix, positive-label weights, deterministic ellipsoid grid, transverse Hermite expansion, none of which is explained or defined even informally here. These words mean nothing to me and supply zero bits of information. For a first-time reader to understand, the authors should at least explain what the relevant quantities are, e.g. what is the statistic and threshold that allowed us to pin down the list , and what is the derivative matrix weighted by at degree ?
Moreover, these techniques should be motivated (why this method), and put into context of prior work (why prior methods fail). For example, why is it useful to find a plane that controls transverse derivative energy, and why does that make a Hermite expansion in the remaining coordinates effective? How does this compare with other works with similar "estimate list of direction and then brute force" recipe, such as the homogeneous PTAS by Diakonikolas et al.? As written, by reading the two paragraphs, a reader can understand neither the actual method nor the reason for doing so.
These omissions force the reader to reconstruct from the detailed proofs how the stages of the algorithm fit together and why each is needed. Even as a reader familiar with the prior work, I find it difficult to identify the key technical insight and understand how it overcomes the limitations of earlier methods. Providing this explanation is part of the authors’ responsibility, and leaving that work to the reader creates an unreasonable barrier to understanding and evaluating the contribution. This is unacceptable at a top-level conference. In our era of proof abundance, it is of paramount importance that the results and techniques are communicated in a form that improves our understanding, instead of just being correct.
Questions for authors
Could the authors give an intuitive explanation of the dimension-reduction argument in Section 1.2? In particular, why does controlling the gradient energy outside make a low-degree Hermite expansion useful, and how do the spectral step and reflection establish that the retained subspace contains a nearly optimal ReLU?
3 comments
Why the approximation, spectral step, and reflection give relative error
Your dimension-reduction question reduces to three checks: gradient energy bounds the omitted Hermite tail; the normalization bounds residual spectral mass; preserving the weight norm cancels the squared-prediction terms in the loss difference. Points 6–8 give these calculations in that order.
6. Why does controlling gradient energy outside L make low-degree Hermite approximation useful?
Let be the optimal ReLU. The gradient energy measures variation after the coordinates in are fixed. Unless zero already suffices, initialization supplies a listed , of dimension at most two, with . The total gradient energy need not satisfy this relative bound.
Fix and expand in the independent Gaussian coordinates . A degree- Hermite component contributes times its squared norm to . Therefore , where retains degrees through in .
Choosing gives squared error . Its square root pairs with the label residual of norm in the loss calculation, contributing only . Fine cells in add squared error at polynomial cost.
This is why we control the remaining variation before polynomial regression. The identity is Eq. (6), p. 4 (also submitted Eq. (6), p. 4); Section 1.2, step 2, and Appendix C.1 explain its use.
7. What does the weight do, and why keep the top eigenvectors?
The weight cancels the degree factor introduced by differentiation. Let average over cells in and retain degrees through in . Write and .
Linearity gives , with and by contraction. The gradients of share one direction in ; perpendicular to it, only contributes. The normalized derivative energy is bounded by . Hence , for eigenvalues in decreasing order, and .
Every unit direction perpendicular to the first eigenvectors has quadratic form at most . Retaining one additional eigenvector lets us preserve the weight norm in point 8. With coefficient error , the numerator becomes .
Section 4, Eqs. (16)-(17), p. 7, and Appendix C.2 give the calculation.
8. How does reflection put a nearly optimal ReLU in the retained subspace?
Simply projecting the optimal weight can change its norm and hence the squared-prediction term in the risk. Reflection avoids this: the replacement has the same norm and bias, so its Gaussian output distribution is unchanged. After that cancellation, approximation error pairs with , whose norm is , giving relative loss control.
If all directions are retained, take . Otherwise, keep the optimal weight components in and the first eigenvectors, place the remaining length along the th, and keep the bias. This preserves the norm and Gaussian output distribution, so the loss increase is , where .
Set , , and . The reflection fixes and the first directions and commutes with . It gives , , and , where is the last retained eigenvalue and .
Eq. (19) gives . Its four terms are bounded by , , , and .
Substituting , , , and makes their sum at most . Section 5.2 closes Algorithm 1's rounding and risk comparison; Table 2 gives its resource bounds. Appendix C.2 (pp. 18-19) gives the full proof.
Response to response
Thank you for the revision. I want to acknowledge that the new technical overview and expanded explanations do make the paper easier to follow. However, this does not change my overall assessment, and I maintain my score of 1 (Clear Rejection). This is for several reasons (bolded).
A main problem with such a revision is that the submitted manuscript was not even review-ready. Communicating why the argument works, why its constructions are needed, how it differs from prior techniques, and what conceptual insight the community should take away is an (increasingly) big part of the scientific contribution. The original submission completely failed to do this. I do not think we should encourage submitting AI slop, only to be revised later. The submitted version placed a substantial part of the burden of distilling ideas and understanding the motivations on the reviewers, who then effectively supplied the feedback needed to turn the manuscript into a much more intelligible paper.
The revision substantially confirms the scale of this problem. Section 1.2 has been rewritten, Sections 3 and 4 have been considerably expanded, Section 5.2 now closes and explains parts of the main argument and resource accounting, notation has been globally changed, and a new halfspace PTAS has been added in Appendix F. This is a major reconstruction of the manuscript. I do not think it is reasonable to ask reviewers, to re-evaluate essentially from scratch a paper whose exposition and proof digestion have been rebuilt in response to the reviews.
Moreover, even in the revised version, I still find the exposition largely unsatisfactory compared to papers written by human experts. I would point to the refered prior works (e.g., [Diakonikolas et al., 2020a] and [Guo & Vijayaraghavan 2025]) for examples of much clearer exposition --- the quality difference is striking. The least one should do is to discuss the motivations behind the techniques, whereas the revised draft still feels like listing algebraic steps without telling the reader why these are the natural steps to take.
I also encourage the authors to use their own words and distill the ideas on their own. Currently, the draft is still very clearly AI-written, which, again, makes it much harder to read (for humans) than necessary. For example, I'd at least expect some transition words and context in the following paragraph, which is at the very beginning of the technical overview:
Initialization bounds the remaining gradient energy by ; approximation, spectral selection, and reflection yield an loss increase. Degree and search dimension depend only on . Consider a nonconstant optimum , where is its weight norm, is a unit vector, and is its activation threshold. Write , where is the standard Gaussian upper tail.
Right now, it reads like a telegram message instead of an academic paper, written when it was still very costly to send each letter through the machine.
The underlying result may well deserve publication after the argument has been properly digested, written, and independently vetted by the authors. But that should happen through a fresh submission. For these reasons, I maintain my score of Clear Rejection.
Clarified wording, statistics, and relation to prior methods
Thank you for the detailed feedback.
The explanation needs to show why the stages are necessary. A line or plane isolates the variation requiring fine resolution; the remaining Hermite error is then measured relative to optimal risk. The 1/j weights prevent differentiation from amplifying label error. Reflection preserves the Gaussian output distribution so that searching the smaller space still permits a proper ReLU.
1. Meaning of "uses a known second-moment bound."
We agree that "assumes" states the intended meaning. The introductory sentence now reads: "The first theorem assumes a known bound on the second moment of Y" (Section 1.1, p. 2).
Theorem 1.1 assumes the supplied label bound EY2≤1. Rescaling handles a supplied larger bound. Theorem D.1 in Appendix D requires only a finite second moment, without a supplied bound.
2. Notation for the optimum and intermediate accuracy.
We have removed N,n,e. The optimum is consistently OPTW. Detailed ReLU proofs use internal accuracy ε0=ε/C0, with sufficiently large absolute C0, and write OPTW+ε0 explicitly. The overview writes ε to suppress constant-factor accuracy rescaling.
This keeps the comparator, relative error η, requested additive accuracy ε, and internal error budget ε0 distinct.
3. Meaning of "histogram in L" and "transverse Hermite expansion."
Let Z=PLX and G=PL⊥X be independent Gaussian coordinates. We partition each coordinate in L into short intervals. Within each product cell, the fit is a polynomial in G of degree at most k; each polynomial coefficient is constant across that cell. The learner fits labels in this space; the optimal ReLU f\* is used only in the approximation analysis.
Thus "histogram in L" means the cellwise constant dependence on Z, and "transverse" means the coordinates G perpendicular to L. Cell width controls the approximation in L; Hermite degree controls the remaining coordinates.
Because dimL≤2, refining the cells adds a polynomial factor. This allows fine additive accuracy in L while keeping the degree outside L dependent only on relative error. Section 1.2, step 2 (pp. 2-3), now explains these operations; Section 5.1 (p. 8) specifies the partition. Point 6 explains the error bound.
4. What statistics and thresholds produce the direction list? What is the ellipsoid grid?
Write the optimum as f\*=a(vTX−t)+, where a is the weight norm and ∣v∣=1. For t≥1, first moments can be overwhelmed by residual error. Enumerate positive thresholds including one with a/(64t)≤τy≤a/(32t). Estimate s=EYτy and Q=E[YτyXXT], where Yτy=Y1Y≥τy.
Bias optimality supplies a lower bound α on the fraction of retained weight in the activation region. Its weighted input mean μ is close to tv, and Jensen gives μμT⪯Q/(αs). Thus μ lies in a computable ellipsoid. A Gaussian trace bound permits a polynomial-size grid in its large-eigenvalue subspace; the omitted mean component is bounded. Normalizing nonzero grid points gives coarse axes.
When a plane is needed, estimate E[YPu⊥X1uTX>T] for a listed axis u and threshold guess T. Replacing Y by f\* makes this vector parallel to Pu⊥v. The residual contributes at most OPTWpT in Euclidean norm, where pT=Pr(uTX>T). For the useful guesses, Pr(uTX>T,vTX>t)≍pT≍Pr(vTX>t). The resulting span has dimension at most two and outside gradient energy O(OPTW+ε0).
Sections 3.1-3.2 (pp. 5-6), Eq. (12), and Appendix B give the bounds and grids.
5. How does this compare with prior methods, including the homogeneous ReLU PTAS?
The homogeneous PTAS of Diakonikolas et al. (2020), Theorem 19, uses a convex surrogate to obtain a coarse direction. Its final predictor fits a polynomial near the activation boundary and uses linear or zero predictions elsewhere. Our polynomial fit identifies search directions; the final search returns a single ReLU obeying the original weight bound.
Diakonikolas et al. (2021), Theorem 27, can output an affine ReLU but compare against homogeneous ReLUs, with degree and search dimension depending on additive accuracy. We retain their regression-and-subspace framework and prove relative bounds: initialization controls the approximation error by the optimal loss plus additive error, while degree normalization and reflection control proper replacement. Consequently, degree and search dimension are independent of additive accuracy for fixed η.
Section 1.3 (pp. 3-4), Table 1, and General G2 (Part 2) give the comparison. Points 6-8 below explain how these bounds connect.