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

110 papers15 papers in the last four weeks, down 21% on the four weeks before. 0.1% of all new papers.

Sep 26, 2026

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

The support recovery problem in mixture of linear classifiers aims to identify the features relevant to the underlying decision rules when data is generated by a mixture of several linear decision rules. In particular, the goal is to recover the support (nonzero coordinates) of ll unknown kk-sparse vectors from sign measurements. Each measurement is generated by selecting one of the ll vectors uniformly at random, and returning the sign of its inner product with a chosen measurement vector. In this paper, we propose adaptive and non-adaptive schemes that significantly improve upon prior results by simultaneously reducing the number of measurements and achieving sublinear decoding time. In particular, our adaptive constructions substantially reduce measurements compared to existing approaches, while also lowering decoding complexity from super-quadratic to sublinear in the ambient dimension. We further provide a non-adaptive scheme that improves previous measurement bounds while maintaining efficient decoding. Overall, our approach yields a more efficient trade-off between sample complexity and decoding time for support recovery in mixture models compared to previously known methods.
Sep 21, 2026

Adversarially Robust PAC Learning with Optimal VC Rates

We study the problem of adversarially robust PAC learning. In this framework, the learner observes independent samples from an unknown distribution over X×{0,1}\mathcal{X} \times \{0,1\}, as in classical PAC learning. However, given a perturbation map U:X→2X\mathcal{U} : \mathcal{X} \to 2^{\mathcal{X}} known to the learner, the goal is to output, with high probability, a predictor that correctly classifies every perturbation z∈U(x)z \in \mathcal{U}(x) of most future examples (x,y)(x,y) drawn from the same underlying distribution. We determine the optimal U\mathcal{U}-independent sample complexity of this problem in both the realizable and agnostic settings. More specifically, for every concept class H\mathcal{H} of VC⁡\operatorname{VC} dimension dd, we prove upper bounds of O(d/ε+log⁡(1/δ)/ε)\mathcal{O} \big( d/ε+ \log(1/δ)/ε\big) in the realizable setting and O(d/ε2+log⁡(1/δ)/ε2)\mathcal{O} \big( d/ε^2 + \log(1/δ)/ε^2 \big) in the agnostic setting, together with an optimal first-order refinement of the latter. These bounds match the corresponding lower bounds for classical PAC learning. Consequently, and perhaps surprisingly, adversarial robustness incurs no additional distribution-free statistical cost, uniformly over all perturbation maps. Our bounds improve exponentially on those of [Montasser, Hanneke, and Srebro; COLT '19]. On the technical side, we present short and elementary proofs based on a new algorithmic principle that we call binomial-bagging. We believe that binomial-bagging and its analysis may be of independent interest.
Sep 16, 2026

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

Can a logged dataset visit every hidden state frequently and still be exponentially uninformative about a target policy's value? We show that it can when the logger depends on history. For every horizon H≥3H \ge 3, we construct two POMDPs with at most two latent states per stage, three actions, and a common logger with three memory states. Action coverage, belief coverage, and two behavior-marginal outcome-revealing conditions all have constants independent of HH. Nevertheless, evaluating a known deterministic target policy to accuracy 1/81/8 requires Θ((3/2)Hlog⁡(1/δ))Θ((3/2)^H \log(1/δ)) logged episodes at confidence 1−δ1-δ, for 0<δ≤1/40 < δ\le 1/4, even when both candidate models are known. The mechanism is simple: a reset erases the unknown transition that determines the target value. We characterize the resulting statistical experiment exactly and obtain a matching optimal estimator. A directed two-lane gridworld realizes the construction, and trajectory simulations agree with its finite-sample prediction. The result establishes intractability for the history-dependent-logging, model-based case posed by Zhang and Jiang (2025, arXiv:2503.01134), under their behavior-marginal definition of revealing.
Sep 14, 2026

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

We show that logconcave probability measures along the Gaussian cooling path have thin-shell stability, generalizing the thin-shell theorem. This result leads to improved complexity for the fundamental problem of sampling an arbitrary logconcave distribution from a cold start. For (near-)isotropic logconcave distributions, the complexity is nearly n2.5n^{2.5}, improving the previous bound of n2.75n^{2.75}, and matching the complexity of the abstract Speedy walk.
Sep 14, 2026

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

We revisit Valiant's algorithm (Commun. ACM'84) for learning nn-variable CNF formulas with clause size kk and variable degree dd from i.i.d. uniform random solutions in the local lemma regime. For fixed t≥1t\geq1, under k≳(1+1/t)log⁡dk\gtrsim(1+1/t)\log d, Valiant's algorithm achieves total variation error ε\varepsilon with O~(n⌈t⌉/ε)\widetilde{O}(n^{\lceil t \rceil}/\varepsilon) sample complexity. For t>1t>1, we prove a matching lower bound for Valiant's algorithm. At t=1t=1 (covering 0<t<10<t<1), we show Valiant's algorithm has optimal sample complexity up to logarithmic factors by an information-theoretic lower bound Ω~(n/ε)\widetildeΩ(n/\varepsilon).
Sep 12, 2026

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

In the best-arm identification problem, we are given nn stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least 1−δ1-δ, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in [0,1][0,1]. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance II, let Δ[i]Δ_{[i]} be the gap between the largest and the ii-th largest mean, let H(I)=∑i=2nΔ[i]−2H(I)=\sum_{i=2}^{n}Δ_{[i]}^{-2}, and let Ent(I)(I) denote the entropy of the normalized complexities of its dyadic gap groups. For every 0<δ<0.10<δ<0.1, we show that the order-oblivious instance-wise lower bound is Θ(H(I)[log⁡(1/δ)+Ent(I)]).Θ (H(I)[\log(1/δ)+Ent(I)]). We also give a single δδ-correct algorithm with expected sample complexity O(H(I)[log⁡(1/δ)+Ent(I)]+Dlog⁡(e+log⁡(e+D))),D=Δ[2]−2,O ( H(I)[\log(1/δ)+Ent(I)] +D\log(e+\log(e+D))),D=Δ_{[2]}^{-2}, without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.
Sep 11, 2026

Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions

We establish the stochastic-gradient query complexity of sampling smooth strongly log-concave distributions in every fixed dimension d≥1d\geq1. For μμ-strongly convex, LL-smooth potentials with unknown minimizers xf⋆x_f^\star in the ball B(0,μ−1/2)\mathbb{B}(0,μ^{-1/2}), and unbiased gradient oracles with variance at most σ2σ^2, the minimax worst-case expected query complexity is Θ(log⁡(1+κ)+σ2με)Θ\left(\log(1+κ)+\frac{σ^2}{μ\varepsilon}\right), jointly optimal for the condition number κ:=L/μκ:=L/μ, variance σ2≥0σ^2\ge 0, and TV accuracy 0<ε≤1/100<\varepsilon\leq 1/10. In the noiseless setting σ=0σ=0, this tight complexity Θ(log⁡(1+κ))Θ\left(\log(1+κ)\right) is independent of ε\varepsilon. Moreover, a gradient-only sampler generates an exact sample with O(log⁡(1+κ)){O}(\log(1+κ)) worst-case expected queries. Without previous ball B(0,μ−1/2)\mathbb{B}(0,μ^{-1/2}), exact sampling from any initial point x0x_0 can be implemented with expected cost O(log⁡(1+κ)+log⁡(1+μ∥x0−xf⋆∥)){O}\left(\log(1+κ)+\log(1+\sqrtμ\|x_0-x_f^\star\|)\right), without knowing the initial distance. We also show that dependence on initial distance is generally unavoidable.
Aug 31, 2026

Bandit Multiclass PAC Learning: Structural Baselines and a Confidence Direct Sum

How much does high confidence cost when a multiclass learner sees only whether its prediction is correct? We separate two behaviors in realizable bandit PAC learning. An anchored dimension gives a general lower bound that is attained, up to universal constants, by a family of product-block classes. In contrast, for n≥16n\ge16 divisible by four, an affine multiplexer with bandit DS dimension 2n−12n-1 has sample complexity Θ((nmin⁡{n,ln⁡(1/δ)}+ln⁡(1/δ))/ε)Θ((n\min\{n,\ln(1/δ)\}+\ln(1/δ))/\varepsilon) in the standard accuracy and confidence regime. Its lower bound applies to adaptive randomized learners with improper outputs. The obstruction is that evidence collected against one candidate group cannot be reused against the others. The better of two algorithms matches this cost. One finds the correct group through a positive response. The other exhausts the rank of successive groups. The resulting confidence profile rules out a universal additive-confidence bound linear in the bandit DS dimension. Moreover, classes with identical anchored dimension, bandit DS dimension, and pointwise label width can have polynomially different sample complexities. We also sharpen the confidence accounting in ListCascade and show how one positive response replaces the bandit DS dimension by the anchored dimension in a general upper bound.
Aug 17, 2026

Learning to Price with Persuasion

Motivated by modern marketplaces, where the platform or the seller routinely gathers detailed user profiles, we study a novel learning theoretic model that simultaneously involves information and mechanism design. Specifically, we consider the economic setting recently introduced by Bergemann et al. (2022), where in addition to the menu of quality-price pairs, the seller offers information on the value of the match between product quality and buyer's taste via a signaling scheme. We relax the assumption that the seller knows the buyers' belief about the distribution of tastes and study the sample requirements of designing a revenue maximizing scheme. We consider both the batch setting where we have access to data from a set of i.i.d. buyers and an online demand query model where we observe the buyers' behaviors to seller's schemes. Despite the apparent non-convexity of the problem, we also give the first FPTAS to compute a scheme that maximizes the revenue within an arbitrarily small additive loss, which was left open by Bergemann et al. (2022). Overall, this brings a new learning perspective in asymmetric economic settings where buyers and sellers know different types of information.
Aug 13, 2026

Active-Trace Complexity Bounds for Moreau--Yosida Unadjusted Langevin Sampling

We study the Moreau--Yosida unadjusted Langevin algorithm (MYULA) for the nonsmooth composite target π(dx)∝exp⁡{−f(x)−g(x)} dx,x∈Rd,π(dx)\propto \exp\{-f(x)-g(x)\}\,dx, \qquad x\in\mathbb R^d, where ff is mm-strongly convex with LfL_f-Lipschitz gradient and gg is convex and GG-Lipschitz. Let gλg_λ be the Moreau envelope of gg, πλπ_λ the corresponding smoothed target, and aλ=tr⁡Hλa_λ=\operatorname{tr}H_λ, where HλH_λ is the a.e./weak Hessian of gλg_λ. We show that the leading MYULA discretization error is controlled by the reference active trace BrefB_{\mathrm{ref}}, the average of aλa_λ along the heat substep of one MYULA update started from πλπ_λ, rather than by the global curvature bound d/λd/λ. If MλM_λ is an a.e. upper bound for aλa_λ, then, up to logarithmic factors, N≲1m[Lf+τf+G2+Brefεalg2+Mλεalg],τf:=sup⁡xtr⁡∇2f(x),N \lesssim \frac{1}{m} \left[ L_f + \frac{ τ_f+G^2+B_{\mathrm{ref}} }{ \varepsilon_{\mathrm{alg}}^2 } + \frac{M_λ}{\varepsilon_{\mathrm{alg}}} \right], \qquad τ_f:= \sup_x\operatorname{tr}\nabla^2 f(x), iterations suffice to ensure m W2(μN,πλ)≤εalg\sqrt m\,W_2(μ_N,π_λ)\leq\varepsilon_{\mathrm{alg}}, where μNμ_N is the law of the NN-th iterate and W2W_2 is the quadratic Wasserstein distance. We also prove the Moreau-bias bound m W2(πλ,π)≤G2λ4.\sqrt m\,W_2(π_λ,π) \leq \frac{G^2λ}{4}. Thus, choosing λ≍ε/G2λ\asymp\varepsilon/G^2 gives an end-to-end guarantee for ππ. The universal estimate Bref≤d/λB_{\mathrm{ref}}\leq d/λ yields O~(ε−3)\widetilde O(\varepsilon^{-3}) accuracy dependence. For the structured piecewise-linear, lasso-type, group, and total-variation penalties considered here, curvature--tube estimates make BrefB_{\mathrm{ref}} independent of λλ, yielding O~(ε−2)\widetilde O(\varepsilon^{-2}) for the same classical MYULA kernel.
Aug 5, 2026

The Sample Complexity of Distributionally Robust PAC Learning under Cressie--Read Divergences

We study distributionally robust PAC learning for the 00--11-loss, where adversarial perturbations of the data distribution are constrained by a Cressie--Read divergence of order k>1k>1 and radius ρ≥0ρ\geq 0. For hypothesis classes with VC dimension dd, we establish realizable and agnostic sample-complexity bounds tight up to constant and logarithmic factors, respectively; ordinary empirical risk minimization attains both rates up to logarithmic factors. For target accuracy ε∈(0,1)\varepsilon\in(0,1) and confidence δ∈(0,1)δ\in(0,1), their respective orders are max⁡ ⁣{1ε,ρ1k−1εk⋆}⋅(d+log⁡δ−1)andmax⁡ ⁣{1ε2,ρ1k−1εk⋆∨2}⋅(d+log⁡δ−1),\max\!\left\{\frac{1}{\varepsilon}, \frac{ρ^{\frac 1{k-1}}}{\varepsilon^{k_\star}} \right\}\cdot(d+\log δ^{-1}) \qquad\text{and}\qquad \max\!\left\{\frac{1}{\varepsilon^2}, \frac{ρ^{\frac1{k-1}}}{\varepsilon^{k_\star\vee 2}} \right\}\cdot(d+\log δ^{-1}), where k⋆=k/(k−1)k_\star={k}/{(k-1)}. For every fixed ρ>0ρ>0, robustness changes the realizable ε\varepsilon-dependence from ε−1\varepsilon^{-1} to ε−k⋆\varepsilon^{-k_\star} as ε↓0\varepsilon\downarrow0. In the agnostic case, for 1<k<21<k<2, robustness changes the ε\varepsilon-dependence from ε−2\varepsilon^{-2} to ε−k⋆\varepsilon^{-k_\star}, whereas for k≥2k\geq2 the exponent remains the classical 22, with nontrivial ρρ-dependence. Building on the known scalar reduction of robust 00--11 risk to ordinary classification error, our analysis reveals a scale-sensitive interaction between the statistical estimation of classification error and its amplification by robustness, sharply explaining the transition in the agnostic rate. We extend the previously studied χ2χ^2-divergence case to every Cressie--Read order k>1k>1, close its upper--lower gaps, and recover standard PAC learning rates as ρ→0ρ\to0, unlike previous bounds that fail to interpolate correctly in this limit.
Aug 4, 2026

Sample Complexity of Multicalibration for Multilevel Properties

Calibration requires a predictor to be unbiased after conditioning on its own predictions. Multicalibration asks for this guarantee simultaneously across a collection of groups. Many prediction tasks ask for several related features of the same conditional outcome distribution: variance is defined relative to the mean, skewness relative to both mean and variance, and conditional value at risk relative to a quantile. We study multicalibration for a sequence of kk properties in which each property is identifiable once the preceding properties are fixed. This framework includes Bayes pairs but does not require the properties to arise from a single loss. For every fixed k≥2k\ge2, we establish matching upper and lower sample-complexity bounds up to logarithmic factors under regularity conditions. Even with only polylogarithmically many binary groups, achieving multicalibration error ε\varepsilon requires Ω~(ε−(k+2))\widetildeΩ(\varepsilon^{-(k+2)}) samples. Conversely, for any finite group family G\mathcal G, we give a randomized learner using O(ε−(k+2)+ε−2log⁡∣G∣)O(\varepsilon^{-(k+2)}+\varepsilon^{-2}\log|\mathcal G|) samples. Thus the sample complexity is Θ~(ε−(k+2))\widetildeΘ(\varepsilon^{-(k+2)}) for polynomial-size group families. We instantiate the theory for three canonical examples.
Aug 3, 2026

Interaction Is Not Necessary for Order-Optimal 1-Bit Mean Estimation

This paper is concerned with one-bit mean estimation, where each independent sample is represented by a single binary message. We consider distributions on R\mathbb{R} with mean in [−λ,λ][-λ,λ] and absolute kk-th central moment at most σkσ^k, where k>1k>1 is fixed. For this class, previous work attained the optimal sample complexity for general queries using a two-stage protocol. The first stage localizes the mean. The second-stage queries are chosen after localization and refine the estimate around the decoded center. We show that this interaction can be avoided by constructing a randomized fully non-adaptive protocol that fixes all queries before observing the data and matches the optimal adaptive sample complexity. For target accuracy εε and confidence 1−δ1-δ, its sample complexity scales as log⁡λσ+{(σ/ε)2log⁡(1/δ),k>2,(σ/ε)2log⁡(σ/ε)log⁡(1/δ),k=2,(σ/ε)k/(k−1)log⁡(1/δ),1<k<2,\log\fracλσ + \begin{cases} (σ/ε)^2\log(1/δ), & k>2,\\ (σ/ε)^2\log(σ/ε)\log(1/δ), & k=2,\\ (σ/ε)^{k/(k-1)}\log(1/δ), & 1<k<2, \end{cases} up to constants depending only on kk. In the range covered by the known lower bound, this rate is minimax optimal even among fully adaptive protocols. This gives a negative answer to the COLT 2026 open problem asking whether interaction is necessary for order-optimal one-bit mean estimation with general queries \citep[Open Problem~1]{lau2026open}.
Jul 30, 2026

Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection

Low-Rank Adaptation (LoRA) has become the standard mechanism for fine-tuning large pretrained models, yet its statistical properties remain only partially understood. Existing generalization results provide upper bounds of the form O~(sqrt(rd/n)) or O~(rd/n), but a matching lower bound is missing, and the question of how to choose the LoRA rank r has no formal answer. Both gaps are closed here. A local Rademacher argument establishes an upper bound of O~(rd/n) on the excess risk of the empirical risk minimizer over rank-r LoRA, whenever the target adaptation has rank at most r. A matching minimax lower bound of Omega(rd/n) is then proved via a Fano-type packing of the rank-r subspace of R^{d x d}; the bound applies to any estimator whose output lies in the rank-r LoRA class. Combining the two yields a rank-selection dichotomy. For the constrained empirical risk minimizer, the optimal rank equals the intrinsic rank r*, and over-ranking strictly hurts. For adaptive estimators of the nuclear-norm-then-truncate type, over-ranking is harmless and the rate saturates at Theta~(r* d / n) regardless of r. Taken together, the three results characterize the statistical complexity of LoRA fine-tuning within the well-specified locally quadratic regime, and identify the empirically observed over-parameterization penalty as a property of unregularized empirical risk minimization rather than of the LoRA class itself. Predictions of the theory are verified on a synthetic trace-regression benchmark and on real LoRA fine-tuning across three (model, task) configurations covering DistilBERT and RoBERTa on SST-2 and MRPC. All configurations exhibit the predicted U-shape in validation loss, with two showing statistically significant loss inflation at large ranks (paired permutation p = 0.016).
Jul 28, 2026

Denoising growth complexity: Data geometry and certified schedules for diffusion sampling

Two central challenges in diffusion-based sampling are the theoretical one of understanding their remarkable effectiveness even in high-dimensional settings, and the practical one of designing algorithms with certified performance guarantees. We show that these questions are intimately connected via the denoising growth complexity (DGC\mathsf{DGC}). It is a geometric measure defined by a log-time weighted integral of the derivative of the denoising mean-squared error along the Gaussian heat flow. We show how the DGC\mathsf{DGC} increments lead to a simple and explicit bound on the KL error of an Euler scheme applied to the stochastic innovations representation. The bound is local along the path: each step is controlled by the corresponding DGC\mathsf{DGC} increment and its relative stepsize. This structure allows us to derive KL sampling guarantees for optimized stepsize schedules, both in a simpler single-block setting and in a more refined KK-block setting. The DGC\mathsf{DGC} function has a natural martingale structure, which we exploit to develop fully data-certified versions of these algorithms. It also admits information-theoretic upper bounds in terms of covariance, rate distortion, metric entropy, and the Poincar'e constant, thereby recovering and sharpening a range of existing diffusion-sampling guarantees, as well as giving new results. In log heat-time, the fine partition limit is governed by an integral involving the square root of the DGC\mathsf{DGC} density, whereas a single-block schedule depends on its ordinary integral. This comparison precisely characterizes when adaptation to data geometry yields substantial computational gains, including logarithmic-to-constant separations for simple Gaussian mixture models.
Jul 26, 2026

Generalization bounds and sample complexity for remaining useful life prediction from complete degradation trajectories

Data-driven remaining useful life (RUL) prediction requires complete degradation trajectories for training, yet such run-to-failure data are scarce and expensive. Practitioners currently lack principled guidance on how many failure examples suffice for a given model and accuracy target. This paper develops a sample complexity framework for RUL prediction comprising seven main results organised around three themes. First, we establish fundamental learning rates: a distribution-free generalization bound shows that the uniform deviation of the mean squared error decreases as O(B2p/n)O(B^{2}\sqrt{p/n}), where pp is the model complexity and nn the number of trajectories, and a minimax lower bound proves that the Θ(p/n)Θ(p/n) rate is unimprovable.} \rev{Second, we quantify how domain knowledge accelerates learning: incorporating degradation physics reduces data requirements by up to two orders of magnitude for deep networks, a Bernstein-type analysis achieves the minimax-optimal O(p/n)O(p/n) rate under high signal-to-noise conditions, and closed-form penalties reveal when an incorrectly assumed physics model hurts rather than helps. Third, we characterise the impact of data quality: fleet variability induces an irreducible bias−-variance tradeoff, while right-censored observations suffer an efficiency loss that depends critically on the degradation class.} Closed-form expressions are provided for exponential, power-law, and stretched-exponential degradation. \rev{Cross-domain validation against published turbofan, battery, and bearing benchmarks confirms the theoretical predictions within a factor of 2−-3 on average. The results yield practical guidelines for planning data collection, selecting model complexity, and evaluating physics model assumptions in prognostics applications.
Jul 21, 2026

The Tractability Landscape of Sampling with Inexact Scores

We provide a simple and tight characterization of the types of inexact score oracle access that permit sampling with vanishing total variation bias, for a standard, well-behaved target family. Our main result shows that any weaker error than the sub-Gaussian assumption used by [YW26] rules out the tractability of unbiased sampling. This strengthens the conclusion of [CCSW26] to be algorithm-agnostic, and to hold for a wider range of error assumptions.
Jul 21, 2026

On the Limits of Sampling-Based Reachability: Geometry, Dynamics, and Sample Complexity

Reachability analysis is central to safety-critical control, robotics, and neural network verification, but classical computational methods, such as Hamilton--Jacobi reachability and set propagation, scale poorly with state dimension. Sampling-based methods have emerged as a promising alternative, often providing finite-sample guarantees that bound the probability-mass left uncovered. However, an explicit account of how the geometry of the initial set, the dynamics, and the sampling law affect the accuracy of the estimator is not fully available in the literature. We study this by casting sampling-based reachable-set recovery as geometric support estimation over a family of problems specified by an initial set, its dynamics, and a sampling law. First, we identify two regularity properties, positive reach of the initial set's complement and Lipschitz continuity of the dynamics, that together make recovery well-posed: a probability-mass coverage guarantee can be upgraded to accuracy rr in Hausdorff distance. Second, we bound the resulting sample complexity: recovery is achievable with O~((eLT/r)n)\tilde{\mathcal{O}}\big((e^{LT}/r)^n\big) samples, exponential in both the state dimension and the time horizon. Third, we show that neither can be removed: a minimax lower bound of Ω~((eLT/r)n)\tildeΩ\big((e^{LT}/r)^n\big) holds for every estimator, so the exponential dependence on dimension and the degradation over the horizon are both intrinsic, not artifacts of a particular method. Experiments on nonlinear systems confirm that adversarial sampling improves constants but not the scaling.
Jul 18, 2026

Tight Sample Bounds for Renyi and Min-Entropy Estimation

Estimating entropy from samples is fundamental in information theory and property testing. Shannon entropy measures average uncertainty and can be estimated to constant additive accuracy over a kk-symbol alphabet using Θ(k/log⁡k)Θ(k/\log k) samples. Min-entropy depends only on the most likely symbol. Both are special cases of order-αα R'{e}nyi entropy, HαH_α. We characterize the sample complexity of estimating min-entropy and R'{e}nyi entropy for kk and integer α>1α>1; our lower bounds also hold for noninteger α≥1.001α\ge1.001. We prove that min-entropy estimation to constant additive accuracy has sample complexity Θ(klog⁡k)Θ(k\log k). The upper bound uses the largest empirical frequency and concentration via dyadic grouping. The matching lower bound hides a slightly heavier symbol at a uniformly random location. Thus, min-entropy requires Θ(log⁡2k)Θ(\log^2 k) more samples than Shannon entropy and corrects a previously stated Θ(k/log⁡k)Θ(k/\log k) characterization. For every integer 2≤α≤c0log⁡k2\leα\le c_0\log k, we prove the matching fixed-accuracy bound Θc0(αk1−1/α)Θ_{c_0}(αk^{1-1/α}). Previous results gave Ωα(k1−1/α)Ω_α(k^{1-1/α}) for fixed integer α>1α>1 and Oc0(α2k1−1/α)O_{c_0}(α^2k^{1-1/α}) for all integer α>1α>1. Our upper bound analyzes an unbiased falling-factorial estimator based on αα-way collisions, while a hidden-heavy-coordinate construction gives the matching lower bound and shows that the factor αα is unavoidable. For every real 1.001≤α≤c0log⁡k1.001\leα\le c_0\log k, we prove the uniform lower bound Ωc0(αk1−1/α)Ω_{c_0}(αk^{1-1/α}). Finally, since 0≤Hα(p)−H∞(p)≤log⁡k/(α−1)0\le H_α(p)-H_\infty(p)\le\log k/(α-1), min-entropy uniformly approximates HαH_α when αα is a sufficiently large multiple of log⁡k\log k. Combining this reduction with our min-entropy bounds gives Θε(klog⁡k)Θ_\varepsilon(k\log k) sample complexity in the high-order regime.
Jul 13, 2026

From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

A theoretical understanding of Transformers is crucial to better understand the capacities and limitations of large language models (LLMs). There is much work analyzing the expressivity of attention-based models. By proposing handcrafted weights or using computational complexity arguments, a large amount of past theoretical works have sought to characterize which tasks are and which are not in the hypothesis class of Transformer models. However, little work investigates the learnability of such solutions. In this work, we make progress towards this goal. Inspired by recent loss landscape analysis work, we propose preliminary sample complexity bounds for learning C-RASP constructions with Transformers.
Jul 10, 2026

Data-Efficient Deep Learning: Empirical Guidelines for Training Set Size Estimation in Inertial Sensor Classification

Deep learning models dependency on large-scale inertial datasets presents a significant bottleneck in inertial sensor-based classification tasks, such as human activity recognition and smartphone location recognition. In these domains, data collection requires massive recording campaigns that are complex, time-consuming, and difficult to scale. Currently, data-driven guidelines for determining the minimum sample size required to reach a desired accuracy level do not exist. To address this gap, this study presents a systematic empirical evaluation of learning curve convergence rates in inertial classification. We introduce a unified framework that analyzes classification performance under both binary and multi-class scenarios, and derive an empirical formula to estimate performance relative to dataset size. Testing across six diverse, real-world datasets totaling 102.7 hours of inertial measurements demonstrates that accuracy follows a consistent logarithmic growth pattern, regardless of task complexity. Leveraging this finding, we propose a quantitative stability point metric, defined as the sample size required for the learning curve to stabilize within a predefined mean absolute percentage deviation of its asymptotic maximum. Our analysis reveals that models often reach practical stability with substantially fewer samples than traditional heuristics suggest. Ultimately, we offer a generalizable framework to extrapolate total data requirements from small-scale pilot studies, optimizing the tradeoff between recording effort and model reliability. These findings shift the prevailing paradigm from maximizing data volume toward optimizing data efficiency, offering concrete, data-backed guidelines for planning recording campaigns in inertial sensing applications.
Jul 7, 2026

Width-Robust Learnability in Mean-Field Bayesian Neural Networks

Infinite-width limits are a standard way to reason about neural networks, but it is not automatic that the limiting learner has the same complexity-theoretic inductive bias as large finite networks. We study this question for Bayesian neural networks at the mean-field, or critical feature-learning, scaling. The central quantity is the reduced entropy s∞(y,ε)=lim sup⁡N−1Nlog⁡πN0(L≤ε),s_\infty(y,\varepsilon)=\limsup_N -\frac{1}{N}\log π_N^0(L\le \varepsilon), the intensive prior cost of representing a target function yy to population mean-squared error ε\varepsilon. Our main result is a width-robust learnability theorem. At fixed depth, a family of Boolean-cube targets is learnable from polynomially many samples at infinite width if and only if it is learnable at polynomial width, if and only if its reduced entropy is polynomially bounded. Equivalently, up to polynomial slack in accuracy, the Bayesian mean-field learner generalizes exactly on the targets that can be represented by polynomial-size networks. The forward direction is proved by a form of subsampling: from the infinitely many hidden neurons in the mean-field solution, one can select polynomially many representatives and still preserve the learned function on every input simultaneously. At the critical scaling this subsampling has both an active'' component, which keeps the data-dependent low-dimensional statistics, and a lazy'' component, which resamples the entropy-dominated directions from the prior. Thus the infinite-width mean-field limit gives a clean analytic description of learning without introducing spurious width-dependent generalization power.
Jul 3, 2026

A Hierarchy of Policy Learning Problems

Policy learning has received substantial attention with the goal of learning policies from observational data for decision-making. A majority of work in this space has focused on developing algorithms for computing policies that minimize regret compared to the optimal policy. However, in many practical settings, there is insufficient data to obtain low regret. As a result, recent work has shifted attention to alternative objectives, most notably, studying whether it is possible to learn an improving policy that statistically significantly outperforms baseline policies. We argue that there is substantial merit in studying a broader range of policy learning problems. When there is insufficient data to learn an improving policy, there may still be useful questions that can be answered. To this end, we provide a mathematical framework for studying the relationships between policy learning problems. We formalize three problems within our framework: beyond the optimal policy problem and the improving policy problem, we also propose the policy existence problem, which aims to determine if an improving policy exists. Within our framework, we show that the policy existence problem reduces to the improving policy problem, which in turn reduces to the optimal policy problem; these reductions prove that each problem is at least as easy as the next one (in sample complexity). A key question remains: is this hardness strict? We provide partial answers. First, the gap between the optimal policy and improving policy problems is strict. For the improving policy and policy existence problems, we prove that a sublinear polynomial gap exists under natural conditions on improving policy learning algorithms. Thus, we may be able to answer questions about the existence of an improving policy even when we cannot find one. These results highlight the value in studying a broader range of policy learning problems.
Jun 28, 2026

Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

Scientific discovery via symbolic regression is often viewed as statistically and computationally intractable because the hypothesis space of expressions grows combinatorially with depth. This paper revisits the statistical side through the lens of PAC learning, focusing on compositional function trees built from a finite vocabulary of smooth operators (e.g., {+,×,sin⁡,exp⁡}\{+,\times,\sin,\exp\} and affine maps). We prove that the relevant generalization quantity, Rademacher complexity, hence the excess risk, does not necessarily blow up exponentially with the number of distinct symbolic structures, but is controlled by (i) the depth dd and (ii) the Lipschitz constants of the base operators along the composed computation graph. Concretely, under mild Lipschitz conditions on operators and bounded affine leaves, a finite-union bound over a vocabulary of size K=∣Hbase∣K=|\mathcal{H}_{\mathrm{base}}| together with Maurer-type vector contraction yields Rn(Hcompd)≤(Kb2L)d−1Rn(Hcomp1)\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{d}) \leq (Kb\sqrt{2}L)^{d-1}\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1}) with arity bound bb; corresponding high-probability risk bounds scale as O(Ld/n)\mathcal{O}(L^{d}/\sqrt{n}) when K,b=O(1)K,b=O(1) and Rn(Hcomp1)=O(n−1/2)\mathfrak{R}_n(\mathcal{H}_{\mathrm{comp}}^{1})=O(n^{-1/2}). We complement the theory with a modular codebase that trains differentiable operator trees (not MLPs) on synthetic "physics-like" targets of controlled depth and shows that the empirical generalization gap correlates positively with the predicted complexity term (L^d)/n(\widehat{L}^{d})/\sqrt{n}.
Jun 25, 2026

Recovering Governing Equations from Solution Data: Identifiability Bounds for Linear and Nonlinear ODEs

Learning governing equations from observed solution data is a fundamental challenge in scientific machine learning, yet the theoretical conditions under which a ground-truth ODE can be uniquely and stably identified from multiple solution observations remain largely undeveloped, and no quantitative analysis of the sample complexity of such learning tasks exists in the literature. To address this gap, we introduce the Hausdorff distance on solution sets as the natural metric for comparing differential equations, since it captures the worst-case separation between two equations over all admissible initial conditions and thus encodes the minimax structure of the identification problem. We establish identifiability bounds for governing ODEs across a wide class of structure equations--ranging from linear ODEs to nonlinear classes with Lipschitz (Hölder)-continuous vector fields--characterizing precisely when two distinct equations can be distinguished from solution data. Using this metric, we derive metric entropy estimates for the relevant ODE classes and analyze sample complexity bounds, quantifying how many solution observations are needed to reliably recover the governing equation.
Jun 23, 2026

Sample complexity of unbalanced entropic OT

Optimal transport (OT) has become a central language for comparing probability measures, but exact balanced OT is often both too rigid for data with missing, created, or destroyed mass and subject to unfavorable high-dimensional sample complexity. Entropic regularization and unbalanced relaxations address these limitations in complementary ways. Entropy smooths the geometry, improves statistical behavior, and enables fast Sinkhorn-type algorithms, while unbalanced marginal penalties replace hard conservation constraints by divergence terms adapted to noisy empirical data. This paper studies the sample complexity of entropic unbalanced OT at the level of the optimal coupling, rather than only the scalar transport value. We develop a translation-invariant dual formulation, prove compactness and strong convexity properties for the intrinsic dual variables, and convert these geometric estimates into high-probability finite-sample bounds for empirical couplings. The results clarify why regularization is a practical necessity in machine learning applications: it softens the curse of dimensionality, reduces the number of samples needed for stable transport estimation, and keeps the resulting estimators compatible with scalable Sinkhorn-type solvers.
Jun 23, 2026

Token Complexity of Certifying Stochastic-Oracle Reliability

Wang~\cite{Wang2026} introduced the Stochastic-Oracle Turing Machine (SOTM) framework and defined token complexity as the minimum expected cost of interacting with a stochastic oracle needed to attain a specified solution quality for a task. This paper develops an analogous notion for certifying the reliability of a stochastic oracle on a given domain. Certification token complexity is the minimum expected token cost required, with controlled error probability, to distinguish oracles that meet a target reliability level from those that fall below a lower reliability threshold. We construct an SPRT-based certification SOTM that queries the oracle, computes binary correctness scores, and stops when the accumulated log-likelihood evidence crosses a decision threshold. The SOTM halts almost surely, satisfies the desired two-sided error guarantee over the reliability regions to be certified, and yields an explicit upper bound on certification token complexity in terms of the reliability thresholds, the error bound, and the expected per-turn token cost. We then establish a matching information-theoretic lower bound: even with adaptive queries, every error-bounded certification SOTM must incur the same leading-order expected token cost as the SPRT-based construction as the prescribed error bound tends to zero. Together, these bounds characterize the leading-order certification token complexity in the small-error regime.
Jun 15, 2026

Tight L∞L_\infty Sample Complexity for Low-Degree and Sparse Boolean Polynomials

Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform L∞L_\infty-error guarantees rather than the usual L2L_2-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most dd on nn variables, the sample complexity scales as nd+1n^{d+1}. Second, for ss-sparse Fourier-Walsh polynomials with s≤ns \leq n, it scales as ns2ns^2. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as ndn^d and nsns, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the L2L_2-norm do not naturally extend to the L∞L_\infty-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the L∞L_\infty-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.
Jun 10, 2026

Quantum Occam Learning: Sample-Supported Expressibility for Circuit-Based Quantum Learning

A central principle in quantum machine learning is that an ansatz should be expressive enough to represent the quantum data of interest. Yet, the expressibility is statistically meaningful only insofar as it can be learned from finitely many copies of an unknown quantum state. In this work, we develop an information-theoretic Occam theory for quantum data generated by finite-size quantum circuits. For the class Sn,GS_{n,G} of nn-qubit pure states preparable with at most GG two-qubit gates, a metric-entropy argument gives the realizable sample law Θ~(G/ε2)\widetildeΘ(G/ε^2) in the circuit-limited regime. For an arbitrary source ρ^\hatρ, we introduce the best GG-gate approximation error dG(ρ^)d_G(\hatρ) and the approximate circuit complexity Cη(ρ^)C_η(\hatρ). We prove an agnostic quantum Occam theorem: with MM copies, one can learn up to the best GG-gate approximation error plus a statistical penalty O~(G/M)\widetilde{O}(\sqrt{G/M}). We then remove the need to know GG in advance through an adaptive model-selection theorem whose oracle inequality selects the circuit complexity justified by the data. Matching lower bounds yield a sample-supported expressibility law: at trace-distance accuracy εε, MM samples can support only Gsupported≃Mε2G_{\rm supported} \simeq Mε^2 gates, up to logarithmic factors and tomography saturation at 2n2^n. Thus, the circuit complexity becomes an adaptive statistical resource rather than a static promise. Our framework turns bounded circuit complexity into a model-selection principle for quantum machine learning.
Jun 9, 2026

The Power of Test-Time Training for Approximate Sampling

Efficiently sampling from a complex probability distribution is a fundamental problem which has become increasingly pertinent in recent years with the rise of generative AI, as sophisticated sampling procedures from LLMs have been proposed to solve challenging reasoning problems. The efficacy of such sampling algorithms is limited, however, by the relationship between the LLM and the particular sampling task at hand, which has motivated the framework of test-time training (TTT). TTT works by updating a model's weights in response to partial generations and reward feedback received at inference time, thus adapting to the particular problem. In this work, we propose a formalization for TTT as the problem of producing a sample from a given probability measure μ⋆μ^\star belonging to a known class F{F} of distributions, given an oracle μ^\hat μ which yields approximate density estimates for μ⋆μ^\star. This is closely related to the problem of reducing sampling to approximate counting studied in seminal works of Jerrum, Valiant & Vazirani (1986) and Jerrum & Sinclair (1989): namely, when F{F} is the class of all distributions, it coincides exactly with the aforementioned counting-to-sampling reduction. In this paper, we first show a quadratic lower bound on the query complexity of sampling from μ⋆μ^\star given query access to μ^\hat μ (for sufficiently large classes F{F}), thus showing that the random walk approach proposed by Jerrum & Sinclair (1989) and refined by Hayes & Sinclair (2010), is optimal. This answers an open question posed by Hayes & Sinclair. We then show that this lower bound can be circumvented if the size of F{F} is bounded appropriately. As we discuss, this latter result can be viewed as an abstraction of TTT, and thus represents a starting point for the development of a principled theoretical framework for TTT.