Statistical Learning Theory

Ask about this topic

Overview

Statistical learning theory asks when a learner can infer rules that work beyond its training data, and quantifies sample complexity, prediction error, and limits on what can be learned. Classical tools include VC and Littlestone dimensions, covering numbers, Rademacher complexity, stability, PAC-Bayes bounds, and minimax analysis; these provide guarantees for empirical risk minimization, online learning, kernels, and robust or private learning. Current work also studies high-dimensional and overparameterized regression, including interpolation and double descent, neural networks and Transformers, and learning under distribution shift, dependence, partial labels, or adaptive data. An enduring tension is that statistically optimal rates may be computationally unattainable, while guarantees for modern architectures often rely on idealized assumptions and may not explain practical optimization.

Latest papers

CardsList

584 papers79 papers in the last four weeks, up 58% on the four weeks before. 0.5% of all new papers.

Mar 25, 2026

Isomorphic Functionalities between Ant Colony and Ensemble Learning: Part II-On the Strength of Weak Learnability and the Boosting Paradigm

In Part I of this series, we established a rigorous mathematical isomorphism between ant colony decision-making and random forest learning, demonstrating that variance reduction through decorrelation is a universal principle shared by biological and computational ensembles. Here we turn to the complementary mechanism: bias reduction through adaptive weighting. Just as boosting algorithms sequentially focus on difficult instances, ant colonies dynamically amplify successful foraging paths through pheromone-mediated recruitment. We prove that these processes are mathematically isomorphic, establishing that the fundamental theorem of weak learnability has a direct analog in colony decision-making. We develop a formal mapping between AdaBoost's adaptive reweighting and ant recruitment dynamics, show that the margin theory of boosting corresponds to the stability of quorum decisions, and demonstrate through comprehensive simulation that ant colonies implementing adaptive recruitment achieve the same bias-reduction benefits as boosting algorithms. This completes a unified theory of ensemble intelligence, revealing that both variance reduction (Part I) and bias reduction (Part II) are manifestations of the same underlying mathematical principles governing collective intelligence in biological and computational systems.

Ernest Fokoué, Gregory Babbitt, Yuval Levental

School of Mathematics and Statistics, Rochester Institute of Technology · Gosnell School of Life Sciences, Rochester Institute of Technology · Center for Imaging Science, Rochester Institute of Technology

Ensemble LearningEmergent Behavior in Multi-Agent SystemsStatistical Learning Theory
AskPDF
Mar 24, 2026

General Machine Learning: Theory for Learning Under Variable Regimes

We study learning under regime variation, where the learner, its memory state, and the evaluative conditions may evolve over time. This paper is a foundational and structural contribution: its goal is to define the core learning-theoretic objects required for such settings and to establish their first theorem-supporting consequences. The paper develops a regime-varying framework centered on admissible transport, protected-core preservation, and evaluator-aware learning evolution. It records the immediate closure consequences of admissibility, develops a structural obstruction argument for faithful fixed-ontology reduction in genuinely multi-regime settings, and introduces a protected-stability template together with explicit numerical and symbolic witnesses on controlled subclasses, including convex and deductive settings. It also establishes theorem-layer results on evaluator factorization, morphisms, composition, and partial kernel-level alignment across semantically commensurable layers. A worked two-regime example makes the admissibility certificate, protected evaluative core, and regime-variation cost explicit on a controlled subclass. The symbolic component is deliberately restricted in scope: the paper establishes a first kernel-level compatibility result together with a controlled monotonic deductive witness. The manuscript should therefore be read as introducing a structured learning-theoretic framework for regime-varying learning together with its first theorem-supporting layer, not as a complete quantitative theory of all learning systems.

Aomar Osmani

INSA-Rouen, France

Statistical Learning TheoryAdaptive Learning
AskPDF
Mar 24, 2026

A One-Inclusion Graph Approach to Multi-Group Learning

We prove the tightest-known upper bounds on the sample complexity of multi-group learning. Our algorithm extends the one-inclusion graph prediction strategy using a generalization of bipartite bb-matching. In the group-realizable setting, we provide a lower bound confirming that our algorithm's log⁡n/n\log n / n convergence rate is optimal in general. If one relaxes the learning objective such that the group on which we are evaluated is chosen obliviously of the sample, then our algorithm achieves the optimal 1/n1/n convergence rate under group-realizability.

Noah Bergam, Samuel Deng, Daniel Hsu

Columbia University

Statistical Learning Theory
AskPDF
Mar 24, 2026

Generalization Bounds for Physics-Informed Neural Networks for the Incompressible Navier-Stokes Equations

This work establishes rigorous first-of-its-kind upper bounds on the generalization error for the method of approximating solutions to the (d+1)-dimensional incompressible Navier-Stokes equations by training depth-2 neural networks trained via the unsupervised Physics-Informed Neural Network (PINN) framework. This is achieved by bounding the Rademacher complexity of the PINN risk. For appropriately weight bounded net classes our derived generalization bounds do not explicitly depend on the network width and our framework characterizes the generalization gap in terms of the fluid's kinematic viscosity and loss regularization parameters. In particular, the resulting sample complexity bounds are dimension-independent. Our generalization bounds suggest using novel activation functions for solving fluid dynamics. We provide empirical validation of the suggested activation functions and the corresponding bounds on a PINN setup solving the Taylor-Green vortex benchmark.

Sebastien Andre-Sloan, Dibyakanti Kumar, Alejandro F Frangi +1

Department of Computer Science, The University of Manchester

Generalization BoundsPhysics-Informed MLComputational Fluid DynamicsStatistical Learning Theory
AskPDF
Mar 24, 2026

Asymptotic Learning Curves for Diffusion Models with Random Features Score and Manifold Data

We study the theoretical behavior of denoising score matching--the learning task associated to diffusion models--when the data distribution is supported on a low-dimensional manifold and the score is parameterized using a random feature neural network. We derive asymptotically exact expressions for the test, train, and score errors in the high-dimensional limit. Our analysis reveals that, for linear manifolds the sample complexity required to learn the score function scales linearly with the intrinsic dimension of the manifold, rather than with the ambient dimension. Perhaps surprisingly, the benefits of low-dimensional structure starts to diminish once we have a non-linear manifold. These results indicate that diffusion models can benefit from structured data; however, the dependence on the specific type of structure is subtle and intricate.

Anand Jerry George, Nicolas Macris

École Polytechnique Fédérale de Lausanne (EPFL), Lab for Statistical Mechanics of Inference in Large Systems (SMILS), CH-1015 Lausanne, Switzerland

Intrinsic DimensionalityRandom Feature MethodsLearning CurvesScore-Based Generative ModelingStatistical Learning TheoryDiffusion Models
AskPDF
Mar 24, 2026

Transformers Trained via Gradient Descent Can Provably Learn a Class of Teacher Models

Transformers have achieved great success across a wide range of applications, yet the theoretical foundations underlying their success remain largely unexplored. To demystify the strong capacities of transformers applied to versatile scenarios and tasks, we theoretically investigate utilizing transformers as students to learn from a class of teacher models. Specifically, the teacher models covered in our analysis include convolution layers with average pooling, graph convolution layers, and various classic statistical learning models, including a variant of sparse token selection models [Sanford et al., 2023, Wang et al., 2024] and group-sparse linear predictors [Zhang et al., 2025]. When learning from this class of teacher models, we prove that one-layer transformers with simplified "position-only'' attention can successfully recover all parameter blocks of the teacher models, thus achieving the optimal population loss. Building upon the efficient mimicry of trained transformers towards teacher models, we further demonstrate that they can generalize well to a broad class of out-of-distribution data under mild assumptions. The key in our analysis is to identify a fundamental bilinear structure shared by various learning tasks, which enables us to establish unified learning guarantees for these tasks when treating them as teachers for transformers.

Chenyang Zhang, Qingyue Zhao, Quanquan Gu +1

The University of Hong Kong · University of California, Los Angeles

TransformerStatistical Learning TheoryKnowledge Distillation
AskPDF
Mar 24, 2026

The No-Clash Teaching Dimension is Bounded by VC Dimension

In the realm of machine learning theory, to prevent unnatural coding schemes between teacher and learner, No-Clash Teaching Dimension was introduced as provably optimal complexity measure for collusion-free teaching. However, whether No-Clash Teaching Dimension is upper-bounded by Vapnik-Chervonenkis dimension remains unknown. In this paper, for any finite concept class, we construct fragments of size equals to its Vapnik-Chervonenkis dimension which identify concepts through an ordered compression scheme. Naturally, these fragments are used as teaching sets, one can easily see that they satisfy the non-clashing condition, i.e., this open question is resolved for finite concept classes.

Jiahua Liu, Benchong Li

School of Mathematics and Statistics, Xidian University.

Sample CompressionStatistical Learning Theory
AskPDF
Mar 23, 2026

Sharper Generalization Bounds for Transformer

This paper studies generalization error bounds for Transformer models. Based on the offset Rademacher complexity, we derive sharper generalization bounds for different Transformer architectures, including single-layer single-head, single-layer multi-head, and multi-layer Transformers. We first express the excess risk of Transformers in terms of the offset Rademacher complexity. By exploiting its connection with the empirical covering numbers of the corresponding hypothesis spaces, we obtain excess risk bounds that achieve optimal convergence rates up to constant factors. We then derive refined excess risk bounds by upper bounding the covering numbers of Transformer hypothesis spaces using matrix ranks and matrix norms, leading to precise, architecture-dependent generalization bounds. Finally, we relax the boundedness assumption on feature mappings and extend our theoretical results to settings with unbounded (sub-Gaussian) features and heavy-tailed distributions.

Yawen Li, Tao Hu, Zhouhui Lian +4

School of Mathematical Sciences, Capital Normal University, 100048 Beijing, China · Wangxuan Institute of Computer Technology, Peking University, China, 100871 · Advanced Institute of Information Technology, Peking University +4

Generalization BoundsTransformerStatistical Learning Theory
AskPDF
Mar 21, 2026

High-dimensional online learning via asynchronous decomposition: Non-divergent results, dynamic regularization, and beyond

Existing high-dimensional online learning methods often face the challenge that their error bounds, or per-batch sample sizes, diverge as the number of data batches increases. To address this issue, we propose an asynchronous decomposition framework that leverages summary statistics to construct a surrogate score function for current-batch learning. This framework is implemented via a dynamic-regularized iterative hard thresholding algorithm, providing a computationally and memory-efficient solution for sparse online optimization. We provide a unified theoretical analysis that accounts for both the streaming computational error and statistical accuracy, establishing that our estimator maintains non-divergent error bounds and ℓ0\ell_0 sparsity across all batches. Furthermore, the proposed estimator adaptively achieves additional gains as batches accumulate, attaining the oracle accuracy as if the entire historical dataset were accessible and the true support were known. These theoretical properties are further illustrated through an example of the generalized linear model.

Shixiang Liu, Zhifan Li, Hanming Yang +1

School of Statistics, Renmin University of China · School of Statistics and Mathematics, Zhongnan University of Economics and Law · Institute of Statistics and Big Data, Renmin University of China +1

Statistical Learning TheoryStreaming AlgorithmsSparse Recovery
AskPDF
Mar 21, 2026

Diffusion Model for Manifold Data: Score Decomposition, Curvature, and Statistical Complexity

Diffusion models have become a leading framework in generative modeling, yet their theoretical understanding -- especially for high-dimensional data concentrated on low-dimensional structures -- remains incomplete. This paper investigates how diffusion models learn such structured data, focusing on two key aspects: statistical complexity and influence of data geometric properties. By modeling data as samples from a smooth Riemannian manifold, our analysis reveals crucial decompositions of score functions in diffusion models under different levels of injected noise. We also highlight the interplay of manifold curvature with the structures in the score function. These analyses enable an efficient neural network approximation to the score function, built upon which we further provide statistical rates for score estimation and distribution learning. Remarkably, the obtained statistical rates are governed by the intrinsic dimension of data and the manifold curvature. These results advance the statistical foundations of diffusion models, bridging theory and practice for generative modeling on manifolds.

Zixuan Zhang, Kaixuan Huang, Tuo Zhao +2

Georgia Tech · Princeton University · Northwestern University

Diffusion ModelsStatistical Learning Theory
AskPDF
Mar 18, 2026

A Noise Sensitivity Exponent Controls Large Statistical-to-Computational Gaps in Single- and Multi-Index Models

Understanding when learning is statistically possible yet computationally hard is a central challenge in high-dimensional statistics. In this work, we investigate this question in the context of single- and multi-index models, classes of functions widely studied as benchmarks to probe the ability of machine learning methods to discover features in high-dimensional data. Our main contribution is to show that a Noise Sensitivity Exponent (NSE) - a simple quantity determined by the activation function - governs the existence and magnitude of statistical-to-computational gaps within a broad regime of these models. We first establish that, in single-index models with large additive noise, the onset of a computational bottleneck is fully characterized by the NSE. We then demonstrate that the same exponent controls a statistical-computational gap in the specialization transition of large separable multi-index models, where individual components become learnable. Finally, in hierarchical multi-index models, we show that the NSE governs the optimal computational rate in which different directions are sequentially learned. Taken together, our results identify the NSE as a unifying property linking noise robustness, computational hardness, and feature specialization in high-dimensional learning.

Leonardo Defilippis, Florent Krzakala, Bruno Loureiro +1

Departement d’Informatique, École Normale Supérieure, PSL & CNRS · Information, Learning and Physics Laboratory, École Polytechnique Fédérale de Lausanne (EPFL) · INRIA Paris

Statistical Learning TheoryMulti-Index ModelsSingle-Index Models
AskPDF
Mar 18, 2026

Consistency of the kk-Nearest Neighbor Regressor under Complex Survey Designs

We study the consistency of the kk-nearest neighbor regressor under complex survey designs. While consistency results for this algorithm are well established for independent and identically distributed data, corresponding results for complex survey data are lacking. We show that the kk-nearest neighbor regressor is consistent under regularity conditions on the sampling design and the distribution of the data. We derive lower bounds for the rate of convergence and show that these bounds exhibit the curse of dimensionality, as in the independent and identically distributed setting. Empirical studies based on simulated and real data illustrate our theoretical findings.

Caren Hasler

k-Nearest NeighborsNonparametric RegressionStatistical Learning Theory
AskPDF
Mar 17, 2026

Self-Regularized Learning Methods

We introduce a general framework for analyzing learning algorithms based on the notion of self-regularization, which captures implicit complexity control without requiring explicit regularization. This is motivated by previous observations that many algorithms, such as gradient-descent based learning, exhibit implicit regularization. In a nutshell, for a self-regularized algorithm the complexity of the predictor is inherently controlled by that of the simplest comparator achieving the same empirical risk. This framework is sufficiently rich to cover both classical regularized empirical risk minimization and gradient descent. Building on self-regularization, we provide a thorough statistical analysis of such algorithms including minmax-optimal rates, where it suffices to show that the algorithm is self-regularized -- all further requirements stem from the learning problem itself. Finally, we discuss the problem of data-dependent hyperparameter selection, providing a general result which yields minmax-optimal rates up to a double logarithmic factor and covers data-driven early stopping for RKHS-based gradient descent.

Max Schölpple, Liu Fanghui, Ingo Steinwart

Institute for Stochastics and Applications, University of Stuttgart · School of Mathematical Sciences, Institute of Natural Sciences and MOE-LSC, Shanghai Jiao Tong University

Statistical Learning TheoryImplicit RegularizationEmpirical Risk Minimization
AskPDF
Mar 17, 2026

High-Dimensional Gaussian Mean Estimation under Realizable Contamination

We study mean estimation for a Gaussian distribution with identity covariance in Rd\mathbb{R}^d under a missing data scheme termed realizable εε-contamination model. In this model an adversary can choose a function r(x)r(x) between 0 and εε and each sample xx goes missing with probability r(x)r(x). Recent work Ma et al., 2024 proposed this model as an intermediate-strength setting between Missing Completely At Random (MCAR) -- where missingness is independent of the data -- and Missing Not At Random (MNAR) -- where missingness may depend arbitrarily on the sample values and can lead to non-identifiability issues. That work established information-theoretic upper and lower bounds for mean estimation in the realizable contamination model. Their proposed estimators incur runtime exponential in the dimension, leaving open the possibility of computationally efficient algorithms in high dimensions. In this work, we establish an information-computation gap in the Statistical Query model (and, as a corollary, for Low-Degree Polynomials and PTF tests), showing that algorithms must either use substantially more samples than information-theoretically necessary or incur exponential runtime. We complement our SQ lower bound with an algorithm whose sample-time tradeoff nearly matches our lower bound. Together, these results qualitatively characterize the complexity of Gaussian mean estimation under εε-realizable contamination.

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

University of Wisconsin-Madison · University of California, San Diego

Data ContaminationStatistical Learning Theory
AskPDF
Mar 16, 2026

Learnability with Partial Labels and Adaptive Nearest Neighbors

Prior work on partial labels learning (PLL) has shown that learning is possible even when each instance is associated with a bag of labels, rather than a single accurate but costly label. However, the necessary conditions for learning with partial labels remain unclear, and existing PLL methods are effective only in specific scenarios. In this work, we mathematically characterize the settings in which PLL is feasible. In addition, we present PL A-kkNN, an adaptive nearest-neighbors algorithm for PLL that is effective in general scenarios and enjoys strong performance guarantees. Experimental results corroborate that PL A-kkNN can outperform state-of-the-art methods in general PLL scenarios.

Nicolas A. Errandonea, Santiago Mazuelas, Jose A. Lozano +1

Basque Center for Applied Mathematics, Bilbao, Spain · Ikerbasque, Basque Foundation for Science · University of the Basque Country, Spain +1

Statistical Learning Theoryk-Nearest Neighbors
AskPDF
Mar 16, 2026

Analyzing Error Sources in Global Feature Effect Estimation

Global feature effects such as partial dependence (PD) and accumulated local effects (ALE) plots are widely used to interpret black-box models. However, they are only estimates of true underlying effects, and their reliability depends on multiple sources of error. Despite the popularity of global feature effects, these error sources are largely unexplored. In particular, the practically relevant question of whether to use training or holdout data to estimate feature effects remains unanswered. We address this gap by providing a systematic, estimator-level analysis that disentangles sources of bias and variance for PD and ALE. To this end, we derive a mean-squared-error decomposition that separates model bias, estimation bias, model variance, and estimation variance, and analyze their dependence on model characteristics, data selection, and sample size. We validate our theoretical findings through an extensive simulation study across multiple data-generating processes, learners, estimation strategies (training data, validation data, and cross-validation), and sample sizes. Our results reveal that, while using holdout data is theoretically the cleanest, potential biases arising from the training data are empirically negligible and dominated by the impact of the usually higher sample size. The estimation variance depends on both the presence of interactions and the sample size, with ALE being particularly sensitive to the latter. Cross-validation-based estimation is a promising approach that reduces the model variance component, particularly for overfitting models. Our analysis provides a principled explanation of the sources of error in feature effect estimates and offers concrete guidance on choosing estimation strategies when interpreting machine learning models.

Timo Heiß, Coco Bögel, Bernd Bischl +1

LMU Munich, Munich, Germany · Munich Center for Machine Learning (MCML)

Statistical Learning Theory
AskPDF
Mar 16, 2026

Dataset Distillation Efficiently Encodes Low-Dimensional Representations from Gradient-Based Learning of Non-Linear Tasks

Dataset distillation, a training-aware data compression technique, has recently attracted increasing attention as an effective tool for mitigating costs of optimization and data storage. However, progress remains largely empirical. Mechanisms underlying the extraction of task-relevant information from the training process and the efficient encoding of such information into synthetic data points remain elusive. In this paper, we theoretically analyze practical algorithms of dataset distillation applied to the gradient-based training of two-layer neural networks with width LL. By focusing on a non-linear task structure called multi-index model, we prove that the low-dimensional structure of the problem is efficiently encoded into the resulting distilled data. This dataset reproduces a model with high generalization ability for a required memory complexity of \tildeΘ$$(r^2d+L), where dd and rr are the input and intrinsic dimensions of the task. To the best of our knowledge, this is one of the first theoretical works that include a specific task structure, leverage its intrinsic dimensionality to quantify the compression rate and study dataset distillation implemented solely via gradient-based algorithms.

Yuri Kinoshita, Naoki Nishikawa, Taro Toyoizumi

The University of Tokyo, Tokyo, Japan · Laboratory for Neural Computation and Adaptation, RIKEN Center for Brain Science, Wako, Japan · RIKEN Center for Advanced Intelligence Project, Nihonbashi, Japan

Two-Layer Neural NetworksDataset DistillationStatistical Learning TheoryMulti-Index Models
AskPDF
Mar 15, 2026

Learning in Function Spaces: An Unified Functional Analytic View of Supervised and Unsupervised Learning

Many machine learning algorithms can be interpreted as procedures for estimating functions defined on the data distribution. In this paper we present a conceptual framework that formulates a wide range of learning problems as variational optimization over function spaces induced by the data distribution. Within this framework the data distribution defines operators that capture structural properties of the data, such as similarity relations or statistical dependencies. Learning algorithms can then be viewed as estimating functions expressed in bases determined by these operators. This perspective provides a unified way to interpret several learning paradigms. In supervised learning the objective functional is defined using labeled data and typically corresponds to minimizing prediction risk, whereas unsupervised learning relies on structural properties of the input distribution and leads to objectives based on similarity or smoothness constraints. From this viewpoint, the distinction between learning paradigms arises primarily from the choice of the functional being optimized rather than from the underlying function space. We illustrate this framework by discussing connections with kernel methods, spectral clustering, and manifold learning, highlighting how operators induced by data distributions naturally define function representations used by learning algorithms. The goal of this work is not to introduce a new algorithm but to provide a conceptual framework that clarifies the role of function spaces and operators in modern machine learning.

K. Lakshmanan

Department of Computer Science and Engineering, Indian Insititute of Technology (BHU), Varanasi 221005.

Supervised LearningStatistical Learning Theory
AskPDF
Mar 13, 2026

Deconstructing the Failure of Ideal Noise Correction: A Three-Pillar Diagnosis

Statistically consistent methods based on the noise transition matrix (TT) offer a theoretically grounded solution to Learning with Noisy Labels (LNL), with guarantees of convergence to the optimal clean-data classifier. In practice, however, these methods are often outperformed by empirical approaches such as sample selection, and this gap is usually attributed to the difficulty of accurately estimating TT. The common assumption is that, given a perfect TT, noise-correction methods would recover their theoretical advantage. In this work, we put this longstanding hypothesis to a decisive test. We conduct experiments under idealized conditions, providing correction methods with a perfect, oracle transition matrix. Even under these ideal conditions, we observe that these methods still suffer from performance collapse during training. This compellingly demonstrates that the failure is not fundamentally a TT-estimation problem, but stems from a more deeply rooted flaw. To explain this behaviour, we provide a unified analysis that links three levels: macroscopic convergence states, microscopic optimisation dynamics, and information-theoretic limits on what can be learned from noisy labels. Together, these results give a formal account of why ideal noise correction fails and offer concrete guidance for designing more reliable methods for learning with noisy labels.

Chen Feng, Zhuo Zhi, Zhao Huang +5

Queen’s University Belfast · University College London · University of Aberdeen +3

Learning with Noisy LabelsStatistical Learning Theory
AskPDF
Mar 13, 2026

A theory of learning data statistics in diffusion models, from easy to hard

While diffusion models have emerged as a powerful class of generative models, their learning dynamics remain poorly understood. We address this issue first by empirically showing that standard diffusion models trained on natural images exhibit a distributional simplicity bias, learning simple, pair-wise input statistics before specializing to higher-order correlations. We reproduce this behaviour in simple denoisers trained on a minimal data model, the mixed cumulant model, where we precisely control both pair-wise and higher-order correlations of the inputs. We identify a scalar invariant of the model that governs the sample complexity of learning pair-wise and higher-order correlations that we call the diffusion information exponent, in analogy to related invariants in different learning paradigms. Using this invariant, we prove that the denoiser learns simple, pair-wise statistics of the inputs at linear sample complexity, while more complex higher-order statistics, such as the fourth cumulant, require at least cubic sample complexity. We also prove that the sample complexity of learning the fourth cumulant is linear if pair-wise and higher-order statistics share a correlated latent structure. Our work describes a key mechanism for how diffusion models can learn distributions of increasing complexity.

Lorenzo Bardone, Claudia Merger, Sebastian Goldt

Statistical Physics of Computation Laboratory, EPFL, Lausanne, Switzerland · Theoretical and Scientific Data Science Group, SISSA, Trieste, Italy

Diffusion ModelsStatistical Learning Theory
AskPDF
Mar 12, 2026

Decomposing Observational Multiplicity in Decision Trees: Leaf and Structural Regret

Many machine learning tasks admit multiple models that perform almost equally well, a phenomenon known as predictive multiplicity. A fundamental source of this multiplicity is observational multiplicity, which arises from the stochastic nature of label collection: observed training labels represent only a single realization of the underlying ground-truth probabilities. While theoretical frameworks for observational multiplicity have been established for logistic regression, their implications for non-smooth, partition-based models like decision trees remain underexplored. In this paper, we introduce two complementary notions of observational multiplicity for decision tree classifiers: leaf regret and structural regret. Leaf regret quantifies the intrinsic variability of predictions within a fixed leaf due to finite-sample noise, while structural regret captures variability induced by the instability of the learned tree structure itself. We provide a formal decomposition of observational multiplicity into these two components and establish statistical guarantees. Our experimental evaluation across diverse credit risk scoring datasets confirms the near-perfect alignment between our theoretical decomposition and the empirically observed variance. Notably, we find that structural regret is the primary driver of observational multiplicity, accounting for over 15 times the variability of leaf regret in some datasets. Furthermore, we demonstrate that utilizing these regret measures as an abstention mechanism in selective prediction can effectively identify arbitrary regions and improve model safety, elevating recall from 92% to 100% on the most stable sub-populations. These results establish a rigorous framework for quantifying observational multiplicity, aligning with recent advances in algorithmic safety and interpretability.

Mustafa Cavus

Eskisehir Technical University, Department of Statistics, Turkiye 26555

Statistical Learning TheoryDecision Tree Learning
AskPDF
Mar 12, 2026

A Geometrically-Grounded Drive for MDL-Based Optimization in Deep Learning

This paper introduces a novel optimization framework that fundamentally integrates the Minimum Description Length (MDL) principle into the training dynamics of deep neural networks. Moving beyond its conventional role as a model selection criterion, we reformulate MDL as an active, adaptive driving force within the optimization process itself. The core of our method is a geometrically-grounded cognitive manifold whose evolution is governed by a coupled Ricci flow, enriched with a novel MDL Drive term derived from first principles. This drive, modulated by the task-loss gradient, creates a seamless harmony between data fidelity and model simplification, actively compressing the internal representation during training. We establish a comprehensive theoretical foundation, proving key properties including the monotonic decrease of description length (Theorem~\ref{thm:convergence}), a finite number of topological phase transitions via a geometric surgery protocol (Theorems~\ref{thm:surgery}, \ref{thm:ultimate_fate}), and the emergence of universal critical behavior (Theorem~\ref{thm:universality}). Furthermore, we provide a practical, computationally efficient algorithm with O(Nlog⁡N)O(N \log N) per-iteration complexity (Theorem~\ref{thm:complexity}), alongside guarantees for numerical stability (Theorem~\ref{thm:stability}) and exponential convergence under convexity assumptions (Theorem~\ref{thm:convergence_rate}). Empirical validation on synthetic regression and classification tasks confirms the theoretical predictions, demonstrating the algorithm's efficacy in achieving robust generalization and autonomous model simplification. This work provides a principled path toward more autonomous, generalizable, and interpretable AI systems by unifying geometric deep learning with information-theoretic principles.

Ming Lei, Shufan Wu, Christophe Baehr

School of Aeronautics and Astronautics, Shanghai JiaoTong University, Shanghai China · Météo-France/CNRS CNRM/GAME UMR 3589 and the Mathematical Institute of Toulouse, France

Deep Learning OptimizationMinimum Description LengthStatistical Learning Theory
AskPDF
Mar 10, 2026

Upper Generalization Bounds for Neural Oscillators

Neural oscillators that originate from second-order ordinary differential equations (ODEs) have shown competitive performance in learning mappings between dynamic loads and responses of complex nonlinear structural systems. Despite this empirical success, theoretically quantifying the generalization capacities of their neural network architectures remains undeveloped. In this study, the neural oscillator consisting of a second-order ODE followed by a multilayer perceptron (MLP) is considered. Its upper probably approximately correct (PAC) generalization bound for approximating causal and uniformly continuous operators between continuous temporal function spaces and that for approximating the uniformly asymptotically incrementally stable second-order dynamical systems are derived by leveraging the Rademacher complexity framework. These bounds are further extended to the squared Wasserstein-1 distances between the probability measures of quantities of interest calculated from target causal operators and the corresponding learned neural oscillators. The theoretical results show that the estimation errors grow polynomially with respect to both MLP sizes and the time length, thereby avoiding the curse of parametric complexity. Furthermore, the derived error bounds demonstrate that constraining the Lipschitz constants of the MLPs via loss function regularization can improve the generalization ability of the neural oscillator. Numerical studies considering a Bouc-Wen nonlinear system under stochastic seismic excitation validates the theoretically predicted power laws of the estimation errors with respect to the sample size and time length, and confirms the effectiveness of constraining MLPs' matrix and vector norms in enhancing the performance of the neural oscillator under limited training data.

Zifeng Huang, Konstantin M. Zuev, Yong Xia +1

Institute for Risk and Reliability, Leibniz University Hannover, Callinstraße 34, Hannover, 30167, Germany · Department of Computing and Mathematical Sciences, California Institute of Technology, Pasadena, California, United States · Joint Research Centre for Marine Infrastructure, Department of Civil and Environmental Engineering, The Hong Kong Polytechnic University, Kowloon, Hong Kong, China +2

Generalization BoundsNeural Network GeneralizationOscillatory Neural NetworksStatistical Learning Theory
AskPDF
Mar 8, 2026

From Garbage to Gold: A Data-Architectural Theory of Predictive Robustness

Tabular machine learning presents a paradox: modern models achieve state-of-the-art performance using high-dimensional (high-D), collinear, error-prone data, defying the "Garbage In, Garbage Out" mantra. To help resolve this, we synthesize principles from Information Theory, Latent Factor Models, and Psychometrics, clarifying that predictive robustness arises not solely from data cleanliness, but from the synergy between data architecture and model capacity. Partitioning predictor-space "noise" into "Predictor Error" and "Structural Uncertainty" (informational deficits from stochastic generative mappings), we prove that leveraging high-D sets of error-prone predictors asymptotically overcomes both types of noise, whereas cleaning a low-D set is fundamentally bounded by Structural Uncertainty. We demonstrate why "Informative Collinearity" (dependencies from shared latent causes) enhances reliability and convergence efficiency, and explain why increased dimensionality reduces the latent inference burden, enabling feasibility with finite samples. To address practical constraints, we propose "Proactive Data-Centric AI" to identify predictors that enable robustness efficiently. We also derive boundaries for Systematic Error Regimes and show why models that absorb "rogue" dependencies can mitigate assumption violations. Linking latent architecture to Benign Overfitting, we offer a first step towards a unified view of robustness to Outcome Error and predictor-space noise, while also delineating when traditional DCAI's focus on label cleaning remains powerful. By redefining data quality from item-level perfection to portfolio-level architecture, we provide a theoretical rationale for "Local Factories" -- learning from live, uncurated enterprise "data swamps" -- supporting a deployment paradigm shift from "Model Transfer" to "Methodology Transfer'' to overcome static generalizability limitations.

Terrence J. Lee-St. John, Jordan L. Lawson, Bartlomiej Piechowski-Jozwiak

Independent Researcher & Institute for Healthier Living Abu Dhabi, Abu Dhabi, UAE · Independent Researcher & Brown University, Center for Computation and Visualization, Providence, RI, USA

Statistical Learning Theory
AskPDF
Mar 8, 2026

Sparsity and Out-of-Distribution Generalization

Explaining out-of-distribution generalization has been a central problem in epistemology since Goodman's "grue" puzzle in 1946. Today it's a central problem in machine learning, including AI alignment. Here we propose a principled account of OOD generalization with three main ingredients. First, the world is always presented to experience not as an amorphous mass, but via distinguished features (for example, visual and auditory channels). Second, Occam's Razor favors hypotheses that are "sparse," meaning that they depend on as few features as possible. Third, sparse hypotheses will generalize from a training to a test distribution, provided the two distributions sufficiently overlap on their restrictions to the features that are either actually relevant or hypothesized to be. The two distributions could diverge arbitrarily on other features. We prove a simple theorem that formalizes the above intuitions, generalizing the classic sample complexity bound of Blumer et al. to an OOD context. We then generalize sparse classifiers to subspace juntas, where the ground truth classifier depends solely on a low-dimensional linear subspace of the features.

Scott Aaronson, Lin Lin Lee, Jiawei Li

UT Austin

OOD GeneralizationGeneralization BoundsStatistical Learning Theory
AskPDF
Mar 7, 2026

ShakyPrepend: A Multi-Group Learner with Improved Sample Complexity

Multi-group learning is a learning task that focuses on controlling predictors' conditional losses over specified subgroups. We propose ShakyPrepend, a method that leverages tools inspired by differential privacy to obtain improved theoretical guarantees over existing approaches. Through numerical experiments, we demonstrate that ShakyPrepend adapts to both group structure and spatial heterogeneity. We provide practical guidance for deploying multi-group learning algorithms in real-world settings.

Lujing Zhang, Daniel Hsu, Sivaraman Balakrishnan

Department of Statistics and Data Science Carnegie Mellon University · Computer Science Department Data Science Institute Columbia University · Department of Statistics and Data Science Machine Learning Department Carnegie Mellon University

Statistical Learning Theory
AskPDF
Mar 7, 2026

Margin in Abstract Spaces

Margin-based learning, exemplified by linear and kernel methods, is one of the few classical settings where generalization guarantees are independent of the number of parameters. This makes it a central case study in modern highly over-parameterized learning. We ask what minimal mathematical structure underlies this phenomenon. We begin with a simple margin-based problem in arbitrary metric spaces: concepts are defined by a center point and classify points according to whether their distance lies below rr or above RR. We show that whenever R>3rR>3r, this class is learnable in any metric space. Thus, sufficiently large margins make learnability rely only on the triangle inequality, without any linear or analytic structure being necessary. Our first main result extends this phenomenon to concepts defined by bounded linear combinations of distance functions, and reveals a sharp threshold: there exists a universal constant such that whenever the margin is larger than this constant, the class is learnable in every metric space, while below it there exist metric spaces where it is not learnable at all. We then ask whether margin-based learnability can always be explained via an embedding into a linear space -- that is, reduced to linear classification in some Banach space through a kernel-type construction. We answer this negatively by demonstrating a margin learnable class that cannot be embedded into any Banach space in which linear classification with margins is learnable.

Yair Ashlagi, Roi Livni, Shay Moran +1

School of Electrical and Computer Engineering, Tel Aviv University. · Departments of Mathematics, Computer Science, and Data and Decision Sciences, Technion, and Google Research. · Departments of Mathematics, Technion.

Kernel MethodsStatistical Learning TheoryMargin-Based Learning
AskPDF
Mar 7, 2026

Post-Training with Policy Gradients: Optimality and the Base Model Barrier

We study post-training linear autoregressive models with outcome and process rewards. Given a context x\boldsymbol{x}, the model must predict the response y∈YN\boldsymbol{y} \in Y^N, a sequence of length NN that satisfies a γγ margin condition, an extension of the standard separability to sequences. We prove that on test samples where the base model achieves a non-trivial likelihood αα, a variant of policy gradient (PG) can achieve likelihood 1−ε1 - \varepsilon with an essentially minimax optimal number of reward queries O~((α−1+ε−1)/γ2)\tilde{O}((α^{-1} + \varepsilon^{-1})/γ^2). However, a barrier arises for going beyond the support of the base model. We prove that the overall expected error after post-training with outcome rewards is governed by a property of the base model called the Likelihood Quantile (LQ), and that variants of PG, while minimax optimal, may require a number of reward queries exponential in NN to go beyond this support, regardless of the pre-training algorithm. To overcome this barrier, we study post-training with a process reward model, and demonstrate how PG variants in this setting avoid the curse of dimensionality in NN via dependence on a token-level LQ. Along the way, we prove that under the margin condition, SGD with adaptive learning rate (LR) achieves a near optimal test error for statistical learning, and PG with adaptive LR achieves a near optimal number of mistakes for online learning while being computationally efficient whenever possible, both of which may be of independent interest.

Alireza Mousavi-Hosseini, Murat A. Erdogdu

University of Toronto, Vector Institute. · University of Toronto, Vector Institute, and Numurho.

Language Model Post-TrainingPolicy GradientRL for Language ModelsProcess Reward ModelsStatistical Learning Theory
AskPDF
Mar 6, 2026

Agnostic learning in (almost) optimal time via Gaussian surface area

The complexity of learning a concept class under Gaussian marginals in the difficult agnostic model is closely related to its L1L_1-approximability by low-degree polynomials. For any concept class with Gaussian surface area at most ΓΓ, Klivans et al. (2008) show that degree d=O(Γ2/ε4)d = O(Γ^2 / \varepsilon^4) suffices to achieve an ε\varepsilon-approximation. This leads to the best-known bounds on the complexity of learning a variety of concept classes. In this note, we improve their analysis by showing that degree d=O~(Γ2/ε2)d = \tilde O (Γ^2 / \varepsilon^2) is enough. In light of lower bounds due to Diakonikolas et al. (2021), this yields (near) optimal bounds on the complexity of agnostically learning polynomial threshold functions in the statistical query model. Our proof relies on a direct analogue of a construction of Feldman et al. (2020), who considered L1L_1-approximation on the Boolean hypercube.

Lucas Pesenti, Lucas Slot, Manuel Wiedmer

ETH Zurich · University of Amsterdam

Agnostic LearningStatistical Learning TheoryLow-Degree Polynomial MethodBoolean Function Learning
AskPDF
Mar 5, 2026

Improved Scaling Laws via Weak-to-Strong Generalization in Random Feature Ridge Regression

It is increasingly common in machine learning to use learned models to label data and then employ such data to train more capable models. The phenomenon of weak-to-strong generalization exemplifies the advantage of this two-stage procedure: a strong student is trained on imperfect labels obtained from a weak teacher, and yet the strong student outperforms the weak teacher. In this paper, we show that the potential improvement is substantial, in the sense that it affects the scaling law followed by the test error. Specifically, we consider students and teachers trained via random feature ridge regression (RFRR). Our main technical contribution is to derive a deterministic equivalent for the excess test error of the student trained on labels obtained via the teacher. Via this deterministic equivalent, we then identify regimes in which the scaling law of the student improves upon that of the teacher, unveiling that the improvement can be achieved both in bias-dominated and variance-dominated settings. Strikingly, the student may attain the minimax optimal rate regardless of the scaling law of the teacher -- in fact, when the test error of the teacher does not even decay with the sample size.

Diyuan Wu, Lehan Chen, Theodor Misiakiewicz +1

Institute of Science and Technology Austria (ISTA) · Department of Applied and Computational Mathematics, Yale University · Department of Statistics and Data Science, Yale University

Weak-to-Strong GeneralizationScaling LawsStatistical Learning TheoryRandom Feature Methods
AskPDF