Sample Complexity

Follow this topic Ask about this topic

Sample complexity quantifies the data or oracle access needed to achieve a specified accuracy and confidence in tasks such as PAC learning, estimation, hypothesis testing, system identification, and generative sampling. Researchers derive upper and lower bounds using tools such as VC and Rademacher complexity, information-theoretic arguments, minimax analysis, and adaptive sampling algorithms. A central theme is how structure—sparsity, low intrinsic dimension, symmetry, smoothness, or prior knowledge—can reduce data needs, while noise, distribution shift, robustness, and limited feedback can raise them. Matching bounds are known in many settings, but guarantees can change sharply with the task, assumptions, and resource being counted, so translating theory to practical data requirements remains an open challenge.

Latest papers

102 papers21 papers in the last four weeks, up 110% on the four weeks before. 0.1% of all new papers.

Learn from your own latents and not from tokens: A sample-complexity theory
May 26, 2026Daniel J. Korchinski, Alessandro Favero, Matthieu WyartUnsupervised Learning Self-Supervised Learning
Department of Physics & Institute of Physics Johns Hopkins University & EPFL Baltimore, MD USA & Lausanne, VD Switzerland
On the Sample Complexity of Robust Binary Hypothesis Testing
May 23, 2026Shankar Vallinayagam, Ankit Pensia, Varun JogSample Complexity Data Contamination
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge · Department of Statistics, Carnegie Mellon University
Optimal Dimension-Free Sampling for Regularized Classification
May 22, 2026Meysam Alishahi, Alexander Munteanu, Simon Omlor +1Sample Complexity Statistical Learning Theory
University of Utah, USA · TU Dortmund, Germany
How Many Training Samples Are Needed for the Inverse Kinematics Solutions by Artificial Neural Networks
May 22, 2026Dong-Won LimSample Complexity Inverse Kinematics
The University of Suwon, Hwaseong 18323, Republic of Korea
Sample Complexity of Transfer Learning: An Optimal Transport Approach
May 19, 2026Haoyang Cao, Xin Guo, Wenpin Tang +1Sample Complexity Transfer Learning
Department of Applied Mathematics and Statistics, John Hopkins University, Baltimore, MD, USA · Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA, USA · Department of Industrial Engineering and Operations Research, Columbia University, New York, NY, USA +1
A Fourier perspective on the learning dynamics of neural networks: from sample complexities to mechanistic insights
May 16, 2026Fabiola Ricci, Claudia Merger, Sebastian GoldtSample Complexity Frequency-Domain Feature Learning
International School of Advanced Studies (SISSA), Trieste, Italy
Learning with Shallow Neural Networks on Cluster-Structured Features
May 14, 2026Elisabetta Cornacchia, Laurent MassouliéShallow Neural Networks Neural Network Generalization
INRIA, DI/ENS, PSL.
Finite Sample Bounds for Learning with Score Matching
May 13, 2026Devin Smedira, Abhijith Jayakumar, Sidhant Misra +2Score Matching Sample Complexity
Operations Research Center, Massachusetts Institute of Technology · Theoretical division, Los Alamos National Lab
The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
May 13, 2026Maximilian Graf, Victor ThuotSample Complexity Adaptive Sampling
INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France
On Observation Time for Recovering Latent Hawkes Networks
May 8, 2026Jonas Linkerhägner, Michele Bortolasi, Lorenzo Baldassari +2Temporal Point Processes Sample Complexity
University of Basel · Rice University
Sample Complexity of Stochastic Optimization with Integer Variables
May 8, 2026Hongyu Cheng, Yinghao Zheng, Marco Molinaro +1Stochastic Optimization Sample Complexity
Dept. of Applied Mathematics & Statistics Johns Hopkins University Baltimore, MD 21218 · Microsoft Research (Redmond) · Dept. of Computer Science, PUC-Rio
Locally Near Optimal Piecewise Linear Regression in High Dimensions via Difference of Max-Affine Functions
May 7, 2026Haitham Kanj, Kiryung LeeGradient Descent Sample Complexity
Department of Electrical and Computer Engineering The Ohio State University, Columbus, OH, USA
On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization
May 4, 2026Kaixuan Ji, Qiwei Di, Heyang Zhao +2Multi-Armed Bandits Sample Complexity
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
Mean Testing under Truncation beyond Gaussian
May 2, 2026Yuhao Wang, Roberto Imbuzeiro Oliveira, Themis GouleakisSample Complexity Information-Theoretic Lower Bounds
Amazon · IMPA, Rio de Janeiro, RJ, Brazil · Nanyang Technological University
On the Learning Curves of Revenue Maximization
Apr 29, 2026Steve Hanneke, Alkis Kalavasis, Shay Moran +1Sample Complexity Learning Curves
Purdue University · Yale University · Technion +1
The Optimal Sample Complexity of Multiclass and List Learning
Apr 27, 2026Chirag PabbarajuSample Complexity Multiclass Classification
Stanford University
The Exact Replica Threshold for Nonlinear Moments of Quantum States
Apr 24, 2026Shuai ZengSample Complexity Information-Theoretic Lower Bounds
School of Communication and Information Engineering, Chongqing University of Posts and Telecommunications, Chongqing 400065, P.R. China
The Sample Complexity of Multicalibration
Apr 23, 2026Natalie Collina, Jiuyao Lu, Georgy Noarov +1Probability Calibration Sample Complexity
University of Pennsylvania
Distributional Off-Policy Evaluation with Deep Quantile Process Regression
Apr 20, 2026Qi Kuang, Chao Wang, Yuling Jiao +1Distributional RL Quantile Regression
School of Statistics and Data Science, and Philosophy and Social Sciences Laboratory of Data Science in Finance and Economics at the Ministry of Education,2026 Jiangxi University of Finance and Economics · School of Statistics and Data Science, Shanghai University of Finance and EconomicsApr · School of Artificial Intelligence, and Hubei Key Laboratory of Computational Science, 24 Wuhan University
Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
Apr 13, 2026Steve Hanneke, Idan Mehalel, Shay MoranCoT Supervision Sample Complexity
Purdue University · The Hebrew University · Technion and Google Research
Replicable Composition
Apr 12, 2026Kiarash Banihashem, MohammadHossein Bateni, Hossein Esfandiari +2Sample Complexity ML Reproducibility
University of Maryland, College Park, MD, USA · Google Research, New York City, NY, USA · Google Research, London, UK
Finite-Sample Analysis of Nonlinear Independent Component Analysis:Sample Complexity and Identifiability Bounds
Apr 10, 2026Yuwen JiangQuery Identifiability Independent Component Analysis
School of Artificial Intelligence, Guangzhou Institute of Science and Technology, Guangzhou, China
Optimal Centered Active Excitation in Linear System Identification
Apr 7, 2026Kaito Ito, Alexandre ProutiereSample Complexity Active Learning
Department of Information Physics and Computing, The University of Tokyo, Tokyo 113-8654, Japan · Division of Decision and Control Systems, School of Electrical Engineering and Computer Science, KTH Royal Institute of Technology, Stockholm 114 28, Sweden
Partially deterministic sampling for compressed sensing with denoising guarantees
Apr 6, 2026Yaniv Plan, Matthew S. Scott, Ozgur YilmazCompressed Sensing Sparse Recovery
Department of Mathematics, University of British Columbia, Vancouver, BC, Canada. · CNRS – PIMS International Research Laboratory
Algorithmic warm starts for Hamiltonian Monte Carlo
Mar 24, 2026Matthew S. Zhang, Jason M. Altschuler, Sinho ChewiMarkov Chain Monte Carlo Sample Complexity
UToronto · UPenn · Yale
Achieving $\widetilde{O}(1/ε)$ Sample Complexity for Bilinear Systems Identification under Bounded Noises
Mar 21, 2026Hongyu Yi, Chenbei Lu, Jing YuParameter Estimation Uncertainty Quantification
Department of Electrical and Computer Engineering, University of Washington, Seattle, WA, USA. · Cornell University AI for Science Institute, Cornell University, Ithaca, NY, USA.
Sample Complexity Bounds for Robust Mean Estimation with Mean-Shift Contamination
Feb 25, 2026Ilias Diakonikolas, Giannis Iakovidis, Daniel M. Kane +1Robust Mean Estimation Robust Estimation
UW Madison · UC San Diego
The Sample Complexity of Replicable Realizable PAC Learning
Feb 23, 2026Kasper Green Larsen, Markus Engelund Mathiasen, Chirag Pabbaraju +1PAC Learning Sample Complexity
Computer Science Department, Aarhus University · Computer Science Department, Stanford University
Efficient Sampling with Discrete Diffusion Models: Sharp and Adaptive Guarantees
Feb 16, 2026Daniil Dmitriev, Zhihan Huang, Yuting WeiSample Complexity Diffusion Model Sampling
Department of Statistics and Data Science, the Wharton School, University of Pennsylvania
Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach
Feb 4, 2026Senrui Chen, Weiyuan Gong, Sisi ZhouSample Complexity Quantum Machine Learning
IQIM, California Institute of Technology · SEAS, Harvard University · Perimeter Institute

May 26, 2026J/K move · Enter open · S save

Learn from your own latents and not from tokens: A sample-complexity theory

Daniel J. Korchinski, Alessandro Favero, Matthieu Wyart

Department of Physics & Institute of Physics Johns Hopkins University & EPFL Baltimore, MD USA & Lausanne, VD Switzerland

Unsupervised Learning Self-Supervised Learning Sample Complexity Hierarchical Representation Learning Predictive Representation Learning

Open paper AskPDF arXiv

Generative models, from diffusion models to large language models, achieve remarkable performance but at a cost in training data orders of magnitude larger than what biological learners require. An alternative paradigm has emerged in which networks are trained to predict their own latent representations of related views or masked regions, as in data2vec and JEPA -- an idea related to predictive-coding accounts of the cortex. Despite strong empirical results, the theoretical understanding of these methods remains limited. Central questions include: by how much does latent prediction actually improve data efficiency? Is there a benefit to stacking such methods into multi-scale hierarchies? We answer both using as data a tractable probabilistic context-free grammar that captures the compositional structure of natural language and images. Such a grammar generates strings of visible tokens by recursively applying production rules along a tree of hidden symbols of depth

L

. For such data, supervised or token-level SSL require a number of samples exponential in

L

to recover the latent tree; we prove that latent prediction achieves this with a number of samples constant in

L

, up to logarithmic factors. We confirm this bound with (i) a hierarchical clustering algorithm, (ii) an end-to-end neural network whose predictor-clusterer modules predict their own latents at each level via gradient descent, and (iii) the first sample-complexity analysis of data2vec, which we show implicitly performs hierarchical latent prediction. This suggests that explicit stacking such as H-JEPA is largely redundant.