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.

Nov 9, 2026

Identifiable but Hard to Estimate: Rotation in Equally Spaced Overcomplete ICA

How many observations are needed to estimate a common rotation in two-dimensional overcomplete independent component analysis? We study equally spaced mixing columns with known source count, common source law, and column norm. For a fixed non-Gaussian fourth-order Gram-Charlier source law, the rotation is identifiable modulo the column spacing. Yet the sample size for fixed relative angular accuracy grows exponentially with the source count. We characterize this sample size, up to absolute constants, by the reciprocal of the squared Hellinger distance between two rotations separated by half the column spacing. An explicit radially weighted phase estimator attains this scale uniformly over the rotation family, using the observation radius to prevent cancellation in the mean of an angular harmonic. We also determine the exact exponential decay rate of single-observation total variation for the same pair. This gives bounds on the sample size exponent; its exact value remains open. Finally, a noisy binary-source example shows how an exact zero line of the observed characteristic function can have an exponentially small normal derivative.
Nov 7, 2026

Toward a theory of Evaluability

Machine learning models, particularly large foundation models, are increasingly evaluated along multiple axes that are relevant for their usage. In addition to accuracy measures appropriate for the specific task of interest, measures capturing safety, calibration and fairness properties are often of interest. The classical approach to these problems assumes that the test set has been held out from the training process, an assumption that is increasingly harder to justify for large foundation models. In this work, we formalize a notion of evaluability without this assumption, and ask if it is feasible to evaluate black-box models in settings where our test samples may have been used during training. We study this problem under different settings, capturing different levels of access to the model. We first study the natural setting, where the evaluator only looks at the output of the model on the test set. We fully characterize the class of distributions where accurate evaluation is possible, and show tight upper and lower bounds on the sample complexity of evaluation. Our results show that black-box evaluation in this setup is feasible if and only if the distribution is close to being small support. We then consider evaluation algorithms that can query the model on additional inputs and demonstrate connections to self-correctors studied in program testing. Using these, we show that a small amount of query access can increase the power of the evaluator for natural distributions and concept classes.
Nov 3, 2026

The Price of List Replicability: Tight Bounds for Bias Estimation

We study the sample complexity of list replicable algorithms for estimating the biases of dd coins. An algorithm is (k,ε,δ)(k,\varepsilon,δ)-list replicable if for every bias vector p∈[0,1]d\mathbf{p}\in[0,1]^d, there is a set of outputs Lp⊆RdL_{\mathbf{p}}\subseteq \mathbb{R}^d of at most kk elements such that every y∈Lp\mathbf{y}\in L_{\mathbf{p}} satisfies ∥y−p∥∞≤ε\lVert\mathbf{y}-\mathbf{p}\rVert_\infty\leq\varepsilon, and the algorithm output is in LpL_{\mathbf{p}} with probability at least 1−δ1-δ. Prior work gave a (d+1,ε,δ)(d+1,\varepsilon,δ)-list replicable algorithm with sample complexity O~(d3ε2)\widetilde{O}\left(\frac{d^3}{\varepsilon^2}\right), but no nontrivial sample complexity lower bound was known. We establish the first non-trivial sample complexity lower bound for this problem and give an improved algorithm that matches it up to polylogarithmic factors. Together, these results determine the optimal sample complexity for list size d+1d+1 to be Θ~(d2ε2)\widetildeΘ\left(\frac{d^2}{\varepsilon^2}\right), showing that the quadratic dependence on dimension is inherent up to polylogarithmic factors. More generally, for every k∈[d+1,2d]k\in[d+1,2^d], we establish matching upper and lower bounds of Θ~(d2ε2log⁡k)\widetildeΘ\left(\frac{d^2}{\varepsilon^2\log k}\right) on the total sample complexity.
Nov 2, 2026

The Information Limits of Neural Controlled Differential Equations Under Sparse Observations

Neural controlled differential equations (Neural CDEs) evolve hidden states along continuous paths constructed by interpolating discrete observations. Sparse measurements leave the input between observation times undetermined, and admissible continuous paths consistent with the same data can produce different terminal states. We characterize this ambiguity for planar drivers with bounded speed. The set of compatible terminal states admits a leading-order zonotopic approximation determined by feasible signed areas and transported Lie brackets. Its projection onto a scalar prediction yields a computable, target-specific ambiguity certificate. We also study the number of measurements needed to reduce the remaining uncertainty. For nondegenerate planar CDEs, the optimal worst-case radius over deterministic adaptive sampling policies scales as N−1N^{-1} when speed is bounded and N−2N^{-2} when both speed and acceleration are bounded, where NN is the number of observation intervals. Synthetic experiments assess the certificate using admissible continuous completions and examine the role of path regularity.
Nov 2, 2026

Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity

Calibrated multiaccuracy asks that a predictor be globally calibrated and multiaccurate with respect to a bounded test family GG; that is, its residuals should be uncorrelated with every test g(x)∈Gg(x)\in G. This weakening of multicalibration suffices for many applications. Its sample complexity was not known to improve on that of full multicalibration, which is Θ~(log⁡∣G∣ε2+1ε3)\widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{3}}\right) when ∣G∣|G| is at least a sufficiently large power of log⁡(1/ε)\log(1/\varepsilon). We resolve the sample complexity of ε\varepsilon-calibrated multiaccuracy, showing that it scales as Θ~(log⁡∣G∣ε2+1ε5/2),\widetildeΘ\left(\frac{\log|G|}{\varepsilon^2} + \frac{1}{\varepsilon^{5/2}}\right), separating it from the complexity of multicalibration. The upper bound is obtained by an algorithm that outputs a randomized predictor. For deterministic predictors, we establish the tight rate Θ~(log⁡∣G∣ε2+(log⁡∣G∣)1/3ε8/3)\widetildeΘ\left( \frac{\log|G|}{\varepsilon^2} + \frac{(\log|G|)^{1/3}}{\varepsilon^{8/3}} \right) whenever log⁡∣G∣=Ω(log⁡(1/ε))\log|G|=Ω(\log(1/\varepsilon)). When log⁡∣G∣≤ε−1+κ\log|G|\le\varepsilon^{-1+κ} for any fixed κ∈(0,1)κ\in(0,1), this rate is polynomially larger than the rate for randomized predictors. Thus, unlike for multicalibration, calibrated multiaccuracy exhibits a genuine sample-complexity separation between deterministic and randomized predictors. The matching upper and lower bounds show that the unusual cube-root dependence on log⁡∣G∣\log|G| is intrinsic. At log⁡∣G∣≍ε−1\log|G|\asymp\varepsilon^{-1}, the minimax rates for randomized and deterministic calibrated multiaccuracy both coincide with the minimax rate for multicalibration.
Nov 1, 2026

Generative Modeling with Continuous Flows: Sample Complexity of Flow Matching

Flow matching has emerged as a promising alternative to diffusion-based generative modeling, offering a continuous-time ordinary differential equation formulation with fast sampling and a simple regression-based training objective. Despite its empirical success, some theoretical analyses idealize the learning procedure by assuming that the velocity field is obtained by exact empirical risk minimization. This assumption does not reflect the practical finite-dataset setting, where the empirical flow-matching loss is only approximately minimized by a finite number of stochastic-gradient updates. We develop an empirical-risk-minimizer-free analysis for flow matching that explicitly accounts for both finite-sample statistical error and finite-time empirical optimization error. Our analysis considers a finite dataset of NN flow-matching samples and a learned parameter θTθ_T obtained after TT stochastic gradient updates on the empirical objective. Under regularity assumptions on the interpolation path, sub-exponential source and target distributions, approximation by a bounded-parameter smooth neural velocity class, empirical-loss optimization, and uniform flow stability, we prove a guarantee that holds with high probability over the finite training dataset and in expectation over the stochastic-gradient randomness. The resulting bound separates approximation error, statistical error from the finite dataset, tail error from unbounded source and target distributions, and empirical optimization error from approximate minimization of the finite-sample objective.
Oct 27, 2026

The Structure Gap: When More Data Cannot Replace Structured Reasoning

A persistent belief in modern AI is that sufficiently large learners trained on sufficiently much data can make explicit domain knowledge optional. This paper examines a limitation of that belief. We define structure-encoded problems: tasks whose input-output map is determined, or sharply constrained, by known structure such as a solver, symmetry group, graph, physical law, measurement operator, grammar, combinatorial search space, or optimization objective. For such tasks, the central question is not expressivity--a dense neural network may contain the desired map--but finite-data identification, extrapolation, and certification. We introduce the structure gap: the finite-resource gap between a method that receives the governing structure and a learner that receives only examples. The strongest useful form of the claim is asymptotic rather than absolute: structure-agnostic learning may approach a structured solver as coverage grows, but every finite dataset can leave residual uncertainty that the structure resolves by construction. We prove this exactly for a Gaussian inverse problem: the known-operator Wiener solver attains Bayes risk, while the dense empirical learner in the correct linear class has persistent expected excess risk. We also prove a cell-coverage lower bound and an unobserved-orbit non-identifiability result. Controlled experiments in known-operator inversion, sparse recovery, and graph reachability with size extrapolation instantiate the mechanisms. When validated structure is available, it can constrain the hypothesis space before learning begins, leaving learning to address components the structure does not specify.
Oct 22, 2026

Reverse-KL Policy Distillation: Statistical Guarantees and Limits

Reverse Kullback-Leibler (KL) distillation has shown empirical promise for training language models, but its statistical guarantees and limits remain poorly understood. In particular, the effects of two design choices remain unclear: Does access to the teacher's full action distribution provide an advantage over observing only the probability it assigns to the sampled action? Must training trajectories come from the student (online distillation), or can teacher-generated trajectories (offline distillation) suffice? Our work takes a first step toward understanding the theory underlying these questions. We study the sample complexity of online reverse-KL distillation under two feedback models: the teacher reveals either its full action distribution or only the probability of the student-generated action. We establish minimax bounds for the former and show that substantially more data may be required for the latter. In contrast, offline reverse-KL distillation can attain the same minimax rate whether the teacher reveals its full distribution or only its probability of the teacher-generated action. The key distinction is that teacher-generated actions themselves reveal the teacher's preferences, while queries at student-selected actions can leave those preferences unobserved. This highlights an additional statistical challenge for online distillation compared to offline distillation. These statistical guarantees do not follow simply from optimizing standard distillation objectives: our lower bounds show that common online objectives can fail when candidates are evaluated only on past student-generated trajectories. We develop trajectory-loss and importance-ratio truncation techniques together with policy-space learning to achieve optimal online distillation guarantees.
Oct 21, 2026

The role of locality and weight sharing in convolutional neural networks

The success of convolutional neural networks is often attributed to locality and weight sharing. However, how these two properties separately shape learning, and how their effects depend on the spatial correlations of natural images, remain poorly understood. We address these questions in a teacher-student model with a convolutional teacher acting on PP input positions with correlation cc between positions. We compare convolutional and locally connected students trained by online stochastic gradient descent, and derive ordinary differential equations that describe their dynamics exactly in the limit of large feature dimension DD. For uncorrelated positions (c=0c = 0), the two students follow the same learning trajectory, with the convolutional student learning exactly PP times faster. We also find that locality affects the sample complexity: a student that matches the kernel size of the teacher recovers it from OD(D)\mathcal{O}_{D}(D) samples, whereas OD(Dlog⁡(D))\mathcal{O}_{D}(D\log(D)) samples are needed with a larger kernel. For c>0c > 0, spatial correlations can reduce the advantage of weight sharing. The asymptotic error of the convolutional student grows with cc, whereas that of the locally connected student is independent of cc and overall lower when evaluated at the same learning rate. When the learning rate is instead tuned to the training horizon, however, the locally connected student wins at early times and the convolutional student at late times, with a transition that we predict analytically.
Oct 21, 2026

Asymmetric Likelihood-Free Hypothesis Testing

In likelihood-free hypothesis testing (LFHT), given samples from two unknown distributions P,QP,Q on [n][n] with dTV(P,Q)≥ε\mathrm{d_{TV}}(P,Q)\geq\varepsilon, and from a third distribution D∈{P,Q}D\in\{P,Q\}, the goal is to identify whether D=PD=P or D=QD=Q. We study asymmetric likelihood-free hypothesis testing, where the sample budgets sPs_P and sQs_Q for PP and QQ may differ, and characterize the feasible triples (sP,sQ,sD)(s_P,s_Q,s_D) up to logarithmic factors. We establish that unequal reference budgets can give a polynomial saving. For instance, for constant separation, nn samples from PP and n3/4n^{3/4} from QQ allow testing with O~(n1/4)\widetilde O(n^{1/4}) samples from DD, whereas both existing baselines---symmetric LFHT and unequal-sample closeness testing---require Ω(n)Ω(\sqrt n) samples from DD. We further apply our results to non-adaptive distribution 2-clustering, where the sample allocation among kk distributions must be fixed before observing any data. We obtain matching upper and lower bounds for this problem up to logarithmic factors in terms of the domain size, number of distributions, smaller cluster size, and separation, both with one cluster distribution known and with both unknown. Comparing with known bounds for adaptive sample allocation gives a worst-case adaptivity gap of Θ~(k1/4)\widetildeΘ(k^{1/4}).
Oct 21, 2026

The Price of Choice in Selective Prediction

A selective classifier may be claimed to satisfy a risk-coverage contract if some rule from a predeclared menu (a threshold or a union of KK score intervals) attains coverage at least κκ and error at most αα. Refuting this existential claim requires ruling out every permitted rule. The intersection-union test (IUT) achieves validity without a multiplicity correction, but its sample cost can increase with menu richness. We characterize this cost and compare it with the optimal audit. For a fixed interior risk target αα and gap γγ, the minimax sample size for K-interval menus at coverage floor κκ is K(1−κ)/(κγ2)K(1-κ)/(κγ^2), up to logarithmic factors, in the stated small-gap, large-menu regime; exact IUT attains this rate. The lower bound holds even with a known score distribution, while the upper bound extends to menus of VC dimension dd. Procedures that refuse to reject whenever any rule appears feasible on the audit sample can pay a linear KK cost even when a square-root rate is possible. Reference-free testing reaches a smaller scale under constant-risk alternatives, whereas unknown heterogeneous risks can make the linear cost unavoidable. In simulations with K=4K=4, the raw menu cost varies 7.7-fold between κ=.5κ=.5 and κ=.95κ=.95; after theorem-motivated normalization the endpoint values differ by approximately 5%. Held-out experiments with three VLM judges show positive exact-hiding windows in all 60 split-specific confidence-gate families, with 28/30 contracts chosen on audit-A remaining hidden on untouched audit-B. On a cleaner multi-annotator target, hiding is weaker and transfers in 3/10 resplits. Frozen image and multimodal classifiers show boundary behavior consistent with the IUT guarantee and strong power relative to practical certificates.
Oct 18, 2026

The Optimal Sample Complexity of Pointwise Replicable Agnostic Learning

Pointwise replicability asks that two independently trained predictors, using the same random seed, agree at each fixed query with high probability. We determine its optimal agnostic sample complexity on finite and countable domains. For every nonempty binary class of finite VC dimension d≥1d\ge1, the required number of independent examples is Θ ⁣(dρ2α2+log⁡(1/β)α2)Θ\!\left(\frac{d}{ρ^2α^2}+\frac{\log(1/β)}{α^2}\right), uniformly over independent accuracy, failure, and disagreement parameters α,β,ρ∈(0,1/10)α,β,ρ\in(0,1/10). The learner returns one binary function, may be improper, and uses unrestricted shared randomness. Its sample budget is fixed before observing data, and the replicability guarantee includes queries of zero marginal mass. The main construction combines an ensemble of empirical-risk minimizers with a smooth, signal-dependent risk decomposition. A single shared phase selects the final binary predictor. Record times certify its weak-signal risk, while a uniform bound protects the strong-signal risk at that same selected time. A phase-comparison theorem controls the actual shared-seed execution under simultaneous changes in the marginals and risk coefficients. A rare repair step then makes the confidence cost additive. Together with matching lower bounds, this removes the remaining logarithmic overhead and parameter restrictions in the general countable-domain sample-complexity problem. This extended version also retains the earlier explicit constructions and their proofs, including proper learning for VC-one classes, the full finite-atom class, a faster realizable bound, and counterexamples that separate restrictions of particular algorithms from restrictions of the learning problem.
Oct 18, 2026

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

Strict replicability requires two independent training samples, processed with the same random seed, to produce exactly the same hypothesis. We study realizable Boolean learning under unknown and known instance marginals. For unknown marginals, we obtain the worst-case sample complexity Θ(((log⁡M)2/ρ2+log⁡(1/δ))/ε)Θ(((\log M)^2/ρ^2+\log(1/δ))/\varepsilon) for classes of cardinality at most MM, throughout a fixed small-parameter range. This resolves the distribution-free finite-class sample-complexity question up to universal constants and rules out a general ρ−1ρ^{-1} dependence. The upper bound uses a truncated-power distribution with a hard empirical-error budget. For known marginals, a control-variate learner uses O(((1+log⁡M)3/2/ρ+log⁡(1/δ))/ε)O(((1+\log M)^{3/2}/ρ+\log(1/δ))/\varepsilon) samples, and explicit uniform-marginal instances establish the matching class-size exponent. On a product of dd finite threshold chains of length kk, we determine the exact rate Θ((dklog⁡(1+d/(kρ))+log⁡(1/δ))/ε)Θ((dk\log(1+\sqrt d/(kρ))+\log(1/δ))/\varepsilon). We also characterize deterministic learning, the very-small-ρρ regime for arbitrary finite classes, and every cardinality-replicability regime for finite classes of VC dimension one. A VC-covering-number bound yields the fixed-accuracy exponent 3/23/2 independently of cardinality. Finally, we separate statistical complexity from implementation costs: we prove a sharp fixed-block trade-off, short-seed existence bounds, and a shared rejection-filter reduction from optimal learning of the full Boolean class to efficient public sampling of ordinary Bernoulli product distributions. Detailed proofs include the geometric lower bounds, the discrete posterior-kernel comparison, and the finite-bit constructions.
Oct 13, 2026

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

Modern machine learning models increasingly operate on variable-size structured data, such as sets and graphs. A central requirement is size generalization: the ability of a model trained on inputs of one size to generalize to inputs of a different, potentially much larger, size. Classical statistical learning theory, however, primarily considers fixed input domains, and its guarantees often deteriorate with input dimension. Although extensive work has established when models on sets and graphs can be transferred across input sizes, such results do not characterize the statistical cost of doing so: the sample complexity of size generalization, and its relationship to classical in-domain learning, remain largely unknown. We develop a statistical learning theory of size generalization and establish a sharp exponential separation in sample complexity. Letting nn denote the number of training samples, we show that polynomial source decay is insufficient for efficient size generalization: while it yields error n−Θ(1)n^{-Θ(1)} and hence polynomial sample complexity for in-domain learning, size-generalization error decays only as (log⁡n)−Θ(1)(\log n)^{-Θ(1)}, yielding an exponential separation. Thus, polynomial in-domain sample complexity can become exponential across sizes. We then identify an exponential source condition under which size generalization achieves error n−Θ(1)n^{-Θ(1)}, recovering polynomial sample complexity. These guarantees are independent of input dimension and depend only on the number of training samples, yielding dimension-free scaling laws. We also provide matching minimax lower bounds, establishing optimality. To our knowledge, this work provides the first dimension-free minimax theory of size generalization and a rigorous characterization of when, and at what statistical cost, learning can transfer across input sizes.
Oct 13, 2026

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

Best-arm identification (BAI) aims to identify the optimal arm using as few samples as possible. While most existing work focuses on a single objective, many real-world applications involve multiple criteria, which motivates the study of BAI in multi-objective bandits. Intuitively, multi-objective identification seems harder, since the learner must identify optimal arms in a higher-dimensional reward space; however, the additional objectives also provide richer feedback that can reduce the required exploration. In this paper, we characterize when and why multiple objectives can make BAI easier. For Gaussian bandits, we establish a characteristic-time lower bound for fixed-confidence identification that holds uniformly across preference orders. Through explicit comparisons under Pareto, linear, and lexicographic preferences, we reveal three phenomena: (i) identifying a larger optimal set can require fewer samples than identifying a unique optimum; (ii) the advantage of vector feedback over coordinate feedback depends fundamentally on the preference order; and (iii) multi-objective identification can require fewer samples than even the easiest corresponding single-objective problem. Finally, we propose Order-Aware Track-and-Stop (OATS), an algorithm that is correct at any prescribed confidence level and asymptotically matches the lower bound.
Oct 13, 2026

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

We study learning an unknown element gg of a group acting with finite orbits on a countable set, from examples (x,gx)(x,gx). After a sample on AA, the consistent hypotheses are the restrictions of a coset of the pointwise stabilizer of AA, and the sample forces exactly the labels of points this stabilizer fixes; for a Galois group, they form the field generated by the data. Through this correspondence, multiclass dimensions become group invariants: the DS and graph dimensions equal the height, the Littlestone dimension the longest irredundant sequence length, and the teaching dimension the minimal base size. Among deterministic learners, symmetry makes empirical risk minimization optimal: on nondegenerate classes every consistent learner, whatever its tie-breaking, attains the optimal realizable sample complexity up to constant factors, and every consistent online learner the optimal mistake bound. Agnostically, every ERM's sample complexity exceeds the known lower bound by at most the DS-to-Natarajan ratio, up to constants. For finite Galois extensions of countable fields, the Natarajan dimension equals a group invariant, the coset-cube number, which is at least the number of complemented factors of any chief series of any subgroup. Hence the dimensions coincide for every solvable Galois group, while for the groups A5A_5 and S5S_5 of the quintic they are 2<32<3 and 3<43<4, and A5A_5 is the smallest group with a gap. For the Galois group SnS_n of the general equation of degree nn, they coincide exactly when n≤4n\le 4, i.e., in characteristic zero, exactly when the equation is solvable by radicals; the implication is one-way, as the simple group PSL(2,8)\mathrm{PSL}(2,8) has no gap. For linear, orthogonal and unitary maps of Rd\mathbb R^d or Cd\mathbb C^d both dimensions equal dd, and a two-fibered pseudo-cube is a disjoint union of Natarajan cubes exactly when its monodromy group is abelian.
Oct 9, 2026

The Sample Complexity of Multicalibration with an ERM Oracle

A predictor is multicalibrated with respect to a class of subpopulations (formally, of functions on the inputs, called auditors) if, for every subpopulation in the class and every value the predictor outputs, the average outcome among the members of that subpopulation who receive that value is close to the value itself. For finite classes, about ε−3\varepsilon^{-3} samples are necessary and sufficient to learn a predictor with multicalibration error ε\varepsilon, but the algorithms that attain this rate enumerate the class, which is impossible for the large classes of interest. We ask how many samples suffice when the learner accesses the class only through an empirical risk minimization (ERM) oracle. We give an algorithm that uses O~(d/ε3)\tilde{O}(d/\varepsilon^{3}) samples and polynomially many ERM calls, where dd is the VC dimension of the class. Its dependence on ε\varepsilon is optimal for all learners. When dd is at least about 1/ε1/\varepsilon, every learner that can only access the class through polynomially many ERM calls needs Ω~(d/ε3)\tildeΩ(d/\varepsilon^{3}) samples. Learners with unlimited computation need only O~(ε−3+dε−2)\tilde{O}(\varepsilon^{-3}+d\varepsilon^{-2}) samples, so the extra factor 1/ε1/\varepsilon on the dimension term is the price of oracle efficiency. For swap multicalibration, which allows a different function from the class for each predicted value, Θ~(d/ε3)\tildeΘ(d/\varepsilon^{3}) samples are necessary and sufficient. For estimating the error of a given predictor, the ordinary notion is the harder one: the swap error can be estimated with an ERM oracle, whereas the ordinary error is NP-hard to approximate even for classes with linear-time ERM. Consequently, there are classes for which it is computationally easier to learn a multicalibrated predictor than to compute the multicalibration error of a given predictor.
Oct 9, 2026

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

We study dictionary learning for probability measure-valued data by embedding measures into Hilbert spaces using features derived from optimal transport geometry. We learn data-adapted dictionaries through sparse autoencoder parameterizations, producing fast, scalable representations of probability measures as sparse finite-dimensional codes. The resulting framework combines the rich, geometric structure of optimal transport with the interpretability and efficiency of sparse representation learning. We demonstrate its utility across diverse data modalities, including hyperspectral images, geometric point clouds, and document embeddings in large language model latent spaces. We also prove generalization bounds for sparse dictionary learning objectives on broad classes of L2L^2-valued measure embeddings, expressed in terms of the metric complexity of the atom class. For optimal transport and entropic transport map dictionaries, we derive new covering number bounds that yield explicit rates. Together, our computational and theoretical results support a new, scalable model for representation learning in the space of probability measures via embedding into Hilbert spaces.
Oct 8, 2026

Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube

For a known finite-dimensional model subspace, classical Gaussian regression theory guarantees that least squares eventually attains the parametric rate, with prediction error scaling as the subspace dimension divided by the sample size. Yet subspaces with the same number of unknown coefficients can require very different sample sizes to reach this regime. For subspaces of polynomials on the Boolean cube, a fundamental question is how restrictions on degree and ambient dimension jointly determine this threshold. Our main result sharply characterizes the worst-subspace minimax sample threshold over a substantial parameter range, revealing an exponential dependence on degree and precisely quantifying the joint effects of degree, ambient dimension, and subspace dimension. A small modification of our lower-bound construction reveals a strong separation: a single subspace can admit noiseless recovery with optimal sample complexity independent of degree, yet require essentially the worst-case sample size, exponential in degree, to attain the noisy parametric rate. To establish the sampling lower bound, we sharpen the Polyanskiy-Samorodnitsky uncertainty principle (J. Funct. Anal., '19) to uniformly optimal precision and extend its concentration guarantee to large subspaces in which every function concentrates most of its energy on one shared Hamming ball. The sampling upper bound follows from the sharp moment bound of Kirshner and Samorodnitsky (IEEE Trans. Inf. Theory, '21) combined with empirical-process bounds.
Oct 8, 2026

Recovery Guarantees for Posterior Sampling of One-Bit Compressed Sensing

We study the sample complexity of noisy one-bit compressed sensing for signals drawn from a prior distribution. By characterizing the effective distributional complexity of the prior via its approximate covering number, we prove that posterior sampling achieves accurate recovery with high probability when the number of measurements scales with the logarithm of the approximate covering number, up to a one-bit separation gap factor. This upper bound is robust to learned prior mismatch. Specifically, we show that posterior sampling with an approximate prior remains reliable, provided that the learned prior distribution is sufficiently close to the true signal distribution in Wasserstein distance. In addition, we establish a sample complexity lower bound for any reliable method of noisy one-bit compressed sensing, showing that our upper bound is nearly matched in its main prior dependent term. To approximate the ideal posterior sampling process for real world scenarios, we instantiate posterior sampling through a plug-and-play algorithm with diffusion priors. Experiments on the FFHQ and ImageNet datasets demonstrate the effectiveness of our proposed approach.
Oct 7, 2026

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

We study ranking models by population-average utility from pairwise comparisons when preferences vary across users and tasks. Prior work shows that a single comparison per user can be insufficient to identify the alternative with the highest average utility, even with arbitrarily many users (Golz et al., 2025). We investigate how many repeated comparisons within each user-task context are necessary and sufficient for ranking recovery. Under a heterogeneous Bradley-Terry model with fixed inverse temperature, we start with a naive MLE-based algorithm that requires Ω(1/Δ2)Ω(1/Δ^2) repeated comparisons per context to ensure ranking recovery. We then present two MLE-based variants and a randomized Russian Roulette-style algorithm that recover the ranking using O(log⁡(1/Δ))O(\log(1/Δ)) repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only O(1)O(1) comparisons per context in expectation. Synthetic experiments and semi-synthetic experiments based on Arena data compare the four algorithms in settings with varying levels of preference heterogeneity and under varying context distributions.
Oct 5, 2026

Sharp dimensional analysis of midpoint methods for Langevin sampling

We study deterministic and randomized midpoint discretizations of Langevin dynamics for a target π∝e−Vπ\propto e^{-V}, where 0≺αI⪯∇2V⪯βI0 \prec αI\preceq\nabla^2V\preceqβI and κ=β/ακ=β/α. To achieve α W2⩽ε\sqrtα\,W_2\leqslant\varepsilon, we show that deterministic Heun uses at most O~(κ4/3d1/3ε−2/3)\widetilde O(κ^{4/3}d^{1/3}\varepsilon^{-2/3}) gradient queries, and underdamped exponential midpoint uses O~(κ5/4d1/4ε−1/2)\widetilde O(κ^{5/4}d^{1/4}\varepsilon^{-1/2}). The proofs exploit cancellation at stationarity and smoothing using techniques from Malliavin calculus, outperforming previous upper bounds based on standard couplings. At bounded condition number, a lower bound matches the dd and ε\varepsilon powers of both deterministic methods. To contrast, for the randomized midpoint methods and Poisson midpoint with at least two grid points (both overdamped and underdamped variants), a simple Gaussian calculation yields a lower bound d1/3ε−1/3d^{1/3}\varepsilon^{-1/3} to get an ε\varepsilon-close sample despite starting at a benign initialization. This shows surprisingly that in high dimensions, deterministic discretizations can outperform their random counterparts.
Oct 2, 2026

Seer: Maximum Likelihood Regression for Learning-Speed Curves

The research presented here focuses on modeling machine-learning performance. The thesis introduces Seer, a system that generates empirical observations of classification-learning performance and then uses those observations to create statistical models. The models can be used to predict the number of training examples needed to achieve a desired level and the maximum accuracy possible given an unlimited number of training examples. Seer advances the state of the art with 1) models that embody the best constraints for classification learning and most useful parameters, 2) algorithms that efficiently find maximum-likelihood models, and 3) a demonstration on real-world data from three domains of a practicable application of such modeling. The first part of the thesis gives an overview of the requirements for a good maximum-likelihood model of classification-learning performance. Next, reasonable design choices for such models are explored. Selection among such models is a task of nonlinear programming, but by exploiting appropriate problem constraints, the task is reduced to a nonlinear regression task that can be solved with an efficient iterative algorithm. The latter part of the thesis describes almost 100 experiments in the domains of soybean disease, heart disease, and audiological problems. The tests show that Seer is excellent at characterizing learning-performance and that it seems to be as good as possible at predicting learning performance. Finally, recommendations for choosing a regression model for a particular situation are made and directions for further research are identified.
Sep 30, 2026

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

We establish non-asymptotic sample complexity bounds for the least-squares estimation of vector autoregressive models for exponentially stable systems with heavy-tailed noise based on a single observed trajectory. By assuming i.i.d. noise, bounded noise covariance, and persistent excitation, we show that the estimation error is O~(r1/2T−1/2+1/p)\widetilde{\mathcal{O}}(r^{1/2}T^{-1/2+1/p}) under bounded ppth moment for p>2p > 2, where TT is the number of samples, rr is the noise dimension, and O~(⋅)\widetilde{\mathcal{O}}(\cdot) hides logarithmic terms. We also introduce a unifying approach to sample complexity analysis applicable to broad classes of noise distributions and showcase this by deriving error bounds for sub-exponential and sub-Gaussian noise distributions. Finally, we specialize our analysis to autoregressive models with exogenous inputs and show that the dimension factor of the error bound is independent of the model order.
Sep 30, 2026

How Many Samples Are Enough for Learning Across Domains?

Understanding the fundamental mechanisms of learning is essential for designing systems with strong generalization. Recent studies have shown that increasing the number of training domains, or enlarging the distribution shift among them, improves generalization when each domain contains sufficiently many data samples. However, the conditions under which the data samples can be considered sufficient remain unexplored. In this work, we fill this gap by establishing criteria for per-domain sample requirements based on the presented learning bounds. These criteria not only reveal an inverse linear scaling law between the number of training domains and the number of samples required per domain, but also explain the fundamental rationale behind the assumption of data sufficiency, thereby providing theoretical guidance for assessing the adequacy of existing datasets and constructing datasets. This differs from classical learning theory, as the number of samples required is highly dependent on the number of training domains. Additionally, we prove the close relationship between in-domain learning and out-of-domain generalization through the presented generalization bounds, and lastly discuss some key arguments.
Sep 29, 2026

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

Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.
Sep 29, 2026

Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure

Masked generative models offer parallel token prediction, but accurate parallel sampling must account for dependencies among tokens. When dependencies are unknown, finding safe batches also costs model evaluations. We study whether total evaluations, including discovery, can be sublinear in sequence length NN; sublinear sequential depth then follows. We consider discrete distributions with hidden forest structure, accessed through a fixed approximate conditional oracle. Under explicit regularity conditions and uniform Hellinger error bounds, for any fixed target accuracy ε∈(0,1/8]\varepsilon\in(0,1/8] and sufficiently large NN, our sampler achieves seed-averaged total-variation error at most ε\varepsilon, with total masked-state submissions and sequential depth both bounded by O~(NCε−a)\widetilde{O}(N^C \varepsilon^{-a}) for constants 0<C<10<C<1 and a>0a>0. These guarantees use polynomial vocabulary size and an edge-response lower bound set by NN and ε\varepsilon. The sampler shares evaluations of hypothetical reveals across dependence tests to identify safe parallel batches without requiring full recovery of the hidden forest. A tunable parameter trades probing cost against irreversible commit rounds. In the same class, any admissible irreversible product-commit sampler attaining the same seed-averaged accuracy requires Ω(Ncεb)Ω(N^c \varepsilon^b) counterfactual submissions or commit rounds in the worst case, for constants c,b>0c,b>0.
Sep 28, 2026

The Statistical Cost of Causal Discovery with Feedback

What determines the unavoidable sample cost of learning cyclic causal structure? For cyclic linear non-Gaussian models, we study exact condensation recovery from observational data: identifying the strongly connected component (SCC) partition and all edges between components. We establish the first information-theoretic lower bounds on sample complexity for this target. For pp variables, maximum SCC size smax⁡s_{\max}, and maximum external-parent count dBd_B, any estimator requires order smax⁡log⁡(ep/smax⁡)+dBlog⁡(ep/dB)s_{\max}\log(ep/s_{\max})+d_B\log(ep/d_B) samples in the worst case over a regular model class. These bounds distinguish the costs of SCC membership and external-parent selection. Under principal invertibility and without correlation faithfulness, we establish a population block-exogeneity principle that identifies unknown root SCCs through residual independence and inclusion minimality. A sparse-adjustment characterization shows that small adjustment sets suffice to identify SCCs and their direct external parents, without regressing on all previously recovered variables. These characterizations yield BlockExo, which attains a structurally matching sample bound without knowing smax⁡s_{\max} or dBd_B under suitable conditions. Simulations support the structural dependence of our sample bound and demonstrate BlockExo's sample-efficient recovery in comparisons with other methods for cyclic causal discovery.
Sep 27, 2026

The cost of useful natural gradient updates

What information is needed to turn a natural-gradient direction into a useful finite update? Under a population Kullback-Leibler (KL) budget, we call a step useful if it is feasible and loses at most a fraction ε\varepsilon of the best feasible gain along the direction. We construct a four-state exponential family whose laws share their initial gradient, scalar Fisher information and natural gradient, yet two laws have disjoint useful-step sets. With these quantities supplied exactly and the law otherwise known only through draws, the family's worst-case sample complexity is Θ(log⁡(1/δ)/(pε2))Θ(\log(1/δ)/(p\varepsilon^2)) for small ε\varepsilon, where pp scales rare-state probabilities and δδ is the failure probability. The budget is fixed and the optimal gain stays bounded away from zero, so the step length, not the direction, carries this cost. For succinctly described event-tilt models, returning a useful step is NP-hard even with the exact natural gradient and efficient exact sampling. Recovering the unit natural gradient to constant error is also NP-hard even in a two-parameter logistic family with Fisher condition number at most 3. We also give matching sample bounds for event tilts, sample bounds for damped Fisher solves and a population-KL certificate for affine classifiers. In frozen-feature classifier heads, stopping at a sampled KL boundary succeeds in about half of the trials, and a 10% KL margin raises joint success above 93% at a KL budget of 0.01. Thus, knowing where to move is not enough: how far to move can carry an update's entire cost.
Sep 26, 2026

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

Modern machine learning spans supervised, transfer, continual, meta-learning, and related regimes that often reuse the same hypothesis classes, architectures, and optimizers but differ in information access, objectives, memory, adaptation, and sample accounting. This makes it difficult to determine whether one paradigm is genuinely distinct, a special case of another, or part of a broader structural hierarchy. We introduce a protocol-objective-resource (POR) framework that separates representational capacity from these design choices. A paradigm is specified by an environment class, observation protocol, admissible learners, performance functional, and resource accounting rule. POR reductions combine environment embeddings, learner compilers, threshold maps, and calibrated resource overheads. Our main theorem shows that such reductions imply worst-case complexity domination on embedded comparison classes, transferring upper bounds forward and lower bounds backward; under labeled-example accounting, this yields sample complexity domination. We also show that calibrated nontrivial accuracy regimes are necessary to avoid vacuous comparisons, and that strengthening the objective can strictly increase minimax sample complexity even with unchanged protocols and learner classes. Instantiating the framework for supervised, transfer, continual, and meta-learning yields canonical special-case relations: continual contains transfer, transfer contains supervised, and meta-learning contains supervised under aligned raw-example accounting. We further derive a non-exact episode-to-example reduction for episodic meta-learning and capture within-paradigm refinements such as replay memory and task identifiers. The framework thus provides a unified language for structuring learning paradigms and transferring complexity guarantees across them.