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

Sep 22, 2025stat.ML

Effects of Structural Allocation of Geometric Task Diversity in Linear Meta-Learning Models

Meta-learning aims to leverage information across related tasks to improve prediction on unlabeled data for new tasks when only a small number of labeled observations are available ("few-shot" learning). Increased task diversity is often believed to enhance meta-learning by providing richer information across tasks. However, recent work by Kumar et al. (2022) shows that increasing task diversity, quantified through the overall geometric spread of task representations, can in fact degrade meta-learning prediction performance across a range of models and datasets. In this work, we build on this observation by showing that meta-learning performance is affected not only by the overall geometric variability of task parameters, but also by how this variability is allocated relative to an underlying low-dimensional structure. Similar to Pimonova et al. (2025), we decompose task-specific regression effects into a structurally informative component and an orthogonal, non-informative component. We show theoretically and through simulation that meta-learning prediction degrades when a larger fraction of between-task variability lies in orthogonal, non-informative directions, even when the overall geometric variability of tasks is held fixed.

Saptati Datta, Nicolas W. Hengartner, Yulia Pimonova +2

Department of Statistics, Texas A&M University, TX, USA · Los Alamos National Laboratory, Los Alamos, USA.

Meta-Learning Few-Shot Learning Statistical Learning Theory

Sep 14, 2025stat.ML

A Kernel-based Stochastic Approximation Framework for Nonlinear Operator Learning

We develop a stochastic approximation framework for learning nonlinear operators between infinite-dimensional spaces utilizing general Mercer operator-valued kernels. Our framework encompasses two key classes: (i) operator-valued kernels whose associated integral operators are compact and hence admit discrete spectral decompositions, and (ii) separable kernels of the form

K(x,x')=k(x,x')T

, where

k

is a scalar-valued kernel and

T

is a positive operator on the output space. This broad setting induces expressive vector-valued reproducing kernel Hilbert spaces (RKHSs) that generalize the classical

K=kI

paradigm, thereby enabling rich structural modeling with rigorous theoretical guarantees. To address target operators lying outside the RKHS, we introduce vector-valued interpolation spaces to precisely quantify misspecification error. Within this framework, we establish non-asymptotic convergence rates for prediction, estimation, and misspecification errors in the online and finite-horizon settings. Importantly, the framework also accommodates a range of operator learning settings, from Fredholm integral operators to encoder--decoder architectures. Numerical experiments on the two-dimensional Navier--Stokes equations illustrate the proposed approach.

Jia-Qi Yang, Lei Shi

School of Mathematical Sciences and Shanghai Key Laboratory for Contemporary Applied Mathematics, Fudan University, Shanghai 200433, China.

Stochastic Approximation Reproducing Kernel Hilbert Spaces Kernel Methods Operator Learning Statistical Learning Theory

Jul 10, 2025cond-mat.dis-nn

A statistical physics framework for optimal learning

Learning is a complex dynamical process shaped by a range of interconnected decisions. Careful design of hyperparameter schedules for artificial neural networks or efficient allocation of cognitive resources by biological learners can dramatically affect performance. Yet, theoretical understanding of optimal learning strategies remains sparse, especially due to the intricate interplay between evolving metaparameters and nonlinear learning dynamics. The search for optimal protocols is further hindered by the high dimensionality of the learning space, often resulting in predominantly heuristic, difficult to interpret, and computationally demanding solutions. Here, we combine statistical physics with control theory in a unified theoretical framework to identify optimal learning protocols in prototypical neural network models. In the high-dimensional limit, we derive closed-form ordinary differential equations that track online stochastic gradient descent through low-dimensional order parameters. We formulate the design of learning protocols as an optimal control problem directly on the dynamics of the order parameters with the goal of minimizing the generalization error. This formulation encompasses a variety of learning scenarios, optimization constraints, and control budgets. We apply it to representative cases, including optimal curricula, adaptive dropout regularization and noise schedules in denoising autoencoders. We find nontrivial yet interpretable strategies highlighting how optimal protocols mediate learning trade-offs. Our results establish a principled foundation for understanding and designing optimal protocols and suggest a path toward a theory of meta-learning grounded in statistical physics.

Francesca Mignacco, Francesco Mori

1Joseph Henry Laboratories of Physics, Princeton University, Princeton, NJ 08544, USA · 2Graduate Center, City University of New York, New York, NY 10016, USA · Center of Mathematical Sciences and Applications, Harvard University, Cambridge, MA 02138, USA

Statistical Physics of Learning Neural Network Training Dynamics Statistical Learning Theory Optimal Control Hyperparameter Optimization

Jul 9, 2025stat.ML

Adaptively Truncated Signature-based Logistic Regression for Semi-parametric Functional Classification

Modern sensing technologies routinely generate multi-dimensional functional data, often accompanied by scalar covariates, motivating statistical methods that can jointly accommodate nonlinear functional effects, complex cross-component dependencies, and irregular sampling patterns. Existing functional logistic regression approaches rely on basis expansions whose performance is critically sensitive to the choice of basis, smoothing parameters, and sampling design; meanwhile, current signature-based methods require heuristic selection of the signature truncation order. We propose Adaptively Truncated Signature-based Logistic Regression (ATSLR), a semi-parametric classification framework that integrates path-signature representations with a data-driven procedure for selecting the signature truncation order via penalized empirical risk minimization. Our method is supported by rigorous theoretical guarantees, including the existence of an optimal truncation order, consistency of its adaptive estimator, convergence rates for the classifier risk, a finite and computable search bound, and a general error-propagation analysis for irregular sampling. Experiments on synthetic and real-world datasets demonstrate that our framework consistently outperforms traditional functional classifiers and fixed-order signature baselines in accuracy, robustness, and interpretability. Our results highlight the practical and theoretical value of integrating rough path theory with adaptive model complexity control.

Pengcheng Zeng, Siyuan Jiang

Institute of Mathematical Sciences, ShanghaiTech University, Shanghai, China

Statistical Learning Theory

Jun 14, 2025stat.ML

On the Existence of Consistent Adversarial Attacks in High-Dimensional Linear Classification

What fundamentally distinguishes an adversarial attack from a misclassification due to limited model expressivity or finite data? In this work, we investigate this question in the setting of high-dimensional binary classification, where statistical effects due to limited data availability play a central role. We introduce a new error metric that precisely capture this distinction, quantifying model vulnerability to consistent adversarial attacks -- perturbations that preserve the ground-truth labels. Our main technical contribution is an exact and rigorous asymptotic characterization of these metrics in both well-specified models and latent space models, revealing different vulnerability patterns compared to standard robust error measures. The theoretical results demonstrate that as models become more overparameterized, their vulnerability to label-preserving perturbations grows, offering theoretical insight into the mechanisms underlying model sensitivity to adversarial attacks.

Matteo Vilucchio, Lenka Zdeborová, Bruno Loureiro

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

Adversarial Attacks Adversarial Robustness Adversarial Perturbations Consistent Adversarial Attacks Statistical Learning Theory

May 26, 2025stat.ML

No Free Lunch: Non-Asymptotic Analysis of Prediction-Powered Inference

Prediction-Powered Inference (PPI) is a popular strategy for combining gold-standard and possibly noisy pseudo-labels to perform statistical estimation. Prior work has shown an asymptotic \enquote{free lunch} for PPI++, an adaptive form of PPI, showing that the \textit{asymptotic} variance of PPI++ is always less than or equal to the variance obtained from using gold-standard labels alone. Notably, this result holds \textit{regardless of the quality of the pseudo-labels}. In this work, we demystify this result by conducting an exact finite-sample analysis of the estimation error of PPI++ on the mean estimation problem. We give a \enquote{no free lunch} result, characterizing the settings (and sample sizes) where PPI++ has provably worse estimation error than using gold-standard labels alone. Specifically, PPI++ will outperform if and only if the correlation between pseudo- and gold-standard is above a certain level that depends on the number of labeled samples (

n

). In some cases our results simplify considerably: For Gaussian data, for instance, the correlation must be at least

1/\sqrt{n - 2}

in order to see improvement. More broadly, by providing exact non-asymptotic expressions for the variance of PPI++ under sample splitting, we aim to empower practitioners to transparently reason about the benefits of PPI++ in specific applications. In experiments, we illustrate that our theoretical findings hold on real-world datasets.

Pranav Mani, Peng Xu, Zachary C. Lipton +1

Abridge AI, San Francisco, CA, USA · Machine Learning Department, Carnegie Mellon University, Pittsburgh, PA, USA · Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA

Adaptive Inference Statistical Learning Theory Prediction-Powered Inference

May 26, 2025cs.LG

Representation Learning for Equivariant Inference with Guarantees

In many real-world applications of regression, conditional probability estimation, and uncertainty quantification, exploiting symmetries rooted in physics or geometry can dramatically improve generalization and sample efficiency. While geometric deep learning has made empirical advances by incorporating symmetry and geometry priors, less attention has been given to statistical learning guarantees. In this paper, we introduce an equivariant representation learning framework that simultaneously addresses regression, conditional probability estimation, and uncertainty quantification while providing first-of-its-kind non-asymptotic statistical learning guarantees. Grounded in operator and group representation theory, our framework approximates the spectral decomposition of the conditional expectation operator, building representations that are both equivariant and disentangled along independent symmetry quotient groups. Empirical evaluations on synthetic datasets and real-world robotics applications confirm the potential of our approach, matching or outperforming existing equivariant baselines in regression while providing well-calibrated uncertainty estimates.

Daniel Ordoñez-Apraez, Vladimir Kostić, Alek Fröhlich +3

CSML, Italian Institute of Technology, Genova, Italy · Universit`a di Genova, Genova, Italy · University of Novi Sad, Novi Sad, Serbia +2

Disentangled Representation Learning Representation Learning Uncertainty Quantification Conditional Distribution Estimation Equivariant Representation Learning Statistical Learning Theory

May 19, 2025cs.LG

When majority rules, minority loses: bias amplification of gradient descent

Despite growing empirical evidence of bias amplification in machine learning, its theoretical foundations remain poorly understood. We develop a formal framework for majority-minority learning tasks, showing how standard training can favor majority groups and produce stereotypical predictors that neglect minority-specific features. Assuming population and variance imbalance, our analysis reveals three key findings: (i) the close proximity between ``full-data'' and stereotypical predictors, (ii) the dominance of a region where training the entire model tends to merely learn the majority traits, and (iii) a lower bound on the additional training required. Our results are illustrated through experiments in deep learning for tabular and image classification tasks.

François Bachoc, Jérôme Bolte, Ryan Boustany +1

LPP · University of Lille · Institut Universitaire de France (IUF) +6

Class-Imbalanced Learning Gradient Descent Algorithmic Bias Classification Statistical Learning Theory

Apr 23, 2025cs.LG

The Dynamics of Generalization in Deep Learning

We derive a differential equation that governs the evolution of the generalization gap when a model is trained by gradient descent-based methods. This differential equation is driven by two key quantities, a contraction factor that brings together trajectories corresponding to slightly different datasets, and a perturbation factor that accounts for them training on different datasets. The coupled decay of contraction and perturbation guarantees a controlled accumulation of generalization gap during training. We analyze this differential equation to show that the generalization gap is given by a quadratic form that consists of an ``effective Gram matrix'' that depends upon the training trajectory and a certain residual of the predictor at initialization. Our framework is applicable to general deep networks and smooth loss functions. In numerical experiments on different neural network architectures, datasets and sample sizes, we show that this quadratic form accurately captures the actual generalization gap. We also show how to instantiate our framework in a number of examples via analytical calculations. For example, for high-dimensional linear regression, our framework matches existing calculations of generalization gap in the literature exactly in under-parameterized, over-parameterized and critical regimes.

Rubing Yang, Pratik Chaudhari

Department of Applied Mathematics and Computational Sciences, University of Pennsylvania Philadelphia, PA, 19104, USA · Department of Electrical and Systems Engineering, University of Pennsylvania Philadelphia, PA, 19104, USA

Neural Network Generalization Neural Network Training Dynamics Statistical Learning Theory Gradient Descent Dynamics

Apr 11, 2025cs.GT

Learning in Structured Stackelberg Games

We initiate the study of structured Stackelberg games, a novel form of strategic interaction between a leader and a follower where contextual information can be predictive of the follower's (unknown) type. Motivated by applications such as security games and AI safety, we show how this additional structure can help the leader learn a utility-maximizing policy in both the online and distributional settings. In the online setting, we first prove that standard learning-theoretic measures of complexity do not characterize the difficulty of the leader's learning task. Notably, we find that there exists a learning-theoretic measure of complexity, analogous to the Littlestone dimension in online classification, that tightly characterizes the leader's instance-optimal regret. We term this the Stackelberg-Littlestone dimension, and leverage it to provide a provably optimal online learning algorithm. In the distributional setting, we provide analogous results by showing that two new dimensions control the sample complexity upper- and lower-bound.

Maria-Florina Balcan, Kiriaki Fragkia, Keegan Harris

Carnegie Mellon University, Pittsburgh, USA · University of California, Berkeley, USA

Game Theory Stackelberg Games Statistical Learning Theory Online Learning

Feb 25, 2025stat.ML

Recursive Learning Without Collapse: A Weighting-Based Stabilization Framework

Recent studies identified an intriguing phenomenon in recursive generative model training known as model collapse, where models trained on data generated by previous models exhibit severe performance degradation. Addressing this issue and developing more effective training strategies have become central challenges in generative model research. In this paper, we investigate this phenomenon within a novel framework, where generative models are iteratively trained on a combination of newly collected real data and synthetic data from the previous training step. To develop an optimal training strategy for integrating real and synthetic data, we evaluate the performance of a weighted training scheme in various scenarios, including Gaussian distribution estimation, generalized linear models, and nonparametric estimation. We theoretically characterize the impact of the mixing proportion and weighting scheme of synthetic data on the final model's performance. Our key finding is that, across different settings, the optimal weighting scheme under different proportions of synthetic data asymptotically follows a unified expression, revealing a fundamental trade-off between leveraging synthetic data and model performance. In some cases, the optimal weight assigned to real data corresponds to the reciprocal of the golden ratio. Finally, we validate our theoretical results on extensive simulated datasets and a real tabular dataset.

Hengzhi He, Shirong Xu, Guang Cheng

Department of Statistics and Data Science, University of California, Los Angeles · Wang Yanan Institute for Studies in Economics, Xiamen University

Model Collapse Generative Modeling Statistical Learning Theory

Feb 21, 2025math.ST

Optimal and Provable Calibration in High-Dimensional Binary Classification: Angular Calibration and Platt Scaling

We study the fundamental problem of calibrating a linear binary classifier of the form

σ(\hat{w}^\top x)

, where the feature vector

x

is Gaussian,

σ

is a link function, and

\hat{w}

is an estimator of the true linear weight

w^\star

. By interpolating with a noninformative

\textit{chance classifier}

, we construct a well-calibrated predictor whose interpolation weight depends on the angle

\angle(\hat{w}, w_\star)

between the estimator

\hat{w}

and the true linear weight

w_\star

. We establish that this angular calibration approach is provably well-calibrated in a high-dimensional regime where the number of samples and features both diverge, at a comparable rate. The angle

\angle(\hat{w}, w_\star)

can be consistently estimated. Furthermore, the resulting predictor is uniquely

\textit{Bregman-optimal}

, minimizing the Bregman divergence to the true label distribution within a suitable class of calibrated predictors. Our work is the first to provide a calibration strategy that satisfies both calibration and optimality properties provably in high dimensions. Additionally, we identify conditions under which a classical Platt-scaling predictor converges to our Bregman-optimal calibrated solution. Thus, Platt-scaling also inherits these desirable properties provably in high dimensions.

Yufan Li, Pragya Sur

Department of Statistics Harvard University Cambrdige, MA 02138

Probability Calibration Binary Classification Statistical Learning Theory

Jan 18, 2025stat.ML

Fixed-Gaussian Spectral Algorithms: Minimax Optimal Rates for Misspecified Learning and Transfer

The principal objective of this work is twofold within nonparametric regression settings: (1) to establish the minimax optimal convergence rates for fixed-bandwidth Gaussian kernel spectral algorithms when the true regression function resides in a Sobolev space, and (2) to apply Gaussian spectral algorithms for achieving robust and adaptive transfer learning under concept shift. While minimax optimality of misspecified spectral algorithms has been established, existing guarantees are typically restricted to the non-saturation regime. We demonstrate that the infinite smoothness of fixed-bandwidth Gaussian kernels provides universal robustness to model misspecification by showing that this kernel choice enables any spectral algorithm to attain minimax optimal rates, provided the regularization parameter decays exponentially. This result effectively decouples optimality from the algorithm's inherent qualification. Building on this, we then advocate Gaussian spectral algorithms as powerful components in a learning framework for robust and adaptive transfer. Specifically, we derive the adaptive convergence rate of the excess risk for this framework and show that the rates are optimal up to logarithmic factors. Our results also reveal the impact of the magnitude of the concept shift and the sample size on the generalization error.

Haotian Lin, Matthew Reimherr

Department of Statistics, The Pennsylvania State University.

Spectral Regularization Concept Drift Transfer Learning Kernel Methods Spectral Methods Statistical Learning Theory

Nov 18, 2024cs.LG

The Method of Gaps: Exact Expressions for the Generalization Error of Supervised Learning Algorithms

In this paper, the method of gaps, a technique for deriving closed-form expressions in terms of information measures for the generalization error of supervised learning algorithms, is introduced. This method relies on the notion of gaps, which characterize the variation of the expected empirical risk (when either the model or dataset is kept fixed) with respect to changes in the probability measure on the varying parameter. This distinction results in two classes of gaps: algorithm-driven gaps (fixed dataset) and data-driven gaps (fixed model). The method relies on two central observations: (i) the generalization error is the expectation of an algorithm-driven gap or a data-driven gap. In the first case, the expectation is with respect to a measure on the datasets; in the second case, it is with respect to a measure on the models. (ii) Both algorithm-driven gaps and data-driven gaps exhibit closed-form expressions in terms of relative entropies. In particular, algorithm-driven gaps involve a Gibbs probability measure on the set of models, which represents a supervised Gibbs algorithm. Alternatively, data-driven gaps involve a worst-case data-generating (WCDG) probability measure on the set of data points, which is also a Gibbs probability measure. Interestingly, such Gibbs measures, which are exogenous to the analysis of generalization, place the supervised Gibbs algorithm and the WCDG probability measure as natural references for the analysis of supervised learning algorithms. New exact expressions and all existing exact expressions for the generalization error of supervised learning algorithms can be obtained with the proposed method. Such new expressions are intended as structural and conceptual characterizations, not computational shortcuts. Finally, these expressions unveil strong connections among generalization, hypothesis testing, information measures, and Pythagorean identities.

Samir M. Perlaza, Xinying Zou

INRIA, Centre Inria d’Universit´e Cˆote d’Azur, 06902 Sophia Antipolis, France

Information-Theoretic Generalization Bounds Statistical Learning Theory Generalization Bounds

Oct 17, 2024stat.ML

Discrete distributions are learnable from metastable samples

Physically motivated stochastic dynamics are widely used to sample from high-dimensional distributions. However, such samplers often get trapped in metastable states, approximately sampling from a distribution that differs significantly from the desired stationary state. We rigorously show that for multivariable discrete distributions, the true stationary model can nevertheless be recovered from these metastable samples. This relies on a fundamental observation: for distributions satisfying a strong metastability condition, their single-variable conditional probabilities are on average extremely close to those of the true stationary distribution. This remains true even when the two distributions are far apart under global metrics such as Kullback-Leibler divergence. Consequently, we can effectively learn the true model using a conditional-likelihood estimator even when the samples are drawn from a restricted state space. Extending these general results to Ising models, we prove rigorous parameter and structure learning guarantees. Finally, we demonstrate this phenomenon numerically on higher-alphabet spin glass models.

Abhijith Jayakumar, Andrey Y. Lokhov, Sidhant Misra +1

Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA

Conditional Distribution Estimation Statistical Learning Theory

Oct 17, 2024cs.LG

Adaptive and oblivious statistical adversaries are equivalent

We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the types of corruption they can make and their level of knowledge about the sample. The latter distinguishes between sample-adaptive adversaries which know the contents of the sample when choosing the corruption, and sample-oblivious adversaries, which do not. We prove that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are \emph{equivalent} up to polynomial factors in the sample size. This resolves the main open question introduced by [BLMT22] and further explored in [CHL+23]. Specifically, consider any algorithm

A

that solves a statistical task even when a sample-oblivious adversary corrupts its input. We show that there is an algorithm

A'

that solves the same task when the corresponding sample-adaptive adversary corrupts its input. The construction of

A'

is simple and maintains the computational efficiency of

A

: It requests a polynomially larger sample than

A

uses and then runs

A

on a uniformly random subsample.

Guy Blanc, Gregory Valiant

Stanford

Statistical Learning Theory

Oct 15, 2024stat.ML

On Generalisation Error Bounds for Transformers

In this paper, we establish a collection of covering number bounds for linear function classes under various norm constraints on the inputs and matrices. We then combine these results with existing covering number bounds to derive improved estimates and, based on these estimates, develop generalization error bounds for single-layer Transformers. The resulting generalization bounds improve upon several existing results in the literature and, in particular, are independent of the input sequence length. Moreover, our generalization error bound decays at the rate

O(1/\sqrt{n})

, where

n

denotes the sample size, thereby improving upon existing bounds that scale as

O((\log n)/\sqrt{n})

. Furthermore, our covering number analysis explicitly incorporates rank constraints on the underlying matrix classes, allowing us to characterize how low-rank structures affect the metric entropy and, consequently, the resulting generalization bounds for Transformer architectures.

Lan V. Truong

Faculty of Computer Science and Engineering, Ho Chi Minh City University of Technology (HCMUT), Vietnam

Transformer Statistical Learning Theory Generalization Bounds

Oct 14, 2024math.NA

Which Spaces can be Embedded in $L_p$ -type Reproducing Kernel Banach Space? A Characterization via Metric Entropy

In this paper, we establish a novel connection between the metric entropy growth and the embeddability of function spaces into reproducing kernel Hilbert/Banach spaces. Metric entropy characterizes the information complexity of function spaces and has implications for their approximability and learnability. Classical results show that embedding a function space into a reproducing kernel Hilbert space (RKHS) implies a bound on its metric entropy growth. Surprisingly, we prove a \textbf{converse}: a bound on the metric entropy growth of a function space allows its embedding to a

L_p-

type Reproducing Kernel Banach Space (RKBS). This shows that the

{L}_p-

type RKBS provides a broad modeling framework for learnable function classes with controlled metric entropies. Our results shed new light on the power and limitations of kernel methods for learning complex function spaces.

Yiping Lu, Daozhe Lin, Qiang Du

Industrial Engineering & Management Sciences, Northwestern University · Department of Applied Physics & Applied Mathematics, Columbia University

Reproducing Kernel Hilbert Spaces Kernel Methods Statistical Learning Theory

Oct 14, 2024stat.ML

Statistical Properties of Deep Neural Networks with Dependent Data

This paper develops theory for deep neural network (DNN) estimators under dependent data. To provide theory applicable to a variety of DNN-based estimators, I first establish nonasymptotic probability bounds on the theoretical and empirical

\mathcal{L}^{2}

-errors of nonparametric sieve estimators for a general class of estimation problems under possibly nonstationary

β

-mixing data taking values in unbounded sets. I then apply the theory to fully connected and convolutional DNN estimators without bounds or sparsity restrictions on the DNN weights. For both DNN classes, I derive general results when the function to be estimated is Hölder smooth and the data are nonstationary, subgaussian, and

β

-mixing with either exponential or polynomial decay. I then specialize these to nonparametric regression, logistic regression, and quantile regression settings. Under exponential

β

-mixing, the resulting estimators attain the nonparametric minimax rate of Stone (1982) up to logarithmic factors.

Chad Brown

Department of Economics, University of Colorado Boulder, 80309, USA.

Nonparametric Regression Neural Network Approximation Theory Statistical Learning Theory

Sep 16, 2024stat.ML

The EM-algorithm and the Method of Moments in Softmax Mixture Models

Softmax Mixture Models (SMMs) are discrete

K

-component mixture models for the probabilities of selecting one of

p

candidate feature vectors

X_1,\ldots,X_p\in\mathbb{R}^L

in heterogeneous populations and are widely used in econometrics and scientific applications. Related softmax mixture mechanisms also appear in modern LLM architectures. We provide a theoretical and methodological study of SMMs, focusing on the Expectation-Maximization (EM) algorithm and the Method of Moments (MoM). We show that EM recovers the mixture atoms at the parametric rate, up to logarithmic factors, after

\mathcal{O}(\log N)

iterations, provided atom separation is at least of order

\log K

. This improves on separation conditions in existing analyses of EM for high-dimensional Gaussian mixtures. We also develop MoM procedures for parameter and subspace estimation. Although MoM parameter estimates converge more slowly than EM and can deteriorate with

K

, they provide provable warm starts for EM and are useful for small

K

. For general

K

, we estimate the atom subspace via MoM and recommend running EM from multiple random initializations within this subspace. Finally, as

p\to\infty

, we show that SMMs approximate mixtures of exponential tilts of the feature distribution, yielding asymptotic identifiability.

Xin Bing, Florentina Bunea, Jonathan Niles-Weed +1

Department of Statistical Sciences, University of Toronto · Department of Statistics and Data Science, Cornell University · Courant Institute of Mathematical Sciences and Center for Data Science, New York University +1

Expectation-Maximization Discrete Choice Modeling Statistical Learning Theory

Jul 8, 2024math.DS

Adversarial dynamical systems characterize when data-driven learning succeeds or fails

Many systems resist analytical modeling, making data-driven inference of dynamics important. Yet data-driven methods can fail to converge or generalize, leaving open a central question: When can system behavior be learned reliably from data, and when is such learning impossible? We answer this question using adversarial dynamical systems to identify the boundary between accessible and inaccessible regimes. In Koopman operator learning, a leading framework for representing nonlinear dynamics through linear spectral objects, we design optimal data-driven spectral algorithms with convergence and certification guarantees under conditions arising broadly in physical systems. This yields a convergence theory for Koopman-operator approximations and resolves a longstanding open problem in Koopman spectral analysis. Conversely, by constructing adversarial systems, we prove matching impossibility results: without these conditions, no single-sequence limiting procedure can guarantee learning, regardless of data quality. These results sharply characterize when data-driven spectral learning can succeed and when it must fail. We validate the framework on oscillators, chaotic fluid flows and Arctic sea ice concentration forecasting. In the latter, we uncover hidden modes of Arctic sea ice decline, deliver long-range forecasts with geographic error bounds, and outperform state-of-the-art dynamical and deep learning models at substantially lower computational cost, enabling real-time deployment on standard CPUs.

Matthew J. Colbrook, Igor Mezić, Alexei Stepanenko

DAMTP, University of Cambridge, Cambridge, CB3 0WA, UK. · University of California, Santa Barbara, CA 93106, USA.

Koopman Operator Learning Spectral Methods Statistical Learning Theory Chaotic Time-Series Prediction

Jul 1, 2024cs.LG

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension

In traditional models of supervised learning, the goal of a learner-- given examples from an arbitrary joint distribution on

\mathbb{R}^d \times \{\pm 1\}

-- is to output a hypothesis that is competitive (to within

ε

) of the best fitting concept from some class. In order to escape strong hardness results for learning even simple concept classes, we introduce a smoothed-analysis framework that requires a learner to compete only with the best classifier that is robust to small random Gaussian perturbation. This subtle change allows us to give a wide array of learning results for any concept that (1) depends on a low-dimensional subspace (aka multi-index model) and (2) has a bounded Gaussian surface area. This class includes functions of halfspaces and (low-dimensional) convex sets, cases that are only known to be learnable in non-smoothed settings with respect to highly structured distributions such as Gaussians. Our definition of smoothed agnostic learning is an interpolation between the case where the instance distribution

D

and the optimal classifier can be arbitrarily coupled (which corresponds to agnostic learning and

σ= 0

) and completely decoupled (when

σ= \infty

). This decoupling allows us to avoid worst-case concepts that can encode complexity-theoretic primitives. Surprisingly, our analysis also yields new results for traditional non-smoothed frameworks such as learning with margin. In particular, we obtain the first algorithm for agnostically learning intersections of

k

-halfspaces in time

k^{\mathrm{poly}(\frac{\log k}{εγ}) }

where

γ

is the margin parameter. Before our work, the best-known runtime was exponential in

k

(Arriaga and Vempala, FOCS' 99).

Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis +2

a University of Texas at Austin · b University of California, Los Angeles

Statistical Learning Theory Multi-Index Models

Jun 20, 2024math.ST

Generalization error of min-norm interpolators in transfer learning

This paper establishes the generalization error of pooled min-

\ell_2

-norm interpolation in transfer learning, where data from diverse distributions are available. Min-norm interpolators arise naturally as implicit regularized limits of modern machine learning algorithms. Prior work has characterized their out-of-distribution risk when samples from the test distribution are unavailable during training. In many applications, however, limited test samples may be available at training time, yet properties of min-norm interpolation in this regime remain poorly understood. We address this gap by characterizing the bias and variance of pooled min-

\ell_2

-norm interpolation under both covariate shift and model shift. Our results yield several important implications. In certain cases under model shift, we show that adding data always hurts when the signal-to-noise ratio (SNR) is low. At higher SNR levels, transfer learning is beneficial provided the shift-to-signal ratio falls below a threshold that we characterize explicitly. Under covariate shift, we find that when the source sample size is small relative to the dimension, greater heterogeneity between domains reduces risk, and vice versa. While our model shift results are initially established for Gaussian designs, we extend them to more general designs through a universality argument. To illustrate the broader applicability of our technical tools beyond interpolation learning, we characterize the risk of a bias-corrected estimator that uses the pooled interpolator as an initialization and corrects the resulting bias with target data. On the technical side, we develop a novel anisotropic local law and a Lindeberg-swapping argument, yielding tools that may be of independent interest in random matrix theory and universality analysis. Finally, we supplement our theory with simulations demonstrating the finite-sample efficacy of our results.

Yanke Song, Kenneth Gu, Sohom Bhattacharya +1

Department of Statistics, Harvard University · Department of Statistics, Stanford University · Department of Statistics, University of Florida

OOD Generalization Cross-Domain Transfer Learning Transfer Learning Statistical Learning Theory

Mar 22, 2024stat.ML

Estimation of multiple mean vectors in high dimension

We endeavour to estimate numerous multi-dimensional means of various probability distributions on a common space based on independent samples. Our approach involves forming estimators through convex combinations of empirical means derived from these samples. We introduce two strategies to find appropriate data-dependent convex combination weights: a first one employing a testing procedure to identify neighbouring means with low variance, which results in a closed-form plug-in formula for the weights, and a second one determining weights via minimization of an upper confidence bound on the quadratic risk. Through theoretical analysis, we evaluate the improvement in quadratic risk offered by our methods compared to the empirical means. Our analysis focuses on a dimensional asymptotics perspective, showing that our methods asymptotically approach an oracle (minimax) improvement as the effective dimension of the data increases. We demonstrate the efficacy of our methods in estimating multiple kernel mean embeddings through experiments on both simulated and real-world datasets.

Gilles Blanchard, Jean-Baptiste Fermanian, Hannah Marienwald

LMO, DATASHAPE · Université Paris Saclay, Institut Mathématique d’Orsay, France. · LMO +2

Kernel Mean Embeddings Statistical Learning Theory

Mar 16, 2024cs.LG

A Probabilistic Approach for Model Alignment with Human Comparisons

A growing trend involves integrating human knowledge into learning frameworks, leveraging subtle human feedback to refine AI models. While these approaches have shown promising results in practice, the theoretical understanding of when and why such approaches are effective remains limited. This work takes steps toward developing a theoretical framework for analyzing the conditions under which human comparisons can enhance the traditional supervised learning process. Specifically, this paper studies the effective use of noisy-labeled data and human comparison data to address challenges arising from noisy environment and high-dimensional models. We propose a two-stage "Supervised Learning+Learning from Human Feedback" (SL+LHF) framework that connects machine learning with human feedback through a probabilistic bisection approach. The two-stage framework first learns low-dimensional representations from noisy-labeled data via an SL procedure and then uses human comparisons to improve the model alignment. To examine the efficacy of the alignment phase, we introduce a concept, termed the "label-noise-to-comparison-accuracy" (LNCA) ratio. This paper identifies from a theoretical perspective the conditions under which the "SL+LHF" framework outperforms the pure SL approach; we then leverage this LNCA ratio to highlight the advantage of incorporating human evaluators in reducing sample complexity. We validate the framework on a real high-dimensional crowdfunding-prediction task: under a fixed query budget, trading labels for comparisons improves accuracy precisely when labels are scarce, and the findings hold when the evaluator is replaced by real large language models. A study conducted via Amazon Mechanical Turk (MTurk) further validates the model primitives.

Junyu Cao, Mohsen Bayati

McCombs School of Business, The University of Texas at Austin · Graduate School of Business, Stanford University

Human Preference Modeling Statistical Learning Theory Preference Learning

Jul 24, 2023stat.ML

A Differentially Private Weighted Empirical Risk Minimization Procedure and its Application to Outcome Weighted Learning

Data used to train predictive models via empirical risk minimization (ERM) often contain sensitive personal information. While differential privacy (DP) provides mathematically provable bounds to protect such data, previous work has focused almost exclusively on unweighted ERM. We consider weighted ERM (wERM) -- an important generalization where individual contributions to the objective function vary. We propose the first DP algorithm for general wERM with formal privacy guarantees and derive both its empirical and population excess risk bounds. Crucially, this general wERM framework provides a pathway for deriving privacy-preserving learning methods for individualized treatment rules, including the popular outcome-weighted learning (OWL) approach. We evaluate DP-wERM applied to OWL in simulated and real data experiments. Our empirical results demonstrate that training OWL models via wERM provides strong DP guarantees while maintaining robust performance, proving the method is practical for sensitive, real-world data.

Spencer Giddens, Yiwang Zhou, Kevin R. Krull +3

University of Notre Dame, Notre Dame, IN 46556, USA · St. Jude Children’s Research Hospital, Memphis, TN 38138, USA · University of Michigan, Ann Arbor, MI 48109, USA

Privacy-Preserving ML Differential Privacy Statistical Learning Theory Empirical Risk Minimization

Apr 6, 2023cs.LG

Reliable learning in challenging environments

The problem of designing learners that provide guarantees that their predictions are provably correct is of increasing importance in machine learning. However, learning theoretic guarantees have only been considered in very specific settings. In this work, we consider the design and analysis of reliable learners in challenging test-time environments as encountered in modern machine learning problems: namely adversarial' test-time attacks (in several variations) and natural' distribution shifts. In this work, we provide a reliable learner with provably optimal guarantees in such settings. We discuss practical implementations of the learner and further show that our algorithm achieves strong positive performance guarantees on several natural examples: for example, linear separators under log-concave distributions or smooth boundary classifiers under smooth probability distributions.

Maria-Florina Balcan, Steve Hanneke, Rattana Pukdee +1

Carnegie Mellon University · Purdue University

Distribution Shift Robustness Adversarial Robustness Statistical Learning Theory

Mar 15, 2023stat.ML

Distribution-free Deviation Bounds and The Role of Domain Knowledge in Learning via Model Selection with Cross-validation Risk Estimation

Cross-validation is one of the most widely used tools for risk estimation and model selection in statistics and machine learning, yet its theoretical properties when embedded in a learning procedure remain insufficiently understood. This paper develops a general, distribution-free framework for learning via model selection with cross-validation risk estimation within classical statistical learning theory. We establish VC dimension-based deviation bounds for the entire learning pipeline, providing detailed proofs for both bounded and unbounded loss functions, the latter requiring a novel extension of existing results. A central focus of the analysis is how the structure of the collection of candidate models influences generalization. To this end, we introduce Learning Spaces as collections of candidate models equipped with a partial order whose inclusion structure reflects increasing model complexity. We show how Learning Spaces can be constructed from domain knowledge and analyze how such structural information increases generalization. The framework is illustrated through case studies and a simulation study in high-dimensional linear regression, comparing learning via model selection in two distinct Learning Spaces against ordinary least squares, LASSO, and ridge regression across scenarios of varying alignment between prior knowledge and the true target. The results demonstrate that, when the Learning Space is well-adapted to the target and an efficient search algorithm is employed, learning via model selection can outperform standard methods by orders of magnitude. Through theoretical insights and concrete examples, we provide guidance on selecting the family of candidate models based on domain knowledge to enhance the performance of model selection with cross-validation.

Diego Marcondes, Cláudia Peixoto

Model Selection Statistical Learning Theory Generalization Bounds

Jun 24, 2022math.ST

How many labelers do you have? A closer look at gold-standard labels

The construction of most supervised learning datasets revolves around collecting multiple labels for each instance, then aggregating the labels to form a type of "true" label. We question the wisdom of this pipeline by developing a (stylized) theoretical model of this process and analyzing its statistical consequences, showing how access to non-aggregated label information can make training well-calibrated models more feasible than it is with cleaned labels. The entire story, however, is subtle, and the contrasts between aggregated and fuller label information depend on the particulars of the problem, where estimators that use aggregated information exhibit robust but slower rates of convergence, while estimators that can effectively leverage all labels converge more quickly if they have fidelity to (or can learn) the true labeling process. The theory makes several predictions for real-world datasets, including when non-aggregate labels should improve learning performance, which we test to corroborate the validity of our predictions.

Chen Cheng, Hilal Asi, John Duchi

Department of Statistics, Stanford University · Department of Electrical Engineering, Stanford University · Departments of Statistics and Electrical Engineering, Stanford University

Model Calibration Noisy-Label Learning Dataset Aggregation Statistical Learning Theory

Jun 9, 2022cs.LG

Learning Non-Vacuous Generalization Bounds from Optimization

One of the fundamental challenges in the deep learning community is to theoretically understand how well a deep neural network generalizes to unseen data. However, current approaches often yield generalization bounds that are either too loose to be informative of the true generalization error or only valid to the compressed nets. In this study, we present a simple yet non-vacuous generalization bound from the optimization perspective. We achieve this goal by leveraging that the hypothesis set accessed by stochastic gradient algorithms is essentially fractal-like and thus can derive a tighter bound over the algorithm-dependent Rademacher complexity. The main argument rests on modeling the discrete-time recursion process via a continuous-time stochastic differential equation driven by fractional Brownian motion. Numerical studies demonstrate that our approach is able to yield plausible generalization guarantees for modern neural networks such as ResNet and Vision Transformer, even when they are trained on a large-scale dataset (e.g. ImageNet-1K).

Chengli Tan, Jiangshe Zhang, Junmin Liu +1

Northwestern Polytechnical University, Xi’an, China · Xi’an Jiaotong University, Xi’an, China · SGIT AI Lab, State Grid Corporation of China, Xi’an, China

Neural Network Generalization Statistical Learning Theory Generalization Bounds