Sublinearly Structured Deep Neural Networks Achieve Feature Learning Consistency for Compositional Functions

Sehwan Kim, Yan Sun, Faming LiangarXiv 2026 · arXiv

TL;DR

This paper bridges the gap between deep learning practice and statistical theory by proving that "sublinearly structured" deep neural networks (DNNs)—where layer widths grow slower than the training sample size—can consistently learn true underlying features and make accurate predictions. Crucially, this theoretical guarantee holds even when the network is highly over-parameterized, providing a rigorous statistical explanation for why massive models like ResNet and VGG succeed on structured data like images.

What Problem Does This Paper Address?

Despite the monumental success of deep neural networks, providing complete theoretical guarantees for why they generalize so well remains a major challenge in machine learning. From a classical statistical perspective, we expect models to achieve "consistency"—meaning that as you feed the model more data, its parameter estimates and predictions should converge to the true underlying function.

However, proving this for modern DNNs is incredibly difficult due to two main hurdles:

  1. Over-parameterization: Modern networks routinely have far more parameters than training samples ($p \gg n$), which traditionally risks severe overfitting.
  2. Non-identifiability: Many different combinations of weights and biases can produce the exact same network output, making standard parameter consistency metrics useless.

The authors tackle these challenges by shifting the focus from parameter estimation consistency to feature-learning consistency (recovering the correct directional subspaces of the weights) specifically for hierarchically compositional functions—functions built like trees or directed acyclic graphs where each piece only looks at a small, bounded number of variables.

Methods

The authors introduce the concept of a sublinearly structured DNN. In these networks, the input/output dimensions and individual hidden layer widths ($d_l$) grow sublinearly with the sample size $n$ (written as $d_l \prec n$). Crucially, because the total number of parameters depends on the product of adjacent layers ($d_l \times d_{l-1}$), the total parameter count can still vastly exceed $n$, keeping the model firmly in the over-parameterized regime.

To prove consistency, the authors use a clever theoretical detour:

  • The Surrogate Model (StoNet): They map the deterministic DNN to a Stochastic Neural Network (StoNet), which injects auxiliary Gaussian noise into the pre-activations of each layer. This turns the complex network into a Markovian composition of standard linear or logistic regressions.
  • The Optimization Bridge: They utilize the Imputation-Regularized Optimization (IRO) algorithm to analyze StoNet. They prove an asymptotic equivalence lemma showing that as $n$ grows, the empirical objective functions (energy landscapes) of the StoNet surrogate and the standard DNN converge.
  • Mathematical Proofs: By leveraging this bridge, they apply classical regression theory to the layers. They use the Davis-Kahan sin-theta theorem to demonstrate that the eigenvectors of the learned weight matrices ($w_l^\top w_l$) converge to the true population feature subspaces, ensuring feature-learning consistency.

Datasets

The paper validates its theoretical claims using a mix of synthetic simulations, structural audits of classic models, and standard benchmarks:

  • Synthetic Data: Custom-generated hierarchical compositional functions used to evaluate feature recovery and mean squared error (MSE) across varying widths and depths.
  • MNIST: A subset ($n_{train} = 4,000$) used to analyze the "double descent" and "double ascent" phenomena.
  • CelebA: An image dataset ($n_{train} = 14,000$) used to visualize facial feature extraction (e.g., detecting smiles, glasses, hats).
  • UCI Benchmarks: Real-world regression datasets including Boston Housing, Yacht, and Energy.
  • Structural Audit: The authors analyzed the standard benchmark configurations of ImageNet, CIFAR-10, and CIFAR-100 to verify that famous architectures like AlexNet, VGGNet, ResNet, and GoogLeNet mathematically qualify as sublinearly structured relative to their dataset sizes.

Key Insights and Ideas

  • Sublinear Width $\neq$ Small Models: A network can have individual layers that grow slower than $n$, yet the overall parameter count can still be massive. This allows models to remain highly expressive while maintaining statistical consistency.
  • Real-World Models are Already Sublinear: When trained on massive datasets like ImageNet ($n \approx 1.28$ million), architectures like ResNet18 are technically sublinear. For instance, ResNet18's maximum number of incoming connections to a single node is only 4,609—far smaller than $n$.
  • Demystifying Double Descent: The authors provide a feature-learning explanation for the "double descent" curve. Small hidden widths extract only dominant features. Moderate widths introduce noisy features (causing a temporary ascent in test error). Highly over-parameterized, sublinear widths finally allow the network to stably resolve subtle, low-eigenvalue features that are crucial for clean classification.
  • Beating the Curse of Dimensionality: By restricting the target domain to hierarchically compositional functions (which naturally mirrors how human images are structured—pixels form edges, edges form motifs, motifs form faces), sublinear DNNs achieve universal approximation in the large-sample limit without requiring exponentially large datasets.

Key Results

  • Subspace Convergence: Theorem 1 mathematically guarantees that the learned feature matrices recover the exact population feature spectra and eigenspaces in terms of operator norm as $n \to \infty$.
  • Robustness to Hyperparameters: In MNIST and synthetic testing, sublinear DNNs maintained stable training and test errors across a wide range of learning rates, whereas excessively wide networks were highly volatile and sensitive to optimization tuning.
  • Superior Generalization: In non-linear regression benchmarks (Table S3), sublinear architectures (e.g., depth $h=4$, width $L=150$) achieved a lower test MSE ($2.99$) than their wider counterparts ($L=1000$, test MSE $3.83$), proving that unbounded width can sometimes harm prediction accuracy.

Limitations and Future Work

  • Strict Function Class Assumptions: The theoretical guarantees rely heavily on the target function being hierarchically compositional or belonging to the Korobov space. It remains unproven whether these consistency results hold for entirely unstructured or fully chaotic data distributions.
  • Optimization Idealism: The bridge between the stochastic surrogate and standard DNNs assumes that the optimization algorithm (like SGD) successfully interpolates the training data to reach a global minimum.
  • Extension to Super-Wide Regimes: The authors note that extending this framework to analyze "benign overfitting" in infinitely wide networks (beyond the sublinear boundary) remains an open conjecture for future research.

Summary updated

Abstract

Over the past decade, deep neural networks (DNNs) have achieved remarkable success on complex machine-learning tasks, yet the theoretical foundations of their performance remain incomplete. From a statistical viewpoint, a natural question is: can DNNs attain feature-learning and prediction consistency comparable to that of classical models? While a full characterization is open, we provide positive results for a broad subclass. We establish feature-learning consistency guarantees for sublinearly structured DNNs-architectures whose input/output dimensions and number of hidden neurons grow sublinearly with the sample size-when learning hierarchically compositional target functions. Importantly, this consistency still holds even in the conventional "over-parameterized" regime where the total number of parameters exceeds the number of training samples. Empirically, sublinearly structured DNNs match or surpass wide DNNs in prediction. A structural audit further indicates that widely used convolutional neural networks (CNNs), including AlexNet, VGGNet, ResNet, GoogLeNet, are sublinearly structured on their image classification benchmarks. We further prove that the sublinearly structured DNNs achieve universal approximation for hierarchically compositional functions in the large-sample limit. Moreover, images exhibit an inherent hierarchical, compositional structure. Taken together, these results explain, through a statistical lens, why many large-scale deep learning models succeed after adequate training on massive image datasets.
BibTeX
@misc{kim2026sublinearly,
  author = {Sehwan Kim and Yan Sun and Faming Liang},
  title = {{Sublinearly Structured Deep Neural Networks Achieve Feature Learning Consistency for Compositional Functions}},
  year = {2026},
  eprint = {2606.23477},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.23477},
}
Figure