Statistical Learning Theory

Follow this topic Ask about this topic

Momentum

34 papers in the last four weeks, up 127% on the four weeks before. 0.3% of all new papers.

Jul 13Week of Sep 28

Latest papers 395

May 8, 2026cs.LG

The Geometric Structure of Models Learning Sparse Data

The manifold hypothesis (MH) is often used to explain how machine learning can overcome the curse of dimensionality. However, the MH is only applicable in regimes where the training data provides a sufficiently dense sample of the underlying low-dimensional data manifold, or where such a low-dimensional manifold is conceivably present. We describe the regimes where the MH is not applicable as sparse. In this paper, we demonstrate that models succeed in the sparse regime by exploiting a highly structured local geometry, a property we formalize as normal alignment. We prove that normal-aligned classifiers -- whose input-output Jacobians are rank-one and align perfectly with the training data -- minimize the training objective under norm constraints and achieve maximal local robustness under a non-zero Jacobian constraint. For continuous piecewise-affine deep networks, normal alignment manifests geometrically as centroid alignment within the network's induced power diagram partition and results from the feature-learning regime. Motivated by these theoretical insights, we introduce GrokAlign, a regularization strategy that actively induces normal alignment. We demonstrate that GrokAlign significantly accelerates the training dynamics of deep networks relevant to the grokking phenomenon. Furthermore, we apply the principle of normal alignment to Recursive Feature Machines (RFMs) to introduce Recursive Feature Alignment Machines (RFAMs). We show that RFAMs exhibit greater adversarial robustness compared to RFMs when trained on tabular data.

Thomas Walker, T. Mitchell Roddenberry, Ahmed Imtiaz Humayun +2

Rice University · Rice University† · Now at Google Research +1

Neural Representation Geometry Statistical Learning Theory Data-Efficient Learning

May 8, 2026stat.ML

A Note on Non-Negative $L_1$ -Approximating Polynomials

L_1

-Approximating polynomials, i.e., polynomials that approximate indicator functions in

L_1

-norm under certain distributions, are widely used in computational learning theory. We study the existence of \textit{non-negative}

L_1

-approximating polynomials with respect to Gaussian distributions. This is a stronger requirement than

L_1

-approximation but weaker than sandwiching polynomials (which themselves have many applications). These non-negative approximating polynomials have recently found uses in smoothed learning from positive-only examples. In this short note, we prove that every class of sets with Gaussian surface area (GSA) at most

Γ

under the standard Gaussian admits degree-

k

non-negative polynomials that

\eps

-approximate its indicator functions in

L_1

-norm, for

k=\tilde{O}(Γ^2/\varepsilon^2)

. Equivalently, finite GSA implies

L_1

-approximation with the stronger pointwise guarantee that the approximating polynomial has range contained in

[0,\infty)

. Up to a constant-factor, this matches the degree of the best currently known Gaussian

L_1

-approximation degree bound without the non-negativity constraint.

Jane H. Lee, Anay Mehrotra, Manolis Zampetakis

Yale University · Stanford University

Statistical Learning Theory

May 8, 2026cs.LG

Flatness and Gradient Alignment Are Both Necessary: Spectral-Aware Gradient-Aligned Exploration for Multi-Distribution Learning

Sharpness-aware and gradient-alignment methods have been shown to improve generalization, however each family of methods targets a single geometric property of the loss landscape, while ignoring the other. In this paper, we show that this omission is structurally unavoidable and that both flatness and gradient alignment should be considered in multi-distribution learning settings. Specifically, we derive an excess-risk decomposition that yields two additive leading-order terms: (i) an alignment term, controlled by the trace of

\bar{H}^{-1}Σ_g

and (ii) a curvature term, controlled by

\bar{H}

, where

\bar{H}

is the average Hessian and

Σ_g

is the covariance of the gradient across distributions. Notably,

\bar{H}

appears inverted in one and non-inverted in the other. We further show, via a counterexample, that neither quantity bounds the other in general, so no algorithm targeting only one term can guarantee low excess risk. Motivated by this decomposition, we propose SAGE (Spectral-Aware Gradient-Aligned Exploration) that targets both terms. The curvature component replaces SAM's gradient-scaled perturbation with the polar factor of each layer's gradient matrix, computed via Newton-Schulz iteration, so that the ascent step probes all directions with similar magnitude. On the other hand, the alignment component injects isotropic noise at the descent step, the magnitude of which scales with cross-distribution gradient disagreement. Experiments on five domain-generalization and two multi-task learning benchmarks show that the proposed method establishes a new state-of-the-art on DomainBed and acts as a general-purpose improvement to base MTL solvers, remaining competitive with, or even surpassing, state-of-the-art methods.

Aristotelis Ballas, Christos Diou

Department of Informatics and Telematics Harokopio University of Athens Omirou 9, Athens, Greece

Sharpness-Aware Minimization Multi-Task Learning Cross-Domain Generalization Nonconvex Optimization Statistical Learning Theory Gradient Alignment

May 8, 2026cs.LG

The Minimax Rate of Perturbed Second-Order Calibration

Second-order calibration error quantifies how closely a higher-order predictor's epistemic-uncertainty estimate matches the conditional variance of the label probability on its level sets. We characterize the minimax rate of estimating the second-order calibration error for binary classification in the regime where a small perturbation is applied to the classifier outputs. Our procedure is simple: add independent bandwidth-

h

sech noise to the score coordinates, then regress

Y^{(1)}

and

Y^{(1)}Y^{(2)}

on the perturbed score using low-degree polynomials. Crucially, the sech perturbation makes the calibration functions analytic in a suitable strip. The resulting estimator has error

O_h(\log^{3/2}n/\sqrt n)

, with explicit constants. In the same setting, a matching

Ω(1/\sqrt{n})

lower bound establishes minimax optimality up to logarithmic factors. As a corollary, we give a finite-sample guarantee for perturbed second-order Platt scaling, yielding a post-hoc procedure that recalibrates both the mean prediction and the epistemic-variance estimate of the perturbed higher-order predictor. Along the way, we give an explicit two-moment formulation of second-order calibration error and relate it quantitatively to the bucketed formulation of Ahdritz et al. [2025]. Our experiments confirm the predicted rate and the quality of the recalibrated uncertainties.

Kamil Ciosek, Banafsheh Rafiee, Sina Ghiassian +1

Spotify

Post-Hoc Calibration Minimax Estimation Model Calibration Binary Classification Statistical Learning Theory Uncertainty Calibration+1

May 8, 2026stat.ML

A Refined Generalization Analysis for Extreme Multi-class Supervised Contrastive Representation Learning

Contrastive Representation Learning (CRL) has achieved strong empirical success in multiple machine learning disciplines, yet its theoretical sample complexity remains poorly understood. Existing analyses usually assume that input tuples are identically and independently distributed, an assumption violated in most practical settings where contrastive tuples are constructed from a finite pool of labeled data, inducing dependencies among tuples. While one recent work analyzed this learning setting using U-Statistics to estimate the population risk, the techniques used therein require the risk of each class to concentrate uniformly, making excess risk bounds scale in the order of

ρ_{\min}^{-{1}/{2}}

where

ρ_{\min}

denotes the probability of the rarest class. Such a dependency can be overly pessimistic in the extreme multiclass settings where there are many tail classes which contribute minimally to the overall population risk. Our contributions are two-fold. Firstly, we improve upon the previous work and prove a bound with a sample complexity of the same order as the number of classes

R

, regardless of the distribution over classes. Furthermore, we formulate a different estimator that captures the concentration of the risk \textit{across classes}, enabling sharper bounds in extreme multi-class learning scenarios, especially where class distributions are long-tailed. Under mild assumptions on the class distributions, the resulting sample complexity is

\mathcal{O}(k)

where

k

is the number of samples per tuple.

Nong Minh Hieu, Antoine Ledent

School of Computing and Information Systems, Singapore Management University.

Class-Imbalanced Learning Contrastive Learning Multiclass Classification Supervised Contrastive Learning Statistical Learning Theory

May 8, 2026cs.LG

A Qualitative Test-Risk Mechanism for Scaling Behavior in Normalized Residual Networks

The scaling behavior, in which test performance often improves as model size and data increase, is a central empirical phenomenon in modern deep learning, yet its theoretical basis remains incomplete. In this paper, we study depth expansion in normalized residual networks: starting from a trained model in an old hypothesis class, we insert a new residual block at an intermediate layer and ask when such an expansion can yield a provable improvement in test risk. We develop a unified framework that decomposes this question into representational gain, optimization gain, and generalization transfer. First, under a first-order descent condition near zero initialization, we prove that the expanded hypothesis class contains an auxiliary jumpboard model with strictly smaller population risk than the original model. Second, under norm control tailored to post-normalized residual architectures, we establish a norm-based Rademacher complexity bound for the expanded model class. These ingredients lead to two complementary test-risk guarantees: one route passes through population risk and is tighter when a positive population margin is available, while the other works directly at the train/test level, avoids Hoeffding transfer, and is more robust in degenerate regimes. Together, these results provide a theorem-driven mechanism under which residual depth expansion can improve test performance in normalized residual networks. More broadly, they suggest that scaling is inherently joint: depth creates new improving directions, width enhances the finite-sample observability of weak signals, and data determines whether the statistical cost of expansion can be controlled.

Daning Cheng, Zeyu Liu, Jun Sun +4

ICT · Zhejiang Lab · JD corporation +1

Neural Network Generalization Residual Learning Neural Scaling Laws Statistical Learning Theory

May 8, 2026cs.LG

Risk-Consistent Multiclass Learning from Random Label-Subset Membership Queries

Obtaining accurate class labels is often costly or unreliable, and may also be limited by privacy or other practical conditions. Compared with asking an annotator to provide the exact class, it is often easier to ask whether the true label belongs to a certain label subset. This query-response form defines a distinct weak-supervision mechanism: weak supervision information is generated through feedback on a label subset. Although weakly supervised learning has studied many learning frameworks, most existing work starts from established weak label objects. A systematic characterization is still lacking for weakly supervised learning generated directly by such query response observations. This paper proposes a multiclass learn ing framework under random label-subset queries. We model the data-generating distribution of query-response observations and derive an unbiased estimator of the target risk under the empirical risk minimization (ERM) framework. To address negative empirical risk and the associated overfitting problem, we introduce corrected risk estimators based on non-negative and absolute-value corrections. Theoretical analysis establishes a conditional generalization and excess-risk bound for the unbiased estimator, and a bias-and-consistency result for the corrected risk estimator. Experiments under the matched random-query mechanism demonstrate the feasibility of direct query-response learning and the stabilization effect of risk correction.

Jiaxu Su, Junpeng Li, Changchun Hua +1

Engineering Research Center of the Ministry of Education for Intelligent Control System and Intelligent Equipment, Yanshan University, Qinhuangdao, China

Multiclass Classification Weakly Supervised Learning Classification Statistical Learning Theory Empirical Risk Minimization

May 7, 2026stat.ML

Kernel Selection is Model Selection: A Unified Complexity-Penalized Approach for MMD Two-Sample Tests

The Maximum Mean Discrepancy (MMD) is a cornerstone statistic for nonparametric two-sample testing, but its test power is dictated entirely by the chosen kernel. Because any fixed kernel inherently fails to distinguish certain distributions, the kernel must be dynamically optimized. However, data-driven optimization violates the foundational i.i.d. assumption, forcing a strict trade-off in existing frameworks. Ratio criteria ignore this dependence, inducing overfitting and variance collapse on rich kernel classes. Conversely, aggregation methods bypass the dependence using finite grids, but this strategy cannot scale to continuous search spaces like deep kernels. To break this dichotomy, we establish data-driven kernel selection as a model selection problem. We propose Complexity-Penalized MMD (CP-MMD), a criterion derived by applying the two-sample uniform concentration inequality of preceding works to the post-optimization MMD problem. The resulting penalty bounds the empirical MMD by the complexity of the kernel search space, mathematically absorbing the cost of optimization, so that CP-MMD enables direct, grid-free maximization over continuous parametric classes, including scalar bandwidths, polynomial feature bandwidths, and deep network parameters. By formally accounting for optimization complexity, we prove that CP-MMD maximizes true test power while ensuring unconditional Type-I validity. Consequently, CP-MMD enables grid-free kernel selection across linear, polynomial-feature, and deep regimes, matching or exceeding state-of-the-art test power.

Yijin Ni, Xiaoming Huo

H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332, USA

Model Selection Two-Sample Testing Maximum Mean Discrepancy Kernel Methods Statistical Learning Theory

May 7, 2026cs.LG

A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning

Autoregressive generation lies at the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an input string (prompt), the generator is applied for

M

steps, and the last generated token is taken as the final output. [Joshi et al., 2025] proposed a PAC model for studying the learnability of the input-output maps arising from this process. We develop an online analogue of this framework, focusing on the mistake bound of learning the final output induced by an unknown next-token generator. We distinguish between two forms of feedback. In the End-to-End model, after each round the learner observes only the final token produced after

M

autoregressive steps. In the Chain-of-Thought model, the learner is additionally shown the entire

M

-step trajectory. Our goal is to understand how the optimal mistake bound depends on the generation horizon

M

, and to what extent observing intermediate tokens can reduce this dependence. Our main results show that the online theory of autoregressive learning exhibits a qualitative picture analogous to the statistical one found by [Hanneke et al., 2026], but with a different scale of dependence on the generation horizon. In the End-to-End model, we prove a taxonomy of possible mistake-bound growth rates in the generation horizon

M

: essentially any rate between constant and logarithmic can arise. We further show that this logarithmic ceiling is unavoidable. In the Chain-of-Thought model, we show that access to the full generated trajectory eliminates the dependence on

M

altogether. We also analyze autoregressive linear threshold classes, and prove optimal mistake bounds, as well as a new lower bound for the statistical setting. Along the way, our results resolve several questions left open by [Joshi et al., 2025].

Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel

1MIT · 2The Hebrew University

CoT Reasoning Autoregressive Generation Statistical Learning Theory

May 7, 2026cs.AI

A Regime Theory of Controller Class Selection for LLM Action Decisions

Deployed language and vision-language models must decide, on each input, whether to answer directly, retrieve evidence, defer to a stronger model, or abstain. Contrary to the common monotonicity intuition, greater per-input expressivity is not uniformly beneficial in finite samples: under identical strict cross-validation, different benchmarks prefer different controller classes. This reflects a finite-sample limitation of instance-level uncertainty signals, which can be exhausted at a distribution-dependent scale. We organize controllers into a nested lattice of four classes: fixed actions, partition routers, instance-level controllers, and prior-gated controllers, ordered by complexity. We prove a regime theory that turns three data-estimable bottlenecks into a class choice: how much improvement is possible beyond the best fixed action, whether there are enough samples for instance-level controllers to make reliable decisions, and how much improvement a coarse partition router can recover when instance-level signal is unreliable. The resulting Bernstein-tight threshold has a matching information-theoretic lower bound, and strict nested cross-validation provably selects a near-best class. Across SMS-Spam, HallusionBench, A-OKVQA, and FOLIO, the predicted class matches the empirical winner; the prior-gated controller wins on TextVQA when OCR tokens supply a label-free prediction-time prior. Code is available at https://github.com/Anonymous-Awesome-Submissions/Regime-Theory.

Zhaoyang Jiang, Zhizhong Fu, Yunsoo Kim +4

University of Glasgow · UESTC, Chengdu, China · University College London

Selective Prediction Language Model-Based Control LLM Decision-Making LLM Routing Statistical Learning Theory

May 7, 2026cs.LG

Contrastive Identification and Generation in the Limit

In the classical identification in the limit model of Gold [1967], a stream of positive examples is presented round by round, and the learner must eventually recover the target hypothesis. Recently, Kleinberg and Mullainathan [2024] introduced generation in the limit, where the learner instead must eventually output novel elements of the target's support. Both lines of work focus on positive-only or fully labeled data. Yet many natural supervision signals are inherently relational rather than singleton, which encode relationships between examples rather than labels of individual ones. We initiate the study of contrastive identification and generation in the limit, where the learner observes a contrastive presentation of data: a stream of unordered pairs

\{x,y\}

satisfying

h(x)\ne h(y)

for an unknown target binary hypothesis

h

, but which element is positive is hidden from the learner. We first present three results in the noiseless setting: an exact characterization of contrastive identifiable classes (a one-line geometric refinement of Angluin [1980]'s tell-tale condition), a combinatorial dimension called contrastive closure dimension (a contrasitive analogue of the closure dimension in Raman et al. [2025]) and exactly characterizing uniform contrastive generation with tight sample complexity, and a strict hierarchy in which contrastive generation and text identification are mutually incomparable. We then prove a sharp reversal under finite adversarial corruption: there exist classes identifiable from contrastive pairs under any finite corruption budget by a single budget-independent algorithm, yet not identifiable from positive examples under even one corrupted observation. The unifying technical object is the common crossing graph, which encodes pairwise ambiguity, family-level generation obstructions, and corruption defects in a single coverage-and-incidence language.

Xiaoyu Li, Andi Han, Jiaojiao Jiang +1

University of New South Wales · University of Sydney

Statistical Learning Theory

May 7, 2026cs.LG

A Fine-Grained Understanding of Uniform Convergence for Halfspaces

We study the fine-grained uniform convergence behavior of halfspaces beyond worst-case VC bounds. For inhomogeneous halfspaces in

\mathbb{R}^d

with

d\ge 2

, we show that standard first-order VC bounds are essentially tight: even consistent hypotheses can incur population error

Θ(d\ln(n/d)/n)

, and in the agnostic setting the deviation scales as

\sqrt{τ\ln(1/τ)}

at true error

τ

. In contrast, homogeneous halfspaces in

\mathbb{R}^2

exhibit a markedly different behavior. In the realizable case, every hypothesis consistent with the sample has error

O(1/n)

. In the agnostic case, we prove a bandwise, log-free deviation bound on each dyadic risk band via a critical-wedge localization argument. Unioning over bands incurs only a

\ln\ln n

overhead, and we establish a matching lower bound showing this overhead is unavoidable. Together, these results give a fine-grained and nearly complete picture of uniform convergence for halfspaces, revealing sharp dimensional and structural thresholds.

Aryeh Kontorovich, Kasper Green Larsen

Ben-Gurion University · Aarhus University

Statistical Learning Theory Generalization Bounds

May 7, 2026cs.LG

A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iteration

While reinforcement learning (RL) promises to revolutionize the control of complex nonlinear robotic systems, a profound gap persists between the heuristic success of model-free off-policy deep RL and the underlying theory, which remains largely confined to tabular or linearizable settings. We identify the cause of this gap as an emergent isolation of three traditions: (i) measure-theoretic MDP foundations on general spaces limit their analysis to exact dynamic programming and ignore all error sources of a learning process; (ii) deterministic error propagation analysis addresses the approximation error via concentrability coefficients without a finite-sample analysis of the estimation error; and (iii) PAC generalization bounds characterize the estimation errors of simplified topologies. We bridge these traditions with a unified theoretical framework for fitted Q-iteration (FQI) on general measurable Borel spaces. Our main result provides a finite-sample, adaptive-data performance bound by chaining measure-theoretic probability with Bellman-operator contraction in Banach spaces. We prove that sequential Rademacher complexity controls Bellman-regression generalization under policy-dependent data collection. We further extend this analysis to provide the first cumulative, pathwise online regret guarantee for FQI in continuous spaces. These results lay the necessary foundations for the formal analysis of many modern deep RL algorithms.

Manuel Haussmann, Mustafa Mert Çelikok, Melih Kandemir

Department of Mathematics and Computer Science University of Southern Denmark

Reinforcement Learning Q-Learning Statistical Learning Theory Sample-Efficient RL

May 7, 2026cs.LG

Weak-to-Strong Generalization is Nearly Inevitable (in Linear Models)

Weak-to-strong generalization is a phenomenon in post-training whereby a strong student model, when finetuned solely with feedback from a weaker teacher, can not only surpass the teacher, but can improve upon its own capabilities. Recent work of Burns et al. (2023) demonstrated that this can occur in the setting of frontier language models, and subsequently there has been a flurry of both empirical work trying to exploit this phenomenon, as well as theoretical work attempting to understand it. In this work, we demonstrate that weak-to-strong generalization occurs in standard linear logistic regression, under mild distributional assumptions on the data. In fact, we show that this happens for most student-teacher pairs, suggesting that weak-to-strong generalization is in fact \emph{almost inevitable}, even in this basic setting. Notably, our setting does not require the student to be more expressive or have more model capacity in any way compared to the teacher, which runs contrary to the prevailing theoretical belief that a mismatch in model capacity is a central mechanism to weak-to-strong generalization.

Scott Geng, Dutch Hansen, Jerry Li

University of Washington, Seattle.

Logistic Regression Weak-to-Strong Generalization Statistical Learning Theory Teacher-Student Learning

May 7, 2026cs.LG

When Can Voting Help, Hurt, or Change Course? Exact Structure of Binary Test-Time Aggregation

Majority voting is one of the few black-box interventions that can improve a fixed stochastic predictor: repeated access can be cheaper than changing a high-capability model. Classical fixed-competence theory makes this intervention look monotone -- more votes help above the majority threshold and hurt below it. We show that this picture is fundamentally incomplete. Under the de Finetti representation for exchangeable repeated correctness, voting is governed by a latent distribution of per-example correctness probabilities. Even simple latent mixtures can generate sharply different voting curves, including nonmonotone behavior and, in an explicit construction, infinitely many trend changes. The full latent law determines the curve, but the curve does not determine the law. The exact object recovered by voting is a signed voting signature: at each binomial variance scale, it records excess latent mass above rather than below the majority threshold. Our main theorem proves that the complete odd-budget curve and this signature are equivalent: the curve increments are signed Hausdorff moments, and the full curve recovers the signature uniquely. This viewpoint explains shape phenomena, branch-symmetric nonidentifiability, realizability, variation, and endpoint rates. It also separates estimation regimes: direct per-example success-probability information targets the full signature, whereas fixed-depth grouped labels reveal only a finite prefix.

Yi Liu

York University

Statistical Learning Theory Majority Voting

May 6, 2026stat.ME

A renormalization-group inspired lattice-based framework for piecewise generalized linear models

We formally introduce a class of models inspired by renormalization group (RG) theory, built on additive hierarchical expansions analogous to those appearing in functional ANOVA and mixed-effects models. Like ReLU convolutional neural networks, they are almost everywhere locally linear; unlike ReLU networks, their partition structure is explicit, interpretable, and easy to modify or constrain. In these models, one defines a multidimensional lattice partition of the input space and uses it to scaffold variations in regression parameters. Each dimension of the lattice corresponds to an attribute by which the statistics of the problem may vary. The parameters are themselves expressed in the form of an expansion, where each term captures variations relative to a lower (coarser) interaction scale. These models admit multiple equivalent interpretations: as piecewise GLMs, as hierarchical mixed-effects regressions, or as regression trees with structured parameter sharing. Since RG motivates the design of these models, we use techniques from statistical physics -- specifically replica analysis -- to study their generalization properties. Specifically, we analyze the behavior of the Watanabe-Akaike Information Criterion (WAIC) as a proxy for generalization loss. This analysis yields two practical results: (i) guidance on the lattice design as a function of dataset size and predictor dimensionality; and (ii) a principled scaling law for the regularization prior when adding higher-order terms to the expansion so that one can increase model complexity without an expected increase in generalization loss. We evaluate the methodology on public datasets and find performance competitive against both blackbox methods and other intrinsically interpretable approaches.

Joshua C. Chang

NIH Clinical Center, Rehabilitation Medicine · Mederrata Research Inc · Sound Prediction Inc

Interpretable ML Statistical Learning Theory Generalized Linear Models

May 6, 2026cs.IT

Information-theoretic Limits of Learning and Estimation

Information theory plays a central role in establishing fundamental limits on what any learning or estimation algorithm can -- and cannot -- achieve, regardless of computational power. In this chapter, we provide an introduction to these connections. End-of-chapter exercises makes the material suitable for both classroom use and self-study. We begin by introducing concentration inequalities along with the notions of covering and packing in metric spaces, and the associated concept of metric entropy. These tools are essential for our analysis. We then introduce the learning-theoretic framework and derive upper bounds on generalization error in terms of metric entropy, Rademacher complexity, and the VC dimension, as well as mutual information and relative entropy. Finally we discuss the minimax estimation framework and establish lower bounds on minimax risk using Fano's inequality, yielding bounds in terms of relative entropy and covering and packing numbers. This manuscript contains preprint of a chapter under consideration for inclusion in the forthcoming third edition of Cover and Thomas's Elements of Information Theory, posted with permission from Wiley. It would follow the chapter posted at arXiv:2605.02989 . The table of contents of the new edition can be found at: https://docs.google.com/document/d/1L-m4oQEJw1PJhoxBeMwrrBD8S_HmvzMEkPbYvS24980/edit?usp=sharing . For feedback, please contact [email protected].

Abbas El Gamal, Maxim Raginsky

Stanford University* · UIUC**

Information-Theoretic Generalization Bounds Minimax Estimation Statistical Learning Theory Information-Theoretic Lower Bounds Generalization Bounds

May 6, 2026cs.LG

Understanding In-Context Learning for Nonlinear Regression with Transformers: Attention as Featurizer

Pre-trained transformers are able to learn from examples provided as part of the prompt without any weight updates, a remarkable ability known as in-context learning (ICL). Despite its demonstrated efficacy across various domains, the theoretical understanding of ICL is still developing. Whereas most existing theory has focused on linear models, we study ICL in the nonlinear regression setting. Through the interaction mechanism in attention, we explicitly construct transformer networks to realize nonlinear features, such as polynomial or spline bases, which span a wide class of functions. Based on this construction, we establish a framework to analyze end-to-end in-context nonlinear regression with the constructed features. Our theory provides finite-sample generalization error bounds in terms of context length and training set size. We numerically validate the theory on synthetic regression tasks.

Alexander Hsu, Zhaiming Shen, Wenjing Liao +1

Department of Mathematics, Purdue University · School of Mathematics, Georgia Institute of Technology

Transformer Attention In-Context Learning Statistical Learning Theory

May 5, 2026cs.LG

A Closed-Form Adaptive-Landmark Kernel for Certified Point-Cloud and Graph Classification

We introduce PALACE (Persistence Adaptive-Landmark Analytic Classification Engine), the data-adaptive companion to PLACE, paying a small cross-validation tier on three knobs (budget, radii, bandwidth;

\leq 5

choices each). A cover-theoretic core (Lebesgue-number criterion on the landmark cover) yields four closed-form guarantees. (i) A structural lower distortion bound

λ(τ;ν)

on

\mathcal{D}_n

under cross-diagram non-interference, with a

(D/L)^2

budget reduction over the uniform grid when diagrams concentrate. (ii) Equal weights

w_k = K^{-1/2}

maximizing

λ

, and farthest-point-sampling positions

2

-approximating the optimal

k

-center covering radius; both derived from training labels alone, no gradient training. (iii) A kernel-RKHS classification rate

O((k-1)\sqrt{K}/(γ\sqrt{m_{\min}}))

with binary necessity threshold

m = Ω(\sqrt K/γ)

from a matching Le Cam lower bound, and a closed-form filtration-selection rule. The kernel-Mahalanobis margin

\hatρ_{\mathrm{Mah}}

is the strongest closed-form ranker across the chemical-graph pool (mean Spearman

ρ\approx +0.60

); the isotropic surrogate

\hatγ/\sqrt{K}

admits a selection-consistency rate, and

\widehatλ

from (i) provides an independent data-level signal (positive on COX2 and PTC). (iv) A per-prediction certificate, in non-asymptotic Pinelis and asymptotic Gaussian forms, with no calibration split. Empirically, PALACE is the strongest closed-form diagram-based method on Orbit5k (

91.3 \pm 1.0\%

, matching Persformer), leads every diagram-based competitor on COX2 and MUTAG, and is competitive on DHFR (within 1 pp of ECP). At

8\times

domain inflation, adaptive placement maintains

94\%

while the uniform grid collapses to chance (

25\%

on 4-class data).

Sushovan Majhi, Atish Mitra, Žiga Virk +1

Data Science, George Washington University, USA · Department of Mathematical Sciences, Montana Technological University, USA · Faculty of Computer and Information Science, University of Ljubljana, Slovenia +1

Point Cloud Classification Classification Kernel Methods Graph Classification Persistent Homology Statistical Learning Theory

May 5, 2026cs.LG

Realizable Bayes-Consistency for General Metric Losses

We study strong universal Bayes-consistency in the realizable setting for learning with general metric losses, extending classical characterizations beyond

0

-

1

classification (Bousquet et al., 2020; Hanneke et al., 2021) and real-valued regression (Attias et al., 2024). Given an instance space

(X,ρ)

, a label space

(Y,\ell)

with possibly unbounded loss, and a hypothesis class

H \subseteq Y^{X}

, we resolve the realizable case of an open problem presented in Tsir Cohen and Kontorovich (2022). Specifically, we find the necessary and sufficient conditions on the hypothesis class

H

under which there exists a distribution-free learning rule whose risk converges almost surely to the best-in-class risk (which is zero) for every realizable data-generating distribution. Our main contribution is this sharp characterization in terms of a combinatorial obstruction: Similarly to Attias et al. (2024), we introduce the notion of an infinite non-decreasing

(γ_k)

-Littlestone tree, where

γ_k \to \infty

. This extends the Littlestone tree structure used in Bousquet et al. (2020) to the metric loss setting.

Dan Tsir Cohen, Steve Hanneke, Aryeh Kontorovich

1Ben-Gurion University of the Negev · 2Purdue University, USA.

Statistical Learning Theory

May 5, 2026cs.LG

Phase Transitions in Driven Informational Systems: A Two-Field Perspective on Learning Theory and Non-Equilibrium Chemistry

Phase-transition phenomena in deep learning (grokking, emergent capabilities, and ontological reorganization under context shift) have been studied through several lenses, including representational compression, singular learning theory, and information-theoretic progress measures. Independently, non-equilibrium statistical physics has identified phase transitions in driven chemical reaction networks underlying prebiotic selection, with empirical signatures that are difficult to reproduce within single-field gradient accounts. We propose a perspective in which both classes of phenomena admit a common description as driven informational systems: stochastic processes governed by two gradient fields, an entropy production rate Sigma and an information quasi-potential Phi_I := -ln p*, where p* is the stationary density. Within this framework we introduce two candidate order parameters: an adversarial breakdown threshold alpha_dagger and a self-referential coupling threshold kappa_c. The joint scaling of (alpha_dagger, kappa_c) defines a candidate universality class with exponents (gamma_1, gamma_2). We outline the geometric structure of this framework, identify falsifiable predictions distinguishing it from single-field alternatives, and show consistency with recent empirical findings (2024--2026) on alignment transitions, adversarial breakdown scaling, and partial introspection in large language models.

Truong Xuan Khanh

H&K Research Studio, Clevix LLC Hanoi, Vietnam

Phase Transitions Statistical Learning Theory

May 5, 2026stat.ML

On the Spectral Structure and Objective Equivalence of Orthogonal Multilabel Fisher Discriminants

We provide a unified theoretical analysis of Linear Discriminant Analysis with simultaneous multilabel scatter matrix formulations and Stiefel orthogonality constraints. Our contributions span both algebraic structure and statistical guarantees. On the algebraic side, we characterize the rank of the multilabel between-class scatter matrix, showing that the effective discriminant dimensionality can strictly exceed the classical single-label bound of

C-1

; we establish a multilabel partition of variance and prove that all four Fisher objectives are equivalent under the

W^\top S_t^{ML} W = I_r

constraint while characterizing their divergence under the Stiefel constraint; and we prove a two-sided label-distance preservation bound relating projected distances to Hamming distances in label space. On the statistical side, we establish a finite-sample

O(k_{\max}\sqrt{d\log d/n}/gap_r)

bound on the subspace estimation error under sub-Gaussian noise with a matching

Ω(σ^2 d/(n\,gap_r))

minimax lower bound, establishing a near-minimax-optimal rate (matching up to logarithmic and

k_{\max}

factors) for multilabel discriminant subspace estimation. We further provide high-probability distance concentration, robustness guarantees under label interactions, and a regularization analysis preserving the spectral structure when

d \gg n

. All results are verified numerically on synthetic data generated from the linear label-effect model, covering both the algebraic identities and the multilabel-specific quantities (

k_{\max}

,

κ(S_t^{ML})

,

\|Γ/n\|_2

,

Δ_r

) that govern the statistical bounds. The numerical experiments are designed as a sanity check for the theorems rather than as an empirical benchmark; evaluation on real multilabel datasets is left to future work targeting application-oriented venues.

Brian Keith-Norambuena, Juan Bekios-Calfa

Department of Computing & Systems Engineering, Universidad Cat´olica del Norte, Antofagasta, Chile.

Multi-Label Classification Statistical Learning Theory

May 4, 2026cs.LG

A Closed-Form Persistence-Landmark Pipeline for Certified Point-Cloud and Graph Classification

We introduce PLACE (Persistence-Landmark Analytic Classification Engine), a closed-form pipeline for classifying point clouds and graphs through their persistent-homology signatures. Three quantitative guarantees -- a margin-based excess-risk rate, a closed-form descriptor-selection rule, and a per-prediction certificate -- are derived from training labels alone, with no learned weights or held-out calibration. The embedding sums Mitra-Virk single-point coordinate functions over a sparse landmark grid; the closed-form weight rule

w_k^2 \propto (d_{k+1}^2 - d_k^2)/R_k^2

maximizes the distortion slope in Mitra-Virk's affine certificate under

ν

-coherence. (i) An

O(kR/(Δ\sqrt{m_{\min}}))

margin bound, driven by class-mean separation

Δ

and embedding radius

R

, matched in the sample-starved regime

m \lesssim R/Δ

by a Le Cam minimax lower bound. (ii) The Mahalanobis margin under Ledoit-Wolf-shrunk covariance is the strongest closed-form ranker on a 64-descriptor chemical-graph pool (mean Spearman

ρ= +0.56

across 11 benchmarks, positive on 10 of 11); the isotropic surrogate

Δ/\sqrt{\ell}

admits a closed-form selection-consistency rate on the homogeneous protein/social pools. (iii) A training-time-decided certificate, with no per-prediction overhead, in three concrete radii (Pinelis, Gaussian plug-in, and variance-aware Pinelis-Bernstein). Empirically, PLACE is the strongest diagram-based method on Orbit5k and matches the strongest topology-based baseline within statistical noise on MUTAG and COX2; remaining gaps fall into two diagnosable regimes (descriptor blindness on NCI1/NCI109; pool-coverage limits elsewhere). The Pinelis-Bernstein radius fires on 8 of the 12 benchmarks; on MUTAG the empirical and population nearest-centroid rules agree on every one of 940 held-out test predictions, validating the certificate's mechanism.

Sushovan Majhi, Atish Mitra, Žiga Virk +1

Data Science, George Washington University, USA · Department of Mathematical Sciences, Montana Technological University, USA · Faculty of Computer and Information Science, University of Ljubljana, Institute IMFM, Slovenia +1

Point Cloud Classification Classification Graph Classification Persistent Homology Statistical Learning Theory

May 4, 2026cs.LG

A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces

We study the complexity of smoothed agnostic learning of halfspaces on

\{\pm 1\}^n

under uniform marginals in the model of~\cite{KM25}, where each input coordinate is independently flipped with probability

σ\in (0, {1}/{2})

. We show that

L^1

polynomial regression achieves runtime and sample complexity

\tilde{O}(n^{O(\log(1/\varepsilon)/σ)})

, and prove a nearly matching Statistical Query complexity lower bound of

n^{Ω(\log(1+σ/\varepsilon^2)/σ)}

. This complements the recent work of~\cite{DK26}, which established analogous bounds in the continuous setting under Gaussian marginals.

Tim Sinen

University of Bonn, Germany

Boolean Function Learning Statistical Learning Theory

May 4, 2026stat.ME

Denoising data using convex relaxations

We study the problem of denoising observations

Y_i=X_i+Z_i

, where the latent variables

X_i

are sampled from a low-dimensional manifold in

\mathbb{R}^n

and the noise variables

Z_i

are isotropic Gaussian. We propose a convex-relaxation estimator that first reduces dimension by principal component analysis and then projects the observations onto the convex hull of the projected latent manifold. We construct a statistical oracle that estimates its supporting hyperplanes from empirical Gaussian tail probabilities of the noisy sample. Under a lower-mass condition on the latent distribution, we prove finite-sample guarantees for the oracle and derive error bounds for the resulting denoiser. The analysis combines risk bounds for least-squares projection under convex constraints with entropy bounds for convex hulls. We also verify the assumptions of the framework for a Cryo-Electron Microscopy observation model by establishing suitable covering number and Lipschitz estimates for the associated group action and imaging operators.

Charles Fefferman, Aalok Gangopadhyay, Matti Lassas +2

Department of Mathematics, Princeton University, Princeton, NJ 08544, USA. · TCS Research · Department of Mathematics and Statistics, University of Helsinki, FI-00014 Helsinki, Finland. +2

Cryo-Electron Microscopy Statistical Learning Theory

May 4, 2026cs.LG

Statistical Consistency and Generalization of Contrastive Representation Learning

Contrastive representation learning (CRL) underpins many modern foundation models. Despite recent theoretical progress, existing analyses suffer from several key limitations: (i) the statistical consistency of CRL remains poorly understood; (ii) available generalization bounds deteriorate as the number of negative samples increases, contradicting the empirical benefits of large negative sets; and (iii) the retrieval performance of CRL has received limited theoretical attention. In this paper, we develop a unified statistical learning theory for CRL. For downstream tasks, we evaluate retrieval quality using an AUC-type population criterion and show that the contrastive loss is \emph{statistically consistent} with optimal ranking. We further establish a \emph{calibration-style inequality} that quantitatively relates excess contrastive risk to excess retrieval suboptimality. For upstream training, we study both supervised and self-supervised contrastive objectives and derive generalization bounds of order

O(1/m + 1/\sqrt{n})

and

O(1/\sqrt{m} + 1/\sqrt{n})

, respectively, where

m

denotes the number of negative samples and

n

the number of anchor points. These bounds not only explain the empirical advantages of large negative sets but also reveal an explicit trade-off between

m

and

n

. Extensive experiments on large-scale vision--language models corroborate our theoretical predictions.

Yuanfan Li, Xiyuan Wei, Tianbao Yang +1

University of Sydney · 2Texas A&M University

Contrastive Learning Supervised Contrastive Learning Statistical Learning Theory

May 3, 2026stat.ML

Extrapolation in Statistical Learning with Extreme Value Theory

Extreme value theory provides rigorous theory and statistical tools for extrapolation in machine learning, particularly in settings where traditional methods struggle due to data scarcity in the tails. A broad range of tasks benefit from these advances, including regression and classification beyond the training data, extreme quantile regression, supervised and unsupervised dimension reduction, generative artificial intelligence and anomaly detection. This review synthesizes recent developments in these fields at the intersection of statistical learning and extreme value theory, with a focus on principled methods based on asymptotically motivated representations of the tail of univariate and multivariate distributions. We consider different theoretical frameworks for both asymptotically dependent and independent data and discuss how they translate into efficient statistical methods for extrapolation to extreme regions. By addressing both theoretical and practical aspects, we offer a comprehensive overview of the state-of-the-art in this quickly evolving field, and identify promising directions for future research.

Sebastian Engelke, Nicola Gnecco, Anne Sabourin

Research Institute for Statistics and Information Science, University of Geneva, Switzerland · Department of Mathematics, Imperial College London, United Kingdom · Université Paris Cité, Université Paris-Saclay, ENS Paris-Saclay, CNRS, SSA, INSERM, Centre Borelli, France

OOD Generalization Statistical Learning Theory Extreme Value Theory

May 3, 2026cs.LG

How Label Imbalance Shapes Geometry: A General Spectral Analysis of Multi-Label Neural Collapse

This work investigates the phenomenon of Neural Collapse (NC) in multi-label classification, extending its conceptual framework from multi-class learning to general correlated and imbalanced multi-label settings. Although recent studies have identified a ''tag-wise averaging'' structure for multi-label features, this view relies on implicit assumptions of label balance and combinatorial symmetry. Consequently, it fails to account for the geometrical distortions caused by intrinsic label correlations and data imbalance, which are common in practice. We resolve the multiplicity-one imbalance conjecture raised by Li et al. (2024), showing that higher-multiplicity prototypes obey a class-frequency-weighted synthesis rule rather than uniform averaging. To address this, we propose a rigorous spectral-control framework to analyze the terminal phase of multi-label learning under general imbalanced conditions. We introduce the label covariance spectrum

κ_m

, a scalar controlling the distribution-dependent lower-bound geometry, derived from the second-order moment matrix of the label distribution. Contrary to the averaging perspective, our analysis reveals that the centered label covariance spectrum controls the stability of terminal geometry by quantifying the weakest centered inter-class contrast directions. We prove that the classical Tag-wise Averaging emerges only as a special case under perfect orthogonality. Numerical experiments on synthetic distributions validate our theoretical bounds. This work resolves the scaled-average aspect of the imbalance conjecture and establishes a unifying theoretical framework that extends Neural Collapse to complex, imbalanced multi-label settings.

Xiaoxuan Ma, Yixuan Yang, Song Li +1

Department of Mathematics, Zhejiang University, Hangzhou, China.

Class-Imbalanced Learning Multi-Label Classification Neural Collapse Statistical Learning Theory

May 2, 2026cs.LG

Quantifying Multimodal Capabilities: Formal Generalization Guarantees in Pairwise Metric Learning

Multimodal learning leverages the integration of diverse data modalities to enhance performance in complex tasks. Yet, it frequently encounters incomplete or redundant modality data in real-world scenarios. This paper presents a fine-grained theoretical analysis of the generalization properties of multimodal metric learning models, addressing critical gaps in understanding the relationship between modality selection and algorithmic performance. We establish hierarchical relationships between function classes corresponding to different modality subsets and quantify the discrepancy between learned mappings and ground truth. Through rigorous analysis of pairwise complexity within the multimodal learning framework, we derive novel generalization error bounds that reveal the joint impact of modality quantity and granularity on model performance. Our theoretical findings on both upper and lower bounds demonstrate that incorporating fine-grained modality features reduces the complexity of the hypothesis space by enhancing modality complementarity. This work offers both theoretical foundations and practical implications for improving convergence rates and accuracy in multimodal learning systems.

Richeng Zhou, Xuelin Zhang, Liyuan Liu

Metric Learning Statistical Learning Theory Multimodal Learning Generalization Bounds

May 1, 2026cs.LG

Networked Information Aggregation for Binary Classification

We study networked binary classification on a directed acyclic graph (DAG) where each agent observes only a subset of the feature columns of a shared dataset. Agents act sequentially along the DAG: each receives prediction columns from its parents (if any), augments its local features with these columns, fits a logistic predictor by minimizing binary cross-entropy (BCE), and forwards its prediction column to its outgoing neighbors. We ask whether this sequential distributed training procedure achieves information aggregation, meaning that some agent attains small excess loss compared to the best logistic predictor trained with access to all feature columns. This question was studied for linear regression under squared loss by Kearns, Roth, and Ryu (SODA 2026). Extending their guarantees to classification is nontrivial because their analysis relies on quadratic structure that does not directly transfer to BCE with a logistic link. We analyze the resulting sequential logit-passing protocol and prove: (i) an excess loss upper bound of

O(M/\sqrt{D})

on depth-

D

paths under the condition that every

M

contiguous subsequence of

M

agents collectively observe all features, and (ii) a close lower bound showing instances with excess loss of at least

Ω(k/D)

where

k

is the dimension of the feature space. Together, these results identify network depth as a fundamental bottleneck for information aggregation in networked logistic regression.

MohammadHossein Bateni, Zahra Hadizadeh, MohammadTaghi Hajiaghayi +2

Google Research, New York City, NY, USA · University of California, Irvine, CA, USA · University of Maryland, College Park, MD, USA

Logistic Regression Binary Classification Statistical Learning Theory