CS Paper Radar

Geometric Stability and Sample Complexity for Compositional Function Priors

Christopher L. Hammond

cs.LG stat.ML ·submitted 2026-11-14 17:41 UTC · v1
publishedtheory

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))$, where $A\in\mathbb{R}^{k\times d}$ is a linear base map, $Δh$ is a nonlinear correction, and $g$ is an outer function; that is, $f$ is an arbitrary smooth function of a $k$-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 $kd$ entries of the linear map and nonparametric only in the representation dimension $k$, and an ambient $d$-dimensional nonparametric rate; the interpolation is controlled by the correction size $\varepsilon=\|Δh\|$. We then connect $\varepsilon$ to data geometry. If the data lie in a small tube around a $k$-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))$ with $A$ 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.

Comment
25 pages. An extended abstract was accepted at the NeurIPS 2026 Workshop on Symmetry and Geometry in Neural Representations (NeurReps), non-archival. Ancillary file: companion document with extended proofs and examples

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse Priors for Efficient Distribution Learning

cs.LG math.ST ·2026-09-16 ·Saumya Goyal, Barnabás Póczos
theory similarity 0.64
Abstract

Despite the widespread use and success of generative AI techniques today, theoretical guarantees on learning a distribution supported in $d$ dimensions from $n$ samples degrade as $O(n^{-1/Θ(d)})$, though shown to be minimax optimal. We hypothesize that present bounds are too pessimistic because smoothness assumptions are not enough to capture the structure of distributions that often appear in real applications. Consequently, we introduce the class of sparse priors and define the "Sparse Dimension" as a measure of sparsity of a prior over the space of all distributions. We show that distribution learning under a $k$-sparse prior achieves a Bayesian risk lower bound of $Ω(\sqrt{k/n})$ under common distance metrics, and show a matching (up to logarithmic terms asymptotically in $n,k$) upper bound for the TV distance under mild additional assumptions. We show the statistical equivalence of distribution learning and learning to sample in the Bayesian setting so that our results apply to learning to sample as well. While $k$ can still depend on the dimension $d$, or a notion of intrinsic dimension, our results show that learning under an appropriate prior overcomes the curse of dimensionality with respect to the dependence on $n$.

0.33

Extending Rademacher Complexity-Based Generalization Theory to Domain Generalization

cs.LG cs.CV ·2026-11-19 ·Xi Wang, Liang Bai, Xian Yang, Richard Yi Da Xu
similarity 0.62
Abstract

Domain generalization (DG) aims to train models on multiple source domains with distinct distributions to ensure robust performance on unseen target domains. In doing so, it elevates the concept of generalization from the traditional sample level to the distribution level. Existing theoretical frameworks introduce a domain space endowed with a meta-distribution to extend classical generalization analysis to this new setting. However, these approaches typically treat the domain space as devoid of geometry. In reality, the domain space is an inherently infinite-dimensional, nonlinear abstract space composed of probability distributions, and its complex geometric properties fundamentally determine generalization behavior. Consequently, existing geometry-free theories of domain generalization have a fundamental limitation. They lack a formal characterization of what distinguishes distribution-level generalization from sample-level generalization, leaving the inherent difficulty of generalizing across domains largely unexplained. To bridge this gap, we formalize the domain space as the Wasserstein space over the representation space. Building on the geometric properties of this space (specifically the $\mathrm{CD}(K,\infty)$ curvature theory) we derive a novel, geometry-dependent DG error bound. By introducing an additional curvature-dependent confidence term, this bound formally disentangles the two levels of generalization effects and reveals the essential nature that domain generalization is affected by both the invariance and the curvature of the representation space. Finally, we experimentally validate the effect of curvature on domain generalization.

0.13

Formalizing the Intrinsic Dimension of Objective Landscapes by a Generalized Notion of Co-dimension

cs.LG stat.MLmath.MG ·2026-10-29 ·Ernesto Araya, Gitta Kutyniok, Weilin Li, Johannes Maly, Manjot Singh
similarity 0.61
Abstract

In this work, we formalize the concept of intrinsic dimension of objective landscapes introduced in Li et al. (2018), which measures the structural complexity of learning problems by training along randomly generated subspaces. We define the intrinsic dimension of a set $Θ\subset\mathbb{R}^p$ as the minimal dimension $d_{\mathrm{int}}(Θ)$ such that a random plane of dimension $d_{\mathrm{int}}(Θ)$ in $\mathbb{R}^p$ intersects $Θ$ with probability one. We show that it is a generalized notion of co-dimension that depends on the global geometry of $Θ$. We study mathematical properties of the intrinsic dimension and develop techniques to estimate the intrinsic dimension of sets $Θ$ that arise in learning problems. More specifically, we derive upper and/or lower bounds where $Θ$ is the set of optimal parameters in student-teacher settings with shallow and deep ReLU networks, including finite and infinite sample cases, and with and without regularization. We discuss how our theory leads to novel types of generalization bounds, thereby showing that the intrinsic dimension is a measure of learning complexity. Our results connect techniques from seemingly different areas of machine learning research such as classification of symmetries of ReLU networks and stochastic geometry.

0.15

Learning Submanifolds for Subsequent Inference on Random Dot Product Graphs, Part 1: Theory

cs.LG stat.ML ·2026-09-16 ·Michael W. Trosset, Carey E. Priebe
similarity 0.61
Abstract · 23 pages

We propose a framework for restricted inference on random dot product graphs whose latent positions lie on an unknown low-dimensional support manifold. For general decision problems, we propose semisupervised decision rules that use auxiliary data to learn the support manifold. Specifically, our rules use the Isomap manifold learning procedure to construct a low-dimensional Euclidean representation of the observed graph, in which space an isometrically invariant function maps configurations of points to actions. We study the behavior of the proposed rules as the quantity of auxiliary data sampled from the unknown support manifold increases. We show that, as the auxiliary sample size increases, the risk of the semisupervised rule converges to the risk of an oracle rule that relies on the maximal amount of low-dimensional Euclidean structure that can be extracted from the support manifold. Examples, applications, and simulation studies are deferred to a sequel.

0.38

Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

cs.LG cs.AI ·2026-10-13 ·Behrooz Tahmasebi, Melanie Weber
published similarity 0.60
Abstract · 32 pages, 1 figure. An extended abstract of this paper appeared at the ICML 2026 HiLD Workshop (July 10, 2026)

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is \emph{size generalization}: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting $n$ denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error $n^{-Θ(1)}$ and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as $(\log n)^{-Θ(1)}$, yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error $n^{-Θ(1)}$, recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. To our knowledge, this work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes.

0.31

Deep Learning for Random Objects in Metric Spaces: Beyond Manifold Assumptions

cs.LG stat.MLmath.STstat.ME ·2026-10-22 ·Marcos Matabuena, Xiaokai Luo, Oscar Hernan Madrid Padilla
hot direction similarity 0.59
Abstract

Deep learning (DL) methods have substantially improved predictive performance across a wide range of downstream prediction tasks, enabling new discoveries in multiple domains. However, principled DL methods for non-Euclidean random objects remain relatively scarce, despite the growing importance of modern biomedical outcomes taking the form of probability distributions, random graphs, functions, and other random objects in metric spaces. Motivated by a new generation of digital and clinical biomarkers, we propose a deep learning framework for regression with random objects in metric spaces. Our approach operates directly on the metric structure of the response space, avoiding restrictive manifold or Euclidean embedding assumptions imposed by many existing methods. At the same time, it retains modern statistical guarantees under the stated statistical assumptions. We establish statistical consistency and convergence rates for the proposed estimator, and characterize conditions under which it can mitigate the curse of dimensionality for hierarchically compositional regression functions. Extensive simulation studies demonstrate competitive predictive performance, with gains over several competing approaches in multiple Euclidean and non-Euclidean configurations. Finally, we demonstrate the practical utility of the proposed framework in two digital health case studies with distribution-valued outcomes in Wasserstein spaces, using high-resolution accelerometry and continuous glucose monitoring data. Embedding-based deep-learning methods may be less suitable when no informative low-dimensional representation exists or when the learned embedding does not adequately preserve the intrinsic geometry of the response space.

0.50

Communication Complexity of Universal Features

cs.DS stat.MLcs.LG ·2026-10-19 ·Lunjia Hu, Anish Jayant, Peter Li, Princewill Okoroafor, Abhishek Shetty
theory similarity 0.59
Abstract

Motivated by the notion of features from machine learning, we study the complexity of representing data that allows for evaluation with a given family of functions. Concretely, we consider a deterministic encoder that observes $X\sim D$ and produces a finite encoding before a task $f\in\mathcal{F}\subseteq\{0,1\}^{\mathcal{X}}$ is specified. For each task, a decoder must predict $f(X)$ with error at most $\varepsilon$ under $D$. We construct an encoder that outputs a representation with $O(d^{*}\log(1/\varepsilon))$ bits, where $d^{*}$ is the dual VC dimension of $\mathcal{F}$. Our encoder greedily selects $O((d^{*}/\varepsilon)\log(1/\varepsilon))$ functions from the class and uses their joint label pattern to produce the encoding. The key idea in our upper bound is a novel potential function argument, where we compare the entropy gained from each greedy selection with the number of patterns allowed by the dual VC dimension. We present lower bounds showing that the representation length achieved by our encoder is worst-case optimal for every $d^* \ge 1$ and $\varepsilon < 1/4$ up to a universal constant factor, and instance-wise optimal for every family $\mathcal{F}$ up to an $O(\log(1/\varepsilon))$ factor. We give two ways to learn the representation from unlabeled samples, with different guarantees on the representation size and sample complexity. Experimentally, we verify the greedy construction's accuracy-size tradeoff and explore its connection to neural sparse autoencoders.

0.21

Can Domain Generalization be Guaranteed in Small-Sample Learning?

cs.LG ·2026-09-30 ·Hong Zheng
similarity 0.59
Abstract

The small-sample learning problem remains a fundamental challenge in machine learning because limited training data lead to unstable model estimation and generalization. Structural Risk Minimization (SRM) has long been regarded as a principled solution under the classical i.i.d. assumption. However, domain generalization (DG) violates this assumption, leaving the theoretical role of SRM in DG largely unexplored. To bridge this gap, we establish the first theoretical guarantees for SRM in DG under mild assumptions. Specifically, based on the concept of stability, we derive learning consistency and generalization error bounds and prove that these bounds become tight when the hypotheses satisfy the stability condition. Building upon this, under a specific hypothesis space assumption, we establish stability, learning, and generalization bounds for SRM. We further discuss the applicability of these bounds to deep learning. This work establishes theoretical foundations for SRM under distribution shifts and sheds light on the design of robust DG algorithms in small-sample scenarios.

0.20