acceptodds
Under review as a conference paper at ICLR 2027

A Proper SQ PTAS for Agnostic Learning of Arbitrarily Biased ReLUs

Abstract

Agnostic ReLU regression seeks to match the best single ReLU under arbitrary label noise. Under standard Gaussian inputs, we give a deterministic proper statistical query (SQ) polynomial-time approximation scheme (PTAS) for this problem with arbitrary bias. For every fixed , the learner returns a ReLU with weight norm at most and squared loss at most , where is the minimum loss over the same class. This sharpens prior constant-factor guarantees to a factor arbitrarily close to one while preserving the model class and norm constraint. To obtain this guarantee, we reduce the search to dimensions while preserving the comparator's Gaussian output distribution and controlling its label correlation. For fixed and a known label second-moment bound, the query count, inverse tolerance, and arithmetic cost are polynomial in the dimension, , the moment bound, and . Moreover, the same guarantee extends to unknown finite label second moments without polynomial dependence on label scale: only logarithmically many additional queries are needed to locate the label mean.

Primary area:
learning theory
Keywords:
Agnostic learning, ReLU regression, proper learning, statistical query learning, polynomial-time approximation schemes.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_BMWFOpenReview ↗
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 (1+η)OPT⁡W+ϵ(1+\eta)\operatorname{OPT}_W+\epsilon. Assuming EY2≤B\mathbb{E}Y^2\le B, its query count, inverse tolerance, and arithmetic cost are polynomial in dd, WW, BB, and 1/ϵ1/\epsilon for fixed η\eta. 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 O(OPT⁡W+ϵ)O(\operatorname{OPT}_W+\epsilon). 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 O(η−2)O(\eta^{-2}) 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 1+η1+\eta, while returning a single ReLU under the same weight-norm constraint. For fixed η\eta, the dimension exponent is independent of the additive accuracy ϵ\epsilon. 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 YY". The word choice of "use" is misleading.
  • This paper uses NN for OPTW\mathrm{OPT}_W, 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 e=ϵ/C0e = \epsilon/C_0 and n=N+en = N + e?
  • 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 LL, 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 LL, and what is the derivative matrix weighted by 1/j1/j at degree jj?

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 LL 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
AuthorsOpenReview ↗

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/j1/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 YY" (Section 1.1, p. 2).

Theorem 1.1 assumes the supplied label bound EY2≤1\mathbb E Y^2\le1. 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,eN,n,e. The optimum is consistently OPTW\mathrm{OPT}_W. Detailed ReLU proofs use internal accuracy ε0=ε/C0\varepsilon_0=\varepsilon/C_0, with sufficiently large absolute C0C_0, and write OPTW+ε0\mathrm{OPT}_W+\varepsilon_0 explicitly. The overview writes ε\varepsilon to suppress constant-factor accuracy rescaling.

This keeps the comparator, relative error η\eta, requested additive accuracy ε\varepsilon, and internal error budget ε0\varepsilon_0 distinct.

3. Meaning of "histogram in L" and "transverse Hermite expansion."

Let Z=PLXZ=P_LX and G=PL⊥XG=P_{L^\perp}X be independent Gaussian coordinates. We partition each coordinate in LL into short intervals. Within each product cell, the fit is a polynomial in GG of degree at most kk; each polynomial coefficient is constant across that cell. The learner fits labels in this space; the optimal ReLU f\*f_\* is used only in the approximation analysis.

Thus "histogram in LL" means the cellwise constant dependence on ZZ, and "transverse" means the coordinates GG perpendicular to LL. Cell width controls the approximation in LL; Hermite degree controls the remaining coordinates.

Because dim⁡L≤2\dim L\le2, refining the cells adds a polynomial factor. This allows fine additive accuracy in LL while keeping the degree outside LL 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)+f_\*=a(v^TX-t)_+, where aa is the weight norm and ∣v∣=1\\|v\\|=1. For t≥1t\ge1, first moments can be overwhelmed by residual error. Enumerate positive thresholds including one with a/(64t)≤τy≤a/(32t)a/(64t)\le\tau_y\le a/(32t). Estimate s=EYτys=\mathbb E Y_{\tau_y} and Q=E[YτyXXT]Q=\mathbb E[Y_{\tau_y}XX^T], where Yτy=Y1Y≥τyY_{\tau_y}=Y\mathbf1_{Y\ge\tau_y}.

Bias optimality supplies a lower bound α\alpha on the fraction of retained weight in the activation region. Its weighted input mean μ\mu is close to tvtv, and Jensen gives μμT⪯Q/(αs)\mu\mu^T\preceq Q/(\alpha s). Thus μ\mu 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]\mathbb E[YP_{u^\perp}X\mathbf1_{u^TX > T}] for a listed axis uu and threshold guess TT. Replacing YY by f\*f_\* makes this vector parallel to Pu⊥vP_{u^\perp}v. The residual contributes at most OPTWpT\sqrt{\mathrm{OPT}_W p_T} in Euclidean norm, where pT=Pr⁡(uTX>T)p_T=\Pr(u^TX > T). For the useful guesses, Pr⁡(uTX>T,vTX>t)≍pT≍Pr⁡(vTX>t)\Pr(u^TX > T,v^TX > t)\asymp p_T\asymp\Pr(v^TX > t). The resulting span has dimension at most two and outside gradient energy O(OPTW+ε0)O(\mathrm{OPT}_W+\varepsilon_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 η\eta.

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.

AuthorsOpenReview ↗

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 1/j1/j 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 f\*f_\* be the optimal ReLU. The gradient energy measures variation after the coordinates in LL are fixed. Unless zero already suffices, initialization supplies a listed LL, of dimension at most two, with JL:=E∣∇L⊥f\*∣2=O(OPTW+ε0)J_L:=\mathbb E\\|\nabla_{L^\perp}f_\*\\|^2=O(\mathrm{OPT}_W+\varepsilon_0). The total gradient energy need not satisfy this relative bound.

Fix Z=PLXZ=P_LX and expand in the independent Gaussian coordinates G=PL⊥XG=P_{L^\perp}X. A degree-jj Hermite component contributes jj times its squared norm to JLJ_L. Therefore ∣f\*−Π≤kGf\*∣22≤JL/(k+1)\\|f_\*-\Pi_{\le k}^{G}f_\*\\|_2^2\le J_L/(k+1), where Π≤kG\Pi_{\le k}^{G} retains degrees through kk in GG.

Choosing k=O(η−2)k=O(\eta^{-2}) gives squared error O(η2(OPTW+ε0))O(\eta^2(\mathrm{OPT}_W+\varepsilon_0)). Its square root pairs with the label residual of norm OPTW\sqrt{\mathrm{OPT}_W} in the loss calculation, contributing only O(η)(OPTW+ε0)O(\eta)(\mathrm{OPT}_W+\varepsilon_0). Fine cells in LL add O(η2ε0)O(\eta^2\varepsilon_0) 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 1/j1/j weight do, and why keep the top eigenvectors?

The weight cancels the degree factor introduced by differentiation. Let Π\Pi average over cells in LL and retain degrees through kk in G=PL⊥XG=P_{L^\perp}X. Write g=ΠY=∑j=0kgjg=\Pi Y=\sum_{j=0}^k g_j and Mg=∑j=1kj−1E[∇Ggj∇GgjT]M_g=\sum_{j=1}^k j^{-1}\mathbb E[\nabla_Gg_j\nabla_Gg_j^T].

Linearity gives g=Πf\*+ζg=\Pi f_\*+\zeta, with ζ=Π(Y−f\*)\zeta=\Pi(Y-f_\*) and ∣ζ∣2≤OPTW\\|\zeta\\|_2\le\sqrt{\mathrm{OPT}_W} by contraction. The gradients of Πf\*\Pi f_\* share one direction in GG; perpendicular to it, only ζ\zeta contributes. The normalized derivative energy is bounded by ∑j=1kj−1E∣∇Gζj∣2≤∣ζ∣22≤OPTW\sum_{j=1}^k j^{-1}\mathbb E\\|\nabla_G\zeta_j\\|^2\le\\|\zeta\\|_2^2\le\mathrm{OPT}_W. Hence ∑i≥2λi(Mg)≤OPTW\sum_{i\ge2}\lambda_i(M_g)\le\mathrm{OPT}_W, for eigenvalues in decreasing order, and λm(Mg)≤OPTW/(m−1)\lambda_m(M_g)\le\mathrm{OPT}_W/(m-1).

Every unit direction perpendicular to the first m−1m-1 eigenvectors has quadratic form at most λm\lambda_m. Retaining one additional eigenvector lets us preserve the weight norm in point 8. With coefficient error δ\delta, the numerator becomes (OPTW+δ)2(\sqrt{\mathrm{OPT}_W}+\delta)^2.

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 Y−f\*Y-f_\*, whose norm is OPTW\sqrt{\mathrm{OPT}_W}, giving relative loss control.

If all directions are retained, take f′=f\*f'=f_\*. Otherwise, keep the optimal weight components in LL and the first m−1m-1 eigenvectors, place the remaining length along the mmth, and keep the bias. This preserves the norm and Gaussian output distribution, so the loss increase is −2E[Yh]-2\mathbb E[Yh], where h=f′−f\*h=f'-f_\*.

Set g=ΠYg=\Pi Y, h⊥=(I−Π)hh_\perp=(I-\Pi)h, and ∣g^−g∣2≤δ\\|\widehat g-g\\|_2\le\delta. The reflection fixes LL and the first m−1m-1 directions and commutes with Π\Pi. It gives ∣E[g^h]∣≤2λJL|\mathbb E[\widehat gh]|\le2\sqrt{\lambda J_L}, ∣h∣2≤2JL\\|h\\|_2\le2\sqrt{J_L}, and ∣h⊥∣2≤2θOPTW+ε0\\|h_\perp\\|_2\le2\theta\sqrt{\mathrm{OPT}_W+\varepsilon_0}, where λ\lambda is the last retained eigenvalue and θ=cη\theta=c\eta.

Eq. (19) gives R(f′)−OPTW=−2E[g^h]−2E[(g−g^)h]−2E[(Y−f\*)h⊥]+∣h⊥∣22R(f')-\mathrm{OPT}_W=-2\mathbb E[\widehat gh]-2\mathbb E[(g-\widehat g)h]-2\mathbb E[(Y-f_\*)h_\perp]+\\|h_\perp\\|_2^2. Its four terms are bounded by 4λJL4\sqrt{\lambda J_L}, 4δJL4\delta\sqrt{J_L}, 4θOPTW(OPTW+ε0)4\theta\sqrt{\mathrm{OPT}_W(\mathrm{OPT}_W+\varepsilon_0)}, and 4θ2(OPTW+ε0)4\theta^2(\mathrm{OPT}_W+\varepsilon_0).

Substituting JL=O(OPTW+ε0)J_L=O(\mathrm{OPT}_W+\varepsilon_0), λ≤(OPTW+δ)2/(m−1)\lambda\le(\sqrt{\mathrm{OPT}_W}+\delta)^2/(m-1), δ2=cη2ε0\delta^2=c\eta^2\varepsilon_0, and k=m=⌈C/η2⌉k=m=\lceil C/\eta^2\rceil makes their sum at most (η/8)(OPTW+ε0)(\eta/8)(\mathrm{OPT}_W+\varepsilon_0). 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.

Reviewer_BMWFOpenReview ↗

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 O(OPTW+ϵ)O(OPT_W + \epsilon); approximation, spectral selection, and reflection yield an O(η)(OPTW+ϵ)O(\eta)(OPT_W + \epsilon) loss increase. Degree and search dimension depend only on η\eta. Consider a nonconstant optimum f∗=a(vTX−t)+f_* = a(v^T X - t)_+, where a∈(0,W]a \in (0, W] is its weight norm, vv is a unit vector, and tt is its activation threshold. Write p=Φ‾(t)p = \overline{\Phi}(t), where Φ‾\overline{\Phi} 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.

Reviewer_usJ5OpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the task of agnostic proper learning ReLUs under data points generated from Gaussian marginals. Recently, Guo & Vijayaraghavan (2025) gave a proper constant-factor statistical query (SQ) algorithm for the problem getting error O(OPT) + eps in polynomial time. This paper extends this to arbitrary PTAS achieving (1+eta) OPT + eps in poly_eta( d, 1/eps) time. This is essentially best possible as FPTAS is shown to be computationally hard.

Critical strengths

Learning ReLUs is central problem in learning theory and Machine Learning. This work provides an important generalization of prior work and gives principled methods to train ReLU models - single neuron.

Critical weaknesses

None,

Questions for authors

Could you provide a concise comparison of the techniques with the prior work? This would make the contribution clearer beyond the results.

In particular, how does the paper extend the techniques of Guo & Vijayaraghavan (2025) on constant approximation? Also, the idea of the algorithm is similar to the work of Diakonikolas et al that provides a PTAS for proper agnostic learning for general halfspaces under Gaussian marginals. Identify a relevant subspace and then search in exponential time on that.

Finally, can the techniques be extended to a PTAS for proper agnostic learning for general halfspaces? This is left open by prior work.

1 comment
AuthorsOpenReview ↗

Comparison of techniques and the new halfspace extension

Thank you for the questions about prior techniques and for suggesting the halfspace extension.

1. How does the method extend Guo and Vijayaraghavan (2025)?

Their initialization thresholds ∣Y∣|Y| and uses second moments of the selected inputs. We retain positive-label magnitudes through Yτy=Y1Y≥τyY_{\tau_y}=Y\mathbf1_{Y\ge\tau_y} and estimate EYτy\mathbb E Y_{\tau_y} and E[YτyXXT]\mathbb E[Y_{\tau_y}XX^T]. Bias optimality lower-bounds the retained weight in the optimum's activation region. An ellipsoid covering then gives a direction list even when that fraction is small.

The refinement analysis in their Assumption 6 and Theorem 7 assumes zero fails a sufficiently large constant-factor guarantee. A PTAS must also handle cases where zero meets that guarantee. For example, ignoring a small additive error, zero's risk 2OPTW2\mathrm{OPT}_W meets a large constant-factor bound but misses the 1.1OPTW1.1\mathrm{OPT}_W target for η=0.1\eta=0.1.

We handle these cases through the coarse list, supplemented by a first moment or a conditional correlation producing a plane. The resulting gradient bound supports relative approximation and proper replacement (Sections 3-4, pp. 4-8).

Both algorithms use general SQ access and nonlinear label dependence. Their CSQ lower bound concerns queries restricted to label correlations.

2. How does this differ from the halfspace method that finds and searches a subspace?

We build on the polynomial-regression, derivative-matrix, and subspace-search framework of Diakonikolas et al. (2021). Their Theorem 2 handles arbitrary thresholds with additive error and an accuracy-dependent dimension exponent; their Theorem 3 gives a PTAS against homogeneous halfspaces.

Here f\*f_\* is the optimal ReLU and ε0=ε/C0\varepsilon_0=\varepsilon/C_0 is internal accuracy, with sufficiently large C0C_0. Our additional estimates make the approximation and replacement errors proportional to OPTW+ε0\mathrm{OPT}_W+\varepsilon_0. Initialization bounds the gradient energy outside at most two directions by this quantity. The resulting Hermite tail needs degree O(η−2)O(\eta^{-2}), independently of additive accuracy.

Let Π\Pi be the cellwise polynomial projection. The label fit decomposes as ΠY=Πf\*+Π(Y−f\*)\Pi Y=\Pi f_\*+\Pi(Y-f_\*); projection contracts the residual norm. The 1/j1/j weights bound the spectrum outside the projected optimum's one gradient direction by residual risk. Reflection preserves the weight norm and Gaussian output distribution; remaining approximation terms pair with Y−f\*Y-f_\* of norm OPTW\sqrt{\mathrm{OPT}_W}. This gives m=O(η−2)m=O(\eta^{-2}) and relative loss control.

Revised Section 1.3 (pp. 3-4) explains this comparison; Section 4 (pp. 6-8) gives the spectral and reflection calculations.

3. Can the method give a proper PTAS for general halfspaces?

Yes. We added Theorem F.1 (p. 28): for standard Gaussian inputs and binary labels, a deterministic algorithm returns one affine halfspace with err⁡(h^)≤(1+η)OPTHS+ε\operatorname{err}(\widehat h)\le(1+\eta)\mathrm{OPT}_{\mathrm{HS}}+\varepsilon. The comparator permits arbitrary thresholds, including constants. Query count, inverse tolerance, and arithmetic cost are each poly⁡η(d,1/ε)\operatorname{poly}_\eta(d,1/\varepsilon).

A halfspace has no square-integrable weak derivative, so the extension needs a different approximation argument. Define SL=ϕ(t)∣PL⊥v∣S_L=\phi(t)\\|P_{L^\perp}v\\|, where v,tv,t are the optimal unit normal and threshold and ϕ\phi is the Gaussian density. Set internal accuracy ε0=cη2ε\varepsilon_0=c\eta^2\varepsilon. Unless a constant suffices, positive-label moments and Gaussian-band updates produce a candidate axis with SL=O(OPTHS+ε0)S_L=O(\mathrm{OPT}_{\mathrm{HS}}+\varepsilon_0). A dyadic budget satisfies OPTHS≤r≤2(OPTHS+ε0)\mathrm{OPT}_{\mathrm{HS}}\le r\le2(\mathrm{OPT}_{\mathrm{HS}}+\varepsilon_0); on this branch, each accepted update increases alignment for every valid SQ answer.

Gaussian noise sensitivity gives squared tail O(SL/k+1)O(S_L/\sqrt{k+1}) and truncated energy O(SLk+1)O(S_L\sqrt{k+1}). On the useful budget branch, Eq. (58) gives leading excess error proportional to OPTHS+ε0\mathrm{OPT}_{\mathrm{HS}}+\varepsilon_0 times O((k+1)1/4/m−1+(k+1)−1/4)O((k+1)^{1/4}/\sqrt{m-1}+(k+1)^{-1/4}). Taking k=m=⌈Cη−4⌉k=m=\lceil C\eta^{-4}\rceil makes the factor O(η)O(\eta), independently of additive accuracy. Only the finite projection is differentiated.

Appendix F (pp. 28-33) proves these estimates and the finite implementation; Algorithm 3 is on p. 32.

Reviewer_ciPuOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper gives a PTAS for proper nonhomogeneous (agnostic) learning of a single ReLU. Prior work on the nonhomogeneous case give a constant factor approximation. The paper seems LLM generated. The technical overview is severely lacking.

Critical strengths

It improves the known constant factor approximation for agnostic nonhomogeneous ReLU activation.

Critical weaknesses

The writing is clearly LLM generated. I am not confident it is correct.

Questions for authors

Please give a much more legible technical overview.

1 comment
AuthorsOpenReview ↗

Why initialization and reflection give a proper PTAS

We agree that the submitted overview was too compressed to explain the proof. The obstacle is relative error: when the optimal loss is small, a fixed absolute polynomial-approximation error can overwhelm the desired (1+η)OPTW+ε(1+\eta)\mathrm{OPT}_W+\varepsilon guarantee. The revised Section 1.2 explains how each stage avoids this loss.

1. Isolate the coordinates needing fine resolution. Label-weighted moments and correlations produce a polynomial-size list of lines and planes. Unless zero or a constant already suffices, one listed space LL leaves gradient energy JL=O(OPTW+ε0)J_L=O(\mathrm{OPT}_W+\varepsilon_0) outside it, where ε0=ε/C0\varepsilon_0=\varepsilon/C_0 is internal accuracy. We can resolve the at most two coordinates in LL finely at polynomial cost.

2. Approximate the remaining variation. For Gaussian inputs, Hermite degree jj contributes jj times its squared coefficient norm to gradient energy. Therefore the squared tail above degree kk is at most JL/(k+1)J_L/(k+1). Taking k=O(η−2)k=O(\eta^{-2}) makes the approximation error relative to the optimal loss, independently of additive accuracy.

3. Keep a small search space despite arbitrary label error. We fit labels, not the unknown optimum. The fit is the projected optimal ReLU plus the projected label residual, whose norm is at most OPTW\sqrt{\mathrm{OPT}_W}. Weighting each degree's derivative matrix by 1/j1/j cancels the differentiation factor. Outside the optimum's one remaining gradient direction, the total spectral mass is bounded by residual risk. Keeping m=O(η−2)m=O(\eta^{-2}) directions controls what is discarded.

4. Return one ReLU with the original weight bound. A reflection moves the optimal weight into the retained space while preserving its norm and bias. Under Gaussian inputs, this preserves its output distribution, so the squared-prediction terms cancel in the loss difference. The remaining correlation terms are controlled by Steps 2–3. Reflection proves existence; a finite feasible grid and risk comparison select the output.

The checkable calculation is Lemma 4.1 and Eq. (19), p. 7: approximation errors pair with Y−f\*Y-f_\*, of norm OPTW\sqrt{\mathrm{OPT}_W}, rather than with the full label norm. With k=m=⌈C/η2⌉k=m=\lceil C/\eta^2\rceil and coefficient error δ2=cη2ε0\delta^2=c\eta^2\varepsilon_0, the replacement loss is at most (η/8)(OPTW+ε0)(\eta/8)(\mathrm{OPT}_W+\varepsilon_0). Section 5.2 closes rounding and candidate selection; Table 2 lists the resource bounds; Appendix C.2 gives the full reflection proof.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response 1/2: main guarantee and proof route

We thank the reviewers. Our main result is a deterministic proper SQ PTAS for a single ReLU with arbitrary bias under standard Gaussian inputs. It returns one ReLU satisfying R(f^)≤(1+η)OPTW+ε,∣w^∣≤W,R(\widehat f)\le(1+\eta)\mathrm{OPT}_W+\varepsilon,\qquad \\|\widehat w\\|\le W, where RR is squared loss and OPTW\mathrm{OPT}_W uses the same weight bound. With a supplied bound EY2≤1\mathbb E Y^2\le1, query count, inverse tolerance, and arithmetic cost are each poly⁡η(d,W,1/ε)\operatorname{poly}_\eta(d,W,1/\varepsilon).

The ReLU guarantee was already in the submission. The revision makes its proof and resource accounting explicit; it also adds the arbitrary-threshold halfspace PTAS described in Part 2. The main text now closes Theorem 1.1 in Section 5.2 (pp. 9–10), with resource budgets in Table 2 (p. 9). All locations below refer to the revision.

G1. Why the four stages give relative error and a proper output.

A fixed absolute approximation error can overwhelm the desired bound when OPTW\mathrm{OPT}_W is small. The proof instead controls errors relative to OPTW+ε0\mathrm{OPT}_W+\varepsilon_0, where ε0=ε/C0\varepsilon_0=\varepsilon/C_0 is internal accuracy. Let f\*f_\* be an optimal ReLU.

1. Isolate the variation requiring fine resolution. Unless zero or a constant suffices, initialization lists lines and planes, one of which has remaining gradient energy JL:=E∣∇L⊥f\*∣2=O(OPTW+ε0).J_L:=\mathbb E\\|\nabla_{L^\perp}f_\*\\|^2=O(\mathrm{OPT}_W+\varepsilon_0). Rare activation can hide the signal in ordinary first moments. Positive-label weighted moments supply coarse axes, and a conditional correlation supplies a second direction when needed. We allow large variation within LL and control what remains outside it. Section 3 explains the retained label weight, ellipsoid covering, and threshold choices.

2. Approximate the remaining variation. Fix the coordinates in LL and expand in the independent Gaussian coordinates G=PL⊥XG=P_{L^\perp}X. Degree jj contributes jj times its squared Hermite coefficient norm to gradient energy, so the squared tail above degree kk is at most JL/(k+1)J_L/(k+1). Taking k=O(η−2)k=O(\eta^{-2}) gives squared error O(η2(OPTW+ε0))O(\eta^2(\mathrm{OPT}_W+\varepsilon_0)). Fine cells within LL add a polynomial factor because dim⁡L≤2\dim L\le2. Write Π\Pi for this cell averaging and Hermite projection.

3. Control the effect of fitting labels. The fit is g=ΠY=Πf\*+Π(Y−f\*)g=\Pi Y=\Pi f_\*+\Pi(Y-f_\*), and the projected residual has norm at most OPTW\sqrt{\mathrm{OPT}_W}. Weighting each degree-jj derivative matrix by 1/j1/j cancels the differentiation factor. Perpendicular to the optimum's one remaining gradient direction, only the residual contributes. If at least mm directions are available, the mmth largest eigenvalue obeys λm≤OPTW/(m−1)\lambda_m\le\mathrm{OPT}_W/(m-1) with exact coefficients; otherwise all directions are retained. Total L2L^2 fitting error δ\delta changes the numerator to (OPTW+δ)2(\sqrt{\mathrm{OPT}_W}+\delta)^2.

4. Preserve a good single ReLU in the retained space. Reflection moves the optimal weight into LL plus the retained directions while preserving its norm and bias. Gaussian inputs then give the same output distribution, cancelling the squared-prediction terms in the loss difference. The approximation errors pair with Y−f\*Y-f_\*, of norm OPTW\sqrt{\mathrm{OPT}_W}, which gives relative loss control. A finite feasible grid and risk comparison select the proper output; reflection proves that a suitable candidate exists.

Lemma 4.1 and Eq. (19) (p. 7) give the checkable loss calculation. With k=m=⌈C/η2⌉k=m=\lceil C/\eta^2\rceil and δ2=cη2ε0\delta^2=c\eta^2\varepsilon_0, replacement increases risk by at most (η/8)(OPTW+ε0)(\eta/8)(\mathrm{OPT}_W+\varepsilon_0). Section 5.2 accounts for numerical error, rounding, zero/constant cases, and candidate selection. Appendix C.2 gives the reflection proof and Appendix C.5 the resource derivation.

Part 2 compares prior techniques (G2), records manuscript changes (G3), and states the added halfspace result (G4).

AuthorsOpenReview ↗

General response 2/2: comparisons, revisions, and halfspaces

Part 1 gives the reading guide and ReLU proof (G1). Below are comparisons (G2), changes (G3), and halfspaces (G4). Locations refer to the revision unless marked submitted.

G2. Relation to prior techniques (Section 1.3, pp. 3-4).

Polynomial regression, derivative matrices, and subspace search are established tools. The distinction is the relative approximation and replacement estimates:

  • Diakonikolas et al. (2020), Theorem 19 give an improper homogeneous-ReLU PTAS with a piecewise predictor. Our polynomial fit identifies directions for a search over single ReLUs.
  • Diakonikolas et al. (2021), Theorem 27 can output an affine ReLU but compare against homogeneous ReLUs; degree and search dimension depend on additive accuracy. Our initialization makes the Hermite error relative to OPTW+ε0\mathrm{OPT}_W+\varepsilon_0. Degree normalization and reflection then give k=m=O(η−2)k=m=O(\eta^{-2}), independently of additive accuracy.
  • Guo and Vijayaraghavan (2025) give a proper constant-factor guarantee for arbitrary bias. Their reweighted-gradient analysis assumes zero fails a sufficiently large constant-factor bound. A PTAS must also handle cases where zero already meets that bound. Positive-label weighted lists and an additional correlation cover the regimes needed for our relative guarantee.

The result combines arbitrary bias, factor 1+η1+\eta, and a single ReLU with the original weight bound. Appendix E.1 excludes an FPTAS under the subexponential learning-with-errors hardness assumption; the best dependence on η\eta remains open.

G3. Changes relative to the submitted paper.

The ReLU guarantees and asymptotic resources of submitted Theorems 1.1-1.2 are preserved (now Theorems 1.1 and D.1). The main text now closes Theorem 1.1.

The revision:

  • Rewrites Section 1.2 to motivate each stage and connect label fitting to the optimal residual.
  • Expands Section 3: bias optimality supplies positive retained weight, and one tail correlation cancels the rare-event factors in the remaining energy bound.
  • Compares techniques and comparator classes in Section 1.3; barriers are collected in Appendix E.
  • Uses OPTW\mathrm{OPT}_W, ε0\varepsilon_0, and explicit OPTW+ε0\mathrm{OPT}_W+\varepsilon_0 in detailed ReLU bounds; the overview suppresses constant-factor accuracy rescaling.
  • Expands Section 4's spectral and reflection derivation, including coefficient error. The reflection and loss identity already appeared in submitted Appendix D.2, Eqs. (41)-(44), p. 18. Reflection proves existence; finite search finds the candidate.
  • Closes the zero, constant, replacement, rounding and risk-comparison cases in Section 5.2. Table 2 gives subspace, feature, grid, query and tolerance bounds, with the roles of k,mk,m explicit; Appendix C.5 derives them.
  • Places the full unknown-moment statement and Algorithm 2 in Appendix D, and adds the halfspace result in Appendix F, below.

G4. Added result: arbitrary-threshold halfspaces.

Following the extension question, Theorem F.1 (p. 28) gives a deterministic proper PTAS for X∼N(0,Id)X\sim\mathcal N(0,I_d) and Y∈−1,1Y\in\\{-1,1\\}. It returns one affine halfspace with err⁡(h^)≤(1+η)OPTHS+ε\operatorname{err}(\widehat h)\le(1+\eta)\mathrm{OPT}_{\mathrm{HS}}+\varepsilon, comparing with all affine halfspaces, including constants. Query count, inverse tolerance, and arithmetic cost are each poly⁡η(d,1/ε)\operatorname{poly}_\eta(d,1/\varepsilon).

A halfspace has no square-integrable weak derivative, so the initialization controls the rotation quantity SL=ϕ(t)∣PL⊥v∣S_L=\phi(t)\\|P_{L^\perp}v\\| instead, for optimal unit normal vv, threshold tt, and standard Gaussian density ϕ\phi. Positive-label moments and Gaussian-band updates supply the useful axis; Gaussian noise sensitivity controls the Hermite tail. Degree-normalized spectral selection and reflection then give a proper replacement. Only the finite polynomial projection is differentiated.

Here degree and retained dimension are k=m=O(η−4)k=m=O(\eta^{-4}), independently of additive accuracy. Appendix F (pp. 28–33) proves initialization, finite precision, bounded queries, and candidate selection; Algorithm 3 is on p. 32. The extension supports the same proof strategy, while the main-text argument remains focused on the ReLU theorem.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.