Sample Complexity

Ask about this topic

Overview

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

CardsList

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

  1. Reverse-KL Policy Distillation: Statistical Guarantees and Limits

    Oct 22, 2026Haolin Liu, Chen-Yu Wei, Julian ZimmertLanguage Model DistillationKnowledge Distillation

    University of Virginia · Google Research · National Taiwan University

  2. The role of locality and weight sharing in convolutional neural networks

    Oct 21, 2026Francesco Mori, Melanie WeberConvolutional Neural NetworksNeural Network Training Dynamics

    Center of Mathematical Sciences and Applications, Harvard University · John A. Paulson School of Engineering and Applied Sciences, Harvard University

  3. Asymmetric Likelihood-Free Hypothesis Testing

    Oct 21, 2026Gunjan Kumar, Yash Pote, Jonathan ScarlettStatistical Hypothesis TestingSample Complexity

    IIT Kanpur · National University of Singapore

  4. The Price of Choice in Selective Prediction

    Oct 21, 2026Daniel Cieślak, Andrzej CzyżewskiSelective PredictionAlgorithmic Auditing

    Gdańsk University of Technology Gdańsk, Poland

  5. The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

    Oct 18, 2026Guangjian ZhangAgnostic LearningSample Complexity

  6. Strictly Replicable Realizable Learning: Unknown Marginals, Finite-Class Interpolation, and the Cost of Shared Randomness

    Oct 18, 2026Guangjian ZhangSample ComplexityStatistical Learning Theory

  7. Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation

    Oct 13, 2026Behrooz Tahmasebi, Melanie WeberSample ComplexityStatistical Learning Theory

    Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS), Harvard University, Cambridge, MA 02138, USA

  8. When More Objectives Make Identification Easier: The Role of Preferences and Feedback

    Oct 13, 2026Bo Xue, Ji Cheng, Yuanyu Wan +1Multi-Armed BanditsBest-Arm Identification

    City University of Hong Kong · Zhejiang University

  9. Learning a Group Element from Its Action: Galois Correspondences, Optimal ERM, and an Abel-Ruffini Threshold for the Natarajan Dimension

    Oct 13, 2026Xiaoyu LiSample ComplexityMulticlass Classification

    University of New South Wales

  10. The Sample Complexity of Multicalibration with an ERM Oracle

    Oct 9, 2026Princewill OkoroaforMulticalibrationSample Complexity

    Harvard University

  11. Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity

    Oct 9, 2026Brendan Mallery, Shuchin Aeron, James MurphyRepresentation LearningSparse Coding

    Independent Researcher · Department of Electrical and Computer Engineering, Tufts University · The NSF AI Institute for Artificial Intelligence and Fundamental Interactions (IAIFI) +1

  12. Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

    Oct 8, 2026Thomas WeinbergerSample ComplexityStatistical Learning Theory

    School of Computer and Communication Sciences, EPFL, Switzerland

  13. Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

    Oct 8, 2026Jing Ma, Yujia Wu, Zhaoqiang LiuCompressed SensingSample Complexity

    University of Electronic Science and Technology of China

  14. How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?

    Oct 7, 2026Shashaank Aiyer, Han ShaoPairwise RankingPairwise Preference Learning

    University of Maryland

  15. Sharp dimensional analysis of midpoint methods for Langevin sampling

    Oct 5, 2026Fan Chen, Sinho Chewi, Jianfeng Lu +1Markov Chain Monte CarloStochastic Differential Equations

    Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. · Department of Statistics and Data Science, Yale University. · Department of Mathematics, Duke University. +1

  16. Seer: Maximum Likelihood Regression for Learning-Speed Curves

    Oct 2, 2026Carl Myers KadieLearning CurvesSample Complexity

    University of Illinois at Urbana-Champaign, Graduate College, Computer Science, Urbana, Illinois

  17. Learning Linear Systems under Heavy-Tailed Noise: A Non-Asymptotic Analysis from A Single Trajectory

    Sep 30, 2026Xiaomian Yang, Sungho ShinStochastic Linear Dynamical SystemsSample Complexity

    Department of Chemical Engineering Massachusetts Institute of Technology Cambridge, MA 02139

  18. How Many Samples Are Enough for Learning Across Domains?

    Sep 30, 2026Hong ZhengSample ComplexityDomain Generalization

    This work was completed during my Ph.D. period and was the result of a flash of inspiration. I decided to submit it to arXiv and leave its value to the readers.

  19. Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

    Sep 29, 2026Natsuto Isogai, Satoshi Yoshida, Mio MuraoSample ComplexityQuantum Machine Learning

    Department of Physics, Graduate School of Science, The University of Tokyo, Tokyo, Japan

  20. Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure

    Sep 29, 2026Ryotaro Kawata, Satoshi Hayakawa, Taiji SuzukiSample ComplexityProbabilistic Graphical Models

    The University of Tokyo · RIKEN AIP

  21. The Statistical Cost of Causal Discovery with Feedback

    Sep 28, 2026Sunmin Oh, Seungsu Han, Gunwoong ParkSample ComplexityCausal Discovery

    Department of Statistics; Institute for Data Innovation in Science, Seoul National University, Korea · Department of Operations Research and Financial Engineering, Princeton University, USA · Department of Statistics; Interdisciplinary Program in Artificial Intelligence; Institute for Data Innovation in Science, Seoul National University, Korea.

  22. The cost of useful natural gradient updates

    Sep 27, 2026Subhransu S. Bhattacharjee, Dylan Campbell, Rahul ShomeSample ComplexityNatural Gradient Methods

    School of Computing, The Australian National University

  23. Structuring Relations Among Learning Paradigms via Protocol--Objective--Resource Reductions

    Sep 26, 2026Junwei Su, Changjie Wang, Dongyang ChangStatistical Learning TheoryMeta-Learning

    University of Science and Technology of China

  24. Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements

    Sep 26, 2026Xiaxin Li, Arya MazumdarSparse RecoverySample Complexity

    Halıcıoğlu Data Science Institute, University of California, San Diego

  25. Adversarially Robust PAC Learning with Optimal VC Rates

    Sep 21, 2026Steve Hanneke, Amirreza ShaeiriSample ComplexityAdversarial Robustness

    Department of Computer Sciences, Purdue University, USA.

  26. Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

    Sep 16, 2026Pranaya JajooOff-Policy EvaluationSample Complexity

    University of Alberta

  27. Thin-shell stability of Gaussian cooling: logconcave sampling with sesteric complexity from a cold start

    Sep 14, 2026Yunbum Kook, Santosh S. VempalaSample ComplexityLog-Concave Sampling

    University of Michigan · Georgia Tech

  28. Learning CNF Formulas from Uniform Random Solutions: Near-Tight Sample Complexity for Valiant's Algorithm

    Sep 14, 2026Weiming Feng, Yixiao Yu, Yiyao ZhangBoolean Function LearningSample Complexity

    School of Computing and Data Science, The University of Hong Kong. · State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University.

  29. Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

    Sep 12, 2026Jiarui Yao, Jiaxi Zhao, Xiangxin ZhouBest-Arm IdentificationSample Complexity

    UIUC · NUS · Tencent Hunyuan

  30. Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions

    Sep 11, 2026Weiming Ou, Xiao WangSample ComplexityLog-Concave Sampling

    Shanghai University of Finance and Economics · MoE Key Laboratory of Interdisciplinary Research of Computation and Economics, Shanghai University of Finance and Economics