1 Introduction↩︎

Consider forecasting a sequence of outcomes \((y_t)_{t \geq 1}\), taken from a finite set \(\mathcal{Y}\), when the outcomes are selected by an adaptive adversary. When the predictions are probability forecasts \((q_t)_{t \geq 1}\) and the loss function is the squared loss \(\ell(p, y) = \sum_{j=1}^d \left( p_j - \mathbf{e}_y \right)^2\), it is well-known that the cumulative squared loss can be decomposed into the sum of the calibration score — a measure of the extent to which the forecaster is not calibrated — and the refinement score — representing the fundamental variance present within the outcome sequence. To calibeat is to reduce (or beat) the cumulative loss of a forecaster by an amount equal to the forecaster’s calibration score. In their seminal work, [1] showed that online calibeating strategies do exist. Regarding the squared loss (also called the Brier score in their work), they mentioned:

“it easily leads to useful decompositions, such as the Brier score being the sum of the refinement and calibration scores here. However, it raises the question of how much our results depend on the quadratic scores. We believe that the ideas and approach here carry through for other scoring functions…”

Foster and Hart go on to show a similar decomposition is possible for the log loss, leaving open how to push through calibeating for general proper losses.

Our work shows how to achieve calibeating for general proper losses by making a fundamental connection to no-regret online learning.⁴ A key player in making this connection is the Bregman divergence viewpoint of a proper loss. While this viewpoint is well-understood [3]–[5], we are unsure if the general community is aware of how neatly calibeating can be connected to regret minimization through the language of Bregman divergences. Moreover, in the course of making this connection, we discovered that we had devised a U-calibration procedure.

U-calibration, recently introduced by [6], is the problem of finding a single algorithm (that generates a single sequence of predictions) that simultaneously obtains low regret for all losses in some class of losses. The original U-calibration paper [6] considered the class of all bounded, proper losses, as did a follow-up paper by [7]. Our regret minimization results are also U-calibration results. Unlike previous results, the class of losses we consider includes the set of unscaled \(\alpha\)-Tsallis losses, defined for any \(\alpha \in [1, 2]\) as \[\begin{align} \ell_\alpha(p, y) = \frac{1}{1 - \alpha} \left( \alpha p_y^{\alpha - 1} - 1 \right) + \sum_{j=1}^d p_j^\alpha . \end{align}\] We use the term “unscaled” because prior works [7]–[9] instead consider the scaled \(\alpha\)-Tsallis loss, defined for any \(\alpha \in [1, 2]\) as⁵ \[\begin{align} \ell_{\mathrm{\alpha}}(p, y) = (\alpha - 1) \sum_{j=1}^d p_j^\alpha - \alpha p_y^{\alpha - 1} . \end{align}\] Our interest in the unscaled family is that it includes as special cases the log loss (corresponding to the limiting case of \(\alpha = 1\), henceforth referred to as \(\alpha = 1\) for simplicity) and the squared loss (corresponding to \(\alpha = 2\)). Our results also imply regret bounds for the scaled \(\alpha\)-Tsallis losses for \(\alpha \in [1, 2]\) (see 5.2 for our full discussion of unscaled and scaled Tsallis losses). We note, however, that the family we consider does not include the 0-1 loss. On the other hand, our results seem to be the first that attain U-calibration on classes of non-Lipschitz, unbounded losses.

The calibeating procedure we present is based on an algorithm that achieves U-calibration. Consequently, this calibeating procedure simultaneously calibeats for all losses in some class, a notion that we call U-calibeating. Our U-calibration algorithm itself fits into the Follow The Regularized Leader (FTRL) framework [10], as does our analysis. In particular, by using a generalized variance identity for Bregman divergences [11], we get a regret equality (1) for the regret of Be The Regularized Leader relative to the best prediction in hindsight. This regret equality allows us to extend the ideas of [1] for analyzing squared loss (and log loss) to the wider class of losses that we consider here. The regret equality holds for any proper loss and may be of independent interest.

Our core technical contributions are:

• A general, regret minimization-based analysis framework for calibeating.

• An apparently new regret equality (1, already mentioned above) for the regret of BTRL versus the best prediction in hindsight, holding for general proper losses. Behind this regret equality are two results that may be of independent interest: (a) a generalization of the variance update formula using a generalized notion of variance for Bregman divergences as well as general weights (see 8 in 7), and, relatedly, (b) a generalization of the online formula for the variance (see 9, also in 7).

• A single, simple algorithm that simultaneously obtains \(O(\log T)\) regret for the family of unscaled \(\alpha\)-Tsallis losses (which includes log loss and squared loss), the scaled \(\alpha\)-Tsallis losses (which are of interest in the robust statistics community), and all Lipschitz losses.

• For unscaled and scaled \(\alpha\)-Tsallis losses, using our general analysis, the \(T\)-dependent term has the optimal dimension dependence for log loss, which is \(d \log T\), and for squared loss, which is simply \(\log T\). Moreover, for any \(\alpha \in [1, 2]\), the \(T\)-dependent term is of order \(d^{2-\alpha} \log T\), which we suspect is the optimal rate for the \(\log T\) term. Our result improves on results of [7], who give the rate \(O(d^2 \log T)\) for any scaled \(\alpha\)-Tsallis loss and who do not consider the unscaled \(\alpha\)-Tsallis losses (thereby not being able to handle log loss).

• Our general analysis for unscaled and scaled \(\alpha\)-Tsallis losses gives an additive \(d\) term, which should not be present for squared loss. For Lipschitz losses with Lipschitz constant \(G\), when using no regularization the algorithm obtains regret \(O(G \log T)\). For squared loss, this regret bound is \(O(\log T)\) with no additive \(d\) factor.

The next section formalizes the problem setting. We present some background and related work in 3. Next, in 4, we introduce the structure of our analysis framework, showing the connection between calibeating and regret minimization and giving an overview of our U-calibration regret analysis. In 5, we establish U-calibration results by exhibiting a simple FTRL procedure and showing that it simultaneously obtains low regret for various subclasses of losses. We then move to our U-calibeating results in 6. In 7, we sketch a proof of our regret equality result (1). Finally, 8 closes with a discussion and open questions. All proofs not presented in the main text appear in the appendix.

2 Problem Setup↩︎

In this section, we first formally introduce proper losses and calibeating and then review how to represent proper losses in terms of convex functions and, similarly, in terms of a Bregman divergences.

2.0.0.1 Proper losses.

We consider losses of the form \(\ell: \Delta_d \times [d] \rightarrow \mathbb{R}\cup\{+\infty\}\).⁶ We extend the second argument of \(\ell\) to the simplex \(\Delta_d\) via \(\ell(p, q) = \mathop{\mathrm{\mathbb{E}}}_{Y \sim q} [ \ell(p, Y) ]\). When the second argument of the loss corresponds to a label \(y\), we may write either \(y\) or \(\mathbf{e}_y\), where \(\mathbf{e}_y\) is the \(y\mathop{\mathrm{^{\text{th}}}}\) standard basis vector. A loss is proper if for all \(q \in \Delta_d\), the prediction \(q\) is a minimizer of \(p \mapsto \ell(p, q)\). Moreover, a loss is strictly proper if \(q\) is a unique minimizer. Throughout this work, we consider proper losses, and we implicitly assume that perfect prediction results in zero loss, i.e., \[\begin{align} \ell(\mathbf{e}_y, y) = 0 \quad \text{for all } y \in \mathcal{Y}. \label{eqn:fair} \end{align}\tag{1}\]

2.0.0.2 Calibeating.

Before introducing calibeating, we require some notation. For any \(t \in [T]\), we denote the empirical outcome frequency up until round \(t\) as \(\bar{p}_t = \frac{1}{s} \sum_{s=1}^t \mathbf{e}_{y_s}\). For any \(x \in \Delta_d\) and sequence of forecasts \((q_t)_t\), let \(\mathcal{T}_x = \{t \in [T] : q_t = x\}\) and \(\bar{p}_T(x)\) be the empirical outcome frequency among the rounds in \(\mathcal{T}_x\). Similarly, for any set \(B \subseteq \Delta_d\), let \(\mathcal{T}_B = \{t \in [T] : q_t \in B\}\).

Following [1], we introduce calibeating in the case of the squared loss \(\ell(p, y) = \left\| p - \mathbf{e}_y \right\|_2^2\). For a forecaster with sequence of probability forecasts \((q_t)_{t \in [T]}\) against outcome sequence \((y_t)_{t \in [T]}\), the cumulative squared loss \(\mathcal{L}_T = \sum_{t=1}^T \ell(q_t, y_t)\) admits the decomposition \(\mathcal{L}_T = \mathcal{L}_T^{(\mathrm{ref})} + \mathcal{L}_T^{(\mathrm{cal})}\), where \[\begin{align} \mathcal{L}_T^{(\mathrm{ref})} = \sum_{t=1}^T \left\| \mathbf{e}_{y_t} - \bar{p}_T(q_t) \right\|_2^2 \end{align}\] is the refinement score and \[\begin{align} \mathcal{L}_T^{(\mathrm{cal})} = \sum_{t=1}^T \left\| \bar{p}_T(q_t) - q_t \right\|_2^2 \end{align}\] is the calibration score.

Now, we say that a sequence \((p_t)_{t \in [T]}\) calibeats \((q_t)_{t \in [T]}\) if \[\begin{align} \sum_{t=1}^T \ell(q_t, y_t) - \sum_{t=1}^T \ell(p_t, y_t) \geq \mathcal{L}_T^{(\mathrm{cal})} + o(T) , \end{align}\] where \(\mathcal{L}_T^{(\mathrm{cal})}\) is the calibration score under \((q_t)_{t \in [T]}\).

In 4.1, we show that the concept of calibeating — developed above for squared loss — can be extended to arbitrary proper losses.

2.0.0.3 Representation of proper loss in terms of convex function.

For a convex function \(\psi:\Delta_d\mapsto \overline{\mathbb{R}}\) we define its Bregman divergence \(D_{\psi}:\Delta_d\times\Delta_d\mapsto\overline{\mathbb{R}}\) as \[D_{\psi}(p,q)=\psi(p)-\psi(q)-\langle \nabla \psi(q),p-q\rangle \qquad \forall p\in \Delta_d,\,\forall q\in dom(\partial \psi) ,\] where \(\nabla \psi\) is a (measurable) selection of subgradients of \(\psi\); in particular, \(\nabla \psi(p)\in \partial \psi(p)\), for all \(p\in dom(\partial \psi)\). One of the most useful properties of Bregman divergences is the three-points identity [12], \[\begin{align} \label{eqn:three95points95identity} D_\psi(p, q) = D_\psi(p, r) + D_\psi(r, q) + \bigl\langle \nabla \psi(r) - \nabla \psi(q), p - r \bigr\rangle . \end{align}\tag{2}\]

Next, we review the Savage representation of a proper loss [5], [13], [14].

We call the function \(\psi\) the convex representation of the proper loss \(\ell\). This representation enjoys some properties that will be needed throughout.

3 Background and Related work↩︎

3.0.0.1 Proper losses.

Proper losses were first introduced in the special case of Brier loss by [15] and then more generally by [16]. These short papers were succeeded by longer expositions by [17], [13], [4], [14], and [5]. In the binary case, [17] characterized proper losses via what is now commonly called the Savage representation of a proper loss. [13] obtained his eponymous representation in the multi-class case. In a fundamental paper, [14] provided a more rigorous treatment of the Savage representation. The explicit connection between proper losses and Bregman divergences was first made — essentially in parallel — by [14], [3], and [4], with the latter authors focusing on the binary case.

[18] showed for binary outcomes that the expectation of a proper loss can be decomposed into the refinement score and the calibration score. [19] showed⁷ this decomposition holds for general proper losses. Here we review this decomposition to help with the understanding of 4.1. Let the forecast \(R\) be a random variable which can (and, if it is any good, should) depend on the outcome \(Y\), also viewed as a random variable. Assume that \(Y\) has law \(P\) and let \(P_r\) denote the conditional law of \(Y\) given \(R = r\). Then the expected loss conditional on report realization \(r\) is \[\begin{align} \ell(r, P_r) &= \mathop{\mathrm{\mathbb{E}}}[ \ell(r, Y) \mid R = r] \\ &= \mathop{\mathrm{\mathbb{E}}}_{Y \sim P_r} [ \ell(P_r, Y) \mid R = r] + D_\psi(P_r, r) \\ &= \ell(P_r, P_r) + D_\psi(P_r, r) , \end{align}\] where \(\ell(P_r, P_r)\) is the conditional refinement score and \(D_\psi(P_r, r)\) is the conditional calibration score, both conditional on \(R = r\). We can then express the (unconditional) expectation of the loss of \(R\) in terms of the (unconditional) refinement and calibration scores: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}[ \ell(R, Y) ] = \mathop{\mathrm{\mathbb{E}}}[ \ell(P_R, P_R) ] + \mathop{\mathrm{\mathbb{E}}}[ D_\psi(P_R, R) ] . \end{align}\] This decomposition is completely analogous to the decomposition in the online setting, shown both by [1] for Brier loss and log loss and shown by us (4.1) for general proper losses.

3.0.0.2 Follow The Regularized Leader.

FTRL has too rich of a history to cover here; we refer the reader to the excellent history given in bibliographical notes of [20]. One standard analysis of FTRL’s regret is to equate the regret with the sum of two regrets: the regret of FTRL versus BTRL (which is a type of stability term) and the regret of BTRL (versus the best prediction in hindsight). When the loss is Lipschitz, a simple analysis of the stability term involves bounding each iterate by the learning rate \(\eta\) times the dual norm of a gradient. For proper losses, a tighter analysis of the stability term is possible: properness allows for a closed form expression for FTRL and BTRL, and again due to properness, the predictions of FTRL and BTRL in a given iterate are close. This tighter analysis is implicit in the analysis of [1] and is used in the FTL analysis of [7].

Regarding the regret of BTRL, the standard analysis is to apply the “Be The Leader” Lemma to the regularized losses, giving an upper bound equal to the difference between the regularizer’s maximum value and the regularizer’s evaluation at FTRL’s initial prediction. The Be The Leader Lemma is originally due to [21] (see also see also Lemma 3.1 of [22]). For proper losses, a tighter analysis of BTRL’s regret is also possible. In the case of Brier loss, [1] showed how BTRL’s regret (although they did not use this language) can be expressed using the online formula for the variance. This formula can be proved using the law of total variance. [11] showed a generalized law of total variance that holds for Bregman divergences; we use this result to obtain a generalized online formula for the variance and ultimately extend Foster and Hart’s expression for BTRL’s regret in terms of this generalized online formula for the variance. The generalized law of total variance shown by [11] is of intrinsic interest, but Gupta et al. emphasized the importance of this law for separating out the effect of different sources of randomness on the performance of machine learning algorithms.

3.0.0.3 Calibration and Calibeating.

The calibration literature is too broad to be accurately represented in this review. Nevertheless, it is worth pointing out that the study of calibration in the online setting was initiated by the work of [23], that established asymptotic calibration for coherent forecasters in a Bayesian setting. This paper also introduces a strong impossibility result: no online forecaster can calibrate itself against nature in a coherent way. This impossibility was eventually circumvented by the remarkable work of [24], with the introduction of randomized strategies. This line of work later inspired the idea of calibeating [1].

[25] study online binary recalibration for proper losses. The main distinction between this work and the calibeating literature is that no ‘beating’ is established: namely, the recalibration procedure is approximately calibrated, but its regret is only approximately bounded by that of the uncalibrated procedure used as input.

Aside from papers mentioned earlier, there are not many works focusing on calibeating or recalibration more broadly. In the offline setting, Platt’s scaling is a popular approach [26]. This method takes a pretrained classifier as input and recalibrates it on new data by warping within a parametric family of sigmoids. An online recalibration strategy based on Platt’s scaling was proposed by [27]. We remark that their recalibration strategy is based on Brier score and therefore is not directly related to the interests of our work.

3.0.0.4 Concurrent works.

After completing our work, we became aware of two concurrent and independent works, by [2] and [28], which also study calibeating. We discuss these works in turn.

Both [2] and our work make exactly the same key observation that calibeating can be reduced to no-regret learning. The works diverge at this point. When considering regret that is logarithmic in \(T\), [2] consider using exponentially weighted online optimization [29]; this method is loss-specific, meaning that changing the loss will change the sequence of predictions.⁸ On the other hand, we consider a simple FTRL-style algorithm that U-calibeats (i.e, simultaneously calibeats) for a class of losses that includes Lipschitz proper losses and \(\alpha\)-Tsallis losses (for \(\alpha \in [1, 2]\)). Interestingly, [2] also show that lower bounds for regret minimization imply lower bounds for calibeating, giving minimax equivalence. They also show results for multi-calibeating and obtaining calibeating predictors that cannot themselves be “calibeaten”; while very interesting, these results do not overlap with our work and so are out of scope for our comparison.

[28] study calibration and calibeating for the class of Lipschitz proper losses. Among their main results that may overlap with our work⁹ are that calibration under squared loss implies calibration under all Lipschitz proper losses and that calibeating under squared loss does not imply calibeating for general, Lipschitz proper losses. Regarding the first result, they define a notion of proper calibeating: a single predictor proper calibeats if it simultaneously calibeats for all Lipschitz¹⁰ proper losses. They show that a simple predictor, FTL, proper calibeats. Comparing to our work, proper calibeating is equivalent to U-calibeating when the class of losses is all Lipschitz proper losses. We show that the FTRL predictor 4 proper calibeats, but more than that, it U-calibeats for an expanded class of losses that includes the \(\alpha\)-Tsallis family of losses for \(\alpha \in [1, 2]\); recall that \(\alpha\)-Tsallis loss is not Lipschitz for \(\alpha \in [1, 2)\). To prove that FTL proper calibeats, [28] generalize various supporting technical results of their prior analysis [1] to accommodate general proper losses. We independently also extend the prior analysis of [1], but for FTRL, which introduces some additional challenges.

Ultimately, despite a similar motivation to extend the theory of calibeating to general proper losses, the results in our work and that of [28] are mostly independent (when considering their common ancestor of [1]). Also, in particular, their work does not study non-Lipschitz losses and (relatedly) does not incorporate regularization.

4 Analysis framework↩︎

4.1 From Calibeating to U-Calibration↩︎

To isolate the crux of the connection between calibeating and no-regret learning, in this section we consider a forecaster whose probability forecasts \((q_t)_{t \geq 1}\) belong to a finite set of forecasts \(\mathcal{Q} \subset \Delta_d\). For this section only, the reader should think of each forecast from \(\mathcal{Q}\) occurring frequently in the sequence \((q_t)_{t \geq 1}\). In general, the probability forecast in each round can be and likely is distinct, even as \(T \rightarrow \infty\). We handle this more general setting in 6 by extending our analysis in the present section with a more or less standard binning approach.

We begin with the decomposition \[\begin{align} \sum_{t=1}^T \ell_t(q_t, y_t) = \sum_{x \in \mathcal{X}} \sum_{t \in \mathcal{T}_x} \ell_t(q_t, y_t) . \end{align}\]

We call the first summation in the right-hand side of ?? the conditional refinement score (given \(x\)) because, after summing over \(x\), it becomes the (unconditional) refinement score. We call the second summation the conditional calibration score (given \(x\)); again, summing over \(x\) yields the (unconditional) calibration score. In the case of squared loss, the conditional refinement score is nothing other than the variance of the outcomes among the rounds in which the forecaster played forecast \(x\). If we think of each forecast \(x\) as defining its own bin¹¹ — all rounds where the forecast is made belong to this bin — then for a fixed binning, this variance of the outcomes within a bin is fundamental to the sequence of outcomes and cannot be reduced by the forecaster. For general proper losses, this irreducible quantity is a generalized entropy. It is fruitful to consider the following normalized version of the conditional refinement score: \[\begin{align} \frac{1}{|\mathcal{T}_x|} \sum_{t \in \mathcal{T}_x} D_\psi(y_t, \bar{p}_T(x)) . \end{align}\] Using the simple observation that \(D_\psi(y_t, \bar{p}_T) = \ell(\bar{p}_T, y_t)\) and the properness of the loss, the above is equal to \[\begin{align} \frac{1}{|\mathcal{T}_x|} \sum_{t \in \mathcal{T}_x} \ell(\bar{p}_T(x), y_t) = \min_{q \in \Delta_d} \frac{1}{|\mathcal{T}_x|} \sum_{t \in \mathcal{T}_x} \ell(q, y_t) . \end{align}\] Using this alternate form for the conditional refinement score immediately gives the following re-expression of 2.

Thus, the conditional calibration score (the second summation on the right-hand side of ?? ) is precisely the regret of the forecaster for the subgame induced by \(\mathcal{T}_x\). From here, our goal is to, in an online way, improve the forecaster’s predictions by swapping out the sequence \((q_t)_{t \in \mathcal{T}_x}\) with an improved sequence \((p_t)_{t \in \mathcal{T}_x}\) that obtains as low regret as possible. Put another way, considering the subgame induced by \(\mathcal{T}_x\), we wish to beat the original forecaster (i.e., reduce its cumulative loss) by an amount which — modulo the regret — is equal to the conditional calibration score. After summing over \(x\), we wish to — modulo the sum (over \(x\)) of the regrets — beat the original forecaster by an amount equal to its calibration score. Moreover, to accommodate downstream agents that might care about different proper losses, we would like to choose the new sequence \((p_t)_t\) in a way that is agnostic to the particular proper loss being used. That is, we want the new sequence to obtain low regret for all loss functions in some large class. This problem is exactly the problem of U-calibration.

4.2 U-Calibration via FTRL↩︎

Let \(\mathbf{p}^T\) denote a sequence of forecasts \((p_t)_{t \in [T]}\), and let \(\mathbf{y}^T\) denote a sequence of outcomes \((y_t)_{t \in [T]}\). The regret \(\mathcal{R}^{(\ell)}(\mathbf{p}^T, \mathbf{y}^T)\) of an online learning algorithm that forms predictions \(\mathbf{p}^T\) under outcome sequence \(\mathbf{y}^T\) is defined as \[\begin{align} \mathcal{R}^{(\ell)}(\mathbf{p}^T, \mathbf{y}^T) = \sum_{t=1}^T \ell(p_t, y_t) - \min_{p \in \Delta_d} \sum_{t=1}^T \ell(p, y_t) . \end{align}\] Formally, as it was originally introduced by [6], the U-calibration error of an online learning algorithm that forms predictions \((p_t)_t\) is the supremum, taken over all proper losses \(\ell\) with bounded range \([-1, 1]\), of the regret \(\mathcal{R}^{(\ell)}(\mathbf{p}^T, \mathbf{y}^T)\), i.e., \[\begin{align} \sup_{\ell\colon \Delta_d \times \mathcal{Y}\rightarrow [-1, 1]} \mathcal{R}^{(\ell)}(\mathbf{p}^T, \mathbf{y}^T) . \end{align}\] Note that the single sequence of predictions is assessed against any such bounded proper loss. While this class of bounded proper losses includes popular losses like squared loss, 0-1 loss, and cost-sensitive losses (referred to as V-shaped scoring rules in [6]), a notable, popular omission from this class is the log loss. Morever, there is an entire spectrum of losses that interpolate between the log loss and the squared loss; this spectrum is traced out by the family of unscaled \(\alpha\)-Tsallis losses.

In this work, we consider a variant of U-calibration that, using a single sequence of predictions, seeks to obtain, for each proper loss for which the minimax regret is \(O(\log T)\), the optimal regret for that loss. While our focus on \(O(\log T)\) regret necessarily rules out the 0-1 loss, this focus allows us to pursue refined dependence on dimension quantities. In particular, we seek improved dependence on the dimension \(d\) compared to analyses from previous works.

To set the stage for our algorithm, we begin by considering Follow The Leader (FTL) in the case of Lipschitz losses. In round \(t\), FTL plays the empirical mean \(\bar{p}_{t-1}\). For the class of Lipschitz losses, it is not hard to show that FTL obtains regret that is logarithmic in \(T\). Yet, there are various proper losses for which FTL produces linear regret. For example, under log loss, it is not hard to show that FTL can obtain infinite (hence, at least linear) regret. A standard solution is to somehow restrict predictions to a suitable interior of the simplex. One way to accomplish this restriction is to employ regularization. This is precisely the approach we take here: for each loss, we use an instance of FTRL. Depending on the loss, the choice of regularizer varies, but due to a nice property of proper losses (and the particular choice of regularizer we employ), the effect of the regularization on the prediction \(p_t\) will be the same for all losses. That is, the predictions are agnostic to the particular proper loss being used. Yet, for a large class of losses, we will be able to obtain regret bounds that are logarithmic in \(T\) with either the optimal (or improved, relative to previous results) dependence on the dimension \(d\).

The FTRL algorithm that we use is defined according to \[\begin{align} p_{t+1} = \mathop{\mathrm{arg\,min}}_{p \in \Delta_d} \left\{ \sum_{s=1}^t \ell(p, y_s) + \frac{1}{\eta} \Phi(p) \right\} , \label{eqn:ftrl} \end{align}\tag{4}\] where \(\Phi(p) = \sum_{j=1}^d \ell(p, \mathbf{e}_j)\). Since the regularizer is a sum of losses, we call this regularizer loss-based regularization. Given the form of the regularizer, it is easy to see that \(p_{t+1}\) takes the form \[p_{j,t+1} = \frac{c_{j,t} + \frac{1}{\eta}}{t + \frac{d}{\eta}} ,\] where \(c_{j,t} = \sum_{s=1}^t \delta_{\{\mathbf{e}_{y_s}=j\}}\) is the number of times outcome \(j\) has occurred by the end of round \(t\).

The next proposition provides a regret decomposition that is the foundation for our regret analysis. We express the regret of FTRL as the sum of the regret of FTRL relative to Be The Regularized Leader (BTRL), the regret of BTRL relative to \(p_{T+1}\) (the best action in hindsight when regularizing the losses), and the regret of \(p_{T+1}\) relative to the best action in hindsight. In the result below, recall that \(\bar{p}_T = \frac{1}{T} \sum_{t=1}^T \mathbf{e}_{y_t}\) is the best action in hindsight from the properness of the loss.

In 5, we will show how to bound each of the terms in 4 for various classes of losses. Here, we comment on our approach for controlling the regret of BTRL with respect to its final iterate \(p_{T+1}\) (the best action in hindsight when considering the regularized cumulative loss). The typical way to control this regret is via the Be The Leader Lemma (see e.g. Lemma 3.1 of [22]), suitably adapted to accommodate regularization. In the special case of loss-based regularization, we introduce in 1 below an apparently new way to express this regret. The regret representation given in the lemma, being an equality, is stronger than what one gets from the Be The Leader Lemma approach. The key to our lemma is a generalized variance identity for Bregman divergences.

In the next lemma, for \(j \in [d]\), we somewhat abuse notation and define \(p_{j/d} = \frac{1}{j} \sum_{i=1}^j \mathbf{e}_i\). For clarity, note that \(p_{1/d} = \mathbf{e}_1\), \(p_{2/d} = \frac{1}{2} (\mathbf{e}_1 + \mathbf{e}_2)\), and \(p_{d/d} = p_1 = \frac{1}{d} \mathbf{1}\) (which makes our abuse of notation consistent with our standard notation).

Note that on the right-hand side of the equality, all the summation terms but the first one are nonpositive (either due to the nonnegativity of the loss or the nonnegativity of Bregman divergences). In our regret analysis for unscaled \(\alpha\)-Tsallis loss, we make use of the first nonpositive summation term, but we have not yet tried to make use of the last two summations (we simply drop them in our analysis). For more detail, see 13 on .

The heart of the analysis behind 1 is a generalized law of total variance [11] for a generalized notion of variance based on Bregman divergences. From the generalized law of total variance, we derive generalized versions of both the variance update formula and the online formula for the variance. These latter two results may be of independent interest. For more information and a proof sketch of 1, we direct the interested reader to 7.

5 Regret bounds↩︎

5.1 Warmup: Lipschitz losses↩︎

As a warm-up, we first show how to use the general FTRL-based regret decomposition 2 for losses that are \(G\)-Lipschitz. An equivalent result was shown by [7].

We also briefly mention that if instead we set \(\eta = 1\) (as we will do for Tsallis losses), then we get a somewhat worse regret bound of \(G R (d + \log T)\); this result is 8 in 9.

The squared loss (also called Brier loss) is defined as \(\ell_{\mathrm{sq}}(p, y) = \sum_{j=1}^d (p_j - (\mathbf{e}_y)_j)^2\). We can take \(\|\cdot\|\) to be the \(\ell_1\) norm, so the diameter \(R = 2\), and then \(G = 2\) is an upper bound on \(\ell_\infty\) norm of the gradient, so overall we get the regret bound \(4 (1 + \log T)\).

The spherical loss is defined as \(\ell(p, y) = 1 - \frac{p_y}{\sqrt{\sum_{j=1}^d p_j^2}}\). For spherical loss, we can take \(G = 2 \sqrt{d}\), which gives the following regret bound.

5.2 Scaled and unscaled \(\boldsymbol{\alpha}\)-Tsallis loss↩︎

The \(\alpha\)-Tsallis score is a loss function that has seen use in the robust statistics literature [9]. For \(\alpha > 1\), which is the regime of interest in robust statistics, \(\alpha\)-Tsallis score is defined as [8]: \[\begin{align} \ell_{\mathrm{\alpha}}(p, y) = (\alpha - 1) \sum_{j=1}^d p_j^\alpha - \alpha p_y^{\alpha - 1} . \label{eqn:tsallis-score} \end{align}\tag{6}\] Note that \(\alpha\)-Tsallis score is strictly proper.¹²

When it comes to regret minimization, an interesting property of the \(\alpha\)-Tsallis score is that in the regime \(\alpha \in (1, 2)\), the loss is not Lipschitz. We also note that in this regime, the loss range is contained in \([-1, 1]\). Recently, [7] showed in their Corollary 3 that for \(\alpha \in (1, 2)\), FTL obtains a regret bound of¹³ \[\begin{align} O(\alpha (\alpha - 1) d^2 \log T) \label{eqn:luo-tsallis-regret} . \end{align}\tag{7}\]

In the limiting case of \(\alpha \rightarrow 2\), the \(\alpha\)-Tsallis score becomes \(\ell_2(p, y) = \sum_{j=1}^d p_j^2 - 2 p_y\), which is a (shifted, depending on convention) version of squared loss. The family of \(\alpha\)-Tsallis scores, while standard in the literature, is somewhat unsatisfying because the other limiting case, of \(\alpha \rightarrow 1\), renders the loss trivial. If one shifts the \(\alpha\)-Tsallis score by adding one and then divides the result by \((\alpha - 1)\), we get the following affine transformation of \(\alpha\)-Tsallis score: \[\begin{align} \ell_\alpha(p, y) = \frac{1}{1 - \alpha} \left( \alpha p_y^{\alpha - 1} - 1 \right) + \sum_{j=1}^d p_j^\alpha , \label{eqn:our-tsallis} \end{align}\tag{8}\] We call this transformed version of the \(\alpha\)-Tsallis score the unscaled \(\alpha\)-Tsallis loss. Like the scaled \(\alpha\)-Tsallis loss, if we set \(\alpha = 2\) then the unscaled \(\alpha\)-Tsallis loss becomes the version of squared loss we gave earlier in the paper: \(\ell_2(p, y) = \sum_{j=1}^d \left( p_j - (\mathbf{e}_y)_j \right)^2 = \ell_{\mathrm{sq}}(p, y)\). Unlike the scaled \(\alpha\)-Tsallis loss, for unscaled \(\alpha\)-Tsallis loss the limiting case of \(\alpha \rightarrow 1\) recovers log loss, i.e., \(\ell_1(p, y) = -\log p_y = \ell_{\log}(p, y)\). Since log loss is unbounded, it follows that in the range \(\alpha \in (1, 2)\), unscaled \(\alpha\)-Tsallis loss is not bounded in general (although it becomes bounded as soon as \(\alpha\) is bounded away from 1 by some positive margin).

In this section, we show regret bounds for FTRL with loss-based regularization under unscaled \(\alpha\)-Tsallis loss. Since unscaled \(\alpha\)-Tsallis loss can be transformed into scaled \(\alpha\)-Tsallis loss by multiplying by \((\alpha - 1)\) and then shifting by 1, our regret bounds for unscaled \(\alpha\)-Tsallis loss immediately imply the same regret bounds for scaled \(\alpha\)-Tsallis score after scaling by \((\alpha - 1)\). Despite the fact that the loss range of unscaled \(\alpha\)-Tsallis loss is unbounded as \(\alpha \rightarrow 1\), the next theorem shows that FTRL obtains \(O(d \log T)\) regret.

Our bound in Theorem 2 — after multiplying by \((\alpha - 1)\) due to the scale difference — improves the bound 7 by improving the dimension dependence from \(d^2\) to \(d^{2 - \alpha}\), which is always strictly better. Moreover, our theorem covers the fundamentally important case of log loss [30], which cannot be covered by the scaled \(\alpha\)-Tsallis loss results of [7] (nor their other results, since they restrict to bounded losses). We note that for squared loss (\(\alpha = 2\)), an optimal bound would have no dimension dependence (see 1), whereas our bound still has an additive \(O(d)\) gap. We believe this term \(d\) is an artifact of our analysis. We conjecture that for all \(\alpha \in [1, 2]\), the optimal regret for both unscaled and scaled \(\alpha\)-Tsallis loss is \(O(d^{2-\alpha} \log T)\).

Next, we sketch our proof of Theorem 2.

5.3 Proof sketch of Theorem 2↩︎

Proofs for all lemmas in this section can be found in 10.

The next lemma bounds the stability term.

Next, we bound the regret of BTRL relative to \(p_{T+1}\).

The dependence on \(\eta\) in the above result is strange because as \(\eta \rightarrow \infty\), BTRL becomes Be The Leader (BTL) and \(p_{T+1}\) becomes the best action in hindsight. Hence, in this case, we should expect a nonpositive regret bound. We attribute our result not being good in this case to our dropping — in the proof — certain nonpositive terms from 4 (which generally seem minor but can become very important when \(\eta\) is large). Also, as \(\eta \rightarrow 0\), our bound is the best possible, even though BTRL is useless in this case. The way to reconcile this latter fact is that we also compare BTRL to the regularized best-in-hindsight action \(p_{T+1}\), so when \(\eta = 0\), both BTRL and the regularized best-in-hindsight action are the uniform distribution.

We also give a second result for BTRL’s regret relative to \(p_{T+1}\). When \(\alpha\) is bounded away from \(1\) with some margin, this second result is generally better since its bound does not grow with \(T\).

Finally, we control the smoothing term. Unlike the previous results, currently we only give a bound for \(\eta = 1\) due to the difficulty in bounding this term.

The proof of 5 is intricate. We did not see a way to illuminate the proof using a sketch.

6 Calibeating↩︎

Recall that in 4.1 we assumed a trivial binning where each distinct forecast is associated with its own bin. In general, it is likely that each forecast in the sequence \((q_t)_{t \geq 1}\) was made only in a single round; consequently, each online learning subgame in 4.1 consists of a single round, and no-regret learning becomes useless. In the present section, we give our full results for calibeating. To this end, we first present 6, which extends 2 to accommodate binnings for which each bin can contain multiple, distinct forecasts.

Let \(\mathcal{B}\) be a finite, disjoint union of bins \(B\) such that \(\bigcup_{B \in \mathcal{B}} = \Delta_d\) and each bin \(B\) has a unique representative \(\tilde{x}_B\) in a finite grid \(\mathcal{G}\). Thus, in particular, each forecast \(x \in B\) is associated with representative \(\tilde{x}_B\). For any bin \(B \in \mathcal{B}\), recall that \(\mathcal{T}_B = \{t \in [T] : p_t \in B\}\).

Similar to 3, we can re-express the equality in 6 in terms of regret-minimization.

The above proposition makes clear that the conditional calibration score plus a (typically negative) approximation error due to binning is equal to the regret. Thus, if we can improve the forecast sequence \((q_t)_{t \in \mathcal{T}_B}\) to a sequence \((p_t)_{t \in \mathcal{T}_B}\) whose time-average regret (over \(\mathcal{T}_B\)) goes to zero as \(|\mathcal{T}_B| \rightarrow \infty\), then up to the additive approximation error term and the regret of \((p_t)_{t \in \mathcal{T}_B}\), we will have reduced the cumulative loss of the sequence \((q_t)_{t \in \mathcal{T}_B}\) by an amount equal to the conditional calibration score. The next result formalizes this idea.

The regret term in the corollary can be controlled using our U-calibration results (e.g., 2). The next result controls the approximation error.

Let us assume that we choose the binning from the proof of 6 so that the per-round approximation error is \(O(\varepsilon)\). Then letting \(N_\varepsilon\) be the number of bins, it is possible to show the following result. We omit factors polynomial in \(d\) for simplicity.

For completeness, we give a proof of the first inequality of the theorem in 11. The second inequality just involves some algebra.

7 Proof sketch of 1↩︎

In this section, we sketch our proof of 1. Along the way, we develop two results — 8 and 9 — that strictly extend arguments of [1] and may be of interest in their own right. Because of how we prove 1, for this section only it will be convenient to adopt the notation \(x_1, \ldots, x_n\) to refer to a sequence of \(n\) outcomes (each represented as a “one-hot” \(d\)-dimensional vector). In addition, for any \(k \in [n]\), we define the empirical mean \(\bar{x}_k = \frac{1}{k} \sum_{i=1}^k x_i\) (which is an empirical frequency vector).

The spiritual predecessor of our analysis is Proposition 2 of [1], which they used to calibeat in the case of squared loss. Their Proposition 2 gives the following online formula for the variance: \[\begin{align} \sum_{i=1}^n \|x_i - \bar{x}_n\|_2^2 = \sum_{i=1}^n \left( 1 - \frac{1}{i} \right) \|x_i - \bar{x}_{i-1}\|_2^2 . \end{align}\] As mentioned and shown by [1], the above online formula for the variance easily follows from the variance update formula (see equation (10) of [1] or Formula I of [31] for an earlier reference) which, defining \(s_n = \sum_{i=1}^n \|x_i - \bar{x}_n\|^2\), is \[\begin{align} s_n = s_{n-1} + \left( 1 - \frac{1}{n} \right) \| x_n - \bar{x}_{n-1}\|^2 . \end{align}\] This formula is easily established using the law of total variance (see 14 below).

Our main work in establishing 1 is establishing a generalized version of the variance update formula and then using that result to obtain a generalized version of the online formula for the variance. The foundation for our generalized analysis is a powerful result¹⁵ of [11]: for any Bregman divergence \(D_\psi\), there is a generalized law of total variance. For random variables \(X\) and \(Y\), recall that the usual law of total variance states that \[\begin{align} \mathop{\mathrm{\mathsf{Var}}}(X) = \mathop{\mathrm{\mathbb{E}}}[\mathop{\mathrm{\mathsf{Var}}}(X \mid Y)] + \mathop{\mathrm{\mathsf{Var}}}(\mathop{\mathrm{\mathbb{E}}}[X \mid Y]). \label{eqn:law-total-var} \end{align}\tag{14}\] The next lemma states the generalized law of total variance.

In preparation for our generalization of the variance update formula, we set up some notation. For any \(n\), define for positive weights \(w_1, \ldots, w_n\): \[\begin{align} W_n := \sum_{j=1}^n w_j \qquad \bar{x}_n := \frac{\sum_{j=1}^n w_j x_{j}}{W_n} \qquad s_n := \sum_{i=1}^n w_i D_\psi(x_i, \bar{x}_n) . \end{align}\]

Note that 8 generalizes the standard variance update formula both by allowing for general weights and, more significantly, allowing for generalized variances. Taking \(w_i = 1\) and \(\psi = \|\cdot\|_2\) recovers the standard formula. After completing our results, we noticed that [1], in equation 36 of their Appendix A.6, had already generalized the standard variance update formula to allow for general weights (see also their Proposition 14 for their corresponding generalization of the online formula for the variance). Interestingly, Foster and Hart made this generalization to handle fractional binnings, whereas we made this generalization to handle loss-based regularization. Our results are further generalized by handling generalized variances (based on general Bregman divergences).

Next, we present a generalization of the online formula for the variance.

With the above two lemmas in place, we are ready to prove 1.

8 Discussion↩︎

We have shown that for both the unscaled and scaled version of \(\alpha\)-Tsallis loss with \(\alpha \in [1, 2]\), a single sequence of probability forecasts can obtain \(O(d + d^{2-\alpha} \log T)\) regret. While it was known that there exists an algorithm that obtains \(O(d \log T)\) regret for log loss, to our knowledge (from an extensive literature review) the best known regret bound (even without considering simultaneous regret) for the scaled \(\alpha\)-Tsallis loss with \(\alpha \in (1, 2)\) was \(O(d^2 \log T)\). This best known bound is from [7], and no prior results considered the unscaled version of \(\alpha\)-Tsallis loss (excluding the special cases of \(\alpha = 1\) and \(\alpha = 2\)). For log loss, it is known that \(O(d \log T)\) is the optimal rate. For squared loss, it is known that our additive \(d\) term is should not be present. For \(\alpha \in (1, 2)\), considering either the unscaled or scaled version of \(\alpha\)-Tsallis loss, it remains unclear what the optimal rate is. We conjecture that the optimal rate is \(O(d^{2-\alpha} \log T)\) with no additive \(d\) term. It would be interesting to prove a lower bound with this rate. Regarding our upper bound analysis, the additive \(d\) term comes from our bound on the regret of BTRL relative to \(p_{T+1}\) (3) and our bound on the smoothing term (5). Beyond the cases of Lipschitz losses and Tsallis losses, we hope that our new regret equality (1) may encounter further use. Unfortunately, in our analyses we were unable to fully leverage some negative terms appearing in this identity, but a more careful analysis could potentially sharpen existing regret bounds in our context, as well as others.

Acknowledgements↩︎

M. Fichtl’s research was supported from ANID Anillo ACT210005 grant under a postdoctoral position at Universidad de Chile. C. Guzmán’s research was partially supported by ANID FONDECYT 1251029 grant, ANID Anillo ACT210005 grant, and National Center for Artificial Intelligence CENIA FB210017, Basal ANID. N. Mehta was supported by the NSERC Discovery Grant RGPIN-2018- 03942. Much of this work happened while N. Mehta was visiting C. Guzmán at Pontificia Universidad Católica de Chile from February to April 2024.

9 Regret bound for Lipschitz losses when using our universal procedure↩︎

10 Proofs for 5.3 (Regret for scaled \(\boldsymbol{\alpha}\)-Tsallis losses)↩︎

10.1 Stability term↩︎

10.2 Proof for regret of BTRL relative to \(\boldsymbol{p_{T+1}}\)↩︎

10.3 Smoothing term↩︎

11 Proofs for Calibeating (6)↩︎

References↩︎

---

1. Independent researcher, mfichtl@gmail.com↩︎

2. Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Católica de Chile, crguzmanp@uc.cl↩︎

3. Department of Computer Science, University of Victoria, nmehta@uvic.ca↩︎

4. In a concurrent work, [2] independently made this same observation; for more discussion, see the end of 3.↩︎

5. Throughout the paper, we use the same notation for the unscaled and scaled versions; the text always clarifies which version is meant.↩︎

6. The main reason we include \(+\infty\) in the range is because of log loss.↩︎

7. See equation (10) of [19]; note that \(d(\cdot, \cdot)\) is a Bregman divergence but with the order of the arguments reversed, and \(S(\cdot, \cdot)\) is a loss.↩︎

8. However, for bounded, proper losses, they consider a prior U-calibration algorithm of [7].↩︎

9. Similar to original paper of [1], the new paper of [28] also gives results for multi-calibeating and obtaining a calibeating predictor that itself cannot be calibeaten; these results are no doubt interesting but out of scope for our comparison.↩︎

10. Compactness of the simplex implies these losses are also bounded.↩︎

11. 6 considers the more general setting in which each bin can be associated with multiple forecasts.↩︎

12. [8] also consider the case of \(\alpha < 1\), for which the definition has a sign flip, but we do not consider this regime here.↩︎

13. [7] scale the loss by a constant \(\tilde{c}_K\) (they use \(K\) for the dimension) to fit the loss range into \([-1, 1]\). It is easy to see that choosing a scaling constant of \(1/2\) suffices, regardless of the choice of \(\alpha \in [1, 2]\), and so we can ignore their term \(\tilde{c}_K\) when using big-O notation.↩︎

14. Due to our use of regularization, it is fine if \(1\) is excluded.↩︎

15. For more background, the interested reader is directed to the works of [32] and [4].↩︎

16. Note that we could conclude this same inequality by applying 4; indeed, that result gives a better inequality from the facts that \(\ell(p_{1/d}, \mathbf{e}_1) = \ell(\mathbf{e}_1, \mathbf{e}_1) = 0\) and \(\ell(p_{T+1}, \mathbf{e}_1) \geq 0\) plus the fact that the last two summation terms of 4 are nonpositive. ↩︎