$\displaystyle\leq\int_{E\times{\mathcal{X}}}b(x,z)\nu_{v}(dx,dz)+\int_{E\times{\mathcal{X}}}\left[d(z)+c\int_{{\mathcal{X}}}\nu_{v}^{(x)}(de)\right]\nu_{v}(dx,dz)+\int_{{{\mathcal{V}}_{p}}\times{\mathcal{D}}}\bar{\beta}\,{\nu_{v}}(dx,dz)\,{\nu_{u}}(dy)$
(A.1) $\displaystyle+\int_{{{\mathcal{V}}_{c}}\times
E}\bar{\eta}\,{\nu_{c}}(dy,dz)\,\zeta_{E}(dx)+\int_{{{\mathcal{V}}_{c}}}\gamma(z)\,{\nu_{c}}(dy,dz),$

We conclude using Assumption 1 and setting:

$C=\max\left\\{\bar{b},\bar{d},\bar{\gamma},\bar{\beta},\bar{\eta},c\right\\}.$

∎

###  A.1. Path-wise construction of the process

In this section we rigorously define the Markov processes on path space
$\mathcal{D}([0,\infty),{\mathcal{M}}_{F})$, with generator ${\mathcal{L}}$
given by (1.3). Following [23], we provide an specific construction in terms
of Poisson point measures.

Let us introduce some additional notation. Let
${\mathbb{N}}^{*}={\mathbb{N}}\setminus\\{0\\}$. Let $\lambda$ be the Lebesgue
measure on ${\mathbb{R}}_{+}$, $\lambda_{c}$ the counting measure on
${\mathbb{N}}^{*}$ and $\zeta_{E}$ the counting measure on $E$. Moreover, for
all $t\geq 0$, we introduce the following notation:

${\mathcal{A}}(t)=[0,t]\times{\mathbb{N}}^{*}\times{\mathbb{R}}_{+}$

######  Definition A.2.

Let $(\Omega,{\mathcal{F}},{\mathbb{P}})$ be a sufficiently large probability
space. On this probability space we consider the following independent random
elements:

  * •

$Q_{inf}$ a Poisson random measure on
${\mathbb{R}}_{+}\times{\mathbb{N}}^{*}\times{\mathbb{N}}^{*}\times{\mathbb{R}}_{+}$,
with intensity
$\lambda(ds)\otimes\lambda_{c}(di)\otimes\lambda_{c}(dj)\otimes\lambda(d\theta)$,

  * •

$Q_{dis}$ a Poisson random measure on ${\mathbb{R}}_{+}\times
E\times{\mathbb{N}}^{*}\times{\mathbb{R}}_{+}$, with intensity
$\lambda(ds)\otimes\zeta_{E}(dx)\otimes\lambda_{c}(dj)\otimes\lambda(d\theta)$,

  * •

$Q_{los}$, $Q_{d}$, $Q_{cb}$ Poisson random measures on
${\mathbb{R}}_{+}\times{\mathbb{N}}^{*}\times{\mathbb{R}}_{+}$, with intensity
$\lambda(ds)\otimes\lambda_{c}(di)\otimes\lambda(d\theta)$,

  * •

$Q_{bm}$, a Poisson random measure on
${\mathbb{R}}_{+}\times{\mathbb{N}}^{*}\times\mathcal{X}\times\lambda(d\theta)$,
with intensity
$\lambda(ds)\otimes\lambda_{c}(di)\otimes\overline{m}(dz)\otimes\lambda(d\theta)$.

  * •

For $\alpha\in\\{u,c\\}$, the set $\\{W^{i,\alpha};i\geq 1\\}$ denotes a
family of independent Brownian motions in ${\mathbb{R}}^{d}$.

Moreover, we enlarge the original probability space
$(\Omega,{\mathcal{F}},{\mathbb{P}})$ to the filtered probability space
$(\Omega,{\mathcal{F}},{\mathcal{F}}_{t},{\mathbb{P}})$ , where
$({\mathcal{F}}_{t})_{t\geq 0}$ is the canonical filtration generated by
$\\{Q_{inf},Q_{dis},Q_{los},Q_{bm}\\}$ and the families $\\{W^{i,\alpha};i\geq
1\\}$ for $\alpha\in\\{u,c\\}$.

We then have the following representations:

  * •

Individuals (in the virus population) born from clonal births up to time $t$
are given by

$\displaystyle{\boldsymbol{\nu}}_{cb}(t)=\int_{{\mathcal{A}}(t)}\left(\delta_{x_{i}(s^{-}),z_{i}(s^{-})},0,0\right)\,\mathds{1}_{\left\\{i\leq
N_{v}(s^{-})\right\\}}\mathds{1}_{\left\\{\theta\leq(1-\mu)b(x_{i}(s^{-}),z_{i}(s^{-}))\right\\}}Q_{cb}(ds\,di\,d\theta).$

  * •

Individuals born with mutations are given by

$\displaystyle{\boldsymbol{\nu}}_{bm}(t)=\int_{{\mathcal{A}}(t)\times{\mathcal{X}}}\left(\delta_{x_{i}(s^{-}),z},0,0\right)\,\mathds{1}_{\left\\{i\leq
N_{v}(s^{-})\right\\}}\mathds{1}_{\left\\{\theta\leq\mu
b(x_{i}(s^{-}),z_{i}(s^{-}))m(z_{i}(s^{-}),z)\right\\}}Q_{bm}(ds\,di\,dz\,d\theta).$

  * •

Individuals who died before time $t\geq 0$ are given by

$\displaystyle{\boldsymbol{\nu}}_{d}(t)=\int_{{\mathcal{A}}(t)}\left(\delta_{x_{i}(s^{-}),z_{i}(s^{-})},0,0\right)\,\mathds{1}_{\left\\{i\leq
N_{v}(s^{-})\right\\}}\mathds{1}_{\left\\{\theta\leq
d(z_{i}(s^{-}))+cN_{x_{i}(s^{-})}(t)\right\\}}Q_{d}(ds\,di\,d\theta).$

  * •

Viruses being charged on a vector are represented by:

$\displaystyle{\boldsymbol{\nu}}_{inf}(t)=\int_{{\mathcal{A}}(t)\times{\mathbb{N}}^{*}}\left(-\delta_{x_{i}(s^{-}),z_{i}(s^{-})},-\delta_{Y_{j}(s^{-})},\delta_{Y_{j}(s^{-}),z_{i}(s^{-})}\right)\,\mathds{1}_{\left\\{i\leq
N_{v}(s^{-})\right\\}}\mathds{1}_{\left\\{j\leq N_{u}(s^{-})\right\\}}$
$\displaystyle\times\mathds{1}_{\left\\{\theta\leq\beta(s^{-},Y_{j}(s^{-}),x_{i}(s^{-}),N_{x_{i}(s^{-})},z_{i}(s^{-}))\right\\}}Q_{inf}(ds\,di\,dj\,d\theta).$

  * •

Viruses who have been unloaded on a host plant up to time $t$ are given by

$\displaystyle{\boldsymbol{\nu}}_{dis}(t)=\int_{{\mathcal{A}}(t)\times
E}\left(\delta_{x,z_{j}(s^{-})},\delta_{Y_{j}(s^{-})},-\delta_{Y_{j}(s^{-}),z_{i}(s^{-})}\right)\,\mathds{1}_{\left\\{j\leq
N_{c}(s^{-})\right\\}}\mathds{1}_{\left\\{\theta\leq\eta(s^{-},Y_{j}(s^{-}),x,z_{j}(s^{-}))\right\\}}Q_{dis}(ds\,dx\,dj\,d\theta).$

  * •

Finally, viruses dying on vectors up to time t:

$\displaystyle{\boldsymbol{\nu}}_{los}(t)=\int_{{\mathcal{A}}(t)}\left(0,\delta_{Y_{i}(s-)},-\delta_{Y_{i}(s^{-}),z_{i}(s-)}\right)\,\mathds{1}_{\left\\{i\leq
N_{c}(s^{-})\right\\}}\mathds{1}_{\left\\{\theta\leq\gamma(z_{i}(s^{-}))\right\\}}Q_{los}(ds\,di\,d\theta).$

######  Definition A.3.

The process ${\boldsymbol{\nu}}(t)=(\nu_{v}(t),{\nu_{u}}(t),{\nu_{c}}(t);t\geq
0)$ is defined as the ${\mathcal{F}}_{t}$-adapted solution to the equation:

$\displaystyle\langle{\boldsymbol{\phi}},{\boldsymbol{\nu}}(t)\rangle$
$\displaystyle=\langle{\boldsymbol{\phi}},{\boldsymbol{\nu}}(0)\rangle+\langle{\boldsymbol{\phi}},{\boldsymbol{\nu}}_{cb}(t)\rangle+\langle{\boldsymbol{\phi}},{\boldsymbol{\nu}}_{bm}(t)\rangle-\langle{\boldsymbol{\phi}},{\boldsymbol{\nu}}_{d}(t)\rangle+\langle{\boldsymbol{\phi}},{\boldsymbol{\nu}}_{inf}(t)\rangle+\langle{\boldsymbol{\phi}},{\boldsymbol{\nu}}_{dis}(t)\rangle+\langle{\boldsymbol{\phi}},{\boldsymbol{\nu}}_{los}(t)\rangle$
$\displaystyle+\int_{0}^{t}\langle\mathcal{L}^{u}{\boldsymbol{\phi}},{\boldsymbol{\nu}}(s)\rangle\,ds+\int_{0}^{t}\langle\mathcal{L}^{c}{\boldsymbol{\phi}},{\boldsymbol{\nu}}(s)\rangle\,ds+\int_{0}^{t}\sum_{i=1}^{N_{u}(s^{-})}\sigma^{u}(Y^{u}_{i}(s^{-}))\nabla\phi_{u}(Y^{u}_{i}(s^{-}))\cdot
dW^{i,u}_{s}$ (A.2)
$\displaystyle+\int_{0}^{t}\sum_{i=1}^{N_{c}(s^{-})}\sigma^{c}(Y^{c}_{i}(s^{-}))\nabla_{y}\,{\phi_{c}}(Y^{c}_{i}(s^{-}),z_{i}(s^{-}))\cdot
dW^{i,c}_{s},$

for all ${\boldsymbol{\phi}}\in\Phi({\mathcal{M}}_{p})$, and
${\mathcal{L}}^{\alpha}{\boldsymbol{\phi}}$ is given as in Remark 1.

######  Remark 14.

The diffusion of vectors forces us to integrate the equation as observed in
[2] (see in particular equation 3.2, which contains analogous terms).

The following proposition gives conditions to guarantee that a solution to
(A.3) follows the dynamics given by the generator ${\mathcal{L}}$ given in
(1.3).

######  Proposition A.4.

Let $\left({\boldsymbol{\nu}}_{t}\right)_{t\geq
0}=(\nu_{v}(t),{\nu_{u}}(t),{\nu_{c}}(t);t\geq 0)$ be a solution of (A.3) such
that for all $T>0$ we have

${\mathbb{E}}\left(\sup_{t\leq
T}<\mathbf{1},{\boldsymbol{\nu}}_{t}>^{2}\right)<\infty,$

where $\mathbf{1}\in\Phi({\mathcal{M}}_{p})$ denotes the admissible triplet
with all functions equal to the constant 1. Then, under Assumption 1, the
process $\left({\boldsymbol{\nu}}_{t}\right)_{t\geq 0}$ is Markov with
infinitesimal generator ${\mathcal{L}}$ given by (1.3).

###### Proof.

The fact that it is Markov is standard. We need to verify that the generator
is the one we claimed. We will use Itô’s lemma (see for example Theorem 5.1 in
[17]) applied to (A.3) to find an expression for
$F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(t))$. Let us split this in two,
one part coming from jump events, and the other from diffusion, as follows:

$F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(t))-F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(0))=(F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(t))-F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(0)))_{\text{Jump}}+(F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(t))-F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(0)))_{\text{Diff}}$

The way to verify that this corresponds to the generator ${\mathcal{L}}$ is to
take expectations and later differentiate with respect to time. We refer to
[23], Proposition 6.3 in particular, for the same procedure in the absence of
diffusion. Let us do this for the diffusive part of the generator. Notice that
by Itô’s lemma, the diffusive part is given by:

$\displaystyle(F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(t))$ $\displaystyle-
F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}(0)))_{\text{Diff}}=\int_{0}^{t}F_{{\boldsymbol{\phi}}}^{\prime}\mkern-1.2mu({\boldsymbol{\nu}}(s))\langle\mathcal{L}^{u}{\boldsymbol{\phi}},{\boldsymbol{\nu}}(s)\rangle\,ds+\int_{0}^{t}F_{{\boldsymbol{\phi}}}^{\prime}\mkern-1.2mu({\boldsymbol{\nu}}(s))\sum_{i=1}^{N_{u}(s^{-})}\sigma^{u}(Y^{u}_{i}(s^{-}))\nabla\phi_{u}(Y^{u}_{i}(s^{-}))\cdot
dW^{i,u}_{s}$
$\displaystyle+\frac{1}{2}\int_{0}^{t}F_{{\boldsymbol{\phi}}}^{\prime\prime}\mkern-1.2mu({\boldsymbol{\nu}}(s))\sum_{i=1}^{N_{u}(s^{-})}\sigma^{u}(Y^{u}_{i}(s^{-}))^{2}\mid\nabla\phi_{u}(Y^{u}_{i}(s^{-}))\mid^{2}\,ds+\int_{0}^{t}F_{{\boldsymbol{\phi}}}^{\prime}\mkern-1.2mu({\boldsymbol{\nu}}(s))\langle\mathcal{L}^{c}{\boldsymbol{\phi}},{\boldsymbol{\nu}}(s)\rangle\,ds$
$\displaystyle+\int_{0}^{t}F_{{\boldsymbol{\phi}}}^{\prime}\mkern-1.2mu({\boldsymbol{\nu}}(s))\sum_{i=1}^{N_{c}(s^{-})}\sigma^{c}(Y^{c}_{i}(s^{-}))\nabla_{y}\,{\phi_{c}}(Y^{c}_{i}(s^{-}),z_{i}(s^{-}))\cdot
dW^{i,c}_{s}$
$\displaystyle+\frac{1}{2}\int_{0}^{t}F_{{\boldsymbol{\phi}}}^{\prime\prime}\mkern-1.2mu({\boldsymbol{\nu}}(s))\sum_{i=1}^{N_{c}(s^{-})}\sigma^{c}(Y^{c}_{i}(s^{-}))^{2}\mid\nabla_{y}\,{\phi_{c}}(Y^{c}_{i}(s^{-}),z_{i}(s^{-}))\mid^{2}\,ds.$

In order to verify that we get the second part of the generator
${\mathcal{L}}$, we have to proceed as before. Notice however, that by taking
expectations the Itô integrals vanish. Differentiating what is left at $t=0$
leads to the RHS of (1). ∎

Now we show the well-definedness of the process
$({\boldsymbol{\nu}}_{t})_{t\geq 0}$. That is, Theorem 1.3. Moreover we show
that a control of the $p$-th moment at time zero can be extended to later
times. More precisely, we show the following proposition:

######  Proposition A.5.

Let ${\boldsymbol{\nu}}_{0}=({\nu_{v}}(0),{\nu_{u}}(0),{\nu_{c}}(0))$ be such
that for some $p\geq 1$, we have:

(A.3)
$\mathbb{E}\left(\langle\mathbf{1},{\boldsymbol{\nu}}_{0}\rangle^{p}\right)<\infty$

Then, under Assumption 1, the process
$\left({\boldsymbol{\nu}}_{t}\right)_{t\geq
0}=\left(\nu_{v}(t),{\nu_{u}}(t),{\nu_{c}}(t):t\geq 0\right)$ satisfies:

(A.4)
$\mathbb{E}\left(\sup_{t\in[0,T]}\langle\mathbf{1},{\boldsymbol{\nu}}_{t}\rangle^{p}\right)<\infty$

In particular, if (A.3) holds for $p=1$, we also have that the process
$\nu_{t}$ is well defined.

###### Proof.

To show (A.4), because the number of vectors is invariant under the dynamics,
it is enough to show:

$\mathbb{E}\left(\sup_{t\in[0,T]}\langle
1,{\nu_{v}}(t)\rangle^{p}\right)<\infty.$

In order to do so, we use a stopping time argument. Let us define $\tau_{n}$
as follows:

$\tau_{n}=\inf\left\\{t\geq 0:\langle 1,{\nu_{v}}(t)\rangle\geq n\right\\}$

Let us also consider $F_{p}:{\mathcal{M}}_{p}^{\alpha}\to{\mathbb{R}}$ given
by the choice:

$F_{p}({\boldsymbol{\nu}})=\left(\langle
1,{\nu_{v}}\rangle\right)^{p}+\left(\langle 1,{\nu_{c}}\rangle\right)^{p}.$

Hence, by (A.3) we have:

$\displaystyle\sup_{s\in[0,t\wedge\tau_{n}]}$ $\displaystyle\langle
1,{\nu_{v}}(s)\rangle^{p}\leq\langle 1,{\nu_{v}}(0)\rangle^{p}$
$\displaystyle+\int_{0}^{t\wedge\tau_{n}}\int_{{\mathbb{N}}^{*}\times{\mathbb{R}}_{+}}\left[(\langle
1,{\nu_{v}}(s-)\rangle+1)^{p}-\langle
1,{\nu_{v}}(s-)\rangle^{p}\right]\,\mathds{1}_{\left\\{i\leq
N_{v}(s^{-})\right\\}}\mathds{1}_{\left\\{\theta\leq(1-\mu)b(x_{i}(s^{-}),z_{i}(s^{-}))\right\\}}Q_{cb}(ds\,di\,d\theta)$
$\displaystyle+\int_{0}^{t\wedge\tau_{n}}\int_{{\mathbb{N}}^{*}\times{\mathbb{R}}_{+}\times
E}\left[(\langle 1,{\nu_{v}}(s-)\rangle+1)^{p}-\langle
1,{\nu_{v}}(s-)\rangle^{p}\right]\,\mathds{1}_{\left\\{j\leq
N_{c}(s^{-})\right\\}}\mathds{1}_{\left\\{\theta\leq\eta(s^{-},Y_{j}(s^{-}),x,z_{j}(s^{-}))\right\\}}Q_{dis}(ds\,dx\,dj\,d\theta)$
$\displaystyle+\int_{0}^{t\wedge\tau_{n}}\int_{{\mathbb{N}}^{*}\times\mathcal{X}\times{\mathbb{R}}_{+}}\left[(\langle
1,{\nu_{v}}(s-)\rangle+1)^{p}-\langle
1,{\nu_{v}}(s-)\rangle^{p}\right]\mathds{1}_{\left\\{i\leq
N_{v}(s^{-})\right\\}}\mathds{1}_{\left\\{\theta\leq\mu
b(x_{i}(s^{-}),z_{i}(s^{-}))m(z_{i}(s^{-}),z)\right\\}}Q_{bm}(ds\,di\,dz\,d\theta).$

where the diffusion terms vanished due to the presences of derivatives of the
constant function $1$, and we have dropped the integral terms with a negative
contribution (death terms, and loading terms).

Taking expectations and using the bounds given by Assumption 1 we obtain:

$\displaystyle{\mathbb{E}}\left[\sup_{s\in[0,t\wedge\tau_{n}]}\langle
1,{\nu_{v}}(s)\rangle^{p}\right]$ $\displaystyle\leq{\mathbb{E}}\left[\langle
1,{\nu_{v}}(0)\rangle^{p}\right]+C{\mathbb{E}}\left[\int_{0}^{t\wedge\tau_{n}}N_{v}(s)\left[(\langle
1,{\nu_{v}}(s)\rangle+1)^{p}-\langle
1,{\nu_{v}}(s)\rangle^{p}\right]\,\right]\,ds$
$\displaystyle+C{\mathbb{E}}\left[\int_{0}^{t\wedge\tau_{n}}\left[(\langle
1,{\nu_{v}}(s)\rangle+1)^{p}-\langle
1,{\nu_{v}}(s)\rangle^{p}\right]\right]\,ds.$ $\displaystyle\leq
C\left(1+{\mathbb{E}}\left[\int_{0}^{t\wedge\tau_{n}}N_{v}(s)\left[(\langle
1,{\nu_{v}}(s)\rangle+1)^{p}-\langle
1,{\nu_{v}}(s)\rangle^{p}\right]\,ds\right]\right)$

where the constant $C$ changed its value incorporating the constant given by
(A.3).

Using the fact that $N_{v}(s)\leq\langle 1,{\nu_{v}}(s)\rangle$, and the
simple inequality $(x+1)^{p}-x^{p}\leq C_{p}(1+x^{p-1})$, we obtain:

$\displaystyle{\mathbb{E}}\left[\sup_{s\in[0,t\wedge\tau_{n}]}\langle
1,{\nu_{v}}(s)\rangle^{p}\right]$ $\displaystyle\leq
C_{p}\left(1+{\mathbb{E}}\left[\int_{0}^{t}\left[\langle
1,{\nu_{v}}(s\wedge\tau_{n})\rangle+\langle
1,{\nu_{v}}(s\wedge\tau_{n})\rangle^{p}\right]\,ds\right]\right)$
$\displaystyle\leq C_{p}\left(1+{\mathbb{E}}\left[\int_{0}^{t}\langle
1,{\nu_{v}}(s\wedge\tau_{n})\rangle^{p}\,ds\right]\right)$

where again the constant $C_{p}$ changed its value incorporating new
constants.

By Gronwalls inequality we then have:

(A.5) ${\mathbb{E}}\left[\sup_{s\in[0,t\wedge\tau_{n}]}\langle
1,{\nu_{v}}(s)\rangle^{p}\right]\leq C_{p}e^{C_{p}t}$

for some constant $C_{p}$ independent of $n$.

From (A.5) we can deduce that $\tau_{n}$ goes to infinity as $n\to\infty$ a.s.
We then apply Fatou’s lemma to conclude:

${\mathbb{E}}\left[\sup_{s\in[0,t]}\langle
1,{\nu_{v}}(s)\rangle^{p}\right]\leq\liminf_{n\to\infty}{\mathbb{E}}\left[\sup_{s\in[0,t\wedge\tau_{n}]}\langle
1,{\nu_{v}}(s)\rangle^{p}\right]\leq C_{p}e^{C_{p}t}.$

To conclude the well-definedness of the process $\nu_{t}$ one has to construct
the process step by step, where the time steps are given by a sequence of jump
instants $T_{n}$ exponentially distributed with law:

$R(\nu_{n-1})e^{-R(\nu_{n-1})t}$

and where the total jump rate $R(\nu)$ is given by (A).

It is then enough to check that the sequence $T_{n}$ goes to infinity almost
surely. This follows from

${\mathbb{E}}\left(\sup_{t\in[0,T]}\langle
1,{\boldsymbol{\nu}}_{t}\rangle\right)<\infty$

which is a consequence of (A.4) when $p=1$. ∎

###  A.2. Relevant martingales

Now we will introduce a few martingales that are relevant when computing
scaling limits. Let us start from a simple application of Dynkin’s theorem:

######  Proposition A.6.

Let $\nu_{0}=({\nu_{v}}(0),{\nu_{u}}(0),{\nu_{c}}(0))$ be such that for some
$p\geq 2$ we have:

$\mathbb{E}\left(\langle 1,{\nu_{v}}_{0}\rangle^{p}\right)<\infty$

Let also $F\in\mathcal{C}^{2}({\mathbb{R}})$ and
${\boldsymbol{\phi}}\in\Phi({\mathcal{M}}_{p})$, be such that there exists a
$C$, possibly dependent on $F$ and ${\boldsymbol{\phi}}$, such that:

(A.6)
$|F_{{\boldsymbol{\phi}}}(\nu)|+|{\mathcal{L}}F_{{\boldsymbol{\phi}}}(\nu)|\leq
C\,\left(1+\langle\nu,\mathbf{1}\rangle^{p}\right)$

where $F_{\boldsymbol{\phi}}$ is given as in Definition 1.2

Then, under Assumption 1, we have that the process

(A.7)
$M_{t}(F_{{\boldsymbol{\phi}}})=F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}_{t}))-F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}_{0})-\int_{0}^{t}{\mathcal{L}}F_{{\boldsymbol{\phi}}}({\boldsymbol{\nu}}_{s})\,ds$

is a càdlàg martingale.

###### Proof.

From Proposition A.4 and Dynkin’s theorem we know that $M_{t}(F_{\alpha})$ is
a local martingale. Hence, it is enough to show that the R.H.S. of (A.7) is
integrable. This is a consequence of Assumption (A.6) and Proposition A.5. ∎

######  Remark 15.

Simple but tedious computations show that for, $1\leq q\leq p-1$,
$\phi_{v}\in\mathcal{C}_{b}^{2}({{\mathcal{V}}_{p}}),{\phi_{u}}\in\mathcal{C}_{b}^{2}({\mathcal{D}})\cap
D({\mathcal{L}}^{u})$ and
${\phi_{c}}\in\mathcal{C}_{b}^{2}({{\mathcal{V}}_{c}})\cap
D({\mathcal{L}}^{c})$, the functions

$\displaystyle
F_{v}^{q}(\nu_{v}):=\left(\langle{\phi_{v}},{\nu_{v}}\rangle\right)^{q},\quad
F_{u}^{q}({\nu_{u}}):=\left(\langle{\phi_{u}},{\nu_{u}}\rangle\right)^{q},\text{
and
}F_{c}^{q}({\nu_{c}}):=\left(\langle{\phi_{c}},{\nu_{c}}\rangle\right)^{q}$

satisfy (A.6).

The following result is a consequence of Proposition A.6 and Remark 15

######  Proposition A.7.

Let ${\phi_{v}}\in\mathcal{C}_{b}^{2}({{\mathcal{V}}_{p}}),{\phi_{u}}\in
D({\mathcal{L}}^{u})$ and ${\phi_{c}}\in D({\mathcal{L}}^{c})$, under
Assumption 1, we have the following càdlàg martingales:

  1. (1)

For the virus population:

$\displaystyle M_{t}^{\phi_{v}}$
$\displaystyle=\langle{\nu_{v}}(t),{\phi_{v}}\rangle-\langle{\nu_{v}}(0),{\phi_{v}}\rangle-\int_{0}^{t}\int_{{{\mathcal{V}}_{p}}}b(x,z){\phi_{v}}(x,z){\nu_{v}}(s)(dx,dz)\,ds$
$\displaystyle+\mu\int_{0}^{t}\int_{{{\mathcal{V}}_{p}}}b(x,z)\left[{\phi_{v}}(x,z)-\int_{{\mathcal{X}}}m(z,z^{\prime}){\phi_{v}}(x,z^{\prime})\,dz^{\prime}\right]{\nu_{v}}(s)(dx,dz)\,ds$
$\displaystyle+\int_{0}^{t}\left[\int_{{{\mathcal{V}}_{p}}}\left(d(z)+c\langle{\nu_{v}}^{x},1\rangle\right){\phi_{v}}(x,z){\nu_{v}}(s)(dx,dz)+\int_{{{\mathcal{V}}_{p}}\times{\mathcal{D}}}\beta(s,y,x,\langle{\nu_{v}}^{x},1\rangle,z)\phi_{v}(x,z){\nu_{v}}(s)(dx,dz)\,{\nu_{u}}(s)(dy)\right]ds$
(A.8) $\displaystyle-\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}\times
E}\eta(s,y,x,z){\phi_{v}}(x,z)\,{\nu_{c}}(s)(dy,dz)\,dx\,ds$

is a càdlàg martingale with predictable quadratic variation

$\displaystyle\langle M^{\phi_{v}}\rangle_{t}$
$\displaystyle=(1-\mu)\int_{0}^{t}\int_{{{\mathcal{V}}_{p}}}b(x,z)\,\phi_{v}(x,z)^{2}\,\nu_{v}(s)(dx,dz)\,ds+\mu\int_{0}^{t}\int_{{{\mathcal{V}}_{p}}\times{\mathcal{X}}}b(x,z)m(z,z^{\prime})\,{\phi_{v}}(x,z^{\prime})^{2}\,dz^{\prime}{\nu_{v}}(s)(dx,dz)\,ds$
$\displaystyle+\int_{0}^{t}\int_{{{\mathcal{V}}_{p}}}\left(d(z)+c\langle{\nu_{v}}^{x},1\rangle\right)\,{\phi_{v}}(x,z)^{2}\,{\nu_{v}}(s)(dx,dz)+\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}\times
E}\eta(s,y,x,z)\,{\phi_{v}}(x,z)^{2}\,{\nu_{c}}(s)(dy,dz)\,dx\,ds$ (A.9)
$\displaystyle+\int_{0}^{t}\int_{{{\mathcal{V}}_{p}}\times{\mathcal{D}}}\beta(s,y,x,\langle{\nu_{v}}^{x},1\rangle,z)\,\phi_{v}(x,z)^{2}\,{\nu_{v}}(s)(dx,dz)\,{\nu_{u}}(s)(dy)ds$

  2. (2)

For the free-vector population:

$\displaystyle M_{t}^{{\phi_{u}}}$
$\displaystyle=\langle{\nu_{u}}(t),{\phi_{u}}\rangle-\langle{\nu_{u}}(0),{\phi_{u}}\rangle-\int_{0}^{t}\int_{{\mathcal{D}}}{\mathcal{L}}^{u}{\phi_{u}}(y)\,{\nu_{u}}(s)(dy)\,ds-\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}\times
E}\eta(s,y,x,z){\phi_{u}}(y){\nu_{c}}(s)(dy,dz)\,dx\,ds$ (A.10)
$\displaystyle+\int_{0}^{t}\left[\int_{{{\mathcal{V}}_{p}}\times{\mathcal{D}}}\beta(s,y,x,\langle{\nu_{v}}^{x},1\rangle,z){\phi_{u}}(y){\nu_{v}}(s)(dx,dz)\,{\nu_{u}}(s)(dy)-\int_{{{\mathcal{V}}_{c}}}\gamma(z){\phi_{u}}(y)\,{\nu_{c}}(s)(dy,dz)\right]ds$

is a càdlàg martingale with predictable quadratic variation

$\displaystyle\langle M^{{\phi_{u}}}\rangle_{t}$
$\displaystyle=\int_{0}^{t}\int_{{\mathcal{D}}}\sigma^{u}(y)^{2}\,|\nabla{\phi_{u}}(y)|^{2}\,{\nu_{u}}(s)(dy)\,ds+\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}\times
E}\eta(s,y,x,z){\phi_{u}}(y)^{2}{\nu_{c}}(s)(dy,dz)\,dx\,ds$
$\displaystyle+\int_{0}^{t}\int_{{{\mathcal{V}}_{p}}\times{\mathcal{D}}}\beta(s,y,x,\langle{\nu_{v}}^{x},1\rangle,z)\,{\phi_{u}}(y)^{2}\,{\nu_{v}}(s)(dx,dz)\,{\nu_{u}}(s)(dy)ds+\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}}\gamma(z){\phi_{u}}(y)^{2}\,{\nu_{c}}(s)(dy,dz)\,ds$

  3. (3)

For the charged-vector population:

$\displaystyle M_{t}^{{\phi_{c}}}$
$\displaystyle=\langle{\nu_{c}}(t),{\phi_{c}}\rangle-\langle{\nu_{c}}(0),{\phi_{c}}\rangle-\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}}{\mathcal{L}}^{c}{\phi_{c}}(y,z)\,{\nu_{c}}(s)(dy,dz)\,ds+\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}\times
E}\eta(s,y,x,z){\phi_{c}}(y,z){\nu_{c}}(s)(dw,du)\,dx\,ds$ (A.11)
$\displaystyle-\int_{0}^{t}\left[\int_{{{\mathcal{V}}_{p}}\times{\mathcal{D}}}\beta(s,y,x,\langle{\nu_{v}}^{x},1\rangle,z){\phi_{c}}(y,z){\nu_{v}}(s)(dx,dz)\,{\nu_{u}}(s)(dy)-\int_{{{\mathcal{V}}_{c}}}\gamma(y){\phi_{c}}(y,z)\,{\nu_{c}}(s)(dy,dz)\right]ds$

is a càdlàg martingale with quadratic variation

$\displaystyle\langle M^{{\phi_{c}}}\rangle_{t}$
$\displaystyle=\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}}\sigma^{c}(y)^{2}|\nabla_{y}{\phi_{c}}(y,z)|^{2}\,{\nu_{c}}(s)(dy,dz)\,ds+\int_{0}^{t}\int_{{{\mathcal{V}}_{c}}\times
E}\eta(s,y,x,z){\phi_{c}}(y,z)^{2}{\nu_{c}}(s)(dy,dz)\,dx\,ds$
$\displaystyle+\int_{0}^{t}\left[\int_{{{\mathcal{V}}_{p}}\times{\mathcal{D}}}\beta(s,y,x,\langle{\nu_{v}}^{x},1\rangle,z){\phi_{c}}(y,z)^{2}{\nu_{v}}(s)(dx,dz)\,{\nu_{u}}(s)(dy)+\int_{{{\mathcal{V}}_{c}}}\gamma(y){\phi_{c}}(y,z)^{2}\,{\nu_{c}}(s)(dy,dz)\right]ds$

###### Proof.

Assume $p\geq 3$. By Theorem A.6 and Remark 15 with $q=1$, we have that (1),
(2), and (3) are càdlàg martingales. For the predictable quadratic variation
we just use Remark 15 with $q=2$, and Itô formula toghether with the Doob-
Meyer decomposition. See [23] for examples on a similar context. ∎


# MT3: Meta Test-Time Training for Self-Supervised Test-Time Adaption

Alexander Bartler, Andre Bühler, Felix Wiewel, Mario Döbler and Bin Yang
Institute of Signal Processing and System Theory, University of Stuttgart,
Germany
{alexander.bartler, felix.wiewel, mario.doebler<EMAIL_ADDRESS>stuttgart.de

###### Abstract

An unresolved problem in Deep Learning is the ability of neural networks to
cope with domain shifts during test-time, imposed by commonly fixing network
parameters after training. Our proposed method Meta Test-Time Training (MT3),
however, breaks this paradigm and enables adaption at test-time. We combine
meta-learning, self-supervision and test-time training to learn to adapt to
unseen test distributions. By minimizing the self-supervised loss, we learn
task-specific model parameters for different tasks. A meta-model is optimized
such that its adaption to the different task-specific models leads to higher
performance on those tasks. During test-time a single unlabeled image is
sufficient to adapt the meta-model parameters. This is achieved by minimizing
only the self-supervised loss component resulting in a better prediction for
that image. Our approach significantly improves the state-of-the-art results
on the CIFAR-10-Corrupted image classification benchmark. Our implementation
is available on GitHub.111https://github.com/AlexanderBartler/MT3

##  1 Introduction

Deep neural networks have dramatically improved the results in a wide range of
applications. However, after they are deployed the distribution of test data
may be very different compared to the distribution of the training data.
During testing, samples may be corrupted by, e.g., noise, different lighting
conditions, or environmental changes such as snow or fog (see Figure 1). These
corruptions and the resulting distribution shifts can cause a dramatic drop in
performance [3, 17]. Even truly unseen test images without a large
distribution shift can harm the model performance [29]. Adversarial
perturbations are examples for an intentional distribution shift, that is not
recognizable to humans, but also reduces model performance drastically.

(a) original

(b) snow

(c) fog

(d) glass blur

(e) impulse

Figure 1: Example of a CIFAR-10 image with different corrupted versions of the
most severe level taken from the CIFAR-10-Corrupted dataset.

To address changes in the test distribution and the resulting performance
drop, recent work has mainly focused on the robustness to adversarial examples
[6, 9, 10, 20, 31] or the generalization to out-of-distribution samples [1,
16, 23]. Both areas aim to train a model in order to be robust against various
types of unknown corruptions, distribution shifts, or domain shifts during
testing. Another concept assumes that during training multiple unlabeled
samples of the target domain are available and therefore unsupervised domain
adaptation (UDA) can be performed [32, 34, 35, 37]. In the extreme case of
one-shot UDA, only one unlabeled sample of the target domain is available
during training [26, 5].

On the contrary, it is possible to account for distribution shifts only during
test-time using a single test image under the assumption that the test image
contains information about the distribution it originates from. Since the
adaption to a single test sample is then performed by adapting the model at
test-time, there is no need for any test data or information about the test
distribution during the training stage. Additionally, in contrast to UDA,
neither the original training data is needed for the adaption to a new test
sample nor the test samples have to be drawn from the same distribution, since
each test sample is processed individually. The assumption that each test
sample can be corrupted differently could occur more likely in practice than
having a persistent shift of the test distribution after deployment. For the
concept of adaption during test-time, the model can be quickly adapted using
only the sample itself, where in one-shot UDA the complete training dataset is
additionally used to train a model on the target domain. If the target
distribution is not stationary, the one-shot UDA has to be applied for each
test sample individually, which would result in a tremendous testing
complexity.

#### Test-Time Training

The concept of adaption during test-time was first proposed in [30] and is
called Test-Time Training (TTT). In order to train a model which is able to
adapt to unseen images, [30] proposed to train the model using a supervised
and a self-supervised loss jointly, denoted as joint training. During testing,
only the self-supervised loss on one unlabeled test image is applied to adapt
the model parameters which is hence called test-time training. After that, the
refined model is used for inference. This test-time adaption is done for each
test sample individually starting from the initially trained model.

The used architecture has two heads and a shared feature extractor. One head
is used for the supervised downstream task, e.g., for classification the
minimizization of the categorical cross-entropy loss. The second head enables
self-supervised learning. It solves a simple auxiliary task of rotation
prediction, where four different rotation angles have to be predicted in a
four-way classification problem [12].

During testing, a batch of augmented views of a single image is used to
minimize only the self-supervised loss subsequently to adapt the shared
feature extractor while keeping the head for the supervised downstream task
unchanged. The adapted model is used to make the prediction of the test
sample. In addition, the authors in [30] showed under strong assumptions that
minimizing the self-supervised loss during testing implicitly minimizes the
supervised loss.

While for the standard test procedure the adapted model is only used for a
single image, the authors proposed an online setting where the model
parameters are adapted sequentially during testing with a stream of test
samples of a stationary or gradually changing test distribution. This online
setting can be seen as online unsupervised domain adaption.

#### Self-Supervised Learning

In [30] the rather simple auxiliary task of rotation prediction [12] is used
for self-supervision. Recent state-of-the-art approaches for representation
learning, on the other hand, rely on constrastive learning [7, 8, 14, 33]. The
key idea of contrastive learning is to jointly maximize the similarity of
representations of augmented views of the same image while minimizing the
similarity of representations of other samples, so called negatives. Another
state-of-the-art technique for self-supervised representation learning is
called Bootstrap Your Own Latent (BYOL) [13]. Compared to contrastive losses,
the main advantage of BYOL is that there is no need for negative samples. This
makes BYOL suitable for test-time training since there is only a single image
available during test-time.

BYOL consists of two neural networks, the online and target model. Both
networks predict a representation of two different augmented views of the same
image. The online network is optimized such that both the online and target
predictions of the two augmented views are as similar as possible. This is
realized by minimizing the mean squared euclidean distance of both
$l_{2}$-normalized predictions. The parameters of the target network are
updated simultaneously using an exponential moving average of the online
network parameters.

$\nabla_{\phi_{1}}\mathcal{L}_{\text{BYOL}}\bigg{(}\qquad\quad,\qquad\quad\bigg{)}$
---
$\nabla_{{\bm{\phi}}_{2}}\mathcal{L}_{\text{BYOL}}\bigg{(}\qquad\quad,\qquad\quad\bigg{)}$
---
$\nabla_{{\bm{\theta}}}\mathcal{L}_{\text{total}}$
---
${\bm{\theta}}$
---
${\bm{\phi}}_{2}$
---
${\bm{\phi}}_{1}$
---
(a) meta-training

$\nabla_{\phi_{1}}\mathcal{L}_{\text{BYOL}}\bigg{(}\qquad\quad,\qquad\quad\bigg{)}$
---
$\nabla_{{\bm{\phi}}_{2}}\mathcal{L}_{\text{BYOL}}\bigg{(}\qquad\quad,\qquad\quad\bigg{)}$
---
${\bm{\theta}}^{*}$
---
${\bm{\phi}}_{2}$
---
${\bm{\phi}}_{1}$
---
$\nabla_{{\bm{\phi}}_{3}}\mathcal{L}_{\text{BYOL}}\bigg{(}\qquad\quad,\qquad\quad\bigg{)}$
---
${\bm{\phi}}_{3}$
---
(b) test-time adaption

Figure 2: MT3 training and test-time adaption: (a) In the outer loop the meta-
parameters ${\bm{\theta}}$ are updated to minimize
$\mathcal{L}_{\text{total}}$ which depends on multiple inner loop adaption
steps. In the inner loop, different augmented views of the same image are used
to adapt the meta-model to the task-specific model. (b) Test-time adaption to
different corruptions starting from optimized meta-parameters
${\bm{\theta}}^{*}$.

#### Meta-Learning

Another concept of adapting to unknown tasks or distributions is meta-
learning, which is used in many state-of-the art results, e.g., for supervised
few-shot learning [2, 11, 18, 25, 28] or unsupervised few-short learning [19,
21]. Meta-learning has also shown its flexibility in the work of [27] where an
unsupervised update rule is learned which can be used for pre-training a
network in order to get powerful representations of unknown data
distributions. In [4], meta-learning is used to train models that generalize
well to unknown domains. A widely used optimization based meta-learning
algorithm is Model-Agnostic Meta-Learning (MAML) [11].

The main concept of MAML is to find the meta-model parameters $\bm{\theta}$
which can be adapted to a new task using a small number of samples and
gradient steps. This means, it maximizes the sensitivity of the meta-model to
changes in the task. In few-shot learning, tasks are defined as a set of new
and unknown classes. During training, multiple tasks ${\mathcal{T}}_{i}$ are
sampled from a distribution of tasks $P(\mathcal{T})$ and used to optimize the
task-specific parameters ${\bm{\phi}}_{i}$ using a few gradient steps by
minimizing a task-specific loss. This is often called the inner loop. The
meta-parameters ${\bm{\theta}}$ are then optimized in the outer loop such that
the adaption to ${\bm{\phi}}_{i}$ of each new task ${\mathcal{T}}_{i}$
maximizes the performance on that task. This results in an optimization over
the gradient steps in inner loops, thus a second order optimization.

#### Meta Test-Time Training (MT3)

In our work, we propose a novel combination of self-supervision and meta-
learning to have the capability of adapting the model to unknown distributions
during test-time. In contrast to simply using joint training as in [30], we
propose to train the model such that it directly learns to adapt at test-time
without supervision. We therefore train the meta-model, parameterized by
${\bm{\theta}}$, using a supervised and a slightly modified version of BYOL
which are combined with MAML. During testing of a single sample, we start with
the final meta-model parameters ${\bm{\theta}}^{*}$ and fine-tune them for
each unlabeled test image to ${\bm{\phi}}^{*}$ using solely the self-
supervised BYOL-like loss. The adapted model is in turn used for inference of
that test image.

For training the meta-parameters in MT3, we define a batch of images as a task
${\mathcal{T}}_{i}$. The parameters ${\bm{\theta}}$ are transformed to
${\bm{\phi}}_{i}$ for each task ${\mathcal{T}}_{i}$ by minimizing the modified
BYOL loss using two augmented versions of an unlabeled image. The meta-
parameters are optimized such that the prediction of the updated model
parameterized by ${\bm{\phi}}_{i}$ leads to a high performance for task
${\mathcal{T}}_{i}$. The optimization of ${\bm{\theta}}$ is performed over
multiple tasks simultaneously as shown exemplarily in Figure 2 (a).

During testing, illustrated in Figure 2 (b), a batch of different augmented
views of a single test sample defines a task for which we optimize the task-
specific parameters with the BYOL-like loss in a self-supervised fashion using
one or several gradient steps. This corresponds to the standard version of
test-time training in [30]. The online setting of [30] is not considered
further in our work. The optimized parameters ${\bm{\phi}}^{*}$ for a single
sample are only used for the classification prediction of itself and are
discarded afterwards. With this test-time adaption we aim for compensating the
performance drop caused by unseen test distribution or distribution shifts.

Our contributions are as follows:

  * •

We propose a novel combination of meta-learning and self-supervision which is
able to adapt to unseen distribution shifts at test-time without supervision.

  * •

We analyze MT3 and show that the combination of meta-learning and BYOL
achieves better performance than just joint training.

  * •

Our method MT3 significantly outperforms the state-of-the-art in adapting to
unseen test distribution shifts.

##  2 Method

#### Tasks

In this work, the training dataset with $N$ input-output pairs is defined as
${\mathcal{D}^{\text{train}}}=\\{{\bm{x}}^{k},{\bm{y}}^{k}\\}_{k=1}^{N}$ with
inputs ${\bm{x}}\in{\mathcal{X}}$ and their corresponding class labels
${\bm{y}}\in{\mathcal{Y}}$. Each meta-training task ${\mathcal{T}}_{i}$ is
associated to a batch of $K$ input-output pairs
${\mathcal{D}_{i}^{\text{train}}}=\\{{\bm{x}}_{i}^{k},{\bm{y}}_{i}^{k}\\}_{k=1}^{K}$
uniformly sampled from ${\mathcal{D}^{\text{train}}}$. Each update of the
meta-parameters is performed over a meta-batch which consists of $T$ tasks. In
contrast to MAML, where the meta-objective is the adaption to new tasks, our
meta-objective is to adapt the model to unknown data distribution shifts.
Therefore, we do not sample the tasks ${\mathcal{T}}_{i}$ with respect to a
different set of classes, but different distributions, which is further
described in Section 2.2. During testing, a task ${\mathcal{T}}$ is defined as
adapting the meta-model on $K_{T}$ augmented views of a single test sample
${\bm{x}}_{\text{test}}$.

#### Architecture

Similar to previous work in representation learning [7, 8, 13], the overall
architecture as shown in Figure 3 consists of a feature extractor $f$, a
classification head $h$ for a supervised classification, a projector $p$ and a
predictor $q$ for an auxiliary self-supervised task. The shared representation
${\bm{g}}$ will either be used for the classification prediction
$\hat{{\bm{y}}}$ or to calculate the projection ${\bm{z}}$ and the prediction
${\bm{r}}$. As introduced in [7, 8], the similarity in the self-supervised
loss is calculated in the projection space ${\bm{z}}$, instead of the
representation space ${\bm{g}}$. The meta-model is parameterized by the meta-
parameters
${\bm{\theta}}=\left[{\bm{\theta}}_{f},{\bm{\theta}}_{h},{\bm{\theta}}_{p},{\bm{\theta}}_{q},\right]^{T}$.
The task-specific parameters are denoted as
${\bm{\phi}}=\left[{\bm{\phi}}_{f},{\bm{\phi}}_{h},{\bm{\phi}}_{p},{\bm{\phi}}_{q},\right]^{T}$.

###  2.1 Meta Test-Time Training

Since the final model parameters ${\bm{\theta}}^{*}$ are adapted at test-time
using a single unlabeled test sample ${\bm{x}}_{\text{test}}$, the sample-
specific parameters ${\bm{\phi}}^{*}$ are then used for prediction. This test
procedure breaks the classical learning paradigm where the model parameters
are fixed at test-time.

In order to make the model adaptable at test-time, there are two crucial
problems which need to be addressed. First, we need an unsupervised loss
function which is used to adapt the model parameters at test-time, and second,
the model has to be optimized during training such that adaptation during
test-time results in a better classification performance.

$f$
---
${\bm{x}}$
---
$p$
---
$q$
---
$h$
---
${\bm{g}}$
---
$\hat{{\bm{y}}}$
---
${\bm{z}}$
---
${\bm{r}}$
---
Figure 3: Used architecture in MT3 with shared feature extractor $f$,
classification head $h$, and self-supervision head with projector $p$ and
predictor $q$.

Following [30], a self-supervised loss is minimized in order to update the
model parameters at test-time. We make use of BYOL [13], since the rather
simple self-supervised rotation loss used in [30] can fail to provide enough
information for adapting the model, specifically if the input sample is
rotation invariant. [30] further proposed to jointly minimize a supervised and
a self-supervised loss during training. Although the authors have shown a
correlation between both loss functions under strong assumptions, joint
training may not lead to a quickly adaptable model for different self-
supervised loss functions as will be shown in our experiments.

In contrast to this, we propose a novel training procedure to directly train a
model such that it learns to adapt to unseen samples.

#### Meta-Training

The goal of the meta-training phase is to find the meta-parameters
${\bm{\theta}}$ which are quickly adaptable to different unseen samples at
test-time for achieving a more accurate classification under unknown
distribution shifts.

During one meta-training outer loop step, the minimization of the self-
supervised loss $\mathcal{L}_{\text{BYOL}}^{i,k}$ leads to the task-specific
parameters ${\bm{\phi}}_{i}$ for each task ${\mathcal{T}}_{i}$ in the inner
loop. The meta-parameters ${\bm{\theta}}$ are then optimized such that the
optimization step to the task-specific parameters leads to high classification
accuracy on these $T$ tasks ${\mathcal{T}}_{i}$.

For each task ${\mathcal{T}}_{i}$, two augmentations
${\bm{a}}_{i}^{k},\tilde{{\bm{a}}}_{i}^{k}$ are generated from
${\bm{x}}_{i}^{k}$ using the sample augmentation $\mathcal{A}$ in order to
calculate a variation of the BYOL loss as explained in detail in Section 2.2.
To further enlarge the differences between the training tasks
${\mathcal{T}}_{i}$, a random batch augmentation $\mathcal{B}$ is applied to
${\bm{x}}_{i},{\bm{a}}_{i}$ and $\tilde{{\bm{a}}}_{i}$. Note that the
parameters of $\mathcal{B}$ are fixed for all $K$ images within one task and
differ across tasks. Therefore, $\mathcal{B}$ artificially generates a
distribution shift between tasks and and facilitates meta-learning.

To calculate our modified BYOL-like loss for each pair ${\bm{a}}_{i}^{k}$ and
$\tilde{{\bm{a}}}_{i}^{k}$, the predictions ${\bm{r}}_{{\bm{\phi}}_{i}}^{k}$
and $\tilde{{\bm{r}}}_{{\bm{\phi}}_{i}}^{k}$ are calculated by the task-
specific model parameterized by ${\bm{\phi}}_{i}$ and the projections
${\bm{z}}_{{\bm{\theta}}}^{k}$ and $\tilde{{\bm{z}}}_{{\bm{\theta}}}^{k}$
using the meta-model ${\bm{\theta}}$. This differs from the original idea of
BYOL where the target model is parameterized by an exponential moving average
(EMA) of the online model parameters. In our approach, the meta-model model
can be regarded as a smooth version of our task-specific models and therefore
a separate target model is obsolete.

Our modified BYOL loss for optimizing the task-specific model is defined as

$\mathcal{L}_{\text{BYOL}}^{i,k}=\bar{\mathcal{L}}({\bm{r}}_{{\bm{\phi}}_{i}}^{k},\tilde{{\bm{z}}}_{{\bm{\theta}}}^{k})+\bar{\mathcal{L}}(\tilde{{\bm{r}}}_{{\bm{\phi}}_{i}}^{k},{\bm{z}}_{{\bm{\theta}}}^{k}),$
(1)
$\text{with}\quad\bar{\mathcal{L}}({\bm{a}},{\bm{b}})=2-2\cdot\frac{{\bm{a}}^{T}{\bm{b}}}{\lVert{\bm{a}}\rVert_{2}\cdot\lVert{\bm{b}}\rVert_{2}}$

denoting the squared $l_{2}$-norm of the difference between $l_{2}$-normalized
versions of two vectors ${\bm{a}}$ and ${\bm{b}}$. The first loss term at the
right hand side of Eq. 1 measures the closeness of the prediction
${\bm{r}}_{{\bm{\phi}}_{i}}^{k}$ of the task-specific model to the projection
$\tilde{{\bm{z}}}_{{\bm{\theta}}}^{k}$ of the meta-model. The second loss term
symmetrizes the first one. Note that this loss is only differentiated with
respect to the task-specific model parameters ${\bm{\phi}}_{i}$ excluding the
classification head parameters ${\bm{\phi}}_{h}$. Hence, the $M$ update steps
with the inner learning rate $\alpha$ are performed by

${\bm{\phi}}_{i}\leftarrow{\bm{\phi}}_{i}-\alpha\nabla_{{\bm{\phi}}_{i}}\frac{1}{K}\sum_{k}\mathcal{L}_{\text{BYOL}}^{i,k},$
(2)

where ${\bm{\phi}}_{i}$ is initialized with the meta-parameters
${\bm{\theta}}$.

Now, making use of all optimized task-specific parameters within a meta-batch,
the classification predictions for each task
$\hat{{\bm{y}}}_{{\bm{\phi}}_{i}}^{k}$ are calculated by the task-specific
models parameterized by ${\bm{\phi}}_{i}$ and, in combination with
${\bm{y}}_{i}^{k}$, are used to optimize the meta-parameters by minimizing the
cross-entropy loss
$\mathcal{L}_{\text{CE}}(\hat{{\bm{y}}}_{{\bm{\phi}}_{i}}^{k},{\bm{y}}_{i}^{k})$.
Additionally, the BYOL-like loss function weighted by $\gamma$ is minimized
here since $\mathcal{L}_{\text{CE}}$ is not differentiable with respect to the
parameter of the predictor $p$ and the projector $q$.

The total loss function in the outer loop is defined as

$\mathcal{L}_{\text{total}}^{i,k}=\mathcal{L}_{\text{CE}}^{i,k}+\gamma\cdot\mathcal{L}_{\text{BYOL}}^{i,k}$
(3)

and is calculated using the task-specific parameters ${\bm{\phi}}_{i}$. The
update of the meta-parameters ${\bm{\theta}}$ is done by

${\bm{\theta}}\leftarrow{\bm{\theta}}-\beta\nabla_{\bm{\theta}}\frac{1}{KT}\sum_{i}\sum_{k}\mathcal{L}_{\text{total}}^{i,k},$
(4)

where $\beta$ is the meta-learning rate. Note that the meta-gradient
$\nabla_{{\bm{\theta}}}$ is a gradient over the optimization steps from
${\bm{\theta}}$ to every ${\bm{\phi}}_{i}$. The pseudo-code of the meta-
training procedure is described in Algorithm 1.

#### Meta-Testing

At test-time, the optimized meta-model parameters ${\bm{\theta}}^{*}$ are
adapted to a single test sample ${\bm{x}}_{\text{test}}$ using the self-
supervised BYOL loss in Equation 1. Since only one sample is available during
testing, an artificial batch is generated using $K_{T}$ different augmentation
pairs of ${\bm{x}}_{\text{test}}$ by using the sample augmentation
$\mathcal{A}$ to minimize the BYOL-like loss. Using the adapted model, the
final classification prediction $\hat{{\bm{y}}}_{\text{test}}$ is performed.
After a prediction, the adapted parameters ${\bm{\phi}}^{*}$ are discarded and
we return back to the final meta-model parameters ${\bm{\theta}}^{*}$ for the
next test sample. The pseudo-code for processing a single test sample is
illustrated in Algorithm 2.

Algorithm 1 Meta-Training

1:Require: Training data ${\mathcal{D}^{\text{train}}}$, number of inner steps
$M$, meta-batch size $T$, task batch size $K$, meta-learning rate $\beta$,
inner learning rate $\alpha$, loss weight $\gamma$, sample augmentation
$\mathcal{A}$, batch augmentation $\mathcal{B}$

2:while not converged do

3: Sample $T$ tasks ${\mathcal{T}}_{i}$ each with batch size $K$

4: for each ${\mathcal{T}}_{i}$ do

5: Get augmented images ${\bm{a}}_{i}^{k}$ and $\tilde{{\bm{a}}}_{i}^{k}$ with
$\mathcal{A}({\bm{x}}_{i}^{k})$

6: Apply batch augmentation $\mathcal{B}$ to
${\bm{x}}_{i}^{k},{\bm{a}}_{i}^{k},\tilde{{\bm{a}}}_{i}^{k}$

7: for $step=1,2,\ldots,M$ do

8: Calculate
${\bm{r}}_{{\bm{\phi}}_{i}}^{k},\tilde{{\bm{r}}}_{{\bm{\phi}}_{i}}^{k},{\bm{z}}_{{\bm{\theta}}}^{k},\tilde{{\bm{z}}}_{{\bm{\theta}}}^{k}$

9: Optimize task-specific model parameters:

10:
${\bm{\phi}}_{i}\leftarrow{\bm{\phi}}_{i}-\alpha\nabla_{{\bm{\phi}}_{i}}\frac{1}{K}\sum_{k}\mathcal{L}_{\text{BYOL}}^{i,k}$
$\triangleright$ Eq. 1

11: end for

12: end for

13: Update meta-parameters:

14:
${\bm{\theta}}\leftarrow{\bm{\theta}}-\beta\nabla_{\bm{\theta}}\frac{1}{KT}\sum_{i}\sum_{k}\mathcal{L}_{\text{total}}^{i,k}$
$\triangleright$ Eq. 3

15:end while

16:Return: ${\bm{\theta}}^{*}$

Algorithm 2 Test-Time Adaption

1:Require: Meta-model ${\bm{\theta}}^{*}$, test sample
${\bm{x}}_{\text{test}}$, number of steps $M$, test batch size $K_{T}$,
learning rate $\alpha$, sample augmentation $\mathcal{A}$

2:for $step=1,2,\ldots,M$ do

3: Initialize ${\bm{\phi}}$ with ${\bm{\theta}}^{*}$

4: Copy ${\bm{x}}_{\text{test}}$ $K_{T}$ times

5: Get $K_{T}$ different pairs of augmentations
$({\bm{a}}^{k},\tilde{{\bm{a}}}^{k})$

6: from ${\bm{x}}_{\text{test}}$ with $\mathcal{A}$

7: Optimize task-specific model parameters:

8:
${\bm{\phi}}\leftarrow{\bm{\phi}}-\alpha\nabla_{{\bm{\phi}}}\frac{1}{K_{T}}\sum_{k}\mathcal{L}_{\text{BYOL}}^{k}$
$\triangleright$ Eq. 1

9:end for

10:Get final classification prediction $\hat{{\bm{y}}}_{\text{test}}$

###  2.2 Implementation Details

#### Architecture

We use a ResNet architecture [15] with 26 layers as our feature extractor $f$
with 32 initial filters for all of our experiments. Although the original
implementation uses batch normalization (BN), we use group normalization (GN)
[36] with 16 groups similar to [30]. The projector $p$ and predictor $q$ are
each a two-layer MLP with 256 hidden neurons and output dimension of 128. The
classifier $h$ shares the first hidden layer with the projector $p$ as
proposed in [8] followed by a 10-dimensional softmax activated output layer.
We empirically found that using no GN in the projector and predictor improves
performance.

#### Augmentations

For the BYOL-like loss in Equation 1, the sample augmentation $\mathcal{A}$
generates two augmentations of one image. Similar to [7, 8, 13], we adjusted
the random cropping for CIFAR-10 (uniform between 20 and 32 pixels) and resize
back to the original image size of $32\times 32$. In contrast to other
approaches, we apply random vertical flipping with a probability of
$50\,\mathrm{\%}$, since horizontal flipping is already used in the batch
augmentation $\mathcal{B}$ and could be reversed if it is applied twice.
Lastly, color jittering and color dropping are applied. We use the same types
of color jittering as in [13] with the adapted strength of $0.2$ compared to
$1.0$ for ImageNet [8]. The color jittering is applied with a probability of
$80\,\mathrm{\%}$ and color dropping with a probability of $20\,\mathrm{\%}$.

Additionally, to simulate larger distribution shifts between tasks
${\mathcal{T}}_{i}$ during meta-training, batch augmentation $\mathcal{B}$ is
applied to the complete batch
$\\{{\bm{x}}_{i}^{k},{\bm{a}}_{i}^{k},\tilde{{\bm{a}}}_{i}^{k}\\}_{k=1}^{K}$.
The parameters of $\mathcal{B}$ are randomly chosen for each task, but fixed
for each image within the current task. Random horizontal flipping
($50\,\mathrm{\%}$ probability), Gaussian blurring ($20\,\mathrm{\%}$
probability) with a $3\times 3$ filter with a standard deviation of $1.0$,
brightness adjustment (uniformly distributed delta between $-0.2$ and $0.2$)
and Gaussian noise with a uniformly distributed standard deviation between $0$
and $0.02$ are applied.

#### Optimization

We use SGD for the meta-optimization with a fixed learning rate of
$\beta=0.01$ and a momentum of $0.9$. The inner optimization is done using
only one ($M=1$) gradient step with a step size of $\alpha=0.1$. During
testing, we use the same fixed learning rate of $\alpha=0.1$ and one gradient
step since the same parameters are used during training. Weight decay is
applied to the meta-model parameters with a strength of $1.5\cdot 10^{-6}$. We
set the weight of the BYOL loss to $\gamma=0.1$. Gradient $l_{2}$-norm
clipping with a clipping norm of $10$ is applied to both the inner- and meta-
gradient to stabilize the training [11]. The meta-batch size is set to $T=4$
and each task consists of $K=8$ images. During test-time adaption, the batch
size is set to $K_{T}=32$. In all experiments the meta-model is trained for
200 epochs which takes approximately 48 hours on a single RTX 2080 Ti (11 GB).
Note that the hyper-parameters are only chosen such that the training loss
converges. No extensive hyper-parameter optimization was performed.

#### Dataset

For training, the CIFAR-10 training dataset [22] is used. For evaluating the
test-time training, we use the CIFAR-10-Corrupted dataset [17]. It consists of
all 10,000 CIFAR-10 validation images with 15 different types of simulated
corruptions for 5 different levels. All our results are reported for the most
severe level 5. An example image with different corruptions is shown in Figure
1. The corruption types come from the four major categories noise, blur,
weather, and digital. Examplary subcategories are impulse noise, Gaussian
blurring, frost, and JPEG compression.

##  3 Experiments

In our experiments, we first analyze the training behavior of our method MT3
followed by a detailed analysis of the impact of meta-learning. For this, we
compare to our own baseline and pure joint training (JT) without the meta-
learning component. Finally, we compare our results with the state-of-the art
method TTT [30]. An overview of all methods is given in Table 1.

###  3.1 Ablation Studies

#### Convergence of MT3

To show its stability and the ability of adaption, we evaluate the
classification accuracy during training twice. First, we measure the
classification accuracy of each task ${\mathcal{T}}_{i}$ with the meta-model
parameters ${\bm{\theta}}$ before applying the self-supervised adaption.
Second, we evaluate the model with the task-specific parameters
${\bm{\phi}}_{i}$ after the adaption in the inner loop. As shown in Figure 4,
the training of MT3 leads to a stable convergence without large deviations.
The small deviations, especially after adaption, highlight the reproducibility
and stability of MT3. Furthermore, even at an early stage of training, MT3
learns to adapt such that the accuracy increases as shown by the large gap
before and after the self-supervised adaption. This clearly shows that the
learned meta-parameters ${\bm{\theta}}^{*}$ are able to be adapted with a
single gradient step and image resulting in an improved classification
accuracy.

$\displaystyle{0}$$\displaystyle{25}$$\displaystyle{50}$$\displaystyle{75}$$\displaystyle{100}$$\displaystyle{125}$$\displaystyle{150}$$\displaystyle{175}$$\displaystyle{200}$Epochs$\displaystyle{50}$$\displaystyle{60}$$\displaystyle{70}$$\displaystyle{80}$$\displaystyle{90}$$\displaystyle{100}$Accuracy
[%]beforeafter

Figure 4: Training accuracy of tasks ${\mathcal{T}}_{i}$ before and after
adaption to task-specific model parameters ${\bm{\phi}}_{i}$ over 3 runs.

Method | self-superv. | $\mathcal{B}$ | training | test-time adaption
---|---|---|---|---
Baseline [30] | - | - | CE | -
JT [30] | rotation | - | joint | -
TTT [30] | rotation | - | joint | $\checkmark$
Baseline (ours) | - | - | CE | -
JT (ours) | BYOL | $\checkmark$ | joint | -
TTT (ours) | BYOL | $\checkmark$ | joint | $\checkmark$
MT (ours) | BYOL | $\checkmark$ | meta | -
MT3 (ours) | BYOL | $\checkmark$ | meta | $\checkmark$

Table 1: Component overview of all considered methods: Baseline, joint training (JT) and test-time training (TTT) with either cross-entropy (CE), rotation augmentation [12] or BYOL [13]; usage of batch augmentation $\mathcal{B}$; and used training principles, joint training or meta training with or without test-time adaption. | Baseline | JT | TTT | Baseline | JT | TTT | MT | MT3
---|---|---|---|---|---|---|---|---
| [30] | [30] | [30] | (ours) | (ours) | (ours) | (ours) | (ours)
brit | $86.5$ | $\mathbf{87.4}$ | $87.2$ | $86.7\pm 0.44$ | $86.5\pm 0.13$ | $86.6\pm 0.26$ | $84.3\pm 1.15$ | $86.2\pm 0.47$
contr | $75.0$ | $74.7$ | $76.1$ | $54.0\pm 6.42$ | $75.4\pm 2.02$ | $75.1\pm 2.38$ | $69.3\pm 2.63$ | $\mathbf{77.6\pm 1.21}$
defoc | $76.3$ | $75.8$ | $78.2$ | $68.1\pm 2.34$ | $84.7\pm 0.11$ | $\mathbf{84.7\pm 0.09}$ | $82.7\pm 1.33$ | $84.4\pm 0.44$
elast | $72.6$ | $76.0$ | $\mathbf{77.4}$ | $74.3\pm 0.27$ | $74.6\pm 0.80$ | $74.4\pm 1.19$ | $74.2\pm 1.08$ | $76.3\pm 1.18$
fog | $71.9$ | $72.5$ | $74.9$ | $70.7\pm 0.98$ | $70.3\pm 0.86$ | $70.4\pm 0.67$ | $72.0\pm 1.03$ | $\mathbf{75.9\pm 1.26}$
frost | $65.6$ | $67.5$ | $70.0$ | $65.2\pm 0.93$ | $79.8\pm 0.62$ | $79.5\pm 0.73$ | $76.6\pm 1.16$ | $\mathbf{81.2\pm 0.20}$
glass | $48.3$ | $51.5$ | $53.9$ | $50.7\pm 2.96$ | $62.8\pm 0.97$ | $61.9\pm 1.10$ | $62.8\pm 1.35$ | $\mathbf{66.3\pm 1.24}$
gauss | $49.5$ | $50.6$ | $54.6$ | $52.4\pm 3.08$ | $84.5\pm 0.08$ | $84.3\pm 0.14$ | $82.3\pm 1.65$ | $\mathbf{84.7\pm 0.21}$
impul | $43.9$ | $46.6$ | $50.0$ | $43.4\pm 4.31$ | $\mathbf{59.3\pm 3.04}$ | $58.5\pm 3.17$ | $50.3\pm 1.68$ | $58.2\pm 1.25$
jpeg | $70.2$ | $71.3$ | $72.8$ | $76.0\pm 0.86$ | $78.6\pm 0.37$ | $\mathbf{79.0\pm 0.44}$ | $75.2\pm 0.06$ | $77.3\pm 0.26$
motn | $75.7$ | $75.2$ | $77.0$ | $71.6\pm 0.46$ | $70.7\pm 0.45$ | $69.8\pm 0.46$ | $72.6\pm 3.17$ | $\mathbf{77.2\pm 2.37}$
pixel | $44.2$ | $48.4$ | $52.8$ | $60.1\pm 2.73$ | $65.0\pm 0.32$ | $62.1\pm 0.44$ | $67.8\pm 5.13$ | $\mathbf{72.4\pm 2.29}$
shot | $52.8$ | $54.7$ | $58.2$ | $52.3\pm 2.17$ | $\mathbf{72.3\pm 1.36}$ | $71.0\pm 1.09$ | $64.0\pm 1.24$ | $70.5\pm 0.72$
snow | $74.4$ | $75.0$ | $76.9$ | $74.5\pm 0.46$ | $77.2\pm 0.58$ | $77.2\pm 0.55$ | $77.1\pm 0.51$ | $\mathbf{79.8\pm 0.63}$
zoom | $73.7$ | $73.6$ | $76.1$ | $67.4\pm 1.70$ | $81.6\pm 0.69$ | $\mathbf{81.7\pm 0.66}$ | $78.7\pm 1.72$ | $81.3\pm 0.58$
avg. | $65.4$ | $66.7$ | $69.1$ | $64.5\pm 0.52$ | $74.9\pm 0.70$ | $74.4\pm 0.74$ | $72.7\pm 0.57$ | $\mathbf{76.6\pm 0.33}$
Table 2: Performance on the CIFAR-10-Corrupted dataset for MT3 compared to the
results from [30], including their baseline, joint training with rotation loss
(JT), and test-time adaption (TTT). Additionally, we report our results of MT3
without test-time adaption (MT), our baseline, joint training (JT), and test-
time adaption (TTT) using BYOL. Mean and standard deviation are reported over
3 runs.

#### Baseline

In order to compare MT3 to classical supervised training, we choose the same
architecture as described in Section 2.2 without the projector and predictor.
This baseline model is simply trained by minimizing the cross-entropy loss. We
use SGD with a fixed learning rate of 0.1 and a momentum of 0.9. The strength
of weight decay is set to $5\cdot 10^{-4}$. We train the baseline model for
200 epochs with a batch size of 128. We use the standard data augmentation
protocol by padding with 4 pixels followed by random cropping to $32\times 32$
pixels and random horizontal flipping [15, 24]. The hyper-parameters of the
baseline training are optimized independently of other methods in order to
have a fair comparison.

#### Joint Training

To show the improvement caused by meta-learning, we compare MT3 to a second
baseline, namely joint training (JT). We use exactly the same architecture as
for MT3 and minimize the joint loss function similar to Equation 3 but without
any inner step, i.e., without meta-learning. Additionally, we use the
exponential moving average of the online model as the target model as
originally proposed in [13] with an update momentum of 0.996. The BYOL-like
loss is weighted by $\gamma=0.1$. For minimizing the joint loss function, we
use SGD with a learning rate of 0.1 and a momentum of 0.9. The strength of
weight decay is set to $1.5\cdot 10^{-6}$. We train the model for 200 epochs
with a batch size of 128. In order to have a fair comparison and to show the
impact of meta-learning in MT3, we use the same data augmentation
$\mathcal{A}$ for minimizing the BYOL-like loss. Furthermore, we use the same
batch augmentation $\mathcal{B}$ to simulate distributions shifts here as
well. The only major difference to MT3 is the use of joint training instead of
meta-learning.

On the one hand, we use joint training to compare it to MT3 by fixing the
learned model at test-time. On the other hand, similar to [30], we adapt our
jointly trained model at test-time using only the self-supervised loss (TTT).
During test-time adaption, we use the same test-time parameters as for MT3
except the learning rate is set to 0.01 which is more comparable to the
effective learning rate during joint training (due to $\gamma=0.1$). The
hyper-parameters of joint training are again optimized independently of other
methods.

Figure 5: Performance on the CIFAR-10-Corrupted dataset for MT3 compared to
MT3 without test-time adaption (MT), joint training with BYOL (JT (ours)),
joint training with rotation loss (JT) [30], and test-time training (TTT)
[30]. Mean and standard deviation are reported over 3 runs.

#### Comparison to our baselines

We first compare our baseline and joint training without test-time adaption
against our proposed method MT3. Additionally, we show the results of MT3 with
fixed parameters at test-time (MT), thus without a gradient step at test-time.
The results on the 15 corruption types of the CIFAR-10-Corrupted images are
shown in Table 2 with their mean and standard deviation estimated over 3 runs.
Furthermore, the average accuracy over all corruption types for each run is
given by its mean and standard deviation. In case of TTT, the model parameters
are adapted before the prediction of each single test image. The final
accuracy is then calculated over the predictions of the 10,000 adapted models.

Our baseline model has on average the worst performance with an accuracy of
$64.5\,\mathrm{\%}$. In comparison, our JT with stronger data augmentation and
the utilization of the BYOL loss leads to a 10.4 % increase in accuracy
achieving $74.9\,\mathrm{\%}$. Applying test-time training to our jointly
trained model, the average accuracy drops down to $74.4\,\mathrm{\%}$,
contrary to our expectations. Although joint training followed by test-time
training is expected to help improving the result as shown in [30], we did not
experience this in our case, where BYOL instead of a rotation loss is used.
For some corruption types, e.g. jpeg compression (jpeg), a small improvement
can be achieved with our TTT, but in 9 of 15 cases the test accuracy decreases
with test-time training, e.g. for pixelate (pixel) by almost $3\,\mathrm{\%}$.

In contrast, our method MT3 achieves a higher classification accuracy for all
types of corruption after performing test-time adaption. MT3 raises the
average accuracy of the meta-model from $72.7\,\mathrm{\%}$ before to
$76.6\,\mathrm{\%}$ after adaption. Considering the average over all
corruptions, MT3 has the lowest standard deviation, which highlights the
stability and reproducibility of our method. Similar to JT, the results of the
two corruption types Gaussian blurring (gauss) and brightness (brit), which
overlap with the applied batch augmentation $\mathcal{B}$, have improved
compared to our baseline. The improvement on these datasets is mainly caused
by the applied data augmentation and should therefore be handled carefully.
Still, our method MT3 outperforms JT on average despite both methods using the
same data augmentations.

In summary, the results suggest that our proposed method MT3 has learned
during training to adapt at test-time, while joint training using BYOL
combined with test-time adaption did not show that behavior. Furthermore, our
analysis shows that the absolute improvement of MT3 is caused by meta-training
and not only by using joint training with stronger data augmentation.

###  3.2 Comparison with state-of-the art

We compare our method to the state-of-the-art TTT [30] as shown in Table 2 and
Figure 5. Besides our results, we discuss the baseline, joint training (JT)
and joint training with test-time adaption (TTT) of [30]. The difference
between all analyzed methods are shown in Table 1.

Our baseline as well as the baseline of [30] have similar average performance
over all corruption types. This highlights that both models have a comparable
capacity or generalization capability and possible improvements are not caused
by the model structure itself. In our work, joint training with the BYOL-like
loss leads to a much higher average accuracy compared to the previous method
where rotation classification as self-supervision was used. The large gap of
$8.2\,\mathrm{\%}$ might be caused by the stronger data augmentations or the
use of BYOL in our method. Despite this, one important result is that simple
joint training does not enable the ability to adapt at test-time in general.
In the previous work [30], the adaption with only the self-supervised loss to
a single test image using ten gradient steps leads on average to an
improvement of $2.4\,\mathrm{\%}$. In comparison, test-time adaption for our
jointly trained model using BYOL leads to an average degradation of
$0.5\,\mathrm{\%}$. We also investigated the case of ten gradient steps at
test-time, but found that on average the performance further degrades.

Our method MT3, on the other hand, shows the ability to adapt by a large
improvement of $3.9\,\mathrm{\%}$ before and after a single gradient step.
Furthermore, the final average accuracy of $76.6\,\mathrm{\%}$ over all
corruption types is the best among all considered methods. For 8 out of 15
corruption types, MT3 has the highest accuracy compared to our baselines and
previous work. This again highlights the ability of our method to adapt to
unseen distribution shifts using a single gradient step during test-time.

##  4 Conclusion

We proposed a novel algorithm that allows to adapt to distribution shifts
during test-time using a single sample. We show that our approach, based on
meta-learning (MAML) and self-supervision (BYOL), effectively enables
adaptability during test-time. In contrast to the previous work, where simply
joint training was used, meta-learning has the explicit purpose to learn meta-
parameters that can be rapidly adapted which we showed in our experiments. Our
combination of meta-learning and self-supervision improves the average
accuracy on the challenging CIFAR-10-Corrupted dataset by $7.5\%$, a $10.85\%$
relative increase, compared to the state-of-the-art TTT.

## References

  * [1] Isabela Albuquerque, Nikhil Naik, Junnan Li, Nitish Keskar, and Richard Socher.  Improving out-of-distribution generalization via multi-task self-supervised pretraining.  arXiv preprint arXiv:2003.13525, 2020.
  * [2] Antreas Antoniou, Harrison Edwards, and Amos Storkey.  How to train your maml.  arXiv preprint arXiv:1810.09502, 2018.
  * [3] Aharon Azulay and Yair Weiss.  Why do deep convolutional networks generalize so poorly to small image transformations?  Journal of Machine Learning Research, 20(184):1–25, 2019.
  * [4] Yogesh Balaji, Swami Sankaranarayanan, and Rama Chellappa.  Metareg: Towards domain generalization using meta-regularization.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [5] Sagie Benaim and Lior Wolf.  One-shot unsupervised cross domain translation.  In NeurIPS, 2018.
  * [6] Nicholas Carlini and David Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 3–14, 2017.
  * [7] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1597–1607. PMLR, 13–18 Jul 2020\.
  * [8] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton.  Big self-supervised models are strong semi-supervised learners.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 22243–22255. Curran Associates, Inc., 2020.
  * [9] Tianlong Chen, Sijia Liu, Shiyu Chang, Yu Cheng, Lisa Amini, and Zhangyang Wang.  Adversarial robustness: From self-supervised pre-training to fine-tuning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [10] Yinpeng Dong, Qi-An Fu, Xiao Yang, Tianyu Pang, Hang Su, Zihao Xiao, and Jun Zhu.  Benchmarking adversarial robustness on image classification.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [11] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In International Conference on Machine Learning, pages 1126–1135. PMLR, 2017.
  * [12] Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  CoRR, abs/1803.07728, 2018.
  * [13] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent: A new approach to self-supervised learning.  arXiv preprint arXiv:2006.07733, 2020.
  * [14] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9729–9738, 2020.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [16] Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, et al.  The many faces of robustness: A critical analysis of out-of-distribution generalization.  arXiv preprint arXiv:2006.16241, 2020.
  * [17] Dan Hendrycks and Thomas Dietterich.  Benchmarking neural network robustness to common corruptions and perturbations.  arXiv preprint arXiv:1903.12261, 2019.
  * [18] Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey.  Meta-learning in neural networks: A survey.  arXiv preprint arXiv:2004.05439, 2020.
  * [19] Kyle Hsu, Sergey Levine, and Chelsea Finn.  Unsupervised learning via meta-learning.  arXiv preprint arXiv:1810.02334, 2018.
  * [20] Ahmadreza Jeddi, Mohammad Javad Shafiee, Michelle Karg, Christian Scharfenberger, and Alexander Wong.  Learn2perturb: An end-to-end feature perturbation learning to improve adversarial robustness.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [21] Siavash Khodadadeh, Ladislau Bölöni, and Mubarak Shah.  Unsupervised meta-learning for few-shot image classification.  arXiv preprint arXiv:1811.11819, 2018.
  * [22] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [23] David Krueger, Ethan Caballero, Joern-Henrik Jacobsen, Amy Zhang, Jonathan Binas, Dinghuai Zhang, Remi Le Priol, and Aaron Courville.  Out-of-distribution generalization via risk extrapolation (rex).  arXiv preprint arXiv:2003.00688, 2020.
  * [24] Chen-Yu Lee, Saining Xie, Patrick Gallagher, Zhengyou Zhang, and Zhuowen Tu.  Deeply-supervised nets.  In Artificial intelligence and statistics, pages 562–570. PMLR, 2015.
  * [25] Zhenguo Li, Fengwei Zhou, Fei Chen, and Hang Li.  Meta-sgd: Learning to learn quickly for few-shot learning.  arXiv preprint arXiv:1707.09835, 2017.
  * [26] Yawei Luo, Ping Liu, Tao Guan, Junqing Yu, and Yi Yang.  Adversarial style mining for one-shot unsupervised domain adaptation.  arXiv preprint arXiv:2004.06042, 2020.
  * [27] Luke Metz, Niru Maheswaranathan, Brian Cheung, and Jascha Sohl-Dickstein.  Meta-learning update rules for unsupervised representation learning.  arXiv preprint arXiv:1804.00222, 2018.
  * [28] Alex Nichol, Joshua Achiam, and John Schulman.  On first-order meta-learning algorithms.  arXiv preprint arXiv:1803.02999, 2018.
  * [29] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar.  Do ImageNet classifiers generalize to ImageNet?  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5389–5400. PMLR, 09–15 Jun 2019.
  * [30] Yu Sun, Xiaolong Wang, Zhuang Liu, John Miller, Alexei Efros, and Moritz Hardt.  Test-time training with self-supervision for generalization under distribution shifts.  In International Conference on Machine Learning, pages 9229–9248. PMLR, 2020.
  * [31] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199, 2013.
  * [32] Chuanqi Tan, Fuchun Sun, Tao Kong, Wenchang Zhang, Chao Yang, and Chunfang Liu.  A survey on deep transfer learning.  In International conference on artificial neural networks, pages 270–279. Springer, 2018.
  * [33] Aäron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  CoRR, abs/1807.03748, 2018.
  * [34] Mei Wang and Weihong Deng.  Deep visual domain adaptation: A survey.  Neurocomputing, 312:135–153, 2018.
  * [35] Garrett Wilson and Diane J Cook.  A survey of unsupervised deep domain adaptation.  ACM Transactions on Intelligent Systems and Technology (TIST), 11(5):1–46, 2020.
  * [36] Yuxin Wu and Kaiming He.  Group normalization.  In Proceedings of the European conference on computer vision (ECCV), pages 3–19, 2018.
  * [37] Sicheng Zhao, Xiangyu Yue, Shanghang Zhang, Bo Li, Han Zhao, Bichen Wu, Ravi Krishna, Joseph E Gonzalez, Alberto L Sangiovanni-Vincentelli, Sanjit A Seshia, et al.  A review of single-source deep unsupervised visual domain adaptation.  IEEE Transactions on Neural Networks and Learning Systems, 2020\.


be a quantum neural network state set with $N=LRn^{4}$. If the relationship

$\displaystyle 1/n+\eta_{u}\geq\max_{M=V|0\rangle\langle
0|V^{\dagger}}\mathcal{L}_{R}(\vec{\bm{q}},M)\geq\Omega(1/n),$ (97)

holds, where $V\in\mathcal{U}_{\mathcal{A}}$ and $\eta_{u}\leq 1/\sqrt{n}$,
then with probability at least $2/3$, $\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle
0^{n}|)$ cannot be approximated by any $U|0^{n}\rangle\langle
0^{n}|U^{\dagger}$ within $\Omega(1/n)$-LS error for $U\in\mathcal{U_{A}}(R)$.

We first introduce the following lemma to support our proof.

######  Lemma 10.

Suppose two random variables $0<m_{1}\leq a_{i}\leq M_{1}$ and $0<m_{2}\leq
b_{i}\leq M_{2}$ for $i\in[N]$, then the relationship

$\displaystyle\left(\sum\limits_{i=1}^{N}a_{i}^{2}\right)\left(\sum\limits_{i=1}^{N}b_{i}^{2}\right)\leq\frac{1}{4}\left(\sqrt{\frac{m_{1}m_{2}}{M_{1}M_{2}}}+\sqrt{\frac{M_{1}M_{2}}{m_{1}m_{2}}}\right)^{2}\left(\sum\limits_{i=1}^{N}a_{i}b_{i}\right)^{2}$
(98)

holds.

###### Proof.

Since $0<m_{1}\leq a_{i}\leq M_{1}$ and $0<m_{2}\leq b_{i}\leq M_{2}$ for
$i\in[N]$, we have

$\displaystyle\frac{m_{1}}{M_{2}}\leq\frac{a_{i}}{b_{i}}\leq\frac{M_{1}}{m_{2}}.$
(99)

Then, the relationship

$\displaystyle\left(\frac{a_{i}}{b_{i}}-\frac{m_{1}}{M_{2}}\right)\left(\frac{a_{i}}{b_{i}}-\frac{M_{1}}{m_{2}}\right)\leq
0$ (100)

holds, and equivalently,

$\displaystyle
a_{i}^{2}-\left(\frac{m_{1}}{M_{2}}+\frac{M_{1}}{m_{2}}\right)a_{i}b_{i}+\frac{m_{1}M_{1}}{m_{2}M_{2}}b_{i}^{2}\leq
0.$ (101)

Summation the index $i\in[N]$,

$\displaystyle\sum\limits_{i=1}^{N}a_{i}^{2}+\frac{m_{1}M_{1}}{m_{2}M_{2}}\sum\limits_{i=1}^{N}b_{i}^{2}\leq\left(\frac{m_{1}}{M_{2}}+\frac{M_{1}}{m_{2}}\right)\sum\limits_{i=1}^{N}a_{i}b_{i},$
(102)

then consider the LHS is lower bounded by
$2\sqrt{\frac{m_{1}M_{1}}{m_{2}M_{2}}\left(\sum\limits_{i=1}^{N}a_{i}^{2}\right)\left(\sum\limits_{i=1}^{N}b_{i}^{2}\right)}$,
and Eq. 98 thus holds. ∎

###### Proof of Lemma 9.

Denote the function

$\displaystyle\bm{g}(|\Psi_{\alpha}\rangle\langle\Psi_{\alpha}|,\Phi_{p,\tilde{R}})={\rm
Tr}\left(M\left(|\Psi_{\alpha}\rangle\langle\Psi_{\alpha}|-\Phi_{p,\tilde{R}}\right)\right),$
(103)

where $M=\arg\max_{M=V|0^{n}\rangle\langle
0^{n}|V^{\dagger}}\mathcal{L}_{R}(\vec{\bm{q}},M)$. In the QML procedure, all
the function $\bm{g}$ are estimated from polynomial time quantum measurements,
and the estimated $\bm{g}$ is thus at least $1/\rm poly(n)$. This proof is
valid under a reasonable assumption $\bm{g}\geq 15/N=15/(LRn^{4})$.

According to the condition in Lemma, one obtains

$\displaystyle\begin{split}\mathbb{E}_{|\Psi_{\bm{\alpha}}\rangle\sim(\mathcal{S}_{\rm
QNN},\vec{\bm{q}})}\left[\bm{g}(|\Psi_{\alpha}\rangle\langle\Psi_{\alpha}|,\Phi_{p,\tilde{R}})\right]=\max_{M}\mathcal{L}_{R}(\vec{\bm{q}},M)\geq\Omega(1/n),\end{split}$
(104)

where $|\Psi_{\bm{\alpha}}\rangle\sim\mathcal{S}_{\rm QNN}$ represents the
SQNN state $|\Psi_{\bm{\alpha}}\rangle$ is uniformly sampled from
$\mathcal{S}_{\rm QNN}$, $\Phi_{p,\tilde{R}}$ denotes the abbreviation of
$\Phi_{p,\tilde{R}}(|0^{n}\rangle\langle 0^{n}|)$. Using the Chebyshev
inequality on the $\mathcal{U}_{\mathcal{A}}$, the relationship

$\displaystyle{\rm
Pr}\left[\left|\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})-\mathbb{E}_{|\Psi_{\bm{\alpha}}\rangle=U|0^{n}\rangle,U\sim\mathcal{U}_{\mathcal{A}}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right|\geq\epsilon_{1}\right]\leq\frac{{\rm
Var}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]}{\epsilon_{1}^{2}}$
(105)

holds, where the variance

$\displaystyle{\rm
Var}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]=\mathbb{E}_{|\Psi_{\bm{\alpha}}\rangle=U|0^{n}\rangle,U\sim\mathcal{U}_{\mathcal{A}}}\left[\bm{g}^{2}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]-\mathbb{E}_{|\Psi_{\bm{\alpha}}\rangle=U|0^{n}\rangle,U\sim\mathcal{U}_{\mathcal{A}}}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]^{2}.$
(106)

After that, the Hoeffding inequality is used to link the relationship between
$\mathcal{S}_{\rm QNN}$ and $\mathcal{U}_{\mathcal{A}}$ in terms of mean-value
function and variance function, that is $\left|\mathbb{E}_{S_{\rm
QNN}}[\bm{g}^{k}]-\mathbb{E}_{\mathcal{U}_{\mathcal{A}}}[\bm{g}^{k}]\right|\leq
t$ with probability at least $1-e^{-N^{2}t}$ for $k=1,2$. As a result,

$\displaystyle{\rm
Var}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]\leq\mathbb{E}_{S_{\rm
QNN}}[\bm{g}^{2}]+t-\left(\mathbb{E}_{S_{\rm QNN}}[\bm{g}]-t\right)^{2}$ (107)

holds with probability at least $(1-e^{-N^{2}t})^{2}$. Let $t=1/n$ and
$N=LRn^{4}$, the success probability $\leq(1-e^{-(LR)^{2}n^{7}})^{2}$ Then
taking $a_{i}=\bm{g}(\Psi_{i},\Phi_{p,\tilde{R}})$, $b_{i}=1$,
$m_{1}=\min(g)$, and $M_{1}=m_{2}=M_{2}=1$ into Lemma 98, one obtains

$\displaystyle\mathbb{E}_{S_{\rm
QNN}}[\bm{g}^{2}]\leq\frac{1}{4N}\left(\sqrt{\min(\bm{g})}+\frac{1}{\sqrt{\min(\bm{g})}}\right)^{2}\left(\mathbb{E}_{S_{\rm
QNN}}[\bm{g}]\right)^{2}.$ (108)

According to the assumption $\bm{g}\geq 15/(N)=15/((LR)n^{4})$ and Eq. 104,
then one obtains

$\displaystyle{\rm
Var}\left[\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\right]\leq\frac{1}{60}\left(\frac{1}{n}+\eta\right)^{2}+t-\left(\frac{1}{n}-t\right)^{2}.$
(109)

Let $\eta\leq 1/\sqrt{n}$, the variance function can be upper bounded by
$1/(10n)$. Therefore,

$\displaystyle\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})\leq\mathbb{E}_{\mathcal{U}_{\mathcal{A}}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})-\epsilon_{1}$
(110)

with probability at most $\frac{1}{10n}\epsilon_{1}^{-2}$. Meanwhile,
Hoeffding inequality suggests that
$\mathbb{E}_{\mathcal{U}_{\mathcal{A}}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})\leq\mathbb{E}_{\mathcal{S}_{\rm
QNN}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})+t$ with nearly unit
probability, and one obtains

$\displaystyle\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})\leq\mathbb{E}_{\mathcal{S}_{\rm
QNN}}\bm{g}(\Psi_{\bm{\alpha}},\Phi_{p,\tilde{R}})+t-\epsilon_{1}\leq\frac{1}{n}+\eta+t-\epsilon_{1}$
(111)

with probability at most $\frac{1}{10n}\epsilon_{1}^{-2}$. Let
$\epsilon_{1}=\sqrt{3/(10n)}$, we finally obtain

$\displaystyle\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})\leq\mathcal{O}(1/\sqrt{n})$
(112)

with probability $\leq 1/3$. Equivalently, for any $|\Psi_{i}\rangle$
generated from $\mathcal{U}_{\mathcal{A}}$, the relationship

$\displaystyle\frac{1}{2}\||\Psi_{i}\rangle\langle\Psi_{i}|-\Phi_{p,\tilde{R}}\|_{1}\geq\bm{g}(\Psi_{\bm{\alpha}^{*}},\Phi_{p,\tilde{R}})>\mathcal{O}(1/\sqrt{n})$
(113)

with the probability $>2/3$. This immediately implies
$\langle\Psi_{i}|\Phi_{p,\tilde{R}}|\Psi_{i}\rangle<1-\mathcal{O}(1/n)$ for
any $|\Psi_{i}\rangle=U|0^{n}\rangle$ where $U\in\mathcal{U}_{\mathcal{A}}$.

∎

###  E.8 Proof of theorem 4

We need following two lemmas to support our proof.

######  Lemma 11 (Lemma 5.1 in [101]).

Pick faliure probability $\delta\in(0,1)$ and set
$\kappa_{t}=2\log(\left|\mathcal{D}_{\rm domain}\right|\pi_{t}/\delta)$, where
$\sum_{t\geq 1}\pi_{t}^{-1}=1$ and $\pi_{t}>0$. Then

$\displaystyle\left|\mathcal{L}(\bm{z})-\mu_{t-1}(\bm{z})\right|\leq\kappa_{t}^{1/2}\sigma_{t-1}(\bm{z})$
(114)

holds for any $t\geq 1$ and $\bm{z}\in\mathcal{D}_{\rm domain}$.

######  Lemma 12 (Lemma 5.4 in [101]).

Pick failure probability $\delta\in(0,1)$ and let $\kappa_{t}$ be defined as
in Lemma 11. Then the following holds with probability $\geq 1-\delta$:

$\displaystyle\sum\limits_{t=1}^{T}4\kappa_{t}\sigma^{2}_{t-1}(\bm{z}_{t})\leq\kappa_{T}\gamma_{T},$
(115)

where $\gamma_{T}=\max_{A\in\mathcal{D}_{\rm
domain}}\frac{1}{2}\log\left|I+\sigma^{-2}K_{A}\right|$, and $K_{A}$
represents the used covariance matrix in Bayesian optimization.

###### Proof.

We first consider the continuity of the loss function $\mathcal{L}(\bm{z})$.
Considering $\sum_{i=1}^{N}\bm{\beta}_{i}=1$, the gradient function can be
upper bounded by

$\displaystyle\left|\frac{\partial\mathcal{L}(\bm{z})}{\partial\bm{p}_{j}}\right|=\left|\sum\limits_{i=1}^{N}\bm{\beta}_{i}\left(|\langle\Psi_{i}|\Psi_{j}\rangle|^{2}-\langle\Psi_{i}|\rho|\Psi_{i}\rangle\right)\right|\leq\left|\sum\limits_{i=1}^{N}\bm{\beta}_{i}\right|=1$
(116)

($\left|\partial\mathcal{L}(\bm{z})/\partial\bm{\beta}_{j}\right|$ has the
same upper bound), where the inequality comes from
$|\langle\Psi_{i}|\Psi_{j}\rangle|^{2}-\langle\Psi_{i}|\rho|\Psi_{i}\rangle<1$.
Therefore, the relationship

$\displaystyle\left|\mathcal{L}(\bm{z})-\mathcal{L}(\bm{z}^{\prime})\right|\leq\left|\bm{z}-\bm{z}^{\prime}\right|_{1}$
(117)

holds for any $\bm{z},\bm{z}^{\prime}\in\mathcal{D}_{\rm domain}$. Now let us
choose a discretization $\mathcal{D}^{t}_{\rm domain}$ of size
$(\tau_{t})^{N}$ such that for all $\bm{z}\in\mathcal{D}_{\rm domain}$,

$\displaystyle\|\bm{z}-[\bm{z}]_{t}\|_{1}\leq N/\tau_{t},$ (118)

where $[\bm{z}]_{t}$ represents the closest point in discretization on
$\mathcal{D}^{t}_{\rm domain}$ to $\bm{z}$. Combine Eqs. 117-118, one obtains

$\displaystyle\left|\mathcal{L}(\bm{z})-\mathcal{L}([\bm{z}]_{t})\right|\leq
N\tau_{t}^{-1}=t^{-2},$ (119)

where the last inequality comes from $\tau_{t}=t^{2}N$, furthermore,
$\left|\mathcal{D}^{t}_{\rm domain}\right|=(t^{2}N)^{N}$.

Using Lemma 11, we know that

$\displaystyle\kappa_{t}=2\log(\left|\mathcal{D}_{\rm
domain}\right|a_{t}/\delta)$ (120)

enables the relationship

$\displaystyle\left|\mathcal{L}(\bm{z})-\mu_{t-1}(\bm{z})\right|\leq\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z})$
(121)

holds with probability at least $1-\delta$, where $a_{t}>0$ and $\sum_{t\geq
1}a_{t}^{-1}=1$. A common selection is $a_{t}=\pi t^{2}/6$. Taking
$\left|\mathcal{D}^{t}_{\rm domain}\right|=(t^{2}N)^{N}$ into $\kappa_{t}$
(Eq. 120), one obtains

$\displaystyle\kappa_{t}=2\log\left((t^{2}N)^{N}a_{t}/\delta\right).$ (122)

Combine Eq. 119 and 121, we have

$\displaystyle\left|\mathcal{L}(\bm{z}^{*})-\mu_{t-1}([\bm{z}^{*}]_{t})\right|\leq\left|\mathcal{L}(\bm{z}^{*})-\mathcal{L}([\bm{z}^{*}]_{t})\right|+\left|\mathcal{L}([\bm{z}^{*}]_{t})-\mu_{t-1}([\bm{z}^{*}]_{t})\right|\leq
t^{-2}+\sqrt{\kappa_{t}}\sigma_{t-1}([\bm{z}^{*}]_{t})$ (123)

for any $t\geq 1$, where $\bm{z}^{*}=\arg\max_{\bm{z}\in\mathcal{D}_{\rm
domain}}\mathcal{L}(\bm{z})$. Now we connect the relationship between above
inequality to the regret bound.

By the definition of $\bm{z}^{(t)}$ (maximizing the $\mathcal{A}_{\rm
UCB}(\bm{z})$ in the $t$-th step):
$\mu_{t-1}(\bm{z}^{(t)})+\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z}^{(t)})\geq\mu_{t-1}([\bm{z}^{*}]_{t})+\sqrt{\kappa_{t}}\sigma_{t-1}([\bm{z}^{*}]_{t})$.
Also, by Eq. 123, we have
$\mathcal{L}(\bm{z}^{*})\leq\mu_{t-1}([\bm{z}^{*}]_{t})+\sqrt{\kappa_{t}}\sigma_{t-1}([\bm{z}^{*}]_{t})+1/t^{2}$.
Therefore, instantaneous regret

$\displaystyle\begin{split}r_{t}&=\mathcal{L}(\bm{z}^{*})-\mathcal{L}(\bm{z}^{(t)})\\\
&\leq\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z}^{(t)})+1/t^{2}+\mu_{t-1}(\bm{z}^{(t)})-\mathcal{L}(\bm{z}^{(t)})\\\
&\leq 2\sqrt{\kappa_{t}}\sigma_{t-1}(\bm{z}^{(t)})+1/t^{2},\end{split}$

where the last inequality comes from Eq. 121. Using Lemma 12,
$\sum_{t=1}^{T}4\kappa_{t}\sigma_{t-1}(\bm{z}_{t})\leq\kappa_{T}\gamma_{T}$,
where

$\gamma_{T}=\max_{A\in\mathcal{D}_{\rm
domain}}\frac{1}{2}\log\left|I+\sigma^{-2}K_{A}\right|,$

and $K_{A}$ represents the used covariance matrix in ${\rm
BMaxS}(\Phi_{p,\tilde{R}},\mathcal{S}_{\rm QNN}(R,\mathcal{A},N),T)$. In the
linear regression case, $K_{A}$ can be selected as the polynomial kernel
function, and $\gamma_{T}=\mathcal{O}(N\log(T))$ [102]. Furthermore, using the
Cauchy-Schwartz inequality to
$\sum_{t=1}^{T}4\kappa_{t}\sigma_{t-1}^{2}(\bm{z}_{t})\leq\kappa_{T}\gamma_{T}$,
one obtains
$\sum_{t=1}^{T}2\kappa_{t}^{1/2}\sigma_{t-1}(\bm{z}_{t})\leq\sqrt{T\kappa_{T}\gamma_{T}}$

Finally, we have the result

$\displaystyle\begin{split}R_{T}&=\frac{1}{T}\sum\limits_{t=1}^{T}r_{t}\\\
&\leq\frac{1}{T}\sum\limits_{t=1}^{T}2\kappa_{t}^{1/2}\sigma_{t-1}(\bm{z}_{t})+\frac{\pi^{2}}{6T}\\\
&\leq\sqrt{\frac{\kappa_{T}\gamma_{T}}{T}}+\frac{\pi^{2}}{6T}\\\
&=\mathcal{O}\left(\sqrt{\frac{2N^{2}\log(T^{2}N)\log(T)+2N\log(T^{2}\pi^{2}/(6\delta))\log(T)}{T}}\right)\\\
&\leq\mathcal{O}\left(\sqrt{\frac{4N^{2}\log^{2}T+2N\log
T\log(\pi^{2}/(6\delta))}{T}}\right),\end{split}$ (124)

where the first inequality results from $\sum_{t\geq 1}t^{-2}=\pi^{2}/6$ and
the last inequality comes from $N\leq T$. ∎

##  Appendix F Review of Shadow tomography

In quantum computation, the basic operators are the Pauli operators
$\\{I,\sigma^{x},\sigma^{y},\sigma^{z}\\}$ which provide a basis for the
density operators of a single qubit as well as for the unitaries that can be
applied to them. For an $n$-qubit case, one can construct the Pauli group
according to

$\mathbf{P}_{n}=\\{e^{i\alpha\pi/2}\sigma^{j_{1}}\otimes...\otimes\sigma^{j_{n}}|j_{k}\in\\{I,x,y,z\\},1\leq
k\leq n\\},$

where $e^{i\alpha\pi/2}\in\\{0,\pm 1,\pm i\\}$ is a global phase. Then the
Clifford group $\mathbf{Cl}(2^{n})$ is defined as the group of unitaries that
normalize the Pauli group:

$\mathbf{Cl}(2^{n})=\left\\{U|U\mathbf{P}^{(1)}U^{\dagger}=\mathbf{P}^{(2)},\left(\mathbf{P}^{(1)},\mathbf{P}^{(2)}\in\mathbf{P}_{n}\right)\right\\}.$

The $n$-qubit Clifford gates are then defined as elements in the Clifford
group $\mathbf{Cl}(2^{n})$, and these Clifford gates compose the Clifford
circuit.

Randomly sampling Clifford circuit $U$ can reproduce the first $3$ moments of
the full Clifford group endowed with the Haar measure $\mathbf{d}\mu(U)$ which
is the unique left- and right- invariant measure such that

$\int_{\mathbf{Cl}(2^{n})}\mathbf{d}\mu(U)f(U)=\int\mathbf{d}\mu(U)f(VU)=\int\mathbf{d}\mu(U)f(UV)$

for any $f(U)$ and $V\in\mathbf{Cl}(2^{n})$. Using this property, one can
sample Clifford circuits $U\in\mathbf{Cl}(2^{n})$ with the probability
${\rm{Pr}}(U)$, and the corresponding expectation
${\rm{E}}_{U\in\mathbf{Cl}(2^{n})}[\left(U\rho U^{\dagger}\right)^{\otimes
t}]$ can be expressed as

$\sum\limits_{U\in\mathbf{Cl}(2^{n})}{\rm{Pr}}(U)\left(U\rho
U^{\dagger}\right)^{\otimes
t}=\int_{\mathbf{Cl}(2^{n})}\mathbf{d}\mu(U)\left(U\rho
U^{\dagger}\right)^{\otimes t},$

for any $n$-qubit density matrix $\rho$ and $t=1,2,3$, where ${\rm{Pr}}(U)$
indicates the probability on sampling $U$. The right hand side of the above
equation can be evaluated explicitly by representation theory, this thus
yields a closed-form expression for sampling from a Clifford group.

To extract meaningful information from an $n$-qubit unknown quantum state
$\rho$, the shadow tomography technique was proposed by H. Huang et al.[68].
The Clifford sampling is implemented by repeatedly performing a simple
measurement procedure: apply a random unitary $U\in\mathbf{Cl}(2^{n})$ to
rotate the state $\rho$ and perform a $\sigma^{z}$-basis measurement. The
number of repeating times of this procedure is defined as the Clifford
sampling complexity. On receiving the $n$-bit measurement outcome
$|b\rangle\in\\{0,1\\}^{n}$, according to the Gottesman-Knill theorem [84], we
can efficiently store an classical description of $U^{\dagger}|b\rangle\langle
b|U$ in the classical memory. This classical description encodes meaningful
information of the state $\rho$ from a particular angle, and it is thus
instructive to view the average mapping from $\rho$ to its classical snapshot
$U^{\dagger}|b\rangle\langle b|U$ as a quantum channel:

$\displaystyle\mathcal{M}(\rho)=\textmd{E}_{U\in\mathbf{Cl}(2^{n})}\left(\textmd{E}_{b\in\\{0,1\\}^{n}}[U^{\dagger}|b\rangle\langle
b|U]\right),$ (125)

where the quantum channel $\mathcal{M}$ depends on the ensemble of unitary
transformation, and the quantum channel $\mathcal{M}$ can be further expressed
as

$\displaystyle\mathcal{M}(\rho)=\textmd{E}_{U\in\mathbf{Cl}(2^{n})}\sum\limits_{\widehat{b}\in\\{0,1\\}^{n}}\langle\widehat{b}|U\rho
U^{\dagger}|\widehat{b}\rangle
U^{\dagger}|\widehat{b}\rangle\langle\widehat{b}|U=\frac{\rho+{\rm{Tr}}(\rho)I}{(2^{n}+1)2^{n}},$
(126)

where $I$ indicates the $2^{n}\times 2^{n}$ identity matrix. Therefore the
inverse of quantum channel $\mathcal{M}^{-1}(\rho)=(2^{n}+1)\rho-I$, and an
estimation of $\rho$ is defined as

$\widehat{\rho}=\mathcal{M}^{-1}\left(U^{\dagger}|b\rangle\langle b|U\right).$

Repeat this procedure $M$ times results in an array of Clifford samples of
$\rho$:

$\displaystyle
S(\rho;M)=\left\\{\widehat{\rho}_{1}=\mathcal{M}^{-1}\left(U_{1}^{\dagger}|b_{1}\rangle\langle
b_{1}|U_{1}\right),...,\widehat{\rho}_{M}=\mathcal{M}^{-1}\left(U_{M}^{\dagger}|b_{M}\rangle\langle
b_{M}|U_{M}\right)\right\\},$ (127)

which is defined as the _classical shadow_ of the quantum state $\rho$.