Statistical Learning Theory

Follow this topic Ask about this topic

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

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

Feb 19, 2026

Interactive Learning of Single-Index Models via Stochastic Gradient Descent

Stochastic gradient descent (SGD) is a cornerstone algorithm for high-dimensional optimization, renowned for its empirical successes. Recent theoretical advances have provided a deep understanding of how SGD enables feature learning in high-dimensional nonlinear models, most notably the single-index model with i.i.d. data. In this work, we study the sequential learning problem for single-index models, also known as generalized linear bandits or ridge bandits, where SGD is a simple and natural solution, yet its learning dynamics remain largely unexplored. We show that, similar to the optimal interactive learner, SGD undergoes a distinct burn-in'' phase before entering the learning'' phase in this setting. Moreover, with an appropriately chosen learning rate schedule, a single SGD procedure simultaneously achieves near-optimal (or best-known) sample complexity and regret guarantees across both phases, for a broad class of link functions. Our results demonstrate that SGD remains highly competitive for learning single-index models under adaptive data.

Nived Rajaraman, Yanjun Han

Microsoft Research NYC · Courant Institute of Mathematical Sciences and Center for Data Science, New York University

Single-Index Models Generalized Linear Bandits Stochastic Gradient Descent Statistical Learning Theory

Feb 19, 2026

Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning

Self-distillation (SD) is the process of retraining a student on a mixture of ground-truth labels and the teacher's own predictions using the same architecture and training data. Although SD has been empirically shown to often improve generalization, its formal guarantees remain limited. We study SD for ridge regression in unconstrained setting in which the mixing weight

ξ

may be outside the unit interval. Conditioned on the training data and without any distributional assumptions, we prove that for any squared prediction risk (including out-of-distribution), the optimally mixed student strictly improves upon the ridge teacher for every regularization level

λ> 0

at which the teacher ridge risk

R(λ)

is nonstationary (i.e.,

R'(λ) \neq 0

). We obtain a closed-form expression for the optimal mixing weight

ξ^\star(λ)

for any value of

λ

and show that it obeys the sign rule:

\operatorname{sign}(ξ^\star(λ))=-\operatorname{sign}(R'(λ))

. In particular,

ξ^\star(λ)

can be negative, which is the case in over-regularized regimes. To quantify the risk improvement due to SD, we derive exact deterministic equivalents for the optimal SD risk in the proportional asymptotics regime (where the sample and feature sizes

n

and

p

both diverge but their aspect ratio

p/n

converges) under general anisotropic covariance and deterministic signals. Our asymptotic analysis extends standard second-order ridge deterministic equivalents to their fourth-order analogs using block linearization, which may be of independent interest. From a practical standpoint, we propose a consistent one-shot tuning method to estimate

ξ^\star

without grid search, sample splitting, or refitting. Experiments on real-world datasets and pretrained neural network features support our theory and the one-shot tuning method.

Hien Dang, Pratik Patil, Alessandro Rinaldo

Department of Statistics and Data Sciences, University of Texas, Austin, TX 78712, USA.

Self-Distillation Statistical Learning Theory Ridge Regression

Feb 19, 2026

Bayesian Optimality of In-Context Learning with Selective State Spaces

We propose Bayesian optimal sequential prediction as a new principle for understanding in-context learning (ICL). Unlike interpretations framing Transformers as performing implicit gradient descent, we formalize ICL as meta-learning over latent sequence tasks. For tasks governed by Linear Gaussian State Space Models (LG-SSMs), we prove a meta-trained selective SSM asymptotically implements the Bayes-optimal predictor, converging to the posterior predictive mean. We further establish a statistical separation from gradient descent, constructing tasks with temporally correlated noise where the optimal Bayesian predictor strictly outperforms any empirical risk minimization (ERM) estimator. Since Transformers can be seen as performing implicit ERM, this demonstrates selective SSMs achieve lower asymptotic risk due to superior statistical efficiency. Experiments on synthetic LG-SSM tasks and a character-level Markov benchmark confirm selective SSMs converge faster to Bayes-optimal risk, show superior sample efficiency with longer contexts in structured-noise settings, and track latent states more robustly than linear Transformers. This reframes ICL from "implicit optimization" to "optimal inference," explaining the efficiency of selective SSMs and offering a principled basis for architecture design.

Di Zhang, Jiaqi Xing

School of AI and Advanced Computing Xi’an Jiaotong-Liverpool University Suzhou, Jiangsu, China

In-Context Learning Selective SSMs Bayesian Inference Statistical Learning Theory

Feb 19, 2026

Semi-Supervised Learning on Graphs using Graph Neural Networks

Graph neural networks (GNNs) work remarkably well in semi-supervised node regression, yet a rigorous theory explaining when and why they succeed remains lacking. To address this gap, we study an aggregate-and-readout model that encompasses several common message passing architectures: node features are first propagated over the graph then mapped to responses via a nonlinear function. For least-squares estimation over GNNs with linear graph convolutions and a deep ReLU readout, we prove a sharp non-asymptotic risk bound that separates approximation, stochastic, and optimization errors. The bound makes explicit how performance scales with the fraction of labeled nodes and graph-induced dependence. Approximation guarantees are further derived for graph-smoothing followed by smooth nonlinear readouts, yielding convergence rates that recover classical nonparametric behavior under full supervision while characterizing performance when labels are scarce. Numerical experiments validate our theory, providing a systematic framework for understanding GNN performance and limitations.

Juntong Chen, Claire Donnat, Olga Klopp +1

School of Mathematical Sciences, Xiamen University · Department of Statistics, University of Chicago · ESSEC Business School +1

Graph Neural Networks Graph-Based Semi-Supervised Learning Statistical Learning Theory

Feb 18, 2026

Separating Oblivious and Adaptive Models of Variable Selection

Sparse recovery is among the most well-studied problems in learning theory and high-dimensional statistics. In this work, we investigate the statistical and computational landscapes of sparse recovery with

\ell_\infty

error guarantees. This variant of the problem is motivated by variable selection tasks, where the goal is to estimate the support of a

k

-sparse signal in

\mathbb{R}^d

. Our main contribution is a provable separation between the oblivious (for each'') and *adaptive* (for all'') models of

\ell_\infty

sparse recovery. We show that under an oblivious model, the optimal

\ell_\infty

error is attainable in near-linear time with

\approx k\log d

samples, whereas in an adaptive model,

\gtrsim k^2

samples are necessary for any algorithm to achieve this bound. This establishes a surprising contrast with the standard

\ell_2

setting, where

\approx k \log d

samples suffice even for adaptive sparse recovery. We conclude with a preliminary examination of a partially-adaptive model, where we show nontrivial variable selection guarantees are possible with

\approx k\log d

measurements.

Ziyun Chen, Jerry Li, Kevin Tian +1

University of Washington · University of Texas at Austin

Sparse Recovery Feature Selection Statistical Learning Theory Inverse Problems

Feb 18, 2026

On the Power of Source Screening for Learning Shared Feature Extractors

Learning with shared representation is widely recognized as an effective way to separate commonalities from heterogeneity across various heterogeneous sources. Most existing work includes all related data sources via simultaneously training a common feature extractor and source-specific heads. It is well understood that data sources with low relevance or poor quality may hinder representation learning. In this paper, we further dive into the question of which data sources should be learned jointly by focusing on the traditionally deemed ``good'' collection of sources, in which individual sources have similar relevance and qualities with respect to the true underlying common structure. Towards tractability, we focus on the linear setting where sources share a low-dimensional subspace. We find that source screening can play a central role in statistically optimal subspace estimation. We show that, for a broad class of problem instances, training on a carefully selected subset of sources suffices to achieve minimax optimality, even when a substantial portion of data is discarded. We formalize the notion of an informative subpopulation, develop algorithms and practical heuristics for identifying such subsets, and validate their effectiveness through both theoretical analysis and empirical evaluations on synthetic and real-world datasets.

Leo Muxing Wang, Connor Mclaughlin, Lili Su

Northeastern University

Shared Representation Learning Representation Learning Data Selection Training Data Selection Multi-Task Learning Statistical Learning Theory

Feb 17, 2026

Uniform error bounds for quantized dynamical models

This paper provides statistical guarantees on the accuracy of dynamical models learned from dependent data sequences. Specifically, we develop uniform error bounds that apply to quantized models and imperfect optimization algorithms commonly used in practical contexts for system identification, and in particular hybrid system identification. Two families of bounds are obtained: slow-rate bounds via a block decomposition and fast-rate, variance-adaptive, bounds via a novel spaced-point strategy. The bounds scale with the number of bits required to encode the model and thus translate hardware constraints into interpretable statistical complexities.

Abdelkader Metakalard, Fabien Lauer, Kevin Colin +1

CRAN, SYNALP · ∗Universit´e de Lorraine, CNRS, CRAN, F-54000 Nancy, France · ∗∗Universit´e de Lorraine, CNRS, LORIA, F-54000 Nancy, France +2

System Identification Generalization Bounds Low-Bit Quantization Statistical Learning Theory

Feb 17, 2026

Scenario Approach with Post-Design Certification of User-Specified Properties

The scenario approach is an established data-driven design framework that comes equipped with a powerful theory linking design complexity to generalization properties. In this approach, data are simultaneously used both for design and for certifying the design's reliability, without resorting to a separate test dataset. This paper takes a step further by guaranteeing additional properties, useful in post-design usage but not considered during the design phase. To this end, we introduce a two-level framework of appropriateness: baseline appropriateness, which guides the design process, and post-design appropriateness, which serves as a criterion for a posteriori evaluation. We provide distribution-free upper bounds on the risk of failing to meet the post-design appropriateness; these bounds are computable without using any additional test data. Under additional assumptions, lower bounds are also derived. As part of an effort to demonstrate the usefulness of the proposed methodology, the paper presents two practical examples in H2 and pole-placement problems. Moreover, a method is provided to infer comprehensive distributional knowledge of relevant performance indexes from the available dataset.

Algo Carè, Marco C. Campi, Simone Garatti

Department of Information Engineering - University of Brescia, via Branze 38, 25123 Brescia, Italia · Dipartimento di Elettronica, Informazione e Bioingegneria - Politecnico di Milano, piazza Leonardo da Vinci 32, 20133 Milano, Italia

Generalization Bounds Statistical Learning Theory

Feb 11, 2026

Statistical Inference and Learning for Shapley Additive Explanations (SHAP)

The SHAP (short for Shapley additive explanation) framework has become an essential tool for attributing importance to variables in predictive tasks. In model-agnostic settings, SHAP uses the concept of Shapley values from cooperative game theory to fairly allocate credit to the features in a vector

X

based on their contribution to an outcome

Y

. While the explanations offered by SHAP are local by nature, learners often need global measures of feature importance in order to improve model explainability and perform feature selection. The most common approach for converting these local explanations into global ones is to compute either the mean absolute SHAP or mean squared SHAP. However, despite their ubiquity, there do not exist approaches for performing statistical inference on these quantities. In this paper, we take a semi-parametric approach for calibrating confidence in estimates of the

p

th powers of Shapley additive explanations. We show that, by treating the SHAP curve as a nuisance function that must be estimated from data, one can reliably construct asymptotically normal estimates of the

p

th powers of SHAP. When

p \geq 2

, we show a de-biased estimator that combines U-statistics with Neyman orthogonal scores for functionals of nested regressions is asymptotically normal. When

1 \leq p < 2

(and the hence target parameter is not twice differentiable), we construct de-biased U-statistics for a smoothed alternative. In particular, we show how to carefully tune the temperature parameter of the smoothing function in order to obtain inference for the true, unsmoothed

p

th power. We complement these results by presenting a Neyman orthogonal loss that can be used to learn the SHAP curve via empirical risk minimization and discussing excess risk guarantees for commonly used function classes.

Justin Whitehouse, Ayush Sawarni, Vasilis Syrgkanis

Management Science and Engineering, Stanford University

SHAP Feature Attribution Shapley Value Attribution Semiparametric Inference Statistical Learning Theory

Feb 5, 2026

Fast Rates for Nonstationary Weighted Risk Minimization

Weighted empirical risk minimization is a common approach to prediction under distribution drift. This article studies its out-of-sample prediction error under nonstationarity. We provide a general decomposition of the excess risk into a learning term and an error term associated with distribution drift, and prove oracle inequalities for the learning error under mixing conditions. The learning bound holds uniformly over arbitrary weight classes and accounts for the effective sample size induced by the weight vector, the complexity of the weight and hypothesis classes, and potential data dependence. We also analyze the drift error in the square loss setting and provide explicit bounds for structural-break and smoothly drifting processes. We then combine the learning and drift analysis in (auto-) regression problems with linear models, basis approximations, and neural networks. In all cases, the optimal weights are characterized by a bias--variance trade-off between learning and drift, while minimax-optimal rates (up to logarithmic factors) are recovered when specialized to unweighted and stationary settings.

Tobias Brock, Thomas Nagler

LMU Munich Munich Center for Machine Learning (MCML)

Empirical Risk Minimization Statistical Learning Theory Adaptive Loss Weighting

Feb 5, 2026

Limitations of SGD for Multi-Index Models Beyond Statistical Queries

Understanding the limitations of gradient methods, and stochastic gradient descent (SGD) in particular, is a central challenge in learning theory. To that end, a commonly used tool is the Statistical Queries (SQ) framework, which studies performance limits of algorithms based on noisy interaction with the data. However, it is known that the formal connection between the SQ framework and SGD is tenuous: Existing results typically rely on adversarial or specially-structured gradient noise that does not reflect the noise in standard SGD, and (as we point out here) can sometimes lead to incorrect predictions. Moreover, many analyses of SGD for challenging problems rely on non-trivial algorithmic modifications, such as restricting the SGD trajectory to the sphere or using very small learning rates. To address these shortcomings, we develop a new, non-SQ framework to study the limitations of standard vanilla SGD, for single-index and multi-index models (namely, when the target function depends on a low-dimensional projection of the inputs). Our results apply to a broad class of settings and architectures, including (potentially deep) neural networks.

Daniel Barzilai, Ohad Shamir

Weizmann Institute of Science · University of Toronto

Single-Index Models Statistical Learning Theory Multi-Index Models Stochastic Gradient Descent

Feb 2, 2026

PCA of probability measures: Sparse and Dense sampling regimes

A common approach to perform PCA on probability measures is to embed them into a Hilbert space where standard functional PCA techniques apply. While convergence rates for estimating the embedding of a single measure from

m

samples are well understood, the literature has not addressed the setting involving multiple measures. In this paper, we study PCA in a double asymptotic regime where

n

probability measures are observed, each through

m

samples. We derive convergence rates of the form

n^{-1/2} + m^{-α}

for the empirical covariance operator and the PCA excess risk, where

α>0

depends on the chosen embedding. This characterizes the relationship between the number

n

of measures and the number

m

of samples per measure, revealing a sparse (small

m

) to dense (large

m

) transition in the convergence behavior. Moreover, we prove that the dense-regime rate is minimax optimal for the empirical covariance error. Our numerical experiments validate these theoretical rates and demonstrate that appropriate subsampling preserves PCA accuracy while reducing computational cost.

Gachon Erell, Jérémie Bigot, Elsa Cazelles

Institut de Mathématiques de Bordeaux, Université de Bordeaux, CNRS (UMR 5251) · CNRS, IRIT (UMR 5505), Université de Toulouse

Principal Component Analysis Dimensionality Reduction Statistical Learning Theory

Feb 1, 2026

Theoretical Analysis of Measure Consistency Regularization for Partially Observed Data

The problem of corrupted data, missing features, or missing modalities continues to plague the modern machine learning landscape. To address this issue, a class of regularization methods that enforce consistency between imputed and fully observed data has emerged as a promising approach for improving model generalization, particularly in partially observed settings. We refer to this class of methods as Measure Consistency Regularization (MCR). Despite its empirical success in various applications, such as image inpainting, data imputation and semi-supervised learning, a fundamental understanding of the theoretical underpinnings of MCR remains limited. This paper bridges this gap by offering theoretical insights into when MCR yields a more favorable finite-sample estimation-error upper bound, viewed through the lens of neural network distance. Under ideal interpolation and compatibility conditions, we show that the MCR estimation-error upper bound is no larger than vanilla supervised training and becomes strictly smaller when the mixed-sample alternative is favorable. We then extend the analysis to the non-ideal regime, where optimization and compatibility residuals can potentially offset this finite-sample advantage. Guided by these insights, we propose a novel practical diagnostic that leverages the duality gap and a calibrated drift estimator to infer the potential benefit of MCR training. We present detailed empirical evidence to support our theoretical claims and to show the effectiveness and accuracy of our practical diagnostic. We further provide simulations on real-world datasets to show the versatility of MCR under different model architectures designed for different data sources.

Yinsong Wang, Shahin Shahrampour

University of Nevada Reno, Reno, NV 89557 USA · Department of Mechanical and Industrial Engineering at Northeastern University, Boston, MA 02115 USA

Neural Network Generalization Learning with Missing Data Statistical Learning Theory Consistency Regularization

Jan 31, 2026

Deep networks learn to parse uniform-depth context-free languages from local statistics

Understanding how the structure of language can be learned from sentences alone is a central question in both cognitive science and machine learning. Studies of the internal representations of Large Language Models (LLMs) support their ability to parse text when predicting the next word, while representing semantic notions independently of surface form. Yet, which data statistics make these feats possible, and how much data is required, remain largely unknown. Probabilistic context-free grammars (PCFGs) provide a tractable testbed for studying these questions. However, prior work has focused either on the post-hoc characterization of the parsing-like algorithms used by trained networks; or on the learnability of PCFGs with fixed syntax, where parsing is unnecessary. Here, we (i) introduce a tunable class of PCFGs in which both the degree of ambiguity and the correlation structure across scales can be controlled; (ii) provide a learning mechanism -- an inference algorithm inspired by the structure of deep convolutional networks -- that links learnability and sample complexity to specific language statistics; and (iii) validate our predictions empirically across deep convolutional and transformer-based architectures. Overall, we propose a unifying framework where correlations at different scales lift local ambiguities, enabling the emergence of hierarchical representations of the data.

Jack T. Parley, Francesco Cagnetta, Matthieu Wyart

Institute of Physics, École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland · Theoretical and Scientific Data Science, SISSA, Trieste, Italy · Department of Physics and Astronomy, Johns Hopkins University, Baltimore, Maryland.

Hierarchical Representation Learning Statistical Learning Theory

Jan 27, 2026

Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining

The empirical success of deep learning is often attributed to deep networks' ability to exploit hierarchical structure in data, constructing increasingly complex features across layers. Yet despite substantial progress in deep learning theory, most optimization results sill focus on networks with only two or three layers, leaving the theoretical understanding of hierarchical learning in genuinely deep models limited. This leads to a natural question: can we prove that deep networks, trained with gradient-based methods and standard input-label pairs, can efficiently exploit hierarchical structure? In this work, we consider Random Hierarchy Models -- a hierarchical context-free grammar introduced by arXiv:2307.02129 and conjectured to separate deep and shallow networks. We prove that, under mild conditions, a deep convolutional network can be efficiently trained to learn this function class. Our proof builds on a general observation: if intermediate layers can receive clean signal from the labels and the relevant features are weakly identifiable, then layerwise training each individual layer suffices to hierarchically learn the target function.

Yunwei Ren, Yatin Dandi, Florent Krzakala +1

Princeton University · École Polytechnique Fédérale de Lausanne · University of California, Berkeley

Deep Learning Optimization Hierarchical Representation Learning Convolutional Neural Networks Statistical Learning Theory

Jan 20, 2026

Optimal L2 Regularization in High-dimensional Continual Linear Regression

We study generalization in an overparameterized continual linear regression setting, where a model is trained with L2 (isotropic) regularization across a sequence of tasks. We derive a closed-form expression for the expected generalization loss in the high-dimensional regime that holds for arbitrary linear teachers. We demonstrate that isotropic regularization mitigates label noise under both single-teacher and multiple i.i.d. teacher settings, whereas prior work accommodating multiple teachers either did not employ regularization or used memory-demanding methods. Furthermore, we prove that the optimal fixed regularization strength scales nearly linearly with the number of tasks

T

, specifically as

T/\ln T

. To our knowledge, this is the first such result in theoretical continual learning. Finally, we validate our theoretical findings through experiments on linear regression and neural networks, illustrating how this scaling law affects generalization and offering a practical recipe for the design of continual learning systems.

Gilad Karpel, Edward Moroshko, Ran Levinstein +3

Department of Data and Decisions Sciences, Technion · School of Engineering, University of Edinburgh · Department of Computer Science, Technion +2

Regularization-Based Continual Learning High-Dimensional Linear Regression Statistical Learning Theory

Jan 19, 2026

Approximate full conformal prediction in an RKHS

Full conformal prediction is a framework that implicitly formulates distribution-free confidence prediction regions for a wide range of estimators. However, a classical limitation of the full conformal framework is the computation of the confidence prediction regions, which is usually impossible since it requires training infinitely many estimators (for real-valued prediction for instance). The main purpose of the present work is to describe a generic strategy for designing a tight approximation to the full conformal prediction region that can be efficiently computed. Along with this approximate confidence region, a theoretical quantification of the tightness of this approximation is developed, depending on the smoothness assumptions on the loss and score functions. The new notion of thickness is introduced for quantifying the discrepancy between the approximate confidence region and the full conformal one.

Davidson Lova Razafindrakoto, Alain Celisse, Jérôme Lacaille

Laboratoire SAMM Université Paris 1 Panthéon-Sorbonne 90, rue de Tolbiac 75634 PARIS CEDEX 13, FRANCE · Safran Aircraft Engines Rond-Point René Ravaud, Réau, 77550 Moissy-Cramayel CEDEX, France

Confidence Region Estimation Conformal Prediction Statistical Learning Theory

Jan 5, 2026

Learning with Monotone Adversarial Corruptions

We study the extent to which standard machine learning algorithms rely on exchangeability and independence of data by introducing a monotone adversarial corruption model. In this model, an adversary, upon looking at a "clean" i.i.d. dataset, inserts additional "corrupted" points of their choice into the dataset. These added points are constrained to be monotone corruptions, in that they get labeled according to the ground-truth target function. Perhaps surprisingly, we demonstrate that in this setting, all known optimal learning algorithms for binary classification can be made to achieve suboptimal expected error on a new independent test point drawn from the same distribution as the clean dataset. On the other hand, we show that uniform convergence-based algorithms do not degrade in their guarantees. Our results showcase how optimal learning algorithms break down in the face of seemingly helpful monotone corruptions, exposing their overreliance on exchangeability.

Kasper Green Larsen, Chirag Pabbaraju, Abhishek Shetty

Aarhus University · Stanford University · MIT

Corruption Robustness Binary Classification Statistical Learning Theory

Jan 4, 2026

SGD-Based Knowledge Distillation with Bayesian Teachers: Theory and Guidelines

Knowledge Distillation (KD) is a central paradigm for transferring knowledge from a large teacher network to a typically smaller student model, often by leveraging soft probabilistic outputs. While KD has shown strong empirical success in numerous applications, its theoretical underpinnings remain only partially understood. In this work, we adopt a Bayesian perspective on KD to rigorously analyze the convergence behavior of students trained with Stochastic Gradient Descent (SGD). We study two regimes:

(i)

when the teacher provides the exact Bayes Class Probabilities (BCPs); and

(ii)

supervision with noisy approximations of the BCPs. Our analysis shows that learning from BCPs yields variance reduction and removes neighborhood terms in the convergence bounds compared to one-hot supervision. We further characterize how the level of noise affects generalization and accuracy. Motivated by these insights, we advocate the use of Bayesian deep learning models, which typically provide improved estimates of the BCPs, as teachers in KD. Consistent with our analysis, we experimentally demonstrate that students distilled from Bayesian teachers not only achieve higher accuracies (up to +4.27%), but also exhibit more stable convergence (up to 30% less noise), compared to students distilled from deterministic teachers.

Itai Morad, Nir Shlezinger, Yonina C. Eldar

School of ECE, Ben-Gurion University, Be’er Sheva, Israel · Faculty of Math and CS, Weizmann Institute of Science, Rehovot, Israel

Statistical Learning Theory Teacher-Student Learning Knowledge Distillation

Dec 20, 2025

The Challenger: When Do New Data Sources Justify Switching Machine Learning Models?

Organizations often have an incumbent predictive model in production when new data sources become available. Because historical training data lack the new features, a challenger model must be trained on a small but growing full-feature dataset. We study whether, and when, the organization should switch to the challenger. The decision is statistical and economic: the challenger's predictive performance improves as full-feature data accumulate, but repeated retraining is costly and delays benefits from deployment. We develop a framework linking learning-curve dynamics to model-switching economics. Under a standard power-law learning curve and finite data-collection horizon

T

, the optimal time to train and evaluate the challenger scales as

T^{1/(1+α)}

: learning-curve shape (through its learning speed

α

) is the primary theoretical determinant of when to stop experimenting; costs determine switching profitability. Even without knowing the learning curve, the operational problem is tractable: we show that any algorithm stopping on the

T^{2/3}

scale and making reliable switch/discard decisions achieves

O(T^{2/3}\sqrt{\log T})

regret relative to a full-foresight oracle. We propose a sequential evaluation algorithm that uses local learning-curve trends to anticipate improvement, and test it in a real-world credit-scoring study. Even with this local approximation, the algorithm theoretically and empirically achieves near-oracle performance. It is also more stable than greedy sequential evaluation algorithms, where noisy early estimates trigger premature discarding, or simple one-shot evaluation algorithms, which work only when their fixed evaluation time matches the (unknown in practice) theoretical timing scale. Our framework offers a step toward principled model governance when new data sources require costly collection, validation, and deployment.

Vassilis Digalakis, Christophe Pérignon, Sébastien Saurin +1

Boston University · HEC Paris

Sequential Decision Making Learning Curves Credit Scoring Statistical Learning Theory

Dec 16, 2025

Maximum Mean Discrepancy with Unequal Sample Sizes via Generalized U-Statistics

Existing two-sample testing techniques, particularly those based on choosing a kernel for the Maximum Mean Discrepancy (MMD), often assume equal sample sizes from the two distributions. Applying these methods in practice can require discarding valuable data, unnecessarily reducing test power. We address this long-standing limitation by extending the theory of generalized U-statistics and applying it to the usual MMD estimator, resulting in new characterization of the asymptotic distributions of the MMD estimator with unequal sample sizes (particularly outside the proportional regimes required by previous partial results). This generalization also provides a new criterion for optimizing the power of an MMD test with unequal sample sizes. Our approach preserves all available data, enhancing test accuracy and applicability in realistic settings. Along the way, we give much cleaner characterizations of the variance of MMD estimators, revealing something that might be surprising to those in the area: while zero MMD implies a degenerate estimator, it is sometimes possible to have a degenerate estimator with nonzero MMD as well; we give a construction and a proof that it does not happen in common situations.

Aaron Wei, Milad Jalali, Danica J. Sutherland

University of British Columbia · Independent researcher, Vancouver, Canada · Alberta Machine Intelligence Institute

Two-Sample Testing Maximum Mean Discrepancy Statistical Learning Theory Statistical Hypothesis Testing U-Statistics

Dec 5, 2025

Learnability Window in Gated Recurrent Neural Networks

We develop a statistical theory of temporal learnability in recurrent neural networks, quantifying the maximal temporal horizon

\mathcal{H}_N

over which gradient-based learning can recover lag-dependent structure at finite sample size

N

. The theory is built on the effective learning rate envelope

f(\ell)

, a function that captures how gating mechanisms and adaptive optimizers jointly shape the coupling between state-space dynamics and parameter updates during Backpropagation Through Time. Under heavy-tailed (

α

-stable) fluctuations, where empirical averages concentrate at rate

N^{-1/κ_α}

with

κ_α= α/(α-1)

, the interplay between envelope decay and statistical concentration yields explicit scaling laws for the growth of

\mathcal{H}_N

: logarithmic, polynomial, and exponential temporal learning regimes emerge according to the decay law of

f(\ell)

. These results identify envelope decay as the key determinant of temporal learnability. Slower attenuation of

f(\ell)

enlarges

\mathcal{H}_N

, while heavy-tailed fluctuations compress it by weakening statistical concentration. Moreover, envelope geometry outweighs dataset size: slowing the envelope's decay enlarges

\mathcal{H}_N

more than adding data, so more complex architectures that realize slower-decaying envelopes can be more data-efficient than simpler ones. Experiments across multiple gated architectures and optimizers corroborate these structural predictions.

Lorenzo Livi

OPIT – Open Institute of Technology

Gated Recurrent Unit Recurrent Neural Networks Neural Network Training Dynamics Statistical Learning Theory

Dec 4, 2025

Provable FDR Control for Deep Feature Selection: Deep MLPs and Beyond

We develop a flexible feature selection framework based on deep neural networks that approximately controls the false discovery rate (FDR), a measure of Type-I error. The method applies to architectures whose first layer is fully connected. From the second layer onward, it accommodates multilayer perceptrons (MLPs) of arbitrary width and depth, convolutional and recurrent networks, attention mechanisms, residual connections, and dropout. The procedure also accommodates stochastic gradient descent with data-independent initializations and learning rates. To the best of our knowledge, this is the first work to provide a theoretical guarantee of FDR control for feature selection within such a general deep learning setting. Our analysis is built upon a multi-index data-generating model and an asymptotic regime in which the feature dimension

n

diverges faster than the latent dimension

q^{*}

, while the sample size, the number of training iterations, the network depth, and hidden layer widths are left unrestricted. Under this setting, we show that each coordinate of the gradient-based feature-importance vector admits a marginal normal approximation, thereby supporting the validity of asymptotic FDR control. As a theoretical limitation, we assume

\mathbf{B}

-right orthogonal invariance of the design matrix, and we discuss broader generalizations. We also present numerical experiments that underscore the theoretical findings.

Kazuma Sawaya

The University of Tokyo, Bunkyo, Tokyo, Japan

FDR Control Feature Selection Statistical Learning Theory Multiple Hypothesis Testing

Nov 28, 2025

A Unified and Stable Risk Minimization Framework for Weakly Supervised Learning with Theoretical Guarantees

Weakly supervised learning has emerged as a practical alternative to fully supervised learning when complete and accurate labels are costly or infeasible to acquire. However, many existing methods are tailored to specific supervision patterns -- such as positive-unlabeled (PU), unlabeled-unlabeled (UU), complementary-label (CLL), partial-label (PLL), or similarity-unlabeled annotations -- and rely on post-hoc corrections to mitigate instability induced by indirect supervision. We propose a principled, unified framework that bypasses such post-hoc adjustments by directly formulating a stable surrogate risk grounded in the structure of weakly supervised data. The formulation naturally subsumes diverse settings -- including PU, UU, CLL, PLL, multi-class unlabeled, and tuple-based learning -- under a single optimization objective. We further establish a non-asymptotic generalization bound via Rademacher complexity that clarifies how supervision structure, model capacity, and sample size jointly govern performance. Beyond this, we analyze the effect of class-prior misspecification on the bound, deriving explicit terms that quantify its impact, and we study identifiability, giving sufficient conditions -- most notably via supervision stratification across groups -- under which the target risk is recoverable. Extensive experiments show consistent gains across class priors, dataset scales, and class counts -- without heuristic stabilization -- while exhibiting robustness to overfitting.

Miao Zhang, Junpeng Li, Changchun Hua +1

Engineering Research Center of the Ministry of Education for Intelligent Control System and Intelligent Equipment, Yanshan University, Qinhuangdao, China

Weakly Supervised Learning Statistical Learning Theory Positive-Unlabeled Learning Generalization Bounds

Nov 14, 2025

Learning and Testing Convex Functions

We consider the problems of learning and testing real-valued convex functions over Gaussian space. Despite the extensive study of function convexity across mathematics, statistics, and computer science, its learnability and testability have largely been examined only in discrete or restricted settings -- typically with respect to the Hamming distance, which is ill-suited for real-valued functions. In contrast, we study these problems in high dimensions under the standard Gaussian measure, assuming sample access to the function and a mild smoothness condition, namely Lipschitzness. A smoothness assumption is natural and, in fact, necessary even in one dimension: without it, convexity cannot be inferred from finitely many samples. As our main results, we give: - Learning Convex Functions: An agnostic proper learning algorithm for Lipschitz convex functions that achieves error

\varepsilon

using

n^{O(1/\varepsilon^2)}

samples, together with a complementary lower bound of

n^{\mathrm{poly}(1/\varepsilon)}

samples in the correlational statistical query (CSQ) model. - Testing Convex Functions: A tolerant (two-sided) tester for convexity of Lipschitz functions with the same sample complexity (as a corollary of our learning result), and a one-sided tester (which never rejects convex functions) using

O(\sqrt{n}/\varepsilon)^n

samples.

Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel +1

Columbia University · Harvard University · MIT

Statistical Learning Theory

Nov 5, 2025

Sparse, self-organizing ensembles of local kernels detect rare statistical anomalies

Modern artificial intelligence has revolutionized how we extract representations from scientific data, yet the statistical properties of these representations remain poorly controlled, causing misspecified anomaly detection methods to falter. The hardest anomalies to detect are the rare, weakly separable ones hiding within the nominal distribution-a regime that grows in importance as models mature and easily separable signals are exhausted. We identify structural desiderata for detection in this regime under minimal prior information: sparsity, to enforce parsimony; locality, to preserve geometric sensitivity; and competition, to promote efficient allocation of model capacity. These principles define a class of self-organizing local kernels that adaptively partition the representation space around regions of statistical imbalance. As an instantiation, we introduce SparKer, a sparse ensemble of Gaussian kernels trained in a semi-supervised Neyman-Pearson framework to locally model the likelihood ratio between a sample that may contain anomalies and an anomaly-free reference. We provide theoretical insights into the mechanisms driving detection and self-organization, and demonstrate the approach on realistic high-dimensional problems in scientific discovery, open-world novelty detection, intrusion detection, and generative-model validation. Ensembles of only a handful of kernels identify statistically significant anomalies in representation spaces of thousands of dimensions while remaining sensitive across regimes, underscoring the interpretability, efficiency, and scalability of the approach.

Gaia Grosso, Sai Sumedh R. Hindupur, Thomas Fel +3

NSF AI Institute for Artificial Intelligence and Fundamental Interactions, Cambridge, 02139, MA · Laboratory for Nuclear Science, Massachusetts Institute of Technology, Cambridge, 02139, MA · School of Engineering and Applied Sciences, Harvard University, Allston, 02134, MA +1

Kernel Methods Semi-Supervised Anomaly Detection Statistical Learning Theory Anomaly Detection

Nov 4, 2025

Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning

We study computable probably approximately correct (CPAC) learning, where learners are required to be computable functions. It had been previously observed that the Fundamental Theorem of Statistical Learning, which characterizes PAC learnability by finiteness of the Vapnik-Chervonenkis (VC-)dimension, no longer holds in this framework. Recent works recovered analogs of the Fundamental Theorem in the computable setting, for instance by introducing an effective VC-dimension. Guided by this, we investigate the connection between CPAC learning and recursively enumerable representable (RER) classes, whose members can be algorithmically listed. Our results show that the effective VC-dimensions can take arbitrary values above the traditional one, even for RER classes, which creates a whole family of (non-)examples for various notions of CPAC learning. Yet the two dimensions coincide for classes satisfying sufficiently strong notions of CPAC learning. We then observe that CPAC learnability can also be characterized via containment of RER classes that realize the same samples. Furthermore, it is shown that CPAC learnable classes satisfying a unique identification property are necessarily RER. Finally, we establish that agnostic learnability can be guaranteed for RER classes, by considering the relaxed notion of nonuniform CPAC learning.

David Kattermann, Lothar Sebastian Krapp

Institute for Symbolic Artificial Intelligence, Johannes Kepler University Linz, Austria. · Department of Mathematics and Statistics, University of Konstanz, Germany. · Institute for the Interdisciplinary Study of Language Evolution, University of Zurich, Switzerland.

PAC Learning Statistical Learning Theory

Oct 27, 2025

Optimal In-context Adaptivity and Distributional Robustness of Transformers

We study in-context learning problems where a Transformer is pretrained on tasks drawn from a mixture distribution

π=\sum_{α\in\mathcal{A}} λ_α π_α

, called the pretraining prior, in which each mixture component

π_α

is a distribution on tasks of a specific difficulty level indexed by

α

. Our goal is to understand the performance of the pretrained Transformer when evaluated on a different test distribution

μ

, consisting of tasks of fixed difficulty

β\in\mathcal{A}

, and with potential distribution shift relative to

π_β

, subject to the chi-squared divergence

χ^2(μ,π_β)

being at most

κ

. In particular, we consider nonparametric regression problems with random smoothness, and multi-index models with both random smoothness and random effective dimension. We prove that a large Transformer pretrained on sufficient data achieves the optimal rate of convergence corresponding to the difficulty level

β

, uniformly over test distributions

μ

in the chi-squared divergence ball. Thus, the pretrained Transformer is able to achieve faster rates of convergence on easier tasks and is robust to distribution shift at test time. Finally, we prove that even if an estimator had access to the test distribution

μ

, the convergence rate of its expected risk over

μ

could not be faster than that of our pretrained Transformers, thereby providing a more appropriate optimality guarantee than minimax lower bounds.

Tianyi Ma, Tengyao Wang, Richard J. Samworth

Statistical Laboratory, University of Cambridge · Department of Statistics, London School of Economics and Political Science

In-Context Learning Distribution Shift Robustness Statistical Learning Theory Distributionally Robust Optimization Nonparametric Regression

Oct 27, 2025

Complexity Dependent Error Rates for Physics-informed Statistical Learning via the Small-ball Method

Physics-informed statistical learning (PISL) integrates empirical data with physical knowledge to enhance the statistical performance of estimators. While PISL methods are widely used in practice, a comprehensive theoretical understanding of how informed regularization affects statistical properties is still missing. Specifically, two fundamental questions have yet to be fully addressed: (A) what is the trade-off between soft penalties and hard constraints, and (B) what is the statistical gain of incorporating physical knowledge compared to purely data-driven empirical error minimisation. In this paper, we address these questions for PISL in classes of functions whose convex hull satisfies a small-ball condition, in particular convex classes, under physical knowledge expressed as linear equations by developing appropriate complexity dependent error rates based on the small-ball method. We specialise them to linear classes of finite dimension

q

in which the space of solutions of the equation has dimension

k < q

, and show that (A) the physics-informed estimator attains the error bound of the hard-constrained empirical error minimiser whenever the penalty parameter is above an explicit threshold, and that (B) the penalty improves the error rate from

\sqrt{q/n}

to

\sqrt{k/n}

under a second moment condition on the noise only, having the effect of a dimensionality reduction. We also quantify how these conclusions degrade when the equation is misspecified, in terms of the excess residual of the target function. This work establishes a theoretical framework for evaluating the statistical properties of physics-informed estimators in such classes, contributing to closing the gap between statistical theory and practical PISL.

Diego Marcondes

Physics-Informed ML Statistical Learning Theory Empirical Risk Minimization

Oct 16, 2025

Predicting kernel regression learning curves from only raw data statistics

We study kernel regression with common rotation-invariant kernels on real datasets including CIFAR-5m, SVHN, and ImageNet. We give a theoretical framework that predicts learning curves (test risk vs. sample size) from only two measurements: the empirical data covariance matrix and an empirical polynomial decomposition of the target function

f_*

. The key new idea is an analytical approximation of a kernel's eigenvalues and eigenfunctions with respect to an anisotropic data distribution. The eigenfunctions resemble Hermite polynomials of the data, so we call this approximation the Hermite eigenstructure ansatz (HEA). We prove the HEA for Gaussian data, but we find that real image data is often "Gaussian enough" for the HEA to hold well in practice, enabling us to predict learning curves by applying prior results relating kernel eigenstructure to test risk. Extending beyond kernel regression, we empirically find that MLPs in the feature-learning regime learn Hermite polynomials in the order predicted by the HEA. Our HEA framework is a proof of concept that an end-to-end theory of learning which maps dataset structure all the way to model performance is possible for nontrivial learning algorithms on real datasets.

Dhruva Karkada, Joseph Turnbull, Yuxi Liu +1

UC Berkeley · Imbue

Kernel Regression Kernel Methods Statistical Learning Theory Learning Curves