Sample Complexity

Follow this topic Ask about this topic

Momentum

7 papers in the last four weeks, against 2 the four weeks before. 0.1% of all new papers.

Jul 13Week of Sep 28

Latest papers 66

All topics

Sample complexity bounds for categorical Markov random fields via Discrete Diffusions
Oct 1, 2026Shivam Kumar, Nabarun DebScore-Based Diffusion Model Markov
Booth School of Business, University of Chicago
Sharp Non-Asymptotic Analysis of the Penalized Challenger in $β$ -EB-TCI for Bernoulli Bandits
Oct 1, 2026Nam Nguyen, Tuan Quang DamOptimal Sample Complexity Best-Of-N
Hanoi University of Science and Technology, Hanoi, Vietnam · Center for AI Research, VinUniversity, Hanoi, Vietnam
Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries
Sep 29, 2026Natsuto Isogai, Satoshi Yoshida, Mio MuraoQuantum Learning Quantum Machine Learning
Department of Physics, Graduate School of Science, The University of Tokyo, Tokyo, Japan
Arbitrary-Accuracy Neural Approximation with Optimal Neuron Count and Near-Optimal Bit Complexity
Sep 28, 2026Zilan Cheng, Li-Lian Wang, Zhongjian WangNeural Approximations Approximation
Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, 637371, Singapore.
On the Sample Complexity of Active Learning with Membership Queries
Sep 23, 2026Ganghua Wang, Shaddin DughmiPool-Based Active Learning Active Learning
Department of Mathematics University of Arizona · Department of Computer Science University of Southern California
Near-Optimal Nonconvex Matrix Completion
Sep 15, 2026Jian-Feng Cai, Xiliang Lu, Juntao YouTensor Completion Convex Optimization
Department of Mathematics, Hong Kong University of Science and Technology. · School of Mathematics and Statistics, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China. · School of Artificial Intelligence, Hubei Center for Applied Mathematics, and Hubei Key Laboratory of Computational Science, Wuhan University, Wuhan 430072, China.
The Sample Complexity of Quantum Entanglement Allocation
Sep 9, 2026Nathan RollQubit Entanglement
Stanford University
Resolution-Aware Experimental Design under Partial Identifiability
Sep 3, 2026Sofianos Panagiotis FotiasBayesian Experimental Design Identifiability
National Technical University of Athens
Bagging Robustly Learns VC Classes with Linear Sample Complexity
Aug 13, 2026Omar MontasserEmpirical Risk Minimization Tree Ensembles
Yale University
The Sample Complexity of Policy Learning with Mu-Resets
Aug 7, 2026Gene LiOptimal Sample Complexity Sample Complexity
Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
Aug 6, 2026Yuepeng Yang, Yuxin Chen, Yuejie ChiMarkov Decision Processes Optimal Policies
*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.
An Optimal Agnostic PAC Algorithm
Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyOptimal Sample Complexity Sample Complexity
Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley
The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences
Aug 5, 2026Elad Aigner-Horev, Daniel Rosenberg, Roi WeissDistributionally-Robust Optimization Optimal Sample Complexity
School of Computer Science and AI Ariel University 40800 Ariel, Israel
Sample Complexity of Multicalibration for Multilevel Properties
Aug 4, 2026Jiuyao Lu, Krishnakumar Balasubramanian, Aleksandr Podkopaev +1Optimal Sample Complexity Sample Complexity
Department of Statistics and Data Science, The Wharton School, University of Pennsylvania · 2Amazon · Department of Statistics, University of California, Davis
Randomized Algorithms for Learning Partitions with Near Optimal Query Complexity in Constant Rounds
Aug 3, 2026Deeparnab Chakrabarty, Aditi Dudeja, David SaulpicO(\Bar{K}\Log N)$Partitioning
Dartmouth College · The Chinese University of Hong Kong (Shenzhen) · CNRS and Universit´e Paris Cit´e
Actions Have Consequences: Detecting Outcome Performativity using Intervention Testing
Jul 29, 2026Brandon Gower-Winter, Georg KremplClinical Prediction Implications
Utrecht University 8 Hiedelberglaan, Utrecht, 3584 CS, NL
Learning Distributions from Multiple Data Providers
Jul 27, 2026Jon Kleinberg, Amin Saberi, Xizhi Tan +1Learnability Sample Complexity
Cornell University · Stanford University · Google Research
Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
Jul 26, 2026Heyang Zhao, Tianyuan Jin, Weixin Wang +3Stochastic Multi-Armed Bandits Variance Reduction
Department of Computer Science, University of California, Los Angeles · Department of Electrical and Computer Engineering, National University of Singapore · Department of Biostatistics & Bioinformatics, Duke University +2
Generalization bounds and sample complexity for remaining useful life prediction from complete degradation trajectories
Jul 26, 2026Huy Hoang Le, Kim-Anh NguyenUseful Life Prediction Degradation
R&D Department, PowerMore Ltd., Da Nang 550000, Vietnam · Faculty of Electrical Engineering, University of Science and Technology, The University of Danang, Da Nang 550000, Vietnam
Local Regularization Does Not Characterize Multiclass PAC Learnability
Jul 26, 2026Eric HouLearnability Multiclass Classification
On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity
Jul 21, 2026Jixian Liu, Ihab Tabbara, Hussein Sibai +1Reachability Hamilton-Jacobi Reachability
Department of Electrical and Computer Engineering, Johns Hopkins University · Department of Computer Science, Washington University in St. Louis
Publicly-Verifiable Certificates for Statistical Algorithms
Jul 17, 2026Michael Ngo, Michael P. KimZero-Knowledge Proofs Certificates
MIT · Research completed while at Cornell University, supported by the Bowers Undergraduate Research Experience (BURE) and the Dean Archer Undergraduate Research Program. · Cornell University
From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP
Jul 13, 2026Michael Rizvi-Martel, Satwik Bhattamishra, Guillaume Rabusseau +1Transformer Architectures Learnability
Mila & Universit´e de Montr´eal · University of Oxford · Saarland University
The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
Jul 8, 2026Zhiyuan LiOptimal Sample Complexity Sample Complexity
Toyota Technological Institute at Chicago
When Does In-Context Search Help? A Sampling-Complexity Theory of Reflection-Driven Reasoning
Jul 7, 2026Yotam Wolf, Noam Wies, Amnon ShashuaLLM Reasoning Strategies In-Context
The Hebrew University
Deep Neural Variation Spaces: A Unifying Perspective on Depth and Complexity
Jul 6, 2026Julia Nakhleh, Robert D. NowakRectified Linear Unit Networks Deep Network
Department of Computer Science · University of Wisconsin-Madison · Department of Electrical & Computer Engineering
Optimal Stabilizer Testing and Learning with Limited Quantum Memory
Jul 2, 2026Srinivasan Arunachalam, Louis SchatzkiQubit Sample Complexity
IBM Research Silicon Valley · Dahlem Center for Complex Quantum Systems Freie Universität Berlin
From Spectral Methods to Sample Complexity Bounds for Fourier Neural Operators
Jul 1, 2026Nisha Chandramoorthy, Daniel Sanz-Alonso, Nathan WaniorekFourier Neural Operators Nonlinear Operators
University of Chicago
Sample Complexities of Estimating Gumbel--Max Watermark Proportions with and without Reduction to Pivotal Statistics
Jun 30, 2026Shuwen Chai, Qiaosen WangWatermarking Watermarks
Northwestern University · University of Chicago
SGD Provably Prioritizes a Shortcut Spurious Feature in the XOR Model
Jun 29, 2026Tyler LaBonte, Vidya MuthukumarFeature Learning Rectified Linear Unit Networks
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology · School of Electrical and Computer Engineering, Georgia Institute of Technology
Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees
Jun 28, 2026Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem YalçınSymbolic Regression Sample Complexity
Independent Researcher · TÜBİTAK Science High School
Sample complexity of unbalanced entropic OT
Jun 23, 2026Francisco Andrade, Gabriel Peyré, Clarice PoonOptimal Transport Approach Optimal Sample Complexity
INRIA (PreMeDICaL & HeKA) · INRIA · CNRS and ENS, PSL Universit´e +1
Tight $L_\infty$ Sample Complexity for Low-Degree and Sparse Boolean Polynomials
Jun 15, 2026Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1Optimal Sample Complexity Sample Complexity
Institute for Mathematical and Computational Engineering, Pontificia Universidad Católica de Chile, Chile · Blavatnik School of Computer Science and AI, Tel Aviv University, Israel · Institute for Mathematical and Computational Engineering, and Department of Industrial and Systems Engineering, Pontificia Universidad Católica de Chile, Chile
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Jun 12, 2026Tianhao Wu, Matthew Zurek, Weina Wang +1Markov Decision Processes Sample Complexity
Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison · Computer Science Department, Carnegie Mellon University
Tight Sample Complexity of Transformers
Jun 8, 2026Chenxiao Yang, Nathan Srebro, Zhiyuan LiTransformer Architectures Sample Complexity
Toyota Technological Institute at Chicago (TTIC)
Sample Complexity and Decision-Theoretic Guarantees for Bayesian Model Averaging over Decision Trees with Catalan-Exponential Priors
May 31, 2026Livija Jakaite, Vitaly SchetininDecision Trees Model Selection
School of Computing and Engineering University of Bedfordshire, Luton, UK
Diffusion Models Are Statistically Optimal for Learning Low-Dimensional Multi-Modal Distributions
May 28, 2026Jingda Wu, Changxiao CaiLow-Dimensional Structure Score-Based Diffusion Model
Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, USA.
The Sample Complexity of Multiclass and Sparse Contextual Bandits
May 28, 2026Liad Erez, Fan Chen, Alon Cohen +4Contextual Bandit Framework Optimal Sample Complexity
1Tel Aviv University, Israel · 2Massachusetts Institute of Technology, USA · 3Google Research Tel Aviv, Israel +1
Sample Complexity of Policy Gradient for Log-Growth Control
May 26, 2026Qiuhua Pan, Yukai Shen, Liwei Zhang +2Policy Gradient Stochastic Optimal Control
State Key Laboratory of Submarine Geoscience, School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai 200240, China · Key Laboratory of System Control and Information Processing, Ministry of Education of China, Shanghai 200240, China · Shanghai Key Laboratory of Perception and Control in Industrial Network Systems, Shanghai 200240, China +1
PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
May 25, 2026Steve Hanneke, Qinglin Meng, Shay Moran +1Sample Complexity Bandits
Department of Computer Science Purdue University West Lafayette, IN, USA · Faculties of Mathematics, Computer Science, and Data and Decision Sciences Technion – Israel Institute of Technology and Google Research Haifa, Israel
Learning Sparse Compositional Functions with Norm-Constrained Neural Networks
May 25, 2026Shuo Huang, Lorenzo Fiorito, Lorenzo Rosasco +1Neural Network Sparsity
MaLGa, DIMA, Università degli Studi di Genova, Genoa, Italy · CBMM, Massachusetts Institute of Technology, Cambridge, MA, USA
On the Sample Complexity of Robust Binary Hypothesis Testing
May 23, 2026Shankar Vallinayagam, Ankit Pensia, Varun JogTwo-Sample Testing Optimal Sample Complexity
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge · Department of Statistics, Carnegie Mellon University
Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning
May 21, 2026Benjamin D. Kim, Lav R. Varshney, Daniel AlabiOptimal Sample Complexity Model Auditing
University of Illinois Urbana-Champaign · 1Massachusetts Institute of Technology · Brook University
On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents
May 20, 2026Oliver Mortensen, Mohammad Sadegh TalebiConditional-Value-At-Risk Value Functions
Department of Computer Science, University of Copenhagen.
Sample Complexity of Transfer Learning: An Optimal Transport Approach
May 19, 2026Haoyang Cao, Xin Guo, Wenpin Tang +1Transfer Learning Learnability
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 GoldtNeural Network Fourier
International School of Advanced Studies (SISSA), Trieste, Italy
Testing properties of trees in graphical models with covariance queries
May 15, 2026Sofiya Burova, Francisco Calvillo, Gábor Lugosi +1Probabilistic Graphical Models Trees
IMTECH and Departament de Matem`atiques, Universitat Polit`nica de Catalunya, Barcelona, Spain and Department of Economics and Business, Pompeu Fabra University, Barcelona, Spain. · LPSM, Sorbonne Universit´e, 4 Place Jussieu, 75005 Paris, France · ICREA, Pg. Llu´ıs Companys 23, 08010 Barcelona, Spain; Department of Economics and Business, Pompeu Fabra University, Barcelona, Spain; Barcelona School of Economics. +1
Learning with Shallow Neural Networks on Cluster-Structured Features
May 14, 2026Elisabetta Cornacchia, Laurent MassouliéLow-Dimensional Structure Feature Learning
INRIA, DI/ENS, PSL.
Tight Sample Complexity Bounds for Entropic Best Policy Identification
May 13, 2026Amer Essakine, Claire VernadeEntropy Regularized Reinforcement Learning Boltzmann Policies
ENS Paris Saclay · University of Technology Nuremberg
The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
May 13, 2026Maximilian Graf, Victor ThuotChange-Point Detection Optimal Sample Complexity
Institut für Mathematik, Universität Potsdam, Potsdam, Germany · INRAE, Mistea, Institut Agro, Univ Montpellier, Montpellier, France
Selection of the Best Policy under Fairness Constraints for Subpopulations
May 11, 2026Tingyu Zhu, Yuhang Wu, Zeyu ZhengAlgorithmic Fairness Selection Bias
Department of Industrial Engineering and Operations Research & Berkeley Artificial Intelligence Research Lab University of California Berkeley
Sample Complexity of Stochastic Optimization with Integer Variables
May 8, 2026Hongyu Cheng, Yinghao Zheng, Marco Molinaro +1Stochastic Optimization Optimal Sample Complexity
Dept. of Applied Mathematics & Statistics Johns Hopkins University Baltimore, MD 21218 · Microsoft Research (Redmond) · Dept. of Computer Science, PUC-Rio
Distributed Learning with Adversarial Gradient Perturbations
May 5, 2026Nawapon Sangsiri, Yufei TaoBounded Adversary Optimality
CUHK
Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation
May 4, 2026Jingchu Gai, Laixi ShiMean Field Games Multi-Agent Reinforcement Learning
Machine Learning Department, Carnegie Mellon University. · Department of Electrical and Computer Engineering, Johns Hopkins University, MD 21286, USA.
A Near-optimal SQ Lower Bound for Smoothed Agnostic Learning of Boolean Halfspaces
May 4, 2026Tim SinenSample Complexity
University of Bonn, Germany
The Optimal Sample Complexity of Multiclass and List Learning
Apr 27, 2026Chirag PabbarajuMulticlass Classification Optimal Sample Complexity
Stanford University
Constraint-Based Analysis of Reasoning Shortcuts in Neurosymbolic Learning
Apr 25, 2026Akihiro Takemura, Katsumi Inoue, Masaaki NishinoNeuro-Symbolic Framework Constraint Satisfaction
National Institute of Informatics, Tokyo, Japan · Communication Science Laboratories, NTT, Inc., Japan
The Sample Complexity of Multicalibration
Apr 23, 2026Natalie Collina, Jiuyao Lu, Georgy Noarov +1Optimal Sample Complexity Calibrated Uncertainty
University of Pennsylvania
Sample Complexity Bounds for Stochastic Shortest Path with a Generative Model
Apr 17, 2026Jean Tarbouriech, Matteo Pirotta, Michal Valko +1Optimal Policies Shortest Paths
Facebook AI Research Paris & Inria Lille · Facebook AI Research Paris · DeepMind Paris
Optimal Centered Active Excitation in Linear System Identification
Apr 7, 2026Kaito Ito, Alexandre ProutiereSystem Identification Least Squares
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

Oct 1, 2026, math.STJ/K move · Enter open · S save

Sample complexity bounds for categorical Markov random fields via Discrete Diffusions

Shivam Kumar, Nabarun Deb

Booth School of Business, University of Chicago

Score-Based Diffusion Model Markov Optimal Sample Complexity Sample Complexity

Open paper AskPDF arXiv

Many applications in statistics, economics, and physics require sampling from high-dimensional categorical distributions with local dependence structures. Examples include finite memory language models, Ising and Potts systems in statistical physics and protein folding, etc. In modern machine learning, discrete diffusions have emerged as a flexible approach for sampling such data, with strong empirical performance. Motivated by this, we develop learning methods with end-to-end sample complexity bounds for discrete diffusion with uniform noising under local dependence, which we model through low order Markov random fields (MRFs). Our main technical insight is a new \emph{pinning decomposition} of the discrete score. It shows that unlike in continuous diffusions, the score decomposes into components where the dependence on time separates multiplicatively from the dependence on the target. Building on this decomposition, we propose a \emph{weight-sharing neural score learner} and combine it with

τ

-leaping to obtain an end-to-end sampling procedure. Rather than treating score-learning error as a black-box input, as is common in existing sampling analyses, we study the score learning error from finite data and derive optimal sampling guarantees with explicit dependence on the vocabulary size, the interaction order of the MRF, and the sample size. Moreover, our strategy trains a single score network across uniform noise levels while leaving the sampling discretization to be chosen at inference-time. This allows the same trained model to trade accuracy for computational cost as inference-time budgets vary. Numerical experiments on Potts, Ising, and tree-structured models show that weight-sharing score networks outperform fully connected ones for sampling long sequences.

Momentum

Related topics

Latest papers 66