Geometric Stability and Sample Complexity for Compositional Function Priors
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 , where is a linear base map, is a nonlinear correction, and is an outer function; that is, is an arbitrary smooth function of a -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 entries of the linear map and nonparametric only in the representation dimension , and an ambient -dimensional nonparametric rate; the interpolation is controlled by the correction size . We then connect to data geometry. If the data lie in a small tube around a -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 with 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 is thus the effective-dimension parameter linking curvature to statistical complexity.
Statistical Learning Theory
Statistical learning theory studies when data-driven algorithms generalize, how many samples they need, and what statistical or computational limits apply.
See all 635 papers