1 Introduction↩︎

Our play opens with what appears to be a two-protagonist drama. They make their separate entrances across two acts, each insisting on a solo turn in the spotlight. In the final act they meet, only to realize that they are, in fact, a mirror image of each other.

1.0.0.1 Act I: Self-normalized martingales

In an introductory course on Probability, we learn that the sum of normal random variables is also normal, and, in particular, \(\frac{\sum_{i=1}^T X_i}{\sqrt{\sum_{i=1}^T \sigma_i^2}} \sim \mathsf{N}{\left( 0,1 \right)}\) where \(X_i\sim \mathsf{N}{\left( 0, \sigma_i^2 \right)}\) are independent normal random variables and \(\sigma_i\) are constants. If one replaces the denominator by the random realizations of \(X_i\), then the distribution of \(\frac{\sum_{i=1}^T X_i}{\sqrt{\sum_{i=1}^T X_i^2}}\) is no longer normal, yet its tails are similar to those of the normal distribution. In particular, an application of Hoeffding’s inequality (via symmetrization) shows that \[\mathbb{P}\left(\frac{\sum_{i=1}^T X_i}{\sqrt{\sum_{i=1}^T X_i^2}} > u\right) \leq \exp\left(-\frac{u^2}{2}\right)\] for any symmetric independent random variables \(X_i\), remarkably under no further assumptions on their distributions (see e.g., [1]). To bring out the symmetry requirement, we may instead write the above inequality as \[\begin{align} \mathbb{P}\left(\frac{\sum_{i=1}^T \varepsilon_i X_i}{\sqrt{\sum_{i=1}^T X_i^2}} > u\right) \leq \exp\left(-\frac{u^2}{2}\right), \label{eq:hoeffding-selfnorm} \end{align}\tag{1}\] where \(\varepsilon_i\) are i.i.d. Rademacher random variables, and \(X_i\) are independent with no further assumption on their distributions. Such inequalities for self-normalized sums are very attractive, both due to the lack of assumptions and due to their natural scale invariance.

It is then reasonable to ask whether inequalities similar to 1 hold for martingales. More precisely, suppose for simplicity that \(X_i\) are deterministic functions of \(\varepsilon_1,\ldots,\varepsilon_{i-1}\), i.e. measurable with respect to the dyadic filtration. Clearly, the sum \(\sum_{i=1}^T \varepsilon_i X_i\) is a martingale. Does the inequality 1 also hold for this martingale without assumptions on \(X_i\)’s?

Perhaps surprisingly, the answer is no. Even more interestingly, this answer is related to what is referred to as “doubly uniform regret” in online learning. But we are getting ahead of ourselves.

For simplicity of exposition, let us consider the first moment of the ratio, rather than the tail bound. The following inequality can be found in the classical book of [2]: \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\left[S_T/V_T^{1/2}\right] \leq C+ c\mathop{\mathrm{\mathbb{E}}}\brk*{0\vee\log \log (V_T^{1/2}\vee V_T^{-1/2})}, \label{eq:depena-selfnorm} \end{align}\tag{2}\] where, henceforth, we abbreviate \(S_T=\sum_{i=1}^T \varepsilon_i X_i\) and \(V_T=\sum_{i=1}^T X_i^2\), and \(C,c>0\) are constants. In the multi-dimensional setting, described below, the upper bound also involves the logarithm of the condition number of the matrix \(V_T\) (see additionally [3] and references therein).

The inequality 2 lacks the scale-invariance property that we desire: the left-hand side does not change when multiplying all \(X_i\)’s by a constant, yet the right-hand side does. This lack of scale-invariance is present in many results in the literature on self-normalized martingales, and it stems from the pseudo-maximization (or the method of mixtures) technique pioneered by [4] and used extensively by [2], [5]. The method aims to place a non-trivial mass on a parameter that can only be known after observing the scale of the realization.

One approach to remove scale-dependence in the upper bound on the self-normalized martingale is to change the denominator. This can be achieved by augmenting \(V_T\) with a regularization term. For instance, [5] establishes \[\begin{align} \mathbb{P}\left(\frac{S_T}{(V_T+\mathop{\mathrm{\mathbb{E}}}V_T)^{1/2}} > u\right) \leq \sqrt{2}\exp\left(-\frac{u^2}{4}\right). \label{eq:selfnorm-by-mixture} \end{align}\tag{3}\] The expected value \(\mathop{\mathrm{\mathbb{E}}}V_T\) can be viewed as fixing the scale of the problem, yet its presence in the denominator is not desirable. Another approach is to augment \(V_T\) with a constant, making both the ratio and the ensuing upper bound scale-dependent.

In particular, the addition of a regularizing constant to \(V_T\) has been employed in the multi-dimensional setting (that is, \(X_i=X_i(\varepsilon_1,\ldots,\varepsilon_{i-1})\) are taking values in \(\mathbb{R}^d\) and \(V_T=\sum_{i=1}^T X_i X_i^\top\) is the sample covariance) by [2] and [6] to establish tail bounds of the form \[\begin{align} \label{eq:self-norm-with-Gamma} S_T^\top (V_T+\Gamma)^{-1}S_T \lesssim \log \left(\frac{\det(V_T+\Gamma)}{\det(\Gamma)}\right)+\log(1/\delta) \end{align}\tag{4}\] with probability at least \(1-\delta\), for some deterministic positive definite matrix \(\Gamma\). Once again, both sides are not scale-invariant, limiting the applicability of the bound when the scale is unknown.

Before continuing our discussion, we mention that the analysis of self-normalized martingales plays a central role in bandits and reinforcement learning: it underlies confidence ellipsoids for online least-squares estimators (e.g., [6], [7]) and the resulting online-to-confidence set conversions (see [8]–[10] and the textbook [11] for bibliographic pointers), identification in Linear Time-Invariant systems [12], [13], and beyond. More broadly, there is renewed interest in formulations and in weakening tail assumptions beyond the classical conditionally sub-Gaussian setting (e.g., [3], [14]–[17]).

1.0.0.2 Act II: Doubly uniform regret

One of the first online prediction methods is the celebrated Vovk-Azoury-Warmuth (VAW) estimator, initially proposed by [18] and later refined by [19], [20] (see also [21]). First, we recall that in online supervised learning with squared loss, on each round \(t\in[T]\), the forecaster observes \(x_t\in\mathbb{R}^d\), selects a prediction \(\widehat{y}_t\in\mathbb{R}\) and observes \(y_t\in[-1,1]\). The VAW estimator, defined later in the text, is essentially a regularized least squares estimator with a regularization parameter \(\lambda>0\), and it achieves the following regret bound: for any \(\theta\in\mathbb{R}^d\), \[\begin{align} \label{eq:vaw-regret} \sum_{t=1}^{T} (\widehat{y}_{t}-y_{t})^2- \sum_{t=1}^{T} (\tri{\theta, x_{t}}-y_{t})^2 \leq \lambda\nrm{\theta}^2 + d\log\prn*{1+\frac{T\max_{t} \nrm{x_{t}}^2}{\lambda}}. \end{align}\tag{5}\] Notably, the bound is non-uniform in two ways: it depends both on the norm of the comparator vector \(\theta\) and the scale of the covariates. [22] raised the question of whether one can obtain a regret bound that is uniform over all \(\theta\), as the existing lower bounds do not show this necessity (see, e.g., [23]). This led the authors of [23] to further ask whether regret bounds that are doubly uniform—with respect to the norm of the target parameter and the covariates—are possible in online linear regression.

So far, this double uniformity is only known in the so-called transductive online setup, where all design vectors are arbitrary but known in advance so that the predictor can use them [22]–[24], and, roughly speaking, establish the scale of the prediction problem. This double uniformity also appears in the statistical (i.i.d.) setup, where variants of non-linear predictors allow one to bypass the dependence on both the distribution of the design and the norm of the parameter [25], [26]. More generally, in the context of GLMs there is recent interest in analyzing unbounded parameter spaces, for example in classification with logistic regression, where large parameter norms are very natural and relate to (almost) linearly separable samples. In the transductive setup and in the context of online logistic regression, see [27], while [24] focuses on regression with square, hinge and logarithmic losses.

1.0.0.3 Act III: On the equivalence of martingale bounds and regret inequalities

Denote the regret of the learner in the online prediction problem with arbitrary \(\theta\in\mathbb{R}^d\) as \[\begin{align} \label{eq:reg95def} \mathbf{Reg}(T)\vcentcolon=\sum_{t=1}^{T}(\widehat{y}_{t}-y_{t})^2-\inf_{\theta\in\mathbb{R}^d} \sum_{t=1}^{T}(\tri{\theta, x_{t}}-y_{t})^2. \end{align}\tag{6}\] Suppose the forecaster attempts to predict the following sequence. Covariates form a predictable process \(x_t=X_t(\varepsilon_1,\ldots,\varepsilon_{t-1})\), as earlier in the text, and the outcome variable \(y_t=\varepsilon_t\) is an independent Rademacher random variable. It is clear that in this setting, the best strategy for the forecaster is to predict \(\widehat{y}_t=0\) for all \(t\). Then, the expected regret of the forecaster is given by \[\begin{align} \mathop{\mathrm{\mathbb{E}}}_{\varepsilon}\brk*{\sum_{t=1}^{T}y_t^2-\inf_{\theta\in\mathbb{R}^d} \sum_{t=1}^{T}(\tri{\theta, x_{t}}-y_{t})^2 }&=\mathop{\mathrm{\mathbb{E}}}_{\varepsilon}\sup_{\theta\in\mathbb{R}^d} 2\tri{\theta, \sum_{t=1}^{T}\varepsilon_t X_t} - \tri{\theta, \sum_{t=1}^{T}X_t X_t^\top \theta} \\ &= \mathop{\mathrm{\mathbb{E}}}_{\varepsilon}\brk*{S_T^\top (V_T)^{\dagger} S_T}. \end{align}\] which is precisely the expected value of the self-normalized process that appeared in Act I. Furthermore, [28] proved a converse statement (for a more general setting of regression with any class of functions): no matter what the sequence of \(\{(x_t,y_t)\}_{t\in[T]}\) is, even if chosen adaptively by Nature, there exists a prediction strategy that achieves a regret bound that is, up to a multiplicative constant, in the above self-normalized form for the worst-case martingale (see below for more details). Thus, upper bounds on 6 for all sequences imply upper bounds for the expected self-normalized ratio, and vice versa.

The connection between probabilistic martingale inequalities and regret bounds has been a focus of extensive research, including [29]–[35], and, in particular, certain equivalence between these two seemingly unrelated fields was studied in [31], [32].

1.0.0.4 Finale

Due to the two-sided equivalence between minimax regret bounds for unbounded comparators \(\theta\in\mathbb{R}^d\) and expected value of self-normalized martingales, we can establish lower/upper bounds for one by studying the other, whichever is more convenient. In particular, the issues discussed in Act I regarding the knowledge of the scale of the problem are precisely the issues discussed in Act II regarding the knowledge of the norm of the comparator vector \(\theta\) and the scale of the covariates. In particular, later in the paper, we describe the exact link between self-normalized bounds of the form 4 and the Vovk-Azoury-Warmuth forecaster.

In particular, our contributions are:

• We establish a sharp separation between the cases \(d=1\) and \(d>1\). When \(d=1\), we prove a fully scale-invariant bound of order \(O(\log T)\) for self-normalized martingales without any assumption on the covariates. Via the regret–martingale connection developed in [31], this implies a doubly-uniform \(O(\log T)\) regret guarantee for online linear regression, thereby resolving the question of [23] in dimension one. Moreover, we provide an explicit algorithm achieving this doubly-uniform \(O(\log T)\) regret.

• In contrast, when \(d>1\) we show that no nontrivial scale-invariant control of self-normalized vector martingales is possible in full generality, and consequently sublinear doubly-uniform regret bounds for online linear regression cannot hold. This completes our answer to the question of [23].

• On the positive side, still in the regime \(d>1\), we introduce a smoothness condition on the covariate process, requiring that each conditional law admits a bounded Radon–Nikodym derivative with respect to a fixed base measure. Under this assumption we obtain sublinear regret without assuming bounded covariates. Moreover, our bounds avoid the usual matrix regularization penalties (e.g., the log-determinant term in 4 ), yielding what appears to be a first natural example of a scale-invariant self-normalized martingale bound in a genuinely non-i.i.d.setting.

2 Preliminaries↩︎

In the previous section, we motivated the study of dyadic self-normalized martingales of the form \(\varepsilon_t X_t\), where \((\varepsilon_t)_{t\ge1}\) are i.i.d.Rademacher signs and each \(X_t\) is \(\sigma(\varepsilon_1,\ldots,\varepsilon_{t-1})\)-measurable. In particular, if \((X_t)\) is deterministic (or more generally independent of \((\varepsilon_t)\)), then conditioning on \((X_t)_{t\le T}\) and applying Hoeffding’s inequality yields the scale-invariant tail bound 1 for the ratio \(\sum_{t=1}^T \varepsilon_t X_t/\sqrt{\sum_{t=1}^T X_t^2}\). Let us now present the more general filtered definition that is standard in the online regression and bandit literature (e.g., [6], [16]), and that will serve as our main probabilistic object. Throughout this probabilistic discussion we use capitals \((X_t,Y_t)\); later, when we switch to the online learning protocol, we will revert to the conventional lowercase notation \((x_t,y_t)\) and use a separate notion of game history that also records predictions.

Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space equipped with a filtration \((\mathcal{G}_t)_{t\ge0}\). We assume that \(X_t\) is predictable and that \((Y_t)_{t=1}^T\) is a real-valued martingale difference sequence with respect to \((\mathcal{G}_t)\): \[X_t\in\mathbb{R}^d ~\text{is }~ \mathcal{G}_{t-1}~\text{-measurable and}\qquad \mathop{\mathrm{\mathbb{E}}}\left[Y_t \,\middle| \mathcal{G}_{t-1}\right]=0 \qquad\text{for all } t\in[T].\label{eq:def95martingale95XY}\tag{7}\] Depending on the application, one may further assume boundedness \(|Y_t|\le 1\) almost surely or a conditional sub-Gaussian condition. Define the cumulative vector and the Gram matrix \[S_t \vcentcolon=\sum_{i=1}^t Y_i X_i \in \mathbb{R}^d, \qquad V_t \vcentcolon=\sum_{i=1}^t X_i X_i^\top \in \mathbb{R}^{d\times d}.\] The canonical scale-free quantity is the self-normalized process \[R_t \vcentcolon=\|S_t\|_{V_t^\dagger}^2 = S_t^\top V_t^\dagger S_t,\] where \(V_t^\dagger\) denotes the Moore–Penrose pseudoinverse. Controlling \(R_t\) (in expectation or with high probability) is a central theme of the self-normalization literature [2], [36], [37] and, in the online learning context, it is the quantity that underlies confidence ellipsoids and regret bounds in least squares and linear bandits [6], [16].

The question we pursue is whether martingale analogues of 1 can hold for \(R_t\) under minimal assumptions on the predictable covariates \((X_t)\). Since we aim for a uniform upper bound that holds for all martingales of the form 7 , we define \[\label{eq:cR95d} \mathcal{R}_d(T)= \sup_{P_{X,Y}} \mathop{\mathrm{\mathbb{E}}}_{P_{X,Y}}\brk*{\nrm{S_T}_{V_T^\dagger}^2},\tag{8}\] where the supremum ranges over all laws \(P_{X,Y}\) of dimension \(d\) satisfying 7 and such that \(|Y_t|\le 1\) almost surely for all \(t\in [T]\).

A dyadic martingale is a special case where \(Y_t=\varepsilon_t\) are i.i.d.Rademacher and \(X_t = X_t(\varepsilon_1,\ldots,\varepsilon_{t-1})\) is a deterministic function of the past signs. Such a process can be viewed as an \(\mathbb{R}^d\)-valued tree \(X\) of depth \(T\), or a sequence of mappings \(X_t\colon \{\pm1\}^{t-1}\to\mathbb{R}^d\). Let \[\mathcal{R}_d^{\mathrm{dyadic}}(T)\vcentcolon=\sup_X \mathop{\mathrm{\mathbb{E}}}_\varepsilon\brk*{R_T},\] where the supremum is over all trees \(X\) and expectation is over i.i.d.Rademacher \((\varepsilon_t)\).

In words, worst-case martingales—from the point of view of self-normalized ratios—are the dyadic martingales, up to a factor \(2\). Since each dyadic martingale is defined by \(2^T-1\) values (the number of nodes in the binary tree), for each such dyadic martingale we can consider its rescaled (by the maximum norm) variant \(X'\) with \(\|X'_t\|\leq 1\). Since the value of the self-normalized ratio does not change when scaled by a constant, we also have the following conclusion. Let \(\mathcal{R}_d^{\mathrm{bdd}}(T)\) denote the supremum over the processes of the form 7 with \(\|X_t\|\leq 1\) almost surely, and let \(\mathcal{R}_d^{\mathrm{bdd,dyadic}}(T)\) denote the corresponding supremum restricted to dyadic and bounded martingales.

In the following section, this result will imply that the difficulty in doubly-uniform regret bounds is a consequence of unbounded \(\theta\) rather than unbounded covariates. This is also reflected by our lower bounds, which hold for bounded covariates.

2.1 An online prediction game↩︎

We now use the standard online learning notation and write covariates, outcomes, and predictions as \((x_t,y_t,\widehat{y}_t)\). On each round \(t\in[T]\), the environment \(\mathsf{Env}\) reveals a covariate vector \(x_{t}\in\mathbb{R}^d\), the learner \(\mathsf{Alg}\) outputs a prediction \(\widehat{y}_{t}\in\mathbb{R}\), and then \(\mathsf{Env}\) reveals an outcome \(y_{t}\in[-1,1]\). Both \(\mathsf{Env}\) and \(\mathsf{Alg}\) may be adaptive. We denote the history prior to round \(t\) by \[\mathcal{H}^{t-1}\vcentcolon=\sigma\Big(\{(x_{s},\widehat{y}_{s},y_{s})\}_{s<t}\Big).\]

Given a comparator set \(\Theta\subseteq\mathbb{R}^d\), the square-loss regret is \[\label{eq:regret-theta} \mathbf{Reg}_\Theta(T) \vcentcolon= \sum_{t=1}^{T}(\widehat{y}_{t}-y_{t})^2 -\inf_{\theta\in\Theta}\sum_{t=1}^{T}\bigl(\tri{\theta,x_{t}}-y_{t}\bigr)^2.\tag{9}\] Since our focus is on \(\Theta=\mathbb{R}^d\), we abbreviate \(\mathbf{Reg}(T)\vcentcolon=\mathbf{Reg}_{\mathbb{R}^d}(T)\).

A convenient way to relate regret to self-normalization is to consider a stochastic environment with conditionally unbiased outcomes. Fix any algorithm \(\mathsf{Alg}\) and a sequential law \(P_{x,y}\) over \((x_{1},y_{1},\ldots,x_{T},y_{T})\) such that, when the environment is generated from \(P_{x,y}\) independently of the predictions of \(\mathsf{Alg}\), the outcomes satisfy \[\label{eq:online-unbiased} \mathop{\mathrm{\mathbb{E}}}\left[y_{t}\,\middle|\,x_{1},y_{1},\ldots,x_{t-1},y_{t-1},x_{t}\right]=0 \qquad\text{for all } t\in[T].\tag{10}\] Let \(\mathsf{Env}\) be the environment that samples \((x_{1},y_{1},\ldots,x_{T},y_{T})\sim P_{x,y}\) and reveals it round by round. Then \[\begin{align} \mathop{\mathrm{\mathbb{E}}}^{{\scriptscriptstyle\mathsf{Env},\mathsf{Alg}}}\brk*{\sum_{t=1}^{T}(\widehat{y}_{t}-y_{t})^2} &= \mathop{\mathrm{\mathbb{E}}}^{{\scriptscriptstyle\mathsf{Env},\mathsf{Alg}}}\brk*{\sum_{t=1}^{T}\bigl(\widehat{y}_{t}^2-2\widehat{y}_{t}y_{t}+y_{t}^2\bigr)} \nonumber\\ &= \mathop{\mathrm{\mathbb{E}}}^{{\scriptscriptstyle\mathsf{Env},\mathsf{Alg}}}\brk*{\sum_{t=1}^{T}\bigl(\widehat{y}_{t}^2+y_{t}^2\bigr)} \ge \mathop{\mathrm{\mathbb{E}}}_{P_{x,y}}\brk*{\sum_{t=1}^{T}y_{t}^2}, \label{eq:loss-lb-y2} \end{align}\tag{11}\] where the middle equality uses 10 (hence \(\mathop{\mathrm{\mathbb{E}}}[\widehat{y}_{t}y_{t}]=0\)). Next, define \(S_T \vcentcolon=\sum_{t=1}^{T}y_{t}x_{t}\in\mathbb{R}^d\) and \(V_T \vcentcolon=\sum_{t=1}^{T}x_{t}x_{t}^{{\scriptscriptstyle\top}}\in\mathbb{R}^{d\times d}\). A direct completion of squares gives the exact identity \[\begin{align} \sum_{t=1}^{T}y_{t}^2-\inf_{\theta\in\mathbb{R}^d}\sum_{t=1}^{T}\bigl(\tri{\theta,x_{t}}-y_{t}\bigr)^2 = \sup_{\theta\in\mathbb{R}^d}\Bigl\{2\tri{\theta,S_T}-\nrm{\theta}_{V_T}^2\Bigr\} = \nrm{S_T}_{V_T^\dagger}^2. \label{eq:selfnorm-identity-game} \end{align}\tag{12}\] Combining 11 with 12 yields \[\begin{align} \mathop{\mathrm{\mathbb{E}}}^{{\scriptscriptstyle\mathsf{Env},\mathsf{Alg}}}\brk*{\mathbf{Reg}(T)} \ge \mathop{\mathrm{\mathbb{E}}}_{P_{x,y}}\brk*{\nrm{S_T}_{V_T^\dagger}^2}. \label{eq:regret-lb-selfnorm} \end{align}\tag{13}\] This implies that for every algorithm \(\mathsf{Alg}\), \[\max_{\mathsf{Env}}\mathop{\mathrm{\mathbb{E}}}^{{\scriptscriptstyle\mathsf{Env},\mathsf{Alg}}}\brk*{\mathbf{Reg}(T)} \ge \mathcal{R}_d(T).\] Conversely, the work of [31] provides a minimax upper bound turning self-normalized control into regret guarantees (up to universal constants), yielding a two-sided link between self-normalization and optimal regret in online linear regression. We state here the upper bound of [28] for the linear function class:

We remark that the actual upper bound in the proof is smaller than \(\mathcal{R}_{d+1}(T)\); for our purposes, this is only important for \(d=1\), which we treat separately.

3 Self-normalized martingales and online prediction in the fully adversarial setting↩︎

In this section, we first discuss the one-dimensional case \(d=1\), and then the case \(d\ge 2\). Remarkably, both regret and the self-normalized martingale exhibit very different behavior in these two regimes.

3.1 Dimension one: logarithmic self-normalized martingale and doubly-uniform regret↩︎

In this section, we focus on the one-dimensional case \(d=1\). We show that (i) the dyadic self-normalized martingale admits \(O(\log T)\) control in expectation, and (ii) the minimax doubly-uniform regret in online linear regression is also \(\Theta(\log T)\). Taken together, these results settle the behavior of both objects of interest in dimension one.

We start from the probabilistic side by establishing a linear bound on the exponential moment of the one-dimensional dyadic self-normalized martingale.

Theorem 1 provides a homogeneous, scale-invariant control of the self-normalized martingale in dimension one. In particular, it improves upon the scale-sensitive behavior suggested by classical mixture-based bounds such as 2 : the right-hand side grows only logarithmically with \(T\) and requires no boundedness or moment assumptions on the predictable covariates \((X_t)\) beyond measurability with respect to the dyadic filtration.

In light of the regret–martingale connection discussed above, the logarithmic behavior in Theorem 1 suggests that \(\log T\) is the correct scale for doubly-uniform regret in one dimension. We make this precise by giving a matching upper bound via an explicit procedure.

Complementarily, the minimax lower bound of order \(\Omega(\log T)\) follows from [23] (adapted from [19]).

Together, Theorem 2 and Proposition [prop:lower-bound-1d] yield the claimed \(\Theta(\log T)\) characterization of doubly-uniform regret in dimension one, aligning with the logarithmic self-normalized control in Theorem 1.

3.2 Dimension two and higher: linear lower bounds↩︎

We now turn to \(d\ge 2\). In sharp contrast to the one-dimensional case, the self-normalized vector martingale can grow linearly in the worst case. Through 13 , this implies that doubly-uniform regret cannot be sublinear under a fully adversarial environment.

Note that since the ratio is homogeneous, the construction in the proof can be rescaled so that \(\|X_t\|\le 1\) deterministically.

4 Online prediction with smooth environment↩︎

Even though the worst-case lower bound looks grim, the picture brightens if the environment is forced to “add randomness”. We formalize this with a smoothness condition that caps how concentrated each \(x_t\) can be relative to a fixed base measure \(\mu\) [38].

This assumption limits how concentrated the conditional law of \(x_t\) can be; for instance, when \(\mu\) is non-atomic it rules out choosing \(x_t\) deterministically, as in the lower-bound construction of 3. The condition is trivially satisfied when \(\mathcal{X}\) is finite (with \(\mu=\mathrm{Unif}(\mathcal{X})\) and \(C_{\mathsf{cov}}\le |\mathcal{X}|\)). When \(\mathcal{X}\) is infinite, however, it can be a fairly strong assumption on the environment, and can make online prediction significantly easier.

To provide more intuition, [39] show that under 1, \(x_1,\ldots,x_T\) can be coupled with a subsequence of i.i.d.random vectors (8), echoing the “smoothed analysis” philosophy in algorithms.

4.1 The Vovk–Azoury–Warmuth (VAW) algorithm under the smoothness assumption↩︎

For upper bounds under 1, we use the Vovk–Azoury–Warmuth (VAW) predictor, a classic forecaster for online linear regression. The regularized version is well known, but since both the comparator and the covariates may be unbounded here, standard analyses that rely on a fixed regularizer do not account for smoothness. We therefore study the unregularized VAW (1) and tailor the analysis to the smooth setting.

We prove the following guarantee for VAW through an (almost) purely combinatorial argument, rather than the standard elliptical-potential analysis.

We briefly indicate how the proof goes. It is standard to reduce the regret analysis of VAW-type algorithms to upper bounding the sum \(\sum_{t=1}^{T}x_{t}^{{\scriptscriptstyle\top}}V_{t}^\dagger x_{t}\); in the usual analysis this leads to a dependence on the magnitudes of the \(x_t\)’s. In contrast, we use smoothed-analysis ideas. To control \(\sum_{t=1}^{T}x_{t}^{{\scriptscriptstyle\top}}V_{t}^\dagger x_{t}\), we consider the longest subsequence \(x_{t_1},\ldots,x_{t_k}\) such that \(\nrm{x_{t_j}}_{V_{t_j}^\dagger}^2\ge r\) for a fixed threshold \(r>0\), and then use the coupling result from 8 to reduce to an i.i.d.sequence. Compare this with the standard VAW bound 5 , where a regularization parameter \(\lambda\) is essential (one cannot take \(\lambda\to 0\) without making the bound trivial), and the resulting regret bound depends explicitly on \(\max_{t\le T}\|x_t\|\).

5 Bounding self-normalized martingales via regret analysis: high probability results↩︎

We are now back in the setup of self-normalized martingales, and we re-derive a self-normalized concentration inequality by combining (i) a deterministic regret bound for an online regression algorithm and (ii) a stochastic exponential supermartingale coming from the conditional sub-Gaussian noise assumption. Such a reduction is standard and is a key tool in [31].

Let \((\mathcal{F}_t)_{t\ge 0}\) be a filtration such that, for each round \(t\), the covariate \(X_t\) and the prediction \(\hat{y}_t\) are \(\mathcal{F}_{t-1}\)-measurable, and \(Y_t\) is then revealed. Assume that \((Y_t)_{t\ge 1}\) is a martingale difference sequence with conditionally sub-Gaussian increments: for some \(\sigma>0\), \[\label{eq:cond-subg-sec} \mathbb{E}\left[Y_t\mid \mathcal{F}_{t-1}\right]=0 \qquad\text{and}\qquad \mathbb{E}\left[\exp(\alpha Y_t)\mid \mathcal{F}_{t-1}\right]\le \exp\left(\frac{\alpha^2\sigma^2}{2}\right),\tag{14}\] for all \(\alpha \in \mathbb{R}\) and \(t \ge 1\). Fix a deterministic \(0\prec \Gamma\in\mathbb{R}^{d\times d}\) and define \(S_t \vcentcolon=\sum_{i=1}^t X_i Y_i\) and \(V_t \vcentcolon=\sum_{i=1}^t X_i X_i^\top\). As above, completion of squares yields \[\label{eq:selfnorm-identity-sec} \sum_{t=1}^T Y_t^2 -\inf_{\theta\in\mathbb{R}^d}\left\{\sum_{t=1}^T\bigl(\tri{\theta,X_t}-Y_t\bigr)^2+\theta^\top\Gamma\theta\right\} \;=\;\nrm{S_T}_{(V_T+\Gamma)^{-1}}^2,\tag{15}\] which equivalently, for any sequence of predictions \((\hat{y}_t)_{t=1}^T\), can be rewritten as \[\label{eq:regret-decomp-sec} \nrm{S_T}_{(V_T+\Gamma)^{-1}}^2 = \mathbf{Reg}_T(\hat{y}) +\sum_{t=1}^T\bigl(2\hat{y}_t Y_t-\hat{y}_t^2\bigr),\tag{16}\] where the last term is the one we will control stochastically using 14 . The next simple result shows that this term admits a sharp high-probability bound.

Finally, we combine the high-probability regret bound under smoothness with the generic reduction of 16 to obtain a self-normalized concentration inequality without any explicit bound on \(\|X_t\|\) and without introducing a positive definite regularization matrix \(\Gamma\) in the self-normalization.

Importantly, compared to the canonical bound [6], namely under the sub-Gaussian assumption 14 but without smoothness, for any positive definite \(\Gamma\), \[\nrm{S_T}_{(V_T + \Gamma)^\dagger}^2 \le \sigma^2\left( \log \left(\frac{\det(V_T+\Gamma)}{\det(\Gamma)}\right)+2\log(1/\delta)\right),\] the right-hand side of ?? has no explicit dependence on \(\max_t\|X_t\|\) and no regularization matrix \(\Gamma\) is needed in the self-normalized quantity. Moreover, the base measure \(\mu\) from Assumption 1 is only used for the analysis: even for the regret analysis of 4 the algorithm itself does not require knowing \(\mu\), and the regret bound is used purely as a tool to prove concentration.

6 Proofs from 2↩︎

6.1 Proof of Lemma 2↩︎

When the “centering” in [28] is incorporated into the \(X\)-process, the upper bound reads as \[\sup_{X} \mathop{\mathrm{\mathbb{E}}}\sup_{\theta\in\mathbb{R}^d} \sum_{t=1}^T 4\varepsilon_t \tri{(\theta,1), X_t} - \tri{(\theta,1), X_t}^2\] where \(X=(X_t)\) is an \(\mathbb{R}^{d+1}\)-valued tree with \(X_t[d+1]\in[-1,1]\). We over-bound by choosing a \((d+1)\)-dimensional \(\theta\) in the supremum.

7 Proofs from 3↩︎

7.1 Proof of 1↩︎

We note that \[S_{T+1}=S_T+\varepsilon_{T+1}X_{T+1}, \qquad V_{T+1}=V_T+X_{T+1}^2.\] Conditioning on \(\mathcal{F}_T\) and expanding, \[\begin{align} \mathbb{E}\!\left[\exp(cR_{T+1})\mid \mathcal{F}_T\right] &= \mathbb{E}\!\left[\exp\!\left(\frac{c(S_T+\varepsilon_{T+1}X_{T+1})^2}{V_T+X_{T+1}^2}\right)\Bigm|\mathcal{F}_T\right]\\ &= \exp\!\left(\frac{cS_T^2+cX_{T+1}^2}{V_T+X_{T+1}^2}\right)\, \mathbb{E}\!\left[\exp\!\left(\frac{2c\,\varepsilon_{T+1}S_TX_{T+1}}{V_T+X_{T+1}^2}\right)\Bigm|\mathcal{F}_T\right]. \end{align}\] Introduce \[u:=\frac{V_T}{V_T+X_{T+1}^2}\in[0,1], \qquad 1-u=\frac{X_{T+1}^2}{V_T+X_{T+1}^2}, \qquad \frac{S_T^2}{V_T+X_{T+1}^2}=u\frac{S_T^2}{V_T}=uR_T.\] Also define \[a := \frac{2c\,S_TX_{T+1}}{V_T+X_{T+1}^2}.\] By Hoeffding’s lemma for a Rademacher variable, \(\mathbb{E}[\exp(\varepsilon_{T+1}a)\mid \mathcal{F}_T]\le \exp(a^2/2)\), hence \[\mathbb{E}\!\left[\exp(cR_{T+1})\mid \mathcal{F}_T\right] \le \exp\!\left(cuR_T + c(1-u) + \frac{a^2}{2}\right).\] Next, \[\frac{a^2}{2} = \frac{1}{2}\cdot \frac{4c^2 S_T^2X_{T+1}^2}{(V_T+X_{T+1}^2)^2} = 2c^2\cdot \frac{S_T^2}{V_T}\cdot \frac{V_TX_{T+1}^2}{(V_T+X_{T+1}^2)^2} = 2c^2 R_T\,u(1-u).\] Therefore, \[\begin{align} \mathbb{E}\!\left[\exp(cR_{T+1})\mid \mathcal{F}_T\right] &\le \exp\!\left(cuR_T + c(1-u) + 2c^2R_T\,u(1-u)\right) \notag\\ &\leq \exp\!\left(cuR_T + c(1-u) + 2c^2R_T\,(1-u)\right). \notag \end{align}\] where the second inequality is because \(2c^2R_T(1-u)^2 \geq 0\). Now split into two cases.

pt Case 1: \(R_T\le \frac{1}{1-2c}\). Then we have \[\begin{align} \exp\!\left(cuR_T + c(1-u) + 2c^2R_T\,(1-u)\right) &= \exp\!\left(c + 2c^2R_T+ cuR_T -cu - 2c^2R_Tu\right)\\ &= \exp\!\left(c + 2c^2R_T+ cu( (1-2c)R_T-1)\right)\\ &\leq \exp\!\left(c + 2c^2R_T\right)\\ &\leq \exp\!\Bigl(\frac{c}{1-2c}\Bigr) = C_0, \end{align}\] where both inequalities are due to the condition of case 1.

pt Case 2: \(R_T> \frac{1}{1-2c}\). Then \(c(1-u)(1-(1-2c)R_T)\leq 0\). Reorgnizing the terms, we have \(cuR_T + c(1-u) + 2c^2R_T(1-u)\leq cR_T\). This implies \[\begin{align} \exp\!\left(cuR_T + c(1-u) + 2c^2R_T\,(1-u)\right) \leq \exp\!\left(cR_T\right). \end{align}\]

Combining both cases yields the one-step inequality \[\mathbb{E}\!\left[\exp(cR_{T+1})\mid \mathcal{F}_T\right] \le \exp(cR_T)+C_0.\] Taking expectations and iterating gives \[\mathbb{E}\exp(cR_T) \le \mathbb{E}\exp(cR_1) + (T-1)C_0 \le TC_0,\] since \(\exp(cR_1) = \exp(c) \le \exp(c/(1-2c))=C_0\). Finally, by Jensen’s inequality, \(c\,\mathbb{E}[R_T]\le \log \mathbb{E}\exp(cR_T)\le \log(TC_0)\), proving the stated bound.

7.2 ↩︎

Let \(n=\floor{\frac{1}{2}\log T}\) and \(K=\floor{T/n}\). We set \(M=\frac{2T}{n}\).

Consider the following sequence dyadic martingale difference sequence. Set \(X_1=1\).

• For \(t=jn+1\), we set \(X_t=M\cdot X_{(j-1)n+1}\) if there exists \(\ell\in[(j-1)n+1,jn]\) such that \(\varepsilon_{\ell}=-1\). Otherwise we set \(X_{t}=0\).

• For \(t\in(jn+1,(j+1)n]\), we set \(X_t=X_{jn+1}\).

Let \(i\) be the first index such that \(\varepsilon_\ell=1\forall \ell\in[in+1,(i+1)n]\), and if no such index exists we set \(i=K+1\). Then, if \(i\leq K\), we can bound \(\abs{S_T-M^in}\leq M^{i-1}T\) and \(V_T\leq \frac{nM^{2i}}{1-M^{-1}}\). Therefore \(\frac{S_T^2}{V_T}\geq \frac{(n-T/M)^2}{2n}\geq \frac{n}{8}\). On the other hand, we have \[\begin{align} \mathbb{P}(i=K+1)\leq&~ \mathbb{P}(\forall 0\leq j<K, \exists \ell\in[jn+1,(j+1)n], \varepsilon_\ell\neq 1 ) \\ \leq&~ (1-2^{-n})^K\leq e^{-2^{-n}K}\leq 1-c_0, \end{align}\] where \(c_0>0\) is an absolute constant. This implies \(\mathop{\mathrm{\mathbb{E}}}[S_T^2/V_T]\geq \frac{c_0}{8}n=\Omega(\log T)\).

7.3 ↩︎

The above algorithm utilizes a sequence of subroutines \(\crl{\mathsf{Alg}_k}_{k\in\mathbb{Z}}\) and additionaly the trivial algorithm \(\mathsf{Alg}_{\infty}\) that always predicts \(\widehat{y}_{t}=0\). We can then decompose the regret of 2 to the regret of each subroutine \(\mathsf{Alg}_k\).

7.3.0.1 Subroutines

It remains to construct subroutines satisfying 2. We first recall that Vovk-Azoury-Warmuth forecaster has the following guarantee.

However, the forecaster ?? may not achieve good \(\beta(n)\) bound. Therefore, we hedge it against the \(0\) forecaster.

To summarize, we have the following corollary.

In particular, we can choose \(\beta=\frac{1}{T}\) and \(M=T^2\), and by 4, 2 can be suitably instantiated such that it achieves \[\begin{align} \mathbf{Reg}\leq O(\log T). \end{align}\] As a remark, the dependence \(\log(1/\beta)\) is crucial for this regret bound, and it can be regarded as the “price of super-efficiency” against \(0\).

7.4 ↩︎

The martingale is constructed as follows. Let \(\varepsilon_1,\ldots,\) be an i.i.d. sequence of Rademacher random variables, and we will define \(x_t=X_t(\varepsilon_1,\ldots,\varepsilon_{t-1})\) below. Let \(S_t=\sum_{i=1}^t \varepsilon_i x_i\) and \(V_{t}=\sum_{i=1}^t x_i x_i^\top\). Consider \(\widetilde{V}_{t}=V_{t}+I\succ V_{t}\). Observe that under our construction, \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\brk*{ \nrm{S_{t+1}}_{\widetilde{V}_{t+1}^{-1}}^2} =\mathop{\mathrm{\mathbb{E}}}\brk*{ \nrm{S_{t}}_{\widetilde{V}_{t+1}^{-1}}^2+\nrm{x_{t+1}}_{\widetilde{V}_{t+1}^{-1}}^2 }. \end{align}\] Using \[\begin{align} \widetilde{V}_{t+1}^{-1}=\widetilde{V}_{t}^{-1}-\frac{\widetilde{V}_{t}^{-1}x_{t+1}x_{t+1}^\top \widetilde{V}_{t}^{-1}}{1+\nrm{x_{t+1}}_{\widetilde{V}_{t}^{-1}}^2}, \end{align}\] we have \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\brk*{ \nrm{S_{t+1}}_{\widetilde{V}_{t+1}^{-1}}^2} =\mathop{\mathrm{\mathbb{E}}}\brk*{ \nrm{S_{t}}_{\widetilde{V}_{t}^{-1}}^2+\frac{\nrm{x_{t+1}}_{\widetilde{V}_{t}^{-1}}^2-\tri{x_{t+1}, \widetilde{V}_{t}^{-1}S_{t}}^2}{1+\nrm{x_{t+1}}_{\widetilde{V}_{t}^{-1}}^2} }. \end{align}\]

We define \(x_{t}\) recursively: \(x_{1}\) is an arbitrarily fixed vector with norm \(r>0\), and for \(t\geq 1\), \[\begin{align} &~ x_{t+1}=r\widetilde{V}_{t}^{1/2} e_{t}, \qquad \text{where e_{t} is a unit vector such that } \tri{e_{t}, \widetilde{V}_{t}^{-1/2} S_{t}}=0. \end{align}\] Then, it holds that \[\begin{align} \mathop{\mathrm{\mathbb{E}}}\brk*{ \nrm{S_{t+1}}_{\widetilde{V}_{t+1}^{-1}}^2 } =\mathop{\mathrm{\mathbb{E}}}\brk*{ \nrm{S_{t}}_{\widetilde{V}_{t}^{-1}}^2+\frac{\nrm{x_{t+1}}_{\widetilde{V}_{t}^{-1}}^2}{1+\nrm{x_{t+1}}_{\widetilde{V}_{t}^{-1}}^2} } =\mathop{\mathrm{\mathbb{E}}}\brk*{ \nrm{S_{t}}_{\widetilde{V}_{t}^{-1}}^2 } + \frac{r^2}{r^2+1}. \end{align}\] Hence, since \(S_{T}\in \mathrm{Range}(V_{T})\), it is clear that \(\mathop{\mathrm{\mathbb{E}}}[\nrm{S_{T}}_{V_{T}^{\dagger}}^2] \geq \mathop{\mathrm{\mathbb{E}}}[\nrm{S_{T}}_{{\widetilde{V}_{T}^{-1}}}^2]=\frac{Tr^2}{r^2+1}\), and the proof is then completed by choosing \(r=\frac{1}{\varepsilon}\).

8 Proofs from 4↩︎

8.1 Proof of Lemma 3↩︎

Fix \(t\ge 1\). Since \(\hat{y}_t\) is \(\mathcal{F}_{t-1}\)-measurable, using 14 with \(\alpha=\hat{y}_t/\sigma^2\) gives \[\begin{align} \mathbb{E}\left[\exp\left(\frac{1}{2\sigma^2}(2\hat{y}_t y_t-\hat{y}_t^2)\right)\,\middle|\,\mathcal{F}_{t-1}\right] &= \exp\left(-\frac{\hat{y}_t^2}{2\sigma^2}\right)\, \mathbb{E}\left[\exp\left(\frac{\hat{y}_t}{\sigma^2}y_t\right)\,\middle|\,\mathcal{F}_{t-1}\right]\\ &\le \exp\left(-\frac{\hat{y}_t^2}{2\sigma^2}\right)\, \exp\left(\frac{\hat{y}_t^2}{2\sigma^2}\right) =1. \end{align}\] Multiplying by \(M_{t-1}\) and taking conditional expectations yields \(\mathbb{E}[M_t\mid \mathcal{F}_{t-1}]\le M_{t-1}\), so \((M_t)\) is a nonnegative supermartingale and hence \(\mathbb{E}[M_t]\le \mathbb{E}[M_0]=1\). Finally, the proof follows from Ville’s inequality for nonnegative supermartingales.

We will make use of the following upper bound of VAW.

To provide a upper bound for VAW, it remains to upper bound the quantity \(\sum_{t=1}^{T}x_{t}^{{\scriptscriptstyle\top}}V_{t}^\dagger x_{t}\). This is nontrivial because the matrix \(V_{t}\) can be ill-conditioned, and (as we have shown in 3.2) this sum can be \(\Omega(T)\) without smoothness. In the following, we bound this quantity by a “combinatorial dimension” of the sequence \(x\), and then apply the coupling trick and the backward analysis technique.

8.1.0.1 Step 1: Connect to combinatorial quantities of the sequence

To proceed, we introduce the notion of “bad” subsequence. For any sequence \(z=(z_{1},\cdots,z_{k})\), we define \(V(z)\vcentcolon=\sum_{i\leq k}z_{i}z_{i}^{{\scriptscriptstyle\top}}\). We call a sequence \(z=(z_{1},\cdots,z_{k})\) \(r\)-bad if for any \(t\in[k]\), \(\nrm{z_{t}}_{V(z_{1:t})^\dagger}^2\geq r\). We define \(N(r;z)\) to be the length of the longest \(r\)-bad subsequence of \(z\).

In the following, we bound the sum \(\sum_{t=1}^{T}x_{t}^{{\scriptscriptstyle\top}}V_{t}^\dagger x_{t}\) by \(N(r;x)\) for \(r\in\crl{2^{-1},2^{-2},\cdots}\).

8.1.0.2 Step 2: Coupling smooth sequence to a i.i.d sequence

We invoke the following coupling lemma for smooth sequence [39]. The idea of this lemma is quite simple: Any smooth sequence can be generated by performing rejection sampling. We sketch the proof below.

Note that this lemma implies () \(N(r;x)\leq N(r;z)\), and it remains to control \(N(r;z)\) under the i.i.d sequence \(z\).

8.1.0.3 Step 3: Bad i.i.d sequence is rare

Finally, the problem is now reduced to bounding the probability that a i.i.d sequence \((z_1,\cdots,z_k)\) being \(r\)-bad, as we handle in the following proposition.

8.1.0.4 Finalizing the proof

Combining the results above, we can conclude that VAW achieves a sublinear regret.

8.2 Tightness of our analysis↩︎

We argue that in the worst-case, the sum \(\sum_{t=1}^{T}x_{t}^{{\scriptscriptstyle\top}}V_{t}^\dagger x_{t}=\Omega(\sqrt{C_{\mathsf{cov}}T})\) even when \(d=1\), demonstrating that our analysis is nearly tight.

8.3 Dyadic filtration is enough↩︎

9 Proofs from 5↩︎

9.1 Proof of 5↩︎

By 3 and 16 , with probability at least \(1-\delta/2\), \[\label{eq:selfnorm-smooth-step1} \nrm{S_T}_{V_T^\dagger}^2 \le \mathbf{Reg}_T(\hat{y}) + 2\sigma^2\log(2/\delta).\tag{17}\]

On the other hand, applying to the VAW predictor with confidence level \(\delta/2\) gives, with probability at least \(1-\delta/2\), \[\label{eq:selfnorm-smooth-step2} \mathbf{Reg}_T(\hat{y}) \lesssim \sigma^2\Bigl(\sqrt{d\,C_{\mathsf{cov}}\,T\,\log(2T/\delta)}+\log(2/\delta)\Bigr).\tag{18}\] By the union bound, with probability at least \(1-\delta\) both 17 and 18 hold.

References↩︎

---

1. Here we assume smoothness with respect to the partial history \(\mathcal{H}^x_{t-1}\). While it may be more natural to assume smoothness given the full history \(\mathcal{H}_{t-1}=\crl{(x_s,y_s,\widehat{y}_s)}_{s<t}\), requiring smoothness conditional on the partial history is weaker.↩︎