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. We break this paradigm to achieve parameter-level recovery of deep target networks, albeit by using active data queries. Specifically, we study L-layer polynomial networks with even degree-k 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 \textbf{ASPIRE} (\textbf{A}ctive \textbf{S}am\textbf{P}ling for \textbf{I}terative \textbf{R}ecovery via \textbf{E}igendirections), a layerwise sampling-based diagonalization algorithm that recovers all network parameters to δ-accuracy with sample complexity $ \widetilde O_{k,L}\left(d^{L^2+O(L)}δ^{-2e}\right) $ in polynomial time. To our knowledge, this is the \emph{first} parameter-recovery guarantee for deep target networks whose exponent grows only polynomially with depth, as well as the \emph{first} justification for the effectiveness of using high-quality data in neural network training, with a remarkably \emph{exponential} separation.
Related
- Provable Guarantees and Efficient Learning of Structural Equation Models with Latent Confounders
- On the Sample Complexity of Active Learning with Membership Queries
- Learning Provable Neural Network Observer for Uncertain Dynamical Systems
- Polynomial Residual Networks are Generically Identifiable
- Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks
BibTeX
@misc{tang2026beyond,
title = {{Beyond Overparameterization: Provable Learning of Input-Convex Multi-Layer Polynomial Networks with Active Queries}},
author = {Jinqi Tang and Qian Chen and Shihong Ding and Cong Fang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04999},
eprint = {2610.04999},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04999},
}
RIS
TY - UNPB
TI - Beyond Overparameterization: Provable Learning of Input-Convex Multi-Layer Polynomial Networks with Active Queries
AU - Jinqi Tang
AU - Qian Chen
AU - Shihong Ding
AU - Cong Fang
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.04999
UR - https://arxiv.org/abs/2610.04999
AB - 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. We break this paradigm to achieve parameter-level recovery of deep target networks, albeit by using active data queries. Specifically, we study L-layer polynomial networks with even degree-k 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 \textbf{ASPIRE} (\textbf{A}ctive \textbf{S}am\textbf{P}ling for \textbf{I}terative \textbf{R}ecovery via \textbf{E}igendirections), a layerwise sampling-based diagonalization algorithm that recovers all network parameters to δ-accuracy with sample complexity $ \widetilde O_{k,L}\left(d^{L^2+O(L)}δ^{-2e}\right) $ in polynomial time. To our knowledge, this is the \emph{first} parameter-recovery guarantee for deep target networks whose exponent grows only polynomially with depth, as well as the \emph{first} justification for the effectiveness of using high-quality data in neural network training, with a remarkably \emph{exponential} separation.
ER -