Metraipolis › archive › dc_136d58da2467

Batch Universal Prediction via Conditional Additive Smoothing — arXiv:2610.41859

Source

arXiv (en)

Original

https://arxiv.org/abs/2610.41859

License (as archived)

CC0-1.0

Archived

2026-11-03T05:45:28.671Z

SHA-256 of the archived text

28bfe89838c26f80199f59f593df55982a1b2e192ccc3a29baca6f8131cc2dff

Stable URL of this page

https://metraipolis.com/documento/dc_136d58da2467

How to cite

Batch Universal Prediction via Conditional Additive Smoothing — arXiv:2610.41859 — arXiv (en), https://arxiv.org/abs/2610.41859 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_136d58da2467 (Metraipolis archive dc_136d58da2467, sha256 28bfe89838c26f80199f59f593df55982a1b2e192ccc3a29baca6f8131cc2dff)

@misc{dc136d58da2467,
  title = {Batch Universal Prediction via Conditional Additive Smoothing — arXiv:2610.41859},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.41859},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_136d58da2467; sha256 28bfe89838c26f80199f59f593df55982a1b2e192ccc3a29baca6f8131cc2dff},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.41859. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Modern language models motivate renewed interest in universal prediction problems in which a predictor can exploit previously observed data before predicting a fresh sequence. We study an idealized version of this setting by introducing \emph{batch regret}: a conditional analogue of classical average regret in which a predictor observes a batch of $n$ training sequences and is then evaluated on an independent test sequence generated by the same unknown source. Additive smoothing estimators, which add a bias to the observed token frequencies before predicting the next token, played a fundamental role as a simple prediction strategy with almost-optimal average regret for memoryless and Markov sources. Their equivalent under batch regret are the conditional additive smoothing estimators, which estimate the conditional distribution of the test sequence given the training batch. In this work, we study their asymptotical batch regret for binary memoryless and first-order Markov sources. For binary memoryless sources, we show how the optimal bias of the estimator, and consequently the corresponding batch regret, change as a function of the training batch size $n$, by extending the Poisson-based analysis of Krichevsky. For binary Markov sources with positive transitions, we characterize the leading coefficient of batch regret and its dependence on whether the initial law is known, free, or stationary. Finally, we introduce a Rényi analogue of batch regret and identify the corresponding optimal predictors as conditional $\alpha$-NML estimators, thereby giving an operational interpretation to a conditional version of Sibson's $\alpha$-mutual information.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2610.41859 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T05:32:32.025Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).