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

Jun 22, 2026cs.LG

Non-asymptotic estimates of the minimal risk in statistical learning

In this paper we prove some concentration inequalities for two types of error probabilities in the Empirical Risk Principle (ERP) in statistical learning, which provide a lower bound and an upper bound for the minimal risk (in terms of the minimal empirical risk) with non-asymptotic high confidence. The usual boundedness condition of the empirical risk function is relaxed to the Gaussian or exponential integrability condition. The confidence of the lower bound of the minimal risk is shown to be independent of the number of training parameters and the dimension of the input vectors, allowing one to detect the deficiency of a learning machine efficiently; and the confidence of the upper bound of the minimal risk is proved to be high provided that the sample size

n

is much greater than the box dimension of the parameter set

Θ

in the Orlicz metric

d_{ψ_1}

associated with the risk functions. Our work is based on Talagrand's concentration inequalities (the sharp versions by Bousquet and Klein-Rio), transport-entropy inequalities and the recent progress in the theory of empirical processes and statistical learning.

Liming Wu, Sen Yang

Laboratoire de Mathématiques Blaise Pascal, CNRS-UMR 6620, Université Clermont Auvergne · IASM, Harbin Institute of Technology

Statistical Learning Theory Empirical Risk Minimization Generalization Bounds

Jun 22, 2026math.ST

Generalized nonparametric regression in reproducing kernel Hilbert spaces: Consistency and rates of convergence

We develop a comprehensive theory for regularized M-estimation in reproducing kernel Hilbert spaces. Under mild conditions on the loss we establish existence and measurability of the estimator, covering a wide range of convex and non-convex losses, including bounded robust losses. We further prove sharp rates of convergence with an explicit bias-variance decomposition governed by a novel complexity measure. We show that the variance is independent of misspecification, while the bias depends on a source condition parameter known in the learning literature. For tensor product Sobolev spaces we obtain new rates that connect to spaces of functions with dominating mixed smoothness, substantially extending existing results and explaining why these estimators circumvent the curse of dimensionality. Our methodology, combining elements from both functional analysis and empirical process theory, allows for an asymptotic linearisation of the objective function that avoids both closed-form solutions and global Lipschitz assumptions, and may be of independent interest. The estimators are implemented in C++ and theory is supported by numerical experiments.

Ioannis Kalogridis

School of Mathematics and Statistics, University of Glasgow, United Kingdom

Nonparametric Regression Reproducing Kernel Hilbert Spaces Kernel Methods Statistical Learning Theory

Jun 21, 2026cs.LG

Noise-Debiased Thermodynamic Variance for Local Learning Coefficient Probes

Local learning coefficient (LLC) probes offer a singularity-aware view of neural-network training, but mean-energy methods require a local loss baseline that is ambiguous at transient checkpoints. Thermodynamic variance avoids this input; under mini-batch evaluation, however, direct variance mixes cross-state loss fluctuations with same-state noise. We operationalize this route with the \emph{Shift-Invariant Variance Estimator} (SIVE), which estimates and subtracts the latter component using repeated evaluations. Conditional on any fixed retained path, unclipped SIVE is unbiased for noiseless path variance without requiring MCMC stationarity. The finite-scale diagnostic remains indexed by localization scale

h

---even a locally linear loss has tether-dependent variance---while interpretation as a Real Log Canonical Threshold (RLCT) requires additional stationary low-temperature conditions. Toy experiments recover calibrated finite-scale targets. At the primary localization scale, all five MNIST MLP trajectories exhibit a mid-training trough followed by a rebound in SIVE, while Raw Variance decreases from Epoch 40 to 100 in every trajectory. Across four localization scales, the joint early-drop/late-rise criterion is met in 19 of 20 trajectory--scale pairs. At Epoch 40, the estimated observation-noise correction accounts for

77.5\%

of Raw Variance. Same-state debiasing thus reveals a reproducible turning structure masked by time-varying observation noise.

Yingjia Cai

Singular Learning Theory Neural Network Training Dynamics Statistical Learning Theory Local Learning

Jun 21, 2026quant-ph

No Reference-Free Generalization in Quantum Machine Learning

Quantum machine learning is often motivated by the exponentially large state space of quantum systems, but this promise leaves a basic generalization problem unresolved: how can a learner assign different meanings to unseen quantum directions when the training data provide no preferred basis, measurement frame, or other orienting structure? We address this identifiability problem by formulating supervised learning without an external quantum reference frame, so that predictions cannot depend on an arbitrary choice of Hilbert-space coordinates. This requirement forces the learned classifier to preserve every unitary symmetry left unbroken by the training data. We prove that whenever the training states fail to span the full Hilbert space, all pure states orthogonal to their span must receive the same prediction -- even when those states are mutually orthogonal and perfectly distinguishable once an appropriate measurement is supplied. The limitation is therefore not caused by state discrimination, optimization, or computational power, but by missing reference information. We further establish a robust version under weak symmetry breaking and show that learning generic unstructured concepts on multiqubit systems requires exponentially many independently oriented training directions. Numerical illustrations visualize the resulting prediction collapse and its controlled relaxation. Our results identify feature maps, measurement bases, Hamiltonians, locality, symmetry priors, architectures, and sufficiently diverse training states as operational resources for generalization. The central implication is that Hilbert-space dimension alone is not a learnable feature space: successful QML must specify the physical structure that gives unseen quantum directions semantic meaning.

Jeongho Bang

Institute for Convergence Research and Education in Advanced Technology, Yonsei University, Seoul 03722, Republic of Korea · Department of Quantum Information, Yonsei University, Incheon 21983, Republic of Korea

Quantum Machine Learning Statistical Learning Theory

Jun 20, 2026stat.ML

Convergence Analysis of Nyström Subsampling in Covariate Shift Adaptation for Misspecified case

This paper investigates convergence properties of regularized Nyström subsampling applied to the unsupervised domain adaptation problem under covariate shift. We focus on the low-smoothness (misspecified) case where the target function lies outside the reproducing kernel Hilbert space. By combining Tikhonov regularization with Nyström projection onto a subsampled subspace, we obtain upper bounds on the excess risk that hold with high probability and are expressed in terms of the source condition, the effective dimension, and the sample sizes. We further extend the analysis to the setting where the Radon-Nikodym derivative between the target and source marginal distributions is unknown and must be approximated, and we identify the minimal additional sample sizes required to maintain the same convergence rate as in the oracle case.

Hanna Myleiko, Sergei Solodky, Vasyl Semenov

Institute of Mathematics NAS of Ukraine, 3 Tereschenkivska st., Kyiv, Ukraine. · Institute of Mathematics NAS of Ukraine, 3 Tereschenkivska st., Kyiv, Ukraine · University of Giessen, Department of Mathematics, Giessen, Germany. +1

Unsupervised Domain Adaptation Domain Adaptation Covariate Shift Statistical Learning Theory

Jun 19, 2026stat.ML

Finite-Sample Performance of Gradient Descent in Logistic Regression with Gaussian Design

We consider the parameter estimation problem in logistic regression with Gaussian design: the estimation of a fixed unknown parameter

θ^*\in \mathbb{R}^d

(

\|θ^*\|_2\ge 1

) from

n

i.i.d. samples

\{(x_i,y_i)\}_{i=1}^n

, where

x_i\sim N(0,I_d)

and

y_i|x_i \sim {\rm Bernoulli}(1/(1+\exp(-x_i^\top θ^*)))

. Our main aim is to characterize the finite-sample estimation performance and convergence behavior of gradient descent (GD) on the maximum likelihood objective (i.e., the logistic loss). Under small

O(1)

stepsize and

0

initialization, we show that GD linearly converges to a small neighborhood of

θ^*

achieving an

\ell_2

error of order

O(\sqrt{\|θ^*\|_2^5d/n})

. This substantially goes beyond existing theoretical results that lack non-asymptotic estimation error rate and exhibit much slower parameter convergence. We also establish a faster local linear convergence to the same statistical error under a large

Θ(\|θ^*\|_2)

stepsize. The main technical component is to show that the gradient of the logistic loss satisfies a certain approximate invertibility condition (AIC). To that end, we uniformly control the deviation of the gradient from its population counterpart by covering and peeling arguments, and then show that the population GD is a contraction by a delicate analysis based on the eigenvalues of population Hessian matrices. Finally, we build upon the recent work Matsumoto and Mazumdar (2025) and devise a novel efficient estimator that attains a sharper rate in high dimensions. This indicates that the existing non-asymptotic guarantees exhibit sub-optimal dependence on

\|θ^*\|_2

, and that in many regimes

Θ(\sqrt{\|θ^*\|_2d/n})

is the tight estimation error rate. Numerical examples are provided to corroborate our theoretical results.

Junren Chen, Arya Mazumdar

Department of Mathematics, University of Maryland, College Park. · Halıcıoğlu Data Science Institute, UC San Diego.

Logistic Regression Gradient Descent Statistical Learning Theory Gradient Descent Dynamics

Jun 19, 2026stat.ML

Subsampling for supervised learning in reproducing kernel Hilbert spaces

In the era of big data, subsampling became a common practice in statistical learning. By selecting a subgroup of individuals based on which the learner is trained, subsampling aims at reducing the computational cost and time of the estimation step, and ideally leads to a decrease of its energy consumption and carbon footprint. This work focuses on a nonparametric setting, in which the hypotheses set lies in a reproducing kernel Hilbert space, and the estimator is a minimizer of an empirical risk reweighted à la Horvitz-Thompson. By studying the asymptotic properties of this estimator, we reveal an optimal subsampling scheme (regarding the trace of the covariance operator) and show that it can be used via plug-in. A numerical study on synthetic and real-world datasets shows the practicability and the benefit of the proposed approach.

Eyal Vayness, Maxime Sangnier

Sorbonne Universit´e, LPSM, Paris, France

Importance Sampling Adaptive Sampling Reproducing Kernel Hilbert Spaces Statistical Learning Theory

Jun 19, 2026cs.LG

Gradient-Free Warm-Start Library Recovery: an Amortized-Regret Separation

Continual learning that is gradient-free, local, online, and append-only is attractive for edge and streaming deployment, but its value is usually argued informally. We give a provable account on recurring-regime streams. Given segmentation, a warm-start library learner attains amortized recovery cost

O\!\big(KD/\varepsilon^2+(R-K)\logK/Δ^2\big)

versus a memoryless re-estimator's

Θ(RD/\varepsilon^2)

, an advantage

(R-K)\,Θ(D/\varepsilon^2)

growing with dimension

D

and recurrence density. The mechanism is a decoupling: recognizing which of

K

seen regimes is active costs

O(\log K/Δ^2)

, independent of

D

, whereas estimating a regime costs

Θ(D/\varepsilon^2)

. We prove this is tight: matching lower bounds give recognition

Θ(\log K/Δ^2)

and a memoryless-class bound

Ω(RD/\varepsilon^2)

, so each term is individually minimax-tight (the joint statement is conditional). The separation is born-immune (a memoryless learner's advantage is identically zero) and paradigm-level: it matches, and does not beat, a fair spawn-capable Bayesian baseline; the contribution is attaining this cost structure without end-to-end backprop and with zero forgetting by construction. A count-calibrated variant ties the baseline's leading constant up to a bounded, never-negative per-recurrence overshoot, hyperparameter-free and with no per-step transcendentals. We bound the scope: recognizable regimes are capped by simplex packing (walls

e^{Θ(D)}

); autonomous segmentation is impossible at the packing wall (no detector escapes the false-alarm/delay frontier as regimes overlap); the advantage vanishes under overlap. The dimension-dependent separation is corroborated on synthetic streams and real

k

-mer genome distributions (memoryless cost

\propto D^{1.04}

, recognition

D

-independent); the one real sequential stream sits in the

D{=}1

near-null corner.

Jianwei Lou

RailMind Systems, Neuss, Germany

Continual Learning Online Continual Learning Statistical Learning Theory Online Learning

Jun 19, 2026cs.LG

Dead-Direction Signatures: A Cheap Spectral Reading of Singular Complexity

Singular learning theory characterises the complexity of a deep network through the geometry of its loss singularities. The local learning coefficient (LLC), the standard estimator of Watanabe's real log canonical threshold (RLCT,

λ

), reads this geometry as an integrated Bayesian scalar through SGLD, which needs per-task calibration and

10^4

-

10^6

forward-backward passes per checkpoint. We introduce Dead-Direction Signatures (DDS), a family of cheap closed-form spectral readings of singular structure: each reads a network's activation matrix or per-sample-gradient Fisher-Gram at a chosen layer, replacing the SGLD posterior chain with spectral linear algebra. The readings rest on a dead-direction framework that predicts a structural correlation between activation- and Fisher-side spectra at any singular minimum, and a rank-multiplicative volume identity that single-eigenvalue monitors cannot produce: the active-volume

\log\det^{+}(G)

slope counts the dead directions, tracking the rank-deficit

r

across

r \in \{1,2,3,4\}

(slope ratios

2.0, 3.1, 4.0

at

r{=}2,3,4

against the predicted

2,3,4

), where the smallest eigenvalue is rank-blind. On reduced-rank regression with closed-form

λ

, calibrated LLC recovers

λ

at

99\%

mean and the DDS observables rank-track it at the framework-predicted sign; on a non-linear modular-addition transformer DDS separates

d_{\mathrm{model}}

across eighteen orders of magnitude where calibrated LLC at the protocol budget is rank-flat. Complementary to LLC's integrated posterior reading, DDS gives a directional, layer-local handle on a network's dead directions, read in closed form from its activation and gradient spectra.

Tejas Pradeep Shirodkar, P. J. Narayanan

IIIT, Hyderabad

Singular Learning Theory Spectral Methods Statistical Learning Theory

Jun 18, 2026cs.LG

On the Oracle Complexity of Interpolation-Based Gradient Descent

Recent work on first-order optimizers for empirical risk minimization (ERM) has suggested that smoothness of ERM loss functions in the training data, rather than in the optimization parameters, can be leveraged to improve the oracle complexity of gradient descent (GD) methods. In this paper, we propose an inexact gradient method, piecewise polynomial interpolation-based gradient descent (PPI-GD), which approximates the full gradient in each iteration by querying the first-order oracle at equidistant points in the data domain to construct polynomial interpolants of the resulting gradient samples over appropriately sized patches of the data domain. We analyze the oracle complexity of PPI-GD for strongly convex and non-convex loss functions when the data space dimension is bounded by a polylogarithmic function of the number of training samples, and find it to outperform several GD variants in key regimes when the loss function is sufficiently smooth. Furthermore, our analysis extends several techniques from the error analysis of bicubic spline interpolants to the setting of

d

-variate tensor product polynomial interpolants which may be of independent interest in interpolation analysis.

Dongmin Lee, William Lu, Anuran Makur

Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA · Department of Computer Science and the Elmore Family School of Electrical and Computer Engineering, Purdue University, West Lafayette, IN 47907, USA

Oracle Complexity Gradient Descent Nonconvex Optimization Statistical Learning Theory Empirical Risk Minimization

Jun 17, 2026stat.ML

On Local Population-Risk Certificates

We develop finite-sample certificates for local population-risk increments

Pδ_v=R(θ_0+v)-R(θ_0)

,

v\in\mathcal D

. The primitive object is an expected-valid upper endpoint

\widehat{\mathsf U}_{\mathcal D}

satisfying

\mathbb E\sup_{v\in\mathcal D} \{Pδ_v-\widehat{\mathsf U}_{\mathcal D}(v)\}\le0

. This uniform criterion certifies any measurable update selected from the same sample and allows penalties to depend on empirical geometry. The main construction is a cross-fitted ridge calibration for linear feature classes. A pilot fold learns the ridge metric, the complementary fold calibrates the squared mean error in that metric, and complete split averaging recovers the full empirical covariance in the directional quadratic form

\widehat q_{X,λ}

. The optimized diagnostic scale is

\{\widehat q_{X,λ}(h) \widehat r_{X,n_{\rm p},λ}^{\rm cf}/n\}^{1/2}

, and the calibrated trace factor

\widehat r_{X,n_{\rm p},λ}^{\rm cf}

is compared with the ordinary ridge effective dimension

\widehat r_{X,λ}

. For nonsmooth losses, an exact fixed-mask decomposition

δ_v=J_v^0+R_v^\circ+C_v

separates frozen Taylor fluctuations, good-path remainders, and interface crossings. Applying the linear and composite certificates componentwise yields endpoints for same-sample expected local search and concentrated release rules.

Mingzhi Song

Department of Mathematics, The University of Hong Kong, Hong Kong

Statistical Learning Theory Generalization Bounds

Jun 17, 2026cs.LG

Smoothness-Based Derandomization of PAC-Bayes Bounds

We study PAC-Bayes derandomization for smooth loss functions. Our goal is to obtain generalization bounds that hold with high probability for deterministic predictors by exploiting smoothness properties of both the loss and the predictor class. We show that passing from the Gibbs predictor to the deterministic predictor at the posterior mean has a precise cost, given by the generalization gap of the Jensen gap class. We control this class through its Rademacher complexity, leading to bounds for deterministic predictors that involve flatness quantities expressed in terms of parameter Jacobians and Hessians of the score map. The framework applies to both bounded and unbounded smooth loss functions, and we specialize the results to linear predictors and smooth neural networks. Finally, the Jacobian and Hessian quantities appearing in the theory motivate a practical regularizer. For BatchNorm networks, we compute this regularizer with respect to effective BatchNorm weights obtained by folding the BatchNorm transformation into the adjacent affine weights. Experiments on CIFAR-10 illustrate the behavior of this regularizer under different batch sizes.

Alexandre Lemire Paquin, Brahim Chaib-Draa, Philippe Giguère

Department of Computer Science and Software Engineering Université Laval, Québec, Canada

Neural Network Generalization PAC-Bayesian Generalization Bounds Statistical Learning Theory

Jun 17, 2026stat.ML

Kernel of Partition Paths: A Unified Representation for Tree Ensembles

A recent line of work has reframed individual decision trees as linear models on engineered features associated with their splits, opening routes for oracle inequalities and feature-importance reinterpretation, but leaving open the question of what unified geometric object a forest induces when one indexes its feature map by nodes rather than by splits. The present paper studies that object. KPP indexes the feature map by the nodes of the forest, weighted by a path metric that turns each coordinate into a component of a squared-Euclidean path-isometric embedding. KPP unifies four pillars under a single node-indexed representation whose Gram is non-diagonal and carries a metric: prediction, exact additive attribution, deterministic Lipschitz robust radius in the KPP metric, and uniform Rademacher risk bounds for regression and classification under fixed, honest, or cross-fit conditioning. All probabilistic guarantees are conditional on the representation and are stated under three explicit conditioning regimes; the robust-radius guarantee is deterministic in the KPP metric rather than in a norm on the raw input. Conjectured fast-rate refinements for both regression and classification are stated as open problems and are not claimed as theorems.

Nicolas Mahler

Datapred SAS 23 rue Mirabeau 94300 Vincennes, France · Datapred SA EPFL Innovation Park – Bâtiment A 1015 Lausanne, Switzerland

Feature Attribution Ensemble Learning Kernel Methods Certified Robustness Statistical Learning Theory

Jun 16, 2026cs.LG

Sign-Rank, Index, and List Replicability: Connections and Separations

In learning theory, the sign rank of a binary concept class captures the smallest dimension in which it can be represented by points and halfspaces. Despite tremendous interest, lower bounds on sign rank are notoriously difficult to come by. Two recent approaches to the problem establish lower bounds on sign rank by measures that are easier to analyze: the

\mathbb{Z}_2

-index and the list replicability number. We order these measures, showing that the

\mathbb{Z}_2

-index is upper-bounded by a linear function of the list replicability number. As a main consequence, we obtain a strong separation between sign rank and

\mathbb{Z}_2

-index, thereby resolving a question of Frick, Hosseini, and Vasileuski. This motivates a thorough study of list replicability, the stronger of the two lower-bounding measures. We establish upper bounds on the list replicability number by two combinatorial measures: height and minimum star number. We also prove a fundamental composition result, showing that the product of two concept classes has list replicability number bounded by the sum of the list replicability numbers of the two classes.

Ari Blondal, Hamed Hatami, Pooya Hatami +2

McGill University · Ohio State University

Statistical Learning Theory

Jun 16, 2026cs.LG

No-Free-Fairness: Fundamental Limits and Trade-offs in Learning Systems

In this paper, we establish a set of theoretical impossibility results, termed the No-Free-Fairness theorems, that identify three fundamental sources of disparity in learning systems. First, we show that when a task exhibits irreducible cost on a subgroup, any decision rule must trade off overall performance with disparity, yielding an inherent fairness--cost frontier. Second, we prove that even in ideal, noise-free settings where a perfectly fair and accurate solution exists, finite-sample learning alone induces nontrivial subgroup disparity, ruling out distribution-free fairness guarantees. More seriously, enforcing strict relative fairness creates a statistical bottleneck: achieving low cost may require exponentially many samples. Third, we show that limitations of the model class can independently induce disparity: if the model cannot represent accurate solutions for a subgroup, fairness remains unattainable regardless of data or training procedure. Overall, these results demonstrate that unfairness is not solely a consequence of biased data or suboptimal optimization, but arises from the intrinsic structure of decision problems, the constraints of finite data, and the expressivity of models. Our framework applies broadly beyond standard supervised learning, and suggests that achieving fairness requires explicit trade-offs and should be treated as a core design consideration.

Khoat Than

Hanoi University of Science and Technology

Algorithmic Fairness Group Fairness Statistical Learning Theory

Jun 15, 2026stat.ML

Another Look at Log-PCA for Probability Measures: A Dynamical Formulation and Statistical Convergence

This paper is concerned with learning principal variations of random probability measures on

\mathbb{R}^m

under the Wasserstein geometry. We introduce a new dynamical formulation to interpret the log-PCA, a linearized principal geodesic analysis, as a variational approach. Our differentiable version, termed as the Wasserstein Tangential PCA (WT-PCA), captures the local principal modes of geodesic variations of a (weighted) probability measure on the Wasserstein space via its covariance operator at barycenter. Based on the dynamical perspective and leveraging parallel transport structure of the optimal transport problems, we derive a general statistical convergence rate of the empirical WT-PCA when estimated from data in terms of the 2-Wasserstein distance between the population and empirical barycenter reference measures.

Peng Xu, Changbo Zhu, Young-Heon Kim +1

Department of Statistics University of Illinois Urbana-Champaign · Department of ACMS University of Notre Dame · Department of Mathematics University of British Columbia +1

Principal Component Analysis Statistical Learning Theory Optimal Transport

Jun 15, 2026stat.ML

A nonparametric two-sample test using a parametric integral probability metric

Detecting distributional differences between two independent samples is a fundamental problem in statistics and machine learning. Nonparametric two-sample testing provides a principled framework for determining whether two samples are drawn from the same underlying distribution, without assuming any specific parametric form for the distribution. In this study, we propose a new two-sample test statistic based on a newly introduced integral probability metric (IPM), using a specially designed parametric discriminator class with a single node of a neural network. We show that the resulting test statistic, called PReLU-IPM, is nonparametric and establish theoretical guarantees for the associated two-sample testing procedure, PReLU-TST, including its consistency and asymptotical equivalence to nonparametric IPM-based tests under regularity conditions. By analyzing multiple simulated and real benchmark datasets, we demonstrate that PReLU-TST achieves higher power across a range of alternatives or performs comparably to its competitors, for finite samples.

Yuha Park, Yongdai Kim

Department of Mathematics, University of Hamburg, Hamburg, Germany. · Department of Statistics, Seoul National University, Seoul, Republic of Korea.

Two-Sample Testing Statistical Learning Theory Integral Probability Metrics Statistical Hypothesis Testing

Jun 14, 2026cs.LG

Brownian Kernel Ladders

Constructing mathematically tractable function spaces that capture hierarchical compositional representations remains a central challenge in statistical learning theory. We introduce Brownian kernel ladders (BKLs), a recursively defined hierarchy of integral reproducing kernel Hilbert spaces generated through Brownian-kernel integral constructions. Starting from linear functionals, each layer is obtained by integrating Brownian kernels over probability measures supported on subsets of the previous layer, yielding a recursive function-space model in which depth is encoded directly through the hierarchy. Based on this framework, we define canonical BKL spaces together with an associated complexity functional. We establish several analytical and statistical properties of these spaces. In particular, we show that BKL spaces form quasi-Banach spaces, satisfy depth-dependent Hölder regularity estimates, and exhibit strict monotonicity with respect to depth. We further prove existence results for regularized empirical risk minimization and derive Gaussian complexity bounds that remain uniformly controlled with respect to both the ambient dimension and the hierarchy depth. A key ingredient of the analysis is a combinatorial proof technique based on recursive subset decompositions and Brownian-kernel threshold representations. These estimates yield excess-risk guarantees of near-parametric order for regularized empirical risk minimization over BKL spaces. Our results provide a mathematically tractable hierarchical function-space framework for studying compositional representations in deep learning.

Mahdi Mohammadigohari, Giuseppe Di Fatta, Giuseppe Nicosia +1

Faculty of Engineering, Free University of Bozen-Bolzano, Via Bruno Buozzi 1, Bolzano, 39100, Italy · Department of Biomedical and Biotechnological Sciences, University of Catania, Catania, 95123, Santa Sofia, 97, Italy · Center for Applied Optimization, Department of Industrial and Systems Engineering, University of Florida, FL 32611, Gainesville, USA

Hierarchical Representation Learning Reproducing Kernel Hilbert Spaces Kernel Methods Statistical Learning Theory Generalization Bounds

Jun 13, 2026cs.LG

Can Neural Networks Achieve Optimal Computational-statistical Tradeoff? An Analysis on Single-Index Model

In this work, we tackle the following question: Can neural networks trained with gradient-based methods achieve the optimal computational-statistical tradeoff in learning Gaussian single-index models? Prior research has shown that any polynomial-time algorithm under the statistical query (SQ) framework requires

Ω(d^{s^\star/2}\lor d)

samples, where

s^\star

is the generative exponent representing the intrinsic difficulty of learning the underlying model. However, it remains unknown whether neural networks can achieve this sample complexity. Inspired by prior techniques such as label transformation and landscape smoothing for learning single-index models, we propose a unified gradient-based algorithm for training a two-layer neural network in polynomial time. Our method is adaptable to a variety of loss and activation functions, covering a broad class of existing approaches. We show that our algorithm learns a feature representation that strongly aligns with the unknown signal

θ^\star

, with sample complexity

\widetilde{O} (d^{s^\star/2} \lor d)

, matching the SQ lower bound up to a polylogarithmic factor for all generative exponents

s^\star\geq 1

. Furthermore, we extend our approach to the setting where

θ^\star

is

k

-sparse for

k = o(\sqrt{d})

by introducing a novel weight perturbation technique that leverages the sparsity structure. We derive a corresponding SQ lower bound of order

\widetildeΩ(k^{s^\star})

, matched by our method up to a polylogarithmic factor. Our framework, especially the weight perturbation technique, is of independent interest, and suggests potential gradient-based solutions to other problems such as sparse tensor PCA.

Siyu Chen, Beining Wu, Miao Lu +2

Department of Statistics and Data Science, Yale University · Department of Statistics, University of Chicago · Department of Management Science and Engineering, Stanford University +1

Representation Learning Single-Index Models Neural Network Optimization Statistical Learning Theory

Jun 12, 2026cs.LG

The Geometry of Saturation: Effective Rank Predicts When Labels Stop Helping in Few-Shot Classification

Few-shot label acquisition lacks a label-free signal for when additional labels cease to improve accuracy: existing stopping criteria either require a held-out validation set (violating the few-shot premise) or rely on theoretically ungrounded heuristics, so we introduce the spectral saturation index

S(K)=\mathrm{erank}(\hatΣ_W^{(K)})/K

, the exponential spectral entropy of the pooled within-class covariance normalized by per-class support size

K

, which measures the exploration rate per label and falls below a fixed threshold

τ=0.02

once the explored spectral subspace saturates and marginal accuracy gains vanish; across 49 real tasks (binary, 5-way, 10-way) and three frozen backbones (PCA-50, CLIP ViT-B/32, DINOv2 ViT-S/14),

S(K)

correlates strongly with the marginal gain on doubling the support set (

ρ_{\text{pool}}=0.6366

,

p=2.9\times10^{-57}

, cluster-bootstrap 95% CI

[0.551,0.720]

), a fixed

τ=0.02

classifies stop/continue decisions with cluster-bootstrap

\mathrm{AUC}=0.787

(95% CI

[0.713,0.860]

) with high recall on meaningful gains (

ΔA>1\%

), and a partial correlation controlling for

\log K

yields

ρ_{\text{partial}}=0.324

(

p=1.65\times10^{-13}

), confirming

S(K)

carries spectral information beyond shared

K

-dependence; theory predicts this from first principles, since the population effective rank sets the saturation scale

K_{\text{sat}}\approx\mathrm{erank}(Σ_W)/τ

,

τ=0.02

sits at the boundary between the first and second descent (Nakkiran et al., 2021), and

O(1/K)

bias in the sample effective rank explains the small-

K

hump in

S(K)

; for unregularized linear probes (

C=\infty

), practitioners should halt when

S(K)<0.02

(PCA-50, hard stop) or monitor

S(K)

dropping from

\sim0.3\to0.05

(foundation models, diminishing-returns signal), with computation costing

\sim1

ms at

d=50

.

Arnav Gupta

Independent Researcher, Nepal

Early Stopping Few-Shot Learning Classification Statistical Learning Theory

Jun 12, 2026stat.ML

Gradient boosting for extremes: sampling theory and application to insurance

We develop a statistical learning theory for gradient boosting applied to the estimation of covariate-dependent Generalized Pareto (GP) distributions in the context of Peaks-over-Threshold modeling. After an orthogonal reparametrization of the GP likelihood that diagonalizes its Fisher information matrix, we cast the estimation problem within the Empirical Risk Minimization (ERM) framework and derive non-asymptotic error bounds for the boosting estimator. Our analysis accounts for three distinct sources of error in the process: statistical fluctuations, the approximation bias inherent to the asymptotic nature of the GP model-controlled under second-order regular variation-and the approximation error associated with the finite number of boosting iterates, making explicit the resulting bias-variance trade-off. We illustrate the practical benefits of the reparametrization through simulations, showing that it significantly reduces gradient correlation during training and improves convergence stability. The methodology is applied to a medical malpractice insurance dataset from the Texas Department of Insurance, comprising over 18 000 closed claims. The gradient boosting approach yields a good fit for the tail of settlement cost distributions and reveals that the number of days to settlement is the dominant predictor of tail heaviness, consistent with earlier findings in the reserving literature.

Stéphane Lhaut, Olivier Lopez

1CREST, CNRS, Ecole polytechnique, Groupe ENSAE-ENSAI, ENSAE Paris, Institut Polytechnique de Paris, Palaiseau, France

Gradient-Boosted Decision Trees Heavy-Tailed Distributions Statistical Learning Theory Extreme Value Theory

Jun 12, 2026stat.ML

A Bregman Perspective on Classification and Regression Trees

Classification and Regression Trees (CART) constitute one of the most influential paradigms in statistical learning. Although a variety of impurity measures have been proposed for different statistical models, these criteria are typically introduced on a case-by-case basis and analyzed separately. In this paper, we study CART through the lens of Bregman divergences. This perspective places the classical least-squares criterion, Poisson deviance, Kullback-Leibler-type losses, and other impurity measures associated with exponential-family models within a common framework. As a result, key ingredients of the CART methodology -- including node representatives, impurity measures, and split selection rules -- can be expressed and analyzed through general properties of convex functions rather than through separate model-specific constructions. Beyond the algorithmic formulation, we investigate theoretical properties of Bregman-based CART procedures. In particular, we analyze how geometric properties of the generating convex function influence impurity reductions and stability of recursive partitions. We also establish consistency results within the proposed framework, providing a unified theoretical treatment for a broad family of CART type procedures. Our results provide a geometric interpretation of impurity-based tree construction and show that many classical CART impurity criteria admit a common interpretation within a Bregman framework.

Mathias Bourel

IESTA, Facultad de Ciencias Económicas y de Administración, Universidad de la República, Uruguay · IRL-2030, Instituto Franco-Uruguayo de Matemática e Interacciones (IFUMI)

Functional Bregman Divergences Decision Tree Learning Classification Statistical Learning Theory

Jun 11, 2026cs.LG

Learning with Simulators: No Regret in a Computationally Bounded World

Understanding the minimal assumptions necessary for generalization is the fundamental question in learning theory. Unfortunately, most results rely heavily on independence (or some proxy thereof) of the data-generating process, while results for strongly dependent data are far more limited. Towards addressing this gap, we introduce the framework of simulatable processes, where the learner has access to a simulator that approximates the distribution generating the data (which may be an arbitrarily complex and dependent process). Surprisingly, given access to such a simulator, we show that we can recover the same learning guarantees as in the classical setting with independent data, namely, error bounds that depend on the VC dimension. Further, we use this framework to study the power of conditional sampling and show strict statistical and computational advantages in this setting. As a highlight of our framework, we exhibit a single algorithm that simultaneously learns any given VC class under all processes samplable in bounded polynomial time, with regret controlled by the time-bounded Kolmogorov complexity of the process. This provides a significant conceptual broadening of the classical PAC model.

Sasha Voitovych, Abhishek Shetty, Noah Golowich +1

MIT · Microsoft Research

PAC Learning Statistical Learning Theory

Jun 11, 2026cs.LG

Limits of spectral learning under noise

Learning functional relationships from noisy data is a central problem in scientific inference. Spectral methods approximate unknown functions by expanding them in a basis and estimating the corresponding coefficients from data, but the stability of these coefficients under noise remains poorly understood. Here we study supervised regression with additive label noise using sparse spectral representations across multiple bases and dimensions. We show that noise induces a predictable drift in the learned coefficient vector whose magnitude depends on the effective number of active spectral modes. After whitening the empirical feature geometry, we derive a closed-form expression for the overlap between noisy and noiseless coefficient vectors, revealing a universal degradation curve governed by a single intrinsic noise scale. Numerical experiments across Fourier, Legendre, Bessel, and Haar bases confirm the theoretical prediction. The results demonstrate that spectral learning exhibits a fundamental noise threshold beyond which coefficient estimates become unstable, placing intrinsic limits on recovering functional structure from noisy data.

Sabin Roman, Ljupco Todorovski, Saso Dzeroski +2

Jožef Stefan Institute, Ljubljana, Slovenia · Faculty of Mathematics and Physics, University of Ljubljana, Slovenia · Department of Chemical Engineering, Universitat Rovira i Virgili, Tarragona, Catalonia +2

Noisy-Label Learning Spectral Methods Statistical Learning Theory

Jun 11, 2026cond-mat.dis-nn

A solvable model for unsupervised federated learning

We introduce a theoretical framework for analyzing federated learning in a generative setting through a teacher-multiple interacting students scenario, in which each student receives a distinct realization of the data, either through a different noise corruption or by accessing a different subset, possibly of varying size. Using theoretical tools in equilibrium disordered system, we analytically show that interactions among students systematically enhance learning performance: highly noisy students require fewer samples to recover the underlying pattern, while low-noise students achieve a larger overlap with the ground-truth signal. We derive the optimal Bayesian conditions for teacher recovery as functions of the sample complexity, noise level, and interaction strength, and validate these predictions through numerical simulations. The resulting dynamics can be mapped onto equilibrium sampling in a Restricted Boltzmann Machine with a structured hidden layer, providing a principled theoretical understanding of how interactions improve distributed generative modeling.

Giovanni Catania, Aurélien Decelle, Gianluca Manzan +2

Institute for Cross-disciplinary Physics and Complex Systems IFISC (CSIC-UIB), Campus Universitat Illes Balears, 07122 Palma de Mallorca, Spain. · Escuela Técnica Superior de Ingenieros Industriales, Universidad Politécnica de Madrid, Calle de José Gutiérrez Abascal 2, Madrid 28006, Spain. · GISC - Grupo Interdisciplinar de Sistemas Complejos 28040 Madrid, Spain. +5

Statistical Physics of Learning Unsupervised Learning Generative Modeling Statistical Learning Theory Teacher-Student Learning Federated Learning

Jun 11, 2026cs.LG

Is Spurious Correlation Removal Always Learnable?

Invariant learning can fail even when the invariant structure is statistically identifiable. We show a conditional computational barrier: under a black-box samplable supervised sparse recovery primitive motivated by average-case sparse-recovery reductions, there exist \emph{samplable} multi-environment instances with a one-dimensional predictive invariant subspace (

k=1

) that are learnable with polynomial samples by exhaustive search, while any polynomial-time constant-accuracy recovery algorithm would contradict the primitive. We further quantify environment diversity by a separation parameter

γ

, which controls identifiability and the curvature of invariance objectives. Under sufficient diversity and local Gaussian regularity, the minimax risk is

\mathbb{E}[\dist(\hat{V},V_{\mathrm{inv}})^2]=Θ(k(d-k)/(n|\mathcal{E}|))

, and under label-induced shifts a phase transition occurs at

n^*\propto k(d-k)/(|\mathcal{E}|γ^2)

with refined estimation error scaling proportional to

1/γ^2

. Synthetic and real datasets illustrate the predicted gaps and transitions and motivate simple diversity diagnostics.

Yibo Zhou, Bo Li, Hai-Miao Hu +3

Beijing Key Laboratory of Digital Media, School of Computer Science and Engineering, Beihang University, Beijing 100191, China · State Key Laboratory of Virtual Reality Technology and Systems, Beihang University, Beijing 100191, China · Hangzhou Innovation Institute of Beihang University, Hangzhou 310051, China +1

Spurious Correlation Robustness Invariant Representation Learning Statistical Learning Theory

Jun 10, 2026cs.LG

Two-Layer Linear Auto-Regressive Models Estimate Latent States

Auto-regressive models have emerged as powerful tools for sequential data, from language to video. Understanding how and why these models learn latent representations remains an open theoretical question. In this work, we demonstrate that when trained by empirical risk minimization on data from partially observed linear dynamical systems, two-layer linear auto-regressive models naturally learn to approximate Kalman filtering. In particular, we show that the learned hidden representation coincides, up to a similarity transformation, with the state estimates produced by the optimal (Kalman) filter, even though the model has no explicit knowledge of the underlying dynamics or state. The result follows from three main insights. First, we establish that the Kalman filter is well approximated by an auto-regressive model with bounded truncation error. Second, we show that despite non-convexity, the two-layer optimization landscape is benign, i.e., all stationary points are either strict saddles or global minima. Finally, as our main contributions, we provide finite-sample guarantees on prediction error, parameter estimation error, and latent state recovery. Numerical simulations support the theoretical results and demonstrate that the latent representations of auto-regressive models recover state estimates.

Yahya Sattar, Sunmook Choi, Leo Maynard-Zhang +3

Cornell · U Washington · Imperial College London +1

Dynamical Systems Kalman Filtering State Representation Learning Statistical Learning Theory Autoregressive Modeling

Jun 10, 2026cs.LG

How Useful is Causal Invariance for Domain Adaptation in Finite-Sample Settings?

Machine learning models often degrade when they are deployed on a target distribution that differs from the source distributions they were trained on. Recent work in causality-based domain generalization has shown how shared causal structure between domains can induce invariant predictors, e.g., models on a subset of features which have stable risk across structured domain shifts. However, the extent to which such population-level causal invariances can lead to gains in finite-sample settings remains underexplored. In particular, in practice we often have access to a few labeled target samples, a setting called supervised domain adaptation (sDA). In this paper, we explore when (full or partial) causal knowledge can provably improve supervised domain adaptation. As a first step, we study linear regression, where full or partial causal knowledge specifies a collection of invariant or possibly invariant feature subsets, each yielding a source-trained candidate predictor. We derive matching upper and lower bounds showing that finite-sample gains are governed by the target-risk margins separating the candidates, together with the finite-source estimation error. When these margins are sufficiently large relative to

n_Q

, an adaptive aggregation procedure can match the best candidate predictor while avoiding negative transfer relative to target-only learning. On the other hand, when the margins are too small, no algorithm can reliably exploit the candidate collection to obtain faster finite-sample rates. We further connect these margins to structural shift magnitude in linear SCMs and validate the theory on real-world causal benchmarks.

Julia Kostin, Kasra Jalaldoust, Elias Bareinboim +2

Department of Computer Science, ETH Zurich · Causal Artificial Intelligence Lab, Columbia University · Department of Statistics, Columbia University

Structural Causal Models Statistical Learning Theory

Jun 10, 2026quant-ph

Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning

A central principle in quantum machine learning is that an ansatz should be expressive enough to represent the quantum data of interest. Yet, the expressibility is statistically meaningful only insofar as it can be learned from finitely many copies of an unknown quantum state. In this work, we develop an information-theoretic Occam theory for quantum data generated by finite-size quantum circuits. For the class

S_{n,G}

of

n

-qubit pure states preparable with at most

G

two-qubit gates, a metric-entropy argument gives the realizable sample law

\widetildeΘ(G/ε^2)

in the circuit-limited regime. For an arbitrary source

\hatρ

, we introduce the best

G

-gate approximation error

d_G(\hatρ)

and the approximate circuit complexity

C_η(\hatρ)

. We prove an agnostic quantum Occam theorem: with

M

copies, one can learn up to the best

G

-gate approximation error plus a statistical penalty

\widetilde{O}(\sqrt{G/M})

. We then remove the need to know

G

in advance through an adaptive model-selection theorem whose oracle inequality selects the circuit complexity justified by the data. Matching lower bounds yield a sample-supported expressibility law: at trace-distance accuracy

ε

,

M

samples can support only

G_{\rm supported} \simeq Mε^2

gates, up to logarithmic factors and tomography saturation at

2^n

. Thus, the circuit complexity becomes an adaptive statistical resource rather than a static promise. Our framework turns bounded circuit complexity into a model-selection principle for quantum machine learning.

Jeongho Bang, Kyoungho Cho, Jeongwoo Jae

Institute for Convergence Research and Education in Advanced Technology, Yonsei University, Seoul 03722, Republic of Korea · Department of Quantum Information, Yonsei University, Incheon 21983, Republic of Korea · Department of Statistics and Data Science, Yonsei University, Seoul 03722, Republic of Korea +1

Model Selection Sample Complexity Quantum Machine Learning Statistical Learning Theory Information-Theoretic Lower Bounds

Jun 9, 2026cs.LG

Robust Regression of General ReLUs with Queries

We study the task of agnostically learning general (as opposed to homogeneous) ReLUs under the Gaussian distribution with respect to the squared loss. In the passive learning setting, recent work gave a computationally efficient algorithm that uses

poly(d,1/ε)

labeled examples and outputs a hypothesis with error

O(opt)+ε

, where

opt

is the squared loss of the best fit ReLU. Here we focus on the interactive setting, where the learner has some form of query access to the labels of unlabeled examples. Our main result is the first computationally efficient learner that uses

d polylog(1/ε)+\tilde{O}(\min\{1/p, 1/ε\})

black-box label queries, where

p

is the bias of the target function, and achieves error

O(opt)+ε

. We complement our algorithmic result by showing that its query complexity bound is qualitatively near-optimal, even ignoring computational constraints. Finally, we establish that query access is essentially necessary to improve on the label complexity of passive learning. Specifically, for pool-based active learning, any active learner requires

\tildeΩ(d/ε)

labels, unless it draws a super-polynomial number of unlabeled examples.

Ilias Diakonikolas, Daniel M. Kane, Mingchen Ma

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

ReLU Neural Networks Active Learning Statistical Learning Theory