Hugging Face Trending Papers

Next-token functional estimation

arXiv Machine Learning
Sep 18

Next-token functional estimation

The paper introduces a leave‑a‑window‑out estimator for next‑token functionals, such as the surprise probability and test error, in sequences of random variables. By deleting a window of length τ after each index, the estimator generalizes leave‑one‑out and achieves parametric error decay for stationary β‑mixing processes that admit a Marton coupling. The authors provide both upper bounds and a minimax lower bound for the surprise probability, and demonstrate through simulations that their method outperforms traditional baselines on Markov, moving‑average, and autoregressive processes.

By Milind Nakul, Vidya Muthukumar, Ashwin Pananjady
arXiv Machine Learning
Nov 2

A Unified Framework for Probability Estimation of Data-Dependent Events

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 Machine Learning
Aug 10

Stochastic Autoregressive Learning

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
arXiv Statistics ML
Oct 7

Poisson empirical Bayes estimation of sums of random variables via minimum-distance methods

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
arXiv Machine Learning
Nov 5

Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs

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
arXiv Machine Learning
Sep 10

Mixing Makes Markovian Contexts Cheap for Linear Bandits

The paper extends the idea that contexts are cheap for linear bandits from i.i.d. settings to Markovian context processes. By assuming uniform geometric ergodicity, the authors construct a stationary surrogate action set and use a delayed‑update scheme to mitigate bias from nonstationary conditional context distributions. They provide a phased algorithm for unknown stationary distributions and achieve high‑probability regret bounds comparable to standard linear bandit oracles in fast‑mixing regimes, with empirical validation showing gains over LinUCB.

By Kaan Buyukkalayci, Osama Hanna, Christina Fragouli
arXiv Machine Learning
Oct 16

Stochastic Gradient Descent: A Nonlinear Time Series Perspective

This paper studies the statistical properties of Stochastic Gradient Descent (SGD) with a constant step size using the framework of iterated random functions. It demonstrates convergence in Euclidean distance via Geometric Moment Contraction, establishes quenched central limit theorems, invariance principles, and α-stable convergence for averaged SGD regardless of initialization, and explores the effect of step sizes through derivative processes. The authors further develop a Richardson-Romberg extrapolation with multiple step sizes, propose a bias-reduced variant, and introduce an online inference method that yields empirical confidence intervals with coverage approaching nominal levels as sample size increases.

By Jiaqi Li, Zhipeng Lou, Stefan Richter, Wei Biao Wu