# Anytime-valid sequential testing for elicitable functionals via
supermartingales

Philippe<EMAIL_ADDRESS>[ Martin
<EMAIL_ADDRESS>[ Johanna
<EMAIL_ADDRESS>[ ETH Zürich,  Carnegie Mellon
University,  University of Bern,

###### Abstract

We design sequential tests for a large class of nonparametric null hypotheses
based on elicitable and identifiable functionals. Such functionals are defined
in terms of scoring functions and identification functions, which are ideal
building blocks for constructing nonnegative supermartingales under the null.
This in turn yields anytime valid tests via Ville’s inequality. Using regret
bounds from Online Convex Optimization, we obtain rigorous guarantees on the
asymptotic power of the tests for a wide range of alternative hypotheses. Our
results allow for bounded and unbounded data distributions, assuming that a
sub-$\psi$ tail bound is satisfied.

sequential statistics,

anytime-valid tests,

elicitable functionals,

identifiable functionals,

online optimization,

###### keywords:

, and

##  1 Introduction

We design sequential tests and confidence sequences for a large class of
nonparametric null hypotheses based on elicitable and identifiable
functionals. Such functionals include moments, quantiles, expectiles, and many
other examples, all of which can be tested using the approach developed here.
The null hypotheses that we cover are highly composite and nonparametric; for
instance, the null could consist of _all_ distributions whose median, say, is
a given value. Our tests are sequential, or _anytime valid_ , in the sense
that data is observed sequentially through time, and at each point in time the
decision to stop or continue may depend on all available data without
compromising Type-I error guarantees. We also obtain guarantees on the power
of our tests with respect to large composite nonparametric alternative
hypotheses.

The basic mechanism we use to construct anytime valid tests rests on the
notion of _test (super-)martingale_ due to Shafer et al. (2011). The idea is
simple but powerful: a test statistic that is a nonnegative supermartingale if
the null hypothesis is true can only reach large values with small
probability. This can be quantified using Ville’s inequality. Thus if one
rejects the null only when a sufficiently large value of the test statistic
has been observed, Type-I error control is ensured.

The first contribution of our work is the observation that elicitable and
identifiable functionals in the sense of Lambert, Pennock and Shoham (2008);
Gneiting (2011); Fissler and Ziegel (2016) are ideal building blocks for
constructing test supermartingales. Combined with a construction known as
predictable mixing, one immediately obtains large families of test
supermartingales which can be used as possible test statistics for the null
hypothesis defined by a particular elicitable or identifiable functional.

The predictable mixing construction can be interpreted in terms of betting or
trading. Finding a useful predictable mixture corresponds to determining a
profitable trading strategy. The supermartingale condition under the null
ensures that profits are limited if the null is true. But if the null is
false, it may be possible to “bet against the null” in a way that leads to
large profits and, hence, reject the null. Doing so requires two things.
First, in order to bet against the null, one must specify a suitable
distribution to bet on. Second, given this distribution, one must find a
strategy that is likely to be profitable.

The second contribution of our work is to address these two points at once by
making use of ideas from online convex optimization (OCO). We demonstrate how
off-the-shelf algorithms can be used to produce strong trading strategies.
This leads to powerful test supermartingales given as predictable mixtures of
the basic set of test supermartingales constructed from the elicitable or
identifiable functional used to specify the null hypothesis. A major advantage
of this approach is that these algorithms come with performance guarantees in
the form of regret bounds. These regret bounds translate into rigorous
guarantees on the power of the resulting sequential test under a wide variety
of alternative hypotheses.

Sequential testing goes back to Wald (1945). A large body of literature on the
subject exists, and martingale techniques have played an important role from
the beginning; see Appendix D in Waudby-Smith and Ramdas (2020) for an
overview. The concept of a test martingale was introduced in Shafer et al.
(2011), and there has recently been a number of papers related to this circle
of ideas, for instance Howard et al. (2020, 2021) which derive time-uniform
confidence sequences and concentration bounds. In particular, the closely
related notion of e-variables and e-processes have received significant
attention; see e.g. Grünwald, de Heide and Koolen (2019); Vovk and Wang
(2021); Xu, Wang and Ramdas (2021); Ramdas et al. (2020, 2022) as well as
Remark 2.3 below. Most closely related to our paper is the work of Waudby-
Smith and Ramdas (2020), which develops anytime valid confidence sequences for
the mean of a sequence of bounded random variables. That paper makes use of
the same betting perspective, which enables the authors to obtain powerful
confidence sequences. It also discusses various related strands of literature
and the history of the subject. However, the authors do not consider other
functionals beyond the mean, and they rely on the boundedness of the data in
an essential way. Our work generalizes both of these points. Moreover, they do
not make use of OCO to obtain regret bounds which then translate into
statements about power. Our use of regret bounds is reminiscent of Ramdas et
al. (2022), where regret bounds are used to derive power guarantees for the
particular problem of testing exchangeability of binary sequences. Another
paper related to ours is Henzi and Ziegel (2021), which treats the problem of
probability forecasting. The authors rely on the betting analogy to construct
sequential tests for the statistical significance of score differences of
competing forecasts.

The concepts of elicitability and identifiability go back to the PhD thesis of
Osband (1985). However, the term elicitability was coined later (Lambert,
Pennock and Shoham, 2008), and it was popularized by Gneiting (2011);
Steinwart et al. (2014); Frongillo and Kash (2021); Fissler and Ziegel (2016).
However, prior to our work, no systematic approach to the sequential testing
problem for elicitable and identifiable functionals had been developed. Thus
our paper contributes to this literature as well, the essential point being
the link between test supermartingales and the concepts of elicitability and
identifiability.

The paper is organized as follows. In Section 2 we review the definition of
test supermartingales and how they can be used to construct powerful anytime
valid tests via predictable mixing. In Section 3 we discuss elicitability and
identifiability, both as a way of specifying nonparametric null hypotheses and
as the basis for constructing test supermartingales. Importantly, we show how
sub-$\psi$ tail bounds can be leveraged to handle unbounded data. Section 4
discusses how regret bounds from online convex optimization lead to statements
about asymptotic power of the tests. In Section 5 we briefly discuss the
related issue of confidence sequences. Section 6 contains a simulation study
illustrating the techniques developed in this paper.

##  2 Sequential testing via supermartingales

We consider a sequential testing environment in which a discrete-time
stochastic process $(X_{t})_{t\in{\mathbb{N}}}$, taking values in some
measurable space ${\mathcal{X}}$, is observed sequentially through time. The
process $X$ is called the _data generating process_. Concrete examples of data
generating processes include patient data collected from clinical trials or
daily profit and loss values of a trading strategy. The filtration generated
by the data generating process is denoted
${\mathcal{F}}:=({\mathcal{F}}_{t})_{t\in{\mathbb{N}}}$ where
${\mathcal{F}}_{t}:=\sigma(X_{1},\ldots,X_{t})$ is the information set
generated by the data collected until time $t$. We let ${\mathcal{F}}_{0}$
denote the trivial $\sigma$-algebra.

A statistical hypothesis is a collection
${\mathcal{H}}\subseteq{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})$, where
${\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})$ is the set of all probability
distributions of the data generating process. Thus an element
$P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})$ is a distribution _over
the entire sequence_ $(X_{t})_{t\in{\mathbb{N}}}$. The hypothesis
${\mathcal{H}}$ encodes the belief that the realized data was governed by one
of the distributions $P\in{\mathcal{H}}$. A _(sequential) test_ for a given
null hypothesis ${\mathcal{H}}_{0}$ is defined as an ${\mathcal{F}}$-stopping
time $\tau$ that specifies the time at which ${\mathcal{H}}_{0}$ is rejected.
The requirement that $\tau$ be a stopping time means that the decision whether
to stop and reject ${\mathcal{H}}_{0}$, or to continue and observe more data,
is only based on data available at the time the decision is made. Stopping
times are allowed to take the value infinity, and this corresponds to the
possibility that the test never rejects the null.

###  2.1 Anytime validity and test supermartingales

In contrast to traditional hypothesis testing with a fixed and known total
sample size, the total sample size that will be produced by the $X_{t}$ before
stopping is not known in advance. As a consequence, repeatedly evaluating a
test designed for fixed finite sample sizes will generate an inflated Type-I
error (or size) of the test, see for example Albers (2019); O’neill and
Wetherill (1971). Although techniques such as multiple comparison p-value
adjustments, see for example Hsu (1996), exist to correctly modify tests
a-posteriori, these methods have quickly decaying power as the number of
repeated tests grows large and require that the number of tests to be
performed be known in advance. In order to avoid these issues, we work with
the concept of an _anytime valid test_ which allows arbitrary testing policies
that need not necessarily be specified in advance.

######  Definition 2.1 (anytime validity).

Let a null hypothesis ${\mathcal{H}}_{0}$ be given. We say that a test is
_anytime valid_ , or has _Type-I error control_ , at a level $\alpha\in(0,1)$
if for all ${\mathcal{F}}$-stopping-times $\tau$ we have

$P(\text{${\mathcal{H}}_{0}$ is rejected at time $\tau$})\leq\alpha\text{ for
all $P\in{\mathcal{H}}_{0}$.}$

A classical method for constructing anytime valid tests is based on
nonnegative supermartingales. The following definition goes back to Shafer et
al. (2011).

######  Definition 2.2 (test supermartingale).

Let a null hypothesis ${\mathcal{H}}_{0}$ be given. A _test supermartingale
(for ${\mathcal{H}}_{0}$)_ is a nonnegative adapted process
$W:=(W_{t})_{t\in{\mathbb{N}}}$ with initial value $W_{0}\leq 1$ that is a
$P$-supermartingale for all $P\in{\mathcal{H}}_{0}$.

We recall that a random process $(Z_{t})_{t\in{\mathbb{N}}}$ adapted to a
filtration $({\mathcal{G}}_{t})_{t\in{\mathbb{N}}}$ such that
${\mathbb{E}}_{P}|Z_{i}|<\infty$ is a $P$-supermartingale ($P$-submartingale)
if for all $t\in{\mathbb{N}}$ we have
${\mathbb{E}}_{P}[Z_{t+1}\mid{\mathcal{G}}_{t}]\leq Z_{t}$
(${\mathbb{E}}_{P}[Z_{t+1}\mid{\mathcal{G}}_{t}]\geq Z_{t}$). A process that
is both a $P$-supermartinale and a $P$-submartingale is called a
$P$-martingale, and satisfies the equality
${\mathbb{E}}_{P}[Z_{t+1}\mid{\mathcal{G}}_{t}]=Z_{t}$ for all
$t\in{\mathbb{N}}$. Here, ${\mathbb{E}}_{P}$ means that the expectation is
taken with respect to the probability measure
$P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})$.

Test supermartingales can be used to construct anytime valid tests. The basic
tool for showing anytime validity is Ville’s inequality (Ville, 1939), which
states that any nonnegative $P$-supermartingale $W$ with $W_{0}\leq 1$
satisfies $P\left(\sup_{t\in{\mathbb{N}}}W_{t}>1/\alpha\right)\leq\alpha$ for
all $\alpha\in(0,1)$. Thus, if $W$ is a test supermartingale and
$\alpha\in(0,1)$ is fixed, then the test which rejects the null as soon as $W$
reaches a value above $1/\alpha$,

$\tau=\inf\left\\{t\in{\mathbb{N}}\colon W_{t}>\frac{1}{\alpha}\right\\},$ (1)

satisfies

$\displaystyle P(\text{$\tau$ rejects
${\mathcal{H}}_{0}$})=P(\tau<\infty)=P\left(\sup_{t\in{\mathbb{N}}}W_{t}>\frac{1}{\alpha}\right)\leq\alpha,$

and is therefore anytime valid at level $\alpha$.

######  Remark 2.3.

A notion closely related to test supermartingales is that of an _e-process_ ,
which is a nonnegative adapted process $W$ such that
${\mathbb{E}}_{P}[W_{\tau}]\leq 1$ for all $P\in{\mathcal{H}}_{0}$ and all
stopping times $\tau$ (Vovk and Wang, 2021; Xu, Wang and Ramdas, 2021; Ramdas
et al., 2020, 2022). The stopping theorem implies that every test
supermartingale is an e-process, but the converse is not true (Ramdas et al.,
2020, 2022). The ‘static’ or non-sequential analog of an e-process is known as
an _e-variable_ , which is a nonnegative random variable $E$ such that
${\mathbb{E}}_{P}[E]\leq 1$ for all $P\in{\mathcal{H}}_{0}$. These notions
have recently been studied extensively as a tool for safe inference (Grünwald,
de Heide and Koolen, 2019).

###  2.2 Power and growth

In addition to validity we are also interested in power against suitable
alternative hypotheses ${\mathcal{H}}_{1}$ disjoint from ${\mathcal{H}}_{0}$.
Loosely speaking this means that if the true data distribution belongs to
${\mathcal{H}}_{1}$, the test should reject ${\mathcal{H}}_{0}$ quickly with
high probability. For tests arising from test supermartingales $W$ via (1)
this corresponds to designing $W$ to grow quickly with high probability under
distributions in ${\mathcal{H}}_{1}$. This can be approached using the Growth
Rate Optimal (GRO) criterion, which has recently received significant
attention in the context of e-values and e-process (Grünwald, de Heide and
Koolen, 2019). In our setting the GRO criterion is as follows. At each time
$T$ one seeks to maximize the expected logarithmic increment conditionally on
data observed so far across all test supermartingale increments. More formally
one aims to solve

$\operatorname*{maximize}\
{\mathbb{E}}_{Q}\left[\log\frac{W_{T+1}}{W_{T}}\mid{\mathcal{F}}_{T}\right]\quad\text{
subject to
}\quad\sup_{P\in{\mathcal{H}}_{0}}{\mathbb{E}}_{P}\left[\frac{W_{T+1}}{W_{T}}\mid{\mathcal{F}}_{T}\right]\leq
1$ (2)

given the observed data $X_{1},\ldots,X_{T}$, where $Q$ is a suitable
distribution. As we will see, $Q$ need not itself be the only element of
${\mathcal{H}}_{1}$, or even belong to ${\mathcal{H}}_{1}$ at all. It is a
purely computational device used to guide the choice of $W$.

In implementing this idea one is faced with three key issues:

  1. (i)

The problem (2) optimizes over the set of all test supermartingales. Solving
it requires a description of this set, or of a sufficiently rich subset.

  2. (ii)

A suitable distribution $Q$ has to be specified.

  3. (iii)

One has to actually solve (2), at least numerically, and ideally derive
performance guarantees with respect to the set ${\mathcal{H}}_{1}$ of
alternatives.

In this paper, we consider null hypotheses ${\mathcal{H}}_{0}$ based on
elicitable functionals and identifiable functionals, which admit large
families of explicit test supermartingales. This addresses (i). In order to
address (ii) we focus on distributions $Q$ which are not fixed in advance but
rather learned in an online fashion as more and more data is observed. This
idea has recently also been explored by Waudby-Smith and Ramdas (2020). Having
dealt with (i) and (ii), the GRO criterion becomes a concrete optimization
problem which we solve using methods from Online Convex Optimization (OCO). A
key feature of this approach is that OCO methods come with asymptotic
performance guarantees in the form of regret bounds. We employ these bounds to
show that the resulting tests have asymptotic power one under a large
composite nonparametric alternative hypothesis ${\mathcal{H}}_{1}$, in the
sense that we obtain a test supermartingale which tends to infinity with
probability one under every distribution in ${\mathcal{H}}_{1}$. Consequently,
if the true data distribution is some element of ${\mathcal{H}}_{1}$ then any
test $\tau$ of the form (1) is guaranteed to eventually reject the null:
$P(\tau<\infty)=1$ for all $P\in{\mathcal{H}}_{1}$. This addresses (iii).

###  2.3 Test supermartingales via mixing

The null hypotheses considered in this paper will be constructed directly in
terms of explicit families of test supermartingales
$L^{\theta}=(L^{\theta}_{t})_{t\in{\mathbb{N}}}$ indexed by a parameter
$\theta\in\Theta$, where $\Theta$ is an (arbitrary) index set. Whenever such a
family $\\{L^{\theta}\\}_{\theta\in\Theta}$ is available, it is possible to
construct new test supermartingales by combining its members. For instance, it
is clear that any convex combination of test supermartingales is again a test
supermartingale. More generally, one can use predictably mixed test
supermartingales as shown in the following lemma; see also Waudby-Smith and
Ramdas (2020). In this way one can assemble weak test supermartingales into
more powerful ones.

######  Lemma 2.4 (Predictably mixed supermartingale).

Let $\\{L^{\theta}\\}_{\theta\in\Theta}$ be a family of test supermartingales
and $(\pi_{t})_{t\in{\mathbb{N}}}$ a predictable sequence of probability
measures on $\Theta$. Then the process $W=(W_{t})_{t\in{\mathbb{N}}}$ defined
by $W_{0}=1$ and

$W_{t}=\prod_{i=1}^{t}\int_{\Theta}\frac{L_{i}^{\theta}\;}{L_{i-1}^{\theta}}\,\pi_{i}(d\theta),\quad
t\in{\mathbb{N}},$ (3)

is also a test supermartingale.

To be precise, we assume here that $\Theta$ is a measurable space, and that
$(\omega,\theta)\mapsto L_{t}^{\theta}(\omega)$ is measurable for each $t$.
The condition on $(\pi_{t})_{t\in{\mathbb{N}}}$ means that for each
$t\in{\mathbb{N}}$, $\pi_{t}=\pi_{t}(X_{1},\ldots,X_{t-t};d\theta)$ is a
probability measure on $\Theta$ that may depend on the preceding data points.
The proof of Lemma 2.4 can be found in the appendix.

######  Example 1 (i.i.d. Gaussians).

Consider the hypothesis
${\mathcal{H}}_{0}=\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\colon
X_{t}\sim\text{ i.i.d. }{\mathcal{N}}(0,1)\\}$. Then for every
$\lambda\in{\mathbb{R}}$ the process $L^{\lambda}$ defined by
$L^{\lambda}_{0}=1$ and for $t\in{\mathbb{N}}$ by
$L_{t}^{\lambda}=\exp\left(\lambda\sum_{i=1}^{t}X_{i}-\frac{1}{2}\lambda^{2}t\right)$
is a test (super)martingale. The predictably mixed process $W$ in (3) then
takes the form

$W_{t}=\prod_{i=1}^{t}\int_{\mathbb{R}}\exp\left(\lambda
X_{i}-\frac{1}{2}\lambda^{2}t\right)\pi_{i}(d\lambda).$

######  Remark 2.5.

The mixing construction (3) admits a useful interpretation in terms of trading
a portfolio of financial assets. Treating the collection of test
supermartingales $\\{L^{\theta}\\}_{\theta\in\Theta}$ as a collection of
tradable assets indexed by $\theta\in\Theta$, we may think of $W_{t}$ in (3)
as the value of a portfolio trading these assets. Indeed, regard
$\pi_{t}(d\theta)$ as the portfolio weights specifying the proportion of
capital allocated to each asset $\theta$ at time $t-1$; this is observable at
time $t-1$ because $(\pi_{t})_{t\in{\mathbb{N}}}$ is a predictable sequence.
The portfolio return from time $t-1$ to $t$ is the weighted average of the
individual asset returns,

$\int_{\Theta}\frac{L_{t}^{\theta}-L_{t-1}^{\theta}}{L_{t-1}^{\theta}}\,\pi_{t}(d\theta).$

Rearranging (3) one sees that this is equal to the overall portfolio return
$(W_{t}-W_{t-1})/W_{t-1}$. We can think of selecting a strong allocation
strategy $(\pi_{t})_{t\in{\mathbb{N}}}$ as choosing bets against
${\mathcal{H}}_{0}$ in order to make $W_{t}$ grow quickly, eventually
exceeding the threshold $\alpha^{-1}$ to reject ${\mathcal{H}}_{0}$. Indeed,
if ${\mathcal{H}}_{0}$ is false, there may exist assets $L^{\theta}$ which are
not supermartingales, enabling one to ‘bet against the null’ by selecting
$(\pi_{t})_{t\in{\mathbb{N}}}$ with weights on these processes such that the
wealth process grows on average. In contrast, if ${\mathcal{H}}_{0}$ is true,
Ville’s inequality shows that, regardless of the trading strategy employed, it
is unlikely (with probability bounded by $\alpha$) that our wealth ever
exceeds the threshold $\alpha^{-1}$.

In practice it is not feasible to work with general predictable sequences
$(\pi_{t})_{t\in{\mathbb{N}}}$. Instead we consider parsimonious
specifications that tend to work well in experiments. A key example is the
Dirac specification, $\pi_{t}=\delta_{\theta_{t}}$, where
$(\theta_{t})_{t\in{\mathbb{N}}}$ is a $\Theta$-valued predictable process.
This is the simplest possible specification. In terms of the trading
interpretation in Remark 2.5, a strategy of this kind chooses in each period
one single asset where all capital is invested. The test supermartingale (3)
simplifies to

$W_{t}=\prod_{i=1}^{t}\frac{L_{i}^{\theta_{i}}}{L_{i-1}^{\theta_{i}}}.$ (4)

##  3 Specifying the null hypothesis

We consider null hypotheses involving the value of certain statistical
functionals of the (conditional) distributions of the data. For example, for a
given value $\lambda_{0}$ we may want to to test the hypothesis

${\mathcal{H}}_{0}=\left\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\colon\text{$\lambda_{0}$
is a median of the conditional distribution
$P(X_{t}\in\cdot\mid{\mathcal{F}}_{t-1})$ for $t\in{\mathbb{N}}$}\right\\}.$

The hypotheses considered below generalize this example beyond medians to a
large class of _elicitable functionals_ and _identifiable functionals_. These
concepts are reviewed below; they include quantiles, moments, expectiles, and
many other examples. The key common feature of these hypotheses is that they
can be expressed in the form

${\mathcal{H}}_{0}=\left\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\colon
L^{\theta}\text{ is a $P$-supermartingale for all }\theta\in\Theta\right\\}$
(5)

for some explicit family of nonnegative processes
$L^{\theta}=(L^{\theta}_{t})_{t\in{\mathbb{N}}}$ starting at
$L^{\theta}_{0}=1$, indexed by a parameter $\theta\in\Theta$ where $\Theta$ is
an (arbitrary) index set. In our applications $\Theta$ will be a subset of a
finite-dimensional space. Thus by construction,
$\\{L^{\theta}\\}_{\theta\in\Theta}$ constitutes a family of ‘base’ test
supermartingales for ${\mathcal{H}}_{0}$ which can be used to form other test
supermartingales through predictable mixing as explained in Subsection 2.3.

###  3.1 Definition of elicitability and identifiability

We review the definitions as given in Fissler and Ziegel (2016). Fix
$k\in{\mathbb{N}}$ and a subset $\Lambda\subseteq{\mathbb{R}}^{k}$. A _scoring
function_ is simply a measurable map
$s\colon\Lambda\times{\mathcal{X}}\to{\mathbb{R}}$. Let $\mathcal{M}$ be a
class of probability distributions on $\mathcal{X}$. If for each distribution
$\mu\in\mathcal{M}$ the map

$\lambda\mapsto{\mathbb{E}}_{\mu}[s(\lambda,X)]$ (6)

is well-defined and finite, let $T(\mu)$ denote the set of its minimizers. The
induced map $T$ is called an _elicitable functional (with respect to
$\mathcal{M}$)_ and $s(\lambda,x)$ a _strictly consistent scoring function_
for $T$. Here $X$ denotes the canonical random variable on ${\mathcal{X}}$. If
$T(\mu)$ consists only of one element, that is the minimizer in (6) is unique,
we abuse notation and also use the notation $T(\mu)$ for the minimizer. Any
given elicitable functional can have many different strictly consistent
scoring functions.

Similarly, an _identification function_ is a measurable map
$m\colon\Lambda\times{\mathcal{X}}\to{\mathbb{R}}^{k}$. If for each
distribution $\mu\in\mathcal{M}$ the map

$\lambda\mapsto{\mathbb{E}}_{\mu}[m(\lambda,X)]$ (7)

is well-defined and finite, let $T(\mu)$ denote the set of its zeros. Then $T$
is called an _identifiable functional (with respect to $\mathcal{M}$)_ and
$m(\lambda,x)$ a _strict identification function_ for $T$. A zero of the
expected identification function in (7) is understood to hold component-wise,
since $m(\lambda,X)\in{\mathbb{R}}^{k}$. These definitions of elicitability
and identifiability are called higher-order elicitability by Fissler and
Ziegel (2016).

When applying an elicitable or identifiable functional $T$ to a distribution
$\mu$ in the following, we always implicitly assume that the functional is
well-defined for this distribution.

Table 1 contains some examples of commonly used functionals that happen to be
both elicitable and identifiable. The presented scoring functions are standard
but not strictly consistent on the maximal possible domain $\mathcal{M}$ of
definition of the respective functionals. Different choices of strictly
consistent scoring functions allow to show elicitability of these functionals
on their natural domains of definition; see Gneiting (2011) for details.

In the presence of convexity, the connection between scoring and
identification functions can be understood through subgradients. For instance,
if $T$ is an elicitable functional whose scoring function $s(\lambda,x)$ is
convex in $\lambda$, then $T$ is also an identifiable functional with
identification function $m(\lambda,x)\in\partial_{\lambda}s(\lambda,x)$, an
element of the subgradient of the scoring function with respect to $\lambda$.
For the converse, linking an identification function $m(\lambda,x)$ to a
unique convex scoring function $s(\lambda,x)$, more subtle conditions are
needed, and we point interested readers to Rockafellar and Wets (2009, Theorem
12.25). In the absence of convexity, scoring and identification functions are
still linked through gradients under sufficient differentiability assumptions
which are formalized as Osband’s principle in Fissler and Ziegel (2016).

| $T(\mu)$ | $s(\lambda,x)$ | $m(\lambda,x)$
---|---|---|---
Mean | ${\mathbb{E}}_{\mu}[X]$ | $\frac{1}{2}(x-\lambda)^{2}$ | $x-\lambda$
$\alpha$-Quantile | $\inf\\{\lambda:\alpha\geq\mu(X<\lambda)\\}$ | $|x-\lambda|\left(\,\alpha\mathbbm{1}_{\\{x<\lambda\\}}+(1-\alpha)\mathbbm{1}_{\\{x>\lambda\\}}\,\right)$ | $\mathbbm{1}_{\\{x>\lambda\\}}-\alpha$
Regression | $\operatorname*{argmin}_{\lambda\in{\mathbb{R}}^{k}}E_{\mu}[(\lambda^{\prime}Y-Z)^{2}]$ | $\frac{1}{2}\|\lambda^{\prime}y-z\|^{2}$ | $\lambda yy^{\prime}-zy^{\prime}$
Table 1: Examples of statistical quantities that can be expressed as
elicitable and identifiable functionals. In the elicitable case, for the mean,
$\mathcal{M}$ is the class of all distributions with finite second moment; for
the quantiles, it is the class of all distributions with finite first moment;
for regression, $X=(Y,Z),x=(y,z)\in{\mathbb{R}}^{k+1}$, and $\mathcal{M}$
contains all distributions on ${\mathbb{R}}^{k+1}$ with finite expected
squared norm. In the identifiable case, for the mean, $\mathcal{M}$ is the
class of all distributions with finite first moment; for the quantiles, it is
the class of all distributions with continuous distribution function at the
$\alpha$-quantile; for regression, $X=(Y,Z),x=(y,z)\in{\mathbb{R}}^{k+1}$, and
$\mathcal{M}$ contains all distributions on ${\mathbb{R}}^{k+1}$ with finite
mean.

We now use the concepts of elicitability and identifiability to construct null
hypotheses for the sequential testing problem. Let $T$ be either an elicitable
functional or an identifiable functional with scoring function $s(\lambda,x)$
(in the elicitable case) or identification function $m(\lambda,x)$ (in the
identifiable case). Given a fixed value $\lambda_{0}\in\Lambda$ we consider
the null hypothesis

${\mathcal{H}}_{0}=\left\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\colon\lambda_{0}\in
T(P(X_{t}\in\cdot\mid{\mathcal{F}}_{t-1}))\text{ for all
}t\in{\mathbb{N}},\text{ $P$-a.s.}\right\\}.$ (8)

Thus the hypothesis is that $T$ returns a set containing $\lambda_{0}$
whenever it is applied to the conditional distribution of an observation
$X_{t}$ given all earlier observations. For instance, if $T$ is the median
functional, we recover the example at the beginning of this section.

Using the definition of elicitability or identifiability, we obtain a simpler
representation of ${\mathcal{H}}_{0}$ in terms of supermartingales or
martingales and the scoring or identification function. Specifically, we have

${\mathcal{H}}_{0}=\left\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\colon\sum_{i=1}^{t}\left(s(\lambda_{0},X_{i})-s(\lambda,X_{i})\right)\text{
is a $P$-supermartingale for all }\lambda\in\Lambda\right\\}$ (9)

in the elicitable case, and

${\mathcal{H}}_{0}=\left\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\colon\sum_{i=1}^{t}m(\lambda_{0},X_{i})\text{
is a $P$-martingale}\right\\}$ (10)

in the identifiable case. Note that in the identifiable case,
$\sum_{i=1}^{t}m(\lambda_{0},x_{i})$ is a _vector valued_ martingale. For
convenience, if ${\mathcal{H}}_{0}$ is of the form (9) we call it an
_elicitable hypothesis_ , and if it is of the form (10) we call it an
_identifiable hypothesis_.

Let us spell out why, in the elicitable case, (8) essentially coincides with
(9); the identifiable case is similar. Due to the definition of elicitability,
$\lambda_{0}\in T(P(X_{t}\in\cdot\mid{\mathcal{F}}_{t-1}))$ is equivalent to
having
${\mathbb{E}}_{P}[s(\lambda_{0},X_{t})\mid{\mathcal{F}}_{t-1}]\leq{\mathbb{E}}_{P}[s(\lambda,X_{t})\mid{\mathcal{F}}_{t-1}]$
for all $\lambda\in\Lambda$. This holds for all $t\in{\mathbb{N}}$ if and only
if the process $\sum_{i=1}^{t}(s(\lambda_{0},X_{i})-s(\lambda,X_{i}))$ is a
$P$-supermartingale. Thus the right-hand sides of (8) and (9) are essentially
the same. There is one subtlety that we have neglected in this argument which
is usually irrelevant in applications. Since strictly consistent scoring
functions are not unique, it may happen that the elicitable functional is
defined for a larger class of distributions than the one where the chosen
strictly consistent scoring function in (9) has finite expectation. This means
that the moment conditions on the conditional distributions in (9) may be
slightly stronger than in (8). However, for many examples including the ones
in Table 1, this problem does not arise since we work with score differences.

The scoring function which elicits a functional $T$ is usually not unique. For
example, the class of consistent scoring functions for the mean consists of
all Bregman loss functions (Savage, 1971). Although there are no general
guidelines for how one should select a scoring function, it is often natural
to give preference to scoring functions that satisfy certain additional
desirable properties, a relevant example in our setting being convexity in the
first argument. For the mean, ratios of expectations and quantiles, convex
strictly consistent scoring functions are essentially unique, see Fissler
(2017, Corollary 4.2.17), Caponnetto (2005) and Steinwart et al. (2014,
Corollary 10). In the context of estimation in semi-parametric models for a
quantile or the mean, Komunjer and Vuong (2010a, b); Dimitriadis, Fissler and
Ziegel (2020) show that there exist unique choices of scoring functions which
maximize the asymptotic efficiency of the estimators, but these are different
from the convex choices described above.

The form of ${\mathcal{H}}_{0}$ in (9) and (10) are suggestive of how one
could construct families $\\{L^{\theta}\\}_{\theta\in\Theta}$ of base test
supermartingales. If $s(\lambda,x)$ or $m(\lambda,x)$ is uniformly bounded,
this is straightforward, see Subsection 3.2. The unbounded case requires to
include additional moment bounds, which we achieve by imposing a sub-$\psi$
condition, see Subsection 3.3.

###  3.2 Uniformly bounded scoring and identification functions

We construct parametric families $\\{L^{\theta}\\}_{\theta\in\Theta}$ of test
martingales when the score difference, $(\lambda,x)\mapsto
s(\lambda_{0},x)-s(\lambda,x)$, or the norm of the identification function,
$x\mapsto m(\lambda_{0},x)$, are uniformly bounded. The proofs of the
following two lemmas can be found in the appendix.

######  Lemma 3.1 (Test martingales for elicitable hypotheses).

Consider an elicitable hypothesis ${\mathcal{H}}_{0}$ of the form (9), and
assume that
$\,\inf_{\lambda\in\Lambda,x\in{\mathcal{X}}}\\{s(\lambda_{0},x)-s(\lambda,x)\\}>-1$.
For each $\lambda\in\Lambda$, define the processes
$L^{\lambda}=(L^{\lambda}_{t})_{t\in{\mathbb{N}}}$ by

$L^{\lambda}_{t}=\prod_{i=1}^{t}\left(1+s(\lambda_{0},X_{i})-s(\lambda,X_{i})\right)\;.$

Then the collection of processes $\\{L^{\lambda}\\}_{\lambda\in\Lambda}$ forms
a family of ${\mathcal{H}}_{0}$ test supermartingales.

The lower bound of $-1$ appearing in the assumption that
$\inf_{\lambda\in\Lambda,x\in{\mathcal{X}}}\\{s(\lambda_{0},x)-s(\lambda,x)\\}>-1$
is without loss of generality since scoring functions may be rescaled by
positive constants leaving the elicitable functional itself unchanged. In a
similar fashion, we may construct test martingales for identifiable hypotheses
as follows.

######  Lemma 3.2 (Test martingales for identifiable hypotheses).

Consider an identifiable hypothesis ${\mathcal{H}}_{0}$ of the form (10),
assume that $\sup_{x\in{\mathcal{X}}}\|m(\lambda_{0},x)\|<\infty$ and define
$A^{\mathrm{bd}}_{m,\lambda_{0}}:=\\{\eta\in{\mathbb{R}}^{d}:\inf_{x\in{\mathcal{X}}}\langle\eta,m(\lambda_{0},x)\rangle>-1\\}$.
For each $\eta\in A^{\mathrm{bd}}_{m,\lambda_{0}}$, define the process
$L^{\eta}=(L^{\eta}_{t})_{t\in{\mathbb{N}}}$ by

$L^{\eta}_{t}=\prod_{i=1}^{t}\left(1+\langle\eta\mathrel{,}m(\lambda_{0},X_{i})\rangle\right)\;.$

Then $A^{\mathrm{bd}}_{m,\lambda_{0}}$ is convex with non-empty interior, and
the set $\left\\{L^{\eta}\right\\}_{\eta\in A^{\mathrm{bd}}_{m,\lambda_{0}}}$
forms a family of ${\mathcal{H}}_{0}$ test martingales.

######  Remark 3.3.

Whenever the scoring function $s(\lambda,x)$ is convex in $\lambda$ and
satisfies the conditions of Lemma 3.1, there is a direct connection between
the two martingale constructions presented above. Indeed, if we let
$m(\lambda_{0},x)\in\partial_{\lambda}s(\lambda_{0},x)$, then

$-1<s(\lambda_{0},x)-s(\lambda,x)\leq\langle\lambda_{0}-\lambda,m(\lambda_{0},x)\rangle$
(11)

for all $x$ and $\lambda$. Hence, each increment of the test martingale
construction of Lemma 3.2 can be thought of as a linearization of the
increments of the processes defined in Lemma 3.1. Moreover, equation (11)
implies that for any elicitable hypotheses with convex scoring function,
identifiable test martingales generated by Lemma 3.2 will dominate the
elicitable test martingale Lemma 3.1 whenever $\eta=\lambda-\lambda_{0}$.
Indeed, it is easy to verify that

$0<\prod_{i=1}^{t}(1+s(\lambda_{0},x_{i})-s(\lambda,x_{i}))\leq\prod_{i=1}^{t}(1+\langle\lambda_{0}-\lambda,m(\lambda_{0},x_{i})\rangle)\;,$

and that the right-hand side produces a valid test supermartingale for all
$\lambda,\lambda_{0}\in\Lambda$. This observation suggests that whenever an
elicitable functional $T$ admits a bounded and convex scoring function, the
test generated by its subgradient using Lemma 3.2 will always be more powerful
that the one generated by Lemma 3.1.

Fissler (2017, Proposition 3.2.1) shows that, under suitable conditions,
identification functions are unique up to multiplication with a matrix valued
function in $\lambda$. Therefore, the Remark 3.3 does not only apply to a
subgradient of a convex scoring function but to any identification function,
as long as a convex scoring function for the respective functional exists, and
with a suitable modification of the relation $\eta=\lambda_{0}-\lambda$.

In the setting of analyzing the asymptotic efficiency of semi-parametric
estimators of elicitable and identifiable functionals, a similar relation is
observed, in which an estimator generated by the identification function will
always be asymptotically more efficient that its elicitable counterpart
(Dimitriadis, Fissler and Ziegel, 2020).

The uniform boundedness assumptions in Lemmas 3.1 and 3.2 may appear to be
restrictive. However, they cover a number of cases of interest including the
mean whenever the data generating process $\\{X_{i}\\}_{i\in{\mathbb{N}}}$ is
bounded, see also Waudby-Smith and Ramdas (2020). A second relevant example
are (vectors of) quantiles, where the uniform boundedness assumption for the
identification function is met, regardless of whether the data generating
process is bounded or not. Indeed, it is easy to see from the rightmost column
of Table 1 that $\|m(\lambda,x)\|\leq\max\\{\alpha\mathrel{,}1-\alpha\\}$ is
uniformly bounded. Hence the family of test martingales of Lemma 3.2 is always
valid in the case of testing quantiles.

###  3.3 Test supermartingales for sub-$\psi$ hypotheses

In the more general case that the scoring function or identification function
is unbounded, we construct families of test martingales under the assumption
of a tail bound on the scoring or identification function which involves
bounding the cumulant generating function. We introduce the definition of a
sub-$\psi$ process below, a notion related to those introduced in Freedman
(1975); de la Peña, Klass and Lai (2004) but most closely related to (Howard
et al., 2020, Definition 1).

######  Definition 3.4 (Sub-$\psi$ Process).

Let $Y=(Y_{t})_{t\in{\mathbb{N}}}$ and $V=(V_{t})_{t\in{\mathbb{N}}}$ be
${\mathcal{F}}$-adapted processes, where the variance process $V_{t}$ is
assumed to be non-negative and $Y_{0}=V_{0}=0$. We say that $(Y,V)$ is
sub-$\psi$ if there is a $u_{\max}>0$ and a nonnegative convex function
$\psi:[0,u_{\max})\to[0,\infty)$ satisfying satisfying
$\psi(0)=\psi^{\prime}(0)=0$, where $\psi^{\prime}(0)$ is its right
derivative, and for each $u\in[0,u_{\max})$,

$(e^{u\,(Y_{t}-\bar{Y}_{t})-V_{t}\,\psi(u)})_{t\in{\mathbb{N}}}$

is a supermartingale, where
$\bar{Y}_{t}=\sum_{i=1}^{t}{\mathbb{E}}[Y_{i}-Y_{i-1}\mid{\mathcal{F}}_{i-1}]$.

Definition 3.4 is similar to Howard et al. (2020, Definition 1), but there are
some noteworthy differences. In particular, (Howard et al., 2020, Definition
1) is a weaker condition in that it allows
$e^{u\,(Y_{t}-\bar{Y}_{t})-V_{t}\,\psi(u)}$ to only be upper-bounded by a
supermartingale, rather than be a supermartingale itself. We make the choice
of requiring the supermartingale condition in order to be able work with the
supermartingale predictable mixing introduced in Section 2.3, which would
break down without this assumption. Further discussion of the sub-$\psi$
condition and its applications in time-uniform confidence bounds can be found
in Howard et al. (2020, 2021). In particular, we point the reader to Howard et
al. (2020, Section 3.1, Table 3) for a collection of commonly used $\psi$
functions and variance processes $V_{t}$ which are valid under a wide variety
of assumptions.

Typically, $V_{t}=t$ is the simplest possible choice of variance process, and
we use it for all concrete examples in this paper. We have chosen to state our
theoretical results for the more general Definition 3.4 in order to be
consistent with existing literature. When $V_{t}=t$, the sub-$\psi$ condition
specializes to (conditional, one-sided versions of) sub-Gaussian, sub-Gamma,
sub-Exponential, sub-Bernoulli and related conditions on the increments
$\Delta Y_{t}=Y_{t+1}-Y_{t}$ of $Y$, obtained by choosing $\psi$ to be the
corresponding cumulant generating function. Specifically, the condition in
Definition 3.4 is then equivalent to

${\mathbb{E}}\left[e^{u\,(\Delta Y_{t}-{\mathbb{E}}[\Delta
Y_{t}\mid{\mathcal{F}}_{t}])}\mid{\mathcal{F}}_{t-1}]\right]\leq
e^{\psi(u)}\text{ for all $u\in[0,{u}_{\text{max}})$, $t\in{\mathbb{N}}$.}$

This condition implies a bound on the right tail probabilities of the
increments of a sub-$\psi$ process $Y$. Indeed, Chernoff’s inequality (see
e.g. Hagerup and Rüb, 1990) states that

$\log P\left(\Delta Y_{t}>c+{\mathbb{E}}[\Delta
Y_{t}\mid{\mathcal{F}}_{t}]\middle|{\mathcal{F}}_{t}\right)\leq-\psi^{\ast}\left(c\right)\text{
for all $t\in{\mathbb{N}}$},$

where $\psi^{\ast}(c)=\sup\\{u\,c-\psi(u)\colon u\in[0,u_{\text{max}})\\}$ is
the convex conjugate of $\psi$.

The following lemma shows that, for a given sub-$\psi$ process
$Y=(Y_{t})_{t\in{\mathbb{N}}}$, the supermartingale property on $Y$ is
equivalent to the existence of a non-negative supermartingale.

######  Lemma 3.5.

Suppose that $(Y,V)=(Y_{t},V_{t})_{t\in{\mathbb{N}}}$ is an
${\mathcal{F}}$-adapted sub-$\psi$ process. Then $Y$ is a supermartingale if
and only if $(e^{u\,Y_{t}-V_{t}\psi(u)})_{t\in{\mathbb{N}}}$ is a
supermartingale.

###### Proof.

Let $Y$ be a supermartingale. By the sub-$\psi$ property, and denoting the
forward increments of processes as $\Delta Z_{t}=Z_{t+1}-Z_{t}$, we have that

$\displaystyle
e^{u\bar{Y}_{t}}{\mathbb{E}}\left[e^{u\,(Y_{t}-\bar{Y}_{t})-V_{t}\psi(u)}\middle|{\mathcal{F}}_{t-1}\right]$
$\displaystyle\leq e^{u\,Y_{t-1}-V_{t-1}\psi(u)}\;e^{u\,\Delta\bar{Y}_{t-1}}$
$\displaystyle=e^{u\,Y_{t-1}-V_{t-1}\psi(u)}\;e^{u\,{\mathbb{E}}[\Delta
Y_{t-1}\mid{\mathcal{F}}_{t-1}]}\leq e^{u\,Y_{t-1}-V_{t-1}\psi(u)}\;,$

where the last inequality follows since the supermartingale property implies
that ${\mathbb{E}}[Y_{t}-Y_{t-1}\mid{\mathcal{F}}_{t-1}]\leq 0$.

Now, assume that $(e^{u\,Y_{t}-V_{t}\,\psi(u)})_{t\in{\mathbb{N}}}$ is a
supermartingale for all $u\in[0,u_{\max})$. Since $\psi^{\prime}(0)=0$ we have

$\displaystyle{\mathbb{E}}[\Delta Y_{t-1}\mid$
$\displaystyle{\mathcal{F}}_{t-1}]={\mathbb{E}}\left[\Delta Y_{t-1}-\Delta
V_{t-1}\psi^{\prime}(0)\mid{\mathcal{F}}_{t-1}\right]$
$\displaystyle={\mathbb{E}}\left[\lim_{u\downarrow 0}\frac{e^{u\,\Delta
Y_{t-1}-\Delta
V_{t-1}\,\psi(u)}-1}{u}\middle|{\mathcal{F}}_{t-1}\right]=\lim_{u\downarrow
0}\frac{{\mathbb{E}}\left[e^{u\,\Delta Y_{t-1}-\Delta
V_{t-1}\,\psi(u)}\mid{\mathcal{F}}_{t-1}\right]-1}{u}\;,$

where in the third line we use the fact that since $\psi$ is convex and
differentiable at zero, there exists a closed neighborhood including zero in
which $(e^{u\,\Delta Y_{t-1}-\Delta V_{t-1}\,\psi(u)}-1)/u$ is continuous and
hence has an integrable upper bound, allowing us to exchange the limit and the
expectation by the dominated convergence theorem. Lastly, noting that
$({\mathbb{E}}[e^{u\,\Delta Y_{t-1}-\Delta
V_{t-1}\,\psi(u)}\mid{\mathcal{F}}_{t-1}]-1)/u\leq 0$ by the assumed
supermartingale property, we conclude that ${\mathbb{E}}\left[\Delta
Y_{t-1}\mid{\mathcal{F}}_{t-1}\right]\leq 0$, demonstrating that
$(Y_{t})_{t\in{\mathbb{N}}}$ is a supermartingale, as desired. ∎

We say that a family $\\{Y^{\theta}\\}_{\theta\in\Theta}$ of integrable
processes indexed by $\Theta$ is sub-$\psi$ if for each $\theta\in\Theta$
there is a function $\psi_{\theta}:[0,u_{\text{max}})\to[0,\infty)$ and a
process $V^{\theta}$ such that for each $\theta\in\Theta$, $Y^{\theta}$ is
sub-$\psi_{\theta}$. We note that although
$\theta\mapsto(\psi_{\theta}(\cdot),V^{\theta})$ varies with $\theta$, the
interval $[0,u_{\text{max}})$ is assumed to be the same for all
$\theta\in\Theta$. Using Lemma 3.5, we construct families of test
supermartingales under the assumption that the scoring or identification
functions satisfy a sub-$\psi$ condition, allowing us to extend the anytime-
valid sequential testing methodology to unbounded data. The proofs of the
following two Lemmas can be found in the appendix.

######  Lemma 3.6 (Test supermartingales for sub-$\psi$ elicitable
hypotheses).

Let $T$ be an elicitable functional with scoring function $s(\lambda,x)$ and
let ${\mathcal{H}}_{0}$ be an elicitable hypothesis of the form (9). For every
$\lambda\in\Lambda$ define
$Y_{t}^{\lambda}=\sum_{i=1}^{t}s(\lambda_{0},X_{i})-s(\lambda,X_{i})$ and
$V_{t}^{\lambda}=\sum_{i=1}^{t}v^{\lambda}_{i}$ for some nonnegative
${\mathcal{F}}$-adapted process $(v_{i}^{\lambda})_{i\in{\mathbb{N}}}$. If the
family $\\{(Y^{\lambda},V^{\lambda})\\}_{\lambda\in\Lambda}$ is sub-$\psi$
under every measure in ${\mathcal{H}}_{0}$, then for each $\lambda\in\Lambda$
and $u\in[0,u_{\text{max}})$, the process
$L^{\lambda,u}=(L^{\lambda,u}_{t})_{t\in{\mathbb{N}}}$ defined by

$L^{\lambda,u}_{t}=e^{uY_{t}^{\lambda}-V_{t}^{\lambda}\psi_{\lambda}(u)}=\prod_{i=1}^{t}e^{u\left(s(\lambda_{0},X_{i})-s(\lambda,X_{i})\right)-v_{i}^{\lambda}\psi_{\lambda}(u)}$

is an ${\mathcal{H}}_{0}$ test supermartingale.

Proceeding almost identically to Lemma 3.6, we may construct test
supermartingale families for identifiable hypotheses.

######  Lemma 3.7 (Test martingales for sub-$\psi$ identifiable hypotheses).

Let $T$ be an identifiable functional with identification function
$(\lambda,x)\mapsto m(\lambda,x)\in{\mathbb{R}}^{k}$, and let
${\mathcal{H}}_{0}$ be an identifiable hypothesis of the form (10). Let
$A^{\psi}_{m,\lambda_{0}}\subseteq{\mathbb{R}}^{k}$, and define for each
$\eta\in A^{\psi}_{m,\lambda_{0}}$ the processes
$Y_{t}^{\eta}=\sum_{i=1}^{t}\langle\eta\mathrel{,}m(\lambda_{0},X_{i})\rangle$
and $V_{t}^{\eta}=\sum_{i=1}^{t}v_{i}^{\eta}$ for some nonnegative
${\mathcal{F}}$-adapted process $(v_{i}^{\lambda})_{i\in{\mathbb{N}}}$. If the
family of processes $\left\\{\,(Y^{\eta},V^{\eta})\,\right\\}_{\eta\in
A^{\psi}_{m,\lambda_{0}}}$ is sub-$\psi$ under every measure in
${\mathcal{H}}_{0}$, then for each $\eta\in A^{\psi}_{m,\lambda_{0}}$ and
$u\in[0,u_{\max})$ the process
$L^{\eta,u}=(L^{\eta,u}_{t})_{t\in{\mathbb{N}}}$ defined by

$L^{\eta,u}_{t}=\prod_{i=1}^{t}e^{u\langle\eta,m(\lambda_{0},X_{i})\rangle-
v_{i}^{\eta}\psi_{\eta}(u)}$

is an ${\mathcal{H}}_{0}$ test supermartingale.

The following examples illustrate two situations where test supermartingales
can be constructed for unbounded data using sub-$\psi$ assumptions.

######  Example 2 (Sub-$\psi$ mean).

Recall from Table 1 that the mean is identifiable with identification function
$m(\lambda,x)=x-\lambda$. Now suppose that a real-valued data-generating
process $(X_{t})_{t\in{\mathbb{N}}}$ has conditionally sub-Gaussian increments
so that
$\log{\mathbb{E}}[e^{u(X_{t}-{\mathbb{E}}[X_{t}\mid{\mathcal{F}}_{t-1}])}\mid{\mathcal{F}}_{t-1}]\leq\tilde{\psi}(u)$
for $\tilde{\psi}(u)=\sigma^{2}u^{2}/2$ and some $\sigma>0$. Under this
assumption, we have that $\sum_{i=1}^{t}\langle z,X_{i}-\lambda_{0}\rangle$ is
sub-$\psi$ with $\psi_{z}(u)=z^{2}\tilde{\psi}(u)$ and $V_{t}=t$, allowing us
to apply Lemma 3.7.

######  Example 3 (Sub-$\psi$ regression).

Consider the hypothesis that the data follows an $\mathrm{AR}(k)$ linear time
series model, $X_{t}=\sum_{i=1}^{k}\beta_{i}\,X_{t-i}+\epsilon_{t}$, where
$X_{t},\epsilon_{t}\in{\mathbb{R}}$, $(\epsilon_{t})_{t\in{\mathbb{N}}}$ is a
martingale difference sequence where
$(\pm\sum_{i=1}^{t}\epsilon_{i})_{t\in{\mathbb{N}}}$ is sub-$\psi$ with
variance process $V_{t}=t$ and $\beta\in{\mathbb{R}}^{k}$ is unknown. We wish
to test whether $\beta=\beta_{0}\in{\mathbb{R}}^{k}$. In each time step,
$\beta$ is the value of the identifiable functional
$T(P)=\operatorname*{argmin}_{\beta}{\mathbb{E}}_{P}[\|\sum_{i=1}^{k}\beta_{i}\,X_{t-i}-X_{t}\|^{2}\mid{\mathcal{F}}_{t-1}]$.
In view of the regression example of Table 1, this functional has
identification function

$m\left(\beta\mathrel{,}(y,\mathbf{x})\right)=\left(\;\left(\textstyle{\sum_{j=1}^{k}}\beta_{j}x_{j}-y\right)\frac{x_{i}}{\|\mathbf{x}\|}\;\right)_{i=1}^{k}$

where $\mathbf{x}=(x_{i})_{i=1}^{k}$ and where the re-scaling by
$\nicefrac{{1}}{{\|x\|}}$ is possible because
$\mathbf{X}_{(t-1):(t-k)}=(X_{t-i})_{i=1}^{k}$ is
${\mathcal{F}}_{t-1}$-measurable. In order to apply the testing methodology of
Lemma 3.7, we show that the processes $Y_{t}^{z}$ with
$Y_{t}^{z}-Y_{t-1}^{z}=\langle
z,m(\beta_{0}\mathrel{,}(X_{t}\mathrel{,}\mathbf{X}_{(t-1):(t-k)})\rangle$ are
sub-$\psi_{z}$ with $V_{t}^{z}=t$ for all $z\in{\mathbb{R}}^{d}$ with
$\|z\|\leq 1$. Computing

$\left\langle
z\mathrel{,}m\left(\beta_{0}\mathrel{,}(X_{t}\mathrel{,}\mathbf{X}_{(t-1):(t-k)}\right)\right\rangle-{\mathbb{E}}\left[\left\langle
z\mathrel{,}m\left(\beta_{0}\mathrel{,}(X_{t}\mathrel{,}\mathbf{X}_{(t-1):(t-k)}\right)\right\rangle\middle|{\mathcal{F}}_{t-1}\right]=c(z)\,\epsilon_{t}$

where $c(z)=\langle
z,\mathbf{X}_{(t-1):(t-k)}\rangle/\|\mathbf{X}_{(t-1):(t-k)}\|$, we see that
if $\pm\sum_{i=1}^{t}\epsilon_{i}$ are sub-$\psi$ with $V_{t}=t$, then
$Y_{t}^{z}$ will also be sub-$\psi$ since
$\log{\mathbb{E}}_{P}\left[\exp(c(z)u\,\epsilon_{t})\right]\leq\psi(|c(z)|\,u)\leq\psi(u)$,
which follows due to the fact that $|c(z)|\leq 1$. Hence, a sufficient
condition for this identifiable functional to satisfy the necessary sub-$\psi$
condition is simply that the signed residual processes
$(\pm\sum_{i=1}^{t}\epsilon_{i})_{t\in{\mathbb{N}}}$ are sub-$\psi$.

There is a relationship between tests for identifiable and elicitable
hypotheses with a convex scoring function in the sub-$\psi$ case, analogous to
the one pointed out in Remark 3.3. Indeed, let $T(\mu)$ be an elicitable
functional with a convex scoring function $(\lambda,x)\mapsto s(\lambda,x)$.
As pointed out in Remark 3.3, $T(\mu)$ is also identifiable with
identification function $m(\lambda,x)\in\partial_{\lambda}s(\lambda,x)$. If we
assume in addition that for a fixed $\lambda_{0}\in\Lambda$, the family of
processes $\\{(Y_{t}^{\lambda})_{t\geq 0}\\}_{\lambda\in\Lambda}$ with
increments
$Y_{t}^{\lambda}-Y_{t-1}^{\lambda}=\langle\lambda_{0}-\lambda\mathrel{,}m(\lambda_{0},X_{t})\rangle$
is sub-$\psi$ with $V_{t}=t$, then for any $\lambda\in\Lambda$ and
$u\in[0,u_{\max})$, the process

$L_{t}^{\lambda,u}=\prod_{i=1}^{t}e^{u\,\left\langle\lambda_{0}-\lambda\,\mathrel{,}\,m(\lambda_{0},X_{i}))\right\rangle-\psi_{\lambda}(u)}\;,$

is a valid test supermartingale according to Lemma 3.7. However, since
$s(\lambda,x)$ is convex and the
$\left\langle\lambda_{0}-\lambda\mathrel{,}m(\lambda_{0},X_{i})\right\rangle$
are increments of the sub-$\psi$ process $Y_{t}^{\lambda}$, we have that under
${\mathcal{H}}_{0}$,

${\mathbb{E}}\left[e^{u\,\left(s(\lambda_{0},X_{i})-s(\lambda,X_{i})\right)}\middle|{\mathcal{F}}_{i-1}\right]\leq{\mathbb{E}}\left[e^{u\,\left\langle\lambda_{0}-\lambda\mathrel{,}m(\lambda_{0},X_{i})\right\rangle}\middle|{\mathcal{F}}_{i-1}\right]\leq
e^{\psi(u)}\;.$

Hence, the processes

$\tilde{L}_{t}^{\lambda,u}=\prod_{i=1}^{t}e^{u\,\left(s(\lambda_{0},X_{i})-s(\lambda,X_{i})\right)-\psi_{\lambda}(u)}\;,$

are valid ${\mathcal{H}}_{0}$ test supermartingales which match the form of
the test supermartingales presented in Lemma 3.6. Due to (3.3), however, we
note that $\tilde{L}_{t}^{\lambda,u}\leq L_{t}^{\lambda,u}$. Hence, whenever
$\lambda\mapsto s(\lambda,x)$ is convex and the families of processes
$\left\\{\left(s(\lambda_{0},X_{i})-s(\lambda,X_{i})\right)_{i\in{\mathbb{N}}}\right\\}_{\lambda\in\Lambda}$
and
$\left\\{\left(\langle\lambda_{0}-\lambda\mathrel{,}m(\lambda_{0},X_{i})\rangle\right)_{i\in{\mathbb{N}}}\right\\}_{\lambda\in\Lambda}$
are both increments of a sub-$\psi$ process, we find that the tests generated
by the identification function $m$ according to Lemma 3.7 will always be more
powerful than a test generated by the scoring function $s$ according to Lemma
3.6, yielding a conclusion analogous to that in Remark 3.3.

######  Remark 3.8 (Bridging the sub-$\psi$ and bounded test
supermartingales).

Although the sub-$\psi$ and uniformly bounded hypothesis testing methodologies
may appear disjoint, there are in fact some connections which are worth
highlighting.

The first and arguably most important remark is that all processes with
bounded increments are sub-Gaussian, and hence sub-$\psi$. Indeed, whenever a
process $(Y_{t})_{t\in{\mathbb{N}}}$ satisfies $\Delta
Y_{t}=Y_{t+1}-Y_{t}\in[a,b]$, it follows by Hoeffding’s lemma (see e.g.
Hoeffding (1994); Hertz (2020)) that

$\log{\mathbb{E}}\left[e^{u\,(\Delta Y_{t}-{\mathbb{E}}[\Delta
Y_{t}\mid{\mathcal{F}}_{t}])}\mid{\mathcal{F}}_{t}\right]\leq\frac{1}{8}u^{2}\,(b-a)^{2}\;,$
(12)

where the second and third expression in the above inequality are the cumulant
generating functions of a Gaussian random variable. Hence, we have that
processes with bounded increments are sub-$\psi$, where $\psi$ is given by
either expressions in (12).

There exists a deeper connection between the two as follows. Let
$Z=(Z_{t})_{t\in{\mathbb{N}}}$ be a supermartingale difference process and let
$Y_{t}=\sum_{i=1}^{t}Z_{i}$. Define for each $n\in{\mathbb{N}}$ and $u\geq 0$
the family of processes
$M_{t}^{u,n}=\prod_{i=1}^{t}\left(1+uZ_{i}/n\right)^{n}\,e^{-\mu_{n}(u)}$,
where the collection of compensators $\\{\mu_{n}\\}_{n\in{\mathbb{N}}}$ with
$\mu_{n}:[0,\infty)\to[0,\infty]$ satisfy
$\log{\mathbb{E}}\left[\left(1+uZ_{i}/n\right)^{n}\mid{\mathcal{F}}_{i-1}\right]\leq\mu_{i}(u)$
for all $i\in{\mathbb{N}}$ and $u>0$. Since the function
$z\mapsto\left(1+z/n\right)^{n}$ is monotone, nonnegative and convex function
on $z\in[-n,\infty)$, we find that whenever $u\,Z_{i}\geq-n$ for all
$i\in{\mathbb{N}}$, the process $L^{u,n}$ is a nonnegative supermartingale
with initial value $L_{0}^{u,n}=1$.

Whenever $n=1$, we recover a set of processes with multiplicative increments
that are linear in the $Z_{i}$,
$M_{t}^{u,1}=\prod_{i=1}^{t}\left(1+{u\,Z_{i}}\right)\,e^{-\mu_{1}(u)}$.
Noting that if $uZ_{i}>-1$ and
${\mathbb{E}}\left[Z_{i}\mid{\mathcal{F}}_{i-1}\right]\leq 0$, we find that
$\mu_{1}\equiv 0$ is a valid compensator and $M^{u,1}$, defined in this
manner, matches the structure of the uniformly bounded test supermartingales
presented in Section 3.2. On the other hand, we note that as $n\to\infty$,
$\left(1+z/n\right)^{n}\to e^{z}$ pointwise, which yields the process
$M_{t}^{u,\infty}=\prod_{i=1}^{t}e^{u\,Z_{i}-\mu_{\infty}(u)}$, revealing a
similar structure to the test supermartingales discussed in Section 3.3.
Indeed, whenever the process $Y_{i}$ is sub-$\psi$ and $u\geq 0$, we find that
$L^{u,\infty}$ is a nonnegative supermartingale.

The families of test supermartingales presented in Lemmas 3.2 and 3.7 can be
thought of as generalizations of the processes presented in Waudby-Smith and
Ramdas (2020) for the purpose of building confidence sequences for means of
bounded random variables. In particular, let us consider the functional
$T(\mu)={\mathbb{E}}_{\mu}[X]$ with identification function
$m(\lambda,x)=\lambda-x$, where the random process
$\\{X_{i}\\}_{i\in{\mathbb{N}}}$ is constrained to the interval $[0,1]$.
Applying Lemma 3.2 to this particular setting, we recover the capital process
in Waudby-Smith and Ramdas (2020, §4). Similarly, as noted in Remark 3.8, the
process $\sum_{i=1}^{t}\langle z,m(X_{i},\lambda)\rangle$ is sub-$\psi$ for
all $\lambda\in[0,1]$ with $\psi_{\lambda}(u)=\frac{1}{8}u^{2}$ and $V_{t}=t$,
allowing us to recover via Lemma 3.7 the so-called Chernoff and predictably-
mixed Chernoff martingales (Waudby-Smith and Ramdas, 2020, §2.3 & §3.1).

##  4 Power via online convex optimization

Consider a null hypothesis ${\mathcal{H}}_{0}$ of the form (5) given in terms
of a family of base test supermartingales
$\\{L^{\theta}\\}_{\theta\in\Theta}$. We assume that each $L^{\theta}$ is of
product form,

$L^{\theta}_{t}=\prod_{i=1}^{t}f_{\theta}(X_{i})$ (13)

for some nonnegative function $f_{\theta}(x)$. This is the case for all the
hypotheses considered in Section 3. We now address the problem of designing a
powerful test supermartingale $W$. As a starting point we take the GRO
criterion in (2) and search among processes obtained by predictable mixing as
in (3). We must choose a distribution
$\hat{Q}\in{\mathcal{M}}({\mathcal{X}}^{\mathbb{N}})$ to bet on. This
distribution will not be fully specified ahead of time, but rather learnt
adaptively. For $t\in{\mathbb{N}}$ we set
$\hat{Q}(X_{t+1}\in\cdot\mid{\mathcal{F}}_{t})=(1/t)\sum_{i=1}^{t}\delta_{X_{i}}$,
the empirical measure of the data observed so far. Together with
$\hat{Q}(X_{1}\in\cdot)$, which we choose arbitrarily, this uniquely specifies
the distribution $\hat{Q}$. The GRO problem (2) at time $T$, restricted to
predictable mixtures $V$ as in (3), now takes the form

$\operatorname*{maximize}_{\pi_{T+1}}\
\sum_{i=1}^{T}\log\int_{\Theta}f_{\theta}(X_{i})\pi_{T+1}(d\theta).$ (14)

Let us give some further details for how to get from (2) to (14). First of
all, the supermartingale constraint in (2) is automatically satisfied since
$V$ is a predictable mixture. Next, the form of $W$ and $L^{\theta}$ imply
that
$W_{T+1}/W_{T}=\int_{\Theta}(L^{\theta}_{T+1}/L^{\theta}_{T})\pi_{T+1}(d\theta)=\int_{\Theta}f_{\theta}(X_{T})\pi_{T+1}(d\theta)$.
Finally, because $\hat{Q}(X_{T+1}\in\cdot\mid{\mathcal{F}}_{T})$ is defined as
the empirical measure of $X_{1},\ldots,X_{T}$ it follows that the objective
function in (2) is equal to

${\mathbb{E}}_{\hat{Q}}\left[\log\frac{W_{T+1}}{W_{T}}\mid{\mathcal{F}}_{T}\right]={\mathbb{E}}_{\hat{Q}}\left[\log\int_{\Theta}f_{\theta}(X_{T+1})\pi_{T+1}(d\theta)\mid{\mathcal{F}}_{T}\right]=\frac{1}{T}\sum_{i=1}^{T}\log\int_{\Theta}f_{\theta}(X_{i})\pi_{T+1}(d\theta).$

Since the factor $1/T$ does not affect the optimization, we arrive at (14).

Although the maximization problem (14) is concave in $\pi_{T+1}$, for
practical reasons we wish to avoid optimizing over this potentially infinite
dimensional quantity. Instead, as discussed in Subsection 2.3, we restrict the
optimization to the much smaller set of ‘one-asset strategies’ of the form
$\pi_{T+1}=\delta_{\theta_{T+1}}$ for some $\theta_{T+1}\in\Theta$ that may
depend on $X_{1},\ldots,X_{T}$. Doing so simplifies (14) further to

$\operatorname*{maximize}_{\theta_{T+1}}\ \sum_{i=1}^{T}\log
f_{\theta_{T+1}}(X_{i}).$ (15)

Due to the product form of $L^{\theta}$ the objective function is actually of
the even simpler form $\log L^{\theta_{T+1}}_{T}$. Here the dependence on the
optimization variable $\theta_{T+1}$ is no longer concave in general.
Nonetheless, the following lemma shows that in a wide range of examples
concavity does, in fact, hold. This will allow us to apply results from Online
Convex Optimization, either directly to (15) itself, or to regularized
versions of it.

######  Lemma 4.1.

Let $\\{L^{\theta}\\}_{\theta\in\Theta}$ satisfy one of the following
conditions.

  1. (i)

There exists a convex set $\Theta\subseteq\Lambda$ such that
$\\{L^{\theta}\\}_{\theta\in\Theta}$ are test supermartingales for a bounded
elicitable hypothesis defined according to Lemma 3.1, where the scoring
function $\Theta\ni\lambda\mapsto s(\lambda,x)$ is convex for all
$x\in{\mathcal{X}}$.

  2. (ii)

There exists a convex set $\Theta\subseteq A^{\mathrm{bd}}_{m,\lambda_{0}}$
such that $\\{L^{\theta}\\}_{\theta\in\Theta}$ are test martingales for a
bounded identifiable hypothesis defined according to Lemma 3.2.

  3. (iii)

There exists a finite dimensional convex set $\Theta$ and a map

$\Theta\ni\theta\mapsto(\lambda(\theta),u(\theta))\subseteq\Lambda\times[0,u_{\max})$

such that the collection
$\\{L^{\theta}\\}_{\theta\in\Theta}=\\{L^{\lambda(\theta),u(\theta)}\\}_{\theta\in\Theta}$
are test supermartingales for a sub-$\psi$ elicitable hypothesis defined
according to Lemma 3.6 and

$\Theta\ni\theta\mapsto
u(\theta)\,(s(\lambda_{0},x_{i})-s(\lambda(\theta),x_{i}))-v_{i}^{\lambda(\theta)}\psi_{\lambda(\theta)}(u(\theta))$

is almost surely concave.

  4. (iv)

There exists a finite-dimensional convex set $\Theta$ and a map

$\Theta\ni\theta\mapsto(\eta(\theta),u(\theta))\subseteq
A^{\psi}_{m,\lambda_{0}}\times[0,u_{\max})$

such that
$\\{L^{\theta}\\}_{\theta\in\Theta}=\\{L^{\eta(\theta),u(\theta)}\\}_{\theta\in\Theta}$
are test supermartingales for a sub-$\psi$ identifiable hypothesis defined
according to Lemma 3.7, and

$\Theta\mapsto
u(\theta)\,\langle\eta(\theta)\mathrel{,}m(\lambda_{0},x_{i})\rangle-
v_{i}^{\lambda(\theta)}\psi_{\eta(\theta)}(u(\theta))$

is almost surely concave.

Then for each $t\in{\mathbb{N}}$, the map $\theta\mapsto\log L_{t}^{\theta}$
is concave a.s.

The proof of the lemma uses that the composition of an increasing concave
function with a concave function is concave and is given in the appendix.

###  4.1 Regret and asymptotic power

By repeatedly solving (15) (or a regularized version of it) in each time
period, we obtain a predictable sequence $(\theta_{t})_{t\in{\mathbb{N}}}$
which produces the test supermartingale

$W_{t}=\prod_{i=1}^{t}f_{\theta_{i}}(X_{i}).$ (16)

A standard way of measuring the quality of the sequence
$(\theta_{t})_{t\in{\mathbb{N}}}$ is the _regret_ , defined at each time $t$
by

$\text{Regret}_{t}:=\max_{\theta\in\Theta}\left\\{\log L_{t}^{\theta}-\log
W_{t}\right\\}.$ (17)

The regret represents the difference between the log-value of the best
retrospectively chosen single-asset portfolio, $\max_{\theta\in\Theta}\log
L_{t}^{\theta}$, and the given log-wealth $\log W_{t}$. Various well-known
algorithms for solving either (15) or regularized versions of it, yield regret
that grows sublinearly,

$\text{Regret}_{T}=o(T)\,,$

where we emphasize that this holds almost surely, that is,
$\lim_{T\to\infty}\text{Regret}_{T}/T=0$ a.s. We review some of these
algorithms in Subsection 4.2. The following theorem shows that if regret grows
sublinearly, then the test (1) constructed from the test supermartingale $W$
has asymptotic power one.

######  Theorem 4.2 (Sublinear regret implies asymptotic power).

Let $W=(W_{t})_{t\in{\mathbb{N}}}$ be a predictably mixed test supermartingale
process defined according to (16), generated by a family of test
supermartingales $\\{L^{\theta}\\}_{\theta\in\Theta}$ and a sequence
$(\theta_{t})_{t\in{\mathbb{N}}}$ achieving $\text{Regret}_{T}=o(T)$. Let
$\alpha\in(0,1]$, and let $\tau$ be the test induced by $W$, that is,
$\tau=\inf\\{t\in{\mathbb{N}}\colon W_{t}>\alpha^{-1}\\}$. Suppose that for a
probability measure $Q\notin{\mathcal{H}}_{0}$, there exists
$\theta^{\prime}\in\Theta$ for which

$Q\left(\liminf_{T\to\infty}\frac{\log
L_{T}^{\theta^{\prime}}}{T}>0\right)=1,$ (18)

then

$Q\left(\text{$\tau$ rejects
${\mathcal{H}}_{0}$}\right)=Q(\tau<\infty)=Q\left(\lim_{T\to\infty}\max_{0\leq
t\leq T}W_{t}>\alpha^{-1}\right)=1,$

that is, $\tau$ eventually rejects ${\mathcal{H}}_{0}$ with probability one.

###### Proof.

Using the definition of regret in equation (17), we have that for all
$\theta\in\Theta$,

$\frac{1}{T}\log W_{T}\geq\frac{1}{T}\log L_{T}^{\theta}-\frac{1}{T}B_{T}\;,$

where $B_{T}=\text{Regret}_{T}$. Applying the assumptions that $B_{T}=o(T)$
and (18), we have that

$\displaystyle\liminf_{T\to\infty}\frac{\log\max_{0\leq t\leq
T}W_{t}}{T}\geq\liminf_{T\to\infty}\frac{\log W_{T}}{T}$
$\displaystyle\geq\liminf_{T\to\infty}\left\\{\frac{\log
L_{T}^{\theta^{\prime}}}{T}-\frac{B_{T}}{T}\right\\}=\liminf_{T\to\infty}\frac{\log
L_{T}^{\theta^{\prime}}}{T}>0\;,$

where these inequalities hold $Q$-almost surely. This implies that, $Q$-almost
surely, there exists a $T^{\prime}\in{\mathbb{N}}$ and $\epsilon>0$ such that
$\max_{0\leq t\leq T}W_{t}\geq e^{\epsilon\,T}$ for all $T>T^{\prime}$. Hence,
we may conclude that $\lim_{T\to\infty}\max_{0\leq t\leq
T}W_{t}\geq\lim_{T\to\infty}e^{\epsilon T}=\infty$ $Q$-almost surely, as
desired. ∎

Each of the algorithms presented in Subsection 4.2 achieve sublinear regret,
as required in the statement of Theorem 4.2. The second assumption in Theorem
4.2 that must be met to achieve asymptotic power one, is the existence of a
$\theta^{\prime}$ that satisfies (18). In the next lemma, we show that there
are easily verifiable sufficient conditions to guarantee this condition when
data is generated by a stationary ergodic process.

######  Proposition 4.3.

Suppose that for $Q\notin{\mathcal{H}}_{0}$, the data-generating process
$(X_{t})_{t\in{\mathbb{N}}}$ is stationary and ergodic with invariant measure
$Q_{\infty}$. Let $\\{L_{t}^{\theta}\\}_{\theta\in\Theta}$ be a collection of
${\mathcal{H}}_{0}$ test supermartingales where one of the following
conditions holds.

  1. (i)

${\mathcal{H}}_{0}$ is a uniformly bounded elicitable hypothesis with
$\\{L_{t}^{\theta}\\}_{\theta\in\Theta}$ defined according to Lemma 3.1 where
$\Theta\subseteq\Lambda$ and there exists $\lambda^{\prime}\in\Theta$ such
that
${\mathbb{E}}_{Q_{\infty}}\log\left(1+s(\lambda_{0},X_{\infty})-s(\lambda^{\prime},X_{\infty})\right)>0$.

  2. (ii)

${\mathcal{H}}_{0}$ is a uniformly bounded identifiable hypothesis with
$\\{L_{t}^{\theta}\\}_{\theta\in\Theta}$ defined according to Lemma 3.2 where
$\Theta\subseteq A^{\mathrm{bd}}_{m,\lambda_{0}}$ and there exists
$\eta^{\prime}\in\Theta$ such that
${\mathbb{E}}_{Q_{\infty}}\log\left(1+\langle\eta^{\prime},m(\lambda_{0},X_{\infty})\rangle\right)>0$.

  3. (iii)

${\mathcal{H}}_{0}$ is a sub-$\psi$ elicitable hypothesis with
$\\{L_{t}^{\theta}\\}_{\theta\in\Theta}$ defined according to Lemma 3.6 where
$\Theta=\Theta^{\prime}\times[0,\epsilon)$ in which $0<\epsilon\leq u_{\max}$,
$\Theta^{\prime}\subseteq\Lambda$,
$\lim_{t\to\infty}\tfrac{1}{t}\sum_{i=1}^{t}v_{i}^{\lambda}<\infty$ a.s. for
all $\lambda\in\Lambda$, and there exists $\lambda^{\prime}\in\Theta^{\prime}$
such that
${\mathbb{E}}_{Q_{\infty}}[s(\lambda_{0},X_{\infty})-s(\lambda^{\prime},X_{\infty})]>0$.

  4. (iv)

${\mathcal{H}}_{0}$ is a sub-$\psi$ identifiable hypothesis with
$\\{L_{t}^{\theta}\\}_{\theta\in\Theta}$ defined according to Lemma 3.7 where
$\Theta=\Theta^{\prime}\times[0,\epsilon)$ in which $0<\epsilon\leq u_{\max}$,
$\Theta^{\prime}\subseteq A^{\psi}_{m,\lambda_{0}}$,
$\lim_{t\to\infty}\tfrac{1}{t}\sum_{i=1}^{t}v_{i}^{\eta}<\infty$ a.s. for all
$\eta\in A^{\psi}_{m,\lambda_{0}}$ , and there exists $\eta\in\Theta^{\prime}$
such that
${\mathbb{E}}_{Q_{\infty}}\langle\eta\mathrel{,}m(\lambda_{0},X_{\infty})\rangle>0$.

Then there exists $\theta^{\prime}\in\Theta$ for which (18) holds.

###### Proof.

_Cases (i) and (ii):_ By Lemma 3.1 or 3.2, we may write each test
submartingale as $\log
L_{t}^{\theta}=\sum_{i=1}^{t}\log\left(1+f(\theta,X_{i})\right)$, where we
have either $f(\theta,x)=s(\lambda_{0},x)-s(\theta,x)$ or
$f(\theta,x)=\langle\theta,m(\lambda_{0},x)\rangle$, respectively. Since
$(X_{t})_{t\in{\mathbb{N}}}$ is assumed to be stationary and ergodic under
$Q_{\infty}$, we may apply the Birkhoff-Khintchin ergodic theorem (Cornfeld,
Fomin and Sinai, 2012, Theorem 1) to obtain

$\lim_{t\to\infty}\frac{\log
L_{t}^{\theta}}{t}=\lim_{t\to\infty}\frac{1}{t}\sum_{i=1}^{t}\log\left(1+f(\theta,X_{i})\right)={\mathbb{E}}_{Q_{\infty}}\left[\log\left(1+f(\theta,X_{\infty})\right)\right]\;.$
(19)

_Cases (iii) and (iv):_ By Lemma 3.6 or 3.7, we may write each test
submartingale as

$\log L_{t}^{\theta}=\log
L_{t}^{(\theta^{\prime},u)}=\sum_{i=1}^{t}\left\\{u\,f(\theta^{\prime},X_{i})-v_{i}^{\theta^{\prime}}\psi_{\theta^{\prime}}(u)\right\\}\;,$

where have $u\in[0,\epsilon)$ with $\epsilon>0$, $v_{i}^{\theta^{\prime}}>0$
and, either $f(\theta^{\prime},x)=s(\lambda_{0},x)-s(\theta^{\prime},x)$ in
the elicitable case, or
$f(\theta^{\prime},x)=\langle\theta^{\prime},m(\lambda_{0},x)\rangle$ in the
identifiable case. By assumption, in each case there exists a
$\theta^{\prime}_{0}$ (where $\Theta^{\prime}\subseteq\Lambda$ in the
elicitable case and $\Theta^{\prime}\subseteq A^{\psi}_{m,\lambda_{0}}$ in the
identifiable case) such that
$E_{Q_{\infty}}f(\theta^{\prime}_{0},X_{\infty})=c>0$. Since
$(X_{t})_{t\in{\mathbb{N}}}$ is assumed to be stationary and ergodic under
$Q$, we may apply the Birkhoff-Khintchin ergodic theorem (Cornfeld, Fomin and
Sinai, 2012, Theorem 1) to $L^{(\theta^{\prime}_{0},u)}$ to obtain

$\displaystyle\lim_{t\to\infty}\frac{\log L_{t}^{(\theta^{\prime}_{0},u)}}{t}$
$\displaystyle=\lim_{t\to\infty}\frac{1}{t}\sum_{i=1}^{t}\left\\{u\,f(\theta^{\prime}_{0},X_{i})-v_{i}^{\theta_{0}^{\prime}}\psi_{\theta^{\prime}_{0}}(u)\right\\}$
$\displaystyle=u\,{\mathbb{E}}_{Q_{\infty}}\left[f(\theta^{\prime}_{0},X_{\infty})\right]-\psi_{\theta^{\prime}_{0}}(u)=u\,c-\bar{v}\psi_{\theta^{\prime}_{0}}(u)\;,$

where $0<\bar{v}=\lim_{t\to\infty}\frac{1}{t}\sum_{i=1}^{t}\bar{v}$ which is
non-negative and finite by assumption. By Definition 3.4, we find that
$\psi_{\theta^{\prime}_{0}}(0)=0$ and $\lim_{u\searrow
0}\psi_{\theta^{\prime}_{0}}(0)/u=0$. Hence, letting
$g(u)=u\,c-\bar{v}\psi_{\theta^{\prime}_{0}}(u)$, we find that, $g(0)=0$ and
$g^{\prime}(0)=\lim_{u\searrow 0}g(u)/u=c>0$. Hence, there exists
$u^{\prime}_{0}\in(0,\epsilon)$ such that $g(u^{\prime}_{0})>0$. By picking
this $u^{\prime}_{0}$, we then have that $\lim_{t\to\infty}\log
L_{t}^{(\theta^{\prime}_{0},u^{\prime}_{0})}/t=g(u^{\prime}_{0})=c>0$,
yielding the desired result. ∎

We remark here that two common cases in which Proposition 4.3 may apply are
when $(X_{t})_{t\in{\mathbb{N}}}$ is either i.i.d. or generated by a
stationary, irreducible and aperiodic Markov chain. Moreover, conditions
_(iii)_ and _(iv)_ of Proposition 4.3 hold for any $Q\notin{\mathcal{H}}_{0}$,
which can be seen by inspecting (9) or (10).

To conclude, Theorem 4.2 can be interpreted at a high-level result stating
that whenever there are alternative hypotheses which offer ‘sufficient
evidence against the null’, regret-optimal strategies will asymptotically
reject the null with probability one. Proposition 4.3 quantifies the notion of
‘sufficient evidence against the null’ in the case of a stationary ergodic
data generating process.

###  4.2 Online Convex Optimization Algorithms

We summarize a few simple but effective OCO algorithms that can be applied to
optimizing the predictably mixed test supermartingale
$V=(V_{t})_{t\in{\mathbb{N}}}$ by selecting a sequence of single-asset
portfolios given by $(\theta_{t})_{t\in{\mathbb{N}}}$ which maximize the
growth rate of (16). We point interested readers to Hazan (2016); Shalev-
Shwartz (2011) for a comprehensive introduction to OCO.

For the remainder of the section, we assume that for all $t\in{\mathbb{N}}$,
the maps of forward differences defined on a convex set $\Theta$,

$\theta\mapsto\Delta\log L_{t-1}^{\theta}=\log L_{t}^{\theta}-\log
L_{t-1}^{\theta}$

are concave. We say that a convex function $f:\Theta\rightarrow{\mathbb{R}}$
is strongly convex with parameter $\mu>0$ whenever
$f(\theta_{1})-f(\theta_{0})-\langle\nu_{0},\theta_{1}-\theta_{0}\rangle\geq\mu\|\theta_{1}-\theta_{0}\|^{2}$
for all $\theta_{0},\theta_{1}\in\Theta$, where
$\nu_{0}\in\partial_{\theta}f(\theta_{0})$ is an element the subgradient of
$f$ at $\theta_{0}$. Similarly, $f$ is strongly concave whenever $-f$ is
strongly convex. We define the norm of the subgradient of a convex function
$f:\Theta\rightarrow{\mathbb{R}}$ as
$\|\partial_{\theta}f(\theta)\|=\sup_{\nu\in\partial_{\theta}f(\theta)}\|\nu\|$.

Follow The Leader. We define the Follow The Leader (FTL) algorithm as choosing
at each iteration $t+1$

$\theta_{t+1}\in\operatorname*{argmin}_{\theta\in\Theta}-\log
L_{t}^{\theta}=\operatorname*{argmin}_{\theta\in\Theta}-\sum_{1\leq i\leq
t}\Delta\log L_{i-1}^{\theta}\;.$ (FTL)

Hence, at each iteration, (FTL) picks $\theta\in\Theta$ such that $\log
L_{t}^{\theta}$ has the largest average growth rate in hindsight. Implicitly,
this algorithm assumes that computing the $\operatorname*{argmax}$ at each
round can be done relatively easily. Under the additional assumptions that (i)
$\sup_{\theta\in\Theta}\|\partial_{\theta}(-\Delta\log L_{t-1}^{\theta})\|\leq
G<\infty$ and (ii) the $\Delta\log{L_{t}^{\theta}}$ are strongly concave, we
have that $\text{Regret}_{T}\leq\frac{G^{2}}{2}(1+\log T)$. We point the
reader to McMahan (2017, §3.6) for a derivation of this bound. This algorithm
is not recommended for the case when $\Delta\log L_{t}^{\theta}$ are not
strongly concave. Indeed, it is possible to create counterexamples, such as
those presented in Shalev-Shwartz (2011, Example 2.2) or Hazan (2016, Page
65), of non strongly-concave functions where the algorithm induces super-
linear growth in the regret. The bounded gradient assumption (i) will be
satisfied by, for example, Lipschitz continuous functions.

Follow The Regularized Leader. A simple fix for this problem leads to the
second algorithm, which involves the inclusion of regularization, increasing
the algorithm’s stability. The most obvious implementation of this concept is
the Follow The Regularized Leader (FTRL) algorithm, in which we introduce
regularization terms to the optimization problem in (FTL). Precisely, at each
iteration $t+1$, FTRL selects

$\theta_{t+1}\in\operatorname*{argmin}_{\theta\in\Theta}\left\\{-\log
L_{t}^{\theta}+\sum_{1\leq i\leq t}r_{i-1}(\theta)\right\\}\;,$ (FTRL)

where the $\\{r_{t}\\}_{t\in{\mathbb{N}}}$ are a sequence of strongly convex
functions for which either (a)
$x_{0}=\operatorname*{argmin}_{\theta\in\Theta}r_{t}(\theta)$ for all $t$, in
which the algorithm is the _FTRL-Centered_ variant or (b) for which we assume
that $x_{t}=\operatorname*{argmin}_{\theta\in\Theta}r_{t}(\theta)$ where this
variant is named _FTRL-Proximal_. Under the additional assumptions that (i)
$\sup_{\theta\in\Theta}\|\partial_{\theta}(-\Delta\log L_{t-1}^{\theta})\|\leq
G<\infty$ and that (ii)
$\operatorname{diam}(\Theta)=\sup_{x,y\in\Theta}\|x-y\|<\infty$, one can
devise a sequence of centered or proximal regularizers
$\\{r_{t}\\}_{t\in{\mathbb{N}}}$ such that the algorithms enjoy the regret
bound $\text{Regret}_{T}=O(\sqrt{T})$. We point the reader to McMahan (2017,
Section 3) for a summary of the exact conditions and specific bounds.

Online Gradient Descent. The $\operatorname*{argmin}$ expressions in (FTL) and
(FTRL) may be difficult to compute directly introducing problems in the
implementation of FTL or FTRL. Instead, using gradients collected in each
step, one can follow the direction of steepest ascent of $\Delta\log
L_{t-1}^{\theta}$ at each iteration. This produces the Online Gradient Descent
(OGD) algorithm, where we choose at each iteration

$\theta_{t+1}=\Pi_{\Theta}\left\\{\theta_{t}-\eta_{t}\nu_{t}\right\\}\text{
where
}\nu_{t}\in\partial_{\theta}\left(-\Delta\log{L_{t-1}^{\theta}}\right)\;,$
(OGD)

where $\\{\eta_{t}\\}_{t\in{\mathbb{N}}}$ is a sequence of positive learning
rates and $\Pi_{\Theta}(x)=\operatorname*{argmin}_{y\in\Theta}\|y-x\|$ is the
projection operator. This algorithm has the advantage that it is extremely
simple to compute, provided that gradients are available at each step. For an
appropriate choice of $\\{\eta_{t}\\}_{t\in{\mathbb{N}}}$, and under the
additional assumption that (i)
$\sup_{\theta\in\Theta}\|\partial_{\theta}(-\Delta\log\left(L_{t-1}^{\theta}\right))\|\leq
G<\infty$ and (ii) $\operatorname{diam}(\Theta)<\infty$, the algorithm has a
regret bound of $\text{Regret}_{T}=O(\sqrt{T})$. We point the reader to
Zinkevich (2003) and McMahan (2017, §3.1) for the specific bounds and
conditions.

We summarize the bounds and assumptions for the OCO algorithms in Table 2,
where we emphasize that the growth rate of the regret in the right-hand column
holds almost surely regardless of the data-generating measure. Beyond the
algorithms presented here, there exist a plethora of online optimization
algorithms which may leverage the geometry of the index set $\Theta$ or past
information about gradients in order to improve rates of convergence. For a
broader survey of available OCO algorithms, we point the reader to Hazan
(2016); Shalev-Shwartz (2011); McMahan (2017). We also point out that although
the algorithms here offer guarantees for convex loss functions, they can in
principle be used on non-convex optimization problems as well. However, while
still yielding valid tests, the worst-case guarantees may no longer hold.

The use of OCO methods for building more powerful predictably mixed test
supermartingales is related to various online methods presented in Waudby-
Smith and Ramdas (2020) for confidence sequence building for means of bounded
random variables. In particular, Kelly betting (Waudby-Smith and Ramdas, 2020,
§5.2,5.3,5.6) can be interpreted as a variation of the FTL algorithm to a
family of processes of the form of Lemma 3.2 for bounded identifiable
functionals. Similarly, the Online Newton Step Algorithm discussed in Waudby-
Smith and Ramdas (2020, §5.5) can be thought of another method in the family
of OCO algorithms. The authors of Waudby-Smith and Ramdas (2020) acknowledge
and elaborate on the connection between their confidence sequence building
methods with OCO and coin-betting algorithms in Waudby-Smith and Ramdas (2020,
Appendix D) but they do not use regret bounds to derive asymptotic power
guarantees.

Although largely ignored over the course of this section, another important
aspect to consider when selecting an algorithm for online convex optimization
is the computational complexity of the algorithm. For example, it is typically
the case that (FTL), (FTRL) or other loss-minimization based algorithms will
be run slower than gradient-based algorithms such as (OGD). On the other hand,
although (OGD) and (FTRL) have similar asymptotic performance, we typically
find that (FTRL) may perform better on average, which can be reflected in the
constants associated with their regret bounds, see for example McMahan (2017).

| Assumptions |
---|---|---
Algorithm | $-\Delta\log W_{t}(\theta)$ | $\text{diam}(\Theta)$ | $\text{Regret}_{T}$
FTL | strongly-convex + bounded gradients | any | $O(\log T)$
FTRL | bounded gradients | $\leq R$ | $O(\sqrt{T})$
OGD | bounded gradients | $\leq R$ | $O(\sqrt{T})$
Table 2: Summary of assumptions and regret bounds for the OCO algorithms
presented in Section 4.2.

Although the OCO algorithms presented in Section 4.2 offer regret guarantees
which translate into asymptotic power, it is possible to generalize these
methods in order to further improve performance in special cases. The
algorithms FTL, FTRL and OGD, attempt to maximize some version of the data-
generated objective function

$\theta\mapsto\frac{1}{t}\log
L_{t}^{\theta}=\frac{1}{t}\sum_{i=1}^{t}\Delta\log
L^{\theta}(X_{i})={\mathbb{E}}_{\hat{P}_{t}}\left[\Delta\log
L^{\theta}(X)\right]\;,$ (20)

where we write $\Delta\log L_{i}^{\theta}=\Delta\log L^{\theta}(X_{i})$ as an
explicit function of the data point $X_{i}$, and where
${\mathbb{E}}_{\hat{P}_{t}}$ represents the expected value with respect to the
empirical measure $\hat{P}_{t}=\frac{1}{t}\sum_{i=1}^{t}\delta(X-X_{i})$.

If additional distributional information is known about
$\\{X_{t}\\}_{t\in{\mathbb{N}}}$, one could replace the empirical distribution
$\hat{P}_{t}$ with a predictive measure $\tilde{P}_{t}$ which may better
represent the true data distribution. Modifying (FTL) with this new measure,
one obtains the algorithm

$\theta_{t+1}\in\operatorname*{argmin}_{\theta\in\Theta}{\mathbb{E}}_{\tilde{P}_{t}}\left[\log\Delta
L^{\theta}(X)\right]\;,$ (FTLP)

and the same principle can be applied to modify both, (FTRL) and (OGD). The
fact that we have complete freedom in choosing $\tilde{P}_{t}$ at each step
can be a major advantage of the betting approach to sequential testing, as has
been discussed in detail elsewhere; see Ramdas et al. (2022); Waudby-Smith and
Ramdas (2020).

##  5 Confidence Sequences and Inverting Tests

Our focus has been on methodology for testing elicitable and identifiable
hypotheses in a sequential setting. However, the techniques we have developed
allow for the construction of anytime-valid confidence sequences. Given a
functional
$T(P):{\mathcal{M}}_{1}({\mathcal{X}})\to\Lambda\subseteq{\mathbb{R}}^{d}$
define an _anytime-valid confidence sequence_ $\\{C_{t}\\}_{t\in{\mathbb{N}}}$
_at level_ $\alpha\in(0,1)$ as a sequence $(C_{t})_{t\in{\mathbb{N}}}$ of
confidence sets $C_{t}\subseteq\Lambda$ for all $t\in{\mathbb{N}}$, satisfying
the property that

$\sup_{P\in{\mathcal{H}}_{0}(\lambda_{0})}P\left(\forall
t\in{\mathbb{N}}\colon\lambda_{0}\notin C_{t}\right)\leq\alpha\;,$ (21)

for any $\lambda_{0}\in\Lambda$. Here, ${\mathcal{H}}_{0}(\lambda_{0})$
denotes the null hypothesis at (8) where we now emphasize the dependence on
$\lambda_{0}$ in the notation. Equation (21) can be interpreted as
guaranteeing that, with high probability, the true value of the functional,
$\lambda_{0}\in T(P)$ is contained within, not only a single confidence set,
but the entire sequence of confidence sets at once.

Using the anytime-valid hypothesis testing methodology, we can construct such
confidence sequences for the elicitable and identifiable martingale hypotheses
of the form (9) and (10). Assume that for each $\lambda_{0}\in\Lambda$ there
exists an ${\mathcal{H}}_{0}(\lambda_{0})$ test supermartingale denoted by
$V^{\lambda_{0}}=(W_{t}^{\lambda_{0}})_{t\in{\mathbb{N}}}$. Each
$W^{\lambda_{0}}$ induces an anytime-valid test for
${\mathcal{H}}_{0}(\lambda_{0})$, so we may construct an anytime-valid
confidence sequence $C=(C_{t})_{t\in{\mathbb{N}}}$ by ‘inverting’ these tests
as follows. For each $t\in{\mathbb{N}}$, we define

$C_{t}=\left\\{\lambda\in\Lambda\colon\max_{0\leq i\leq
t}V_{i}^{\lambda}\leq\alpha^{-1}\right\\}\;,$ (22)

the set of $\lambda$ whose associated null hypotheses have not yet been
rejected by the tests induced by the associated $W^{\lambda_{0}}$. This
construction produces an anytime-valid confidence sequence since
$\sup_{P\in{\mathcal{H}}_{0}(\lambda_{1})}P(\exists t\,\text{ s.t.\
}\colon\lambda_{1}\notin
C_{t})=\sup_{P\in{\mathcal{H}}_{0}(\lambda_{1})}P(\max_{t\in{\mathbb{N}}}W_{t}^{\lambda_{1}}>\alpha^{-1})\leq\alpha$.

We may apply the techniques from previous sections to construct confidence
sequences for elicitable and identifiable functionals as follows. Depending on
whether the functional $T$ in question is elicitable or identifiable and on
whether it is _uniformly bounded_ or _sub- $\psi$_, for each
$\lambda_{0}\in\Lambda_{0}$ we construct a family of test supermartingales
according to Lemmas 3.1, 3.2, 3.6 or 3.7, which we use to construct a mixture
test supermartingale $W^{\lambda_{0}}$ according to Lemma 2.4. In Appendix A,
we show how this methodology can be extended for the purpose of testing one-
sided and set-valued hypotheses.

##  6 Numerical Examples

We begin by applying our tests to sequences of independent and identically
distributed data. Let $\\{X_{t}\\}_{t\in{\mathbb{N}}}\sim\text{ i.i.d.
}\text{Beta}(\alpha,\beta)$, where $\alpha=2$ and $\beta=5$ are the parameters
of the beta distribution.

Our first experiment will be to test the mean and standard deviation of this
data generating process, simultaneously. That is, we consider a functional
$T:{\mathcal{M}}_{1}({\mathcal{X}})\to{\mathbb{R}}^{2}$ where
$T(Q)=({\mathbb{E}}_{Q}[X_{t}],\sqrt{{\mathbb{V}}_{Q}[X_{t}]})^{\prime}$.
Under the assumed ground truth data generating measure $P_{\text{GT}}$, the
value of this functional is approximately
$T(P_{\text{GT}})\approx\left(\begin{smallmatrix}0.3\\\
0.16\end{smallmatrix}\right)$. First, we are interested in testing the null
hypothesis

${\mathcal{H}}_{0}=\left\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\,:\,T(P(X_{t}\in\cdot\mid{\mathcal{F}}_{t-1}))=\left(\begin{smallmatrix}0.4\\\
0.4\end{smallmatrix}\right)\text{ for all }t\in{\mathbb{N}},\
P\text{-a.s.}\right\\}.$ (23)

Although this functional is both an elicitable and identifiable functional, we
choose to test is as the latter, where we use the identification function
$m\left((\lambda_{\mu},\lambda_{\sigma}),x\right)=(\lambda_{\mu}-x,\lambda_{\mu}^{2}+\lambda_{\sigma}^{2}-x^{2})^{\prime}$
which satisfies the uniform boundedness conditions required in order to
generate a family of test supermartingales according to Lemma 3.2. Using this
family of tests, we apply the FTL algorithm. The result of this test and of a
confidence set on a single simulated path of the data generating process is
displayed in Figure 1.

(a) Test supermartingale and rejection threshold.

(b) 95% confidence set at $t=50$.

Figure 1:  Hypothesis tests and confidence sets for the joint mean and
standard deviation of the i.i.d. Beta data generating process. (1(a)) The path
of the test supermartingale $W_{t}$ constructed to test the hypothesis (23)
(blue) with $\alpha=0.05$ rejection threshold (red). (1(b)) The anytime-valid
confidence set obtained at $t=50$ (yellow line). The color gradient represents
the value of $\log(W_{50})$ over the space of possible of null hypotheses. The
white $\star$ represents the true parameter values, and the red x represents
the null hypothesis that is being tested in Figure (1a).

We conduct a second experiment with the same data generating distribution on
the elicitable functional
$T(Q)=(\text{VaR}_{0.05}(Q),\text{CVaR}_{0.05}(Q))^{\prime}$, producing both
the Value-at-Risk, that is, the 5%-quantile, and conditional Value-at-Risk or
expected shortfall, that is ${\mathbb{E}}_{Q}[X_{i}\mid
X_{i}<\text{VaR}_{0.05}(Q)]$, where this functional is identifiable with
identification function
$m((\lambda_{v},\lambda_{c}),x)=(\mathds{1}_{x\leq\lambda_{v}}-\alpha_{0},x\mathds{1}_{x\leq\lambda_{v}}-\alpha_{0}\lambda_{c})^{\prime}$
where $\alpha_{0}=0.05$, see Fissler and Ziegel (2016, Theorem 5.2). We test
the hypothesis

${\mathcal{H}}_{0}=\left\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\colon
T(P(X_{t}\in\cdot\mid{\mathcal{F}}_{t-1}))=\begin{pmatrix}0.2\\\
0.1\end{pmatrix}\text{ for all }t\in{\mathbb{N}},\ P\text{-a.s.}\right\\}$
(24)

where we approximately have that
$T(P_{\text{GT}})\approx\left(\begin{smallmatrix}0.06\\\
0.04\end{smallmatrix}\right)$ under the true data generating measure
$P_{\text{GT}}$. Since the underlying random variables are bounded, we
construct a composite test supermartingale using the family of test
supermartingales for uniformly bounded elicitable hypotheses given in Lemma
3.1. We optimize this composite martingale using the FTL algorithm.

(a) Test supermartingale and rejection threshold.

(b) 95% confidence set at $t=150$

Figure 2:  Hypothesis tests and confidence sets for the joint quantile and
expected shortfall of the i.i.d. Beta data generating process. (2(a)) The path
of the test supermartingale $W_{t}$ constructed to test the hypothesis (24)
(blue) with $\alpha=0.05$ rejection threshold (red). (2(b)) The anytime-valid
confidence set obtained at $t=50$ (white line). The color gradient represents
the value of $\log(W_{50})$ over the space of possible of null hypotheses,
lying in the space of values such that
$\text{CVaR}_{0.05}\leq\text{VaR}_{0.05}$. The white $\star$ represents the
true parameter values, and the red x represents the null hypothesis that is
being tested in Figure (2a).

Let us now consider the problem of estimating the linear coefficient of an
AR(1) model. Specifically, assume that the data generating process is

$X_{t+1}=\beta X_{t}+\xi_{t+1}\,$

where the $\\{\xi_{t}\\}_{t\in{\mathbb{N}}}$ are a 1-sub-Gaussian martingale
difference sequence. This assumption may be replaced with $\sigma$-sub-
Gaussianity for any $\sigma>0$ with straightforward minor modifications. We
are interested in estimating and testing hypotheses regarding the value of
$\beta\in{\mathbb{R}}$. For this purpose, we write this coefficient as the
functional
$\beta(P(\cdot\mid{\mathcal{F}}_{t}))=\min_{\beta^{\prime}\in{\mathbb{R}}}{\mathbb{E}}_{P}[(X_{t+1}-\beta^{\prime}X_{t})^{2}\mid{\mathcal{F}}_{t}]$,
which admits the identification function
$m(\beta_{0},(x_{t},x_{t+1}))=(x_{t}/|x_{t}|)(\beta_{0}x_{t}-x_{t+1})$ which
will be $1$-sub-Gaussian with $\psi(u)=\frac{1}{2}u^{2}$ as shown in Example
3. Hence, we may define the family of test supermartingales,

$L_{t}^{\eta}=\prod_{i=1}^{t}\exp\left(\eta\,m(\beta_{0},(x_{i},x_{i+1}))-\frac{\eta^{2}}{2}\right)\;,$

indexed by $\eta\in\Theta={\mathbb{R}}$. Using this family of test
supermartingales and noting that $\eta\mapsto\log L_{t}^{\eta}$ is strongly
concave, we construct a composite test supermartingale by applying the the FTL
algorithm. This update rule has the advantage that it can be computed in
closed form at each iteration. Indeed, letting
$\overline{m}_{t}=(1/t)\sum_{i=1}^{t}m(\beta_{0},(x_{i},x_{i+1}))$, we have
the update rule
$\eta_{t+1}=\operatorname*{argmin}_{\eta\in\Theta}\left\\{-\log
L_{t}^{\eta}\right\\}=\operatorname*{argmax}_{\eta\in{\mathbb{R}}}\left\\{\eta\,\overline{m}_{t}-\frac{1}{2}\eta^{2}\right\\}=\overline{m}_{t}$.
Applying this OCO algorithm to randomly generated data from the $AR(1)$
process, we test the hypothesis that
${\mathcal{H}}_{0}=\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\,:\,\beta(P(\cdot\mid{\mathcal{F}}_{t}))=0.65\;\text{for
all }t\in{\mathbb{N}}\\}$ when data is generated from an $AR(1)$ process with
$\beta=0.5$ and where $\\{\epsilon_{t}\\}_{t\in{\mathbb{N}}}$ are i.i.d. with
$\epsilon_{t}\sim{\mathcal{N}}(0,0.8)$. The results of this hypothesis test
are displayed in Figure 3(a). Similarly, in Figure 3(b), we display the
running anytime-valid confidence sequence generated using the method described
in Section 5.

(a) Testing

(b) Confidence Sequence

Figure 3: Hypothesis tests and confidence sets for the parameter $\beta$ of an
AR(1) data generating process. (3(a)) The path of the test supermartingale
$W_{t}$ (blue) constructed and the rejection threshold (red), constructed to
test the hypothesis that $\beta(P(\cdot\mid{\mathcal{F}}_{t}))=0.65$ at the
level $\alpha=0.05$. (3(b)) The boundary of the anytime-valid confidence
sequence (white) and the running estimate of the parameter $\beta$ (red). The
color gradient represents the value of $\log(W_{t})$ over the space of
possible of null hypotheses ($y$ axis) at each point in time.

## References

  * Albers (2019) [author] Albers, CasperC. (2019). The problem with unadjusted multiple and sequential statistical testing. Nature Communications 10 1–4.
  * Caponnetto (2005) [author] Caponnetto, AndreaA. (2005). A note on the role of squared loss in regression CBCL Paper, Massachusetts Institute of Technology, Cambridge, MA.
  * Cornfeld, Fomin and Sinai (2012) [author] Cornfeld, Isaac PI. P., Fomin, Sergei VasilevichS. V. and Sinai, Yakov Grigor’evǐcY. G. (2012). Ergodic Theory. Springer, New York, NY.
  * de la Peña, Klass and Lai (2004) [author] de la Peña, Victor H.V. H., Klass, Michael J.M. J. and Lai, Tze LeungT. L. (2004). Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws. The Annals of Probability 32 1902 – 1933. 10.1214/009117904000000397
  * Dimitriadis, Fissler and Ziegel (2020) [author] Dimitriadis, TimoT., Fissler, TobiasT. and Ziegel, Johanna FJ. F. (2020). The Efficiency Gap. arXiv preprint arXiv:2010.14146.
  * Fissler (2017) [author] Fissler, T.T. (2017). On Higher Order Elicitability and Some Limit Theorems on the Poisson and Wiener Space, PhD thesis, University of Bern.
  * Fissler and Ziegel (2016) [author] Fissler, T.T. and Ziegel, J. F.J. F. (2016). Higher order elicitability and Osband’s principle. Annals of Statistics 44 1680–1707.
  * Freedman (1975) [author] Freedman, David A.D. A. (1975). On Tail Probabilities for Martingales. The Annals of Probability 3 100 – 118. 10.1214/aop/1176996452
  * Frongillo and Kash (2021) [author] Frongillo, R.R. and Kash, I. A.I. A. (2021). Elicitation complexity of statistical properties. Biometrika 108 857–879.
  * Gneiting (2011) [author] Gneiting, TilmannT. (2011). Making and evaluating point forecasts. Journal of the American Statistical Association 106 746–762.
  * Grünwald, de Heide and Koolen (2019) [author] Grünwald, PeterP., de Heide, RianneR. and Koolen, WouterW. (2019). Safe Testing. arXiv preprint arXiv:1906.07801.
  * Hagerup and Rüb (1990) [author] Hagerup, TorbenT. and Rüb, ChristineC. (1990). A guided tour of Chernoff bounds. Information Processing Letters 33 305–308. https://doi.org/10.1016/0020-0190(90)90214-I
  * Hazan (2016) [author] Hazan, EladE. (2016). Introduction to Online Convex Optimization. Foundations and Trends in Optimization 2 157–325.
  * Henzi and Ziegel (2021) [author] Henzi, AlexanderA. and Ziegel, Johanna FJ. F. (2021). Valid sequential inference on probability forecast performance. Biometrika. asab047. 10.1093/biomet/asab047
  * Hertz (2020) [author] Hertz, DavidD. (2020). Improved Hoeffding’s lemma and Hoeffding’s tail bounds. arXiv preprint arXiv:2012.03535.
  * Hoeffding (1994) [author] Hoeffding, WassilyW. (1994). Probability inequalities for sums of bounded random variables. In The Collected Works of Wassily Hoeffding 409–426. Springer, New York, NY.
  * Howard et al. (2020) [author] Howard, Steven R.S. R., Ramdas, AadityaA., McAuliffe, JonJ. and Sekhon, JasjeetJ. (2020). Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys 17 257–317. 10.1214/18-PS321 4100718
  * Howard et al. (2021) [author] Howard, Steven R.S. R., Ramdas, AadityaA., McAuliffe, JonJ. and Sekhon, JasjeetJ. (2021). Time-uniform, nonparametric, nonasymptotic confidence sequences. Annals of Statistics 49 1055–1080. 10.1214/20-aos1991 4255119
  * Hsu (1996) [author] Hsu, JasonJ. (1996). Multiple comparisons: theory and methods. Chapman & Hall/CRC, Boca Raton.
  * Komunjer and Vuong (2010a) [author] Komunjer, IvanaI. and Vuong, QuangQ. (2010a). Semiparametric efficiency bound in time-series models for conditional quantiles. Econometric Theory 26 383–405.
  * Komunjer and Vuong (2010b) [author] Komunjer, IvanaI. and Vuong, QuangQ. (2010b). Efficient estimation in dynamic conditional quantile models. Journal of Econometrics 157 272–285.
  * Lambert, Pennock and Shoham (2008) [author] Lambert, N.N., Pennock, D. M.D. M. and Shoham, Y.Y. (2008). Eliciting properties of probability distributions. In Proceedings of the 9th ACM Conference on Electronic Commerce 129–138. Extended abstract.
  * McMahan (2017) [author] McMahan, H BrendanH. B. (2017). A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research 18 3117–3166.
  * O’neill and Wetherill (1971) [author] O’neill, RR. and Wetherill, GBG. (1971). The present state of multiple comparison methods. Journal of the Royal Statistical Society: Series B 33 218–250.
  * Osband (1985) [author] Osband, K. H.K. H. (1985). Providing incentives for better cost forecasting, PhD thesis, University of California, Berkeley.
  * Ramdas et al. (2020) [author] Ramdas, AadityaA., Ruf, JohannesJ., Larsson, MartinM. and Koolen, WouterW. (2020). Admissible anytime-valid sequential inference must rely on nonnegative martingales. arXiv preprint arXiv:2009.03167.
  * Ramdas et al. (2022) [author] Ramdas, AadityaA., Ruf, JohannesJ., Larsson, MartinM. and Koolen, Wouter M.W. M. (2022). Testing exchangeability: Fork-convexity, supermartingales and e-processes. International Journal of Approximate Reasoning 141 83–109. 10.1016/j.ijar.2021.06.017 4364897
  * Rockafellar and Wets (2009) [author] Rockafellar, R TyrrellR. T. and Wets, Roger J-BR. J.-B. (2009). Variational analysis. Springer, Berlin, Heidelberg.
  * Savage (1971) [author] Savage, L. J.L. J. (1971). Elicitation of personal probabilities and expectations. Journal of the American Statistical Association 66 783–801.
  * Shafer et al. (2011) [author] Shafer, GlennG., Shen, AlexanderA., Vereshchagin, NikolaiN. and Vovk, VladimirV. (2011). Test martingales, Bayes factors and $p$-values. Statistical Science 26 84–101. 10.1214/10-STS347 2849911
  * Shalev-Shwartz (2011) [author] Shalev-Shwartz, ShaiS. (2011). Online learning and online convex optimization. Foundations and Trends in Machine Learning 4 107–194.
  * Steinwart et al. (2014) [author] Steinwart, IngoI., Pasin, ChloéC., Williamson, RobertR. and Zhang, SiyuS. (2014). Elicitation and identification of properties. In Conference on Learning Theory 482–526. PMLR.
  * Ville (1939) [author] Ville, JeanJ. (1939). Étude critique de la notion de collectif. Thèses de l’entre-deux-guerres 218\. 3533075
  * Vovk and Wang (2021) [author] Vovk, VladimirV. and Wang, RuoduR. (2021). E-values: Calibration, combination and applications. Annals of Statistics 49 1736 – 1754. 10.1214/20-AOS2020
  * Wald (1945) [author] Wald, A.A. (1945). Sequential tests of statistical hypotheses. Annals of Mathematical Statistics 16 117–186. 10.1214/aoms/1177731118 13275
  * Waudby-Smith and Ramdas (2020) [author] Waudby-Smith, IanI. and Ramdas, AadityaA. (2020). Estimating means of bounded random variables by betting. arXiv preprint arXiv:2010.09686.
  * Xu, Wang and Ramdas (2021) [author] Xu, ZiyuZ., Wang, RuoduR. and Ramdas, AadityaA. (2021). A unified framework for bandit multiple testing. arXiv preprint arXiv:2107.07322.
  * Zinkevich (2003) [author] Zinkevich, MartinM. (2003). Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning 928–936.

##  Appendix A One-Sided and Set-Valued Hypotheses

The methodology considered in this paper may be extended towards testing one-
sided and more generally, set-valued hypotheses on elicitable and identifiable
functionals. Indeed, for a set $K\subseteq\Lambda$ let us consider the
hypothesis

${\mathcal{H}}_{0}(K)=\left\\{P\in{\mathcal{M}}_{1}({\mathcal{X}}^{\mathbb{N}})\colon
T(P(X_{t}\in\cdot\mid{\mathcal{F}}_{t-1}))\subset K\text{ for all
}t\in{\mathbb{N}},\text{ $P$-a.s.}\right\\}.$

where $K$ can be thought of as a set or interval in which we believe the
functional $T$ should lie when applied to the data-generating measure.

We can test the hypothesis ${\mathcal{H}}_{0}(K)$ by building an e-process out
of test supermartingales for pointwise hypotheses. Indeed, for each
$\lambda_{0}\in K$, assume that $(W^{\lambda_{0}}_{t})_{t\in{\mathbb{N}}}$ is
a test supermartingale for
${\mathcal{H}}_{0}(\\{\lambda_{0}\\})={\mathcal{H}}_{0}(\lambda_{0})$ given at
(8). If we define the composite process $(M_{t}^{K})_{t\in{\mathbb{N}}}$ as
$M_{t}^{K}=\min_{\lambda_{0}\in K}W_{t}^{\lambda_{0}}$, it is easy to see that
for any ${\mathcal{F}}$-adapted stopping stopping time $\tau$, we have that

${\mathbb{E}}\left[M_{\tau}^{K}\right]={\mathbb{E}}\left[\min_{\lambda_{0}\in
K}W_{\tau}^{\lambda_{0}}\right]\leq\min_{\lambda_{0}\in
K}{\mathbb{E}}\left[W_{t}^{\lambda_{0}}\right]\leq 1\;,$

showing that $M_{\tau}^{K}>\alpha^{-1}$ can serve as a valid test for
${\mathcal{H}}_{0}^{K}$. In principle, any test derived over the course of
this paper for pointwise hypotheses can be used to generate the set of test
supermartingales $W_{t}^{\lambda_{0}}$ used to test the set-valued hypothesis.

##  Appendix B Proofs

###  B.1 Proof of Lemma 2.4

###### Proof.

Since $W$ is nonnegative and $W_{0}=1$, we only need to check the
$P$-supermartingale property for any $P\in{\mathcal{H}}_{0}$. For each
$t\in{\mathbb{N}}$ we use Tonelli’s theorem, the fact that $W_{t}$ and
$\pi_{t+1}$ are ${\mathcal{F}}_{t}$-measurable, the $P$-supermartingale
property of $L^{\theta}$, and the fact that $\pi_{t+1}$ has total mass one, to
obtain

$\displaystyle{\mathbb{E}}_{P}\left[W_{t+1}\mid{\mathcal{F}}_{t}\right]$
$\displaystyle=W_{t}\,{\mathbb{E}}_{P}\left[\int_{\theta\in\Theta}\frac{L_{t+1}^{\theta}\;}{L_{t}^{\theta}}\,\pi_{t+1}(d\theta)\mid{\mathcal{F}}_{t}\right]$
$\displaystyle=W_{t}\,\int_{\theta\in\Theta}{\mathbb{E}}_{P}\left[\frac{L_{t+1}^{\theta}\;}{L_{t}^{\theta}}\,\mid{\mathcal{F}}_{t}\right]\pi_{t+1}(d\theta)\leq
W_{t}\,\pi_{t+1}(\Theta)=W_{t}.$

This shows that $W$ is a $P$-supermartingale.

###  B.2 Proof of Lemma 3.1

First, we note that
$\inf_{\lambda\in\Lambda,x\in{\mathcal{X}}}\\{s(\lambda_{0},x)-s(\lambda^{\prime},x)\\}>-1$
implies that each $L^{\lambda}$ is nonnegative. Next, for each
$t\in{\mathbb{N}}$, $\lambda\in\Lambda$ and $P\in{\mathcal{H}}_{0}$, we may
compute

$\displaystyle{\mathbb{E}}_{P}\left[L_{t+1}^{\lambda}\mid{\mathcal{F}}_{t}\right]=L_{t}^{\lambda}\left(1+{\mathbb{E}}_{P}\left[s(\lambda_{0},X_{t+1})-s(\lambda^{\prime},X_{t+1})\mid{\mathcal{F}}_{t}\right]\right)\;.$

By assumption, since $P\in{\mathcal{H}}_{0}$ with ${\mathcal{H}}_{0}$ defined
according to equation (9), we have that

$-1<{\mathbb{E}}_{P}\left[s(\lambda_{0},X_{t+1})-s(\lambda^{\prime},X_{t+1})\mid{\mathcal{F}}_{t}\right]\leq
0\;,$

which implies that

$L^{\lambda}_{t}\left(1+{\mathbb{E}}_{P}\left[s(\lambda_{0},X_{t+1})-s(\lambda^{\prime},X_{t+1})\mid{\mathcal{F}}_{t}\right]\right)\leq
L^{\lambda}_{t}\;,$

and hence
${\mathbb{E}}_{P}\left[L_{t+1}^{\lambda}\mid{\mathcal{F}}_{t}\right]\leq
L^{\lambda}_{t}$. Lastly, $L^{\lambda}_{0}=1$.

∎

###  B.3 Proof of Lemma 3.2

###### Proof.

We begin with the proof that $A^{\mathrm{bd}}_{m,\lambda_{0}}$ is convex with
non-empty interior. By assumption, there exists $C>0$ such that
$\sup_{x\in{\mathcal{X}}}\|m(\lambda_{0},x)\|\leq C<\infty$. Hence, for any
$\|\eta\|<1/C$, we have by the Cauchy-Schwarz inequality that

$\langle\eta,m(\lambda_{0},x)\rangle\geq-\|\eta\|\|m(\lambda_{0},x)\|\geq-\|\eta\|\sup_{x\in{\mathcal{X}}}\|m(\lambda_{0},x)\|>-1\;,$

showing that $A^{\mathrm{bd}}_{m,\lambda_{0}}$ has non-empty interior.
Convexity follows from linearity of the scalar product in the first argument.

For $\eta\in A^{\mathrm{bd}}_{m,\lambda_{0}}$, we have
$1+\langle\eta\mathrel{,}m(\lambda_{0},x_{i})\rangle>0$, and hence the
$L^{\eta}$ are all nonnegative. For each $t\in{\mathbb{N}}$, and
$P\in{\mathcal{H}}_{0}$, it holds that

$\displaystyle{\mathbb{E}}_{P}\left[L_{t+1}^{\eta}\mid{\mathcal{F}}_{t}\right]=L_{t}^{\eta}\left(1+\langle\eta\mathrel{,}{\mathbb{E}}_{P}\left[m(\lambda_{0},x_{i})\mid{\mathcal{F}}_{t}\right]\rangle\right)\;.$

By equation (10), we have that
${\mathbb{E}}_{P}\left[\langle\eta\mathrel{,}m(\lambda_{0},X_{i})\rangle\mid{\mathcal{F}}_{t}\right]=0$
and thus
${\mathbb{E}}_{P}\left[L_{t+1}^{\eta}\mid{\mathcal{F}}_{t}\right]=L_{t}^{\eta}$
for all $t$. Lastly, since $L_{0}^{\eta}=1$ and $L_{t}^{\eta}>0$ we conclude
that $L^{\eta}$ is an ${\mathcal{H}}_{0}$ test martingale. ∎

###  B.4 Proof of Lemmas 3.6 and 3.7

###### Proof.

Let us first consider the setting of Lemma 3.6. By construction, each of the
processes $L^{\lambda,u}$ is nonnegative and satisfies $L^{\lambda,u}_{0}=1$.
Fixing $(\lambda,u)$, we have that for all $P\in{\mathcal{H}}_{0}$,

$\displaystyle{\mathbb{E}}_{P}\left[L^{\lambda,u}_{t+1}\mid{\mathcal{F}}_{t}\right]={\mathbb{E}}_{P}\left[e^{uY_{t+1}^{\lambda}-V_{t+1}^{\lambda}\psi_{\lambda}(u)}\mid{\mathcal{F}}_{t}\right]\leq
e^{uY_{t}^{\lambda}-V_{t}^{\lambda}\psi_{\lambda}(u)}=L^{\lambda,u}_{t}\text{
a.s.},$

which follows by noting that $Y^{\lambda}$ is a supermartingale according to
the definition of ${\mathcal{H}}_{0}$ and by applying Lemma 3.5. Hence, each
$L^{\lambda,u}$ is a valid test supermartingale.

For Lemma 3.7, we note that the proof works analogously to that of Lemma 3.6.
∎

###  B.5 Proof of Lemma 4.1

###### Proof.

We prove this claim by proving it for the four separate classes of test
supermartingales of Lemmas 3.1, 3.2, 3.6 and 3.7.

_Lemma 3.1._ In this case, the family of test supermartingales
$\\{L^{\theta}\\}_{\theta\in\Theta}$, where $\theta=\lambda\in\Lambda$, can be
written as

$\log L^{\theta}_{t}=\sum_{1\leq i\leq
t}\log\left(1+s(\lambda_{0},x_{i})-s(\lambda,x_{i})\right)\;.$ (25)

Let us define $f_{i}(\lambda)=s(\lambda_{0},x_{i})-s(\lambda,x_{i})$, which is
concave since $s(\lambda,x_{i})$ is convex. Using the concavity and
monotonicity of $\log$ and the concavity of the $f_{i}$, we have that for any
$\lambda,\lambda^{\prime}\in\Lambda$ and $\rho\in(0,1)$,

$\displaystyle\log(1+f_{i}(\rho\lambda+(1-\rho)\lambda^{\prime}))$
$\displaystyle\geq\log(\rho(1+f_{i}(\lambda))+(1-\rho)f_{i}(\lambda^{\prime}))$
$\displaystyle\geq\rho\,\log(1+f_{i}(\lambda))+(1-\rho)\log(1+f_{i}(\lambda^{\prime}))\;,$

showing that $\log(1+f_{i}(\lambda))$ is concave. Hence, $\log L^{\theta}_{t}$
is a sum of concave functions of $\theta$, and hence is concave as well.

_Lemma 3.2._ In this case, the family of test supermartingales
$\\{L^{\theta}\\}_{\theta\in\Theta}$, where $\eta=\theta\in\Theta\subseteq
A^{\mathrm{bd}}_{m,\lambda_{0}}$, can be written as

$\log L^{\theta}_{t}=\sum_{1\leq i\leq
t}\log\left(1+\left\langle\eta\mathrel{,}m(\lambda_{0},x_{i})\right\rangle\right)\;.$
(26)

By the concavity of the $\log$, each of the
$\log\left(1+\left\langle\eta\mathrel{,}m(\lambda_{0},x_{i})\right\rangle\right)$
are concave in $\eta$. Hence, $\log L^{\theta}_{t}$ is a sum of concave
functions of $\theta$, and hence is concave as well.

_Lemma 3.6._ In this case, the family of test supermartingales
$\\{L^{\theta}\\}_{\theta\in\Theta}$, where
$(\lambda,u)=\theta\in\Theta\subseteq[0,u_{\text{max}})\times\Lambda$, can be
written as

$\log L^{\theta}_{t}=\sum_{1\leq i\leq
t}\left\\{u(\theta)\,\left(s(\lambda_{0},x_{i})-s(\lambda(\theta),x_{i})\right)-v_{i}^{\lambda(\theta)}\psi_{\lambda(\theta)}(u(\theta))\right\\}\;.$
(27)

By assumption, each summand is concave in $\theta=(\lambda,u)$ and hence $\log
L^{\theta}_{t}$ must also be concave in $\theta$.

_Lemma 3.7._ In this case, the family of test supermartingales
$\\{L^{\theta}\\}_{\theta\in\Theta}$, where $(\eta,u)=\theta\in\Theta\subseteq
A^{\psi}_{m,\lambda_{0}}\times[0,u_{\max})$, can be written as

$\log L^{\theta}_{t}=\sum_{1\leq i\leq t}\left\\{\left\langle
u(\theta)\mathrel{,}m(\lambda_{0},x_{i})\right\rangle-
v_{i}^{\lambda(\theta)}\psi_{\eta(\theta)}(u(\theta))\right\\}\;.$ (28)

By assumption, each summand is concave and hence $\log L_{t}^{\theta}$ is a
sum of concave functions and hence is itself almost surely concave.

∎