Model Releases
Beyond Overparameterization: Provable Learning of Input-Convex Multi-Layer Polynomial Networks with Active Queries
arXiv:2610.04999v1 Announce Type: new Abstract: The theoretical understanding of multi-layer neural networks is largely confined to overparameterized settings, which obscure parameter identifiability
arXiv:2610.04999v1 Announce Type: new 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 extbf{ASPIRE} (extbf{A}ctive extbf{S}amextbf{P}ling for extbf{I}terative extbf{R}ecovery via extbf{E}igendirections), a layerwise sampling-based diagonalization algorithm that recovers all network parameters to elta-accuracy with sample complexity widetilde O_{k,L}left(d^{L^2+O(L)}elta^{-2e}right) 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.
Related
- Linear Independence of Polynomial Compositions and Identifiability of Deep Neural Networks
- Feature Learning in Wide Neural Networks under muP: Identifiability and Sparse-Dictionary Decomposition of the Mean-Field Limit
- COFM: Consistent Optimal Transport Flow Matching via Partially Input Convex Neural Networks
- Monotonic Kolmogorov-Arnold Networks: A Theoretical and Empirical Study of Monotonicity as an Inductive Bias
Source: arXiv cs.LG | 2026-10-06