######  Lemma D.13.

Under Assumptions 2-4, with probability at least $1-\delta$, it holds that

$\displaystyle\mathcal{Q}_{ij}(\widehat{g})$
$\displaystyle\leq\varepsilon_{\mathrm{orac}}+CK^{2}BRd\sqrt{TmK\log\left(\frac{TBRK}{\delta}\right)}+CK^{3}d\left(4B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\log\left(\frac{BKT}{\delta}\right)$
$\displaystyle+C\nu^{2}d^{2}Km\log\left(\frac{TRBmdK}{\delta}\right)+C\nu
d\sqrt{Km\log\left(\frac{TRBmdK}{\delta}\right)}.$

To prove this result, we begin by fixing $g\in\mathcal{G}$ and $1\leq i,j\leq
K$ and bounding $\mathcal{Q}_{ij}(g)$ by $\mathcal{R}_{ij}(g)$. We will then
use the results of Section D.1 to make the statement uniform in $\mathcal{G}$.
We proceed with the case of fixed $g$ and prove the following result:

######  Lemma D.14.

Suppose that Assumptions 2-4 all hold. Fix $1\leq i,j\leq K$ and some
$g\in\mathcal{G}$. For any $\lambda>0$, with probability at least $1-\delta$,
it holds that

$\displaystyle\mathcal{Q}_{ij}(g)\leq\mathcal{R}_{ij}(g)+C\nu^{2}dm\log\left(\frac{TRBmd}{\lambda\delta}\right)+C\nu\sqrt{\lambda
dm\log\left(\frac{TRBmd}{\lambda\delta}\right)}+16BR\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|.$

###### Proof.

We begin by expanding

$\displaystyle\mathcal{R}_{ij}(g)$ $\displaystyle=\sum_{t\in
I_{ij}(g)}\left|\left|\widehat{\mathbf{\Theta}}_{i}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\left|\left|\mathbf{\Theta}^{\star}_{j}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}$
$\displaystyle=\sum_{t\in
I_{ij}(g)}\left|\left|\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}-\mathbf{e}_{t}-\bm{\delta}_{t}\right|\right|^{2}-\left|\left|\mathbf{e}_{t}+\bm{\delta}_{t}\right|\right|^{2}$
$\displaystyle=\sum_{t\in
I_{ij}(g)}\left|\left|\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}-2\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t}+\bm{\delta}_{t},\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right\rangle$
$\displaystyle=\mathcal{Q}_{ij}(g)-2\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t}+\bm{\delta}_{t},\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right\rangle.$

Thus, it suffices to bound the second term. By linearity, and the assumption
on $\bm{\delta}_{t}$, we have

$\displaystyle 2\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t}+\bm{\delta}_{t},\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right\rangle\leq
2\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t},\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right\rangle+4BR\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|.$

We use a generalization of the self-normalized martingale inequality, Lemma
D.8 to bound the first term above. To do this, fix some
$\bm{\Delta}\in\mathbb{R}^{m\times(d+1)}$ and define

$\displaystyle E(\bm{\Delta})=\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t},\bm{\Delta}\bar{\mathbf{x}}_{t}\right\rangle$
$\displaystyle V(\bm{\Delta})=\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\Delta}\bar{\mathbf{x}}_{t}\right|\right|^{2}.$

Noting that
$V(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j})=\mathcal{Q}_{ij}(g)$,
we see from the above that

$\displaystyle\mathcal{R}_{ij}(g)=V(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j})-2E(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j})$
(D.6)

We will now bound $E(\bm{\Delta})$ for some fixed $\bm{\Delta}$ and then apply
a covering argument to lift the statement to apply to
$\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}$. By Assumption 4,
we may take $\left|\left|\bm{\Delta}\right|\right|\leq 2R$.

Recall that $\mathscr{F}^{y}_{t}$ denotes the filtration generated by
$\mathbf{x}_{1},\dots,\mathbf{x}_{t},\mathbf{y}_{1},\dots,\mathbf{y}_{t-1}$.
Applying Simchowitz et al. [2019, Lemma E.1], a generalization of Lemma D.8,
with
$e_{t}\leftarrow\left\langle\mathbf{e}_{t},\bm{\Delta}\bar{\mathbf{x}}_{t}\right\rangle$,
$u_{t}=\bm{\Delta}\bar{\mathbf{x}}_{t}$, and the filtration
$\mathscr{F}^{y}_{t}$, tells us that for any $\lambda>0$, it holds with
probability at least $1-\delta$ that

$E(\bm{\Delta})^{2}\leq
2\nu^{2}(\lambda+V(\bm{\Delta}))\log\left(\frac{\sqrt{1+\frac{V(\bm{\Delta})}{\lambda}}}{\delta}\right).$
(D.7)

We note by Assumption 4, it holds that

$V(\bm{\Delta})\leq 4TR^{2}B^{2}$

and thus the subadditivity of the square root tells us that

$\displaystyle E(\bm{\Delta})^{2}\leq
2\nu^{2}(\lambda+V(\bm{\Delta}))\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\right)$

with probability at least $1-\delta$. Now let $\mathscr{N}$ be an
$\varepsilon$-net of the Frobenius ball in $\mathbb{R}^{m\times(d+1)}$ of
radius $2R$. For small $\varepsilon$, we may take $\mathscr{N}$ such that

$\log(\left|\mathscr{N}\right|)\leq
m(d+1)\log\left(\frac{6R}{\varepsilon}\right).$ (D.8)

For any $\bm{\Delta}$, denote by $\bm{\Delta}^{\prime}$ its projection into
$\mathscr{N}$. Then we compute

$\displaystyle E(\bm{\Delta})^{2}$ $\displaystyle\leq
E(\bm{\Delta}^{\prime})^{2}+E(\bm{\Delta})^{2}-E(\bm{\Delta}^{\prime})^{2}$
$\displaystyle\leq\left(\sum_{t\in
I_{ij}(g)}\|\mathbf{e}_{t}\|_{\mathrm{F}}^{2}\right)4RB^{2}T\sqrt{\|\bm{\Delta}-\bm{\Delta}^{\prime}\|_{\mathrm{F}}}+2\nu^{2}\left(\lambda+V(\bm{\Delta}^{\prime})\right)\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\left|\mathscr{N}\right|\right)$
$\displaystyle\leq\left(\sum_{t\in
I_{ij}(g)}\left|\left|\mathbf{e}_{t}\right|\right|^{2}\right)4RB^{2}T\sqrt{\varepsilon}+2\nu^{2}\left(\lambda+V(\bm{\Delta}^{\prime})\right)\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\left|\mathscr{N}\right|\right)$
$\displaystyle\leq\left(\sum_{t\in
I_{ij}(g)}\left|\left|\mathbf{e}_{t}\right|\right|^{2}\right)4RB^{2}T\sqrt{\varepsilon}+2\nu^{2}\left(\lambda+V(\bm{\Delta})\right)\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\left|\mathscr{N}\right|\right)$
$\displaystyle\qquad+(V(\bm{\Delta}^{\prime})-V(\bm{\Delta}))\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\right)$

where the second inequality follows from Claim D.3 along with a union bound
over $\mathscr{N}$ applied to (D.7), the third inequality follows from the
definition of an $\varepsilon$-net, and the last inequality follows from
simply adding and subtracting the same term. Applying Claim D.3 once again, we
have with probability at least $1-\delta$,

$\displaystyle E(\bm{\Delta})^{2}$ $\displaystyle\leq\left(\sum_{t\in
I_{ij}(g)}\left|\left|\mathbf{e}_{t}\right|\right|^{2}\right)4RB^{2}T\sqrt{\varepsilon}+2\nu^{2}\left(\lambda+V(\bm{\Delta})\right)\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\left|\mathscr{N}\right|\right)$
$\displaystyle\qquad+4RB^{2}T\sqrt{\varepsilon}\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\left|\mathscr{N}\right|\right)$
$\displaystyle\leq
2\nu^{2}\left(\lambda+V(\bm{\Delta})\right)\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\left|\mathscr{N}\right|\right)+4RB^{2}T^{2}m\nu^{2}\sqrt{\varepsilon}\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\left|\mathscr{N}\right|\right)$

uniformly for all $\bm{\Delta}$ in the Frobenius ball of radius $2R$. We now
choose

$\varepsilon=C\left(\frac{TRB^{2}md}{\lambda}\right)^{-c}$

for some universal constants $C,c$ to ensure that

$4RB^{2}T^{2}m\nu^{2}\sqrt{\varepsilon}\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\left|\mathscr{N}\right|\right)\leq
2\nu^{2}\lambda$

Thus with probability at least $1-\delta$, it holds for all $\bm{\Delta}$ that

$\displaystyle E(\bm{\Delta})^{2}\leq
2\nu^{2}(\lambda+V(\bm{\Delta}))\left(\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\right)+m(d+1)\log\left(\frac{TR^{2}B^{2}md}{\lambda}\right)\right)$

where we applied (D.8) to bound the size of $\mathscr{N}$. In particular, this
holds for
$\bm{\Delta}=\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}$ and
thus

$\displaystyle
E(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j})^{2}\leq
2\nu^{2}(\lambda+\mathcal{Q}_{ij}(g))\left(\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\right)+m(d+1)\log\left(\frac{TR^{2}B^{2}md}{\lambda}\right)\right)$

Plugging this back into (D.6), we have that with probability at least
$1-\delta$, it holds that

$\displaystyle
4BR|I_{ij}(g)|\varepsilon_{\mathrm{crp}}+\mathcal{R}_{ij}(g)\geq\mathcal{Q}_{ij}(g)-$
$\displaystyle\qquad-C\nu\sqrt{(\lambda+\mathcal{Q}_{ij}(g))\left(\log\left(\frac{1+2RB\sqrt{\frac{T}{\lambda}}}{\delta}\right)+m(d+1)\log\left(\frac{TR^{2}B^{2}md}{\lambda}\right)\right)}.$

Rearranging concludes the proof. ∎

We defer proofs of the technical computations, Lemmas D.3 and D.4, used in the
proof of Lemma D.14 until the end of the section. For now, we press on to lift
our bound from a statement about a fixed $g\in\mathcal{G}$ to one uniform in
$\mathcal{G}$. We require one last lemma before concluding this proof,
however. We are aiming to bound $\mathcal{Q}_{ij}(\widehat{g})$ by
$\mathcal{R}_{ij}(\widehat{g})$, but we need to upper bound
$\mathcal{R}_{ij}(\widehat{g})$. This is the content of the following lemma:

######  Lemma D.15.

With probability at least $1-\delta$, for all $1\leq i,j\leq K$, it holds that

$\displaystyle\mathcal{R}_{ij}(\widehat{g})$
$\displaystyle\leq\varepsilon_{\mathrm{orac}}+4BRK^{2}\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|+CK^{2}BR\sqrt{Tmd\log\left(\frac{TBRK\textsc{DN}(\varepsilon)}{\delta}\right)}$
$\displaystyle\quad+K^{2}\left(4B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\left(2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)\right)$

###### Proof.

We begin by introducing some notation. For fixed
$\mathbf{\Theta}\in\mathbb{R}^{m\times(d+1)}$ and $g\in\mathcal{G}$, let

$\displaystyle\mathcal{R}_{ij}(g,\mathbf{\Theta})=\sum_{t\in
I_{ij}(g)}\left|\left|\mathbf{\Theta}_{i}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\left|\left|\mathbf{e}_{t}+\bm{\delta}_{t}\right|\right|^{2}$

and note that
$\mathcal{R}_{ij}(g)=\mathcal{R}_{ij}(g,\widehat{\mathbf{\Theta}}_{i})$.
First, we note that by definition of ErmOracle,

$\displaystyle\varepsilon_{\mathrm{orac}}$
$\displaystyle\geq\sum_{t=1}^{T}\left|\left|\widehat{\mathbf{\Theta}}_{\widehat{g}(\bar{\mathbf{x}}_{t})}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\inf_{g,\widehat{\mathbf{\Theta}}}\sum_{t=1}^{T}\left|\left|\widehat{\mathbf{\Theta}}_{\widehat{g}(\bar{\mathbf{x}}_{t})}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}$
$\displaystyle\geq\sum_{t=1}^{T}\left|\left|\widehat{\mathbf{\Theta}}_{\widehat{g}(\bar{\mathbf{x}}_{t})}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\left|\left|\mathbf{\Theta}^{\star}_{g_{\star}(\bar{\mathbf{x}}_{t})}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}$
$\displaystyle=\sum_{1\leq i,j\leq K}\mathcal{R}_{ij}(\widehat{g}).$

Thus, we have

$\displaystyle\mathcal{R}_{ij}(\widehat{g})\leq\varepsilon_{\mathrm{orac}}-\sum_{\begin{subarray}{c}1\leq
i^{\prime},j^{\prime}\leq K\\\
(i,j)\neq(i^{\prime},j^{\prime})\end{subarray}}\mathcal{R}_{ij}(\widehat{g}).$
(D.9)

Thus it will suffice to provide a lower bound on
$\mathcal{R}_{ij}(\widehat{g})$ that holds with high probability. To do this,
note that for fixed $g\in\mathcal{G}$ and $\mathbf{\Theta}_{0}$, we have

$\displaystyle\mathcal{R}_{ij}(g,\mathbf{\Theta}_{0})$
$\displaystyle=\sum_{t\in
I_{ij}(g)}\left|\left|\left(\mathbf{\Theta}_{0}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}-2\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t}+\bm{\delta}_{t},\left(\mathbf{\Theta}_{0}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}-\mathbf{e}_{t}-\bm{\delta}_{t}\right\rangle$
$\displaystyle\geq-2\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t}+\bm{\delta}_{t},\left(\mathbf{\Theta}_{0}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right\rangle$
$\displaystyle\geq-2\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t},(\mathbf{\Theta}_{0}-\mathbf{\Theta}^{\star}_{j})\bar{\mathbf{x}}_{t}\right\rangle-4BR\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|.$

Noting that $\mathbf{e}_{t}$ is subGaussian by Assumption 3 and by Assumption
4 we have control over
$\left|\left|\left(\mathbf{\Theta}_{0}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right|\right|$,
we see that with probability at least $1-\delta$, it holds that

$\displaystyle\mathcal{R}_{ij}(g,\mathbf{\Theta}_{0})$
$\displaystyle\geq-2\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t},\left(\mathbf{\Theta}_{0}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right\rangle-4BR\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|$
$\displaystyle\geq-8BR\sqrt{\left|I_{ij}(g)\right|\cdot\log\left(\frac{1}{\delta}\right)}-4BR\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|.$

Now note that

$\displaystyle\mathcal{R}_{ij}(g,\mathbf{\Theta}_{0})-\mathcal{R}_{ij}(g,\mathbf{\Theta}_{0}^{\prime})$
$\displaystyle=\sum_{t\in
I_{ij}(g)}\left|\left|\left(\mathbf{\Theta}_{0}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}-\mathbf{e}_{t}-\bm{\delta}_{t}\right|\right|^{2}-\left|\left|\left(\mathbf{\Theta}_{0}^{\prime}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}-\mathbf{e}_{t}-\bm{\delta}_{t}\right|\right|^{2}$
$\displaystyle=\sum_{t\in
I_{ij}(g)}\left\langle\left(\mathbf{\Theta}_{0}+\mathbf{\Theta}_{0}^{\prime}-2\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}-2\mathbf{e}_{t}-2\bm{\delta}_{t},\left(\mathbf{\Theta}_{0}-\mathbf{\Theta}_{0}^{\prime}\right)\bar{\mathbf{x}}_{t}\right\rangle$

Applying Cauchy Schwarz and noting that with probability at least $1-\delta$
it holds that

$\max_{1\leq t\leq
T}\left|\left|\mathbf{e}_{t}\right|\right|\leq\nu\sqrt{\log\left(\frac{T}{\delta}\right)},$

we have that with probability at least $1-\delta$,

$\displaystyle\mathcal{R}_{ij}(g,\mathbf{\Theta}_{0})-\mathcal{R}_{ij}(g,\mathbf{\Theta}_{0}^{\prime})$
$\displaystyle\leq
4RB^{2}\left|I_{ij}(g)\right|\left|\left|\mathbf{\Theta}_{0}-\mathbf{\Theta}_{0}^{\prime}\right|\right|+4BR\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|.$

Thus if we take a union bound over a $\frac{1}{TRB^{2}}$-net of the Frobenius
ball of radius $R$ in $\mathbb{R}^{m\times(d+1)}$, we see that with
probability at least $1-\delta$, it holds that

$\displaystyle\mathcal{R}_{ij}(g)=\mathcal{R}_{ij}(g,\widehat{\mathbf{\Theta}}_{i})$
$\displaystyle\geq-
CBR\sqrt{Tm(d+1)\log\left(\frac{TBR}{\delta}\right)}-4BR\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|.$

We now note that by Lemma D.1, if $\mathcal{D}$ is an
$\varepsilon$-disagreement cover of $\mathcal{G}$, then

$\displaystyle\sup_{g\in\mathcal{G}}\min_{g_{k}\in\mathcal{D}}\sum_{t=1}^{T}\mathbb{I}\left[g(\bar{\mathbf{x}}_{t})\neq
g_{k}(\bar{\mathbf{x}}_{t})\right]\leq
2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right).$

We now apply Claim D.5 and note that this implies that if $g$ is the
projection of $\widehat{g}$ onto the disagreement cover, then

$\displaystyle\mathcal{R}_{ij}(\widehat{g})\geq\mathcal{R}_{ij}(g)-\left(4B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\left(2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)\right)$

Taking a union bound over $g\in\mathcal{D}$ and all pairs $(i,j)$ tells us
that with probability at least $1-\delta$,

$\displaystyle\mathcal{R}_{ij}(\widehat{g})\geq-
CBR\sqrt{Tmd\log\left(\frac{TBRK\textsc{DN}(\varepsilon)}{\delta}\right)}-4BR\sum_{t\in
I_{ij}(g)}\left|\left|\bm{\delta}_{t}\right|\right|-\left(4B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\left(2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)\right).$

Combining this with (D.9) concludes the proof. ∎

We are now finally ready to prove the main result of this section:

###### Proof of Lemma D.13.

We begin by noting that Lemma D.1 tells us that with probability at least
$1-\delta$, it holds that

$\sup_{g\in\mathcal{G}}\min_{g_{k}\in\mathcal{D}}\sum_{t=1}^{T}\mathbb{I}[g(\bar{\mathbf{x}}_{t})\neq
g_{k}(\bar{\mathbf{x}}_{t})]\leq
2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)$

We observe that for $g,g^{\prime}\in\mathcal{G}$, we have

$\displaystyle\mathcal{Q}_{ij}(g)-\mathcal{Q}_{ij}(g^{\prime})$
$\displaystyle=\sum_{t\in
I_{ij}(g)}\left|\left|(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j})\bar{\mathbf{x}}_{t}\right|\right|^{2}-\sum_{t\in
I_{ij}(g^{\prime})}\left|\left|(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j})\bar{\mathbf{x}}_{t}\right|\right|^{2}$
$\displaystyle\leq
4R^{2}B^{2}\sum_{t}\left|Z_{t;ij}(g)-Z_{t;ij}(g^{\prime})\right|$
$\displaystyle\leq
4R^{2}B^{2}\sum_{t=1}^{T}\mathbb{I}\left[g(\bar{\mathbf{x}}_{t})\neq
g^{\prime}(\bar{\mathbf{x}}_{t})\right].$

By Claim D.5, it holds that with probability at least $1-\delta$, for all
$g,g^{\prime}\in\mathcal{G}$, we have

$\displaystyle\mathcal{R}_{ij}(g)-\mathcal{R}_{ij}(g^{\prime})\leq\left(4B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\sum_{t=1}^{T}\mathbb{I}\left[g(\bar{\mathbf{x}}_{t})\neq
g^{\prime}(\bar{\mathbf{x}}_{t})\right]$

Now, taking a union bound over a minimal disagreement cover at scale
$\varepsilon$ as well as all pairs $1\leq i,j\leq K$, we see that Lemma D.14
implies that with probability at least $1-\delta$, it holds that for all
$g_{k}\in\mathcal{D}$ the disagreement cover,

$\displaystyle\mathcal{Q}_{ij}(g_{k})\leq\mathcal{R}_{ij}(g_{k})+C\nu^{2}dm\log\left(\frac{TRBmdK^{2}\textsc{DN}(\varepsilon)}{\lambda\delta}\right)+C\nu\sqrt{\lambda
dm\log\left(\frac{TRBmdK^{2}\textsc{DN}(\varepsilon)}{\lambda\delta}\right)}.$

Letting $g$ denote the projection of $\widehat{g}$ into the disagreement
cover, we compute:

$\displaystyle\mathcal{Q}_{ij}(\widehat{g})$
$\displaystyle=\mathcal{Q}_{ij}(\widehat{g})-\mathcal{Q}_{ij}(g)+\mathcal{Q}_{ij}(g)$
$\displaystyle\leq
4R^{2}B^{2}\sum_{t=1}^{T}\mathbb{I}\left[\widehat{g}(\bar{\mathbf{x}}_{t})\neq
g(\bar{\mathbf{x}}_{t})\right]+\mathcal{Q}_{ij}(g)$ $\displaystyle\leq
4R^{2}B^{2}\sum_{t=1}^{T}\mathbb{I}\left[\widehat{g}(\bar{\mathbf{x}}_{t})\neq
g(\bar{\mathbf{x}}_{t})\right]+\mathcal{R}_{ij}(g)+C\nu^{2}dm\log\left(\frac{TRBmdK^{2}\textsc{DN}(\varepsilon)}{\lambda\delta}\right)+C\nu\sqrt{\lambda
dm\log\left(\frac{TRBmdK^{2}\textsc{DN}(\varepsilon)}{\lambda\delta}\right)}$
$\displaystyle\leq\left(8B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\left(2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)\right)+\mathcal{R}_{ij}(\widehat{g})$
$\displaystyle+C\nu^{2}dm\log\left(\frac{TRBmdK^{2}\textsc{DN}(\varepsilon)}{\lambda\delta}\right)+C\nu\sqrt{\lambda
dm\log\left(\frac{TRBmdK^{2}\textsc{DN}(\varepsilon)}{\lambda\delta}\right)}$

Setting $\lambda=1$ and applying Lemma D.15 to bound
$\mathcal{R}_{ij}(\widehat{g})$ then tells us that

$\displaystyle\mathcal{Q}_{ij}(\widehat{g})$
$\displaystyle\leq\varepsilon_{\mathrm{orac}}+CK^{2}BR\sqrt{Tmd\log\left(\frac{TBRK\textsc{DN}(\varepsilon)}{\delta}\right)}+K^{2}\left(4B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\left(2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)\right)$
$\displaystyle+C\nu^{2}dm\log\left(\frac{TRBmdK^{2}\textsc{DN}(\varepsilon)}{\delta}\right)+C\nu\sqrt{dm\log\left(\frac{TRBmdK^{2}\textsc{DN}(\varepsilon)}{\delta}\right)}+4BRK^{2}T\varepsilon_{\mathrm{crp}}.$

We can now plug in our bound on $\textsc{DN}(\varepsilon)$ from Lemma D.3
which says that

$\displaystyle\log\left(\textsc{DN}(\mathcal{G},\varepsilon)\right)\leq
2Kd\log\left(\frac{3BK}{\varepsilon}\right)$

and set $\varepsilon=\frac{1}{T}$ to conclude the proof. ∎

With the proof of Lemma D.13 concluded, we now prove the technical lemmas:

######  Claim D.3.

Let $\bm{\Delta},\bm{\Delta}^{\prime}\in\mathbb{R}^{m\times(d+1)}$ have
Frobenius norm at most $R$. Let $E,V$ be defined as in the proof of Lemma
D.14. Then it holds that

$\displaystyle E(\bm{\Delta})^{2}-E(\bm{\Delta}^{\prime})^{2}$
$\displaystyle\leq\left(\sum_{t\in
I_{ij}(g)}\left|\left|\mathbf{e}_{t}\right|\right|^{2}\right)4RB^{2}T\sqrt{\|\bm{\Delta}-\bm{\Delta}^{\prime}\|_{\mathrm{F}}}$
$\displaystyle V(\bm{\Delta}^{\prime})-V(\bm{\Delta})$ $\displaystyle\leq
4RB^{2}T\sqrt{\bm{\Delta}-\bm{\Delta}^{\prime}}$

###### Proof.

We compute:

$\displaystyle E(\bm{\Delta})^{2}-E(\bm{\Delta}^{\prime})^{2}$
$\displaystyle=E(\bm{\Delta}+\bm{\Delta}^{\prime})\cdot
E(\bm{\Delta}-\bm{\Delta}^{\prime})$ $\displaystyle=\left(\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t},(\bm{\Delta}+\bm{\Delta}^{\prime})\mathbf{x}_{t}\right\rangle\right)\cdot\left(\sum_{t\in
I_{ij}(g)}\left\langle\mathbf{e}_{t},(\bm{\Delta}-\bm{\Delta}^{\prime})\mathbf{x}_{t}\right\rangle\right)$
$\displaystyle\leq\left(\sum_{t\in
I_{ij}(g)}\left|\left|\mathbf{e}_{t}\right|\right|^{2}\right)\sqrt{V(\bm{\Delta}+\bm{\Delta}^{\prime})}\cdot\sqrt{V(\bm{\Delta}-\bm{\Delta}^{\prime})}$
$\displaystyle\leq\left(\sum_{t\in
I_{ij}(g)}\left|\left|\mathbf{e}_{t}\right|\right|^{2}\right)\sqrt{16TR^{2}B^{2}}\cdot\sqrt{V(\bm{\Delta}-\bm{\Delta}^{\prime})},$

where the first equality follows from linearity, the first inequality follows
by Cauchy-Schwartz, and the last follows by a Assumption 4. Similarly,

$\displaystyle V(\bm{\Delta})-V(\bm{\Delta}^{\prime})$
$\displaystyle=\sum_{t\in
I_{ij}(g)}\left(\left|\left|\bm{\Delta}\bar{\mathbf{x}}_{t}\right|\right|+\left|\left|\bm{\Delta}^{\prime}\bar{\mathbf{x}}_{t}\right|\right|\right)\left(\left|\left|\bm{\Delta}\bar{\mathbf{x}}_{t}\right|\right|-\left|\left|\bm{\Delta}^{\prime}\bar{\mathbf{x}}_{t}\right|\right|\right)$
$\displaystyle\leq\sum_{t\in
I_{ij}(g)}(4RB)\left|\left|(\bm{\Delta}-\bm{\Delta}^{\prime})\bar{\mathbf{x}}_{t}\right|\right|$
$\displaystyle\leq
4RB\sqrt{T}\cdot\sqrt{V(\bm{\Delta}-\bm{\Delta}^{\prime})}.$

We now note that

$\displaystyle V(\bm{\Delta}-\bm{\Delta}^{\prime})$ $\displaystyle=\sum_{t\in
I_{ij}(g)}\left|\left|(\bm{\Delta}-\bm{\Delta}^{\prime})\bar{\mathbf{x}}_{t}\right|\right|^{2}$
$\displaystyle\leq\sum_{t\in
I_{ij}(g)}\|\bm{\Delta}-\bm{\Delta}^{\prime}\|_{\mathrm{F}}^{2}\left|\left|\bar{\mathbf{x}}_{t}\right|\right|^{2}$
$\displaystyle\leq TB^{2}\|\bm{\Delta}-\bm{\Delta}^{\prime}\|_{\mathrm{F}}.$

The result follows. ∎

######  Claim D.4.

Suppose that Assumption 3 holds. Then with probability at least $1-\delta$, it
holds that

$\displaystyle\sum_{t=1}^{T}\left|\left|\mathbf{e}_{t}\right|\right|^{2}\leq
2\nu^{2}\left(Tm\log(8)+\log\left(\frac{1}{\delta}\right)\right).$

###### Proof.

Denote by $\bar{}\mathbf{e}=(\mathbf{e}_{1},\dots,\mathbf{e}_{T})$ the
concatenation of all the $\mathbf{e}_{t}$ and note that $\bar{}\mathbf{e}$ is
subGaussian by Assumption 3. Let $\bar{}\mathbf{u}$ denote a unit vector in
$\mathbb{R}^{Tm}$ and note that for any fixed
$\bar{}\mathbf{u}\in\mathcal{S}^{Tm-1}$, it holds with probability at least
$1-\delta$ that
$\left\langle\bar{}\mathbf{e},\bar{}\mathbf{u}\right\rangle\leq\sqrt{2\nu^{2}\log\left(\frac{1}{\delta}\right)}$.
Constructing a covering at scale $\frac{1}{4}$ of $\mathcal{S}^{Tm-1}$ and
applying the standard discretization argument, we see that

$\displaystyle\sum_{t=1}^{T}\left|\left|\mathbf{e}_{t}\right|\right|^{2}=\left|\left|\bar{}\mathbf{e}\right|\right|^{2}=\left(\sup_{\bar{}\mathbf{u}\in
S^{Tm-1}}\left\langle\bar{}\mathbf{e},\bar{}\mathbf{u}\right\rangle\right)^{2}\leq
2\nu^{2}\left(Tm\log(8)+\log\left(\frac{1}{\delta}\right)\right)$

with probability at least $1-\delta$. ∎

######  Claim D.5.

Suppose that Assumptions 3 and 4 hold. Then, with probability at least
$1-\delta$, it holds for all $g,g^{\prime}$,

$\displaystyle\mathcal{R}_{ij}(g)-\mathcal{R}_{ij}(g^{\prime})\leq\left(4B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\sum_{t=1}^{T}\mathbb{I}\left[g(\bar{\mathbf{x}}_{t})\neq
g^{\prime}(\bar{\mathbf{x}}_{t})\right].$

###### Proof.

We compute:

$\displaystyle\mathcal{R}_{ij}(g)-\mathcal{R}_{ij}(g^{\prime})$
$\displaystyle=\sum_{t\in
I_{ij}(g)}\left|\left|\widehat{\mathbf{\Theta}}_{i}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\left|\left|\mathbf{e}_{t}\right|\right|^{2}-\sum_{t\in
I_{ij}(g^{\prime})}\left|\left|\widehat{\mathbf{\Theta}}_{i}\bar{\mathbf{x}}_{t}-\mathbf{y}_{t}\right|\right|^{2}-\left|\left|\mathbf{e}_{t}\right|\right|^{2}.$

A union bound and Assumption 3 tell us that with probability at least
$1-\delta$,

$\max_{1\leq t\leq
T}\left|\left|\mathbf{e}_{t}\right|\right|\leq\nu\sqrt{\log\left(\frac{T}{\delta}\right)}.$

As
$\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}\leq
2R$, the result follows. ∎

####  D.5 Proof of Theorem 12

We are now ready to put everything together and conclude the proof of Theorem
12. We first need to prove the following bound by combining results from
Sections D.3 and D.2:

######  Lemma D.16.

For any fixed $\xi<1$, Define the following notation:

$\displaystyle\Xi_{1}$
$\displaystyle=C\frac{B^{8}}{\sigma_{\mathrm{dir}}^{8}\xi^{8}}\left(\log\left(\frac{2T}{\delta}+\frac{d}{2}\log\left(\frac{B}{\sigma_{\mathrm{dir}}\xi}\right)+\log\left(K^{2}\textsc{DN}(\varepsilon)\right)\right)\right)$
$\displaystyle\Xi_{2}$
$\displaystyle=C\frac{B^{2}}{\sigma_{\mathrm{dir}}^{2}\xi^{2}}\left(2T\varepsilon+6\log\left(\frac{\textsc{DN}(\varepsilon)}{\delta}\right)\right)$
$\displaystyle\Xi_{3}$
$\displaystyle=4K^{2}T\xi+12\log\left(\frac{1}{\delta}\right)+\max\left(\Xi_{1},\Xi_{2}\right)$

With probability at least $1-\delta$, it holds that for all $1\leq i,j\leq K$
such that

$\displaystyle\left|I_{ij}(\widehat{g})\right|\geq\Xi_{3}.$ (D.10)

we have

$\displaystyle\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}^{2}\leq
C\frac{B^{2}}{\sigma_{\mathrm{dir}}^{2}\xi^{2}\left|I_{ij}(\widehat{g})\right|}\cdot\mathcal{Q}_{ij}(\widehat{g}).$
(D.11)

###### Proof.

We begin by applying a Chernoff bound (Lemma D.2) to bound the number of times
$t$ such that $Z_{t;ij}(\widehat{g})=1$ and
$\mathbb{P}_{t}(Z_{t;ij}(\widehat{g})=1)\leq\xi$. In particular, we have

$\displaystyle\mathbb{P}$
$\displaystyle\left(\sum_{t=1}^{T}\mathbb{I}\left[\text{there exist }i,j\text{
such that }Z_{t;ij}(\widehat{g})=1\text{ and
}\mathbb{P}_{t}(Z_{t;ij}(\widehat{g}))\leq\xi\right]\geq
2TK^{2}\xi+6\log\left(\frac{1}{\delta}\right)\right)$
$\displaystyle=\mathbb{P}\left(\sum_{t=1}^{T}\sum_{1\leq i,j\leq
K}\mathbb{I}\left[Z_{t;ij}(\widehat{g})=1\text{ and
}\mathbb{P}_{t}(Z_{t;ij}(\widehat{g}))\leq\xi\right]\geq
2TK^{2}\xi+6\log\left(\frac{1}{\delta}\right)\right)$
$\displaystyle\leq\delta$

where the last step follows by Lemma D.2. Now, denote

$\displaystyle\widetilde{I}_{ij}(\widehat{g})$
$\displaystyle=I_{ij}(\widehat{g})\cap\left\\{t|\mathbb{P}_{t}(Z_{t;ij}(\widehat{g}))\geq\xi\right\\}$
$\displaystyle\widetilde{\Sigma}_{ij}(g)$
$\displaystyle=\sum_{t\in\widetilde{I}_{ij}(\widehat{g})}\bar{\mathbf{x}}_{t}\bar{\mathbf{x}}_{t}^{T}$

and note that
$\Sigma_{ij}(\widehat{g})\succeq\widetilde{\Sigma}_{ij}(\widehat{g})$ by
construction. Furthermore, by the Chernoff bound above, with probability at
least $1-\delta$, if

$\displaystyle\left|I_{ij}(\widehat{g})\right|\geq
4K^{2}T\xi+12\log\left(\frac{1}{\delta}\right)+\max\left(\Xi_{1},\Xi_{2}\right),$

it holds that

$\displaystyle\left|\widetilde{I}_{ij}(\widehat{g})\right|\geq\max\left(\frac{1}{2}\left|I_{ij}(\widehat{g})\right|,\max\left(\Xi_{1},\Xi_{2}\right)\right).$

Now, applying Lemmas D.6 and D.10, we see that with probability at least
$1-\delta$,

$\displaystyle\Sigma_{ij}(\widehat{g})\succeq\widetilde{\Sigma}_{ij}(\widehat{g})\succeq
c\frac{\sigma_{\mathrm{dir}}^{2}\xi^{2}}{B^{2}}\left|\widetilde{I}_{ij}(\widehat{g})\right|I\succeq
c\frac{\sigma_{\mathrm{dir}}^{2}\xi^{2}}{B^{2}}\left|I_{ij}(\widehat{g})\right|.$

We now compute:

$\displaystyle\mathcal{Q}_{ij}(\widehat{g})$ $\displaystyle=\sum_{t\in
I_{ij}(\widehat{g})}\left|\left|\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}$
$\displaystyle=\sum_{t\in
I_{ij}(\widehat{g})}\operatorname{Tr}\left(\bar{\mathbf{x}}_{t}^{T}\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)^{T}\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\right)$
$\displaystyle=\sum_{t\in
I_{ij}(\widehat{g})}\operatorname{Tr}\left(\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)^{T}\left(\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\right)\bar{\mathbf{x}}_{t}\bar{\mathbf{x}}_{t}^{T}\right)$
$\displaystyle\geq\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}^{2}\cdot\lambda_{min}\left(\sum_{t\in
I_{ij}(\widehat{g})}\bar{\mathbf{x}}_{t}\bar{\mathbf{x}}_{t}^{T}\right)$
$\displaystyle=\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}^{2}\cdot\lambda_{min}\left(\Sigma_{ij}(\widehat{g})\right)$

where we have denoted by $\lambda_{min}(\cdot)$ the minimal eigenvalue of a
symmetric matrix. Thus, under our assumptions, with probability at least
$1-\delta$, it holds that

$\displaystyle\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}\leq
C\frac{B^{2}}{\sigma_{\mathrm{dir}}^{2}\xi^{2}\left|I_{ij}(\widehat{g})\right|}\cdot\mathcal{Q}_{ij}(\widehat{g})$

for all $i,j$ satisfying (D.10). The result follows. ∎

We are now ready to combine Lemma D.16 with the results of Section D.4 to
conclude the proof.

###### Proof of Theorem 12.

By Lemma D.13, it holds with probability at least $1-\delta$ that

$\displaystyle\mathcal{Q}_{ij}(\widehat{g})$
$\displaystyle\leq\varepsilon_{\mathrm{orac}}+CK^{2}BRd\sqrt{TmK\log\left(\frac{TBRK}{\delta}\right)}+CK^{3}d\left(4B^{2}R^{2}+\nu^{2}\log\left(\frac{T}{\delta}\right)\right)\log\left(\frac{BKT}{\delta}\right)$
$\displaystyle+C\nu^{2}d^{2}Km\log\left(\frac{TRBmdK}{\delta}\right)+C\nu
d\sqrt{Km\log\left(\frac{TRBmdK}{\delta}\right)}+4BRK^{2}\left|I_{ij}(g)\right|\varepsilon_{\mathrm{crp}}$
$\displaystyle\leq\varepsilon_{\mathrm{orac}}+1+CK^{3}B^{2}R^{2}d^{2}m\nu^{2}\sqrt{T}\log\left(\frac{TRBmdK}{\delta}\right)+4BRK^{2}\left|I_{ij}(g)\right|\varepsilon_{\mathrm{crp}}.$

By Lemma D.16, it holds with probability at least $1-\delta$ that for all
$i,j$ satisfying $\left|I_{ij}(\widehat{g})\right|\geq\Xi_{3}$, we have

$\displaystyle\|\widehat{\mathbf{\Theta}}_{i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}^{2}\leq
C\frac{B^{2}}{\sigma_{\mathrm{dir}}^{2}\xi^{2}\left|I_{ij}(\widehat{g})\right|}\mathcal{Q}_{ij}(\widehat{g}).$

It now suffices to note that, by Lemma D.3, it holds that

$\displaystyle\log\left(\textsc{DN}(\mathcal{G},\varepsilon)\right)\leq
K(d+1)\log\left(\frac{3BK}{\varepsilon}\right)$

and so, taking $\varepsilon=\frac{1}{T}$,

$\displaystyle\Xi_{3}\leq
CK^{2}T\xi+C\frac{B^{8}Kd}{\sigma_{\mathrm{dir}}^{8}\xi^{8}}\log\left(\frac{BKT}{\sigma_{\mathrm{dir}}\xi\delta}\right).$

The result follows. ∎

###  Appendix E Modifying the Classifier and Mode Prediction

1:Initialize  Classifier $\widehat{g}$, new parameters
$\left(\widehat{\mathbf{\Theta}}_{1,i}\right)_{1\leq i\leq K}$, old parameters
$\left(\widehat{\mathbf{\Theta}}_{0,i}\right)_{1\leq i\leq K}$, threshold
$A>0$, gap $\Delta_{\mathrm{sep}}>0$

2:for $i,j=1,2,\dots,K$ do (% Combine large clusters with similar
$\widehat{\mathbf{\Theta}}_{1,i}$)

3: if $i=j$ or $\min(I_{i}(\widehat{g}),I_{j}(\widehat{g}))<A$ then (%
Continue if cluster is too small)

4: Continue

5: if
$\left|\left|\widehat{\mathbf{\Theta}}_{1,i}-\widehat{\mathbf{\Theta}}_{1,j}\right|\right|<\Delta_{\mathrm{sep}}$
then (% Combine Cluster if parameters closer than gap)

6: $\widehat{g}\leftarrow(j\mapsto i)\circ\widehat{g}$

7: $I\leftarrow[K]$

8: Empty permutation $\tilde{\pi}:[K]\to[K]$

9: Reorder $I$ so that if $i<i^{\prime}$ then
$\left|I_{i}(\widehat{g})\right|>\left|I_{i^{\prime}}(\widehat{g})\right|$

10:for $i=1,2,\dots,K$ do

11: if $\left|I_{i}(\widehat{g})\right|>A$ then (% Check if cluster is large
enough)

12: $j\leftarrow\operatorname*{argmin}_{j^{\prime}\in
I}\left|\left|\widehat{\mathbf{\Theta}}_{1,i}-\widehat{\mathbf{\Theta}}_{0,j^{\prime}}\right|\right|$

13: $\tilde{\pi}(i)=j$

14: $I\leftarrow I\setminus\\{j\\}$

15: Return  $\tilde{\pi}\circ\widehat{g}$

Algorithm 3 Combine and Permute Labels

In this section, analyze Ogd (Algorithm 2), the algorithm that modifies the
classifer $\widehat{g}_{\tau}$ produced by $ermoracle$ after epoch into a
stabilized classifer $\widetilde{g}_{\tau}$ suitable for online prediction.
The problem with the former classifer $\widehat{g}_{\tau}$ is that while it
performs well on the past examples by construction, directional smoothness is
not strong enough to imply generalization in the sense that
$\widehat{g}_{\tau}$ will continue to perform well on epoch $\tau+1$.

##### Notation.

We begin our analysis of Ogd by defining some notation. For any $1\leq t\leq
T$, let $\tau(t)$ denote the epoch containing $t$, i.e.,
$\tau(t)=\max\left\\{\tau^{\prime}|\tau^{\prime}E\leq t\right\\}$. Further,
recall the concatenated parameter notation
$\mathbf{w}_{1:K}=(\mathbf{w}_{1},\dots,\mathbf{w}_{K})$ for
$\mathbf{w}_{i}\in\mathcal{B}^{d-1}$.

For a given epoch $\tau$, we let
$\left\\{\widehat{\mathbf{\Theta}}_{\tau,i}|i\in[K]\right\\},\widehat{g}_{\tau}$
denote the output of $\textsc{ErmOracle}(\bar{\mathbf{x}}_{1:\tau
E},\mathbf{y}_{1:\tau E})$. For any $g\in\mathcal{G}$ and $i,j\in[K]$, we
denote

$I_{ij;\tau}(g)=\left\\{1\leq t\leq\tau E|g(\bar{\mathbf{x}}_{t})=i\text{ and
}g_{\star}(\bar{\mathbf{x}}_{t})=j\right\\}.$ (E.1)

Finally, for a fixed epoch $\tau$, if ErmOracle has returned parameters
$\widehat{\mathbf{\Theta}}_{\tau,i}$, define

$\pi_{\tau}(i)=\operatorname*{argmin}_{1\leq j\leq
K}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{j}\|_{\mathrm{F}}$
(E.2)

the function that takes a label $i$ according to $\widehat{g}_{\tau}$ and
sends it to the closest label according to $g_{\star}$ as measured by
difference in parameter matrices. The notation “$\pi$” signifies that
$\pi_{\tau}$ represents a permutation when all the estimates
$\widehat{\mathbf{\Theta}}_{\tau,i}$ are sufficiently accurate.

We conduct the analysis under the following condition, which informally states
that for all sufficiently large clusters $I_{ij}$ considered in Algorithm 3
are sufficiently large, the associate parameters, Assumption 5

######  Condition 1.

We say that $\Xi\geq 0$ is a $\delta$-valid clusterability bound if it
satisfies the following property. If Algorithm 3 is run with $A=2K\Xi$ then
with probability at least $1-\delta$, for all $1\leq i\leq K$ such that

$I_{i;\tau}(\widehat{g}_{\tau})=\sum_{1\leq j\leq
K}\left|I_{ij;\tau}(\widehat{g}_{\tau})\right|>2K\Xi$ (E.3)

the following hold:

  1. 1.

There exists a unique $1\leq j\leq K$ such that
$\left|I_{ij;\tau}(\widehat{g}_{\tau})\right|>\Xi$ and for that $j$,
$\left|I_{ij;\tau}(\widehat{g}_{\tau})\right|>K\Xi$.

  2. 2.

For the $j$ given by the previous statement,
$\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau}-\mathbf{\Theta}^{\star}_{j}\right|\right|\leq\frac{\Delta_{\mathrm{sep}}}{4}$.

  3. 3.

For the $j$ in the previous statements, it holds that in epoch $\tau+1$, the
classifer $\widehat{g}_{\tau+1}$ after the reordering step in Algorithm 2, the
estimated parameter satisfies
$\left|I_{ij;\tau}(\widehat{g}_{\tau+1})\right|>\Xi$ and in particular,
$\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau+1}-\mathbf{\Theta}^{\star}_{j}\right|\right|\leq\frac{\Delta_{\mathrm{sep}}}{4}$.

Recall that the the pseudocode for Ogd is in Algorithm 2. In words, the
algorithm runs projected online gradient descent on
$\widetilde{\ell}_{\gamma,t,\widehat{g}}$. We have the following result.

######  Theorem 14.

Suppose that we run Algorithm 1 in the setting described in Section 2. If we
set $A=2K\Xi$, then with probability at least $1-\delta$, it holds that

$\displaystyle\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}})\right]$
$\displaystyle\leq\frac{2BET\eta}{\gamma}+3\left(1+\frac{1}{\gamma}\right)(KE+2K^{2}\Xi)+\frac{4K}{\eta}+\frac{\eta
T}{\gamma^{2}}+\frac{T\gamma}{\sigma_{\mathrm{dir}}}+\sqrt{T\log\left(\frac{1}{\delta}\right)}$
(E.4)

where $\Xi$ is a parameter depending on the gap and the problem, defined in
Lemma E.2.

##### Proof Strategy.

One challenge is that $\widetilde{g}_{\tau(t)}$ is that it is updated at the
start of epoch $\tau+1$, and is trained using labels corresponding to the
permutation $\pi_{\tau}$. Therefore, we decompose to the error indicator into
the case where
$\pi_{\tau+1}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))=\pi_{\tau}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))$,
so this difference is immaterial, and into the cases where $\pi_{\tau+1}$ and
$\pi_{\tau}$ differ.

$\mathbb{I}\left[\pi_{\tau}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}})\right]\leq\underbrace{\mathbb{I}\left[\pi_{\tau+1}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]}_{\text{(look-ahead classification
error)}}+\underbrace{\mathbb{I}\left[\pi_{\tau}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))\neq\pi_{\tau+1}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))\right]}_{\text{(permutation
disagreement error)}}$ (E.5)

We call the former term the “look-ahead classification error”, because it
applies the permutation from the subsequent epoch $\tau+1$; the name for the
second term is self-explanatory. Our online update Ogd(Algorithm 2) controls
the cumulative sum of the look-ahead classification error ( see Theorem 15 in
the following section), while our labeling protocol (Algorithm 3) bounds the
permutation disagreement error (see Lemma E.3 in the Section E.2).

####  E.1 Look-ahead Classification Error

In this section we prove that the first term of (E.5) is small with high
probability, which is the content of the following result:

######  Theorem 15.

With probability at least $1-\delta$, the look-ahead classification error is
at most

$\displaystyle\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau(t)+1}\left(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\right)\neq
g^{\star}(\bar{\mathbf{x}}_{t})\right]$
$\displaystyle\leq\frac{2BET\eta}{\gamma}+2\left(1+\gamma^{-1}\right)(KE+2K^{2}\Xi)+\frac{4K}{\eta}+\frac{\eta
T}{\gamma^{2}}+\frac{K^{2}T\gamma}{\sigma_{\mathrm{dir}}}+\sqrt{T\log\left(\tfrac{1}{\delta}\right)}.$
(E.6)

###### Proof.

In addition to the notation $\widetilde{\ell}_{\gamma,t,\widehat{g}}$ defined
in Equation 4.1, we introduce the following notation:

$\displaystyle i_{t}^{\star}=g^{\star}(\bar{\mathbf{x}}_{t})$
$\displaystyle\widehat{i}_{t}=\operatorname*{arg\,max}_{1\leq i\leq
K}\left\langle\mathbf{w}_{i}^{\tau(t)},\bar{\mathbf{x}}_{t}\right\rangle=\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t})$
$\displaystyle\bar{i}_{t}=\widehat{g}_{\tau(t)+1}(\bar{\mathbf{x}}_{t})$ (E.7)

or, in words, $i_{t}^{\star}$ is the groundtruth correct label,
$\widehat{i}_{t}$ is the class predicted by the current epoch’s linear
predictors, and $\bar{i}_{t}$ is the class predicted by the ERM trained with
the current epoch’s data included. Additionally, let

$\widetilde{\mathbf{w}}_{1:K}^{t}=\Pi_{({\mathcal{B}}^{d-1})^{\times
K}}\left(\widetilde{\mathbf{w}}_{1:K}^{t-1}-\eta\nabla\widetilde{\ell}_{\gamma,t,\widehat{g}_{k(t)+1}}(\widetilde{\mathbf{w}}_{1:K}^{t-1})\right)$
(E.8)

i.e., the predicted weight if we were able to apply gradient descent with the
labels predicted by the ERM trained on the current epoch’s data and

$\widetilde{i}_{t}=\operatorname*{arg\,max}_{1\leq i\leq
k}\left\langle\widetilde{}\mathbf{w}_{i}^{t},\bar{\mathbf{x}}_{t}\right\rangle,$
(E.9)

the class predicted by $\widetilde{\mathbf{w}_{1:K}}$. We also consider the
following “losses” that we will use in the analysis:

$\displaystyle\widehat{\ell}_{t}(\mathbf{w}_{1:K})=\mathbb{I}\left[\widehat{i}_{t}\neq\bar{i}_{t}\right]$
$\displaystyle\ell_{t}^{\star}(\mathbf{w}_{1:K})=\mathbb{I}\left[\pi_{\tau(t)+1}(\widehat{i}_{t})\neq
i_{t}^{\star}\right]$ (E.10)

or, in words, $\widehat{\ell}_{t}$ is the event that our prediction is not
equal to that of $\widehat{g}_{k(t)+1}$ and $\ell_{t}^{\star}$ is the event
that our prediction is not equal to the groundtruth.

##### Mistake Decomposition.

We now compute:

$\displaystyle\sum_{t=1}^{T}\ell_{t}^{\star}(\mathbf{w}_{1:K}^{\tau(t)})$
$\displaystyle\leq\underbrace{\left(\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau+1}(\widehat{g}_{\tau+1}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]\right)}_{\mathrm{Term}_{1}}+\left(\sum_{t=1}^{T}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\neq\widehat{g}_{\tau+1}(\bar{\mathbf{x}}_{t})\right]\right)$
(E.11)

Lemma E.4 in Section E.2 controls $\mathrm{Term}_{1}$. To control the other
term, we note that for any $t,\gamma,g,\mathbf{w}_{1:K}$,

$\displaystyle\widetilde{\ell}_{\gamma,t,g}(\mathbf{w}_{1:K})$
$\displaystyle=\max\left(0,\max_{j\neq
g(\bar{\mathbf{x}}_{t})}\left(1-\frac{\left\langle\mathbf{w}_{g(\bar{\mathbf{x}}_{t})}-\mathbf{w}_{j},\bar{\mathbf{x}}_{t}\right\rangle}{\gamma}\right)\right)\geq\mathbb{I}[g_{\mathbf{w}_{1:K}}(\bar{\mathbf{x}}_{t})\neq
g(\bar{\mathbf{x}}_{t})],$

where $g_{\mathbf{w}_{1:K}}(\bar{\mathbf{x}}_{t})$ is the classifier induced
by the paramters $\mathbf{w}_{1:K}$. As
$\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})$ is the classifier induced by
$\mathbf{w}_{1:K}^{\tau}$, we have

$\displaystyle\sum_{t=1}^{T}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\neq\widehat{g}_{\tau+1}(\bar{\mathbf{x}}_{t})\right]$
$\displaystyle\leq\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\mathbf{w}_{1:K}^{\tau})$
$\displaystyle\leq\underbrace{\left(\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\mathbf{w}_{1:K}^{\tau})-\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\widetilde{\mathbf{w}}_{1:K}^{t})\right)}_{\mathrm{Term}_{2}}+\left(\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\widetilde{\mathbf{w}}_{1:K}^{t})\right)$

Contining, we have

$\displaystyle\sum_{t=1}^{T}\ell_{t}^{\star}(\mathbf{w}_{1:K}^{\tau(t)})$
$\displaystyle\leq\mathrm{Term}_{1}+\mathrm{Term}_{2}+\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\widetilde{\mathbf{w}}_{1:K}^{t})$
$\displaystyle\leq\mathrm{Term}_{1}+\mathrm{Term}_{2}+\underbrace{\sup_{\mathbf{w}_{1:K}}\left(\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\widetilde{\mathbf{w}}_{1:K}^{t})-\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\mathbf{w}_{1:K})\right)}_{\mathrm{Term}_{3}}$
$\displaystyle+\underbrace{\inf_{\mathbf{w}_{1:K}}\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\mathbf{w}_{1:K})}_{\mathrm{Term}_{4}}$

##### Bounding the “delay” penalty: $\mathrm{Term}_{2}$.

$\mathrm{Term}_{2}$ corresponds to the error we may suffer from using delayed
gradient updates. We now observe that

$\displaystyle\left|\left|\nabla\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau(t)+1}}\right|\right|\leq\frac{\left|\left|\bar{\mathbf{x}}_{t}\right|\right|}{\gamma}\leq\frac{B}{\gamma}$
(E.12)

and that projection onto a convex body is a contraction. Furthermore, the
gradient update in Algorithm 2, Line 3 only affects at most two distinct $i,j$
in the coordinates of $\mathbf{w}_{1:K}$ per update. Thus it holds that, for
all $t$,

$\displaystyle\left|\left|{\widetilde{\mathbf{w}}_{1:K}}^{t}-\mathbf{w}_{1:K}^{\tau(t)}\right|\right|\leq
2E\eta.$

Applying (E.12) tells us that

$\mathrm{Term}_{2}:=\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\mathbf{w}_{1:K}^{\tau})-\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\widetilde{\mathbf{w}}_{1:K}^{t})\leq\frac{2BET\eta}{\gamma}.$
(E.13)

##### Bounding the regret term: $\mathrm{Term}_{3}$.

We see that $\mathrm{Term}_{3}$ is just the regret for Online Gradient Descent
for losses with gradients bounded in norm by $\frac{1}{\gamma}$ on the
$K$-fold product of unit balls, having diameter $2\sqrt{K}$. Thus it holds by
classical results (c.f. Hazan et al. [2016, Theorem 3.1]) that

$\mathrm{Term}_{3}=\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{k(t)}}(\widetilde{\mathbf{w}}_{t})-\inf_{\mathbf{w}_{1:K}}\widetilde{\ell}_{\gamma,t,\widehat{g}_{k(t)}}(\mathbf{w}_{1:K})\leq\frac{4K}{\eta}+\frac{\eta
T}{\gamma^{2}}.$ (E.14)

##### Bounding the comparator: $\mathrm{Term}_{4}$.

To bound $\mathrm{Term}_{4}$, we aim to move from the losses with margin
$\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}$ back to sum measure of
comulative classification error. The central object in this analysis is the
following “ambiguous set”, defined for each parameter $\mathbf{w}_{1:K}$:

$D_{\gamma}(\mathbf{w}_{1:K})=\left\\{\bar{\mathbf{x}}:\left|\left\langle\mathbf{w}_{i,1:d}-\mathbf{w}_{j,1:d},\mathbf{x}\right\rangle-
w_{i,d+1}+w_{j,d+1}\right|\leq\gamma\text{ for some }1\leq i\leq K\right\\},$
(E.15)

where we denote the first $d$ coordinates of $\mathbf{w}_{i}$ by
$\mathbf{w}_{i,1:d}$ and its last coordinate by the scalar $w_{i,d+1}$.Then,
by directional smoothness and a union bound, the following is true for any
fixed $\mathbf{w}_{1:K}$:

$\displaystyle\mathbb{P}(\bar{\mathbf{x}}_{t}\in
D_{\gamma}(\mathbf{w}_{1:K})\mid\mathscr{F}_{t})\leq
K^{2}\sup_{i,j}\mathbb{P}(\left|\left\langle\mathbf{w}_{i,1:d}-\mathbf{w}_{j,1:d},\mathbf{x}_{t}\right\rangle-
w_{i,d+1}+w_{j,d+1}\right|\leq\gamma\mid\mathscr{F}_{t})\leq\frac{K^{2}\gamma}{\sigma_{\mathrm{dir}}}.$

Let $\mathbf{w}_{1:K}^{\star}$ be the parameter associated with $g^{\star}$.
Then a consequence of the above display and Azuma’s inequality is that most
$\bar{\mathbf{x}}_{t}$’s fall outside of
$D_{\gamma}(\mathbf{w}_{1:K}^{\star})$:

$\displaystyle\sum_{t=1}^{T}\mathbb{I}\left[\bar{\mathbf{x}}_{t}\in
D_{\gamma}(\mathbf{w}_{1:K}^{\star})\right]$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{P}_{t}\left(\bar{\mathbf{x}}_{t}\in
D_{\gamma}(\mathbf{w}_{1:K}^{\star})\right)+\sqrt{T\log\left(\frac{1}{\delta}\right)}$
$\displaystyle\leq\frac{K^{2}T\gamma}{\sigma_{\mathrm{dir}}}+\sqrt{T\log\left(\frac{1}{\delta}\right)}.$
(E.16)

We compute:

$\displaystyle\inf_{\mathbf{w}_{1:K}}\sum_{t=1}^{T}\widetilde{\ell}_{\gamma,t,\widehat{g}_{\tau+1}}(\mathbf{w}_{1:K})$
$\displaystyle\leq\inf_{\mathbf{w}_{1:K}}\sum_{t=1}^{T}\mathbb{I}\left[\bar{\mathbf{x}}_{t}\in
D_{\gamma}(\mathbf{w}_{1:K})\right]+\left(1+\frac{2}{\gamma}\right)\sum_{t=1}^{T}\widehat{\ell}_{t}(\mathbf{w}_{1:K})$
$\displaystyle\leq\inf_{\mathbf{w}_{1:K}}\sum_{t=1}^{T}\mathbb{I}\left[\bar{\mathbf{x}}_{t}\in
D_{\gamma}(\mathbf{w}_{1:K})\right]+\left(1+\frac{2}{\gamma}\right)\sum_{t=1}^{T}\ell_{t}^{\star}(\mathbf{w}_{1:K})+\mathbb{I}\left[\pi_{\tau(t)+1}(\bar{i}_{t})\neq
i_{t}^{\star}\right]$
$\displaystyle\leq\left(1+\frac{2}{\gamma}\right)\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau(t)+1}(\bar{i}_{t})\neq
i_{t}^{\star}\right]+\inf_{\mathbf{w}_{1:K}}\sum_{t=1}^{T}\mathbb{I}\left[\bar{\mathbf{x}}_{t}\in
D_{\gamma}(\mathbf{w}_{1:K})\right]+\left(1+\frac{2}{\gamma}\right)\ell_{t}^{\star}(\mathbf{w}_{1:K})$
$\displaystyle\leq\left(1+\frac{2}{\gamma}\right)\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau(t)+1}(\bar{i}_{t})\neq
i_{t}^{\star}\right]+\sum_{t=1}^{T}\mathbb{I}\left[\bar{\mathbf{x}}_{t}\in
D_{\gamma}(\mathbf{w}_{1:K}^{\star})\right]$
$\displaystyle\leq\left(1+\frac{2}{\gamma}\right)\underbrace{\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau(t)+1}(\bar{i}_{t})\neq
i_{t}^{\star}\right]}_{=\mathrm{Term}_{1}}+\frac{K^{2}T\gamma}{\sigma_{\mathrm{dir}}}+\sqrt{T\log\left(\frac{1}{\delta}\right)}.$

where the first inequality follows by Lemma E.1, the second inequality is
trivial, the third inequality follows because the final term does not depend
on $\mathbf{w}_{1:K}$, the fourth inequality follows from the realizability
assumption, i.e., that $\ell_{t}^{\star}(\mathbf{w}_{1:K}^{\star})=0$ for all
$t$, and the last from Equation E.16 (recalling the definition of
$\mathrm{Term}_{1}$) .

Thus it holds with probability at least $1-\delta$ that

$\displaystyle\mathrm{Term}_{4}\leq\left(1+\frac{2}{\gamma}\right)\mathrm{Term}_{1}+\frac{K^{2}T\gamma}{\sigma_{\mathrm{dir}}}+\sqrt{T\log\left(\frac{1}{\delta}\right)}.$

##### Concluding the proof.

To conclude, we see that

$\displaystyle\sum_{t=1}^{T}\ell_{t}^{\star}(\mathbf{w}_{1:K}^{\tau(t)})$
$\displaystyle\leq\mathrm{Term}_{1}+\mathrm{Term}_{2}+\mathrm{Term}_{3}+\mathrm{Term}_{4}$
(E.17)
$\displaystyle\leq\left(1+\frac{2}{\gamma}\right)\mathrm{Term}_{1}+\frac{2BET\eta}{\gamma}+\frac{4K}{\eta}+\frac{\eta
T}{\gamma^{2}}+\frac{K^{2}T\gamma}{\sigma_{\mathrm{dir}}}+\sqrt{T\log\left(\frac{1}{\delta}\right)}.$
(E.18)

By Lemma E.4 it holds that

$\displaystyle\mathrm{Term}_{1}=\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau(t)+1}(\bar{i}_{t})\neq
i_{t}^{\star}\right]:=\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau(t)+1}(\widehat{g}_{\tau(t)+1}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]\leq KE+2K^{2}\Xi,$ (E.19)

where $\Xi$ is defined in Lemma E.2. This concludes the proof. ∎

######  Lemma E.1 (Bound indicator by soft margin).

For any $\gamma,t,\widehat{g}$, it holds that if each component of
$\mathbf{w}$ has unit norm, then

$\widetilde{\ell}_{\gamma,t,\widehat{g}}(\mathbf{w})\leq\mathbb{I}\left[\bar{\mathbf{x}}_{t}\in
D_{\gamma}(\mathbf{w}_{1:K})\right]+\left(1+\frac{2}{\gamma}\right)\widehat{\ell}_{t}(\mathbf{w}_{1:K}).$
(E.20)

###### Proof.

We prove this by casework. Suppose that
$\widehat{\ell}_{t}(\mathbf{w}_{1:K})=0$. Then it holds that

$\widehat{g}(\bar{\mathbf{x}}_{t})=\operatorname*{arg\,max}_{1\leq j\leq
K}\left\langle\mathbf{w}_{j},\bar{\mathbf{x}}_{t}\right\rangle$ (E.21)

and in particular for all $j\neq\widehat{g}(\bar{\mathbf{x}}_{t})$, it holds
that
$\left\langle\mathbf{w}_{\widehat{g}(\bar{\mathbf{x}}_{t})}-\mathbf{w}_{j},\bar{\mathbf{x}}_{t}\right\rangle\geq
0$. If $\bar{\mathbf{x}}_{t}\not\in D_{\gamma}(\mathbf{w}_{1:K})$ then it
holds by construction that

$\max_{j\neq\widehat{g}(\bar{\mathbf{x}}_{t})}1-\frac{\left\langle\mathbf{w}_{\widehat{g}(\bar{\mathbf{x}}_{t})}-\mathbf{w}_{j},\bar{\mathbf{x}}_{t}\right\rangle}{\gamma}\leq
0$ (E.22)

and the conclusion clearly holds. If it holds that

$\max_{j\neq\widehat{g}(\bar{\mathbf{x}}_{t})}1-\frac{\left\langle\mathbf{w}_{\widehat{g}(\mathbf{x}_{t})}-\mathbf{w}_{j},\bar{\mathbf{x}}_{t}\right\rangle}{\gamma}>0$
(E.23)

then either there is some $j$ such that
$\left\langle\mathbf{w}_{\widehat{g}(\mathbf{x}_{t})-\mathbf{w}_{j}},\bar{\mathbf{x}}_{t}\right\rangle<0$
or there is some $j$ such that
$\left\langle\mathbf{w}_{\widehat{g}(\bar{\mathbf{x}}_{t})}-\mathbf{w}_{j},\bar{\mathbf{x}}_{t}\right\rangle<\gamma$
and so $\bar{\mathbf{x}}_{t}\in D_{\gamma}(\mathbf{w}_{1:K})$. We cannot have
the former by the assumption that $\widehat{\ell}_{t}(\mathbf{w}_{1:K})=0$ so
the latter holds and the inequality follows in this case.

Now suppose that $\widehat{\ell}_{t}(\mathbf{w}_{1:K})=1$. Then we see that as
$\left|\left|\mathbf{w}_{i}\right|\right|\leq 1$ for all $i$,
$\widetilde{\ell}_{\gamma,t,\widehat{g}}\leq\left(1+\frac{2}{\gamma}\right)$
uniformly and the result holds. ∎

####  E.2 Bounding Permutation Disagreement and $\mathrm{Term}_{1}$

In this section, we provide a bound on the permutation disagreement error -
the second term of (E.5) - as well as on $\mathrm{Term}_{1}$ from the section
above . We begin by notion that Algorithm 3 ensures that large clusters remain
large accross epochs, a statement formalized by the following result:

######  Lemma E.2.

Define the following terms:

$\displaystyle\Xi_{1}$
$\displaystyle=CK^{2}T\xi+C\frac{B^{8}Kd}{\sigma_{\mathrm{dir}}^{8}\xi^{8}}\log\left(\frac{BKT}{\sigma_{\mathrm{dir}}\xi\delta}\right)$
(E.24) $\displaystyle\Xi_{2}$
$\displaystyle=C\frac{B^{2}}{\sigma_{\mathrm{dir}}^{2}\xi^{2}\Delta_{\mathrm{sep}}^{2}}\left(\varepsilon_{\mathrm{orac}}+1+K^{3}B^{2}R^{2}d^{2}m\nu^{2}\sqrt{T}\log\left(\frac{TRBmdK}{\delta}\right)\right)+\sum_{t=1}^{T}\left|\left|\bm{\delta}_{t}\right|\right|.$
(E.25)

Then $\Xi:=\max(\Xi_{1},\Xi_{2})$ is a $\delta$-valid clusterability parameter
in the sense of 1.

###### Proof.

By the pigeonhole principle, if $I_{i}(\widehat{g}_{\tau})>2K\Xi$ there must
be at least one $j$ such that
$\left|I_{ij;\tau}(\widehat{g}_{\tau})\right|>\Xi$ and thus by Theorem 12, it
holds that
$\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau}-\mathbf{\Theta}^{\star}_{j}\right|\right|\leq\frac{\Delta_{\mathrm{sep}}}{4}$
and thus the second statement holds. If there is another $j^{\prime}$ such
that $\left|I_{ij^{\prime};\tau}(\widehat{g}_{\tau})\right|>\Xi$ then it would
also hold that
$\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau}-\mathbf{\Theta}^{\star}_{j^{\prime}}\right|\right|\leq\frac{\Delta_{\mathrm{sep}}}{4}$
and the triangle inequality would then imply that
$\left|\left|\mathbf{\Theta}^{\star}_{j}-\mathbf{\Theta}^{\star}_{j^{\prime}}\right|\right|\leq\frac{\Delta_{\mathrm{sep}}}{2}<\Delta_{\mathrm{sep}}$,
which ensures that $j=j^{\prime}$ by Assumption 5. Applying pigeonhole again
then shows that

$\left|I_{ij;\tau}(\widehat{g}_{\tau})\right|=I_{i;\tau}(\widehat{g}_{\tau})-\sum_{j^{\prime}\neq
j}\left|I_{ij^{\prime};\tau}(\widehat{g}_{\tau})\right|>2K\Xi-(K-1)\Xi=(K+1)\Xi.$
(E.26)

Thus the first statement holds. For the last statement, note that as there are
at least $K\Xi$ times $t<\tau E$ such that
$g_{\star}(\bar{\mathbf{x}}_{t})=j$, there are at least $\Xi$ times
$t<(\tau+1)E$ such that $t\in I_{i^{\prime}j;\tau}(\widehat{g}_{\tau+1})$.
This implies, again by Theorem 12, that
$\left|\left|\widehat{\mathbf{\Theta}}_{i^{\prime}}^{\tau+1}-\mathbf{\Theta}^{\star}_{j}\right|\right|\leq\frac{\Delta_{\mathrm{sep}}}{4}$
and thus
$\left|\left|\widehat{\mathbf{\Theta}}_{i^{\prime}}^{\tau+1}-\widehat{\mathbf{\Theta}}_{i}^{\tau}\right|\right|\leq\frac{\Delta_{\mathrm{sep}}}{2}$.
If $i^{\prime}\neq i$ after running Algorithm 3 then there must be an
$i^{\prime\prime}$ such that
$I_{i^{\prime\prime};\tau}(\widehat{g}_{\tau+1})>K\Xi$ and
$\left|\left|\widehat{\mathbf{\Theta}}_{i^{\prime\prime}}^{\tau+1}-\widehat{\mathbf{\Theta}}_{i}^{\tau}\right|\right|\leq\frac{\Delta_{\mathrm{sep}}}{2}$.
But if this is the case then the triangle inequality implies that
$\left|\left|\widehat{\mathbf{\Theta}}_{i^{\prime\prime}}^{\tau+1}-\widehat{\mathbf{\Theta}}_{i^{\prime}}^{\tau+1}\right|\right|<\Delta_{\mathrm{sep}}$
and as they both are sufficiently large, there were merged by the first half
of Algorithm 3, implying that $i^{\prime\prime}=i^{\prime}$ and, in turn, that
$i^{\prime}=i$, by the the second half of Algorithm 3. Thus the first half of
the third statement holds. To conclude, simply apply Theorem 12. ∎

We are now ready to prove the main bound:

######  Lemma E.3.

With probability at least $1-\delta$, it holds that

$\displaystyle\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))\neq\pi_{\tau+1}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}))\right]\leq
KE+2K^{2}\Xi$ (E.27)

###### Proof.

We begin by fixing some $1\leq i\leq K$ and bounding the number of epochs
$\tau$ such that $\pi_{\tau}(i)\neq\pi_{\tau+1}(i)$. We will restrict our
focus to the probability $1-\delta$ event such that the conclusion of Lemma
E.2 holds. Suppose that there is an $i$ such that
$I_{i;\tau}(\widehat{g}_{\tau})>2K\Xi$ and $\pi_{\tau}(i)=j\neq
j^{\prime}=\pi_{\tau+1}(i)$. Then by Assumption 5 and the triangle inequality,
we have that

$\displaystyle\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau}-\mathbf{\Theta}^{\star}_{j}\right|\right|+\frac{\Delta_{\mathrm{sep}}}{4}$
$\displaystyle\leq\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau+1}-\mathbf{\Theta}^{\star}_{j^{\prime}}\right|\right|$
(E.28)
$\displaystyle\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau+1}-\mathbf{\Theta}^{\star}_{j^{\prime}}\right|\right|+\frac{\Delta_{\mathrm{sep}}}{4}$
$\displaystyle\leq\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau}-\mathbf{\Theta}^{\star}_{j}\right|\right|$
(E.29)

Rearranging and again applying Assumption 5 tells us that

$\frac{\Delta_{\mathrm{sep}}}{2}<\left|\left|\widehat{\mathbf{\Theta}}_{i}^{\tau}-\widehat{\mathbf{\Theta}}_{i}^{\tau+1}\right|\right|.$
(E.30)

Applying the second and third statements of Lemma E.2, however, brings a
contradiction. Thus we have, on the high probability event from Lemma E.2,

$\mathbb{I}\left[\pi_{\tau}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))\neq\pi_{\tau+1}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}))\right]\leq\mathbb{I}\left[I_{i;\tau}(\widehat{g}_{\tau(t)})\leq
2K\Xi\right].$ (E.31)

Thus we have

$\displaystyle\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t}))\neq\pi_{\tau+1}(\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}))\right]$
$\displaystyle\leq\sum_{i=1}^{K}\sum_{t=1}^{T}\mathbb{I}\left[\widetilde{g}_{\tau(t)}(\bar{\mathbf{x}}_{t})=i\right]\mathbb{I}\left[I_{i;\tau}(\widehat{g}_{\tau(t)})\leq
2K\Xi\right]$ (E.32) $\displaystyle\leq K\left(E+2K\Xi\right).$ (E.33)

The result follows. ∎

We may also apply Lemma E.2 to show that
$\pi_{\tau+1}(\widehat{g}_{\tau+1}(\bar{\mathbf{x}}_{t}))=g_{\star}(\bar{\mathbf{x}}_{t})$
most of the time. We formalize this statement in the following result:

######  Lemma E.4 (Wrong Labels Bound).

With probability at least $1-\delta$, it holds that

$\displaystyle\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau+1}(\widehat{g}_{\tau(t)+1}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]\leq KE+2K^{2}\Xi$ (E.34)

###### Proof.

By Lemma E.2, it holds that

$\displaystyle\mathbb{I}\left[\pi_{\tau+1}(\widehat{g}_{\tau(t)+1}(\bar{\mathbf{x}}_{t}))\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]\leq\sum_{i=1}^{K}\mathbb{I}\left[\widehat{g}_{\tau(t)+1}(\bar{\mathbf{x}}_{t})=i\right]\mathbb{I}\left[I_{i;\tau}(\widehat{g}_{\tau(t)+1})\leq
2K\Xi\right].$ (E.35)

Thus we may argue exactly as in Lemma E.3 to conclude the proof. ∎

###  Appendix F Proving Theorem 3

In this section we formally state and prove our main result, i.e., that
Algorithm 1 is an oracle-efficient algorithm for achieving expected regret
polynomial in all the parameters and scaling as $T^{1-\Omega(1)}$ as the
horizon tends to infinity. We have the following formal statement, which we
first estalbish under the assumption of a strict separation between parameters
(Assumption 5).

######  Theorem 16.

Suppose that Assumptions 2-5 hold. Then, for the correct choices of
$\gamma,\eta$, and $E$, given in the proof below (found above (F.7)),
Algorithm 1 experiences expected regret:

$\displaystyle\mathbb{E}\left[\operatorname{Reg}_{T}\right]\leq
CB^{10}R^{2}md\nu^{2}K^{4}\sigma_{\mathrm{dir}}^{-4}\Delta_{\mathrm{sep}}^{-1}T^{\frac{35}{36}}\left(\varepsilon_{\mathrm{orac}}+\log(TRBmdK)\right)+CBRK^{2}\sum_{t=1}^{T}\left|\left|\bm{\delta}_{t}\right|\right|.$

Note that the last term is $O\left(BRK^{2}T\varepsilon_{\mathrm{crp}}\right)$
in the worst case.

###### Proof.

We recall that Algorithm 1 proceeds in epochs of length $E$, a parameter to be
specified. At the beginning of epoch $\tau$, at time $(\tau-1)E+1$, ErmOracle
is called, producing $\widehat{\mathbf{\Theta}}_{\tau,i}$ for $1\leq i\leq K$
and $\widehat{g}_{\tau}$, for a total of $\frac{T}{E}\leq T$ calls to
ErmOracle. We then use Algorithm 2 to modify $\widehat{g}_{\tau}$ to
$\widetilde{g}_{\tau}$ and predict
$\hat{}\mathbf{y}_{t}=\widehat{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})}\bar{\mathbf{x}}_{t}$.
Thus we have

$\displaystyle\operatorname{Reg}_{T}$
$\displaystyle=\sum_{t=1}^{T}\left|\left|\hat{}\mathbf{y}_{t}-\mathbf{\Theta}^{\star}_{g_{\star}(\bar{\mathbf{x}}_{t})}\bar{\mathbf{x}}_{t}\right|\right|^{2}$
$\displaystyle=\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\left|\left|\left(\widehat{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})}-\mathbf{\Theta}^{\star}_{g_{\star}(\bar{\mathbf{x}}_{t})}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}$
$\displaystyle=\left(\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\left|\left|\left(\widehat{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})}-\mathbf{\Theta}^{\star}_{g_{\star}(\bar{\mathbf{x}}_{t})}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}\mathbb{I}\left[\pi_{\tau}\left(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\right)\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]\right)$
$\displaystyle+\left(\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\left|\left|\left(\widehat{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\right)}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}\right).$

For the first term, we have

$\displaystyle\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\left|\left|\left(\widehat{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})}-\mathbf{\Theta}^{\star}_{g_{\star}(\bar{\mathbf{x}}_{t})}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}\mathbb{I}\left[\pi_{\tau}\left(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\right)\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]$
$\displaystyle\leq\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}4B^{2}R^{2}\mathbb{I}\left[\pi_{\tau}\left(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\right)\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]$ $\displaystyle\leq
4B^{2}R^{2}\sum_{t=1}^{T}\mathbb{I}\left[\pi_{\tau}\left(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\right)\neq
g_{\star}(\bar{\mathbf{x}}_{t})\right]$

and thus, applying Theorem 14, it holds that the above expression is bounded
by

$\displaystyle
4B^{2}R^{2}\left(\frac{2BET\eta}{\gamma}+3\left(1+\frac{1}{\gamma}\right)(KE+2K^{2}\Xi)+\frac{4K}{\eta}+\frac{\eta
T}{\gamma^{2}}+\frac{T\gamma}{\sigma_{\mathrm{dir}}}+\sqrt{T\log\left(\frac{1}{\delta}\right)}\right).$
(F.1)

For the second term, we have

$\displaystyle\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\left|\left|\left(\widehat{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\right)}\right)\bar{\mathbf{x}}_{t}\right|\right|^{2}$
$\displaystyle\leq B^{2}\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\|\widehat{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})\right)}\|_{\mathrm{F}}^{2}$
$\displaystyle=B^{2}\sum_{i=1}^{K}\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(i\right)}\|_{\mathrm{F}}^{2}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})=i\right].$

Now, let

$\displaystyle\Xi_{1}$
$\displaystyle=CK^{2}T\xi+C\frac{B^{8}Kd}{\sigma_{\mathrm{dir}}^{8}\xi^{8}}\log\left(\frac{BKT}{\sigma_{\mathrm{dir}}\xi\delta}\right)$
(F.2) $\displaystyle\Xi_{2}^{\prime}$
$\displaystyle=C\frac{B^{2}}{\sigma_{\mathrm{dir}}^{2}\xi^{2}\alpha}\left(\varepsilon_{\mathrm{orac}}+1+K^{3}B^{2}R^{2}d^{2}m\nu^{2}\sqrt{T}\log\left(\frac{TRBmdK}{\delta}\right)\right)+\sum_{t=1}^{T}\left|\left|\bm{\delta}_{t}\right|\right|$
(F.3) $\displaystyle\Xi^{\prime}$ $\displaystyle=\max(\Xi_{1},\Xi_{2}).$ (F.4)

Note that as long as $\alpha<\Delta_{\mathrm{sep}}^{2}$ then Lemma E.2 tells
us that if we run Algorithm 1 with $A\geq 2K\Xi^{\prime}$, then with
probability at least $1-\delta$ it holds for all $1\leq i\leq K$ and all
$\tau\leq\tau^{\prime}$ that if

$\displaystyle I_{i}(\widehat{g}_{\tau})>2K\Xi^{\prime}$

then

$\displaystyle\left|I_{i\pi_{\tau}^{\prime}(i)}(\widehat{g}_{\tau^{\prime}})\right|>\Xi^{\prime}$

and

$\displaystyle\|\widehat{\mathbf{\Theta}}_{i}^{\tau^{\prime}}-\mathbf{\Theta}^{\star}_{\pi_{\tau^{\prime}(i)}}\|_{\mathrm{F}}^{2}\leq\alpha.$

Furthermore, under this condition, Lemma E.2 tells us that

$\displaystyle I_{i}(\widehat{g}_{\tau^{\prime}})>2K\Xi.$

Fixing an $i$, then, we see that

$\displaystyle\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(i\right)}\|_{\mathrm{F}}^{2}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})=i\right]$
$\displaystyle=\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(i\right)}\|_{\mathrm{F}}^{2}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})=i\wedge
I_{i}(\widehat{g}_{\tau})\leq 2K\Xi^{\prime}\right]$
$\displaystyle+\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(i\right)}\|_{\mathrm{F}}^{2}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})=i\wedge
I_{i(\widehat{g}_{\tau})}>2K\Xi^{\prime}\right].$

For the first term, we see that

$\displaystyle\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(i\right)}\|_{\mathrm{F}}^{2}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})=i\wedge
I_{i}(\widehat{g}_{\tau})\leq 2K\Xi^{\prime}\right]$ $\displaystyle\leq
4R^{2}\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})=i\wedge
I_{i}(\widehat{g}_{\tau})\leq 2K\Xi^{\prime}\right]$ $\displaystyle\leq
4R^{2}\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau E}2K\Xi^{\prime}$
$\displaystyle\leq\frac{4R^{2}TK\Xi^{\prime}}{E}.$

For the second term, we have with high probability that

$\displaystyle\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(i\right)}\|_{\mathrm{F}}^{2}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})=i\wedge
I_{i(\widehat{g}_{\tau})}>2K\Xi^{\prime}\right]$
$\displaystyle\leq\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau E}\alpha$
$\displaystyle\leq\alpha T.$

Summing over all $K$, we see that

$\displaystyle\sum_{i=1}^{K}\sum_{\tau=1}^{T/E}\sum_{t=(\tau-1)E+1}^{\tau
E}\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau}\left(i\right)}\|_{\mathrm{F}}^{2}\mathbb{I}\left[\widetilde{g}_{\tau}(\bar{\mathbf{x}}_{t})=i\right]$
$\displaystyle\leq B^{2}K\left(4R^{2}\frac{T}{E}K\Xi^{\prime}+\alpha
T\right).$ (F.5)

Thus, combining (F.1) and (F.5) tells us that with probability at least
$1-\delta$ it holds that $\operatorname{Reg}_{T}$ is upper bounded by

$\displaystyle 4$ $\displaystyle
B^{2}R^{2}\left(\frac{2BET\eta}{\gamma}+3\left(1+\frac{1}{\gamma}\right)(KE+2K^{2}\Xi)+\frac{4K}{\eta}+\frac{\eta
T}{\gamma^{2}}+\frac{T\gamma}{\sigma_{\mathrm{dir}}}+\sqrt{T\log\left(\frac{1}{\delta}\right)}\right)$
$\displaystyle+B^{2}K\left(4R^{2}\frac{T}{E}K\Xi^{\prime}+\alpha T\right)$

where $\Xi^{\prime}$ is given in (F.4) and $\Xi$ is given in Lemma E.2. Now,
setting

$\displaystyle E=T^{\frac{17}{18}},$ $\displaystyle\gamma=T^{-\frac{1}{36}},$
$\displaystyle\xi=T^{-\frac{1}{9}},$ $\displaystyle\alpha=T^{-\frac{1}{6}},$
$\displaystyle\eta=T^{-\frac{19}{36}},$ (F.6)

gives, with probability at least $1-\delta$,

$\displaystyle\operatorname{Reg}_{T}\leq
CB^{10}R^{2}md\nu^{2}K^{4}\sigma_{\mathrm{dir}}^{-4}\Delta_{\mathrm{sep}}^{-1}T^{\frac{35}{36}}\left(\varepsilon_{\mathrm{orac}}+\log(TRBmdK)\right)+CBRK^{2}\sum_{t=1}^{T}\left|\left|\bm{\delta}_{t}\right|\right|.$
(F.7)

This concludes the proof. ∎

###  Appendix G Application to PWA Dynamical Systems

####  G.1 Proof of Lemma 3.1

We observe that this result follows directly from Lemma C.5. Indeed, note that
by assumption, $\mathbf{z}_{t}|\mathscr{F}_{t-1},\mathbf{u}_{t}$ is
$\sigma_{\mathrm{dir}}$-directionally smooth by the assumption that
$\mathbf{e}_{t-1}|\mathscr{F}_{t-1}$ is thus. Similarly,
$\mathbf{u}_{t}|\mathscr{F}_{t-1},\mathbf{z}_{t}$ is
$\sigma_{\mathrm{dir}}$-directionally smooth by the assumption that
$\bar{\mathbf{e}}_{t}|\mathscr{F}_{t-1},\mathbf{e}_{t}$ is smooth. Therefore,
the conclusion follows from Lemma C.5.

####  G.2 Formal Simulation Regret Setup

In this setting, let $\bar{}\mathscr{F}_{t}$ denote the filtration generated
by $(\mathbf{x}_{s,h})_{1\leq s\leq t,1\leq h\leq H}$. Let $\mathscr{F}_{t,h}$
denote the filtration generated by $\bar{}\mathscr{F}_{t-1}$ and
$(\mathbf{x}_{t,h^{\prime}})_{1\leq h^{\prime}\leq h}$, with the convention
$\mathscr{F}_{t,0}=\bar{}\mathscr{F}_{t-1}$. We require that our estimates
$\widehat{\mathbf{\Theta}}_{t,i}$ be $\bar{}\mathscr{F}_{t-1}$-measurable.
Further, we assume that our planner returns open-loop stochastic policies.

######  Assumption 9 (Smoothed, Open Loop Stochastic Policies).

We assume that our policy $\pi_{t}$ is stochastic and does not depend on
state. That is, we assume that for all all $h\in[H]$ and $t\in[T]$.
$\mathbf{u}_{t,h},\dots,\mathbf{u}_{t,H}\perp\mathbf{x}_{t,1:h}\mid\mathscr{F}_{t-1}$.
We further assume that
$\mathbf{u}_{t,h}\mid\mathbf{u}_{t,1:h-1},\mathscr{F}_{t-1}$ is
$\sigma_{\mathrm{dir}}$-smooth.

######  Assumption 10 (Noise Distribution).

We assume that $\|\mathbf{e}_{t,h}\|\leq B_{\mathrm{noise}}$ for all $t,h$.
Further, we assume that there exists a zero-mean,
$\sigma_{\mathrm{dir}}$-directionally smooth distribution $\mathcal{D}$ over
$\mathbb{R}^{d_{z}}$ such that
$\mathbf{e}_{t,h}\mid\mathscr{F}_{t,h-1}\sim\mathcal{D}$.777Results can be
extended to $\mathcal{D}_{t,h}$ changing with the time step as long as these
distributions are known to the learner.  Furthermore, we also assume that
$\mathbf{z}_{t,1}\mid\bar{}\mathscr{F}_{t-1}$ is
$\sigma_{\mathrm{dir}}$-smooth.

######  Definition 17 (Wasserstein Distance).

Let $(\mathcal{X},\mathsf{d})$ be a Polish space with metric
$\mathsf{d}(\cdot,\cdot)$, and let $\mu,\nu$ be two Borel measures on
$\mathcal{X}$. Define the Wasserstein distance as

$\displaystyle\mathcal{W}_{2}^{2}(\mu,\nu)=\inf_{\Gamma}\mathbb{E}_{(X,Y)\sim\Gamma}\left[\mathsf{d}(X,Y)^{2}\right]$

where the infimum is over all couplings $\Gamma$ such that the marginal of $X$
is distributed as $\mu$ and the marginal over $Y$ is distributed as $\nu$.

We will show that with minor modifications, outlined below, Algorithm 1 can be
leveraged to produce $H$-step simulated predictions with laws that are close
in Wasserstein distance. In particular, this allows us to control the error of
the associated predictions in expected squared norm.

####  G.3 Algorithm Modifications

1:Initialize  Epoch length $E$, Classifiers
$\mathbf{w}^{0}=(\mathbf{0},\dots,\mathbf{0})$, margin parameter $\gamma>0$,
learning rate $\eta>0$, noise distributions $\mathcal{D}$

2:for $\tau=1,2,\dots,T/E$ do

3: $\left\\{(\widehat{\mathbf{\Theta}}_{\tau,i})_{1\leq i\leq
K},\,\widehat{g}_{\tau}\right\\}\leftarrow\textsc{ErmOracle}((\bar{\mathbf{x}}_{1:\tau
E},\mathbf{y}_{1:\tau E}))$ (%
$\mathbf{\mathsf{self}}.\mathbf{\mathsf{modelUpdate}}$)

4:
$\widetilde{\mathbf{\Theta}}_{\tau_{i}}\leftarrow\mathbf{\mathsf{Project}}_{\mathcal{C}_{\mathbf{P}}}(\widehat{\mathbf{\Theta}}_{\tau_{i}})$
(% See (G.1))

5:
$\widehat{g}_{\tau}\leftarrow\mathbf{\mathsf{Reorder}}\left(\widehat{g}_{\tau},\left(\widetilde{\mathbf{\Theta}}_{\tau,i}\right)_{1\leq
i\leq K},\left(\widetilde{\mathbf{\Theta}}_{\tau-1,i}\right)_{1\leq i\leq
K}\right)$ (% see Algorithm 3)

6:
$\widetilde{g}_{\tau}\leftarrow\textsc{Ogd}(\bar{\mathbf{x}}_{(\tau-1)E:\tau
E},\widehat{g}_{\tau},\gamma,\eta)$ (% see Algorithm 2)

7: for $t=\tau E,\dots,(\tau+1)E-1$ do

8: Receive  $\bar{\mathbf{x}}_{t}$ and set
$\widehat{\mathbf{x}}_{t,0}=\bar{\mathbf{x}}_{t}$

9: for $h=1,2,\dots,H$ do

10: Sample  $\mathbf{e}_{t,h}^{\prime}\sim\mathcal{D}$

11: Predict
$\widehat{\mathbf{x}}_{t,h}=\widetilde{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\widehat{\mathbf{x}}_{t,h-1})}\cdot\widehat{\mathbf{x}}_{t,h-1}+\mathbf{e}_{t,h}^{\prime}$

12: Receive  $\mathbf{y}_{t}$

Algorithm 4 Algorithm for achieving low Simulation Regret

In order to produce good simulation regret, we run a variant of Algorithm 1
with two changes. First, we need to use Assumption 8 in some way to ensure
that our estimated dynamics are contractive. Second, we need to iterate our
predicitions in order to generate a trajectory of length $H$ for each time
$t$. To address the first problem, suppose that we are in Line 3 of Algorithm
1, which applies ErmOracle to the past data, resulting in
$\left\\{(\widehat{\mathbf{\Theta}}_{\tau,i})_{1\leq i\leq
K},\widehat{g}_{\tau}\right\\}$. For each $i$, we modify
$\widehat{\mathbf{\Theta}}_{\tau,i}$ to become
$\widetilde{\mathbf{\Theta}}_{\tau,i}$ by projecting
$\widehat{\mathbf{\Theta}}_{\tau,i}$ onto the convex set

$\displaystyle\mathcal{C}_{\mathbf{P}}=\left\\{\mathbf{\Theta}|\mathbf{\Theta}^{\top}\mathbf{P}\mathbf{\Theta}\preceq\mathbf{P}\right\\}.$

Formally, we define the projection to be

$\displaystyle\mathbf{\mathsf{Project}}_{\mathcal{C}_{\mathbf{P}}}(\mathbf{\Theta})=\operatorname*{argmin}_{\mathbf{\Theta}^{\prime}\in\mathcal{C}_{\mathbf{P}}}\|\mathbf{\Theta}-\mathbf{\Theta}^{\prime}\|_{\mathrm{F}}.$
(G.1)

Because $\mathcal{C}_{\mathbf{P}}$ is convex, this step can be accomplished
efficiently. As we shall observe in the sequel, this projection step never
hurts our error guarantees due, again, to the convexity of
$\mathcal{C}_{\mathbf{P}}$.

Moving on to the second modification, at each epoch $\tau$, we have a fixed
set of parameters $\left\\{(\widetilde{\mathbf{\Theta}}_{\tau,i})_{1\leq i\leq
K},\widetilde{g}_{\tau}\right\\}$ where the $\widetilde{g}_{\tau}$ are
modified from $\widehat{g}_{\tau}$ exactly as in Algorithm 1. Thus, at each
time, we independently sample $\mathbf{e}_{t,h}^{\prime}\sim\mathcal{D}$, the
noise distribution, for $1\leq h\leq H$ and predict
$\widehat{\mathbf{x}}_{t,h}=\widetilde{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\widehat{\mathbf{x}}_{t,h-1})}\cdot\widehat{\mathbf{x}}_{t,h-1}+\mathbf{e}_{t,h}^{\prime}$.
The entire modified algorithm is given in Algorithm 4 and we prove in the
sequel that we experience low simulation regret.

####  G.4 Formal Guarantees for Simulation Regret

In this section, we prove that Algorithm 4 attains low simulation regret under
our stated assumptions. Noting that Algorithm 4 is oracle-efficient, this
result provides the first efficient algorithm that provably attains low
simulation regret in the PWA setting. The main result is as follows:

######  Theorem 18 (Simulation Regret Bound).

Suppose that we are in the setting of (3.3) and that Assumptions 5, 6, 7, 8,
9, and 10 hold. Suppose that we run Algorithm 4. Then, with probability at
least $1-\delta$, it holds that

$\displaystyle\mathrm{SimReg}_{T,H}\leq\frac{9B^{2}H^{8}}{\sigma_{\mathrm{dir}}^{2}}\cdot\left(CB^{10}R^{2}md\nu^{2}K^{4}\sigma_{\mathrm{dir}}^{-4}\Delta_{\mathrm{sep}}^{-1}T^{\frac{35}{36}}\left(\varepsilon_{\mathrm{orac}}+\log(TRBmdK)\right)+CBRK^{2}T\varepsilon_{\mathrm{crp}}\right).$

Before we prove Theorem 18, we must state the following key lemma, which says
that if both the true and estimated dynamics are stable, and we are able to
predict $\mathbf{x}_{t+1}$ with high accuracy, then our simulation regret $H$
steps into the future is also small.

######  Lemma G.1.

Let $\mathcal{G}:\mathbb{R}^{d}\to[K]$ denote the class of multi-class affine
classifiers and let $\widehat{f},f^{\star}$ denote functions satisfying the
following properties:

  1. 1.

The function $f^{\star}$ can be decomposed as
$f^{\star}(\mathbf{x})=f^{\star}_{g_{\star}(\mathbf{x})}(\mathbf{x})$ and
similarly for $\widehat{f}$ it holds that
$\widehat{f}(\mathbf{x})=\widehat{f}_{\widehat{g}(\mathbf{x})}(\mathbf{x})$
for some $g_{\star},\widehat{g}\in\mathcal{G}$.

  2. 2.

For all $i\in[K]$, it holds that both $\widehat{f}_{i}$ and $f^{\star}_{i}$
are contractions, i.e.,
$\left|\left|f^{\star}_{i}(\mathbf{x})-f^{\star}_{i}(\mathbf{x}^{\prime})\right|\right|\leq\left|\left|\mathbf{x}-\mathbf{x}^{\prime}\right|\right|$.

Suppose that for $0\leq h\leq H-1$, we let

$\displaystyle\mathbf{x}_{h+1}=f^{\star}(\mathbf{x}_{h})+\mathbf{e}_{h}$
$\displaystyle\widehat{\mathbf{x}}_{h+1}=\widehat{f}(\widehat{\mathbf{x}}_{h})+\mathbf{e}_{h}^{\prime}$

for $\mathbf{e}_{h},\mathbf{e}_{h}^{\prime}$ identically distributed
satisfying Assumption 10. Suppose that $\mathbf{x}_{0}$ is
$\sigma_{\mathrm{dir}}$-smooth and that, almost surely,
$\mathbf{x}_{h},\widehat{\mathbf{x}}_{h}$ have norms bounded uniformly by $B$.
If $\max_{1\leq
h<H}\left|\left|\widehat{f}(\mathbf{x}_{h})-f^{\star}(\mathbf{x}_{h})\right|\right|\leq\varepsilon$
then it holds that

$\displaystyle\mathcal{W}_{2}^{2}\left(\mathbf{x}_{H},\widehat{\mathbf{x}}_{H}\right)\leq\frac{9B^{2}H^{6}}{\sigma_{\mathrm{dir}}^{2}}\varepsilon^{2}\varepsilon.$

###### Proof.

We begin by introducing intermediate random variables
$\mathbf{x}_{H}^{(\ell)}$ for $1\leq\ell\leq H$. We let
$\mathbf{x}_{h}^{(\ell)}=\mathbf{x}_{h}$ for $h\leq\ell$ and let

$\displaystyle\mathbf{x}_{h+1}^{(\ell)}=\widehat{f}\left(\mathbf{x}_{h}^{(\ell)}\right)+\mathbf{e}_{t}^{\prime}$

otherwise. Note that $\mathbf{x}_{H}^{(1)}=\widehat{\mathbf{x}}_{H}$ and that
$\mathbf{x}_{H}^{(H)}=\mathbf{x}_{H}$. By the triangle inequality applied to
Wasserstein distance, we observe that

$\displaystyle\mathcal{W}_{2}(\mathbf{x}_{H},\widehat{\mathbf{x}}_{H})\leq\sum_{\ell=1}^{H}\mathcal{W}_{2}\left(\mathbf{x}_{H}^{(\ell)},\mathbf{x}_{H}^{(\ell+1)}\right).$

Consider a coupling where $\mathbf{e}_{h}=\mathbf{e}_{h}^{\prime}$ for all
$h$. Note that under this coupling, for any $h>\ell$, it holds that

$\displaystyle\left|\left|\mathbf{x}_{h}^{(\ell)}-\mathbf{x}_{h}^{(\ell+1)}\right|\right|$
$\displaystyle=\left|\left|\widehat{f}(\mathbf{x}_{h-1}^{(\ell)})+\mathbf{e}_{t}-\widehat{f}(\mathbf{x}_{h-1}^{(\ell+1)})-\mathbf{e}_{t}^{\prime}\right|\right|$
$\displaystyle=\left|\left|\widehat{f}(\mathbf{x}_{h-1}^{(\ell)})-\widehat{f}(\mathbf{x}_{h-1}^{(\ell+1)})\right|\right|$
$\displaystyle\leq\left|\left|\mathbf{x}_{h-1}^{(\ell)}-\mathbf{x}_{h-1}^{(\ell+1)}\right|\right|+B\cdot\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\right].$

Thus, in particular,

$\displaystyle\left|\left|\mathbf{x}_{H}^{(\ell)}-\mathbf{x}_{H}^{(\ell+1)}\right|\right|$
$\displaystyle\leq\left|\left|\mathbf{x}_{\ell+1}^{(\ell)}-\mathbf{x}_{\ell+1}^{(\ell+1)}\right|\right|+B\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\right]$
$\displaystyle\leq\left|\left|\widehat{f}(\mathbf{x}_{\ell})-f^{\star}(\mathbf{x}_{\ell})\right|\right|+B\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\right]$
$\displaystyle\leq\varepsilon+B\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\right]$

by the assumption that
$\left|\left|\widehat{f}(\mathbf{x}_{h})-f^{\star}(\mathbf{x}_{h})\right|\right|\leq\varepsilon$.
We now note that a union bound implies:

$\displaystyle\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\right]$
$\displaystyle=\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\widehat{g}(\mathbf{x}_{h^{\prime}}^{(\ell)})=g_{\star}(\mathbf{x}_{h^{\prime}}^{(\ell+1)})\text{
for }h^{\prime}\leq h\right]$
$\displaystyle+\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and there exists }h^{\prime}\leq h\text{ such that
}\widehat{g}(\mathbf{x}_{h^{\prime}}^{(\ell)})\neq
g_{\star}(\mathbf{x}_{h^{\prime}}^{(\ell+1)})\right]$
$\displaystyle\leq\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\widehat{g}(\mathbf{x}_{h^{\prime}}^{(\ell)})=g_{\star}(\mathbf{x}_{h^{\prime}}^{(\ell+1)})\text{
for }h^{\prime}\leq h\right]$
$\displaystyle+\sum_{h=\ell}^{H-1}(H-1-\ell)\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\widehat{g}(\mathbf{x}_{h^{\prime}}^{(\ell)})=g_{\star}(\mathbf{x}_{h^{\prime}}^{(\ell+1)})\text{
for }h^{\prime}\leq h\right]$ $\displaystyle\leq
H\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\widehat{g}(\mathbf{x}_{h^{\prime}}^{(\ell)})=g_{\star}(\mathbf{x}_{h^{\prime}}^{(\ell+1)})\text{
for }h^{\prime}\leq h\right].$

We now observe that

$\displaystyle\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\widehat{g}(\mathbf{x}_{h^{\prime}}^{(\ell)})=g_{\star}(\mathbf{x}_{h^{\prime}}^{(\ell+1)})\text{
for }h^{\prime}\leq h\right]$
$\displaystyle\leq\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\left|\left|\mathbf{x}_{h-1}^{(\ell)}-\mathbf{x}_{h-1}^{(\ell+1)}\right|\right|\leq\varepsilon\right]$

By the fact that $\mathcal{G}$ is given by multi-class affine thresholds, we
see that

$\displaystyle\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\left|\left|\mathbf{x}_{h-1}^{(\ell)}-\mathbf{x}_{h-1}^{(\ell+1)}\right|\right|\leq\varepsilon\right]$
$\displaystyle\leq\sum_{1\leq i,j\leq
K}\mathbb{I}\left[\left|\left\langle\mathbf{w}_{ij},\mathbf{x}_{h-1}\right\rangle\right|\leq
2\varepsilon\right]$

where the $\mathbf{w}_{ij}$ are the unit vectors determining the decision
boundaries induced by $\widehat{g}$. By smoothness, then, we see that

$\displaystyle\mathcal{W}(\mathbf{x}_{H}^{(\ell)},\mathbf{x}_{H}^{(\ell+1)})$
$\displaystyle\leq\varepsilon+BH\cdot\mathbb{P}\left(\sum_{h=\ell}^{H-1}\mathbb{I}\left[\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\widehat{g}(\mathbf{x}_{h^{\prime}}^{(\ell)})=g_{\star}(\mathbf{x}_{h^{\prime}}^{(\ell+1)})\text{
for }h^{\prime}\leq h\right]>1\right)$
$\displaystyle\leq\varepsilon+BH\sum_{h=1}^{H}\mathbb{P}\left(\widehat{g}(\mathbf{x}_{h-1}^{(\ell)})\neq\widehat{g}(\mathbf{x}_{h-1}^{(\ell+1)})\text{
and
}\widehat{g}(\mathbf{x}_{h^{\prime}}^{(\ell)})=g_{\star}(\mathbf{x}_{h^{\prime}}^{(\ell+1)})\text{
for }h^{\prime}\leq h\right)$
$\displaystyle\leq\varepsilon+BH\sum_{h=1}^{H}\sum_{1\leq i,j\leq
K}\mathbb{P}\left(\left|\left\langle\mathbf{w}_{ij},\mathbf{x}_{h}\right\rangle\right|\leq
2\varepsilon\right)$
$\displaystyle\leq\left(1+\frac{2BH^{2}}{\sigma_{\mathrm{dir}}}\right)\varepsilon.$

Plugging this into our bound at the beginning and noting that
$1\leq\frac{BH^{2}}{\sigma_{\mathrm{dir}}}$ concludes the proof. ∎

We are now ready to prove Theorem 18. In particular, we use Lemma G.1 to
reduce a bound on simulation regret to one of the distance between
$\widehat{f}$ and $f^{\star}$ evaluated on the data sequence. We then apply
Theorems 12 and 14 to control this distance. The details are below:

###### Proof of Theorem 18.

We begin by applying Lemma G.1. Observe that in our setting, $\mathcal{G}$ is
the class of multi-class affine classifiers and $f^{\star},\widehat{f}_{t}$
can be decomposed as required by the theorem, where we let $\tau$ denote the
epoch in which $t$ is placed and let

$\displaystyle\widehat{f}_{t}(\mathbf{x})=\widetilde{\mathbf{\Theta}}_{\tau,\widetilde{g}_{\tau}(\mathbf{x})}\cdot\mathbf{x}.$

By the fact that
$\widetilde{\mathbf{\Theta}}_{\tau,i},\mathbf{\Theta}^{\star}_{i}\in\mathcal{C}_{\mathbf{P}}$,
which follows from the construction of $\widetilde{\mathbf{\Theta}}_{\tau,i}$
and Assumption 8, the contractivity assumption required by Lemma G.1 holds.
Furthermore, note that because $\mathcal{C}_{\mathbf{P}}$ is convex and
$\mathbf{\Theta}^{\star}_{i}\in\mathcal{C}_{\mathbf{P}}$, it holds that

$\displaystyle\|\widetilde{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau(i)}}\|_{\mathrm{F}}\leq\|\widehat{\mathbf{\Theta}}_{\tau,i}-\mathbf{\Theta}^{\star}_{\pi_{\tau(i)}}\|_{\mathrm{F}}.$
(G.2)

Now, note that Algorithm 1 does not update the predicting functions within the
epoch and thus for all $t$ such that $\left\\{t,t+1,\dots,t+H\right\\}$ does
not contain an integral multiple of $E$, it holds that our prediction function
$\widehat{f}_{t}$ is constant on the interval. Let $\mathcal{I}$ denote the
set of times $t$ such that the previous condition fails, i.e.,

$\displaystyle\mathcal{I}=\left\\{t\leq T|\tau E-t>H\text{ for all
}\tau\in\mathbb{N}\right\\}.$

Then, we may apply Lemma G.1 to get

$\displaystyle\mathrm{SimReg}_{T,H}$
$\displaystyle=\sum_{t=1}^{T}\sum_{h=1}^{H}\mathcal{W}_{2}^{2}(\mathbf{x}_{t+h},\widehat{\mathbf{x}}_{t+h}|\mathscr{F}_{t-1})$
$\displaystyle=\sum_{t=1}^{T}\mathbb{I}\left[t\in\mathcal{I}\right]\sum_{h=1}^{H}\mathcal{W}_{2}^{2}(\mathbf{x}_{t+h},\widehat{\mathbf{x}}_{t+h}|\mathscr{F}_{t-1})+\sum_{t=1}^{T}\mathbb{I}\left[t\not\in\mathcal{I}\right]\sum_{h=1}^{H}\mathcal{W}_{2}^{2}(\mathbf{x}_{t+h},\widehat{\mathbf{x}}_{t+h}|\mathscr{F}_{t-1})$
$\displaystyle\leq\sum_{t=1}^{T}\mathbb{I}\left[t\in\mathcal{I}\right]\sum_{h=1}^{H}\frac{9B^{2}H^{6}}{\sigma_{\mathrm{dir}}^{2}}\max_{1\leq
h\leq
H}\left|\left|\widehat{f}(\mathbf{x}_{t+h})-f^{\star}(\mathbf{x}_{t+h})\right|\right|^{2}+4HB^{2}R^{2}\sum_{t=1}^{T}\mathbb{I}\left[t\notin\mathcal{I}\right]$
$\displaystyle\leq\frac{9B^{2}H^{7}}{\sigma_{\mathrm{dir}}^{2}}\sum_{t=1}^{T}\mathbb{I}\left[t\in\mathcal{I}\right]\sum_{h=1}^{H}\left|\left|\widehat{f}(\mathbf{x}_{t+h})-f^{\star}(\mathbf{x}_{t+h})\right|\right|^{2}+4B^{2}R^{2}H\cdot\frac{HT}{E}$
$\displaystyle\leq\frac{9B^{2}H^{8}}{\sigma_{\mathrm{dir}}^{2}}\sum_{t=1}^{T}\mathbb{I}\left[t\in\mathcal{I}\right]\left|\left|\widehat{f}(\mathbf{x}_{t})-f^{\star}(\mathbf{x}_{t})\right|\right|^{2}+4B^{2}R^{2}H^{2}\cdot\frac{T}{E}$
$\displaystyle\leq\frac{9B^{2}H^{8}}{\sigma_{\mathrm{dir}}^{2}}\sum_{t=1}^{T}\left|\left|\mathbf{\widehat{y}}_{t}-f^{\star}(\mathbf{x}_{t})\right|\right|^{2}+4B^{2}R^{2}H^{2}\cdot\frac{T}{E},$

where $\mathbf{\widehat{y}}_{t}$ is the prediction of Algorithm 1. We may now
apply Theorem 16 to bound this last quantity by applying (G.2). The result
follows. ∎

####  G.5 Extensions

For simplicity, we considered a setting where all linear dynamics were stable
with a common Lyapunov function. Our results can be extended to the case where
there are mode-dependent gains $(\mathbf{K}_{i})_{i\in K}$, where
$\mathbf{K}_{i}\in\mathbb{R}^{d_{z}\times d_{u}}$, as well, because our proof
demonstrates that as we achieve low-regret, our simulation accurately recovers
the correct mode sequence. Thus, if we know gains which ensure mutual
stability, we can apply these gains as well. More general closed-loop policies
can also be accomodated, provided we maintain the requisite smoothness (as,
for example, ensured by Lemma 3.1). Lastly, as our regret-guarantees ensure
parameter recovery, we can envision settings where the gains are constructed,
for example, by certainty-equivalent control synthesis, and analyze their
suboptimality via perturbation bounds such as those in Simchowitz and Foster
[2020].