- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
The paper is about recovering the hidden weights of a positive sum of ReLUs under Gaussian inputs. Similar problems with arbitrary output weights have been studied and are known to be worst-case hard. The paper proves conditions which ensure that the true planted weights are statistically identifiable but also proves that they cannot be computed by a randomized polynomial-time algorithm with adaptive membership queries unless NP is in RP. On the positive side, the authors define further conditions under which recovering the exact hidden weights becomes algorithmically tractable (with high probability).
The results seem to be strong (but also heavily AI generated in parts). I did not check the details. The main pages only give very high-level descriptions which are not really understandable for a non-expert reader. Many important preliminaries are not explained (like what exactly is the learning setup with planted networks). I find Section 6 (overview and key ideas) not really helpful at all. It is not clear to which results the paragraphs are referring. This reads very AI-generated. Due to the poor presentation, I tend towards rejection.
Critical strengths
The hardness and tractability results seem to be strong and quite involved.
Critical weaknesses
The paper is not very readable and hard to understand/verify if you are not a real expert in the field.
It is not clear to me how important or interesting the results really are for the theory community (and also for practitioners).
Questions for authors
How realistic are your identifiability and tractability assumptions in practice?
Could your algorithm be run in practice? What is the exact running time?
3 comments
W2/Q1: Significance of the results and realism of the identifiability and tractability assumptions
Our central question is whether exact parameter recovery is computationally tractable for positive ReLU networks under Gaussian inputs. Positivity eliminates output-sign cancellations, and Gaussian inputs provide particularly rich information about the planted weights. One might therefore expect sufficiently separated and identifiable parameters to be efficiently recoverable. The hardness result was unexpected to us and to several experts we consulted.
Theorem 3.4 establishes hardness even when the planted weights have:
- Uniform upper and lower norm bounds.
- Pairwise angular separation.
- A strict positive margin for every nonempty subset sum.
These assumptions rule out obvious degeneracies and ensure quantitative identifiability. Nevertheless, the hidden orientations can encode an NP-hard combinatorial problem. The hardness is therefore not a consequence of nearly coincident neurons or non-identifiability.
Theorem 4.2 establishes tractability under the stronger geometric condition of positive independence:
\ge \eta\sum_{\ell=1}^k\alpha_\ell\|w_\ell\|_2, \qquad \alpha_\ell\ge0.$$ Geometrically, this requires the normalized weights to lie in a common open half-space with a quantitative margin. **How realistic are these assumptions?** The identifiability conditions are relatively mild: non-collinearity excludes redundant neurons on the same line, while the no-subset-cancellation condition excludes exact cancellations. Positive independence is stronger. However, it includes well-conditioned full-column-rank networks and can also hold in overcomplete settings (k>d). For example, angularly separated directions contained in a common spherical cap satisfy the condition with a quantitative margin. We do not claim positive independence is necessary for efficient recovery. It is a sufficient condition under which the discrete orientation problem admits a provably correct convex relaxation. Whether weaker assumptions suffice remains open and an interesting direction for future research. **Why is this theoretically interesting?** Efficient learning of positive ReLU networks under Gaussian inputs has been a longstanding problem. Two recent works, Zheng (2026) and Diakonikolas et al. (2026), appearing after our submission, give polynomial-time guarantees for approximate function learning under general geometric configurations. Exact parameter recovery is a stronger problem whose computational complexity remains much less understood. Our results show that even strongly separated and statistically identifiable networks can be computationally hard to recover exactly. We identify sign orientation as the source of this hardness and establish polynomial-time recovery under an additional geometric condition, including for overcomplete networks. Understanding these conditions may ultimately help explain when gradient descent and other commonly used optimization methods recover planted solutions. Our results show that **even strongly separated and statistically identifiable positive ReLU networks can be computationally hard to recover**. We identify sign orientation as the source of this hardness and give a polynomial-time recovery algorithm under an additional geometric condition, including for overcomplete networks. Together, these results establish a concrete distinction between statistical identifiability, computational hardness, and tractability. ### Q2: Can the algorithm run in practice? What is the exact running time? The algorithm has large theoretical constants and is unlikely to be practical in its current form. The explicit sample-complexity and arithmetic-operation bounds are given in Theorems C.1 and C.2, with polynomial dependence on d, k, 1/r, and 1/ for fixed angular-separation parameter <1. **Our goal is to establish the computational limits of exact recovery**, rather than develop an immediately practical algorithm. The main result shows that polynomial-time recovery is possible under explicit geometric assumptions, even in the overcomplete regime. We hope the geometric insights and algorithmic techniques will also help analyze simpler methods, including gradient descent, and eventually lead to more practical algorithms.I thank the authors for the response. They improved the readability and I am convinced that the results are indeed significant and interesting. I raised my score.
We thank the reviewer for the feedback. We have revised the manuscript to clarify the setup, the connections between the main results, and the computational guarantees.
W1: Readability, missing preliminaries, and the usefulness of Section 6
We have expanded the introduction and added explanations connecting the main results. Our setting is as follows: we observe independent Gaussian inputs xi∼N(0,Id) and noiseless labels generated by an unknown one-hidden-layer ReLU network,
yi=fW(xi)=∑ℓ=1kReLU(wℓ⊤xi).
The objective is to recover the individual planted weights w1,,wk, up to permutation, rather than merely approximate the network's predictions. We have made this distinction explicit in the introduction.
The main question is whether statistical identifiability implies computationally efficient recovery. Our results show that these are different questions:
Statistical identifiability (Section 2). Under mild nondegeneracy assumptions, the population distribution uniquely determines the planted weights. This is a known result, for which we provide an alternative Hermite-moment proof.
Computational hardness (Section 3). Even when the weights are well separated and statistically identifiable with quantitative margins, exact recovery can remain computationally hard. The difficulty lies in determining the orientations of hidden directions identified by even-order moments.
Computational tractability (Section 4). Under the stronger condition of positive independence, the orientation ambiguity can be resolved by convex optimization. This yields polynomial-time, polynomial-sample exact recovery in the stated arithmetic model, including the overcomplete regime k>d.
Section 6 now connects these results more explicitly. Even-order Hermite moments identify the hidden directions up to sign, while the first moment constrains their sum. Recovering the correct signs can encode a discrete subset-sum problem, whereas positive independence allows a convex relaxation. We have also added a short explanation of the hardness reduction in Section 3, including the identity that permits evaluating the network without knowing the hidden signs.
Regarding AI-assisted writing, our AI-use statement discloses its role in developing parts of the hardness argument and editing the exposition. The authors have independently checked the mathematical claims and take responsibility for the results.