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.

Interactive Learning of Single-Index Models via Stochastic Gradient Descent
Feb 19, 2026Nived Rajaraman, Yanjun HanSingle-Index Models Generalized Linear Bandits
Microsoft Research NYC · Courant Institute of Mathematical Sciences and Center for Data Science, New York University
Optimal Unconstrained Self-Distillation in Ridge Regression: Strict Improvements, Precise Asymptotics, and One-Shot Tuning
Feb 19, 2026Hien Dang, Pratik Patil, Alessandro RinaldoSelf-Distillation Statistical Learning Theory
Department of Statistics and Data Sciences, University of Texas, Austin, TX 78712, USA.
Bayesian Optimality of In-Context Learning with Selective State Spaces
Feb 19, 2026Di Zhang, Jiaqi XingIn-Context Learning Selective SSMs
School of AI and Advanced Computing Xi’an Jiaotong-Liverpool University Suzhou, Jiangsu, China
Semi-Supervised Learning on Graphs using Graph Neural Networks
Feb 19, 2026Juntong Chen, Claire Donnat, Olga Klopp +1Graph Neural Networks Graph-Based Semi-Supervised Learning
School of Mathematical Sciences, Xiamen University · Department of Statistics, University of Chicago · ESSEC Business School +1
Separating Oblivious and Adaptive Models of Variable Selection
Feb 18, 2026Ziyun Chen, Jerry Li, Kevin Tian +1Sparse Recovery Feature Selection
University of Washington · University of Texas at Austin
On the Power of Source Screening for Learning Shared Feature Extractors
Feb 18, 2026Leo Muxing Wang, Connor Mclaughlin, Lili SuShared Representation Learning Representation Learning
Northeastern University
Uniform error bounds for quantized dynamical models
Feb 17, 2026Abdelkader Metakalard, Fabien Lauer, Kevin Colin +1System Identification Generalization Bounds
CRAN, SYNALP · ∗Universit´e de Lorraine, CNRS, CRAN, F-54000 Nancy, France · ∗∗Universit´e de Lorraine, CNRS, LORIA, F-54000 Nancy, France +2
Scenario Approach with Post-Design Certification of User-Specified Properties
Feb 17, 2026Algo Carè, Marco C. Campi, Simone GarattiGeneralization Bounds Statistical Learning Theory
Department of Information Engineering - University of Brescia, via Branze 38, 25123 Brescia, Italia · Dipartimento di Elettronica, Informazione e Bioingegneria - Politecnico di Milano, piazza Leonardo da Vinci 32, 20133 Milano, Italia
Statistical Inference and Learning for Shapley Additive Explanations (SHAP)
Feb 11, 2026Justin Whitehouse, Ayush Sawarni, Vasilis SyrgkanisSHAP Feature Attribution Shapley Value Attribution
Management Science and Engineering, Stanford University
Fast Rates for Nonstationary Weighted Risk Minimization
Feb 5, 2026Tobias Brock, Thomas NaglerEmpirical Risk Minimization Statistical Learning Theory
LMU Munich Munich Center for Machine Learning (MCML)
Limitations of SGD for Multi-Index Models Beyond Statistical Queries
Feb 5, 2026Daniel Barzilai, Ohad ShamirSingle-Index Models Statistical Learning Theory
Weizmann Institute of Science · University of Toronto
PCA of probability measures: Sparse and Dense sampling regimes
Feb 2, 2026Gachon Erell, Jérémie Bigot, Elsa CazellesPrincipal Component Analysis Dimensionality Reduction
Institut de Mathématiques de Bordeaux, Université de Bordeaux, CNRS (UMR 5251) · CNRS, IRIT (UMR 5505), Université de Toulouse
Theoretical Analysis of Measure Consistency Regularization for Partially Observed Data
Feb 1, 2026Yinsong Wang, Shahin ShahrampourNeural Network Generalization Learning with Missing Data
University of Nevada Reno, Reno, NV 89557 USA · Department of Mechanical and Industrial Engineering at Northeastern University, Boston, MA 02115 USA
Deep networks learn to parse uniform-depth context-free languages from local statistics
Jan 31, 2026Jack T. Parley, Francesco Cagnetta, Matthieu WyartHierarchical Representation Learning Statistical Learning Theory
Institute of Physics, École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland · Theoretical and Scientific Data Science, SISSA, Trieste, Italy · Department of Physics and Astronomy, Johns Hopkins University, Baltimore, Maryland.
Provable Learning of Random Hierarchy Models and Hierarchical Shallow-to-Deep Chaining
Jan 27, 2026Yunwei Ren, Yatin Dandi, Florent Krzakala +1Deep Learning Optimization Hierarchical Representation Learning
Princeton University · École Polytechnique Fédérale de Lausanne · University of California, Berkeley
Optimal L2 Regularization in High-dimensional Continual Linear Regression
Jan 20, 2026Gilad Karpel, Edward Moroshko, Ran Levinstein +3Regularization-Based Continual Learning High-Dimensional Linear Regression
Department of Data and Decisions Sciences, Technion · School of Engineering, University of Edinburgh · Department of Computer Science, Technion +2
Approximate full conformal prediction in an RKHS
Jan 19, 2026Davidson Lova Razafindrakoto, Alain Celisse, Jérôme LacailleConfidence Region Estimation Conformal Prediction
Laboratoire SAMM Université Paris 1 Panthéon-Sorbonne 90, rue de Tolbiac 75634 PARIS CEDEX 13, FRANCE · Safran Aircraft Engines Rond-Point René Ravaud, Réau, 77550 Moissy-Cramayel CEDEX, France
Learning with Monotone Adversarial Corruptions
Jan 5, 2026Kasper Green Larsen, Chirag Pabbaraju, Abhishek ShettyCorruption Robustness Binary Classification
Aarhus University · Stanford University · MIT
SGD-Based Knowledge Distillation with Bayesian Teachers: Theory and Guidelines
Jan 4, 2026Itai Morad, Nir Shlezinger, Yonina C. EldarStatistical Learning Theory Teacher-Student Learning
School of ECE, Ben-Gurion University, Be’er Sheva, Israel · Faculty of Math and CS, Weizmann Institute of Science, Rehovot, Israel
The Challenger: When Do New Data Sources Justify Switching Machine Learning Models?
Dec 20, 2025Vassilis Digalakis, Christophe Pérignon, Sébastien Saurin +1Sequential Decision Making Learning Curves
Boston University · HEC Paris
Maximum Mean Discrepancy with Unequal Sample Sizes via Generalized U-Statistics
Dec 16, 2025Aaron Wei, Milad Jalali, Danica J. SutherlandTwo-Sample Testing Maximum Mean Discrepancy
University of British Columbia · Independent researcher, Vancouver, Canada · Alberta Machine Intelligence Institute
Learnability Window in Gated Recurrent Neural Networks
Dec 5, 2025Lorenzo LiviGated Recurrent Unit Recurrent Neural Networks
OPIT – Open Institute of Technology
Provable FDR Control for Deep Feature Selection: Deep MLPs and Beyond
Dec 4, 2025Kazuma SawayaFDR Control Feature Selection
The University of Tokyo, Bunkyo, Tokyo, Japan
A Unified and Stable Risk Minimization Framework for Weakly Supervised Learning with Theoretical Guarantees
Nov 28, 2025Miao Zhang, Junpeng Li, Changchun Hua +1Weakly Supervised Learning Statistical Learning Theory
Engineering Research Center of the Ministry of Education for Intelligent Control System and Intelligent Equipment, Yanshan University, Qinhuangdao, China
Learning and Testing Convex Functions
Nov 14, 2025Renato Ferreira Pinto, Cassandra Marcussen, Elchanan Mossel +1Statistical Learning Theory
Columbia University · Harvard University · MIT
Sparse, self-organizing ensembles of local kernels detect rare statistical anomalies
Nov 5, 2025Gaia Grosso, Sai Sumedh R. Hindupur, Thomas Fel +3Kernel Methods Semi-Supervised Anomaly Detection
NSF AI Institute for Artificial Intelligence and Fundamental Interactions, Cambridge, 02139, MA · Laboratory for Nuclear Science, Massachusetts Institute of Technology, Cambridge, 02139, MA · School of Engineering and Applied Sciences, Harvard University, Allston, 02134, MA +1
Recursively Enumerably Representable Classes and Computable Versions of the Fundamental Theorem of Statistical Learning
Nov 4, 2025David Kattermann, Lothar Sebastian KrappPAC Learning Statistical Learning Theory
Institute for Symbolic Artificial Intelligence, Johannes Kepler University Linz, Austria. · Department of Mathematics and Statistics, University of Konstanz, Germany. · Institute for the Interdisciplinary Study of Language Evolution, University of Zurich, Switzerland.
Optimal In-context Adaptivity and Distributional Robustness of Transformers
Oct 27, 2025Tianyi Ma, Tengyao Wang, Richard J. SamworthIn-Context Learning Distribution Shift Robustness
Statistical Laboratory, University of Cambridge · Department of Statistics, London School of Economics and Political Science
Complexity Dependent Error Rates for Physics-informed Statistical Learning via the Small-ball Method
Oct 27, 2025Diego MarcondesPhysics-Informed ML Statistical Learning Theory
Predicting kernel regression learning curves from only raw data statistics
Oct 16, 2025Dhruva Karkada, Joseph Turnbull, Yuxi Liu +1Kernel Regression Kernel Methods
UC Berkeley · Imbue

Feb 19, 2026J/K move · Enter open · S save

Interactive Learning of Single-Index Models via Stochastic Gradient Descent

Nived Rajaraman, Yanjun Han

Microsoft Research NYC · Courant Institute of Mathematical Sciences and Center for Data Science, New York University

Single-Index Models Generalized Linear Bandits Stochastic Gradient Descent Statistical Learning Theory

Open paper AskPDF arXiv

Stochastic gradient descent (SGD) is a cornerstone algorithm for high-dimensional optimization, renowned for its empirical successes. Recent theoretical advances have provided a deep understanding of how SGD enables feature learning in high-dimensional nonlinear models, most notably the single-index model with i.i.d. data. In this work, we study the sequential learning problem for single-index models, also known as generalized linear bandits or ridge bandits, where SGD is a simple and natural solution, yet its learning dynamics remain largely unexplored. We show that, similar to the optimal interactive learner, SGD undergoes a distinct burn-in'' phase before entering the learning'' phase in this setting. Moreover, with an appropriately chosen learning rate schedule, a single SGD procedure simultaneously achieves near-optimal (or best-known) sample complexity and regret guarantees across both phases, for a broad class of link functions. Our results demonstrate that SGD remains highly competitive for learning single-index models under adaptive data.