acceptodds
Under review as a conference paper at ICLR 2027

When Is Learning a Planted ReLU Network Tractable?

Abstract

Learning neural networks from data is a fundamental problem, yet the tractability of even one-hidden-layer networks remains poorly understood. Worst-case hardness is known when the output-layer weights may have arbitrary signs, but a basic and surprisingly unresolved case remains: can one efficiently learn a sum of ReLU units with positive output weights, even under standard Gaussian covariates? We study recovery of the hidden weights in planted networks of the form We first identify when the parameters are statistically determined, up to the natural permutation symmetry. In particular, Gaussian inputs allow the identification of the hidden weights under mild nondegeneracy conditions: no two weights are collinear, and no nonempty subset of the weights sums to zero. However, we show that identifiability alone is far from enough for efficient learning. Even under bounded norms, angular separation, and a strict positive subset-sum margin, any randomized polynomial-time algorithm that exactly recovers the parameters from membership queries at rational points would imply a randomized polynomial-time algorithm for an NP-hard vector subset-sum problem; hence no such algorithm exists unless . This hardness result reveals the central obstruction: Gaussian even-order moments can recover the hidden hyperplanes, but orienting those hyperplanes can encode a hard discrete problem. On the positive side, we identify natural geometric conditions that make the orientation barrier tractable. Specifically, we show that a continuous analogue of the subset-sum margin, in the form of a positive-independence condition, enables, for any fixed angular-separation constant, exact recovery from polynomially many samples in polynomial time, given an exact solver for a polynomial-size linear program. Our method first combines implicit Gaussian Hermite moment estimation with random polynomial features and a low-dimensional matrix pencil to recover the network weights approximately up to sign. It then uses convex sign orientation based on the first moment to identify the correct signs, followed by anchored regression to refine the estimates to exact recovery.

Primary area:
learning theory
Keywords:
Neural network learning theory, ReLU networks, parameter identifiability, tensor decomposition, method of moments, subset-sum problem

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_KYVYOpenReview ↗
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

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)x_i\sim\mathcal N(0,I_d) and noiseless labels generated by an unknown one-hidden-layer ReLU network,

yi=fW(xi)=∑ℓ=1kReLU⁡(wℓ⊤xi).y_i=f_W(x_i)=\sum_{\ell=1}^k\operatorname{ReLU}(w_\ell^\top x_i).

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.

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.

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

The paper studies recovery of the hidden weights of a planted one-hidden-layer ReLU network with positive output weights under standard Gaussian inputs. By positive homogeneity, the output weights can be absorbed into the hidden weights, so the model reduces to a sum of ReLUs, fW(x)=∑ℓReLU(⟨wℓ,x⟩)f_W(x) = \sum_ℓ ReLU(⟨w_ℓ, x⟩).

The paper makes three contributions.

  • Identifiability (Section 2). The hidden weights are identifiable up to permutation under two nondegeneracy conditions: no two weights are collinear (Assumption 2.1), and no nonempty subset of the weights sums to zero (Assumption 2.2). These conditions are natural and rule out merged neurons and sign flips that leave the function unchanged. The result is a specialization of Stock and Gribonval (2023), proved here via Hermite moments.

  • Hardness (Section 3). Identifiability does not imply tractability. The paper adds quantitative assumptions: norm bounds, robust non-collinearity, and a positive subset-sum margin that excludes near-cancellations. Under these, Theorem 3.4 shows that a randomized polynomial-time algorithm recovering the parameters exactly from adaptive membership queries would imply NP ⊆ RP, via a reduction from X3C. Corollary 3.5 transfers the same reduction to passive Gaussian samples, but only in a real-arithmetic computational model, where it does not yield NP ⊆ RP.

  • Tractable regime (Section 4). The paper gives a polynomial-time algorithm under a positive independence assumption (Assumption 4.1). This assumption is equivalent to the weights lying in a common open half-space with a positive margin along a shared direction. The algorithm (Table 1) proceeds in three stages:

  1. estimate the weight directions and magnitudes, up to sign, from even-order Hermite moments;
  2. determine the signs from the first moment through a convex box relaxation;
  3. refine the estimates to exact recovery via anchored regression (Theorem 4.2).

Section 6 gives a proof overview based on the tensor-matching expansion of the population loss from Ge et al. (2018). It identifies sign orientation as the main source of difficulty.

Critical strengths
  • The paper addresses a natural question: whether exact parameter recovery is computationally tractable for one-hidden-layer ReLU networks with positive output weights. The result is interesting and appears to be novel; I could not find prior work treating this case.
  • The paper gives a clear conceptual picture that separates identifiability from efficient recovery and isolates the sign-orientation ambiguity as the obstruction. The discussion around Equation (9) is particularly informative.
  • The paper is easy to read and well structured, and the structure of the arguments is easy to follow. The proof overview in Section 6 is clean.
Critical weaknesses
  • Scope of “learning.” The paper does not make precise what it means by learning a ReLU network. Recovering the parameters wℓw_ℓ is a stronger requirement than learning the function, i.e., achieving small error ‖f−fW‖‖f − f_W‖. The results concern parameter recovery, and this should be stated explicitly, for instance at the start of Section 4, to scope the results correctly.
  • Relation to the linearly independent case. The case of linearly independent weights (k≤dk ≤ d, full rank) has been well studied. The paper mentions this, but would benefit from a more in-depth discussion, when presenting the assumptions in Section 4, of what changes once the weights are no longer linearly independent (e.g., k>dk > d). Compared to the setting of Ge et al., for example.
  • Positioning and technical novelty. Closely related works study similar settings with both signed and positive output weights, notably Diakonikolas and Kane (2025), Diakonikolas et al. (2024), and Ge et al. (2018). Many elements of the algorithm have appeared in these works. The related-work section positions the paper relative to them, but offers little insight into the technical contribution: how the proofs differ, and what is distinctive about the positive setting compared with the signed cases. Beyond remarks that positive independence avoids exponential-time steps, these connections could be developed further.
  • Restrictiveness of positive independence. Assumption 4.1 restricts the admissible weights, and increasingly so as the dimensions grow: for large dd and kk, random weights are less likely to satisfy it. The paper does not discuss in which regimes of kk and dd the result is informative. It also does not discuss whether the condition is likely necessary or an artifact of the algorithm. The discussion near Equation (9) is relevant here; it could be introduced earlier, together with an illustration of the contrast with the signed case.
  • Self-containedness of the hardness results. The main text does not point to the proofs in the appendix or to the corresponding proof sketches, and it describes the reduction only briefly. A few sentences explaining the reduction more precisely would make the statements easier to follow on their own.
  • Choice of moment degree. The main text does not explain how the moment degree m is chosen, or whether the result requires constraints on this choice.
Questions for authors
  • Could the authors clarify whether the results concern parameter recovery or function learning, and how the conclusions would change for the latter?
  • How is the moment degree mm chosen, and is there a constraint on this choice for the result to hold and does it impact the degrees of the polynomial?
  • What are the implications of Assumption 4.1 for random weights when d and k are large? In which regimes of kk and dd is the result informative? Is the condition believed to be necessary, or is it tied to the algorithm’s construction?
  • What are the technical differences from Diakonikolas and Kane (2025), Diakonikolas et al. (2024), and Ge et al. (2018), particularly regarding the algorithm and the proofs?
  • What happens in the full-rank case and in the signed case, and how does the current setting differ from each?
4 comments

We thank the reviewer for the careful reading and constructive comments. We address the overlapping weaknesses and questions together below.

W1/Q1: Parameter recovery versus function learning

Our goal is exact recovery of the planted hidden weights, up to permutation, for networks of the form

fW(x)=∑ℓ=1kReLU⁡(wℓ⊤x).f_W(x)=\sum_{\ell=1}^k \operatorname{ReLU}(w_\ell^\top x).

This is distinct from finding a function with small prediction error under the Gaussian distribution. Our hardness result concerns exact parameter recovery and does not imply hardness of approximate function learning. Since our submission, Zheng (2026, https://arxiv.org/abs/2610.25116) and Diakonikolas et al. (2026, https://arxiv.org/abs/2610.32940) have given polynomial-time guarantees for approximate function learning under Gaussian inputs, without comparable separation or conditioning assumptions. These are important advances, but their objective differs from ours. In particular, Diakonikolas et al. use a representation consisting of a linear function plus absolute-value terms, which allows them to approximate the target without resolving the hidden signs. Both works also recover information about the hidden directions, but neither establishes exact recovery of the original planted parameter set. Our hardness result concerns precisely this stronger parameter-recovery objective and does not imply hardness of function approximation. Our positive result identifies conditions under which exact recovery becomes tractable, including in overcomplete settings.

Our positive result also concerns parameters rather than function values: under positive independence and fixed angular separation, the algorithm recovers the individual weights exactly from finitely many noiseless Gaussian samples, using an exact final LP solver. Theorem 2.3 establishes identifiability, Theorem 3.4 shows that identifiability need not imply efficient recovery, and Theorem 4.2 gives a geometric regime in which exact recovery is efficient. We have stated this distinction earlier in the introduction and Section 4.

W2/Q5: Full rank and overcomplete networks

In the undercomplete case kd, full column rank of W=[w1,,wk] implies positive independence. If ∥wℓ∥2≤1\|w_\ell\|_2\le1, then for every 0,

\ge\frac{\sigma_{\min}(W)}{\sqrt{k}}\sum_{\ell=1}^k\alpha_\ell\|w_\ell\|_2.$$ Thus Assumption 4.1 holds with (W)/k, covering the classical well-conditioned full-rank case. The distinction is in the **overcomplete regime k>d**, where W cannot have full column rank. Our method uses higher-order lifting: for $u_\ell=w_\ell/\|w_\ell\|_2$ satisfying |uiuj|<1, $$\langle u_i^{\otimes m},u_j^{\otimes m}\rangle=(u_i^\top u_j)^m.$$ A sufficiently large degree makes the lifted Gram matrix well-conditioned even when the original directions are linearly dependent. We access the lifted representation implicitly rather than forming a tensor of dimension dm. Positive independence is also compatible with overcompleteness: angularly separated directions in a common spherical cap of radius strictly below /2 is a simple example. Hence neither the unoriented-recovery stage nor the orientation stage requires full column rank of W. We have made this contrast explicit near Assumption 4.1.

W3/Q4/Q5: Technical novelty and relation to prior work

Our method combines established tools to obtain a new exact parameter-recovery guarantee in the overcomplete regime. Implicit high-order Hermite moments, random polynomial features, and a low-dimensional matrix pencil recover the hidden directions and magnitudes approximately, up to sign. Coordinate-weighted contractions recover rank-one projectors. We use the first moment and convex box relaxation to resolve signs under positive independence, followed by anchored regression for exact recovery.

Diakonikolas and Kane (2025). We use their implicit moment estimator as a primitive, not a new contribution. Their function-learning result has runtime poly⁡(d,k) 2poly⁡(1/ε)\operatorname{poly}(d,k)\,2^{\operatorname{poly}(1/\varepsilon)} in the normalized setting. Function approximation, however, does not recover the individual planted parameters. Our contribution is the component-recovery, orientation, and exact-recovery analysis.

Diakonikolas and Kane (2024). Their Schur-polynomial method learns functions represented by general linear combinations of ReLUs, with runtime (dk/)O(k). We instead use selected high-order Hermite contractions and a matrix pencil to identify individual components, then solve the orientation problem. The objectives and algorithms differ.

Ge et al. (2018). Their positive-output recovery approach uses Hermite-based population-loss identities and a favorable optimization landscape, principally in the undercomplete full-rank setting. Our method is spectral, and logarithmic-degree lifting allows k>d. We also separate sign orientation as a computational problem; Theorem 3.4 shows that this step can be hard even for identifiable parameters.

Signed-output networks. Positive output coefficients can be absorbed into the weights by ReLU homogeneity; negative coefficients cannot. Our moment argument uses

Mt=∑ℓ=1krℓuℓ⊗t,rℓ>0,M_t=\sum_{\ell=1}^k r_\ell u_\ell^{\otimes t},\qquad r_\ell>0,

and the orientation argument uses the geometry of positive planted weights. Arbitrary output signs introduce cancellation, so neither argument extends directly. We make no recovery claim for general signed-output networks, and without further assumptions that problem is likely intractable. Diakonikolas et al. (2020) prove a d(k) SQ lower bound for learning such networks under Gaussian inputs, and Goel et al. (2020) prove superpolynomial lower bounds for gradient descent. These bounds transfer to parameter recovery by SQ and gradient-based methods, since accurate parameters determine the function.

Our two main results establish hardness of sign orientation of the planted weights and polynomial-time exact recovery under positive independence without full rank. We have clarified these distinctions in Sections 4–6.

Finally, we note that concurrent works of Zheng (2026) and Diakonikolas et al. (2026) that appeared after our submission further demonstrate that approximate function learning is possible without strong geometric assumptions. Our results address a different question: why exact parameter recovery can remain hard under strong separation assumptions, and how the sign-orientation barrier can be overcome under positive independence.

W4/Q3: Scope and necessity of positive independence

Assumption 4.1 requires a margin >0 such that

\ge\eta\sum_{\ell=1}^k\alpha_\ell\|w_\ell\|_2, \qquad\alpha_\ell\ge0.$$ Equivalently, there is a unit vector q with $$\langle q,w_\ell\rangle\ge\eta\|w_\ell\|_2 \qquad\text{for every }\ell.$$ Thus the normalized directions must lie in a common spherical cap with positive margin. This covers well-conditioned full-rank networks (W2) and some structured overcomplete networks, including angularly separated directions in a common cap. It is substantially more restrictive for independent isotropic directions: a common half-space need not exist, and any separating margin may be small. We do **not** claim the assumption holds generically for random overcomplete networks. Nor do we claim that positive independence is **necessary** for efficient recovery. The hardness result shows that a weaker discrete subset-sum margin, even together with bounded norms and angular separation, does not suffice for efficient exact recovery in our setting. After recovering unoriented vectors, the remaining task is to find $$\sum_{\ell=1}^k s_\ell v_\ell=m_1, \qquad s_\ell\in\{-1,1\}.$$ A discrete margin separates sign assignments but offers no efficient way to find the correct one. Positive independence supplies the stronger geometric condition under which the convex box relaxation succeeds. Whether a different algorithm can recover parameters under substantially weaker assumptions remains open. We have clarified these regimes and the sufficiency—not necessity—of Assumption 4.1.

W5: Making the hardness reduction more self-contained

We have added an overview of the hardness reduction in Section 3. Even-order Hermite moments determine the hidden directions up to sign, while the first moment imposes a signed vector subset-sum constraint.

The reduction proceeds as follows. First, Exact Cover by 3-Sets (X3C) is reduced to signed vector subset sum. Second, randomized isolation gives a unique sign solution with inverse-polynomial probability for satisfiable instances. Third, centered-simplex replication produces planted ReLU weights with the required norm bounds, angular separation, and positive subset-sum margin.

The crucial fourth step is that the network can be evaluated without knowing the hidden signs. The construction gives public vectors Pℓ,aP_{\ell,a} and a public target Q, while the planted weights are wℓ,a∗=sℓ∗Pℓ,aw_{\ell,a}^*=s_\ell^*P_{\ell,a}. Since ReLU⁡(t)=(∣t∣+t)/2\operatorname{ReLU}(t)=(|t|+t)/2,

+\frac12\langle Q,x\rangle.$$ The right-hand side is public, allowing the reduction to answer membership queries without knowing the combinatorial solution. Exact recovery reveals the signs, from which an exact cover can be extracted. Candidate covers are verified, so unsatisfiable instances are never accepted; randomized isolation and repetition give the claimed success probability on satisfiable instances. We have added this outline around Theorem 3.4 in Section 3 and refer to Appendix B for the complete proof. ### W6/Q2: Moment degree and polynomial complexity The moment degree is not an extra assumption or a freely tuned parameter. Equation (38) specifies it from k and the angular-separation parameter : $$m = \min\left\lbrace s \in 2\mathbb{N} : s \ge 4,\quad 8s^2(k-1)\rho^{s-2} \le 1 \right\rbrace.$$ Because $|\langle u_i^{\otimes m},u_j^{\otimes m}\rangle|\le\rho^m$, this choice makes the lifted Gram matrix well-conditioned. The stronger s2s-2 condition also controls the active-gradient second moment needed for anchored regression. Equation (40) yields $$m\le 4+\frac{16}{1-\rho}\log\frac{16k}{1-\rho}.$$ For fixed <1, **m=O(k)**. Thus 3m and 6O(m) are polynomial in k. The algorithm avoids constructing the ambient dm tensor by estimating only the required contractions. The polynomial exponent depends on ; we do not claim uniform polynomial dependence on 1/(1-) as 1. We have added this explanation near the degree-selection rule in Section 4.

I thank the authors for their responses and for the clarifications, the revised manuscript addresses my questions.

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

The paper studies exact recovery of the weight vectors wℓw_\ell in a sum of kk bias-free ReLUs under Gaussian inputs. It shows identifiability when no two weights are collinear and no nonempty subset sums to zero, which is a special case of Stock & Gribonval (2023).

It then proves that recovery is hard even with bounded norms, angular separation and a subset-sum margin. The hardness result is established through a randomized reduction from signed vector subset sum to exact recovery of the ReLU parameters. Finally, under positive independence and fixed angular separation, the paper gives a polynomial-time algorithm. The algorithm has three steps:

  • implicit moment tensors recover the directions up to sign;
  • a box-constrained fit to the first moment fixes the signs;
  • a linear program recovers the weights exactly.
Critical strengths

The question is natural, and the paper locates the hardness in a clean way, identifying both a new hardness result and an efficient algorithm under more general assumptions than known before. There are multiple models of computation and assumptions one can make, and the paper does a good job explaining them. I also appreciate the detailed proof overview with adequate comparison with prior works.

Critical weaknesses

One general concern is overclaiming in introduction and contribution. The identifiability result is listed as the first contribution and called “our first main result" before Theorem 2.3. Only after stating the theorem do the authors acknowledge that its conclusion is a specialization of Stock & Gribonval (2023), which does not resolve the impression of novelty created earlier. The introduction should distinguish the known identifiability conclusion from a new setting-specific Hermite-moment proof.

Moreover, the explicit sample bound in (34) follows from the proof of Diakonikolas & Kane (2025), but the intermediate calculations are omitted. A short derivation tracking the error propagation and sample allocation would make the stated parameter dependence easier to verify.

Finally, I would appreciate a more intuitive discussion of the strength of Corollary 3.5 relative to the finite-bit hardness result. How much does the move to exact real arithmetic change the computational power of the model? Is the distinction mainly a technical issue of simulating exact Gaussian samples, or does it reflect a substantive difference in computational power?

Questions for authors

Can the algorithm run in the rational model or with finite precision? This would place the hardness and tractability results in the same model.

2 comments

We have revised the manuscript to address the reviewer's concerns regarding attribution, the sample bound, and the computational guarantees.

1. Attribution of identifiability

We have clarified in the introduction and Section 2 that Theorem 2.3 specializes the identifiability result of Stock and Gribonval (2023). Our Hermite-based proof distinguishes identification of the hidden lines from recovery of their orientations, the latter being central to our computational results. The revised text explicitly separates this existing identifiability result from our hardness and recovery contributions.

2. Derivation of Equation (34)

We have added a detailed derivation of Equation (34) in Appendix C.1 by specializing Proposition 3.2 of Diakonikolas and Kane (2025). For target order p, the construction uses p+1 independent batches of size N: one for each even source order 2,4,,2p and a fresh batch for the final compressed estimate. Thus n=(p+1)N.

The derivation tracks the common estimation error, recursive subspace error, and implicit tensor error:

a_p\le Cp\sqrt{e},\qquad \|\widehat M_p-M_p\|_F\le Ckp\sqrt{e}+e.$$ On the common preprocessing event, an independent query with directional second moments bounded by V has mean-square error at most $$C\frac{(p+1)^3dk^3V^2}{\sqrt{N\tau}}.$$ Requiring this to be at most 2 and using n=(p+1)N gives $$n\ge C\frac{(p+1)^7d^2k^6V^4}{\tau\zeta^4},$$ as stated in Equation (34). Appendix C.1 also clarifies the probability allocation and the treatment of intermediate spaces of dimension below k. We have further updated Table 1 to distinguish the unbiased Hermite source formula from the data-dependent compressed estimator used by the algorithm. **3. Strength of Corollary 3.5 relative to finite-bit hardness** We have clarified that the Gaussian real-arithmetic model is stronger than the standard finite-bit Turing model: it permits exact Gaussian samples and unit-cost arithmetic and comparisons on arbitrary real numbers, without accounting for bit complexity. The distinction therefore goes beyond the difficulty of simulating Gaussian samples, since exact arithmetic can also conceal computational costs. Our reduction nevertheless uses the same explicit public expression for the labels as the rational membership-query reduction. The underlying combinatorial obstruction remains: recovering the hidden orientations would solve the X3C instance, even with access to exact Gaussian observations. The complexity-theoretic conclusions, however, differ. Theorem 3.4 shows that efficient recovery in the rational membership-query model would imply $\mathrm{NP}\subseteq\mathrm{RP}$. Since a membership-query algorithm can generate its own rounded Gaussian inputs and query their exact labels, this hardness also applies to recovery from Gaussian samples given to polynomially many bits of precision. Corollary 3.5 extends the reduction to exact Gaussian samples in the real-arithmetic model, where efficient recovery would yield a polynomial time algorithm for X3C. We have made this distinction explicit in Section 3 and Appendix B.5. **4. Finite-precision implementation** We have clarified the extent to which the recovery algorithm admits finite-precision implementation. The moment-estimation, numerical linear-algebra, and sign-orientation stages have quantitative error guarantees. In particular, the sign-orientation step tolerates approximate optimization: if a box-feasible point has an unsquared residual within of the optimum, the recovered signs remain correct provided $$2k\varepsilon_V+2\varepsilon_m+\xi<\eta r.$$ Thus, exact optimization is not required for this stage. The main remaining difficulty is exact parameter recovery in the final anchored-regression stage. Theorem 4.2 assumes noiseless observations and an exact solver for a polynomial-size linear program. Although the preceding stages admit quantitative approximation guarantees, we have not established a complete polynomial bit-complexity bound for the algorithm with finite-precision Gaussian observations and labels. For arbitrary real-valued planted weights, exact recovery from rounded observations also requires assumptions on parameter representation and a corresponding numerical-stability analysis. We have explicitly acknowledged this limitation in Theorem 4.2 and Appendix C.3.

Thank you for addressing my concerns. I have no further questions. The paper looks pretty good to me.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.