stat.MLNov 14, 2026

Geometric Stability and Sample Complexity for Compositional Function Priors

Authors: Christopher L. Hammond

Organizations: Susquehanna International Group

Abstract

We study when compositional structure yields dimension reduction in supervised learning. We frame learning as empirical risk minimization with a function-space prior: a regularization functional selects a subset of functions with favorable approximation and metric entropy. The models are compositions f(x)=g(Ax+Δh(x))f(x)=g(Ax+Δh(x)), where A∈Rk×dA\in\mathbb{R}^{k\times d} is a linear base map, ΔhΔh is a nonlinear correction, and gg is an outer function; that is, ff is an arbitrary smooth function of a kk-dimensional representation of the input that is linear up to a correction. We prove covering-number bounds showing that the statistical complexity of this class interpolates between an intrinsic regime, parametric in the kdkd entries of the linear map and nonparametric only in the representation dimension kk, and an ambient dd-dimensional nonparametric rate; the interpolation is controlled by the correction size ε=∥Δh∥\varepsilon=\|Δh\|. We then connect ε\varepsilon to data geometry. If the data lie in a small tube around a kk-dimensional manifold and the regression target depends on the input only through its nearest point on that manifold, then locally the target factorizes exactly as g(Ax+Δh(x))g(Ax+Δh(x)) with AA a tangent chart and a correction whose Sobolev norm scales linearly with curvature at the localization scale. Patching such local models over an atlas gives a finite-sample excess-risk bound for a least-squares estimator over a finite net of local models, whose ambient term vanishes with curvature. For a one-dimensional model problem we also prove a converse: on curved data, every affine compositional predictor faces an error floor unless its correction budget scales with curvature, while the matching curved model class attains the intrinsic rate. The correction size ε\varepsilon is thus the effective-dimension parameter linking curvature to statistical complexity.

Explore similar work

Feb 11, 2026

Deep Learning of Compositional Targets with Hierarchical Spectral Methods

Why depth yields a computational advantage over shallow methods remains a central open question in learning theory. We study this question in a controlled high-dimensional Gaussian setting, focusing on compositional target functions. We analyze their learnability using an explicit three-layer fitting model trained via layer-wise spectral estimators. The target combines polynomial latent features with a scalar readout, and its compositional structure allows learning to proceed in stages. Recovering an intermediate representation reduces the problem to lower-degree spectral estimation tasks, as in multi-index models. Our analysis establishes Gaussian comparison bounds for projected moments when 0<ε<1/30<\varepsilon<1/3, and motivates separations in sample complexity between two- and three-layer learning strategies, conditional on a conjectured spectral recovery step.
Jul 7, 2026

A Function-Space Dichotomy for Compositional Learning: Exponential Sub-Optimality of the Neural Tangent Kernel

A persistent empirical observation is that trained neural networks outperform their neural tangent kernel (NTK) limit on tasks with compositional structure, yet a quantitative account of when\textbf{when} and by how much\textbf{by how much} has been lacking. Working on the unit circle, we give such an account through a dichotomy between two complexity measures of the target: its Fourier complexity\textbf{Fourier complexity}, which controls NTK kernel regression, and its architectural complexity\textbf{architectural complexity}, which controls learning over depth-LL, width-ww ReLU networks with the variation norm of the weights bounded by RR. We first characterize the minimax rate of the architecture class CL,w,R\mathcal{C}_{L,w,R}, pinning it down up to a single factor of LL: between Ω(Lw2R2/n)Ω(Lw^2R^2/n) and O~(L2w2R2/n)\tilde{O}(L^2w^2R^2/n). We then show the NTK estimator sits exponentially\textbf{exponentially} above this floor whenever the two complexities decouple: for the depth-LL iterated sawtooth, NTK regression needs Ω(4L)Ω(4^L) samples while the minimax floor is polynomial in LL. Numerical experiments confirm the theoretical claims: on bandlimited smooth targets, the NTK is competitive or better, while on the hypercube sparse-parity model, a standard two-layer network beats the NTK by four to six orders of magnitude in test error. The gap is thus a function-space property, a mismatch between the kernel's smoothness bias and the target's compositional structure, rather than a generic kernel-versus-network phenomenon.
May 25, 2026

Learning Sparse Compositional Functions with Norm-Constrained Neural Networks

The ability of deep neural networks to learn hierarchical features is widely regarded as a key mechanism underlying their success in high-dimensional learning. Existing theory partially supports this view by establishing approximation rates based on parameter counts and sample complexity guarantees for compositional models without incurring the curse of dimensionality (CoD). To study overparameterized regimes, where the number of parameters exceeds the sample size, we develop a framework that measures complexity via the parameter norm. Within this approach, we establish approximation rates and excess risk bounds for learning sparse compositional functions whose compositional structure is represented by directed acyclic graphs (DAGs), using Frobenius norm-constrained deep neural networks. Our results have broad applicability since every function that is efficiently Turing computable admits sparse compositional representations. In particular, we cover a range of representative models, including multi-index models, binary tree structures, and general compositional architectures. The rates we derive show that deep networks can exploit the compositional structure of the target functions, effectively avoiding the CoD through hierarchical representations.