acceptodds
Under review as a conference paper at ICLR 2027

Beyond Overparameterization: Provable Learning of Input-Convex Multi-Layer Polynomial Networks with Active Queries

Abstract

The theoretical understanding of multi-layer neural networks is largely confined to overparameterized settings, which obscure parameter identifiability and incur high sample complexity. Neural tangent kernel (NTK) provides a general theory for wide networks, but does not offer efficient sample-complexity guarantees. Recent feature-learning results go beyond kernel methods for single-neuron, multi-index, and hierarchical targets. However, the analysis is often restricted to shallow or specific architectures and to the overparameterized regime. %when the target function has a genuinely deep compositional structure, obtaining sample-complexity guarantees with controlled dependence on depth remains largely open. A key reason is that most existing methods stop at learning first-layer representations, making it difficult to obtain efficient guarantees for deeper layers. We break this paradigm to achieve parameter-level recovery of deep target networks, albeit by using active data queries. Specifically, we study -layer polynomial networks with even degree- monomial activations and nonnegative higher-layer weights. This structure makes the target network input-convex, while the optimization landscape remains highly nonconvex with respect to the parameters. Leveraging input convexity and active queries, we propose ASPIRE (Active SamPling for Iterative Recovery via Eigendirections), a layerwise sampling-based diagonalization algorithm that recovers all network parameters to -accuracy with sample complexity in polynomial time. To our knowledge, this is the first parameter-recovery guarantee for deep target networks whose exponent grows only polynomially with depth, as well as the first justification for the effectiveness of using high-quality data in neural network training, with a remarkably exponential separation.

Primary area:
learning theory
Keywords:
multi-layer polynomial networks, input convexity, parameter recovery, active queries

Reviews

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

This paper studies parameter recovery of deep but polynomial networks from the active learning perspective. The target class includes bias-free networks with monomial activations, of non increasing width and with nonnegative weights after the first layer.

Their proposed algorithm learns the network layer by layer, by using function queris to estimate gradients and moment matrices from samples from selected sublevel sets to find the hidden weights.

The authors show that in polynomial time parameter recovery is possible up to arbitrary accuracy. They also establish a sample-complexity lower bound for infinite-width NTK regression on this target class and give a small synthetic recovery experiment.

Critical strengths

A substantive parameter-recovery guarantee.\textbf{A substantive parameter-recovery guarantee.} The paper gives an algorithm for recovering weights across many layers. For fixed depth and activation degree, its time and query bounds are polynomial.

An interesting algorithm.\textbf{An interesting algorithm.} The algorithm uses queries that make moment matrices reveal individual hidden directions. They then use the recovered layers to go into deeper layers of the NN. In my opinion, this is the paper's strongest technical idea.

Critical weaknesses

Are the queries needed?\textbf{Are the queries needed?} I am not convinced that the role of active queries is required. The NTK lower bound is only about one kind of passive method, but doesn't rule out passive algorithms that use the same network structure. Since the benefit of active queries is a central part of the paper’s motivation, this is a significant gap.

Very narrow setting.\textbf{Very narrow setting.} In my opinion the biggest weakness is that this theory applies to a fairly narrow setting. It needs exact answers to arbitrary queries and a known bias-free architecture with even-power activations, nonnegative later weights, and additional conditioning assumptions. Other people in the feature-learning field often ask what can be learned from randomly sampled data using GD. Here, it is unclear what survives if queries are noisy or if the target has biases, signed later-layer weights, or ReLU activations. That makes it hard for me to judge how much the result could extend.

Questions for authors
  1. I could have misunderstood but is the claimed separation specifically against infinite-width NTK regression, or against passive learning more broadly? Prop 3.7 says only the former. If the broader claim was what you meant, what rules out other passive learning methods?

  2. I am not sure how restrictive Assumption 3.5 is. Appendix H constructs weights that satisfy the spectral-gap condition, but is there a reason to expect such a gap for a broader class of networks? And generally could you please comment on the generality of your assumptions, to me they seem to strict.

4 comments
AuthorsOpenReview ↗

On the Separation, Spectral Gap, Active Queries, and Scope of Our Setting

We sincerely thank you for the thoughtful and constructive comments. We particularly appreciate the suggestions on clarifying the scope and generality of our results. Following these suggestions, we have expanded the appendices to include additional theoretical results and discussions on the spectral-gap assumption, noisy queries, and possible extensions of our framework.

Q1: Is the claimed exponential separation against the infinite-width NTK or passive learning algorithms in general?

Sorry for the confusion. Our lower bound in Proposition 3.7 is specifically for the infinite-width NTK, based on Ghorbani et al. (2021), rather than passive learning algorithms in general. More precisely, our result establishes an exponential separation in the input-dimension exponent, comparing L2+O(L)L^2+O(L) for ASPIRE with kL−1−ηk^{L-1}-\eta for the NTK, where η>0\eta>0 is arbitrarily small and fixed. We have clarified this distinction and refined the corresponding claims in the revised manuscript.

Q2: How restrictive is Assumption 3.5, and can the spectral-gap condition hold for broader network classes?

Thanks for this important question. Assumption 3.5 ensures that the spectral signatures of different neurons are sufficiently separated for stable recovery. Similar eigengap assumptions are standard in spectral tensor decomposition (Anandkumar et al., 2014). In particular, our assumption rules out certain highly symmetric cases, such as diagonal hidden-layer weight matrices with coincident spectral signatures, where the individual neurons cannot be distinguished through our spectral decomposition.

More importantly, we have added Appendix I to demonstrate that this assumption holds for a concrete class of randomly generated networks. In particular, we establish the following result:

\textbf{Proposition I.1.}\quad \text{For equal-width networks with independent weak random}\\ \text{off-diagonal couplings, Assumption 3.5 holds with}\\ \gamma=O_{k,L}(r^8\zeta^{-2}) \quad\text{with probability at least }1-\zeta. \end{gathered}$$ This shows that the spectral-gap assumption is satisfied with high probability for a nontrivial class of networks, with inverse spectral gap depending polynomially on the width $r$. Substituting this bound into Theorem 5.1 contributes only an additional $r^{O(L)}$ factor, preserving the leading $L^2$ exponent in our sample-complexity bound. ## **Q3: Are active queries necessary, and can ASPIRE be combined with gradient-based methods?** We appreciate this important question. Our main motivation is to investigate whether active queries can enable us to **fully exploit the hierarchical structure of the target network** and recover its original parameters without overparameterization. Existing approaches, including the NTK and many feature-learning methods, rely on overparameterization to varying degrees, which can make it difficult to fully exploit the target network's layerwise structure and therefore incur high sample complexity. We acknowledge that we have not proved that all other overparameterized passive-learning methods are unable to achieve sample complexity comparable to ours. **Nevertheless, existing overparameterization-based passive-learning algorithms do not provide comparable sample-complexity guarantees for general deep target networks considered in our setting.** In our approach, **active queries are essential to ASPIRE as currently designed**, since they allow us to simulate direct access to suffix networks after recovering the preceding layers. This enables sampling from carefully chosen convex sublevel sets, inducing coordinatewise sign symmetry in the latent coordinates. Consequently, the latent position and gradient moments become diagonal, allowing us to recover individual hidden directions through spectral decomposition and progressively reconstruct the original network. We also agree that gradient-based training is an important direction. In fact, **our approach could be combined with gradient descent by using the sampling-based spectral recovery procedure to provide a sufficiently accurate initialization, followed by gradient-based refinement**. Such an initialization may help avoid the difficulties of direct parameter fitting, as illustrated by the non-global local minima and fourth-order saddle points in Proposition 3.6.

Q4: How general are the architectural and oracle assumptions, particularly regarding noisy queries, biases, signed weights, and ReLU activations?

Thanks for raising these questions about the scope of our results. While our analysis focuses on a structured class of polynomial networks, it allows arbitrary fixed depth and hidden widths that may grow with the input dimension dd. We have also investigated several extensions.

Noisy queries. We have added Appendix H to extend our guarantees beyond exact function-value queries. The main technical challenge comes from noise amplification when simulating complex-valued suffix queries using real evaluations. Under additional conditioning assumptions, we establish the following result:

\textbf{Theorem H.3.}\quad \text{Under equal hidden widths and bounded inverse weights,}\\ \text{ASPIRE achieves polynomial-time parameter recovery}\\ \text{with bounded independent multiplicative query noise.} \end{gathered}$$ This provides a rigorous recovery guarantee in a noisy-query setting. **We focus on multiplicative noise because bounded additive noise can be made arbitrarily small through input rescaling: for a degree-$D$ homogeneous polynomial, querying at $t\mathbf{x}$ and dividing by $t^D$ reduces the additive noise by a factor of $t^D$.** **Signed higher-layer weights.** The nonnegativity assumption is mainly used to ensure input convexity, which enables polynomial-time sampling via Hit-and-Run. With signed higher-layer weights ($\mathbf{W}_{\ell}, \ell < L$), but positive output layer weights ($\mathbf{a}$), **the spectral identification mechanism remains applicable.** Replacing Hit-and-Run with a sampler for nonconvex sets would preserve the identification argument, although polynomial-time guarantees would no longer be ensured. Therefore, we retain the nonnegativity assumption on the higher-layer weights to guarantee polynomial-time parameter recovery. **Biases.** Polynomial networks with biases can be represented through homogenization by introducing additional constant-carrying neurons (Kileel et al., 2019; Usevich et al., 2025). This provides a relatively simple and promising route to extending our framework to networks with biases, by reducing the biased setting to the homogeneous polynomial-network setting considered in our work. **Other activations.** The central idea of constructing diagonalizable moments through active sampling may extend to smooth **even activations**. ReLU networks have a different piecewise-linear structure, for which existing reconstruction methods exploit other techniques (Rolnick & Körding, 2020; Daniely & Granot, 2023). Corollary 5.3 already shows that our recovered polynomial network can be converted into a ReLU network with a rigorous approximation guarantee. We sincerely thank you for these valuable suggestions, which have motivated us to substantially extend our theoretical analysis to cover additional settings and strengthen the generality of our results.

Thank you for the clarifications and the additional results.

My main concern is still how narrow the setting is. For the spectral gap, you now give a family of random networks where the assumption holds, but these networks only have higher layer weight matrices which are close to the identity matrix, with only weak mixing between neurons. It is still unclear to me whether the assumption holds more broadly. The noisy query result addresses my concern about exact answers only partly, although it requires all hidden layers to have the same width and adds further conditions on the weights.

I appreciate the discussion of biases, signed weights, and other activations, but it is still unclear how much of the main result extends to these settings. The response helps and I appreciate it, but I still find the setting too narrow. I will therefore keep my score at weak rejection.

We sincerely thank you for thoughtful feedback and continued engagement with our work. We greatly appreciate the opportunity to further address your concerns. In response to your latest comments, we have made substantial revisions to the manuscript and established two additional theoretical results that directly address the limitations you highlighted.

Q1. Spectral Gap Beyond Near-Identity Networks

We have substantially strengthened our spectral-gap result in Proposition I.1 (Appendix I) (see Line 3164 of the updated manuscript), showing that Assumption 3.5 holds with high probability for a much broader class of networks. Specifically, starting from a deterministic network, we prove that independently perturbing these weights by an arbitrarily small relative amount ε\varepsilon yields, with high probability, an inverse-polynomial lower bound on the relative spectral gaps after normalization. This establishes a smoothed-analysis guarantee, showing that the spectral-gap assumption is robust under small random perturbations of a broad class of positive-weight networks.

\textbf{Proposition I.1 (Smoothed Relative Spectral Gaps).}\\ \text{For any such deterministic center, }0<\varepsilon\le\tfrac12 \text{ and }0<\zeta<\tfrac12,\\ \Pr\left( \forall 1\leq\ell\leq L-2,\quad \frac{\min_{i\neq j}|\theta_{\ell,i}-\theta_{\ell,j}|} {\max_i\theta_{\ell,i}} \geq c_{k,L,K}(\varepsilon\zeta)^{C_{k,L,K}}r_\ell^{-6} \right)\geq 1-\zeta. \end{gathered}$$ **The guarantee holds uniformly over all deterministic centers whose raw higher-layer weights satisfy $\min_{u,v}(W_j^{(0)})_{uv}>0$ and $\frac{\max_{u,v}(W_j^{(0)})_{uv}}{\min_{u,v}(W_j^{(0)})_{uv}}\le K$ for every $2\le j\le L$, including centers with coincident spectral signatures.** These centers can be fully dense, with **substantial mixing between neurons**, and the perturbation magnitude $\varepsilon$ can be arbitrarily small. The constants depend only on $k,L,K$. The proof establishes quantitative anti-concentration of the spectral signatures under independent perturbations, yielding an inverse-polynomial lower bound on the relative gaps. This provides a broader justification for the spectral-gap assumption through smoothed analysis around arbitrary positive higher-layer weights with bounded within-layer ratios, without requiring proximity to the identity. ## **Q2. Noisy Queries with General Hidden-Layer Widths** We have also strengthened the noisy-query result in **Theorem H.4 (Appendix H) (see Line 3027 of the updated manuscript)**, removing the previous requirement that all hidden layers have the same width. The new theorem accommodates the general non-increasing-width architectures considered in our main result. $$\begin{gathered} \textbf{Theorem H.4 (Recovery Under Multiplicative Query Noise).}\\ \text{Under Assumptions 3.2--3.5 and H.1, for arbitrary}\\ r_1\geq r_2\geq\cdots\geq r_{L-1}\geq 2,\\ \Pr\left( \max_{1\leq\ell\leq L-1} \|\widehat{\mathbf W}_\ell-\mathbf W_\ell\|_2\leq\delta,\quad \|\widehat{\mathbf a}-\mathbf a\|_1\leq\delta \right)\geq 1-\zeta,\\ Q_{\mathrm{noisy}} =\widetilde O_{k,L}\left( (1+b^2)\gamma^{O(L)}\kappa^{O(L^2)} \left[ \frac{dr^{L^2+O(L)}}{(\zeta\delta)^{2e}} + \frac{C_{\mathrm{loc}}^{2s}r^{2L^2+O(L)}}{(\zeta\delta)^{4e}} \right] \right). \end{gathered}$$ The analysis still requires an additional local stability condition (Assumption H.1), which controls noise amplification during complex suffix-query simulation. This condition involves only adjacent weight matrices and is expressed through explicit algebraic inequalities. Once again, we sincerely thank you for your time, thoughtful feedback, and constructive suggestions
Reviewer_PZR9OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers polynomial networks with even degree-k monomial activations and LL layers on input of dimension dd and asks how many active function-value queries of a given teacher network is required for an identical student network to recover the parameters. They establish an upper bound of O~(dL2+O(L))\widetilde O(d^{L^2+O(L)}) for their sampling and reconstruction scheme ASPIRE, which is an improvement over the lower bound of Ω(dkL−1−o(1))\Omega(d^{k^{L-1}-o(1)}) that they establish for infinite width limit of NTK with passive samples.

Critical strengths
  • The paper is well written
  • The paper finds sufficient conditions under which sample complexity can be improved. Namely: polynomial nets, structure-aware reconstruction by reconstructing a matching network (in particular width has to be the same as the teacher) and active queries.
Critical weaknesses

I should start by saying thattThe technical contributions seems substantial - my main concerns are about how these results are use to make broader claims than what they support, but these should be easily fixable.

Role of overparameterization I'm somewhat confused about the negative narrative/criticism around overparameterization:

  • First of all it is unclear what role the overparameterization of NTK plays in Proposition 3.7 - is it really the cause of the discouraging lowerbound? Afterall direct polynomial interpolation also leads to O(dkL−1)O(d^{k^{L-1}}).
  • Not treating overparameterization seems more like a limitation of their framework, since their argument goes through parameter recovery (which requires the student having an identical architecture to the teacher).

I would explicitly comment in the main text on the fact that the NTK result does not rule out that feature-learning (more expressive than NTK) might avoid the double exponential lower bound.

Multiple changes at once This leads me to the second point. It is unclear what is causing the separation between the NTK lower bound and the established upper bound of ASPIRE since multiple things are changing in the setup - not only the fact that NTK is overparameterized, which the text seems to imply is the main cause for the separation. There are at least two others, namely i) the sampling scheme is changing from passive queries for NTK to active queries for ASPIRE ii) ASPIRE exploits knowledge of the structure of the network for reconstruction.

This leaves multiple questions:

  • can the double exponential lowerbound be avoided for the overparameterized setting if active queries were permitted instead of passive?
  • are active queries necessary to establish the upperbound in ASPIRE?

It might be worth stating that you find sufficient conditions with ASPIRE, but that it remains unclear which are necessary.

Sometimes misleading wording:

  • "first justification for the effectiveness of using high-quality data in neural network training with an exponential separation." I would suggest downtoning throughout. First of all the paper does not establish that active queries are necessary, and even then active queries are quite different from available of some (curated) dataset.
  • "suggesting active queries can break barriers in overparameterized regime". This seems conflicting with the result of the narrative. If this is really the belief then I would comment on the fact that the NTK lowerbound uses passive samples and that this might be the primary cause of the separation.

Minor:

  • The bounds are not uniform in depth The result establishes an improvement in the depth dependency of the exponent of dd, but not necessarily an improvement of the total complexity as the depth LL grows. Specifically, for the NTK lower bound what seems to be proven is for "fix kk, LL, then take dd sufficiently large" (which could depend on LL). I think it is important to comment on this in the main text.
Questions for authors

See weaknesses.

4 comments
AuthorsOpenReview ↗

On the Role of Overparameterization, Active Queries, and Depth Dependence

We sincerely thank you for the thoughtful and constructive comments. We particularly appreciate the suggestions on clarifying the scope of our comparison and avoiding overly broad claims. Following these suggestions, we revised the abstract and introduction to better reflect what our theoretical results establish.

Q1: Role of overparameterization. Is overparameterization responsible for the NTK lower bound? Is the matched-width requirement a limitation of our framework?

Thank you for pointing out this distinction. Our intention is to highlight that many existing approaches to learning multi-layer networks rely on overparameterization, often to make optimization more tractable and establish convergence guarantees. A representative example is the infinite-width NTK, for which Proposition 3.7 establishes a sample-complexity lower bound of Ωk,L,η(dkL−1−η)\Omega_{k,L,\eta}(d^{k^{L-1}-\eta}) for arbitrarily small fixed η>0\eta>0. Similarly, many feature-learning approaches still rely on overparameterization to approximate the target after identifying its hidden representations. Even direct polynomial interpolation can be viewed as a form of overparameterization in a broader representational sense, since it uses all polynomial coefficients to represent a target with compact hierarchical structure. We certainly do not claim that overparameterization necessarily leads to high sample complexity. Rather, we wish to emphasize that many existing approaches relying on overparameterization still face large sample-complexity bounds for deep hierarchical targets. We have refined our discussion in the revised manuscript to better reflect this distinction.

Regarding the matched-width setting, we would like to clarify that this is a stronger recovery objective rather than a limitation on the applicability of our algorithm. Indeed, our recovered network can be directly embedded into a wider student network by setting the weights associated with additional neurons to zero. Therefore, our algorithm also provides polynomial-time learning guarantees for overparameterized student networks. We hope this clarifies the motivation behind our setting and its relationship to overparameterized learning.

Q2: Multiple changes in the comparison. Can active queries help overparameterized methods overcome the lower bound? Are active queries necessary for ASPIRE?

We acknowledge that we cannot rule out the possibility that active queries could enable other overparameterized methods to achieve comparable sample complexity. However, we would like to highlight an identifiability difficulty in a natural overparameterized approach with active queries that we have considered. Specifically, after recovering the rr-dimensional hidden column space, we can write the reduced function as F(z)=g((C⊤z)⊙k)F(\mathbf z)=g((\mathbf C^\top\mathbf z)^{\odot k}). Consider the tensor lifting ψ(z)=svec⁡(z⊗k)∈RN\psi(\mathbf z)=\operatorname{svec}(\mathbf z^{\otimes k})\in\mathbb R^N, where N=(r+k−1k)N=\binom{r+k-1}{k} is the number of degree-kk monomials in rr variables. Since (ci⊤z)k=ψ(ci)⊤ψ(z)(\mathbf c_i^\top\mathbf z)^k=\psi(\mathbf c_i)^\top\psi(\mathbf z), this lifting makes the degree-kk activation linear in the higher-dimensional feature space, allowing an overparameterized representation to be learned through linear regression.

The difficulty is that the gradient information does not identify the lifted hidden subspace. To see this, consider two subspaces in RN\mathbb R^N:

  • S=span⁡ψ(c~1),…,ψ(c~r)\mathcal S=\operatorname{span}\\{\psi(\widetilde{\mathbf c}_1),\ldots,\psi(\widetilde{\mathbf c}_r)\\} is a candidate rr-dimensional lifted hidden subspace, where c~i\widetilde{\mathbf c}_i are candidate hidden directions.
  • Vz=v∈RN:J(z)⊤v∈span⁡{∇F(z)}\mathcal V_{\mathbf z}=\\{\mathbf v\in\mathbb R^N:\mathbf J(\mathbf z)^\top\mathbf v\in\operatorname{span}\{\nabla F(\mathbf z)\}\\}, where J(z)=Dψ(z)\mathbf J(\mathbf z)=D\psi(\mathbf z), is the subspace determined by the observed gradient at a nonzero query point z\mathbf z. Since J(z)\mathbf J(\mathbf z) has rank rr, we have dim⁡(Vz)=N−r+1\dim(\mathcal V_{\mathbf z})=N-r+1.

By the chain rule, the gradient equations require S∩Vz≠{0}\mathcal S\cap\mathcal V_{\mathbf z}\neq\{\mathbf 0\}. However, the dimension formula gives

\geq r+(N-r+1)-N=1.$$ Thus, this intersection condition is automatically satisfied by every candidate $r$-dimensional subspace. Consequently, **these pointwise gradient constraints cannot distinguish the true lifted hidden subspace**, regardless of how the query points are selected, when the downstream gradients at different queries are treated as independent unknowns. Regarding the second question, **active queries are essential to ASPIRE as currently designed**, since they allow us to simulate direct query access to the suffix networks after recovering the preceding layers. This enables us to sample from carefully chosen convex sublevel sets, inducing coordinatewise sign symmetry in the latent coordinates.

Q3: The claim “first justification for the effectiveness of using high-quality data in neural network training with an exponential separation” is misleading.

Sorry for the misunderstanding. Following your suggestion, we have narrowed our claim to emphasize that our work provides a concrete theoretical example of how structure-aware active sampling enables efficient end-to-end parameter recovery for deep polynomial networks.

Q4: The claim that active queries can break barriers in the overparameterized regime is potentially misleading, since the separation is established against the NTK with passive samples.

Sorry for confusing you. We broadly characterize existing approaches to learning multi-layer networks, including the NTK and many feature-learning methods, as overparameterization-based approaches, since they rely on overparameterization to varying degrees. We have discussed this point in more detail in Q1.

More importantly, we believe that the separation primarily comes from our ability to exploit the target network's hierarchical structure, which enables substantially lower sample complexity. When we say that our approach breaks the barriers of existing overparameterization-based methods, we mean that overparameterized representations often make it difficult to fully exploit the layerwise structure of the target network, even with the help of active queries. We have discussed this difficulty for a natural class of overparameterized approaches in Q2.

Q5: The complexity bounds are not uniform in depth. The improvement concerns the exponent of the input dimension rather than necessarily the total complexity as depth increases.

We appreciate this clarification. Our complexity bounds are established for fixed k,Lk,L, and the constants hidden in O~k,L\widetilde O_{k,L} may depend on the polynomial degree kL−1k^{L-1}. Our intended comparison concerns how the exponent of the input dimension dd scales with depth LL: it grows polynomially as L2+O(L)L^2+O(L) for ASPIRE, compared with exponentially as kL−1−o(1)k^{L-1}-o(1) for NTK. Thus, the separation in the input-dimension exponents becomes more pronounced as LL increases. We have clarified this distinction in the revised manuscript.

We sincerely thank you again for these valuable suggestions. They helped us narrow the scope of our claims and present the theoretical contribution more precisely.

We thank for reviewers for their clarifying response which largely addresses my comments.

As Reviewer 1iaS also pointed out it is unclear from the result whether active queries are necessary, so it is worth down-toning statements like: "This remarkable exponential separation provides a concrete theoretical demonstration of the power of high-quality data selected through active sampling"

Similarly, it is also difficult to verify the changes since they are not highlighted in the updated manuscript (e.g., where has it been mentioned that the bounds are not uniform in depth, so that the total complexities cannot be compared directly?).

We sincerely thank you for the helpful suggestions. We have now highlighted all revised and newly added parts of the manuscript in red to facilitate verification.

Q1. The Role of Active Queries

We have narrowed both the Abstract and Introduction (Lines 12–30 and 80–99). Specifically, we have replaced the claim that our exponential separation demonstrates the power of high-quality data selected through active sampling with a more precise statement emphasizing how our algorithm exploits the compositional structure of deep networks to achieve efficient parameter recovery. We have also clarified that the separation is specifically against the infinite-width NTK, rather than passive learning algorithms in general.

Q2. Dependence on Network Depth

We have clarified this point following Theorem 5.1 (Lines 398–402). We primarily consider the regime where k,Lk,L are fixed and d,rd,r are sufficiently large, focusing on the exponents of the input dimension and hidden width.

We agree that our bounds are not uniform in depth. When LL grows with dd, the hidden k,Lk,L-dependent factors may dominate, so our results do not imply a separation in this regime. However, for each fixed k,Lk,L, the sample complexities can still be compared asymptotically. In particular, for the constant-width target constructed in Appendix J.2, ASPIRE requires O~k,L(dL2+O(L))\widetilde{O}_{k,L}(d^{L^2+O(L)}) queries, whereas the NTK requires Ωk,L,η(dkL−1−η)\Omega_{k,L,\eta}(d^{k^{L-1}-\eta}) samples.

We thank the reviewer again for these constructive suggestions.

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

The paper studies parameter recovery for depth-L, bias-free polynomial networks. The networks have even monomial activations σ(t)=tkσ(t) = t^k, k≥4k ≥ 4, non-increasing layer widths, a single output, and entrywise nonnegative weights from the second layer onward. Under these conditions the network is convex in its input, while the fitting problem remains nonconvex in the parameters. The learner has active query access: it can evaluate the target exactly at arbitrary inputs, and the goal is to recover a network of the same architecture (exact parameterization).

The algorithm works layer by layer. For each layer, Stage I estimates the column space of WℓW_ℓ from suffix gradients obtained through directional-derivative interpolation. Stage II (ASPIRE) then resolves the remaining rotational ambiguity. It samples approximately uniformly from a convex sublevel set of the suffix network using "Hit-and-Run", and jointly diagonalizes the matrices of the sample positions and of the gradients. The sign symmetry induced by the even activation makes both moments diagonal in the basis. Access to deeper "suffix" networks is simulated by inverting the recovered "prefix" through complex-valued inputs. The last hidden layer and the output weights are recovered separately from two Hessians.

Theorem 5.1 states that all parameters are recovered to accuracy δδ with O~(dr+rL2+O(L)δ−2e)Õ(dr + r^{L^2+O(L)} δ^{−2e}) queries, up to condition-number and spectral-gap factors, in polynomial time for fixed kk and LL. This compares with dkL−1d^{k^{L−1}} for unstructured polynomial interpolation, and with a lower bound of the same order for the infinite-width NTK (Proposition 3.7). Corollaries convert the guarantee into Gaussian prediction error and into a ReLU approximation.

Critical strengths
  • The paper targets parameter-level recovery of networks deeper than two or three layers, with a sample and stability analysis. Most feature-learning guarantees stop at prediction error.
  • The core mechanism is simple and well motivated. The illustrative example in Section 6.1 clarifies how the sign symmetry of the sampling distribution diagonalizes both matrices, which helps in understanding the algorithm.
  • The resulting query complexity has an exponent of d that grows polynomially rather than exponentially with depth. This improves on unstructured interpolation and on the kernel lower bound in Proposition 3.7.
  • The assumptions are natural and are shown to be non-vacuous.
Critical weaknesses
  • Clarity of presentation. A few sections of the main text are a bit hard to follow, the exposition of the underlying algorithm could be more intuitive.

    • The notation at the start of Section 3 (prefix representations, suffix polynomials, FℓF_ℓ) is introduced without much intuition, and the operation u⊙ku^{⊙k} is not defined.
    • The “suffix oracles” paragraph in Section 4.1 relies on notation and terminology that has not been motivated, which obscures the idea.
    • The Stage II description in Section 4.2 is dense with compound terminology (“latent coordinates induced by CℓC_ℓ,” “identifiable spectral structure,” position and gradient moments). The basic idea, controlling the distribution of φℓ(x)φ_ℓ(x) and using two moments to resolve the rotational ambiguity, could be stated more directly.
    • Section 4.3 opens with “the final suffix has coincident spectral signatures,” which is difficult to parse without further explanation.
    • Key components, such as the Hit-and-Run sampler and the resulting sampling distribution, are described only in the appendix.
    • The proofs are long and could benefit from reorganization. For example, Proposition E.1 and its proof span almost six pages of technical arguments.
  • Positioning with respect to closely related work. Several directly relevant lines of work are not cited, and the paper does not explain what is new relative to them.

    • Fiedler et al. (2023) use active queries to approximate the matrix subspace spanned by (entangled) network weights and to identify deep networks with non-increasing architectures.
    • Daniely & Granot (2023) give an exact polynomial-time membership-query algorithm for three-layer ReLU networks.
    • Canales-Martínez et al. (2024) extract the parameters of deep ReLU networks layer by layer with a polynomial number of queries and polynomial time.
    • Beyond the overparameterized regime, learning deep hierarchical targets has been studied for networks with quadratic activations (Allen-Zhu & Li, 2023). Algorithms polynomial in the input dimension exist for deep ReLU networks (Chen, Klivans & Meka, 2021).

The framing that existing theory is “largely confined to overparameterized settings” should be lightened.

  • Scope of the assumptions. Assumption 3.5 (uniform relative spectral gap) is central but not very easy to interpret. Its dependence on depth, degree, and width, and its effect on the bounds through γ, are not discussed.

  • Comparison with other learning approaches. Proposition 3.7 shows that learning the target class with the infinite-width NTK requires on the order of dkL−1d^{k^{L−1}} samples. This is a lower bound for fixed kernel methods only, and the paper offers no comparison with other learning algorithms. The abstract presents the result as the “first justification for the effectiveness of using high-quality data in neural network training, with a remarkably exponential separation”. This separation is established only against the NTK. As acknowledged in Appendix I.2, the lower bound does not rule out passive feature-learning algorithms. The claim in the abstract and introduction should be narrowed to a separation from kernel methods, or supported by a result that applies to passive learners more generally.

    • Corollary 5.2 is stated in a non-standard form.
    • Corollary 5.3 (conversion to ReLU networks) is presented in a single sentence, without explaining how the ReLU weights are constructed, how the approximation error is controlled.
Questions for authors
  • The introduction states that prior feature-learning results beyond the kernel regime are restricted to shallow or specific architectures. Could you be more precise about which architectures and which limitations, considering the suggested references?
  • Does the claimed exponential separation hold against passive learning algorithms in general, or only against the NTK?
  • Do the results extend to multi-output networks, as would be needed for operator-learning applications?
  • Could you give an intuitive explanation of the prefix and suffix polynomials, and define u⊙ku^{⊙k}?
  • Could you explain Assumption 3.5 more clearly? Which non-identifiable cases does it rule out, beyond the text description? Does γγ depend on the depth LL, the degree kk, or the widths? How does γ affect the final bounds?
  • In Stage II, what exactly are the “latent coordinates induced by CℓC_ℓ”? What does “coincident spectral signatures” mean in Section 4.3?
  • What sources of error does the analysis account for? How do errors in the recovered earlier layers propagate to the later layers, and what prevents them from compounding?
  • Could you state Corollary 5.2 in terms of the number of samples and compare it with standard statistical baselines?
  • How are the ReLU weights in Corollary 5.3 constructed, how is the approximation error handled?
  • Does the algorithm apply to networks that are not input-convex (with signed weights)?
  • Relative to Ge et al. (2018), Fiedler et al. (2023), Daniely & Granot (2023), and Canales-Martínez et al. (2024), can you clarify the novelty of the algorithm and proofs?

References cited in the review

  • Fiedler, C., Fornasier, M., Klock, T., & Rauchensteiner, M. (2023). Stable recovery of entangled weights: Towards robust identification of deep neural networks from minimal samples. Applied and Computational Harmonic Analysis, 62.
  • Daniely, A., & Granot, E. (2023). An exact poly-time membership-queries algorithm for extracting a three-layer ReLU network. ICLR 2023.
  • Canales-Martínez, I. A., Chávez-Saab, J., Hambitzer, A., Rodríguez-Henríquez, F., Satpute, N., & Shamir, A. (2024). Polynomial time cryptanalytic extraction of neural network models. EUROCRYPT 2024.
  • Allen-Zhu, Z., & Li, Y. (2023). Backward feature correction: How deep learning performs deep (hierarchical) learning. COLT 2023.
  • Chen, S., Klivans, A. R., & Meka, R. (2021). Learning deep ReLU networks is fixed-parameter tractable. FOCS 2021.
5 comments

We sincerely thank you for the careful reading and constructive suggestions. We particularly appreciate the comments on the clarity of our notation and algorithm, the interpretation of our assumptions, and the positioning of our contributions. We have revised our manuscript following your suggestions. We address each point below.

Q1: Could you give an intuitive explanation of the prefix and suffix polynomials, and define u⊙k\mathbf{u}^{\odot k}?

Since our goal is to recover a multi-layer network layer by layer, it is natural to divide the network into two parts at any given hidden layer. The prefix network treats all preceding layers as a single mapping from the original input to an intermediate representation, while the suffix network treats the current and subsequent layers as a single mapping from this representation to the final output. Thus, we can write f⋆(x)=Fℓ(ϕℓ(x))f^\star(\mathbf{x})=F_\ell(\phi_\ell(\mathbf{x})), which facilitates our layerwise recovery procedure. Here, u⊙k\mathbf{u}^{\odot k} denotes the elementwise kk-th power of u\mathbf{u}, i.e., (u⊙k)i=uik(\mathbf{u}^{\odot k})_i=u_i^k. We have clarified these definitions and their intuition in Section 3.

Q2: In Stage II, what are the “latent coordinates induced by Cℓ\mathbf{C}_{\ell} ”? What does “coincident spectral signatures” mean in Section 4.3?

Thanks for this request for clarification. We have revised Sections 4.2–4.3 to explain these concepts more explicitly.

First, after recovering the column space of Wℓ\mathbf{W}_\ell, we can write Wℓ=BℓCℓ\mathbf{W}_\ell=\mathbf{B}_\ell\mathbf{C}_\ell, where Bℓ\mathbf{B}_\ell is an orthonormal basis of the recovered subspace and Cℓ\mathbf{C}_\ell is an unknown invertible matrix. For a suffix input y\mathbf{y}, the reduced coordinates are z=Bℓ⊤y\mathbf{z}=\mathbf{B}_\ell^\top\mathbf{y}, while the latent coordinates are the neuron preactivations u=Wℓ⊤y=Cℓ⊤z\mathbf{u}=\mathbf{W}_\ell^\top\mathbf{y}=\mathbf{C}_\ell^\top\mathbf{z}. Our goal in Stage II is to recover the column directions of Cℓ\mathbf{C}_\ell.

By coincident spectral signatures, we mean that two or more neurons have identical values of θℓ,i:=E[Uℓ,i2]E[(∂ih(ℓ)(Uℓ))2]\theta_{\ell,i}:=\mathbb{E}[U_{\ell,i}^2]\mathbb{E}[(\partial_i h^{(\ell)}(\mathbf{U}_\ell))^2], where Uℓ∼Unif(Hℓ)\mathbf{U}_\ell\sim\mathrm{Unif}(\mathcal{H}_\ell). This leads to repeated eigenvalues in the moment product Σg,ℓΣx,ℓ\Sigma_{g,\ell}\Sigma_{x,\ell}, preventing the corresponding individual hidden directions from being distinguished by eigendecomposition.

Q3: Positioning with respect to closely related work. Several relevant references are missing, the novelty of the algorithm and proofs should be clarified, and the framing of existing theory as largely confined to overparameterization should be softened.

We have expanded Section 2 to better position our contribution relative to existing work and clarify the novelty of our algorithm and analysis.

Our main contribution is a rigorous end-to-end parameter-recovery guarantee for standard fully connected deep polynomial networks. For fixed depth and activation degree, our algorithm achieves polynomial complexity and running time in both the input dimension and hidden widths, even when the widths scale as O(d)O(d). The key technical novelty lies in combining simulated suffix queries, active sampling from convex sublevel sets, and layerwise spectral decomposition, together with a stability analysis that controls error propagation across layers.

We clarify the differences from closely related works as follows. Ge et al. (2018) primarily consider shallow networks, without addressing end-to-end recovery in deeper architectures. Fiedler et al. (2023) establish stable recovery of entangled weights in deep networks, but recovering the original parameters requires heuristic layer attribution and optimization steps without complete theoretical guarantees. Daniely & Granot (2023) provide rigorous polynomial-time membership-query algorithms for two-layer and certain three-layer ReLU networks, but their guarantees do not extend to arbitrary depth. Canales-Martínez et al. (2024) study deeper ReLU networks, but assume that neuron signatures are already available and rely in part on heuristic arguments for sign recovery. Allen-Zhu & Li (2023) establish hierarchical feature learning under an information-gap assumption, using an architecture with skip connections and layerwise output aggregation that allows intermediate features to contribute directly to the output. Chen, Klivans & Meka (2021) establish fixed-parameter tractability for deep ReLU networks, but their complexity depends exponentially on network parameters, including the number of hidden neurons. Thus, their guarantees do not yield polynomial-time learning when the hidden widths grow with dd, as allowed in our setting.

Q4: The introduction states that prior feature-learning results beyond the kernel regime are restricted to shallow or specific architectures. Could you be more precise about which architectures and limitations?

Thank you for requesting this clarification. We revised the introduction and Section 2 to specify the architectural restrictions in the cited works. Allen-Zhu & Li (2023) study networks with skip connections and layerwise output aggregation under an information-gap assumption; Wang et al. (2024) consider three-layer hierarchical polynomial targets; and Ren et al. (2026) analyze a random hierarchy model. Our work instead establishes end-to-end parameter recovery for standard fully connected deep polynomial networks. We adjusted the wording to make this distinction more precise.

Q5: Assumption 3.5 is difficult to interpret. Which non-identifiable cases does it rule out? How does γ\gamma depend on depth, degree, and width, and how does it affect the complexity bounds?

We appreciate this important suggestion. To make Assumption 3.5 more interpretable, we expanded the discussion after its statement and added Appendix I, which provides both concrete examples and quantitative guarantees.

Similar eigengap conditions are standard in spectral tensor decomposition, where eigenvalue separation ensures stable recovery under perturbations (Anandkumar et al., 2014). In our setting, Assumption 3.5 requires the normalized spectral signatures of distinct neurons to be separated by at least γ−1\gamma^{-1}, ensuring stable recovery of their directions from the moment matrices. It rules out spectral degeneracies caused by symmetries between neurons, which can lead to non-identifiability. To illustrate the significance of this condition, we added Proposition I.4, which explicitly constructs a network with non-identifiable first-layer parameters and coincident spectral signatures.

More importantly, we have substantially strengthened Proposition I.1 to show that Assumption 3.5 holds with high probability for a much broader class of networks. Specifically, starting from a deterministic network, we prove that independently perturbing each entry by Unif[−εw‾j,εw‾j]\mathrm{Unif}[-\varepsilon\underline{w}_j,\varepsilon\underline{w}_j], for any 0<ε≤1/20<\varepsilon\le1/2, yields a high-probability inverse-polynomial lower bound on the relative spectral gaps. This establishes a smoothed-analysis guarantee:

\textbf{Proposition I.1 (Smoothed Relative Spectral Gaps).}\\ \text{For arbitrary non-increasing hidden widths and any }0<\zeta<\tfrac12,\\ \text{the independently perturbed and normalized network satisfies}\\ \Pr\left( \forall 1\leq\ell\leq L-2,\quad \frac{\min_{i\neq j}|\theta_{\ell,i}-\theta_{\ell,j}|} {\max_i\theta_{\ell,i}} \geq c_{k,L,K}(\varepsilon\zeta)^{C_{k,L,K}}r_\ell^{-6} \right)\geq 1-\zeta. \end{gathered}$$ We have also made its effect on complexity explicit in Theorem 5.1, where $\gamma$ contributes a factor of $\gamma^{O(L)}$. Consequently, the polynomial spectral-gap bound can be absorbed into the polynomial dependence on the hidden width $r$. ## **Q6: What sources of error does the analysis account for? How do errors in earlier layers propagate, and what prevents them from compounding?** Thank you for this question. Following your suggestion, we clarified the error-propagation mechanism in Section 6.2 and organized the corresponding technical analysis in Appendices B–G. The main errors arise from four sources: 1. **Prefix inversion error:** Since previously recovered weights are approximate, the simulated suffix queries are not exact, introducing a multiplicative error $\xi_\ell\lesssim\kappa^{O(\ell)}r^{\ell/2}\varepsilon_{<\ell}$ (Lemma D.3). 2. **Sampling error:** Hit-and-Run uses the approximate suffix oracle and runs for finitely many steps, so the resulting sampling distribution differs from the desired uniform distribution by a total variation error $\nu$. This introduces bias into the moment estimates (Lemma B.4). 3. **Moment estimation error:** Finite samples and approximate gradient evaluations introduce additional errors. Combining these with the sampling error, we obtain relative accuracy $\eta$ for both moment matrices using $\widetilde O(r^2\eta^{-2})$ samples (Lemmas B.6–B.7). 4. **Spectral perturbation error:** Errors in the moment matrices perturb their eigenvectors. Under the spectral-gap assumption, this perturbation is controlled by $O_{k,L}(\gamma\kappa^{O(1)}r^3\eta)$, allowing stable recovery of individual hidden directions (Lemma A.6). These errors accumulate across layers because the recovery of each layer depends on the accuracy of all preceding layers. We control this propagation by imposing progressively tighter accuracy requirements on earlier layers. The resulting backward accuracy recurrence, together with the sampling and moment-estimation costs, yields the final complexity bound in Theorem 5.1.

Q7: Comparison with other learning approaches. Does the claimed exponential separation hold against passive learning algorithms in general, or only against the NTK? Could Corollaries 5.2 and 5.3 be explained more clearly?

Sorry for confusing you. We would like to clarify that our exponential separation is against the NTK, not passive learning algorithms in general. In particular, Proposition 3.7 establishes a lower bound only for the infinite-width NTK and does not rule out all passive learning algorithms.

We also clarified Corollary 5.2 as an active-query guarantee for Gaussian prediction error, with query complexity O~k,L(dr+rL2+O(L)γO(L)κO(L2)ε−e)\widetilde O_{k,L}(dr+r^{L^2+O(L)}\gamma^{O(L)}\kappa^{O(L^2)}\varepsilon^{-e}). For Corollary 5.3, we provided an explicit ReLU construction in Appendix G by replacing monomial activations with piecewise-linear interpolants. The interpolation errors are controlled using Lipschitz bounds and Gaussian tails.

Q8: Could you state Corollary 5.2 in terms of the number of samples and compare it with standard statistical baselines?

Thank you for this suggestion. We clarified the statement of Corollary 5.2 to emphasize that the algorithm achieves Gaussian squared prediction error at most ε\varepsilon using O~k,L(dr+rL2+O(L)γO(L)κO(L2)ε−e)\widetilde O_{k,L}(dr+r^{L^2+O(L)}\gamma^{O(L)}\kappa^{O(L^2)}\varepsilon^{-e}) samples.

For comparison, unrestricted degree-qq homogeneous polynomial regression, where q=kL−1q=k^{L-1}, involves (d+q−1q)=Oq(dq)\binom{d+q-1}{q}=O_q(d^q) coefficients. More directly, Proposition 3.7 establishes an Ωk,L,η(dq−η)\Omega_{k,L,\eta}(d^{q-\eta}) sample lower bound for the infinite-width NTK at constant prediction error. Here, η>0\eta>0 is arbitrary.

Q9: How are the ReLU weights in Corollary 5.3 constructed, and how is the approximation error handled?

We appreciate this suggestion. To make Corollary 5.3 more concrete, we provided an explicit construction and error analysis in Appendix G.

Specifically, we replace each activation tkt^k with a piecewise-linear interpolant PM(t)=1+∑j=0MbjReLU⁡(t−tj)P_M(t)=1+\sum_{j=0}^{M}b_j\operatorname{ReLU}(t-t_j), where bjb_j are the slope changes at the interpolation knots. The resulting ReLU weights and biases are obtained directly from the recovered polynomial weights.

The interpolation error is Ok(M−2)O_k(M^{-2}) on [−1,1][-1,1]. Lipschitz bounds control its propagation through the layers, while Gaussian tails handle inputs outside the bounded region. More precisely, the squared approximation error is bounded by Ck,L(R2qM−4+re−R2/4)C_{k,L}(R^{2q}M^{-4}+re^{-R^2/4}), where q=kL−1q=k^{L-1}. Choosing R=Ok,L(log⁡(r/ε))R=O_{k,L}(\sqrt{\log(r/\varepsilon)}) and M=O~k,L(ε−1/4)M=\widetilde O_{k,L}(\varepsilon^{-1/4}) yields prediction error at most ε\varepsilon, without additional target queries.

Q10: Do the results extend to multi-output networks, as would be needed for operator-learning applications?

We appreciate this question, particularly its relevance to operator learning. For multiple outputs, one possible extension is to recover the shared hidden layers using a single output coordinate satisfying the required assumptions, and then recover the remaining output weights through linear systems. Alternatively, constructing an artificial scalar readout across multiple outputs may yield a better-conditioned and more robust algorithm.

Q11: Does the algorithm apply to networks that are not input-convex, for example, networks with signed higher-layer weights?

Thank you for this insightful question. Following your suggestion, we added a discussion in Appendix I to distinguish the assumptions needed for spectral identification from those needed for efficient sampling.

The nonnegativity of the higher hidden-layer weights is not essential for spectral identification, but is necessary for guaranteeing polynomial-time parameter recovery with polynomial sample complexity. If output weights are positive, the relevant sublevel sets remain compact, though not necessarily convex. In this case, our spectral identification procedure remains valid if Hit-and-Run is replaced by a sampler for nonconvex sets, but we can no longer guarantee polynomial-time parameter recovery with polynomial sample complexity. We therefore retain nonnegativity in the main theorem to ensure efficient recovery. Removing the convexity assumption while retaining efficient parameter recovery is an interesting direction for future work.

We sincerely thank the reviewer again for the constructive feedback. These suggestions helped us improve the presentation, clarify the scope of our theoretical guarantees, and better position our contributions relative to existing work.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.