# Bayesian mixture autoregressive model with Student’s t innovations

Davide Ravagli
<EMAIL_ADDRESS>Georgi N. Boshnakov
<EMAIL_ADDRESS>
(Department of Mathematics, The University of Manchester
Oxford Road, Manchester M13 9PL, United Kingdom
)

###### Abstract

This paper introduces a fully Bayesian analysis of mixture autoregressive
models with Student t components. With the capacity of capturing the behaviour
in the tails of the distribution, the Student t MAR model provides a more
flexible modelling framework than its Gaussian counterpart, leading to fitted
models with fewer parameters and of easier interpretation. The degrees of
freedom are also treated as random variables, and hence are included in the
estimation process.

##  1 Introduction

Mixture autoregressive (MAR) models (Wong and Li, 2000) were introduced as a
flexible tool to model time series data which presents asymmetry,
multimodality and heteroskedasticity. For this reason, MAR models have proven
valid to deal with financial returns, which often present one or more of such
features.

In their paper, Wong and Li describe a MAR model with Gaussian innovations, in
which the condtitional distribution of each component in the mixture is
assumed to be Normal, using the EM-Algorithm Dempster et al. (1977) for
paramter estimation. Since this, several examples of Bayesian estimation for
MAR models with Gaussian innovations have been presented, see for instance
Sampietro (2006).

Wong et al. (2009) introduced the mixture autoregressive model with Student t
innovations, in which the mixture components are now assumed, conditionally on
the past history of the process, to follow a Student’s t distribution. The
reason behind this different hypothesis for the components is that the Student
t distribution, having heavier tails than the Normal distribution, would be
more suitable to model financial returns. In addition, it was argued by Wong
et al. (2009) that, because the tails of the distribution can be adjusted, a
higher level of flexibility is achieved compared to the Gaussian MAR model.

We present here a fully Bayesian approach to estimating paramters of a mixture
autoregressive model with Student t innovations. In particular, conditional to
the past history of the process, each mixture component is assumed to follow a
standardised Student t distribution. In this way, component variances do not
depend on the degrees of freedom, so that they can be estimated directly. The
proposed method is able to identify the best model to fit a time series, as
well as estimate parameter posterior distributions.

The degrees of freedom of each mixture component are treated as a parameter in
the model. In the Bayesian framework, Geweke (1993) proposes a suitable prior
distribution for such parameters in the case of a linear regression model with
Student t errors. However, it appeared that results are highly affected by the
choice of prior distribution, and therefore one must be careful incorporating
their prior belief or knowledge about the data. Geweke (1994) also used a
similar approach to time series data with the assumption of Student t
innovations.

In general, it is conventient for the Student t distribution to constrain the
degrees of freedom parameters to be larger than $2$, to ensure existence of
both first and second moments. Geweke (1993) and Geweke (1994), as well as
different apporches to the problem such as Fonseca et al. (2008a), do not seem
to take this into account in their analysis. For this reason, we propose a
prior distribution for the degrees of freedom that ensures existence of the
first and second moment.

The paper proceeds as follows: Section 2 reviews the mixture autoregressive
model with Student t innovations, its properties, the missing data
specification and the first and second order stationarity condition. Section 3
presents a fully Bayesian analysis of the MAR model with Student t
innovations, including model selection and estimation of parameter posterior
distributions. Section 4 shows a simulation study to assess the accuracy of
the proposed method, and finally Section 5 presents a real data analysis.

##  2 The mixture vector autoregressive model with Student t innovations

A process $\\{y_{t}\\}$ is said to follow a mixture autoregressive (MAR)
process with Student t innovations (Wong et al., 2009) if its conditional CDF
can be written as:

$F\left(y_{t}\mid\mathcal{F}_{t-1}\right)=\sum_{k=1}^{g}\pi_{k}F_{\nu_{k}}\left(\dfrac{y_{t}-\phi_{k0}-\displaystyle\sum_{i=1}^{p_{k}}\phi_{ki}y_{t-i}}{\sigma_{k}}\right)$
(1)

where:

  * •

$\mathcal{F}_{t}$ is the sigma-field generated by the process up to, and
including (t-1).

  * •

$g$ is the number of mixture components.

  * •

$\pi_{k}>0,k=1,\ldots,g$ are the mixing weights, specifying a discrete
probability distribution in $[1,g]$ such that $\sum_{k=1}^{g}\pi_{k}=1$.

  * •

$F_{\nu_{k}}(\cdot)$, $k=1,\ldots,g$ denotes the conditional CDF of a
standardised Student t distribution for component $k$ of the mixture, with
corresponding degrees of freedom $\nu_{k}$. Formally, we denote a standardised
t distribution with mean $\mu$, variance $\sigma^{2}$ and degrees of freedom
$\nu$ as $\mathcal{S}(\mu,\sigma^{2},\nu)$.

  * •

$\phi_{k}=\left(\phi_{k0},\phi_{k1},\phi_{kp_{k}}\right)$ is the vector of
autoregressive parameters for the $k^{th}$ mixture component, with $\phi_{k0}$
being shift parameter. $p_{k}$ is the autoregressive order, and we
$p=\max(p_{k})$ to be the largest autoregressive order in the model. A useful
convention is to set $\phi_{kj}=0$ for $p_{k}<j\leq p$.

  * •

$\sigma_{k}$, $k=1\ldots,g$ is the scale parameter, and we define
$\tau_{k}=1/\sigma_{k}^{2}$, the corresponding ”precision” parameter.

  * •

If the process starts at $t=1$, then (1) holds for $t>p$.

For the analysis, we exploit the so called integral representation of the
Student t distribution. If a random variable $X$ follows a Student t
distribution with mean $\mu$ and variance $\sigma^{2}$, and degrees of freedom
$\nu$, then the marginal pdf of $X$ can be written as:

$f_{X}(x)=\int_{0}^{\infty}f_{X\mid Z}\left(x\mid z\right)f_{Z}(z)dZ$ (2)

where $X\mid Z\sim N\left(\mu,\dfrac{\sigma^{2}}{z}\right)$ and $Z\sim
Ga\left(\dfrac{\nu}{2},\dfrac{\nu}{2}\right)$. Notice however that this setup
is valid for the non-standardised Student t distribution, for which the
variance is equal to $\sigma^{2}\dfrac{\nu}{\nu-2}$. Therefore, for the
standardised Student t it is necessary to adjust the distribution of $Z$ to a
$Ga\left(\dfrac{\nu}{2},\dfrac{\nu-2}{2}\right)$. With this adjustment, the
variance becomes equal to $\sigma^{2}$, so it does no longer depend on the
degrees of freedom. At the same time, the degrees of freedom play a part in
the shape of the distribution, including the tails.

Given (2) and the subsequent considerations, the pdf of the model can be
written as

$\begin{split}f\left(y_{t}\mid\mathcal{F}_{t-1}\right)&=\sum_{k=1}^{g}\pi_{k}\sqrt{\dfrac{\tau_{k}\xi_{t}}{2\pi}}\exp\Bigg{\\{}-\dfrac{\tau_{k}\xi_{t}}{2}\left(y_{t}-\phi_{k0}-\sum_{i=1}^{p+k}\phi_{ki}y_{t-i}\right)\Bigg{\\}}\\\
&\times\dfrac{\dfrac{\nu_{k}-2}{2}^{\nu_{k}/2}}{\Gamma\left(\dfrac{\nu_{k}}{2}\right)}\xi_{t}^{\nu_{k}/2-1}\exp\Bigg{\\{}-\dfrac{\nu_{k}-2}{2}\xi_{t}\Bigg{\\}}\end{split}$
(3)

where $\xi_{t}\sim Ga(\dfrac{\nu_{k}}{2},\dfrac{\nu_{k}-2}{2})$.

Wong et al. (2009) showed that conditional expectation, conditional variance
and autocorrelation functions are identical to the Gaussian MAR model.
Respectively:

$\begin{split}\operatorname*{E}\left[y_{t}\mid\mathcal{F}_{t-1}\right]&=\sum_{k=1}^{g}\pi_{k}\mu_{tk}\\\
\operatorname*{Var}\left(y_{t}\mid\mathcal{F}_{t-1}\right)&=\sum_{k=1}^{g}\pi_{k}\sigma_{k}^{2}+\sum_{k=1}^{g}\pi_{k}\mu_{tk}^{2}-\sum_{k=1}^{g}\left(\pi_{k}\mu_{tk}\right)^{2}\\\
\rho_{h}&=\sum_{k=1}^{g}\pi_{k}\sum_{i=1}^{p}\phi_{ki}\rho_{\lvert
h-i\rvert},\qquad h\geq 1\end{split}$ (4)

where $\mu_{tk}=\phi_{k0}+\sum_{i=1}^{p_{k}}\phi_{ki}y_{t-i}$ and $\rho_{h}$
is the autocorrelation at lag $h$.

###  2.1 Stability of the MAR model

A matrix is stable if and only if all of its eigenvalues have moduli smaller
than one (equivalently, lie inside the unit circle). Consider the companion
matrices

$A_{k}=\begin{bmatrix}&\phi_{k1}&\phi_{k2}&\dots&\phi_{k(p-1)}&\phi_{kp}\\\
&1&0&\dots&0&0\\\ &0&1&\dots&0&0\\\ &\vdots&\vdots&\ddots&\vdots&\vdots\\\
&0&0&\dots&1&0\\\ \end{bmatrix},\quad k=1,\ldots,g.$

We say that the MAR model is stable if and only if the matrix

$A=\displaystyle\sum_{k=1}^{g}\pi_{k}A_{k}\otimes A_{k}$

is stable ($\otimes$ is the Kronecker product). If a MAR model is stable, then
it can be used as a model for stationary time series. The stability condition
is sometimes called stationarity condition, as when this condition holds, the
model is guaranteed to be first and second order stationary (i.e. weakly
stationary).

If $g=1$, the MAR model reduces to an AR model and the above condition states
that the model is stable if and only if $A_{1}\otimes A_{1}$ is stable, which
is equivalent to the same requirement for $A_{1}$. For $g>1$, it is still true
that if all matrices $A_{1},\dots,A_{g}$, $k=1,\dots,g$, are stable, then $A$
is also stable. However, the inverse is no longer true, i.e. $A$ may be stable
even if one or more of the matrices $A_{k}$ are not stable.

What the above means is that the parameters of some of the components of a MAR
model may not correspond to stationary AR models. It is convenient to refer to
such components as “non-stationary”.

Partial autocorrelations are often used as parameters of autoregressive models
because they transform the stationarity region of the autoregressive
parameters to a hyper-cube with sides $(-1,1)$ (BARNDORFFNIELSEN1973408;
Sampietro, 2006). The above discussion shows that the partial autocorrelations
corresponding to the components of a MAR model cannot be used as parameters if
coverage of the entire stationary region of the MAR model is desired.

##  3 Bayesian analysis of the Student t MAR model

Given a time series $y_{1},\ldots,y_{n}$, the likelihood function for the
Student t MAR model using (3) is:

$\begin{split}L\left(\bm{\phi},\bm{\sigma},\bm{\pi}\mid\bm{y},\bm{\xi}\right)=\prod_{t=p+1}^{n}\sum_{k=1}^{g}&\pi_{k}\sqrt{\dfrac{\tau_{k}\xi_{t}}{2\pi}}\exp\Bigg{\\{}-\dfrac{\tau_{k}\xi_{t}}{2}\left(y_{t}-\phi_{k0}-\sum_{i=1}^{p+k}\phi_{ki}y_{t-i}\right)\Bigg{\\}}\\\
&\times\dfrac{\dfrac{\nu_{k}-2}{2}^{\nu_{k}/2}}{\Gamma\left(\dfrac{\nu_{k}}{2}\right)}\xi_{t}^{\nu_{k}/2-1}\exp\Bigg{\\{}-\dfrac{\nu_{k}-2}{2}\xi_{t}\Bigg{\\}}\end{split}$
(5)

The likelihood function is not very tractable and a standard approach is to
recur to a missing data formulation (Dempster et al., 1977). Let
$Z_{t}=(Z_{t1},\ldots,Z_{tg})$ be a latent allocation random variable, where
$Z_{t}$ is a g-dimensional vector with entry k equal to 1 if $y_{t}$ was
generated from the $k^{th}$ component of the mixture, and 0 otherwise. We
assume that the $Z_{t}$s are discrete random variables, independently drawn
from the discrete distribution:

$P(Z_{tk}=1\mid g,\bm{\pi})=\pi_{k}$

This setup, widely exploited in the literature of finite mixture models (see,
for instance Diebolt and Robert, 1994) allows to rewrite the likelihood
function in a much more tractable way as follows:

$\begin{split}L\left(\bm{\phi},\bm{\sigma},\bm{\pi}\mid\bm{y},\bm{\xi}\right)=\prod_{t=p+1}^{n}\sum_{k=1}^{g}&\Bigg{(}\pi_{k}\sqrt{\dfrac{\tau_{k}\xi_{t}}{2\pi}}\exp\Bigg{\\{}-\dfrac{\tau_{k}\xi_{t}}{2}\left(y_{t}-\phi_{k0}-\sum_{i=1}^{p+k}\phi_{ki}y_{t-i}\right)\Bigg{\\}}\\\
&\times\dfrac{\dfrac{\nu_{k}-2}{2}^{\nu_{k}/2}}{\Gamma\left(\dfrac{\nu_{k}}{2}\right)}\xi_{t}^{\nu_{k}/2-1}\exp\Bigg{\\{}-\dfrac{\nu_{k}-2}{2}\xi_{t}\Bigg{\\}}\Bigg{)}^{z_{tk}}\end{split}$
(6)

Notice that, because exactly one $z_{tk}=1$ at each time $t$, the augmented
likelihood is a product, and therefore easier to handle.

In practice, both the $Z_{t}$s and the $\xi_{t}$s are not available. We refer
them as latent variables of the model, and we use a Bayesian approach to deal
with this.

###  3.1 Priors setup and hyperparameters

The setup of prior distributions mostly exploits and adapts the existing
literature (for relevant examples see, for instance, Diebolt and Robert, 1994;
Geweke, 1993; Sampietro, 2006).

In absence of relevant prior information, it is reasonable to assume a priori
that each observation is equally likely to be generated from any of the
mixture components, i.e. $\pi_{1}=\dots,\pi_{g}=1/g$. This implies a discrete
uniform distribution for the $Z_{t}$s, which is a particular case of the
multinomial distribution. The natural conjugate prior for it is a Dirichlet
distribution for $\bm{\pi}$, and therefore we set:

$\bm{\pi}\sim\mathcal{D}\left(w_{1},\ldots,w_{g}\right),\qquad
w_{1}=\dots=w_{g}=1$

The prior distribution of each $\xi_{t}$ directly depends upon the
corresponding $Z_{t}$, i.e. which of the mixture component $y_{t}$ was
generated from. By model specification, for a generic $z_{tk}=1$, prior
distribution on $\xi_{t}$ is

$\xi_{t}\mid\bm{z}_{t}\sim Ga(\dfrac{\nu_{k}}{2},\dfrac{\nu_{k}-2}{2})$

The prior distribution on the component means is a Normal distribution with
common hyperparamters $\zeta$ for the mean and $\kappa$ for the precision

$\mu_{k}\sim N\left(\zeta,\kappa^{-1}\right),\qquad k=1,\ldots,g$

For the precision $\tau_{k}$, a hierarchical approach is adopted, as suggested
by Richardson and Green (1997). Specifically, we set

$\begin{split}\tau_{k}&\sim Ga\left(c,\lambda\right),\qquad k=1,\ldots,g\\\
\lambda&\sim Ga(a,b)\end{split}$

To account for potential multimodality in the distribution, we choose a
multivariate uniform prior distribution for the autoregressive parameters,
limited in the stability region of the model. Hence, for a generic
$\bm{\phi}_{k}$ we have:

$p(\bm{\phi}_{k})\propto\mathcal{I}\\{\textit{Stable}\\}$

where $\mathcal{I}\\{\cdot\\}$ is the indicator function assuming value 1 if
the model is stable and 0 otherwise.

For prior distribution on the degrees of freedom $\nu_{k}$, $k=1,\ldots,g$,
Geweke (1993) suggests an exponential distribution. However, the posterior
distribution could potentially be highly influenced by the choice of prior,
and therefore choosing an exponential prior could result in favour of low
degrees of freedom. We opt instead for a $Ga(\alpha_{k},\beta_{k})$,
$k=1,\ldots,g$ prior distributions, which are more flexible, and allow to
better incorporate prior information or belief.

Two more considerations have to be made: the degrees of freedom parameter must
assume value larger than $2$ for existence of first and second moments of the
Student t distribution; For degrees of freedom larger than $30$, it is
reasonable to use a Normal approximation. Therefore, we opted for truncating
the prior distribution so that only values in the interval $[2,30]$ belong to
the parameter space.

#### Choice of hyperparameters

We require specification for the hyperparameters $\zeta$, $\kappa$, $c$, $a$
and $b$. Although $\lambda$ is also a hyperparameter, it is a random variable,
fully specified once $a$ and $b$ are chosen.

Following standard setup of mixture models (Richardson and Green, 1997, e.g.),
let $\mathcal{R}_{y}=\max(y)-min(y)$ be the length variation of the dataset.
Hyperparameters are then set as follows:

$\displaystyle a$ $\displaystyle=0.2$ $\displaystyle c$ $\displaystyle=2$
$\displaystyle
b=\dfrac{100a}{c\mathcal{R}_{y}^{2}}=\dfrac{10}{\mathcal{R}_{y}^{2}}$
$\displaystyle\zeta$ $\displaystyle=\min(y)+\dfrac{R_{y}}{2}$
$\displaystyle\kappa$ $\displaystyle=R_{y}^{-1}$

The choice of $\alpha_{k}$ and $\beta_{k}$ for prior distributions of degrees
of freedom parameters are the result of the following reasoning:

  * •

In general, choosing $\alpha>1$ ensures a peak in the gamma distribution,
which could drive the posterior distribution towards such peak.

  * •

The mode of a gamma distribution is equal to $\dfrac{\alpha-1}{\beta}$,
because of the inevitable subjectivity of this prior, it is reasonable to
choose a distribution that sees its peak around the point of maximum
likelihood. Denoting $\hat{\nu}_{k}^{EM}$ the estimate of degrees of freedom
using the EM-algorithm approach (Wong et al., 2009), we set a condition that

$\dfrac{\alpha_{k}-1}{\beta}=\hat{\nu}_{k}^{EM}$

  * •

We may want to assume a priori that degrees of freedom parameters for all
components have a priori the same variance (at least approximately, given the
truncated nature of the prior). Given a target variance $s^{2}$, this can be
done by setting:

$\dfrac{\alpha}{\beta^{2}}=s^{2}$

Thus, each $\alpha_{k}$ and $\beta_{k}$ are carefully chosen so that these two
conditions are satisfied.

###  3.2 Simulation of latent variables and posterior distributions

We here give formulas for simulation of the latent variables in the model,
$\bm{Z}$ and $\bm{\xi}$, and posterior distributions of model parameters.

Let $\bm{\phi}(\cdot)$ denote the pdf of the standard Normal distribution, and
introduce the following notation:

$\displaystyle e_{tk}$
$\displaystyle=y_{t}-\phi_{k0}-\displaystyle\sum_{i=1}^{p}\phi_{ki}y_{t-i},$
$\displaystyle k$ $\displaystyle=1,\ldots,g;$ $\displaystyle t$
$\displaystyle=(p+1),\ldots,n$ $\displaystyle n_{k}$
$\displaystyle=\displaystyle\sum_{t=p+1}^{n}z_{tk}$ $\displaystyle\bar{e}_{k}$
$\displaystyle=\dfrac{1}{n_{k}}\sum_{t:z_{tk}=1}e_{tk}$ $\displaystyle b_{k}$
$\displaystyle=1-\sum_{i=1}^{p}\phi_{ki}$ $\displaystyle c_{k}$
$\displaystyle=\sum_{t:z_{tk}=1}\xi_{t}\left(e_{tk}-\bar{e}_{k}\right)$
$\displaystyle d_{k}$ $\displaystyle=\sum_{t:z_{tk}=1}\xi_{t}$

We have:

$\begin{split}P\left(Z_{tk}=1\mid\bm{\pi},\bm{\mu},\bm{\tau},\lambda,\bm{\nu},\bm{y},\xi_{t}\right)&=\dfrac{\dfrac{\pi_{k}}{\sigma_{k}}\bm{\phi}\left(\dfrac{e_{tk}}{\sigma_{k}/\sqrt{\xi_{t}}}\right)}{\displaystyle\sum_{l=1}^{g}\dfrac{\pi_{l}}{\sigma_{l}}\bm{\phi}\left(\dfrac{e_{tl}}{\sigma_{l}/\sqrt{\xi_{t}}}\right)}\\\
\xi_{t}\mid\bm{z}_{t},\bm{\pi},\bm{\mu},\bm{\tau},\lambda,\bm{y},\bm{\nu}&\sim
Ga\left(\dfrac{\nu_{k}+1}{2},\dfrac{\tau_{k}}{2}e_{tk}^{2}+\dfrac{\nu_{k}-2}{2}\right)\\\
\bm{\pi}\mid\bm{\mu},\bm{\tau},\lambda,\bm{\nu},\bm{y},\bm{z},\bm{\xi}&\sim\mathcal{D}\left(1+n_{1},\ldots,1+n_{g}\right)\\\
\mu_{k}\mid\bm{\pi},\bm{\tau},\lambda,\bm{\nu},\bm{y},\bm{z},\bm{\xi}&\sim
N\left(\dfrac{\tau_{k}b_{k}(\bar{e}_{k}d_{k}+c_{k})+\kappa\zeta}{\tau_{k}b_{k}^{2}d_{k}+\kappa},\dfrac{1}{\tau_{k}b_{k}^{2}d_{k}+\kappa}\right)\\\
\tau_{k}\mid\bm{\pi},\bm{\mu},\lambda,\bm{\nu},\bm{y},\bm{z},\xi_{t}&\sim
Ga\left(\dfrac{n_{k}}{2}+c,\dfrac{1}{2}\sum_{t:z_{tk}=1}\xi_{t}e_{tk}^{2}+\lambda\right)\\\
\lambda\mid\bm{\pi},\bm{\mu},\bm{\tau},\bm{\nu},\bm{y},\bm{z},\xi_{t}&\sim
Ga\left(a+cg,b+\sum_{k=1}^{g}\tau_{k}\right)\end{split}$ (7)

Posterior distributions of $\bm{\phi}_{k}$ and $\nu_{k}$ do not have the form
of a standard distribution, therefore we recur to Metropolis-Hastings methods
for simulation.

For the autoregressive parameters, $\bm{\phi}_{k}$, $k=1,\ldots,g$, we recur
to random walk metropolis. Let $\bm{\phi}_{k}$ be the current state of the
chain. We simulate a candidate value $\bm{\phi}_{k}^{*}$ from the proposal
distribution $MVN\left(\bm{\phi}_{k},\gamma_{k}I_{p_{k}}\right)$, where
$\gamma_{k}$ is a tuning parameter and $I_{pk}$ is the $p_{k}\times p_{k}$
identity matrix. A move to the candidate value $\bm{\phi}_{k}^{*}$ is then
accepted with probability

$\alpha\left(\bm{\phi}_{k}^{,}\bm{\phi}_{k}^{*}\right)=\min\left(1,\dfrac{\exp\Bigg{\\{}-\dfrac{\tau_{k}}{2}\displaystyle\sum_{t:z_{tk}=1}y_{t}-\phi_{k0}^{*}-\displaystyle\sum_{i=1}^{p_{k}}\phi_{ki}^{*}y_{t-i}\Bigg{\\}}}{\exp\Bigg{\\{}-\dfrac{\tau_{k}}{2}\displaystyle\sum_{t:z_{tk}=1}y_{t}-\phi_{k0}-\displaystyle\sum_{i=1}^{p_{k}}\phi_{ki}y_{t-i}\Bigg{\\}}}\right)$
(8)

The posterior distribution of a generic $\nu_{k}$ can be written as:

$p\left(\nu_{k}\mid\bm{\pi},\bm{\mu},\bm{\tau},\lambda,\bm{y},\bm{z},\bm{\xi}\right)\propto\dfrac{\left(\dfrac{\nu_{k}-2}{2}\right)^{n_{k}\nu_{k}/2}}{\Gamma\left(\dfrac{\nu_{k}}{2}\right)}\prod_{t:z_{tk}=1}\xi_{t}^{\nu_{k}/2-1}\exp\\{\dfrac{\nu_{k}-2}{2}\sum_{t:z_{tk}=1}\xi_{t}\\}\\\
\nu_{k}\exp\\{-\beta\nu_{k}\\}$ (9)

which is not a standard distribution. We propose an independent sampler.
Independently of the current state of the chain, $\nu_{k}$, we simulate a
candidate value $\nu_{k}^{*}$ from its prior distribution. In this way, the
acceptance probability reduces to the likelihood ratio between the candidate
value and the current value, i.e.

$\alpha\left(\nu_{k},\nu_{k}^{*}\right)=\min\left(1,\dfrac{\left(\dfrac{\nu_{k}^{*}-2}{2}\right)^{n_{k}\nu_{k}^{*}/2}}{\left(\dfrac{\nu_{k}-2}{2}\right)^{n_{k}\nu_{k}/2}}\dfrac{\Gamma\left(\dfrac{\nu_{k}}{2}\right)}{\Gamma\left(\dfrac{\nu_{k}^{*}}{2}\right)}\dfrac{\displaystyle\prod_{t:z_{tk}=1}\xi_{t}^{\nu_{k}^{*}/2-1}}{\displaystyle\prod_{t:z_{tk}=1}\xi_{t}^{\nu_{k}/2-1}}\dfrac{\nu_{k}^{*}}{\nu_{k}}\exp\big{\\{}-\beta(\nu_{k}-\nu_{k}^{*})\big{\\}}\right)$
(10)

###  3.3 Choosing autoregressive orders

For this step, we recur to reversible jump MCMC (Green, 1995), updating the
equations of Gaussian mixtures to account for the new model specification. At
each iteration, one of the $g$ mixture components, say $k$, is chosen at
random. Let $p_{k}$ be the current autoregressive order of such component. In
addition, set $p_{max}$ as the largest possible autoregressive order. The
proposal is to increase the autoregressive order to $p_{k}^{*}=p_{k}+1$ with
probability $b(p_{k})$, or decrease it to $p_{k}^{*}=p_{k}-1$ with probability
$d(p_{k})$. $b(\cdot)$ may be any function defined in $[0,1]$ satisfying
$b(p_{max})=0$, and $d(p_{k})=1-b(p_{k})$.

Both scenarios have a $1-1$ mapping between current and candidate model, since
the only difference between the two is the addition or subtraction of the
largest order autoregressive parameter. Therefore, the Jacobian is always
equal to $1$.

Given a proposed move, we proceed as follows:

  * •

If the proposed move is to $p_{k}^{*}=p_{k}-1$, the autoregressive parameter
$\phi_{kp_{k}}$ is dropped from the model, and the acceptance probability is
the product of the likelihood and the proposal ratio, i.e.

$\alpha(p_{k},p_{k}^{*})=\min\Bigg{\\{}1,\dfrac{f\left(\bm{y}\mid\bm{\phi}_{k}^{p_{k}^{*}}\right)}{f\left(\bm{y}\mid\bm{\phi}_{k}^{p_{k}}\right)}\times\dfrac{b(p_{k}^{*})}{d(p_{k})}\times\bm{\phi}\left(\dfrac{\phi_{pk}-\phi_{pk}}{1/\sqrt{\gamma_{k}}}\right)\Bigg{\\}}$
(11)

  * •

If the proposal is to move to $p_{k}^{*}=p_{k}+1$, we simulate the additional
parameter $\phi_{kp_{k}^{*}}$ from a $\mathcal{U}(-1.5,1.5)$ distribution.
This choice ensures that values close to $0$ are equally as likely to be taken
into consideration as values far from zero, while trying to maintain the
algorithm as efficient as possible in terms of drawing values within the
stability region of the model.

In this case, the acceptance probability is the ratio between the likelihood
and the proposal, i.e.

$\alpha(p_{k},p_{k}^{*})=\min\Bigg{\\{}1,\dfrac{f\left(\bm{y}\mid\bm{\phi}_{k}^{p_{k}^{*}}\right)}{f\left(\bm{y}\mid\bm{\phi}_{k}^{p_{k}}\right)}\times\dfrac{d(p_{k}^{*})}{b(p_{k})}\times
3\Bigg{\\}}$ (12)

where $3$ is the inverse of the density of any $\phi_{kp_{k}^{*}}$ under a
$\mathcal{U}(-1.5,1.5)$ proposal distribution.

Notice that, in both scenarios, if the candidate model does not satisfy the
stability condition of Section 2.1, then it is automatically rejected.

Ultimately, the model which is selected the most number of times over a fixed
number of iterations is retained to be the best fit for the data (for a
certain fixed $g$).

###  3.4 Choosing the number of mixture components

The analysis presented so far works under the assumption of correct
specification of the number of mixture components $g$. We now need a way to
select a suitable number of mixture components.

Recall the marginal likelihood identity. The marginal likelihood function,
(i.e. only conditional on the number $g$) is defined as:

$f(y\mid g)=\sum_{p}\int f(y\mid\bm{\theta},p,g)p(\bm{\theta},p\mid g)d\theta$
(13)

where $\bm{\theta}$ is the vector of model parameters. In our case,
$\bm{\theta}=(\bm{\phi},\bm{\mu},\bm{\tau},\bm{\pi},\bm{\nu})$.

For any values $\bm{\theta}^{*}$, $p^{*}$, $g$ and observed data $y$, the
marginal likelihood identity can be decomposed into products of quantities
that can be estimated:

$f(y\mid g)=\dfrac{f(y\mid\bm{\theta}^{*},p^{*},g)p(\bm{\theta}^{*}\mid
p^{*},g)p(p^{*}\mid g)}{p(\bm{\theta}^{*}\mid y,p^{*},g)p(p^{*}\mid y,g)}$
(14)

Notice that most quantities in (14) are ready available. In fact,
$f(y\mid\bm{\theta}^{*},p^{*},g)$ is the conditional pdf of the data, which is
known under the model specification; $p(\bm{\theta}^{*}\mid p^{*},g)$ is the
set of prior densities on the model parameters (see Section 3.1); $p(p^{*}\mid
g)$ is the prior on the maximum autoregressive order, which is discrete
uniform in $[1,p_{max}]$ a priori (see Section 3.3); $p(p^{*}\mid y,g)$ is the
posterior distribution of the selected autoregressive orders, which we
approximate by the proportion of times the RJMCMC algorithm in Section 3.3
retains such model; finally, $p(\bm{\theta}^{*}\mid y,p^{*},g)$ is the set of
posterior densities on the model parameters (see Section 3.2), which needs to
be estimated.

To estimate $p(\bm{\theta}^{*}\mid y,p^{*},g)$ we recur to the the methods by
Chib (1995) and Chib and Jeliazkov (2001), respectively for use of output from
Gibbs sampling and Metropolis-Hastings sampling. The method is analogous to
that used in Sampietro (2006), taking into account the different model
specification, and the additional model parameters introduced for the degrees
of freedom of each mixture component.

Notice that $p(\bm{\theta}^{*}\mid y,p^{*},g)$ can be further decomposed into
a product:

$\begin{split}p(\bm{\theta}^{*}\mid y,p^{*},g)=&p(\bm{\phi}^{*}\mid
y,p^{*},g)\\\ &p(\bm{\nu}^{*}\mid\bm{\phi}^{*},y,p^{*},g)\\\
&p(\bm{\mu}^{*}\mid\bm{\phi}^{*},\bm{\nu}^{*},y,p^{*},g)\\\
&p(\bm{\tau}^{*}\mid\bm{\phi}^{*},\bm{\nu}^{*},\bm{\mu}^{*},y,p^{*},g)\\\
&p(\bm{\pi}^{*}\mid\bm{\phi}^{*},\bm{\nu}^{*},\bm{\mu}^{*},\bm{\tau}^{*},y,p^{*},g)\end{split}$
(15)

Once all quantities have been estimated, they are plugged into (14) to
estimate the marginal loglikelihood.

To compare models with different $g$, the algorithm must be run separately for
each individual $g_{1},g_{2},$ and so on. In addition, for better efficiency
it is recommended that models with different number of mixture components are
compared on the basis of high density values of the parameters according to
their distributions in (15).

#### Estimation of $\bm{p(\phi^{*}\mid y,p^{*},g)}$

Posterior distributions of autoregressive paramters are estimated by a
Metropolis-Hastings algorithm. Here we describe how to estimate the
probability of interest.

For a generic mixture component $k$, we partition the parameter space into two
subsets, namely
$\Psi_{k-1}=(p,\bm{\phi}_{1}^{*},\ldots,\bm{\phi}_{k-1}^{*},g)$ and
$\Psi_{k+1}=(\bm{\phi}_{k+1},\ldots,\bm{\phi}_{g},\bm{\nu},\bm{\mu},\bm{\tau},\bm{\pi})$,
where parameters in $\Psi_{k-1}$ are fixed.

First, produce a reduced chain of length $N_{j}$ for the non-fixed parameters,
and fix $\bm{\phi}_{k}^{*}$ to be the highest density value. Define now
$\Psi_{k}=(\Psi_{k-1},\bm{\phi}_{k}^{*})$

Run a second reduced chain of length $N_{i}$ ($N_{i}$ and $N_{j}$ may be
equal) for $\Psi_{k+1}$, as well as a sample $\tilde{\bm{\phi}}_{k}$ from the
proposal distribution $MVN(\bm{\phi}_{k}^{*},\gamma_{k}I_{p_{k}})$.

Finally, let $\alpha(\bm{\phi}_{k}^{(j)},\bm{\phi}_{k}^{*})$ and
$\alpha(\bm{\phi}_{k}^{*},\tilde{\bm{\phi}}_{k}^{(i)})$ be the acceptance
probabilities of the Metropolis-Hastings algorithm, respectively for the first
and the second chain. The conditional density at $\bm{\phi}_{k}^{*}$ can then
be estimated as

$p(\bm{\phi}_{k}^{*}\mid\Psi_{k-1},y,p^{*},g)=\dfrac{\dfrac{1}{N_{j}}\displaystyle\sum_{j=1}^{N_{j}}\alpha(\bm{\phi}_{k}^{(j)},\bm{\phi}_{k}^{*})q_{\phi_{k}}\left(\bm{\phi}_{k}^{(j)},\bm{\phi}_{k}^{*}\right)}{\dfrac{1}{N_{i}}\displaystyle\sum_{i=1}^{N_{i}}\alpha(\bm{\phi}_{k}^{*},\tilde{\bm{\phi}}_{k}^{(i)})}$
(16)

where $q\left(\bm{\phi}_{k}^{(j)},\bm{\phi}_{k}^{*}\right)$ denotes the
density of $\bm{\phi}_{k}^{(j)}$ under the proposal
$MVN(\bm{\phi}_{k}^{*},\gamma_{k}I_{p_{k}})$.

#### Estimation of $\bm{p(\nu^{*}\mid\phi^{*},y,p^{*},g)}$

Degrees of freedom are also estimated via Metropolis-Hastings, therefore we
proceed in a similar way.

For a generic component $k$ partition the parameter space into
$\Omega_{k-1}=(p,\bm{\phi}^{*},\nu_{1},\ldots,\nu_{k-1},g)$ and
$\Omega_{k+1}=(\nu_{k+1},\ldots,\nu_{g},\bm{\mu},\bm{\tau},\bm{\pi})$.

Produce a reduced chain of length $N_{j}$ for the non-fixed parameters and fix
$\nu_{k}^{*}$ to be the highest density value, and define
$\Omega_{k}=(\Omega_{k-1},\nu_{k}^{*})$.

Run as second chain of length $N_{i}$ for $\Omega_{k+1}$, as well as second
sample $\tilde{\nu}_{k}$ from the proposal disitribution. Let
$\alpha(\nu_{k}^{(j)},\nu_{k}^{*})$ and
$\alpha(\nu_{k}^{*},\tilde{\nu}_{k}^{(i)})$ be acceptance probabilities
respectively of the first and second chain. The conditional density at
$\nu_{k}^{*}$ can be estimated as

$p(\nu_{k}^{*}\mid\Omega_{k-1},y,p^{*},g)=\dfrac{\dfrac{1}{N_{j}}\displaystyle\sum_{j=1}^{N_{j}}\alpha(\nu_{k}^{(j)},\nu_{k}^{*})q_{\nu_{k}}\left(\nu_{k}^{(j)},\nu_{k}^{*}\right)}{\dfrac{1}{N_{i}}\displaystyle\sum_{i=1}^{N_{i}}\alpha(\nu_{k}^{*},\tilde{\nu}_{k}^{(i)})}$
(17)

where $q_{\nu_{k}}\left(\nu_{k}^{(j)},\nu_{k}^{*}\right)$ denotes the density
of $\nu_{k}^{(j)}$ under the prior (proposal) distribution $Ga(\alpha,\beta)$.

#### Estimation of $\bm{p(\mu^{*}\mid\phi^{*},\nu^{*},y,p^{*},g)}$

Run a reduced chain of length $N_{j}$ for the non-fixed parameters. Set
$\bm{\mu^{*}}=(\mu_{1}^{*},\ldots,\mu_{g}^{*})$ to be the highest density
value. The posterior density of $\bm{\mu^{*}}$ can be estimated as:

$p\left(\bm{\mu^{*}}\mid\bm{\phi}^{*},\bm{\nu}^{*},y,p^{*},g\right)=\dfrac{1}{N}\sum_{j=1}^{N_{j}}\prod_{k=1}^{g}p\left(\mu_{k}^{*}\mid\bm{\phi}^{*},\bm{\nu}^{*},\bm{\tau}^{(i)},\bm{\pi}^{(i)},y,\bm{z}^{(i)},p^{*},g\right)$
(18)

#### Estimation of $\bm{p(\tau^{*}\mid\phi^{*},\nu^{*},\mu^{*},y,p^{*},g)}$

Run a reduced chain of length $N_{j}$ for the non-fixed parameters. Set
$\bm{\tau^{*}}=(\tau_{1}^{*},\ldots,\tau_{g}^{*})$ to be the highest density
value. The posterior density of $\bm{\tau^{*}}$ can be estimated as:

$p\left(\bm{\tau}^{*}\mid\bm{\phi}^{*},\bm{\nu}^{*},\bm{\mu^{*}},y,p^{*},g\right)=\dfrac{1}{N_{j}}\sum_{j=1}^{N_{j}}\prod_{k=1}^{g}p\left(\tau_{k}^{*}\mid\bm{\phi}^{*},\bm{\nu}^{*},\bm{\mu}^{*},\bm{\pi}^{(i)},y,\bm{z}^{(i)},p^{*},g\right)$
(19)

#### Estimation of
$\bm{p(\pi^{*}\mid\phi^{*},\nu^{*},\mu^{*},\tau^{*},y,p^{*},g)}$

Run a reduced chain of length $N_{j}$ for the mixing weights, which are now
the only non-fixed parameters. Set
$\bm{\pi^{*}}=(\pi_{1}^{*},\ldots,\pi_{g}^{*})$ to be the highest density
value. The posterior density of $\bm{\pi^{*}}$ can be estimated as:

$p\left(\bm{\pi}^{*}\mid\bm{\nu}^{*},\bm{\phi}^{*},\bm{\mu^{*}},\bm{\tau}^{*},y,p^{*},g\right)=\dfrac{1}{N_{j}}\sum_{j=1}^{N_{j}}p\left(\bm{\pi}^{*}\mid\bm{\phi}^{*},\bm{\nu}^{*},\bm{\mu}^{*},\bm{\tau}^{*},y,\bm{z}^{(i)},p^{*},g\right)$
(20)

##  4 Example

To illustrate performance of our method, we simulated a time series of length
$n=500$ from the process:

$y_{t}=\begin{cases}-0.5y_{t-1}+0.5y_{t-2}+\varepsilon_{t1}\qquad&\text{with
probability }0.4\\\ ~{}~{}1.1y_{t-1}+\varepsilon_{t2}\qquad&\text{with
probability }0.4\\\ -0.4y_{t-1}+\varepsilon_{t3}\qquad&\text{with probability
}0.2\\\ \end{cases}$

where $\varepsilon_{t1}\sim\mathcal{S}(0,5^{2},4)$,
$\varepsilon_{t2}\sim\mathcal{S}(0,3^{2},14)$ and
$\varepsilon_{t3}\sim\mathcal{S}(0,1,10)$. We denote this as
$\operatorname*{tMAR}(3;2,1,1)$.

The series can be seen in Figure 1, and it represents what in practice one
should be looking for to assume a MAR model. The series looks in fact
heteroskedastic, amd the plot of the sample autocorrelation shows that data
are slightly correlated at lag 2. Both these features may indicate that the
underlying generating process is mixture autoregressive.

Figure 1: Simulated time series from $\operatorname*{tMAR}(3;2,1,1)$ process
(top) and sample autocorrelation.

For the analysis, we compared all possible models with 2 and 3 mixture
components, and maximum autoregressive order equal to 4.

For what regards the optimal autoregressive orders, the RJMCMC algorithm
chooses a $\operatorname*{tMAR}(3;2,1,1)$ among all 3-component models, with a
preference of $0.8054$ (i.e. the model was retained as ”best” 3-component
model on roughly $81\%$ of the iterations), and a
$\operatorname*{tMAR}(2;2,1)$ among all 2-component models, with a preference
of $0.8149$. When compared with each other in terms of marginal likelihood,
the best model was $\operatorname*{tMAR}(3;2,1,1)$ with marginal log-
likelihood of $-1502.77$ against $-1519.166$ for
$\operatorname*{tMAR}(2;2,1)$.

We then simulated a sample of length $100000$ from the posterior distribution
of the paramters, after allowing $10000$ burn-in iterations. Results are
displayed in Figure 2 and Figure 3.

Figure 2: Trace and density plots of full conditional posterior distributions
of model parameters under selected $\operatorname*{tMAR}(3;2,1,1)$ model. Red
lines highlight true values. Figure 3: Trace plots and histograms of full
conditional posterior distributions of degrees of freedom parameters under
selected $\operatorname*{tMAR}(3;2,1,1)$ model, with unit bin-width. Red lines
highlight true values.

We can see from Figure 2 that almost all ”true” parameters are included within
the $95\%$ posterior density region of their respective distribution. The only
exception is found in $\mu_{1}$, for which such region is $[-1.449,-0.0177]$.
However, it must be taken into account that component 1 has the largest
variance and the largest autoregressive order, and is therefore more subject
to sampling variability. For what regards the degrees of freedom parameter,
all three components have their peak near the true values of the paramaeters:
respectively, peaks are found between $[4,7]$, $[11,13]$ and $[8,11]$ (true
values are $4$, $14$ and $10$).

Overall, we may be satisfied with performance of the algorithm.

##  5 The IBM common stock closing prices

The IBM common stock closing prices (Box and Jenkins, 1976) is a financial
time series widely explored several times in the literature, including
ravagli2020bayesian, which is our focus for comparison. The series contains
369 observations from May 17th 1961 to November 2nd 1962.

We consider the series of first order differences, which can be seen in Figure
4. The series presents clear signs of heteroskedasticity, therefore a tMAR
model may be a reasonable choice to model the data.

Figure 4: Series of first order differences for IBM adjusted closing prices.

For comparison with previous studies, shift parameters $\phi_{k0}$,
$k=1,\ldots,g$ are fixed to 0, hence are not paramters in the model. This
taken into account, our method chooses a $\operatorname*{tMAR}(2;1,1)$ as best
fit among all tMAR models with 2 and 3 mixture components and maximum
autoregressive order equal to 4. More specifically, the model was retained
about half of the iterations (5067 times over 10000 iterations) by RJMCMC,
meaning it is preferred to models with 2 mixing components and larger
autoregressive orders. Furthermore, the marginal loglikelihood for this model
is $-1232.678$, which is larger than that of the competing
$\operatorname*{tMAR}(3;2,1,1)$, $-1258.073$, which was selected as best
3-component model.

Once again, we simulated a sample of size 100000 from the posterior
distribution of the parameters, after 10000 burn-in iterations, which can be
seen in Figure 5.

Figure 5: Trace and density plots of parameter posterior distributions under
selected $\operatorname*{tMAR}(2;1,1)$ model for the IBM data.

ravagli2020bayesian selected a Gaussian $\operatorname*{MAR}(3;1,1,4)$ as best
fit for the same dataset, where one of the mixture components was
”specialised” to model very few observations with large variability. However,
the $\operatorname*{tMAR}$ model, thanks to its flexibility in the tails of
the distribution, only requires 2 components to account for such noise,
returning a model that is simpler, in that it has fewer parameters, and most
importantly has a more straightforward interpretation.

##  6 Conclusions

We have seen a fully Bayesian analysis of mixture autoregressive models with
standardised Student t innovations. In a simulation example, it was shown how
the method can correctly find the best model to fit a given dataset. In
addition, we saw that the proposed MCMC for simulation from parameter
posterior distributions quickly converges to stationarity, and that true
values of those parameters are found in high density region.

Secondly, we showed the analysis performed on the IBM common stock closing
prices, a dataset widely exploited in the literature of heteroskedastic
models. In particular, we focused on comparison with the analysis of
ravagli2020bayesian here, which used a Gaussian MAR model. Results tell that,
thanks to the flexibility of the Student t distribution in its tails, we are
able now to fit the data with a considerably more parsimonious model, which
also has an easier interpretation.

A limitation of the proposed method is that it inevitably relies on prior
information when it comes to degrees of freedom parameters. In practice, this
means that if one incorporates wrong prior beliefs, the resulting posterior
distribution will be affected, potentially leading to wrong conclusions. One
way to make this part of the analysis more objective could be adapting
Jeffrey’s priors for the Student t regression model (Fonseca et al., 2008b) to
the case of mixture autoregression. However, this would require derivation of
the information matrix. On the other hand, the method performs well as long as
hyperparameters are set ”loosely” around the true value of the parameter of
interest, so that it may worth using as long as prior information is broadly
reliable (i.e. it is sufficient that EM-estimates are available).

## References

  * (1)
  * Boshnakov (2011) Boshnakov, G. N.: 2011, On first and second order stationarity of random coefficient models, Linear Algebra Appl. 434(2), 415–423.
  * Box and Jenkins (1976) Box, G. E. P. and Jenkins, G. M.: 1976, Time series analysis : forecasting and control / George E.P. Box and Gwilym M. Jenkins, rev. ed. edn, Holden-Day San Francisco.
  * Chib (1995) Chib, S.: 1995, Marginal likelihood from the Gibbs output., J. A. Stat. Ass. 90(432), 1313–1321.
  * Chib and Jeliazkov (2001) Chib, S. and Jeliazkov, I.: 2001, Marginal likelihood from the Metropolis-Hastings output., J. A. Stat. Ass. 96(453), 270–281.
  * Dempster et al. (1977) Dempster, A. P., Laird, N. M. and Rubin, D. B.: 1977, Maximum likelihood from incomplete data via the em algorithm, Journal of the royal statistical society. Series B (methodological) pp. 1–38.
  * Diebolt and Robert (1994) Diebolt, J. and Robert, C. P.: 1994, Estimation of finite mixture distributions through bayesian sampling, Journal of the Royal Statistical Society. Series B (Methodological) 56, 363–375.
  * Fonseca et al. (2008a) Fonseca, T. C. O., Ferreira, M. A. R. and Migon, H. S.: 2008a, Objective bayesian analysis for the student-t regression model, Biometrika 95(2), 325–333.
http://www.jstor.org/stable/20441467

  * Fonseca et al. (2008b) Fonseca, T. C. O., Ferreira, M. A. R. and Migon, H. S.: 2008b, Objective bayesian analysis for the student-t regression model, Biometrika 95(2), 325–333.
http://www.jstor.org/stable/20441467

  * Geweke (1993) Geweke, J.: 1993, Bayesian treatment of the independent student-t linear model, Journal of Applied Econometrics 8, S19–S40.
http://www.jstor.org/stable/2285073

  * Geweke (1994) Geweke, J.: 1994, Priors for macroeconomic time series and their application, Econometric Theory 10(3-4), 609–632.
  * Green (1995) Green, P. J.: 1995, Reversible jump markov chain monte carlo computation and bayesian model determination, Biometrika 82(4), 711–732.
  * Richardson and Green (1997) Richardson, S. and Green, P. J.: 1997, On Bayesian Analysis of Mixtures with an Unknown Number of Components., J. R. Stat. Soc., Ser. B, Stat. Methodol. 59(4), 731–792.
  * Sampietro (2006) Sampietro, S.: 2006, Bayesian analysis of mixture of autoregressive components with an application to financial market volatility, Applied Stochastic Models in Business and Industry 22(3), 242.
  * Wong et al. (2009) Wong, C. S., Chan, W. S. and Kam, P. L.: 2009, A student t -mixture autoregressive model with applications to heavy-tailed financial data, Biometrika 96(3), 751–760.
http://www.jstor.org/stable/27798861

  * Wong and Li (2000) Wong, C. S. and Li, W. K.: 2000, On a mixture autoregressive model., J. R. Stat. Soc., Ser. B, Stat. Methodol. 62(1), 95–115.


# An information-theoretic lower bound in
Time-uniform estimation

John C. Duchi Saminul Haque
Stanford University Research supported by Office of Naval Research Award
N00014-22-1-2669 and National Science Foundation Award RI-2006777.

(February 2024)

###### Abstract

We present an information-theoretic lower bound for the problem of parameter
estimation with time-uniform coverage guarantees. Via a new a reduction to
sequential testing, we obtain stronger lower bounds that capture the hardness
of the time-uniform setting. In the case of location model estimation,
logistic regression, and exponential family models, our
$\Omega(\sqrt{n^{-1}\log\log n})$ lower bound is sharp to within constant
factors in typical settings.

##  1 Introduction

Let $X_{1},X_{2},\dots$ be independent samples from a common distribution
$P\in\mathcal{P}$ over a domain $\mathcal{X}$. Given a parameter
$\theta:\mathcal{P}\rightarrow\Theta\subset\mathbb{R}$ and an error-bound
function $t:\mathbb{N}\rightarrow\mathbb{R}_{+}$, we say a sequence of
estimators $\\{\hat{\theta}_{n}\\}_{n\in\mathbb{N}}$ is an
$(\alpha,t(\cdot))$-estimator if for all $P\in\mathcal{P}$,

$\displaystyle\mathbb{P}_{X_{i}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P}\left(|\hat{\theta}_{n}(X_{1:n})-\theta(P)|\leq t(n),\textrm{
for all }n\in\mathbb{N}\right)\geq 1-\alpha.$ (1)

We provide fundamental limits on $t(\cdot)$ that imply there exist no
$(\alpha,t(\cdot))$-estimators.

Our motivation comes from the problem of estimating time-uniform confidence
sequences [4, 13], where the analyst must return a confidence set $C_{n}$ at
every $n$ such that $\mathbb{P}(\theta(P)\in C_{n}\textrm{ for all }n)\geq
1-\alpha$. Darling and Robbins [4] introduced confidence sequences as a means
of allowing statistical inference without committing a priori to a fixed
sample size [16]. Their time-uniformity has made confidence sequences are a
popular tool in sequential data analysis, such as in clinical testing [9, 14],
A/B testing [10, 7], and bandit arm identification [8, 11].

Methods for producing confidence sequences often see the size of the
confidence intervals decay at a rate of $\Theta(\sqrt{n^{-1}\log\log n})$ [4,
7, 8], ignoring dependence on parameters other than $n$. This stands in
contrast to the fixed sample size setting, where the confidence intervals
instead be of size $\Theta(n^{-1/2})$; thus, these methods incur a
$\Theta(\sqrt{\log\log n})$ factor to achieve time-uniform coverage. Farrell
[6] (and Jamieson et al. [8], via a reduction to Farrell’s results) shows this
cost is necessary in exponential families. Their lower bound technique
proceeds in two steps: first, they show an optimal estimator takes the form of
a sufficient statistic, and second, they use the law-of-the-iterated-logarithm
to show that this statistic has fluctuations on the order of
$\Theta(\sqrt{n^{-1}\log\log n})$ infinitely often. This argument crucially
relies on the particular structure of the one-parameter exponential family
model, which allows one to argue that an optimal estimator necessarily
thresholds a sufficient statistic, making it unclear how, or even if, the
bounds generalize to other scenarios. In this paper, we elicit the same
$\Theta(\sqrt{\log\log n})$ cost through information-theoretic techniques,
which have the benefit of extending to broader families of problems via now
familiar reductions [e.g. 18, Chapter 14].

Our techniques rely on standard information-theoretic results, such as Le
Cam’s two point method, the Bretagnolle-Huber inequality, and the reduction
from estimation to testing. Our novel technique in proving this lower bound is
to reduce to a sequence of testing problems that grow iteratively harder. By
accumulating the errors from these tests, we obtain the extra
$\Theta(\sqrt{\log\log n})$ factor in the lower bound.

Notation We use $\mathcal{V}$ to denote the set of infinite binary sequences
$\\{0,1\\}^{\infty}$. For $v\in\mathcal{V}$ and $l,k\in\mathbb{N}$, we use
$v_{k:l}$ to denote the $(l-k+1)$-length binary string $(v_{k},\dots,v_{l})$.
If $l<k$, we understand $v_{k:l}$ to be the zero-length null sequence. Given
finite-length bit strings $b\in\\{0,1\\}^{k},b^{\prime}\in\\{0,1\\}^{l}$, we
use $b\oplus b^{\prime}$ to denote the concatenation
$(b_{1},\dots,b_{k},b^{\prime}_{1},\dots,b^{\prime}_{l})\in\\{0,1\\}^{k+1}$.
We use $\mathsf{Uni}^{\mathcal{V}}$ to denote the uniform distribution over
$\mathcal{V}$. Formally, if $V\sim\mathsf{Uni}^{\mathcal{V}}$, then for any
$k\in\mathbb{N}$ and $b\in\\{0,1\\}^{k}$, $\mathbb{P}(v_{1:k}=b)=2^{-k}$. Also
for any $b\in\\{0,1\\}^{\star}$, we use $\mathsf{Uni}^{\mathcal{V}}_{b}$ to
denote the distribution $\mathsf{Uni}^{\mathcal{V}}$ conditioned on the event
that $b$ is a prefix. We will use the property that for any
$b\in\\{0,1\\}^{\star}$,
$\mathsf{Uni}^{\mathcal{V}}_{b}=\tfrac{1}{2}\mathsf{Uni}^{\mathcal{V}}_{b\oplus(0)}+\tfrac{1}{2}\mathsf{Uni}^{\mathcal{V}}_{b\oplus(1)}$.

##  2 Reduction from estimation to testing

We adapt the classical approach to information-theoretic lower bounds of
reducing estimation to testing—showing that if one can solve the estimation
problem (1), then one can distinguish between many distributions. Accordingly,
let $\\{P_{v}\\}_{v\in\mathcal{V}}$ be a family of probability distributions
and for each $v\in\mathcal{V}$, let $\mathbb{P}_{v}$ be the probability space
where $X_{1},X_{2},\dots\stackrel{{\scriptstyle\rm iid}}{{\sim}}P_{v}$. Under
this setting, we define the following time-uniform test:

######  Definition 2.1 ($(\alpha,\\{n_{k}\\}_{k\in\mathbb{N}})$-test).

A sequence of $\\{0,1\\}$-valued randomized tests
$\\{\hat{V}_{k}\\}_{k\in\mathbb{N}}$ is an _$(\alpha,\\{n_{k}\\})$ -test_ if
for all $v\in\mathcal{V}$,
$\mathbb{P}_{v}(\hat{V}_{k}(X_{1:n_{k}})=v_{k}\textrm{ for all
}k\in\mathbb{N})\geq 1-\alpha$.

The testing problem will be to find an $(\alpha,\\{n_{k}\\})$-test given
$\\{P_{v}\\}$. Conversely, we will show that if $\\{n_{k}\\}$ does not grow
fast enough, then no $(\alpha,\\{n_{k}\\})$-test can exist. By reducing the
original estimation problem (1) to this testing problem, the lower bound we
find on $\\{n_{k}\\}$ will confer lower bounds on $t(\cdot)$ for the original
testing problem.

###  2.1 Reduction from estimation to testing

We return to the estimation setting (1), where we have distributions
$\mathcal{P}$ and a parameter $\theta:\mathcal{P}\rightarrow\Theta$. For a
sub-family $\\{P_{v}\\}_{v\in\mathcal{V}}\subset\mathcal{P}$, say that
$\\{P_{v}\\}$ has parameter separation $\\{\delta_{k}\\}_{k\in\mathbb{N}}$ if
for all $k\in\mathbb{N}$ and all $v,v^{\prime}\in\mathcal{V}$ such that the
prefixes $v_{1:k}\neq v^{\prime}_{1:k}$, we have
$\delta_{k}\leq|\theta(P_{v})-\theta(P_{v^{\prime}})|$. This yields the
following proposition which reduces estimation to testing.

######  Proposition 1.

Suppose $\\{P_{v}\\}_{v\in\mathcal{V}}\subset\mathcal{P}$ has parameter
separation $\\{\delta_{k}\\}_{k\in\mathbb{N}}$ and $\hat{\theta}$ is an
$(\alpha,t(\cdot))$-estimator. Then for $n_{k}=\inf\\{n:t(n)<\delta_{k}/2\\}$
there exists an $(\alpha,\\{n_{k}\\})$-test.

Proof For ease of notation, we use $\theta(v)$ to denote $\theta(P_{v})$ and
use $\hat{\theta}_{n}$ to refer to $\hat{\theta}_{n}(X_{1:n})$. We now
construct a test sequence $\hat{V}=\\{\hat{V}_{k}\\}_{k\in\mathbb{N}}$. First
define the projection function

$\displaystyle\hat{v}(\vartheta)$ $\displaystyle=\mathop{\rm
argmin}_{v\in\mathcal{V}}|\vartheta-\theta(v)|,$

where we break potential ties arbitrarily, and then take
$\hat{V}_{k}(X_{1:n_{k}})=\hat{v}(\hat{\theta}_{n_{k}})_{k}.$

To see that $\hat{V}$ is an $(\alpha,\\{n_{k}\\})$-test sequence, let
$v\in\mathcal{V}$ and consider the event
$E=\cap_{n\in\mathbb{N}}\\{|\hat{\theta}_{n}-\theta(v)|\leq t(n)\\}$. By the
time-uniform utility of $\hat{\theta}$, $\mathbb{P}_{v}(E)\geq 1-\alpha$, and
so it suffices to show that on the event $E$, $\hat{V}_{k}=v_{k}$ for all
$k\in\mathbb{N}$. It follows by definition of $\hat{v}$ and $n_{k}$ that for
all $k\in\mathbb{N}$,

$\displaystyle|\hat{\theta}_{n_{k}}-\theta(\hat{v}(\hat{\theta}_{n_{k}}))|\leq|\hat{\theta}_{n_{k}}-\theta(v)|\leq
t(n_{k})<\tfrac{1}{2}\delta_{k}.$

Therefore, $|\theta(\hat{v}(\hat{\theta}_{n_{k}}))-\theta(v)|<\delta_{k}$ by
triangle inequality, which implies by the definition of $\delta_{k}$ that
$v_{1:k}=\hat{v}(\hat{\theta}_{n_{k}})_{1:k}$ and, in particular,
$v_{k}=\hat{v}(\hat{\theta}_{n_{k}})_{k}=\hat{V}_{k}$. ∎

###  2.2 Hardness of the testing problem

We say that $\\{P_{v}\\}$ has distribution closeness
$\\{\Delta_{k}\\}_{k\in\mathbb{N}}$ if for all $k\in\mathbb{N}$ and for all
$v,v^{\prime}\in\mathcal{V}$ such that $v_{1:k}=v^{\prime}_{1:k}$, we have
that $D_{\rm kl}\left({P_{v}}|\\!|{P_{v^{\prime}}}\right)\leq\Delta_{k}$.
Close distributions imply a lower bound on sequences $\\{n_{k}\\}$ for which
$(\alpha,\\{n_{k}\\})$-tests exist.

######  Theorem 1.

Suppose $\\{P_{v}\\}_{v\in\mathcal{V}}$ is a testing problem with distribution
closeness $\\{\Delta_{k}\\}$. If there exists an $(\alpha,\\{n_{k}\\})$-test,
then for infinitely many $k\in\mathbb{N}$,
$n_{k}>(1-\alpha)\Delta_{k}^{-1}\log k$

Combining Theorem 1 with Proposition 1 immediately gives a lower bound for the
time-uniform estimation problem.

######  Corollary 2.1.

Let $\mathcal{P}$ be a family of distributions and
$\theta:\mathcal{P}\rightarrow\mathbb{R}$ be a parameter function. Suppose
there exists a sub-family $\\{P_{v}\\}_{v\in\mathcal{V}}\subset\mathcal{P}$
with parameter separation $\\{\delta_{k}\\}$ and distribution closeness
$\\{\Delta_{k}\\}$. If there exists an $(\alpha,t(\cdot))$-estimator sequence,
then for infinitely many $k\in\mathbb{N}$,

$\displaystyle t\big{(}(1-\alpha)\Delta_{k}^{-1}\log
k\big{)}\geq\delta_{k}/2.$

Proof of Theorem 1 We first argue that we may take the tests to be
deterministic without loss of generality. Consider the augmented problem
setting of $\tilde{\mathcal{X}}=\mathcal{X}\times[0,1]$ and
$\tilde{P}_{v}=P_{v}\otimes\mathsf{Uni}([0,1])$, so sample is supplemented
with independent uniform randomness. Also define $\tilde{\mathbb{P}}_{v}$ as
the probability space corresponding to i.i.d. draws
$\tilde{X}_{1},\tilde{X}_{2},\dots$ from $\tilde{P}_{v}$.

We may express any randomized test $\hat{V}_{k}(X_{1:n_{k}})$ as a
deterministic function $f_{k}$ of $X_{1:n_{k}}$ and some independent noise
$U_{k}$ distributed according to $\mathsf{Uni}([0,1])$. Then, we construct the
deterministic test on $\tilde{\mathcal{X}}^{n_{k}}$ by
$\tilde{V}_{k}((X_{i},U_{i})_{1:n_{k}})=f_{k}(X_{1:n_{k}},U_{n_{k}})$.
Applying this for all $k\in\mathbb{N}$ yields a deterministic test-sequence
$\tilde{V}$ on $\mathcal{X}$ that has the same distribution as $\hat{V}$, and
so if $\hat{V}$ is an $(\alpha,t(\cdot))$-test, then so is $\tilde{V}$.
Finally, observe that $D_{\rm
kl}({\tilde{P}_{v}}|\\!|{\tilde{P}_{v^{\prime}}})=D_{\rm
kl}\left({P_{v}}|\\!|{P_{v^{\prime}}}\right)$ by chain rule of the KL-
divergence, so the family $\\{\tilde{P}_{v}\\}_{v\in\mathcal{V}}$ also has
distribution closeness $\\{\Delta_{k}\\}$. Therefore, proving the lower bound
for deterministic tests on $\\{\tilde{P}_{v}\\}_{v\in\mathcal{V}}$ will imply
the same lower bound for randomized tests on $\\{P_{v}\\}_{v\in\mathcal{V}}$.

We now define

$\displaystyle\mathsf{CondErr}(\tilde{V},v,k):=\tilde{\mathbb{P}}_{v}(\tilde{V}_{k}\neq
v_{k}\mid\tilde{V}_{1:k-1}=v_{1:k-1}),$

which is the probability an $(\alpha,\\{n_{k}\\})$-test $\tilde{V}$ makes an
error at test $k$ conditioned on the event that all previous tests were
correct. The following lemma gives a lower bound on
$\mathsf{CondErr}(\tilde{V},v,k)$ over uniform distributions:

######  Lemma 2.1.

Let $\tilde{V}$ be a deterministic $(\alpha,\\{n_{k}\\})$-test sequence for
the testing problem $\\{\tilde{P_{v}}\\}$. For all $k\in\mathbb{N}$ and all
$b\in\\{0,1\\}^{k-1}$,

$\displaystyle\int\mathsf{CondErr}(\tilde{V},v,k)d\mathsf{Uni}^{\mathcal{V}}_{b}(v)\geq\frac{1}{4}\exp\left(-\frac{\Delta_{k}n_{k}}{1-\alpha}\right).$

Proof Because for each $j\in\mathbb{N}$, $\tilde{V}_{j}$ is a deterministic
function of $\tilde{X}_{1:n_{j}}$, for each $b^{\prime}\in\\{0,1\\}^{j}$ we
may define a set $A_{b^{\prime}}\subset\tilde{\mathcal{X}}^{n_{j}}$ such that
$\\{\tilde{V}_{1:j}=b^{\prime}\\}=\\{\tilde{X}_{1:n_{j}}\in
A_{b^{\prime}}\\}$. Let $\mathcal{V}_{b}=\\{v\in\mathcal{V}\mid
v_{1:k-1}=b\\}$ and note that $\mathcal{V}_{b}$ is the support of
$\mathsf{Uni}^{\mathcal{V}}_{b}$. For all $v\in\mathcal{V}_{b}$, we thus have
the following equality of events in $\tilde{\mathbb{P}}_{v}$:

$\\{\tilde{V}_{1:k-1}=v_{1:k-1}\\}=\\{\tilde{V}_{1:k-1}=b\\}=\\{\tilde{X}_{1:n_{k-1}}\in
A_{b}\\}=\\{\tilde{X}_{1:n_{k}}\in
A_{b}\times\tilde{\mathcal{X}}^{n_{k}-n_{k-1}}\\}.$ (2)

Define
$S:=A_{b}\times\tilde{\mathcal{X}}^{n_{k}-n_{k-1}}\subset\tilde{\mathcal{X}}^{n_{1}}$
and notice that $A_{b\oplus(0)},A_{b\oplus(1)}$ are relative complements in
$S$. Then because
$\mathsf{Uni}^{\mathcal{V}}_{b}=\frac{1}{2}\mathsf{Uni}^{\mathcal{V}}_{b\oplus(0)}+\frac{1}{2}\mathsf{Uni}^{\mathcal{V}}_{b\oplus(1)}$,
we get

$\displaystyle\int\mathsf{CondErr}(\tilde{V},v,k)$ $\displaystyle
d\mathsf{Uni}^{\mathcal{V}}_{b}(v)=\int\tilde{\mathbb{P}}_{v}(\tilde{V}_{k}\neq
v_{k}\mid\tilde{V}_{k-1}=v_{k-1})d\mathsf{Uni}^{\mathcal{V}}_{b}(v)$
$\displaystyle=\frac{1}{2}\int\tilde{\mathbb{P}}_{v}(\tilde{V}_{k}=1\mid\tilde{V}_{k-1}=v_{k-1})d\mathsf{Uni}^{\mathcal{V}}_{b\oplus(0)}(v)$
$\displaystyle\quad+\frac{1}{2}\int\tilde{\mathbb{P}}_{v}(\tilde{V}_{k}=0\mid\tilde{V}_{k-1}=v_{k-1})d\mathsf{Uni}^{\mathcal{V}}_{b\oplus(1)}(v)$
$\displaystyle\stackrel{{\scriptstyle(\star)}}{{=}}\frac{1}{2}\int\tilde{\mathbb{P}}_{v}(\tilde{X}_{1:n_{k}}\in
A_{b\oplus(1)}\mid\tilde{X}_{1:n_{k}}\in
S)d\mathsf{Uni}^{\mathcal{V}}_{b\oplus(0)}(v)$
$\displaystyle\quad+\frac{1}{2}\int\tilde{\mathbb{P}}_{v}(\tilde{X}_{1:n_{k}}\in
A_{b\oplus(0)}\mid\tilde{X}_{1:n_{k}}\in
S)d\mathsf{Uni}^{\mathcal{V}}_{b\oplus(1)}(v)$
$\displaystyle\begin{split}&=\frac{1}{2}\int\tilde{P}_{v}^{n_{k}}(A_{b\oplus(1)}\mid
S)d\mathsf{Uni}^{\mathcal{V}}_{b\oplus(0)}(v)\\\
&\quad+\frac{1}{2}\int\tilde{P}_{v}^{n_{k}}(A_{b\oplus(0)}\mid
S)d\mathsf{Uni}^{\mathcal{V}}_{b\oplus(1)}(v),\end{split}$ (3)

where equality $(\star)$ follows from the identity (2).

To proceed, we use Le Cam’s method and the Bretagnolle-Huber inequality below
(see, e.g. Yu [19, Lemma 1] and Tsybakov [17, Lemma 2.6] for proofs):

######  Lemma 2.2 (Le Cam’s method).

Let $P,Q$ be distributions over a domain $\mathcal{X}$. For any
$S\subset\mathcal{X}$,

$\displaystyle P(S)+Q(S^{c})\geq
1-\sup_{S}(Q(S)-P(S))=1-\left\|{P-Q}\right\|_{\rm TV}.$

######  Lemma 2.3 (Bretagnolle-Huber).

Let $P,Q$ be distributions over a domain $\mathcal{X}$. Then

$\displaystyle\left\|{P-Q}\right\|_{\rm TV}\leq 1-\frac{1}{2}\exp(-D_{\rm
kl}\left({P}|\\!|{Q}\right)).$

Applying Lemma 2.2 to Eq. (3) implies the lower bound

$\displaystyle\int\mathsf{CondErr}(\tilde{V},v,k)d\mathsf{Uni}^{\mathcal{V}}_{b}(v)$
$\displaystyle\qquad\geq\frac{1}{2}\left(1-\left\|{\int\tilde{P}_{v}^{n_{k}}(\cdot\mid
S)d\mathsf{Uni}^{\mathcal{V}}_{b\oplus(0)}(v)-\int\tilde{P}_{v}^{n_{k}}(\cdot\mid
S)d\mathsf{Uni}^{\mathcal{V}}_{b\oplus(1)}(v)}\right\|_{\rm TV}\right).$

Then applying Lemma 2.3 and using the convexity of the KL-divergence, we
obtain the lower bound

$\displaystyle\int\mathsf{CondErr}(\tilde{V},v,k)d\mathsf{Uni}^{\mathcal{V}}_{b}(v)$
$\displaystyle\geq\frac{1}{4}\exp\bigg{(}-\sup_{v,v^{\prime}\in\mathcal{V}_{b}}D_{\rm
kl}\left({\tilde{P}_{v}^{n_{k}}(\cdot\mid
S)}|\\!|{\tilde{P}_{v^{\prime}}^{n_{k}}(\cdot\mid S)}\right)\bigg{)}.$ (4)

To conclude the proof, we use the following lemma to bound the KL-divergence
between conditional distributions:

######  Lemma 2.4 (KL-divergence of conditional distributions).

Let $P,Q$ be two distributions over a domain $\mathcal{X}$. Let $S$ be a
measurable subset of $\mathcal{X}$, and let $P_{S},Q_{S}$ denote the
conditional distributions of $P$ given $S$ and $Q$ given $S$, respectively.
Then $D_{\rm kl}\left({P_{S}}|\\!|{Q_{S}}\right)\leq\frac{1}{P(S)}D_{\rm
kl}\left({P}|\\!|{Q}\right)$.

Proof Let $p,q$ be the densities of $P$ and $Q$ respectively with respect to a
dominating measure $\mu$. Then $dP_{S}/d\mu=\frac{1}{P(S)}p1_{S}$ and
$dQ_{S}/d\mu=\frac{1}{Q(S)}q1_{S}$. We then have

$\displaystyle D_{\rm kl}\left({P_{S}}|\\!|{Q_{S}}\right)$
$\displaystyle=\int\frac{p}{P(S)}1_{S}\log\left(\frac{p/P(S)}{q/Q(S)}\right)d\mu$
$\displaystyle=\frac{1}{P(S)}\int p\log(p/q)1_{S}d\mu+\log(Q(S)/P(S))$
$\displaystyle=\frac{1}{P(S)}D_{\rm
kl}\left({P}|\\!|{Q}\right)+\log(Q(S)/P(S))+\frac{1}{P(S)}\int
p\log(q/p)1_{S^{c}}d\mu.$

As $\log(q/p)=\log(1+(q-p)/p)\leq(q-p)/p$,

$\displaystyle D_{\rm kl}\left({P_{S}}|\\!|{Q_{S}}\right)$
$\displaystyle\leq\frac{1}{P(S)}D_{\rm
kl}\left({P}|\\!|{Q}\right)+\log(Q(S)/P(S))+\frac{1}{P(S)}\int(q-p)1_{S^{c}}d\mu$
$\displaystyle=\frac{1}{P(S)}D_{\rm
kl}\left({P}|\\!|{Q}\right)+\log(Q(S)/P(S))+\frac{P(S)-Q(S)}{P(S)}.$

Again using the inequality $\log(p/q)\leq(q-p)/p$ proves the claim. ∎

By applying Lemma 2.4 and the assumption $D_{\rm
kl}\left({\tilde{P}_{v}}|\\!|{\tilde{P}_{v^{\prime}}}\right)\leq\Delta_{k}$,
we have

$\displaystyle\sup_{v,v^{\prime}\in\mathcal{V}_{b}}D_{\rm
kl}\left({\tilde{P}_{v}^{n_{k}}(\cdot\mid
S)}|\\!|{\tilde{P}_{v^{\prime}}^{n_{k}}(\cdot\mid S)}\right)$
$\displaystyle\leq\sup_{v,v^{\prime}\in\mathcal{V}_{b}}\frac{D_{\rm
kl}\left({\tilde{P}_{v}^{n_{k}}}|\\!|{\tilde{P}_{v^{\prime}}^{n_{k}}}\right)}{\tilde{P}_{v}^{n_{k}}(S)}\leq\frac{\Delta_{k}n_{k}}{1-\alpha}.$

Substituting this into Eq. (4) proves Lemma 2.1. ∎

Iteratively applying Lemma 2.1, we obtain a lower bound on the cumulative
conditional errors:

######  Lemma 2.5.

Let $\tilde{V}$ be a deterministic $(\alpha,\\{n_{k}\\})$-test sequence for
the testing problem $\\{\tilde{P_{v}}\\}$. For all $\ell\in\mathbb{N}$, there
exists a distribution $b\in\\{0,1\\}^{\ell-1}$ such that

$\displaystyle\int\sum_{k=1}^{\ell}\mathsf{CondErr}(\tilde{V},v,k)d\mathsf{Uni}^{\mathcal{V}}_{b}(v)\geq\frac{1}{4}\sum_{k=1}^{\ell}\exp\left(-\frac{\Delta_{k}n_{k}}{1-\alpha}\right).$

Proof We proceed inductively.

Base Case ($\ell=1$). This case follows immediately by applying Lemma 2.1 with
$k=1$.

Inductive step. Let $\ell\geq 2$. Assume the claim holds for $\ell-1$ and let
$b^{\prime}\in\\{0,1\\}^{\ell-2}$ such that

$\displaystyle\int\sum_{k=1}^{\ell-1}\mathsf{CondErr}(\tilde{V},v,k)d\mathsf{Uni}^{\mathcal{V}}_{b^{\prime}}(v)\geq\frac{1}{4}\sum_{k=1}^{\ell-1}\exp\left(-\frac{\Delta_{k}n_{k}}{1-\alpha}\right).$
(5)

It will suffice to find $b\in\\{0,1\\}^{\ell-1}$ that satisfies both

$\displaystyle\int\sum_{k=1}^{\ell-1}\mathsf{CondErr}(\tilde{V},v,k)d\mathsf{Uni}^{\mathcal{V}}_{b}(v)\geq\frac{1}{4}\sum_{k=1}^{\ell-1}\exp\left(-\frac{\Delta_{k}n_{k}}{1-\alpha}\right)$
(6)

and

$\displaystyle\int\mathsf{CondErr}(\tilde{V},v,k)d\mathsf{Uni}^{\mathcal{V}}_{b}(v)\geq\frac{1}{4}\exp\left(-\frac{\Delta_{\ell}n_{\ell}}{1-\alpha}\right).$
(7)

Because
$\mathsf{Uni}^{\mathcal{V}}_{b^{\prime}}=\frac{1}{2}\mathsf{Uni}^{\mathcal{V}}_{b^{\prime}\oplus(0)}+\frac{1}{2}\mathsf{Uni}^{\mathcal{V}}_{b^{\prime}\oplus(1)}$,
the inductive hypothesis (Eq. (5)) implies

$\displaystyle\max_{i\in\\{0,1\\}}\int\sum_{k=1}^{\ell-1}\mathsf{CondErr}(\tilde{V},v,k)d\mathsf{Uni}^{\mathcal{V}}_{b^{\prime}\oplus(i)}(v)\geq\frac{1}{4}\sum_{k=1}^{\ell-1}\exp\left(-\frac{\Delta_{k}n_{k}}{1-\alpha}\right).$
(8)

Let $i\in\\{0,1\\}$ be any bit obtaining the maximum in the left-hand side of
Eq. (8). By taking $b=b^{\prime}\oplus(i)$, we ensure that $b$ satisfies Eq.
(6). Applying Lemma 2.1 with $k=\ell$, we also have that $b$ satisfies Eq.
(7). This completes the induction and proves the claim. ∎

Conversely, the time-uniform conditions on $\tilde{V}$ yield an upper-bound on
the sum of $\mathsf{CondErr}$.

######  Lemma 2.6.

Let $\tilde{V}$ be an $(\alpha,\\{n_{k}\\})$-test sequence. For all
$v\in\mathcal{V}$,

$\displaystyle\sum_{k=1}^{\infty}\mathsf{CondErr}(\tilde{V},v,k)\leq\frac{\alpha}{1-\alpha}.$
(9)

Proof By definition of $\hat{V}$, $\mathbb{P}_{v}(\hat{V}_{1:k}=v_{1:k})\geq
1-\alpha$ for all $v\in\mathcal{V}$ and all $k\in\mathbb{N}$. Furthermore, for
$v\in\mathcal{V}$,

$\displaystyle\mathbb{P}_{v}(\hat{V}_{1:k}=v_{1:k})$
$\displaystyle=\mathbb{P}_{v}(\hat{V}_{1:k-1}=v_{1:k-1})\mathbb{P}_{v}(\hat{V}_{k}=v_{k}\mid\hat{V}_{1:k-1}=v_{1:k-1})$
$\displaystyle=\mathbb{P}_{v}(\hat{V}_{1:k-1}=v_{1:k-1})-\mathbb{P}_{v}(\hat{V}_{1:k-1}=v_{1:k-1})\mathbb{P}_{v}(\hat{V}_{k}\neq
v_{k}\mid\hat{V}_{1:k-1}=v_{1:k-1})$
$\displaystyle\leq\mathbb{P}_{v}(\hat{V}_{1:k-1}=v_{1:k-1})-(1-\alpha)\mathsf{CondErr}(\hat{V},v,k).$

Iterating the above inequality thus yields
$\mathbb{P}_{v}(\hat{V}_{1:k}=v_{1:k})\leq
1-(1-\alpha)\sum_{j=1}^{k}\mathsf{CondErr}(\hat{V},v,j)$. Because
$\mathbb{P}_{v}(\hat{V}_{1:k}=v_{1:k})\geq 1-\alpha$, we have that
$\sum_{j=1}^{k}\mathsf{CondErr}(\hat{V},v,j)\leq\frac{\alpha}{1-\alpha}$.
Taking $k\rightarrow\infty$ proves the result. ∎

Combining Lemmas 2.5 and 2.6, we obtain

$\displaystyle\frac{1}{4}\sum_{k=1}^{\infty}\exp\left(-\frac{\Delta_{k}n_{k}}{1-\alpha}\right)\leq\frac{\alpha}{1-\alpha}.$

Theorem 1 therefore follows because the summability of the sequence implies
that $\exp(-\frac{\Delta_{k}n_{k}}{1-\alpha})<\frac{1}{k}$, or $\log
k<\frac{\Delta_{k}n_{k}}{1-\alpha}$, infinitely often. ∎

##  3 Applying the lower bound

The abstract theorem and Corollary 2.1 combine to yield a fairly
straightforward recipe for proving lower bounds for time-uniform estimation
problems. For a parametric model $\\{P_{\theta}\\}_{\theta\in\Theta}$, where
$\Theta\subset\mathbb{R}$, the basic idea proceeds in three steps:

  1. 1.

Demonstrate the (typical) scaling that $D_{\rm
kl}\left({P_{\theta}}|\\!|{P_{\theta^{\prime}}}\right)\leq
M(\theta-\theta^{\prime})^{2}$ for some $M<\infty$

  2. 2.

Develop a particular well-separated collection of parameters
$\\{\theta(v)\\}\subset\Theta$ by, for $v\in\mathcal{V}$, writing a trinary
expansion of $\theta(v)=2\sum_{i=1}^{\infty}v_{i}3^{-i}$, which guarantees
that if $v,v^{\prime}$ first disagree at position $k$, then $D_{\rm
kl}\left({P_{\theta}}|\\!|{P_{\theta^{\prime}}}\right)\lesssim(3^{-k})^{2}$,
while $|\theta(v)-\theta(v^{\prime})|\gtrsim 3^{-k}$.

  3. 3.

Apply Corollary 2.1.

This approach is familiar from classical “two-point” lower bounds that rely on
reducing estimation to testing [e.g. 19, 5]. The quadratic scaling of the KL-
divergence is indeed common: in (essentially) any setting in which the Fisher
Information $I_{\theta}$ of the model $\\{P_{\theta}\\}$ exists, classical
information geometry considerations show that $D_{\rm
kl}\left({P_{\theta}}|\\!|{P_{\theta^{\prime}}}\right)=\frac{1}{2}I_{\theta}(\theta^{\prime}-\theta)^{2}+o(|\theta^{\prime}-\theta|^{2})$,
[see, e.g., 3, Exercise 11.7]. Our lower bounds require the quadratic bound
only locally, so we expect them to apply in most estimation problems.

Let us formalize these steps. Let $\Theta$ be a convex subset of $\mathbb{R}$
and $\theta_{0}\in\Theta$, and let $r>0$ be (a radius) such that
$[\theta_{0},\theta_{0}+r]\subset\Theta$. To apply the lower bound, we wish to
choose a parameter mapping $\theta:\mathcal{V}\rightarrow\Theta$ to maximize
the parameter separation $\\{\delta_{k}\\}$ while minimizing the distribution
closeness $\\{\Delta_{k}\\}$. In our parametric setting, given a mapping
$\theta:\mathcal{V}\rightarrow\Theta$, we can take

$\displaystyle\delta_{k}=\inf_{v_{1:k}\neq
v^{\prime}_{1:k}}|\theta(v)-\theta(v^{\prime})|~{}~{}~{}\qquad\textrm{and}\qquad~{}~{}~{}\Delta_{k}=\sup_{v_{1:k}=v^{\prime}_{1:k}}M(\theta(v)-\theta(v^{\prime}))^{2}.$

To that end, we take a shifted Cantor set mapping

$\theta(v)=\theta_{0}+r\cdot 2\sum_{i=1}^{\infty}v_{i}3^{-i},$

where by inspection $\theta(v)\in[\theta_{0},\theta_{0}+r]\subset\Theta$.
Upper and lower bounds on $|\theta(v)-\theta(v^{\prime})|$ for
$v,v^{\prime}\in\mathcal{V}$ are then immediate. Indeed, letting
$v,v^{\prime}\in\mathcal{V}$ differ for the first time at index $k$,

$\displaystyle|\theta(v)-\theta(v^{\prime})|=2r\left|\sum_{i=k}^{\infty}(v_{i}-v_{i}^{\prime})3^{-i}\right|$
$\displaystyle=2r\cdot
3^{-k}\left|\sum_{i=0}^{\infty}(v_{i+k}-v_{i+k}^{\prime})3^{-i}\right|$
$\displaystyle\leq 2r\cdot 3^{-k}\sum_{i=0}^{\infty}3^{-i}=3^{1-k}r.$

So long as the KL-bound $D_{\rm
kl}\left({P_{\theta_{0}}}|\\!|{P_{\theta_{0}+\delta}}\right)\leq M\delta^{2}$
holds for $\delta\leq\frac{2}{3}r$, whenever $v_{1:k}=v^{\prime}_{1:k}$ we
have $|\theta(v)-\theta(v^{\prime})|\leq 3^{-k}r$, and we may thus choose
distributional closeness

$\Delta_{k}=M9^{-k}r^{2}.$

On the other hand, when $v,v^{\prime}$ differ for the first time in index $k$,
then again by the triangle inequality,

$\displaystyle|\theta(v)-\theta(v^{\prime})|$ $\displaystyle\geq 2r\cdot
3^{-k}\bigg{(}|v_{k}-v_{k}^{\prime}|-\bigg{|}\sum_{i=1}^{\infty}(v_{i+k}-v_{i+k}^{\prime})3^{-i}\bigg{|}\bigg{)}\geq
3^{-k}r$

because $v_{k}\neq v_{k}^{\prime}$. Therefore, if $v_{1:k}\neq
v^{\prime}_{1:k}$, then $|\theta(v)-\theta(v^{\prime})|\geq 3^{-k}r$ and so we
may take the parameter separation $\delta_{k}=3^{-k}r$. Applying Corollary 2.1
thus yields the following proposition.

######  Proposition 2.

Let $\Theta\subset\mathbb{R}$ be convex and the family
$\\{P_{\theta}\\}_{\theta\in\Theta}$ be such that for some $r>0$ and
$\theta_{0}\in\Theta$ with $[\theta_{0},\theta_{0}+r]\in\Theta$, $D_{\rm
kl}\left({P_{\theta_{0}}}|\\!|{P_{\theta_{0}+\delta}}\right)\leq M\delta^{2}$
for $\delta\leq r$. Then any $(\alpha,t(\cdot))$-estimator sequence satisfies

$t(n)\geq\sqrt{\frac{1-\alpha}{8M}}\cdot\sqrt{\frac{\log\log n}{n}}$

infinitely often.

Proof By Corollary 2.1, if there exists an $(\alpha,t(\cdot))$-estimator, then
for $N_{k}=(1-\alpha)\Delta_{k}^{-1}\log k$, we use the identification of the
distributional closeness $\Delta_{k}=M\delta_{k}^{2}$ with the squared
parameter separation to obtain

$\displaystyle
t(N_{k})\geq\frac{1}{2}\delta_{k}=\frac{1}{2}\sqrt{\frac{\Delta_{k}}{M}}=\frac{1}{2}\sqrt{\frac{(1-\alpha)\log
k}{MN_{k}}}$

for infinitely many $k\in\mathbb{N}$. Because
$N_{k}=\frac{1-\alpha}{Mr^{2}}9^{k}\log k$, for any sufficiently large
$k\in\mathbb{N}$, we have both $N_{k}\leq 10^{k}$ and $\log\log N_{k}\leq\log
k+\log\log 10\leq 2\log k$, or $\log k\geq\frac{1}{2}\log\log N_{k}$. Taking
$n$ from among the indices $\\{N_{k}\\}_{k\in\mathbb{N}}$, we thus have

$\displaystyle t(n)\geq\frac{1}{2}\sqrt{\frac{(1-\alpha)\log\log n}{2Mn}}$

infinitely often. ∎

While Proposition 2 demonstrates the $\log\log n$ penalty of time-uniform
estimation, a more standard technique demonstrates the correct dependence on
the confidence $\alpha$.

######  Proposition 3.

Let the conditions of Propositon 2 hold. Then for $\alpha<\frac{1}{4}$, any
$(\alpha,t(\cdot))$-estimator sequence satisfies

$\displaystyle
t(n)\geq\frac{1}{2}\sqrt{\frac{\log(1/4\alpha)}{Mn}}~{}~{}\mbox{for~{}all~{}}n\in\mathbb{N}.$

As the proof is a more-or-less standard two point lower bound, we defer it to
Section 5.

###  3.1 Location models

We first demonstrate how the recipe above applies to obtain lower bounds on
(time-uniformly) estimating the parameter of a location model without
particular reliance on the structure of the family beyond mild integrability
conditions. Let $f$ be a density on $\mathbb{R}$, and consider the family
$\\{P_{\theta}\\}_{\theta\in\mathbb{R}}$ with densities of the form $x\mapsto
f(x-\theta)$. Then under appropriate integrability conditions on the
derivatives of the density, the Fisher Information
$I_{\theta}=\int\frac{f^{\prime}(x-\theta)^{2}}{f(x-\theta)}dx$ is constant
[15], and we also have the following quadratic expansion [e.g. 12, Section
2.6].

######  Lemma 3.1.

For sufficiently regular location families, $D_{\rm
kl}\left({P_{\theta}}|\\!|{P_{\theta^{\prime}}}\right)=\frac{1}{2}I_{\theta}(\theta-\theta^{\prime})^{2}+o((\theta-\theta^{\prime})^{2})$.

Example 1 (Location families from regular densities): Let $f$ be a suitably
regular density with Fisher Information
$I_{f}=\int\frac{f^{\prime}(x)^{2}}{f(x)}dx$. We may take $M=\frac{1}{2}I_{f}$
in Proposition 2, and so for any $(\alpha,t(\cdot))$-estimator,
$t(n)\geq\frac{1}{2}\sqrt{\frac{(1-\alpha)\log\log n}{I_{f}\cdot n}}$
infinitely often. $\Diamond$

We can be more explicit when it is easy to compute the KL-divergence.

Example 2 (Gaussian location model): Consider
$f(x)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-x^{2}/2\sigma^{2}}$. Then for
$P_{\theta}=\mathsf{N}(\mu,\sigma^{2})$, we have $D_{\rm
kl}\left({P_{\theta}}|\\!|{P_{\theta^{\prime}}}\right)=\frac{1}{2\sigma^{2}}(\theta-\theta^{\prime})^{2}$,
and so taking $M=\frac{1}{2\sigma^{2}}$ Proposition 2 yields that for any
$(\alpha,t(\cdot))$-estimator,
$t(n)\geq\frac{\sigma}{2}\sqrt{\frac{(1-\alpha)\log\log n}{n}}$ infinitely
often. $\Diamond$

Example 3 (Cauchy location model): Consider the density
$p_{\theta}(x)=1/(\pi\sigma[1+(\frac{x-\theta}{\sigma})^{2}])$. Then Chyzak
and Nielsen [2, Theorem 1] show that

$D_{\rm
kl}\left({P_{\theta}}|\\!|{P_{\theta^{\prime}}}\right)=\log\left(1+\frac{(\mu-\mu^{\prime})^{2}}{4\sigma^{2}}\right)\leq\frac{(\mu-\mu^{\prime})^{2}}{4\sigma^{2}},$

and so in Proposition 2 we take $M=\frac{1}{4\sigma^{2}}$ to obtain that for
any $(\alpha,t(\cdot))$-estimator,
$t(n)\geq\sigma\sqrt{\frac{(1-\alpha)\log\log n}{2n}}$ infinitely often.
$\Diamond$

###  3.2 Generalized linear models

We can demonstrate similar lower bounds as those Section 3.1 for a family of
one-parameter conditional models. Consider two domains $\mathcal{X}$ and
$\mathcal{Y}$. Let $Q$ be a distribution over $\mathcal{X}$, $\mu$ be a
reference measure over $\mathcal{Y}$, and
$T:\mathcal{Y}\times\mathcal{X}\rightarrow\mathbb{R}$ be a statistic of $y$
given $x$. We define the conditional exponential family model, or one-
parameter generalized linear model,

$p_{\theta}(y\mid x)=\exp\left(\theta T(y,x)-A(\theta\mid
x)\right)~{}~{}\mbox{where}~{}~{}A(\theta\mid
x)=\log\int_{\mathcal{Y}}\exp(\theta T(y\mid x))d\mu(y)$ (10)

and $p_{\theta}$ is a density with respect to $\mu$. Then we define
$P_{\theta}$ over $\mathcal{X}\times\mathcal{Y}$ such
$P_{\theta}(X\in\cdot)=Q$ and $P_{\theta}(Y\in\cdot\mid X=x)$ has density
$p_{\theta}(y|x)$ with respect to $\mu$. The log-partition function
$A(\theta\mid x)$ is analytic on its open convex domain [1], and

$\displaystyle D_{\rm kl}\left({P_{\theta}}|\\!|{P_{\theta^{\prime}}}\right)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\mathbb{E}_{X\sim
Q}\left[D_{\rm kl}\left({P_{\theta}(Y\in\cdot\mid
X)}|\\!|{P_{\theta^{\prime}}(Y\in\cdot\mid X)}\right)\right]$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}\mathbb{E}_{X\sim
Q}\left[A(\theta^{\prime}\mid X)-A(\theta\mid X)-A^{\prime}(\theta\mid
X)(\theta^{\prime}-\theta)\right],$

where equality $(i)$ follows from the chain rule and equality $(ii)$ is an
immediate calculation for exponential family models. Recognizing the Bregman
divergence between $\theta$ and $\theta^{\prime}$ according to the (convex)
log-partition function $A(\cdot\mid x)$ in this last display, for all
$\theta,\theta+\delta\in\mathop{\rm dom}A(\cdot\mid x)$ we obtain

$D_{\rm kl}\left({P_{\theta}(Y\in\cdot\mid
x)}|\\!|{P_{\theta+\delta}(Y\in\cdot\mid
x)}\right)=\frac{1}{2}A^{\prime\prime}(\theta+t\mid x)\delta^{2}$

for some $t\in[0,\delta]$. Because $A^{\prime\prime}(\theta\mid x)={\rm
Var}_{\theta}(Y\mid X=x)$ in the conditional model (10), Proposition 2 implies
the following corollary.

######  Corollary 3.1.

Assume the expected variance $\mathbb{E}[{\rm Var}_{\theta}(Y\mid X)]$ is
continuous and finite in a neighborhood of some $\theta_{0}$ in the one-
parameter GLM (10). Let $M=\mathbb{E}[{\rm Var}_{\theta_{0}}(Y\mid X)]$. Then
any $(\alpha,t(\cdot))$-estimator satisfies

$t(n)\geq\frac{1}{4}\sqrt{\frac{(1-\alpha)\log\log
n}{Mn}}~{}~{}\mbox{infinitely often}.$

Proof Let $M_{\theta}=\mathbb{E}[{\rm Var}_{\theta}(Y\mid X)]$. Then by
continuity and Taylor’s theorem, $D_{\rm
kl}\left({P_{\theta_{0}}}|\\!|{P_{\theta_{0}+\delta}}\right)=\frac{1}{2}\mathbb{E}[A^{\prime\prime}(\theta_{0}+t\delta\mid
X)]\delta^{2}$ for some $t\in[0,1]$. Using continuity, there exists a
neighborhood of $\theta_{0}$ such that $M_{\theta}\leq 2M$ for all $\theta$ in
the neighborhood. ∎

We can make these calculations explicit for logistic regression:

Example 4 (Logistic regression): Take $\mathcal{X}=\mathbb{R}$,
$\mathcal{Y}=\\{-1,1\\}$, $\mu$ to be the counting measure on $\mathcal{Y}$
and $T(y,x)=yx$. Then the log-partition $A(\theta\mid
x)=\log(e^{-x\theta}+e^{x\theta})$ satisfies

$\displaystyle A^{\prime}(\theta\mid
x)=\frac{x(e^{x\theta}-e^{-x\theta})}{e^{-x\theta}+e^{x\theta}}~{}~{}\mbox{and}~{}~{}A^{\prime\prime}(\theta\mid
x)=x^{2}-\frac{x^{2}(e^{x\theta}-e^{-x\theta})^{2}}{(e^{-x\theta}+e^{x\theta})^{2}}\leq
x^{2}.$

Taking $M=\mathbb{E}[X^{2}]$, any $(\alpha,t(\cdot))$-estimator for $\theta$
satisfies $t(n)\geq\frac{1}{4}\sqrt{\frac{(1-\alpha)\log\log
n}{\mathbb{E}[X^{2}]n}}$ infinitely often. $\Diamond$

##  4 Attaining the lower bound

Via a suitable doubling strategy, we can demonstrate that estimators achieving
high-probability convergence guarantees for fixed sample sizes essentially
immediately provide time-uniform guarantees with an additional $\log\log n$
penalty matching our lower bounds. Suppose we are given a sequence of
estimators $\hat{\theta}_{n}$. We then consider the _time uniform_ estimator-
sequence

$\displaystyle\hat{\theta}^{\textup{tu}}_{n}$
$\displaystyle\coloneqq\hat{\theta}_{2^{\left\lfloor{\log_{2}n}\right\rfloor}}=\begin{cases}\hat{\theta}_{n}(X_{1:n})&~{}\mbox{if}~{}n=2^{k},\textrm{
for some }k\in\mathbb{N}\\\
\hat{\theta}^{\textup{tu}}_{n-1}&\textrm{otherwise},\end{cases}$ (11)

so that $\hat{\theta}^{\textup{tu}}$ is $\hat{\theta}_{n}$ evaluated at the
most recent power of two sample size. The next proposition shows that so long
as $\hat{\theta}$ is sufficiently accurate, $\hat{\theta}^{\textup{tu}}_{n}$
is a time-uniform estimator. In stating the proposition, we say that
$\hat{\theta}$ has _high-probability deviation bound $F$_ for
$F:\mathbb{R}_{+}\times\mathbb{N}\to\mathbb{R}_{+}$ if

$\mathbb{P}\left(|\hat{\theta}_{n}(X_{1:n})-\theta(P)|\leq
F(\log(1/\alpha),n)\right)\geq
1-\alpha~{}~{}\mbox{for~{}all~{}}\alpha\in[0,1],~{}n\in\mathbb{N},$

where $F$ is increasing in its first argument and decreasing in its second. In
typical cases, such as mean estimation for a sub-Gaussian distribution, we
expect $F(t,n)=C\sqrt{t/n}$ for some $C$.

######  Proposition 4.

Let $\hat{\theta}_{n}$ have high probability deviation bound $F$. Then
$\\{\hat{\theta}^{\textup{tu}}_{n}\\}$ is an $(\alpha,t(\cdot))$-estimator for

$t(n)=F\big{(}2\log\log_{2}n+\log(1/\alpha)+1/2,n/2\big{)}.$

Proof Let $E$ denote the event that for all $k\in\mathbb{N}$,
$|\hat{\theta}_{2^{k}}-\theta(P)|\leq F(\log(\pi^{2}k^{2}/6\alpha),2^{k})$. By
a union bound and definition of the deviation function,
$\mathbb{P}(E^{c})\leq\frac{6}{\pi^{2}}\sum_{k=1}^{\infty}\frac{\alpha}{k^{2}}=\alpha$
by the Basel problem, so $E$ occurs with probability at least $1-\alpha$. Now
for $n\in\mathbb{N}$, let $k=k_{n}=\left\lfloor{\log_{2}n}\right\rfloor$ be
the unique natural number such that $2^{k}\leq n<2^{k+1}$. By definition,
$\hat{\theta}_{n}=\hat{\theta}_{2^{k}}$ and so on $E$,

$\displaystyle|\hat{\theta}^{\textup{tu}}_{n}-\theta(P)|\leq
F\left(\log\frac{\pi^{2}k^{2}}{6\alpha},2^{k}\right)$

for all $n$. Now use that $k\leq\log_{2}n$ that $\log k^{2}=2\log k\leq
2\log\log_{2}n$, $\log\frac{\pi^{2}}{6}<\frac{1}{2}$, and that $F$ is
decreasing in its second argument and $2^{k}>n/2$. ∎

As a simple example, consider estimating a sub-Gaussian mean:

Example 5 (Sub-Gaussian mean estimation): Let $X_{i}\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P$ be $\sigma^{2}$-sub-Gaussian with unknown mean
$\theta=\theta(P)$, meaning that
$\mathbb{E}[e^{\lambda(X-\theta)}]\leq\exp(\frac{\lambda^{2}\sigma^{2}}{2})$
for all $\lambda\in\mathbb{R}$. Then standard concentration guarantees [e.g.
18, Ch. 2] for the sample mean
$\hat{\theta}_{n}(X_{1:n})=\frac{1}{n}\sum_{i=1}^{n}X_{i}$ yield
$\mathbb{P}(|\hat{\theta}_{n}-\theta|\geq t)\leq
2\exp(-\frac{nt^{2}}{2\sigma^{2}})$, that is, $\hat{\theta}_{n}$ has high
probability deviation bound
$F(\log\frac{1}{\alpha},n)=\sqrt{\frac{2\sigma^{2}\log(2/\alpha)}{n}}$. Then
the time-uniform estimator (11) is an $(\alpha,t(\cdot))$-estimator for

$\displaystyle t(n)$ $\displaystyle=O(1)\cdot\sigma\sqrt{\frac{\log\log
n+\log(1/\alpha)}{n}}$

by Proposition 4, matching the lower bound in Example 3.1 to within constant
factors; Proposition 3 shows its sharpness generally. $\Diamond$

##  5 Proof of Proposition 3

For $\theta\in\Theta$, let $\mathbb{P}_{\theta}$ represent the probability
space corresponding to $X_{1},X_{2},\ldots\stackrel{{\scriptstyle\rm
iid}}{{\sim}}P_{\theta}$. Considering testing between two points $\theta_{0}$
and $\theta_{\delta}=\theta_{0}+\delta\in\Theta$, where $\delta>0$ is a
quantity we choose later. For any test $T_{n}$ based on a sample of size $n$,
Le Cam’s lemma (Lemma 2.2) and the Bretagnolle-Huber inequality (Lemma 2.3)
give that

$\displaystyle\mathbb{P}_{\theta_{0}}(T_{n}\neq\theta_{0})+\mathbb{P}_{\theta_{\delta}}(T_{n}\neq\theta_{\delta})$
$\displaystyle\geq\frac{1}{2}\exp(-D_{\rm
kl}\left({P_{\theta_{0}}^{n}}|\\!|{P_{\theta_{\delta}}^{n}}\right))\geq\frac{1}{2}\exp(-nM\delta^{2}),$

where we use the assumption that $D_{\rm
kl}\left({P_{\theta_{0}}}|\\!|{P_{\theta_{0}+\delta}}\right)\leq M\delta^{2}$.
One such test is

$\displaystyle T_{n}$
$\displaystyle\coloneqq\begin{cases}\theta_{0}&\textrm{if
}|\theta_{0}-\hat{\theta}_{n}|\leq|\hat{\theta}_{n}-\theta_{\delta}|\\\
\theta_{\delta}&\textrm{otherwise}.\end{cases}$

By the triangle inequality $|\hat{\theta}_{n}-\theta_{0}|\leq\frac{\delta}{2}$
implies $|\hat{\theta}_{0}-\theta_{n}|\leq|\hat{\theta}_{n}-\theta_{\delta}|$
and $T_{n}=\theta_{0}$, and similarly,
$|\hat{\theta}_{n}-\theta_{\delta}|<\delta/2$ implies $T_{n}=\theta_{\delta}$.
Thus

$\displaystyle\mathbb{P}_{\theta_{0}}(|\hat{\theta}_{n}-\theta_{0}|>\delta/2)+\mathbb{P}_{\theta_{\delta}}(|\hat{\theta}_{n}-\theta_{\delta}|\geq\delta/2)$
$\displaystyle\geq\mathbb{P}_{\theta_{0}}(T_{n}\neq\theta_{0})+\mathbb{P}_{\theta_{\delta}}(T_{n}\neq\theta_{\delta})\geq\frac{1}{2}\exp(-nM\delta^{2}),$

and so

$\displaystyle\sup_{\theta\in\Theta}\mathbb{P}_{\theta}(|\hat{\theta}_{n}-\theta|\geq\delta/2)\geq\max_{\theta\in\\{\theta_{0},\theta_{\delta}\\}}\mathbb{P}_{\theta}(|\hat{\theta}_{n}-\theta|\geq\delta/2)\geq\frac{1}{4}\exp(-nM\delta^{2}).$

By choosing $\delta=\sqrt{\log(1/4\alpha^{\prime})/Mn}$ for any
$\alpha^{\prime}>\alpha$, we have

$\displaystyle\inf_{\theta\in\Theta}\mathbb{P}_{\theta}\left(|\hat{\theta}_{n}-\theta|\leq\frac{1}{2}\sqrt{\frac{\log(1/4\alpha^{\prime})}{Mn}}\right)\leq
1-\alpha^{\prime}<1-\alpha.$

On the other hand, the time-uniform condition gives that for any $n$,

$\displaystyle\inf_{\theta\in\Theta}\mathbb{P}_{\theta}(|\hat{\theta}_{n}-\theta|\leq
t(n))\geq\inf_{\theta\in\Theta}\mathbb{P}_{\theta}(|\hat{\theta}_{m}-\theta|\leq
t(m),\text{ for all }m\in\mathbb{N})\geq 1-\alpha.$

This implies that $t(n)\geq\tfrac{1}{2}\sqrt{\log(1/4\alpha^{\prime})/Mn}$.
Taking $\alpha^{\prime}\searrow\alpha$ thus proves the claim.

## References

  * Brown [1986] L. D. Brown.  _Fundamentals of Statistical Exponential Families_.  Institute of Mathematical Statistics, Hayward, California, 1986.
  * Chyzak and Nielsen [2019] F. Chyzak and F. Nielsen.  A closed-form formula for the Kullback-Leibler divergence between Cauchy distributions.  _arXiv:1905.10965 [cs.IT]_ , 2019.
  * Cover and Thomas [2006] T. M. Cover and J. A. Thomas.  _Elements of Information Theory, Second Edition_.  Wiley, 2006.
  * Darling and Robbins [1967] D. A. Darling and H. Robbins.  Confidence sequences for mean, variance, and median.  _Proceedings of the National Academy of Sciences_ , 58(1):66, 1967.
  * Duchi [2023] J. C. Duchi.  Stats311/EE377: Information theory and statistics.  Course at Stanford University, Fall 2023.  URL http://web.stanford.edu/class/stats311.
  * Farrell [1964] R. H. Farrell.  Asymptotic behavior of expected sample size in certain one sided tests.  _Annals of Mathematical Statistics_ , 35(1):36–72, 1964.
  * Howard et al. [2021] S. R. Howard, A. Ramdas, J. McAuliffe, and J. Sekhon.  Time-uniform, nonparametric, nonasymptotic confidence sequences.  _Annals of Statistics_ , 49(2):1055–1080, 2021\.
  * Jamieson et al. [2014] K. Jamieson, M. Malloy, R. Nowak, and S. Bubeck.  lil’UCB: An optimal exploration algorithm for multi-armed bandits.  In _Proceedings of the Twenty Seventh Annual Conference on Computational Learning Theory_ , pages 423–439. PMLR, 2014.
  * Jennison and Turnbull [1989] C. Jennison and B. W. Turnbull.  Interim analyses: the repeated confidence interval approach.  _Journal of the Royal Statistical Society, Series B_ , 51(3):305–334, 1989.
  * Johari et al. [2022] R. Johari, P. Koomen, L. Pekelis, and D. J. Walsh.  Always valid inference: Continuous monitoring of A/B tests.  _Operations Research_ , pages 1806–1821, 2022.
  * Kaufmann et al. [2016] E. Kaufmann, O. Cappé, and A. Garivier.  On the complexity of best arm identification in multi-armed bandit models.  _Journal of Machine Learning Research_ , 17(1):1–42, 2016.
  * Kullback [1968] S. Kullback.  _Information Theory and Statistics_.  Dover Publications, 1968.
  * Lai [1976] T.-L. Lai.  On confidence sequences.  _The Annals of Statistics_ , 4(2):265–280, 1976\.
  * Lai [1984] T.-L. Lai.  Incorporating scientific, ethical and economic considerations into the design of clinical trials in the pharmaceutical industry: a sequential approach.  _Communications in Statistics – Theory and Methods_ , 13(19):2355–2368, 1984.
  * Lehmann and Casella [1998] E. L. Lehmann and G. Casella.  _Theory of Point Estimation, Second Edition_.  Springer, 1998.
  * Robbins [1970] H. Robbins.  Statistical methods related to the law of the iterated logarithm.  _Annals of Mathematical Statistics_ , 41(5):1397–1409, 1970.
  * Tsybakov [2009] A. B. Tsybakov.  _Introduction to Nonparametric Estimation_.  Springer, 2009.
  * Wainwright [2019] M. J. Wainwright.  _High-Dimensional Statistics: A Non-Asymptotic Viewpoint_.  Cambridge University Press, 2019.
  * Yu [1997] B. Yu.  Assouad, Fano, and Le Cam.  In _Festschrift for Lucien Le Cam_ , pages 423–435. Springer-Verlag, 1997.