The success of neural networks is largely attributed to their ability to learn useful representations from training data. However, known results that prove a computational advantage of learned features over fixed ones are restricted to specific input distributions. We settle the COLT open question of Feldman, Kamath, and Srebro (2026) by showing that this advantage can persist in the distribution-free setting. We construct a family of hypothesis classes that can be efficiently learned by a natural gradient-based algorithm on a two-layer ReLU network, but cannot be represented by linear predictors over any fixed feature map with polynomial dimension (and runtime). Specifically, for any sufficiently small error and any sufficiently large runtime budget R (depending on the error), there exists a hypothesis class that the neural network learns under any input distribution to the desired expected classification error in time at most R, while the dimension complexity (governing the dimension needed by linear predictors) is superpolynomial in R.
Figures & tables
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Hyperparameter
Role
Choice
B
Stage-1 batch size
⌈C0(m/ε)4⌉
J
Neurons per block
⌈exp(C03m2/3log2(m/ε))⌉
κ
Initial weight scale
C0m2log(m/ε)1
σ
Stage-1 noise standard deviation
C0logBm2
Rout
Output-layer projection radius
C0log(1/ε)
T
Stage-2 steps
⌈ε2C03m5Jlog2(1/ε)⌉
Appendix
Table 1: Hyperparameters of Algorithm , where C0>0 is a universal constant chosen in the proof.
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
Neural networks can leverage feature superposition to encode more concepts than dimensions, but cross-feature interference constrains the linear accessibility of simultaneously active features. By framing linear accessibility as a compressed sensing problem, we derive high-probability bounds for fixed supports under subgaussian noise, proving the sufficient dimension scales linearly (d=Oε(klogm)) rather than prior worst-case quadratic limits. We characterize the asymmetry between active and inactive interference and the trade-off between interference and observation-noise budgets. We then validate these bounds across system parameters through Gaussian-tail approximations. We also introduce IHT-SAE, which uses learned iterative refinement to improve feature recovery beyond the limits of linear availability. These results quantify the geometric constraints of the linear representation hypothesis, providing a framework for evaluating sparse autoencoders, compositional generalization, and neural interpretability.
Enrico Vompa
Applied Artificial Intelligence Group Tallinn University of Technology, Estonia
Neural learners for classification and regression are often criticized as black boxes. We propose a probabilistic decomposition of neural learners that accounts for heterogeneous predictability across the feature space. A training procedure combining the EM algorithm, stochastic gradient descent, and maximum likelihood estimation is developed to jointly learn the predictable component and an input-dependent reliability score. We show that the optimal decomposed learner recovers the response distribution within the predictable component, while the reliability score characterizes the predictability of individual observations. We further extend the framework to incorporate localized feature transformations. Experiments on synthetic and real-world datasets demonstrate the effectiveness of the proposed framework.
Zelong Bi
Department of Mathematics & Statistics University of New South Wales High St Kensington NSW 2052 Australia
Over the past decade, deep learning has proven to be a highly effective tool for learning meaningful features from raw data. However, it remains an open question how deep networks perform hierarchical feature learning across layers. In this work, we attempt to unveil this mystery by investigating the structures of intermediate features. Motivated by our empirical findings that linear layers mimic the roles of deep layers in nonlinear networks for feature learning, we explore how deep linear networks transform input data into output by investigating the output (i.e., features) of each layer after training in the context of multi-class classification problems. Toward this goal, we first define metrics to measure within-class compression and between-class discrimination of intermediate features, respectively. Through theoretical analysis of these two metrics, we show that the evolution of features follows a simple and quantitative pattern from shallow to deep layers when the input data is nearly orthogonal and the network weights are minimum-norm, balanced, and approximate low-rank: Each layer of the linear network progressively compresses within-class features at a geometric rate and discriminates between-class features at a linear rate with respect to the number of layers that data have passed through. To the best of our knowledge, this is the first quantitative characterization of feature evolution in hierarchical representations of deep linear networks. Empirically, our extensive experiments not only validate our theoretical results numerically but also reveal a similar pattern in deep nonlinear networks which aligns well with recent empirical studies. Moreover, we demonstrate the practical implications of our results in transfer learning. Our code is available at https://github.com/Heimine/PNC_DLN.