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

Jul 2, 2026stat.ML

Contaminated Multi-task Learning with Heterogeneity: Fundamental Limits and Optimal Algorithms

Integrating information across related tasks can improve estimation and prediction in transfer, multi-task, and federated learning, but contamination and heterogeneity make robust borrowing challenging. We study a contaminated multi-task empirical risk minimization (ERM) framework in which an

ε

fraction of

K

tasks, each with sample size

n

, may be arbitrarily contaminated while the remaining tasks are heterogeneous. Our goal is to estimate both the global minimizer of the average risk and the clean task-specific minimizers, thereby combining robustness and personalization. In the Gaussian mean model, we show that several common paradigms, including adaptive and robust regularization around a shared center, global matrix regularization, decomposition-based regularization, and score-based outlier-task detection, all suffer from a worst-case contamination error of order

ε\sqrt{d/n}

, which is suboptimal compared to the lower bound

ε/\sqrt{n}

. This identifies a dimension-dependent barrier for these approaches. We then establish minimax lower bounds for a general heterogeneous ERM setting and propose a computationally efficient filtering-based robust multi-task gradient descent method. Under local strong convexity, smoothness, and sub-Gaussian gradient assumptions, the proposed method attains high-probability upper bounds matching the minimax rates up to logarithmic factors over a broad regime. In particular, it removes the extra

\sqrt{d}

contamination dependence of many regularization-based methods and score-based outlier detection, while achieving personalization to local tasks under strong heterogeneity. Simulations and a real-data analysis demonstrate strong robustness and personalization relative to a broad range of benchmark methods.

Ye Tian, Mengchu Li, Marco Avella Medina

Department of Statistics, Pennsylvania State University · School of Mathematics, University of Birmingham · Department of Statistics, Columbia University

Multi-Task Learning Minimax Estimation Statistical Learning Theory Robust Estimation

Jul 2, 2026math.ST

Aggregation with Exponential Weights is Optimal in Expectation

The aggregation with exponential weights (AEW) estimator is not fully understood in the basic setting of model selection aggregation with squared loss. In particular, whether it is minimax-rate optimal in expectation for large enough fixed temperatures and under random design has been an open problem since its introduction, which was explicitly posed by Lecué and Mendelson (2013). In this paper, we settle this problem by showing that \emph{without} requiring a Bernstein-type assumption, the AEW indeed achieves the excess risk

T \log (M) / (n+1)

in expectation, whenever the temperature

T

satisfies

(L^2/T)\exp(B/T)\leq μ/2

. Here, the number of dictionary elements is

M

, the estimator has observed

n

i.i.d. samples from any distribution, and the loss is assumed to be bounded by

B

,

L

-Lipschitz continuous and

μ

-strongly convex. For squared loss, we show that

T\geq 4 b^2

suffices when the predictions and labels are

[0,b]

-valued. Because AEW is known to be suboptimal in expectation for temperatures below some constant, this shows that AEW has a sharp phase transition when the temperature is large enough but constant, as conjectured by Lecué and Mendelson.

Mikael Møller Høgsgaard, Patrick Rebeschini, Tobias Wegel

Department of Statistics, University of Oxford · Department of Computer Science, ETH Zurich

Ensemble Learning Minimax Estimation Statistical Learning Theory

Jul 2, 2026stat.ML

Statistical Properties of $k$ -means Clustering for Data Missing Completely at Random

The classical

k

-means clustering cannot be directly used to incomplete data, and existing

k

-means-based clustering for missing data primarily focus on improving the practical accuracy of clustering, whereas most of them lack theoretical guarantees in the asymptotic sense. In this paper, we investigate the statistical properties of

k

-means clustering in the presence of missing data. We first establish the

\sqrt{n}

-excess risk bound and prove the consistency of the estimated cluster centers under general missing mechanisms. For the Missing Completely at Random (MCAR) mechanism, we further derive the

\sqrt{n}

-convergence rate and asymptotic normality of the estimated cluster centers. Moreover, we study in what cases the cluster centers estimated by incomplete data converge to the true cluster centers of original fully observed data, and give a sufficient condition about the missing probability and the separation among true clusters. These results provide a theoretical guarantee for missing-data-

k

-means. Notably, our analysis reveal that under MCAR mechanism, both achieving the

\sqrt{n}

-rate and converging to the true cluster centers require

k

true centers to be distinct in every dimension, highlighting the significant challenges of application in high-dimensional regimes. Finally, we conduct numerical simulations on synthetic incomplete datasets to support our theoretical analysis results.

Xin Guan

Graduate School of Information Sciences Tohoku University Sendai, Miyagi 980-8579, Japan

Clustering Unsupervised Clustering Statistical Learning Theory

Jul 1, 2026stat.ML

Function-Counting Theory for Low-Dimensional Data Structures

The success of deep learning models in classification and regression is widely attributed to the low-dimensional structure that real-world data tend to exhibit, despite their high-dimensional representation. This work attempts to provide a mathematical framework for binary classification on low-dimensional data, building on Cover's (1965) function-counting theory. With our framework, we aim to address the question of how the low-dimensional structure of the data affects the classification capabilities of learning models. Cover's theory relies on a general position assumption that blinds it to the underlying data structure. We refine this assumption to account for the low-dimensionality of the data and derive dichotomy counts that reflect the data structure. We further extend Cover's separation capacity and problem of generalization to the low-dimensional setting, enabling the impact of the underlying data structure on both to be analyzed.

Konstantin Häberle, Helmut Bölcskei

ETH Zurich

Intrinsic Dimensionality Binary Classification Statistical Learning Theory Generalization Bounds

Jul 1, 2026cs.LG

Measuring Dead Directions: Decomposing and Classifying Singular Structure off Canonical Alignment

We give a descent-free, alignment-free measurement of singular structure on trained networks. At a single frozen checkpoint the read recovers the order

k

of each dead direction from the directional-Fisher rate, the master invariant from which the per-direction learning coefficient

1/(2k)

follows exactly, in whatever basis the optimizer left. The same read classifies each direction, separating a genuine singularity, whose order the architecture fixes, from a flat gauge symmetry; the directional-Fisher magnitude settles the cases the order cannot. A pluggable detector supplies the directions for transformer, convolutional, and normalisation layers. The read recovers the architecture-predicted order across constructed cells and trained networks, including a fine-tuned vision transformer whose dead structure is the LayerNorm-kernel gauge and a from-scratch one whose compressed MLP forms a node-death at its activation order. Where the singular structure enumerates, the per-direction orders assemble, through the typed intersection of the loci, into the global coefficient

(λ, m)

matching the closed form. The method removes the canonical-alignment and descent preconditions of the underlying rate result, turning order-recovery into a deterministic, architecture-general reading. We then map its reach into the Watanabe triple: the order determines the universal singular fluctuation

ν(k)

, though a trained network's realized

ν

falls below it as the live structure absorbs the dead direction's data fluctuation, and the multiplicity recovers from the dominant structure under a single-locus assumption.

Tejas Pradeep Shirodkar

IIIT, Hyderabad

Singular Learning Theory Statistical Learning Theory

Jun 30, 2026cs.CV

A Mechanism-Driven Theory of Phase Transitions in Active Learning

Active learning (AL) performance is known to be budget-dependent, yet regimes are typically defined by heuristic label counts that fail to generalize across datasets or architectures. We characterize AL dynamics by reframing budget regimes as shifts in the dominant generalization mechanism. By reinterpreting PAC-style risk components as dynamic interacting terms, we prove that dominance shifts are structurally unavoidable, creating a moving bottleneck for generalization. We operationalize this using measurable proxies and a segmented regression procedure to identify a tripartite taxonomy: data-driven, transition, and model-driven phases. Our framework explains the long-standing observation that representativeness, coverage, and uncertainty strategies excel at different stages. Experiments across natural and medical imaging show that AL efficiency depends on the alignment between the strategy's inductive bias and the active bottleneck. Moreover, self-supervised representation shift transitions earlier along the labeling trajectory, highlighting the role of representation quality in shaping AL dynamics. Overall, this work provides a unified framework for the next generation of transition-aware AL algorithms.

Julia Machnio, Mads Nielsen, Mostafa Mehdipour Ghazi

Pioneer Centre for AI, University of Copenhagen, Copenhagen, Denmark

Active Learning Statistical Learning Theory

Jun 30, 2026stat.ML

Accelerating Conformal Prediction via Approximate Leave-One-Out

While conformal prediction provides a general framework for uncertainty quantification in predictive inference, its application is often limited by computational cost. Recent methods, including Jackknife+ and Jackknife-minmax, achieve faster computation by trading a slight loss of efficiency relative to full conformal prediction, but still requires computing leave-one-out refits for all observations. In this paper, we further accelerate conformal prediction by incorporating approximate leave-one-out (ALO) estimators, and establish asymptotic coverage and efficiency. While our proof draws on methods developed for analyzing the consistency of ALO cross-validation risk estimators in high-dimensional statistics, it requires adaptations to handle conformal prediction, where leave-

i

-out residuals are needed for predictions at

x_{n+1}

rather than just at the training covariate

x_i

. Simulation results validate our theoretical findings, showing that the ALO-based methods achieve coverage and efficiency comparable to the exact methods, while significantly reducing the runtime.

Jiachen Cong, Jingbo Liu

Department of Statistics, University of Illinois Urbana-Champaign, Champaign, IL, 61820, USA

Conformal Prediction Statistical Learning Theory Regression Prediction Intervals

Jun 30, 2026math.ST

On Optimal Data Splitting for Split Conformal Prediction

Conformal prediction and its variants, including the split conformal prediction, provide a distribution-free framework for uncertainty quantification by constructing prediction intervals or sets with finite-sample coverage guarantees. The statistical efficiency of these intervals depends critically on how the data are split into training and calibration samples. Despite its practical importance, a principled characterization of the training-calibration split that minimizes prediction interval length while maintaining coverage has remained largely unresolved. In this paper, we develop a theoretical framework for optimal data splitting in split conformal prediction. We first analyze the problem in a general setting and derive analytical characterizations of the length-optimal split ratio under both symmetric and asymmetric regimes. We then show how the general results specialize to several commonly used regression settings, including linear regression, nonparametric regression, and neural networks, thereby demonstrating the scope of the framework. We also describe a data-based method for selecting the optimal proportion. Our analysis clarifies how model-related features govern the optimal allocation of samples between training and calibration and provides principled guidance for constructing shorter prediction intervals. Experiments on both synthetic and real-world datasets demonstrate the applicability of the proposed methodology across a variety of practical scenarios.

Sayan Das, Bahram Yaghooti, Todd A. Kuffner +1

Department of Statistics and Data Science, Washington University in St. Louis, St. Louis, MO 63130, USA · Department of Electrical and Systems Engineering, Washington University in St. Louis, St. Louis, MO 63130, USA

Conformal Prediction Statistical Learning Theory Regression Prediction Intervals

Jun 30, 2026cs.LG

Explaining Machine Learning and Memorization with Statistical Mechanics

Artificial neural networks (NNs) and machine learning (ML) algorithms are poorly understood from a theoretical perspective, which makes it difficult to fully realize their potential and overcome their weaknesses. For instance, ML algorithms train NN weights by moving them along a low-dimensional subspace of their allowed values, but this implicitly low-dimensional learning structure is not properly exploited to improve training because its nature is not well understood. Moreover, trained NNs are easily confused by pervasive adversarial attacks whose theoretical underpinnings are still unclear. This thesis aims to improve our theoretical understanding of NNs and ML, with a particular focus on adversarial attacks and implicitly low-dimensional learning. For this purpose, we use mathematical tools from statistical mechanics to study different types of NNs and ways in which they can fit the data. In particular, we study two classes of models that fit the data with various degrees of learning and memorization: dense associative memory (DAM) and restricted Boltzmann machines (RBM). In the process, we investigate connections between different versions of these models that are useful to make analytical investigations more efficient.

Robin Theriault

Faculty of Science

Statistical Physics of Learning Neural Network Memorization Adversarial Robustness Memorization in Generative Models Statistical Learning Theory Associative Memory+1

Jun 29, 2026math.LO

Fast approximation and learning of binary classification tasks in o-minimal structures using ReLU neural networks

We study binary classification problems whose decision sets are given by definable sets in o-minimal expansions of the real field. Motivated by cell decomposition of definable sets, we introduce traceable sets as a classical proxy for definable decision regions and analyze their approximation by ReLU neural networks. Under uniform bounds on the number of connected components and suitable

C^m

extensions for the boundary functions, we prove that characteristic functions of traceable subsets of

[-1/2,1/2]^n

can be approximated in

L^p

to accuracy

\varepsilon>0

by ReLU neural networks of size

\mathcal{O}(\varepsilon^{-p(n-1)/m})

, with depth independent of

\varepsilon

and polynomially bounded weights. This establishes quantitative approximation rates for certain definable collections in o-minimal structures using ReLU neural networks. The same approach also yields the stated approximation rates for a subclass of definable maps

[-1/2,1/2]^n \to \mathbb{R}

. We then combine the approximation capabilities with entropy estimates for ReLU neural network classes to obtain statistical learning rates for empirical risk minimization with hinge loss. For

N

uniformly distributed samples, the resulting classifiers achieve expected misclassification error of order

N^{-m/(m+pn-p)}

up to an arbitrarily small polynomial loss.

Clemens Kinn, Philipp Petersen

Faculty of Mathematics, University of Vienna, 1090 Vienna, Austria

ReLU Neural Networks Binary Classification Classification Neural Network Approximation Theory Statistical Learning Theory

Jun 29, 2026cs.LG

Informational Frustration in Neural Manifolds: Shannon Bottlenecks and the Limits of Learnability

Why overparameterised deep networks generalise so remarkably well remains one of the most stubborn open questions in machine learning theory. Classical frameworks like VC dimension and Rademacher complexity predict catastrophic overfitting in modern models, leaving a massive theoretical gap between theory and reality. In this paper, we bridge this divide by introducing a unified framework that links information theory, topology, and statistical mechanics to map the hard limits of deep learning. Central to our approach is the Entropic Learnability Horizon (ELH): a fundamental law stating that a network can only truly learn a target function if the Shannon entropy of the data manifold outpaces the topological entropy of the function's decision boundary, balanced by the von Neumann entropy of the network's weight space. We establish the Shannon-Topological Bottleneck Theorem, proving that when a target boundary's geometric complexity exceeds this informational horizon, the system undergoes a sudden entropic phase transition. It falls into a state of Informational Frustration - a glassy, rigid memorization phase where generalization becomes thermodynamically impossible. Using this lens, we show that the enigmatic phenomenon of "grokking" is actually an Entropic Release, where weights abruptly reorganise to unlock the bottleneck. Finally, we translate this theory into practice with Entropic Gradient Descent (EGD), an optimization algorithm that dynamically manages weight entropy to keep learning on track. Ultimately, this work repositions entropy not just as a tool for tracking uncertainty but as the fundamental physical currency that dictates whether a machine can learn.

Srinivasa Rao P., Vangmayi P Reddy

Curlvee Technolabs, India, Former Scientist, C-DAC · Former Scientist, C-DAC · Indian Institute of Technology Madras, India

Statistical Physics of Learning Neural Network Generalization Information Bottleneck Statistical Learning Theory Entropy Regularization

Jun 29, 2026cs.AI

Using Large Language Models as Low-Cost Statistical Estimators for Human-Response Data

Quantitative research across the social and behavioral sciences depends on human subject experiments that are expensive, slow, and subject to sampling bias. Here we show that pretrained large language models induce risk-equivalent estimators of conditional expectations under squared loss, establishing restricted functional risk equivalence: under squared loss, the LLM induces an estimator whose risk matches the Bayes optimal risk for squared-loss prediction of conditional expectations for any inference that depends on the data only through the conditional mean. We formalize the LLM as a misspecified functional estimator

T(\hat{P}_n)

trained on i.i.d.\ data, decompose the estimation error into representation bias

ε_{\mathrm{rep}}

and optimization error, and prove that under mild regularity conditions the LLM's expected error converges to the irreducible population variance plus the squared representation bias, with the representation bias bounded by the Pinsker inequality. The identifiability error

δ

propagates into the effective bias, inflating the asymptotic risk floor. We establish restricted functional risk equivalence via a bidirectional Le Cam deficiency analysis: the forward deficiency vanishes asymptotically while the reverse deficiency is exactly zero. We provide finite-sample concentration bounds and a calibration protocol with explicit decision rules. The result is a precise, provable statement: a well-calibrated LLM achieves the Bayes-optimal risk for conditional-mean-dependent inference, bounded by explicit scope conditions. In practical applications, this means that under satisfied conditions and well-calibrated models, large language models can be used in many prediction and decision-making tasks that originally relied on human experiments, approximating near-optimal statistical inference at lower cost.

Haobo Yang

Department of Computer Science and Engineering, SUSTech University

Language Model Calibration Statistical Learning Theory

Jun 29, 2026cs.LG

Data-Driven Energy-Based Learning via Gibbs Measures on Hierarchical Structures

We introduce a data-driven probabilistic framework for learning systems based on Gibbs measures on hierarchical structures. Unlike standard empirical risk minimization, where a dataset is used to identify a single optimal parameter, our approach transforms the empirical loss function into an interaction potential defining an energy-based model. The resulting Gibbs distribution describes a family of equilibrium learning states generated by the data. We formulate the consistency conditions of the associated finite-volume distributions and derive nonlinear integral fixed-point equations whose solutions characterize the admissible learning states. These equations provide a rigorous connection between empirical loss landscapes and probabilistic inference on trees. For translation-invariant solutions, the problem reduces to the analysis of positive compact operators induced by data-dependent kernels, allowing us to establish existence and uniqueness conditions in the one-dimensional setting. Furthermore, we show that hierarchical learning systems may exhibit phase-transition phenomena: for certain empirical kernels on Cayley trees, multiple Gibbs measures emerge beyond a critical inverse temperature, corresponding to distinct equilibrium prediction regimes. Numerical experiments with non-separable kernels illustrate the appearance of multiple solution branches and demonstrate the coexistence of several data-induced learning states. Our results provide a new perspective on energy-based learning, where data do not merely determine an optimal model through minimization but define an entire probabilistic landscape of possible inference states.

L. U. Abdullaev, F. Herrera, U. A. Rozikov +1

National University of Singapore, Singapore · Department of Computer Science and Artificial Intelligence, University of Granada, E-18071 Granada, Spain · V.I. Romanovskiy Institute of Mathematics, Uzbekistan Academy of Sciences, 9, Universitet str., 100174, Tashkent, Uzbekistan +3

Statistical Physics of Learning Phase Transitions Energy-Based Models Statistical Learning Theory

Jun 29, 2026cs.LG

The Forgetting-Retention Dilemma: Certified Unlearning Theory in Continual Learning

Machine unlearning aims to eliminate the influence of specific data from trained models to safeguard privacy. However, this presents a significant challenge in the context of continual learning (CL), where models update sequentially on dynamic datasets. A major limitation is that current certified unlearning algorithms fail to account for the complex, cumulative model evolution inherent to CL framework. In this work, we establish the first theoretical foundation bridging CL and machine unlearning. We formulate the CL's unlearning objective as the minimization of post-unlearning excess risk, which decomposes into CL excess risk and unlearning loss, characterizing the fundamental trade-off between preserving historical knowledge and targeted forgetting. Under mild assumptions, we first establish an upper bound for the CL excess risk in non-convex models. We then adapt two certified unlearning approaches, gradient-based and Hessian-based, to the CL framework. Our analysis reveals that while the gradient-based approach is less effective than the Hessian-based method in minimizing unlearning loss, it offers the distinct advantage of nearly zero storage overhead for enabling unlearning. This insight motivates a hybrid strategy that reduces storage costs while maintaining post-unlearning performance. Experimental results further validate our theoretical findings.

Yiting Hu, Lingjie Duan, Qian Zhang

Singapore University of Technology and Design, Singapore · The Hong Kong University of Science and Technology (Guangzhou), Guangzhou, China.

Continual Learning Statistical Learning Theory Machine Unlearning

Jun 28, 2026cs.LG

Structured Proper Loss Geometries for Multiclass Classification: Theory and Controlled Empirical Evaluation

Strictly proper scoring rules identify the true conditional class distribution at population level, but their curvature can alter optimization and finite-sample behavior. We study three multiclass objectives: a class-aware quadratic Bregman score (CAPM), a strongly convex generator with constrained log-cosh ridges (HPG), and an HPG objective with an annealed probability-margin penalty (APMS). CAPM is treated as a structured instance of established quadratic scoring-rule theory. We derive conditional-regret, curvature, range, and logit-gradient bounds for CAPM and HPG, and prove exact penalty-range and conditional-target displacement bounds for APMS. Controlled five-seed experiments use Digits, Wisconsin breast cancer, and synthetic confusion and long-tail problems under clean labels, symmetric and pair-flip corruption, class imbalance, calibration evaluation, input corruption, and first-order adversarial perturbations. The candidates are close to cross-entropy on clean data and show descriptive gains in some noisy-label cells, but the five-seed comparisons are interpreted descriptively rather than as significance evidence. The selected noisy-label baselines perform better on Digits with 40% symmetric label noise, and explicit prior-adjustment methods perform better in the 30:1 synthetic long-tail experiment. Ablations do not show a consistent benefit from the candidate-specific graph, ridge, or margin components. The mathematical analysis establishes the stated properties, and the experiments delimit the empirical evidence; together they do not support a claim of general superiority.

Soumyadip Sarkar

Independent Researcher

Proper Scoring Rules Multiclass Classification Classification Statistical Learning Theory

Jun 28, 2026cs.LG

Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

Scientific discovery via symbolic regression is often viewed as statistically and computationally intractable because the hypothesis space of expressions grows combinatorially with depth. This paper revisits the statistical side through the lens of PAC learning, focusing on compositional function trees built from a finite vocabulary of smooth operators (e.g.,

\{+,\times,\sin,\exp\}

and affine maps). We prove that the relevant generalization quantity, Rademacher complexity, hence the excess risk, does not necessarily blow up exponentially with the number of distinct symbolic structures, but is controlled by (i) the depth

d

and (ii) the Lipschitz constants of the base operators along the composed computation graph. Concretely, under mild Lipschitz conditions on operators and bounded affine leaves, a finite-union bound over a vocabulary of size

K=|\mathcal{H}_{\mathrm{base}}|

together with Maurer-type vector contraction yields

\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})

with arity bound

b

; corresponding high-probability risk bounds scale as

\mathcal{O}(L^{d}/\sqrt{n})

when

K,b=O(1)

and

\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})=O(n^{-1/2})

. We complement the theory with a modular codebase that trains differentiable operator trees (not MLPs) on synthetic "physics-like" targets of controlled depth and shows that the empirical generalization gap correlates positively with the predicted complexity term

(\widehat{L}^{d})/\sqrt{n}

.

Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

Independent Researcher · TÜBİTAK Science High School

Sample Complexity Statistical Learning Theory Symbolic Regression

Jun 28, 2026stat.ML

Generalization Analysis of Transformers in Distribution Regression

In recent years, models based on the Transformer architecture have seen widespread applications and have become one of the core tools in the field of deep learning. Numerous successful techniques, such as parameter-efficient fine-tuning and efficient scaling, have been proposed surrounding their applications to further enhance performance. However, the success of these strategies has always lacked the support of rigorous mathematical theory. To study the underlying mechanisms behind Transformers and related techniques, we first propose a Transformer learning framework motivated by distribution regression, with distributions being inputs, connect a two-stage sampling process with natural language processing, and present a mathematical formulation of the attention mechanism called attention operator. We demonstrate that by the attention operator, Transformers can compress distributions into function representations without loss of information. Moreover, with the advantages of our novel attention operator, Transformers exhibit a stronger capability to learn functionals with more complex structures than convolutional neural networks and fully connected networks. Finally, we obtain a generalization bound within the distribution regression framework. Through the aforementioned theoretical results, we further discuss some successful techniques emerging with large language models (LLMs), such as prompt tuning, parameter-efficient fine-tuning, and efficient scaling. We also provide theoretical insights behind these techniques within our novel analysis framework.

Peilin Liu, Ding-Xuan Zhou

School of Mathematics and Statistics, University of Sydney, Sydney, NSW 2006, Australia

Neural Network Generalization Transformer Attention Statistical Learning Theory

Jun 27, 2026cs.LG

How Far Can Sharpness and Complexity Jointly Explain Generalization?

Sharpness and complexity are two central factors in the generalization analysis of deep neural networks. Existing quantitative evaluations of generalization measures have largely focused on individual scalar measures, leaving the joint explanatory power of sharpness and complexity largely unexplored. This work studies how far sharpness and complexity can jointly explain generalization. We use linear regression and introduce a Pareto-based analysis to quantitatively evaluate the joint explanatory power of these two factors. Beyond the existing parameter-level definitions, we further propose realizations of sharpness and complexity that are closer to function space and less dependent on raw parameter representations. We find that function-oriented definitions of these two quantities expand the explanatory scope of the two-factor view beyond what is achieved by existing parameter-level metrics. Overall, our results support the sharpness-complexity perspective as an informative lens for understanding generalization across diverse settings. At the same time, the remaining failures indicate that whether this two-factor view can serve as a complete theory of generalization remains open.

Ziyu Cheng, Xitong Zhang, Longxiu Huang +1

Michigan State University

Neural Network Generalization Statistical Learning Theory

Jun 26, 2026cs.LG

Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model

Modern machine learning models are trained by optimizing high-dimensional non-convex empirical risk functions. Such cost functions can have a multitude of local optima and yet, gradient-based optimization appears to converge to near-global optima. Within a simple supervised learning setting, we develop a precise picture of which parts of the empirical risk landscape are accessible by polynomial-time algorithms. We are given i.i.d. pairs

\{(\boldsymbol{x}_i,y_i):\; 1 \le i\le n\}

with

\boldsymbol{x}_i\in \mathbb{R}^d

standard Gaussian feature vectors, and

y_i\in\mathbb{R}

response variables that depend on

\boldsymbol{x}_i

through their projections on an unknown

k

-dimensional subspace. We use empirical risk minimization to learn a model that depends on an

m

-dimensional projection of the data (e.g., an

m

-neurons neural network). We propose an incremental approximate message passing (IAMP) algorithm and precisely characterize the training error it achieves, as well as the relation between test and training error, in the high dimensional asymptotics

n,d\to\infty

, with

n/d\toα\in (0, +\infty)

. Based on earlier work in related models, we expect that the performance achieved by our algorithm is optimal among polynomial-time algorithms.

Andrea Montanari, Kangjie Zhou

Department of Mathematics and Department of Statistics, Stanford University · Department of Statistics, Columbia University

Statistical Learning Theory Multi-Index Models Empirical Risk Minimization

Jun 26, 2026stat.ML

Surprises in Proper Positive-Only Learning

Binary classification from positive-only samples is a variant of PAC learning in which the learner receives i.i.d. samples from the positive region of an unknown target concept, but is evaluated under the original distribution (which places mass on both positive and negative regions). This model dates back to Natarajan [1987, STOC], and the characterization of improper learning is well-known -- it even appears in textbooks. The characterization of proper positive-only learning, however, has long remained open. In this work, we revisit and settle this question: a concept class is properly learnable from positive-only samples if and only if it has finite VC dimension and satisfies a new combinatorial condition, which we call uniform exterior separability. Together with several separation results, this characterization reveals a surprisingly rich landscape that differs sharply from standard PAC learning: proper and improper learning are separated, randomized and deterministic proper learning are separated, there are classes for which no ERM is a learner, and finite VC dimension does not suffice even for non-uniform learning. Along the way, we introduce new combinatorial dimensions that we believe can be of broader interest in learning theory.

Shai Ben-David, Farnam Mansouri, Anay Mehrotra +1

University of Waterloo and Vector Institute · Stanford University · Yale University

Binary Classification Classification PAC Learning Statistical Learning Theory

Jun 26, 2026cs.LG

How Width and Data Shape Generalization Scaling Laws in Quadratic Neural Networks

Understanding how performance scales jointly with model size and data is a central problem in modern machine learning. Existing theoretical works on scaling laws typically describe generalization as a function of data or compute, often in fixed-feature or infinite-width regimes and for online SGD. Here, we instead study how generalization scales with the number of trainable parameters and the number of samples in a feature-learning model. We analyze

\ell_2

-regularized empirical test error minimization in a quadratic two-layer network in a finite-sample setting with structured data. This setting allows for an explicit characterization of the generalization error as a function of the number of samples, model width, and regularization. Our results reveal a phase diagram with distinct scaling regimes as the number of parameters varies. In particular, the generalization error follows data-dependent power laws controlled by the spectral structure of the target. We further characterize the transitions between regimes, including the onset of interpolation, and their impact on generalization.

Julius Girardin, Emanuele Troiani, Yizhou Xu +3

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

Neural Network Generalization Scaling Laws Neural Scaling Laws Statistical Learning Theory

Jun 26, 2026cs.LG

Singular Learning and Occam's Razor in Deep Monomial Networks

In the optimization of neural networks, gradient dynamics are influenced by critical points that arise from the model's architecture. These critical points occur where the Jacobian of the model's parametrization is rank-deficient, and are the most pronounced singularities studied in Singular Learning Theory. We investigate such points in deep fully-connected networks with monomial activations via tools from polynomial algebra such as Mason's Theorem. We show that, for sufficiently large activation degree, criticality occurs precisely at subnetworks, i.e., at parameter configurations where some neurons are inactive or redundant. This offers a mathematical perspective on the implicit bias in deep neural networks, explaining the tendency of these models to converge toward simpler functions.

Kathlén Kohn, Giovanni Luca Marchetti, Farhan Shabir +2

KTH Stockholm · No Affiliation · Umeå University +1

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

Jun 25, 2026cs.DS

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy

\varepsilon > 0

and dimension

d

we give an efficient algorithm that uses

n = \tilde{O}(d^2/\varepsilon^2)

samples and learns the underlying Gaussian to error

\varepsilon

in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of

d

and

\varepsilon

even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.

Haitong Liu, Deepak Narayanan Sridharan, David Steurer +1

ETH Zurich

Minimax Estimation Statistical Learning Theory

Jun 25, 2026cs.LG

Recovering Governing Equations from Solution Data: Identifiability Bounds for Linear and Nonlinear ODEs

Learning governing equations from observed solution data is a fundamental challenge in scientific machine learning, yet the theoretical conditions under which a ground-truth ODE can be uniquely and stably identified from multiple solution observations remain largely undeveloped, and no quantitative analysis of the sample complexity of such learning tasks exists in the literature. To address this gap, we introduce the Hausdorff distance on solution sets as the natural metric for comparing differential equations, since it captures the worst-case separation between two equations over all admissible initial conditions and thus encodes the minimax structure of the identification problem. We establish identifiability bounds for governing ODEs across a wide class of structure equations--ranging from linear ODEs to nonlinear classes with Lipschitz (Hölder)-continuous vector fields--characterizing precisely when two distinct equations can be distinguished from solution data. Using this metric, we derive metric entropy estimates for the relevant ODE classes and analyze sample complexity bounds, quantifying how many solution observations are needed to reliably recover the governing equation.

Yang Pan, Helmut Bölcskei

Parameter Identifiability Sample Complexity Nonlinear System Identification Statistical Learning Theory ODE Discovery

Jun 25, 2026cs.LG

Sketched Linear Contrastive Learning: Approximation, Optimization, and Statistical Scaling

Scaling laws describe how learning performance varies with model size, data size, and compute. While recent theoretical work has established scaling laws for sketched linear regression, much less is understood for contrastive representation learning. In this paper, we study a sketched linear model for contrastive learning under a paired Gaussian latent-variable setup. The learner observes only sketched views of two correlated variables and trains a bilinear contrastive score by full-batch empirical gradient descent. We analyze a Gaussian-negative quadratic contrastive surrogate under aligned power-law spectra and a contrastive source condition, where we derive a risk decomposition into irreducible risk, approximation error, GD bias, GD variance, and a cross term. The cross term is controlled by the bias and variance and therefore does not affect the upper-bound scaling. Our main theorem gives an explicit scaling law with respect to sketch dimension

M

, sample size

N

, and effective optimization horizon

L_{\mathrm{eff}}γ

. Compared with standard linear-regression scaling laws, the contrastive setting must learn interactions between two views, and this changes how optimization and finite-sample noise scale with model size, data, and training time. This provides a first theoretical step toward understanding scaling behavior in contrastive learning and gives guidance for balancing model size, data, and optimization compute.

Ziyan Chen, Zhongzhu Zhou, Ding-Xuan Zhou

The University of Sydney · Together AI

Contrastive Learning Statistical Learning Theory

Jun 23, 2026cs.LG

Data Augmentation: A Fourier Analysis Perspective

Data augmentation is a simple and model-agnostic approach for exploiting known invariances in learning problems. Given a group acting on the input space, one augments the training set with transformed copies of each sample. Because it exploits symmetries without modifying the underlying learning algorithm, data augmentation can be applied broadly across learning methods. However, this universality comes at a computational cost: when the group is large, full group-sized augmentation quickly becomes computationally infeasible. This raises a fundamental question: Can partial data augmentation achieve the same statistical benefits as full augmentation in terms of generalization and sample complexity? We develop a general framework for investigating this question using Fourier analysis and the representation theory of finite groups. We show that, for a broad class of classical learning problems, partial data augmentation based on a randomly sampled subset of group elements achieves the same minimax rates as full augmentation, up to an approximation error that vanishes as the subset size increases. Our results provide a theoretical explanation for why partial augmentation can retain the statistical benefits of full augmentation despite enforcing symmetry only approximately, and shed light on a recently raised question in learning with symmetries: whether statistically optimal learning under general group invariances can be achieved using computationally scalable methods. Moreover, we prove a complementary impossibility result: enforcing exact invariance via data augmentation requires averaging over the entire group, and cannot be achieved by any strict subset when the hypothesis space is sufficiently expressive. Together, these results provide a unified perspective on full and partial data augmentation, as well as exact and approximate symmetry enforcement.

Behrooz Tahmasebi, Melanie Weber, Stefanie Jegelka

Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Cambridge, MA 02138, USA. · Technical University of Munich (CIT, MCML, MDSI) · MIT Computer Science and Artificial Intelligence Laboratory (CSAIL)

Data Augmentation Statistical Learning Theory

Jun 22, 2026cs.LG

Solve for the Hyperparameter, Skip the Search: Kolmogorov-Optimal Scaling Laws for Spline Regression

Hyperparameter tuning almost always means search: fit the model at every value on a grid, score each by cross-validation, and keep the winner. For spline regression that search is unnecessary. The optimal resolution can be solved for in closed form, to the accuracy an exhaustive search reaches, at a fraction of the compute. Three ingredients make this possible: classical approximation theory pins the squared bias to a known power of the resolution G, exactly the Kolmogorov n-width of the smoothness class; the basis dimension is an explicit polynomial in G; and leave-one-out error follows from a single fit via the PRESS identity. Balancing the two known curves gives the minimizer analytically. We extend this calculus to many coordinates by replacing ambient input dimension with interaction order, the number of active low-order components in an ANOVA decomposition, yielding a scaling law in which the optimal resolution and error are power functions of the effective density (sample size per active component), with input dimension absent from the exponent. The law becomes an algorithm. KORE (Kolmogorov-optimal Order-aware Resolution Estimation) fits two pilot resolutions, solves a leverage-calibrated 2x2 system for the bias and noise scales, and evaluates the closed-form plug-in resolution with a tiny leave-one-out certificate: about a dozen fits instead of a full grid sweep, with a consistency guarantee as the sample grows. Across additive and sparse pairwise targets up to 80 input dimensions, KORE matches exhaustive 3-fold cross-validation and the full classical ladder (GCV, Mallows' Cp, AIC, BIC) while fitting roughly 8x fewer models; on 36 real tabular datasets it ranks first among 21 methods in accuracy per unit of compute, ahead of tuned boosters and kernel machines. When complexity lives in low interaction order, solving for the resolution beats searching for it.

Yong Yi Bay, Kathleen A. Yearick

PhD, University of Illinois at Urbana-Champaign

Model Selection Scaling Laws Statistical Learning Theory Hyperparameter Optimization Tabular Regression

Jun 22, 2026stat.ML

Sublinearly Structured Deep Neural Networks Achieve Feature Learning Consistency for Compositional Functions

Over the past decade, deep neural networks (DNNs) have achieved remarkable success on complex machine-learning tasks, yet the theoretical foundations of their performance remain incomplete. From a statistical viewpoint, a natural question is: can DNNs attain feature-learning and prediction consistency comparable to that of classical models? While a full characterization is open, we provide positive results for a broad subclass. We establish feature-learning consistency guarantees for sublinearly structured DNNs-architectures whose input/output dimensions and number of hidden neurons grow sublinearly with the sample size-when learning hierarchically compositional target functions. Importantly, this consistency still holds even in the conventional "over-parameterized" regime where the total number of parameters exceeds the number of training samples. Empirically, sublinearly structured DNNs match or surpass wide DNNs in prediction. A structural audit further indicates that widely used convolutional neural networks (CNNs), including AlexNet, VGGNet, ResNet, GoogLeNet, are sublinearly structured on their image classification benchmarks. We further prove that the sublinearly structured DNNs achieve universal approximation for hierarchically compositional functions in the large-sample limit. Moreover, images exhibit an inherent hierarchical, compositional structure. Taken together, these results explain, through a statistical lens, why many large-scale deep learning models succeed after adequate training on massive image datasets.

Sehwan Kim, Yan Sun, Faming Liang

Ewha Womans University, Seoul 03760, Republic of Korea · New Jersey Institute of Technology, Newark, NJ 07102, USA · Purdue University, West Lafayette, IN 47907, USA

Neural Network Generalization Hierarchical Representation Learning Statistical Learning Theory Compositional Representation Learning

Jun 22, 2026cs.LG

Non-asymptotic estimates of the minimal risk in statistical learning

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

n

is much greater than the box dimension of the parameter set

Θ

in the Orlicz metric

d_{ψ_1}

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

Liming Wu, Sen Yang

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

Statistical Learning Theory Empirical Risk Minimization Generalization Bounds

Jun 22, 2026math.ST

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

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

Ioannis Kalogridis

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

Nonparametric Regression Reproducing Kernel Hilbert Spaces Kernel Methods Statistical Learning Theory