# Time-uniform Chernoff bounds via nonnegative supermartingales

Steven R. Howard<EMAIL_ADDRESS>[ Department of Statistics
University of California, Berkeley
Berkeley, California 94720, USA
Aaditya Ramdas<EMAIL_ADDRESS>[ Departments of Statistics and
Machine Learning
Carnegie Mellon University
Pittsburgh, PA 15213, USA
Jon McAuliffe<EMAIL_ADDRESS>[ Department of Statistics
University of California, Berkeley
Berkeley, California 94720, USA
Jasjeet Sekhon<EMAIL_ADDRESS>[ Departments of Statistics and
Political Science
University of California, Berkeley
Berkeley, California 94720, USA

###### Abstract

We develop a class of exponential bounds for the probability that a martingale
sequence crosses a time-dependent linear threshold. Our key insight is that it
is both natural and fruitful to formulate exponential concentration
inequalities in this way. We illustrate this point by presenting a single
assumption and theorem that together unify and strengthen many tail bounds for
martingales, including classical inequalities (1960-80) by Bernstein, Bennett,
Hoeffding, and Freedman; contemporary inequalities (1980-2000) by Shorack and
Wellner, Pinelis, Blackwell, van de Geer, and de la Peña; and several modern
inequalities (post-2000) by Khan, Tropp, Bercu and Touati, Delyon, and others.
In each of these cases, we give the strongest and most general statements to
date, quantifying the time-uniform concentration of scalar, matrix, and
Banach-space-valued martingales, under a variety of nonparametric assumptions
in discrete and continuous time. In doing so, we bridge the gap between
existing line-crossing inequalities, the sequential probability ratio test,
the Cramér-Chernoff method, self-normalized processes, and other parts of the
literature.

60E15,

60G17,

60F10,

60B20,

exponential concentration inequalities,

nonnegative supermartingale,

line crossing probability,

###### keywords:

[class=MSC]

###### keywords:

1808.03204

onr1Supported by Office of Naval Research grant N00014-17-1-2176.
onr2Supported by Office of Naval Research grants N00014-15-1-2367,
N00014-17-1-2176.

###### Contents

  1. 1 Introduction
    1. 1.1 Paper organization
    2. 1.2 Historical context
  2. 2 Main results
    1. 2.1 The sub-$\psi$ condition
    2. 2.2 The master theorem
    3. 2.3 Proof of Theorem 1
    4. 2.4 Interpreting the theorem
    5. 2.5 Three simple examples
  3. 3 Sufficient conditions for sub-$\psi$ processes
    1. 3.1 Five useful $\psi$ functions
    2. 3.2 Conditions for sub-$\psi$ processes
    3. 3.3 Implications between sub-$\psi$ conditions
  4. 4 Applications of Theorem 1
    1. 4.1 Fixed-time Cramér-Chernoff and Freedman-style uniform bounds
    2. 4.2 Line-crossing inequalities
    3. 4.3 Self-normalized uniform bounds
    4. 4.4 Martingales in smooth Banach spaces
    5. 4.5 Continuous-time processes
    6. 4.6 Exponential families and the sequential probability ratio test
  5. 5 Discussion and extensions
    1. 5.1 When is Theorem 1 sharp?
    2. 5.2 Geometric relationship between Theorem 1 and Cramér-Chernoff
    3. 5.3 Future work
  6. 6 Proofs
    1. 6.1 Proof of Lemma 1
    2. 6.2 Proof of Proposition 1
    3. 6.3 Proof of Proposition 2
    4. 6.4 An intermediate condition for sub-$\psi$ processes
    5. 6.5 Proof of Lemma 3
    6. 6.6 Proof of Corollary 2
    7. 6.7 Proof of Corollary 3
    8. 6.8 Proof of Corollary 10
    9. 6.9 Proof of Corollary 13
    10. 6.10 Proof of Proposition 3
    11. 6.11 Proof of Corollary 14
    12. 6.12 Proof of Proposition 4
  7. 7 Acknowledgments
  8. A Sharpened pre-factors based on rank
  9. B Relation to the Dubins-Savage inequality
  10. C Graphical comparison of $\psi$ functions
  11. D A more general boundary-crossing result
  12. E Equivalent sub-exponential conditions

##  1 Introduction

Concentration inequalities play an important role in probability and
statistics, giving non-asymptotic tail probability bounds for random variables
or suprema of random processes. In this paper, we consider a method to bound
the probability that a martingale ever crosses a time-dependent linear
threshold. We were motivated by the fact that such bounds are the key
ingredient in many sequential inference procedures. We argue, however, that
this formulation is materially better for the development of exponential
concentration inequalities, even in some non-sequential settings. We give a
master assumption and theorem which handle all of these cases, in discrete and
continuous time, for scalar-valued, matrix-valued, and smooth Banach-space-
valued martingales. By unifying and organizing dozens of results, we
illustrate how these results relate to one another and highlight the specific
ingredients contributed by each author. Our improvements to existing results
come in the form of weakened assumptions, extension of fixed-time or finite-
horizon bounds to infinite-horizon uniform bounds, and improved exponents.

Our main results are presented in full generality in the following section. To
motivate these results, we first contrast a small handful of well-known,
concrete results from the exponential concentration literature; see Section
1.2 for a more detailed overview of the literature we draw upon. Throughout
the paper, most of our results are presented for filtered probability spaces,
and we use $\mathbb{E}_{t}$ to denote expectation conditional on the
underlying filtration $\mathcal{F}_{t}$ at time $t$. For any discrete-time
process $(Y_{t})_{t\in\mathbb{N}}$, we write $\Delta Y_{t}\coloneqq
Y_{t}-Y_{t-1}$ for the increments. Finally, we write $\mathcal{H}^{d}$ for the
space of $d\times d$ Hermitian matrices. The relation $A\preceq B$ denotes the
semidefinite order on $\mathcal{H}^{d}$, while
$\gamma_{\max}:\mathcal{H}^{d}\to\mathbb{R}$ denotes the maximum eigenvalue
map.

######  Example 1.

Unless indicated otherwise, let $(S_{t})_{t=0}^{\infty}$ be a real-valued
martingale with respect to a filtration $(\mathcal{F}_{t})_{t=0}^{\infty}$,
with $S_{0}=0$.

  1. (a)

Three of the earliest and most well-known results for exponential
concentration are attributed to Bernstein, Bennett, and Hoeffding. Assume the
increments $(\Delta S_{t})$ are independent, and let
$v_{t}\coloneqq\sum_{i=1}^{t}\mathbb{E}(\Delta S_{i})^{2}$. We present
Bernstein’s inequality (Bernstein, 1927) in a widely used form (e.g.,
Boucheron et al., 2013, Corollary 2.11): if, for some fixed $m\in\mathbb{N}$
and $c>0$, the increments satisfy the moment condition
$\sum_{i=1}^{m}\mathbb{E}(\Delta S_{t})^{k}\leq\frac{k!}{2}c^{k-2}v_{m}$ for
all integers $k\geq 3$, then for any $x>0$, we have

$\displaystyle\mathbb{P}\left(S_{m}\geq
x\right)\leq\exp\left\\{-\frac{x^{2}}{2(v_{m}+cx)}\right\\}.$ (1.1)

Bernstein’s moment condition is easily seen to be satisfied if the increments
are bounded. Bennett (1962, eq. 8b) improved Bernstein’s result for bounded
increments: if $\Delta S_{t}\leq 1$ for all $t$, then for any $x>0$ and
$m\in\mathbb{N}$, we have

$\displaystyle\mathbb{P}\left(S_{m}\geq
x\right)\leq\left(\frac{v_{m}}{x+v_{m}}\right)^{x+v_{m}}e^{x}.$ (1.2)

Finally, Hoeffding (1963, eq. 2.3) gave a simplified result for increments
bounded from above and below: if $\lvert\Delta S_{t}\rvert\leq 1$ for all $t$,
then for any $x>0$ and $m\in\mathbb{N}$, we have

$\displaystyle\mathbb{P}\left(S_{m}\geq x\right)\leq e^{-x^{2}/2m}.$ (1.3)

  2. (b)

Blackwell (1997, Theorem 1): if $\lvert\Delta S_{t}\rvert\leq 1$ for all $t$,
then for any $a,b>0$, we have

$\displaystyle\mathbb{P}(\exists t\in\mathbb{N}:S_{t}\geq a+bt)\leq e^{-2ab}.$
(1.4)

Relative to Hoeffding’s inequality, Blackwell removes the assumption of
independent increments, although this possibility was noted by Hoeffding
himself (Hoeffding, 1963, p. 18). More importantly, Blackwell replaces the
event $\\{S_{m}\geq x\\}$ for fixed time $m$ with the time-uniform event
$\\{\exists t\in\mathbb{N}:S_{t}\geq a+bt\\}$. To see that Blackwell’s result
recovers and strengthens that of Hoeffding, set $a=x/2$, $b=x/2m$ and note
that Blackwell’s uniform bound recovers Hoeffding’s bound at time $t=m$, so
that Blackwell obtains the same probability bound for a larger event.

  3. (c)

Freedman (1975, Theorem 1.6): if $\lvert\Delta S_{t}\rvert\leq 1$ for all $t$,
then writing $V_{t}\coloneqq\sum_{i=1}^{t}\operatorname{Var}\left(\left.\Delta
S_{i}\,\right|\,\mathcal{F}_{i-1}\right)$, then for any $x,m>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:V_{t}\leq m\text{ and
}S_{t}\geq x\right)\leq\left(\frac{m}{x+m}\right)^{x+m}e^{x}.$ (1.5)

Similar to Bernstein’s and Bennett’s inequalities, but unlike those of
Hoeffding and Blackwell, Freedman’s inequality measures time in terms of a
predictable quantity, the accumulated conditional variance $V_{t}$, rather
than simply the number of observations $t$. Freedman’s inequality bounds the
deviations of $(S_{t})$ uniformly over time, but only up to the finite time
horizon implied by $V_{t}\leq m$.

  4. (d)

de la Peña (1999, Theorem 6.2, eq. 6.4): if the increments are conditionally
symmetric, that is, $\Delta S_{t}\sim-\Delta S_{t}\mid\mathcal{F}_{t-1}$ for
all $t$, then letting $V_{t}=\sum_{i=1}^{t}\Delta S_{i}^{2}$, for any
$\alpha\geq 0$ and $\beta,x,m>0$ we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:V_{t}\geq m\text{ and
}\frac{S_{t}}{\alpha+\beta V_{t}}\geq
x\right)\leq\exp\left\\{-x^{2}\left(\frac{\beta^{2}}{2m}+\alpha\beta\right)\right\\}.$
(1.6)

A remarkable feature of this result is that we measure time via the adapted
quantity $V_{t}$. Unlike Freedman’s inequality, which uses the true
conditional variance to measure time, de la Peña’s inequality relies only on
empirical quantities. In further contrast to Freedman’s inequality, de la
Peña’s bound holds uniformly over $V_{t}\geq m$ rather than $V_{t}\leq m$, and
we bound the deviations of the self-normalized process $S_{t}/(\alpha+\beta
V_{t})$.

  5. (e)

Tropp (2012, Theorem 6.2): departing from the above results for real-valued
martingales, here we begin with a martingale $(Y_{t})_{t\in\mathbb{N}}$ taking
values in $\mathcal{H}^{d}$. Assume that the increments $\Delta Y_{t}$ are
independent and, for some fixed $c>0$ and $\mathcal{H}^{d}$-valued sequence
$(W_{t})_{t\in\mathbb{N}}$, the moments of the increments satisfy
$\mathbb{E}\left(\left.\Delta
S_{t}^{k}\,\right|\,\mathcal{F}_{t-1}\right)\preceq\frac{k!}{2}c^{k-2}\Delta
W_{t}$ for all $t$ and all $k\geq 2$. Then, writing
$S_{t}=\gamma_{\max}(Y_{t})$ and $V_{t}=\gamma_{\max}(W_{t})$, for any $x>0$
and $t\geq 1$, we have

$\displaystyle\mathbb{P}\left(S_{t}\geq x\right)\leq
d\cdot\exp\left\\{-\frac{x^{2}}{2(V_{t}+cx)}\right\\}.$ (1.7)

This elegant result extends Bernstein’s inequality to the matrix setting. Note
the prefactor of $d$ that appears when we bound the deviations of the maximum
eigenvalue of a $d\times d$ matrix-valued process.

  6. (f)

Finally, we recall a textbook result for Brownian motion (e.g., Durrett, 2017,
Exercise 7.5.2): if $(S_{t})_{t\in(0,\infty)}$ is a standard Brownian motion,
then for any $a,b>0$, we have

$\displaystyle\mathbb{P}(\exists t\in(0,\infty):S_{t}\geq a+bt)=e^{-2ab}.$
(1.8)

The result closely resembles Blackwell’s inequality for discrete-time
martingales with bounded increments, but here we have an equality.

Clearly, these results have much in common with each other and with myriad
other results from the exponential concentration literature. Examining the
proofs, we find many shared ingredients which are now well known: the notions
of sub-Gaussian and sub-exponential random variables, the Cramér-Chernoff
method, the large-deviations supermartingale, and so on. Nonetheless, there
are enough differences among the results and their proofs to leave us
wondering whether these results are merely similar in appearance, or whether
they are all special cases of some underlying, general argument.

In this paper, we provide a framework that formally unifies the above results
along with many others. Our framework consists of two pieces. First, we
crystallize the notion of a _sub- $\psi$ process_ (Definition 1), a sufficient
condition general enough to encompass a broad set of results not previously
treated together, yet specific enough to derive a useful set of equivalent
concentration inequalities. This definition provides a convenient
categorization of exponential concentration results into sub-Bernoulli, sub-
Gaussian, sub-Poisson, sub-exponential, and sub-gamma bounds. Second, we give
a generalization of the Cramér-Chernoff argument, Theorem 1. This result
yields strengthened versions of many existing inequalities and illustrates
equivalences among different forms of exponential bounds. For example, Theorem
1 strengthens both “Freedman-style” inequalities such as (1.5) and “de la
Peña-style” inequalities such as (1.6) to hold uniformly over all time, and in
these strengthened forms, the two styles of inequalities are shown to be
equivalent, as depicted in Figure 1. We remark that the seminal works from
which these examples are drawn, like others referenced below, include many
other important contributions, and our claims about Theorem 1 refer only to
the particular inequalities cited from each work.

This paper’s Theorem 1(b) This paper’s Theorem 1(c,d) Freedman-style
inequalities, such as (1.5) de la Peña-style inequalities, such as (1.6)
implies implies imply each other do not imply each other Figure 1: This
paper’s Theorem 1 implies both Freedman-style inequalities such as (1.5) and
de la Peña-style inequalities such as (1.6). Refer also to Figures 4 and 5 for
visualizations of these implications.

Once the framework is in place, the proof of the main result follows using
tools from classical large-deviation theory (Dembo and Zeitouni, 2010). We
construct a nonnegative supermartingale as in Freedman (1975), and we obtain a
bound on its entire trajectory using Ville’s maximal inequality (Ville, 1939).
We invoke Tropp’s ideas (Tropp, 2011) to extend the results to the matrix
setting. The equivalences that follow from optimizing linear bounds are
obtained using convex analysis (Rockafellar, 1970). By drawing together
various proof ingredients from different sources, we elucidate previously
unrecognized or understated connections. For example, we demonstrate how self-
normalized matrix inequalities follow easily upon combining ideas from the
literature on self-normalized processes with those from matrix concentration.

###  1.1 Paper organization

Section 2 lays out our framework for exponential line-crossing inequalities.
Specifically, we formally state Definition 1 and Theorem 1 that together
describe a general formulation of the Cramér-Chernoff method. After stating
Theorem 1, we give a quick overview of existing results which can be recovered
in our framework and the improvements thus obtained. A short proof of our
master theorem comes next, and following some remarks, we provide three
illustrative examples.

Sections 3 and 4 are devoted to a catalog of important results from the
literature which fit into our framework, often yielding results which are
stronger than those originally published. In Section 3, we consider the
maximum-eigenvalue process of a matrix-valued martingale and enumerate useful
sufficient conditions for such a process to be sub-$\psi$, collecting and in
some cases generalizing a variety of ingenious results from the literature.
Section 4 examines various instantiations of our master theorem, obtaining
corollaries by combining one of the sufficient conditions from Section 3 with
one of the four equivalent conclusions of Theorem 1. These illustrate how our
framework recovers and strengthens existing exponential concentration results.
We discuss sharpness, another geometrical insight, and future work in Section
5. Proofs of most results are in Section 6.

###  1.2 Historical context

To aid the reader, we give here some historical context for the existing
results discussed below. This is not intended to be a comprehensive history of
the literature on exponential concentration, and we focus on the specific
results discussed in Section 4, giving pointers to further references as
appropriate.

The Cramér-Chernoff method takes its name from the works of Cramér (1938) and
Chernoff (1952). Both of these authors were concerned with a precise
characterization of the asymptotic decay of tail probabilities beyond the
regime in which the central limit theorem applies; Cramér provided the first
proof of such a “large deviation principle”, while Chernoff gave a more
general formulation and placed more emphasis on the non-asymptotic upper bound
which is our focus. These results spawned a vast literature on large deviation
principles, with the goal of giving sharp upper and lower bounds on the
limiting exponential decay of certain probabilities under a sequence of
measures; see Dembo and Zeitouni (2010) for an excellent presentation of this
literature. Our focus, on non-asymptotic upper bounds for nonparametric
classes of distributions, is rather different, though such upper bounds often
make an appearance in proofs of large deviation principles.

Bernstein was perhaps the earliest proponent of the sort of exponential tail
bounds that are the focus of this paper, having proposed his famous inequality
in 1911, according to Prokhorov (1995); see also Craig (1933), Uspensky (1937,
ch. 10, ex. 12-14, pp. 204-205) and Bernstein (1927), though the last source
appears rather inaccessible. The modern theory of exponential concentration
began to take shape in the 1960’s, as (using the terminology of this paper,
from Section 3) Bennett (1962) improved Bernstein’s sub-gamma inequality to
sub-Bernoulli and sub-Poisson ones for random variables bounded from above.
Hoeffding (1963) gave alternative sub-Bernoulli and sub-Gaussian bounds for
random variables bounded from both above and below. For further references on
this line of work, see Boucheron et al. (2013), whose treatment of the Cramér-
Chernoff method has been invaluable in formulating our own framework, as well
as McDiarmid (1998).

Godwin (1955, p. 936) reports that Bernstein generalized his inequality to
dependent random variables. Hoeffding (1963, pp. 17-18) considered the
generalization of his sub-Bernoulli and sub-Gaussian bounds to martingales and
the possibility of finite-horizon uniform inequalities based on Doob’s maximal
inequality; the martingale generalization was later explored by Azuma (1967).
Freedman (1975) extended Bennett’s sub-Poisson bound to martingales, giving a
uniform bound subject to a maximum value of the predictable quadratic
variation of the martingale. This “Freedman-style” bound has been generalized
to other settings in many subsequent works (de la Peña, 1999; Khan, 2009;
Tropp, 2011; Fan et al., 2015). Chen (2012a, b) has considered the extension
of Chernoff-style bounds to hold uniformly over time for scalar-valued
martingales in a manner similar to our line-crossing inequalities, including a
condition similar to our sub-$\psi$ definition; our formulation further
encompasses matrix-valued processes and self-normalized inequalities.

The extension of these methods to matrix-valued processes, via control of the
matrix moment-generating function, originated with Ahlswede and Winter (2002).
The method was refined by Christofides and Markström (2007), Oliveira (2010a,
b) and then by Tropp (2011, 2012), whose influential treatment synthesized and
improved upon past work, generalizing many scalar exponential inequalities to
operator-norm inequalities for matrix martingales. We have incorporated
Tropp’s formulation into our framework, and we focus on his theorem statements
for our matrix bound statements. See Tropp (2015) for a recent exposition and
further references.

There is a long history of investigation of the concentration of Student’s
$t$-statistic under non-normal sampling. Efron (1969) gives many references to
early work. He also shows, by making use of Hoeffding’s sub-Gaussian bound,
that the equivalent self-normalized statistic
$\left(\sum_{i}X_{i}\right)/\sqrt{\sum_{i}X_{i}^{2}}$ satisfies a 1-sub-
Gaussian tail bound whenever the $X_{i}$ satisfy a symmetry condition, a
result he attributes to Bahadur and Eaton (Efron, 1969, p. 1284). Starting
with Logan et al. (1973), there has been a great deal of work on limiting
distributions and large deviation principles for self-normalized statistics;
see Shao (1997) and references therein. In terms of exponential tail bounds,
de la Peña (1999) explored general conditions for bounding the deviations of a
martingale, introduced new decoupling techniques (cf. de la Peña and Giné,
1999), and showed that any martingale with conditionally symmetric increments
satisfies a self-normalized sub-Gaussian bound with no integrability
condition. This work laid the foundation for the type of self-normalized
exponential inequalities which we explore in this paper. These methods were
extended by de la Peña et al. (2000, 2004), which introduced a general
supermartingale “canonical assumption” that is a key precursor of our
sub-$\psi$ condition, and initiated a flurry of subsequent activity on self-
normalized exponential inequalities (cf. de la Peña et al., 2007; de la Peña,
Klass and Lai, 2009). We note in particular inequality (3.9) of de la Peña et
al. (2001), which gives an infinite-horizon boundary-crossing inequality based
on a mixture extension of their canonical assumption, as well as the
multivariate inequalities (3.24) (for a $t$-statistic) and (3.29) (for general
mixture boundaries) given by de la Peña, Klass and Lai (2009). Bercu and
Touati (2008) gave a self-normalized sub-Gaussian bound without symmetry by
incorporating the conditional quadratic variation, requiring only finite
second moments, and some ingenious further extensions have been given by
Delyon (2009), Fan et al. (2015), and Bercu et al. (2015), many of which we
include in our collection of sufficient conditions for a process to be
sub-$\psi$ (Section 3.2). See de la Peña, Lai and Shao (2009) and Bercu et al.
(2015) for further references.

Ville’s maximal inequality for nonnegative supermartingales, the technical
underpinning of Theorem 1, originates with Ville (1939, p. 101). It is
commonly attributed to Doob, though Doob acknowledged Ville’s priority
extensively in his works, e.g., Doob (1940, pp. 458-460). Mazliak and Shafer
(2009) contains further historical discussion and sources.

##  2 Main results

Let $(S_{t})_{t\in\mathcal{T}\cup\\{0\\}}$ be a real-valued process adapted to
an underlying filtration $(\mathcal{F}_{t})_{t\in\mathcal{T}\cup\\{0\\}}$,
where either $\mathcal{T}=\mathbb{N}$ for discrete-time processes or
$\mathcal{T}=(0,\infty)$ for continuous-time processes. In continuous time, we
assume $(\mathcal{F}_{t})$ satisfies the “usual hypotheses”, namely, that it
is right-continuous and complete, and we assume $(S_{t})$ is càdlàg; see,
e.g., Protter (2005). In a statistical setting, we may think of $(S_{t})$ as a
summary statistic accumulating over time, for example a cumulative sum of
observations, whose deviations from zero we would like to bound under some
null hypothesis. In this setting, a bound on the deviations of $(S_{t})$
holding uniformly over time can be used to construct an appropriate sequential
hypothesis test, a special case of which is Wald’s sequential probability
ratio test discussed in Section 4.6. We first explain our key condition on
$(S_{t})$, the sub-$\psi$ condition. We then state, prove, and interpret our
master theorem, followed by some more detailed examples of its application.

###  2.1 The sub-$\psi$ condition

Our key condition on $(S_{t})$ is stated in terms of two additional objects.
The first object is a real-valued, nondecreasing process
$(V_{t})_{t\in\mathcal{T}\cup\\{0\\}}$, also adapted to $(\mathcal{F}_{t})$
(and càdlàg in the continuous-time case). It is an “accumulated variance”
process which serves as a measure of _intrinsic time_ , an appropriate
quantity to control the deviations of $S_{t}$ from zero (Blackwell and
Freedman, 1973). The second object is a function $\psi:\mathbb{R}_{\geq
0}\to\mathbb{R}$, reminiscent of a cumulant-generating function, which
quantifies the relationship between $S_{t}$ and $V_{t}$. The simplest case is
when $S_{t}$ is a cumulative sum of i.i.d., real-valued, mean-zero random
variables with distribution $F$, in which case we take $V_{t}=t$ and let
$\psi(\lambda)=\log\int e^{\lambda x}\mathop{}\\!\mathrm{d}F(x)$ be the CGF of
$F$. Our key condition requires that $S_{t}$ is unlikely to grow too quickly
relative to intrinsic time $V_{t}$; it generalizes developments from Freedman
(1975); de la Peña et al. (2004); Tropp (2011); Chen (2012b), and others.

######  Definition 1 (Sub-$\psi$ process).

Let $(S_{t})_{t\in\mathcal{T}\cup\\{0\\}}$ and
$(V_{t})_{t\in\mathcal{T}\cup\\{0\\}}$ be two real-valued processes adapted to
an underlying filtration $(\mathcal{F}_{t})_{t\in\mathcal{T}\cup\\{0\\}}$ with
$S_{0}=V_{0}=0$ a.s. and $V_{t}\geq 0$ a.s. for all $t\in\mathcal{T}$. For a
function $\psi:[0,\lambda_{\max})\to\mathbb{R}$ and a scalar
$l_{0}\in[1,\infty)$, we say $(S_{t})$ is _$l_{0}$ -sub-$\psi$ with variance
process $(V_{t})$_ if, for each $\lambda\in[0,\lambda_{\max})$, there exists a
supermartingale $(L_{t}(\lambda))_{t\in\mathcal{T}\cup\\{0\\}}$ with respect
to $(\mathcal{F}_{t})$ such that $L_{0}(\lambda)\leq l_{0}$ a.s. and

$\displaystyle\exp\left\\{\lambda S_{t}-\psi(\lambda)V_{t}\right\\}\leq
L_{t}(\lambda)\text{ a.s.\ for all }t\in\mathcal{T}.$ (2.1)

For given $\psi$ and $l_{0}$, we write $\mathbb{S}^{l_{0}}_{\psi}$ for the
class of pairs of $l_{0}$-sub-$\psi$ processes $(S_{t},V_{t})$:

$\displaystyle\mathbb{S}^{l_{0}}_{\psi}\coloneqq\left\\{(S_{t},V_{t}):(S_{t})\text{
is $l_{0}$-sub-$\psi$ with variance process }(V_{t})\right\\}.$ (2.2)

We often say simply that a process is sub-$\psi$, omitting $l_{0}$ from our
terminology for simplicity. All examples considered in this paper fit into
three cases for the value of $l_{0}$: $l_{0}=1$, when deriving one-sided
bounds on scalar martingales; $l_{0}=2$, when deriving bounds on the norm of
certain Banach-space-valued martingales; or $l_{0}=d$, when deriving bounds on
the maximum-eigenvalue process of a $d\times d$ matrix-valued martingale.
Also, though we often speak of a process $(S_{t})$ being sub-$\psi$, the
sub-$\psi$ condition formally applies to the pair $(S_{t},V_{t})$ and not to
the process $(S_{t})$ alone, so that meaningful statements are always made in
the context of a specific intrinsic time process $(V_{t})$.

Definition 1 may at first defy intuition. We can motivate it from several
angles:

  * •

Suppose $S_{t}$ is a scalar-valued martingale whose deviations we wish to
bound uniformly over time. We might like to apply Ville’s maximal inequality
(see Section 2.3), but must first transform $S_{t}$ into a _nonnegative_
supermartingale. It is natural to consider the exponential transform
$e^{\lambda S_{t}}$ for some $\lambda>0$, which immediately yields a
submartingale. Our task, then, is to find some appropriate $\psi$ and
$(V_{t})$ which “pull down” the submartingale so that the process
$\exp\left\\{\lambda S_{t}-\psi(\lambda)V_{t}\right\\}$ is a supermartingale.
Intuitively, the exponential process $\exp\left\\{\lambda
S_{t}-\psi(\lambda)V_{t}\right\\}$ measures how quickly $S_{t}$ has grown
relative to intrinsic time $V_{t}$, and the free parameter $\lambda$
determines the relative emphasis placed on the tails of the distribution of
$S_{t}$, i.e., on the higher moments. Larger values of $\lambda$ exaggerate
larger movements in $S_{t}$, and $\psi$ captures how much we must
correspondingly exaggerate $V_{t}$.

  * •

Consider again the simple case in which $S_{t}$ is a cumulative sum of i.i.d.
draws from a distribution $F$ over the reals with mean zero and CGF
$\psi(\lambda)<\infty$ for $\lambda\in[0,\lambda_{\max})$. Then, setting
$V_{t}=t$, we may take $L_{t}(\lambda)$ equal to the exponential process
$\exp\left\\{\lambda S_{t}-\psi(\lambda)t\right\\}$, which is a martingale in
this case, so that the defining inequality of Definition 1 is an equality. The
exponential process may be interpreted as the likelihood ratio in an
exponential family containing $F$ with sufficient statistic $S_{t}$. See
Example 2 for a more detailed exposition of this setting and Section 4.6 for
more on the connection with exponential families.

  * •

Alternatively, we may begin from the martingale method for concentration
inequalities (Hoeffding, 1963; Azuma, 1967; McDiarmid, 1998; Raginsky and
Sason, 2012, section 2.2), itself based on the classical Cramér-Chernoff
method (Cramér, 1938; Chernoff, 1952; Boucheron et al., 2013, section 2.2).
The martingale method starts from an assumption such as
$\mathbb{E}\left(\left.e^{\lambda(X_{t}-\mathbb{E}\left(\left.X_{t}\,\right|\,\mathcal{F}_{t-1}\right))}\,\right|\,\mathcal{F}_{t-1}\right)\leq
e^{\psi(\lambda)\sigma_{t}^{2}}$ for all $t\geq 1$ and
$\lambda\in[0,\lambda_{\max})$. When $\psi(\lambda)=\lambda^{2}/2$ and
$\lambda_{\max}=\infty$ (and the condition holds for $\lambda<0$ as well),
this is the definition of a conditionally sub-Gaussian random variable with
variance parameter $\sigma_{t}^{2}$. When
$\psi(\lambda)=\lambda^{2}/(2(1-c\lambda))$ and $\lambda_{\max}=1/c$, we have
the definition of a random variable which is conditionally sub-gamma on the
right tail with variance parameter $\sigma_{t}^{2}$ and scale parameter $c$
(Boucheron et al., 2013). Writing
$S_{t}\coloneqq\sum_{i=1}^{t}(X_{i}-\mathbb{E}_{i-1}X_{i})$ and
$V_{t}\coloneqq\sum_{i=1}^{t}\sigma_{i}^{2}$, the process $\exp\left\\{\lambda
S_{t}-\psi(\lambda)V_{t}\right\\}$ is then a supermartingale for each
$\lambda\in\mathbb{R}$. For example, if $\Delta S_{t}\in[a_{t},b_{t}]$ for all
$t$, then $(S_{t})$ is 1-sub-$\psi$ with $\psi(\lambda)=\lambda^{2}/2$ on
$\lambda\in[0,\infty)$, and
$V_{t}=\sum_{i=1}^{t}\left(\frac{b-a}{2}\right)^{2}$; this fact underlies
Example 1(a,b). Or, if $S_{t}\leq 1$ for all $t$, then $(S_{t})$ is
1-sub-$\psi$ with $\psi(\lambda)=e^{\lambda}-\lambda-1$ on
$\lambda\in[0,\infty)$, a fact which leads to Example 1(c).

  * •

Unlike the martingale method assumption, Definition 1 allows $(V_{t})$ to be
adapted rather than predictable, which leads to a variety of self-normalized
inequalities (de la Peña, 1999; de la Peña et al., 2004; de la Peña, Lai and
Shao, 2009; Bercu et al., 2015; Fan et al., 2015), for example yielding bounds
on the deviation of a martingale in terms of its quadratic variation. In this
context, Definition 1 is closely related to the “canonical assumption” of de
la Peña et al. (2004, eq. 1.6), which requires that $\exp\left\\{\lambda
S_{t}-\Phi(\lambda V_{t})\right\\}$ is a supermartingale for certain
nonnegative, strictly convex functions $\Phi$. We have found it more useful to
separate the second term into $\psi(\lambda)V_{t}$, though both formulations
yield interesting results. For example, if $\Delta S_{t}\sim-\Delta
S_{t}\mid\mathcal{F}_{t-1}$, then $(S_{t})$ is 1-sub-$\psi$ with
$\psi(\lambda)=\lambda^{2}/2$ over $\lambda\in[0,\infty)$, and
$V_{t}=\sum_{i=1}^{t}\Delta S_{t}^{2}$, from which we may obtain Example 1(d).

  * •

Also in contrast to de la Peña et al. (2004), we allow the exponential process
to be merely upper bounded by a supermartingale, rather than being a
supermartingale itself; this permits us to handle bounds on the maximum
eigenvalue process of a matrix-valued martingale, using techniques from Tropp
(2011). For example, under the conditions of Example 1(e), the maximum
eigenvalue process $(S_{t})$ is $d$-sub-$\psi$ with
$\psi(\lambda)=\lambda^{2}/[2(1-c\lambda)]$ on $\lambda\in[0,1/c)$. In this
case, the exponential process $\exp\left\\{\lambda
S_{t}-\psi(\lambda)V_{t}\right\\}$ is not a supermartingale, but is upper
bounded by the trace-exponential supermartingale
$\operatorname{tr}\exp\left\\{\lambda Y_{t}-\psi(\lambda)W_{t}\right\\}$. The
initial value of this trace-exponential process is $l_{0}=d$, which leads to
the pre-factor of $d$ in the bound (1.7).

Section 3 collects a variety of sufficient conditions from the literature for
a process to be sub-$\psi$, including all of the examples given above. These
conditions illustrate the broad applicability of Definition 1 in nonparametric
settings, i.e., those which restrict the distribution of $(S_{t})$ to some
infinite-dimensional class, for example all processes with bounded increments,
or with increments having finite variance. Even in such nonparametric cases,
$\psi$ is still a CGF of some distribution in all of our examples, though this
is not required for the most basic conclusion of Theorem 1. Indeed, the full
force of Theorem 1 comes into effect only when $\psi$ satisfies certain
properties which hold for CGFs of zero-mean, non-constant random variables
(Jorgensen, 1997, Theorem 2.3):

######  Definition 2.

A real-valued function $\psi$ with domain $[0,\lambda_{\max})$ is called _CGF-
like_ if it is strictly convex and twice continuously differentiable with
$\psi(0)=\psi^{\prime}(0_{+})=0$ and
$\sup_{\lambda\in[0,\lambda_{\max})}\psi(\lambda)=\infty$. For such a function
we define

$\displaystyle\bar{b}=\bar{b}(\psi)\coloneqq\sup_{\lambda\in[0,\lambda_{\max})}\psi^{\prime}(\lambda)\in(0,\infty].$
(2.3)

In many typical cases we have $\lambda_{\max}=\infty$ and $\bar{b}=\infty$.
With Definitions 1 and 2 in place, we are ready to set up and state our main
result in the following section.

###  2.2 The master theorem

To state our main theorem on general exponential line-crossing inequalities,
we will make use of the following transforms of $\psi$:

$\displaystyle\text{The Legendre-Fenchel transform:
}\psi^{\star}(u)\coloneqq\sup_{\lambda\in[0,\lambda_{\max})}[\lambda
u-\psi(\lambda)],\quad\text{for }u\geq 0.$ (2.4) $\displaystyle\text{The
``decay'' transform:
}D(u)\coloneqq\sup\left\\{\lambda\in(0,\lambda_{\max}):\frac{\psi(\lambda)}{\lambda}\leq
u\right\\},\quad\text{for }u\geq 0.$ (2.5) $\displaystyle\text{The ``slope''
transform:
}\mathfrak{s}(u)\coloneqq\frac{\psi({\psi^{\star}}^{\prime}(u))}{{\psi^{\star}}^{\prime}(u)},\quad\text{for
}u\in(0,\bar{b}).$ (2.6)

In the definition of $D(u)$, we take the supremum of the empty set to equal
zero instead of the usual $-\infty$. For $u>0$, this case can arise in
general, but not when $\psi$ is CGF-like. Note that $D(u)$ can also be
infinite. We call $D(u)$ the “decay” transform because it determines the rate
of exponential decay of the upcrossing probability bound in Theorem 1(a)
below. We call $\mathfrak{s}(u)$ the “slope” transform because it gives the
slope of the linear boundary in Theorem 1(b); this is defined only when $\psi$
is CGF-like. Defining $\mathfrak{s}(0)=0$ and $\mathfrak{s}(\bar{b})=\bar{b}$
when $\bar{b}<\infty$, we find that $\mathfrak{s}(u)$ is continuous, strictly
increasing, and $0\leq\mathfrak{s}(u)<u$ on $u\in[0,\bar{b})$ (see Lemma 2).
We do not know of other references for the slope transform, or other
situations where it arises naturally. Table 2 gives examples of these
transforms for some common $\psi$ functions.

Our main theorem has four parts, each of which facilitates comparisons with a
particular related literature, as we discuss in Section 4. Recall Definition 1
of the class $\mathbb{S}^{l_{0}}_{\psi}$ of $l_{0}$-sub-$\psi$ processes, and
the underlying filtration $(\mathcal{F}_{t})$ to which processes $(S_{t})$ and
$(V_{t})$ are adapted.

######  Theorem 1.

Fix any $\psi:\mathbb{R}_{\geq 0}\to\mathbb{R}$ and $l_{0}\in[1,\infty)$.

  1. (a)

For any $a,b>0$, we have

$\displaystyle\sup_{(S_{t},V_{t})\in\mathbb{S}^{l_{0}}_{\psi}}\mathbb{P}\left(\left.\exists
t\in\mathcal{T}:S_{t}\geq a+bV_{t}\,\right|\,\mathcal{F}_{0}\right)\leq
l_{0}\exp\left\\{-aD(b)\right\\}.$ (2.7)

Additionally, whenever $\psi$ is CGF-like, the following three statements are
equivalent to statement (a).

  1. (b)

For any $m>0$ and $x\in(0,m\bar{b})$, we have

$\sup_{(S_{t},V_{t})\in\mathbb{S}^{l_{0}}_{\psi}}\mathbb{P}\left(\left.\exists
t\in\mathcal{T}:S_{t}\geq
x+\mathfrak{s}\left(\frac{x}{m}\right)\cdot\left(V_{t}-m\right)\,\right|\,\mathcal{F}_{0}\right)\\\
\leq l_{0}\exp\left\\{-m\psi^{\star}\left(\frac{x}{m}\right)\right\\}.$ (2.8)

  2. (c)

For any $m>0$ and $x\in(0,\bar{b})$, we have

$\sup_{(S_{t},V_{t})\in\mathbb{S}^{l_{0}}_{\psi}}\mathbb{P}\left(\left.\exists
t\in\mathcal{T}:\frac{S_{t}}{V_{t}}\geq
x-\left(\frac{x-\mathfrak{s}(x)}{V_{t}}\right)\cdot(V_{t}-m)\,\right|\,\mathcal{F}_{0}\right)\\\
\leq l_{0}\exp\left\\{-m\psi^{\star}(x)\right\\}.$ (2.9)

  3. (d)

For any $m\geq 0$, $x>0$ and $b>0$, we have (below we take $m\bar{b}=\infty$
whenever $\bar{b}=\infty$)

$\sup_{(S_{t},V_{t})\in\mathbb{S}^{l_{0}}_{\psi}}\mathbb{P}\left(\left.\exists
t\in\mathcal{T}:V_{t}\geq m\text{ and }S_{t}\geq
x+b(V_{t}-m)\,\right|\,\mathcal{F}_{0}\right)\\\
\leq\begin{cases}l_{0}\exp\left\\{-(x-(b\wedge\bar{b})m)D(b)\right\\},&x>m\bar{b}\text{
or }\mathfrak{s}\left(\tfrac{x}{m}\right)>b\\\
l_{0}\exp\left\\{-m\psi^{\star}\left(\tfrac{x}{m}\right)\right\\},&x\leq
m\bar{b}\text{ and }\mathfrak{s}\left(\tfrac{x}{m}\right)\leq b.\end{cases}$
(2.10)

We give a straightforward proof in Section 2.3 that uses only Ville’s maximal
inequality for nonnegative supermartingales (Ville, 1939) and elementary
convex analysis. Theorem 1 can be seen to unify and strengthen many known
exponential bounds, showing that we lose nothing in going from a fixed-time to
a uniform bound. This includes classical inequalities by Hoeffding (Corollary
1a), Bennett and Freedman (Corollary 1b), and Bernstein (Corollary 1c), along
with their matrix extensions due to Tropp and Mackey et al. (Corollary 1a-c);
discrete-time scalar line-crossing inequalities due to Blackwell (Corollaries
4 and 5) and Khan (Section 4.2); self-normalized bounds due to de la Peña
(Corollaries 6 and 7), Delyon (Corollary 8), Bercu and Touati (Corollary 8),
and Fan (Corollary 9); bounds for martingales in smooth Banach spaces due to
Pinelis (Corollary 10); continuous-time bounds due to Shorack and Wellner
(Corollary 11) and van de Geer (Corollary 11); and Wald’s sequential
probability ratio test (Corollary 12). Visualizations of how the bounds of
Theorem 1 relate to Freedman’s and de la Peña’s inequalities are provided in
Figures 4 and 5. For convenience, Table 1 lists the existing results we
recover and our corresponding corollaries, along with ways in which our
analysis strengthens conclusions.

For the remainder of the paper after Section 2.3, we will assume
$\mathcal{F}_{0}$ is the trivial $\sigma$-field and omit from our notation the
conditioning on $\mathcal{F}_{0}$ in the results of Theorem 1 and its
corollaries.

Existing result | Our result | [A] | [B] | [C] | [D] | [E]
---|---|---|---|---|---|---
Bernstein (1927) |  Corollary 1(c) |  | ✓ | ✓ | ✓ |
Bennett (1962, eq. 8b) |  Corollary 1(b) | ✓ | ✓ | ✓ | ✓ |
Hoeffding (1963, Theorem 2) |  Corollary 1(a) | ✓ | ✓ |  | ✓ |
Freedman (1975, Theorem 1.6) |  Corollary 1(b) |  | ✓ | ✓ | ✓ |
Shorack and Wellner (1986, App. B, Ineq. 1) |  Corollary 11(b) |  | ✓ |  |  |
Pinelis (1994, Theorems 3.4, 3.5) | Corollary 10 |  | ✓ |  |  |
van de Geer (1995, Lemma 2.2) |  Corollary 11(c) |  | ✓ |  | ✓ |
Blackwell (1997, Theorem 1) |  Corollary 4(a) | ✓ |  | ✓ | ✓ |
Blackwell (1997, Theorem 2) | Corollary 5 |  |  |  | ✓ |
Blackwell (1997, Theorem 2) |  Corollary 4(b) | ✓ |  | ✓ | ✓ |
de la Peña (1999, Theorems 6.1, 1.2B (eq. 1.5)) | Corollary 6 |  | ✓ | ✓ | ✓ |
de la Peña (1999, Theorem 6.2) | Corollary 7 |  |  | ✓ | ✓ | ✓
Bercu and Touati (2008, Theorem 2.1) | Corollary 8 |  | ✓ |  | ✓ | ✓
Delyon (2009, Theorem 4) | Corollary 8 |  | ✓ |  | ✓ |
Khan (2009, Theorem 4.2) |  Theorem 1(b) |  | ✓ | ✓ | ✓ |
Khan (2009, Theorem 4.3) |  Theorem 1(d) |  |  | ✓ | ✓ | ✓
Tropp (2011, Theorem 1.2) |  Corollary 1(b) |  | ✓ |  |  |
Tropp (2012, Theorem 1.3) |  Corollary 1(a) |  | ✓ |  |  | ✓
Tropp (2012, Theorem 1.4) |  Corollary 1(c) |  | ✓ |  |  |
Mackey et al. (2014, Corollary 4.2) |  Corollary 1(a) | ✓ | ✓ |  |  |
Table 1: Some existing results which are strengthened by Theorem 1, as
detailed in Section 4. For clarity, we enumerate the different ways in which
we strengthen or generalize existing results with the following mnemonics:

  1. [A]

Assumptions: we recover the result under weaker conditions on the
distributional or dependence structure of the process.

  2. [B]

Boundary: we strengthen the result by replacing a fixed-time bound or a
finite-horizon constant uniform boundary with an infinite-horizon linear
uniform boundary which is everywhere at least as strong (i.e., low) as the
fixed-time or finite-horizon bound.

  3. [C]

Continuous time: we extend a discrete-time result to include continuous time.

  4. [D]

Dimension: we extend a result for scalar process to one for
$\mathcal{H}^{d}$-valued processes, recovering the scalar result at $d=1$.

  5. [E]

Exponent: we improve the exponent in the result’s probability bound.

###  2.3 Proof of Theorem 1

Throughout the proof, we write $\mathbb{P}_{0}(\cdot)$ for the conditional
probability $\mathbb{P}\left(\left.\cdot\,\right|\,\mathcal{F}_{0}\right)$.
Ville’s maximal inequality for nonnegative supermartingales (Ville, 1939) is
the foundation of all uniform bounds in this paper. It is an infinite-horizon
uniform extension of Markov’s inequality:

######  Lemma 1 (Ville’s inequality).

If $(L_{t})_{t\in\mathcal{T}\cup\\{0\\}}$ is a nonnegative supermartingale
with respect to the filtration
$(\mathcal{F}_{t})_{t\in\mathcal{T}\cup\\{0\\}}$, then for any $a>0$, we have

$\displaystyle\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:L_{t}\geq
a\right)\leq\frac{L_{0}}{a}.$ (2.11)

For completeness, we give an elementary proof of Lemma 1 in Section 6.1.
Applying Ville’s inequality to Definition 1 gives, for any
$(S_{t},V_{t})\in\mathbb{S}^{l_{0}}_{\psi}$, $\lambda\in(0,\lambda_{\max})$,
and $z\in\mathbb{R}$,

$\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:\exp\left\\{\lambda
S_{t}-\psi(\lambda)V_{t}\right\\}\geq e^{z}\right)\\\
\leq\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:L_{t}\geq e^{z}\right)\leq
L_{0}e^{-z}\leq l_{0}e^{-z}.$ (2.12)

To derive Theorem 1(a) from (2.12), fix $a,b>0$ and choose
$\lambda\in[0,\lambda_{\max})$ such that $\psi(\lambda)\leq b\lambda$,
supposing for the moment that some such value of $\lambda$ exists. Then

$\displaystyle\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:S_{t}\geq
a+bV_{t}\right)$ $\displaystyle=\mathbb{P}_{0}\left(\exists
t\in\mathcal{T}:\exp\left\\{\lambda S_{t}-b\lambda V_{t}\right\\}\geq
e^{a\lambda}\right)$ (2.13) $\displaystyle\leq\mathbb{P}_{0}\left(\exists
t\in\mathcal{T}:\exp\left\\{\lambda S_{t}-\psi(\lambda)V_{t}\right\\}\geq
e^{a\lambda}\right)$ (2.14) $\displaystyle\leq l_{0}e^{-a\lambda},$ (2.15)

applying (2.12) in the last step. This bound holds for all choices of
$\lambda$ in the set
$\\{\lambda\in[0,\lambda_{\max}):\psi(\lambda)/\lambda\leq b\\}$, so to
minimize the final bound, we take the supremum over this set, recovering the
stated bound $l_{0}e^{-aD(b)}$ by the definition of $D(b)$. If no value
$\lambda\in[0,\lambda_{\max})$ satisfies $\psi(\lambda)\leq b\lambda$, then
$D(b)=0$ by definition, so that the bound holds trivially. This shows that
Definition 1 implies Theorem 1(a).

To complete the proof we will show that the four parts of Theorem 1 are
equivalent whenever $\psi$ is CGF-like. We repeatedly use the well-known fact
about the Legendre-Fenchel transform that
${\psi^{\prime}}^{-1}(u)={\psi^{\star}}^{\prime}(u)$ for $0<u<\bar{b}$, which
follows by differentiating the identity
$\psi^{\star}(u)=u{\psi^{\prime}}^{-1}(u)-\psi({\psi^{\prime}}^{-1}(u))$. We
also require some simple facts about $\psi(\lambda)/\lambda$:

######  Lemma 2.

Suppose $\psi$ is CGF-like with domain $[0,\lambda_{\max})$.

  1. (i)

$\psi(\lambda)/\lambda<\psi^{\prime}(\lambda)$ for all
$\lambda\in(0,\lambda_{\max})$.

  2. (ii)

$\lambda\mapsto\psi(\lambda)/\lambda$ is continuous and strictly increasing on
$\lambda>0$.

  3. (iii)

$\inf_{\lambda\in(0,\lambda_{\max})}\psi(\lambda)/\lambda=\lim_{\lambda\downarrow
0}\psi(\lambda)/\lambda=0$.

  4. (iv)

$\sup_{\lambda\in(0,\lambda_{\max})}\psi(\lambda)/\lambda=\lim_{\lambda\uparrow\lambda_{\max}}\psi(\lambda)/\lambda=\bar{b}$.

  5. (v)

$\psi(D(b))/D(b)=b$ for any $b\in(0,\bar{b})$, that is, $D(b)$ is the inverse
of $\psi(\lambda)/\lambda$.

  6. (vi)

$\mathfrak{s}(u)$ is continuous, strictly increasing, and
$0<\mathfrak{s}(u)<u$ for all $u\in(0,\bar{b})$.

###### Proof of Lemma 2.

To see (i), write
$\psi(\lambda)=\int_{0}^{\lambda}\psi^{\prime}(t)\mathop{}\\!\mathrm{d}t<\lambda\psi^{\prime}(\lambda)$,
where the inequality follows since $\psi$ is strictly convex so that
$\psi^{\prime}$ is strictly increasing. For (ii), the function is continuous
because $\psi$ is continuous, and differentiating reveals it to be strictly
increasing by part (i). L’Hôpital’s rule implies (iii) along with the
assumptions $\psi(\lambda)=\psi^{\prime}(\lambda)=0$ at $\lambda=0$, and
implies (iv) along with the CGF-like assumption
$\sup_{\lambda}\psi(\lambda)=\infty$, which means
$\psi(\lambda)\uparrow\infty$ as $\lambda\uparrow\lambda_{\max}$ since $\psi$
is convex. Part (v) follows from the definition of $D(\cdot)$ and parts (ii),
(iii) and (iv). To obtain (vi), note that $\mathfrak{s}$ is the composition of
$\lambda\mapsto\psi(\lambda)/\lambda$ with ${\psi^{\star}}^{\prime}$. Both of
these are continuous and strictly increasing, the former by part (ii) and the
latter since ${\psi^{\star}}^{\prime}={\psi^{\prime}}^{-1}$ and
$\psi^{\prime}$ is continuous and strictly increasing by the CGF-like
assumption. As $u\downarrow 0$, we have
${\psi^{\star}}^{\prime}(u)={\psi^{\prime}}^{-1}(u)\downarrow 0$, so
$\mathfrak{s}(u)\downarrow 0$ since $\psi(0)=\psi^{\prime}(0_{+})=0$.
Likewise, if $\bar{b}<\infty$, then as $u\uparrow\bar{b}$,
${\psi^{\star}}^{\prime}(u)\uparrow\lambda_{\max}$ and
$\mathfrak{s}(u)\uparrow\bar{b}$. Hence $\mathfrak{s}(u)$ is continuous as
defined. Next, note that $\psi(u)>0$ for $u>0$ since $\psi$ is strictly convex
with $\psi(0)=\psi^{\prime}(0_{+})=0$, and
${\psi^{\star}}^{\prime}(u)={\psi^{\prime}}^{-1}(u)>0$ since
$\psi^{\prime}(\lambda)$ increases from zero at $\lambda=0$ to $\bar{b}$ as
$\lambda\uparrow\lambda_{\max}$. Hence $\mathfrak{s}(u)>0$ for $u>0$. Finally,
use part (i) to write
$\mathfrak{s}(u)=\psi({\psi^{\star}}^{\prime}(u))/{\psi^{\star}}^{\prime}(u)<\psi^{\prime}({\psi^{\star}}^{\prime}(u))=u$,
using the fact that ${\psi^{\star}}^{\prime}(u)={\psi^{\prime}}^{-1}(u)$ for
$u\in(0,\bar{b})$. ∎

Lemma 2 allows us to prove the equivalences among the parts of Theorem 1 as
follows.

  * •

$(a)\Rightarrow(b)$: Fix $m>0$ and $x\in(0,m\bar{b})$. Any line with slope
$b\in(0,x/m)$ and intercept $x-bm$ passes through the point $(m,x)$ in the
$(V_{t},S_{t})$ plane, and part $(a)$ yields

$\displaystyle\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:S_{t}\geq
x+b(V_{t}-m)\right)$ $\displaystyle\leq l_{0}\exp\left\\{-(x-bm)D(b)\right\\}$
(2.16) $\displaystyle=l_{0}\exp\left\\{-m\left(\frac{x}{m}\cdot
D(b)-\psi(D(b))\right)\right\\}$ (2.17)

using Lemma 2(v) in the second step. Now we choose the slope $b$ to minimize
the probability bound. The unconstrained optimizer $b_{\star}$ satisfies
${\psi^{\prime}(D(b_{\star}))=x/m}$, and a solution is guaranteed to exist by
our restriction on $x$. This solution is given by
$D(b_{\star})={\psi^{\prime}}^{-1}(x/m)={\psi^{\star}}^{\prime}(x/m)$. Hence
$b_{\star}=\mathfrak{s}(x/m)$ using Lemma 2(v) and the definition of
$\mathfrak{s}(\cdot)$. Lemma 2(vi) shows $0<b_{\star}<x/m$, verifying that
$b_{\star}$ is feasible. Identify the Legendre-Fenchel transformation
$\psi^{\star}(x/m)=(x/m)D(b_{\star})-\psi(D(b_{\star}))$ to complete the proof
of part $(b)$.

  * •

$(b)\Rightarrow(c)$: Fix $m>0$ and $x\in(0,\bar{b})$ and observe that

$\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:\frac{S_{t}}{V_{t}}\geq
x-\left(\frac{x-\mathfrak{s}(x)}{V_{t}}\right)\cdot(V_{t}-m)\right)\\\
=\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:S_{t}\geq
mx+\mathfrak{s}(x)\cdot(V_{t}-m)\right).$ (2.18)

Now applying part $(b)$ with values $m$ and $mx$ yields part $(c)$.

  * •

$(c)\Rightarrow(a)$: Fix $a,b>0$. Suppose first that $b<\bar{b}$, and set
$x=\psi^{\prime}(D(b))$ and $m=a/(x-\mathfrak{s}(x))$. Recalling
${\psi^{\star}}^{\prime}={\psi^{\prime}}^{-1}$ we see that
$\mathfrak{s}(x)=\psi(D(b))/D(b)=b$ by Lemma 2(v). Also, Lemma 2(vi) shows
that $m>0$. Now apply part $(c)$ to obtain

$\displaystyle\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:S_{t}\geq
a+bV_{t}\right)$ $\displaystyle\leq
l_{0}\exp\left\\{-a\cdot\frac{\psi^{\star}(x)}{x-\mathfrak{s}(x)}\right\\}$
(2.19)
$\displaystyle=l_{0}\exp\left\\{-a\cdot\frac{\psi^{\star}(x)\cdot{\psi^{\star}}^{\prime}(x)}{x{\psi^{\star}}^{\prime}(x)-\psi({\psi^{\star}}^{\prime}(x))}\right\\}.$
(2.20)

Recognizing the Legendre-Fenchel transform in the denominator of the final
exponent, we see that the probability bound equals
$l_{0}\exp\left\\{-a{\psi^{\star}}^{\prime}(x)\right\\}$. Again using
${\psi^{\star}}^{\prime}(x)={\psi^{\prime}}^{-1}(x)=D(b)$ yields part $(a)$.

If instead $b\geq\bar{b}$, then the above argument yields

$\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:S_{t}\geq
a+bV_{t}\right)\leq\inf_{b^{\prime}<\bar{b}}\mathbb{P}_{0}\left(\exists
t\in\mathcal{T}:S_{t}\geq a+b^{\prime}V_{t}\right)\\\ \leq
l_{0}\exp\left\\{-a\sup_{b^{\prime}<\bar{b}}D(b^{\prime})\right\\}.$ (2.21)

But $\sup_{b^{\prime}<\bar{b}}D(b^{\prime})=\lambda_{\max}=D(b)$ from the
definition of $D(\cdot)$.

  * •

$(a)\Rightarrow(d)$: Fix $m\geq 0$ and $x,b>0$. Observe that $\\{\exists
t\in\mathcal{T}:V_{t}\geq m,\,S_{t}\geq x+b(V_{t}-m)\\}\subseteq\\{\exists
t\in\mathcal{T}:S_{t}\geq x^{\prime}+b^{\prime}(V_{t}-m)\\}$ for any
$0<x^{\prime}\leq x$ and $0<b^{\prime}\leq b$, so part $(a)$ yields

$\displaystyle\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:V_{t}\geq
m,\,S_{t}\geq x+b(V_{t}-m)\right)\leq
l_{0}\exp\left\\{-(x^{\prime}-b^{\prime}m)D(b^{\prime})\right\\}$ (2.22)

for any $(x^{\prime},b^{\prime})$ in the feasible set
$\\{x^{\prime}\in(0,x],b^{\prime}\in(0,b]:x^{\prime}>mb^{\prime}\\}$. If
$x>m\bar{b}$, then $(x,b\wedge\bar{b})$ is feasible; note that
$D(b\wedge\bar{b})=D(b)$ by the definition of $D(\cdot)$. If $x\leq m\bar{b}$
and $b<s(x/m)$, then by Lemma 2(vi) and the definition
$\mathfrak{s}(\bar{b})\coloneqq\bar{b}$, we have $b<x/m$, so $(x,b)$ is
feasible and $b\leq\bar{b}$. Combining these two cases, we have

$\displaystyle\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:V_{t}\geq
m,\,S_{t}\geq x+b(V_{t}-m)\right)\leq
l_{0}\exp\left\\{-(x-(b\wedge\bar{b})m)D(b)\right\\}$ (2.23)

whenever $x>m\bar{b}$ or $b<s(x/m)$, proving the first case in (2.10). On the
other hand, if $x\leq m\bar{b}$ and $s(x/m)\leq b$, then
$(x^{\prime},s(x^{\prime}/m))$ is feasible for any $x^{\prime}<x$, by Lemma
2(vi). This yields

$\displaystyle\mathbb{P}_{0}\left(\exists t\in\mathcal{T}:V_{t}\geq
m,\,S_{t}\geq x+b(V_{t}-m)\right)\leq
l_{0}\exp\left\\{-m\psi^{\star}\left(\frac{x^{\prime}}{m}\right)\right\\}$
(2.24)

as in part $(b)$. We minimize the probability bound over $x^{\prime}<x$,
noting that $\sup_{x^{\prime}<x}\psi^{\star}(x^{\prime}/m)=\psi^{\star}(x/m)$
since $\psi^{\star}$ is increasing (as $\psi$ is CGF-like) and closed
(Rockafellar, 1970, Theorem 12.2). This proves the second case in (2.10).

  * •

$(d)\Rightarrow(a)$: set $m=0$ and $x=a$ to recover part $(a)$. ∎

It is worth noting here that, unlike the proofs of Freedman (1975), Khan
(2009), Tropp (2011), and Fan et al. (2015), we do not explicitly construct a
stopping time in our proof. While an optional stopping argument is hidden
within the proof of Ville’s inequality, the underlying stopping time here is
different from that in the aforementioned citations.

###  2.4 Interpreting the theorem

Figure 2: Illustration of the equivalent statements of Theorem 1, as described
in the text.

It is instructive to think of the parts of Theorem 1 as statements about the
process $(V_{t},S_{t})$ or $(V_{t},S_{t}/V_{t})$ in $\mathbb{R}^{2}$. Many of
our results are better understood via this geometric intuition. Specifically,
Figure 2 illustrates the following points:

  * •

Theorem 1(a) takes a given line $a+bV_{t}$ and bounds its $S_{t}$-upcrossing
probability.

  * •

Theorem 1(b) takes a point $(m,x)$ in the $(V_{t},S_{t})$-plane and, out of
the infinitely many lines passing through it, chooses the one which yields the
tightest upper bound on the corresponding $S_{t}$-upcrossing probability.

  * •

Theorem 1(c) is like part (b), but instead of looking at $S_{t}$, we look at
$S_{t}/V_{t}$, fix a point $(m,x)$ in the $(V_{t},S_{t}/V_{t})$-plane, and
choose from among the infinitely many curves $b+a/V_{t}$ passing through it to
minimize the probability bound.

  * •

The intuition for Theorem 1(d) is as follows. If we want to bound the
upcrossing probability of the line $(x-bm)+bV_{t}$ on $\\{V_{t}\geq m\\}$, we
can clearly obtain a conservative bound from Theorem 1(a) with $a=x-bm$. This
yields the first case in (2.10). However, we can also apply Theorem 1(b) with
the values $m,x$, obtaining a bound on the upcrossing probability for a line
which passes through the point $(m,x)$ in the $(V_{t},S_{t})$-plane, and this
line yields the minimum possible probability bound among all lines passing
through $(m,x)$. If the slope of this line, $\mathfrak{s}(x/m)$, is less than
$b$, then this optimal probability bound is conservative for the upcrossing
probability over the original line $x+b(V_{t}-m)$ on $\\{V_{t}\geq m\\}$. This
gives the second case in (2.10), which is guaranteed to be at least as small
as the bound in the first case when $\mathfrak{s}(x/m)\leq b$.

We make some additional remarks below:

  * •

We extend bounds for discrete-time scalar-valued processes to include both
discrete-time matrix-valued processes and continuous-time scalar-valued
processes, but we do not handle continuous-time matrix-valued processes, as
this seems to require further technical developments beyond the scope of this
paper (see Bacry et al. (2018) for one approach to exponential bounds in this
case). We write [C or D] when discussing extensions to existing results to
emphasize this fact (see Table 1).

  * •

Most of this paper is concerned with right-tail bounds, hence the restriction
to $\lambda\geq 0$ in Definition 1. It is understood that identical techniques
yield left-tail bounds upon verifying that Definition 1 holds for $(-S_{t})$.

  * •

The purpose of excluding $\psi$ being CGF-like from Definition 1 is to
separate the truth of statement (a), which follows solely from Definition 1,
from its equivalence to (b), (c), and (d), which follows from $\psi$ being
CGF-like.

###  2.5 Three simple examples

We illustrate some simple instantiations of our theorem with three examples: a
sum of coin flips, a discrete-time concentration inequality for random
matrices, and a continuous-time scalar Brownian motion. These examples make
use of several results from Section 3 describing conditions under which a
process is sub-$\psi$; such results may be taken for granted on a first
reading.

######  Example 2 (Coin flipping).

Suppose $X_{i}\overset{\text{iid}}{\sim}\operatorname{Ber}(p)$, and let
$S_{t}=\sum_{i=1}^{t}(X_{i}-p)$ denote the centered sum. The CGF of each
increment of $S_{t}$, scaled by $1/[p(1-p)]$, is
$\psi_{B}(\lambda)\coloneqq[p(1-p)]^{-1}\log\mathbb{E}\exp\left\\{\lambda(X_{i}-p)\right\\}=[p(1-p)]^{-1}\log(pe^{(1-p)\lambda}+(1-p)e^{-p\lambda})$,
so that $\lambda_{\max}=\infty$ and $\bar{b}=1/p$. One may directly check the
martingale property to confirm that
${L_{t}(\lambda)\coloneqq\exp\left\\{\lambda
S_{t}-\psi_{B}(\lambda)p(1-p)t\right\\}}$ is a martingale for any $\lambda$,
so that $(S_{t})$ is 1-sub-$\psi_{B}$ with $V_{t}=p(1-p)t$. Then, for any
$t_{0}\in\mathbb{N}$ and $x\in(0,(1-p)t_{0})$, setting $m=p(1-p)t_{0}$ in
Theorem 1(b) yields

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+p(1-p)\mathfrak{s}_{B}\left(\frac{x}{p(1-p)t_{0}}\right)\cdot(t-t_{0})\right)$
(2.25)
$\displaystyle\qquad\leq\exp\left\\{-t_{0}\text{KL}\left(\left.p+\frac{x}{t_{0}}\,\right\rVert\,p\right)\right\\}$
(2.26)
$\displaystyle\qquad=\left[\left(\frac{p}{p+x/t_{0}}\right)^{p+x/t_{0}}\left(\frac{1-p}{1-p-x/t_{0}}\right)^{1-p-x/t_{0}}\right]^{t_{0}}.$
(2.27)

Here KL denotes the Bernoulli Kullback-Leibler divergence,

$\displaystyle\text{KL}\left(\left.q\,\right\rVert\,p\right)=q\log\left(\frac{q}{p}\right)+(1-q)\log\left(\frac{1-q}{1-p}\right).$
(2.28)

It takes some algebra to obtain this KL as the Legendre-Fenchel transform of
$\psi_{B}$; in Table 2 we summarize all such transforms used in this paper.
The final expression is Equation (2.1) of Hoeffding (1963), but here we have a
bound not just for the deviation of $S_{m}$ above its expectation at the fixed
time $m$, but for the upper deviations of $S_{t}$ for all $t\in\mathbb{N}$,
simultaneously. We can use this to sequentially test a hypothesis about $p$,
or to construct a sequence of confidence intervals for $p$ possessing a
coverage guarantee holding uniformly over unbounded time.

The slope transform $\mathfrak{s}_{B}(u)$ for $\psi_{B}$, given in Table 2, is
unwieldy. To derive a more analytically convenient bound, we use the fact that
$p(1-p)\psi_{B}(\lambda)\leq\lambda^{2}/8$ for all $\lambda\geq 0$; see the
proof of Proposition 2, part 2. Hence $\exp\left\\{\lambda
S_{t}-\lambda^{2}t/8\right\\}\leq L_{t}(\lambda)$ with $L_{t}$ defined as
above, so $(S_{t})$ is also 1-sub-$\psi$ with $\psi(\lambda)=\lambda^{2}/8$
and $V_{t}=t$. Now Theorem 1(b) yields

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+\frac{x}{2m}\cdot(t-m)\right)\leq\exp\left\\{-\frac{2x^{2}}{m}\right\\}.$
(2.29)

This is equivalent to Blackwell’s line-crossing inequality (1.4), and in the
form (2.29) it is clear that it recovers Hoeffding’s inequality at the fixed
time $t=m$. Instead of using $p(1-p)\psi_{B}(\lambda)\leq\lambda^{2}/8$, we
might alternatively use
$\psi_{B}(\lambda)\leq(1-2p)^{-2}(e^{(1-2p)\lambda}-(1-2p)\lambda-1)$; see the
proof of Proposition 2, part 3. This will yield a uniform extension of
Bennett’s inequality (1.2) which improves upon Hoeffding’s inequality
substantially for values of $p$ near zero and one. We will see other examples
of such “sub-Poisson” bounds below.

######  Example 3 (Covariance estimation for a spiked random vector ensemble).

The estimation of a covariance matrix via an i.i.d. sample is a common
application of exponential matrix concentration, starting with Rudelson
(1999). See also Vershynin (2012), Gittens and Tropp (2011), Tropp (2015), and
Koltchinskii and Lounici (2017) for more recent treatments; this particular
example is drawn from Wainwright (2017). Let $d\geq 2$ and consider
$\mathbb{R}^{d}$-valued, mean-zero observations
$X_{i}=\sqrt{d}\xi_{i}e_{U_{i}}$, where
$\xi_{i}\overset{\text{iid}}{\sim}\operatorname{Rademacher}$,
$(e_{k})_{k=1}^{d}$ are the standard basis vectors and
$U_{i}\overset{\text{iid}}{\sim}\operatorname{Unif}\left\\{1,\dots,d\right\\}$.
What can we say about the concentration of the sample covariance matrix
$\widehat{\Sigma}_{t}\coloneqq t^{-1}\sum_{i=1}^{t}X_{i}X_{i}^{T}$ around the
true covariance $I_{d}$, the $d\times d$ identity matrix? Let
$\gamma_{\max}(A)$ denote the maximum eigenvalue of a matrix $A$. We have
$\gamma_{\max}(X_{i}X_{i}^{T}-I_{d})=d-1$ always, and
$\mathbb{E}(X_{i}X_{i}^{T}-I_{d})^{2}=\left(\frac{(d-1)^{2}}{d}\right)I_{d}$.
Hence Fact 1(c) shows that $S_{t}=t\gamma_{\max}(\widehat{\Sigma}_{t}-I_{d})$
is $d$-sub-$\psi$ with variance process $V_{t}=\frac{(d-1)^{2}t}{d}$, where

$\displaystyle\psi(\lambda)=\frac{e^{(d-1)\lambda}-(d-1)\lambda-1}{(d-1)^{2}}\leq\frac{\lambda^{2}}{2(1-(d-1)\lambda/3)}.$
(2.30)

Here the inequality holds for all $\lambda\in[0,3/(d-1))$ as demonstrated in
the proof of Proposition 2, part 5. Applying Theorem 1(c) with $\psi$ equal to
the final expression in (2.30), we obtain, after some algebra, for any
$x,m>0$,

$\mathbb{P}\left(\exists
t\in\mathbb{N}:\gamma_{\max}\left(\widehat{\Sigma}_{t}-I_{d}\right)\geq
x\left(\frac{1+\frac{m}{t}\sqrt{1+2x/3(d-1)}}{1+\sqrt{1+2x/3(d-1)}}\right)\right)\\\
\leq d\exp\left\\{-\frac{mx^{2}}{2(d-1)\left[(d-1)/d+x/3\right]}\right\\}.$
(2.31)

At the fixed time $t=m$, this implies

$\displaystyle\gamma_{\max}\left(\widehat{\Sigma}_{m}-I_{d}\right)\leq\sqrt{\frac{2(d-1)^{2}\log(d/\alpha)}{dm}}+\frac{2(d-1)\log(d/\alpha)}{3m}$
(2.32)

with probability at least $1-\alpha$, a known fixed-sample result (Wainwright,
2017). However, as above, (2.31) gives a bound on the upper deviations of
$\widehat{\Sigma}_{t}$ for all $t\in\mathbb{N}$ simultaneously. Such a bound
enables, for example, sequential hypothesis tests concerning the true
covariance matrix.

######  Example 4 (Line-crossing for Brownian motion).

Let $(S_{t})_{t\in[0,\infty)}$ denote standard Brownian motion. It is a
standard fact that the process $\exp\left\\{\lambda
S_{t}-\lambda^{2}t/2\right\\}$ is a martingale, so that $(S_{t})$ is
1-sub-$\psi$ with $\psi(\lambda)=\lambda^{2}/2$ and $V_{t}=t$. In this case,
Theorem 1 says that, for any $a,b>0$,

$\displaystyle\mathbb{P}\left(\exists t\in(0,\infty):S_{t}\geq a+bt\right)\leq
e^{-2ab},$ (2.33)

a well-known line-crossing bound for Brownian motion, which in fact holds with
equality (Durrett, 2017, Exercise 7.5.2).

##  3 Sufficient conditions for sub-$\psi$ processes

Much of the power of Definition 1 comes from the array of sufficient
conditions for it which have been discovered under diverse, nonparametric
conditions. In this section, we define some standard $\psi$ functions and
collect a broad set of conditions from the literature for a process $(S_{t})$
to be sub-$\psi$ with one of these functions, summarized in Tables 3 and 4. In
other words, we collect here some families of process pairs $(S_{t},V_{t})$
which are contained within $\mathbb{S}^{l_{0}}_{\psi}$ for standard choices of
$\psi$. All discrete-time results in this paper use
$S_{t}=\gamma_{\max}(Y_{t})$ where $(Y_{t})_{t\in\mathbb{N}}$ is a martingale
taking values in $\mathcal{H}^{d}$, with the exception of Section 4.4, which
deals with martingales in abstract Banach spaces. Typically, setting $d=1$
recovers the corresponding known scalar result exactly. We note also that our
results for Hermitian matrices extend directly to rectangular matrices using
Hermitian dilations (Tropp, 2012), as we illustrate in Corollary 2.

###  3.1 Five useful $\psi$ functions

We define five particular $\psi$ functions corresponding to five sub-$\psi$
cases: the sub-Gaussian case in Hoeffding’s inequality, the “sub-gamma” case
corresponding to Bernstein’s inequality, the sub-Poisson case from Bennett’s
and Freedman’s inequalities, and the sub-exponential and sub-Bernoulli cases
which are used in several other existing bounds. The $\psi$ functions and
corresponding transforms for these five cases are summarized in Table 2, while
Figure 3 summarizes relationships among these cases, with Proposition 2
containing the formal statements. Recall
$\bar{b}=\sup_{\lambda\in[0,\lambda_{\max})}\psi^{\prime}(\lambda)$ from
Definition 2, and note that we take $1/0=\infty$ by convention in the
expressions for $\lambda_{\max}$ and $\bar{b}$ below.

  1. 1.

We say $(S_{t})$ is _sub-Bernoulli_ with range parameters $g,h>0$ when it is
sub-$\psi_{B,g,h}$ for some suitable variance process $(V_{t})$, where

$\displaystyle\psi_{B,g,h}(\lambda)\coloneqq\frac{1}{gh}\log\left(\frac{ge^{h\lambda}+he^{-g\lambda}}{g+h}\right)\quad\text{for
}0\leq\lambda<\infty=\lambda_{\max},$ (3.1)

which is the scaled CGF of a mean-zero random variable taking values $-g$ and
$h$. Here $\bar{b}=1/g$.

  2. 2.

We say $(S_{t})$ is _sub-Gaussian_ when it is sub-$\psi_{N}$ for some suitable
variance process $(V_{t})$, where

$\displaystyle\psi_{N}(\lambda)\coloneqq\lambda^{2}/2\quad\text{for
}0\leq\lambda<\infty=\lambda_{\max}.$ (3.2)

Here $\bar{b}=\infty$.

  3. 3.

We say $(S_{t})$ is _sub-Poisson_ with scale parameter $c\in\mathbb{R}$ when
it is sub-$\psi_{P,c}$ for some suitable variance process $(V_{t})$, where

$\displaystyle\psi_{P,c}(\lambda)\coloneqq\frac{e^{c\lambda}-c\lambda-1}{c^{2}}\quad\text{for
}0\leq\lambda<\infty=\lambda_{\max}.$ (3.3)

By taking the limit, we define $\psi_{P,0}=\psi_{N}$. Here $\bar{b}=\lvert
c\wedge 0\rvert^{-1}$.

  4. 4.

We say $(S_{t})$ is _sub-gamma_ with scale parameter $c\in\mathbb{R}$ when it
is sub-$\psi_{G,c}$ for some suitable variance process $(V_{t})$, where

$\displaystyle\psi_{G,c}(\lambda)\coloneqq\frac{\lambda^{2}}{2(1-c\lambda)}\quad\text{for
}0\leq\lambda<\frac{1}{c\vee 0}=\lambda_{\max},$ (3.4)

Here $\bar{b}=\lvert 2c\wedge 0\rvert^{-1}$.

  5. 5.

We say $(S_{t})$ is _sub-exponential_ with scale parameter $c\in\mathbb{R}$
when it is sub-$\psi_{E,c}$ for some suitable variance process $(V_{t})$,
where

$\displaystyle\psi_{E,c}(\lambda)\coloneqq\frac{-\log(1-c\lambda)-c\lambda}{c^{2}},\quad\text{for
}0\leq\lambda<\frac{1}{c\vee 0}=\lambda_{\max}.$ (3.5)

By taking the limit, we define $\psi_{E,0}=\psi_{N}$. Here $\bar{b}=\lvert
c\wedge 0\rvert^{-1}$.

We will typically write $\psi_{B}$, $\psi_{P}$, $\psi_{G}$, and $\psi_{E}$,
omitting the range or scale parameters from the notation when they are clear
from the context. We follow the definition of sub-gamma from Boucheron et al.
(2013), despite the somewhat inconsistent terminology: unlike the other four
cases, $\psi_{G}$ is not the CGF of a gamma-distributed random variable. It is
convenient for a number of reasons: it includes $\psi_{N}$ as a special case,
it gives a useful upper bound for $\psi_{P}$ (see Proposition 2 part 5,
below), it falls naturally out of the use of a Bernstein condition on higher
moments to bound the CGF, and it is simple enough to permit analytically
tractable results for the slope and decay transforms and the various bounds to
follow. We remark also that our definition of sub-exponential in terms of the
CGF of the exponential distribution follows that of Boucheron et al. (2013,
Exercise 2.22), but differs from another well-known definition which says that
the CGF is bounded by $\lambda^{2}/2$ for $\lambda$ in some neighborhood of
zero. The two are equivalent up to appropriate choice of constants, as
detailed in Appendix E.

The sub-gamma and sub-exponential functions $\psi_{G,c}$ and $\psi_{E,c}$
possess the following universality property, which we prove in Section 6.2.

######  Proposition 1.

For any twice-differentiable $\psi:[0,\lambda_{\max})\to\mathbb{R}$ with
$\psi(0)=\psi^{\prime}(0_{+})=0$, there exist constants $a,c>0$ such that
$\psi(\lambda)\leq a\psi_{G,c}(\lambda)$ for all
$\lambda\in[0,\lambda_{\max})$. Likewise, there exists constants
$\tilde{a},\tilde{c}>0$ such that
$\psi(\lambda)\leq\tilde{a}\psi_{E,\tilde{c}}(\lambda)$ for all
$\lambda\in[0,\lambda_{\max})$.

In particular, this means that if $S_{t}=\sum_{i=1}^{t}X_{i}$ for any zero-
mean, i.i.d. sequence $(X_{i})$ satisfying $\mathbb{E}e^{\lambda
X_{1}}<\infty$ for some $\lambda>0$, then $(S_{t})$ is sub-gamma and sub-
exponential with appropriate scale constants and variance process $V_{t}$
proportional to $t$. Furthermore, any process that is sub-$\psi$ with a CGF-
like $\psi$ function is also sub-gamma and sub-exponential with appropriate
scaling of the variance process by a constant.

Name | $\psi(\lambda)$ |  Legendre-Fenchel transform $\psi^{\star}(u)$ |  Slope transform $\mathfrak{s}(u)$ |  Decay transform $D(u)$
---|---|---|---|---
Bernoulli $\psi_{B},\mathfrak{s}_{B},D_{B}$ | $\frac{1}{gh}\log\left(\frac{ge^{h\lambda}+he^{-g\lambda}}{g+h}\right)$ | $\frac{1}{gh}\text{KL}\left(\left.\frac{g(1+hu)}{g+h}\,\right\rVert\,\frac{g}{g+h}\right)$ | $\frac{h\log(1-gu)^{-1}-g\log(1+hu)}{gh(\log(1-gu)^{-1}+\log(1+hu))}$ | $\geq\frac{2ghu}{\varphi(g,h)}$
Gaussian/normal $\psi_{N},\mathfrak{s}_{N},D_{N}$ | $\lambda^{2}/2$ | $u^{2}/2$ | $u/2$ | $2u$
Poisson $\psi_{P},\mathfrak{s}_{P},D_{P}$ | $\frac{e^{c\lambda}-c\lambda-1}{c^{2}}$ | $\frac{(1+cu)\log(1+cu)-cu}{c^{2}}$ | $\frac{cu-\log(1+cu)}{c\log(1+cu)}$ | $\geq\frac{2u}{1+2cu/3}$
“Gamma” $\psi_{G},\mathfrak{s}_{G},D_{G}$ | $\frac{\lambda^{2}}{2(1-c\lambda)}$ | $\frac{u^{2}}{1+cu+\sqrt{1+2cu}}$ | $\frac{u}{1+\sqrt{1+2cu}}$ | $\frac{2u}{1+2cu}$
Exponential $\psi_{E},\mathfrak{s}_{E},D_{E}$ | $\frac{\log(1-c\lambda)^{-1}-c\lambda}{c^{2}}$ | $\frac{cu-\log(1+cu)}{c^{2}}$ | $\frac{(1+cu)\log(1+cu)-cu}{c^{2}u}$ | $\geq\frac{2u}{1+2cu}$

Table 2: Summary of common $\psi$ functions and related transforms. KL denotes
the Bernoulli Kullback-Leibler divergence,
${\text{KL}\left(\left.q\,\right\rVert\,p\right)=q\log\left(\frac{q}{p}\right)+(1-q)\log\left(\frac{1-q}{1-p}\right)}$.
For the gamma and exponential cases, the domain of $\psi$ is bounded by
$\lambda_{\max}=1/(c\vee 0)$; for the other three cases,
$\lambda_{\max}=\infty$. For the Bernoulli, Poisson, and exponential cases, a
closed-form expression for $D(u)$ is not available, but we give lower bounds
based on Proposition 2; $\varphi(g,h)$ is defined in (3.7).

###  3.2 Conditions for sub-$\psi$ processes

| Condition | $\psi$ | $V_{t}$
---|---|---|---
_Discrete time, one-sided_
Bernoulli II | $\Delta S_{t}\leq h,\mathbb{E}\Delta S_{t}^{2}\leq gh$ | $\psi_{B}$ | $ght$
Bennett | $\Delta S_{t}\leq c$ | $\psi_{P}$ | $\left\langle S\right\rangle_{t}$
Bernstein | $\mu^{k}_{t}\leq\frac{k!}{2}c^{k-2}\mu^{2}_{t}$ | $\psi_{G}$ | $\left\langle S\right\rangle_{t}$
⋆Heavy on left | $\mathbb{E}_{t-1}T_{a}(\Delta S_{t})\leq 0,\,\forall a>0$ | $\psi_{N}$ | $[S]_{t}$
Bounded below | $\Delta S_{t}\geq-c$ | $\psi_{E}$ | $[S]_{t}$
_Discrete time, two-sided_
Parametric | $\Delta S_{t}\overset{\text{iid}}{\sim}F$ | $\log\mathbb{E}e^{\lambda\Delta S_{1}}$ | $t$
Bernoulli I | $-g\leq\Delta S_{t}\leq h$ | $\psi_{B}$ | $ght$
Hoeffding-KS | $-g_{t}\leq\Delta S_{t}\leq h_{t}$ | $\psi_{N}$ | $\sum_{i=1}^{t}\varphi(g_{i},h_{i})$
$\Rightarrow$ Hoeffding I | $-g_{t}\leq\Delta S_{t}\leq h_{t}$ | $\psi_{N}$ | $\sum_{i=1}^{t}\left(\frac{g_{i}+h_{i}}{2}\right)^{2}$
⋆Symmetric | $\Delta S_{t}\sim-\Delta S_{t}\mid\mathcal{F}_{t-1}$ | $\psi_{N}$ | $[S]_{t}$
SN I | $\mathbb{E}_{t-1}\Delta S_{t}^{2}<\infty$ | $\psi_{N}$ | $([S]_{t}+2\left\langle S\right\rangle_{t})/3$
SN II | $\mathbb{E}_{t-1}\Delta S_{t}^{2}<\infty$ | $\psi_{N}$ | $([S_{+}]_{t}+\left\langle S_{-}\right\rangle_{t})/2$
Cubic SN | $\mathbb{E}_{t-1}\lvert\Delta S_{t}\rvert^{3}<\infty$ | $\psi_{G}$ | $[S]_{t}+\sum_{i=1}^{t}\lvert\mu\rvert^{3}_{i}$
_Continuous time, one-sided_
Bennett | $\Delta S_{t}\leq c$ | $\psi_{P}$ | $\left\langle S\right\rangle_{t}$
Bernstein | $W_{m,t}\leq\frac{m!}{2}c^{m-2}V_{t}$ | $\psi_{G}$ | $V_{t}$
_Continuous time, two-sided_
Lévy | $\mathbb{E}e^{\lambda S_{1}}<\infty$ | $\log\mathbb{E}e^{\lambda S_{1}}$ | $t$
Continuous paths | $\Delta S_{t}\equiv 0$ | $\psi_{N}$ | $\left\langle S\right\rangle_{t}$
Table 3: Summary of sufficient conditions for a real-valued, discrete- or continuous-time martingale $(S_{t})$ to be sub-$\psi$ with the given variance process. We use the shorthand $\mu^{k}_{t}\coloneqq\mathbb{E}_{t-1}(\Delta S_{t})^{k}$ and $\lvert\mu\rvert^{k}_{t}\coloneqq\mathbb{E}_{t-1}\left\lvert\Delta S_{t}\right\rvert^{k}$. In starred cases (⋆), the first moment $\mathbb{E}_{i-1}\Delta S_{i}$ need not exist, so $(S_{t})$ need not be a martingale. See Facts 1, 3, and 2 for details of each case. “$\Rightarrow$ Hoeffding I” indicates that the variance process $(V_{t})$ for Hoeffding-KS is smaller. “SN” is short for “self-normalized”.  | Condition | $\psi$ | $Z_{t}$
---|---|---|---
_Discrete time, one-sided_
Bernoulli II | $\Delta Y_{t}\preceq hI_{d},\mathbb{E}\Delta Y_{t}^{2}\preceq ghI_{d}$ | $\psi_{B}$ | $ghtI_{d}$
Bennett | $\Delta Y_{t}\preceq cI_{d}$ | $\psi_{P}$ | $\left\langle Y\right\rangle_{t}$
Bernstein | $\mu^{k}_{t}\preceq\frac{k!}{2}c^{k-2}\mu^{2}_{t}$ | $\psi_{G}$ | $\left\langle Y\right\rangle_{t}$
Bounded below | $\Delta Y_{t}\succeq-cI_{d}$ | $\psi_{E}$ | $[Y]_{t}$
_Discrete time, two-sided_
Bernoulli I | $-gI_{d}\preceq\Delta Y_{t}\preceq hI_{d}$ | $\psi_{B}$ | $ghtI_{d}$
Hoeffding-KS | $-G_{t}I_{d}\preceq\Delta Y_{t}\preceq H_{t}I_{d}$ | $\psi_{N}$ | $\sum_{i=1}^{t}\varphi(G_{i},H_{i})I_{d}$
$\Rightarrow$ Hoeffding I | $-G_{t}I_{d}\preceq\Delta Y_{t}\preceq H_{t}I_{d}$ | $\psi_{N}$ | $\sum_{i=1}^{t}\left(\frac{G_{i}+H_{i}}{2}\right)^{2}I_{d}$
Hoeffding II | $\Delta Y_{t}^{2}\preceq A_{t}^{2}$ | $\psi_{N}$ | $\sum_{i=1}^{t}A_{i}^{2}$
⋆Symmetric | $\Delta Y_{t}\sim-\Delta Y_{t}\mid\mathcal{F}_{t-1}$ | $\psi_{N}$ | $[Y]_{t}$
SN I | $\mathbb{E}_{t-1}\Delta Y_{t}^{2}<\infty$ | $\psi_{N}$ | $([Y]_{t}+2\left\langle Y\right\rangle_{t})/3$
SN II | $\mathbb{E}_{t-1}\Delta Y_{t}^{2}<\infty$ | $\psi_{N}$ | $([Y_{+}]_{t}+\left\langle Y_{-}\right\rangle_{t})/2$
Cubic SN | $\mathbb{E}_{t-1}\lvert\Delta Y_{t}\rvert^{3}<\infty$ | $\psi_{G}$ | $[Y]_{t}+\sum_{i=1}^{t}\lvert\mu\rvert^{3}_{i}$
Table 4: Summary from Facts 1 and 3 of sufficient conditions for an
$\mathcal{H}^{d}$-valued, discrete-time martingale $(Y_{t})$ to have a
sub-$\psi$ maximum eigenvalue process $S_{t}=\gamma_{\max}(Y_{t})$ with
variance process $V_{t}=\gamma_{\max}(Z_{t})$. We use the shorthand
$\mu^{k}_{t}\coloneqq\mathbb{E}_{t-1}(\Delta S_{t})^{k}$ and
$\lvert\mu\rvert^{k}_{t}\coloneqq\mathbb{E}_{t-1}\left\lvert\Delta
S_{t}\right\rvert^{k}$. In the symmetric⋆ case, $\mathbb{E}_{i-1}\Delta Y_{i}$
need not exist, so $(Y_{t})$ need not be a martingale. “$\Rightarrow$
Hoeffding I” indicates that $(V_{t})$ for Hoeffding-KS is smaller. “SN” is
short for “self-normalized”.

In Tables 3 and 4, we summarize a variety of standard and novel conditions for
a process $(S_{t})$ to be sub-$\psi$. Facts 1 and 3 contain discrete-time
results, while results for continuous time are in Fact 2. We let $I_{d}$
denote the $d\leavevmode\nobreak\ \times\leavevmode\nobreak\ d$ identity
matrix. For a process $(Y_{t})_{t\in\mathcal{T}}$, $[Y]_{t}$ denotes the
quadratic variation and $\left\langle Y\right\rangle_{t}$ the conditional
quadratic variation; in discrete time, $[Y]_{t}\coloneqq\sum_{i=1}^{t}\Delta
Y_{i}^{2}$ and $\left\langle
Y\right\rangle_{t}\coloneqq\sum_{i=1}^{t}\mathbb{E}_{i-1}\Delta Y_{i}^{2}$. We
extend a function $f:\mathbb{R}\to\mathbb{R}$ on the real line to an operator
$f:\mathcal{H}^{d}\to\mathcal{H}^{d}$ on the space of Hermitian matrices in
the standard way: if $A\in\mathcal{H}^{d}$ has the spectral decomposition
$U\Lambda U^{\star}$ where $\Lambda$ is diagonal with elements
$\lambda_{1},\dots,\lambda_{d}$, then $f(A)=Uf(\Lambda)U^{\star}$ where
$f(\Lambda)$ is diagonal with elements $f(\lambda_{1}),\dots,f(\lambda_{d})$.
In particular, the absolute value function extends to $\mathcal{H}^{d}$ by
taking absolute values of the eigenvalues, while
$[Y_{+}]_{t}\coloneqq\sum_{i=1}^{t}\max(0,\Delta Y_{i})^{2}$ and $\left\langle
Y_{-}\right\rangle_{t}\coloneqq\sum_{i=1}^{t}\mathbb{E}_{i-1}\min(0,\Delta
Y_{i})^{2}$ operate by truncating the eigenvalues.

In the discrete-time case, we have the following known results.

######  Fact 1.

Let $(Y_{t})_{t\in\mathbb{N}}$ be any $\mathcal{H}^{d}$-valued martingale, and
let $S_{t}\coloneqq\gamma_{\max}(Y_{t})$ for $t\in\mathbb{N}$. In all cases we
set $l_{0}=d$.

  1. (a)

(Scalar parametric) If $d=1$ and $S_{t}$ is a cumulative sum of i.i.d., real-
valued random variables, each of which is mean zero with known CGF
$\psi(\lambda)$ that is finite on $\lambda\in[0,\lambda_{\max})$, then
$(S_{t})$ is sub-$\psi$ with variance process $V_{t}=t$.

  2. (b)

(Bernoulli I) If $-gI_{d}\preceq\Delta Y_{t}\preceq hI_{d}$ a.s. for all
$t\in\mathbb{N}$, then $(S_{t})$ is sub-Bernoulli with variance process
$V_{t}=ght$ and range parameters $g,h$ (Hoeffding, 1963; Tropp, 2012).

  3. (c)

(Bennett) If $\Delta Y_{t}\preceq cI_{d}$ a.s. for all $t\in\mathbb{N}$ for
some $c>0$, then $(S_{t})$ is sub-Poisson with variance process
$V_{t}=\gamma_{\max}(\left\langle Y\right\rangle_{t})$ and scale parameter $c$
(Bennett, 1962; Hoeffding, 1963; Tropp, 2012).

  4. (d)

(Bernstein) If $\mathbb{E}_{t-1}(\Delta
Y_{t})^{k}\preceq(k!/2)c^{k-2}\mathbb{E}_{t-1}(\Delta Y_{t})^{2}$ for all
$t\in\mathbb{N}$ and $k=2,3,\dots$, then $(S_{t})$ is sub-gamma with variance
process $V_{t}=\gamma_{\max}(\left\langle Y\right\rangle_{t})$ and scale
parameter $c$ (Bernstein, 1927; Tropp, 2012; Boucheron et al., 2013).

  5. (e)

(Heavy on left) Let $T_{a}(y)\coloneqq(y\wedge a)\vee-a$ for $a>0$ denote the
truncation of $y$. If $d=1$ and

$\displaystyle\mathbb{E}_{t-1}T_{a}(\Delta Y_{t})\leq 0\quad\text{for all
}a>0,t\in\mathbb{N},$ (3.6)

then $(S_{t})$ is sub-Gaussian with variance process
$V_{t}=\gamma_{\max}([Y]_{t})$. A random variable satisfying (3.6) is called
_heavy on left_ , and $(Y_{t})$ need not be a martingale in this case (Bercu
and Touati, 2008; Delyon, 2015; Bercu et al., 2015). For example, the centered
versions of the exponential, gamma, Pareto, log-normal, Poisson
($\lambda\in\mathbb{N}$), Bernoulli ($p<1/2$) and geometric ($0<p<1$)
distributions are known to be heavy on left. When $-\Delta Y_{t}$ satisfies
(3.6) we say $\Delta Y_{t}$ is _heavy on right_.

In addition to the above known results, we provide the following extensions of
known scalar results to matrices.

######  Lemma 3.

Let $(Y_{t})_{t\in\mathbb{N}}$ be any $\mathcal{H}^{d}$-valued martingale, and
let $S_{t}\coloneqq\gamma_{\max}(Y_{t})$ for $t\in\mathbb{N}$. In all cases we
set $l_{0}=d$.

  1. (a)

(Bernoulli II) If, for all $t\in\mathbb{N}$, $\Delta Y_{t}\preceq hI_{d}$ a.s.
and $\mathbb{E}\Delta Y_{t}^{2}\preceq ghI_{d}$, then $(S_{t})$ is sub-
Bernoulli with variance process $V_{t}=ght$.

  2. (b)

(Hoeffding-KS) If $-G_{t}I_{d}\preceq\Delta Y_{t}\preceq H_{t}I_{d}$ a.s. for
all $t\in\mathbb{N}$ for some real-valued, predictable sequences $(G_{t})$ and
$(H_{t})$, then $(S_{t})$ is sub-Gaussian with variance process
${V_{t}=\sum_{i=1}^{t}\varphi(G_{i},H_{i})}$, where

$\displaystyle\varphi(g,h)\coloneqq\begin{cases}\frac{h^{2}-g^{2}}{2\log(h/g)},&g<h\\\
gh,&g\geq h.\end{cases}$ (3.7)

  3. (c)

(Hoeffding I) If $-G_{t}I_{d}\preceq\Delta Y_{t}\preceq H_{t}I_{d}$ a.s. for
all $t\in\mathbb{N}$ for some real-valued, predictable sequences $(G_{t})$ and
$(H_{t})$, then $(S_{t})$ is sub-Gaussian with variance process
${V_{t}=\sum_{i=1}^{t}(G_{i}+H_{i})^{2}/4}$.

  4. (d)

(Conditionally symmetric) If $\Delta Y_{t}\sim-\Delta
Y_{t}\leavevmode\nobreak\ |\leavevmode\nobreak\ \mathcal{F}_{t-1}$ for all
$t\in\mathbb{N}$, then $(S_{t})$ is sub-Gaussian with variance process
$V_{t}=\gamma_{\max}([Y]_{t})$. Here, $\Delta Y_{t}$ need not be integrable,
so $(Y_{t})$ need not be a martingale.

  5. (e)

(Bounded from below) If $\Delta Y_{t}\succeq-cI_{d}$ a.s. for all
$t\in\mathbb{N}$ for some $c>0$, then $(S_{t})$ is sub-exponential with
variance process $V_{t}=\gamma_{\max}([Y]_{t})$ and scale parameter $c$.

  6. (f)

(General self-normalized I) If $\mathbb{E}_{t-1}\Delta Y_{t}^{2}$ is finite
for all $t\in\mathbb{N}$, then $(S_{t})$ is sub-Gaussian with variance process
$V_{t}=\gamma_{\max}([Y]_{t}+2\left\langle Y\right\rangle_{t})/3$.

  7. (g)

(General self-normalized II) If $\mathbb{E}_{t-1}\Delta Y_{t}^{2}$ is finite
for all $t\in\mathbb{N}$, then $(S_{t})$ is sub-Gaussian with variance process
$V_{t}=\gamma_{\max}([Y_{+}]_{t}+\left\langle Y_{-}\right\rangle_{t})/2$.

  8. (h)

(Hoeffding II) If $\Delta Y_{t}^{2}\preceq A_{t}^{2}$ a.s. for all
$t\in\mathbb{N}$ for some $\mathcal{H}^{d}$-valued predictable sequence
$(A_{t})$, then $(S_{t})$ is sub-Gaussian with variance process
$V_{t}=\gamma_{\max}(\sum_{i=1}^{t}A_{i}^{2})$.

  9. (i)

(Cubic self-normalized) If $\mathbb{E}_{t-1}\left\lvert\Delta
Y_{t}\right\rvert^{3}$ is finite for all $t\in\mathbb{N}$, then $(S_{t})$ is
sub-gamma with variance process
$V_{t}=\gamma_{\max}\left([Y]_{t}+\sum_{i=1}^{t}\mathbb{E}_{i-1}\left\lvert\Delta
Y_{i}\right\rvert^{3}\right)$ and scale parameter $c=1/6$.

The proof of the above lemma can be found in Section 6.5. Case (a) is a
straightforward extension of Bennett’s condition for upper-bounded random
variables with bounded variance to matrices with upper-bounded eigenvalues and
bounded matrix variance (Bennett, 1962, p. 42). Cases (b) and (c) are similar
extensions of Hoeffding’s sub-Gaussian conditions for bounded random variables
to matrices with bounded eigenvalues (Hoeffding, 1963, Theorems 1 and 2;
Kearns and Saul, 1998; Bercu et al., 2015, Theorem 2.49). In the conditionally
symmetric case (d), we can achieve control without any moment or boundedness
assumptions by defining $V_{t}$ in terms of observed rather than expected
squared deviations; this is known for $d=1$ (de la Peña, 1999, Lemma 6.1;
Bercu et al., 2015), allowing exponential concentration for distributions like
Cauchy. In the lower-bounded increments case (e), we have a self-normalized
complement to the Bennett-style bound, a result known for $d=1$ (Fan et al.,
2015, Lemma 4.1). For the square-integrable martingale cases (f, g), we
achieve control for a broad class of processes by incorporating the
conditional variance and the observed squared deviations, as known for $d=1$
(Delyon, 2009, Theorem 4; Bercu et al., 2015). The Hoeffding-like case (h)
follows from the self-normalized bounds, highlighting a connection implicit in
the proof of Corollary 4.2 of Mackey et al. (2014). The third moment bound (i)
is similar to a fixed-sample bound given by Fan et al. (2015, Corollary 2.2).

In the continuous-time, scalar case we have the following sufficient
conditions for a local martingale $(S_{t})$ to be sub-$\psi$. Here we always
assume $(S_{t})$ is càdlàg, $\Delta S_{t}\coloneqq S_{t}-S_{t-}$ denotes the
jumps of $S$, $[S]_{t}$ denotes the quadratic variation, and $\left\langle
S\right\rangle_{t}$ is the conditional quadratic variation, the compensator of
$[S]_{t}$.

######  Fact 2.

Here $\mathcal{T}=(0,\infty)$ and $d=1$, and we set $l_{0}=1$.

  1. (a)

(Lévy process) If $(S_{t})$ is a Lévy process which is a martingale with the
CGF $\psi(\lambda)=\log\mathbb{E}e^{\lambda S_{1}}<\infty$ for all
$\lambda\in[0,\lambda_{\max})$, then $(S_{t})$ is sub-$\psi$ with variance
process $V_{t}=t$. See, e.g., Papapantoleon (2008, Proposition 10.2).

  2. (b)

(Continuous Bennett) If $(S_{t})$ is a local martingale with $\Delta S_{t}\leq
c$ for all $t$ a.s., then $(S_{t})$ is sub-Poisson with scale parameter $c$
and variance process $V_{t}=\left\langle S\right\rangle_{t}$ (Lepingle, 1978,
p. 157).

  3. (c)

(Continuous Bernstein) Suppose $(S_{t})$ is a locally square integrable
martingale: let $W_{2,t}=\left\langle S\right\rangle_{t}$, and for
$m=3,4,\dots$ let $W_{m,t}$ be the compensator of the process $\sum_{u\leq
t}\lvert\Delta S_{u}\rvert^{m}$. If, for some $c>0$ and predictably
measurable, càdlàg, nondecreasing process $(V_{t})$, it holds that
$W_{m,t}\leq\frac{m!}{2}c^{m-2}V_{t}$ for all $m\geq 2$, then $(S_{t})$ is
sub-gamma with scale parameter $c$ and variance process $V_{t}$ (van de Geer,
1995, implicit in the proof of Lemma 2.2).

  4. (d)

(Continuous paths) If $(S_{t})$ is a local martingale with a.s. continuous
paths, then $(S_{t})$ is sub-Gaussian with variance process
$V_{t}=\left\langle S\right\rangle_{t}$. This may be seen as a special case of
(c), or a limiting case of (b).

###  3.3 Implications between sub-$\psi$ conditions

In many settings, a process $(S_{t})$ may satisfy Definition 1 with several
different choices of $\psi$ and $(V_{t})$. Choosing a smaller $\psi$ function
will lead to tighter bounds in Theorem 1, but in some cases one may opt for a
larger $\psi$ function to achieve analytical or computational convenience. It
is clear that making $\psi$ uniformly larger retains the sub-$\psi$ property,
since the exponential process $\exp\left\\{\lambda
S_{t}-\psi(\lambda)V_{t}\right\\}$ can only become smaller. It is therefore
useful to characterize relationships among the above sub-$\psi$ conditions, so
that, after invoking one of the sufficient conditions given in Section 3.2,
one may invoke Theorem 1 with a different, more convenient $\psi$ function.

Sub-Bernoulli Sub-Gaussian Sub-Poisson Sub-gamma Sub-exponential $c<0$$c<0$$c<0$ Figure 3: Each arrow indicates that any process satisfying the source sub-$\psi$ condition, subject to a restriction on the scale parameter $c$, also satisfies the destination sub-$\psi$ condition with appropriately scaled variance process. See Table 5 and Proposition 2 for details.  | $\psi_{1}$ | $\psi_{2}$ | $a$ | Restriction
---|---|---|---|---
(1) | $\psi_{B,g,h}$ | $\psi_{N}$ | $\frac{\varphi(g,h)}{gh}$ |
(2) | $\psi_{B,g,h}$ | $\psi_{N}$ | $\frac{(g+h)^{2}}{4gh}$ |
(3) | $\psi_{B,g,h}$ | $\psi_{P,h-g}$ | 1 |
(4) | $\psi_{N}$ | $\psi_{P,0}$ | 1 |
(5) | $\psi_{P,c}$ | $\psi_{G,c/3}$ | 1 |
(6) | $\psi_{G,c}$ | $\psi_{E,3c/2}$ | 1 |
(7) | $\psi_{E,c}$ | $\psi_{G,c}$ | 1 | $c\geq 0$
(8) | $\psi_{E,c}$ | $\psi_{G,c/2}$ | 1 | $c<0$
(9) | $\psi_{G,c}$ | $\psi_{P,2c}$ | 1 | $c<0$
(10) | $\psi_{P,c}$ | $\psi_{N}$ | 1 | $c<0$
(11) | $\psi_{P,c}$ | $\psi_{B,-c,h}$ | 1 |  $c<0$, any $h>0$
Table 5: If $(S_{t})$ is sub-$\psi_{1}$ with variance process $(V_{t})$,
subject to the given restriction, then $(S_{t})$ is also sub-$\psi_{2}$ with
variance process $(aV_{t})$. $\varphi(g,h)$ is defined in (3.7). See
Proposition 2 for details.

Note that $\psi_{G}$, $\psi_{P}$ and $\psi_{E}$ are nondecreasing in $c$ for
all values of $\lambda\geq 0$, so that if a process is sub-$\psi$ with scale
$c$ for any of these $\psi$ functions, then it is sub-$\psi$ for any scale
$c^{\prime}>c$ as well. Similarly, $\psi_{B}$ is nonincreasing in $g$ and
nondecreasing in $h$. Table 5 and Proposition 2 fully characterize all
implications among sub-$\psi$ conditions, as illustrated in Figure 3. These
follow from inequalities of the form $\psi_{1}\leq a\psi_{2}$, some of which
are based on standard arguments; see Section 6.3.

######  Proposition 2.

For each row in Table 5, if $(S_{t})$ is sub-$\psi_{1}$ with variance process
$(V_{t})$, and the given restrictions are satisfied, then $(S_{t})$ is also
sub-$\psi_{2}$ with variance process $(aV_{t})$. Furthermore, when we allow
only scaling of $V_{t}$ by a constant, these capture all possible implications
among the five sub-$\psi$ conditions defined above, and the given constants
are the best possible (in the case of row (2), the constant $(g+h)^{2}/4gh$ is
the best possible of the form $k/gh$ where $k$ depends only on the total range
$g+h$).

##  4 Applications of Theorem 1

Here, we illustrate how Theorem 1 recovers or strengthens a wide variety of
existing results. Most results in this section follow immediately upon
combining one of the sufficient conditions from Fact 1, Lemma 3, or Fact 2
with Theorem 1, and we omit proof details in many cases. As a rough plan, we
first discuss classical Cramér-Chernoff and Freedman-style bounds and then
Blackwell’s line crossing inequalities. After discussing de la Peña-style
self-normalized bounds and Pinelis’ Banach-space inequalities, we end by
exhibiting some continuous time results and mention connections to the
sequential probability ratio test.

###  4.1 Fixed-time Cramér-Chernoff and Freedman-style uniform bounds

Figure 4: Comparison of $(i)$ fixed-time Cramér-Chernoff bound (4.2), which
bounds the deviations of $S_{m}$ at a fixed time $m$; $(ii)$ “Freedman-style”
constant uniform bound (4.3), which bounds the deviations of $S_{t}$ for all
$t$ such that $V_{t}\leq m$, with a constant boundary equal in value to the
fixed-time Cramér-Chernoff bound; and $(iii)$ linear uniform bound from
Theorem 1(b), which bounds the deviations of $S_{t}$ for all $t\in\mathbb{N}$,
with a boundary growing linearly in $V_{t}$. Each bound gives the same tail
probability and thus implies the preceding one.

In the discrete-time, scalar setting, a simple sufficient condition for a
process $(S_{t})$ to be 1-sub-$\psi$ with variance process $(V_{t})$ is that

$\displaystyle\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
S_{t}-\psi(\lambda)\Delta V_{t}\right\\}\leq 1,\quad\forall t,$ (4.1)

which is the standard assumption for a martingale-method Cramér-Chernoff
inequality, typically with $(V_{t})$ predictable (McDiarmid, 1998; Chung and
Lu, 2006; Boucheron et al., 2013). When $(V_{t})$ is deterministic, the fixed-
time Cramér-Chernoff method gives, for fixed $x$ and $m$,

$\displaystyle\mathbb{P}(S_{m}\geq
x)\leq\exp\left\\{-V_{m}\psi^{\star}\left(\frac{x}{V_{m}}\right)\right\\},$
(4.2)

so Theorem 1(b) is a uniform _extension_ of the Cramér-Chernoff inequality,
losing nothing at the fixed time $m$ [B; C or D]. For random $(V_{t})$, a
stopping time argument due to Freedman (1975) extends this to the uniform
bound

$\displaystyle\mathbb{P}(\exists t\in\mathcal{T}:S_{t}\geq x\text{ and
}V_{t}\leq m)\leq\exp\left\\{-m\psi^{\star}\left(\frac{x}{m}\right)\right\\}.$
(4.3)

When $(V_{t})$ is deterministic, analogous uniform bounds can be obtained from
Doob’s maximal inequality for submartingales, as in Hoeffding (1963, eq.
2.17). Theorem 1 strengthens this “Freedman-style” inequality [B; C or D],
since it yields tighter bounds for all times $t$ such that $V_{t}<m$, and also
extends the inequality to hold for all times $t$ with $V_{t}>m$, as
illustrated by Figure 4.

Tropp (2011, 2012) extends the scalar Cramér-Chernoff approach to random
matrices via control of the matrix moment-generating function, giving matrix
analogues of Hoeffding’s, Bennett’s, Bernstein’s and Freedman’s inequalities.
Following this approach, Theorem 1 gives corresponding strengthened versions
of these inequalities for matrix-valued processes [B].

We summarize explicit results below for three well-known special cases
reviewed in Example 1(a): Hoeffding’s sub-Gaussian inequality for observations
bounded from above and below, with variance process depending only on the
radius of the interval of boundedness (Hoeffding, 1963); Bennett’s sub-Poisson
inequality for observations bounded from above, with variance process
depending on the true variance of the observations (Bennett, 1962); and
Bernstein’s sub-gamma inequality for observations satisfying a bound on growth
of higher moments, also with a variance process depending on the true variance
(Bernstein, 1927). In each case below, we recover the standard, fixed-sample
result at $V_{t}=m$. Recall the definitions of
$\mathfrak{s}_{P},\psi^{\star}_{P},\mathfrak{s}_{G},\psi^{\star}_{G}$ from
Table 2.

######  Corollary 1.

  1. (a)

Suppose $(Y_{t})_{t\in\mathbb{N}}$ is an $\mathcal{H}^{d}$-valued martingale
whose increments satisfy $\Delta Y_{t}^{2}\preceq A_{t}^{2}$ a.s. for all $t$
for some $\mathcal{H}^{d}$-valued, predictable sequence $(A_{t})$. Let
$S_{t}\coloneqq\gamma_{\max}(Y_{t})$, and let either

$\displaystyle V_{t}\coloneqq\frac{1}{2}\gamma_{\max}\left(\left\langle
Y\right\rangle_{t}+\sum_{i=1}^{t}A_{i}^{2}\right)\quad\text{or}\quad
V_{t}\coloneqq\gamma_{\max}\left(\sum_{i=1}^{t}A_{i}^{2}\right).$ (4.4)

Then for any $x,m>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+\frac{x}{2m}(V_{t}-m)\right)\leq d\exp\left\\{-\frac{x^{2}}{2m}\right\\}.$
(4.5)

This strengthens Hoeffding’s inequality (Hoeffding, 1963) [A,B,D] and its
matrix analogues in Tropp (2012, Theorem 7.1) [B,E] and Mackey et al. (2014,
Corollary 4.2) [A,B].

  2. (b)

Suppose $(Y_{t})_{t\in\mathbb{N}}$ is an $\mathcal{H}^{d}$-valued martingale
satisfying $\gamma_{\max}(\Delta Y_{t})\leq c$ a.s. for all $t$. Let
$S_{t}\coloneqq\gamma_{\max}(Y_{t})$ and
$V_{t}\coloneqq\gamma_{\max}(\left\langle Y\right\rangle_{t})$. Then for any
$x,m>0$, we have

$\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+\mathfrak{s}_{P}\left(\frac{x}{m}\right)\cdot(V_{t}-m)\right)\leq
d\exp\left\\{-m\psi^{\star}_{P}\left(\frac{x}{m}\right)\right\\}\\\ \leq
d\exp\left\\{-\frac{x^{2}}{2(m+cx/3)}\right\\}.$ (4.6)

This strengthens Bennett’s and Freedman’s inequalities (Bennett, 1962;
Freedman, 1975) [B; C or D] for scalars and the corresponding matrix bounds
from Tropp (2011, 2012) [B].

  3. (c)

Suppose $(S_{t})$ is $l_{0}$-sub-gamma with variance process $(V_{t})$ and
scale parameter $c$. Then for any $x,m>0$, we have

$\mathbb{P}\left(\exists t\in\mathcal{T}:S_{t}\geq
x+\mathfrak{s}_{G}\left(\frac{x}{m}\right)\cdot(V_{t}-m)\right)\leq
l_{0}\exp\left\\{-m\psi^{\star}_{G}\left(\frac{x}{m}\right)\right\\}\\\ \leq
l_{0}\exp\left\\{-\frac{x^{2}}{2(m+cx)}\right\\}.$ (4.7)

This strengthens Bernstein’s inequality (Bernstein, 1927) [B; C or D], along
with the matrix Bernstein inequality (Tropp, 2012) [B].

Case (a) is a consequence of Lemma 3(g); see also Corollary 8, which uses
$V_{t}=\frac{1}{2}\gamma_{\max}([Y_{+}]_{t}+\left\langle
Y_{-}\right\rangle_{t})$. The first setting of $V_{t}$ in case (a) follows
from the bound $[Y_{+}]_{t}\preceq\sum_{i=1}^{t}A_{i}^{2}$, and further upper
bounding $\left\langle Y_{-}\right\rangle_{t}\preceq\sum_{i=1}^{t}A_{i}^{2}$
yields the second setting of $V_{t}$. As is well known, the Hoeffding-style
bound in part (a) and the Bennett-style bound in part (b) are not directly
comparable: $V_{t}$ may be smaller in part (b), but
$\psi^{\star}_{P}\leq\psi^{\star}_{N}$, so neither subsumes the other. We
remark that
$\psi^{\star}_{P}(u)\geq\frac{u}{2c}\operatorname{arcsinh}\left(\frac{cu}{2}\right)$,
so the Bennett-style inequality in part (b) is an improvement on the
inequality of Prokhorov (1959) for sums of independent random variables, as
noted by Hoeffding (1963), as well as its extension to martingales in de la
Peña (1999).

As an example of the Hermitian dilation technique for extending bounds on
Hermitian matrices to bounds for rectangular matrices, we give a bound for
rectangular matrix Gaussian and Rademacher series, following Tropp (2012);
here $\lVert A\rVert_{\text{op}}$ denotes the largest singular value of $A$.
The proof is in Section 6.6.

######  Corollary 2.

Consider a sequence $(B_{t})_{t\in\mathbb{N}}$ of fixed matrices with
dimension $d_{1}\times d_{2}$, and let $(\epsilon_{t})_{t\in\mathbb{N}}$ be a
sequence of independent standard normal or Rademacher variables. Let
$S_{t}\coloneqq\lVert\sum_{i=1}^{t}\epsilon_{i}B_{i}\rVert_{\text{op}}$ and

$\displaystyle
V_{t}\coloneqq\max\left\\{\lVert\sum_{i=1}^{t}B_{i}B_{i}^{\star}\rVert_{\text{op}},\lVert\sum_{i=1}^{t}B_{i}^{\star}B_{i}\rVert_{\text{op}}\right\\}.$
(4.8)

Then for any $x,m>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+\frac{x}{2m}(V_{t}-m)\right)\leq(d_{1}+d_{2})\exp\left\\{-\frac{x^{2}}{2m}\right\\}.$
(4.9)

This strengthens Corollary 4.2 of Tropp (2012) [B].

###  4.2 Line-crossing inequalities

Before giving specific results in this section, we start with simplified
versions of Theorem 1(d) which are useful for recovering existing results. The
probability bound in (4.10) is merely an analytically simplified upper bound
on that from Theorem 1(d). We prove the following in Section 6.7.

######  Corollary 3.

If $(S_{t})$ is $l_{0}$-sub-$\psi$ with variance process $(V_{t})$ and $\psi$
is CGF-like, then for any $m\geq 0$, $x>0$ and $b\in(0,\bar{b})$, we have

$\mathbb{P}\left(\exists t\in\mathcal{T}:V_{t}\geq m\text{ and }S_{t}\geq
x+b(V_{t}-m)\right)\\\ \leq
l_{0}\exp\left\\{-m\psi^{\star}(b)-(x-bm){\psi^{\star}}^{\prime}(b)\right\\}.$
(4.10)

In particular, for $m>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathcal{T}:V_{t}\geq m\text{ and
}S_{t}\geq bV_{t}\right)\leq l_{0}\exp\left\\{-m\psi^{\star}(b)\right\\}.$
(4.11)

In fitting with the approach of this paper, Theorem 1(d) and Corollary 3 bound
the upcrossing probability on $\\{V_{t}\geq m\\}$ using the results of Theorem
1(a,b) and a geometric argument. It may seem naive and wasteful to bound a
line-crossing probability on $\\{V_{t}\geq m\\}$ using a bound which applies
for $\\{V_{t}>0\\}$. The literature includes a handful of results bounding
line-crossing probabilities on $\\{V_{t}\geq m\\}$ which appear to give bounds
tighter than what Theorem 1 offers, by making more direct use of the
intrinsic-time condition (Blackwell, 1997; Khan, 2009). Below we demonstrate
that this is not true: we give several special cases of Theorem 1(d) and
Corollary 3 which improve upon existing results.

######  Corollary 4.

Suppose $(S_{t})$ is $l_{0}$-sub-gamma with variance process $(V_{t})$ and
scale parameter $c$.

  1. (a)

For any $a,b>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathcal{T}:S_{t}\geq
a+bV_{t}\right)\leq l_{0}\exp\left\\{-\frac{2ab}{1+2cb}\right\\}.$ (4.12)

When $\mathcal{T}=\mathbb{N}$, $c=0$ and $d=1$ this strengthens Theorem 1 of
Blackwell (1997) [A; C or D], which is written for discrete-time scalar
processes with bounded increments.

  2. (b)

For any $m,b>0$, we have

$\mathbb{P}\left(\exists t\in\mathcal{T}:V_{t}\geq m\text{ and }S_{t}\geq
bV_{t}\right)\leq l_{0}\exp\left\\{-m\psi^{\star}_{G}(b)\right\\}\\\ \leq
l_{0}\exp\left\\{-\frac{b^{2}m}{2(1+cb)}\right\\}.$ (4.13)

When $\mathcal{T}=\mathbb{N}$, $c=0$ and $d=1$ this strengthens the second
bound in Theorem 2 of Blackwell (1997) [A; C or D], which is written for
discrete-time scalar processes with bounded increments.

In discrete time, as presented in Fact 1, for a process with bounded
increments we may construct both sub-Bernoulli and sub-Gaussian bounds. The
sub-Bernoulli case, in combination with (4.11), yields the following:

######  Corollary 5.

Suppose $(Y_{t})_{t\in\mathbb{N}}$ is an $\mathcal{H}^{d}$-valued martingale
satisfying $\lVert\Delta Y_{t}\rVert_{\text{op}}\leq 1$ a.s. for all
$t\in\mathbb{N}$. Then for any $b\in[0,1]$ and $m\geq 1$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:t\geq m\text{ and
}\gamma_{\max}(Y_{t})\geq
bt\right)\leq\left[(1+b)^{(1+b)}(1-b)^{(1-b)}\right]^{-m/2}.$ (4.14)

This strengthens the first bound in Theorem 2 of Blackwell (1997) [D].

Theorems 4.1-4.3 of Khan (2009) are closest in form to our main results and
represent key precedents to our framework. The simplified bound (4.10)
recovers Khan’s Theorem 4.3 [C or D], while Theorem 1(d) improves the exponent
[E]. Our Theorem 1(b) gives a strengthened version of Khan’s “Freedman-style”
Theorem 4.2 [B; C or D]. Khan’s Theorem 4.1 is not strictly comparable to our
work since it involves an initial condition on _nominal_ time, $t\geq t_{0}$,
rather than on intrinsic time, $V_{t}\geq m$, but when $V_{t}$ is
deterministic, then our Theorem 1(d) is tighter [B; C or D; E].

###  4.3 Self-normalized uniform bounds

Collectively, de la Peña (1999); de la Peña et al. (2000, 2004, 2007); de la
Peña, Klass and Lai (2009); and de la Peña, Lai and Shao (2009) give a wide
variety of sufficient conditions for the exponential process
$\exp\left\\{\lambda S_{t}-\psi(\lambda)V_{t}\right\\}$ to be a
supermartingale in both discrete- and continuous-time settings. They formulate
their bounds for ratios involving $S_{t}$ in the numerator and $V_{t}$ in the
denominator, as in Theorem 1(c), and often specify initial-time conditions, as
in Theorem 1(d). In this section we draw some comparisons between Theorem 1
and their results. As a first example, consider the boundary of Theorem 1(c)
for the ratio $S_{t}/V_{t}$, strictly decreasing towards the asymptotic level
$\mathfrak{s}(x)$. In particular, at time $V_{t}=m$ the boundary equals $x$,
so Theorem 1(c) strengthens various theorems of de la Peña (1999) and de la
Peña et al. (2007) which use a constant boundary after time $V_{t}=m$ [B; C or
D]; for example, Theorem 1.2B, eq. 1.5 of de la Peña (1999) states that

$\displaystyle\mathbb{P}\left(\exists t\geq 1:V_{t}\geq m\text{ and
}\frac{S_{t}}{V_{t}}\geq
x\right)\leq\exp\left\\{-m\psi_{G}^{\star}(x)\right\\}$ (4.15)

for scalar processes $(S_{t})$ which are 1-sub-gamma with variance process
$(V_{t})$. As before, we give explicit results for special cases.

Figure 5: Comparison of our decreasing boundary from Theorem 1(c), as in
inequality (4.16), to a “de la Peña-style” constant uniform bound as in
inequality (4.15), which bounds the deviations of $S_{t}/V_{t}$ for all $t$
such that $V_{t}\geq m$ with a constant boundary.

######  Corollary 6.

Suppose $(S_{t})$ is $l_{0}$-sub-gamma with variance process $(V_{t})$ and
scale parameter $c$. Then for any $x,m>0$, we have

$\mathbb{P}\left(\exists
t\in\mathcal{T}:\frac{S_{t}}{V_{t}}\geq\mathfrak{s}_{G}(x)\left(1+\frac{m\sqrt{1+2cx}}{V_{t}}\right)\right)\leq
l_{0}\exp\left\\{-m\psi^{\star}_{G}(x)\right\\}\\\ \leq
l_{0}\exp\left\\{-\frac{mx^{2}}{2(1+cx)}\right\\}.$ (4.16)

This strengthens eq. 1.5 from Theorem 1.2B of de la Peña (1999) [B; C or D].
In the sub-Gaussian case (obtained at $c=0$), the above bound simplifies to

$\displaystyle\mathbb{P}\left(\exists
t\in\mathcal{T}:\frac{S_{t}}{V_{t}+m}\geq x\right)\leq
l_{0}\exp\left\\{-2mx^{2}\right\\}.$ (4.17)

This strengthens Theorem 2.1 of de la Peña et al. (2007) and Theorem 6.1 of de
la Peña (1999) [B, C or D].

Recall that $\mathfrak{s}_{G}(x)=x/(1+\sqrt{1+2cx})$, so for the boundary in
(4.16), we have $\mathfrak{s}_{G}(x)(1+m\sqrt{1+2cx}/V_{t})\leq x$ for all
$V_{t}\geq m$ with equality at $V_{t}=m$. Corollary 6(a), therefore, gives the
same probability bound as (4.15) for a larger crossing event. Figure 5
visualizes this relationship.

More generally, when we normalize by $\alpha+\beta V_{t}$ and include an
initial time condition $V_{t}\geq m$, Theorem 1(d) and Corollary 3 become the
following:

######  Corollary 7.

If $(S_{t})$ is $l_{0}$-sub-$\psi$ with variance process $(V_{t})$, where
$\psi$ is CGF-like and $\bar{b}=\infty$, then for any $\beta,x>0$ and
$\alpha,m\geq 0$ with at least one of $\alpha,m>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathcal{T}:V_{t}\geq m\text{ and
}\frac{S_{t}}{\alpha+\beta V_{t}}\geq x\right)$ (4.18)
$\displaystyle\qquad\leq\begin{cases}l_{0}\exp\left\\{-\alpha xD(\beta
x)\right\\},&\beta x\leq\mathfrak{s}\left(\frac{x(\alpha+\beta
m)}{m}\right)\\\ l_{0}\exp\left\\{-m\psi^{\star}\left(\frac{x(\alpha+\beta
m)}{m}\right)\right\\},&\beta x\geq\mathfrak{s}\left(\frac{x(\alpha+\beta
m)}{m}\right)\end{cases}$ (4.19) $\displaystyle\qquad\leq
l_{0}\exp\left\\{-m\psi^{\star}(\beta x)-\alpha x{\psi^{\star}}^{\prime}(\beta
x)\right\\}.$ (4.20)

In the case $(S_{t})$ is sub-Gaussian, for any $\beta,x>0$ and $\alpha,m\geq
0$ with at least one of $\alpha,m>0$, we have

$\mathbb{P}\left(\exists t\in\mathcal{T}:V_{t}\geq m\text{ and
}\frac{S_{t}}{\alpha+\beta V_{t}}\geq x\right)\\\
\leq\exp\left\\{-x^{2}\left(2\alpha\beta+\frac{(\beta
m-\alpha)^{2}1_{\alpha\leq\beta m}}{2m}\right)\right\\},$ (4.21)

taking $0/0=0$ on the right-hand side when $m=0$. With Lemma 3(d), this
improves eq. 6.4 from Theorem 6.2 of de la Peña (1999) [C or D; E].

A defining feature of self-normalized bounds is that they involve a variance
process $(V_{t})$ constructed with the squared observations themselves rather
than just conditional variances or constants. Such normalization can be found
in common statistical procedures such as the $t$-test. Furthermore, it allows
for Gaussian-like concentration while reducing or eliminating moment
conditions. Lemma 3 gives several extensions of well-known conditions for
scalar sub-Gaussian concentration of self-normalized processes. As one
particular special case, Lemma 3(f) and (g) yield general self-normalized
uniform bounds for any discrete-time, square-integrable,
$\mathcal{H}^{d}$-valued martingale, building upon breakthrough results
obtained for scalar processes by Bercu, Touati and Delyon:

######  Corollary 8.

Suppose $(Y_{t})_{t\in\mathbb{N}}$ is an $\mathcal{H}^{d}$-valued martingale
with $\mathbb{E}Y_{t}^{2}<\infty$ for all $t\in\mathbb{N}$. Let
${S_{t}\coloneqq\gamma_{\max}(Y_{t})}$ and either

$\displaystyle V_{t}\coloneqq\frac{1}{2}\gamma_{\max}([Y_{+}]_{t}+\left\langle
Y_{-}\right\rangle_{t})\quad\text{or}\quad
V_{t}\coloneqq\frac{1}{3}\gamma_{\max}([Y]_{t}+2\left\langle
Y\right\rangle_{t}).$ (4.22)

Then for any $x,m>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:\frac{S_{t}}{V_{t}+m}\geq
x\right)\leq d\exp\left\\{-2mx^{2}\right\\}.$ (4.23)

This strengthens eq. 20 from Theorem 4 of Delyon (2009) [B,D], Theorem 2.1 of
Bercu and Touati (2008) [B,D,E], and an implicit self-normalized bound of
Mackey et al. (2014, Corollary 4.2) [B].

Corollary 8 is remarkable for the fact that it gives Gaussian-like
concentration with only the existence of second moments for the increments. If
the increments have conditionally symmetric distributions, one may instead
apply Lemma 3(d) to achieve Gaussian-like concentration without existence of
any moments, as discovered by de la Peña (1999) and illustrated in the
following example.

######  Example 5 (Cauchy increments).

Let $(\Delta S_{t})_{t\in\mathbb{N}}$ be i.i.d. standard Cauchy random
variables (symmetric about zero). Lemma 3(d) shows that $(S_{t})$ is sub-
Gaussian with variance process $V_{t}=[S]_{t}$. Corollary 6 yields, for any
$x,m>0$,

$\displaystyle\mathbb{P}\left(\exists
t\in\mathbb{N}:\frac{S_{t}}{[S]_{t}+m}\geq
x\right)\leq\exp\left\\{-2mx^{2}\right\\}.$ (4.24)

For another example, Lemma 3(i) gives a self-normalized bound involving third
rather than second moments:

######  Corollary 9.

Suppose $(Y_{t})_{t\in\mathbb{N}}$ is an $\mathcal{H}^{d}$-valued martingale
with $\mathbb{E}\left\lvert Y_{t}\right\rvert^{3}$ finite for all
$t\in\mathbb{N}$. Let ${S_{t}\coloneqq\gamma_{\max}(Y_{t})}$ and
${V_{t}\coloneqq\gamma_{\max}([Y]_{t}+\sum_{i=1}^{t}\mathbb{E}_{i-1}(\Delta
Y_{i})_{-}^{3})}$. Then for $\mathfrak{s}_{G}$ and $\psi^{\star}_{G}$ using
$c=1/6$, we have for any $x,m>0$,

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+\mathfrak{s}_{G}\left(\frac{x}{m}\right)\cdot(V_{t}-m)\right)$
$\displaystyle\leq
d\exp\left\\{-m\psi^{\star}_{G}\left(\frac{x}{m}\right)\right\\}$ (4.25)
$\displaystyle\leq d\exp\left\\{-\frac{x^{2}}{2(m+x/6)}\right\\}.$ (4.26)

This is a uniform alternative to Corollary 2.2 of Fan et al. (2015) [B,D].

Note the exponent in (4.26) is different from that in Fan et al. (2015);
neither strictly dominates the other. Also note that, unlike the classical
Bernstein bound, neither of Corollaries 8 and 9 assume existence of moments of
all orders.

###  4.4 Martingales in smooth Banach spaces

The applications presented thus far allow us to uniformly bound the operator
norm deviations of a sequence of random Hermitian matrices. A different
approach is due to Pinelis (1992, 1994), who gave an innovative approach to
exponential tail bounds in abstract Banach spaces. We describe how this
approach can be incorporated into our framework. For this section, let
$(Y_{t})_{t\in\mathbb{N}}$ be a martingale with respect to $(\mathcal{F}_{t})$
taking values in a separable Banach space $(\mathcal{X},\lVert\cdot\rVert)$.
We can use Pinelis’s device to uniformly bound the process $(\Psi(Y_{t}))$ for
any function $\Psi:\mathcal{X}\to\mathbb{R}$ which satisfies the following
smoothness property:

######  Definition 3 (Pinelis, 1994).

A function $\Psi:\mathcal{X}\to\mathbb{R}$ is called _$(2,D)$ -smooth_ for
some $D>0$ if, for all $x,v\in\mathcal{X}$, we have

$\displaystyle\Psi(0)$ $\displaystyle=0$ (4.27a)
$\displaystyle\lvert\Psi(x+v)-\Psi(x)\rvert$ $\displaystyle\leq\lVert v\rVert$
(4.27b) $\displaystyle\Psi^{2}(x+v)-2\Psi^{2}(x)+\Psi^{2}(x-v)$
$\displaystyle\leq 2D^{2}\lVert v\rVert^{2}.$ (4.27c)

A Banach space is called $(2,D)$-smooth if its norm is $(2,D)$-smooth; in such
a space we may take $\Psi(\cdot)=\lVert\cdot\rVert$ to uniformly bound the
deviations of a martingale. In this case, observe that property (4.27a) is
part of the definition of a norm, property (4.27b) is the triangle inequality,
and property (4.27c) can be seen to hold with $D=1$ for the norm induced by
the inner product in any Hilbert space, regardless of the (possibly infinite)
dimensionality of the space. Note also that setting $x=0$ shows that $D\geq 1$
whenever $\Psi(\cdot)=\lVert\cdot\rVert$. Finally, observe that if we write
$f(x)=\Psi^{2}(x)$, then we may equivalently replace condition (4.27c) by
$f(tx+(1-t)y)\geq tf(x)+(1-t)f(y)-D^{2}t(1-t)\lVert x-y\rVert^{2}$, a perhaps
more familiar definition of smoothness.

######  Corollary 10.

Consider a martingale $(Y_{t})_{t\in\mathbb{N}}$ taking values in a separable
Banach space $(\mathcal{X},\lVert\cdot\rVert)$. Let the function
$\Psi:\mathcal{X}\to\mathbb{R}$ be $(2,D)$-smooth and define
$D_{\star}\coloneqq 1\vee D$.

  1. (a)

Suppose $\lVert\Delta Y_{t}\rVert\leq c_{t}$ a.s. for all $t\in\mathbb{N}$ for
some constants $(c_{t})_{t\in\mathbb{N}}$, and let
$V_{t}\coloneqq\sum_{i=1}^{t}c_{i}^{2}$. Then for any $x,m>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:\Psi(Y_{t})\geq
x+\frac{D_{\star}^{2}x}{2m}(V_{t}-m)\right)\leq
2\exp\left\\{-\frac{x^{2}}{2D_{\star}^{2}m}\right\\}.$ (4.28)

This strengthens Theorem 3.5 from Pinelis (1994) [B].

  2. (b)

Suppose $\lVert\Delta Y_{t}\rVert\leq c$ a.s. for all $t\in\mathbb{N}$ for
some constant $c$, and let
$V_{t}\coloneqq\sum_{i=1}^{t}\mathbb{E}_{i-1}\lVert\Delta Y_{i}\rVert^{2}$.
Then for any $x,m>0$, we have

$\mathbb{P}\left(\exists t\in\mathbb{N}:\Psi(Y_{t})\geq
x+D_{\star}^{2}\mathfrak{s}_{P}\left(\frac{x}{m}\right)\cdot(V_{t}-m)\right)\\\
\leq
2\exp\left\\{-D_{\star}^{2}m\psi^{\star}_{P}\left(\frac{x}{D_{\star}^{2}m}\right)\right\\}\leq
2\exp\left\\{-\frac{x^{2}}{2(D_{\star}^{2}m+cx/3)}\right\\}.$ (4.29)

This strengthens Theorem 3.4 from Pinelis (1994) [B].

We prove this result in Section 6.8. As before, the Hoeffding-style bound in
part (a) and the Bennett-style bound in part (b) are not directly comparable:
$V_{t}$ may be smaller in part (b), but the exponent is also smaller.

We briefly highlight some of the strengths and limitations of this approach.
Since the Euclidean $l_{2}$-norm is induced by the standard inner product in
$\mathbb{R}^{d}$, Corollary 10 gives a dimension-free uniform bound on the
$l_{2}$-norm deviations of a vector-valued martingale in $\mathbb{R}^{d}$
which exactly matches the form for scalars. Compare this to bounds based on
the operator norm of a Hermitian dilation: the bound of Tropp (2012) includes
dimension dependence [B,E] while the bound of Minsker (2017, Corollary 4.1)
incurs an extra constant factor of 14 [B,E]. Our bounds extend to martingales
taking values in sequence space
$\left\\{(a_{i})_{i\in\mathbb{N}}:\sum_{i}\lvert
a_{i}\rvert^{2}<\infty\right\\}$ or function space $L^{2}[0,1]$, and we may
instead use the $l_{p}$ norm, $p\geq 2$, in which case $D=\sqrt{p-1}$. These
cases follow from Pinelis (1994, Proposition 2.1).

Similarly, Corollary 10 gives dimension-free uniform bounds for the Frobenius-
norm deviations of a matrix-valued martingale. This extends to martingales
taking values in a space of Hilbert-Schmidt operators on a separable Hilbert
space, with deviations bounded in the Hilbert-Schmidt norm; compare Minsker
(2017, §3.2), which gives operator-norm bounds. The method of Corollary 10
does not extend directly to operator-norm bounds because the operator norm is
not $(2,D)$-smooth for any $D$: for a simple illustration in
$\mathcal{H}^{2}$, consider $x=aI_{2}$ and $v=\operatorname{diag}\\{b,-b\\}$,
so that $\lVert x+v\rVert_{\text{op}}^{2}+\lVert
x-v\rVert_{\text{op}}^{2}-2\lVert x\rVert_{\text{op}}^{2}=2b^{2}+4ab$ and
condition (4.27c) cannot be satisfied. However, Corollary 10 does apply to the
matrix Schatten $p$-norm for $p<\infty$, using $D=\sqrt{p-1}$, and this holds
for rectangular matrices as well (Ball et al., 1994).

###  4.5 Continuous-time processes

While Corollaries 1, 4, 6, and 7 already generalize results known in discrete
time to new results for continuous-time martingales [C], here we summarize a
few more useful bounds explicitly for continuous-time processes which follow
from Theorem 1 and the conditions of Fact 2, making use of the novel
strategies devised by Shorack and Wellner (1986) and van de Geer (1995). These
results use the conditional quadratic variation $\left\langle
S\right\rangle_{t}$. We remind the reader that $[S]_{t}=\left\langle
S\right\rangle_{t}=t$ for Brownian motion, and the first equality holds more
generally for martingales with continuous paths, while for a Poisson process
with rate one, $\left\langle S\right\rangle_{t}=t$ but $[S]_{t}=S_{t}$.

######  Corollary 11.

Let $(S_{t})_{t\in(0,\infty)}$ be a real-valued process.

  1. (a)

If $(S_{t})$ is a locally square-integrable martingale with a.s. continuous
paths, then for any $a,b>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in(0,\infty):S_{t}\geq a+b\left\langle
S\right\rangle_{t}\right)\leq e^{-2ab}.$ (4.30)

If $\left\langle S\right\rangle_{t}\uparrow\infty$ as $t\uparrow\infty$, then
the probability upper bound holds with equality. This recovers as a special
case the standard line-crossing probability for Brownian motion (e.g.,
Durrett, 2017, Exercise 7.5.2).

  2. (b)

If $(S_{t})$ is a local martingale with $\Delta S_{t}\leq c$ for all $t$, then
for any $x,m>0$, we have

$\mathbb{P}\left(\exists t\in(0,\infty):S_{t}\geq
x+\mathfrak{s}_{P}\left(\frac{x}{m}\right)\cdot(\left\langle
S\right\rangle_{t}-m)\right)\\\
\leq\exp\left\\{-m\psi^{\star}_{P}\left(\frac{x}{m}\right)\right\\}\leq\exp\left\\{-\frac{x^{2}}{2(m+cx/3)}\right\\}.$
(4.31)

This strengthens Appendix B, Inequality 1 of Shorack and Wellner (1986) [B].

  3. (c)

If $(S_{t})$ is any locally square-integrable martingale satisfying the
Bernstein condition of Fact 2(c) for some predictable process $(V_{t})$, then
for any $x,m>0$, we have

$\mathbb{P}\left(\exists t\in(0,\infty):S_{t}\geq
x+\mathfrak{s}_{G}\left(\frac{x}{m}\right)\cdot(V_{t}-m)\right)\\\
\leq\exp\left\\{-m\psi^{\star}_{G}\left(\frac{x}{m}\right)\right\\}\leq\exp\left\\{-\frac{x^{2}}{2(m+cx)}\right\\}.$
(4.32)

This strengthens Lemma 2.2 of van de Geer (1995) [B,E].

Clearly, Corollary 11(b) applies to centered Poisson processes with ${c=1}$.
Of course, one can also apply Fact 2(a) for general Lévy processes, obtaining
the same bound (4.31). The point of Corollary 11(b) is that any local
martingale with bounded jumps obeys this inequality, and so concentrates like
a centered Poisson process in this sense. Barlow et al. (1986, §4) describe
further exponential supermartingales obtained for continuous-time processes
using the quadratic variation, and derive “Freedman-style” self-normalized
bounds; incorporating these cases into our framework would be interesting
future work.

###  4.6 Exponential families and the sequential probability ratio test

It is well known that the likelihood ratio
$f_{1,t}(X_{1}^{t})/f_{0,t}(X_{1}^{t})$ is a martingale under the null
hypothesis that $X_{1}^{t}\sim f_{0,t}$. Then Ville’s inequality gives a
sequential test with valid type I error, equivalent to an open-ended
sequential probability ratio test (SPRT, Wald, 1945), in which we stop when
the likelihood ratio exceeds an upper threshold, but not when it drops below
any lower threshold. In the one-parameter exponential family case, we obtain a
simple analytical result which is equivalent to Theorem 1, as we detail below.

Suppose $(X_{t})_{t\in\mathbb{N}}$ are i.i.d. from a one-parameter exponential
family with natural parameter $\theta$ and log-partition function $A$, so that
$X_{t}$ has density $f_{\theta}(x)=h(x)\exp\left\\{\theta
T(x)-A(\theta)\right\\}$. Let $S_{t}=\sum_{i=1}^{t}T(X_{i})$. An open-ended
SPRT testing $H_{0}:\theta=\theta_{0}$ against
$H_{1}:\theta=\theta_{0}+\lambda$ stops to reject $H_{0}$ as soon as the
likelihood ratio $L_{t}=\exp\left\\{\lambda
S_{t}-[A(\theta_{0}+\lambda)-A(\theta_{0})]t\right\\}$ exceeds the threshold
$\alpha^{-1}>1$.

######  Corollary 12.

This one-sided SPRT has type I error rate no greater than $\alpha$:
$\mathbb{P}_{\theta_{0}}(\exists
t\in\mathbb{N}:L_{t}\geq\alpha^{-1})\leq\alpha$.

This standard fact follows easily from Theorem 1 because $L_{t}\geq A$ if and
only if $S_{t}\geq(\log A)/\lambda+\psi(\lambda)t/\lambda$, where
$\psi(\lambda)=A(\theta_{0}+\lambda)-A(\theta_{0})$, the CGF of $T(X_{i})$ at
$\theta=\theta_{0}$. Hence the rejection boundary for the SPRT is equivalent
to the linear boundary of Theorem 1. In light of this, we may interpret the
above sub-Gaussian, sub-Poisson, sub-exponential and sub-Bernoulli bounds as
open-ended SPRTs for i.i.d. observations from these exponential families. The
fact that such tests are also valid for testing various nonparametric classes
of distributions, as outlined in Section 3, illustrates how our framework
provides nonparametric generalizations of the SPRT. For example, if one wants
to test the mean of a bounded distribution, our framework suggests that one
apply an SPRT for Bernoulli or Poisson observations, for example. It has long
been known that the normal SPRT bound can be applied to sequential problems
involving any i.i.d. sequence of sub-Gaussian observations (Darling and
Robbins, 1967; Robbins, 1970). Our work expands the breadth of nonparametric
sequential problems amenable to such methods and deepens the connection
between exponential concentration inequalities and sequential testing
procedures.

##  5 Discussion and extensions

This section is divided into three parts. We first discuss the sharpness of
the derived bounds. Then, building further on the geometric intuition of the
paper, we point out an interesting geometric relationship between fixed-sample
exponential bounds and our uniform bounds. We end by discussing directions for
future work.

###  5.1 When is Theorem 1 sharp?

In the discrete-time, sub-Gaussian case $\psi=\psi_{N}$ and $l_{0}=1$, Theorem
1(a) is sharp: for any $a,b>0$,

$\displaystyle\sup_{(S_{t},V_{t})\in\mathbb{S}^{1}_{\psi_{N}}}\mathbb{P}\left(\left.\exists
t\in\mathbb{N}:S_{t}\geq a+bV_{t}\,\right|\,\mathcal{F}_{0}\right)=e^{-2ab}.$
(5.1)

In fact, this can be achieved by rescaling any sum of i.i.d. observations with
finite variance, which we prove in Section 6.9 as a corollary of Theorem 2 of
Robbins and Siegmund (1970):

######  Corollary 13.

Suppose $(X_{t})_{t\in\mathbb{N}}$ are i.i.d. mean zero with variance
$\sigma^{2}<\infty$. Let $S_{t}=\sum_{i=1}^{t}X_{i}$. Let
$S^{(m)}_{t}\coloneqq S_{t}/\sqrt{m}$ and $V^{(m)}_{t}\coloneqq
t\sigma^{2}/m$. Then for any $a,b>0$,

$\displaystyle\lim_{m\to\infty}\mathbb{P}\left(\exists
t\in\mathbb{N}:S^{(m)}_{t}\geq a+bV^{(m)}_{t}\right)=e^{-2ab}.$ (5.2)

The following more general sandwich relation, which we prove in Section 6.10,
quantifies the looseness in Theorem 1(a) and gives a sufficient condition for
the probability bound to be exact. This condition involves the “overshoot” of
the process $S_{t}$ over the line $a+bV_{t}$, a quantity which has been
studied extensively in the context of sequential testing (Siegmund, 1985). The
upper bound in equation (5.3) below is a restatement of Theorem 1(a); only the
lower bound is new.

######  Proposition 3.

Consider real-valued processes $(S_{t})$, $(V_{t})$ and a CGF-like function
$\psi$. Fix $a>0,b\in(0,\bar{b})$ and suppose

  1. 1.

$M_{t}\coloneqq\exp\left\\{D(b)S_{t}-\psi(D(b))V_{t}\right\\}$ is a martingale
with $M_{0}\equiv 1$ (rather than just upper bounded by a supermartingale, as
Definition 1 requires),

  2. 2.

$S_{t}-bV_{t}\to-\infty$ as $t\uparrow\infty$ a.s., and

  3. 3.

For some $\epsilon\geq 0$, $S_{\tau}\leq a+bV_{\tau}+\epsilon$ a.s. on
$\\{\tau<\infty\\}$, where $\tau\coloneqq\inf\\{t\in\mathcal{T}:S_{t}\geq
a+bV_{t}\\}$.

Then we have

$\displaystyle e^{-\epsilon D(b)}\leq\frac{\mathbb{P}\left(\exists
t\in\mathcal{T}:S_{t}\geq a+bV_{t}\right)}{\exp\left\\{-aD(b)\right\\}}\leq
1.$ (5.3)

In particular, if the conditions of Proposition 3 hold with $\epsilon=0$, then
the probability bounds in Theorem 1 parts (a), (b) and (c) hold with equality.
In the continuous-time case with $(S_{t})$ a continuous martingale, these
conditions often hold with $\psi=\psi_{N}$ and $V_{t}=[S]_{t}$. We give
details for the following result in Section 6.11; see Protter (2005, Theorem
III.44) for more on Kazamaki’s criterion:

######  Corollary 14.

Suppose $(S_{t})_{t\in(0,\infty)}$ is a continuous martingale with $S_{0}=0$
and $[S]_{t}\uparrow\infty$ a.s. satisfying Kazamaki’s criterion:
$\sup_{T}\mathbb{E}e^{S_{T}/2}<\infty$, where the supremum is taken over all
bounded stopping times $T$. Then $\mathbb{P}(\exists t\in(0,\infty):S_{t}\geq
a+bV_{t})=e^{-2ab}$.

In the discrete-time case with i.i.d. observations bounded above by $\epsilon$
a.s. and having CGF $\psi$, the conditions of Proposition 3 hold, setting
$V_{t}=t$. Hence the probability bound in Theorem 1(a) can be made arbitrarily
close to exact by taking $b$ sufficiently small relative to $\epsilon$, and
similarly for parts (b) and (c). So Theorem 1 is sharp in the sense that for
any such process, the probability bound is arbitrarily close to exact for some
choice of $(a,b)$ or $(x,m)$. To see the connection with Corollary 13, rewrite
(5.2) to keep the processes $S_{t}$ and $V_{t}=t\sigma^{2}$ fixed and take
limits with respect to $a,b$:

$\displaystyle\lim_{m\to\infty}\mathbb{P}\left(\exists
t\in\mathbb{N}:S_{t}\geq a\sqrt{m}+\frac{b}{\sqrt{m}}\cdot
t\sigma^{2}\right)=e^{-2ab}.$ (5.4)

###  5.2 Geometric relationship between Theorem 1 and Cramér-Chernoff

Figure 6: Geometric illustration of Theorem 1(b) and its relation to fixed-
time Cramér-Chernoff bounds. Theorem 1(b) chooses the linear boundary which is
optimal for $V_{t}=m$, but other linear boundaries with the same crossing
probability are illustrated, each of which achieves the optimal fixed-time
bound at some other time $V_{t}=m_{\pm}$. Each uniform Chernoff bound is
tangent to the curve of fixed-time bounds, and indeed the curve of fixed-time
bounds may be defined as the pointwise infimum of such linear uniform bounds.

Whenever a process $(S_{t})$ is sub-$\psi$ with $V_{t}=t$, a fixed-time
Cramér-Chernoff upper bound of the form (4.2) holds: for any fixed
$t\in\mathbb{N}$, we have $\mathbb{P}(S_{t}\geq
x)\leq\exp\left\\{-t\psi^{\star}(x/t)\right\\}$. Let $f_{\alpha}(t)$ denote
the curve of such fixed-time bounds constructed for a fixed crossing
probability $\alpha$ at each time $t$:

$\displaystyle f_{\alpha}(t)\coloneqq
t{\psi^{\star}}^{-1}\left(\frac{\log\alpha^{-1}}{t}\right),$ (5.5)

where ${\psi^{\star}}^{-1}(\lambda)=\inf\\{u\geq
0:\psi^{\star}(u)>\lambda\\}$. For example, in the sub-Gaussian case
$\psi(\lambda)=\psi_{N}(\lambda)=\lambda^{2}/2$, we have the standard formula
$f_{\alpha}(t)=\sqrt{2t\log\alpha^{-1}}$.

######  Proposition 4.

Any line $a+bt$ which is tangent to $f_{\alpha}(t)$ satisfies
$\mathbb{P}(\exists t\in\mathcal{T}:S_{t}\geq a+bt)\leq\alpha$.

In words, the above proposition states that the set of linear boundaries from
Theorem 1 is exactly the set of tangent lines to $f_{\alpha}$, or conversely,
$f_{\alpha}$ is defined as the pointwise infimum of this set of linear
boundaries, as illustrated in Figure 6. We give the proof in Section 6.12.
This observation provides some intuition for the appearance of the Legendre-
Fenchel transform in the standard Cramér-Chernoff formula (4.2).

###  5.3 Future work

Characterizing families of sub-$\psi$ processes. Our Theorem 1 bounds the
maximal line-crossing probability over each family
$\mathbb{S}^{l_{0}}_{\psi}$, and Section 3 collects sufficient conditions for
membership is many such families. It would be interesting to better delineate
such families, for example by characterizing necessary conditions for
inclusion. When $\psi$ is CGF-like and $(V_{t})$ is predictable, it is
necessary for the increments $\Delta S_{t}$ to have finite conditional CGFs
a.s. When $S_{t}$ is a cumulative sum of i.i.d., real-valued random variables
and $V_{t}\propto t$, the existence of the CGF is sufficient as well (Fact
1(a)). When the increments are not i.i.d., however, existence of conditional
CGFs is no longer sufficient. When $(V_{t})$ is not predictable, as with self-
normalized bounds, it is no longer necessary for increments to have finite
CGFs (e.g., Example 5).

Determining optimal $l_{0}$ values. Smaller values of $l_{0}$ are preferable
since they lead to tighter bounds in Theorem 1. Most of the results in this
paper take either $l_{0}=1$ for scalar observations or $l_{0}=d$ for $d\times
d$ matrix observations. Taking $\lambda\downarrow 0$ in Definition 1 shows we
cannot have $l_{0}<1$. Furthermore, asymptotic results about maxima of
independent Gaussians show that $l_{0}=d$ is an asymptotic lower bound as
$d\uparrow\infty$ for operator-norm inequalities over any class that includes
matrices with independent Gaussians on the diagonal (Galambos, 1978; Boucheron
et al., 2013, Exercise 2.17). It would be useful to derive more results about
optimal values of $l_{0}$ in various settings.

Generalizing assumptions. Definition 1 can be further generalized, allowing it
to subsume more known inequalities and yield sharper results for certain
cases. However, the corresponding general theorem and specific results are
less user-friendly. We have chosen our Definition 1 and Theorem 1 to balance
generality and tractability, but in Appendix D we present one possible
generalization of our assumption and a corresponding general theorem and
specific bound.

Polynomial line-crossing inequalities. We have focused on exponential
inequalities, but polynomial concentration also plays an important role in the
literature. A theory of polynomial line-crossing analogous to that presented
here may begin with the Dubins-Savage inequality (see Appendix B) and its
$l_{p}$ extension in Khan (2009).

Banach spaces. The Banach space bounds in Section 4.4 give dimension-free
$l_{p}$ bounds for $2\leq p<\infty$, but do not give $l_{\infty}$ bounds. In
particular, this does not yield operator-norm bounds for infinite-dimensional
Hilbert-Schmidt operators, as in Minsker (2017). Extending Minsker’s
“effective rank” approach to the uniform bounds of this paper would be an
interesting future extension.

##  6 Proofs

###  6.1 Proof of Lemma 1

Define the stopping time $\tau\coloneqq\inf\\{t\in\mathcal{T}:L_{t}\geq a\\}$,
where $\inf\emptyset=\infty$. For any fixed $m\in\mathcal{T}$, Markov’s
inequality implies

$\displaystyle\mathbb{P}\left(\left.\tau\leq
m\,\right|\,\mathcal{F}_{0}\right)=\mathbb{P}\left(\left.L_{\tau\wedge m}\geq
a\,\right|\,\mathcal{F}_{0}\right)\leq\frac{\mathbb{E}\left(\left.L_{\tau\wedge
m}\,\right|\,\mathcal{F}_{0}\right)}{a}\leq\frac{L_{0}}{a},$ (6.1)

where we have used Doob’s optional stopping theorem for bounded stopping times
in the final step (e.g., Durrett, 2017, Exercise 4.4.2; or Protter, 2005,
Theorem I.17). Taking $m\to\infty$ and using the bounded convergence theorem
yields $\mathbb{P}\left(\left.\tau<\infty\,\right|\,\mathcal{F}_{0}\right)\leq
L_{0}/a$, which is the desired conclusion.

###  6.2 Proof of Proposition 1

Applying Taylor’s theorem to $\psi$ at the origin, we have
$\psi(\lambda)=\left[\frac{\psi^{\prime\prime}(0_{+})}{2}+h(\lambda)\right]\lambda^{2}$
where $h(\lambda)\to 0$ as $\lambda\downarrow 0$. Choose $\lambda_{0}>0$ small
enough so that $\psi(\lambda)\leq\psi^{\prime\prime}(0_{+})\lambda^{2}$ for
all $0\leq\lambda<\lambda_{0}$. Then, setting $a\coloneqq
2\psi^{\prime\prime}(0_{+})$, $c\coloneqq 1/\lambda_{0}$ and using that fact
that $\psi_{G,c}\geq\psi_{N}$ for $c\geq 0$, we have $\psi(\lambda)\leq
a\psi_{N}(\lambda)\leq a\psi_{G,c}(\lambda)$ for all $0\leq\lambda<1/c$. The
same argument holds with $\psi_{E}$ in place of $\psi_{G}$. ∎

###  6.3 Proof of Proposition 2

In each case, we show an inequality between two $\psi$ functions. The
conclusion then follows from the fact that is $\psi_{1}\leq\psi_{2}$, then
$\exp\left\\{\lambda