# Learning from non-irreducible Markov chains

Nikola Sandrić  Department of Mathematics
University of Zagreb
Zagreb
Croatia<EMAIL_ADDRESS>and  Stjepan Šebek  Department of Applied
Mathematics
Faculty of Electrical Engineering and Computing
University of Zagreb
Zagreb
Croatia<EMAIL_ADDRESS>
###### Abstract.

Most of the existing literature on supervised learning problems focuses on the
case when the training data set is drawn from an i.i.d. sample. However, many
practical supervised learning problems are characterized by temporal
dependence and strong correlation between the marginals of the data-generating
process, suggesting that the i.i.d. assumption is not always justified. This
problem has been already considered in the context of Markov chains satisfying
the Doeblin condition. This condition, among other things, implies that the
chain is not singular in its behavior, i.e. it is irreducible. In this
article, we focus on the case when the training data set is drawn from a not
necessarily irreducible Markov chain. Under the assumption that the chain is
uniformly ergodic with respect to the $\mathrm{L}^{1}$-Wasserstein distance,
and certain regularity assumptions on the hypothesis class and the state space
of the chain, we first obtain a uniform convergence result for the
corresponding sample error, and then we conclude learnability of the
approximate sample error minimization algorithm and find its generalization
bounds. At the end, a relative uniform convergence result for the sample error
is also discussed.

###### Key words and phrases:

Approximate sample error minimization algorithm, Generalization bounds, Markov
chain, Wasserstein distance

###### 2010 Mathematics Subject Classification:

68W40, 68T10, 60J05

##  1\. Introduction

Let $(\mathsf{X},\mathcal{X})$ and $(\mathsf{Y},\mathcal{Y})$ be measurable
spaces, let $\mathsf{Z}\subseteq\mathsf{X}\times\mathsf{Y}$ be a complete
separable metric space with bounded metric $\uprho$, and let
$\mathrm{pr}_{\mathsf{X}}:\mathsf{Z}\to\mathsf{X}$ and
$\mathrm{pr}_{\mathsf{Y}}:\mathsf{Z}\to\mathsf{Y}$ be the projection mappings.
We endow $(\mathsf{Z},\uprho)$ with its Borel $\sigma$-algebra
$\mathfrak{B}(\mathsf{Z})$. Assume that
$\mathrm{pr}^{-1}_{\mathsf{X}}(\mathrm{pr}_{\mathsf{X}}(\mathsf{Z})\cap\mathcal{X})\subseteq\mathfrak{B}(\mathsf{Z})$
and
$\mathrm{pr}^{-1}_{\mathsf{Y}}(\mathrm{pr}_{\mathsf{Y}}(\mathsf{Z})\cap\mathcal{Y})\subseteq\mathfrak{B}(\mathsf{Z})$.
This, in particular, implies that $\mathrm{pr}_{\mathsf{X}}$ and
$\mathrm{pr}_{\mathsf{Y}}$ are measurable.

Further, let $(\Omega,\mathcal{F},\mathbb{P}_{z},\\{Z_{n}\\}_{n\geq
0},\\{\mathcal{F}_{n}\\}_{n\geq 0})_{z\in\mathsf{Z}}$, denoted by
$\\{Z_{n}\\}_{n\geq 0}$ in the sequel, be a temporally-homogeneous Markov
chain on $(\mathsf{Z},\mathfrak{B}(\mathsf{Z}))$, in the sense of [MT09]. The
process $\\{Z_{n}\\}_{n\geq
0}=\\{(\mathrm{pr}_{\mathsf{X}}(Z_{n}),\mathrm{pr}_{\mathsf{Y}}(Z_{n}))\\}_{n\geq
0}$ is viewed as a sequence of input data (the first component) together with
their outputs (the second component).

The main aim of this article is to learn a function (from a given hypothesis
class $\mathscr{H}\subseteq\mathsf{Y}^{\mathsf{X}}$) that, given a training
set of data $z_{0},\dots,z_{n-1}\in\mathsf{Z}$ drawn from the first $n$
samples of $\\{Z_{n}\\}_{n\geq 0}$, best approximates the relationship between
the input and output observable. We remark that even if there is an exact
functional relationship, this function is in general not known to us and it
does not have to belong to the class $\mathscr{H}$.

This type of problem has already been considered in the literature, see the
literature review part below. However, in all these works a crucial assumption
is that the process $\\{Z_{n}\\}_{n\geq 0}$ is not singular in its behavior,
i.e. it is irreducible. In this article, we study the learning problem in the
case when $\\{Z_{n}\\}_{n\geq 0}$ does not necessarily possess this property.
We follow the standard statistical learning theory scheme: we first obtain a
uniform convergence result for the corresponding sample error, and then we
conclude learnability of the approximate sample error minimization (ASEM)
algorithm and find its generalization bounds.

### Main results

We start with the description of the model. Assume the following:

(A1):

$\mathsf{Y}\subseteq\mathbb{R}$,
$\mathcal{Y}=\mathfrak{B}(\mathbb{R})\cap\mathsf{Y}$ (the standard relative
Euclidean $\sigma$-algebra), and $\mathscr{H}\subseteq\mathsf{Y}^{\mathsf{X}}$
is a totally bounded metric space, i.e. $\mathscr{H}$ admits a metric
$\uprho_{\mathscr{H}}$ such that for each $\epsilon>0$ there is finite
$\mathscr{H}_{\epsilon}\subseteq\mathscr{H}$ with the property that for every
$h\in\mathscr{H}$ there is $h_{\epsilon}\in\mathscr{H}_{\epsilon}$ with
$\uprho_{\mathscr{H}}(h,h_{\epsilon})<\epsilon$.

For $\epsilon>0$ let

$\mathcal{N}(\epsilon,\mathscr{H},\uprho_{\mathscr{H}})\coloneqq\min\\{|\mathscr{H}_{\epsilon}|\colon\mathscr{H}_{\epsilon}\text{
is an }\epsilon\text{-covering of }\mathscr{H}\text{ in the sense of (A1)}\\}$

be the $\epsilon$-covering number of $\mathscr{H}$. Typical examples of
classes of functions satisfying (A1) are the following:

  * (i)

Let $\mathsf{X}=[0,T]$, let $\mathsf{Y}=[-V/2,V/2]$ and let
$\mathscr{H}\subset\mathsf{Y}^{\mathsf{X}}$ be a class of functions with total
variation at most $V$, for some $T,V>0$. Further, let $\uprho_{\mathscr{H}}$
be the corresponding $\mathrm{L}^{1}$-metric (with respect to the Lebesgue
measure). Then, in [BKP97, Theorem 1] it has been shown that

$\mathcal{N}(\epsilon,\mathscr{H},\uprho_{\mathscr{H}})\leq
2^{13VT/\epsilon}.$

  * (ii)

Let $\mathsf{X}\subset\mathbb{R}^{d}$ be compact and let
$\mathscr{H}\subset\mathcal{C}^{\gamma}(\mathsf{X},\mathbb{R})$ be bounded
(with respect to the corresponding Hölder metric) for some $0<\gamma\leq 1$.
Then, for $\uprho_{\mathscr{H}}$ being the Hölder or sup-metric, in [Zho03,
Theorem 4] it has been shown that there is $C>0$ such that

(1.1)
$\mathcal{N}(\epsilon,\mathscr{H},\uprho_{\mathscr{H}})\leq\mathrm{e}^{C\epsilon^{-2d/\gamma}}.$

Further, let $\ell:\mathsf{Y}\times\mathsf{Y}\to[0,\infty)$ be measurable (the
loss function), and for each $h\in\mathscr{H}$ define
$\ell_{h}:\mathsf{Z}\to[0,\infty)$ by

$\ell_{h}(z)\coloneqq\ell\bigl{(}h(\mathrm{pr}_{\mathsf{X}}(z)),\mathrm{pr}_{\mathsf{Y}}(z)\bigr{)}.$

We next assume:

(A2):

there are $L,\bar{L}\geq 0$ such that
$\displaystyle|\ell_{h_{1}}(z_{1})-\ell_{h_{2}}(z_{2})|\leq
L\uprho(z_{1},z_{2})+\bar{L}\uprho_{\mathscr{H}}(h_{1},h_{2})$ for all
$z_{1},z_{2}\in\mathsf{Z}$ and $h_{1},h_{2}\in\mathscr{H}$.

Examples of classes of functions for which (A2) holds are the following:

  * (i)

Let $\mathsf{X}$ and $\mathscr{H}$ be as in (ii) above, with $\gamma=1$ (the
class of Lipschitz continuous functions). Assume also that $\mathsf{Y}$ is
bounded. Then, (A2) holds with $\ell(y,\bar{y})=|y-\bar{y}|^{2}$, and $\uprho$
and $\uprho_{\mathscr{H}}$ being the Euclidean and sup metric, respectively.

  * (ii)

Let $\mathsf{X}$ and $\mathsf{Y}$ be as in (i), and let
$\mathscr{H}\subseteq\\{h\in\mathsf{Y}^{\mathsf{X}}\colon h\text{ is Lipschitz
continuous and }h(x_{0})=y_{0}\\}$ for some $x_{0}\in\mathsf{X}$ and
$y_{0}\in\mathsf{Y}$. Then, (A2) holds with $\ell(y,\bar{y})=|y-\bar{y}|^{2}$,
and $\uprho$ and $\uprho_{\mathscr{H}}$ being the Euclidean and Lipschitz
metric, respectively.

Denote by $\mathcal{P}(z,\mathrm{d}\bar{z})$ the (one-step) transition kernel
of $\\{Z_{n}\\}_{n\geq 0}$, and let $\mathscr{P}_{1}(\mathsf{Z})$ be the class
of all probability measures on $\mathsf{Z}$ having finite first moment. Recall
that the $\mathrm{L}^{1}$-Wasserstein distance on
$\mathscr{P}_{1}(\mathsf{Z})$ is defined by

$\mathscr{W}(\upmu_{1},\upmu_{2})\coloneqq\inf_{\Pi\in\mathcal{C}(\upmu_{1},\upmu_{2})}\int_{\mathsf{Z}\times\mathsf{Z}}\uprho(z,\bar{z})\,\Pi(\mathrm{d}{z},\mathrm{d}{\bar{z}}),$

where $\mathcal{C}(\upmu_{1},\upmu_{2})$ is the family of couplings of
$\upmu_{1}(\mathrm{d}z)$ and $\upmu_{2}(\mathrm{d}z)$, i.e.
$\Pi\in\mathcal{C}(\upmu_{1},\upmu_{2})$ if, and only if,
$\Pi(\mathrm{d}z,\mathrm{d}\bar{z})$ is a probability measure on
$\mathsf{Z}\times\mathsf{Z}$ having $\upmu_{1}(\mathrm{d}z)$ and
$\upmu_{2}(\mathrm{d}z)$ as its marginals. We finally assume:

(A3):

$\mathsf{Y}$ is bounded and there is $\eta\in(0,1)$ such that

$\mathscr{W}\bigl{(}\mathcal{P}(z_{1},\mathrm{d}\bar{z}),\mathcal{P}(z_{2},\mathrm{d}\bar{z})\bigr{)}\leq(1-\eta)\,\uprho(z_{1},z_{2}).$

An example satisfying (A3) is as follows. Let $\\{\chi_{n}\\}_{n\geq 1}$ be a
sequence of i.i.d. $\mathbb{R}$-valued random variables defined on a
probability space $(\Omega,\mathcal{F},\mathbb{P})$, satisfying
$\mathbb{P}(\chi_{n}=0)=\mathbb{P}(\chi_{n}=1/2)=1/2$. Define

$X_{n+1}\coloneqq\frac{1}{2}X_{n}+\chi_{n+1}$

with $X_{0}=x\in[0,1]$. Clearly, $\\{X_{n}\\}_{n\geq 0}$ is a Markov chain on
$[0,1]$ with transition kernel
$\mathcal{P}_{X}(x,\mathrm{d}\bar{x})=\mathbb{P}(\chi_{1}+x/2\in\mathrm{d}\bar{x})$.
Further, let $f:[0,1]\to\mathbb{R}$ be Lipschitz continuous with Lipschitz
constant $\mathrm{Lip}(f)<\sqrt{3}$ (hence, $f(x)$ is of bounded variation),
and set $Z_{n}\coloneqq(X_{n},f(X_{n}))$ for $n\geq 0$. Then,
$\\{Z_{n}\\}_{n\geq 0}$ is a Markov chain on $\mathsf{Z}=\\{(x,f(x))\colon
x\in[0,1]\\}$ with transition kernel
$\mathcal{P}(z,\mathrm{d}\bar{z})=\mathbb{P}(\chi_{1}+\mathrm{pr}_{\mathsf{X}}(z)/2\in\mathrm{d}\mathrm{pr}_{\mathsf{X}}(\bar{z}))$,
see Lemma 3.1. For $\uprho$ we take the standard Euclidean metric. Clearly,
$\\{Z_{n}\\}_{n\geq 0}$ is not irreducible. Namely, for $z\in\mathsf{Z}$ such
that $\mathrm{pr}_{\mathsf{X}}(z)\in\mathbb{Q}$ it holds that
$\mathcal{P}^{n}(z,\mathsf{Z}\cap(\mathbb{Q}^{c}\times\mathbb{R}))=0$ for all
$n\geq 1$, and analogously for $z\in\mathsf{Z}$ such that
$\mathrm{pr}_{\mathsf{X}}(z)\in\mathbb{Q}^{c}$ it holds that
$\mathcal{P}^{n}(z,\mathsf{Z}\cap(\mathbb{Q}\times\mathbb{R}))=0$ for all
$n\geq 1$. Further, let ${\rm Length}(\mathrm{d}z)$ be the arc-length measure
on $\mathsf{Z}$. It is then easy to see that $\uppi(\mathrm{d}z)\coloneqq{\rm
Length}(\mathrm{d}z)/{\rm Length}(\mathsf{Z})$ satisfies
$\int_{\mathsf{Z}}\mathcal{P}(z,\mathrm{d}\bar{z})\uppi(\mathrm{d}z)=\uppi(\mathrm{d}\bar{z}),$
i.e. $\uppi(\mathrm{d}z)$ is an invariant probability measure for
$\\{Z_{n}\\}_{n\geq 0}$. Here, ${\rm Length}(\mathsf{Z})$ is the length of
$\mathsf{Z}$. Observe that $\uppi(\mathrm{d}\bar{z})$ and
$\mathcal{P}(z,\bar{z})$ are mutually singular, implying that the relation in
eq. 1.4 cannot hold. Finally, we show the relation in (A3). By Kantorovich-
Rubinstein theorem we have that

$\mathscr{W}(\upmu_{1},\upmu_{2})=\sup_{\\{g\colon\mathrm{Lip}(g)\leq
1\\}}\,|\upmu_{1}(g)-\upmu_{2}(g)|,$

where the supremum is taken over all Lipschitz continuous functions
$g\colon\mathsf{Z}\to\mathbb{R}$ with Lipschitz constant $\mathrm{Lip}(g)\leq
1$ and, for a probability measure $\upmu(\mathrm{d}z)$ on $\mathsf{Z}$ and a
measurable function $f:\mathsf{Z}\to\mathbb{R}$, the symbol $\upmu(f)$ stands
for $\int_{\mathsf{Z}}f(z)\upmu(\mathrm{d}z)$, whenever the integral is well
defined. Thus, for any
$z_{1}=(x_{1},f(x_{1})),z_{2}=(x_{2},f(x_{2}))\in\mathsf{Z}$ it holds that

$\displaystyle\mathscr{W}(\mathcal{P}(z_{1},\bar{z}),\mathcal{P}(z_{2},\bar{z}))$
$\displaystyle=\sup_{\\{g\colon\mathrm{Lip}(g)\leq
1\\}}\,\left|\int_{\mathsf{Z}}g(\bar{z})\mathbb{P}\bigl{(}\chi_{1}+\mathrm{pr}_{\mathsf{X}}(z_{1})/2\in\mathrm{d}\mathrm{pr}_{\mathsf{X}}(\bar{z})\bigr{)}-\int_{\mathsf{Z}}g(\bar{z})\mathbb{P}\bigl{(}\chi_{1}+\mathrm{pr}_{\mathsf{X}}(z_{2})/2\in\mathrm{d}\mathrm{pr}_{\mathsf{X}}(\bar{z})\bigr{)}\right|$
$\displaystyle=\sup_{\\{g\colon\mathrm{Lip}(g)\leq
1\\}}\,\Bigg{|}\frac{1}{2}\left(g\left(x_{1}/2,f\left(x_{1}/2\right)\right)-g\left(x_{2}/2,f\left(x_{2}/2\right)\right)\right)$
$\displaystyle\ \ \
+\frac{1}{2}\left(g\left((x_{1}+1)/2,f\left((x_{1}+1)/2\right)\right)-g\left((x_{2}+1)/2,f\left((x_{2}+1)/2)\right)\right)\right)\Bigg{|}$
$\displaystyle\leq\frac{1}{2}\uprho\left(\left(x_{1}/2,f\left(x_{1}/2\right)\right),\left(x_{2}/2,f\left(x_{2}/2\right)\right)\right)$
$\displaystyle\ \ \
+\frac{1}{2}\uprho\left(\left((x_{1}+1)/2,f\left((x_{1}+1)/2\right)\right),\left((x_{2}+1)/2,f\left((x_{2}+1)/2\right)\right)\right)$
$\displaystyle\leq\frac{\sqrt{1+\mathrm{Lip}(f)^{2}}}{2}|x_{1}-x_{2}|$
$\displaystyle\leq\frac{\sqrt{1+\mathrm{Lip}(f)^{2}}}{2}\uprho(z_{1},z_{2}),$

which proves (A3) with $\eta=1-\sqrt{1+\mathrm{Lip}(f)^{2}}/2$ (recall that
$\mathrm{Lip}(f)<\sqrt{3}$).

According to [But14, Theorem 2.1] (by taking $V\equiv 1$, $\varphi(t)=t$ and
$K\geq 1$) the relation in (A3) implies that

  * (i)

$\\{Z_{n}\\}_{n\geq 0}$ admits a unique invariant probability measure
$\uppi(\mathrm{d}z)$;

  * (ii)

there are $C_{1},C_{2}>0$ such that

(1.2)
$\mathscr{W}\bigl{(}\mathcal{P}^{n}(z,\mathrm{d}\bar{z}),\uppi(\mathrm{d}\bar{z})\bigr{)}\leq
C_{1}\mathrm{e}^{-C_{2}n}.$

Before stating the main results of this article, we introduce some notation we
need. For $n\in\mathbb{N}$, $z\in\mathsf{Z}$ and $h\in\mathscr{H}$, let
$\hat{\rm er}_{n}(h)\coloneqq\frac{1}{n}\sum_{i=0}^{n-1}\ell_{h}(Z_{i})$,
${\rm er}_{\uppi}(h)\coloneqq\uppi(\ell_{h})$,
$\ell_{h}^{\uppi}(z)\coloneqq\ell_{h}(z)-{\rm er}_{\uppi}(h)$ and ${\rm
opt}_{\uppi}(\mathscr{H})\coloneqq\inf_{h\in\mathscr{H}}{\rm er}_{\uppi}(h)$.
Observe that, according to (A2) and boundedness of $\uprho$, ${\rm
er}_{\uppi}(h)$ and $\ell_{h}^{\uppi}(z)$ are well defined. Next, for
$\varepsilon>0$ the $\varepsilon$-ASEM algorithm for $\mathscr{H}$ is defined
as a mapping
$\mathcal{A}^{\varepsilon}:\bigcup_{n=1}^{\infty}\mathsf{Z}^{n}\to\mathscr{H}$
satisfying

$\frac{1}{n}\sum_{i=0}^{n-1}\ell_{\mathcal{A}^{\varepsilon}(z_{0},\dots,z_{n-1})}(z_{i})<\inf_{h\in\mathscr{H}}\frac{1}{n}\sum_{i=0}^{n-1}\ell_{h}(z_{i})+\varepsilon.$

######  Theorem 1.1.

Assume (A1)-(A3), and fix $\varepsilon>0$ and $\delta\in(0,1)$. Then, for any
initial distribution $\upmu$ of $\\{Z_{n}\\}_{n\geq 0}$,

$\mathbb{P}_{\upmu}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|<5\varepsilon\right)\geq
1-\delta,\qquad\forall\,n\geq n_{1}(\varepsilon,\delta),$

where

$n_{1}(\varepsilon,\delta)\coloneqq\max\left\\{\frac{16C_{1}L}{\varepsilon(1-\mathrm{e}^{-C_{2}})},\frac{128C_{1}^{2}L^{2}\ln\frac{\mathcal{N}(\varepsilon/4\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}{\delta}}{\varepsilon^{2}(1-\mathrm{e}^{-C_{2}})^{2}}\right\\}.$

The main step in the proof of Theorem 1.1 is the following sample error
uniform convergence result

$\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)\leq\mathcal{N}(\varepsilon/4\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})\mathrm{e}^{-\bigl{(}\frac{\varepsilon
n(1-\mathrm{e}^{-C_{2}})}{4C_{1}L}-2\bigr{)}^{2}/(2n)},\quad\ \ \
\forall\,n\geq\frac{8C_{1}L}{\varepsilon(1-\mathrm{e}^{-C_{2}})},$

(see eq. 2.4). Notice that in the case when
$\mathcal{N}(\varepsilon,\mathscr{H},\mathsf{d}_{\mathscr{H}})=\mathrm{e}^{C\varepsilon^{-2d/\gamma}}$
(see eq. 1.1) the sample size (in the above relation or Theorem 1.1) is of
order $\varepsilon^{-(2+2d/\gamma)}$. On the oder hand, one expects that the
sample size $n$ needed to ensure that $(1+\alpha)\hat{\rm
er}_{n}(h)+\varepsilon\geq\mathrm{er}_{\uppi}(h)$ for some
$\alpha,\varepsilon>0$ is of much smaller order. This problem was studied in
[AB99, Subsection 5.5]. Crucial step in the proof of this result is to study
the uniform relative error

$\sup_{h\in\mathscr{H}}\frac{\left|\mathrm{er}_{\uppi}(h)-\hat{\rm
er}_{n}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}},$

instead of the uniform standard error

$\sup_{h\in\mathscr{H}}\left|\mathrm{er}_{\uppi}(h)-\hat{\rm
er}_{n}(h)\right|.$

Studying this quantity is additionally motivated by the observation that a
uniform convergence bound fails to capture the phenomenon that for those
functions $h\in\mathscr{H}$ for which the true error $\mathrm{er}_{\uppi}(h)$
is small, the deviation $\mathrm{er}_{\uppi}(h)-\hat{\rm er}_{n}(h)$ is also
small with large probability. However, the relative deviation
$(\mathrm{er}_{\uppi}(h)-\hat{\rm er}_{n}(h))/\sqrt{\mathrm{er}_{\uppi}(h)}$
is more appropriate for capturing this phenomenon (see [ZZX09, Section 4]).
With relative error we penalize the difference between the sample error and
the true error much more when the true error is very small in the first place.
Notice that if there is an exact functional relationship between the input and
the output observable, and if this function is in the class $\mathscr{H}$,
then the logic behind the relative error tells us that every function (except
the true one) is infinitely worse than the true one. Hence, studying relative
error makes sense only when the true error is bounded away from zero. Even
though this assumption does seem a bit unnatural, in many practical
applications there will not even be a true function in the background, but
some distribution, and even if there will be a functional relationship between
the input and the output observable, this relationship can often be pretty
complex and hence not contained in the class $\mathscr{H}$.

######  Theorem 1.2.

Assume (A1)-(A3) and assume additionally that there exist constants $m,M>0$
such that

(1.3)
$m\leq\inf_{h\in\mathscr{H}}\mathrm{er}_{\uppi}(h)\leq\sup_{h\in\mathscr{H}}\mathrm{er}_{\uppi}(h)\leq
M.$

Fix $\varepsilon>0$ and $\delta\in(0,1)$. Then , for any initial distribution
$\upmu$ of $\\{Z_{n}\\}_{n\geq 0}$,

$\mathbb{P}_{\upmu}\left(\sup_{h\in\mathscr{H}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\varepsilon\right)\leq\delta,\qquad\forall\,n\geq
n_{2}(\varepsilon,\delta),$

where

$n_{2}(\varepsilon,\delta)\coloneqq\max\left\\{\frac{2C_{1}L}{\varepsilon(\sqrt{m}\wedge
1)(1-\mathrm{e}^{-C_{2}})},\frac{1}{\xi_{1}\varepsilon^{2}}\left(\xi_{2}\varepsilon+\ln\left(\frac{4\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}{\delta}\right)\right)\right\\}$

and

$\xi_{1}=\frac{49m^{4}(1-\mathrm{e}^{-C_{2}})^{2}}{72M(M+6m)^{2}C_{1}^{2}L^{2}},\qquad\xi_{2}=\frac{7m^{2}(1-\mathrm{e}^{-C_{2}})}{6\sqrt{M}(M+6m)C_{1}L}.$

As a consequence of Theorem 1.2 we conclude the following.

######  Corollary 1.3.

Assume (A1)-(A3) and eq. 1.3. Fix $\alpha,\varepsilon>0$ and $\delta\in(0,1)$.
Then, for any initial distribution $\upmu$ of $\\{Z_{n}\\}_{n\geq 0}$,

$\mathbb{P}_{\upmu}\left(\exists\,h\in\mathscr{H}:\mathrm{er}_{\uppi}(h)>(1+\alpha)\hat{\rm
er}_{n}(h)+\varepsilon\right)\leq\delta,\qquad\forall\,n\geq
n_{3}(\varepsilon,\delta),$

where

$\displaystyle n_{3}(\varepsilon,\delta)$
$\displaystyle\coloneqq\max\left\\{\frac{2C_{1}L\sqrt{1+1/\alpha}}{\sqrt{\varepsilon}(\sqrt{m}\wedge
1)(1-\mathrm{e}^{-C_{2}})},\right.$
$\displaystyle\qquad\left.\frac{\alpha+1}{\alpha\xi_{1}}\cdot\frac{1}{\varepsilon}\left(\frac{\xi_{2}}{\sqrt{1+1/\alpha}}\cdot\varepsilon^{1/2}+\ln\left(\frac{4\mathcal{N}\left(\frac{\varepsilon^{1/2}}{\bar{L}\sqrt{1+1/\alpha}},\mathscr{H},\mathsf{d}_{\mathscr{H}}\right)}{\delta}\right)\right)\right\\},$

and constants $\xi_{1}$ and $\xi_{2}$ are as in Theorem 1.2.

######  Remark 1.4.

Notice that for
$\mathcal{N}(\varepsilon,\mathscr{H},\mathsf{d}_{\mathscr{H}})=\mathrm{e}^{C\varepsilon^{-2d/\gamma}}$,
we need to have $n$ of order $\varepsilon^{-(1+d/\gamma)}$ (which is much
smaller than $\varepsilon^{-(2+2d/\gamma)}$).

###  1.1. Literature review

Our work contributes to the understanding of statistical properties of
supervised learning problems. Most of the existing literature focuses on the
case when the training data set is drawn from an i.i.d. sample, see the
classical monographs [AB99] and [SSBD14]. However, many practical supervised
learning problems (e.g. speech recognition, object tracking, market
prediction, etc.) are characterized by temporal dependence and strong
correlation between the marginals of the data-generating process, suggesting
that the i.i.d. assumption is not always justified. This problem has been
first addressed in [Yu94], [Mei00] and [Vid03] in the context of stationary
$\beta$-mixing sequences, and in [MM96] in the case of stationary
$m$-dependent $\alpha$-mixing sequences. In [SHS09] the authors relax the
stationarity assumption and require that the data-generating process satisfies
a certain law of large numbers only. This, for example, includes (not
necessarily stationary) $\alpha$-mixing sequences and Markov chains satisfying
the Doeblin condition. Recall that the Doeblin condition implies
irreducibility, aperiodicity and uniform exponential ergodicity of the chain
(see [MT09, Theorem 16.0.2]). The learning problem of the later model was
further investigated in a series of articles [Gam03], [ZZX09], [ZLX12],
[ZLX+13] and [ZXX14]. We remark that a crucial step in all these works is the
Hoeffding’s inequality for uniformly ergodic Markov chains, obtained in
[GO02]. Generalization of these results to irreducible aperiodic
$\mathcal{V}$-ergodic Markov chains has been obtained in [ZXX14]. Actually the
proof of the main results of this article (Theorems 1 and 2) is taken from
[Vid03, Theorem 3.5]. We also remark that these results do not give
generalization bounds in the full sense. Namely, a crucial assumption in the
article is that the data-generating process starts from its invariant measure,
which is unrealistic. A way to partly fix this gap is presented below.

Recall that the chain $\\{Z_{n}\\}_{n\geq 0}$ is said to be

  1. (i)

irreducible if there exists a $\sigma$-finite measure $\upvarphi(\mathrm{d}z)$
on $\mathsf{Z}$ such that whenever $\upvarphi(B)>0$ we have
$\sum_{n=0}^{\infty}\mathcal{P}^{n}(z,B)>0$ for all $z\in\mathsf{Z}$;

  2. (ii)

aperiodic if there does not exist a partition
$\\{B_{1},\dots,B_{k}\\}\subseteq\mathfrak{B}(\mathsf{Z})$ with $k\geq 2$ of
$\mathsf{Z}$ such that $\mathcal{P}(z,B_{i+1})=1$ for all $z\in B_{i}$ and all
$1\leq i\leq k-1$, and $\mathcal{P}(z,B_{1})=1$ for all $z\in B_{k}$.

  3. (iii)

$\mathcal{V}$-ergodic if it admits an invariant probability measure
$\uppi(\mathrm{d}z)$ and there are $\mathcal{V}:\mathsf{Z}\to[1,\infty)$ with
$\int_{\mathsf{Z}}\mathcal{V}(z)\uppi(\mathrm{d}z)<\infty$, $C>0$ and
$\kappa\in(0,1)$, such that

(1.4)
$\lVert\mathcal{P}^{n}(z,\mathrm{d}\bar{z})-\uppi(\mathrm{d}\bar{z})\rVert_{\mathcal{V}}\leq
C\mathcal{V}(z)\kappa^{n}$

for all $z\in\mathsf{Z}$ and $n\geq 0$.

Here, for a signed measure $\upmu(\mathrm{d}\mathsf{z})$ on $\mathsf{Z}$,

$\lVert\upmu(\mathrm{d}z)\rVert_{\mathcal{V}}\coloneqq\sup_{|f|\leq\mathcal{V}}|\upmu(f)|.$

Further, the $\beta$-mixing (or complete regularity, or the Kolmogorov)
coefficient of the chain $\\{Z_{n}\\}_{n\geq 0}$ with initial distribution
$\upmu(\mathrm{d}z)$ is defined as

$\beta^{\upmu}(n)\coloneqq\sup_{m\geq
0}\mathbb{E}_{\mu}\left[\sup_{B\in\sigma\\{Z_{k}:k\geq
m+n\\}}|\mathbb{P}_{\upmu}(B|\mathcal{F}_{m})-\mathbb{P}_{\upmu}(B)|\right].$

If $\uppi(\mathrm{d}z)$ is an invariant probability measure of
$\\{Z_{n}\\}_{n\geq 0}$, then, by employing the Markov property and
stationarity,

$\beta^{\uppi}(n)=\int_{\mathsf{Z}}\lVert\mathcal{P}^{n}(z,\mathrm{d}\bar{z})-\uppi(\mathrm{d}\bar{z})\rVert_{\mathrm{TV}}\uppi(\mathrm{d}z).$

In particular, if $\\{Z_{n}\\}_{n\geq 0}$ is $\upvarphi$-irreducible,
aperiodic and $\mathcal{V}$-ergodic with invariant probability measure
$\uppi(\mathrm{d}z)$, then

$\beta^{\uppi}(n)\leq\int_{\mathsf{Z}}\lVert\mathcal{P}^{n}(z,\mathrm{d}\bar{z})-\uppi(\mathrm{d}\bar{z})\rVert_{\mathcal{V}}\uppi(\mathrm{d}z)\leq
C\uppi(\mathcal{V})\kappa^{n}$

for all $n\geq 0.$ Under this assumptions, (A1) and

($\overline{\text{A2}})$:

$\displaystyle
B\coloneqq\sup_{z\in\mathsf{Z},\,h\in\mathscr{H}}\ell_{h}(z)<\infty$ and
$\displaystyle|\ell_{h_{1}}(z)-\ell_{h_{2}}(z)|\leq\bar{L}\uprho_{\mathscr{H}}(h_{1},h_{2})$
for some $\bar{L}>0$, and all $z\in\mathsf{Z}$ and $h_{1},h_{2}\in\mathscr{H}$

in [ZXC12, Theorem 2] (as we have already commented, the proof of this result
has been taken from [Vid03, Theorem 3.5]) it has been shown that for fixed
$\varepsilon\in(0,3B)$,

$\displaystyle\mathbb{P}_{\uppi}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)$
$\displaystyle\leq
2(1+C\uppi(\mathcal{V})\mathrm{e}^{-2})\mathcal{N}(\varepsilon/4\bar{L},\mathscr{H},\uprho_{\mathscr{H}})\mathrm{e}^{-\frac{\sqrt{n}\sqrt{\ln(\kappa^{-1})}\varepsilon^{2}}{16\sqrt{2}B^{2}}}$

for all

$n\geq
n_{0}(\varepsilon)\coloneqq\max\left\\{\frac{16+8\sqrt{4+\ln(\kappa^{-1})^{2}}+8\ln(\kappa^{-1})^{2}}{\ln(\kappa^{-1})^{2}},\frac{\ln(\kappa^{-1})}{8}\right\\}.$

From this it follows (see the proof of Theorem 1.1) that for fixed
$\varepsilon>0$ and $\delta\in(0,1)$, and an $\varepsilon$-ASEM algorithm
$\mathcal{A}^{\varepsilon}$ for $\mathscr{H}$, we have that

(1.5)
$\mathbb{P}_{\uppi}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|<5\varepsilon\right)\geq
1-\delta\qquad\forall\,n\geq n_{0}(\varepsilon,\delta),$

where

$n_{0}(\varepsilon,\delta)\coloneqq\max\left\\{n_{0}(\varepsilon),\frac{512B^{4}}{\ln(\kappa^{-1})\varepsilon^{4}}\ln\left(\frac{2(1+C\uppi(\mathcal{V})\mathrm{e}^{-2})\mathcal{N}(\varepsilon/4\bar{L},\mathscr{H},\uprho_{\mathscr{H}})}{\delta}\right)^{2}\right\\}.$

However, as we have already commented, this result is restrictive and
impractical since it assumes that the process is initially distributed
according to the invariant distribution $\uppi(\mathrm{d}z)$ which is in
general unknown to us. It is more natural, and in the spirit of generalization
bounds, that the relation in eq. 1.5 holds for every initial distribution of
$\\{Z_{n}\\}_{n\geq 0}$. This result can be slightly generalized by employing
(i) Hölder inequality, or (ii) ergodicity property in eq. 1.4.

  * (i)

Let $\upmu(\mathrm{d}z)$ be any initial distribution of $\\{Z_{n}\\}_{n\geq
0}$ such that $\upmu\ll\uppi$. Assume also that there is $p\in(1,\infty]$ such
that $\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}\in\mathrm{L}^{p}(\uppi)$. Then,

$\displaystyle\mathbb{P}_{\upmu}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)$
$\displaystyle=\int_{\mathsf{Z}}\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)\upmu(\mathrm{d}z)$
$\displaystyle=\int_{\mathsf{Z}}\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}(z)\uppi(\mathrm{d}z)$
$\displaystyle\leq\bigl{\lVert}\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}\bigr{\rVert}_{p}\left(\int_{\mathsf{Z}}\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)^{q}\uppi(\mathrm{d}z)\right)^{1/q}$
$\displaystyle\leq\bigl{\lVert}\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}\bigr{\rVert}_{p}\mathbb{P}_{\uppi}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)^{1/q},$

where $q\in[1,\infty)$ is such that $1/p+1/q=1$. Thus, for fixed
$\varepsilon>0$ and $\delta\in(0,1)$, and an $\varepsilon$-ASEM algorithm
$\mathcal{A}^{\varepsilon}$ for $\mathscr{H}$, we have that

$\mathbb{P}_{\upmu}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|<5\varepsilon\right)\geq
1-\delta$

for all

$n\geq\max\left\\{n_{0}(\varepsilon,\delta),\frac{512B^{4}q^{2}}{\ln(\kappa^{-1})\varepsilon^{4}}\ln\left(\frac{\bigl{(}2(1+C\uppi(\mathcal{V})\mathrm{e}^{-2})\mathcal{N}(\varepsilon/4\bar{L},\mathscr{H},\uprho_{\mathscr{H}})\bigr{)}^{1/q}\bigl{\lVert}\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}\bigr{\rVert}_{p}}{\delta}\right)^{2}\right\\}.$

  * (ii)

Let now $\upmu(\mathrm{d}z)$ be any initial distribution of
$\\{Z_{n}\\}_{n\geq 0}$ such that $\upmu(\mathcal{V})<\infty$. Fix
$\varepsilon>0$ and $\delta\in(0,1)$, and let $\mathcal{A}^{\varepsilon}$ be
an $\varepsilon$-ASEM algorithm for $\mathscr{H}$. Then, for any $n\geq
n_{0}(\varepsilon,\delta)$ the relation in eq. 1.5 implies

$\displaystyle\mathbb{P}_{\upmu}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{n},\dots,Z_{2n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)$
$\displaystyle\leq\mathbb{P}_{\uppi}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)$ $\displaystyle\ \ \
+\bigl{|}\mathbb{P}_{\upmu}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{n},\dots,Z_{2n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)$ $\displaystyle\hskip
28.45274pt-\mathbb{P}_{\uppi}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)\bigr{|}$
$\displaystyle<\delta+\big{|}\mathbb{E}_{\upmu}\bigl{[}\mathbb{P}_{Z_{n}}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)\bigr{]}$ $\displaystyle\hskip
36.98866pt-\mathbb{E}_{\uppi}\bigl{[}\mathbb{P}_{Z_{n}}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)\bigr{]}\big{|}$
$\displaystyle\leq\delta+\left|\int_{\mathsf{Z}}\mathbb{P}_{z}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)\bigl{(}\upmu\mathcal{P}^{n}(\mathrm{d}z)-\uppi(\mathrm{d}z)\bigr{)}\right|$
$\displaystyle\leq\delta+\lVert\upmu\mathcal{P}^{n}(\mathrm{d}z)-\uppi(\mathrm{d}z)\rVert_{\mathrm{TV}}$
$\displaystyle\leq\delta+C\upmu(\mathcal{V})\kappa^{n}.$

In addition to the above assumptions assume that $\\{Z_{n}\\}_{n\geq 0}$ is
also reversible, i.e.

$\int_{A}\mathcal{P}(z,B)\uppi(\mathrm{d}z)=\int_{B}\mathcal{P}(z,A)\uppi(\mathrm{d}z)\qquad\forall\,A,B\in\mathfrak{B}(\mathsf{Z}).$

Then, according to [KM12, Lemma 2.2] and [RR97, Theorem 2.1], it admits a
spectral gap in $\mathrm{L}^{2}(\uppi)$, i.e.

$\lambda\coloneqq\sup_{f\in\mathrm{L}^{2}(\uppi),\,\lVert
f\rVert_{2}=1}\lVert\mathcal{P}f-\uppi(f)\rVert_{2}<1.$

Now, from [Mia14, Theorem 3.3] it follows that

$\mathbb{P}_{\uppi}\bigl{(}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\bigr{)}\leq\mathrm{e}^{-2\frac{1-\lambda}{1+\lambda}\varepsilon^{2}n}\qquad\forall\,n\geq
0.$

From this, analogously as in the proof of Theorem 1.1, we conclude that

$\displaystyle\mathbb{P}_{\uppi}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)$
$\displaystyle\leq\mathcal{N}(\varepsilon/4\bar{L},\mathscr{H},\uprho_{\mathscr{H}})\mathrm{e}^{-\frac{1-\lambda}{2(1+\lambda)}\varepsilon^{2}n}\qquad\forall\,n\geq
0.$

Let $\upmu(\mathrm{d}z)$ be any initial distribution of $\\{Z_{n}\\}_{n\geq
0}$ such that $\upmu\ll\uppi$ and
$\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}\in\mathrm{L}^{p}(\uppi)$ for some
$p\in(1,\infty]$. Then,

$\displaystyle\mathbb{P}_{\upmu}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)$
$\displaystyle\leq\bigl{\lVert}\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}\bigr{\rVert}_{p}\mathbb{P}_{\uppi}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\varepsilon\right)^{1/q},$

where again $q\in[1,\infty)$ is such that $1/p+1/q=1$. From this it follows
that for $\varepsilon>0$, $\delta\in(0,1)$ and an $\varepsilon$-ASEM algorithm
$\mathcal{A}^{\varepsilon}$ for $\mathscr{H}$, we have that

$\mathbb{P}_{\upmu}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|<5\varepsilon\right)\geq
1-\delta$

for all

$n\geq\frac{2q(1+\lambda)}{(1-\lambda)}\log\left(\frac{\bigl{\lVert}\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}\bigr{\rVert}_{p}\mathcal{N}(\varepsilon/4\bar{L},\mathscr{H},\uprho_{\mathscr{H}})^{1/q}}{\delta}\right).$

Additionally, if $p=2$ from [KM12, Proposition 1.5] we conclude

$\displaystyle\mathbb{P}_{\upmu}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{n},\dots,Z_{2n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)$
$\displaystyle\leq\mathbb{P}_{\uppi}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)$ $\displaystyle\ \ \
+\bigl{|}\mathbb{P}_{\upmu}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{n},\dots,Z_{2n-1})\bigr{)}-\mathrm{opt}_{\uppi}(\mathscr{H})|\geq
5\varepsilon\right)$ $\displaystyle\hskip
28.45274pt-\mathbb{P}_{\uppi}\left(|\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}-\mathrm{opt}_{\upmu}(\mathscr{H})|\geq
5\varepsilon\right)\bigr{|}$
$\displaystyle\leq\delta+\lVert\upmu\mathcal{P}^{n}(\mathrm{d}z)-\uppi(\mathrm{d}z)\rVert_{\mathrm{TV}}$
$\displaystyle\leq\delta+\frac{1}{2}\left(\int_{\mathsf{Z}}\left(1-\frac{\mathrm{d}\upmu}{\mathrm{d}\uppi}(z)\right)^{2}\uppi(\mathrm{d}z)\right)^{1/2}(1-\lambda)^{n}$

for all

$n\geq\frac{2(1+\lambda)}{(1-\lambda)}\log\left(\frac{\mathcal{N}(\varepsilon/4\bar{L},\mathscr{H},\uprho_{\mathscr{H}})}{\delta}\right).$

##  2\. Proof of the main results

In this section, we prove Theorems 1.1 and 1.2.

### Proof of Theorem 1.1

Fix $h\in\mathscr{H}$ and $z_{0}\in\mathsf{Z}$. Then, (A2) and the boundedness
of the metric $\rho$ on $\mathsf{Z}$, imply that
$\lVert\ell^{\uppi}_{h}\rVert_{\infty}\leq 2\lVert\ell_{h}\rVert_{\infty}\leq
2\sup_{z_{1},z_{2}\in\mathsf{Z}}\uprho(z_{1},z_{2})+2|\ell_{h}(z_{0})|<\infty$,
$\uppi(\ell^{\uppi}_{h})=0$, $\ell_{h}$ and $\ell^{\uppi}_{h}$ are Lipschitz
continuous, and $\mathrm{Lip}(\ell^{\uppi}_{h})=\mathrm{Lip}(\ell_{h})$.
Further, by employing Kantorovich-Rubinstein theorem, for any
$z\in\mathsf{Z}$, from eq. 1.2 it follows that

$\mathbb{E}_{z}\bigl{[}\ell_{h}^{\uppi}(Z_{n})\bigr{]}\leq\mathrm{Lip}(\ell^{\uppi}_{h})\mathscr{W}\bigl{(}\mathcal{P}^{n}(z,\mathrm{d}\bar{z}),\uppi(\mathrm{d}\bar{z})\bigr{)}\leq
C_{1}\mathrm{Lip}(\ell_{h})\mathrm{e}^{-C_{2}n}\leq
C_{1}L\mathrm{e}^{-C_{2}n},$

where in the last line we used assumption (A2), more precisely, we used that
$|\ell_{h}(z_{1})-\ell_{h}(z_{2})|\leq L\rho(z_{1},z_{2})$. Thus, the function

(2.1) $g(z)\coloneqq\sum_{n\geq
0}\mathbb{E}_{z}\bigl{[}\ell_{h}^{\uppi}(Z_{n})\bigr{]}$

is well defined. Furthermore, the function $g(z)$ satisfies

(2.2) $\lVert g\rVert_{\infty}\leq C_{1}L/(1-\mathrm{e}^{-C_{2}})$

and solves the equation

(2.3) $g(z)-\mathbb{E}_{z}\bigl{[}g(Z_{1})\bigr{]}=\ell_{h}^{\uppi}(z).$

Set now $W_{i}\coloneqq\ell_{h}(Z_{i})$ and
$S_{n}\coloneqq\sum_{i=0}^{n-1}W_{i}$ for $i\geq 0$ and $n\geq 1$. Thus,

$S_{n}-n\,\uppi(\ell_{h})=n\,\hat{\mathrm{er}}_{n}(h)-n\,\mathrm{er}_{\uppi}(h).$

Fix now arbitrary $\epsilon>0$. Analogously as in the proof of [GO02, Theorem
2] we see that

$\displaystyle\mathbb{P}_{z}\bigl{(}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>\epsilon\bigr{)}$
$\displaystyle=\mathbb{P}_{z}\bigl{(}|S_{n}-n\,\uppi(\ell_{h})|>n\epsilon\bigr{)}$
$\displaystyle\leq\mathrm{e}^{-(\epsilon n/\lVert
g\rVert_{\infty}-2)^{2}/(2n)}$
$\displaystyle\leq\mathrm{e}^{-\bigl{(}\frac{\epsilon
n(1-\mathrm{e}^{-C_{2}})}{2C_{1}L}-2\bigr{)}^{2}/(2n)}\qquad\forall
n\geq\frac{4C_{1}L}{\epsilon(1-\mathrm{e}^{-C_{2}})}.$

Further, let
$\mathscr{C}_{\epsilon}=\\{h_{1},\dots,h_{\mathcal{N}(\epsilon,\mathscr{H},\mathsf{d}_{\mathscr{H}})}\\}$
be the $\epsilon$-cover of $\mathscr{H}$. Thus, for any $h\in\mathscr{H}$
there is $h_{i}\in\mathscr{C}_{\epsilon}$ such that
$\mathsf{d}_{\mathscr{H}}(h,h_{i})<\epsilon$. We now have,

$\displaystyle\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>4\bar{L}\epsilon\right)$
$\displaystyle\leq\mathbb{P}_{z}\left(\bigcup_{i=1}^{\mathcal{N}(\epsilon,\mathscr{H},\mathsf{d}_{\mathscr{H}})}\left\\{\sup_{h\in\\{\bar{h}:\mathsf{d}_{\mathscr{H}}(\bar{h},h_{i})<\epsilon\\}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>4\bar{L}\epsilon\right\\}\right)$
$\displaystyle\leq\sum_{i=1}^{\mathcal{N}(\epsilon,\mathscr{H},\mathsf{d}_{\mathscr{H}})}\mathbb{P}_{z}\left(\sup_{h\in\\{\bar{h}:\mathsf{d}_{\mathscr{H}}(\bar{h},h_{i})<\epsilon\\}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>4\bar{L}\epsilon\right).$

For $h\in\\{\bar{h}:\mathsf{d}_{\mathscr{H}}(\bar{h},h_{i})<\epsilon\\}$, from
(A2), it follows that

$|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)-\hat{\mathrm{er}}_{n}(h_{i})+\mathrm{er}_{\uppi}(h_{i})|\leq
2\bar{L}\uprho_{\mathscr{H}}(h,h_{i})<2\bar{L}\epsilon.$

Thus,

$\displaystyle\mathbb{P}_{z}\left(\sup_{h\in\\{\bar{h}:\mathsf{d}_{\mathscr{H}}(\bar{h},h_{i})<\epsilon\\}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>4\bar{L}\epsilon\right)$
$\displaystyle\leq\mathbb{P}_{z}\left(|\hat{\mathrm{er}}_{n}(h_{i})-\mathrm{er}_{\uppi}(h_{i})|>2\bar{L}\epsilon\right)$
$\displaystyle\leq\mathrm{e}^{-\bigl{(}\frac{\epsilon\bar{L}n(1-\mathrm{e}^{-C_{2}})}{C_{1}L}-2\bigr{)}^{2}/(2n)}\qquad\forall
n\geq\frac{2C_{1}L}{\bar{L}\epsilon(1-\mathrm{e}^{-C_{2}})},$

which implies

(2.4)
$\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|>4\bar{L}\epsilon\right)\leq\mathcal{N}(\epsilon,\mathscr{H},\mathsf{d}_{\mathscr{H}})\mathrm{e}^{-\bigl{(}\frac{\epsilon\bar{L}n(1-\mathrm{e}^{-C_{2}})}{C_{1}L}-2\bigr{)}^{2}/(2n)}\\\
$

for all $n\geq 2C_{1}L/\bar{L}\epsilon(1-\mathrm{e}^{-C_{2}})$.

Finally, set $\varepsilon\coloneqq 4\bar{L}\epsilon$, let
$\mathcal{A}^{\varepsilon}$ be the $\varepsilon$-ASEM algorithm for
$\mathscr{H}$, and fix $\delta\in(0,1)$. Then,

$\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}|\hat{\mathrm{er}}_{n}(h)-\mathrm{er}_{\uppi}(h)|\leq\varepsilon\right)\geq
1-\delta\qquad\forall n\geq n_{1}(\varepsilon,\delta).$

Consequently, for all $n\geq n_{0}(\varepsilon,\delta)$ it follows that with
probability at least $1-\delta$,

$\displaystyle\mathrm{er}_{\uppi}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}$
$\displaystyle\leq\mathrm{er}_{\uppi}(h_{(Z_{0},\dots,Z_{n-1})})+\varepsilon/4$
$\displaystyle\leq\hat{\mathrm{er}}_{n}(h_{(Z_{0},\dots,Z_{n-1})})+5\varepsilon/4$
$\displaystyle\leq\hat{\mathrm{er}}_{n}\bigl{(}\mathcal{A}^{\varepsilon}(Z_{0},\dots,Z_{n-1})\bigr{)}+6\varepsilon/4$
$\displaystyle\leq\inf_{h\in\mathscr{H}}\hat{\mathrm{er}}_{n}(h)+10\varepsilon/4$
$\displaystyle\leq\hat{\mathrm{er}}_{n}(\bar{h})+5\varepsilon/2$
$\displaystyle\leq\hat{\mathrm{er}}_{n}(h_{i})+11\varepsilon/4$
$\displaystyle\leq\mathrm{er}_{\uppi}(h_{i})+15\varepsilon/4$
$\displaystyle\leq\mathrm{er}_{\uppi}(\bar{h})+4\varepsilon$
$\displaystyle<\mathrm{opt}_{\uppi}(\mathscr{H})+5\varepsilon,$

where $h_{(Z_{0},\dots,Z_{n-1})}\in\mathscr{C}_{\varepsilon/4\bar{L}}$,
$\bar{h}\in\mathscr{H}$ is such that
$\mathrm{er}_{\uppi}(\bar{h})<\mathrm{opt}_{\uppi}(\mathscr{H})+\varepsilon$,
and $h_{i}\in\mathscr{C}_{\varepsilon/4\bar{L}}$ such that
$\mathsf{d}_{\mathscr{H}}(\bar{h},h_{i})<\varepsilon/4\bar{L}$. ∎

### Proof of Theorem 1.2

We again follow the proof of [GO02, Theorem 2]. For $i\geq 0$ and
$z\in\mathsf{Z}$, set

$D_{i}\coloneqq g(Z_{i})-\mathbb{E}_{z}[g(Z_{i})\mid
Z_{0},\ldots,Z_{i-1}]=g(Z_{i})-\mathbb{E}_{Z_{i-1}}[g(Z_{1})].$

Recall that the function $g(z)$ is given by eq. 2.1. Since
$\mathbb{E}[D_{i}]=0$ for all $i\geq 0$, $\\{D_{i}\\}_{i\geq 0}$ is a
martingale difference sequence. Using Markov property and eq. 2.3 we get

$S_{n}-n\,\uppi(\ell_{h})=\sum_{i=1}^{n}D_{i}+g(Z_{0})-g(Z_{n})\leq\sum_{i=1}^{n}D_{i}+2\lVert
g\rVert_{\infty}.$

From this it follows that

$\displaystyle\mathbb{E}_{z}\left[\mathrm{e}^{\theta(S_{n}-n\,\uppi(\ell_{h}))}\right]$
$\displaystyle\leq\mathrm{e}^{2\theta\lVert
g\rVert_{\infty}}\mathbb{E}_{z}\left[\mathrm{e}^{\theta\sum_{i=1}^{n}D_{i}}\right]$
$\displaystyle=\mathrm{e}^{2\theta\lVert
g\rVert_{\infty}}\mathbb{E}_{z}\left[\mathrm{e}^{\theta\sum_{i=1}^{n-1}D_{i}}\mathbb{E}\left[\mathrm{e}^{\theta
D_{n}}\mid Z_{0},\ldots,Z_{n-1}\right]\right].$

Since $|D_{n}|\leq 2\lVert g\rVert_{\infty}$, applying [DGL96, Lemma 8.1] with
expectation conditional to $Z_{0},\ldots,Z_{n-1}$, $a=-2\lVert
g\rVert_{\infty}$ and $b=2\lVert g\rVert_{\infty}$ gives us

$\mathbb{E}_{z}\left[\mathrm{e}^{\theta D_{n}}\mid
Z_{0},\ldots,Z_{n-1}\right]\leq\mathrm{e}^{2\theta^{2}\lVert
g\rVert_{\infty}^{2}}.$

Iterating this procedure results in

$\mathbb{E}_{z}\left[\mathrm{e}^{\theta\sum_{i=1}^{n}D_{i}}\right]\leq\mathrm{e}^{2n\theta^{2}\lVert
g\rVert_{\infty}^{2}}.$

Hence, we have

$\mathbb{E}_{z}\left[\mathrm{e}^{\theta(S_{n}-n\,\uppi(\ell_{h}))}\right]\leq\mathrm{e}^{2\theta\lVert
g\rVert_{\infty}+2n\theta^{2}\lVert g\rVert_{\infty}^{2}}.$

Using Markov’s inequality, we get

$\mathbb{P}_{z}\left(S_{n}-n\,\uppi(\ell_{h})\geq
n\varepsilon\right)\leq\frac{\mathbb{E}_{z}\left[\mathrm{e}^{\theta(S_{n}-n\,\uppi(\ell_{h}))}\right]}{\mathrm{e}^{\theta
n\varepsilon}}\leq\mathrm{e}^{2n\lVert g\rVert_{\infty}^{2}\theta^{2}+(2\lVert
g\rVert_{\infty}-n\varepsilon)\theta}.$

Notice that if we define $D_{i}$ as

$D_{i}\coloneqq\mathbb{E}_{z}\left[g(Z_{i})\mid
Z_{0},\ldots,Z_{i-1}\right]-g(Z_{i})$

and repeat the same steps, we would get

$\mathbb{P}_{z}\left(n\,\uppi(\ell_{h})-S_{n}\geq
n\varepsilon\right)\leq\mathrm{e}^{2n\lVert
g\rVert_{\infty}^{2}\theta^{2}+(2\lVert
g\rVert_{\infty}-n\varepsilon)\theta}.$

Therefore

$\displaystyle\mathbb{P}_{z}\left(|S_{n}-n\,\uppi(\ell_{h})|\geq
n\varepsilon\right)$
$\displaystyle=\mathbb{P}_{z}\left(S_{n}-n\,\uppi(\ell_{h})\geq
n\varepsilon\right)+\mathbb{P}_{z}\left(n\,\uppi(\ell_{h})-S_{n}\geq
n\varepsilon\right)$ $\displaystyle\leq 2\mathrm{e}^{2n\lVert
g\rVert_{\infty}^{2}\theta^{2}+(2\lVert
g\rVert_{\infty}-n\varepsilon)\theta}.$

This relation holds for all $\theta>0$. The best bound is obtained for
$\theta$ that minimizes the function $\theta\mapsto 2n\lVert
g\rVert_{\infty}^{2}\theta^{2}+(2\lVert g\rVert_{\infty}-n\varepsilon)\theta$.
It is easy to see that the value of $\theta$ that minimizes this function is

$\theta_{n}=\frac{n\varepsilon-2\lVert g\rVert_{\infty}}{4n\lVert
g\rVert_{\infty}^{2}}.$

Hence,

$\mathbb{P}_{z}\left(|S_{n}-n\,\uppi(\ell_{h})|\geq n\varepsilon\right)\leq
2\mathrm{exp}\left(-\frac{(n\varepsilon-2\lVert
g\rVert_{\infty})^{2}}{8n\lVert g\rVert_{\infty}^{2}}\right).$

Using eq. 2.2, for every
$n\geq\frac{2C_{1}L}{\varepsilon(1-\mathrm{e}^{-C_{2}})}$ we get

$\bigl{(}n\varepsilon-2\lVert
g\rVert_{\infty}\bigr{)}^{2}\geq\left(n\varepsilon-\frac{2C_{1}L}{1-\mathrm{e}^{-C_{2}}}\right)^{2}.$

This, together with $8n\lVert g\rVert_{\infty}^{2}\leq
8nC_{1}^{2}L^{2}(1-\mathrm{e}^{-C_{2}})^{-2}$ gives

$-\frac{(n\varepsilon-2\lVert g\rVert_{\infty})^{2}}{8n\lVert
g\rVert_{\infty}^{2}}\leq-\frac{(n\varepsilon-2C_{1}L(1-\mathrm{e}^{-C_{2}})^{-1})^{2}}{8nC_{1}^{2}L^{2}(1-\mathrm{e}^{-C_{2}})^{-2}}=-\frac{(n\varepsilon(1-\mathrm{e}^{-C_{2}})-2C_{1}L)^{2}}{8nC_{1}^{2}L^{2}}.$

Therefore,

$\mathbb{P}_{z}\left(|S_{n}-n\,\uppi(\ell_{h})|\geq n\varepsilon\right)\leq
2\mathrm{exp}\left(-\frac{(n\varepsilon(1-\mathrm{e}^{-C_{2}})-2C_{1}L)^{2}}{8nC_{1}^{2}L^{2}}\right).$

Combining this with relations $\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)=\frac{1}{n}(S_{n}-n\,\uppi(\ell_{h}))$ and
$\mathrm{er}_{\uppi}(h)\geq m$ (recall that for every $h\in\mathscr{H}$ it
holds that $\mathrm{er}_{\uppi}(h)\geq m$), we get that for every
$n\geq\frac{2C_{1}L}{\varepsilon\sqrt{m}(1-\mathrm{e}^{-C_{2}})}$ it holds

$\displaystyle\mathbb{P}_{z}\left(\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\varepsilon\right)$
$\displaystyle\leq\mathbb{P}_{z}\left(\left|S_{n}-n\,\uppi(\ell_{h})\right|\geq
n\varepsilon\sqrt{m}\right)$ $\displaystyle\leq
2\mathrm{exp}\left(-\frac{(n\varepsilon\sqrt{m}(1-\mathrm{e}^{-C_{2}})-2C_{1}L)^{2}}{8nC_{1}^{2}L^{2}}\right).$

Let $\varepsilon>0$ be arbitrary and denote with
$\mathscr{C}_{\varepsilon/\bar{L}}=\\{h_{1},h_{2},\ldots,h_{\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}\\}$
the $\varepsilon/\bar{L}$-cover of $\mathscr{H}$. By subadditivity, we have

$\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\varepsilon\right)\leq\sum_{i=1}^{\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\varepsilon\right),$

where
$\mathscr{H}_{i}\coloneqq\\{\bar{h}:\mathsf{d}_{\mathscr{H}}(\bar{h},h_{i})<\varepsilon/\bar{L}\\}$.
Our goal now is to provide an upper bound for the summands on the right hand
side. Since it can happen that $\hat{\rm er}_{n}(h)\geq\mathrm{er}_{\uppi}(h)$
and $\hat{\rm er}_{n}(h)\leq\mathrm{er}_{\uppi}(h)$, we will inspect
expressions $\mathrm{er}_{\uppi}(h)-\hat{\rm er}_{n}(h)$ and $\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)$ separately.

Part 1: $\mathrm{er}_{\uppi}(h)-\hat{\rm er}_{n}(h)$. For $\eta\in(0,1)$,
define

$\phi(h)\coloneqq(1-\eta)\mathrm{er}_{\uppi}(h)-\hat{\rm er}_{n}(h).$

For any $h\in\mathscr{H}_{i}$ we have that

$\displaystyle\phi(h)-\phi(h_{i})$
$\displaystyle=(1-\eta)\bigl{(}\mathrm{er}_{\uppi}(h)-\mathrm{er}_{\uppi}(h_{i})\bigr{)}+\bigl{(}\hat{\rm
er}_{n}(h_{i})-\hat{\rm er}_{n}(h)\bigr{)}$
$\displaystyle\leq(1-\eta)\int_{\mathsf{Z}}\bigl{|}\ell_{h}(z)-\ell_{h_{i}}(z)\bigr{|}\uppi(\mathrm{d}z)+\frac{1}{n}\sum_{j=0}^{n-1}\bigl{|}\ell_{h_{i}}(z_{j})-\ell_{h}(z_{j})\bigr{|}$
$\displaystyle\leq(2-\eta)\varepsilon,$

where we used assumption (A2), more precisely, we used that

$\left|\ell_{h}(z)-\ell_{h_{i}}(z)\right|\leq\bar{L}\mathsf{d}_{\mathscr{H}}(h,h_{i})\leq\bar{L}\cdot\frac{\varepsilon}{\bar{L}}=\varepsilon.$

Hence, if $\sup_{h\in\mathscr{H}_{i}}\phi(h)\geq 2\varepsilon(2-\eta)$, then
$\phi(h_{i})\geq\varepsilon(2-\eta)$, i.e. for
$i\in\\{1,2,\ldots,\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})\\}$
we have

$\underbrace{\mathbb{P}_{z}\left(\phi(h_{i})\geq\varepsilon(2-\eta)\right)}_{\eqqcolon
I_{1}}\geq\underbrace{\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\phi(h)\geq
2\varepsilon(2-\eta)\right)}_{\eqqcolon I_{2}}.$

Recall that for every $h\in\mathscr{H}$ it holds
$m\leq\mathrm{er}_{\uppi}(h)\leq M$. Setting
$\eta\coloneqq\varepsilon/\mathrm{er}_{\uppi}(h_{i})$ and taking
$0<\varepsilon<2m/3$, we get

$\displaystyle I_{1}$
$\displaystyle=\mathbb{P}_{z}\left((1-\eta)\mathrm{er}_{\uppi}(h_{i})-\hat{\rm
er}_{n}(h_{i})\geq\varepsilon(2-\eta)\right)$
$\displaystyle=\mathbb{P}_{z}\left(\mathrm{er}_{\uppi}(h_{i})-\hat{\rm
er}_{n}(h_{i})\geq\varepsilon+\varepsilon\left(2-\frac{\varepsilon}{\mathrm{er}_{\uppi}(h_{i})}\right)\right)$
$\displaystyle=\mathbb{P}_{z}\left(\frac{\mathrm{er}_{\uppi}(h_{i})-\hat{\rm
er}_{n}(h_{i})}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{\varepsilon}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\left(3-\frac{\varepsilon}{\mathrm{er}_{\uppi}(h_{i})}\right)\right)$
$\displaystyle\leq\mathbb{P}_{z}\left(\frac{\mathrm{er}_{\uppi}(h_{i})-\hat{\rm
er}_{n}(h_{i})}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{\varepsilon}{\sqrt{M}}\left(3-\frac{\varepsilon}{m}\right)\right)$
$\displaystyle\leq\mathbb{P}_{z}\left(\frac{\mathrm{er}_{\uppi}(h_{i})-\hat{\rm
er}_{n}(h_{i})}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{7\varepsilon}{3\sqrt{M}}\right).$

In a similar fashion one can obtain

$I_{2}\geq\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\frac{\mathrm{er}_{\uppi}(h)-\hat{\rm
er}_{n}(h)}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\frac{M+4m}{m^{3/2}}\varepsilon\right).$

Since $I_{1}\geq I_{2}$, we have

$\mathbb{P}_{z}\left(\frac{\mathrm{er}_{\uppi}(h_{i})-\hat{\rm
er}_{n}(h_{i})}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{7\varepsilon}{3\sqrt{M}}\right)\geq\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\frac{\mathrm{er}_{\uppi}(h)-\hat{\rm
er}_{n}(h)}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\frac{M+4m}{m^{3/2}}\varepsilon\right).$

Part 2: $\hat{\rm er}_{n}(h)-\mathrm{er}_{\uppi}(h)$. For $\eta\in(0,1)$,
define

$\widetilde{\phi}(h)\coloneqq\hat{\rm
er}_{n}(h)-(1+\eta)\mathrm{er}_{\uppi}(h).$

Analogously as in Part 1, we obtain

$\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\frac{\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\frac{M+4m}{m^{3/2}}\varepsilon\right)\leq\mathbb{P}_{z}\left(\frac{\hat{\rm
er}_{n}(h_{i})-\mathrm{er}_{\uppi}(h_{i})}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{3\varepsilon}{\sqrt{M}}\right).$

Since $(M+6m)/m^{3/2}>(M+4m)/m^{3/2}$ and $3/\sqrt{M}>7/(3\sqrt{M})$, we get

$\displaystyle\mathbb{P}_{z}$
$\displaystyle\left(\sup_{h\in\mathscr{H}_{i}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\frac{M+6m}{m^{3/2}}\varepsilon\right)$
$\displaystyle\leq\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\frac{\mathrm{er}_{\uppi}(h)-\hat{\rm
er}_{n}(h)}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\frac{M+6m}{m^{3/2}}\varepsilon\right)+\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\frac{\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\frac{M+6m}{m^{3/2}}\varepsilon\right)$
$\displaystyle\leq\mathbb{P}_{z}\left(\frac{\left|\mathrm{er}_{\uppi}(h_{i})-\hat{\rm
er}_{n}(h_{i})\right|}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{7\varepsilon}{3\sqrt{M}}\right)+\mathbb{P}_{z}\left(\frac{\left|\hat{\rm
er}_{n}(h_{i})-\mathrm{er}_{\uppi}(h_{i})\right|}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{7\varepsilon}{3\sqrt{M}}\right)$
$\displaystyle\leq
2\mathbb{P}_{z}\left(\frac{\left|\mathrm{er}_{\uppi}(h_{i})-\hat{\rm
er}_{n}(h_{i})\right|}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{7\varepsilon}{3\sqrt{M}}\right).$

Setting $\varepsilon^{\prime}\coloneqq m^{3/2}\varepsilon/(M+6m)$, we have

(2.5) $\displaystyle\mathbb{P}_{z}$
$\displaystyle\left(\sup_{h\in\mathscr{H}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\varepsilon\right)$
$\displaystyle\leq\sum_{i=1}^{\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\varepsilon\right)$
$\displaystyle=\sum_{i=1}^{\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}_{i}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\frac{M+6m}{m^{3/2}}\varepsilon^{\prime}\right)$
$\displaystyle\leq
2\sum_{i=1}^{\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}\mathbb{P}_{z}\left(\frac{\left|\hat{\rm
er}_{n}(h_{i})-\mathrm{er}_{\uppi}(h_{i})\right|}{\sqrt{\mathrm{er}_{\uppi}(h_{i})}}\geq\frac{7\varepsilon^{\prime}}{3\sqrt{M}}\right)$
$\displaystyle\leq
4\sum_{i=1}^{\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}\mathrm{exp}\left(-\frac{\left(7\varepsilon^{\prime}n\sqrt{m}(1-\mathrm{e}^{-C_{2}})-2C_{1}L\right)^{2}}{72MnC_{1}^{2}L^{2}}\right)$
$\displaystyle\leq
4\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})\,\mathrm{e}^{-\xi_{1}\varepsilon^{2}n+\xi_{2}\varepsilon},$

where

$\xi_{1}=\frac{49m^{4}(1-\mathrm{e}^{-C_{2}})^{2}}{72M(M+6m)^{2}C_{1}^{2}L^{2}}\qquad\text{and}\qquad\xi_{2}=\frac{7m^{2}(1-\mathrm{e}^{-C_{2}})}{6\sqrt{M}(M+6m)C_{1}L}.$

Hence, to have

$\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\varepsilon\right)\leq\delta,$

it suffices to have

$4\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})\,\mathrm{e}^{-\xi_{1}\varepsilon^{2}n+\xi_{2}\varepsilon}\leq\delta,$

which is equivalent to

$n\geq\frac{1}{\xi_{1}\varepsilon^{2}}\left(\xi_{2}\varepsilon+\log\left(\frac{4\mathcal{N}(\varepsilon/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}})}{\delta}\right)\right),$

and this is exactly what we wanted to prove. ∎

### Proof of Corollary 1.3

Define

$\tilde{\varepsilon}\coloneqq\sqrt{\frac{\varepsilon}{1+\frac{1}{\alpha}}},$

where $\varepsilon>0$ is the one from the statement of this result. Using

$n\geq\frac{2C_{1}L\sqrt{1+1/\alpha}}{\sqrt{\varepsilon}(\sqrt{m}\wedge
1)(1-\mathrm{e}^{-C_{2}})}=\frac{2C_{1}L}{\tilde{\varepsilon}(\sqrt{m}\wedge
1)(1-\mathrm{e}^{-C_{2}})},$

together with eq. 2.5 we get

$\mathbb{P}_{z}\left(\sup_{h\in\mathscr{H}}\frac{\left|\hat{\rm
er}_{n}(h)-\mathrm{er}_{\uppi}(h)\right|}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\tilde{\varepsilon}\right)\leq
4\mathcal{N}\left(\tilde{\varepsilon}/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}}\right)\mathrm{e}^{-\xi_{1}\tilde{\varepsilon}^{2}n+\xi_{2}\tilde{\varepsilon}}.$

Hence, we obviously have

(2.6)
$\mathbb{P}_{z}\left(\exists\,h\in\mathscr{H}:\frac{\mathrm{er}_{\uppi}(h)-\hat{\rm
er}_{n}(h)}{\sqrt{\mathrm{er}_{\uppi}(h)}}\geq\tilde{\varepsilon}\right)\leq
4\mathcal{N}\left(\tilde{\varepsilon}/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}}\right)\mathrm{e}^{-\xi_{1}\tilde{\varepsilon}^{2}n+\xi_{2}\tilde{\varepsilon}}.$

We now follow the proof of [AB99, Theorem 5.8]. Suppose that

(2.7) $\mathrm{er}_{\uppi}(h)-\hat{\rm
er}_{n}(h)\leq\tilde{\varepsilon}\sqrt{\mathrm{er}_{\uppi}(h)}.$

Then, for $\alpha>0$ from the statement of this result (arbitrary, but fixed)
we have two cases.

Case 1: If $\mathrm{er}_{\uppi}(h)<(1+1/\alpha)^{2}\tilde{\varepsilon}^{2}$
then eq. 2.7 implies

$\mathrm{er}_{\uppi}(h)\leq\hat{\rm
er}_{n}(h)+\tilde{\varepsilon}^{2}\left(1+\frac{1}{\alpha}\right).$

Case 2: If $\mathrm{er}_{\uppi}(h)\geq(1+1/\alpha)^{2}\tilde{\varepsilon}^{2}$
then $\tilde{\varepsilon}\leq\sqrt{\mathrm{er}_{\uppi}(h)}/(1+1/\alpha)$.
Hence, from eq. 2.7 it follows that

$\mathrm{er}_{\uppi}(h)\leq\hat{\rm
er}_{n}(h)+\frac{\alpha}{\alpha+1}\cdot\mathrm{er}_{\uppi}(h),$

which is equivalent to

$\mathrm{er}_{\uppi}(h)\leq(1+\alpha)\hat{\rm er}_{n}(h).$

Therefore, we have just showed that eq. 2.7 implies

$\mathrm{er}_{\uppi}(h)\leq(1+\alpha)\hat{\rm
er}_{n}(h)+\tilde{\varepsilon}^{2}\left(1+\frac{1}{\alpha}\right)=(1+\alpha)\hat{\rm
er}_{n}(h)+\varepsilon.$

Combining this with eq. 2.6, we get

$\displaystyle\mathbb{P}_{z}$
$\displaystyle\left(\exists\,h\in\mathscr{H}:\mathrm{er}_{\uppi}(h)>(1+\alpha)\hat{\rm
er}_{n}(h)+\varepsilon\right)\leq\mathbb{P}_{z}\left(\exists\,h\in\mathscr{H}:\frac{\mathrm{er}_{\uppi}(h)-\hat{\rm
er}_{n}(h)}{\sqrt{\mathrm{er}_{\uppi}(h)}}>\tilde{\varepsilon}\right)$
$\displaystyle\qquad\leq
4\mathcal{N}\left(\tilde{\varepsilon}/\bar{L},\mathscr{H},\mathsf{d}_{\mathscr{H}}\right)\mathrm{e}^{-\xi_{1}\tilde{\varepsilon}^{2}n+\xi_{2}\tilde{\varepsilon}}$
$\displaystyle\qquad=4\mathcal{N}\left(\frac{\varepsilon^{1/2}}{\bar{L}\sqrt{1+1/\alpha}},\mathscr{H},\mathsf{d}_{\mathscr{H}}\right)\mathrm{exp}\left(-\xi_{1}\cdot\frac{\varepsilon}{1+\frac{1}{\alpha}}\cdot
n+\xi_{2}\cdot\sqrt{\frac{\varepsilon}{1+\frac{1}{\alpha}}}\right),$

and this is clearly less than or equal to $\delta$ for

$n\geq\frac{\alpha+1}{\alpha\xi_{1}}\cdot\frac{1}{\varepsilon}\left(\frac{\xi_{2}}{\sqrt{1+1/\alpha}}\cdot\varepsilon^{1/2}+\ln\left(\frac{4\mathcal{N}\left(\frac{\varepsilon^{1/2}}{\bar{L}\sqrt{1+1/\alpha}},\mathscr{H},\mathsf{d}_{\mathscr{H}}\right)}{\delta}\right)\right),$

which is exactly what we wanted to prove. ∎

##  3\. Appendix

In this section, we prove the auxiliary result used in the construction of the
example satisfying condition (A3).

######  Lemma 3.1.

Let $\\{X_{n}\\}_{n\geq 0}$ be a Markov chain on $\mathsf{X}$ with transition
kernel $\mathcal{P}_{X}(x,\mathrm{d}\bar{x})$, and let $f:\mathsf{X}\to
f(\mathsf{X})\subseteq\mathsf{Y}$ be measurable. The family of random
variables $\\{f(X_{n})\\}_{n\geq 0}$ is a Markov chain on $\mathsf{Y}$ if
$\\{f^{-1}(\\{y\\})\\}_{y\in f(\mathsf{X})}$ forms a family of atoms for
$\\{X_{n}\\}_{n\geq 0}$ on $f^{-1}(f(\mathsf{X}))$, i.e. for any $y\in
f(\mathsf{X})$ and $x_{1},x_{2}\in f^{-1}(\\{y\\})$,

$\mathcal{P}_{X}(x_{1},f^{-1}(B))=\mathcal{P}_{X}(x_{2},f^{-1}(B)).$

In that case, transition kernel of $\\{f(X_{n})\\}_{n\geq 0}$ is given by

$\mathcal{P}(y,B)=\mathcal{P}_{X}(x,f^{-1}(B))$

for $y\in f(\mathsf{X})$ and $x\in f^{-1}(\\{y\\})$.

###### Proof.

By assumption, $\\{X_{n}\\}_{n\geq 0}$ is defined on
$(\Omega,\mathcal{F},\mathbb{P}_{x})_{x\in\mathsf{X}}$. Now, on
$(\Omega,\mathcal{F})$ define a family of probability measures
$\\{\bar{\mathbb{P}}_{y}\\}_{y\in f(\mathsf{X})}$ by
$\bar{\mathbb{P}}_{y}(f(X_{n})\in B)\coloneqq\mathbb{P}_{x}(X_{n}\in
f^{-1}(B))$ for $n\geq 0$, $y\in f(\mathsf{X})$ and $x\in f^{-1}(\\{y\\})$. By
assumption, $\\{\bar{\mathbb{P}}_{y}\\}_{y\in f(\mathsf{X})}$ is well defined,
and the assertion now follows directly. ∎

## Acknowledgements

Financial support through Alexander von Humboldt Foundation (No. HRV 1151902
HFST-E) and Croatian Science Foundation under project 8958 (for N. Sandrić),
and the Croatian Science Foundation under project 4197 (for S. Šebek) is
gratefully acknowledged.

## References

  * [AB99] M. Anthony and P. L. Bartlett.  Neural network learning: theoretical foundations.  Cambridge University Press, Cambridge, 1999.
  * [BKP97] P. L. Bartlett, S. R. Kulkarni, and S. E. Posner.  Covering numbers for real-valued function classes.  IEEE Trans. Inform. Theory, 43(5):1721–1724, 1997.
  * [But14] O. Butkovsky.  Subgeometric rates of convergence of Markov processes in the Wasserstein metric.  Ann. Appl. Probab., 24(2):526–552, 2014.
  * [DGL96] L. Devroye, L. Györfi, and G. Lugosi.  A probabilistic theory of pattern recognition, volume 31 of Applications of Mathematics (New York).  Springer-Verlag, New York, 1996.
  * [Gam03] D. Gamarnik.  Extension of the PAC framework to finite and countable Markov chains.  IEEE Trans. Inform. Theory, 49(1):338–345, 2003.
  * [GO02] P. W. Glynn and D. Ormoneit.  Hoeffding’s inequality for uniformly ergodic Markov chains.  Statist. Probab. Lett., 56(2):143–146, 2002.
  * [KM12] I. Kontoyiannis and S. P. Meyn.  Geometric ergodicity and the spectral gap of non-reversible Markov chains.  Probab. Theory Related Fields, 154(1-2):327–339, 2012.
  * [Mei00] R. Meir.  Nonparametric time series prediction through adaptive model selection.  Machine Learning, 39(1):5–34, 2000.
  * [Mia14] B. Miasojedow.  Hoeffding’s inequalities for geometrically ergodic Markov chains on general state space.  Statist. Probab. Lett., 87:115–120, 2014.
  * [MM96] D. S. Modha and E. Masry.  Minimum complexity regression estimation with weakly dependent observations.  IEEE Trans. Inform. Theory, 42(6, part 2):2133–2145, 1996.
  * [MT09] S. Meyn and R. L. Tweedie.  Markov chains and stochastic stability.  Cambridge University Press, Cambridge, second edition, 2009.
  * [RR97] G. O. Roberts and J. S. Rosenthal.  Geometric ergodicity and hybrid Markov chains.  Electron. Comm. Probab., 2:no. 2, 13–25, 1997.
  * [SHS09] I. Steinwart, D. Hush, and C. Scovel.  Learning from dependent observations.  J. Multivariate Anal., 100(1):175–194, 2009.
  * [SSBD14] S. Shalev-Shwartz and S. Ben-David.  Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014.
  * [Vid03] M. Vidyasagar.  Learning and generalization.  Springer-Verlag London, Ltd., London, 2003.
  * [Yu94] B. Yu.  Rates of convergence for empirical processes of stationary mixing sequences.  Ann. Probab., 22(1):94–116, 1994.
  * [Zho03] D. X. Zhou.  Capacity of reproducing kernel spaces in learning theory.  IEEE Trans. Inform. Theory, 49(7):1743–1752, 2003.
  * [ZLX12] B. Zou, L. Li, and Z. Xu.  Generalization performance of least-square regularized regression algorithm with Markov chain samples.  J. Math. Anal. Appl., 388(1):333–343, 2012.
  * [ZLX+13] B. Zou, L. Li, Z. Xu, T. Luo, and Y. Y. Tang.  Generalization performance of Fisher linear discriminant based on Markov sampling.  IEEE Trans. Neural. Netw. Learn. Syst., 24(2):288–300, 2013.
  * [ZXC12] B. Zou, Z. Xu, and X. Chang.  Generalization bounds of ERM algorithm with $V$-geometrically ergodic Markov chains.  Adv. Comput. Math., 36(1):99–114, 2012.
  * [ZXX14] B. Zou, Z. Xu, and J. Xu.  Generalization bounds of ERM algorithm with Markov chain samples.  Acta Math. Appl. Sin. Engl. Ser., 30(1):223–238, 2014.
  * [ZZX09] B. Zou, H. Zhang, and Z. Xu.  Learning from uniformly ergodic Markov chains.  J. Complexity, 25(2):188–200, 2009.


# Magnetometry with spin polarized Hydrogen from molecular photo-dissociation

Konstantinos Tazes  University of Crete, Department of Physics, Heraklion,
Greece  Alexandros K. Spiliotis  Michalis Xygkis  Foundation for Research and
Technology Hellas, Institute of Electronic Structure and Laser, N. Plastira
100, Heraklion, Crete, Greece, GR-71110  University of Crete, Department of
Physics, Heraklion, Greece  George E. Katsoprinakis  Foundation for Research
and Technology Hellas, Institute of Electronic Structure and Laser, N.
Plastira 100, Heraklion, Crete, Greece, GR-71110  T. Peter Rakitzis
Foundation for Research and Technology Hellas, Institute of Electronic
Structure and Laser, N. Plastira 100, Heraklion, Crete, Greece, GR-71110
University of Crete, Department of Physics, Heraklion, Greece  Georgios
Vasilakis  Foundation for Research and Technology Hellas, Institute of
Electronic Structure and Laser, N. Plastira 100, Heraklion, Crete, Greece,
GR-71110

###### Abstract

In a recent publication [arXiv:2010.14579], we introduced a new type of atomic
magnetometer, which relies on hydrohalide photo-dissociation to create high-
density spin-polarized hydrogen. Here, we extend our previous work and present
a detailed theoretical analysis of the magnetometer signal and its dependence
on time. We also derive the sensitivity for a spin-projection noise limited
magnetometer, which can be applied to an arbitrary magnetic field waveform.

###### pacs:

07.55.Ge, 67.65.+z

A broad range of physical objects and processes generate magnetic fields which
upon detection can convey important information about the nature and structure
of their origin. As a result, magnetic field detection lies at the heart of
many scientific and technological applications, which can benefit
significantly from advances in magnetometry book:MagneticSensors .

Different magnetic field sensors have been developed which offer distinct
advantages and are attractive for particular applications. In general terms,
an ideal magnetometer should present high-sensitivity, wide bandwidth
detection, high-performance over a large dynamic range and operating
conditions, as well as capability for miniaturization when used for magnetic
field imaging.

Recently, a new type of atomic magnetometer was demonstrated based on high-
density spin-polarized atomic H (SPH) NanosecondresolvedMagnetometer , which
has the potential to address satisfactorily the above requirements for
magnetometry. The spin-polarized ensemble is produced by photo-dissociating
hydrohalide gas with a circularly-polarized laser pulse Rakitzis_Science ;
Sofikitis_HClHBr_SPH ; Rakitzis_ChemPhysChem . Magnetic field detection is
achieved by monitoring the dynamics of the H hyperfine coherences, which are
created in the optical pumping process without the need for external magnetic
fields.

This paper is an extension of the work presented in
NanosecondresolvedMagnetometer , analytically deriving equations for the spin-
dynamics, the magnetometer signal and the quantum spin-projection noise.

We will consider the magnetometer scheme with mutually orthogonal directions
for optical pumping, magnetic field direction and spin-probing, as shown in
Fig. 1. Without loss of generality we take the magnetic field to be in the $z$
direction, the optical pumping along the $y$ axis and the probe axis in the
$x$ direction. Monitoring of spins is realized with an inductive pick-up coil,
which detects the magnetic flux generated by the H spins. Since the electron
magnetic moment is more than three orders of magnitude larger than the proton
magnetic moment, the coil is to a very good approximation only sensitive to
the H electron spins. In the following, we will assume a pickup coil with a
response time much shorter than the hyperfine interaction period and neglect
complications arising from a non-spherical polarized region or from
geometrical factors in the coupling of the magnetic field from spins to the
coil. For simplicity, we will assume that the observable is
$\frac{d\hat{S}_{x}}{dt}$, where $\hat{S}_{i}$ expresses the dimensionless
electron spin operator in the $i$ direction.

Figure 1: Schematic of the magnetometer setup. A circularly-polarized laser
pulse (red arrow), photo-dissociate molecular hydrohalide gas producing spin-
polarized atomic H. A pickup coil detects the evolution of the ensemble
magnetization in the presence of a magnetic field (green arrow).

##  I Time evolution

In the presence of a magnetic field $\mathbf{B}$ (which can be time varying),
the SPH evolves according to the Hamiltonian (we neglect for the moment the
relaxation):

$\hat{H}=\omega_{0}\hat{\mathbf{S}}\cdot\hat{\mathbf{I}}+\frac{g_{\text{s}}\mu_{\text{B}}}{\hbar}\mathbf{B}\cdot\hat{\mathbf{S}}=\hat{H}_{0}+\frac{g_{\text{s}}\mu_{\text{B}}}{\hbar}B\cdot\hat{S}_{z}$
(1)

where $\hat{\mathbf{I}}$ is the dimensionless nuclear spin operator,
$\omega_{0}$ is the hyperfine frequency of H, $\mu_{\text{B}}$ is the Bohr
magneton, $g_{\text{s}}\approx 2$ is the electron spin $g$-factor,
$\hat{H}_{0}$ is the Hamiltonian for hyperfine interaction expressed in
(angular) frequency units. In the above equation, we neglected the coupling of
the magnetic field to nuclear spin, as this is three orders of magnitude
smaller than the coupling to the electron spin.

For clarity we write the Hamiltonian in the coupled (subscript c) and
uncoupled (subscript u) basis taking $z$ (the magnetic field direction) as the
quantization axis:

$\hat{H}_{\text{u}}=\begin{pmatrix}\frac{\omega_{0}}{4}+\gamma_{\text{H}}B&0&0&0\\\
0&-\frac{\omega_{0}}{4}-\gamma_{\text{H}}B&\frac{\omega_{0}}{2}&0\\\
0&\frac{\omega_{0}}{2}&-\frac{\omega_{0}}{4}+\gamma_{\text{H}}B&0\\\
0&0&0&\frac{\omega_{0}}{4}-\gamma_{\text{H}}B\end{pmatrix},\text{
}\hat{H}_{\text{c}}=\begin{pmatrix}\frac{\omega_{0}}{4}+\gamma_{\text{H}}B&0&0&0\\\
0&\frac{\omega_{0}}{4}&0&\gamma_{\text{H}}B\\\
0&0&\frac{\omega_{0}}{4}-\gamma_{\text{H}}B&0\\\
0&\gamma_{\text{H}}B&0&-\frac{3\omega_{0}}{4}\end{pmatrix},$ (2)

where $\gamma_{\text{H}}=g_{\text{s}}\mu_{\text{B}}/2\hbar$ is the
gyromagnetic ratio of atomic H. The above matrices are expressed in a basis
with the following ordering:

$\displaystyle\begin{split}\text{uncoupled basis:
}&\\{|m_{s}=1/2,m_{I}=1/2\rangle,|m_{s}=-1/2,m_{I}=1/2\rangle,|m_{s}=1/2,m_{I}=-1/2\rangle,|m_{s}=-1/2,m_{I}=-1/2\rangle\\},\\\
\text{coupled basis:
\phantom{un}}&\\{|F=1,m_{F}=1\rangle,|F=1,m_{F}=0\rangle,|F=1,m_{F}=-1\rangle,|F=0,m_{F}=0\rangle\\},\end{split}$
(3)

where $F$ is the total spin (sum of electronic and nuclear spin) quantum
number, $m_{s}$, $m_{I}$ and $m_{F}$ are respectively the electronic, nuclear
and total spin projection along the quantization axis.

Transformation of an arbitrary operator $\hat{\mathcal{O}}$ or state vector
$|\psi\rangle$ from one basis to the other can be performed according to the
following rules:

$\hat{\mathcal{O}}_{\text{c}}=\mathcal{T}_{\text{cu}}\cdot\hat{\mathcal{O}}_{\text{u}}\cdot\mathcal{T}_{\text{cu}}^{-1},\text{
}\hat{\mathcal{O}}_{\text{u}}=\mathcal{T}_{\text{cu}}^{-1}\cdot\hat{\mathcal{O}}_{\text{c}}\cdot\mathcal{T}_{\text{cu}},\text{
}|\psi\rangle_{c}=\mathcal{T}_{\text{cu}}|\psi\rangle_{\text{u}},\text{
}|\psi\rangle_{u}=\mathcal{T}_{\text{cu}}^{-1}|\psi\rangle_{\text{c}},$ (4)
$\mathcal{T}_{\text{cu}}=\begin{pmatrix}1&0&0&0\\\
0&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0\\\ 0&0&0&1\\\
0&-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}&0\end{pmatrix}.$ (5)

The hydrohalide photo-dissociation occurs with a sub-nanosecond laser pulse
and optical pumping effectively transfers angular momentum from light to the
electronic spin, leaving the nuclear spin degrees of freedom in their thermal
(completely unpolarized) state. Following the above basis ordering, after
optical pumping half of the polarized H atoms are in the quantum state
(expressed as a column vector):

$|\psi(0)\rangle_{0}=|\psi_{0}\rangle=\begin{cases}\left(1,0,0,0\right)_{\text{u,y}}^{\intercal}\xrightarrow{\hat{\mathcal{R}}_{x}\cdot\left(1,0,0,0\right)^{\intercal}}\left(\frac{1}{2},-\frac{\imath}{2},-\frac{\imath}{2},-\frac{1}{2}\right)_{\text{u}}^{\intercal}\xrightarrow{\mathcal{T}_{\text{cu}}}\left(\frac{1}{2},-\frac{\imath}{2},-\frac{1}{2},0\right)_{\text{c}}^{\intercal}&,\sigma=1\\\
\left(0,0,0,1\right)_{\text{u,y}}^{\intercal}\xrightarrow{\hat{\mathcal{R}}_{x}\cdot\left(0,0,0,1\right)^{\intercal}}\left(-\frac{1}{2},-\frac{\imath}{2},-\frac{\imath}{2},\frac{1}{2}\right)_{\text{u}}^{\intercal}\xrightarrow{\mathcal{T}_{\text{cu}}}\left(-\frac{1}{2},-\frac{\imath}{2},\frac{1}{2},0\right)_{\text{c}}^{\intercal}&,\sigma=-1\end{cases},$
(6)

where the subscript y denotes that the quantization axis for spin projections
was taken in the $y$ direction (if no axis subscript appears it is implicitly
assumed that the quantization axis is in the $z$ direction), $\intercal$ is
the transpose operation, $\sigma$ is the helicity of the pumping light pulse
and $\hat{\mathcal{R}}_{x}$ is the rotation matrix around the $x$-axis applied
to the uncoupled basis (two spins, each of spin 1/2) :

$\hat{\mathcal{R}}_{x}=e^{-\imath\hat{S}_{x}\frac{\pi}{2}}\otimes
e^{-\imath\hat{S}_{x}\frac{\pi}{2}}.$ (7)

The other half of the polarized H atoms are in the state:

$|\psi(0)\rangle_{1}=|\psi_{1}\rangle=\begin{cases}\left(0,0,1,0\right)_{\text{u,y}}^{\intercal}\xrightarrow{\hat{\mathcal{R}}_{x}\cdot\left(0,0,1,0\right)^{\intercal}}\left(-\frac{\imath}{2},-\frac{1}{2},\frac{1}{2},-\frac{\imath}{2}\right)_{\text{u}}^{\intercal}\xrightarrow{\mathcal{T}_{\text{cu}}}\left(-\frac{\imath}{2},0,-\frac{\imath}{2},\frac{1}{\sqrt{2}}\right)_{\text{c}}^{\intercal}&,\sigma=1\\\
\left(0,1,0,0\right)_{\text{u,y}}^{\intercal}\xrightarrow{\hat{\mathcal{R}}_{x}\cdot\left(0,1,0,0\right)^{\intercal}}\left(-\frac{\imath}{2},\frac{1}{2},-\frac{1}{2},-\frac{\imath}{2}\right)_{\text{u}}^{\intercal}\xrightarrow{\mathcal{T}_{\text{cu}}}\left(-\frac{\imath}{2},0,-\frac{\imath}{2},-\frac{1}{\sqrt{2}}\right)_{\text{c}}^{\intercal}&,\sigma=-1\end{cases}.$
(8)

For the observable $\frac{d\hat{S}_{x}}{dt}$ the contribution to signal of
atoms initially at state $|\psi(0)\rangle_{0}$ is a factor of
$\gamma_{\text{H}}B/\omega_{0}$ smaller than the contribution of atoms
initially at $|\psi(0)\rangle_{1}$. In the case of
$\gamma_{\text{H}}B/\omega_{0}\ll 1$, the magnetometer signal is mainly
determined by the atoms initially at $|\psi(0)\rangle_{1}$.

For static magnetic field, Schrödinger equation can be solved in a
straightforward manner:

$\imath\frac{\partial}{\partial
t}|\psi(t)\rangle=\hat{H}|\psi(t)\rangle\Rightarrow|\psi(t)\rangle=e^{-\imath\hat{H}t}|\psi(0)\rangle$
(9)

where $|\psi(t)\rangle$ is the wavefunction at time $t$ after optical pumping.
For $|\psi(0)\rangle=|\psi(0)\rangle_{1}$ the wavefunction at time $t$ in the
coupled basis is:

$\displaystyle|\psi(t)\rangle_{1}$
$\displaystyle=\left(-\frac{1}{2}ie^{-\imath\left(\frac{\omega_{0}}{4}+\gamma_{\text{H}}B\right)t},-\imath\sigma\frac{\sqrt{2}\gamma_{\text{H}}Be^{\imath\frac{\omega_{0}}{4}t}\sin\left[\frac{1}{2}\tilde{\omega}t\right]}{\tilde{\omega}},-\frac{1}{2}\imath
e^{-\imath\left(\frac{\omega_{0}}{4}-\gamma_{\text{H}}B\right)t},\sigma\frac{e^{\imath\frac{\omega_{0}}{4}t}\left(\imath\omega_{0}\sin\left[\frac{1}{2}\tilde{\omega}t\right]+\tilde{\omega}\cos\left[\frac{1}{2}\tilde{\omega}t\right]\right)}{\sqrt{2}\tilde{\omega}}\right)^{\intercal}$
(10) $\displaystyle\approx-\frac{1}{2}\imath
e^{\imath\frac{1}{4}\left(\omega_{0}+2\tilde{\omega}\right)t}\left(e^{-\imath\left(\frac{\omega_{0}}{2}+\gamma_{\text{H}}B+\frac{1}{2}\tilde{\omega}\right)t},0,e^{-\imath\left(\frac{\omega_{0}}{2}-\gamma_{\text{H}}B+\frac{1}{2}\tilde{\omega}\right)t},\imath\sqrt{2}\sigma\right)^{\intercal},$
(11)

where: $\tilde{\omega}=\sqrt{\omega_{0}^{2}+4\gamma_{\text{H}}^{2}B^{2}}$.

In the general case of a time varying magnetic field the Schrödinger equation
cannot be solved analytically, as the Hamiltonian does not commute with itself
at different times. For an approximate analytical solution it is convenient to
work in the interaction picture (denoted by the $\tilde{\phantom{a}}$ symbol):

$\frac{\partial}{\partial
t}|\tilde{\psi}(t)\rangle=-\imath\hat{\tilde{V}}|\tilde{\psi}(t)\rangle,$ (12)

where $\hat{\tilde{V}}$ is the Hamiltonian describing the magnetic field
coupling to the atoms:

$\hat{\tilde{V}}(t)=e^{\imath\hat{H}_{0}t}\left[g_{s}\mu_{\text{B}}B\hat{S}_{z}\right]e^{-\imath\hat{H}_{0}t}=\gamma_{\text{H}}B(t)\begin{pmatrix}1&0&0&0\\\
0&-\cos(\omega_{0}t)&\imath\sin(\omega_{0}t)&0\\\
0&-\imath\sin(\omega_{0}t)&\cos(\omega_{0}t)&0\\\ 0&0&0&-1\end{pmatrix}.$ (13)

In the last equation $\hat{\tilde{V}}$ is expressed in the uncoupled basis.

The solution of Eq. 12 can be expressed in the form of the Magnus series
MagnusExpansion . For magnetic fields that change slowly with respect to the
hyperfine frequency so that:

$\int_{0}^{t}B(t^{\prime})e^{\imath\omega_{0}t^{\prime}}\mathop{}\\!\mathrm{d}t^{\prime}\ll\int_{0}^{t}B(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}$
(14)

the solution of Eq. 12 can be approximated by keeping only the first term in
Magnus expansion. In this case:

$|\tilde{\psi}(t)\rangle\approx\exp\left(-\imath\int_{0}^{t}\hat{\tilde{V}}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}\right)|\psi(0)\rangle,$
(15)

and the observable (taking into account the condition 14) can be written as:

$\displaystyle\frac{d}{dt}\langle\tilde{\psi}(t)|e^{\imath\hat{H}_{0}t}\hat{S}_{x}e^{-\imath\hat{H}_{0}t}|\tilde{\psi}(t)\rangle$
$\displaystyle\approx\sigma\frac{d}{dt}\left\\{\frac{1}{2}\sin\left[\gamma_{\text{H}}\int_{0}^{t}B(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}\right]\cos(\omega_{0}t)\right\\}$
(16)
$\displaystyle\approx-\sigma\frac{\omega_{0}}{2}\sin\left[\gamma_{\text{H}}\int_{0}^{t}B(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}\right]\sin(\omega_{0}t).$
(17)

The last approximation holds for $\gamma_{\text{H}}B\ll\omega_{0}$.

The condition stated in 14 implies that the magnetic field does not induce
hyperfine transitions and the magnetic field can be treated as a perturbation
to the energies of the hyperfine levels. Then, for small magnetic fields
($\gamma_{\text{H}}B\ll\omega_{0}$) the Hamiltonian for H atoms (hyperfine
levels with $F=0$ and $F=1$) can be approximated to be (as before the magnetic
field direction is taken to be the quantization axis):

$\hat{H}\approx\hat{H}_{0}+\gamma_{\text{H}}B(t)(\hat{S}_{z}+\hat{I}_{z}).$
(18)

This Hamiltonian commutes with itself at different times and the Schrödinger
equation can be solved analytically:

$|\psi(t)\rangle=e^{-\imath\int_{0}^{t}\hat{H}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}}|\psi(0)\rangle$
(19)

###  I.1 Decay

The evolution of spins is also affected by relaxation processes leading to
non-Hamiltonian dynamics. We model these by introducing a decay term in the
density matrix equation:

$\frac{d\rho}{dt}=\imath[\rho,H]-\frac{1}{T_{2}}(\rho-\rho_{\text{eq}}),$ (20)

where $1/T_{2}$ is the decay rate, and $\rho_{\text{eq}}$ corresponds to the
state towards which the decay processes drive the system. We take this quantum
state to be the completely unpolarized state, written in the form:

$\rho_{\text{eq}}=\frac{1}{4}\mathbb{I}_{4\times 4},$ (21)

where $\mathbb{I}_{4\times 4}$ is the $4\times 4$ identity matrix. For Eqs.
20-21 to be valid the population decay (hydrogen atom losses due to formation
of molecules) should be significantly slower compared to (atomic) hydrogen
spin-decoherence processes. This condition is justified in our case.

The density matrix at $t=0$ is ($z$ quantization axis the direction of
magnetic field and optical pumping in the $y$ axis):

$\rho(0)=\frac{1}{2}|\psi_{0}\rangle\langle\psi_{0}|+\frac{1}{2}|\psi_{1}\rangle\langle\psi_{1}|\rightarrow\begin{pmatrix}\frac{1}{4}&\sigma\frac{\imath}{4}&0&0\\\
-\sigma\frac{\imath}{4}&\frac{1}{4}&0&0\\\
0&0&\frac{1}{4}&\sigma\frac{\imath}{4}\\\
0&0&-\sigma\frac{\imath}{4}&\frac{1}{4}\end{pmatrix}_{\text{u}}\rightarrow\frac{1}{4}\begin{pmatrix}1&\sigma\frac{\imath}{\sqrt{2}}&0&-\sigma\frac{\imath}{\sqrt{2}}\\\
-\sigma\frac{\imath}{\sqrt{2}}&1&\sigma\frac{\imath}{\sqrt{2}}&0\\\
0&-\sigma\frac{\imath}{\sqrt{2}}&1&-\sigma\frac{\imath}{\sqrt{2}}\\\
\sigma\frac{\imath}{\sqrt{2}}&0&\sigma\frac{\imath}{\sqrt{2}}&1\end{pmatrix}_{\text{c}}.$
(22)

An analytical solution to the density matrix equation can be found for a
static magnetic field or for an arbitrary field when the Hamiltonian can be
approximated by Eq. 18. In the experimentally relevant limit of
$\omega_{0}\gg(1/T2,\gamma_{\text{H}}B)$ the signal is (keeping lowest order
terms in the harmonic amplitudes):

$\langle\frac{d\hat{S}_{x}}{dt}\rangle(t)=\text{Tr}\left[\frac{d\rho}{dt}\hat{S}_{x}\right]\approx-\sigma\frac{1}{4}e^{-t/T_{2}}\sin\left[\gamma_{\text{H}}\int_{0}^{t}B(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}\right]\sin(\omega_{0}t).$
(23)

Eqs. 20-21 implies spin-damping occurs (at equal rate) for both electron and
nuclear spin of H. However, the results derived here are general for the
relevant approximations ($\omega_{0}\gg(1/T2,\gamma_{\text{H}}B$) and
condition 14. For instance, Eq. 23 is reproduced also for decay mechanisms
that relax only the electronic spin:

$\frac{d\rho}{dt}=\imath[\rho,H]-\frac{4}{3T_{2}}(\hat{\mathbf{S}}^{2}\cdot\rho-\hat{\mathbf{S}}\cdot\rho\hat{\mathbf{S}}\cdot).$
(24)

##  II Spin-projection noise

In the following we will need to know the multi-time correlation

$\langle\frac{d\hat{S}_{x}}{dt}(t)\frac{d\hat{S}_{x}}{dt}(t^{\prime})\rangle,$
(25)

where we take:

$\frac{d}{dt}\hat{S}_{x}=\imath\left[\hat{H},\hat{S}_{x}\right]-\frac{1}{T_{2}}\hat{S}_{x}$
(26)

The last term (not derived from first principles) was introduced to account
for the spin decay. We assume that the evolution of the density matrix $\rho$
is given by Eq. 20 (though the results are the same -within the relevant
approximations- for the evolution described in Eq. 24).

The multi-time correlation can be written operationally in the form:

$\langle\frac{d\hat{S}_{x}}{dt}(t)\frac{d\hat{S}_{x}}{dt}(t^{\prime})\rangle=\text{Tr}\left\\{\frac{d\hat{S}_{x}}{dt}\left[\hat{U}(t,t^{\prime})\left(\frac{d\hat{S}_{x}}{dt}\rho(t^{\prime})\right)\right]\right\\},$
(27)

where $U(t,t^{\prime})$ is the evolution operator of the density matrix from
time $t^{\prime}$ to $t$ ($t>t^{\prime}$), and $\rho(t^{\prime})$ is the
density matrix at time $t^{\prime}$:
$\rho(t^{\prime})=U(t^{\prime},0)\rho(0)$. The evolution operator $U$ cannot
be written in the form of a matrix and is not associative. The evolved state
$\hat{U}(t,t^{\prime})\left(\frac{d\hat{S}_{x}}{dt}\rho(t^{\prime})\right)$
can be found from the general solution of Eq. 20 taking
$\frac{d\hat{S}_{x}}{dt}\rho(t^{\prime})$ as the initial condition for the
density matrix. For quantum noise analysis we can take the magnetic field to
be zero in the calculation of the multi-time correlation, since quantum noise
affects considerably magnetometry only at low fields. When $\omega_{0}T_{2}\gg
1$, it can be found that:

$\langle\frac{d\hat{S}_{x}}{dt}(t)\frac{d\hat{S}_{x}}{dt}(t^{\prime})\rangle=\frac{1}{8}\omega^{2}e^{-|t-t^{\prime}|/T_{2}}\cos\left[\omega_{0}(t-t^{\prime})\right].$
(28)

In order to find what is the magnetic field uncertainty due to spin-projection
noise, we have to specify a method for estimating the magnetic field from the
detected signal $\frac{d\hat{S}_{x}}{dt}(t)$. Taking into account Eq. 23, one
way to do this (appropriate for arbitrary magnetic waveforms) is from
considering the “quasi-instantaneous” amplitude of the frequency component at
the hyperfine frequency:

$\xi(nT_{\text{hf}})=\frac{1}{T_{\text{hf}}}\int_{nT_{\text{hf}}}^{(n+1)T_{\text{hf}}}\frac{d\hat{S}_{x}}{dt}(t)\sin(\omega_{0}t)\mathop{}\\!\mathrm{d}t,$
(29)

where $T_{\text{hf}}=2\pi/\omega_{0}$ is the period of hyperfine oscillation
and $n$ is an integer number. We assume that the magnetic field can be written
in the form: $B(t)=B_{0}\mathcal{K}(t)$, where $\mathcal{K}$ is a known (but
other than this an arbitrary), time-dependent function. Spin-projection noise
creates an uncertainty in the estimation of $B_{0}$.

We consider the case where the functions $\mathcal{K}(t)$ and $e^{-t/T_{2}}$
evolve in time much slower compared to $\sin(\omega_{0}t)$ and can therefore
be considered constant during the hyperfine period. Effectively this is the
situation for $\omega_{0}T_{2}\gg 1$ and the condition stated in 14. Then, the
quasi-amplitude of the sine wave at hyperfine frequency is (we ignore the
-irrelevant for noise purposes- $-\sigma$ factor in the signal in Eq. 23):

$\frac{1}{T_{\text{hf}}}\int_{nT_{\text{hf}}}^{(n+1)T_{\text{hf}}}\frac{d\hat{S}_{x}}{dt}(t)\sin(\omega_{0}t)\mathop{}\\!\mathrm{d}t\approx\frac{1}{8}\omega_{0}e^{-nT_{\text{hf}}/T_{2}}\sin\left[\gamma_{H}B_{0}\int_{0}^{nT_{\text{hf}}}\mathcal{K}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}\right]\approx\frac{1}{8}\omega_{0}e^{-nT_{\text{hf}}/T_{2}}\gamma_{H}B_{0}\int_{0}^{nT_{\text{hf}}}\mathcal{K}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime},$
(30)

where the last approximation holds for small magnetic fields.

The magnetic field $B_{0}$ can be estimated by minimizing with respect to the
parameter $B_{0}$ the $\chi^{2}$ function:

$\chi^{2}=\sum_{n=0}^{M}\left[\frac{1}{8}\omega_{0}e^{-nT_{\text{hf}}/T_{2}}\gamma_{H}B_{0}\int_{0}^{nT_{\text{hf}}}\mathcal{K}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}-\xi(nT_{\text{hf}})\right]^{2},$
(31)

where $MT_{\text{hf}}$ is the total measurement time. The above equation can
be viewed as a curve fitting problem with unknown parameter $B_{0}$ for a
noisy signal. The solution to the curve fitting problem is:

$B_{0}=\frac{\sum_{n=0}^{M}\xi(nT_{\text{hf}})e^{-nT_{\text{hf}}/T_{2}}\int_{0}^{nT_{\text{hf}}}\mathcal{K}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}}{\gamma_{H}\sum_{n=0}^{K}\frac{1}{8}\omega_{0}e^{-2nT_{\text{hf}}/T_{2}}\left(\int_{0}^{nT_{\text{hf}}}\mathcal{K}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}\right)^{2}},$
(32)

and the estimation uncertainty in $B_{0}$ due to the spin-projection noise is:

$\delta
B_{0}^{2}=\frac{\sum_{n^{\prime}=0}^{M}\sum_{n=0}^{M}\langle\xi(nT_{\text{hf}})\xi(n^{\prime}T_{\text{hf}})\rangle
e^{-(n+n^{\prime})T_{\text{hf}}/T_{2}}\int_{0}^{nT_{\text{hf}}}\mathcal{K}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}\int_{0}^{n^{\prime}T_{\text{hf}}}\mathcal{K}(t^{\prime\prime})\mathop{}\\!\mathrm{d}t^{\prime\prime}}{\gamma_{H}^{2}\left[\sum_{n=0}^{K}\frac{1}{8}\omega_{0}e^{-2nT_{\text{hf}}/T_{2}}\left(\int_{0}^{nT_{\text{hf}}}\mathcal{K}(t^{\prime})\mathop{}\\!\mathrm{d}t^{\prime}\right)^{2}\right]^{2}}.$
(33)

From Eqs. 28 and 29 we find (in the limit of $\omega_{0}\gg\gamma$):

$\langle\xi(nT_{\text{hf}})\xi(n^{\prime}T_{\text{hf}})\rangle=\frac{1}{32}\omega_{0}^{2}e^{-\left|(n-n^{\prime})\right|T_{\text{hf}}/T_{2}},$
(34)

so that:

$\delta
B_{0}^{2}=2\frac{\int_{0}^{T_{m}}\int_{0}^{T_{m}}\mathop{}\\!\mathrm{d}t\mathop{}\\!\mathrm{d}t^{\prime}e^{-\left(t+t^{\prime}\right)/T_{2}}e^{-\left|t-t^{\prime}\right|/T_{2}}\int_{0}^{t}\mathcal{K}(x^{\prime})\mathop{}\\!\mathrm{d}x^{\prime}\int_{0}^{t^{\prime}}\mathcal{K}(x)\mathop{}\\!\mathrm{d}x}{\left[\gamma_{H}\int_{0}^{T_{m}}\mathop{}\\!\mathrm{d}te^{-2t/T_{2}}\left(\int_{0}^{t}\mathcal{K}(x)\mathop{}\\!\mathrm{d}x\right)^{2}\right]^{2}},$
(35)

where $T_{m}$ is the measurement time for a single run of the experiment.

The above derivation applies to a measurement a single H atom. For
$N_{\text{SPH}}$ independent (absence of spin-squeezing) H atoms the
uncertainty in magnetic field estimation is:

$\delta
B_{0}^{2}=\frac{2}{N_{\text{SPH}}}\frac{\int_{0}^{T_{m}}\int_{0}^{T_{m}}\mathop{}\\!\mathrm{d}t\mathop{}\\!\mathrm{d}t^{\prime}e^{-\left(t+t^{\prime}\right)/T_{2}}e^{-\left|t-t^{\prime}\right|/T_{2}}\int_{0}^{t}\mathcal{K}(x^{\prime})\mathop{}\\!\mathrm{d}x^{\prime}\int_{0}^{t^{\prime}}\mathcal{K}(x)\mathop{}\\!\mathrm{d}x}{\left[\gamma_{H}\int_{0}^{T_{m}}\mathop{}\\!\mathrm{d}te^{-2t/T_{2}}\left(\int_{0}^{t}\mathcal{K}(x)\mathop{}\\!\mathrm{d}x\right)^{2}\right]^{2}}.$
(36)

##  III Summary

We developed analytical equations describing the operation of the SPH
magnetometer shown in Fig. 1. The time evolution of the quantum state for a
time-varying magnetic field was derived and the magnetometer signal was shown
to exhibit first order dependence to the sensed field. Finally, the effect of
spin-projection noise on the estimation of magnetic field was considered,
deriving a formulation for an arbitrary waveform.

##  IV Acknowledgements

This work was supported by the Hellenic Foundation for Research and Innovation
(HFRI) and the General Secretariat for Research and Technology (GSRT), grant
agreement No HFRI-FM17-3709 (project NUPOL) and by the project “HELLAS-CH”
(MIS 5002735), which is implemented under the “Action for Strengthening
Research and Innovation Infrastructures”, funded by the Operational Programme
“Competitiveness, Entrepreneurship and Innovation” (NSRF 2014-2020) and
cofinanced by Greece and the European Union (European Regional Development
Fund).

## References

  * (1) Pavel Ripka.  Magnetic Sensors and Magnetometers.  Artech House Publishers, 2001.
  * (2) Alexandros K. Spiliotis, Michail Xygkis, Konstantinos Tazes, George E. Katsoprinakis, Georgios Vasilakis, and T. Peter Rakitzis.  A nanosecond-resolved atomic hydrogen magnetometer, 2020.
  * (3) T. P. Rakitzis, P. C. Samartzis, R. L. Toomes, T. N. Kitsopoulos, Alex Brown, G. G. Balint-Kurti, O. S. Vasyutinskii, and J. A. Beswick.  Spin-polarized hydrogen atoms from molecular photodissociation.  Science, 300(5627):1936–1938, 2003.
  * (4) Dimitris Sofikitis, Luis Rubio-Lago, Lykourgos Bougas, Andrew J. Alexander, and T. Peter Rakitzis.  Laser detection of spin-polarized hydrogen from HCl and HBr photodissociation: Comparison of H- and halogen-atom polarizations.  The Journal of Chemical Physics, 129(14):144302, 2008.
  * (5) Rakitzis T. P.  Pulsed-laser production and detection of spin-polarized hydrogen atoms.  Chemphyschem : a European journal of chemical physics and physical chemistry, 5:1489–1494, 2004.
  * (6) S. Blanes, F. Casas, J.A. Oteo, and J. Ros.  The magnus expansion and some of its applications.  Physics Reports, 470(5):151 – 238, 2009.