Statistical Learning Theory

Follow this topic Ask about this topic

Momentum

34 papers in the last four weeks, up 127% on the four weeks before. 0.3% of all new papers.

Jul 13Week of Sep 28

Latest papers 395

Oct 7, 2026cs.LG

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

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

.

Arthur da Cunha, Kasper Green Larsen, Liang-Yu Zou

Aarhus University

Statistical Learning Theory Weak-to-Strong Generalization Ensemble Learning

Oct 7, 2026stat.ML

Data Reuse in Non-Stationary Learning

We consider online learning in non-stationary environments, where the goal is to track an unknown parameter that switches abruptly between a finite set of recurring values. Recurrence opens the possibility of judiciously reusing past observations to improve algorithm performance. However, the changing nature of the underlying signal and lack of information on these dynamics may limit the ability to "safely" reuse data. In this paper we quantify some of the fundamental tradeoffs in this class of problems, and show that they bear a certain resemblance to the classical bias-variance dilemma. Specifically, we propose a class of anytime algorithms, dubbed Exposure-Capped Reuse (ECR), that combine online change detection, compatibility testing, and "contamination" control. We characterize the regime in which ECR's regret scales with the number of distinct values rather than the number of changes, and derive a novel information-theoretic lower bound that establishes the near-minimax optimality of ECR. This provides rigorous quantification of the statistical "value" of data reuse.

Tomer Gafni, Garud Iyengar, Assaf Zeevi

Columbia University

Statistical Learning Theory Dynamic Regret Minimization

Oct 7, 2026cs.LG

Benign Overfitting under Heterogeneous Input Fusion

Benign overfitting is extensively studied when learning from a single high-dimensional input, but its behavior under heterogeneous input fusion remains largely unexplored. We study this question for minimum-norm linear interpolation under a heterogeneous Gaussian design, comparing two statistically dependent input blocks with their fusion while holding the underlying population task fixed. For regression, we identify a full-spectrum covariance certificate whose asymptotic status is independent of the cutoff threshold and prove that it is preserved by every positive-semidefinite joint covariance consistent with the two marginals. This protection is sharp, yet it does not extend to all benign regression problems: outside the certified regime, two benign marginals can have a harmful fusion. For one-sparse Gaussian classification, benignity in the regular regime is characterized by the balance between surviving predictive signal and nuisance contamination. Fusion can move these two quantities in opposite directions, and within this model class every marginal-to-joint benign/non-benign pattern is attainable. We further show that the same fused input can have qualitatively different effects on regression and classification. These results establish that benign overfitting under heterogeneous fusion is determined by the joint signal and spectral geometry created by input interaction, rather than by marginal benignity alone.

Houzhen Liu, Xiaobo Xia

University of Science and Technology of China

Benign Overfitting Statistical Learning Theory Multimodal Fusion

Oct 6, 2026cs.LG

An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information

Loss-difference conditional mutual information (ld-CMI) uses the smallest of the standard observations in the supersample hierarchy of generalization bounds: it measures what a learner's loss differences reveal about which candidate of each pair it was trained on. Accuracy is known to force information into the model; data processing does not carry such lower bounds to losses. We show, by bounding three moments of the loss differences, that accuracy also forces ld-CMI. For linear predictors with a smooth convex loss of nonzero slope at zero, such as the logistic loss, plus a regularizer whose curvature and growth are both of power

r\ge2

, on product distributions over a scaled sign cube in dimension at least linear in

n

, every proper learner with expected excess risk at most

\varepsilon

on these distributions at the optimal sample size

n\asymp\varepsilon^{-2+2/r}

has worst-case ld-CMI of order

n

bits, and

Θ(n/(1+(τ/\varepsilon)^2))

bits under Gaussian noise of standard deviation

τ

on the loss differences. The same holds without a regularizer, at

n\asymp\varepsilon^{-2}

. Consequently, range-scaled ld-CMI bounds cannot vanish on these distributions, although every proper learner's generalization gap is

O(n^{-1/2})

. We also show that model-level information does not determine noisy loss-difference information, and that the growth, slope and dimension conditions are needed, the last up to a logarithm.

Hazar Yueksel

Statistical Learning Theory Information-Theoretic Generalization Bounds Information-Theoretic Lower Bounds Mutual Information

Oct 6, 2026cs.LG

Exact Dynamics and Finite-Sample Trajectory Recovery of Linear Recursive Feature Machines

Recursive feature machines (RFMs) learn representations of data by alternating between fitting a predictor to a dataset and updating features of that predictor using the average gradient outer product (AGOP). Connections between AGOPs and feature learning in neural networks motivate linear RFMs as a simple setting for analyzing how representations evolve during training. Here, we study the dynamics and statistics of linear RFM in noisy multi-output regression with isotropic sub-Gaussian input data and targets generated by a low-rank teacher matrix of dimension

d

. We extend the known connection between linear RFM and iteratively reweighted least squares from the interpolating setting to ridge-regularized multi-output regression with noise. We show that the learned feature matrix remains close to its infinite-data ideal counterpart at every iteration. Namely, for

n

samples, we show the error in the feature matrix decays as

O(\sqrt{d/n})

with high probability. Experiments on real-world text and single-cell gene-expression data illustrate the features learned by this simple linear model.

Andrew Cheng, Bobak T. Kiani, Yue M. Lu +1

Harvard University · Bowdoin College · Massachusetts Institute of Technology

Statistical Learning Theory

Oct 6, 2026cs.LG

Symmetry-Aware Feature Learning: A Polynomial Separation for Multi-Index Models

We establish a polynomial sample complexity separation between symmetry-aware and symmetry-agnostic feature learning. We study growing-rank multi-index models with high-dimensional Gaussian covariates in

\mathbb{R}^d

and

r=Θ(d^δ)

teacher directions forming a cyclic symmetry orbit, where

0<δ<1/2

. We compare three ways of exploiting this structure: architectural weight sharing, data augmentation over the full symmetry group, and learning without access to the symmetry. In particular, we analyze a symmetry-tied convolutional network, an untied network, and the same untied network trained with full-group data augmentation, using spherical online SGD with correlation loss. For a class of polynomial links with information exponent

p\ge3

, we prove matching sample complexity bounds up to logarithmic factors: the tied and augmented learners achieve weak directional recovery in

\widetildeΘ(d^{p-1})

samples, whereas the symmetry-agnostic learner requires

\widetildeΘ(rd^{p-1})

. For the pure quadratic Hermite link, the same separation holds for weak recovery of the teacher subspace, with sample complexities

\widetildeΘ(d)

and

\widetildeΘ(rd)

, respectively. Thus, full-group data augmentation matches the sample efficiency of architectural weight sharing, and both provide a polynomial advantage over training without symmetry. For

p\ge3

, the proof reveals a two-stage mechanism: fluctuations at initialization select one direction in the teacher orbit, after which localized growth amplifies its overlap to the weak recovery scale while competing overlaps remain near their initialization scale.

Jivan Waber, Vanessa Piccolo, Yatin Dandi +1

Information, Learning and Physics Laboratory École Polytechnique Fédérale de Lausanne (EPFL) · Statistical Physics of Computation Laboratory École Polytechnique Fédérale de Lausanne (EPFL)

Representation Learning Data Augmentation Equivariant Representation Learning Statistical Learning Theory Multi-Index Models

Oct 6, 2026stat.ML

How Many Independent Samples Does a Satellite Image Contain? Generalization Bounds for Spatially Dependent Data

Machine learning classifiers for remote sensing imagery are typically evaluated as though every pixel were an independent sample. Spatial autocorrelation violates this assumption, since neighboring pixels carry redundant information which inflates sample sizes. How many independent samples does a satellite image actually contain? For an

n \times n

image whose spatial correlation persists over a range of

r

pixels, the effective sample size is

Θ(n^2/r^2)

, not

n^2

. We prove this as a finite-sample upper bound for classifiers on spatially correlated data, and show via a matching lower bound that the rate is tight, and no algorithm can do better. We extend the results to images with directional correlation and spatially varying correlation structure. Our result justifies spatial cross-validation since block holdout with separation proportional to the correlation range achieves optimal generalization guarantees, while random holdout can underestimate confidence interval widths by a factor proportional to

r

. We validate the theory on synthetic data and satellite image tiles from three sensors (Landsat 8, Sentinel-2, and Sentinel-1).

Robin Young

Department of Computer Science and Technology University of Cambridge, UK

Spatial Generalization Remote Sensing Statistical Learning Theory Generalization Bounds

Oct 6, 2026stat.ML

Stability of Measure-to-Measure Transformers on Sub-Gaussian Data

Transformers have exhibited impressive empirical success across various domains, but their theoretical foundations remain less developed. This work constitutes a mathematical study of the measure-to-measure operators defined by transformers. We show that transformers map sub-Gaussian inputs to sub-Gaussian outputs; this ensures that taking arbitrary-length compositions of the softmax operator is well-defined. We then show that transformers are Hölder continuous with respect to the 1-Wasserstein distance on appropriate spaces of sub-Gaussian inputs. This allows us to establish estimates on the error propagation along a transformer between a sub-Gaussian input and its empirical approximation. We also study a mean-field analog of the cross-attention mechanism, which is an operator from a pair of probability measures to a single probability measure. We show that cross-attention exhibits different Hölder regularity and sample-complexity in its two input arguments. Last, we apply our results to deduce approximation guarantees for measure-to-measure transformers. Together, these results provide a firm stability and finite-sample theory for transformers on sub-Gaussian data.

Frank Cole, Nicholas H. Nelsen, Takashi Furuya

UCLA · UT Austin · Doshisha University, RIKEN AIP

Transformer Statistical Learning Theory

Oct 6, 2026stat.ML

Uniform Discrete Diffusion Models are Minimax Optimal for Estimating Distributions with Small Effective Support Size

Discrete diffusion models have emerged as a practically successful framework for generative modeling on discrete product spaces, yet their statistical generalization properties remain poorly understood. Discrete real-world data such as text or biological sequences often concentrate on a small fraction of the astronomically large ambient space because of semantic or physical constraints, but existing bounds fail to capture this distributional structure and instead scale with the size of the ambient space, giving rise to almost vacuous error bounds. We address this gap for uniform discrete diffusion, one of the two dominant discrete diffusion paradigms alongside masking diffusion, by deriving statistical guarantees governed by the effective support size

s_n(P_0)

, a sample-size-dependent measure of distributional complexity. Given

n

independent and identically distributed (i.i.d.) samples from an unknown data distribution

P_0

on

[K]^d

, we show that, with appropriate choices of network size and hyperparameters, the expected total variation (TV) loss scales as

O(\sqrt{s_n(P_0)/n})

, while the expected Kullback--Leibler (KL) divergence is bounded by

O(\frac{1}{n}s_n(P_0)\log(eK^d/s_n(P_0))\log n)

. Furthermore, we show that the TV rate is minimax optimal and that the KL rate is minimax optimal up to a factor of

\log n

. Together, these upper and lower bounds show that uniform discrete diffusion successfully avoids the curse of dimensionality for distributions with small effective support size: the TV error rate depends on the ambient state-space size only through

s_n(P_0)

, while the corresponding KL rate incurs only an additional logarithmic dependence on the ambient state-space size.

Dongsun Yoon, Saptarshi Chakraborty

Department of Statistics, University of Michigan

Minimax Estimation Statistical Learning Theory Density Estimation Diffusion Models

Oct 6, 2026stat.ML

Is $\sqrt{d}$ Separation Necessary for Gradient EM to Learn Gaussian Mixtures in High Dimensions?

Learning Gaussian mixture models (GMMs) using the Expectation-Maximization (EM) algorithm and its gradient-based variants is a fundamental problem in machine learning. It is known that randomly initialized (gradient) EM fails to learn multi-component GMMs in the exact-parameterized setting, where the number of components matches that of the ground-truth GMM. Recently, global convergence of gradient EM has been established in the over-parameterized setting, where more components are used, provided that the ground-truth components are well separated. In particular, the minimum separation between ground-truth components is required to scale as

Ω(\sqrt{d})

, where

d

is the dimension. In this paper, we show that this dimensional dependence is unavoidable in high-dimensional settings. Specifically, we consider a hybrid EM algorithm that uses standard EM updates for the mixing weights and gradient EM updates for the component means. For any

ε> 0

, we prove that when the dimension is sufficiently large, in the worst case a separation of order

Ω(d^{0.5-ε})

is insufficient to guarantee global convergence of population gradient EM in sub-exponential time under random initialization, even in the over-parameterized regime. Our result establishes an almost optimal worst-case lower bound on the ground-truth separation required for learning Gaussian mixtures via gradient EM in high dimensions.

Yiran Zhang, Mo Zhou, Weihang Xu +2

University of California, Berkeley · University of Washington · Amazon, Inc.

Gaussian Mixture Models Expectation-Maximization Statistical Learning Theory

Oct 5, 2026quant-ph

Gaussian Universality and Its Breakdown in Tensor-Network Machine Learning

Gaussian-process limits are powerful in describing overparameterized machine learning models, yet their validity in structured tensor-network architectures remains unclear. Here we analytically present a moment-based approach that identifies precise conditions for the emergence and breakdown of Gaussian universality in tensor-network learning models, with a focus on matrix product states. We prove that in the large bond dimension limit, the learning models with both local and global observables converge to Gaussian processes, with explicit finite-size bounds on higher-order moment deviations. Whereas in the large physical dimension limit, the Gaussian universality no longer persists: while the models with local observables retain Gaussian-process behavior, those global cases exhibit persistent non-Gaussian corrections. Our results reveal that Gaussian-process behavior in tensor-network learning is controlled not only by parameter number, but also by architectural scaling, observable locality, and the spectral properties.

Shi-Tuan Wang, Zidu Liu, Li-Wei Yu

Theoretical Physics Division, Chern Institute of Mathematics and LPMC, Nankai University, Tianjin 300071, China · Max Planck Institute of Quantum Optics, 85748 Garching, Germany

Tensor Networks Gaussian Processes Statistical Learning Theory

Oct 1, 2026quant-ph

Classical Hardness of Learning Functions of Hamiltonians

Morohoshi, Nakayama, Manabe, and Mitarai proposed a physically motivated quantum machine learning problem in which the goal is to predict quantities of the form

\operatorname{Tr}[f(H)ρ]

from classical descriptions of a Hamiltonian

H

and a quantum state

ρ

, where

f

is an unknown function. We call this problem Hamiltonian function learning in this paper. They constructed an efficient quantum learning algorithm under suitable conditions, while leaving a rigorous proof of average-case classical hardness open. In this paper, we rigorously prove the average-case classical hardness for two distribution-specific Hamiltonian function learning problems for

f_{\cos,π}(λ)=\cos(πλ)

and

f_{\exp,β}(λ)=e^{-βλ}

discussed in the paper of Morohoshi et al. under the assumption of the average-case hardness of factoring random RSA moduli. More specifically, we show that an efficient classical randomized learner under squared loss whose output hypotheses are evaluable in classical polynomial time for either problem would yield a classical randomized polynomial-time algorithm for factoring random RSA moduli.

Sota Hashimoto, Akinori Kawachi

Graduate School of Engineering, Mie University

Quantum Machine Learning Statistical Learning Theory

Sep 30, 2026stat.ML

Estimation of the Label-Noise Transition Matrix with Performance Guarantees via Selective Classification

Modern machine learning depends heavily on massive datasets, but obtaining high-quality annotations at scale is often expensive. As a result, learning from noisily-labeled data has become common, making accurate estimation of the label-noise transition matrix crucial. However, existing transition matrix estimators rely on the fragile estimation of class-posteriors and do not provide finite-sample performance guarantees. In this work, we propose a novel methodology to estimate the transition matrix based on one-sided selective classification. This approach bypasses class-posterior estimation, provides finite-sample performance guarantees, and leverages flexible learning methods for binary classification. Moreover, we introduce effective algorithms to implement the proposed methodology and provide their refined finite-sample performance bounds.

Xabier de Juan, Santiago Mazuelas, Yilun Zhu +1

Basque Center of Applied Mathematics (BCAM) · IKERBASQUE-Basque Foundation for Science · Electrical and Computer Engineering, University of Michigan

Noisy-Label Learning Statistical Learning Theory

Sep 30, 2026cs.LG

Can Domain Generalization be Guaranteed in Small-Sample Learning?

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.

Hong Zheng

This work was completed during my Ph.D. period and was the result of a flash of inspiration. I decided to submit it to arXiv and leave its value to the readers.

Domain Generalization Statistical Learning Theory Data-Efficient Learning Generalization Bounds

Sep 30, 2026stat.ML

Principal Component Regression Dominates all Monotone Spectral Filters for Linear Regression

We compare the instance-wise, finite-sample risks of monotone spectral filters for linear regression, a broad class of estimators including principal component regression (PCR), gradient descent (GD), and ridge regression. We show that PCR dominates all monotone spectral filters: compared to any such filter, the risk of optimally tuned PCR is no bigger by a constant factor for all problems. Furthermore, the dominance is strong if the filter is separated from step functions (e.g., GD and ridge): there exist problem instances for which the risk of PCR is smaller by a polynomial factor in sample size dependence. Our comparison results show that PCR is optimal and thus admissible among monotone filters, significantly extending Wu et al. (2026)'s result that GD strongly dominates ridge. From a technical perspective, we establish new upper and lower bounds for general spectral filters, which are instance-wise sharp when specialized to ridge or GD, recovering or improving the best-known bounds.

Juno Kim, Hengyu Fu, Peter Bartlett +2

University of California, Berkeley · Google DeepMind

Spectral Regularization Linear Regression Statistical Learning Theory

Sep 30, 2026stat.ML

Asymptotic Properties of Support Vector Machines in High-Dimension, Low-Sample-Size Settings under a Spiked Model

In this paper, we consider asymptotic properties of the support vector machine (SVM) in high-dimension, low-sample-size (HDLSS) settings under a spiked model. The existing theory of the SVM in the HDLSS context relies on the geometric representation of HDLSS data, which requires that the eigenvalues of the covariance matrices are not dominant. We first show that the geometric representation does not hold under the spiked model. We show that the Gram matrix of HDLSS data converges in distribution to a random matrix, namely, the HDLSS data converge to a random configuration in a finite-dimensional space whose dimension is given by the number of the spikes. We show that the misclassification rates of the SVM do not tend to zero, that is, the SVM does not hold the consistency property. We also show that the bias-corrected SVM (BC-SVM) does not give preferable performance in this setting because the bias term itself should be modified. In order to overcome such difficulties, we propose a spike-corrected SVM (SC-SVM). We show that the SC-SVM holds the consistency property when the sample size goes to infinity, and that the growth of the sample size is essential in the sense that any projection-based procedure fails when the sample size is fixed. Finally, we check the performance of the classifiers by numerical simulations.

Yugo Nakayama

Independent researcher

Support Vector Machines Classification Statistical Learning Theory Data-Efficient Learning

Sep 30, 2026stat.ML

Minimax rates for learning spectral Barron functions by deep ReLU neural networks

We study how well deep neural networks approximate and learn spectral Barron functions. Recent studies have shown that these function classes can be efficiently approximated by shallow neural networks without suffering from the curse of dimensionality. We complement these results by providing new approximation bounds for deep networks with ReLU activation and establishing the minimax rates for learning these function classes. Specifically, we show that

d

-dimensional spectral Barron functions with smoothness index

s>0

can be approximated by deep ReLU neural networks with approximation rate

\widetilde{\mathcal{O}} (S^{-\frac{1}{2}-\frac{s}{d}})

, where

S

denotes the number of nonzero parameters in the network. Using this approximation result, we further show that deep ReLU neural networks can learn spectral Barron functions in a fast rate

n^{-\frac{d+2s}{2d+2s}}

with

n

training samples. Finally, we prove that this convergence rate is minimax optimal up to logarithmic factors.

Songqiu Ma, Yunfei Yang

School of Mathematics (Zhuhai), Sun Yat-sen University, Zhuhai, China. · School of Mathematics (Zhuhai) and Guangdong Province Key Laboratory of Computational Science, Sun Yat-sen University, Zhuhai, China.

ReLU Neural Networks Minimax Estimation Neural Network Approximation Theory Statistical Learning Theory

Sep 30, 2026stat.CO

Learn-Then-Differentiate Gradient Estimation

Learn-then-differentiate (LTD) estimates gradients by fitting a model to simulation outputs and differentiating it. We develop a unified framework explaining what LTD differentiates and how accurately it estimates gradients. For models with a weighted representation, LTD differentiates a learned representation of the underlying probability measure. We then show how accuracy guarantees for fitted models translate into guarantees for gradients and higher-order derivatives, with rates approaching the standard Monte Carlo rate under suitable smoothness conditions. The framework recovers established results for kernel regression, local polynomial regression, and kernel ridge regression, and yields further guarantees for multiple kernel learning and smooth neural networks. These results provide a common foundation for understanding and analyzing LTD across learning methods.

Nifei Lin, Qingkai Zhang, L. Jeff Hong

Research Institute for Interdisciplinary Sciences, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai 200433, China · Department of Decision Analytics and Operations, City University of Hong Kong, Hong Kong, China · Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, Minnesota 55455

Statistical Learning Theory

Sep 30, 2026cs.LG

How Accurate Is Accurate Enough?

How accurate must a numerical approximation be within a learning system? Primitive error alone cannot answer this question: errors of the same magnitude can have very different consequences for losses, predictions, and gradients at different learning states. We study this question through the learning objective itself. The objective weights classwise numerical errors nonuniformly according to the current state, so the importance of an error depends not only on its magnitude but also on the class it affects and the weight that class receives. For softmax cross-entropy, we characterize this coupling between class weights and errors and derive the exact extrema of the signed loss change over pairings of fixed non-target probability and score-error multisets, with the target probability and target score error held fixed. Building on this structure, we establish finite-error guarantees that propagate primitive error to losses, probabilities, predictions, and feature gradients, then invert these guarantees to obtain a certified primitive tolerance for the current state under prescribed learning-level error requirements. We give a complete instantiation of the framework in high-dimensional von Mises-Fisher learning. Controlled interventions and a large collection of saved learning states show that identical primitive error can produce substantially different learning consequences, while certified numerical tolerances vary by orders of magnitude across states under the same learning-level requirements. These results show that the adequacy of a numerical approximation must be assessed in relation to the current learning state and the quantity to be preserved; numerical accuracy should itself be treated as part of the learning objective.

Ningkang Peng, Qianfeng Yu, Jingyang Mao +2

Nanjing Normal University · Nanjing University of Chinese Medicine

Statistical Learning Theory

Sep 29, 2026cs.LG

Grokking through the Lens of Minimum-Norm Interpolation

Grokking shows that fitting the training data and learning the underlying signal can occur at very different stages. However, existing theories offer limited quantitative insight into how this delayed generalization depends on inductive bias and signal structure. Our work addresses the gap by developing a statistical theory that characterizes how regularization geometry and signal sparsity govern generalization near interpolation. In particular, we focus on the prototypical setting of high-dimensional regression and identify regimes in which sparsity-promoting regularization makes exact interpolation much more accurate than approximate fitting. In strongly overparameterized noiseless problems, we prove a zero--one generalization law and construct a family of convex norms whose interpolators transition from the trivial risk of the all-zero predictor to exact recovery, while keeping the training error equal to

0

. Furthermore, when feature dimension and sample size are proportional, we provide a precise characterization of training and generalization errors along

\ell_r

-regularization paths. This in turn allows us to quantify the generalization gain that remains near interpolation: we show that this gain increases as the norm becomes more sparsity-promoting and as the target becomes sparser, with a sharp drop in generalization reached for noiseless data and

\ell_1

regularization. Experiments on diagonal linear networks and transformers trained on modular arithmetic demonstrate the generality of our theoretical predictions. Finally, beyond grokking, our work reveals a statistical instability in minimum-norm interpolation: small perturbations in the regularization strength can lead to drastically different generalization, while preserving small training error.

Gil Kur, Ileana Rugina, Clémentine Carla Juliette Dominé +1

ETH Zürich · Institute of Science and Technology Austria · Harvard University

Statistical Learning Theory Implicit Regularization Grokking

Sep 28, 2026stat.ML

Understanding Generalization Requires Universal Induction

Classical statistical theory is insufficient to explain the successes of general-purpose AI models, because it depends on handcrafted inductive biases that it cannot justify. No Free Lunch (NFL) theorems force any learner that beats chance on some environments to underperform on others. We might hope that past experience informs which environments to expect, but NFL applies equally to meta-learning. Thus, any method that makes meaningful predictions necessarily begins with an inductive bias external to the data. Choosing to bias toward short programs yields Solomonoff induction (SI), whose performance is competitive against all computable learners - albeit up to "constants" that become large when comparing against specialized methods that exploit background information. We therefore relativize SI to an information vantage point, biasing toward short programs with access to all preexisting information. This reframes the inductive bias: instead of seeking some absolute notion of simplicity, we favor accessibility with respect to our vantage point. An algorithm can only outpredict the relativized SI to the extent that its code contains additional information about the data, and no algorithm can generate such information. While SI is incomputable and hence not a practical algorithm, it provides a formal optimum for inference in the limit of infinite compute, and there is evidence to suggest that frontier AI systems roughly approximate it. Thus, the only known answer to meta-NFL is rooted in algorithmic information theory, which we should expect to play a fundamental role in explaining the generalization behavior of modern (and future) AI systems.

Aram Ebtekar, Marcus Hutter, Danica J. Sutherland

AIXI Labs · Google DeepMind & ANU · UBC & Amii

Inductive Bias Statistical Learning Theory

Sep 27, 2026stat.ML

An Active-Bottleneck Mechanism for Weak-to-Strong Generalization

Weak-to-strong generalization (W2SG) occurs when a student trained on a teacher's predictions outperforms that teacher. We study when this happens under fully converged, ridgeless two-stage learning, with no early stopping, no explicit regularization, and no assumption that the student is more expressive than the teacher. In two-stage linear regression, a teacher is fit from

n

labeled examples and a student is trained solely on the teacher's predictions on

m

fresh, unlabeled inputs. Although both stages share the same hypothesis class and the same training rule, we show that the student outperforms the teacher exactly when

m

lies in an explicit intermediate range: too few pseudo-labels leave the student without enough signal, too many let it inherit the teacher's noise. Under power-law covariance, we derive this range in closed form as a function of the spectral decay and noise level, including regimes where the improving region splits into two disjoint intervals of

m

. We then study a random-feature model in which the student has strictly more features than the teacher, and identify two regimes, again given by explicit thresholds: one where improvement occurs only for

m

in a bounded interval, and one where it occurs only once the student width

N_S

exceeds an explicit threshold. Both regimes are governed by a single "active-bottleneck" principle: whichever of

m

or

N_S

is scarcer controls how much teacher error is filtered out, while increasing the other resource only reduces estimation noise. Together, these results show that finite data and finite width can themselves regularize a two-stage learner, with no explicit mechanism doing so.

Mohammad Zeinalpour, Amir Najafi

Department of Computer Engineering, Sharif University of Technology

Weak-to-Strong Generalization Pseudo-Labeling Statistical Learning Theory

Sep 27, 2026cs.LG

A Spectral Theory of Compositional Learning

How does compositional reasoning emerge during learning? We address this question by mathematically analyzing the learning dynamics of deep linear networks. We train these networks in structured synthetic environments and derive a theory linking the structure of experience to compositional learning. Our theory predicts when compositional inferences emerge, whether they are identifiable from the available evidence, and how new linking evidence can rapidly unlock previously unavailable inferences. These results provide a qualitative explanation for several phenomena observed in human cognition. They account for why a composition can fail despite knowing its premises, why similar compositions can emerge at different times, and how a single linking fact can suddenly enable many new inferences. Taken together, these findings establish a mathematical link between the statistical structure of experience and the development of compositional reasoning.

Hugo Rydel

University of Manchester

Computational Cognitive Modeling Compositional Reasoning Statistical Learning Theory Compositional Representation Learning

Sep 27, 2026cs.LG

Benign Overfitting for General Norms and Distributions

Understanding why predictors can generalize despite interpolating noisy training data is a central puzzle in machine learning. Most work on such "benign overfitting" studies minimum-2-norm linear regression, reflecting the inductive bias of gradient descent. However, modern optimizers such as Adam and Muon use non-Euclidean update geometries, favoring solutions associated with other norms. Analyzing regression for non-Euclidean norms is substantially more difficult, with known results essentially limited to Gaussians. In this paper, we develop a method to analyze benign overfitting in linear regression for general norms and general (sub-Gaussian) distributions. As a special case, we prove that minimum-p-norm interpolation with p>1 can benignly overfit even for non-Gaussian distributions, under suitable conditions. Perhaps surprisingly, for the 1-norm, benign overfitting does not hold in general for well-behaved (but non-Gaussian) distributions, showing that existing positive 1-norm results rely crucially on Gaussianity. Our proof analyzes the geometry of the dual optimization problem, using concentration and central limit tools to show it is approximately Euclidean in many high-dimensional cases.

Daniel Barzilai, Ohad Shamir

Weizmann Institute of Science · University of Toronto & Vector Institute

Benign Overfitting Statistical Learning Theory

Sep 27, 2026cs.LG

Geometric Identification in Predict-Then-Optimize Learning

Decision-focused surrogates can recover downstream decisions without identifying the quotient report. We characterize the equality set of the convex Smart Predict-then-Optimize surrogate (SPO+) population risk. Under central symmetry, the centered mean class is the unique Bayes minimizer exactly when every nonzero effective displacement makes the old optimizer leave the shifted optimal face with positive probability. This condition separates face crossing from selected-oracle disagreement and gives quantitative local coercivity. Without symmetry, strict crossing alone need not identify the mean; selection balance with reflected crossing restores quotient-report identification, and conditional versions extend the result to measurable predictors. These are population statements, without finite-sample report-recovery or generic transfer-regret guarantees. Closed-form mechanisms reproduce the analytic identities and rates. Portfolio, complete-matrix KuaiRec, and Energy/Storage studies measure predictive fidelity, shifted regret, and fitted-report geometry. A known data-generating process (DGP) companion retains their application geometries while isolating conditional-mean recovery and crossing, without testing the original observational assumptions.

Jiaxiao Xu, Changhong Mou, Keji Liu +2

Shanghai University of Finance and Economics · Utah State University

Predict-Then-Optimize Decision-Focused Learning Statistical Learning Theory

Sep 27, 2026stat.ML

The Statistical Benefits of Multiple Responses for Learning from Demonstrations

Many generative systems return multiple candidate responses and are evaluated according to the best one. Recent work shows that, when demonstrations are optimal, pass@

k

can reduce the sample complexity of learning from demonstrations by a logarithmic factor in

k

. We ask what happens when the demonstrator is not assumed to be optimal. We find that multiple responses provide a qualitatively stronger benefit in this setting. In a finite reward-class model with no reward feedback, moving from pass@

1

to any pass@

k

with

k\ge2

changes the worst-case dependence on target accuracy from

1/\varepsilon^2

to

1/\varepsilon

, uniformly over demonstrator quality. Under standard evaluation, where an unknown reward is fixed before training, increasing

k

provides an additional and distinct benefit: the optimal dependence on a reward class of size

N

improves from

\log N

to

\log N/\log k

. We further show that these two effects can be separated. Under robust evaluation, where one learned policy must compete with the demonstrator simultaneously for every reward in the class, the fast

1/\varepsilon

dependence persists, while the

1/\log k

improvement can disappear. We establish matching upper and lower bounds in the corresponding regimes and give a greedy multiplicative-weights learner achieving the upper bounds without any assumption on demonstrator quality.

Chandramauli Chakraborty, Cong Ma

Department of Statistics, University of Chicago

Learning from Demonstration Statistical Learning Theory Data-Efficient Learning

Sep 23, 2026cs.LG

Even Sharper Bounds for Transductive Learning and Its Applications

We introduce Sharper Transductive Local Complexity (STLC), a localized complexity method for transductive learning under uniform sampling without replacement. The construction starts from a Bernstein-type concentration inequality for the supremum of the test--train empirical process. Its proof uses the modified log-Sobolev inequality for the swap walk and a two-parameter entropy closure. A peeling argument with a surrogate localization functional then gives excess-risk bounds with the same fixed-point and confidence terms as the classical inductive local Rademacher-complexity bounds, without the additional logarithmic confidence factor in earlier transductive results. For realizable learning over a binary class of VC dimension

\dVC

, with training size

m

, test size

u

, and

u\ge m\ge\dVC

, STLC yields

\cO\{\dVC\log(me/\dVC)/m\}

. This matches the standard inductive rate and, when

m\ge9

, is within a logarithmic factor of the transductive minimax lower bound of order

\dVC/m

. For transductive kernel learning, STLC gives a spectrum-adaptive excess-risk bound without the multiplicative imbalance factors appearing in the earlier local-complexity bound.

Yingzhen Yang

Arizona State University, 699 S Mill RD, Tempe, AZ 85281, USA

Transductive Learning Statistical Learning Theory Generalization Bounds

Sep 23, 2026stat.ML

On the Sample Complexity of Active Learning with Membership Queries

This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, we find that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular, some hypothesis classes that are inherently slow to learn in the pool-based setting, achieving only polynomial error decay in the number of samples, become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its complexity. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.

Ganghua Wang, Shaddin Dughmi

Department of Mathematics University of Arizona · Department of Computer Science University of Southern California

Active Learning Statistical Learning Theory

Sep 22, 2026quant-ph

When are bosonic Gaussian states classical to learn?

A fundamental question in physics is: When does classical behavior emerge from quantum systems? Bosonic Gaussian states provide a natural setting to explore this quantum-classical boundary, as they capture both the classical field behavior and the intrinsic quantum nature of light. Here, we address this problem from a learning-theoretic perspective by asking: When are bosonic Gaussian states classical to learn? That is, under what conditions (if any) can an n-mode bosonic Gaussian state be learned with as few samples, and with operations as simple, as are needed to learn a classical 2n-variate Gaussian distribution? We establish a smooth crossover in learnability governed by the state's thermal fluctuations: - Cold Gaussian states are non-classical to learn: When the covariance matrix satisfies

Σ\le(\frac12+O(\frac1n))I

, i.e. close to the vacuum covariance, tomography under single-copy (i.e., non-entangled) measurements fundamentally requires

Ω(n^3)

copies, strictly exceeding the sample complexity

Θ(n^2)

of learning classical Gaussian distributions. We show that this hardness persists even when few-copy entangled measurements are allowed. - Warm Gaussian states are classical to learn: When thermal fluctuations exceed the vacuum noise, parameterized by

Σ\ge(\frac12+ν)I

for any parameter

ν>0

, we prove that single-copy tomography requires

N=Θ\left(n^2\min(n,1+ν^{-1})\right)

copies. This bound is tight and is achieved by simple, non-adaptive, unentangled heterodyne measurements. Crucially, for

ν=Ω(1)

, the sample complexity drops to

Θ(n^2)

, matching the classical case. Our results tightly characterize a quantum-to-classical crossover in the learnability of bosonic Gaussian states, reveal a novel connection between fundamental physics and statistical learning theory, and have implications for real-world sensing experiments.

Senrui Chen, Antonio Anna Mele, Francesco Anna Mele +1

Institute for Quantum Information and Matter, Caltech, Pasadena, CA 91125, USA · Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany

Quantum State Tomography Statistical Learning Theory Information-Theoretic Lower Bounds

Sep 22, 2026stat.ML

Statistical Gains from Looped Estimation under Parameter Budgets

Memory constraints in artificial intelligence motivate accurate function approximation with fewer parameters. We study looping, which repeatedly composes one update function with shared parameters; each output becomes the next input. A looped Transformer, for example, reuses one block, whereas its conventional untied counterpart uses separately parameterized blocks. We compare their parameter requirements for a given worst-case approximation accuracy, or equivalently, their approximation accuracy under a common budget limiting distinct trainable coefficients. We then ask whether this representational parsimony improves statistical accuracy. For general likelihood models, we establish an upper squared Hellinger risk bound for looped sieve maximum likelihood and a minimax lower bound for the jointly tuned untied family. Further loop iterations improve the approximation bound without adding parameters, while increasing computation and the fitted-class complexity bound. For targets of known Hölder smoothness, looped residual feedforward networks and post-layer-normalized Transformers attain the minimax polynomial rate up to logarithmic factors with a fixed number of bounded real parameters. At sufficiently large fixed budgets, looped worst-case risk vanishes while optimal worst-case untied risk remains bounded away from zero. The loop-to-untied risk ratio also tends to zero under specified growing-budget conditions. Regression, binary response, and energy-based generative models illustrate the theory.

Xinyu Tian, Xiaotong Shen

School of Statistics, University of Minnesota

Parameter Estimation Minimax Estimation Neural Network Approximation Theory Statistical Learning Theory