sample-complexity

This paper introduces a cross-model map for certifying selective predictors that must meet both an automation floor and a risk ceiling under covariate shift, deriving feasibility frontiers and two-resource sample-complexity trade-offs.

This paper studies adaptive symmetry discovery for dynamical system identification, showing that known symmetries reduce the trajectory length needed for identification and proposing a method to learn unknown symmetry groups from a single trajectory to achieve the same optimal length.

This paper studies the sample complexity of policy learning under the mu-resets interaction protocol in reinforcement learning, resolving a question about the role of policy realizability and showing horizon dependence is exponential under all-policy concentrability and sqrt-exponential under pushforward concentrability.

This paper answers an open question from Hanneke, Moran, and Waknine by showing that the agnostic PAC learning curve of a direct sum is not determined solely by the single-instance learning curve and the number of factors, providing a rate separation.

This paper studies the sample complexity of robust average-reward Markov decision processes, deriving minimax-optimal learning rates via plug-in reductions under total-variation uncertainty sets.

This paper studies the sample complexity of multicalibration for a sequence of properties that are sequentially identifiable, establishing matching upper and lower bounds up to logarithmic factors.

This paper proposes a Hessian-free hypergradient-based bilevel reinforcement learning algorithm that achieves state-of-the-art sample complexity and removes the PL condition assumption in convergence analysis.

This paper presents improved algorithms for learning truncated Boolean product distributions, achieving sample complexity that matches the untruncated minimax rate using the concept of influence from Boolean function analysis.

This paper introduces Graded Large Language Models (GLLMs), an algebraic framework that imposes a hierarchical grading on transformer representations, theoretically improving sample efficiency for language hierarchies while preserving inference complexity. It provides geometric and information-theoretic justifications, and outlines a grade-selection procedure validated in a companion manuscript.

Introduces VRDQ, a decentralized Q-learning algorithm for multi-agent reinforcement learning over static and time-varying networks, with finite-time convergence guarantees that achieve linear speedups in sample complexity with only Õ(1) communication.

This paper addresses the fixed-confidence top-k identification problem from noisy pairwise comparisons, and develops an asymptotically optimal algorithm that minimizes the expected number of comparisons.

This paper studies fixed-confidence best-arm identification where costly reward observations are paired with cheap but correlated proxy scores from generative models. It proposes the PROBE algorithm that uses control-variate adjustment and upper certificates on residual variance to achieve oracle-like sample complexity.

This paper proposes a noisy expert model to explain the gap between offline and online imitation learning, showing that offline learning from noisy trajectories requires exponential sample complexity while online on-policy distillation achieves polynomial dependence. The analysis leads to an alternative loss function and experiments confirm the theoretical findings.

This paper develops a Fourier analysis framework to study data augmentation under group invariances, showing that partial augmentation can achieve the same minimax rates as full augmentation up to a vanishing approximation error, while also proving that exact invariance requires full group averaging.

This paper demonstrates that two-layer neural networks trained with gradient-based methods can achieve the optimal computational-statistical tradeoff for learning Gaussian single-index models, matching the SQ lower bound up to polylogarithmic factors for all generative exponents and extending to sparse settings with a novel weight perturbation technique.

This paper develops a statistical theory for offline reinforcement learning from trajectory-level outcome supervision, proposing the OPAC algorithm and characterizing when such supervision enables efficient learning versus when fundamental barriers arise.

This paper studies the sample complexity of learning in average-reward weakly-coupled MDPs and restless bandits, establishing finite-sample PAC guarantees with polynomial complexity using a novel Lyapunov-based analysis framework.

This paper empirically measures the symmetry–data exchange rate predicted by equivariance theory, finding that wrong-group symmetry constraints are actively harmful, augmentation with test-time orbit averaging matches equivariant architectures, and the theoretical |G|-fold sample complexity reduction is only weakly confirmed with wide confidence intervals. The study is explicitly exploratory and not pre-registered.

This paper proves that learning by predicting latent representations (as in world models like JEPA and data2vec) requires exponentially less data than predicting tokens (as in LLMs) for hierarchical data with hidden structure.

This exploratory study empirically measures the symmetry–data exchange rate predicted by equivariance theory on controlled C_n-symmetric tasks, finding that wrong-group constraints are actively harmful, augmentation with test-time orbit averaging matches equivariant models exactly, and the empirical exchange rate is broadly consistent with theory but statistically inconclusive. The authors emphasize the study's exploratory nature and call for registered replications.