CS Paper Radar

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

Ernesto Araya, Gitta Kutyniok, Weilin Li, Johannes Maly, Manjot Singh

cs.LG stat.MLmath.MG ·submitted 2026-10-29 09:22 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG cs.AI ·2026-10-13 ·Behrooz Tahmasebi, Melanie Weber
published similarity 0.67
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

Combinatorial Characterizations of the Learnability of Conditional Distributions

cs.LG stat.ML ·2026-10-22 ·Mihir Dhanakshirur, Ambuj Tewari
similarity 0.66
Abstract

We study the PAC-learnability of function classes that map inputs to probability distributions over a finite space. The learner observes i.i.d. input-label pairs, with each label sampled from the conditional distribution of an unknown target hypothesis in the class. We measure learning through excess risk under a bounded proper loss that satisfies two mild assumptions. We introduce the \textbf{fat$_γ$Natarajan dimension}, which generalizes both fat$_γ$ and Natarajan dimension, and prove that its finiteness at every positive scale is necessary and sufficient for learnability. We also introduce a \textbf{fat$_γ$Graph} dimension extending the classical \gra dimension and establish inequalities comparing the two dimensions at different scales, leading to an equivalent characterization of learnability. Finally, we show that a distribution-valued function class is learnable if and only if each of its coordinate classes is learnable in the probabilistic concept model.

0.15

How Many Samples Are Enough for Learning Across Domains?

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

Understanding the fundamental mechanisms of learning is essential for designing systems with strong generalization. Recent studies have shown that increasing the number of training domains, or enlarging the distribution shift among them, improves generalization when each domain contains sufficiently many data samples. However, the conditions under which the data samples can be considered sufficient remain unexplored. In this work, we fill this gap by establishing criteria for per-domain sample requirements based on the presented learning bounds. These criteria not only reveal an inverse linear scaling law between the number of training domains and the number of samples required per domain, but also explain the fundamental rationale behind the assumption of data sufficiency, thereby providing theoretical guidance for assessing the adequacy of existing datasets and constructing datasets. This differs from classical learning theory, as the number of samples required is highly dependent on the number of training domains. Additionally, we prove the close relationship between in-domain learning and out-of-domain generalization through the presented generalization bounds, and lastly discuss some key arguments.

0.30

VC-Dimension and Generalization in Geometric Machine Learning with Applications to Active Learning

cs.LG stat.MLmath.DG ·2026-11-09 ·Gokul Bhusal, Delanna Do, Ekaterina Merkurjev, Kevin Miller, Stephan Wojtowytsch
theory similarity 0.63
Abstract · 19 pages + appendices

We compute the VC-dimension of metric ball classifiers in the model spaces of Riemannian geometry (Euclidean, spherical, hyperbolic) and present upper and lower bounds on the VC-dimension of metric balls in several other situations, including general normed vector spaces (potentially infinite VC-dimension), vector spaces with $\ell^p$-norms (VC-dimension grows at least linearly in the dimension, faster than Euclidean for $p=1$), flat tori, and general Riemannian manifolds (arbitrarily large VC-dimension after a conformal change). In several situations where the VC-dimension is large or even infinite, we prove generalization bounds under additional assumptions on the data distribution using covering arguments. Both in the VC-dimension and covering setting, we consider data on low-dimensional subsets of high-dimensional Euclidean spaces. As an application, we consider coverage-based algorithms in active learning.

0.37

Geometric Stability and Sample Complexity for Compositional Function Priors

cs.LG stat.ML ·2026-11-14 ·Christopher L. Hammond
publishedtheory similarity 0.61
Abstract · 25 pages. An extended abstract was accepted at the NeurIPS 2026 Workshop on Symmetry and Geometry in Neural Representations (NeurReps), non-…

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.

0.39

Boosting and the Expressive Power of Simple Weak Learners via the $γ$-VC Dimension

cs.LG ·2026-10-07 ·Arthur da Cunha, Kasper Green Larsen, Liang-Yu Zou
similarity 0.61
Abstract

Boosting converts weak hypotheses with a small edge over random guessing into highly accurate predictors, but the expressive power of the resulting classifier can depend strongly on the structure of the base class. We study this phenomenon through the $γ$-VC dimension introduced by Alon et al. (STOC 2021). Our first result shows that this parameter characterizes the sample complexity for weak-to-strong learning up to a constant factor scaling in $γ$. We then sharpen the general relationship between the classic VC dimension and the $γ$-VC dimension. Finally, we also give improved upper and lower bounds on the $γ$-VC dimension for the fundamental concept classes of decision stumps and axis-parallel rectangles in $\mathbb{R}^d$.

0.21

Marginal-Nonuniform Multiclass Learning

cs.LG stat.ML ·2026-11-06 ·Nataly Brukhim, Steve Hanneke, Amirreza Shaeiri, Maximilian Thiessen
top venue similarity 0.61
Abstract · Accepted at NeurIPS 2026

We study the problem of multiclass classification within the framework of marginal-nonuniform learning, where the constants in the learning rate may depend on the unknown marginal distribution generating the unlabeled data, but not on the target concept. This notion naturally lies between classical PAC learning, where the constants are independent of both the marginal distribution and the target concept, and more recent universal learning, where the constants may depend on both. We give a complete characterization of the optimal marginal-nonuniform learning rates, establishing a fundamental trichotomy: exponential, linear, and arbitrarily slow rates. This characterization is witnessed by a new combinatorial dimension, termed the uncentered DS-eluder dimension. A key ingredient in the upper-bound proofs is a set of new distributional exhaustion lemmas that exploit the sequential nature of this dimension and may be of independent interest.

0.45

Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space

cs.CG cs.CCcs.LG ·2026-10-14 ·Ditbul Ban, Younghun Roh, Julian Shun, Vihan Lakshman
similarity 0.60
Abstract · 55 pages

Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions $d \le 3$. In arbitrary dimensions, we give a randomized algorithm that returns a $(1 \pm \varepsilon)$-approximation with probability at least $1-δ$ in time $O \left(\frac{nd}{\varepsilon^2}\log\frac{2}δ\right)$ for $n$ points. The axiomatic guarantee applies to exact canonical GKD; the randomized algorithm approximates this deterministic quantity. We further show that the two diversity measures of Mironov and Prokhorenkova (2025) remain NP-hard on Euclidean-realizable inputs and, unless $\mathrm{NP} = \mathrm{RP}$, admit no FPRAS even on this restricted domain.

0.24