Statistical Learning Theory

Follow this topic Ask about this topic

Statistical learning theory asks when a learner can infer rules that work beyond its training data, and quantifies sample complexity, prediction error, and limits on what can be learned. Classical tools include VC and Littlestone dimensions, covering numbers, Rademacher complexity, stability, PAC-Bayes bounds, and minimax analysis; these provide guarantees for empirical risk minimization, online learning, kernels, and robust or private learning. Current work also studies high-dimensional and overparameterized regression, including interpolation and double descent, neural networks and Transformers, and learning under distribution shift, dependence, partial labels, or adaptive data. An enduring tension is that statistically optimal rates may be computationally unattainable, while guarantees for modern architectures often rely on idealized assumptions and may not explain practical optimization.

Latest papers

584 papers79 papers in the last four weeks, up 58% on the four weeks before. 0.5% of all new papers.

Sep 16, 2024

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

Ask PDF

Jul 8, 2024

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

Ask PDF

Jul 1, 2024

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

Agnostic Learning Margin-Based Learning Statistical Learning Theory Multi-Index Models

Ask PDF

Jun 20, 2024

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

Ask PDF

Mar 22, 2024

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 Shrinkage Estimation

Ask PDF

Mar 16, 2024

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

Ask PDF

Jul 24, 2023

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

Ask PDF

Apr 6, 2023

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

Ask PDF

Mar 15, 2023

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 Cross-Validation Statistical Learning Theory Generalization Bounds

Ask PDF

Jun 24, 2022

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 Supervised Learning

Ask PDF

Jun 9, 2022

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

Ask PDF

Feb 17, 2022

Universality of empirical risk minimization

We study a general class of optimization problems with decision variable

\boldsymbolΘ \in \mathbb{R}^{p \times k}

and cost function which is the sum of

n

terms, each dependent on

\boldsymbolΘ

through the

k

-dimensional projection

\boldsymbolΘ^\top \boldsymbol{x}_i

, where

\boldsymbol{x}_i

i \leq n

are i.i.d. random vectors. This setting is general enough to include examples of current interest in statistical physics, high-dimensional statistics, and statistical learning theory. We consider the proportional asymptotics

n, p \to \infty

, with

n/p = Θ(1)

, and prove that, whenever there exists a minimizer satisfying a suitable generalization of a "delocalization" condition, the minimum value is universal. Namely, (for subgaussian

\boldsymbol{x}_i

) it depends on the distribution of

\boldsymbol{x}_i

only through its asymptotic mean and covariance. This delocalization condition is essentially necessary. Earlier universality results for such problems were limited to strongly convex loss functions. We derive applications of our theory to statistical learning and prove general universality results both for train and (under additional conditions) test error. In particular, we establish universality for vectors

\boldsymbol{x}_i

generated by random 1-layer neural networks (random features models) and first-order Taylor approximations of 2-layer networks (neural tangent models). Finally, we establish that the delocalization property holds for a class of statistical learning problems under a condition that is easy to verify.

Andrea Montanari, Basil Saeed

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

Statistical Learning Theory Empirical Risk Minimization High-Dimensional Asymptotics

Ask PDF

Jan 6, 2022

Robust Linear Predictions: Analyses of Uniform Concentration, Fast Rates and Model Misspecification

The problem of linear predictions has been extensively studied for the past century under pretty generalized frameworks. Recent advances in the robust statistics literature allow us to analyze robust versions of classical linear models through the prism of Median of Means (MoM). Combining these approaches in a piecemeal way might lead to ad-hoc procedures, and the restricted theoretical conclusions that underpin each individual contribution may no longer be valid. To meet these challenges coherently, in this study, we offer a unified robust framework that includes a broad variety of linear prediction problems on a Hilbert space, coupled with a generic class of loss functions. Notably, we do not require any assumptions on the distribution of the outlying data points (

\mathcal{O}

) nor the compactness of the support of the inlying ones (

\mathcal{I}

). Under mild conditions on the dual norm, we show that for misspecification level

ε

, these estimators achieve an error rate of

O(\max\left\{|\mathcal{O}|^{1/2}n^{-1/2}, |\mathcal{I}|^{1/2}n^{-1} \right\}+ε)

, matching the best-known rates in literature. This rate is slightly slower than the classical rates of

O(n^{-1/2})

, indicating that we need to pay a price in terms of error rates to obtain robust estimates. Additionally, we show that this rate can be improved to achieve so-called "fast rates" under additional assumptions.

Saptarshi Chakraborty, Debolina Paul, Swagatam Das

Department of Statistics, University of California, Berkeley · Department of Statistics, Stanford University · Electronics and Communication Sciences Unit, Indian Statistical Institute, Kolkata, India

Robust Regression Model Misspecification Linear Regression Statistical Learning Theory Robust Estimation Robust Statistics

Ask PDF

Sep 6, 2021

A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning

The last decade of progress in machine learning (ML), especially the deep learning era, has raised a number of scientific questions that challenge the longstanding dogma of the field. One of the most important riddles was the good empirical generalization of overparameterized models. Overparameterized models are highly complex with respect to the size of the training dataset, which enables them to perfectly fit (i.e., interpolate) even noisy training data. Such interpolation of noisy data is traditionally associated with detrimental overfitting, and yet a wide range of interpolating models -- from simple linear models to deep neural networks -- have been observed to generalize remarkably well on fresh test data. Indeed, the discovery of the double descent phenomenon has revealed that highly overparameterized models can improve over the best underparameterized model in test performance. Understanding learning in this overparameterized regime required new theory and foundational empirical studies, even for the simplest case of the linear model. The underpinnings of this understanding have been laid in foundational analyses of overparameterized linear regression and related statistical learning tasks, mostly published between 2018 and 2022, which resulted in precise analytic characterizations of double descent. This paper provides an overview of the theory of overparameterized ML (henceforth abbreviated as TOPML) by focusing on explaining the most foundational findings through a statistical signal processing perspective. We emphasize the unique aspects that define the TOPML research area as a subfield of modern ML theory and outline interesting open frontiers that remain.

Yehuda Dar, Vidya Muthukumar, Richard G. Baraniuk

Faculty of Computer and Information Science, Ben-Gurion University · Schools of Electrical and Computer Engineering, and Industrial and Systems Engineering, Georgia Institute of Technology · Electrical and Computer Engineering Department, Rice University

Double Descent Neural Network Generalization Benign Overfitting Statistical Learning Theory Overparameterization

Ask PDF