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

May 15, 2026math.ST

Statistical Unlearning of Distributions: A Hypothesis Testing Approach

Machine learning systems increasingly face requirements to forget not only individual data points, but entire domains of information, such as toxic language, copyrighted corpora, or demographic biases. This raises a fundamental dilemma of statistical-computational tradeoffs: removing all samples from an unwanted domain may be computationally prohibitive, while randomly removing a subset may not provide distribution-level statistical guarantees. We propose a statistical framework for distributional unlearning, in which domains are modeled as probability distributions, and the goal is to remove a carefully chosen subset of samples that reduces the effect of an unwanted distribution while preserving performance on a desired one. We formalize this using a hypothesis test of the edited data with the desired and unwanted domains, leading to an interpretable and robust criterion for selecting samples to remove. Within this statistical framework, we characterize the fundamental region of the allowable edited data distributions and the removal-preservation Pareto frontier for a broad class of distribution families. This includes parametric families such as shifted Gaussians of arbitrary dimension, a one-dimensional location family with log-concave noise, and the one-dimensional Poisson family. It also includes nonparametric families such as the Gaussian white noise model, a canonical model for nonparametric regression. We prove composition rules that describe how distributional unlearning behaves across multimodal unwanted domains, and introduce a central-limit behavior for the removal-preservation baselines when composing a large number of such families. Finally, we provide finite sample guarantees by providing Pareto frontiers for some selection algorithms, and observe an information-computation gap.

Aaradhya Pandey, Sanjeev Kulkarni

Princeton University

Statistical Learning Theory Machine Unlearning

May 15, 2026cs.LG

The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimization

Differential privacy changes the effective sample size governing CVaR learning. For tail mass

τ

, the privacy-relevant sample size is not

n

, but

nτ

; equivalently, the effective private tail sample size is

εnτ

. Private CVaR excess risk decomposes into ordinary tail-risk statistical error and a privacy price. This decomposition is complete for scalar estimation and finite classes: scalar estimation has rate

Θ(B \min\{1,(nτ)^{-1/2}+(εnτ)^{-1}\})

, and finite classes of size

M

have rate

Θ(B \min\{1,\sqrt{\log(2M)/(nτ)}+\log(2M)/(εnτ)\})

. These complete rates hold under pure DP, and their lower bounds extend to approximate DP in the stated small-

δ

regimes. For convex Lipschitz learning, modular upper and lower reductions show that the CVaR-specific privacy term necessarily scales as

1/(εnτ)

, with dimension dependence inherited from private stochastic convex optimization. Together, these results identify ordinary private learning on

Θ(nτ)

informative tail records as the canonical hard subproblem inside private CVaR learning.

El Mustapha Mansouri

School of Engineering, Institute of Science Tokyo, Yokohama, Kanagawa 226-8501, Japan

Stochastic Optimization Differential Privacy Statistical Learning Theory Conditional Value-at-Risk Privacy-Utility Tradeoff

May 15, 2026stat.ML

Pessimistic Risk-Aware Policy Learning in Contextual Bandits

We study risk-aware offline policy learning, aiming to learn a decision rule from logged data that is optimal under general risk criteria. This problem is crucial in high-stakes domains where online interaction is infeasible and adverse outcomes must be carefully controlled. However, existing literature on offline contextual bandits either centers on expected-reward criteria or restricts risk considerations to policy evaluation instead of optimization. In this work, we propose a unified distributional framework for optimizing Lipschitz-continuous risk functionals, a broad class of risk measures encompassing mean-variance, entropic risk, and conditional value-at-risk, among others. By developing novel empirical concentration inequalities for importance sampling-based distributional estimators, our analysis derives data-dependent suboptimality bounds with an

\tilde{\mathcal{O}}(1/\sqrt{n})

rate, without relying on restrictive uniform overlap assumptions. This rate is minimax optimal and matches that of risk-neutral offline policy optimization, indicating that optimizing general Lipschitz risk criteria incurs no additional statistical cost relative to the expected-reward.

Yilong Wan, Yuqiang Li, Xianyi Wu

Risk-Sensitive RL Contextual Bandits Statistical Learning Theory

May 14, 2026cs.LG

Learning with Shallow Neural Networks on Cluster-Structured Features

The success of deep learning in high-dimensional settings is often attributed to the presence of low-dimensional structure in real-world data. While standard theoretical models typically assume that this structure lies in the target function, projecting unstructured inputs onto a low-dimensional subspace, data such as images, text or genomic sequences exhibit strong spatial correlations within the input space itself. In this paper, we propose a tractable model to study how these correlations affect the sample complexity of learning with gradient descent on shallow neural networks. Specifically, we consider targets that depend on a small number of latent Boolean variables, and input features grouped into clusters and correlated with the latent variables. Under an identifiability assumption, we show that for a layerwise gradient-descent variant, the sample complexity scales with the number of hidden variables and, when the signal-to-noise ratio is sufficiently high, is independent of the input dimension, up to logarithmic terms. We empirically test our theoretical findings on both synthetic and real data.

Elisabetta Cornacchia, Laurent Massoulié

INRIA, DI/ENS, PSL.

Shallow Neural Networks Neural Network Generalization Sample Complexity Statistical Learning Theory

May 14, 2026cs.LG

Fast Rates for Inverse Reinforcement Learning

We establish novel structural and statistical results for entropy-regularized min-max inverse reinforcement learning (Min-Max-IRL) with linear reward classes in finite-horizon MDPs with Borel state and action spaces. On the structural side, we show that maximum likelihood estimation (MLE) and Min-Max-IRL are equivalent at the population level, and at the empirical level under deterministic dynamics. On the statistical side, exploiting pseudo-self-concordance of the Min-Max-IRL loss, we prove that both the trajectory-level KL divergence and the squared parameter error in the Hessian norm decay at the fast rate

\mathcal{O}(n^{-1})

, where

n

is the number of expert trajectories. Our guarantees apply under misspecification and require no exploration assumptions. We further extend reward-identifiability results to general Borel spaces and derive novel results on the derivatives of the soft-optimal value function with respect to reward parameters.

Andreas Schlaginhaufen, Maryam Kamgarpour

Sycamore, EPFL

Reinforcement Learning Statistical Learning Theory

May 14, 2026stat.ML

Scaling Laws from Sequential Feature Recovery: A Solvable Hierarchical Model

We propose a simple mechanism by which scaling laws emerge from feature learning in multi-layer networks. We study a high-dimensional hierarchical target that is a globally high-degree function, but that can be represented by a combination of latent compositional features whose weights decrease as a power law. We show that a layer-wise spectral algorithm adapted to this compositional structure achieves improved scaling relative to shallow, non-adaptive methods, and recovers the latent directions sequentially: strong features become detectable at small sample sizes, while weaker features require more data. We prove sharp feature-wise recovery thresholds and show that aggregating these transitions yields an explicit power-law decay of the prediction error. Technically, the analysis relies on random matrix methods and a resolvent-based perturbation argument, which gives matching upper and lower bounds for individual eigenvector recovery beyond what standard gap-based perturbation bounds provide. Numerical experiments confirm the predicted sequential recovery, finite-size smoothing of the thresholds, and separation from non-hierarchical kernel baselines. Together, these results show how smooth scaling laws can emerge from a cascade of sharp feature-learning transitions.

Arie Wortsman-Zurich, Hugo Tabanelli, Yatin Dandi +2

Département d’Informatique, Ecole Normale Supérieure, PSL & CNRS · Information Learning and Physics Laboratory, École Polytechnique Fédérale de Lausanne (EPFL) · Statistical Physics of Computation Laboratory, École Polytechnique Fédérale de Lausanne (EPFL)

Hierarchical Representation Learning Scaling Laws Spectral Methods Statistical Learning Theory

May 13, 2026cs.LG

Finite Sample Bounds for Learning with Score Matching

Learning of continuous exponential family distributions with unbounded support remains an important area of research for both theory and applications in high-dimensional statistics. In recent years, score matching has become a widely used method for learning exponential families with continuous variables due to its computational ease when compared against maximum likelihood estimation. However, theoretical understanding of the statistical properties of score matching is still lacking. In this work, we provide a non-asymptotic sample complexity analysis for learning the structure of exponential families of polynomials with score matching. The derived sample bounds show a polynomial dependence on the model dimension. These bounds are the first of its kind, as all prior work has shown only asymptotic bounds on the sample complexity.

Devin Smedira, Abhijith Jayakumar, Sidhant Misra +2

Operations Research Center, Massachusetts Institute of Technology · Theoretical division, Los Alamos National Lab

Score Matching Sample Complexity Statistical Learning Theory

May 13, 2026stat.ME

Wahkon: A Statistically Principled Deep RKHS Superposition Network

Deep learning excels at prediction but often lacks finite-sample guarantees and calibrated uncertainty; RKHS (Reproducing Kernel Hilbert Space)-based methods provide those guarantees but struggle to adapt in high dimensions. We propose Wahkon, a deep RKHS superposition network that unifies Kolmogorov's superposition principle with RKHS regularization in the smoothing-spline tradition of Wahba. This yields a finite-dimensional deep representer theorem that makes training tractable and provides explicit layerwise complexity control. We show the penalized estimator is exactly the MAP (maximum a posteriori) estimate under a hierarchical Gaussian-process prior, extending the spline/GP duality to deep compositions. Using metric-entropy arguments, we establish minimax-optimal convergence rates under mild smoothness and clarify how depth and width trade off with regularity. Empirically, Wahkon outperforms multilayer perceptrons, Neural Tangent Kernels, and Kolmogorov--Arnold Networks across simulation benchmarks and a single-cell CITE-seq study. By unifying Kolmogorov's superposition principle with RKHS regularization, Wahkon delivers accuracy, interpretability, and statistical rigor in a single framework.

Yongkai Chen, Wenxuan Zhong, Ping Ma

Department of Statistics, Harvard University · Department of Statistics, University of Georgia

Reproducing Kernel Hilbert Spaces Kernel Methods Neural Network Approximation Theory Statistical Learning Theory

May 13, 2026stat.ML

What is Learnable in Valiant's Theory of the Learnable?

Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: Which classes are learnable in it? For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that

d

-dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a

\mathrm{poly}(d) \tilde{O}(1/ε)

sample and

\mathrm{poly}(d) \mathrm{polylog}(1/ε)

query algorithm, and prove that at least

Ω(d)

samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.

Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1

Purdue University · Stanford University · Google Research +1

PAC Learning Statistical Learning Theory

May 13, 2026cs.LG

Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

We study the optimal scale at which real-valued function classes exhibit uniform convergence and learnability. Our main result establishes a scale-sensitive generalization of the fundamental theorem of PAC learning: for every bounded real-valued class and every

γ>0

, uniform convergence at scale

γ

, agnostic learnability at scale

γ/2

, and finiteness of the fat-shattering dimension at every scale

γ'>γ

are equivalent. This resolves a question by Anthony and Bartlett (Cambridge Univ. Press 1999) on the precise scales governing learnability, refuting a conjecture attributed there to Phil Long that a multiplicative 2-factor gap is unavoidable, and improves the upper bounds of Bartlett and Long (JCSS 1998), which incur such a loss. The key technical ingredient is a direct bound on empirical

\ell_\infty

covering numbers, avoiding the standard detour through packing numbers. As a consequence, we obtain sharp asymptotic metric-entropy bounds in terms of the fat-shattering scale

γ

: an

O(\log^2 n)

bound holds already at scale

γ/2

, while an

O(\log n)

bound holds at scale

2γ

. We further show that the

O(\log^2 n)

bound is sometimes tight. These results resolve open questions by Alon et al. (JACM 1997) and Rudelson and Vershynin (Ann. of Math. 2006). As an application, we establish a sharp dichotomy for bounded integral probability metrics: every such IPM is either estimable or cannot be weakly evaluated within any multiplicative factor

c<3

, while

3

-weak evaluability always holds, resolving an open question from Aiyer et al. (ICML 2026). We also highlight several open questions on quantitative sample complexity and evaluability.

Shashaank Aiyer, Yishay Mansour, Shay Moran +2

University of Maryland · Tel Aviv University and Google Research · Technion and Google Research +1

Statistical Learning Theory Integral Probability Metrics Generalization Bounds

May 13, 2026cs.LG

Deep Learning as Neural Low-Degree Filtering: A Spectral Theory of Hierarchical Feature Learning

Understanding how deep neural networks learn useful internal representations from data remains a central open problem in the theory of deep learning. We introduce Neural Low-Degree Filtering (Neural LoFi), a stylized limit of gradient-based training in which hierarchical feature learning becomes an explicit iterative spectral procedure. In this limit, the dynamics at each layer decouple: given the current representation, the next layer selects directions with maximal accessible low-degree correlation to the label. This yields a tractable surrogate mechanism for deep learning, together with a natural kernel-space interpretation. Neural LoFi provides a mathematically explicit framework for studying multi-layer feature learning beyond the lazy regime. It predicts how representations are selected layer by layer, explains how emergence of concepts arises with given sample complexity,and gives a concrete mechanism by which depth progressively constructs new features from old ones through low-degree compositionality. We complement the theory with mechanistic experiments on fully connected and convolutional architectures, showing that Neural LoFi improves over lazy random-feature baselines, recovers meaningful structured filters, and predicts representations aligned with early gradient-descent feature discovery with real datasets.

Yatin Dandi, Matteo Vilucchio, Luca Arnaboldi +2

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

Hierarchical Representation Learning Neural Network Training Dynamics Statistical Learning Theory

May 13, 2026cs.LG

Strategic PAC Learnability via Geometric Definability

Strategic classification studies learning settings in which individuals can modify their features, at a cost, in order to influence the classifier's decision. A central question is how the sample complexity of the induced (strategic) hypothesis class depends on the complexities of the underlying hypothesis class and the cost structure governing feasible manipulations. Prior work has shown that in several natural settings, such as linear classifiers with norm costs, the induced complexity can be controlled. We begin by showing that such guarantees fail in general - even in simple cases: there exist hypothesis classes of VC dimension

1

on the real line such that, even under the simplest interval neighborhoods, the induced class has infinite VC dimension. Thus, strategic behavior can turn an easy learning problem into a non-learnable one. To overcome this, we introduce structure via a geometric definability assumption: both the hypothesis class and the cost-induced neighborhood relation can be defined by first-order formulas over

\mathbb{R}_{\mathtt{exp}}

. Intuitively, this means that hypotheses and costs can be described using arithmetic operations, exponentiation, logarithms, and comparisons. This captures a broad range of natural classes and cost functions, including

\ell_p

distances, Wasserstein distance, and information-theoretic divergences. Under this assumption, we prove that learnability is preserved, with sample complexity controlled by the complexity of the defining formulas.

Yuval Filmus, Shay Moran, Elizaveta Nesterova +2

Faculty of Mathematics, Technion – Israel Institute of Technology. · Faculty of Computer Science, Technion – Israel Institute of Technology. · Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology. +1

Strategic Classification PAC Learning Statistical Learning Theory

May 13, 2026stat.ML

Kernel-based guarantees for nonlinear parametric models in Bayesian optimization

Modern Bayesian optimization and adaptive sampling methods increasingly rely on nonlinear parametric models, yet theoretical guarantees for such models under adaptive data collection remain limited. Existing analyses largely focus on Gaussian processes, kernel machines, linear models, or linearized neural approximations, leaving a gap between theory and the nonlinear models used in practice. We develop a kernel based framework for analyzing regularized nonlinear parametric models trained on adaptively collected data. Our approach uses kernels over the parameter space to induce reproducing kernel Hilbert space structures over the corresponding model class, yielding confidence bounds for models trained with broad classes of regularized convex losses. We show how these bounds can support convergence guarantees for nonlinear acquisition and surrogate models, including randomized regularized policies that select points by maximizing a trained random model. These results provide a unified route to analyzing nonlinear parametric models in Bayesian optimization and related adaptive optimization settings.

Rafael Oliveira

The Commonwealth Scientific and Industrial Research Organisation (CSIRO) Sydney, Australia

Bayesian Optimization Adaptive Sampling Kernel Methods Statistical Learning Theory

May 13, 2026cs.IT

On the Generalization of Knowledge Distillation: An Information-Theoretic View

Knowledge distillation is widely used to improve generalization in practice, yet its theoretical understanding remains elusive. In the standard distillation setting, a teacher model provides soft predictions to guide the training of a student model. We model teacher and student training as coupled stochastic processes and introduce a distillation divergence, defined as the Kullback-Leibler divergence between these two stochastic kernels. Within this framework, we derive two generalization bounds for the student model relative to the teacher's generalization gap: an upper bound under a sub-Gaussian assumption via algorithmic stability, and a lower bound under a central condition with sharper dependence on the distillation divergence. We further develop a loss-sharpness-aware bound with an explicit tightness regime, showing that the teacher's local flatness can strictly tighten the bound. Additionally, in a linear Gaussian case study, the distillation divergence admits an interpretable decomposition into bias, variance, and rank-bottleneck costs, yielding practical guidance for distillation design.

Bingying Li, Haiyun He

Internet of Things Thrust, Information Hub The Hong Kong University of Science and Technology (Guangzhou) Guangzhou, China

Information-Theoretic Generalization Bounds Statistical Learning Theory Teacher-Student Learning Knowledge Distillation Generalization Bounds

May 13, 2026cs.LG

Separating Shortcut Transition from Cross-Family OOD Failure in a Minimal Model

Shortcut features are often invoked to explain out-of-distribution (OOD) failure, but training correlation, learned shortcut use, and test-time failure need not coincide. We study a minimal binary model with one invariant coordinate and one family-dependent shortcut coordinate. In the deterministic regime, positive average shortcut correlation pulls logistic ERM toward positive shortcut weight, but ridge regularization keeps the classifier invariant-dominated and prevents deterministic OOD failure. When the invariant coordinate is noisy, ridge-logistic ERM switches to the shortcut rule once the training shortcut signal exceeds the invariant signal. Whether that transition causes failure depends on the held-out family: weaker shortcut correlation yields positive excess risk, and sign-flipped families yield above-chance error. Synthetic checks match these analytic regimes and show that the same training-side transition can have different held-out consequences. The model separates shortcut attraction, shortcut-rule transition, and cross-family OOD failure.

Hongmin Li

School of Life Science and Technology, Institute of Science Tokyo · Department of Computational Biology and Medical Sciences, Graduate School of Frontier Sciences, The University of Tokyo

Logistic Regression OOD Generalization Binary Classification Spurious Correlation Robustness Shortcut Learning Statistical Learning Theory

May 12, 2026cs.LG

Learning to Decide with AI Assistance under Human-Alignment

It is widely agreed that when AI models assist decision-makers in high-stakes domains by predicting an outcome of interest, they should communicate the confidence of their predictions. However, empirical evidence suggests that decision-makers often struggle to determine when to trust a prediction based solely on this communicated confidence. In this context, recent theoretical and empirical work suggests a positive correlation between the utility of AI-assisted decision-making and the degree of alignment between the AI confidence and the decision-makers' confidence in their own predictions. Crucially, these findings do not yet elucidate the extent to which this alignment influences the complexity of learning to make optimal decisions through repeated interactions. In this paper, we address this question in the canonical case of binary predictions and binary decisions. We first show that this problem is equivalent to a two-armed online contextual learning problem with full feedback, and establish a lower bound of

Ω(\sqrt{|H| \cdot |B| \cdot T} )

on the expected regret any learner can attain, where

H

and

B

denote the sets of human and AI confidence values. We then demonstrate that, under perfect alignment between AI and human confidence, a learner can attain an expected regret of

O(\sqrt{|H| \cdot T\log T})

and, when

\sqrt{|H|} = O(\log T)

and

B

is countable, a non-trivial generalization of the Dvoretzky-Kiefer-Wolfowitz inequality improves the regret bound to

O(\sqrt{T\log T})

. Taken together, these results reveal that alignment can reduce the complexity of learning to make decisions with AI assistance. Experiments on real data from two different human-subject studies where participants solve simple decision-making tasks assisted by AI models show that our theoretical results are robust to violations of perfect alignment.

Nina Corvelo Benz, Eleni Straitouri, Manuel Gomez-Rodriguez

§Max Planck Institute for Biochemistry, Martinsried, Germany · †Max Planck Institute for Software Systems, Kaiserslautern, Germany

AI-Assisted Decision Making Human-AI Decision Making Statistical Learning Theory Online Learning

May 12, 2026cs.LG

High-arity Sample Compression

Recently, a series of works have started studying variations of concepts from learning theory for product spaces, which can be collected under the name high-arity learning theory. In this work, we consider a high-arity variant of sample compression schemes and we prove that the existence of a high-arity sample compression scheme of non-trivial quality implies high-arity PAC learnability.

Leonardo N. Coregliano, William Opich

PAC Learning Statistical Learning Theory

May 12, 2026cs.LG

Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds

We study the fundamental and timely problem of learning long sequences in autoregressive modeling and next-token prediction under model misspecification, measured by the joint Kullback--Leibler (KL) divergence. Our goal is to characterize how the sequence horizon

H

affects both approximation and estimation errors in this joint-distribution, sequence-level regime. By establishing matching upper and lower bounds, we provide, to our knowledge, the first complete characterization of long-horizon error behavior under the natural joint KL objective, with improved rates and optimality justification relative to existing work. On the approximation side, we show that joint KL admits a horizon-free approximation factor, in sharp contrast to Hellinger-based analyses that exhibit an

Ω(H)

dependence for computationally efficient methods; this isolates the choice of divergence as the source of approximation amplification. On the estimation side, we prove a fundamental information-theoretic lower bound of order

Ω(H)

that holds for both decomposable policy classes and fully shared policies, matching the

\widetilde O(H)

upper bounds achieved by computationally efficient algorithms. Our analysis clarifies the landscape of recent autoregressive learning results by aligning the log-loss training objective, the sequence-level evaluation metric, and the approximation metric {\color{black}through a sharp joint-KL oracle theory}. We further show that these joint-KL guarantees imply policy learning regret bounds at rates matching prior imitation learning literature.

Yunbei Xu, Yuzhe Yuan, Ruohan Zhan

National University of Singapore · University College London

Statistical Learning Theory Information-Theoretic Lower Bounds Autoregressive Modeling

May 12, 2026stat.ML

Minimax Rates and Spectral Distillation for Tree Ensembles

Tree ensembles such as random forests (RFs) and gradient boosting machines (GBMs) are among the most widely used supervised learners, yet their theoretical properties remain incompletely understood. We adopt a spectral perspective on these algorithms, with two main contributions. First, we derive minimax-optimal convergence for RF regression, showing that, under mild regularity conditions on tree growth, the eigenvalue decay of the induced kernel operator governs the statistical rate. Second, we exploit this spectral viewpoint to develop compression schemes for tree ensembles. For RFs, leading eigenfunctions of the kernel operator capture the dominant predictive directions; for GBMs, leading singular vectors of the smoother matrix play an analogous role. Learning nonlinear maps for these spectral representations yields distilled models that are orders of magnitude smaller than the originals while maintaining competitive predictive performance. Our methods compare favorably to state of the art algorithms for forest pruning and rule extraction, with applications to resource constrained computing.

Binh Duc Vu, David S. Watson

King’s College London

Model Compression Gradient-Boosted Decision Trees Decision Tree Learning Spectral Methods Statistical Learning Theory Knowledge Distillation+1

May 12, 2026stat.ML

Learning U-Statistics with Active Inference

U

-statistics play a central role in statistical inference. In many modern applications, however, acquiring the labels required for

U

-statistics is costly. Motivated by recent advances in active inference, we develop an active inference framework for

U

-statistics that selectively queries informative labels to improve estimation efficiency under a fixed labeling budget, while preserving valid statistical inference. Our approach is built on the augmented inverse probability weighting

U

-statistic, which is designed to incorporate the sampling rule and machine learning predictions. We characterize the optimal sampling rule that minimizes its variance and design practical sampling strategies. We further extend the framework to

U

-statistic-based empirical risk minimization. Experiments on real datasets demonstrate substantial gains in estimation efficiency over baseline methods, while maintaining target coverage.

Xiaoning Wang, Yuyang Huo, Liuhua Peng +1

School of Statistics and Data Sciences, LPMC, KLM-DASR and LEBPS, Nankai University, Tianjin, China · School of Mathematics and Statistics, The University of Melbourne, Melbourne, Australia

Active Inference Active Learning Adaptive Sampling Statistical Learning Theory Empirical Risk Minimization

May 11, 2026stat.ML

Factual recall in linear associative memories: sharp asymptotics and mechanistic insights

Large language models demonstrate remarkable ability in factual recall, yet the fundamental limits of storing and retrieving input--output associations with neural networks remain unclear. We study these limits in a minimal setting: a linear associative memory that maps

p

input embeddings in

\mathbb{R}^d

to their corresponding~

d

-dimensional targets via a single layer, requiring each mapped input to be well separated from all other targets. Unlike in supervised classification, this strict separation induces~

p

constraints per association and produces strong correlations between constraints that make a direct characterisation of the storage capacity difficult. Here, we provide a precise characterisation of this capacity in the following way. We first introduce a decoupled model in which each input has its own independent set of competing outputs, and provide numerical and analytical evidence that this decoupled model is equivalent to the original model in terms of storage capacity, spectra of the learnt weights, and storage mechanism. Using tools from statistical physics, we show that the decoupled model can store up to

p_c \log p_c / d^2 = 1 / 2

associations, and generalise the computation of

p_c

to linear two-layer architectures. Our analysis also gives mechanistic insight into how the optimal solution improves over a naïve Hebbian learning rule: rather than boosting input-output alignments with broad fluctuations, the optimal solution raises the correct scores just above the extreme-value threshold set by the competing outputs. These findings give a sharp statistical-physics characterisation of factual storage in linear networks and provide a baseline for understanding the memory capacity of more realistic neural architectures.

Alessio Giorlandino, Sebastian Goldt, Antoine Maillard

1International School of Advanced Studies (SISSA), Trieste, Italy · 2INRIA Paris & DI ENS, PSL University, Paris, France

Statistical Learning Theory Associative Memory

May 11, 2026stat.ML

Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data

We study sparse recovery when observations come from mixed-quality sources: a small collection of high-quality measurements with small noise variance and a larger collection of lower-quality measurements with higher variance. For this heterogeneous-noise setting, we establish sample-size conditions for information-theoretic and algorithmic recovery. On the information-theoretic side, we show that it is sufficient for

(n_1, n_2)

to satisfy a linear trade-off defining the Price of Quality: the number of low-quality samples needed to replace one high-quality sample. In the agnostic setting, where the decoder is completely agnostic to the quality of the data, it is uniformly bounded, and in particular one high-quality sample is never worth more than two low-quality samples for this sufficient condition to hold. In the informed setting, where the decoder is informed of per-sample variances, the price of quality can grow arbitrarily large. On the algorithmic side, we analyze the LASSO in the agnostic setting and show that the recovery threshold matches the homogeneous-noise case and only depends on the average noise level, revealing a striking robustness of computational recovery to data heterogeneity. Together, these results give the first conditions for sparse recovery with mixed-quality data and expose a fundamental difference between how the information-theoretic and algorithmic thresholds adapt to changes in data quality.

Youssef Chaabouni, David Gamarnik

Operations Research Center Massachusetts Institute of Technology Cambridge, MA 02139, USA

Sparse Recovery Statistical Learning Theory

May 11, 2026cs.LG

A Spectral Framework for Closed-Form Relative Density Estimation

We propose a closed-form spectral framework for relative log-density estimation in linearly parameterized probabilistic models, including unnormalized and conditional models. This is achieved by representing the Kullback-Leibler (KL) divergence as an integral of weighted chi-squared divergences, converting KL estimation into a family of least-squares problems. We derive an explicit spectral formula based only on first- and second-order feature moments, yielding closed-form estimators of both divergences and log-density potentials for fixed features. The framework extends to a broad class of f-divergences and can be combined with kernelization or feature learning with neural networks. We prove convergence guarantees for the resulting estimators and empirically compare them on synthetic data with optimization-based variational formulations, including logistic and softmax regression for normalized conditional models.

Francis Bach

SIERRA · Inria - Ecole Normale Supérieure · PSL Research University

Density Ratio Estimation Spectral Methods Statistical Learning Theory Density Estimation

May 11, 2026stat.ML

Characterizing the Generalization Error of Random Feature Regression with Arbitrary Data-Augmentation

This paper aims at analyzing the regularization effect that data augmentation induces on supervised regression methods in the proportional regime, where the number of covariates grows proportionally to the number of samples. We provide a tight characterization of the test error, measured in mean squared error, in terms only of the population quantities of the true data, as well as first and second order statistics of the augmentation scheme. Our results are valid under misspecified feature maps, and for any network architecture where only the last readout layer is trained, and the rest of the network is either frozen or randomly initialized. We specify our results in the case of Gaussian data, and show that our asymptotic characterization is tight in this setting.

Lucas Morisset, Alain Durmus, Adrien Hardy

Qube Research & Technologies · École Polytechnique

Neural Network Generalization Data Augmentation Statistical Learning Theory

May 11, 2026cs.LG

The Benefits of Temporal Correlations: SGD Learns k-Juntas from Random Walks Efficiently

We study how temporal correlations in the data can make certain sparse learning problems efficiently learnable by gradient-based methods. Our focus is on Boolean k-juntas, a canonical sparse learning problem known to pose barriers for gradient-based methods under independent uniform samples. We show that this picture changes when the samples are generated by a lazy random walk on the hypercube. In this setting, the temporal dependencies can be exploited by a two-layer ReLU network trained using stylized-SGD with a temporal-difference loss, which compares target and predicted increments across consecutive samples. For every fixed k, the resulting sample complexity is essentially linear in the ambient dimension d. By contrast, we show that for large-batch gradient methods using standard convex pointwise losses, temporal correlations do not provide the same advantage.

Elisabetta Cornacchia, Dan Mikulincer, Elchanan Mossel

1Bocconi University · University of Washington (UW). · 3Massachusetts Institute of Technology (MIT).

Statistical Learning Theory Stochastic Gradient Descent

May 10, 2026cs.LG

On Uniform Error Bounds for Kernel Regression under Non-Gaussian Noise

Providing non-conservative uncertainty quantification for function estimates derived from noisy observations remains a fundamental challenge in statistical machine learning, particularly for applications in safety-critical domains. In this work, we propose novel non-asymptotic probabilistic uniform error bounds for kernel-based regression. Compared to related bounds in the literature that are restricted to (conditionally) independent sub-Gaussian noise, our bounds allow to consider a broad class of non-Gaussian distributions, such as sub-Gaussian, bounded, sub-exponential, and variance/moment-bounded noise. Moreover, our results apply to correlated and uncorrelated noise. We compare our proposed error bounds with existing results in terms of the induced uncertainty region and their performance in safe control, demonstrating the tightness of the proposed bounds.

Johannes Teutsch, Oleksii Molodchyk, Marion Leibold +2

Chair of Automatic Control Engineering, Department of Computer Engineering, Technical University of Munich, 80333 Munich, Germany · Institute of Control Systems, Hamburg University of Technology, 21073 Hamburg, Germany · Department of Electrical and Computer Engineering, National University of Singapore, 117583 Singapore

Kernel Regression Uncertainty Quantification Nonparametric Regression Convergence Analysis Kernel Methods Statistical Learning Theory

May 10, 2026cs.LG

Online Set Learning from Precision and Recall Feedback

We consider the problem of learning an unknown subset

N_\text{target}

of a domain in an online setting. In each round

t

, the learner predicts a set of items

{N}_t

and receives one of two types of feedback, each with equal probability: precision feedback, in which a randomly chosen item from the predicted set

N_t

is revealed and the learner is told whether it belongs to

N_\text{target}

(incurring a reward if it does), or recall feedback, in which a randomly chosen item from the target set

N_\text{target}

is revealed and the learner is told whether it belongs to

N_t

(incurring a reward if it does). The goal is to maximize the cumulative reward over time. This simple online set learning problem abstracts a variety of learning scenarios with precision- and recall-type feedback. We show that a hypothesis class (a family of subsets of the domain) is learnable in this setting if and only if it has finite Vapnik-Chervonenkis (VC) dimension, mirroring the classical PAC characterization. However, the resulting algorithmic structure is markedly more intricate: in contrast to standard Probably Approximately Correct (PAC) learning -- where the algorithmic landscape is governed by the simple principle of Empirical Risk Minimization (ERM) -- our partial feedback model can invalidate ERM and even all proper learning rules. We develop algorithms to address the dependencies induced by the feedback, obtaining regret guarantees in both the realizable and agnostic settings. Our results provide a qualitative characterization of learnability in this model, addressing its most basic question, while pointing to a range of natural and intriguing open questions, including the determination of optimal regret rates.

Lee Cohen, Yishay Mansour, Shay Moran +1

1Stanford University · 2Tel Aviv University and Google Research · 3Technion and Google Research +1

PAC Learning Statistical Learning Theory Online Learning

May 10, 2026cs.LG

Instance-Adaptive Online Multicalibration

We study online multicalibration beyond the worst-case. We give a single, efficient algorithm which dynamically interpolates between benign and worst-case sequences by adaptively refining a dyadic grid of prediction values. Its error is controlled by the number of leaves in the refinement tree. Our analysis recovers the known

\widetilde O(T^{2/3})

worst-case-optimal rate for online multicalibration, while simultaneously automatically adapting to easier instances: in the marginal stochastic setting it obtains a rate of

\widetilde O(\sqrt T)

, and for piecewise-stationary means with

J

segments its rate is

\widetilde O(\sqrt{JT})

. More generally, the rate depends on a threshold-complexity measure of the predictable mean process relative to the group family. We show that this dependence is tight up to logarithmic factors.

Zhiming Huang, Jamie Morgenstern, Aaron Roth +1

Paul G. Allen School of Computer Science and Engineering, University of Washington · Department of Computer and Information Sciences, University of Pennsylvania

Probability Calibration Model Calibration Statistical Learning Theory Adaptive Learning Multicalibration

May 9, 2026cs.LG

A Complete Characterization of Learnability for Adversarial Noisy Bandits

We study adversarial noisy bandits given a known function class

\mathcal{F}

. In each round, the adversary selects a function

f \in \mathcal{F}

, the learner chooses an arm, and then observes a noisy reward determined by the chosen arm and the function

f

. The goal is to minimize the cumulative regret

R(T)

, defined as the difference between the learner's performance and that of the best fixed arm in hindsight over

T

rounds. We say that a function class

\mathcal{F}

is learnable if there exists an algorithm achieving sublinear regret. Our main result is a complete characterization of learnability for adversarial noisy bandits. The characterization is given in terms of a convexified variant of the generalized maximin volume introduced by Hanneke and Wang (2025): namely, the generalized maximin volume evaluated on the convex hull

\operatorname{co}(\mathcal F)

. We prove that

\mathcal F

is learnable if and only if this convexified generalized maximin volume is positive at every scale. This condition characterizes learnability against both oblivious and adaptive adversaries, showing in particular that these two notions of learnability are equivalent in the noisy bandit setting. Our analysis reveals that the key complexity measure is closely connected to two new combinatorial notions, hitting set and distribution covering number, which may be of independent interest. These results establish the first complete characterization of learnability for adversarial noisy bandits.

Steve Hanneke, Kun Wang

Department of Computer Science, Purdue University

Multi-Armed Bandits Statistical Learning Theory Adversarial Bandits

May 9, 2026stat.ML

Learning Theory of Transformers: Local-to-Global Approximation via Softmax Partition of Unity

This paper investigates the learning theory of Transformer networks for regression tasks on the compact Euclidean domain

[0,1]^d

and

d

-dimensional compact Riemannian manifolds. We propose a novel constructive approximation framework for Transformers that builds local approximations of the target function and aggregates them into a global approximation via softmax partition of unity. This approach leverages the attention mechanism to achieve spatial localization through affine transformations of the input. The softmax activation plays a crucial role in aggregating local approximations to a global output. From an approximation perspective, we prove that a dense Transformer equipped with only two encoder blocks and standard single-hidden-layer point-wise feed-forward networks can achieve a uniform

\varepsilon

-approximation error for

α

-Hölder continuous functions with

α\in (0,1]

using

\mathcal{O}(\varepsilon^{-d/α})

total parameters. Building upon this approximation guarantee, we establish a near minimax-optimal generalization error bound of order

\mathcal{O}\big(n^{-\frac{2α}{2α+d}} \log n\big)

for the empirical risk minimizer, where

n

is the training data size. The Transformer architecture studied in this paper is dense, shallow and wide, and employs softmax activation and sinusoidal positional encodings, closely reflecting practical implementations.

Zhongjie Shi, Wenjing Liao

School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30332, United States

Neural Network Generalization Transformer Neural Network Approximation Theory Statistical Learning Theory