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

Jul 29, 2026stat.ML

Feature Bagging Provides Stability

We study feature bagging through the lens of algorithmic stability. Feature bagging is an ensemble strategy that aggregates base learners trained on randomly subsampled feature subsets, possibly in a data-dependent manner. We introduce feature instability (FI), the feature-axis analogue of instance instability (II), which measures sensitivity to removing a single feature. Smaller values of II or FI correspond to stronger stability, and our experiments show that FI captures generalization-relevant information complementary to II. Within this framework, we analyze feature bagging in both a parametric linear model and a model-free setting inspired by recursive feature subsampling in random forests. In both settings, we establish formal guarantees showing that feature bagging improves the relevant stability relative to its non-bagged counterpart, with larger improvements under more aggressive subsampling. We further show that a modest number of bagging rounds is sufficient to approach the infinite-bagging stability level.

Yuheng Ma, Qiang Sun

School of Statistics, East China Normal University · University of Toronto · MBZUAI

Ensemble Learning Algorithmic Stability Statistical Learning Theory

Jul 29, 2026cs.LG

Simultaneous Coverage and Efficiency Guarantee in Online Conformal Prediction

Adaptive conformal inference (ACI) of Gibbs and Cand{è}s and its variants are the standard approach to online conformal prediction under distribution shift, but they suffer from three fundamental limitations. First, their guarantees control only the \emph{signed} long-run coverage error: persistent miscoverage in one direction can be masked by compensating errors later, so a method can satisfy the theoretical guarantee while being badly wrong for extended periods. Second, existing guarantees say nothing about prediction-set size, so validity can be achieved trivially at the cost of unduly wide prediction sets. Third, the efficiency guarantees that do exist compare against a \emph{fixed} predictor chosen in hindsight, a benchmark that becomes increasingly less meaningful once the data-generating distribution shifts, since the very notion of an optimal threshold then changes over time. We consider a unified online learning framework that simultaneously controls absolute, non-cancelling coverage violation and prediction-set efficiency against a dynamically evolving benchmark for three important models. In the fully adversarial setting, exploiting the fact that the standard ACI update is exactly projected online gradient descent on the pinball loss, we derive simultaneous coverage and efficiency guarantees for arbitrary monotone Lipschitz efficiency objectives, with no distributional or {\it convexity} assumptions. In the stochastic setting with full-score feedback, we propose a sliding-window quantile tracker and establish a matching minimax lower bound showing our algorithm is rate-optimal. In the covariate-dependent stochastic setting, we develop a partitioned ACI algorithm that tracks a function-valued oracle threshold, and derive simultaneous coverage and efficiency guarantees.

Rahul Vaze

Tata Institute of Fundamental Research, Mumbai

Set Prediction Conformal Prediction Adaptive Conformal Inference Statistical Learning Theory

Jul 27, 2026cs.DS

Learning Distributions from Multiple Data Providers

Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to learn an unknown distribution

p

on a finite domain

[n]

. The learner is given a fixed family of queryable sets

\mathscr{S} \subseteq 2^{[n]}

, and each query to

S \in \mathscr{S}

returns an independent sample from the conditional distribution

p(\cdot \mid S)

. Learnability is governed by the co-occurrence graph associated with

\mathscr{S}

: two domain elements are adjacent if they appear together in some queryable set. Pointwise consistency is achievable when this graph is connected on the target support. PAC learning requires more: it is possible when the co-occurrence graph is complete. The optimal sample complexity of PAC learning ranges from nearly linear to quadratic. Every query family with complete co-occurrence graph admits sample complexity

\widetilde O(n^2/ε^2)

, and this bound is tight in the worst case. On the other hand, if

[n]

is queryable then ordinary sampling improves the bound to

Θ(n/ε^2)

, and this cannot be improved further even if every set is queryable. More generally, we identify hierarchical comparabilityas a sufficient structural condition on

\mathscr S

under which the optimal complexity is nearly linear,

\widetilde Θ(n/ε^2)

, with pairwise query families as a canonical example. Finally, the full range of polynomial rates between linear and quadratic is attainable: for every

α\in (1,2)

, there exists a query family with optimal PAC rate

\widetilde Θ(n^α/ε^2)

.

Jon Kleinberg, Amin Saberi, Xizhi Tan +1

Cornell University · Stanford University · Google Research

Statistical Learning Theory

Jul 26, 2026stat.ML

Learning switched non-linear dynamical systems from a single trajectory

We study empirical risk minimization for learning non-linear dynamical systems whose transition dynamics may switch over time. Under stability assumptions, and i.i.d switching over a set of

K

modes, we derive non-asymptotic bounds on the prediction risk expressed in terms of the metric entropy of the underlying function class. We instantiate our general result for Hölder and linear function classes, obtaining explicit convergence rates that depend on the effective sample size

Tp_i

, where

T

is the trajectory length and

p_i

is the probability of observing mode

i

. Numerical simulations support our theoretical findings. To the best of our knowledge, these results are the first non-asymptotic guarantees for learning switched nonlinear dynamical systems from a single trajectory.

Sunny G. W. Wang, Hemant Tyagi

Division of Mathematical Sciences, SPMS, NTU Singapore 637371

Regime-Switching Dynamical Systems Nonlinear System Identification System Identification Statistical Learning Theory Empirical Risk Minimization

Jul 26, 2026cs.LG

Generalization bounds and sample complexity for remaining useful life prediction from complete degradation trajectories

Data-driven remaining useful life (RUL) prediction requires complete degradation trajectories for training, yet such run-to-failure data are scarce and expensive. Practitioners currently lack principled guidance on how many failure examples suffice for a given model and accuracy target. This paper develops a sample complexity framework for RUL prediction comprising seven main results organised around three themes. First, we establish fundamental learning rates: a distribution-free generalization bound shows that the uniform deviation of the mean squared error decreases as

O(B^{2}\sqrt{p/n})

, where

p

is the model complexity and

n

the number of trajectories, and a minimax lower bound proves that the

Θ(p/n)

rate is unimprovable.} \rev{Second, we quantify how domain knowledge accelerates learning: incorporating degradation physics reduces data requirements by up to two orders of magnitude for deep networks, a Bernstein-type analysis achieves the minimax-optimal

O(p/n)

rate under high signal-to-noise conditions, and closed-form penalties reveal when an incorrectly assumed physics model hurts rather than helps. Third, we characterise the impact of data quality: fleet variability induces an irreducible bias

-

variance tradeoff, while right-censored observations suffer an efficiency loss that depends critically on the degradation class.} Closed-form expressions are provided for exponential, power-law, and stretched-exponential degradation. \rev{Cross-domain validation against published turbofan, battery, and bearing benchmarks confirms the theoretical predictions within a factor of 2

-

3 on average. The results yield practical guidelines for planning data collection, selecting model complexity, and evaluating physics model assumptions in prognostics applications.

Huy Hoang Le, Kim-Anh Nguyen

R&D Department, PowerMore Ltd., Da Nang 550000, Vietnam · Faculty of Electrical Engineering, University of Science and Technology, The University of Danang, Da Nang 550000, Vietnam

RUL Estimation Sample Complexity Physics-Informed ML Statistical Learning Theory

Jul 26, 2026cs.LG

Local Regularization Does Not Characterize Multiclass PAC Learnability

Local regularization assigns each hypothesis a test-point-dependent score and predicts with a minimum-score hypothesis consistent with the sample. Asilis et al. asked whether this principle characterizes multiclass PAC learnability. We give a negative answer. There is a countable class of Daniely--Shalev-Shwartz dimension at most two with realizable PAC sample complexity

O\!\left(\frac{1}{\varepsilon}\log\frac{1}δ\right),

that no local regularizer learns. Hypotheses are edges of complete graphs and instances are tournaments. At a test tournament, the scores fix an edge ranking while the training sample independently removes competitors. Cyclic triangles force enough inversions that surviving competitors produce constant population error at arbitrarily large sample sizes.

Eric Hou

Multiclass Classification Classification PAC Learning Statistical Learning Theory

Jul 24, 2026stat.ML

Learning Ergodic Dynamical Systems from a Finite Trajectory

We consider the problem of learning from a single finite trajectory of an ergodic stochastic dynamical system. More precisely, we study discrete-time autonomous stochastic systems defining time-homogeneous Markov processes. We first focus on estimating the optimal one-step prediction function by nonlinear least squares, and derive high-probability guarantees measured with respect to the invariant measure of the process. These results make explicit how the non-independent and non-identically distributed nature of trajectory data modifies the classical statistical learning analysis. We then extend the framework to higher-order systems and finite-state spaces. Finally, we show that the same least squares and concentration arguments naturally extend to learning Koopman operators. Our approach combines tools from statistical learning theory and quantitative ergodic theory for Markov chains. It relies, in particular, on a concentration inequality for Hilbert-space-valued additive functionals of uniformly geometrically ergodic Markov chains.

Oleksii Kachaiev, Silvia Villa, Lorenzo Rosasco

MaLGa center, DIMA, Università degli Studi di Genova, Genoa, Italy · Istituto Italiano di Tecnologia, Genoa, Italy · MaLGa center, DIBRIS, Università degli Studi di Genova, Genoa, Italy

Koopman Operator Learning Markov Models Nonlinear System Identification System Identification Statistical Learning Theory

Jul 23, 2026cs.LG

Smart predict-then-robustly-optimize

In this paper, we propose and study a robust variant of the smart predict-then-optimize approach that accounts for prediction shifts due to disturbance in the covariate feature space. While traditional integrated-learning-and-optimization models assume that side information is perfectly revealed, empirical data-driven features are frequently corrupted or noisy at the time of decision-making, leading to fragile operational policies. To bridge this gap, we integrate principles of robust optimization directly into the predictive-prescriptive pipeline via a smart predict-then-robustly optimize loss and establish a computationally tractable convex surrogate, designed to hedge against worst-case feature perturbations. On the theoretical front, we formalize the structural validity of this surrogate by proving its approximation error probability decays exponentially according to a sub-Gaussian concentration profile. Furthermore, we establish that under mild assumptions, the surrogate is Fisher consistent with high probability. We also prove necessary conditions under which our framework outperforms standard smart predict-then-optimize and maintain its superiority even when the standard method is equipped with regularized upstream predictions. Numerical experiments validate that our robust framework consistently yields significant performance improvements over standard methods, both in out-of-sample terms and in training stability.

Aakil Caunhye, Xuefei Lu, Belen Martin-Barragan

Distribution Shift Robustness Predict-Then-Optimize Decision-Focused Learning Robust Optimization Robust Loss Functions Statistical Learning Theory

Jul 23, 2026math.CO

Encoding orders and trees in real-valued functions

We prove function-theoretic analogues of a quantitative result of Hodges on extracting the order property from a sufficiently large 2-tree coded in a binary relation. Similar analogues for functions were previously obtained by Daskalakis and Golowich and by Anderson and Benedikt. These results are from statistical learning theory, where 2-trees are captured by sequential fat-shattering dimension, and the order property is controlled by various notions of "thresholds". Our first main result (Theorem 1.11) focuses on extracting a less restrictive kind of threshold from a tree, and yields significantly better bounds compared to what can be obtained from earlier results focusing on more restrictive versions. Part of the motivation for Theorem 1.11 lies in a companion paper, where this theorem is used to obtain efficient bounds in quantitative regularity lemmas for "stable functions". Here will use Theorem 1.11 to reprove a result of Anderson and Benedikt in a stronger form and with improved bounds. We also use Theorem 1.11 to prove an at most double-exponential bound on dual sequential fat-shattering, which resolves an open problem. In our second main result (Theorem 1.14), we give a new proof of a result of Daskalakis and Golowich on extracting "tight thresholds" from large sequential fat-shattering dimension, with improved bounds. This resolves another open problem related to correcting the proof of a result claimed by Jung, Kim, and Tewari.

G Conant, C Terry

Statistical Learning Theory

Jul 22, 2026cs.LG

Fisher Widths: Local Learning Geometry and Anisotropic Recovery

We study Gaussian-width complexity on statistical manifolds through a pair of functionals: the primal Fisher width

w_G(T) = w(G^{1/2}T)

, induced by the Fisher metric, and the inverse-Fisher width

w_{G^{-1}}(T) = w(G^{-1/2}T)

, induced by the inverse Fisher metric. The two widths play complementary statistical roles. On the learning side, the Fisher width measures the size of local parameter fluctuations in the geometry induced by the Fisher information. For Fisher-regular losses, we prove that the scale

w_G(H_r)/\sqrt n

is attained on sufficiently small Fisher balls. On the recovery side, the inverse-Fisher width captures the effect of anisotropic Gaussian measurements whose covariance is determined by the inverse Fisher information. For sparse recovery, the resulting geometry depends not only on sparsity but also on the position of the active coordinates in the Fisher spectrum. We obtain a two-sided estimate for the corresponding statistical dimension, together with support-sensitive recovery estimates and a natural ordering of supports with different curvature profiles. Finally, we establish a sharp relation between the primal and inverse-Fisher widths. On any common compact coordinate set

T

, they satisfy

w_G(T)w_{G^{-1}}(T)\geq w(T)^2.

Thus, Fisher anisotropy may transfer complexity from one geometry to the other, but cannot reduce both widths relative to the Euclidean scale.

Vu Khac Ky

Department of Mathematics, FPT University, Vietnam

Information Geometry Sparse Recovery Statistical Learning Theory

Jul 21, 2026stat.ML

Fundamental limits of distributed multiclass classification from simple binary decisions

We consider the problem of constructing a

K

-class classifier from the combination of

O(\log K)

simple binary classifiers -- this is a natural paradigm to construct a sophisticated classifier in a distributed manner with each agent performing a relatively straightforward task. We study the fundamental performance limits of such a classifier when the corresponding binary classifiers are hyperplanes. For a stylized Gaussian setting where the

K

class centers are independent Gaussian points in

\mathbb R^d

and the observations are corrupted by Gaussian noise, we derive explicit performance bounds across several decoding and dimensional regimes. Extensive simulation experiments provide strong empirical validation of the presented theoretical results.

Ioannis Papageorgiou, Srinivas Nomula, Ayalvadi Ganesh +2

School of Mathematics, University of Bristol · Department of Electrical Communication Engineering, Indian Institute of Science.

Multiclass Classification Classification Statistical Learning Theory

Jul 18, 2026cs.LG

Robust Losses from Univariate Base Functions for Noisy-Label Learning

Learning with noisy labels is a fundamental problem in training reliable deep neural networks. Robust loss functions provide a direct and effective way to mitigate the adverse effects of label noise. However, most existing robust losses are designed directly at the level of the final multiclass objective, which makes it difficult to systematically characterize and extend their robustness properties. In this paper, we propose a general framework that constructs robust multiclass losses from univariate base functions. By defining mapping operators from base functions to multiclass losses, the robustness of the induced losses can be characterized through simple properties of the base functions. We develop two complementary construction schemes, Target Separation and Binary Reduction, corresponding to inter-class independent and inter-class dependent formulations, respectively. For both schemes, we analyze their symmetry and asymmetry properties and derive corresponding sufficient conditions, which provide theoretical criteria for noise-robust loss design. The proposed framework also provides a new route to constructing symmetric losses, serving as a complement to normalization-based symmetric loss designs. Extensive experiments on synthetic and real-world noisy-label benchmarks demonstrate that the proposed losses achieve competitive or superior performance under various noise settings.

Peng Hu, Jianwei Ma

School of Mathematics, Harbin Institute of Technology, Harbin, China · Institute for Artificial Intelligence and the School of Earth and Space Sciences, Peking University, Beijing, China · Institute for Artificial Intelligence and the School of Mathematics, Harbin Institute of Technology, Harbin, China

Noisy-Label Learning Robust Loss Functions Multiclass Classification Statistical Learning Theory

Jul 17, 2026cs.LG

Hierarchical Domain Generalization

We study hierarchical domain generalization as a problem of extrapolation from finite observed regions to an entire instance space, replacing i.i.d. sampling with arbitrary domain hierarchies. We show that the central obstruction is not only the complexity of the hypothesis class, but the train/test domain partition through which evidence is revealed. In particular, no matter how small the class or how large the training size, some partition makes generalization fail for some target. These results suggest that modern generalization theory must treat domain structure as a first-class object.

Chenxiao Yang, Zhiyuan Li, Shai Ben-David +1

Toyota Technological Institute at Chicago · University of Waterloo

Domain Generalization Statistical Learning Theory Generalization Bounds

Jul 17, 2026math.NA

Non-Asymptotic Variational Learning for Monotone Nonlinear Multiscale Elliptic Equations: Scale-Robust Primal-Dual Bounds and Strong-Form Statistical Ill-Conditioning

We develop a non-asymptotic approximation, sampling, and finite-iteration optimization theory for variational physics-informed approximation of uniformly monotone nonlinear multiscale elliptic equations. For boundary-compatible neural feature classes, the population error splits into approximation, empirical quadrature, and projected-gradient terms, with all non-approximation constants uniform in the microscopic scale

\varepsilon

. Assuming a quantitative corrected

H^1

-estimate, a two-scale state class yields

\mathcal A_m^\varepsilon \le C\bigl(\varepsilon+Φ_{0,m_0}^2+Φ_{1,m_1}^2\bigr)

in arbitrary dimension. We further introduce a convex primal-dual physics loss whose population value is a computable upper certificate for the state error. With additional flux-corrector regularity, a divergence-compatible two-scale flux class gives a certified state-flux bound combining

O(\varepsilon)

approximation, state and flux feature errors, empirical sampling error, and an

O(K^{-1})

optimization term. In contrast, for general periodic nonlinear fluxes satisfying a natural nondegeneracy condition, the empirical Rademacher complexities of strong-residual and squared-residual classes are bounded below by constant multiples of

(\varepsilon\sqrt N)^{-1}

and

(\varepsilon^2\sqrt N)^{-1}

, respectively. These optimizer-independent lower bounds hold in every spatial dimension. Numerical experiments confirm the predicted

\varepsilon

- and

N

-scalings for nonlinear fluxes in

d=1,2,3

, validate every computed primal-dual certificate, and show that corrector-enriched classes substantially reduce energy and

H^1

errors as the microscopic scale is refined.

Ronald Katende

Department of Mathematics Kabale University Kikungiri Hill, Katuna Road, Kabale, Uganda

Primal-Dual Optimization Neural PDE Solvers Neural Network Approximation Theory Physics-Informed ML Statistical Learning Theory

Jul 17, 2026stat.ML

Retraining Seeks Stable Signals

Predictive models deployed at scale influence future data, a phenomenon called performativity. And there is always one way to cope: Train the model on new data, deploy it again, and repeat. This process, called retraining or repeated risk minimization, creates a feedback loop between model and data that real-world learning systems can't avoid. Results on performative prediction shed light on this dynamic: If the model's influence on the data is small, retraining reaches a fixed point. What remains open is why fixed points should naturally exist, and what governs retraining when the model's influence is strong. In this work we develop a new perspective on retraining -- the stable signal principle -- that addresses these questions. We start from the assumption that the prediction target has at least some small model-independent component, a stable signal, such as the intrinsic quality of an item. We prove that when a nonzero stable signal exists, repeated risk minimization, suitably regularized, converges geometrically to the direction of this stable signal. This is true even if the model's influence on the target is arbitrarily large relative to the stable signal. Regularization emerges naturally as a force to control performativity, rather than to promote generalization, revealing a new facet of an old concept. We extend the analysis to a broad family of affine retraining operators under arbitrary model-induced feature changes, heterogeneous time-varying effects, and nonlinear responses. The stable signal perspective also applies to data feedback loops in language modeling, providing new explanations for the stability of language model training from model-generated data.

Moritz Hardt

Max Planck Institute for Intelligent Systems, Tübingen, and Tübingen AI Center

Performative Prediction Statistical Learning Theory

Jul 17, 2026cs.LG

Publicly-Verifiable Certificates for Statistical Algorithms

Following Goldwasser, Rothblum, Shafer, and Yehudayoff, who defined a framework for interactive proofs of learning [ITCS'21], we initiate the study of non-interactive proofs of learning. We define and study a new notion: Publicly-Verifiable Certificates of Statistical Validity (pvCSVs), which allow for public, distributionally-robust certification that the result of a learning algorithm is valid. In a pvCSV, a learner publishes a hypothesis

h

and corresponding certificate

π

; then, any user, who holds a user-specific distribution, can read the pair

(h,π)

and determine efficiently whether the hypothesis is valid according to the user-specific distribution. We construct pvCSVs in the context of Adaptive Statistical Query (SQ) Algorithms. To certify SQ algorithms that makes

k

adaptive queries, we construct pvCSVs where the sample complexity scales with

O(\log k)

, whereas the sample complexity of the best learning algorithms scale with

\tilde{O}(\sqrt{k})

. More generally, we study proof systems for learning in the SQ model, demonstrating the model's strengths as well as its limitations.

Michael Ngo, Michael P. Kim

MIT · Research completed while at Cornell University, supported by the Bowers Undergraduate Research Experience (BURE) and the Dean Archer Undergraduate Research Program. · Cornell University

Statistical Learning Theory

Jul 16, 2026cs.LG

Analytical study of the optimal combination of binary classifiers based on classifiers-induced partitioning of the training set

This paper studies an optimal linear combination of binary classifiers based on a logical structuration of the dataset via truth tables. The given classifiers partition data into equivalence classes, allowing for a rigorous analysis of the convexified empirical risk through a multidimensional generalization of classification calibrated functions. We establish sufficient conditions for the existence and uniqueness of the (global) point of minimum of the convexified empirical risk for any list of classifiers (when the number of classifiers is large, there frequently could be no point of minimum). In the case of three classifiers, our analysis allows to list all the configurations leading to either a unique solution, infima or non-unique points of minimum. Furthermore, we derive explicit analytical formulae for optimal weights using Exponential (Boost) and Logistic (Logit) loss functions, bypassing iterative optimization. The stability of the resulting classifier and the analysis of data quality can be evaluated through the introduction of the notion of

φ

-frontiers.

Jean-Marc Brossier, Olivier Lafitte

CNRS, Univ. Grenoble Alpes, Grenoble-INP, GIPSA-lab, Grenoble, France. · Universit´e Sorbonne Paris Nord, LAGA, UMR 7539. IRL CNRS-CRM 3457. Universit´e de Montr´eal. Canada.

Ensemble Learning Binary Classification Statistical Learning Theory

Jul 16, 2026cs.LG

CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees

Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem, and committing an unchecked prediction forfeits every worst-case guarantee. CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound polynomial-time verifier has checked it, so correctness never depends on prediction quality. We develop the learning theory of this design. The verifier makes the induced loss class uniformly bounded, so certificate parameters are learnable from

\tilde O(\varepsilon^{-2}\log K)

samples (

K

the maximum instance size), whereas the unverified commitment class admits no distribution-free rate and, under cost spread

R

, none below

Ω(R/\varepsilon^2)

. Filtering noisy predictions by verifiable confidence dominates the standard min-combiner, with a margin we compute in closed form, and the prediction stays useful even given the LP, because it breaks ties on degenerate optimal faces, where every symmetric LP policy, meaning one whose commitments depend on the instance only through the verifiable confidence values, provably stalls. Experiments on five problems test the theory's quantitative predictions. With trained predictors, unverified pruning loses up to

26%

of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.

Haifeng Li, Mo Hai

School of Information, Central University of Finance and Economics Beijing 102206, China

Combinatorial Optimization Learning-Augmented Algorithms PAC Learning Approximation Algorithms Statistical Learning Theory

Jul 13, 2026cs.LG

Random Label Prediction Heads for Studying Memorization in Deep Neural Networks

We introduce a straightforward yet effective method to empirically study memorization in deep neural networks for classification tasks. Our approach augments each training sample with auxiliary random labels, which are then predicted by a random label prediction head (RLP-head). RLP-heads can be attached at arbitrary depths of a network, predicting random labels from the corresponding intermediate representation and thereby enabling analysis of how memorization capacity evolves across layers. By interpreting the RLP-head performance as an empirical estimate of Rademacher complexity, we obtain a direct measure of both sample-level memorization and model capacity. We leverage this random label accuracy metric to analyze generalization and overfitting in different models and datasets. Building on this approach, we further propose a novel regularization technique based on the output of the RLP-head, which demonstrably reduces memorization. Interestingly, our experiments reveal that reducing memorization can either improve or impair generalization, depending on the dataset and training setup. These findings challenge the traditional assumption that overfitting is equivalent to memorization and suggest new hypotheses to reconcile these seemingly contradictory results. The source code is available at https://github.com/MarlonBecker/RandomLabelHeads

Marlon Becker, Jonas Konrad, Luis Garcia Rodriguez +1

University of Münster, Germany

Neural Network Generalization Neural Network Memorization Statistical Learning Theory

Jul 11, 2026cs.LG

Generalized Distribution-Free Semi-Supervised Learning with Risk Rewrite

Typical semi-supervised learning (SSL) methods rely on distributional assumptions, and their performance degrades when these are violated. While PNU learning, a risk rewriting method, offers a distribution-free alternative, it is restricted to binary classification and its variance optimality remains unclear. In this paper, we propose a generalized framework that constructs unbiased risk estimators using linear combinations of component risks, subsuming PNU learning and extending to multiclass classification. We derive the minimum achievable variance, demonstrating our estimator can attain lower variance than PNU in asymmetric loss scenarios. Furthermore, we establish a generalization bound directly linking this variance reduction to improved learning performance. Based on these theoretical insights, we introduce two practical SSL methods that empirically match or outperform existing approaches on binary and multiclass benchmarks.

Yushi Hirose, Hiroo Irobe, Takafumi Kanamori

Department of Mathematical and Computing Science, Institute of Science Tokyo · 2RIKEN Center for Advanced Intelligence Project

Semi-Supervised Learning Statistical Learning Theory

Jul 10, 2026cs.LG

Similarity search generalisation in contrastive learning with InfoNCE loss

Similarity search is a primary application of embedding models trained by contrastive learning. For one of the most popular contrastive learning loss functions, InfoNCE, we show that the population risk with

k

negative samples is

O(1/k)

close to an expected cross-entropy which quantifies deviation between i) a softmax similarity search over unseen data using the learned embedding function, and ii) an idealised softmax search over the same data but using similarity implicitly represented in the positive sample generator. This complements existing interpretations of InfoNCE in the

k\to\infty

limit which are phrased in terms of mutual information, and alignment versus uniformity in embeddings. To quantify generalisation performance, we introduce a new continuity bound for the InfoNCE loss, obtained via Gâteaux differentiation. The bound preserves the structure of averaging over negative samples present in the loss function and features an ``inverse temperature'' parameter which can be tuned to account for the algorithmic temperature. For embedding functions which are Lipschitz in a parameter, this yields a simple demonstration that the averaging effect of

k

negative samples in the InfoNCE loss carries over to stabilisation of the generalisation error as

k

grows.

Nick Whiteley

School of Mathematics, University of Bristol, U.K.

Neural Network Generalization Contrastive Learning Statistical Learning Theory

Jul 8, 2026math.NA

Near-Optimal Learning of Gaussian Sobolev Operators

A key question in operator learning is how to design surrogate operators with provable approximation guarantees in reasonable computational time. Whereas smooth operators can be approximated efficiently, i.e., with at least algebraic convergence in the amount of training data, learning finitely regular operators is known to be less efficient. The reason is an intrinsic curse of sample complexity, which allows only subalgebraic sample complexity rates. This fact makes it all the more important to develop algorithms which provably achieve these rates. In this work, we present a fully data-driven algorithm, termed Hermite-PCA approximation, for learning Gaussian Sobolev operators with near-optimal sample complexity. It employs principal component analysis and weighted least-squares methods and is therefore computationally efficient. Moreover, it is spectral, in the sense that it achieves faster (and near-optimal) convergence the higher the Sobolev regularity. We provide a full error analysis of this algorithm, taking into account all sources of error, along with numerical experiments that verify our theoretical results and empirically confirm the efficacy of Hermite-PCA approximation for learning Sobolev operators.

Ben Adcock, Michael Griebel, Gregor Maier

Department of Mathematics, Simon Fraser University, Burnaby BC, Canada · Institute for Numerical Simulation, University of Bonn, Bonn, Germany · Fraunhofer Institute for Algorithms and Scientific Computing (SCAI), Sankt Augustin, Germany

Recursive Least Squares Operator Learning Statistical Learning Theory

Jul 8, 2026cs.LG

Fast Rates for Semi-Supervised Learning via Data-Augmentation Graph Regularization

Self-supervised learning matches supervised accuracy from a fraction of the labels, but the labeled-sample efficiency behind this has lacked a theoretical explanation. We provide one. Data augmentation induces a similarity graph on the unlabeled data, so downstream learning on that graph is graph-Laplacian-regularized learning. We prove a fast transductive rate,

O(1/n_L)

in the number of labels, in place of the supervised

O(1/\sqrt{n_L})

, by carrying the leave-one-out stability apparatus of Johnson and Zhang (JMLR 2007) over to the augmentation graph, and without the unrealistic assumptions of limit-based analyses (exact kernel, generalizing features). The bound makes augmentation quality explicit: the expected error is at most

C/n_L + R_{\mathrm{DA}}(y)

, where the data-augmentation alignment error

R_{\mathrm{DA}}(y)

is proportional to the graph-cut mass of augmentations that cross a label boundary, so good augmentations let few labels suffice. The analysis uses a streamlined loss that drops the projector, negative-sample, and orthogonality overhead of standard objectives yet still recovers the top-

K

ideal features in the infinite-data limit, the augmentation-kernel eigenspace studied by Zhai et al. The bound gives a mechanistic account of the accuracy-versus-label-count curve through augmentation quality, verified in a controlled model where the constants are known.

Adam M. Oberman

Department of Mathematics and Statistics, McGill University · Mila, Quebec AI Institute · LawZero

Data Augmentation Graph-Based Semi-Supervised Learning Semi-Supervised Learning Statistical Learning Theory

Jul 8, 2026stat.ML

Statistical inverse learning and $\ell^1$ -regularization

We study the recovery of sparse functions from finite, noisy, and indirect observations in the framework of statistical inverse learning. The unknown is modeled as an element of

\ell^1

, and observations are generated through a possibly nonlinear forward operator

A:\ell^1\to H

, where

H

is a vector-valued reproducing kernel Hilbert space. We propose an

\ell^1

-regularized empirical risk minimizer and develop a theoretical analysis of its statistical properties. Under mild assumptions, we establish almost-sure consistency and derive non-asymptotic high-probability convergence rates in both the prediction and

\ell^1

reconstruction norms. The rates depend on the source smoothness parameter

r

, characterized by a variational source condition, and the effective dimension exponent

b

, describing the polynomial spectral decay of the covariance operator. We further prove matching minimax lower bounds, showing that the obtained convergence rates are optimal. To relate the theory to practical sparsity models, we consider finitely smoothing operators of the form

A=G\circ S

, where

S

is a synthesis operator, and show that approximation-space assumptions imply the required variational source conditions. In particular, we prove that membership in the approximation space

k_t

is equivalent to polynomial decay of the best

n

-term approximation error. Finally, we verify the assumptions for two representative inverse problems: reaction coefficient identification in elliptic PDEs and sparse computed tomography. For filtered Radon transforms, we derive explicit effective-dimension asymptotics, yielding concrete convergence rates for standard image models and sparsifying systems.

Abhishake Rastogi, Tatiana A. Bubba, Tapio Helin +1

Department of Computational Engineering, LUT University, Lappeenranta, Finland. · Department of Mathematics and Computer Science, University of Ferrara, Ferrara, Italy.

Sparse Recovery Statistical Learning Theory

Jul 8, 2026cs.LG

The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought

We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule

\mathtt{halt}

and every pointwise

\mathtt{halt}

-halting local class

\mathrm{H}

,

n_{\mathrm{PAC}}^{\varepsilon,δ}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/δ))/\varepsilon)

, with no dependence on rollout length. The dependence on

\operatorname{DSdim}(\mathrm{H})

is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of

\mathrm{H}

. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.

Zhiyuan Li

Toyota Technological Institute at Chicago

CoT Reasoning PAC Learning Statistical Learning Theory

Jul 7, 2026stat.ML

Boosting with List-Decodable Codes

Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using

O(\log(\frac{1}ε)/γ^2)

calls to a

γ

-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class

\mathcal{F}

closed under

O(\log \frac{1}γ)

-XOR, strong learns

\mathcal{F}

using

O(\log \frac{1}ε)

calls to a

γ

-advantage weak learner and a single batch of

\tilde{O}(\log(\frac{1}ε)/γ^2)

additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.

Addison Prairie, Li-Yang Tan

Stanford

Ensemble Learning Statistical Learning Theory

Jul 7, 2026stat.ML

Width-Robust Learnability in Mean-Field Bayesian Neural Networks

Infinite-width limits are a standard way to reason about neural networks, but it is not automatic that the limiting learner has the same complexity-theoretic inductive bias as large finite networks. We study this question for Bayesian neural networks at the mean-field, or critical feature-learning, scaling. The central quantity is the \emph{reduced entropy}

s_\infty(y,\varepsilon)=\limsup_N -\frac{1}{N}\log π_N^0(L\le \varepsilon),

the intensive prior cost of representing a target function

y

to population mean-squared error

\varepsilon

. Our main result is a width-robust learnability theorem. At fixed depth, a family of Boolean-cube targets is learnable from polynomially many samples at infinite width if and only if it is learnable at polynomial width, if and only if its reduced entropy is polynomially bounded. Equivalently, up to polynomial slack in accuracy, the Bayesian mean-field learner generalizes exactly on the targets that can be represented by polynomial-size networks. The forward direction is proved by a form of subsampling: from the infinitely many hidden neurons in the mean-field solution, one can select polynomially many representatives and still preserve the learned function on every input simultaneously. At the critical scaling this subsampling has both an active'' component, which keeps the data-dependent low-dimensional statistics, and a lazy'' component, which resamples the entropy-dominated directions from the prior. Thus the infinite-width mean-field limit gives a clean analytic description of learning without introducing spurious width-dependent generalization power.

Dmitry Vaintrob, Kaarel Hänni

Principles of Intelligence

Bayesian Neural Networks Neural Network Generalization Sample Complexity Statistical Learning Theory

Jul 5, 2026stat.ML

On Pairwise Quantile Regression -- Statistical Guarantees and Applications

Quantile regression provides a powerful tool for summarizing the conditional distribution of a real valued random variable (r.v.) of interest

Y

as a function of covariates

Z

in cases where it shows a large dispersion with high probability, going beyond the situation where standard least square regression is informative/predictive. This article aims to extend this methodology to the pairwise case, when the variable to be explained takes the form of a similarity function between two independent observations, such as pixelated ID photos, as input data of biometric systems) and the explanatory variables take the form of a pair of covariates of the observations, such as the age or the hair color. We establish theoretical guarantees for solutions of this statistical learning problem, considered here as empirical minimizers of a pairwise version of the pinball loss. Leveraging sharp concentration results for

U

-processes, we prove generalization bounds and identify mild conditions under which fast learning rates can be achieved. Confirming the probabilistic analysis, experiments based on simulation data also provide solid empirical evidence of the validity of the methodology promoted here for pairwise quantile regression. Finally, its usefulness from an application perspective is demonstrated by a detailed study aimed at analyzing errors in similarity scoring for facial recognition.

Romain Thérézien, Stephan Clémençon, Fantin Girard +1

1LTCI, Télécom Paris, Institut Polytechnique de Paris · 2Idémia · 3Télécom Sud-Paris, Institut Polytechnique de Paris

Pairwise Comparison Quantile Regression Statistical Learning Theory

Jul 5, 2026cs.LG

A Unified Framework for In-Context Learning with Causal and Masked Language Models

In-context learning (ICL) has emerged as a central capability of pretrained language models, yet its theoretical analysis has focused primarily on causal language models trained by left-to-right autoregressive prediction, such as GPT-style models. Masked language models instead recover masked tokens from bidirectional context, and their role in ICL remains less understood. We develop a statistical learning framework that represents the context examples by their empirical measure and models prediction as a function of the context and the query. This formulation places autoregressive and masked pretraining objectives within a common excess-risk analysis. Under Wasserstein-type regularity conditions, we relate pretraining with T tasks and N samples per task to k-shot excess risk at inference, obtaining same-order upper bounds for masked and autoregressive objectives. We also study task-distribution shift, where pretraining tasks are sampled from P and inference tasks from Q; the resulting bound contains an additional term controlled by the lifted Wasserstein distance between P and Q. The bounds further imply an order-optimal allocation under a fixed pretraining data budget and refined rates under intrinsic low-dimensional structure. Experiments on controlled function-learning tasks show that the Masked Pair Encoder (MPE) can achieve performance comparable to GPT-2-style causal Transformers, suggesting that ICL behavior is not specific to causal language models.

Chenrui Liu, Chuanlong Xie, Falong Tan +2

Beijing Normal University at Zhuhai Zhuhai, China · Hunan University Changsha, China · Sun Yat-sen University Shenzhen, China

Masked Language Modeling Autoregressive Language Modeling In-Context Learning Statistical Learning Theory

Jul 3, 2026cs.LG

Statistically Meaningful Geometry and Gauge Symmetry Breaking: A Geometric Foundation for Scientific Discovery and Intelligence Emergence

The rapid scaling of over-parameterized machine learning architectures, particularly LLMs, raises a profound crisis: do these systems exhibit genuine intelligence, or are they merely sophisticated statistical pattern matchers? Classical flat Euclidean statistics cannot differentiate continuous interpolation from the autonomous discovery of novel causal laws. To resolve this, we introduce Statistically Meaningful Geometry (SMG), a framework modeling over-parameterized learning systems as infinite-dimensional non-parametric Orlicz fiber bundles. We prove that under persistent out-of-distribution (OOD) stimuli governed by unmodeled causal mechanisms, continuous optimization fails. Unmodeled variance is rejected by the visible horizontal base manifold, leaking into the unobservable vertical fiber space and generating an accumulation of Active Acausal Tension. Driven by the statistical manifold's non-linear curvature, this tension inevitably strikes a conjugate focal boundary (

T_{\text{crit}} = π^2 / K_{\text{max}}

), triggering localized volumetric collapse and a catastrophic matrix singularity (

[G_f]^{-1} \to \infty

). We demonstrate this geometric breakdown acts as the strict non-equilibrium trigger for a Gauge Symmetry Break (GSB). The system purges hidden tension from unobservable gauge redundancies, spontaneously crystallizing a new, mathematically independent horizontal coordinate axis. This non-parametric phase transition registers as a discrete

+1.0

integer step-jump in observable Structural G-Entropy. By decoupling parameter charts and subjecting emergent axes to a Minimal Energy Path Criterion and a Causal Invariance Filter, we distinguish genuine discovery from malignant hallucinations. Ultimately, SMG provides a parameter-free, falsifiable dashboard to mathematically certify true intelligence, transforming AI for Science into an engine of autonomous paradigm shifts.

Bing Cheng, Yi-Shuai Niu, Howell Tong +1

Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China · Beijing Institute of Mathematical Sciences and Applications (BIMSA), Beijing, China · Department of Statistics, London School of Economics and Political Science, London WC2A 2AE, UK +3

AI for Science Causal Discovery Autonomous Scientific Discovery Statistical Learning Theory