S_{t}-\psi_{2}(\lambda)V_{t}\right\\}\leq\exp\left\\{\lambda
S_{t}-\psi_{1}(\lambda)V_{t}\right\\}$, showing that the key condition of
Definition 1 continues to hold with $\psi_{2}$ in place of $\psi_{1}$.

Part (1): the proof of Theorem 1 in Hoeffding (1963) shows that, for all
$\mu\in(0,1)$ and all $t\in[0,1-\mu)$,

$(\mu+t)\log\left(\frac{\mu+t}{\mu}\right)+(1-\mu-t)\log\left(\frac{1-\mu-t}{1-\mu}\right)\\\
\geq
t^{2}\begin{cases}\frac{1}{1-2\mu}\log\left(\frac{1-\mu}{\mu}\right),&0<\mu<\frac{1}{2},\\\
\frac{1}{2\mu(1-\mu)},&\frac{1}{2}\leq\mu<1,\end{cases}$ (6.2)

with equality at $t=1-2\mu$. Substituting $\mu=g/(g+h)$ and $t=u/(g+h)$ for
$u\in[0,h)$, some algebra shows that the left-hand side is equal to
$gh\psi_{B}^{\star}(u/gh)$ and the right-hand side is equal to
$\psi_{N}^{\star}(u)/\varphi(g,h)$, so that, for all $g,h>0$ and $u\in[0,h)$,
$\psi_{B}^{\star}(u/gh)\geq\psi_{N}^{\star}(u)/[gh\varphi(g,h)]$, with
equality at $u=h-g$. The order-reversing and scaling properties of the
Legendre-Fenchel transform now imply
$\psi_{B}^{\star\star}(\lambda)\leq\psi_{N}^{\star\star}(\varphi(g,h)\lambda)/[gh\varphi(g,h)]$
for all $\lambda\geq 0$. Finally, since $\psi_{B}$ and $\psi_{N}$ are convex
and continuous, each is equal to its biconjugate $\psi^{\star\star}$ by the
Fenchel-Moreau theorem, so that
$\psi_{B}(\lambda)\leq\frac{\varphi(g,h)}{gh}\psi_{N}(\lambda)$.

Part (2): This follows directly from equation (4.15) in Hoeffding (1963)
which, in our notation, says that
$\psi_{B}(\lambda)\leq\frac{(g+h)^{2}}{4gh}\psi_{N}(\lambda)$ for all
$\lambda\in\mathbb{R}$.

Part (3): In our notation, Lemma 2.32 of Bercu et al. (2015) shows that
$(g\psi_{B,g,1})^{\star}(u)\geq(g\psi_{P,1-g})^{\star}(u)$ for all $u\in[0,1]$
and $g>0$. The order-reversing and scaling properties of the Legendre-Fenchel
transform imply
$\psi_{B,g,1}^{\star\star}(\lambda)\leq\psi_{P,1-g}^{\star\star}(\lambda)$ for
all $\lambda\geq 0$. Since $\psi_{B,g,1}$ and $\psi_{P,1-g}$ are convex and
continuous, each is equal to its biconjugate $\psi^{\star\star}$ by the
Fenchel-Moreau theorem, so that
$\psi_{B,g,1}(\lambda)\leq\psi_{P,1-g}(\lambda)$. The result now follows from
algebraic identities involving $\psi_{B}$ and $\psi_{P}$: for any $g,h>0$,

$\displaystyle\psi_{B,g,h}(\lambda)=\frac{1}{h^{2}}\psi_{B,g/h,1}(h\lambda)\leq\frac{1}{h^{2}}\psi_{P,(h-g)/h}(h\lambda)=\psi_{P,h-g}(\lambda).$
(6.3)

Part (4) is immediate from the definition $\psi_{P}=\psi_{N}$ when $c=0$.

Part (5): since $\psi_{P,c_{P}}^{\prime\prime}(\lambda)=e^{c_{P}\lambda}$ and
$\psi_{G,c_{G}}^{\prime\prime}(\lambda)=(1-c_{G}\lambda)^{-3}$,

$\displaystyle\frac{\psi_{P,c}^{\prime\prime}(\lambda)}{\psi_{G,c/3}^{\prime\prime}(\lambda)}=(1-c\lambda/3)^{3}e^{c\lambda}=f(1-c\lambda/3),\quad\text{where
}f(y)=y^{3}e^{3(1-y)}.$ (6.4)

We have $f(1)=1$ and $f^{\prime}(y)=3y^{2}e^{3(1-y)}(1-y)$, so that
$f^{\prime}(y)\leq 0$ for $y\geq 1$ and $f^{\prime}(y)\geq 0$ for $y\leq 1$.
Hence $f(y)\leq f(1)=1$ for all $y$, i.e.,
$\psi_{P,c}^{\prime\prime}(\lambda)\leq\psi_{G,c/3}^{\prime\prime}(\lambda)$
for all $\lambda$. Since $\psi_{P,c}(0)=\psi_{G,c/3}(0)=0$ and
$\psi_{P,c}^{\prime}(0)=\psi_{G,c/3}^{\prime}(0)=0$, we conclude
$\psi_{P,c}(\lambda)\leq\psi_{G,c/3}(\lambda)$ for all $\lambda$.

Parts (6,7,8): some algebra shows that

$\displaystyle\psi_{G,c_{G}}^{\prime}(\lambda)-\psi_{E,c_{E}}^{\prime}(\lambda)=\frac{\lambda^{2}[3c_{G}-2c_{E}+c_{G}(c_{E}-2c_{G})\lambda]}{2(1-c_{G}\lambda)^{2}(1-c_{E}\lambda)}.$
(6.5)

Since $\psi_{G,c_{G}}(0)=\psi_{E,c_{E}}(0)=0$, we have
$\psi_{G,c_{G}}(\lambda)\geq(\leq)\,\psi_{E,c_{E}}(\lambda)$ for all $\lambda$
if $\psi_{G,c_{G}}^{\prime}\geq(\leq)\,\psi_{E,c_{E}}^{\prime}$ for all
$\lambda$, and (6.5) shows the latter is true if and only if
$f(\lambda)\coloneqq 3c_{G}-2c_{E}+c_{G}(c_{E}-2c_{G})\lambda\geq(\leq)\,0$
for all $\lambda$. Note we need only check the domain
$0\leq\lambda<c_{E}^{-1}\wedge(2c_{G})^{-1}$ on which both functions are
defined.

  * •

For part (6), if $c_{E}=3c_{G}/2$, then $f(\lambda)=-c_{G}^{2}\lambda/2\leq
0$, so that $\psi_{G,c}\leq\psi_{E,3c/2}$ for $c\in\mathbb{R}$.

  * •

For part (7), if $c_{G}=c_{E}\geq 0$ then we have
$f(\lambda)=c(1-c\lambda)\geq 0$ for $0\leq\lambda<c^{-1}$, so that
$\psi_{E,c}\leq\psi_{G,c}$ for $c\geq 0$.

  * •

For part (8), if $c_{G}=c_{E}/2<0$, then $f(\lambda)=-c_{E}/2>0$, so that
$\psi_{E,c}\leq\psi_{G,c/2}$ for $c<0$.

Part (9): from $\psi_{P,2c}^{\prime}(\lambda)=\frac{e^{2c\lambda}-1}{2c}$ and
$\psi_{G,c}^{\prime}(\lambda)=\frac{\lambda(2-c\lambda)}{2(1-c\lambda)^{2}}$,
we have

$\displaystyle\psi_{P,2c}^{\prime}(\lambda)-\psi_{G,c}^{\prime}(\lambda)=\frac{1-f(1+\lvert
c\rvert\lambda)}{2\lvert c\rvert(1-c\lambda)^{2}},\quad\text{where
}f(y)=y^{2}e^{2(1-y)}.$ (6.6)

We have $f(1)=1$ and $f^{\prime}(y)=2ye^{2(1-y)}(1-y)\leq 0$ for all $y\geq
1$, so that $f(y)\leq 1$ for all $y\geq 1$. Hence
$\psi_{P,2c}^{\prime}(\lambda)\geq\psi_{G,c}^{\prime}(\lambda)$ for all
$\lambda\geq 0$. Together with $\psi_{P,2c}(0)=\psi_{G,c}(0)=0$, we conclude
$\psi_{P,2c}(\lambda)\geq\psi_{G,c}(\lambda)$ for all $\lambda\geq 0$.

Part (10) follows from the fact that $\psi_{P,c}\uparrow\psi_{N}$ as
$c\uparrow 0$.

Part (11): for any $g,h>0$, we have

$\displaystyle\psi_{B,g,h}^{\prime}(\lambda)=\frac{e^{h\lambda}-e^{-g\lambda}}{ge^{h\lambda}+he^{-g\lambda}},$
(6.7)

so $\lim_{h\downarrow
0}\psi_{B,g,h}^{\prime}(\lambda)=(1-e^{-g\lambda})/g=\psi_{P,-g}^{\prime}(\lambda)$.
Since $\psi_{B,g,h}(0)=\psi_{P,c}=0$ for all $g,h>0$ and all $c\in\mathbb{R}$,
we see that $\lim_{h\downarrow 0}\psi_{B,g,h}(\lambda)=\psi_{P,-g}(\lambda)$
for all $\lambda\geq 0$. Furthermore, differentiating (6.7) with respect to
$h$ reveals

$\displaystyle\frac{d}{dh}\psi_{B,g,h}^{\prime}(\lambda)=\frac{e^{(h-g)\lambda}(g+h)^{2}\psi_{P,-(g+h)}(\lambda)}{(ge^{h\lambda}+he^{-g\lambda})^{2}}\geq
0,$ (6.8)

which implies $\psi_{B,g,h}(\lambda)$ is nondecreasing with $h$ for all
$\lambda\geq 0$. We conclude
$\psi_{B,g,h}(\lambda)\downarrow\psi_{P,-g}(\lambda)$ as $h\downarrow 0$,
hence $\psi_{P,c}\leq\psi_{B,-c,h}$ for all $h>0$ whenever $c<0$.

To see that no other implications are possible, observe that, as
$\lambda\to\infty$, $\psi_{B}(\lambda)=\mathcal{O}(\lambda)$,
$\psi_{N}(\lambda)=\mathcal{O}(\lambda^{2})$, and when $c>0$,
$\psi_{P}(\lambda)=\mathcal{O}(e^{c\lambda})$, while $\psi_{G}(\lambda)$ and
$\psi_{E}(\lambda)$ diverge at a finite value of $\lambda$. So we cannot use
$a\psi_{B}$ to upper bound any of the other $\psi$ functions for any constant
$a$. Likewise, we cannot use $a\psi_{N}$ to upper bound $\psi_{P}$, $\psi_{G}$
or $\psi_{E}$, and we cannot use $a\psi_{P}$ to upper bound $\psi_{G}$ or
$\psi_{E}$.

Now if $S_{t}$ is a sum of i.i.d. $\mathcal{N}(0,1)$ random variables, then
$(S_{t})$ is sub-Gaussian with variance process $V_{t}=t$, and the exponential
process $\exp\left\\{\lambda S_{t}-\lambda^{2}t/2\right\\}$ is a martingale.
Under any scaling of $V_{t}$ by a constant $a>0$, $(S_{t})$ cannot be sub-
Bernoulli, because $\mathbb{E}\exp\left\\{\lambda\Delta
S_{t}-a\psi_{B}(\lambda)\right\\}=\exp\left\\{\lambda^{2}/2-a\psi_{B}(\lambda)\right\\}>1$
for sufficiently large $\lambda$, so the exponential process
$\exp\left\\{\lambda S_{t}-\psi_{B}(\lambda)t\right\\}$ will be expectation-
increasing. Analogous arguments shows that other reverse implications are not
possible.

To see that the above constants are the best possible when we allow only
scaling of $V_{t}$ by a constant, consider the third-order expansions of each
$\psi$ function about $\lambda=0$:

$\displaystyle\psi_{B}(\lambda)$
$\displaystyle=\left[\frac{\lambda^{2}}{2}+\frac{(h-g)\lambda^{3}}{6}\right]+o(\lambda^{3})$
(6.9) $\displaystyle\psi_{N}(\lambda)$ $\displaystyle=\frac{\lambda^{2}}{2}$
(6.10) $\displaystyle\psi_{P}(\lambda)$
$\displaystyle=\frac{\lambda^{2}}{2}+\frac{c\lambda^{3}}{6}+o(\lambda^{3})$
(6.11) $\displaystyle\psi_{E}(\lambda)$
$\displaystyle=\frac{\lambda^{2}}{2}+\frac{c\lambda^{3}}{3}+o(\lambda^{3})$
(6.12) $\displaystyle\psi_{G}(\lambda)$
$\displaystyle=\frac{\lambda^{2}}{2}+\frac{c\lambda^{3}}{2}+o(\lambda^{3}).$
(6.13)

It is clear from these expansions that parts (3), (4), (5), (6), and (11) have
the best possible constants. Part (7) is unimprovable because $\psi_{E}$
diverges at $\lambda=1/c$, and using any scale parameter in $\psi_{G}$ smaller
than $c$ would make $\psi_{G}$ finite at $\lambda=1/c$. For part (8), recall
that when $c<0$, $\bar{b}=\lvert c\rvert^{-1}$ for $\psi_{E}$, while
$\bar{b}=\lvert 2c\rvert^{-1}$ for $\psi_{G}$. Hence, if $c^{\prime}<c/2<0$,
then $\lim_{\lambda\to\infty}\psi_{G,c^{\prime}}^{\prime}(\lambda)=\lvert
2c^{\prime}\rvert^{-1}<\lvert
c\rvert^{-1}=\lim_{\lambda\to\infty}\psi_{E,c}^{\prime}(\lambda)$, so that
$\psi_{G,c^{\prime}}(\lambda)$ must be smaller than $\psi_{E,c}(\lambda)$ for
sufficiently large $\lambda$. Part (9) is unimprovable by an analogous
argument.

For part (1), when $g\geq h$, we know that the constant of one in front of
$\psi_{N}(\lambda)$ is the best possible from the expansions above. When
$g<h$, some algebra shows that the inequality
$\psi_{B,g,h}(\lambda)\leq\frac{\varphi(g,h)}{gh}\psi_{N}(\lambda)$ holds with
equality at $\lambda=(h-g)/\varphi(g,h)$, so the constant cannot be improved.
For part (2), it is easy to see that
$\varphi(g,h)=\left(\frac{g+h}{2}\right)^{2}=g^{2}$ when $g=h$, so the
constant $\frac{(g+h)}{4gh}$ is the best possible of the form $k/gh$ where $k$
is a function of $g+h$ alone. ∎

A brief remark on the rationale behind part (2). In the “Bernoulli I” (Fact
1(b)) and “Bernoulli II” (Lemma 3(a)) conditions, $V_{t}=ght$, so applying
Proposition 2, part (2) leads to $V_{t}=\left(\frac{g+h}{2}\right)^{2}t$, a
function of the total range $g+h$ alone. This is useful in the common case
that observations are known to be bounded in a range $[a,b]$, and an
inequality is desired which depends only on the range $b-a$ and not on the
location of the means within $[a,b]$.

###  6.4 An intermediate condition for sub-$\psi$ processes

In discrete time, the following result capture a useful general condition on a
matrix-valued process $(Y_{t})$ that is sufficient to show that the maximum-
eigenvalue process $S_{t}=\gamma_{\max}(Y_{t})$ is sub-$\psi$.

######  Lemma 4.

Let $\psi$ be a real-valued function with domain $[0,\lambda_{\max})$. Let
$(Y_{t})_{t\in\mathbb{N}}$ be an adapted, $\mathcal{H}^{d}$-valued process.
Let $(W_{t})_{t\in\mathbb{N}}$ be predictable, $\mathcal{H}^{d}$-valued, and
nondecreasing in the semidefinite order, with $W_{0}$ = 0. Let
$(U_{t})_{t\in\mathbb{N}}$ be defined by $U_{0}=0$ and $\Delta
U_{t}=u_{t}(\Delta Y_{t})$ for some $u_{t}:\mathbb{R}\to\mathbb{R}_{\geq 0}$,
for each $t$. If, for all $t\in\mathbb{N}$ and $\lambda\in[0,\lambda_{\max})$,
we have

$\displaystyle\log\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
Y_{t}-\psi(\lambda)\Delta U_{t}\right\\}\preceq\psi(\lambda)\Delta W_{t},$
(6.14)

then ${S_{t}=\gamma_{\max}(Y_{t})}$ is $d$-sub-$\psi$ with variance process
$V_{t}=\gamma_{\max}(U_{t}+W_{t})$.

For a familiar example, suppose $d=1$ and $(Y_{t})$ has independent
increments. Let $W_{t}=t$, $U_{t}\equiv 0$ and $\psi(\lambda)=\lambda^{2}/2$.
Then (6.14) reduces to the usual definition of a 1-sub-Gaussian random
variable (Boucheron et al., 2013). For a self-normalized example, let $(\Delta
Y_{t})$ be i.i.d. from any distribution symmetric about zero. Then, again
letting $\psi(\lambda)=\lambda^{2}/2$, an argument due to de la Peña (1999)
shows that (6.14) holds with $W_{t}\equiv 0$ and $U_{t}=\sum_{i=1}^{t}\Delta
Y_{i}^{2}$. See Lemma 3(d) for a general statement of this condition.

The value $l_{0}=d$, the ambient dimension, leads to a pre-factor of $d$ in
all of our operator-norm matrix bounds. In cases when
$\sup_{t\in\mathcal{T}}\operatorname{rank}(U_{t}+W_{t})\leq r<d$ a.s., the
pre-factor $d$ in our bounds may be replaced by $r$ via an argument originally
due to Oliveira (2010b). See Appendix A for details.

###### Proof of Lemma 4.

The key result here is Lieb’s concavity theorem:

######  Fact 3 (Lieb, 1973; Tropp, 2012).

For any fixed $H\in\mathcal{H}^{d}$, the function
$A\mapsto\operatorname{tr}\exp\left\\{H+\log(A)\right\\}$ is concave on the
positive-definite cone.

Fixing ${\lambda\in[0,\lambda_{\max})}$, Lieb’s theorem and Jensen’s
inequality together imply

$\mathbb{E}_{t-1}\operatorname{tr}\exp\left\\{\lambda
Y_{t}-\psi(\lambda)\cdot(U_{t}+W_{t})\right\\}\\\
\leq\operatorname{tr}\exp\left\\{\lambda
Y_{t-1}-\psi(\lambda)\cdot(U_{t-1}+W_{t})+\log\mathbb{E}_{t-1}e^{\lambda\Delta
Y_{t}-\psi(\lambda)\cdot\Delta U_{t}}\right\\}.$ (6.15)

Now we apply inequality (6.14) to the expectation and use the monotonicity of
the trace exponential to obtain

$\displaystyle\mathbb{E}_{t-1}\operatorname{tr}\exp\left\\{\lambda
Y_{t}-\psi(\lambda)\cdot(U_{t}+W_{t})\right\\}$
$\displaystyle\leq\operatorname{tr}\exp\left\\{\lambda
Y_{t-1}-\psi(\lambda)\cdot(U_{t-1}+W_{t-1})\right\\}.$ (6.16)

This shows that the process
$L_{t}\coloneqq\operatorname{tr}\exp\left\\{\lambda
Y_{t}-\psi(\lambda)\cdot(U_{t}+W_{t})\right\\}$ is a supermartingale, with
$L_{0}=d$. Next we show that the key condition of Definition 1 holds,
$L_{t}\geq\exp\left\\{\lambda\gamma_{\max}(Y_{t})-\psi(\lambda)\gamma_{\max}(U_{t}+W_{t})\right\\}$
a.s. for all $t$. We repeat a short argument from Tropp (2012). First, by the
monotonicity of the trace exponential,

$\displaystyle\operatorname{tr}\exp\left\\{\lambda
Y_{t}-\psi(\lambda)\cdot(U_{t}+W_{t})\right\\}$ (6.17)
$\displaystyle\qquad\geq\operatorname{tr}\exp\left\\{\lambda
Y_{t}-\psi(\lambda)\gamma_{\max}(U_{t}+W_{t})I_{d}\right\\}$ (6.18)
$\displaystyle\qquad\geq\gamma_{\max}\left(\exp\left\\{\lambda
Y_{t}-\psi(\lambda)\gamma_{\max}(U_{t}+W_{t})I_{d}\right\\}\right)\eqqcolon
B.$ (6.19)

using the fact that the trace of a positive semidefinite matrix is at least as
large as its maximum eigenvalue. Then the spectral mapping property gives

$\displaystyle B$ $\displaystyle=\exp\left\\{\gamma_{\max}\left(\lambda
Y_{t}-\psi(\lambda)\gamma_{\max}(U_{t}+W_{t})I_{d}\right)\right\\}.$ (6.20)

Finally, we use the fact that $\gamma_{\max}(A-cI_{d})=\gamma_{\max}(A)-c$ for
any $A\in\mathcal{H}^{d}$ and $c\in\mathbb{R}$ to see that
${B=\exp\left\\{\lambda\gamma_{\max}(Y_{t})-\psi(\lambda)\gamma_{\max}(U_{t}+W_{t})\right\\}}$,
completing the argument. ∎

###  6.5 Proof of Lemma 3

We rely on the following transfer rule for the semidefinite ordering.

######  Fact 4 (Tropp, 2012, eq. 2.2).

If $f(a)\leq g(a)$ for all $a\in S$, then $f(A)\preceq g(A)$ when the
eigenvalues of $A$ lie in $S$.

We make frequent use of the martingale property $\mathbb{E}_{t-1}\Delta
Y_{t}=0$, and prove in most cases that

$\displaystyle\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
Y_{t}-\psi(\lambda)\Delta U_{t}\right\\}\preceq\exp\left\\{\psi(\lambda)\Delta
W_{t}\right\\}$ (6.21)

for some $(U_{t})$ and $(W_{t})$, then invoke Lemma 4. This a stronger
condition than property (6.14); the latter is implied by taking logarithms on
both sides, recalling the monotonicity of the matrix logarithm.

Part (a): we adapt the argument of Bennett (1962, p. 42). Fix $\lambda\geq 0$
and choose real numbers $u,v,w$ so that $e^{\lambda x}\leq ux^{2}+vx+w$ for
all $x\leq h$, with equality at $x=h$ and $x=-g$. Using the assumption $\Delta
Y_{t}\preceq hI_{d}$, the transfer rule implies

$\displaystyle\mathbb{E}_{t-1}e^{\lambda\Delta Y_{t}}\preceq
u\mathbb{E}_{t-1}\Delta Y_{t}^{2}+v\mathbb{E}_{t-1}\Delta
Y_{t}+wI_{d}\preceq(ugh+w)I_{d},$ (6.22)

where the second inequality uses the assumption $\mathbb{E}_{t-1}\Delta
Y_{t}^{2}\preceq ghI_{d}$ and the martingale property. Now consider the random
matrix

$\displaystyle Z=\begin{cases}-gI_{d},&\text{with probability
}\frac{h}{h+g},\\\ hI_{d},&\text{with probability }\frac{g}{h+g}.\end{cases}$
(6.23)

Evidently $\mathbb{E}Z=0$ and $\mathbb{E}Z^{2}=ghI_{d}$, so $Z$ also satisfies
the aforementioned assumptions. Note that for any function
$f:\mathbb{R}\to\mathbb{R}$,

$\displaystyle\mathbb{E}f(Z)=\left[\frac{h}{h+g}\cdot f(-g)+\frac{g}{h+g}\cdot
f(h)\right]I_{d}.$ (6.24)

By our choice of $u,v,w$, we see that $\mathbb{E}e^{\lambda
Z}=\mathbb{E}(uZ^{2}+vZ+wI_{d})=(ugh+w)I_{d}$, so by direct calculation,

$\displaystyle(ugh+w)I_{d}=\mathbb{E}e^{\lambda Z}=\left[\frac{h}{h+g}\cdot
e^{-\lambda g}+\frac{g}{h+g}\cdot e^{\lambda
h}\right]I_{d}=e^{gh\psi_{B}(\lambda)}I_{d}.$ (6.25)

Combining (6.25) with (6.22) shows that (6.21) holds with $U_{t}\equiv 0$ and
$W_{t}=ghtI_{d}$, as desired.

Part (b): As in Lemma 1 of Hoeffding (1963), we use the fact that $e^{\lambda
x}\leq\frac{g+x}{g+h}e^{h\lambda}+\frac{h-x}{g+h}e^{-g\lambda}$ for all
$x\in[-g,h]$, along with the transfer rule, to conclude that, for each $t$,

$\displaystyle\mathbb{E}_{t-1}e^{\lambda\Delta
Y_{t}}\preceq\left(\frac{G_{t}}{G_{t}+G_{t}}e^{H_{t}\lambda}+\frac{H_{t}}{G_{t}+H_{t}}e^{-G_{t}\lambda}\right)I_{d}=\exp\left\\{G_{t}H_{t}\psi_{B,G_{t},H_{t}}(\lambda)\right\\}I_{d}.$
(6.26)

Now the proof of Proposition 2 part (1) shows that
$\psi_{B,g,h}(\lambda)\leq\varphi(g,h)\psi_{N}(\lambda)/gh$, so we have

$\displaystyle\mathbb{E}_{t-1}e^{\lambda\Delta
Y_{t}}\preceq\exp\left\\{\psi_{N}(\lambda)\varphi(G_{t},H_{t})I_{d}\right\\},$
(6.27)

which shows that (6.21) holds with $U_{t}\equiv 0$ and $\Delta
W_{t}=\varphi(G_{t},H_{t})I_{d}$, as desired.

Part (c): the argument is identical to that for part (a), except for the use
of $\psi_{B,g,h}(\lambda)\leq\frac{(g+h)^{2}}{4gh}\psi_{N}(\lambda)$ from the
proof of Proposition 2 part (2).

Part (d): From the standard inequality $\cosh x\leq e^{x^{2}/2}$ we see that
$f(x)\coloneqq e^{-x^{2}/2}\cosh x\leq 1$ for all $x$. Introducing an
independent Rademacher random variable $\varepsilon$, we have for any $t$,

$\displaystyle\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
Y_{t}-\frac{\lambda^{2}\Delta Y_{t}^{2}}{2}\right\\}$
$\displaystyle=\mathbb{E}_{t-1}\exp\left\\{\lambda\varepsilon\Delta
Y_{t}-\frac{\lambda^{2}\Delta Y_{t}^{2}}{2}\right\\}$ (6.28)
$\displaystyle=\mathbb{E}_{t-1}\mathbb{E}\left[\left.\exp\left\\{\lambda\varepsilon\Delta
Y_{t}-\frac{\lambda^{2}\Delta
Y_{t}^{2}}{2}\right\\}\,\right|\,\mathcal{F}_{t-1},\Delta Y_{t}\right]$ (6.29)
$\displaystyle=\mathbb{E}_{t-1}f(\lambda\Delta Y_{t})$ (6.30)
$\displaystyle\preceq I_{d},$ (6.31)

applying the transfer rule in the last step. This shows that (6.21) holds with
$U_{t}=[Y]_{t}$ and $W_{t}\equiv 0$.

Part (e): Lemma 4.1 of Fan et al. (2015) shows that

$\displaystyle\exp\left\\{\lambda
x-[\log(1-\lambda)^{-1}-\lambda]x^{2}\right\\}\leq 1+\lambda x,\text{ for all
}x\geq-1\text{ and }0\leq\lambda<1.$ (6.32)

Applying the transfer rule and taking expectations, we have for any $t$,

$\displaystyle\mathbb{E}_{t-1}\exp\left\\{\lambda\cdot\frac{\Delta
Y_{t}}{c}-[\log(1-\lambda)^{-1}-\lambda]\cdot\frac{\Delta
Y_{t}^{2}}{c^{2}}\right\\}\preceq I_{d}.$ (6.33)

Replace $\lambda$ with $c\lambda$ and identify $\psi_{E}$ to complete the
argument that (6.21) holds with $U_{t}=[Y]_{t}$ and $W_{t}\equiv 0$.

Part (f): Proposition 12 of Delyon (2009) shows that $e^{x-x^{2}/6}\leq
1+x+x^{2}/3$ for all $x\in\mathbb{R}$. This implies, by the transfer rule,

$\displaystyle\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
Y_{t}-\frac{\lambda^{2}}{6}\Delta Y_{t}^{2}\right\\}$ $\displaystyle\preceq
I_{d}+\frac{\lambda^{2}}{3}\mathbb{E}_{t-1}\Delta Y_{t}^{2}$ (6.34)
$\displaystyle\preceq\exp\left\\{\frac{\lambda^{2}}{3}\mathbb{E}_{t-1}\Delta
Y_{t}^{2}\right\\}.$ (6.35)

This shows that (6.21) holds with $U_{t}=[Y]_{t}/3$ and $W_{t}=2\left\langle
Y\right\rangle_{t}/3$.

Part (g): Proposition 12 of Delyon (2009), together with the fact that
$e^{-x}+x-1\leq x^{2}/2$ for $x\geq 0$, shows that $e^{x-x_{+}^{2}/2}\leq
1+x+x_{-}^{2}/2$. Again the transfer rule implies

$\displaystyle\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
Y_{t}-\frac{\lambda^{2}}{2}(\Delta Y_{t})_{+}^{2}\right\\}$
$\displaystyle\preceq I_{d}+\frac{\lambda^{2}}{2}\mathbb{E}_{t-1}(\Delta
Y_{t})_{-}^{2}$ (6.36)
$\displaystyle\preceq\exp\left\\{\frac{\lambda^{2}}{2}\mathbb{E}_{t-1}(\Delta
Y_{t})_{-}^{2}\right\\}.$ (6.37)

This shows that (6.21) holds with $U_{t}=[Y_{+}]_{t}/2$ and
$W_{t}=\left\langle Y_{-}\right\rangle_{t}/2$.

Part (h): we appeal to part (d) to see that $S_{t}$ is $d$-sub-Gaussian with
variance process
$V_{t}=\gamma_{\max}(\frac{1}{3}[Y]_{t}+\frac{2}{3}\left\langle
Y\right\rangle_{t})$. Now the condition $\Delta Y_{t}^{2}\preceq A_{t}^{2}$
ensures that $\frac{1}{3}[Y]_{t}+\frac{2}{3}\left\langle
Y\right\rangle_{t}\preceq\sum_{i=1}^{t}A_{i}^{2}$, hence
$V_{t}\leq\gamma_{\max}(\sum_{i=1}^{t}A_{i}^{2})$. Substituting this larger
variance process only makes the exponential process in Definition 1 smaller,
so the assumption remains satisfied.

Part (i): the proof of Corollary 2.2 in Fan et al. (2015) is based on the
inequality $e^{x-x^{2}/2}\leq 1+x+x_{-}^{3}/3$ for all $x\in\mathbb{R}$. The
transfer rule implies

$\displaystyle\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
Y_{t}-\frac{\lambda^{2}}{2}\Delta Y_{t}^{2}\right\\}\preceq
I_{d}+\frac{\lambda^{3}}{3}\mathbb{E}_{t-1}(\Delta
Y_{t})_{-}^{3}\preceq\exp\left\\{\frac{\lambda^{3}}{3}\mathbb{E}_{t-1}(\Delta
Y_{t})_{-}^{3}\right\\}.$ (6.38)

Setting $c=1/6$ in $\psi_{G}$, we have for all $x\in[0,6)$ the obvious
inequality $x^{2}/2\leq\psi_{G}(x)$ and we claim $x^{3}/3\leq\psi_{G}(x)$ as
well; indeed,

$\displaystyle\frac{x^{3}/3}{x^{2}/2(1-x/6)}=\frac{x(6-x)}{9},$ (6.39)

which reaches a maximum value of one at $x=3$. The transfer rule now implies

$\displaystyle\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
Y_{t}-\psi_{G}(\lambda)\Delta Y_{t}^{2}\right\\}$
$\displaystyle\preceq\mathbb{E}_{t-1}\exp\left\\{\lambda\Delta
Y_{t}-\frac{\lambda^{2}}{2}\Delta Y_{t}^{2}\right\\}$ (6.40)
$\displaystyle\preceq\exp\left\\{\frac{\lambda^{3}}{3}\mathbb{E}_{t-1}(\Delta
Y_{t})_{-}^{3}\right\\}$ (6.41)
$\displaystyle\preceq\exp\left\\{\psi_{G}(\lambda)\mathbb{E}_{t-1}(\Delta
Y_{t})_{-}^{3}\right\\},$ (6.42)

which shows that (6.21) holds with $U_{t}=[Y]_{t}$ and
$V_{t}=\sum_{i=1}^{t}\mathbb{E}_{i-1}\lvert\Delta Y_{i}\rvert^{3}$.

###  6.6 Proof of Corollary 2

Define the $\mathcal{H}^{d_{1}+d_{2}}$-valued process $(Y_{t})$ using the
dilation of $B_{t}$:

$\displaystyle\Delta Y_{t}\coloneqq\epsilon_{t}\begin{pmatrix}0&B_{t}\\\
B_{t}^{\star}&0\end{pmatrix}.$ (6.43)

Since the dilation operation is linear and preserves spectral information, we
have
$S_{t}=\gamma_{\max}(Y_{t})=\lVert\sum_{i=1}^{t}\epsilon_{i}B_{i}\rVert_{\text{op}}$
(Tropp, 2012, Eq. 2.12). Furthermore, since each $B_{i}$ is fixed and
$\epsilon_{i}$ is 1-sub-Gaussian (in the usual sense for scalar random
variables), $(Y_{t})$ satisfies the conditions of Lemma 4 with
$\psi=\psi_{N}$, $U_{t}\equiv 0$, and

$\displaystyle W_{t}=\sum_{i=1}^{t}\begin{pmatrix}B_{i}B_{i}^{\star}&0\\\
0&B_{i}^{\star}B_{i}\end{pmatrix},$ (6.44)

by Tropp (2012, Lemma 4.3). Hence $(S_{t})$ is $(d_{1}+d_{2})$-sub-Gaussian
with variance process

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

The result now follows from Theorem 1(b).

###  6.7 Proof of Corollary 3

First, observe $\mathfrak{s}^{-1}(u)=\psi^{\prime}(D(u))$ for any
$u\in(0,\bar{b})$. Indeed, from the definition of $\mathfrak{s}(\cdot)$ and
Lemma 2(v) we see that if $u=\mathfrak{s}(v)$ then
$D(u)={\psi^{\star}}^{\prime}(v)={\psi^{\prime}}^{-1}(v)$, so that
$v=\psi^{\prime}(D(u))$. This identity will be used below.

Now let $h(b)\coloneqq m\psi^{\star}(b)+(x-bm){\psi^{\star}}^{\prime}(b)$. We
will show the following:

  1. (I)

If $m=0$ or $b\leq\mathfrak{s}\left(\frac{x}{m}\right)$, then
$h(b)\leq(x-(b\wedge\bar{b})m)D(b)$.

  2. (II)

If $m>0$ then $h(b)\leq
m\psi^{\star}\left(\frac{x}{m}\right)=h\left(\frac{x}{m}\right)$.

Together with Theorem 1(d) these prove that (4.10) holds, and (4.11) follows
upon setting $x=bm$.

First suppose $m=0$, so it suffices to show ${\psi^{\star}}^{\prime}(b)\leq
D(b)$ to prove (I) in this case. But Lemma 2(vi) implies
$u\leq\mathfrak{s}^{-1}(u)$ for any $u\in[0,\bar{b})$, and together with the
convexity of $\psi^{\star}$, we have
${\psi^{\star}}^{\prime}(b)\leq{\psi^{\star}}^{\prime}(\mathfrak{s}^{-1}(b))$.
Then the identities $\mathfrak{s}^{-1}(u)=\psi^{\prime}(D(u))$ and
${\psi^{\star}}^{\prime}={\psi^{\prime}}^{-1}$ imply
${\psi^{\star}}^{\prime}(\mathfrak{s}^{-1}(b))=D(b)$.

Now suppose $m>0$. It is easy to see that
$h^{\prime}(b)=(x-bm){\psi^{\star}}^{\prime\prime}(b)$. The convexity of
$\psi^{\star}$ now implies $h$ is nondecreasing for $b\leq x/m$ and
nonincreasing for $b\geq x/m$. Hence $h(b)$ is maximized at $b=x/m$, which
proves (II). To prove (I) in this case, we claim that
$h(\mathfrak{s}^{-1}(b))=(x-bm)D(b)$. Then the condition
$b\leq\mathfrak{s}(x/m)$ and Lemma 2(vi) imply $b<\mathfrak{s}^{-1}(b)\leq
x/m$, so that $h(b)\leq h(\mathfrak{s}^{-1}(b))$ since $h$ is nondecreasing on
this region, which is (I).

To prove the claim, substitute the identity
$\mathfrak{s}^{-1}(u)=\psi^{\prime}(D(u))$ into the definition of $h(\cdot)$,
yielding

$\displaystyle h(\mathfrak{s}^{-1}(b))=h(\psi^{\prime}(D(b)))$
$\displaystyle=m\psi^{\star}(\psi^{\prime}(D(b)))+[x-m\psi^{\prime}(D(b))]D(b).$
(6.46)

Now use the identity
$\psi^{\star}(u)=u{\psi^{\star}}^{\prime}(u)-\psi({\psi^{\star}}^{\prime}(u))$
to obtain

$\displaystyle h(\mathfrak{s}^{-1}(b))$ $\displaystyle=xD(b)-m\psi(D(b))$
(6.47) $\displaystyle=xD(b)-mbD(b),$ (6.48)

where the final equality uses Lemma 2(v), proving the claim.

The second statement (4.11) follows directly from Theorem 1(d) with $x=mb$.
When $b\leq\bar{b}$, Lemma 2(vi) implies $s(x/m)\leq x/m=b$, so the second
case in (2.10) applies. When $b>\bar{b}$, we have $x>m\bar{b}$, so the first
case in (2.10) applies. Noting that $D(b)=\infty=\psi^{\star}(b)$ in this case
using Lemma 2(i), we see that (4.11) remains valid. ∎

###  6.8 Proof of Corollary 10

We invoke arguments from Pinelis (1994) and Pinelis (1992) to show that
Definition 1 is satisfied.

For part (a), the proofs of Theorem 3 in Pinelis (1994) and Theorem 3 in
Pinelis (1992) show that, for each $t\in\mathbb{N}$,

$\displaystyle\mathbb{E}_{t-1}\cosh\big{(}\lambda\Psi(Y_{t})\big{)}$
$\displaystyle\leq
e^{\lambda^{2}D_{\star}^{2}c_{t}^{2}/2}\cosh\big{(}\lambda\Psi(Y_{t-1})\big{)}.$
(6.49)

Hence
$L_{t}\coloneqq\cosh\big{(}\lambda\Psi(Y_{t})\big{)}e^{-\lambda^{2}D_{\star}^{2}\sum_{i=1}^{t}c_{i}^{2}/2}$
is a supermartingale, and the inequality $\cosh x>e^{x}/2$ implies that
Definition 1 is satisfied for $S_{t}=\Psi(Y_{t})$,
$V_{t}=D_{\star}^{2}\sum_{i=1}^{t}c_{i}^{2}$ and $\psi=\psi_{N}$ with
$\lambda_{\max}=\infty$ and $l_{0}=2$. The conclusion (4.28) follows from a
slight reparametrization of $V_{t}$ to make $D_{\star}^{2}$ explicit in the
bound.

For part (b), the proof of Theorem 3 in Pinelis (1994) shows that

$\displaystyle\mathbb{E}_{t-1}\cosh\big{(}\lambda\Psi(Y_{t})\big{)}$
$\displaystyle\leq\exp\left\\{D_{\star}^{2}\mathbb{E}_{t-1}\left[e^{\lambda\lVert\Delta
Y_{t}\rVert}-\lambda\lVert\Delta
Y_{t}\rVert-1\right]\right\\}\cosh\big{(}\lambda\Psi(Y_{t-1})\big{)}$ (6.50)
$\displaystyle\leq\exp\left\\{D_{\star}^{2}\left(\frac{e^{c\lambda}-c\lambda-1}{c^{2}}\right)\mathbb{E}_{t-1}\lVert\Delta
Y_{t}\rVert^{2}\right\\}\cosh\big{(}\lambda\Psi(Y_{t-1})\big{)}.$ (6.51)

using the fact that $(e^{c\lambda}-c\lambda-1)/c^{2}$ is nondecreasing. Hence
the process
$L_{t}\coloneqq\cosh\big{(}\lambda\Psi(Y_{t})\big{)}e^{-\psi_{P}(\lambda)D_{\star}^{2}\sum_{i=1}^{t}\mathbb{E}_{i-1}\lVert
X_{i}\rVert^{2}}$ is a supermartingale, and we see that Definition 1 is
satisfied for $S_{t}=\Psi(Y_{t})$,
$V_{t}=D_{\star}^{2}\sum_{i=1}^{t}\mathbb{E}_{i-1}\lVert X_{i}\rVert^{2}$ and
$\psi=\psi_{P}$ with $\lambda_{\max}=\infty$ and $l_{0}=2$. The conclusion
(4.29) follows as in part (a). ∎

###  6.9 Proof of Corollary 13

We invoke Theorem 2 of Robbins and Siegmund (1970) for the sum $S_{n}/\sigma$
with $g(t)=a/\sigma+b\sigma t$, noting that

$\displaystyle\lim_{m\to\infty}\mathbb{P}\left(\exists
t\in\mathbb{N}:\frac{S_{n}}{\sqrt{m}}\geq a+\frac{bt\sigma^{2}}{m}\right)$
$\displaystyle=\lim_{m\to\infty}\mathbb{P}\left(\exists
t\in\mathbb{N}:\frac{S_{n}}{\sigma}\geq\sqrt{m}g\left(\frac{t}{m}\right)\right).$
(6.52)

It is easy to verify the conditions of parts (i) and (ii) of Robbins and
Siegmund’s theorem, yielding the conclusion

$\displaystyle\lim_{m\to\infty}\mathbb{P}\left(\exists
t\in\mathbb{N}:\frac{S_{n}}{\sigma}\geq\sqrt{m}g\left(\frac{t}{m}\right)\right)$
$\displaystyle=\mathbb{P}\left(\exists t\in(0,\infty):B_{t}\geq g(t)\right),$
(6.53)

where $(B_{t})$ is standard Brownian motion. The latter probability is equal
to $e^{-2ab}$ by the standard line-crossing formula for Brownian motion (e.g.,
Durrett, 2017, Exercise 7.5.2). ∎

###  6.10 Proof of Proposition 3

From the definition of $D(\cdot)$, we see that
$M_{t}=\exp\left\\{D(b)\cdot(S_{t}-bV_{t})\right\\}$. Since $\tau$ is a
stopping time, $(M_{t\wedge\tau})$ is a martingale, so
$1=\mathbb{E}M_{t\wedge\tau}$ for each $t\in\mathbb{N}$. The third condition
of the proposition ensures that $M_{t\wedge\tau}\leq
e^{D(b)\cdot(a+\epsilon)}$ for all $t$ a.s., so by dominated convergence we
have $\mathbb{E}M_{t\wedge\tau}\to\mathbb{E}M_{\tau}=1$, where $M_{\tau}$ is
defined as the a.s. limit of $(M_{t\wedge\tau})$, whose existence is
guaranteed since the stopped process is a nonnegative martingale. The second
condition of the proposition implies
$M_{t}\overset{\text{a.s.}}{\rightarrow}0$, hence

$\displaystyle 1=\mathbb{E}M_{\tau}$
$\displaystyle=\mathbb{E}M_{\tau}1_{(\tau<\infty)}+\mathbb{E}M_{\infty}1_{(\tau=\infty)}$
(6.54)
$\displaystyle\leq\exp\left\\{D(b)\cdot(a+\epsilon)\right\\}\mathbb{P}(\tau<\infty),$
(6.55)

which gives the desired lower bound on $\mathbb{P}(\tau<\infty)$.

###  6.11 Proof of Corollary 14

The conclusion follows immediately from Proposition 3 with $\epsilon=0$ once
we show that the conditions of the proposition are satisfied for $(S_{t})$
with $V_{t}=[S]_{t}$ and $\psi=\psi_{N}$.

In this case, since $(S_{t})$ has continuous paths a.s, $(M_{t})$ is the
stochastic exponential of the process $(D(b)S_{t})$ (Protter, 2005, Ch. II,
Theorem 37). Kazamaki’s criterion is sufficient to ensure $(M_{t})$ is a
martingale (Protter, 2005, Ch. III, Theorem 44) and $M_{0}=1$ since $S_{0}=0$.
This shows that condition (1) of Proposition 3 holds. Condition (3) follows
directly from the continuity of paths of $(S_{t})$.

It remains to show that condition (2) holds. For this we express $(S_{t})$ as
a time change of Brownian motion (Protter, 2005, Ch. II, Theorem 42):
$S_{t}=B_{[S]_{t}}$ where $(B_{t})$ is a standard Brownian motion (with
respect to a different filtration). From the law of the iterated logarithm we
know that $B_{t}/t\overset{\text{a.s.}}{\rightarrow}0$ as $t\to\infty$, hence
$S_{t}-b[S]_{t}=[S]_{t}(B_{[S_{t}]}/[S]_{t}-b)\to-\infty$ since
$[S]_{t}\uparrow\infty$. ∎

###  6.12 Proof of Proposition 4

Lemma 2.4 of Boucheron et al. (2013) shows that

$\displaystyle
f_{\alpha}(t)=\inf_{\lambda}\left[\frac{\log\alpha^{-1}}{\lambda}+\frac{\psi(\lambda)}{\lambda}\cdot
t\right],$ (6.56)

so that $f_{\alpha}(t)$ is a pointwise infimum of lines indexed by $\lambda$
with intercepts $a_{\lambda}=(\log\alpha^{-1})/\lambda$ and slopes
${b_{\lambda}=\psi(\lambda)/\lambda}$. Hence $D(b_{\lambda})=\lambda$, and by
Theorem 1 the crossing probability of each such line is
${e^{-a_{\lambda}D(b_{\lambda})}=\alpha}$. Note we have also shown that
$f_{\alpha}$ is concave. The optimizer $\lambda_{\star}(t)$ in (6.56) is the
solution in $\lambda$ of
$\lambda\psi^{\prime}(\lambda)-\psi(\lambda)=(\log\alpha^{-1})/t$. The left-
hand side of this equation has positive derivative in $\lambda$ by the
convexity of $\psi$, so the map $t\mapsto\lambda_{\star}(t)$ is injective.
Hence the optimum line $a_{\lambda_{\star}(m)}+b_{\lambda_{\star}(m)}t$ is
tangent to the curve $f_{\alpha}(t)$ at $t=m$.

##  7 Acknowledgments

We thank Victor de la Peña and Joel Tropp for their detailed perspectives on
our work. We also thank Eli Ben-Michael, Lester Mackey, Xinjia Chen, and
referees for helpful comments. Howard thanks Office of Naval Research (ONR)
Grant N00014-15-1-2367. Sekhon thanks ONR grants N00014-17-1-2176 and
N00014-15-1-2367.

## References

  * (1)
  * Ahlswede and Winter (2002) Ahlswede, R. and Winter, A. (2002), ‘Strong Converse for Identification via Quantum Channels’, IEEE Trans. Inf. Theor. 48(3), 569–579.
  * Azuma (1967) Azuma, K. (1967), ‘Weighted sums of certain dependent random variables.’, Tohoku Mathematical Journal 19(3), 357–367.
  * Bacry et al. (2018) Bacry, E., Gaïffas, S. and Muzy, J.-F. (2018), ‘Concentration inequalities for matrix martingales in continuous time’, Probability Theory and Related Fields 170(1-2), 525–553.
  * Ball et al. (1994) Ball, K., Carlen, E. A. and Lieb, E. H. (1994), ‘Sharp uniform convexity and smoothness inequalities for trace norms’, Inventiones mathematicae 115(1), 463–482.
  * Barlow et al. (1986) Barlow, M. T., Jacka, S. D. and Yor, M. (1986), ‘Inequalities for a Pair of Processes Stopped at a Random Time’, Proceedings of the London Mathematical Society s3-52(1), 142–172.
  * Bennett (1962) Bennett, G. (1962), ‘Probability Inequalities for the Sum of Independent Random Variables’, Journal of the American Statistical Association 57(297), 33–45.
  * Bercu et al. (2015) Bercu, B., Delyon, B. and Rio, E. (2015), Concentration Inequalities for Sums and Martingales, Springer International Publishing, Cham.
  * Bercu and Touati (2008) Bercu, B. and Touati, A. (2008), ‘Exponential inequalities for self-normalized martingales with applications’, The Annals of Applied Probability 18(5), 1848–1869.
  * Bernstein (1927) Bernstein, S. (1927), Theory of probability, Gastehizdat Publishing House, Moscow.
  * Blackwell (1997) Blackwell, D. (1997), Large Deviations for Martingales, in ‘Festschrift for Lucien Le Cam’, Springer, New York, NY, pp. 89–91.
  * Blackwell and Freedman (1973) Blackwell, D. and Freedman, D. A. (1973), ‘On the Amount of Variance Needed to Escape from a Strip’, The Annals of Probability 1(5), 772–787.
  * Boucheron et al. (2013) Boucheron, S., Lugosi, G. and Massart, P. (2013), Concentration inequalities: a nonasymptotic theory of independence, 1st edn, Oxford University Press, Oxford.
  * Chen (2012a) Chen, X. (2012a), A statistical approach for performance analysis of uncertain systems, in R. E. Karlsen, D. W. Gage, C. M. Shoemaker and G. R. Gerhart, eds, ‘Unmanned Systems Technology XIV’, Vol. 8387, International Society for Optics and Photonics, SPIE, pp. 583 – 594.
  * Chen (2012b) Chen, X. (2012b), ‘New Optional Stopping Theorems and Maximal Inequalities on Stochastic Processes’, arXiv:1207.3733 [math, stat] .
  * Chernoff (1952) Chernoff, H. (1952), ‘A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations’, The Annals of Mathematical Statistics 23(4), 493–507.
  * Christofides and Markström (2007) Christofides, D. and Markström, K. (2007), ‘Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales’, Random Structures & Algorithms 32(1), 88–100.
  * Chung and Lu (2006) Chung, F. and Lu, L. (2006), ‘Concentration inequalities and martingale inequalities: a survey’, Internet Mathematics 3(1), 79–127.
  * Craig (1933) Craig, C. C. (1933), ‘On the Tchebychef Inequality of Bernstein’, The Annals of Mathematical Statistics 4(2), 94–102.
  * Cramér (1938) Cramér, H. (1938), ‘Sur un nouveau théorème-limite de la théorie des probabilités’, Actualités Scientifiques 736.
  * Darling and Robbins (1967) Darling, D. A. and Robbins, H. (1967), ‘Iterated Logarithm Inequalities’, Proceedings of the National Academy of Sciences 57(5), 1188–1192.
  * de la Peña (1999) de la Peña, V. H. (1999), ‘A General Class of Exponential Inequalities for Martingales and Ratios’, The Annals of Probability 27(1), 537–564.
  * de la Peña and Giné (1999) de la Peña, V. H. and Giné, E. (1999), Decoupling, Probability and its Applications, Springer New York, New York, NY.
  * de la Peña et al. (2000) de la Peña, V. H., Klass, M. J. and Lai, T. L. (2000), Moment Bounds for Self-Normalized Martingales, in ‘High Dimensional Probability II’, Birkhäuser, Boston, MA, pp. 3–11.
  * de la Peña et al. (2001) de la Peña, V. H., Klass, M. J. and Lai, T. L. (2001), Self-normalized processes: exponential inequalities, moments, and limit theorems.  Stanford University Technical Report No. 2001-6.
  * de la Peña et al. (2004) de la Peña, V. H., Klass, M. J. and Lai, T. L. (2004), ‘Self-normalized processes: exponential inequalities, moment bounds and iterated logarithm laws’, The Annals of Probability 32(3), 1902–1933.
  * de la Peña et al. (2007) de la Peña, V. H., Klass, M. J. and Lai, T. L. (2007), ‘Pseudo-maximization and self-normalized processes’, Probability Surveys 4, 172–192.
  * de la Peña, Klass and Lai (2009) de la Peña, V. H., Klass, M. J. and Lai, T. L. (2009), ‘Theory and applications of multivariate self-normalized processes’, Stochastic Processes and their Applications 119(12), 4210–4227.
  * de la Peña, Lai and Shao (2009) de la Peña, V. H., Lai, T. L. and Shao, Q.-M. (2009), Self-normalized processes: limit theory and statistical applications, Springer, Berlin.
  * Delyon (2009) Delyon, B. (2009), ‘Exponential inequalities for sums of weakly dependent variables’, Electronic Journal of Probability 14, 752–779.
  * Delyon (2015) Delyon, B. (2015), Exponential inequalities for dependent processes, Technical report.
  * Dembo and Zeitouni (2010) Dembo, A. and Zeitouni, O. (2010), Large Deviations Techniques and Applications, Springer, Berlin, Heidelberg.
  * Doob (1940) Doob, J. L. (1940), ‘Regularity properties of certain families of chance variables’, 47(3), 455–486.
  * Dubins and Savage (1965) Dubins, L. E. and Savage, L. J. (1965), ‘A Tchebycheff-like Inequality for Stochastic Processes’, Proceedings of the National Academy of Sciences 53(2), 274–275.
  * Durrett (2017) Durrett, R. (2017), Probability: Theory and Examples, 5a edn.
  * Efron (1969) Efron, B. (1969), ‘Student’s $t$-Test Under Symmetry Conditions’, Journal of the American Statistical Association 64(328), 1278–1302.
  * Fan et al. (2012) Fan, X., Grama, I. and Liu, Q. (2012), ‘Hoeffding’s inequality for supermartingales’, Stochastic Processes and their Applications 122(10), 3545–3559.
  * Fan et al. (2015) Fan, X., Grama, I. and Liu, Q. (2015), ‘Exponential inequalities for martingales with applications’, Electronic Journal of Probability 20(1), 1–22.
  * Freedman (1975) Freedman, D. A. (1975), ‘On Tail Probabilities for Martingales’, The Annals of Probability 3(1), 100–118.
  * Galambos (1978) Galambos, J. (1978), The asymptotic theory of extreme order statistics, Wiley.  Google-Books-ID: O06aAAAAIAAJ.
  * Gittens and Tropp (2011) Gittens, A. and Tropp, J. A. (2011), ‘Tail bounds for all eigenvalues of a sum of random matrices’, ACM Report 2014-02, Caltech .
  * Godwin (1955) Godwin, H. J. (1955), ‘On Generalizations of Tchebychef’s Inequality’, Journal of the American Statistical Association 50(271), 923–945.
  * Hoeffding (1963) Hoeffding, W. (1963), ‘Probability Inequalities for Sums of Bounded Random Variables’, Journal of the American Statistical Association 58(301), 13–30.
  * Jorgensen (1997) Jorgensen, B. (1997), The Theory of Dispersion Models, CRC Press.
  * Kearns and Saul (1998) Kearns, M. and Saul, L. (1998), Large Deviation Methods for Approximate Probabilistic Inference, in ‘Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence’, UAI’98, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, pp. 311–319.
  * Khan (2009) Khan, R. A. (2009), ‘${L}_{p}$-Version of the Dubins–Savage Inequality and Some Exponential Inequalities’, Journal of Theoretical Probability 22(2), 348.
  * Koltchinskii and Lounici (2017) Koltchinskii, V. and Lounici, K. (2017), ‘Concentration inequalities and moment bounds for sample covariance operators’, Bernoulli 23(1), 110–133.
  * Lepingle (1978) Lepingle, D. (1978), Sur le comportement asymptotique des martingales locales, in A. Dold, B. Eckmann, C. Dellacherie, P. A. Meyer and M. Weil, eds, ‘Séminaire de Probabilités XII’, Vol. 649, Springer, Berlin, Heidelberg, pp. 148–161.
  * Lieb (1973) Lieb, E. H. (1973), ‘Convex trace functions and the Wigner-Yanase-Dyson conjecture’, Advances in Mathematics 11, 267–288.
  * Logan et al. (1973) Logan, B. F., Mallows, C. L., Rice, S. O. and Shepp, L. A. (1973), ‘Limit Distributions of Self-normalized Sums’, The Annals of Probability 1(5), 788–809.
  * Mackey et al. (2014) Mackey, L., Jordan, M. I., Chen, R. Y., Farrell, B. and Tropp, J. A. (2014), ‘Matrix concentration inequalities via the method of exchangeable pairs’, The Annals of Probability 42(3), 906–945.
  * Mazliak and Shafer (2009) Mazliak, L. and Shafer, G., eds (2009), The Splendors and Miseries of Martingales [Special issue], Vol. 5, no. 1 of Electronic Journal for History of Probability and Statistics.
http://www.jehps.net/juin2009.html

  * McDiarmid (1998) McDiarmid, C. (1998), Concentration, in M. Habib, C. McDiarmid, J. Ramirez-Alfonsin and B. Reed, eds, ‘Probabilistic Methods for Algorithmic Discrete Mathematics’, Springer, New York, pp. 195–248.
  * Minsker (2017) Minsker, S. (2017), ‘On Some Extensions of Bernstein’s Inequality for Self-adjoint Operators’, Statistics and Probability Letters 127, 111–119.
  * Oliveira (2010a) Oliveira, R. (2010a), ‘The spectrum of random $k$-lifts of large graphs (with possibly large $k$)’, Journal of Combinatorics 1(3), 285–306.
  * Oliveira (2010b) Oliveira, R. (2010b), ‘Sums of random Hermitian matrices and an inequality by Rudelson’, Electronic Communications in Probability 15, 203–212.
  * Papapantoleon (2008) Papapantoleon, A. (2008), ‘An introduction to Lévy processes with applications in finance’, arXiv:0804.0482 .
  * Pinelis (1992) Pinelis, I. (1992), An Approach to Inequalities for the Distributions of Infinite-Dimensional Martingales, in ‘Probability in Banach Spaces, 8: Proceedings of the Eighth International Conference’, Birkhäuser, Boston, MA, pp. 128–134.
  * Pinelis (1994) Pinelis, I. (1994), ‘Optimum Bounds for the Distributions of Martingales in Banach Spaces’, The Annals of Probability 22(4), 1679–1706.
  * Prokhorov (1995) Prokhorov, A. V. (1995), Bernstein inequality, in M. Hazewinkel, ed., ‘Encyclopaedia of Mathematics’, Vol. 1 of Encyclopaedia of Mathematics, Springer, Boston, MA, p. 365.
  * Prokhorov (1959) Prokhorov, Y. V. (1959), ‘An Extremal Problem in Probability Theory’, Theory of Probability & Its Applications 4(2), 201–203.
  * Protter (2005) Protter, P. E. (2005), Stochastic Integration and Differential Equations, Springer Science & Business Media.
  * Raginsky and Sason (2012) Raginsky, M. and Sason, I. (2012), ‘Concentration of measure inequalities in information theory, communications and coding (second edition)’, arXiv:1212.4663 [cs, math] .
  * Robbins (1970) Robbins, H. (1970), ‘Statistical Methods Related to the Law of the Iterated Logarithm’, The Annals of Mathematical Statistics 41(5), 1397–1409.
  * Robbins and Siegmund (1970) Robbins, H. and Siegmund, D. (1970), ‘Boundary Crossing Probabilities for the Wiener Process and Sample Sums’, The Annals of Mathematical Statistics 41(5), 1410–1429.
  * Rockafellar (1970) Rockafellar, R. T. (1970), Convex analysis, Princeton mathematical series, Princeton University Press, Princeton, N.J.
  * Rudelson (1999) Rudelson, M. (1999), ‘Random Vectors in the Isotropic Position’, Journal of Functional Analysis 164(1), 60–72.
  * Shao (1997) Shao, Q.-M. (1997), ‘Self-normalized large deviations’, The Annals of Probability 25(1), 285–328.
  * Shorack and Wellner (1986) Shorack, G. R. and Wellner, J. A. (1986), Empirical processes with applications to statistics, Wiley, New York.
  * Siegmund (1985) Siegmund, D. (1985), Sequential Analysis, Springer New York, New York, NY.
  * Tropp (2011) Tropp, J. A. (2011), ‘Freedman’s inequality for matrix martingales’, Electronic Communications in Probability 16, 262–270.
  * Tropp (2012) Tropp, J. A. (2012), ‘User-friendly tail bounds for sums of random matrices’, Foundations of Computational Mathematics 12(4), 389–434.
  * Tropp (2015) Tropp, J. A. (2015), ‘An Introduction to Matrix Concentration Inequalities’, Foundations and Trends in Machine Learning 8(1-2), 1–230.
  * Uspensky (1937) Uspensky, J. V. (1937), Introduction to mathematical probability, 1st edn, McGraw-Hill Book Company, Inc, New York, London.
  * van de Geer (1995) van de Geer, S. (1995), ‘Exponential Inequalities for Martingales, with Application to Maximum Likelihood Estimation for Counting Processes’, The Annals of Statistics 23(5), 1779–1801.
  * Vershynin (2012) Vershynin, R. (2012), Introduction to the non-asymptotic analysis of random matrices, in Y. C. Eldar and G. Kutyniok, eds, ‘Compressed Sensing: Theory and Applications’, Cambridge University Press, pp. 210–268.
  * Ville (1939) Ville, J. (1939), Étude Critique de la Notion de Collectif., Gauthier-Villars, Paris.
  * Wainwright (2017) Wainwright, M. J. (2017), High-dimensional statistics: A non-asymptotic viewpoint, Cambridge University Press.
  * Wald (1945) Wald, A. (1945), ‘Sequential Tests of Statistical Hypotheses’, Annals of Mathematical Statistics 16(2), 117–186.

##  Appendix A Sharpened pre-factors based on rank

This argument is adapted from Wainwright (2017), though the idea originates in
Oliveira (2010b). Suppose the conditions of Lemma 4 hold and

$\displaystyle\sup_{t\in\mathcal{T}}\operatorname{rank}(U_{t}+W_{t})\leq
r<d,\text{ a.s.}$ (A.1)

Since $\Delta U_{t}\succeq 0$ and $\Delta W_{t}\succeq 0$ for all $t$, we know
that $\operatorname{range}(U_{t}+W_{t})\subseteq S$ for all $t$ a.s., where
$S$ is an $r$-dimensional subspace. Inequality (6.14) implies that
$\operatorname{range}(Y_{t})\subseteq S$ for all $t$ a.s. as well. Let $M$ be
a $d\times r$ matrix whose columns form an orthonormal basis for this
subspace. Then the $r$-dimensional process $\widetilde{Y}_{t}\coloneqq
M^{\star}Y_{t}M$ has the same spectrum as $Y_{t}$ for all $t$ a.s., so we may
apply our bounds to $(\widetilde{Y}_{t})$, with $(\widetilde{U}_{t})$ and
$(\widetilde{W}_{t})$ defined analogously, to obtain bounds with $l_{0}=r$. ∎

##  Appendix B Relation to the Dubins-Savage inequality

The Dubins-Savage inequality (Dubins and Savage, 1965) says that for any
martingale $S_{t}$ in discrete time with $S_{0}=0$, setting
$V_{t}=\sum_{i=1}^{t}\operatorname{Var}_{i-1}(S_{t}-S_{t-1})$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
a+bV_{t}\right)\leq\frac{1}{1+ab}.$ (B.1)

The Dubins-Savage inequality may be proved by means similar to ours, invoking
Ville’s inequality for a suitable supermartingale. The relationship of our
bounds to the Dubins-Savage inequality is analogous to that between fixed-time
Cramér-Chernoff bounds and Chebyshev’s inequality. More precisely, the Dubins-
Savage inequality is analogous to Uspensky’s one-sided version of Chebyshev’s
inequality (Uspensky, 1937; Bennett, 1962):

$\displaystyle\mathbb{P}(X-\mathbb{E}X\geq
x)\leq\frac{\operatorname{Var}X}{\operatorname{Var}X+x^{2}}.$ (B.2)

Similar to our Theorem 1(b), we may optimize the RHS of (B.1) over all lines
passing through a point $(m,x)$ to obtain the equivalent bound

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+\frac{x}{2m}\left(V_{t}-m\right)\right)\leq\frac{m}{m+x^{2}/4},$ (B.3)

recovering Uspensky’s inequality (B.2) with $x/2$ in place of $x$. The Dubins-
Savage inequality does not recover Uspensky’s inequality at the fixed time
$m$—something is necessarily lost in going from a fixed time to a uniform
bound. Compare our Theorem 1(b), which exactly recovers the fixed-time Cramér-
Chernoff bound (4.2). For these exponential bounds, we lose nothing in going
from a fixed time to a uniform bound.

##  Appendix C Graphical comparison of $\psi$ functions

Figure 7: Comparison of $\psi$ functions given in Table 2. We have set $g=h=1$
in $\psi_{B}$, $c=1$ in $\psi_{P}$, $c=1/3$ in $\psi_{G}$, and $c=1/2$ in
$\psi_{E}$. These are all values that might be used in bounding a process with
$[-1,1]$-valued increments using the same variance process; see Figure 3 and
Proposition 2. In general, bounds based on different $\psi$ functions may have
different assumptions and variance processes, so may not be comparable based
on $\psi$ functions alone. However, with identical variance processes, a
smaller $\psi$ function yields a tighter bound. Note all functions behave like
$\psi_{N}(\lambda)=\lambda^{2}/2$ near the origin.

Figure 7 illustrates together the five standard $\psi$ functions discussed in
Section 3, to help the reader gain intuition. With the given parameter
settings, the inequalities apparent in the figure do hold for all $\lambda\geq
0$:
$\psi_{B}(\lambda)\leq\psi_{N}(\lambda)\leq\psi_{P}(\lambda)\leq\psi_{G}(\lambda)\leq\psi_{E}(\lambda)$.
See the proof of Proposition 2 in Section 6.3.

##  Appendix D A more general boundary-crossing result

The following assumption weakens Definition 1, replacing the product
$\psi(\lambda)\Delta V_{t}$ with a function $f(\lambda,\Delta V_{t})$.

######  Assumption 1.

Let $(S_{t})_{t\in\mathbb{N}\cup\\{0\\}}$ and
$(V_{t})_{t\in\mathbb{N}\cup\\{0\\}}$ be two real-valued processes adapted to
an underlying filtration $(\mathcal{F}_{t})_{t\in\mathbb{N}\cup\\{0\\}}$ with
$S_{0}=V_{0}=0$ a.s. and $V_{t}\geq 0$ a.s. for all $t\in\mathbb{N}$. Let
$f:[0,\lambda_{\max})\times(0,\infty)\to\mathbb{R}$ be concave in its second
argument for each value of the first, and let $l_{0}\in[1,\infty)$. We assume,
for each $\lambda\in[0,\lambda_{\max})$, there exists a supermartingale
$(L_{t}(\lambda))_{t\in\mathbb{N}\cup\\{0\\}}$ with respect to
$(\mathcal{F}_{t})$ such that $L_{0}\leq l_{0}$ a.s. and $\exp\left\\{\lambda
S_{t}-\sum_{i=1}^{t}f(\lambda,\Delta V_{i})\right\\}\leq L_{t}(\lambda)$ a.s.
for all $t\in\mathbb{N}$.

Clearly, when $f(\lambda,v)\equiv\psi(\lambda)\cdot v$ for some $\psi$,
Definition 1 holds and Theorem 1 applies. Under the weaker Assumption 1 we
have the following results:

######  Theorem 2.

If Assumption 1 holds for some real-valued processes $(S_{t})$ and $(V_{t})$,
then for any $\lambda\in[0,\lambda_{\max})$ and $a>0$, we have

$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
a+\frac{tf(\lambda,V_{t}/t)}{\lambda}\right)\leq l_{0}e^{-a\lambda}.$ (D.1)

Furthermore, if $f_{v}(\cdot)\coloneqq f(\cdot,v)$ is CGF-like for each $v>0$,
then for any $n\in\mathbb{N}$, $m>0$ and $0\leq
x<n\sup_{\lambda}f_{m/n}^{\prime}(\lambda)$, we have

$\displaystyle\mathbb{P}\left(\exists t\leq n:S_{t}\geq
x+\frac{n}{\lambda_{\star}}\left[f\left(\lambda_{\star},\frac{V_{t}}{n}\right)-f\left(\lambda_{\star},\frac{m}{n}\right)\right]\right)$
$\displaystyle\leq
l_{0}\exp\left\\{-nf_{m/n}^{\star}\left(\frac{x}{n}\right)\right\\}$ (D.2)
$\displaystyle\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+\frac{tf(\lambda_{\star},m/t)-nf(\lambda_{\star},m/n)}{\lambda_{\star}}\right)$
$\displaystyle\leq
l_{0}\exp\left\\{-nf_{m/n}^{\star}\left(\frac{x}{n}\right)\right\\}$ (D.3)

where $\lambda_{\star}\coloneqq(f_{m/n}^{\star})^{\prime}(x/n)$.

The proof follows the same principles as that of Theorem 1 and is omitted for
brevity. One application of this result is to martingales with bounded
increments, making use of $\psi_{B}$:

######  Corollary 15.

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

$\mathbb{P}\left(\exists t\leq n:S_{t}\geq
x+n\left[g\left(\frac{V_{t}}{n}\right)-g\left(\frac{m}{n}\right)\right]\right)\\\
\leq\left[\left(\frac{m}{x+m}\right)^{x+m}\left(\frac{n}{n-x}\right)^{n-x}\right]^{n/(n+m)},$
(D.4)

and

$\mathbb{P}\left(\exists t\in\mathbb{N}:S_{t}\geq
x+tg\left(\frac{m}{t}\right)-ng\left(\frac{m}{n}\right)\right)\\\
\leq\left[\left(\frac{m}{x+m}\right)^{x+m}\left(\frac{n}{n-x}\right)^{n-x}\right]^{n/(n+m)},$
(D.5)

where

$\displaystyle
g(v)\coloneqq\frac{m+cn}{n(v+c)\log\xi}\left[v\xi^{\frac{cn}{m+cn}}+c\xi^{-\frac{vn}{m+cn}}\right]\quad\text{and}\quad\xi\coloneqq\frac{1+x/m}{1-x/cn}.$
(D.6)

This generalizes Theorem 2.1 of Fan et al. (2012) [B, D].

One can further generalize Assumption 1 by replacing $\sum_{i}f(\lambda,\Delta
V_{i})$ with $\sum_{i}f_{i}(\lambda,\Delta V_{i})$, permitting $f_{i}$ to vary
with time, but the added generality further weakens the conclusions we can
draw.

##  Appendix E Equivalent sub-exponential conditions

Here we show that our sub-exponential condition (E.1) is equivalent to another
common definition (E.2) (Wainwright, 2017). We rephrase both conditions for
the right tail of a mean-zero random variable $X$.

######  Proposition 5.

For a zero-mean random variable $X$, the following are equivalent:

  1. 1.

There exist $\sigma^{2}>0$ and $c>0$ such that

$\displaystyle\log\mathbb{E}e^{\lambda
X}\leq\frac{\left[-\log(1-c\lambda)-c\lambda\right]\sigma^{2}}{c^{2}}\qquad\text{
for all }\lambda\in[0,1/c).$ (E.1)

  2. 2.

There exist $\nu>0$ and $\alpha>0$ such that

$\displaystyle\log\mathbb{E}e^{\lambda
X}\leq\frac{\lambda^{2}\nu}{2}\qquad\text{ for all }\lambda\in[0,1/\alpha).$
(E.2)

###### Proof.

Suppose the first condition holds. A Taylor expansion of
$[-\log(1-c\lambda)-c\lambda]/c^{2}$ about $\lambda=0$ yields

$\displaystyle\frac{\left[-\log(1-c\lambda)-c\lambda\right]\sigma^{2}}{c^{2}}=\frac{\lambda^{2}\sigma^{2}}{2}+\lambda^{2}\sigma^{2}\sum_{k=1}^{\infty}\frac{(c\lambda)^{k}}{2+k}=\frac{\lambda^{2}\sigma^{2}}{2}+o(\lambda^{2}).$
(E.3)

So choosing $\nu>\sigma^{2}$, we can find $\alpha$ sufficiently large to
ensure that

$\displaystyle\frac{\left[-\log(1-c\lambda)-c\lambda\right]\sigma^{2}}{c^{2}}\leq\frac{\lambda^{2}\nu}{2}\qquad\text{
for all }\lambda\in[0,1/\alpha),$ (E.4)

implying the second condition holds.

Now suppose the second condition holds. Then since $\lambda\geq 0$, the above
series expansion shows that the first condition holds with $\sigma^{2}=\nu$
and $c=\alpha$. ∎

Note that if the first condition (E.1) applies to both $X$ and $-X$, then $X$
satisfies the usual, two-tailed sub-exponential condition,
$\log\mathbb{E}e^{\lambda X}\leq\lambda^{2}\nu/2$ for all
$\lvert\lambda\rvert<1/\alpha$.