acceptodds
Withdrawn from ICLR 2027

Fully Polynomial Learning of Positive ReLU Sums

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

We give a fully polynomial algorithm for learning positive sums of bias-free ReLUs under Gaussian inputs. From labeled examples of a sum with hidden units in , the algorithm returns, with probability at least , an efficiently evaluable polynomial of degree with relative error at most . It uses labeled samples and arithmetic operations, with the same bound on memory, output size, and evaluation time. The guarantee holds for arbitrary nonnegative weights and ridge vectors, including coincident and antipodal directions. The central step estimates a small, label-observable covariance at each degree. Aligning its factor with the hidden ridge tensors gives a low-rank comparator for tensor-train rounding; balanced degree splits then prevent the rounding loss from accumulating exponentially.

Primary area:
learning theory
Keywords:
learning theory, PAC learning, positive ReLU networks, Gaussian inputs, moment methods, tensor-train approximation

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_yMCsOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper perhaps gives an improper learning algorithm for nonnegative sums of (kk) bias-free ReLU units under standard Gaussian inputs and noiseless labels. With probability at least 1−δ1-\delta it returns a polynomial hypothesis satisfying $ |H-F|_2 \le \epsilon|F|_2, $ with 0≤ϵ,δ≤1/20 \leq \epsilon, \delta \leq 1/2 from Theorem 1.1. The paper however does not provide a proper context such as settings, definitions of used terms, related work neither any experiments and appendices. On a side note, based on its AI use statement it looks AI has generated the whole paper with authors taking responsibility for it.

Critical strengths

Derived results may be possibly correct under certain (not mentioned) circumstances. It is impossible to check paper's soundness, validity and contributions without definitions and assumptions, that are not stated. Thus I have not even tried, see weaknesses.

Critical weaknesses

Abstract is already confusing and it is hard to understand its meaning first hand, e.g.,

"...The guarantee holds for arbitrary nonnegative weights and ridge vectors, including coincident and antipodal directions. The central step estimates a small, label-observable covariance at each degree. Aligning its factor with the hidden ridge tensors gives a low-rank comparator for tensor-train rounding; ..."

Missing context, settings, related work and goal of the paper makes this paper impossible to evaluate for the conference. There are no experiments and appendices with additional information either.

Without a massive, major remake, I found the paper not ready for publication in its current form.

Questions for authors

See above.

2 comments
AuthorsOpenReview ↗

Response to Reviewer yMCs

We agree that the submission lacked the setting, definitions and context a reader needs. The revision supplies them.

  • Setting (p. 1, l. 32–45). The target is F(x)=∑iwimax⁡{0,vi⊤x}F(x)=\sum_iw_i\max\lbrace0,v_i^\top x\rbrace with wi≥0w_i\ge0. Examples are noiseless pairs (X,F(X))(X,F(X)) with X∼N(0,Id)X\sim\mathcal N(0,I_d). The goal is ∥H−F∥L2≤ϵ∥F∥L2\Vert H-F\Vert_{L_2}\le\epsilon\Vert F\Vert_{L_2} with probability at least 1−δ1-\delta. The assumptions are exactly these: Gaussian inputs, noiseless labels, units without biases, nonnegative weights, and resources counted in the real-arithmetic model; nothing is assumed about the directions or the sizes of the weights. Section 3 fixes the remaining notation, and the overview defines each object before using it. With the setting stated, we would welcome a reassessment of soundness.
  • Abstract. It is rewritten, in the PDF and in the OpenReview abstract field, and the sentences you quote are gone.
  • Related work. New Section 1.1 (p. 3, l. 108–148) adds seven references.
  • Appendices A–C contain the routine proofs, the full rounding proof and the resource count. Theorem 6.3 is proved in full.
  • Experiments. The contribution is a complexity statement: a learner whose resources are polynomial in dd, kk and 1/ϵ1/\epsilon, which answers a question posed by Diakonikolas and Kane (2024). Its exponents and constants are large (p. 2, l. 105–107), so the algorithm is not practical as stated, and the paper is purely theoretical.
  • AI use. Our statement describes how AI tools were used, and it now says that the numerical checks served development only. The authors take responsibility for every statement and proof, and we would be glad to address any concern about a specific claim.

I thank authors for the proposed changes. Current revision of the paper seems like a new paper, yet I still find it unsatisfactory clear, e.g., what does that even mean to learn F(X)F(X) from (X,F(X))(X,F(X)) just for starters? This is a first sentence of the abstract: ("We study learning a positive sum of k ReLUs, ... from noiseless examples (X,F(X))(X, F (X)) with Gaussian inputs X∼N(0,Id)X \sim N (0, Id)."). Further, a lack of broader motivation and missing experimental evidence for proposed algorithms, etc., provides more than enough ground for rejecting the paper for the current edition of the ICLR conference. I maintain my previous recommendation.

Reviewer_6kS3OpenReview ↗
Rating
1(−2)
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper considers learning positive sums of bias-free ReLUs under Gaussian inputs and proposes an algorithm with polynomial sample and computational complexity in the dimension, width, and inverse accuracy. The main idea is to estimate observable high-order moments and use tensor-train representations to construct a polynomial approximation without explicitly recovering the hidden directions. In addition, the authors use balanced degree splits to control the accumulation of approximation errors. This addresses an important open problem, as previous approaches achieved polynomial dependence on the dimension and width but retained exponential dependence on the inverse accuracy.

Critical strengths
  • The paper addresses an important open problem in computational learning theory. Improving the dependence on inverse accuracy from exponential to polynomial is a substantial theoretical contribution.

  • The combination of observable moments, factor alignment, and balanced tensor-train rounding is interesting. It avoids explicit construction of high-order tensors and does not require separation between hidden directions.

Critical weaknesses
  • The proof of the tensor-train rounding guarantee in Proposition 2.4 is technically dense. In particular, the argument for preserving the comparator rank constraints and controlling the accumulated approximation error is not sufficiently explicit, although this result is central to the subsequent analysis.
Questions for authors

Can the authors make the induction argument in Proposition 2.4 more explicit, in particular, how the comparator rank constraints are preserved at each step and how the approximation error accumulated across the cuts is bounded?

2 comments
AuthorsOpenReview ↗

Response to Reviewer 6kS3

The induction in old Proposition 2.4 (now Proposition 3.3) is written out in Appendix B (p. 14, l. 753 – p. 16, l. 839), over the cuts from right to left.

  • Invariant (p. 15, l. 770 onward). After cuts q−1,…,j−1q-1,\dots,j-1 there is a comparator BjB_j with three properties. Its unfolding at cut j−1j-1 has columns in the column space of the corresponding unfolding of a best rank-rr train BB, a space of dimension at most rr. Its modes j,…,qj,\dots,q lie in the span of the output cores chosen so far. And ∥A−Bj∥F2≤κq+1−j∥A−B∥F2\Vert A-B_j\Vert_F^2\le\kappa^{q+1-j}\Vert A-B\Vert_F^2.
  • Rank constraint. The new comparator UD^⊤(I⊗Sj+1)⊤U\widehat D^\top(I\otimes S_{j+1})^\top keeps the same left factor UU, an orthonormal basis of that column space. In terms of cores, it keeps the first j−2j-2 cores of BB and absorbs a coefficient matrix into core j−1j-1. The proof also shows why U⊤GU^\top G has full row rank.
  • Error. Every such comparator has error c+∥DU⊤−Cj∥F2c+\Vert DU^\top-C_j\Vert_F^2 with cc independent of DD. Since cc is common to both comparators and κ≥1\kappa\ge1, the sketching lemma gives ∥A−Bj∥2≤κ∥A−Bj+1∥2\Vert A-B_j\Vert^2\le\kappa\Vert A-B_{j+1}\Vert^2, so each cut costs one factor κ\kappa. After q−1q-1 cuts the factor is κq−1<e2/7<9/4\kappa^{q-1}<e^{2/7}<9/4, that is 3/23/2 in norm. The output is the projection of AA onto the chosen cores, so it is no worse than the last comparator.

The overview (p. 5, l. 238–262) explains why the learner needs rounding and where the comparator comes from.

At this stage, the article is not written clearly enough, to reliably assess the technical contributions. Despite a thorough revision, issues of clarity and presentation remain. In line with the other reviewers' concerns, I recommend rejecting the paper for this conference edition and suggesting that the authors simplify and rewrite it for future submission.

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

The paper studies learning F(x)=∑i≤kwi ReLU(vi⊤x)F(x)=\sum_{i\le k} w_i\,\mathrm{ReLU}(v_i^\top x) with wi≥0w_i\ge 0 and no bias, from noiseless examples with X∼N(0,Id)X\sim N(0,I_d). It gives a fully polynomial time improper learner, which returns a polynomial of degree O(ϵ−4/3)O(\epsilon^{-4/3}) with relative L2L_2 error ϵ\epsilon. It needs no separation between the directions.

The degree-ss Hermite coefficient of the even part of FF is a multiple of Ms=∑iwivi⊗sM_s=\sum_i w_i v_i^{\otimes s}. This tensor has dsd^s entries but lies in the span of only kk tensors vi⊗sv_i^{\otimes s}. At each degree, the algorithm builds a subspace of dimension at most kk that nearly contains these tensors. It then estimates the coordinates of MsM_s in that subspace from label correlations. The degree-ss subspace is built from products of the subspaces at degrees ⌊s/2⌋\lfloor s/2\rfloor and ⌈s/2⌉\lceil s/2\rceil. A small covariance estimated from labels selects kk directions, and randomized tensor-train rounding keeps them compact. Balanced splits keep the accumulated rounding loss polynomial.

Critical strengths

The main theorem is interesting. Diakonikolas & Kane (2025) call a poly(d,k,1/ϵ)\mathrm{poly}(d,k,1/\epsilon) algorithm for this class open. This paper resolves that question for positive, bias-free ReLU sums. The guarantee holds for arbitrary positive weights and for coincident or antipodal directions.

The proofs are also neat and self-contained.

Critical weaknesses

A minor attribution point: the key step of Lemma 4.1, ∥A1/2−B1/2∥F2≤∥A−B∥∗\|A^{1/2}-B^{1/2}\|_F^2\le\|A-B\|_*, is the classical Powers–Størmer inequality. The paper proves it without naming it. The related-work discussion is also incomplete. It omits Chen et al. (2023) and Chen & Narayanan (2024) on learning general one-hidden-layer ReLU networks under Gaussian inputs, as well as Awasthi, Tang & Vijayaraghavan (2021), who use higher-order Hermite tensors to learn biased ReLU networks under non-degeneracy assumptions. These works provide relevant algorithmic and technical context. The paper should distinguish function learning without conditioning assumptions from parameter recovery under non-degeneracy, and explain what its positive-weight restriction and compact tensor representation change. Comparing runtime bounds within the positive-weight setting alone does not adequately situate the contribution.

My main concern is presentation. The entire technical overview consists of two paragraphs on lines 54–64 and offers little high-level intuition. For a first-time reader, the explanation should start from the basics and clearly explain (a) what exactly you are doing and (b) why you are doing it, especially in the context of prior work. As written, however, these two paragraphs read more like a summary for someone who already understands the approach and are rather uninformative as a technical overview. For example, the claim that the restricted covariance "can be estimated from labels" does not give any information on the actual estimation method. Likewise, "small Hermite-coordinate tensor trains" is introduced without explaining what it is or why it permits efficient computation.

For example, the technical overview should begin with fundamentals such as "To output a polynomial with small error, we would want to match the low-degree Hermite moments, but the naive estimator takes exponential time and samples; like/unlike Diakonikolas & Kane, we estimate these moments by ...".

I would argue that the presentation and discussion quality is of paramount importance for a theory paper like this one, particularly in this era of proof abundance. Moreover, much of the value of a fully polynomial result lies in explaining how the earlier exponential cost disappears. Here a reader cannot tell whether that reason is the variance of the statistics, the exact evaluation of Hermite tests, or the balanced merge. Without the relevant comparisons, the new technique is hard to identify and harder to apply to other latent variable models.

The fully polynomial guarantee is a substantive improvement, and the proofs appear sound. However, the paper leaves the reader to reconstruct from the detailed analysis how the previous exponential cost is removed and which ideas make this possible. I find this to be unacceptable at a top-level conference. I hence recommend rejection.

Questions for authors

Where exactly does Diakonikolas & Kane (2025) lose the factor exponential in 1/ϵ1/\epsilon, and which change in your algorithm removes it? Do you expect similar methods to apply for the other problems they considered?

2 comments
AuthorsOpenReview ↗

Response to Reviewer MdFu

Overview. The new Section 2 (p. 3, l. 149 – p. 6, l. 274) starts from the Hermite expansion, as you suggested, and adds one obstacle at a time. It covers what must be learned (moment tensors up to degree Θ(ϵ−4/3)\Theta(\epsilon^{-4/3})), how one coordinate is read from labels with polynomial variance, why a kk-dimensional subspace per degree suffices and how it is bootstrapped, and why rounding and balanced merges are needed.

  • "Estimated from labels." The restricted covariance has entries Bjℓ=2c2sE[F(X) pSym(Aj⊗Aℓ)(X)]B_{j\ell}=\frac{2}{c_{2s}}\mathbb E[F(X)\thinspace p_{\mathrm{Sym}(A_j\otimes A_\ell)}(X)], which we estimate by a median of means (variance bound p. 4, l. 172–185; estimate l. 195–212).
  • "Hermite-coordinate tensor trains." The overview now defines them (p. 5, l. 224–236). They store a symmetric tensor by one number per multi-index α∈{0,…,s}d\alpha\in\lbrace0,\dots,s\rbrace^d, as a product of one small matrix per input coordinate. Since Hermite polynomials factor over coordinates, pA(x)p_A(x) is then a product of dd small matrices and is computed exactly.

Where Diakonikolas–Kane (2025) lose the exponential factor. In the variance of their label statistics. Their recursive projections apply efficiently to tensors produced by short sequential computations. The Hermite tensor is not conveniently of that form, so they use the random surrogate Re((x+iy)⊗t)/t!\mathrm{Re}((x+iy)^{\otimes t})/\sqrt{t!}, whose second moments are bounded by 2O(t)2^{O(t)} (their Definition 4.1, Lemma 4.3 and the proof of Theorem 4.7). With tt up to poly(1/ϵ)\mathrm{poly}(1/\epsilon), this is 2poly(1/ϵ)2^{\mathrm{poly}(1/\epsilon)}. We evaluate each Hermite test exactly, so by Lemma 3.1 the normalized test 2F pA/ct2F\thinspace p_A/c_t with ∥A∥F=1\Vert A\Vert_F=1 has second moment at most 4W2(d+2t)/ct24W^2(d+2t)/c_t^2. Exact evaluation uses tensor trains, whose ranks multiply under products, so we round. Each rounding costs a constant factor, and the balanced merge makes the number of such factors along any path O(log⁡T)O(\log T) instead of TT.

Of your three candidates, then: the variance is where the loss occurs, exact evaluation together with the direct bound of Lemma 3.1 (which uses only 0≤F(x)≤W∥x∥20\le F(x)\le W\Vert x\Vert_2) removes it, and the balanced merge makes exact evaluation affordable (p. 2, l. 74–94; p. 4, l. 213 – p. 5, l. 269).

Other problems. The paper does not treat them. Exact evaluation relies on two properties of ReLU sums, named on p. 2, l. 103–105: a polynomial variance bound for exact statistics, which follows from 0≤F(x)≤W∥x∥20\le F(x)\le W\Vert x\Vert_2, and small trains for the components of the moment tensors. An extension depends on whether those models have both.

Powers–Størmer. The note after Lemma 5.1 (p. 8, l. 426) now names the inequality and cites Powers and Størmer (1970).

Related work (Section 1.1, p. 3, l. 108–148). It now discusses Chen et al. (2023), Chen and Narayanan (2024) and Awasthi, Tang and Vijayaraghavan (2021). It separates function learning without conditioning assumptions, where for arbitrary signs the SQ lower bound dΩ(k)d^{\Omega(k)} applies, from parameter recovery under non-degeneracy, where bounds grow with inverse singular values. The matrices KsK_s have rank at most kk for weights of any sign; positivity makes them positive semidefinite, which the subspace step uses (p. 2, l. 98–101). The compact representation is what makes Hermite tests exactly computable.

Reviewer_MdFuOpenReview ↗

Response to response

I appreciate the update and the extended technical overview.

Honestly, the quality of the first draft feels like the first thing a language model produced, without any human filtering at all. To submit this and then to polish it after submission is strange; I don't think this level of redrafting is normal, and I do not think the reviewers are obliged to re-evaluate based on what's essentially an entirely new paper.

I hence maintain my decision to reject.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We thank the reviewers. All three found the paper hard to follow, and they are right. At the submission deadline we did not have time to write the paper properly, so the submission contained the technical content (the algorithm, the theorem and complete proofs) but not the setting, the intuition, the comparison with earlier work and the related literature that a reader needs. We have since substantially completed the paper and uploaded the revision. Every added or changed word is blue (automatically renumbered references excepted), and the new appendices are entirely blue, including the moved proofs. The main text stays within ten pages, and no theorem, lemma or proposition has changed in content (Lemma 3.1 gains a defining phrase).

A reader now meets, in order: the problem and its setting (p. 1); the main theorem next to the earlier bounds, with where the earlier algorithm loses its exponential factor and how ours avoids it (p. 2); related work (Section 1.1, p. 3); a technical overview that builds the algorithm from the Hermite expansion (Section 2, pp. 3–6); then the preliminaries, the algorithm and the analysis. Routine proofs moved to new Appendices A–C, verbatim except for two explanatory sentences added to the proof of Lemma B.1 (p. 14, l. 732–736), and the rounding proof is written out as an explicit induction in Appendix B.

Renumbering (old → new): Lemma 2.1 → 3.1, 2.2 → 3.2, 2.3 → B.1, Proposition 2.4 → 3.3, Lemma 4.1 → 5.1, 4.2 → 5.2, 5.1 → 6.1, Proposition 5.2 → 6.2, Theorem 5.3 → 6.3.

Corrections. In the proof of Proposition 6.2, "squared eigenvalues" now reads "eigenvalues", matching Algorithm 2. The AI-use statement now says that the synthetic numerical checks it mentions were used during development, and that the paper reports no experiments.

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

Related papers

Discussion (0)

Sign in to comment.