Optimal Sample Complexity

Follow this field Ask about this field

Recent momentum

emerging

0 papers in the last 28 days · 0.0% of indexed attention

Twelve weeks of publication activity for this topic as it is defined today.

Weekly history

Recent digests

What was published in this field, kept on the site without email delivery.

Period ending 2026-09-21

13 new papers

A weekly snapshot of new work published in Optimal Sample Complexity.

Period ending 2026-09-14

13 new papers

A weekly snapshot of new work published in Optimal Sample Complexity.

Period ending 2026-09-07

6 new papers

A weekly snapshot of new work published in Optimal Sample Complexity.

Inside this field

Focused directions

Focused topic

Optimal Sample Complexity

Within Optimal Sample Complexity

210 papersExplore

Focused topic

Sample Complexity

Within Optimal Sample Complexity

62 papersExplore

Focused topic

Lower Bounds

Within Optimal Sample Complexity

51 papersExplore

Focused topic

Upper Bounds

Within Optimal Sample Complexity

48 papersExplore

Focused topic

Concentration Inequalities

Within Optimal Sample Complexity

41 papersExplore

Focused topic

Worst-Case

Within Optimal Sample Complexity

33 papersExplore

Focused topic

New Bounds

Within Optimal Sample Complexity

24 papersExplore

426 papers

Latest in Optimal Sample Complexity

Browse all topics →

Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound
May 26, 2026Eichi UeharaCausal Foundation Models Identifiability
Sample Complexity of Policy Gradient for Log-Growth Control
May 26, 2026Qiuhua Pan, Yukai Shen, Liwei Zhang +2Policy Gradient Lyapunov Function
Variational Inference for Evidential Deep Learning
May 26, 2026Jiawei Tang, Xinyan Du, Hui Liu +2Evidential Learning Variational Inference
A PAC-Bayesian View of Generalisation for Physics-Informed Machine Learning
May 25, 2026Thien V. Nguyen, Amaury Habrard, Benjamin GuedjPhysics-Informed Machine Learning Bayesian
Towards Anatomically Plausible Human Image Generation via Synthetic Localized Preferences
May 25, 2026Bao Li, Yuliang Xiu, Zhen LiuAnatomical Priors Video-Text Alignment
PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
May 25, 2026Steve Hanneke, Qinglin Meng, Shay Moran +1Optimal Sample Complexity Sample Complexity
Learning Sparse Compositional Functions with Norm-Constrained Neural Networks
May 25, 2026Shuo Huang, Lorenzo Fiorito, Lorenzo Rosasco +1Neural Network Sparsity
Data-Specific Hyper-Parameter Design: A Paradigm Shift in Reservoir Computing
May 24, 2026G Manjunath, Juan-Pablo Ortega, Alma van der MerweReservoir Computing Reservoir
On the Sample Complexity of Robust Binary Hypothesis Testing
May 23, 2026Shankar Vallinayagam, Ankit Pensia, Varun JogTwo-Sample Testing Sample Complexity
Affinity Graph Connectivity in Convex Clustering
May 23, 2026Sam Rosen, Jason XuExponential Random Graph Models Convex Sets
From One-Pass SGD to Data Reuse: Mini-Batch Scaling Laws in Sketched Linear Regression
May 23, 2026Ziyan Chen, Zhongzhu Zhou, Ding-Xuan ZhouMini-Batch Stochastic Gradient Descent Stochastic Gradient Descent
TUBE: Tangent Upper Bound on Evidence for Discrete Diffusion Language Models
May 22, 2026Arseny Ivanov, Sergei Kholkin, Vladislav Gromadskii +3Diffusion Language Models Likelihood
Verified SHAP: Provable Bounds for Exact Shapley Values of Neural Networks
May 22, 2026David Boetius, Shahaf Bassan, Guy Katz +2Shapley Value Neural Network Verification
The Communication Complexity of Instant-Runoff Voting
May 22, 2026Élie de Panafieu, François Durand, Jérôme LangMaximum Independent Set Upper Bounds
Optimal Dimension-Free Sampling for Regularized Classification
May 22, 2026Meysam Alishahi, Alexander Munteanu, Simon Omlor +1Optimal Sample Complexity Lipschitz Constant
Entropy Equivalence Testing
May 22, 2026Clément L. Canonne, Yash Pote, Jonathan Scarlett +1Optimal Sample Complexity Two-Sample Testing
Holographic functions and neural networks
May 21, 2026Balazs SzegedyHolographic Reduced Representations Polynomials
Adaptive Measurement Allocation for Learning Kernelized SVMs Under Noisy Observations
May 21, 2026Artur MiroszewskiQuantum Kernels Support Vector Machines
Optimal Guarantees for Auditing Rényi Differentially Private Machine Learning
May 21, 2026Benjamin D. Kim, Lav R. Varshney, Daniel AlabiDifferential Privacy Efficient Privacy Loss
On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents
May 20, 2026Oliver Mortensen, Mohammad Sadegh TalebiValue Functions Markov Decision Processes
Concentration of General Stochastic Approximation Under Heavy-Tailed Markovian Noise
May 20, 2026Shubhada Agrawal, Siva Theja Maguluri, Martin ZubeldiaStochastic Approximation Concentration Inequalities
Everywhere Valid Bounds on False Discovery Proportions in Conformal Inference
May 20, 2026Ziang Song, Ying Jin, Emmanuel J. CandèsFalse Discovery Rate Conformal Inference
Lower Bounds for Advection-Diffusion Equations: An Exploration with AI-Generated Proofs
May 20, 2026Chenyang An, Xiaoqian XuAdvection-Reaction-Diffusion Lower Bounds
Sample Complexity of Transfer Learning: An Optimal Transport Approach
May 19, 2026Haoyang Cao, Xin Guo, Wenpin Tang +1Transfer Learning Distributional Learning
Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation
May 19, 2026Peter Matthew Jacobs, Jeff M. PhillipsWasserstein Distance Optimal Sample Complexity
A Van Trees Lower Bound for Fully Interactive Differentially Private Federated Learning
May 19, 2026T. Tony Cai, Yicheng LiDifferential Privacy Federated Learning
Optimal Reconstruction from Linear Queries
May 19, 2026Yuval Filmus, Shay Moran, Elizaveta NesterovaReconstruction Error Optimal Sample Complexity
Provably Data-driven Lagrangian Relaxation for Mixed Integer Linear Programming
May 18, 2026Tung Quoc Le, Anh Tuan Nguyen, Viet Anh NguyenMixed-Integer Programming Semidefinite Programming
Efficient and Noise-Tolerant PAC Learning of Multiclass Linear Classifiers
May 18, 2026Rita Adhikari, Shiwei ZengMulticlass Classification Optimal Sample Complexity
Iterative Chow Filtering for Learning with Distribution Shift
May 17, 2026Gautam Chandrasekaran, Georgios Gkrinias, Adam R. Klivans +2Distributional Learning Distribution Shifts
Sample-efficient inductive matrix completion with noise and inexact side-information
May 16, 2026Yuepeng Yang, Cong MaTensor Completion Sparse Recovery
Multi-task Linear Regression without Eigenvalue Lower Bounds: Adaptivity, Robustness, and Safety
May 16, 2026Seok-Jin KimRegularization Techniques Estimators
When Dynamics Shift, Robust Task Inference Wins: Offline Imitation Learning with Behavior Foundation Models Revisited
May 16, 2026Rishabh Agrawal, Rahul Jain, Ashutosh NayyarImitation Learning Worst-Case
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 Feature Learning
The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimization
May 15, 2026El Mustapha MansouriConditional-Value-At-Risk Long-Tailed Distribution
Testing properties of trees in graphical models with covariance queries
May 15, 2026Sofiya Burova, Francisco Calvillo, Gábor Lugosi +1Conditional Independence Trees
Petri Net Induced Heuristic Search for Resource Constrained Scheduling
May 15, 2026Ido Lublin, Dor Atzmon, Izack CohenOptimal Scheduling Heuristics
Complexity of Non-Log-Concave Sampling in Fisher Information
May 15, 2026Sinho Chewi, Andre WibisonoNon-Log-Concave Optimal Sample Complexity
Learning Context-conditioned Gaussian Overbounds for Convolution-Based Uncertainty Propagation
May 15, 2026Ruirui Liu, Xuejie Hou, Yiping Jiang +1Reliable Uncertainty Quantification Conditional-Value-At-Risk
On the Power of Adaptivity for $\varepsilon$ -Best Arm Identification in Linear Bandits
May 15, 2026Arnab Maiti, Yunbei Xu, Kevin JamiesonLinear Bandits Multi-Armed Bandits
MaxSketch: Robust Distinct Counting in Streams via Random Projections
May 15, 2026Nikos Tsikouras, Constantine Caramanis, Christos TzamosLocality-Sensitive Hashing Optimal Sample Complexity
Beyond Bounded Variance: Variance-Reduced Normalized Methods for Nonconvex Optimization under Blum-Gladyshev Noise
May 14, 2026Antesh Upadhyay, Arda Fazla, Abolfazl HashemiStochastic Smooth Convex Optimization Convex Optimization
Average Gradient Outer Product in kernel regression provably recovers the central subspace for multi-index models
May 14, 2026Libin Zhu, Damek Davis, Dmitriy Drusvyatskiy +1Kernel Ridge Regression Kernel Method
Learning with Shallow Neural Networks on Cluster-Structured Features
May 14, 2026Elisabetta Cornacchia, Laurent MassouliéLow-Dimensional Structure Two-Layer Neural Networks
Orthologic for SAT Solving
May 14, 2026Vladislas de Haldat, Simon Guilloud, Viktor KunčakSatisfiability Propositions
Finite Sample Bounds for Learning with Score Matching
May 13, 2026Devin Smedira, Abhijith Jayakumar, Sidhant Misra +2Optimal Sample Complexity Polynomials
What is Learnable in Valiant's Theory of the Learnable?
May 13, 2026Steve Hanneke, Anay Mehrotra, Grigoris Velegkas +1Singular Learning Theory Optimal Sample Complexity
Provable Quantization with Randomized Hadamard Transform
May 13, 2026Ying Feng, Piotr Indyk, Michael Kapralov +2Calibration-Free Low-Bit Vector Quantization Quantization
Tight Sample Complexity Bounds for Entropic Best Policy Identification
May 13, 2026Amer Essakine, Claire VernadeEntropy Regularized Reinforcement Learning Optimal Policies
Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions
May 13, 2026Ishaq Hamza, Zaiwei ChenSoft Actor-Critic Optimal Policies
Byzantine-Robust Distributed Sparse Learning Revisited
May 13, 2026Yuxuan Wang, Lixin Zhang, Kangqiang LiByzantine Attacks Estimators
The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
May 13, 2026Maximilian Graf, Victor ThuotChange-Point Detection Optimal Sample Complexity
A Survey on Data-Dependent Worst-Case Generalization Bounds
May 13, 2026Hubert Leroux, Jean Marcus, Julien RogerGeneralization Bounds Over-Parameterized Neural Networks
A proximal gradient algorithm for composite log-concave sampling
May 12, 2026Linghai Liu, Sinho ChewiNon-Log-Concave Proximal Gradient Descent
Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds
May 12, 2026Yunbei Xu, Yuzhe Yuan, Ruohan ZhanKullback-Leibler Divergence Autoregressive Model
Lower bounds for one-layer transformers that compute parity
May 12, 2026Daniel HsuTransformer Layers Rectified Linear Unit Networks
Minimax Rates and Spectral Distillation for Tree Ensembles
May 12, 2026Binh Duc Vu, David S. WatsonDecision Trees Random Forest
Price of Quality: Sufficient Conditions for Sparse Recovery using Mixed-Quality Data
May 11, 2026Youssef Chaabouni, David GamarnikSparse Recovery Information-Theoretic Limits
Hierarchical End-to-End Taylor Bounds for Complete Neural Network Verification
May 11, 2026Taha Entesari, Mahyar FazlyabNeural Network Verification Reachability
Don't Fix the Basis -- Learn It: Spectral Representation with Adaptive Basis Learning for PDEs
May 11, 2026Xuxiang Zhao, Angelica I. Aviles-RiveroNeural Operators Partial Differential Equations

May 26, 2026 · stat.MLJ/K move · Enter open · S save

Iterative Causal Discovery: Per-Edge Impossibility Certificates, Tier-Aware Oracle Queries, and the $1+K$ Lower Bound

Eichi Uehara

aflo, Inc., Tokyo, Japan

Causal-discovery algorithms return a directed graph, yet provide no principled means of distinguishing edge directions identified by the data from those assigned without an identifying assumption. Under the standard Markov and faithfulness conditions, the observational distribution identifies only a Markov equivalence class; orientations within that class are not determined by the joint distribution and cannot be recovered from additional samples alone, but require either a functional restriction or an intervention. We introduce a protocol for observational causal discovery on continuous data that attaches to each candidate edge a discrete impossibility certificate: a RESOLVED code records the identifiability theorem under which the direction was committed, while an IMPOSSIBLE code records the failure mode together with the specific question a domain expert must answer to resolve it. The bivariate cascade is extended with five gated identifiability tiers LSNM, IGCI, Stein, MDL, and PEIT that abstain when their precondition test rejects. Two oracle primitives, the meta-hub query and the node-children query, jointly establish an upper bound of

1+K

expert interactions sufficient to recover any DAG, where

K

denotes the number of non-leaf vertices. Under an ideal-oracle assumption, the bound is met exactly on the asia, sachs, child, and alarm benchmarks.

Causal Foundation Models Identifiability Finite-Sample Certificates Oracles Lower Bounds

Open paper Ask about it PDF