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

This paper investigates whether deep neural networks (DNNs) can achieve feature-learning consistency—the ability to reliably identify underlying features in data—similar to classical statistical models. While DNNs are widely successful, their theoretical foundations, particularly in the over-parameterized regime where parameters outnumber samples, remain incomplete. The authors seek to bridge this gap by analyzing a specific class of architectures called sublinearly structured DNNs.

The authors define sublinearly structured DNNs as architectures where the input/output dimensions and the number of hidden neurons grow sublinearly relative to the sample size ($n$). They utilize a "Stochastic Neural Network" (StoNet) as a surrogate model, which treats the network as a composition of linear or logistic regressions with auxiliary noise. By proving that the StoNet and standard DNNs share an asymptotically equivalent energy landscape, the authors transfer theoretical consistency results from the StoNet to the DNN. They also perform a structural audit of popular architectures like ResNet and VGGNet, confirming they satisfy these sublinear constraints on standard image benchmarks.

The study establishes that sublinear DNNs achieve feature-learning consistency for hierarchically compositional functions—functions built from low-dimensional modules arranged in tree or DAG structures. Crucially, this consistency holds even when the network is heavily over-parameterized. The authors also demonstrate that these networks achieve universal approximation in the large-sample limit. Empirically, these sublinear models perform as well as or better than wider, less constrained networks. The results suggest that the success of large-scale models on massive datasets is partly due to their ability to exploit the inherent hierarchical structure of data, such as images, through this sublinear organization.