sample-complexity

该论文证明了所有在总变差距离下可学习的分布类也都是可私有学习的，从而证实了Ashtiani的一个猜想，即在(ε,δ)-差分隐私约束下，只要目标误差可以任意小，有限样本下的可学习性依然成立。

论文提出 Halve-Then-Greedy（HTG）算法，用于固定预算下的自适应实验设计，以最大化推荐设计均值超过目标的后验概率，并证明了近最优的实例相关样本复杂度界。

Harvard researchers develop a statistical learning theory of size generalization, proving an exponential separation in sample complexity between in-domain and cross-size learning, along with dimension-free scaling laws and matching minimax lower bounds.

该论文研究在用户偏好存在异质性时，通过成对比较按总体平均效用对模型进行排序所需的重复比较次数。作者提出了一种 Russian Roulette 式的 MLE 算法，仅需每上下文 O(log 1/Δ) 次（期望 O(1) 次）重复比较即可恢复排序，并证明了该对数依赖是最优的。

A new paper, 'Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation Learning', introduces MA-BC, which pools expert demonstrations only where observed actions do not disagree, and provides upper and lower bounds on sample complexity for learning from experts with differing objectives.

The paper provides theoretical guarantees for beam-search-based test-time scaling in LLM reasoning, proving a lower bound on vanilla beam search sample complexity and proposing confidence-filtered beam search (CF-Beam) that reduces coverage dependence from quadratic to nearly linear, outperforming sequence-level methods like Best-of-N on long-horizon tasks.

This paper introduces sparse priors to improve theoretical guarantees on distribution learning, showing that under a sparse prior, the sample complexity scales as Ω(√(k/n)) instead of O(n^{-1/Θ(d)}), thereby mitigating the curse of dimensionality.

This paper resolves whether Empirical Risk Minimization is relatively smart for binary classification, explores semi-supervised learning with quadratic blowup in unlabeled data, and proves intractability results for certain learners.

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.