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.

When Does Cheap Physics Help? Gated Multi-Fidelity Physics-Informed Networks with Provable Sample Savings and Conformal Guarantees
Feb 1, 2026laf Yunus Laitinen Imanov, Rana Irem Turhan, Isgandar JafarliMultifidelity Modeling Physics-Informed ML
Department of Applied Mathematics and Computer Science (DTU Compute), Technical University of Denmark, Kongens Lyngby, Denmark
Order-Optimal Sample Complexity of Rectified Flows
Jan 28, 2026Hari Krishna Sahoo, Mudit Gaur, Vaneet AggarwalRectified Flow Flow-Based Generative Modeling
Purdue University
Fast Score-Based Sampling via Log-Concave Reductions
Dec 30, 2025M. J. WainwrightSample Complexity Log-Concave Sampling
Laboratory for Information and Decision Systems · Statistics and Data Science Center · EECS & Mathematics +1
Implicit Bias and Invariance: How Hopfield Networks Efficiently Learn Graph Orbits
Dec 16, 2025Michael Murray, Tenzin Chan, Kedar Karhadker +1Sample Complexity Neural Network Memorization
Mathematical Sciences, University of Bath · Department of Mathematics, UCLA · Algebraic
Multi-Dictionary Learning for Low Rank Sparse Coding
Sep 12, 2025Boya Ma, Abram Magner, Maxwell McNeil +1Representation Learning Sample Complexity
University at Albany – SUNY, Computer Science, Albany, NY, USA
The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
Sep 1, 2025Youssef Chaabouni, David GamarnikSparse Recovery Sample Complexity
Massachusetts Institute of Technology
The Sample Complexity of Membership Inference and Privacy Auditing
Aug 26, 2025Mahdi Haghifam, Adam Smith, Jonathan UllmanMembership Inference Attacks Sample Complexity
Khoury College of Computer Sciences, Northeastern University. · Department of Computer Science, Boston University.
Sample Complexity of Linear Quadratic Regulator Without Initial Stability
Feb 20, 2025Amirreza Neshaei Moghaddam, Alex Olshevsky, Bahman GharesifardRL Control Sample Complexity
Breaking the Curse of Dimensionality: Diffusion Models Efficiently Learn Low-Dimensional Distributions
Sep 4, 2024Peng Wang, Huijie Zhang, Zekai Zhang +3Intrinsic Dimensionality Sample Complexity
University of Macau · University of Michigan · University of California, Berkeley
Help Me Help You: The Aggregate Value of Source and Target Data in Transfer Learning
Aug 29, 2024Steve Hanneke, Samory KpotufeTransfer Learning Cross-Domain Transfer Learning
Purdue University · Columbia University
Model Selection and Parameter Estimation of One-Dimensional Gaussian Mixture Models
Apr 19, 2024Xinyu Liu, Hai ZhangSample Complexity Gaussian Mixture Models
Department of Mathematics Hong Kong University of Science and Technology Clear Water Bay, Hong Kong SAR, China
Robust Budget Pacing with a Single Sample
Feb 3, 2023Santiago Balseiro, Rachitesh Kumar, Vahab Mirrokni +2Sample Complexity Online Advertising
DRO, Columbia Business School, New York, NY, USA · Google Research, New York, NY, USA · IEOR, Columbia University, New York, NY, USA

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

When Does Cheap Physics Help? Gated Multi-Fidelity Physics-Informed Networks with Provable Sample Savings and Conformal Guarantees

laf Yunus Laitinen Imanov, Rana Irem Turhan, Isgandar Jafarli

Department of Applied Mathematics and Computer Science (DTU Compute), Technical University of Denmark, Kongens Lyngby, Denmark

Multifidelity Modeling Physics-Informed ML Sample Complexity

Open paper AskPDF arXiv

High-fidelity (HF) simulations of parametric partial differential equations are expensive, whereas low-fidelity (LF) models such as coarse grids or simplified physics are cheap but biased. Multi-fidelity physics-informed neural networks combine the two, yet it remains unclear when cheap physics actually reduces the number of HF solves, and existing methods silently fail when the LF model is misleading and offer no guaranteed uncertainty. We answer the first question with a sharp sample-complexity bound: learning the HF field through its discrepancy from the LF model reduces the number of HF samples needed for accuracy

\varepsilon

by the factor

κ^{2γ}

, where

κ

is the ratio of the complexity of the discrepancy to that of the HF field and

γ

is the effective-dimension exponent, and we confirm the predicted scaling with exact risk computations in a kernel model. Guided by the analysis, we propose GaMF-PINN, a gated multi-fidelity PINN that learns where to trust the LF model and falls back to physics-only learning where it does not, together with a function-level conformal procedure that returns uncertainty bands containing the entire HF solution with probability at least

1-α

in finite samples. We release MFPDE-Bench, an open benchmark of paired LF/HF solvers for four parametric PDEs with coarse-grid and simplified-physics LF models. Across MFPDE-Bench, GaMF-PINN reaches the accuracy of a standard HF-PINN with up to 8x fewer HF solves, remains robust when the LF model is deliberately corrupted, and attains the nominal coverage where Bayesian PINNs and deep ensembles under-cover.