Suppose we observe the first $n$ points of a sequence of random variables having length $n+1$, and wish to estimate a functional of the unobserved final point and the empirical measure of the $n$ obse...
arXiv:2608. 07224v1 Announce Type: new Abstract: Motivated by LLMs, which generate outputs by iteratively sampling from next-token distributions, we introduce a PAC-learning model for binary stochastic autoregressive learning.
By Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel
The paper introduces a unified framework for estimating the probability that an unknown distribution assigns to a data‑dependent event defined by a sample and a known mapping. It analyzes two classical estimators—the empirical plug‑in estimator and the leave‑one‑out (Good–Turing) estimator—showing how their errors relate to generalization gaps and stability under sample deletion. The framework is applied to error estimation for predictors that combine a base classifier with memorized exceptions, leading to new bounds based on VC dimension and mutual information for adaptive missing mass estimation.
By Vitaly Feldman, Satyen Kale, Vinod Raman, Kunal Talwar, Ambuj Tewari
arXiv:2608. 25551v1 Announce Type: new Abstract: Stochastic gradient descent (SGD) is typically analyzed at a deterministic horizon chosen before the algorithm is run, even though practical stopping decisions are made adaptively by inspecting the evolving trajectory.
By Liviu Aolaritei, Lucas L\'evy, Francis Bach, Michael I. Jordan
The paper investigates how Chain-of-Thought (CoT) reasoning enables Large Language Models to generalize to out-of-distribution (OOD) tasks by composing reusable in-distribution (ID) atomic steps. It provides a theoretical framework showing that OOD risk depends on the sum of ID sub-task risks, scaled by a factor independent of the number of reasoning steps, and that the estimation error grows sub-linearly with the number of steps. Experiments on Atom-Task and GSM8K datasets confirm that CoT supports short-to-long and compositional generalization, and that explicit state tracking is essential.
By Nuo-Jing Liang, Xiao-Tong Yuan, Pan Zhou
The paper develops a nonparametric empirical Bayes approach for estimating sums of functions of observable and unobservable variables in Poisson mixture models, using regular and coarsened minimum‑distance estimation of the mixing distribution. It proves large‑sample guarantees that the plug‑in estimates converge to the oracle Bayes estimate, achieving nearly parametric rates when the mixing distribution has finite support. Finite‑sample analyses are provided for two specific sums—total intensity below a threshold and the number of units exceeding latent intensity—along with minimax regret bounds and conditions for bounded regret.
By Stefano Favaro, Sandra Fortini, Soham Jana