Summary
Training very deep neural networks usually requires many examples, making it hard to figure out the exact network parameters. This paper studies a special kind of deep network where the output is made up of polynomial parts and the network is input-convex, a property that helps in analysis. The authors introduce an algorithm called ASPIRE that actively selects the right inputs to ask about, allowing it to efficiently and accurately recover the network’s parameters. This breaks new ground by providing guarantees on learning deep networks without needing excessive data, especially thanks to using carefully chosen queries.
What this means in practice
- •For machine learning engineers: Use the ASPIRE algorithm to efficiently recover parameters of deep polynomial networks with fewer training examples by selecting informative inputs.
- •For data scientists in finance: Improve modeling of convex pricing or risk models by actively identifying parameters of input-convex polynomial networks powering such predictions.
A theory result. No direct application yet.
Authors
Jinqi Tang, Qian Chen, Shihong Ding, Cong Fang
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.