acceptodds
Under review as a conference paper at ICLR 2027

Proper Learning of Signed Narrow ReLU Networks

27 views

Abstract

Cancellation among signed neurons complicates uniform learning guarantees for narrow ReLU networks. We address this challenge with a proper learner for normalized, bias-free networks under Gaussian inputs, without separation assumptions. Specifically, for width and squared error , it uses noiseless examples and real-arithmetic operations. Thus, at any fixed width, sample complexity is nearly linear in dimension and running time is nearly quadratic, while both are polynomial in inverse accuracy. To prove this, we combine first-moment control with a scaled nonlinear label-distance statistic to lower-bound a second-moment signal using residual variance. A norm-preserving rotation then ensures approximation by at most units in the original normalized class, yielding proper output.

Primary area:
learning theory
Keywords:
ReLU networks, proper learning, computational learning theory, subspace learning.

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 4.00 over 3 reviews, above 99% of the others.
Reviewer_ishYOpenReview ↗
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 kk neuron shallow ReLU network on standard Gaussian data in dimension dd within average error ϵ\epsilon. This algorithm is polynomial in dd and 1/ϵ1/\epsilon, although its dependence on kk 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:

  1. The writing is significantly more terse than it needs to be. Including more details would help the reader.
  2. 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
AuthorsOpenReview ↗

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=ε/128v=\varepsilon/128 forces a population moment of norm >8λj\gt 8\lambda_j. Estimation error below λj\lambda_j and power iteration produce an image of norm >7λj/2\gt 7\lambda_j/2, above the acceptance threshold 2λj2\lambda_j. Therefore stopping because every test fails certifies residual variance at most vv.

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\varepsilon/16; independent validation returns squared error below ε/2\varepsilon/2. The proof sets δ′=δ/[3(k+1)]\delta'=\delta/[3(k+1)], giving total failure bound (2k+1)δ′<δ(2k+1)\delta' < \delta.

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:

  1. Detect unexplained label variation. Signed neurons can cancel. Distance to projected subset sums supplies a nonlinear statistic; scaling exposes a second moment when residual variance is large. Homogeneity and Gaussian reweighting make these moments estimable from ordinary independent examples (Section 4.1).
  2. Control repeated direction selection. Subspace-error bounds keep estimation errors from invalidating subsequent searches or the stopping rule.
  3. Return a proper network. The conditional mean need not be a narrow ReLU network. We enlarge the learned subspace to dimension min⁡(k,d)\min(k,d); a norm-preserving rotation guarantees an approximating network in this enlarged space, and a parameter net and validation select a proper output.

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)≤2Cwk3g(k)\le 2^{C_{\rm w}k^3} for an absolute constant CwC_{\rm w} (Appendix E, p. 19).

Thank you for your response. I am satisfied with the changes made.

Reviewer_PNGwOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies proper learning of normalized, bias-free signed ReLU networks of fixed width kk under Gaussian inputs and noiseless labels. The authors establish a sample complexity of g(k)ϵ−O(k2)O~(d)g(k)\epsilon^{-O(k^2)}\widetilde O(d) and a real-arithmetic running time of g(k)ϵ−O(k2)O~(d2)g(k)\epsilon^{-O(k^2)}\widetilde O(d^2), while returning a ReLU network of width at most kk. The main technical idea is to iteratively learn a low-dimensional subspace using a nonlinear distance-to-subset-sums statistic and multi-scale second-moment signals that remain detectable despite signed cancellation, followed by a norm-preserving rotation argument to obtain a proper hypothesis in the original network class. The paper is primarily theoretical, with its empirical component limited to population-level numerical sanity checks illustrating positive and negative second-moment signals.

Critical strengths
  1. The theoretical contribution is substantial and novel. The paper tackles the difficulty caused by cancellation among signed neurons through a nonlinear label-distance statistic and a multi-scale moment construction, while also preserving properness via a separate rotation argument.
  2. The proof is technically coherent and progresses smoothly. The main lemmas are arranged in a clear dependency chain: residual variance leads to a detectable signal, the signal yields new subspace directions, and the final subspace guarantee is converted into a proper network approximation.
Critical weaknesses
  1. The paper is somewhat difficult to read. The proof involves many interdependent parameters and technical components spread across the main text and appendices, which makes the overall argument harder to follow than its high-level structure would suggest.

  2. The result relies on relatively restrictive assumptions. The analysis is limited to Gaussian inputs, noiseless labels, bias-free networks, and a real-arithmetic model. The scope is narrow. However, these assumptions appear closely tied to the techniques developed in the paper and do not substantially diminish the novelty of the theoretical result.

Questions for authors
  1. In Algorithm 1, what exactly is the intended behavior at j=0j=0 when ∥μ^∥<v/16\|\hat\mu\|<\sqrt{v}/16? Should the algorithm directly use the previously estimated MinitM_{\mathrm{init}}, as suggested by the surrounding discussion, or should it execute the coefficient-net and scaled-matrix search in line 8? This affects the precise algorithmic specification and potentially the complexity accounting.

  2. Can the authors provide a more explicit asymptotic upper bound on the width-only factor g(k)g(k)? Even a loose bound such as 2poly(k)2^{\mathrm{poly}(k)} or kO(k2)k^{O(k^2)}, if supported by the derivation, would make the quantitative strength of the theorem easier to assess.

2 comments
AuthorsOpenReview ↗

Proof structure, assumptions, initialization, and explicit width dependence

Thank you for the review and the specific questions. Page references below are to the revision.

Weakness 1: The interdependent parameters and proof components are hard to follow.

We reorganized the presentation around the learner's main steps. Section 1.2 now gives the three-stage overview and parameter-choice explanation (p. 2) before the full pseudocode (Algorithm 1, p. 3). Table 2 (p. 10) collects parameter choices in dependency order and explains their roles.

The parameter choices follow v→(T‾,η,λ)→β→ζjv\to(\overline T,\eta,\lambda)\to\beta\to\zeta_j: the residual-variance target sets scales, coefficient accuracy, and detection thresholds; these determine the error amplification β\beta. Set λ0=v/(32k)\lambda_0=v/(32k) initially and λj=λ\lambda_j=\lambda thereafter. The tolerance ζj=λjv/(kβk−1−j)\zeta_j=\lambda_j\sqrt v/(k\beta^{k-1-j}) compensates for remaining error amplification, explaining why earlier moments require more accurate estimates.

Section 1.2 (pp. 2-3) explains the three stages: detect remaining label variation, control errors while adding directions, and fit a proper network once that variation is small. Sections 3-5 (pp. 5-9) motivate the intermediate results. Section 6 (pp. 9-10) expands the proof through the subspace invariant, stopping rule, final prediction error, and failure accounting, with detailed calculations in the appendices.

Weakness 2: Gaussian inputs, noiseless labels, bias-free networks, and real arithmetic restrict the result's scope.

We agree that these assumptions limit applicability. The revised Conclusion (p. 10) explains their distinct roles:

  • Gaussian inputs: independent orthogonal projections, density differentiation and integration by parts, and the rotation coupling.
  • No biases: positive homogeneity lets us estimate scaled moments from ordinary independent examples.
  • Noiseless labels: mean-zero noise need not cancel inside the nonlinear label-distance statistic; an extension must control the resulting moment distortion.
  • Real arithmetic: the operation bound counts exact real operations; finite-precision guarantees require additional rounding-error analysis.

Gaussian inputs and bias-free networks are also used in the signed-network learning literature. Some moment learners, including Chen et al. (2023) and Diakonikolas and Kane (2024), additionally tolerate independent mean-zero noise; our guarantee concerns noiseless labels.

In the noiseless setting, filtered PCA has width-independent dimension exponents but exponential inverse-accuracy dependence; related higher-order moment learners have polynomial inverse-accuracy dependence at fixed width but dimension exponents growing with width. We combine both guarantees with proper output, without separation or conditioning assumptions.

Question 1: What happens at j=0j=0 when ∣μ^∣<v/16\\|\widehat\mu\\| < \sqrt v/16, and how is initialization counted?

The learner tests only the pre-estimated matrix M^init\widehat M_{\rm init}. It applies the matrix test to this candidate, adds a direction if an image reaches 2λ02\lambda_0, and otherwise stops. Coefficient-net enumeration and scaled-matrix searches occur only for j≥1j\ge1.

Algorithm 1 (p. 3, line 7) now states this branch explicitly. The initialization paragraph in Section 6 (p. 9) specifies one fresh batch estimating two objects: the first-moment vector μ\mu and the initial matrix MinitM_{\rm init}. Thus J=2J=2 counts two estimation events, although there is only one candidate matrix. The initial sample bound uses C0=V0=1C_0=V_0=1 and this count; no additional search or batch is needed in this branch.

Question 2: Can g(k)g(k) be bounded explicitly?

Yes. Theorem 1 (p. 2) now states g(k)≤2Cwk3g(k)\le 2^{C_{\rm w}k^3} for an absolute constant CwC_{\rm w}. Appendix E (p. 19) gives the new width-dependence derivation from the algorithm's parameters.

For k≥2k\ge2 and v=ε/128v=\varepsilon/128, the scale and amplification bounds are

\beta\le 2^{O(k^2)}v^{-(3k-1)/2}.$$ Every inverse estimation tolerance contains at most $k-1$ powers of $\beta$, giving a width factor at most $2^{O(k^3)}$. The moment-estimation scale factors $\overline T^{j+1}$ and $\overline T^{j+2}$ have the same width bound because $j < k$. The coefficient-net enumeration contributes at most $2^{O(k^3)}v^{-(k-1)j}$ candidates, and the final network net has width factor $2^{O(k^2\log(2k))}$. Multiplying these costs, including the $2^k$ subset sums per distance evaluation, preserves the overall width upper bound $2^{O(k^3)}$ and the inverse-accuracy exponent $O(k^2)$.

Thank you for the detailed response. My main concerns have been addressed, and I appreciate the authors’ effort in revising and clarifying the paper. I find the work interesting and meaningful, and I therefore plan to raise my score.

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

The paper provides a PAC style learning algorithm to learn the function of a one-hidden-layer ReLU network of kk neurons without biases from labeled examples. Previous papers by Chen et al. and Chen and Narayanan provided running time guarantees of (d/ε)kO(log⁡2k)(d/\varepsilon)^{k^O(\log^2 k)} or (dk/ε)O(k2)(dk/\varepsilon)^O(k^2), where ε\varepsilon is the squared Gaussian L2L_2 error. Another paper by Chen et al. provided something that is polynomial in dd, but exponential in kk and 1/ε1/\varepsilon. This paper gives a running time in which kk does not appear in the exponent of dd and that is at the same time polynomial in 1/ε1/\varepsilon for any fixed kk.

Critical strengths

The paper answers an interesting open question posed by Chen et al. affirmatively. The approach is reasonably elegant.

Critical weaknesses

The paper gives good guarantees for the asymptotic behaviour in dd and ε\varepsilon, but essentially still doesn't say anything about the asymptotic behaviour in kk. 1/ε1/\varepsilon still has kk in the exponent. And there is a not exactly specified factor of g(k)g(k).

Questions for authors

There is not very much discussion of lower bounds. Is a guarantee that is well-behaved in kk as well impossible?

1 comment
AuthorsOpenReview ↗

Explicit width dependence and the scope of lower bounds

Thank you for the review and for highlighting the width dependence. Page references below are to the revision.

Weakness: g(k)g(k) is unspecified, and the accuracy exponent depends on width.

We agree that the width dependence should be quantified. Theorem 1 (p. 2) now gives g(k)≤2Cwk3g(k)\le 2^{C_{\rm w}k^3} for an absolute constant CwC_{\rm w}, with the new derivation in Appendix E (p. 19).

The largest scale and error amplification per extension have width factors 2O(k2)2^{O(k^2)}. At most k−1k-1 amplifications give a factor 2O(k3)2^{O(k^3)}; moment estimation, coefficient enumeration, and the final network net fit within the same width bound.

The accuracy exponent still depends on width. The advance is combining a width-independent dimension exponent with polynomial inverse-accuracy dependence at every fixed width, while returning a network in the original normalized class. This addresses the direction proposed in Chen et al. (2023), Section 5: achieving these two complexity properties simultaneously. Improving the width factor or the accuracy exponent remains open.

Question: Is learning in time polynomial in width as well impossible?

Whether the signed, noiseless class admits learning in poly⁡(d,k,1/ε)\operatorname{poly}(d,k,1/\varepsilon) time remains open. Our upper bound does not establish that exponential width dependence is necessary. We conjecture that no such jointly polynomial learner exists in the worst case, since contributions of opposite signs can cancel in low-order moments even along directions that matter for prediction. For each candidate tuple of projected coefficients, our learner computes the distance from a label to the nearest subset sum by enumerating all 2k2^k subsets, which already takes exponential time in kk at fixed accuracy.

Section 1.3 (p. 4) now distinguishes two relevant lower bounds:

  • CSQ lower bounds. The regression lower bounds of Diakonikolas et al. (2020) and Goel et al. (2020) concern queries linear in the label. Our distance statistic is nonlinear in the label, so these bounds do not apply to our learner.
  • Noisy-label hardness. Li, Zadik, and Zampetakis (2025) establish cryptographic hardness with polynomially small Gaussian label noise. This does not establish hardness for our noiseless setting.

For nonnegative output coefficients, Diakonikolas et al. (2026) give a fully polynomial algorithm; Table 1 (p. 3) now includes this result. Arbitrary signs therefore remain a substantive distinction in assessing the fully polynomial learning question.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of manuscript revisions

Thank you for the reviews. We have marked new and revised text in blue. All page numbers below refer to the revised manuscript.

  • Theorem 1 (p. 2) states the explicit upper bound on the width factor g(k)g(k). Appendix E (p. 19) gives the derivation.
  • Section 1.2 (pp. 2–3) presents the algorithm overview and full pseudocode. Algorithm 1 (p. 3, line 7) clarifies which matrix is tested at initialization. Section 6 (p. 9) explains how the two initial estimates are counted, and Table 2 (p. 10) lists the parameter choices.
  • Table 1 (p. 3) adds the fully polynomial result for nonnegative output coefficients. Section 1.3 (p. 4) clarifies the scope of the correlational statistical query lower bounds and the hardness result for noisy labels.
  • Section 3.2 (p. 6) connects the scale lemma to the second-moment test. Section 5.1 (p. 9) explains the factor of two in the rotation bound, and Section 6 (p. 10) expands the stopping argument and failure-probability calculation.
  • The Conclusion (p. 10) explains where the analysis uses Gaussian inputs and exact real arithmetic.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.