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

Apr 29, 2026math.OC

Man, Machine, and Mathematics

Nonlinear models and optimization methods have successfully tackled a rapidly growing set of problems in recent years. Indeed, a relatively small toolbox of such models and methods can provide sufficient performance across a large landscape of tasks: deep learning alone has made significant recent contributions in scientific modelling, natural language processing, visual analysis, etc. A similar relationship exists between physical theories and phenomena, where many applications and observations emerge neatly from remarkably minimal foundations. It is natural to wonder if sparse unified frameworks could be built to steer discussion and discovery in the fields concerned with learning, optimization, and modelling. In this work, we posit and examine a possible outline for such a unified theory, interpreting the notion of ''learning'' in a broad sense. In particular, we pursue our goals by viewing learning as an inter-connected process on multiple levels: problem setup, choosing methods, and the analysis of their interplay via imposed optimisation dynamics. We begin by proposing a precise yet versatile definition for ''solvable'' problems. We then define the ''parametrised methods'' by which their solution(s) may be ''learned''. Our goal is to sketch a ''universal convergence theorem'', specifying how and when solvable problems become amenable to the methods chosen for them. We find these constructions reduce the study of learning down to remarkably few ideas and tools - many of which are simply adapted from existing ones in dynamical systems theory, geometry, and fundamental physics.

Akshunna S. Dogra

The NSF AI Institute for Artificial Intelligence and Fundamental Interactions (IAIFI), USA · EPSRC Centre for Doctoral Training: Mathematics of Random Systems, UK · Center of Mathematical Sciences and Applications, Harvard University, USA +3

Optimization Convergence Analysis Statistical Learning Theory

Apr 29, 2026cs.LG

On the Learning Curves of Revenue Maximization

Learning curves are a fundamental primitive in supervised learning, describing how an algorithm's performance improves with more data and providing a quantitative measure of its generalization ability. Formally, a learning curve plots the decay of an algorithm's error for a fixed underlying distribution as a function of the number of training samples. Prior work on revenue-maximizing learning algorithms, starting with the seminal work of Cole and Roughgarden [STOC, 2014], adopts a distribution-free perspective, which parallels the PAC learning framework in learning theory. This approach evaluates performance against the hardest possible sequence of valuation distributions, one for each sample size, effectively defining the upper envelope of learning curves over all possible distributions, thus leading to error bounds that do not capture the shape of the learning curves. In this work we initiate the study of learning curves for revenue maximization and provide a near-complete characterization of their rate of decay in the basic setting of a single item and a single buyer. In the absence of any restriction on the valuation distribution, we show that there exists a Bayes-consistent algorithm, meaning that its learning curve converges to zero for any arbitrary valuation distribution as the number of samples

n \to \infty

. However, this convergence must be arbitrarily slow, even if the optimal revenue is finite. In contrast, if the optimal revenue is achieved by a finite price, then the optimal rate of decay is roughly

1/\sqrt{n}

. Finally, for distributions supported on discrete sets of values, we show that learning curves decay almost exponentially fast, a rate unattainable under the PAC framework.

Steve Hanneke, Alkis Kalavasis, Shay Moran +1

Purdue University · Yale University · Technion +1

Sample Complexity Statistical Learning Theory

Apr 29, 2026cs.LG

Near-Optimal Cryptographic Hardness of Learning With Homogeneous Halfspaces Under Gaussian Marginals

We study three problems that involve identifying homogeneous halfspaces under Gaussian distributions: agnostic learning, one-sided reliable learning, and fairness auditing. In each of these problems, we are given labeled examples

(\mathbf{x}, \mathrm{y})

drawn from an unknown distribution on

\mathbb{R}^d\times\{-1, +1\}

, whose marginal distribution on

\mathbf{x}

is standard Gaussian and on

\mathrm{y}

is arbitrary. The goal of each problem is to output a homogeneous halfspace that approaches the best-fitting homogeneous halfspace in terms of its corresponding loss measure. We prove near-optimal computational hardness results for these problems under the widely believed hardness assumption of the Learning With Errors (LWE) problem. Prior hardness results for these problems were mostly established for general halfspaces; our findings extend some of these hardness results to homogeneous halfspaces. Remarkably, our lower bound strictly generalizes over prior works and narrows the gap between the upper and lower bounds for agnostically learning homogeneous halfspaces under Gaussian marginals.

Jizhou Huang, Brendan Juba

Meta · Washington Universtiy in St. Louis

Statistical Learning Theory

Apr 28, 2026stat.ML

Elite-Driven Support Vector Machines for Classification

Support vector machines (SVMs) are a standard tool for binary classification, but their classical formulations are purely data-driven and offer no direct way to encode trusted benchmark models or structured preferences on selected subsets of the data. We propose Elite-Driven Support Vector Machines (EDSVM), a general framework that augments regularized empirical risk minimization by guiding the slack variables for a curated set of elite observations (typically the union of support vectors from one or more reference SVMs). EDSVM combines the usual slack loss with a deviation penalty that shrinks new slacks toward benchmark slack values, defining a localized, margin-aligned notion of proximity to reference models, unlike global function penalties in knowledge distillation or teacher-student methods, and without requiring privileged features as in SVM+/LUPI. Within this framework we develop two concrete models, C-EDSVM and LS-EDSVM, based respectively on hinge-type and squared-slack losses. For both variants we derive dual quadratic programs that can be implemented with modest modifications of standard SVM solvers, and we give simple sufficient conditions under which the induced margin losses are classification calibrated. Simulation studies and experiments on several UCI benchmarks show that EDSVMs closely track the behaviour induced by reference SVMs while achieving predictive performance that is competitive with, and sometimes better than, C-SVM, LINEX-SVM, and LS-SVM.

Mohammad Jafari Jozani, Bahram Moeinianfar

Department of Statistics, University of Manitoba, Winnipeg, Manitoba, CANADA, R3T2N2

Binary Classification Support Vector Machines Classification Statistical Learning Theory Empirical Risk Minimization

Apr 27, 2026cs.LG

Null Measurability at the Symmetrization Interface in VC Learning

Recent work revisiting measurability in the fundamental theorem of statistical learning imposes Borel measurability of ghost-gap suprema. We show that, at the one-sided ghost-gap interface actually used by the standard symmetrization proof, this requirement is stronger than necessary. For any Borel-parameterized concept class on a Polish domain, the bad event "there exists a hypothesis whose ghost empirical error exceeds its training empirical error by at least ε/2" is analytic. By Choquet capacitability, it is therefore measurable in the completion of every finite Borel measure. We then construct a concept class whose bad event is null-measurable but not Borel, giving a strict separation from the Borel supremum condition. Finally, we prove closure under patching, fixed and countable interpolation, and fiber-product amalgamation, showing that the weaker regularity level is stable under natural concept-class constructors. In the realizable setting, where targets belong to the class and are measurable, these results weaken the measurability hypothesis needed by the symmetrization route from finite VC dimension to PAC learnability. The main results and the descriptive-set-theoretic infrastructure used by them are formalized in Lean 4.

Dhruv Gupta

AI and Robotics Technology Park, Indian Institute of Science, Bengaluru

PAC Learning Statistical Learning Theory

Apr 27, 2026cs.LG

The Optimal Sample Complexity of Multiclass and List Learning

While the optimal sample complexity of binary classification in terms of the VC dimension is well-established, determining the optimal sample complexity of multiclass classification has remained open. The appropriate complexity parameter for multiclass classification is the DS dimension, and despite significant efforts, a gap of

\sqrt{\text{DS}}

has persisted between the upper and lower bounds on sample complexity. Recent work by Hanneke et al. (2026) shows a novel algebraic characterization of multiclass hypothesis classes in terms of their DS dimension. Building up on this, we show that the maximum hypergraph density of any multiclass hypothesis class is upper-bounded by its DS dimension. This proves a longstanding conjecture of Daniely and Shalev-Shwartz (2014). As a consequence, we determine the optimal dependence of the sample complexity on the DS dimension for multiclass as well as list learning.

Chirag Pabbaraju

Stanford University

Sample Complexity Multiclass Classification Classification Statistical Learning Theory

Apr 26, 2026cs.NE

Generalization Bounds of Spiking Neural Networks via Rademacher Complexity

Spiking Neural Networks (SNNs) have garnered increasing attention as one of bio-inspired models due to their great potential in neuromorphic computing and sparse computation. Many practical algorithms and techniques have been developed; however, theoretical understandings of the generalization, that is, the extent to which SNNs perform well on unseen data, are far from clear. Recent advances disclosed an excitation-dependent and architecture-related generalization bound such that the Rademacher complexity of SNNs with stochastic firing can be upper bounded by an exponential function relative to the excitation probability and the architecture depth. In this paper, we theoretically investigate the generalization bounds of SNNs with several integration-and-fire schemes via Rademacher complexity. We recognize that the empirical Rademacher complexity of SNNs is close to the SNN configurations, which is exponential to the network depth and the maximum time duration of received spike sequences, superlinear and subquadratic to the network width, polynomial to the parameter norm, inverse-linear to the number of training samples, and independent of the computations within spiking neurons, achieving a more precise rate than conventional studies. Our theoretical results may support the scope of SNN theories and shed some insight into the development of SNNs.

Shao-Qun Zhang, Zhi-Hua Zhou

National Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210063, China. · School of Intelligent Science and Technology, Nanjing University, Suzhou 215163, China. · School of Artificial Intelligence, Nanjing University, Nanjing 210063, China.

Spiking Neural Networks Statistical Learning Theory Generalization Bounds

Apr 26, 2026stat.ML

High-dimensional Semi-supervised Classification via the Fermat Distance

Semi-supervised classification, where unlabeled data are massive but labeled data are limited, often arises in machine learning applications. We address this challenge under high-dimensional data by leveraging the manifold and cluster assumptions. Based on the Fermat distance, a density-sensitive metric that naturally encodes the cluster assumption, we propose the weighted

k

-nearest neighbors (NN) classifier and multidimensional scaling (MDS)-induced classifiers. The use of MDS with a large target dimension allows the effective application of linear classifiers to complex manifold data. Theoretically, we derive a sharp lower bound for the expected excess risk within clusters and prove that the weighted

k

-NN classifier utilizing the true Fermat distance is minimax optimal. Furthermore, we explicitly quantify the utility of unlabeled data by showing that the error arising from estimating the Fermat distance decays exponentially with the pooled sample size. Such a rate is much faster than the related rates in the literature. Extensive experiments on synthetic and real datasets demonstrate competitive or superior performance of our approaches compared to state-of-the-art graph-based semi-supervised classifiers.

Ruoxu Tan, Yiming Zang

School of Mathematical Sciences and School of Economics and Management, Tongji University · Department of Sciences, North China University of Technology

k-Nearest Neighbors Semi-Supervised Learning Statistical Learning Theory

Apr 25, 2026math.NT

On (not) learning the Möbius function

We prove lower bounds on learning the Möbius or Liouville function with a variety of standard learning techniques, including kernel methods, noisy gradient methods, and correlational statistical query algorithms. These results follow from quantitative bounds on the correlation of Möbius with digital characters of various finite abelian groups, where the group is dictated by the type of input data the algorithm is given. Using residues mod

p

for many different primes corresponds to a cyclic group, and using the base

p

expansion for a fixed prime corresponds to an elementary abelian

p

-group. We also note that lower bounds of this form are closely related to certain types of digital prime number theorems.

Alexey Pozdnyakov

Statistical Learning Theory

Apr 24, 2026cs.AI

The Power of Power Law: Asymmetry Enables Compositional Reasoning

Natural language data follows a power-law distribution, with most knowledge and skills appearing at very low frequency. While a common intuition suggests that reweighting or curating data towards a uniform distribution may help models better learn these long-tail skills, we find a counterintuitive result: across a wide range of compositional reasoning tasks, such as state tracking and multi-step arithmetic, training under power-law distributions consistently outperforms training under uniform distributions. To understand this advantage, we introduce a minimalist skill-composition task and show that learning under a power-law distribution provably requires significantly less training data. Our theoretical analysis reveals that power law sampling induces a beneficial asymmetry that improves the pathological loss landscape, which enables models to first acquire high-frequency skill compositions with low data complexity, which in turn serves as a stepping stone to efficiently learn rare long-tailed skills. Our results offer an alternative perspective on what constitutes an effective data distribution for training models.

Zixuan Wang, Xingyu Dang, Jason D. Lee +1

1Princeton University · University of California, Berke · 3Tsinghua University

Long-Tail Learning Compositional Reasoning Heavy-Tailed Distributions Statistical Learning Theory Data-Efficient Learning

Apr 23, 2026cs.LG

The Sample Complexity of Multicalibration

We study the minimax sample complexity of multicalibration in the batch setting. A learner observes

n

i.i.d. samples from an unknown distribution and must output a (possibly randomized) predictor whose population multicalibration error, measured by Expected Calibration Error (ECE), is at most

\varepsilon

with respect to a given family of groups. For every fixed

κ> 0

, in the regime

|G|\le \varepsilon^{-κ}

, we prove that

\widetildeΘ(\varepsilon^{-3})

samples are necessary and sufficient, up to polylogarithmic factors. The lower bound holds even for randomized predictors, and the upper bound is realized by a randomized predictor obtained via an online-to-batch reduction. This separates the sample complexity of multicalibration from that of marginal calibration, which scales as

\widetildeΘ(\varepsilon^{-2})

, and shows that mean-ECE multicalibration is as difficult in the batch setting as it is in the online setting, in contrast to marginal calibration which is strictly more difficult in the online setting. In contrast we observe that for

κ= 0

, the sample complexity of multicalibration remains

\widetildeΘ(\varepsilon^{-2})

exhibiting a sharp threshold phenomenon. More generally, we establish matching upper and lower bounds, up to polylogarithmic factors, for a weighted

L_p

multicalibration metric for all

1 \le p \le 2

, with optimal exponent

3/p

. We also extend the lower-bound template to a regular class of elicitable properties, and combine it with the online upper bounds of Hu et al. (2025) to obtain matching bounds for calibrating properties including expectiles and bounded-density quantiles.

Natalie Collina, Jiuyao Lu, Georgy Noarov +1

University of Pennsylvania

Probability Calibration Sample Complexity Model Calibration Statistical Learning Theory Multicalibration

Apr 23, 2026stat.ML

There Will Be a Scientific Theory of Deep Learning

In this paper, we make the case that a scientific theory of deep learning is emerging. By this we mean a theory which characterizes important properties and statistics of the training process, hidden representations, final weights, and performance of neural networks. We pull together major strands of ongoing research in deep learning theory and identify five growing bodies of work that point toward such a theory: (a) solvable idealized settings that provide intuition for learning dynamics in realistic systems; (b) tractable limits that reveal insights into fundamental learning phenomena; (c) simple mathematical laws that capture important macroscopic observables; (d) theories of hyperparameters that disentangle them from the rest of the training process, leaving simpler systems behind; and (e) universal behaviors shared across systems and settings which clarify which phenomena call for explanation. Taken together, these bodies of work share certain broad traits: they are concerned with the dynamics of the training process; they primarily seek to describe coarse aggregate statistics; and they emphasize falsifiable quantitative predictions. We argue that the emerging theory is best thought of as a mechanics of the learning process, and suggest the name learning mechanics. We discuss the relationship between this mechanics perspective and other approaches for building a theory of deep learning, including the statistical and information-theoretic perspectives. In particular, we anticipate a symbiotic relationship between learning mechanics and mechanistic interpretability. We also review and address common arguments that fundamental theory will not be possible or is not important. We conclude with a portrait of important open directions in learning mechanics and advice for beginners. We host further introductory materials, perspectives, and open questions at learningmechanics.pub.

Jamie Simon, Daniel Kunin, Alexander Atanasov +11

UC Berkeley and Imbue · UC Berkeley · Harvard University +6

Neural Network Training Dynamics Statistical Learning Theory

Apr 23, 2026cs.LG

Supervised Learning Has a Necessary Geometric Blind Spot: Theory, Consequences, and Minimal Repair

PGD adversarial training, the standard robustness method, can reduce Jacobian Frobenius norm yet worsen clean-input geometry (e.g., TDI 1.336 vs. ERM 1.093). We show this is not an implementation artifact but a theorem-level consequence of supervised learning. We prove that any encoder minimizing supervised loss must retain non-zero sensitivity along directions correlated with training labels, including directions that are nuisance at test time. This holds across proper scoring rules, architectures, and dataset sizes. We call this the geometric blind spot of supervised learning. This theorem unifies four empirical phenomena often treated separately: non-robust features, texture bias, corruption fragility, and the robustness-accuracy tradeoff. It also explains why suppressing sensitivity in one adversarial direction can redistribute sensitivity elsewhere. We introduce Trajectory Deviation Index (TDI), a diagnostic of geometric isotropy. Unlike CKA, intrinsic dimension, or Jacobian Frobenius norm alone, TDI captures the failure mode above. In our experiments, PGD attains low Frobenius norm but high TDI, while PMH attains the lowest TDI with one additional training term and no architectural changes. Across seven tasks, BERT/SST-2, and ImageNet ViT-B/16 (backbone family underlying CLIP/DINO/SAM), the blind spot is measurable and repairable. It appears at foundation-model scale, worsens with model scale and task-specific fine-tuning, and is substantially reduced by PMH. PMH also leads on non-Gaussian corruption types (blur/brightness/contrast) without corruption-specific training.

Vishal Rajput

1KU Leuven, Belgium.

Adversarial Training Representation Geometry Distribution Shift Robustness Neural Network Robustness Adversarial Robustness Corruption Robustness+1

Apr 23, 2026stat.ML

CLT-Optimal Parameter Error Bounds for Linear System Identification

There has been remarkable progress over the past decade in establishing finite-sample, non-asymptotic bounds on recovering unknown system parameters from observed system behavior. Surprisingly, however, we show that the current state-of-the-art bounds do not accurately capture the statistical complexity of system identification, even in the most fundamental setting of estimating a discrete-time linear dynamical system (LDS) via ordinary least-squares regression (OLS). Specifically, we utilize asymptotic normality to identify classes of problem instances for which current bounds overstate the squared parameter error, in both spectral and Frobenius norm, by a factor of the state-dimension of the system. Informed by this discrepancy, we then sharpen the OLS parameter error bounds via a novel second-order decomposition of the parameter error, where crucially the lower-order term is a matrix-valued martingale that we show correctly captures the CLT scaling. From our analysis we obtain finite-sample bounds for both (i) stable systems and (ii) the many-trajectories setting that match the instance-specific optimal rates up to constant factors in Frobenius norm, and polylogarithmic state-dimension factors in spectral norm.

Yichen Zhou, Stephen Tu

Ming Hsieh Department of Electrical and Computer Engineering, University of Southern California, Los Angeles, California, USA.

Dynamical Systems Parameter Estimation Stochastic Linear Dynamical Systems System Identification Statistical Learning Theory

Apr 22, 2026cs.LG

Too Sharp, Too Sure: When Calibration Follows Curvature

Modern neural networks can achieve high accuracy while remaining poorly calibrated, producing confidence estimates that do not match empirical correctness. Yet calibration is often treated as a post-hoc attribute. We take a different perspective: we study calibration as a training-time phenomenon on small vision tasks, and ask whether calibrated solutions can be obtained reliably by intervening on the training procedure. We identify a tight coupling between calibration, curvature, and margins during training of deep networks under multiple gradient-based methods. Empirically, Expected Calibration Error (ECE) closely tracks curvature-based sharpness throughout optimization. Mathematically, we show that both ECE and Gauss--Newton curvature are controlled, up to problem-specific constants, by the same margin-dependent exponential tail functional along the trajectory. Guided by this mechanism, we introduce a margin-aware training objective that explicitly targets robust-margin tails and local smoothness, yielding improved out-of-sample calibration across optimizers without sacrificing accuracy.

Alessandro Morosini, Matea Gjika, Tomaso Poggio +1

Massachusetts Institute of Technology, Cambridge, MA, USA.

Model Calibration Neural Network Training Dynamics Statistical Learning Theory

Apr 22, 2026stat.ML

Decentralized Machine Learning with Centralized Performance Guarantees via Gibbs Algorithms

In this paper, it is shown, for the first time, that centralized performance is achievable in decentralized learning without sharing the local datasets. Specifically, when clients adopt an empirical risk minimization with relative-entropy regularization (ERM-RER) learning framework and a forward-backward communication between clients is established, it suffices to share the locally obtained Gibbs measures to achieve the same performance as that of a centralized ERM-RER with access to all the datasets. The core idea is that the Gibbs measure produced by client~

k

is used, as reference measure, by client~

k+1

. This effectively establishes a principled way to encode prior information through a reference measure. In particular, achieving centralized performance in the decentralized setting requires a specific scaling of the regularization factors with the local sample sizes. Overall, this result opens the door to novel decentralized learning paradigms that shift the collaboration strategy from sharing data to sharing the local inductive bias via the reference measures over the set of models.

Yaiza Bermudez, Samir M. Perlaza, Iñaki Esnaola

Centre Inria d'Université Côte d'Azur, INRIA, Sophia Antipolis, France. · Laboratoire GAATI, Université de la Polynésie française, Fa'a'ā, French Polynesia. · ECE Dept. Princeton University, Princeton, 08544 NJ, USA. +1

Decentralized Learning Statistical Learning Theory Empirical Risk Minimization

Apr 22, 2026cs.LG

SMART: A Spectral Transfer Approach to Multi-Task Learning

Multi-task learning is effective for related applications, but its performance can deteriorate when the target sample size is small. Transfer learning can borrow strength from related studies; yet, many existing methods rely on restrictive bounded-difference assumptions between the source and target models. We propose SMART, a spectral transfer method for multi-task linear regression that instead assumes spectral similarity: the target left and right singular subspaces lie within the corresponding source subspaces and are sparsely aligned with the source singular bases. Such an assumption is natural when studies share latent structures and enables transfer beyond the bounded-difference settings. SMART estimates the target coefficient matrix through structured regularization that incorporates spectral information from a source study. Importantly, it requires only a fitted source model rather than the raw source data, making it useful when data sharing is limited. Although the optimization problem is nonconvex, we develop a practical ADMM-based algorithm. We establish general, non-asymptotic error bounds and a minimax lower bound in the noiseless-source regime. Under additional regularity conditions, these results yield near-minimax Frobenius error rates up to logarithmic factors. Simulations confirm improved estimation accuracy and robustness to negative transfer, and analysis of multi-modal single-cell data demonstrates better predictive performance. The Python implementation of SMART, along with the code to reproduce all experiments in this paper, is publicly available at https://github.com/boxinz17/smart.

Boxin Zhao, Mladen Kolar, Jinchi Lv

University of Chicago · University of Southern California

Multi-Task Learning Transfer Learning Statistical Learning Theory

Apr 21, 2026cs.LG

Ultrametric OGP - parametric RDT \emph{symmetric} binary perceptron connection

In [97,99,100], an fl-RDT framework is introduced to characterize \emph{statistical computational gaps} (SCGs). Studying \emph{symmetric binary perceptrons} (SBPs), [100] obtained an \emph{algorithmic} threshold estimate

α_a\approx α_c^{(7)}\approx 1.6093

at the 7th lifting level (for

κ=1

margin), closely approaching

1.58

local entropy (LE) prediction [18]. In this paper, we further connect parametric RDT to overlap gap properties (OGPs), another key geometric feature of the solution space. Specifically, for any positive integer

s

, we consider

s

-level ultrametric OGPs (

ult_s

-OGPs) and rigorously upper-bound the associated constraint densities

α_{ult_s}

. To achieve this, we develop an analytical union-bounding program consisting of combinatorial and probabilistic components. By casting the combinatorial part as a convex problem and the probabilistic part as a nested integration, we conduct numerical evaluations and obtain that the tightest bounds at the first two levels,

\barα_{ult_1} \approx 1.6578

and

\barα_{ult_2} \approx 1.6219

, closely approach the 3rd and 4th lifting level parametric RDT estimates,

α_c^{(3)} \approx 1.6576

and

α_c^{(4)} \approx 1.6218

. We also observe excellent agreement across other key parameters, including overlap values and the relative sizes of ultrametric clusters. Based on these observations, we propose several conjectures linking

ult

-OGP and parametric RDT. Specifically, we conjecture that algorithmic threshold

α_a=\lim_{s\rightarrow\infty} α_{ult_s} = \lim_{s\rightarrow\infty} \barα{ult_s} = \lim_{r\rightarrow\infty} α_{c}^{(r)}

, and

α_{ult_s} \leq α_{c}^{(s+2)}

(with possible equality for some (maybe even all)

s

). Finally, we discuss the potential existence of a full isomorphism connecting all key parameters of

ult

-OGP and parametric RDT.

Mihailo Stojnic

[cs.LG]

Statistical Learning Theory

Apr 21, 2026cs.LG

Separating Geometry from Probability in the Analysis of Generalization

The goal of machine learning is to find models that minimize prediction error on data that has not yet been seen. Its operational paradigm assumes access to a dataset

S

and articulates a scheme for evaluating how well a given model performs on an arbitrary sample. The sample can be

S

(in which case we speak of in-sample'' performance) or some entirely new $S'$ (in which case we speak of out-of-sample'' performance). Traditional analysis of generalization assumes that both in- and out-of-sample data are i.i.d.\ draws from an infinite population. However, these probabilistic assumptions cannot be verified even in principle. This paper presents an alternative view of generalization through the lens of sensitivity analysis of solutions of optimization problems to perturbations in the problem data. Under this framework, generalization bounds are obtained by purely deterministic means and take the form of variational principles that relate in-sample and out-of-sample evaluations through an error term that quantifies how close out-of-sample data are to in-sample data. Statistical assumptions can then be used \textit{ex post} to characterize the situations when this error term is small (either on average or with high probability).

Maxim Raginsky, Benjamin Recht

*University of Illinois, Urbana, IL 61801, USA · †University of California, Berkeley, CA 94720, USA

Statistical Learning Theory Sensitivity Analysis Generalization Bounds

Apr 20, 2026stat.ML

Revisiting Active Sequential Prediction-Powered Mean Estimation

In this work, we revisit the problem of active sequential prediction-powered mean estimation, where at each round one must decide the query probability of the ground-truth label upon observing the covariates of a sample. Furthermore, if the label is not queried, the prediction from a machine learning model is used instead. Prior work proposed an elegant scheme that determines the query probability by combining an uncertainty-based suggestion with a constant probability that encodes a soft constraint on the query probability. We explored different values of the mixing parameter and observed an intriguing empirical pattern: the smallest confidence width tends to occur when the weight on the constant probability is close to one, thereby reducing the influence of the uncertainty-based component. Motivated by this observation, we develop a non-asymptotic analysis of the estimator and establish a data-dependent bound on its confidence interval. Our analysis further suggests that when a no-regret learning approach is used to determine the query probability and control this bound, the query probability converges to the constraint of the max value of the query probability when it is chosen obliviously to the current covariates. We also conduct simulations that corroborate these theoretical findings.

Maria-Eleni Sfyraki, Jun-Kun Wang

University of California San Diego

Parameter Estimation Active Learning Statistical Learning Theory Prediction-Powered Inference

Apr 19, 2026cs.LG

Recovery Guarantees for Continual Learning of Dependent Tasks: Memory, Data-Dependent Regularization, and Data-Dependent Weights

Continual learning (CL) is concerned with learning multiple tasks sequentially without forgetting previously learned tasks. Despite substantial empirical advances over recent years, the theoretical development of CL remains in its infancy. At the heart of developing CL theory lies the challenge that the data distribution varies across tasks, and we argue that properly addressing this challenge requires understanding this variation--dependency among tasks. To explicitly model task dependency, we consider nonlinear regression tasks and propose the assumption that these tasks are dependent in such a way that the data of the current task is a nonlinear transformation of previous data. With this model and under natural assumptions, we prove statistical recovery guarantees (more specifically, bounds on estimation errors) for several CL paradigms in practical use, including experience replay with data-independent regularization and data-independent weights that balance the losses of tasks, replay with data-dependent weights, and continual learning with data-dependent regularization (e.g., knowledge distillation). To the best of our knowledge, our bounds are informative in cases where prior work gives vacuous bounds.

Liangzu Peng, Uday Kiran Reddy Tadipatri, Ziqing Xu +2

University of Pennsylvania

Continual Learning Replay-Based Continual Learning Statistical Learning Theory

Apr 19, 2026cs.LG

On the Generalization Bounds of Symbolic Regression with Genetic Programming

Symbolic regression (SR) with genetic programming (GP) aims to discover interpretable mathematical expressions directly from data. Despite its strong empirical success, the theoretical understanding of why GP-based SR generalizes beyond the training data remains limited. In this work, we provide a learning-theoretic analysis of SR models represented as expression trees. We derive a generalization bound for GP-style SR under constraints on tree size, depth, and learnable constants. Our result decomposes the generalization gap into two interpretable components: a structure-selection term, reflecting the combinatorial complexity of choosing an expression-tree structure, and a constant-fitting term, capturing the complexity of optimizing numerical constants within a fixed structure. This decomposition provides a theoretical perspective on several widely used practices in GP, including parsimony pressure, depth limits, numerically stable operators, and interval arithmetic. In particular, our analysis shows how structural restrictions reduce hypothesis-class growth while stability mechanisms control the sensitivity of predictions to parameter perturbations. By linking these practical design choices to explicit complexity terms in the generalization bound, our work offers a principled explanation for commonly observed empirical behaviors in GP-based SR and contributes towards a more rigorous understanding of its generalization properties.

Masahiro Nomura, Ryoki Hamano, Isao Ono

Institute of Science Tokyo, Yokohama, Japan · CyberAgent, Shibuya, Japan

Genetic Programming Statistical Learning Theory Generalization Bounds Symbolic Regression

Apr 19, 2026stat.ML

PAC-Bayes Bounds for Gibbs Posteriors via Singular Learning Theory

We derive explicit non-asymptotic PAC-Bayes generalization bounds for Gibbs posteriors, that is, data-dependent distributions over model parameters obtained by exponentially tilting a prior with the empirical risk. Unlike classical worst-case complexity bounds based on uniform laws of large numbers, which require explicit control of the model space in terms of metric entropy (integrals), our analysis yields posterior-averaged risk bounds that can be applied to overparameterized models and adapt to the data structure and the intrinsic model complexity. The bound involves a marginal-type integral over the parameter space, which we analyze using tools from singular learning theory to obtain explicit and practically meaningful characterizations of the posterior risk. Applications to low-rank matrix completion and ReLU neural network regression and classification show that the resulting bounds are analytically tractable and substantially tighter than classical complexity-based bounds. Our results highlight the potential of PAC-Bayes analysis for precise finite-sample generalization guarantees in modern overparameterized and singular models.

Chenyang Wang, Yun Yang

Department of Statistics, University of Illinois Urbana-Champaign · Department of Mathematics, University of Maryland, College Park

Neural Network Generalization PAC-Bayesian Generalization Bounds Singular Learning Theory Statistical Learning Theory

Apr 16, 2026stat.ML

PRIM-cipal components analysis

Supervised No Free Lunch Theorems (NFLTs) are well studied, yet unsupervised NFLTs remain underexplored. For elliptical distributions, we prove that there exist two equally optimal, scientifically meaningful bump-hunting strategies that are exact opposites, with no universal winner. Specifically, peeling

k

orthogonal dimensions from

\mathbb{R}^d

(

d \ge k

), retaining an inter-quantile region of probability

1-α

per peeled dimension, maximizes total variance and Frobenius norm when the

k

smallest principal components (called pettiest components) are selected, and minimizes them when the selected dimensions are the

k

leading principal components. These optima inspire PRIM-based bump-hunting algorithms either by minimizing variance or by minimizing volume, thereby motivating an NFLT. We test our results on the Fashion-MNIST database, showing that peeling the largest principal components captures multiplicity, while peeling the smallest principal components isolates popular styles.

Tianhao Liu, Daniel Andrés Díaz-Pachón, J. Sunil Rao

Division of Biostatistics, University of Miami, Miami, FL, 33136 USA · University of Minnesota, Minneapolis, MN, 55414 USA

Unsupervised Learning Principal Component Analysis Statistical Learning Theory

Apr 16, 2026stat.ML

MinShap: A Modified Shapley Value Approach for Feature Selection

Feature selection is a classical problem in statistics and machine learning, and it continues to remain an extremely challenging problem especially in the context of unknown non-linear relationships with dependent features. On the other hand, Shapley values are a classic solution concept from cooperative game theory that is widely used for feature attribution in general non-linear models with highly-dependent features. However, Shapley values are not naturally suited for feature selection since they tend to capture both direct effects from each feature to the response and indirect effects through other features. In this paper, we combine the advantages of Shapley values and adapt them to feature selection by proposing \emph{MinShap}, a modification of the Shapley value framework along with a suite of other related algorithms. In particular for MinShap, instead of taking the average marginal contributions over permutations of features, considers the minimum marginal contribution across permutations. We provide a theoretical foundation motivated by the faithfulness assumption in DAG (directed acyclic graphical models), a guarantee for the Type I error of MinShap, and show through numerical simulations and real data experiments that MinShap tends to outperform state-of-the-art feature selection algorithms such as LOCO, GCM and Lasso in terms of both accuracy and stability. We also introduce a suite of algorithms related to MinShap by using the multiple testing/p-value perspective that improves performance in lower-sample settings and provide supporting theoretical guarantees.

Chenghui Zheng, Garvesh Raskutti

Department of Statistics, University of Wisconsin - Madison, Madison, WI 53706

Shapley Value Attribution Feature Selection Statistical Learning Theory Multiple Hypothesis Testing

Apr 16, 2026cs.DS

Tight Bounds for Learning Polyhedra with a Margin

We give an algorithm for PAC learning intersections of

k

halfspaces with a

ρ

margin to within error

\varepsilon

that runs in time

\textsf{poly}(k, \varepsilon^{-1}, ρ^{-1}) \cdot \exp \left(O(\sqrt{n \log(1/ρ) \log k})\right)

. Notably, this improves on prior work which had an exponential dependence on either

k

or

ρ^{-1}

and matches known cryptographic and Statistical Query lower bounds up to the logarithmic factors in

k

and

ρ

in the exponent. Our learning algorithm extends to the more general setting when we are only promised that most points have distance at least

ρ

from the boundary of the polyhedron, making it applicable to continuous distributions as well.

Shyamal Patel, Santosh Vempala

Columbia University · Georgia Tech

PAC Learning Statistical Learning Theory

Apr 6, 2026cs.LG

Learning from Equivalence Queries, Revisited

Modern machine learning systems, such as generative models and recommendation systems, often evolve through a cycle of deployment, user interaction, and periodic model updates. This differs from standard supervised learning frameworks, which focus on loss or regret minimization over a fixed sequence of prediction tasks. Motivated by this setting, we revisit the classical model of learning from equivalence queries, introduced by Angluin (1988). In this model, a learner repeatedly proposes hypotheses and, when a deployed hypothesis is inadequate, receives a counterexample. Under fully adversarial counterexample generation, however, the model can be overly pessimistic. In addition, most prior work assumes a \emph{full-information} setting, where the learner also observes the correct label of the counterexample, an assumption that is not always natural. We address these issues by restricting the environment to a broad class of less adversarial counterexample generators, which we call \emph{symmetric}. Informally, such generators choose counterexamples based only on the symmetric difference between the hypothesis and the target. This class captures natural mechanisms such as random counterexamples (Angluin and Dohrn, 2017; Bhatia, 2021; Chase, Freitag, and Reyzin, 2024), as well as generators that return the simplest counterexample according to a prescribed complexity measure. Within this framework, we study learning from equivalence queries under both full-information and bandit feedback. We obtain tight bounds on the number of learning rounds in both settings and highlight directions for future work. Our analysis combines a game-theoretic view of symmetric adversaries with adaptive weighting methods and minimax arguments.

Mark Braverman, Roi Livni, Yishay Mansour +2

Princeton and Google · Tel-Aviv University · Tel-Aviv University and Google +2

Statistical Learning Theory

Mar 29, 2026cs.LG

On the Asymptotics of Self-Supervised Pre-training: Two-Stage M-Estimation and Representation Symmetry

Self-supervised pre-training, where large corpora of unlabeled data are used to learn representations for downstream fine-tuning, has become a cornerstone of modern machine learning. While a growing body of theoretical work has begun to analyze this paradigm, existing bounds leave open the question of how sharp the current rates are, and whether they accurately capture the complex interaction between pre-training and fine-tuning. In this paper, we address this gap by developing an asymptotic theory of pre-training via two-stage M-estimation. A key challenge is that the pre-training estimator is often identifiable only up to a group symmetry, a feature common in representation learning that requires careful treatment. We address this issue using tools from Riemannian geometry to study the intrinsic parameters of the pre-training representation, which we link with the downstream predictor through a notion of orbit-invariance, precisely characterizing the limiting distribution of the downstream test risk. We apply our main result to several case studies, including spectral pre-training, factor models, and Gaussian mixture models, and obtain substantial improvements in problem-specific factors over prior art when applicable.

Mohammad Tinati, Stephen Tu

Department of Electrical and Computer Engineering, University of Southern California

Self-Supervised Pre-Training Invariant Representation Learning Statistical Learning Theory

Mar 24, 2026cs.LG

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

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

Anand Jerry George, Nicolas Macris

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

Intrinsic Dimensionality Score-Based Generative Modeling Statistical Learning Theory Diffusion Models

Mar 17, 2026cs.LG

High-Dimensional Gaussian Mean Estimation under Realizable Contamination

We study mean estimation for a Gaussian distribution with identity covariance in

\mathbb{R}^d

under a missing data scheme termed realizable

ε

-contamination model. In this model an adversary can choose a function

r(x)

between 0 and

ε

and each sample

x

goes missing with probability

r(x)

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

ε

-realizable contamination.

Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas

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

Data Contamination Statistical Learning Theory