- 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
The paper gives an algorithm for recovering weights across many layers. For fixed depth and activation degree, its time and query bounds are polynomial.
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
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.
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
-
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?
-
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
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 . 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 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
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) for ASPIRE with kL−1−η for the NTK, where η>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.