betaFeedback

WorksComputer Science

Batch Universal Prediction via Conditional Additive Smoothing

Abstract

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 batch regret: a conditional analogue of classical average regret in which a predictor observes a batch of nn 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 nn, 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 αα-NML estimators, thereby giving an operational interpretation to a conditional version of Sibson's αα-mutual information.

Introduction

In information theory, prediction concerns the problem of estimating the continuation of a sequence of symbols, or tokens, based on the sequence’s past and on any additional information available about the data distribution. The estimate is produced by a predictor, namely a probability distribution on the possible continuations. Under logarithmic loss, the best predictor for a known source is the source distribution itself, and the excess loss incurred by a universal predictor is called regret. Universal prediction studies predictors whose regret is small uniformly over a prescribed class of sources.

Universal prediction is a classical topic, with roots that can be traced at least to Laplace’s rule of succession [1]. Its connection to modern machine learning is nevertheless direct: language models are trained as next-token predictors, and their performance is usually evaluated through variants of logarithmic loss. However, in the classical formulation of universal prediction, one usually predicts a single long sequence generated by one unknown source. Instead, in many data-rich prediction problems such as large language model training, information about the source is available through a collection of independent training sequences, and performance is then measured on an independent test sequence. This connection motivates revisiting universal prediction in settings where a predictor has access to many previously observed examples before being evaluated on a fresh test sequence. In this work, we therefore introduce batch regret, a conditional regret measure in which the predictor is evaluated on a test sequence of ℓ\ell tokens, conditioned on the observation of a batch of nn training sequences.

The main focus of this paper is the single-source batch setting, where all training sequences and the test sequence are drawn independently from the same unknown distribution ρθ\rho_{\theta}. This setting captures an idealized form of in-distribution prediction: the training batch provides information about the unknown source, and the predictor uses this information when assigning probabilities to the test sequence. More specifically, we will focus on additive smoothing estimators, in which the predictive probability at any given moment is obtained by adding a constant bias β>0\beta> 0 to the empirical frequencies of the tokens. This class includes the Laplacian [1] and the Krichevsky–Trofimov [2] estimators and has been shown to achieve near-optimal asymptotic average regret on a single sequence. Here we will study their conditional extension, in which the training batch is used to improve the estimates. In particular, we will analyze their batch regret when the target classes are binary memoryless and first-order Markov sources. Under this setting, the theoretical limits derived in this work complement a more practical line of research that studies large language models’ capability to optimally predict tokens generated from controlled data distributions such as Markov sources [3, 4, 5, 6, 7, 8].

Main contributions

Our contributions are organized as follows. In Section III we formulate single-source batch regret and relate it to the Kullback-Leibler divergence between the test sequence’s parametric distribution and a predictor, conditioned on the training batch. In Section IV we prove a conditional regret-capacity theorem, which equates minimax batch regret to a maximal conditional mutual information between the distribution parameter and the test sequence given the training batch. As the maximal mutual information can be lower-bounded by choosing any prior distribution on the parameter space, this result can be used to lower bounds on minimax batch regret, which we do in the subsequent sections. In Section V, we introduce conditional additive smoothing estimators, or add-β\beta estimators, for binary memoryless sources and we prove general estimates of their batch regret in the interior and at the border of the simplex, valid whenever nℓ→∞n\ell\to\infty. The overall behavior over the entire simplex depends on the regime in which the batch size nn and the sequence length ℓ\ell interact, and is discussed in the following two sections: in Section VI we consider the large-nn regime, while in Section VII we study the complementary fixed-nn, large-ℓ\ell regime. In Section VIII we discuss the optimal batch regret over the class of all predictors instead. In Section IX, we extend our analysis to first-order binary Markov sources with uniformly positive transitions. Under this setting, assumptions on the initial distribution of the Markov source are fundamental: in fact, we show how the leading coefficient of batch regret changes whenever the initial law is known, free, or stationary. Finally, in Section X we consider a generalized batch regret measure based on conditional Rényi divergence, which we call batch α\alpha-regret, and we prove its relation with a conditional extension of Sibson’s α\alpha-mutual information, thus providing an operational interpretation to it. A preliminary version of some of the results of this paper was first presented in [9, 10].

Universal prediction under cross-entropy loss and universal lossless compression are essentially mathematically equivalent [11, 12], so that literature on either topic is relevant to the other. Universal compression-prediction for memoryless sources was studied by Xie and Barron under both average [13] and worst-case regrets [14]. Their asymptotic techniques are closely related to the compact-interior expansion in Theorem 4. The worst-case regret for Markov sources was studied in [14, 15, 16]. The average case was more recently characterized in [17, 18]. The techniques used in [18], in particular Paulin’s concentration inequalities for Markov chains [19], are instrumental to proving our Theorem 14.

A batch regret with one test sample is the average next-token regret defined in Eq. (28) and first studied by Krichevsky [20]. This regret measure has since been studied in several works [21, 22, 23, 24]; in particular, [24] predicts one test symbol after a training sample and therefore belongs to this next-token setting. A form of conditional average regret for more than one token was introduced in [25], where it is studied for location families. This metric is also studied by [22] and [26]. In particular, [26] focuses on memoryless sources, under which their metric is equivalent to our definition of batch regret. However, in this work we study a different regime of nn and ℓ\ell and a different class of predictors. The equivalence between the two definitions of conditional regret does not extend to other classes of distributions, e.g., the Markov class studied in Section IX: according to our definition, the training batch is composed of nn independent Markov sequences of length ℓ\ell, instead of one sequence of nℓn\ell i.i.d. samples. A closer setting is the one studied in [22], whose general formulation includes independent sequences; however, it does not study the regret as a function of the batch size nn and the sequence length ℓ\ell, which is the focus of this work. Nonetheless, both works include a conditional version of the regret-capacity theorem, similar to our Theorem 2.

Sibson’s α\alpha-mutual information was introduced by Sibson in [27] as an information radius. A revisitation of it as a generalization of Shannon’s mutual information was proposed in [28], which also reviews many of its properties. A more recent discussion can be found in [29]. Proposals for conditional versions of Sibson’s mutual information, including the one used in Eq. (142), appear in [30, 31]. The maximization of Sibson’s mutual information and related measures is studied in [32], including a proof of a regret-capacity theorem for α\alpha-mutual information. The work [33] discusses Sibson’s mutual information in a universal-compression context while studying a closely related redundancy measure called Sundaresan divergence. The predictors introduced in [34] are based on Sibson’s mutual information; in Theorem 18, we obtain conditional analogues of these predictors as optimal predictors under α\alpha-batch regret.

Background

In this section we recall basic information-theoretic definitions and results that will be useful in the sequel. The alphabets are finite and all logarithms are in base ee, unless stated otherwise.

Conditional and Rényi information measures

Given two conditional distributions pU∣Zp_{U|Z} and qU∣Zq_{U|Z} and a distribution pZp_Z, we use the conditional Kullback–Leibler (KL) divergence

D(pU∣Z∥qU∣Z∣pZ)≜∑z∈ZpZ(z)∑u∈UpU∣Z(u∣z)log⁡pU∣Z(u∣z)qU∣Z(u∣z).(1)D(p_{U|Z}\|q_{U|Z}\mid p_Z) \triangleq\sum_{z\in\mathcal{Z}} p_Z(z)\sum_{u\in\mathcal{U}}p_{U|Z}(u\mid z)\log\frac{p_{U|Z}(u\mid z)}{q_{U|Z}(u\mid z)}. \tag*{(1)}

Equivalently, when pUZp_{UZ} and qUZq_{UZ} have the same ZZ-marginal pZp_Z, this quantity is equal to the classical KL divergence D(pUZ∥qUZ)D(p_{UZ}\|q_{UZ}). We also write it as D(U∥U^∣Z)D(U\|\widehat{U}\mid Z) when the underlying conditional laws are clear. Conditional mutual information is the corresponding information radius,

I(X;Y∣Z)=D(pXYZ∥pX∣ZpY∣Z∣pZ).(2)I(X;Y\mid Z)=D(p_{XYZ}\|p_{X|Z}p_{Y|Z}\mid p_Z). \tag*{(2)}

In cases where the distribution of XX varies, we may also write IP(X;Y∣Z)I_P(X;Y\mid Z) to highlight the fact that XX is distributed according to PP.

For α>0\alpha>0, α≠1\alpha\ne1, the Rényi divergence [35] is

Dα(pX∥qX)≜1α−1log⁡∑x∈XpX(x)αqX(x)1−α.(3)D_\alpha(p_X\|q_X)\triangleq\frac{1}{\alpha-1}\log\sum_{x\in\mathcal{X}}p_X(x)^\alpha q_X(x)^{1-\alpha}. \tag*{(3)}

Its limiting cases include D1(pX∥qX)=D(pX∥qX)D_1(p_X\|q_X)=D(p_X\|q_X) and

D∞(pX∥qX)=sup⁡x∈Xlog⁡pX(x)qX(x).(4)D_\infty(p_X\|q_X)=\sup_{x\in\mathcal{X}}\log\frac{p_X(x)}{q_X(x)}. \tag*{(4)}

We will also use the conditional version

Dα(pU∣Z∥qU∣Z∣pZ)≜1α−1log⁡∑z∈ZpZ(z)(∑u∈UpU∣Z(u∣z)αqU∣Z(u∣z)1−α).(5)D_{\alpha}(p_{U|Z}\|q_{U|Z}\mid p_Z) \triangleq\frac{1}{\alpha-1}\log\sum_{z\in\mathcal{Z}}p_Z(z)\left(\sum_{u\in\mathcal{U}}p_{U|Z}(u\mid z)^\alpha q_{U|Z}(u\mid z)^{1-\alpha}\right). \tag*{(5)}

Finally, Sibson’s α\alpha-mutual information [27] is

Iα(X;Y)≜αα−1log⁡∑y∈Y(∑x∈XpX(x)pY∣X(y∣x)α)1/α.(6)I_{\alpha}(X;Y)\triangleq\frac{\alpha}{\alpha-1}\log\sum_{y\in\mathcal{Y}}\left(\sum_{x\in\mathcal{X}}p_X(x)p_{Y|X}(y\mid x)^\alpha\right)^{1/\alpha}. \tag*{(6)}

It admits the variational representation

Iα(X;Y)=min⁡Y^:X⊥Y^Dα(Y∥Y^∣X),(7)I_{\alpha}(X;Y)=\min_{\hat{Y}:X\perp\hat{Y}}D_{\alpha}(Y\|\hat{Y}\mid X), \tag*{(7)}

for the α\alpha-orders considered in this paper. Conditional analogues are introduced in Section X.

Classical universal prediction

Fix a sequence length ℓ\ell. A predictor assigns probabilities p^(xℓ)\hat{p}(x^\ell) to sequences xℓ=(x1,…,xℓ)∈Xℓx^\ell=(x_1,\ldots,x_\ell)\in\mathcal{X}^\ell. When the predictor is used sequentially, it is specified by one-step conditionals and induces the joint distribution

p^(xℓ)=∏i=0ℓ−1p^(xi+1∣xi).(8)\hat{p}(x^\ell)=\prod_{i=0}^{\ell-1}\hat{p}(x_{i+1}\mid x^i). \tag*{(8)}

Universal prediction benchmarks p^\hat{p} against a class P={pθ:θ∈Θ}\mathcal{P}=\{p_\theta:\theta\in\Theta\}. Under logarithmic loss,

L(p^,xℓ)≜−log⁡p^(xℓ),(9)L(\hat{p},x^\ell)\triangleq-\log\hat{p}(x^\ell), \tag*{(9)}

the pointwise regret relative to pθp_\theta is

Rn,ℓ(p^,θ,xℓ)≜L(p^,xℓ)−L(pθ,xℓ)=log⁡pθ(xℓ)p^(xℓ).(10)R_{n,\ell}(\hat{p},\theta,x^\ell)\triangleq L(\hat{p},x^\ell)-L(p_\theta,x^\ell)=\log\frac{p_\theta(x^\ell)}{\hat{p}(x^\ell)}. \tag*{(10)}

The two classical aggregate criteria are the average regret

Rav,ℓ(p^,θ)≜EXℓ∼pθRn,ℓ(p^,θ,Xℓ)(11)R_{\mathrm{av},\ell}(\hat{p},\theta)\triangleq\mathbb{E}_{X^\ell\sim p_\theta}R_{n,\ell}(\hat{p},\theta,X^\ell) \tag*{(11)}
=∑xℓ∈Xℓpθ(xℓ)log⁡pθ(xℓ)p^(xℓ)(12)=\sum_{x^\ell\in\mathcal{X}^\ell}p_\theta(x^\ell)\log\frac{p_\theta(x^\ell)}{\hat{p}(x^\ell)} \tag*{(12)}
=D(pθ∥p^),(13)=D(p_\theta\|\hat{p}), \tag*{(13)}

and the worst-case regret

Rmax⁡,ℓ(p^,θ)≜sup⁡xℓ∈XℓRn,ℓ(p^,θ,xℓ)(14)R_{\max,\ell}(\hat{p},\theta)\triangleq\sup_{x^\ell\in\mathcal{X}^\ell}R_{n,\ell}(\hat{p},\theta,x^\ell) \tag*{(14)}
=sup⁡xℓ∈Xℓlog⁡pθ(xℓ)p^(xℓ)(15)=\sup_{x^\ell\in\mathcal{X}^\ell}\log\frac{p_\theta(x^\ell)}{\hat{p}(x^\ell)} \tag*{(15)}

References

  1. [1]P. S. Laplace, Essai philosophique sur les probabilités. Courcier, Paris, France, 1814.
  2. [2]R. Krichevsky and V. Trofimov, “The performance of universal encoding,” IEEE Transactions on Information Theory, vol. 27, no. 2, pp. 199–207, 1981.DOI
  3. [3]A. Bietti, V. Cabannes, D. Bouchacourt, H. Jegou, and L. Bottou, “Birth of a transformer: A memory viewpoint,” in Thirty-seventh Conference on Neural Information Processing Systems, 2023.arxiv.org/abs/2306.00802
  4. [4]E. Edelman, N. Tsilivis, B. L. Edelman, E. Malach, and S. Goel, “The evolution of statistical induction heads: In-context learning markov chains,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.arxiv.org/abs/2402.11004
  5. [5]A. V. Makkvua, M. Bondaschi, A. Girish, A. Nagle, M. Jaggi, H. Kim, and M. Gastpar, “Attention with markov: A curious case of single-layer transformers,” in The Thirteenth International Conference on Learning Representations, 2025.
  6. [6]A. V. Makkvua, M. Bondaschi, A. Girish, A. Nagle, H. Kim, M. Gastpar, and C. Ekbote, “Local to global: Learning dynamics and effect of initialization for transformers,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
  7. [7]N. Rajaraman, M. Bondaschi, A. V. Makkvua, K. Ramchandran, and M. Gastpar, “Transformers on markov data: Constant depth suffices,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.arxiv.org/abs/2407.17686
  8. [8]M. Bondaschi, A. V. Makkvua, N. Rajaraman, X. Wei, R. Pascanu, C. Gulcehre, and M. Gastpar, “From markov to laplace: How mamba in-context learns markov chains,” in The Fourteenth International Conference on Learning Representations, 2026.arxiv.org/abs/2502.10178
  9. [9]M. Bondaschi and M. Gastpar, “Batch universal prediction,” in 2024 IEEE International Symposium on Information Theory (ISIT). IEEE, 2024, pp. 3552–3557.arxiv.org/abs/2402.03901
  10. [10]——, “The conditional regret-capacity theorem for batch universal prediction,” in 2025 IEEE Information Theory Workshop (ITW). IEEE, 2025, pp. 746–751.
  11. [11]T. M. Cover, Universal gambling schemes and the complexity measures of Kolmogorov and Chaitin. Tech. Rep. 12, Dept. Statist., Stanford Univ., Stanford, CA, 1974.
  12. [12]N. Merhav and M. Feder, “Universal prediction,” IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2124–2147, 1998.DOI
  13. [13]Q. Xie and A. R. Barron, “Minimax redundancy for the class of memoryless sources,” IEEE Transactions on Information Theory, vol. 43, no. 2, pp. 646–657, 1997.DOI
  14. [14]——, “Asymptotic minimax regret for data compression, gambling, and prediction,” IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 431–445, 2000.
  15. [15]B. Y. Ryabko, “Twice-universal coding,” Problems of information transmission, vol. 20, no. 3, pp. 173–177, 1984.
  16. [16]——, “Prediction of random sequences and universal coding,” Problems of information transmission, vol. 24, no. 2, pp. 87–96, 1988.
  17. [17]M. Falhatgar, A. Orlitsky, V. Pichapati, and A. T. Suresh, “Learning Markov distributions: Does estimation trump compression?” in 2016 IEEE International Symposium on Information Theory (ISIT), 2016.
  18. [18]Y. Hao, A. Orlitsky, and V. Pichapati, “On learning markov chains,” Advances in Neural Information Processing Systems, vol. 31, 2018.arxiv.org/abs/1810.11754
  19. [19]D. Paulin, “Concentration inequalities for markov chains by Marton couplings and spectral methods,” Electronic Journal of Probability, vol. 20, no. 79, pp. 1–32, 2015, see also arXiv:1212.2015v5 for the corrected version.arxiv.org/abs/1212.2015
  20. [20]R. Krichevsky, “Laplace’s law of succession and universal encoding,” IEEE Transactions on Information Theory, vol. 44, no. 1, pp. 296–303, 1998.
  21. [21]D. Braess and T. Sauer, “Bernstein polynomials and learning theory,” Journal of Approximation Theory, vol. 128, no. 2, pp. 187–206, 2004.DOI
  22. [22]F. Komaki, “Bayesian predictive densities based on latent information priors,” Journal of Statistical Planning and Inference, vol. 141, no. 12, pp. 3705–3715, 2011.DOI
  23. [23]——, “Asymptotically minimax bayesian predictive densities for multinomial models,” Electron. J. Statist., vol. 6, 2012.DOI
  24. [24]Y. Fogel and M. Feder, “Universal batch learning with log-loss,” in 2018 IEEE International Symposium on Information Theory, 2018.DOI
  25. [25]F. Liang and A. Barron, “Exact minimax strategies for predictive density estimation, data compression, and model selection,” IEEE Transactions on Information Theory, vol. 50, no. 11, pp. 2708–2726, 2004.
  26. [26]Y. Fogel and M. Feder, “Combining batch and online prediction,” in 2024 IEEE International Symposium on Information Theory Workshops (ISIT-W). IEEE, 2024.DOI
  27. [27]R. Sibson, “Information radius,” Z. Wahrscheinlichkeitstheorie verw. Gebiete, no. 14, pp. 149–160, 1969.DOI
  28. [28]S. Verdú, “α-mutual information,” IEEE Information Theory and Applications Workshop, 2015.DOI
  29. [29]A. R. Esposito, M. Gastpar, and I. Issa, “Sibson α-mutual information and its variational representations,” IEEE Transactions on Information Theory, vol. 72, no. 7, pp. 4434–4467, 2026.DOI
  30. [30]M. Tomamichel and M. Hayashi, “Operational interpretation of Rényi information measures via composite hypothesis testing against product and markov distributions,” IEEE Transactions on Information Theory, vol. 64, no. 2, pp. 1064–1082, 2018.DOI
  31. [31]A. R. Esposito, D. Wu, and M. Gastpar, “On conditional Sibson’s α-mutual information,” IEEE International Symposium on Information Theory, 2021.DOI
  32. [32]C. Cai and S. Verdú, “Conditional Rényi divergence saddlepoint and the maximization of α-mutual information,” Entropy, vol. 21, no. 10, 2019.DOI
  33. [33]S. Yagli, Y. Altug, and S. Verdu, “Minimax Rényi redundancy,” IEEE Transactions on Information Theory, vol. 64, no. 5, pp. 3715–3733, 2018.
  34. [34]M. Bondaschi and M. Gastpar, “Alpha-NML universal predictors,” IEEE Transactions on Information Theory, vol. 71, no. 2, pp. 1171–1183, 2025.
  35. [35]A. Rényi, “On measures of entropy and information,” in Proc. 4th Berkeley Sympos. Math. Statist. and Prob., Vol. 1, 1960.
  36. [36]Y. M. Shtarkov, “Universal sequential coding of single messages,” Problems Inform. Transmission, vol. 23, no. 3, pp. 175–186, 1987.
  37. [37]S. Arimoto, “An algorithm for computing the capacity of arbitrary discrete memoryless channels,” IEEE Transactions on Information Theory, vol. 18, no. 1, pp. 14–20, 1972.DOI
  38. [38]R. Blahut, “Computation of channel capacity and rate-distortion functions,” IEEE Transactions on Information Theory, vol. 18, no. 4, pp. 460–473, 1972.DOI
  39. [39]D. Haussler, “A general minimax result for relative entropy,” IEEE Transactions on Information Theory, vol. 43, no. 4, pp. 1276–1280, July 1997.DOI
  40. [40]H. S. Witsenhausen, “Some aspects of convexity useful in information theory,” IEEE Transactions on Information Theory, vol. 26, no. 3, pp. 265–271, 1980.DOI
  41. [41]L. Barletta, I. Zieder, A. Favano, and A. Dytso, “Binomial channel: On the capacity-achieving distribution and bounds on the capacity,” in 2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 711–716.arxiv.org/abs/2401.12818
  42. [42]D. A. Levin and Y. Peres, Markov Chains and Mixing Times, 2nd ed. Providence, RI: American Mathematical Society, 2017.
  43. [43]S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge University Press, 2004.
  44. [44]A. Bhaskar and Y. S. Song, “Descartes’ rule of signs and the identifiability of population demographic models from genomic variation data,” The Annals of Statistics, vol. 42, no. 6, pp. 2469–2493, 2014.DOI

Paper details

vlnc:W_3dr7ntd7
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents