Statistical Learning Theory

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

Aug 9, 2026cs.LG

No Unique Minimizer, No Problem: On the Consistency of Robust Neural Classifiers

Neural network classifiers trained by cross-entropy minimization are highly sensitive to label noise and adversarial contamination. While robust alternatives offer bounded influence and resistance to corruption, their statistical foundations in the deep learning setting are insufficient due to a fundamental difficulty: neural parameterizations are non-identifiable, so the population loss minimizer is an equivalence class of parameters, not a unique point. We develop a consistency theory for robust neural classifiers based on the S-divergence family that requires no identifiability assumption. Casting training as stochastic optimization over a non-identifiable parameter space, we prove that empirical S-divergence minimizers converge to the population-optimal equivalence class under mild regularity conditions, and verify these conditions for three architecture choices. We further establish that limit points of the robust training algorithm are stationary points of the empirical objective. Experiments on vision and language benchmark datasets confirm that S-divergence training maintains clean-data accuracy while exhibiting performance competitive with existing robust methods.

Subhabrata Majumdar, Anand Deo, Partha Pratim Saha +1

Indian Institute of Management Bangalore · Independent Researcher · Indian Statistical Institute, Kolkata

Neural Network Generalization Neural Network Robustness Robust Loss Functions Learning with Noisy Labels Statistical Learning Theory Robust Estimation

Ask PDF

Aug 9, 2026cs.LG

Optimal Learning Under Tsybakov Noise

Probably Approximately Correct (PAC) learning [Val84] is a fundamental learning model that has been extensively investigated. In this model,

\mathcal{H} \subseteq \{0,1\}^{\mathcal{X}}

is a concept class, and

h^*\in\mathcal{H}

is the target concept to be learned. Having access to i.i.d. labeled examples from a distribution

\mathcal{D}

over

\mathcal{X}\times\{0,1\}

, which admits

h^*

as the best concept in

\mathcal{H}

, the goal is to design a learning algorithm that outputs a hypothesis having low error competitive to

h^{*}

with high probability. This model was initially studied under the realizable setting, which assumes that

h^*

has no error. A natural relaxation is to allow label noise, that is, the true label can be flipped with probability

η\in(0,1/2)

. In reality, certain labels might be extremely noisy, especially for those points near the decision boundary. Hence, it is natural to allow very noisy points, though only rarely. This is quantified by a noise model introduced by [MT99] and [Tsy04], now known as Tsybakov noise. For learning general concept classes, [MN06] gave the general upper and lower bounds for error guarantees under Tsybakov noise. However, their upper and lower bounds differ by a logarithmic factor. Resolving this gap has remained a well-known open question for the past twenty years. In this work, we resolve this open question by improving the upper bound to match the best known lower bound, thus establishing the optimal error guarantee for learning under Tsybakov noise. Our learning algorithm operates by adaptively partitioning the instance space into regions, roughly corresponding to different noise levels, and returning a hypothesis in the concept class satisfying a specific error constraint for each region. Our technique shares a conceptual foundation with several recent advances in non-realizable learning, such as [HLZ24] and [Han25].

Steve Hanneke, Hongao Wang, Mingyue Xu

Department of Computer Science Purdue University

Noisy-Label Learning PAC Learning Statistical Learning Theory

Ask PDF

Aug 9, 2026cs.LG

Constrained Learning with Universally Learnable Concept Classes

We study constrained statistical learning over infinite-dimensional hypothesis classes in the fully nonconvex setting, and establish universal PACC learnability of the solutions of dual algorithms: Probably Approximately Correct on Constraints, guaranteeing optimality and constraint satisfaction at once. This strengthens near-PACC results, whose feasibility residual no amount of data can remove. Optimality is caught between generalization, governed by Rademacher complexity and favoring small classes, and strong Lagrangian duality, which rests on Lyapunov convexity for vector measures and needs decomposability, a demand pulling the other way. We reconcile the two by posing the population problem over a universal RKHS

\mathcal{H}_K

, dense in a decomposable envelope, and learning over norm balls of growing radius. This yields the Tikhonov complexity

\mathfrak{T}^{\varepsilon}_{n}

, the least RKHS norm reaching an

\varepsilon

-optimal Lagrangian level set; we prove it finite, obtain exact learnability of the optimal value, and make the sample threshold explicit and polynomial in

1/\varepsilon

under a source condition. Feasibility is harder: absent convexity the Lagrangian may not attain its infimum, and dual information pins down only an averaged constraint-risk vector, not the risks of any returned predictor. We introduce the closure-realization gap

\varepsilon^\star_\infty

, an index of how well

\mathcal{H}_K

retrieves feasible solutions from dualization; it is a property of the problem, not of a modeling choice. Learnability is exact when

\varepsilon^\star_\infty=0

, in particular under dual differentiability, and near-PACC with residual exactly

\varepsilon^\star_\infty

otherwise. Finally, no distribution-free threshold exists already in the unconstrained specialization, so universality is the canonical frame for dual algorithms over large hypothesis classes.

Herlock SeyedAbolfazl Rahimi, Spyridon Pougkakiotis, Dionysis Kalogerias

1Yale University · 2King’s College London

Primal-Dual Optimization Reproducing Kernel Hilbert Spaces PAC Learning Statistical Learning Theory

Ask PDF

Aug 9, 2026cs.LG

Exact Rank and Convex Calibration Dimension Lower Bounds for the Multi-Label F1 Loss

The instance-wise

F_1

measure is a central performance measure for multi-label classification. For a problem with

s

labels, it defines a

2^s\times 2^s

loss matrix. Previous work exhibited

s^2+1

-coordinate affine and shifted low-rank representations and used them to construct quadratic-dimensional convex calibrated surrogates. We determine the exact rank. Under the convention

F_1(\varnothing,\varnothing)=1

, the

F_1

score matrix, the shifted loss matrix, and the unshifted loss matrix all have rank

s^2-s+2

, while the column-affine dimension of the loss is

s^2-s+1

. The proof factors the nonempty score matrix through subset-incidence matrices and a positive-definite Cauchy matrix. Exact rank does not, by itself, lower-bound the dimension of an arbitrary convex calibrated surrogate. We therefore analyze the Bayes geometry of

F_1

directly. We construct a distribution for which precisely all supersets of a fixed core label set are Bayes optimal, and show that the corresponding active loss columns, restricted to the witness support, have affine dimension

hn

, where

n=s-\lfloor s/3\rfloor

and

h=\lceil(s\lfloor s/3\rfloor)^{1/2}\rceil-1

. Applying the feasible-subspace lower bound for convex calibration dimension gives

\operatorname{CCdim}(L^{F_1}) \ge \left(\frac{2}{3\sqrt{3}}-o(1)\right)s^2.

Together with the quadratic upper bound, this establishes

\operatorname{CCdim}(L^{F_1})=Θ(s^2)

Mingyuan Zhang

Independent Researcher

Multi-Label Classification Model Calibration Statistical Learning Theory

Ask PDF

Aug 7, 2026math.ST

High-dimensional ridgeless least squares interpolation under spiked covariance structures

This paper investigates the asymptotic behavior of the out-of-sample prediction risk of the high-dimensional ridgeless least-squares estimator when the feature dimension

p

and the sample size

n

grow proportionally. We consider a generalized spiked population covariance model with multiple latent factors, where the number of spiked eigenvalues may remain finite or increase with

n

, and the spiked eigenvalues may be bounded or diverge at arbitrary rates. Beyond characterizing the impact of covariance spectra, we reveal a new mechanism underlying benign overfitting: the prediction behavior of ridgeless interpolation is fundamentally governed by the alignment between the regression coefficient

\boldsymbolβ

and the spiked eigenspaces of the population covariance matrix. In particular, we show that the signal energy distributed along latent spike directions determines whether interpolation leads to benign, tempered, or catastrophic overfitting. Our theoretical framework establishes sharp prediction risk limits under minimal moment conditions, requiring only finite fourth moments rather than Gaussianity. We characterize how the number, strength, and geometric structure of the spikes jointly influence the double-descent phenomenon. These results provide a unified understanding of when latent covariance structures facilitate or hinder generalization in overparameterized regression.

Zhijun Liu, Dandan Jiang

College of Sciences, Northeastern University, China. · School of Mathematics and Statistics, Xi’an Jiao Tong University, China.

Double Descent Benign Overfitting Statistical Learning Theory

Ask PDF

Aug 7, 2026cs.LG

A Rate Separation for Agnostic Direct Sums

Hanneke, Moran, and Waknine \cite{HannekeMoranWaknine2024} asked how the agnostic PAC learning curve of the direct sum

C^r

depends on the single-instance learning curve

\epsagn(n\mid C)

and on

r

. We show that the single-instance learning rate does not determine the direct-sum rate. Let

\F

be the class of the two constant binary functions and let

\G

consist of the zero function and the identity function. Both classes have agnostic learning curve of order

n^{-1/2}

Mihir More, Aritra Das, Debayan Gupta

Truth Audit Labs

PAC Learning Statistical Learning Theory

Ask PDF

Aug 7, 2026cs.LG

Multiscale Reward Hedging from Correct Demonstrations

Learning from correct demonstrations is harder than supervised learning when many answers are correct: after predicting, the learner sees one valid answer but not whether its own answer was valid, nor any reward. Existing reward-hedging guarantees consequently assume a finite reward class. We give the first horizon-free guarantee for continuous classes. The key is to hedge in one shared vote over tolerant optimality tests at every accuracy scale. A target reward has one surviving proxy per scale, and a prediction with gap above that scale doubles the proxy. This yields the simultaneous tail bound

|\{t:\ell_t>2^{-j}\}|\leq \log_2\mathcal N(\mathcal G,2^{-j-1})+j

, where

\mathcal G

is the class of optimality-gap functions. Integrating the tails gives cumulative hidden gap bounded by a metric-entropy integral, independently of the number of rounds. Polynomial entropy

(A/ε)^d

gives

O(d\log A)

total gap and a fast

O(d/m)

statistical rate. For bounded linear contextual recommendation, the result is

O(d)

regret for arbitrary compact menus. This is the first polynomial finite bound without structural restrictions on the menus, at the price of improper prediction. Although the general vote can be expensive, it is exactly polynomial-time for one-dimensional Lipschitz parameter curves. Fixed-radius rank-two recommendation takes

O(KT^2)

time for menus of size

K

. We also prove an

Ω(d)

lower bound, low-rank and bounded ReLU-network corollaries, and a robust theorem that adds only the demonstrator's cumulative suboptimality. A reproducible adaptive stress test illustrates the predicted scale adaptation. After factorization, an exact MovieLens audit runs in 1.7 CPU seconds across ten users and improves mean latent gap over both a demonstrated-rating policy and a proper online baseline. The learner uses only action demonstrations and never observes a reward or a loss.

Pahan Dewasurendra

Johns Hopkins University

Learning from Demonstration Statistical Learning Theory

Ask PDF

Aug 6, 2026cs.LG

An Optimal Agnostic PAC Algorithm

Let

H\subseteq\{-1,+1\}^X

be a class of finite VC dimension

d\ge1

. Writing

L

for the binary risk and

L^*=\min_{h\in H}L(h)

, we construct a learner achieving the statistically optimal risk bound: from an i.i.d.\ sample of size

n

, for every

0<δ\le 1/2

, with probability at least

1-δ

L(\widehat h) \le L^*+ 7\cdot10^8\left( \sqrt{\frac{L^*(d+\log(1/δ))}{n}} +\frac{d+\log(1/δ)}{n} \right).

This settles the sample complexity of agnostic PAC learning up to universal constants at every fixed

L^*

, matching the lower bounds of Devroye, Györfi, and Lugosi [A Probabilistic Theory of Pattern Recognition, Springer, 1996].

Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley

PAC Learning Statistical Learning Theory Generalization Bounds

Ask PDF

Aug 6, 2026stat.ML

Optimal Rates for Learning with Monotone Adversaries

A monotone adversary observes an i.i.d. labeled sample and appends a finite number of further examples of its choice, every one of them labeled correctly by the target hypothesis. The learner sees a uniform shuffle of the combined sample and is scored on the original distribution. Every example is correctly labeled, but the insertions depend on the clean sample, so the combined sample is not exchangeable. Larsen, Pabbaraju, and Shetty, who introduced this model, showed that empirical risk minimization attains expected error

O((d/n)\log(n/d))

for classes of VC dimension

d

, and that every known optimal learner can be pushed away from the

Θ(d/n)

rate, optimal for PAC learning. They asked whether the extra logarithm is an artifact of those particular algorithms or an inherent consequence of the lack of exchangeability. We show that this additional cost is inherent beyond VC dimension one. In the worst case over classes of VC dimension

d

and over known finite insertion budgets, the minimax expected error is

Θ(1/n)

d=1

and

Θ((d/n)\log(n/d))

for

d\geq 2

. The same rates hold with Littlestone dimension

d_{\mathrm L}

in place of

d

, so the clean online-to-batch rate

O(d_{\mathrm L}/n)

is unattainable as well. Thus, somewhat counterintuitively, adding correctly labeled examples can make learning harder by a logarithmic factor, even for classes that admit finite mistake bounds in online learning. The dimension-one upper bound is achieved by a simple improper learner whose analysis adapts the leave-one-out argument underlying the one-inclusion graph. All of our lower bounds are elementary and come from a single construction: an explicit class and prior on which two target hypothesis, which differ a point of nonnegligible mass, produce the same sample.

Anay Mehrotra

Stanford University

Minimax Estimation Statistical Learning Theory

Ask PDF

Aug 6, 2026stat.ML

Beyond Marginal Validity: Finite-Sample Guarantees for Localized Conformal Prediction

Conformal prediction endows arbitrary black-box predictors with finite-sample, distribution-free marginal coverage, yet marginal validity can hide severe covariate-specific miscalibration, while exact distribution-free conditional coverage is finite-sample unattainable. Randomly localized conformal prediction (RLCP) mitigates this gap by calibrating near the test point while preserving marginal coverage. Existing theory, however, lacks finite-sample guarantees for the realized localized set that jointly control conditional validity and oracle efficiency. We provide such guarantees. For any fixed score, under Hölder regularity of the conditional score CDF and standard density and kernel assumptions, we prove high-probability bounds, uniform over a realized localization neighbourhood, for the conditional-coverage gap and the length error relative to the oracle. The bounds decompose into an

O(h^β)

localization bias and a calibration term decreasing with calibration size, clarifying the bandwidth bias-variance tradeoff and when RLCP tracks the oracle. We also analyze data-split learned scores: when the score targets a pivotal score, as in conformalized quantile regression, uniform local guarantees decompose into fixed-score calibration and uniform score-estimation errors, showing that improved learning sharpens localized guarantees.

Anton Conrad, Rustam Isaev, Denis Belomestny +2

Laboratoire de Recherche d’EPITA, 14–16 rue Voltaire, 94276 Le Kremlin-Bicêtre CEDEX, France · Faculty of Computer Science, HSE University, 11 Pokrovsky Boulevard, Moscow 109028, Russia · Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, 1 Leninskie Gory, Building 52, Moscow 119991, Russia +2

Conformal Prediction Statistical Learning Theory

Ask PDF

Aug 5, 2026cs.LG

Variational Bounds for Perceptron Learning from Structured Data

We introduce a variational approach to a finite-temperature continuous-spin perceptron trained on a Gaussian mixture. The model allows for a broad class of concave utilities and log-concave separable prior measures on the spins. By combining the interpolation method with log-concavity and concentration estimates, we derive lower and upper minimax variational bounds for the limiting quenched pressure. Remarkably, the two bounds differ only in the order of optimization of two variational parameters, while all remaining extrema are controlled by the concave--convex structure of the variational potential. Whenever the two optimizations commute, the two bounds match and identify the solution of the model. The same potential yields the fixed-point equations as stationarity conditions and provides a unified route to the computation of the ground-state energy, training loss, and generalization error.

Francesco Camilli, Pierluigi Contucci, Federica Gerace +1

Department of Mathematics, Alma Mater Studiorum – Universit`a di Bologna, Piazza di Porta San Donato 5, 40126 Bologna, Italy

Statistical Physics of Learning Statistical Learning Theory Generalization Bounds

Ask PDF

Aug 5, 2026cs.LG

The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

We study distributionally robust PAC learning for the

0

1

-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order

k>1

and radius

ρ\geq 0

. For hypothesis classes with VC dimension

d

, we establish realizable and agnostic sample-complexity bounds tight up to constant and logarithmic factors, respectively; ordinary empirical risk minimization attains both rates up to logarithmic factors. For target accuracy

\varepsilon\in(0,1)

and confidence

δ\in(0,1)

, their respective orders are

\max\!\left\{\frac{1}{\varepsilon}, \frac{ρ^{\frac 1{k-1}}}{\varepsilon^{k_\star}} \right\}\cdot(d+\log δ^{-1}) \qquad\text{and}\qquad \max\!\left\{\frac{1}{\varepsilon^2}, \frac{ρ^{\frac1{k-1}}}{\varepsilon^{k_\star\vee 2}} \right\}\cdot(d+\log δ^{-1}),

where

k_\star={k}/{(k-1)}

. For every fixed

ρ>0

, robustness changes the realizable

\varepsilon

-dependence from

\varepsilon^{-1}

\varepsilon^{-k_\star}

\varepsilon\downarrow0

. In the agnostic case, for

1<k<2

, robustness changes the

\varepsilon

-dependence from

\varepsilon^{-2}

\varepsilon^{-k_\star}

, whereas for

k\geq2

the exponent remains the classical

2

, with nontrivial

ρ

-dependence. Building on the known scalar reduction of robust

0

1

risk to ordinary classification error, our analysis reveals a scale-sensitive interaction between the statistical estimation of classification error and its amplification by robustness, sharply explaining the transition in the agnostic rate. We extend the previously studied

χ^2

-divergence case to every Cressie--Read order

k>1

, close its upper--lower gaps, and recover standard PAC learning rates as

ρ\to0

, unlike previous bounds that fail to interpolate correctly in this limit.

Elad Aigner-Horev, Daniel Rosenberg, Roi Weiss

School of Computer Science and AI Ariel University 40800 Ariel, Israel

Sample Complexity Distributionally Robust Optimization PAC Learning Statistical Learning Theory

Ask PDF

Aug 4, 2026cs.LG

Sample Complexity of Multicalibration for Multilevel Properties

Calibration requires a predictor to be unbiased after conditioning on its own predictions. Multicalibration asks for this guarantee simultaneously across a collection of groups. Many prediction tasks ask for several related features of the same conditional outcome distribution: variance is defined relative to the mean, skewness relative to both mean and variance, and conditional value at risk relative to a quantile. We study multicalibration for a sequence of

k

properties in which each property is identifiable once the preceding properties are fixed. This framework includes Bayes pairs but does not require the properties to arise from a single loss. For every fixed

k\ge2

, we establish matching upper and lower sample-complexity bounds up to logarithmic factors under regularity conditions. Even with only polylogarithmically many binary groups, achieving multicalibration error

\varepsilon

requires

\widetildeΩ(\varepsilon^{-(k+2)})

samples. Conversely, for any finite group family

\mathcal G

, we give a randomized learner using

O(\varepsilon^{-(k+2)}+\varepsilon^{-2}\log|\mathcal G|)

samples. Thus the sample complexity is

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

for polynomial-size group families. We instantiate the theory for three canonical examples.

Jiuyao Lu, Krishnakumar Balasubramanian, Aleksandr Podkopaev +1

Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · 2Amazon · Department of Statistics, University of California, Davis

Sample Complexity Model Calibration Statistical Learning Theory Multicalibration

Ask PDF

Aug 4, 2026cs.LG

To Describe or Construct Statistical Learning Models Using the Category-theoretical Language

Statistical learning is a fascinating field that has long been the mainstream of machine learning/artificial intelligence. A large number of results have been produced which can be widely applied to real-world problems. It also leads to many research topics and also stimulates new research. This report summarizes some classical statistical learning models and well-known algorithms, especially for amateurs, and provides a category-theoretic perspective on understanding statistical learning models. The aim is to attract researchers from other fields, including basic mathematics, to participate in the research related to statistical learning.

Congwei Song

Statistical Learning Theory

Ask PDF

Aug 4, 2026cs.LG

Benign interpolation and Occam's razor

Contemporary deep learning methods generalize well even when they fit their training data perfectly, a phenomenon known as benign interpolation. This phenomenon cannot be accounted for by classical statistical learning theory and has prompted a range of attempted new explanations in the statistics and machine learning literature. A common feature of these new proposals is an appeal to a simplicity preference among interpolating models, often presented as a form of Occam's razor. We clarify this debate for a philosophical audience and argue that this new appeal to simplicity creates an explanatory gap. The classical theory offers theorems which connect the simplicity of model classes to good generalization, thus underwriting methodological simplicity norms. The new accounts instead appeal to properties of individual models, which they interpret as a kind of simplicity. Lacking a provable connection to generalization, it is the name "simplicity" that does the work a theorem used to do, making a substantive and unargued assumption look like the application of a familiar methodological principle.

Tom F. Sterkenburg, Daniel A. Herrmann, Jan-Willem Romeijn

Benign Overfitting Inductive Bias Statistical Learning Theory

Ask PDF

Aug 3, 2026cs.AI

Self-Certification of Representation Adequacy: Sequential Certification at Minimum Task Loss

Agents that act on a compressed representation of their history face a structural risk: if the representation aliases histories with different optimal actions, no rule measurable with respect to the representation can avoid an irreducible per-round loss, and the agent may be unable to detect this from its own transcript. This paper develops a four-layer theory of self-certification of representation adequacy. The static layer defines decision-theoretic adequacy through a Bayes-risk grouping identity and prices a one-shot external verification by an exact total-variation threshold. The sequential layer poses certification as an optimal-stopping problem in the currency of task loss: we define an environment-wise certification complexity constant through a covering linear program, prove an information-task-loss lower bound for every delta-correct strategy, and give a Certification Track-and-Stop policy whose cost matches the bound asymptotically. A final boundary layer gives an explicit kernel-switching example and identifies the open theorem needed to cover policy switching or representation repair; it does not claim that the fixed-kernel guarantees extend to representation revision. The proofs of the two main theorems are given in full in the appendices.

Zijie Huang

Independent Researcher

State Representation Learning Statistical Learning Theory

Ask PDF

Aug 3, 2026cs.LG

Sharp Root Anti-Concentration via Projective Incidence and Ordered Root Laws

This paper answers the one-dimensional local root anti-concentration questions posed by Balcan, Pegden, and Sharma in the context of online optimization of piecewise-Lipschitz functions. For a homogeneous feature curve and coefficients whose density relative to the uniform law on a symmetric convex body

K

is bounded by

A

, we show that the worst-case interval-hitting constant equals

A

times a section-averaged projective incidence speed. For cube-supported coefficients, this speed is equivalent, up to universal constants, to the projective Lipschitz constant. This yields a sharp, dimension-free characterization and removes the previous

\sqrt N

loss. For monic degree-

d

polynomials under arbitrary coefficient laws, we prove that the interval-hitting constant is finite if and only if the ordered real-root laws have bounded densities, with a factor-

d

comparison that is sharp. Conditional and joint coefficient-space area formulas, together with a two-chart certificate, make this criterion verifiable for dependent and singular coefficient laws. We also give two graph-learning applications that complete the transition-to-regret chain. A cost-sensitive Gaussian-RBF harmonic classifier uses the projective incidence theorem and achieves expected regret

\widetilde O((An^2D e^{BD}/\ell+1)\sqrt T)

. A common-offset polynomial-kernel model uses rigid translation of the ordered roots and achieves

\widetilde O((qn^2κ+1)\sqrt T)

regret, even when the induced coefficient law is singular in the ambient coefficient space.

Zijun Wang, Yuchen Miao, Yifan Hu +1

Northeastern University, China · Beijing Jiaotong University, China · Xiangtan University, China

Online Convex Optimization Statistical Learning Theory

Ask PDF

Aug 3, 2026stat.ML

The Label Defines the Timescale: Trait-State Limits of Temporal-Aggregate Learning

Machine-learning benchmarks often pair a label that aggregates a long temporal horizon with input observed through one or a few short windows. Their apparent performance ceiling may therefore be an acquisition-protocol ceiling rather than a model-capacity ceiling. We study labels of the form

Θ_{g,T}=T^{-1}\int_0^T g\{Z(t)\}\,\mathrm{d}t

when the latent Gaussian process contains both a stable individual trait and a correlated within-individual state. An exact protocol-conditioned Bayes-risk identity provides a common tool. First, we decompose label variance into an

O(1)

trait component and an

O(T^{-1})

state component, explaining why a snapshot can retain cross-sectional predictability while poorly tracking within-person change. Second, we derive task-dependent effective temporal spans: mean labels depend on the ordinary correlation time, whereas occupation-time labels depend on an entire spectrum of higher-order correlation times. Third, state-driven occupation-label variance is maximal when the stable trait lies at the threshold; window efficiency decays much more slowly away from that boundary. Under an equal segment budget, exact risks and Monte Carlo experiments show that repeated segments at one time rapidly saturate, whereas temporally dispersed observations continue to increase state explainability. The trait ceiling uses quantities available from ordinary test-retest data; only the state ceiling requires short-lag temporal calibration. The results distinguish architectural limits from protocol limits and show that the label, rather than duration or segment count alone, defines the relevant timescale.

Xizhe Zhang

Latent Dynamics Modeling State Tracking Statistical Learning Theory

Ask PDF

Aug 2, 2026cs.LG

Statistical Mechanics of Learning on Product Wasserstein Manifolds

Normally the statistical mechanics of learning treats constraints on weight distributions as restrictions that shrink the space of possible solutions. Therefore, it reduces model capacity. In this paper we would like to take a contrary approach, which, however, is based on the earlier work on distribution-constrained perceptrons. Rather than treating a prescribed weight distribution as a mere restriction, we propose that it defines the intrinsic geometry upon which learning naturally unfolds. We formulate both deep neural networks and variational quantum circuits as gradient flows on a product of Wasserstein manifolds -- one classical Wasserstein space for each layer and one quantum Wasserstein space for the circuit parameters. Within this geometry, the capacity reduction, which was previously associated with distributional constraints, appears as the metric structure of the constraint manifold itself. We develop a hierarchical mean-field description for deep networks, extend the framework to the quantum setting using the quantum Wasserstein distance of order 1, and introduce two such practical algorithms, Hierarchical DisCo-SGD and Quantum DisCo, that follow approximate geodesics on the manifold of the product itself. Experiments on teacher-student problems, standard image classification tasks, and small variational quantum classifiers show that respecting these distributional geometries improves generalization, stabilizes training, and reduces the severity of barren plateaus compared with unconstrained and purely norm-based baselines. This approach firstly reframes structural constraints as geometric priors and suggests a route for incorporating biological, spectral, or hardware-derived distributional information into both learning systems, viz., classical and quantum learning.

Srinivasa Rao P Vangmayi P Reddy

Curlvee Technolabs, India; Former Scientist, C-DAC.

Statistical Physics of Learning Wasserstein Gradient Flows Variational Quantum Circuits Statistical Learning Theory

Ask PDF

Aug 2, 2026cs.DS

Active Regression for Single-Index Models with Unknown Link Functions

This paper studies active regression for single-index models under general

\ell_p

-loss with an unknown

1

-Lipschitz link function

f

, formulated as

\min_{f,x} \|f(Ax)-b\|_p^p

with full access to

A

but coordinate-query access to

b

. Prior work established upper bounds for known link functions for all

p\geq 1

and for unknown link functions only in the

p=2

case, together with lower bounds for

p\leq 2

. This work addresses the more challenging setting of unknown link functions and general

p \geq 1

. A non-adaptive sampling algorithm is presented that achieves a

(1+ε)

-approximation using

O(d^{p/2\vee 1}/ε^{p\vee 2}\operatorname{poly}\log(n/ε))

queries. Nearly tight lower bounds are also established for

p>2

. These results close much of the remaining gap in active

\ell_p

-regression for single-index models.

Chansophea Wathanak In, Yi Li, Wai Ming Tai +1

School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore · Independent Researcher · John Hopcroft Center for Computer Science, Shanghai Jiao Tong University, China

Single-Index Models Active Learning Statistical Learning Theory

Ask PDF

Aug 2, 2026cs.LG

Factorized AdaBoost.MH Achieves the Same Convergence Rate as AdaBoost.MH

{AdaBoost.MH} reduces multi-class classification to a collection of binary subproblems and enjoys the classical boosting-type convergence guarantee under a weak learning condition. A more structured variant, Factorized {AdaBoost.MH}, uses base classifiers of the form

\mathbf{h}(x)=α\mathbf{v} \bm{\varphi}(x)

, where a single binary classifier

\bm{\varphi}

is shared across all classes and the label dependence is carried by a vote vector

\mathbf{v} \in\{\pm1\}^K

. This factorization is algorithmically attractive and achieves better performance in practice, but its convergence depends on whether one can always choose a vote vector with sufficiently large induced binary weight mass. Previous work resolved this question with a lower bound

\max\{1/n,1/\sqrt{2K}\}

, which still leaves a dimension-dependent slowdown relative to the original {AdaBoost.MH} analysis. In this paper, we sharpen this combinatorial step. For the minimax quantity

\mathfrak{W}_{n,K}

governing the factorized edge, we prove

\mathfrak{W}_{n,K} = C_{\min\{n+1,K\}}

, where

C_q=1

for

q=1

C_q=q/(3q-4)

for even

q\ge2

, and

C_q=(q+1)/(3q-1)

for odd

q\ge2

. Since

C_q\downarrow 1/3

, our bounds show that

\mathfrak{W}_{n,K}=Θ(1)

uniformly over

n

and

K

. Consequently, Factorized {AdaBoost.MH} achieves the same boosting-type convergence rate as {AdaBoost.MH} up to a universal constant factor, removing the previously suggested additional dependence on

n

K

in the number of boosting rounds.

Xin Zou, Jingyuan Xu

Ensemble Learning Multiclass Classification Classification Statistical Learning Theory

Ask PDF

Aug 2, 2026cs.LG

The Fourth Quadrant: A Stylized View of Benign Misfitting

Training error is what we can observe on a training set; test error is the quantity we actually care about. We study linear regression with squared-error in a deterministic

(d+1)

-dimensional single-spike model. Each stylized training vector has the same informative spike coordinate, of amplitude

\sqrtγ

with

γ>1

. The remaining directions are nuisance, and the nuisance components of distinct training vectors all have equal norm and are mutually orthogonal. The training labels are all

1

. Fresh test points are drawn from

\vec{x}_{\rm test} \sim \mathcal{N}(\vec{0},\operatorname{diag}(γ,1,\ldots,1))

, with the noise-free test labels being the normalized spike coordinate

x_{\rm test}[1]/\sqrtγ

. We focus on linear predictors in the span of the training vectors, the class naturally reached by zero-initialized linear gradient methods. We exhibit a range of training-set sizes

n

in which every span predictor that generalizes well must fit the training data \emph{worse} than the zero predictor. We call this regime \emph{benign misfitting}, or the fourth quadrant. The best span predictor begins to generalize when

n\gg d/γ^2

, while interpolation does not generalize until the later threshold

n\gg d/γ

. In the window

d/γ^2 \ll n \ll d/γ

, useful prediction within the linear span lies beyond interpolation: predictions on the training points overshoot the labels. We show that one-pass stochastic gradient descent (SGD), with a large constant learning rate, reaches small test error throughout this window---matching the best span predictor up to a logarithmic factor. We also verify directly that it indeed has \emph{large} empirical training error (despite the descent premise in its name). Finally, we show that the unavoidable nuisance component responsible for the training misfit also controls the predictor's adversarial sensitivity.

Gireeja Ranade, Anant Sahai

University of California, Berkeley

Benign Overfitting Linear Regression Statistical Learning Theory

Ask PDF

Aug 2, 2026cs.LG

Hierarchical Solomonoff Induction: An Unbounded Machine Learning Model

Solomonoff Induction, or SolInd, provides an ideal unbounded model of a priori sequence prediction but cannot naturally describe extrapolation from a given training dataset, as performed by Large Language Models. We apply de Finetti's theorem on exchangeable distributions to SolInd to produce what we call Hierarchical Solomonoff Induction, or HSI, which maintains a hyperprior over all Solomonoff priors that can be conditioned on previously observed sequences. We extend Wood et al.'s proof that universal mixtures of semimeasures are equivalent to SolInd to show that universal mixtures of these mixtures are also equivalent, proving that HSI=SolInd. We also prove that HSI's excess error on any distribution, compared to its true generator, is bounded by that generator's complexity in the hyperprior. This result is directly comparable to SolInd's prediction error being bounded by the Kolmogorov complexity of the sequence being predicted, and forces HSI's average excess error to converge to 0 as a dataset grows, leading to optimal prediction in the limit. We claim that HSI is an ideal unbounded model of sequence prediction given a dataset in the same way that SolInd is ideal over individual sequences.

Nathan Young

Strong AI Lab, University of Auckland

Hierarchical Bayesian Modeling Statistical Learning Theory Sequence Modeling

Ask PDF

Jul 31, 2026cs.LG

Who Wins Where? Conformal Model Comparison for Local Superiority

Standard model comparison is global, aggregating losses across the covariate space to declare a single winner. This can obscure heterogeneous performance, where different models are preferable in different regions. We introduce conformalized local model comparison, a split-sample framework for constructing calibrated local best-model maps. Given a model comparison score, such as the difference between two squared losses, the method uses three disjoint splits to fit competing models, estimate local centers and scales from out-of-sample scores, and conformally calibrate residual uncertainty. At a target point, the procedure declares a local winner only when a one-sided conformal bound excludes a tie, with the score's sign determining the favored model. We prove finite-sample marginal control for one-sided erroneous declarations on the realized future comparison score, establish pointwise consistency of the localized mean-score estimator away from tie boundaries, show that aggregate comparison can disagree sharply with the prevalence of local superiority, and derive a squared-loss bias--variance decomposition that clarifies how model structure affects local wins. Synthetic and real-data experiments show that the method recovers heterogeneous winner regions, abstains under uncertainty, and yields higher conditional gain than global selection.

Yi Zhou, Baishi Li, Xuan Yao +1

Asian Institute of Digital Finance, National University of Singapore

Model Selection Selective Prediction Conformal Prediction Statistical Learning Theory

Ask PDF

Jul 30, 2026cs.LG

Fast Rates for Swap-Agnostic Learning of Proper Losses

Swap-agnostic learning strengthens classical agnostic learning by allowing the comparator to select a different hypothesis on each level set of the learner's predictions. This benchmark captures prediction-dependent postprocessing, but appears to require solving a separate agnostic-learning problem for every possible prediction value. We show that, for proper losses, these prediction-level comparisons can instead be controlled jointly. Our main result is an offline swap-agnostic learner for any fixed proper loss. For a finite hypothesis class

H

and any fixed smooth proper loss, the excess risk from

m

i.i.d. samples is

\widetilde{O}((\log |H|/m)^{2/3})

, with a corresponding online swap-regret bound of

\widetilde{O}(T^{1/3}(\log |H|)^{2/3})

. We also give algorithms whose predictions are simultaneously swap-agnostic for entire families of losses. For all proper losses bounded in

[-1,1]

, we obtain online and offline rates of

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

and

\widetilde{O}(\sqrt{\log |H|/m})

, respectively. For convex,

1

-Lipschitz proper losses, these rates improve to

\widetilde{O}(T^{1/3}(\log |H|)^{2/3})

online and

\widetilde{O}((\log |H|/m)^{2/3})

offline. These bounds are tight up to logarithmic factors and improve upon the

\widetilde{O}(T^{2/3}(\log |H|)^{1/3})

rate implied by the swap-omniprediction guarantee of Luo et al. (2025). Our main technical contribution is a reduction from swap-agnostic learning to a second-order form of multicalibration, obtained via Blackwell approachability with a Bernstein-style variance correction.

Princewill Okoroafor

Harvard University

Statistical Learning Theory Online Learning Multicalibration

Ask PDF

Jul 30, 2026stat.ML

The Noise Premium in Adversarial Training for Kernel Regression

Adversarial training can improve the robustness of predictive models to bounded perturbations, often at the cost of statistical efficiency. We study this trade-off in kernel regression over a reproducing kernel Hilbert space (RKHS). It is shown that, under squared loss, adversarial training in RKHS introduces a term involving the product of the function norm with the mean absolute value of the response noise, which we call the \textit{noise premium}. Our analysis shows that the noise premium makes the prediction error of adversarial training converge strictly more slowly than the nonparametric minimax benchmark even after balancing approximation and estimation errors. Moreover, for a fixed perturbation budget, once the budget exceeds a certain threshold, the solution to adversarial training collapses to the zero function. To mitigate these effects of the noise premium, we propose noise-debiased adversarial training. The resulting noise-debiased estimator can attain the minimax optimal rate up to a logarithmic factor for the prediction error, raises the collapse threshold, and admits an explicit bound on the increase in adversarial loss. Numerical experiments on synthetic and real data support the theoretical findings and validate the effectiveness of the proposed noise-debiased method.

Yiling Xie, Xiaoming Huo

Department of Decision Analytics and Operations, City University of Hong Kong · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology

Adversarial Training Kernel Regression Nonparametric Regression Minimax Estimation Statistical Learning Theory

Ask PDF

Jul 30, 2026stat.ML

Error Analysis of Neural-Network-Based Engression

Engression (Shen and Meinshausen, 2024) learns a conditional distribution by fitting a generative model

Y = f(X,\varepsilon)

under the energy score, a strictly proper scoring rule. We provide a theoretical error analysis of engression implemented with deep neural networks. We decompose the excess risk into three components: the approximation error, the stochastic error, and the Monte Carlo error. Based on this decomposition, we establish convergence rates under the assumption that the target conditional generator admits a compositional smoothness structure.

Juntong Chen, Zijian Guo, Xinwei Shen

School of Mathematical Sciences, Xiamen University · Center for Data Science, Zhejiang University · Department of Statistics, University of Washington

Conditional Distribution Estimation Neural Network Approximation Theory Statistical Learning Theory

Ask PDF

Jul 30, 2026cs.LG

Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection

Low-Rank Adaptation (LoRA) has become the standard mechanism for fine-tuning large pretrained models, yet its statistical properties remain only partially understood. Existing generalization results provide upper bounds of the form O~(sqrt(rd/n)) or O~(rd/n), but a matching lower bound is missing, and the question of how to choose the LoRA rank r has no formal answer. Both gaps are closed here. A local Rademacher argument establishes an upper bound of O~(rd/n) on the excess risk of the empirical risk minimizer over rank-r LoRA, whenever the target adaptation has rank at most r. A matching minimax lower bound of Omega(rd/n) is then proved via a Fano-type packing of the rank-r subspace of R^{d x d}; the bound applies to any estimator whose output lies in the rank-r LoRA class. Combining the two yields a rank-selection dichotomy. For the constrained empirical risk minimizer, the optimal rank equals the intrinsic rank r*, and over-ranking strictly hurts. For adaptive estimators of the nuclear-norm-then-truncate type, over-ranking is harmless and the rate saturates at Theta~(r* d / n) regardless of r. Taken together, the three results characterize the statistical complexity of LoRA fine-tuning within the well-specified locally quadratic regime, and identify the empirically observed over-parameterization penalty as a property of unregularized empirical risk minimization rather than of the LoRA class itself. Predictions of the theory are verified on a synthetic trace-regression benchmark and on real LoRA fine-tuning across three (model, task) configurations covering DistilBERT and RoBERTa on SST-2 and MRPC. All configurations exhibit the predicted U-shape in validation loss, with two showing statistically significant loss inflation at large ranks (paired permutation p = 0.016).

Arunan J

Independent Researcher, Chennai, India.

Sample Complexity Low-Rank Adaptation Minimax Estimation Statistical Learning Theory Empirical Risk Minimization

Ask PDF

Jul 29, 2026stat.ML

An analysis of binary isotonic regression: degrees of freedom and implications for calibration

Isotonic regression is a canonical tool for estimating monotone functions and calibrating probabilistic predictors. We provide a fully sharp finite-sample characterization of its worst-case degrees of freedom on binary samples. Specifically, we identify the binary sequences that maximize the number of distinct fitted values produced by isotonic regression. We develop a sharp bound on the degrees of freedom with a leading term of

\frac{3}{(4π^2)^{1/3}} n^{2/3}

using analytic number theory, improving on previous bounds. We then apply this result to calibration. Calibration is a central requirement for probabilistic prediction, and isotonic regression is a widely used post-processing method for improving calibration. Building on deterministic degrees-of-freedom bounds, we derive, to our knowledge, the first nontrivial distribution-free guarantee on the Expected Calibration Error (ECE) of isotonic regression. This ECE bound is fully model-free and distribution-free, only assuming

Y \in \{0,1\}

Raphael Rossellini, Rina Foygel Barber, Zhimei Ren +1

Department of Statistics, University of Chicago · Department of Statistics and Data Science, University of Pennsylvania · Department of Statistics, University of Michigan

Probability Calibration Model Calibration Statistical Learning Theory Isotonic Regression

Ask PDF

Jul 29, 2026stat.ML

PIKS: Universal Physics-Informed Kernel Methods

Physics-informed machine learning incorporates physical principles --often expressed via differential operators-- into data-driven models. While physics-informed neural networks (PINNs) dominate empirical applications, the complexity of neural network architectures and optimization landscapes hinders the development of a corresponding learning theory. In turn, kernel methods offer an appealing alternative with closed-form solutions and analytical tractability, yet existing guarantees primarily cover the well-specified setting where the target belongs to the native Reproducing Kernel Hilbert Space (RKHS). This imposes unrealistic regularity assumptions that physical targets often fail to satisfy. In this paper, we introduce and analyze Physics-Informed Kernel methodS (PIKS). We establish the universal consistency of PIKS for linear differential constraints, proving that for universal kernels (such as Gaussian or Matérn), the estimator asymptotically learns the target while satisfying physical constraints. We further derive finite-sample bounds under suitable source conditions. Our analysis is based on extending classical operator-theoretic analysis of kernel methods to physics-informed machine learning. Numerical experiments demonstrate that PIKS can be competitive with PINNs and traditional finite element methods.

Joachim Bona-Pellissier, Giacomo Meanti, Matteo Santacesaria +1

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

Kernel Methods Physics-Informed ML Statistical Learning Theory

Ask PDF

Momentum

Related topics

Latest papers 395