The forgetting on task $m\in\left[{T-1}\right]$ after $n\geq 1$ cycles is
upper bounded by

$\displaystyle\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\boldsymbol{M}^{n}}\right\|^{2}\leq
2m\left\|{\boldsymbol{M}^{n}-\boldsymbol{M}^{n+1}}\right\|~{};$

  5. (Lemma LABEL:enumilem:dimension_independente)

For any number of cycles $n\geq 1$, it holds that
$\left\|{\boldsymbol{M}^{n-1}-\boldsymbol{M}^{n}}\right\|\leq\sqrt{\nicefrac{{T}}{{n}}}$
;

Moreover, when $\boldsymbol{M}$ is _symmetric_ , we have
$\left\|{\boldsymbol{M}^{n-1}-\boldsymbol{M}^{n}}\right\|\leq\nicefrac{{1}}{{e(n-1)}}$
.

######  Lemma C.4 (Rank-dependent upper bound).

For any vector $\boldsymbol{u}\in\mathbb{C}^{d}$ holding
$\left\|{\boldsymbol{u}}\right\|\leq 1$, and for any non-expansive operator
$\boldsymbol{M}\in\mathbb{R}^{d\times d}$, i.e.,
$\left\|\boldsymbol{M}\right\|_{2}\leq 1$, it holds that

$\displaystyle\left\|\boldsymbol{M}^{n}\boldsymbol{u}\right\|_{2}^{2}-\left\|\boldsymbol{M}^{n+1}\boldsymbol{u}\right\|_{2}^{2}~{}\leq~{}\frac{\operatorname{rank}\left(\boldsymbol{M}\right)}{n}~{}\leq~{}\frac{d}{n}~{}.$

######  Proof C.5 (Proof for Theorem 5.5 – upper bound).

First, we remind the reader that the forgetting after $n$ cycles is upper
bounded by

$\displaystyle\frac{1}{T}\left\|\left[\begin{array}[]{c}I-{\boldsymbol{P}}_{1}\\\
\vdots\\\
I-{\boldsymbol{P}}_{T-1}\end{array}\right]\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)^{n}\right\|_{2}^{2}$
$\displaystyle\leq\frac{1}{T}\sum_{m=1}^{T-1}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)^{n}\right\|_{2}^{2}~{}.$
(16)

The dimension-independent bound directly follows from (Lemma
lem:dimension_independentd) and (Lemma lem:dimension_independente):

$\displaystyle\begin{split}\frac{1}{T}\sum_{m=1}^{T-1}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)^{n}\right\|_{2}^{2}&\leq\underbrace{\frac{1}{T}\sum_{m=1}^{T-1}2m}_{=\left({T-1}\right)}\sqrt{\frac{T}{n}}=\left({T-1}\right)\sqrt{\frac{T}{n}}\leq
T\sqrt{\frac{T}{n}}=\frac{T^{2}}{\sqrt{k}}~{}.\end{split}$

##### A symmetric cyclic operator
$\boldsymbol{M}=\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)$.

Consider a symmetric cyclic operator appearing for instance in back-and-forth
settings where $\forall m\in\left[{T}\right]$ we have
$\mathcal{W}_{m}=\mathcal{W}_{T-m}$. Then, (Lemma lem:dimension_independente)
gives a tighter bound, which in turn (assuming $n\geq 2$) yields an overall
bound of

$\frac{1}{T}\sum_{m=1}^{T-1}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)^{n}\right\|_{2}^{2}\leq\frac{T-1}{e(n-1)}\leq\frac{T}{n}=\frac{T^{2}}{k}~{}.$

Finally, since we prove the theorem’s $\nicefrac{{T^{2}}}{{24ek}}$ lower bound
in Appendix C.2.2 using a back-and-forth task collection, i.e., using a
symmetric cyclic operator, we get that in these back-and-forth settings we
have a sharp worst-case behavior of $\Theta(\nicefrac{{T^{2}}}{{k}})$

Finally, we notice that (Lemma lem:dimension_independenta) implies that

$\displaystyle\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\\!\boldsymbol{M}^{n}\right\|_{2}^{2}$
$\displaystyle\triangleq\\!\\!\\!\max_{\boldsymbol{u}:\left\|\boldsymbol{u}\right\|_{2}=1}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\\!\boldsymbol{M}^{n}\boldsymbol{u}\right\|_{2}^{2}\leq
m\cdot\\!\\!\\!\\!\\!\max_{\boldsymbol{u}:\left\|\boldsymbol{u}\right\|_{2}=1}\\!\left(\left\|{\boldsymbol{M}^{n}\boldsymbol{u}}\right\|^{2}-\left\|{\boldsymbol{M}^{n+1}\boldsymbol{u}}\right\|^{2}\right)\\!,$

and by applying Lemma C.4 on
$\boldsymbol{M}\triangleq{\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}$, we
conclude the dimension-dependent bound:

$\displaystyle\begin{split}\frac{1}{T}\sum_{m=1}^{T-1}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)^{n}\right\|_{2}^{2}&\leq\underbrace{\frac{1}{T}\sum_{m=1}^{T-1}m}_{=\left({T-1}\right)/{2}}\frac{\operatorname{rank}\left(\boldsymbol{M}\right)}{n}\leq\frac{T\left(d-r_{\max}\right)}{2n}=\frac{T^{2}\left(d-r_{\max}\right)}{2k}~{},\end{split}$

where we used our notation of
$r_{\max}\triangleq\max_{m\in\left[{T}\right]}\operatorname{rank}\boldsymbol{X}_{m}=\max_{m\in\left[{T}\right]}\left(d-\operatorname{rank}{\boldsymbol{P}}_{m}\right)$
and the fact that $\forall
m\in\left[{T}\right]:\operatorname{rank}\left(\boldsymbol{M}\right)=\operatorname{rank}\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)\leq\min_{m\in\left[{T}\right]}\operatorname{rank}{\boldsymbol{P}}_{m}$.

Before we prove the lemmas above, we state an auxiliary claim (and a
corollary).

######  Claim 2.

For any $m\in\left[{T}\right]$, it holds that

$\displaystyle\begin{split}\boldsymbol{I}&=\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)+\sum_{\ell=1}^{m-1}\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)+{\boldsymbol{P}}_{m}\cdots{\boldsymbol{P}}_{1}~{}.\end{split}$

######  Proof C.6.

Recursively, we show that

$\displaystyle\begin{split}&{\boldsymbol{I}-{\boldsymbol{P}}_{m}\cdots{\boldsymbol{P}}_{1}}\\\
&={\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)+\left({\boldsymbol{P}}_{1}-{\boldsymbol{P}}_{2}{\boldsymbol{P}}_{1}\right)+\left({\boldsymbol{P}}_{2}{\boldsymbol{P}}_{1}-{\boldsymbol{P}}_{3}{\boldsymbol{P}}_{2}{\boldsymbol{P}}_{1}\right)+\dots+\left({\boldsymbol{P}}_{m-1}\cdots{\boldsymbol{P}}_{1}-{\boldsymbol{P}}_{m}\cdots{\boldsymbol{P}}_{1}\right)}\\\
&={\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)+\left(\boldsymbol{I}-{\boldsymbol{P}}_{2}\right){\boldsymbol{P}}_{1}+\left(\boldsymbol{I}-{\boldsymbol{P}}_{3}\right)\left({\boldsymbol{P}}_{2}{\boldsymbol{P}}_{1}\right)+\dots+\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left({\boldsymbol{P}}_{m-1}\cdots{\boldsymbol{P}}_{1}\right)}\\\
&=\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)+\sum_{\ell=1}^{m-1}\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)~{},\end{split}$

which proves our claim.

######  Corollary C.7.

For any $m\in\left[{T}\right]$, it holds that,

$\displaystyle\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)=\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)+\sum_{\ell=1}^{m-1}\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)~{}.$

######  Proof C.8.

We use Claim 2 and get that

$\displaystyle\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)=\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\boldsymbol{I}$
$\displaystyle=\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left[\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)+\sum_{\ell=1}^{m-1}\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)+{\boldsymbol{P}}_{m}\cdots{\boldsymbol{P}}_{1}\right]$
$\displaystyle=\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left[\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)+\sum_{\ell=1}^{m-1}\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)\right]+\underbrace{\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right){\boldsymbol{P}}_{m}}_{=\boldsymbol{0},~{}\text{by
Prop.~{}\ref{prop:projections}}}{\boldsymbol{P}}_{m-1}\cdots{\boldsymbol{P}}_{1}~{}.$

##### Proof for Lemma C.3

. We now prove our dimension-independent upper bounds, step by step, by
proving all the statements of Lemma C.3.

######  Proof C.9 (Proof for (Lemma lem:dimension_independenta)).

For $m=1$, one can show that:

$\displaystyle\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)\boldsymbol{v}\right\|_{2}^{2}\stackrel{{\scriptstyle\text{idempotence}}}{{=}}\left\|\boldsymbol{v}\right\|_{2}^{2}-\left\|{\boldsymbol{P}}_{1}\boldsymbol{v}\right\|_{2}^{2}\stackrel{{\scriptstyle\begin{subarray}{c}\text{projections}\\\
\text{contract}\end{subarray}}}{{\leq}}1\cdot\left(\left\|\boldsymbol{v}\right\|_{2}^{2}-\left\|\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}\right\|_{2}^{2}\right)~{}.$

Then, for $m=2,3,\dots,T-1$, we apply Corollary C.7 and obtain

$\displaystyle\begin{split}&\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\boldsymbol{v}\right\|_{2}^{2}\\\
\left[\begin{subarray}{c}\text{Corollary~{}\ref{cor:vec_property}}\end{subarray}\right]&=\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)\boldsymbol{v}+\sum_{\ell=1}^{m-1}\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\\\
\left[\begin{subarray}{c}\text{Lemma~{}\ref{lem:square_ineq}}\end{subarray}\right]&\leq
m\left(\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}+\sum_{\ell=1}^{m-1}\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)\\\
\left[\begin{subarray}{c}\text{projections}\\\
\text{contract}\end{subarray}\right]&\leq
m\left(\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}+\sum_{\ell=1}^{m-1}\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)\\\
\left[\begin{subarray}{c}\text{idempotence}\end{subarray}\right]&=m\left(\left\|{\boldsymbol{v}}\right\|^{2}-\left\|{{\boldsymbol{P}}_{1}\boldsymbol{v}}\right\|^{2}+\sum_{\ell=1}^{m-1}\left(\left\|{\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}-\left\|{\left({\boldsymbol{P}}_{\ell+1}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)\right)\\\
\left[\begin{subarray}{c}\text{telescoping}\end{subarray}\right]&=m\left(\left\|{\boldsymbol{v}}\right\|^{2}-\left\|{\left({\boldsymbol{P}}_{m}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)\leq
m\left(\left\|{\boldsymbol{v}}\right\|^{2}-\left\|{\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)~{},\end{split}$

which completes our proof.

##### Remark.

We note in passing that this dependence on $m$ can be further improved. Using
similar techniques, one can also prove that
$\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\boldsymbol{M}\boldsymbol{v}\right\|_{2}^{2}\leq\big{(}{T-m}\big{)}\left(\left\|{\boldsymbol{v}}\right\|^{2}-\left\|{\boldsymbol{M}\boldsymbol{v}}\right\|^{2}\right)$.
This in turn can help tighten the upper bound in Theorem 5.5 by a
multiplicative factor of $2$, but yields a slightly less elegant expression.

######  Proof C.10 (Proof for (Lemma lem:dimension_independentb)).

Notice that Claim 2 (with $m=T$) implies that

$\displaystyle\begin{split}\boldsymbol{I}-{\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}&=\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)+\sum_{\ell=1}^{T-1}\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)~{}.\end{split}$

Then, we prove our lemma:

$\displaystyle\begin{split}\left\|{\boldsymbol{v}-{\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\boldsymbol{v}}\right\|^{2}&=\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)\boldsymbol{v}+\sum_{\ell=1}^{T-1}\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\\\
\left[\begin{subarray}{c}\text{Lemma~{}\ref{lem:square_ineq}}\end{subarray}\right]&\leq
T\left(\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}+\sum_{\ell=1}^{T-1}\left\|{\left(\boldsymbol{I}-{\boldsymbol{P}}_{\ell+1}\right)\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)\\\
\left[\begin{subarray}{c}\text{idempotence}\end{subarray}\right]&=T\left(\left\|{\boldsymbol{v}}\right\|^{2}-\left\|{{\boldsymbol{P}}_{1}\boldsymbol{v}}\right\|^{2}+\sum_{\ell=1}^{T-1}\left(\left\|{\left({\boldsymbol{P}}_{\ell}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}-\left\|{\left({\boldsymbol{P}}_{\ell+1}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)\right)\\\
\left[\begin{subarray}{c}\text{telescoping}\end{subarray}\right]&=T\left(\left\|{\boldsymbol{v}}\right\|^{2}-\left\|{\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)~{}.\end{split}$

##### Remark.

We note in passing that after completing our proof above, we found that a
similar proof was already presented in Netyanun and Solmon (2006) while
discussing Kakutani’s lemma. We still brought our proof here for the sake of
completeness. Moreover, they showed that for a non-expansive _self-adjoint
positive semi-definite_ operator $\boldsymbol{M}$, the factor $T$ can be
alleviated from the inequality. That is,
$\left\|{\boldsymbol{v}-{\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\boldsymbol{v}}\right\|^{2}\leq\cancel{T}\left(\left\|{\boldsymbol{v}}\right\|^{2}-\left\|{\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)\boldsymbol{v}}\right\|^{2}\right)$.
But clearly this does not suit our general cyclic operators which are not
necessarily self-adjoint. Indeed, our proof for (Lemma
lem:dimension_independente) yields a similar conclusion for _symmetric_ cyclic
operators.

######  Proof C.11 (Proof for (Lemma lem:dimension_independentc)).

Let $\boldsymbol{u}\in\mathbb{C}^{d}$. First, we notice that since
$\boldsymbol{M}$ is a non-expansive operator, we have that
$\left\|\boldsymbol{M}^{n}\boldsymbol{u}\right\|_{2}^{2}\geq\left\|\boldsymbol{M}^{n+1}\boldsymbol{u}\right\|_{2}^{2}$.
In turn, this means

$\displaystyle
0\leq\left\|\boldsymbol{M}^{n}\boldsymbol{u}\right\|_{2}^{2}-\left\|\boldsymbol{M}^{n+1}\boldsymbol{u}\right\|_{2}^{2}=\boldsymbol{u}^{*}\Big{(}{\underbrace{\left(\boldsymbol{M}^{n}\right)^{*}\boldsymbol{M}^{n}-\left(\boldsymbol{M}^{n+1}\right)^{*}\boldsymbol{M}^{n+1}}_{\succeq{\boldsymbol{0}}~{}\text{because
it is clearly symmetric as well}}}\Big{)}\boldsymbol{u}~{}.$

Then, we use the fact that for any positive semi-definite matrix
$\boldsymbol{A}\succeq\boldsymbol{0}$, we have that
$\boldsymbol{u}^{*}\boldsymbol{A}\boldsymbol{u}\leq\lambda_{1}\left(\boldsymbol{A}\right)=\left\|{\boldsymbol{A}}\right\|$,
and get

$\displaystyle\left\|\boldsymbol{M}^{n}\boldsymbol{u}\right\|_{2}^{2}-\left\|\boldsymbol{M}^{n+1}\boldsymbol{u}\right\|_{2}^{2}$
$\displaystyle\leq\left\|{\left(\boldsymbol{M}^{n}\right)^{*}\boldsymbol{M}^{n}-\left(\boldsymbol{M}^{n+1}\right)^{*}\boldsymbol{M}^{n+1}}\right\|$
$\displaystyle\left[\begin{subarray}{c}\boldsymbol{A}^{*}\boldsymbol{A}-\boldsymbol{B}^{*}\boldsymbol{B}=\left({\boldsymbol{A}^{*}-\boldsymbol{B}^{*}}\right)\boldsymbol{A}+\boldsymbol{B}^{*}\left({\boldsymbol{A}-\boldsymbol{B}}\right)\end{subarray}\right]$
$\displaystyle=\left\|{\left(\boldsymbol{M}^{n}\right)^{*}\left({\boldsymbol{M}^{n}-\boldsymbol{M}^{n+1}}\right)+\left({\left(\boldsymbol{M}^{n}\right)^{*}-\left(\boldsymbol{M}^{n+1}\right)^{*}}\right)\boldsymbol{M}^{n}}\right\|$
$\displaystyle\left[\begin{subarray}{c}\text{triangle
inequality}\end{subarray}\right]$
$\displaystyle\leq\left\|{\left(\boldsymbol{M}^{n}\right)^{*}\left({\boldsymbol{M}^{n}-\boldsymbol{M}^{n+1}}\right)}\right\|+\left\|{\left({\left(\boldsymbol{M}^{n}\right)^{*}-\left(\boldsymbol{M}^{n+1}\right)^{*}}\right)\boldsymbol{M}^{n}}\right\|$
$\displaystyle\left[\begin{subarray}{c}~{}\left\|{\boldsymbol{A}^{*}}\right\|=\left\|{\boldsymbol{A}}\right\|~{}\end{subarray}\right]$
$\displaystyle\leq
2\left\|{\left(\boldsymbol{M}^{n}\right)^{*}\left({\boldsymbol{M}^{n}-\boldsymbol{M}^{n+1}}\right)}\right\|$
$\displaystyle\left[\begin{subarray}{c}\text{contraction}\end{subarray}\right]$
$\displaystyle\leq
2\left\|{\boldsymbol{M}^{n}-\boldsymbol{M}^{n+1}}\right\|~{}.$

######  Proof C.12 (Proof for (Lemma lem:dimension_independentd)).

This lemma is a direct corollary of (Lemma lem:dimension_independenta) and
(Lemma lem:dimension_independentc).

First, we set $\boldsymbol{v}=\boldsymbol{M}^{n}\boldsymbol{u}$ and apply
(Lemma lem:dimension_independenta):

$\displaystyle\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\boldsymbol{M}^{n}\right\|^{2}=\max_{\boldsymbol{u}:\left\|\boldsymbol{u}\right\|_{2}=1}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\boldsymbol{M}^{n}\boldsymbol{u}\right\|^{2}\leq
m\cdot\\!\\!\max_{\boldsymbol{u}:\left\|\boldsymbol{u}\right\|_{2}=1}\left({\left\|\boldsymbol{M}^{n}\boldsymbol{u}\right\|_{2}^{2}-\left\|\boldsymbol{M}^{n+1}\boldsymbol{u}\right\|_{2}^{2}}\right)~{}.$

Then, we apply (Lemma lem:dimension_independentc) to get:

$\displaystyle\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right)\boldsymbol{M}^{n}\right\|^{2}\leq
m\cdot\\!\\!\max_{\boldsymbol{u}:\left\|\boldsymbol{u}\right\|_{2}=1}\left({\left\|\boldsymbol{M}^{n}\boldsymbol{u}\right\|_{2}^{2}-\left\|\boldsymbol{M}^{n+1}\boldsymbol{u}\right\|_{2}^{2}}\right)\leq
2m\left\|{\boldsymbol{M}^{n}-\boldsymbol{M}^{n+1}}\right\|~{}.$

######  Proof C.13 (Proof for (Lemma lem:dimension_independente)).

We use (Lemma lem:dimension_independentb) to show that

$\displaystyle\begin{split}\sum_{t=0}^{n-1}\left\|{\left(\boldsymbol{M}^{t}-\boldsymbol{M}^{t+1}\right)\boldsymbol{v}}\right\|^{2}=\sum_{t=0}^{n-1}\left\|{\left(\boldsymbol{I}-\boldsymbol{M}\right)\boldsymbol{M}^{t}\boldsymbol{v}}\right\|^{2}&\leq
T\sum_{t=0}^{n-1}\left(\left\|{\boldsymbol{M}^{t}\boldsymbol{v}}\right\|^{2}-\left\|{\boldsymbol{M}^{t+1}\boldsymbol{v}}\right\|^{2}\right)\\\
\left[\begin{subarray}{c}\text{telescoping}\end{subarray}\right]&=T\left(\left\|{\boldsymbol{v}}\right\|^{2}-\left\|{\boldsymbol{M}^{n}\boldsymbol{v}}\right\|^{2}\right)\leq
T\left\|{\boldsymbol{v}}\right\|^{2}~{}.\end{split}$

Since
$\left\|{\left(\boldsymbol{M}^{t}-\boldsymbol{M}^{t+1}\right)\boldsymbol{v}}\right\|^{2}=\left\|{\boldsymbol{M}\left(\left(\boldsymbol{M}^{t-1}-\boldsymbol{M}^{t}\right)\boldsymbol{v}\right)}\right\|^{2}$
and since the cyclic operator $\boldsymbol{M}$ is a contraction operator, we
get that the series
$\left\\{\left\|{\left(\boldsymbol{M}^{t}-\boldsymbol{M}^{t+1}\right)\boldsymbol{v}}\right\|^{2}\right\\}_{t}$
is monotonic non-increasing. This in turn means that

$\displaystyle\forall{\boldsymbol{v}\in\mathbb{C}^{d}}:\left\|{\left(\boldsymbol{M}^{n-1}-\boldsymbol{M}^{n}\right)\boldsymbol{v}}\right\|^{2}$
$\displaystyle=\\!\\!\min_{t=0,\dots,n-1}\left\|{\left(\boldsymbol{M}^{t}-\boldsymbol{M}^{t+1}\right)\boldsymbol{v}}\right\|^{2}$
$\displaystyle\leq\frac{1}{n}\sum_{t=0}^{n-1}\left\|{\left(\boldsymbol{M}^{t}-\boldsymbol{M}^{t+1}\right)\boldsymbol{v}}\right\|^{2}\leq\frac{T}{n}\left\|{\boldsymbol{v}}\right\|^{2}~{},$

which finally implies that
$\left\|{\boldsymbol{M}^{n-1}-\boldsymbol{M}^{n}}\right\|^{2}\leq\nicefrac{{T}}{{n}}$
as required.

##### A symmetric cyclic operator
$\boldsymbol{M}=\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)$.

When $\boldsymbol{M}$ is Hermitian matrix, its spectral decomposition
$\boldsymbol{M}=\boldsymbol{Q}{\boldsymbol{\Lambda}}\boldsymbol{Q}^{*}$
reveals a tighter bound:

$\displaystyle\left\|{\boldsymbol{M}^{n-1}\\!-\\!\boldsymbol{M}^{n}}\right\|=\left\|{\boldsymbol{Q}({\boldsymbol{\Lambda}}^{n-1}\\!-\\!{\boldsymbol{\Lambda}}^{n})\boldsymbol{Q}^{*}}\right\|=\left\|{{\boldsymbol{\Lambda}}^{n-1}\\!-\\!{\boldsymbol{\Lambda}}^{n}}\right\|=\max_{i}\left({\lambda_{i}^{n-1}\left({1\\!-\\!\lambda_{i}}\right)}\right)\leq\frac{1}{e(n-1)}\,.$

######  Proof C.14 (Proof for Lemma C.4).

We follow a proof by fedja (https://mathoverflow.net/users/1131/fedja).

Define the series of matrices $\left\\{\boldsymbol{B}_{n}\right\\}$, where
$\boldsymbol{B}_{n}=\boldsymbol{M}^{n^{\top}}\boldsymbol{M}^{n}-\boldsymbol{M}^{n+1^{\top}}\boldsymbol{M}^{n+1}$.
Notice that it holds that $\boldsymbol{B}_{n}\succeq 0$ (since it is symmetric
and
$\forall\boldsymbol{v}:\boldsymbol{v}^{*}\boldsymbol{B}_{n}\boldsymbol{v}=\left\|\boldsymbol{M}^{n}\boldsymbol{v}\right\|_{2}^{2}-\left\|\boldsymbol{M}^{n+1}\boldsymbol{v}\right\|_{2}^{2}\geq
0$).

Furthermore, Von Neumann’s trace inequality and the fact that $\boldsymbol{M}$
is a contraction operator, imply that

$\displaystyle\operatorname{tr}\left(\boldsymbol{B}_{n+1}\right)=\operatorname{tr}\big{(}{\boldsymbol{M}^{\top}\boldsymbol{B}_{n}\boldsymbol{M}}\big{)}=\operatorname{tr}\big{(}{\underbrace{\boldsymbol{M}\boldsymbol{M}^{\top}}_{\succeq
0}\underbrace{\boldsymbol{B}_{n}}_{\succeq
0}}\big{)}\leq\big{\|}{\boldsymbol{M}\boldsymbol{M}^{\top}}\big{\|}_{2}\operatorname{tr}\left(\boldsymbol{B}_{n}\right)\leq\operatorname{tr}\left(\boldsymbol{B}_{n}\right)~{},$

meaning that the sequence
$\left\\{\operatorname{tr}\left(\boldsymbol{B}_{n}\right)\right\\}_{n}$ is
monotonically non-increasing. Hence, we get that

$\displaystyle\begin{split}n\operatorname{tr}\left(\boldsymbol{B}_{n}\right)&\leq\sum_{\ell=1}^{n}\operatorname{tr}\left(\boldsymbol{B}_{\ell}\right)=\sum_{\ell=1}^{n}\operatorname{tr}\left(\boldsymbol{M}^{\ell^{\top}}\boldsymbol{M}^{\ell}-\boldsymbol{M}^{\ell+1^{\top}}\boldsymbol{M}^{\ell+1}\right)\\\
&=\sum_{\ell=1}^{n}\left(\operatorname{tr}\left(\boldsymbol{M}^{\ell^{\top}}\boldsymbol{M}^{\ell}\right)-\operatorname{tr}\left(\boldsymbol{M}^{\ell+1^{\top}}\boldsymbol{M}^{\ell+1}\right)\right)\\\
\left[\begin{subarray}{c}\text{telescoping}\end{subarray}\right]&=\operatorname{tr}\left(\boldsymbol{M}^{{}^{\top}}\boldsymbol{M}\right)-\underbrace{\operatorname{tr}\left(\boldsymbol{M}^{n+1^{\top}}\boldsymbol{M}^{n+1}\right)}_{\geq
0}\leq\operatorname{tr}\left(\boldsymbol{M}^{{}^{\top}}\boldsymbol{M}\right)\stackrel{{\scriptstyle\text{contraction}}}{{\leq}}\operatorname{rank}{\left(\boldsymbol{M}\right)}\\\
\Longrightarrow\operatorname{tr}\left(\boldsymbol{B}_{n}\right)&\leq\frac{\operatorname{rank}{\left(\boldsymbol{M}\right)}}{n}~{}.\end{split}$

We are now ready to conclude this lemma,

$\displaystyle\begin{split}\max_{\boldsymbol{v}:\left\|\boldsymbol{v}\right\|_{2}=1}\left(\left\|\boldsymbol{M}^{n}\boldsymbol{v}\right\|_{2}^{2}-\left\|\boldsymbol{M}^{n+1}\boldsymbol{v}\right\|_{2}^{2}\right)&=\max_{\boldsymbol{v}:\left\|\boldsymbol{v}\right\|_{2}=1}\boldsymbol{v}^{*}\left(\boldsymbol{M}^{n^{\top}}\boldsymbol{M}^{n}-\boldsymbol{M}^{n+1^{\top}}\boldsymbol{M}^{n+1}\right)\boldsymbol{v}\\\
&=\max_{\boldsymbol{v}:\left\|\boldsymbol{v}\right\|_{2}=1}\boldsymbol{v}^{*}\underbrace{\boldsymbol{B}_{n}}_{\succeq
0}\boldsymbol{v}=\underbrace{\lambda_{1}\left(\boldsymbol{B}_{n}\right)}_{\in\mathbb{R}_{+}}\leq\operatorname{tr}\left(\boldsymbol{B}_{n}\right)\leq\frac{\operatorname{rank}{\left(\boldsymbol{M}\right)}}{n}~{}.\end{split}$

##### Remarks.

For the sake of completeness, we briefly discuss our result above. First, this
result is useful for our derivations since our cyclic operator
$\left({\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}\right)$ is essentially a
contraction operator. In fact, being a product of projections, our cyclic
operator has great expressiveness. It was shown by Oikhberg (1999) that _any_
contraction operator can be decomposed into a product of sufficiently, though
sometimes infinitely, many projections. This explains our interest in
analyzing “general” contraction operators.

Finally, we should mention that the bound derived here is sharp (up to a
constant). For instance, for the Toeplitz operator
$\boldsymbol{M}=\left[\begin{smallmatrix}&1\\\ &&\ddots\\\ &&&1\\\
1-\epsilon\end{smallmatrix}\right]$, a proper choice of $\epsilon$ can yield a
rate of $\nicefrac{{d}}{{en}}$ for the quantity we bound in the lemma above.
However, such an operator cannot be expressed as a product of a _finite_
number of projection operators. One can approximate this operator arbitrarily-
well by replacing the $1$s with $\beta\in\left({0,1}\right)$. However, we were
not able to use this approximation to improve our lower bound in Theorem 5.5,
since $\beta<1$ implies a geometric contraction of _all_ elements at every
cycle and requires a very large number of constructing projections (i.e.,
tasks).

####  C.2.2 Proving the lower bound

######  Proof C.15 (Proof for Theorem 5.5 – lower bound).

To prove the lower bound, we show a construction of a task collection
$S\in\mathcal{S}_{T}$ with $T$ tasks whose forgetting is

$\displaystyle\frac{T^{2}}{24ek}\leq F_{\tau,S}(k)~{}.$

Figure 6: Construction of $T=6$ ”back-and-forth” tasks for the lower bound
proof in Theorem 5.5.

We construct $S$ using data matrices of rank $r=d-1$ whose non-zero singular
values all equal to $1$. Let $\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{T}$ be
the normalized vectors spanning the $T$ rank-_one_ solution spaces
$\mathcal{W}_{1},\dots,\mathcal{W}_{T}$. We also choose to generate labels
using a _unit norm_ offline solution, i.e.,
$\left\|{\boldsymbol{w}^{\star}}\right\|=1$. We spread
$\boldsymbol{v}_{1},\dots,\boldsymbol{v}_{T}$ on a 2-dimensional hyperplane
such that the tasks ”go” back-and-forth, i.e., switch direction at the middle
task (see illustration in Figure 6).

Using Lemma A.8 we have

$\displaystyle
F_{\tau,S}\left(k\right)\geq\frac{1}{k}\left(\prod_{i=1}^{k-1}\cos^{2}\theta_{\tau\left(i,i+1\right)}\right)\sum_{m=1}^{k-1}\left(1-\cos^{2}\theta_{\tau\left(m,k\right)}\right)$
$\displaystyle=\frac{1}{k}\\!\left(\prod_{i=1}^{k-1}\cos^{2}\theta_{\tau\left(i,i+1\right)}\right)\frac{k}{T}\sum_{m=1}^{T}\left(1\\!-\\!\cos^{2}\theta_{m,T}\right)\\!=\\!\frac{1}{T}\\!\left(\prod_{i=1}^{k-1}\cos^{2}\theta_{\tau\left(i,i+1\right)}\\!\right)^{\\!k-1}\\!\\!\\!\sum_{m=1}^{T}\\!\left(1\\!-\\!\cos^{2}\theta_{m,T}\right).$

We consider separately the case of even $T$ and the case of odd $T$.

##### Even $T$:

In this case, we set $\forall
i\in\left[T-1\right]:\,\,\theta_{i,i+1}=\begin{cases}\theta&i<\frac{T}{2}\\\
-\theta&i\geq\frac{T}{2}\end{cases}~{}$, thus obtaining

$\frac{1}{T}\\!\left(\prod_{i=1}^{k-1}\cos^{2}\theta_{\tau\left(i,i+1\right)}\right)^{k-1}\\!\\!\\!\sum_{m=1}^{T}\left(1\\!-\\!\cos^{2}\theta_{m,T}\right)=\frac{1}{T}\\!\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\\!\left(1\\!-\\!\cos^{2}\left(\left(\frac{T}{2}\\!-\\!m\right)\theta\right)\right)~{}.$

We choose $\theta=\sqrt{\nicefrac{{1}}{{k-1}}}$ and get

$\displaystyle\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\left(\left(\frac{T}{2}-m\right)\theta\right)\right)$
$\displaystyle=\frac{1}{T}\left(\cos^{2}\sqrt{\frac{1}{k-1}}\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\left(\left(\frac{T}{2}-m\right)\sqrt{\frac{1}{k-1}}\right)\right).$

Next, using the inequality $1-\cos^{2}x\geq x^{2}-\frac{1}{3}x^{4}$, we get

$\displaystyle\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\left(\left(\frac{T}{2}-m\right)\theta\right)\right)$
$\displaystyle\geq\frac{1}{T}\left(\cos^{2}\sqrt{\frac{1}{k-1}}\right)^{k-1}\sum_{m=1}^{T}\left(\left(\frac{T}{2}-m\right)^{2}\frac{1}{k-1}-\frac{1}{3}\left(\frac{T}{2}-m\right)^{4}\frac{1}{\left(k-1\right)^{2}}\right)$
$\displaystyle\geq\frac{1}{T}\frac{1}{k-1}\left(\cos^{2}\sqrt{\frac{1}{k-1}}\right)^{k-1}\sum_{m=1}^{T}\left(\left(\frac{T}{2}-m\right)^{2}-\left(\frac{T}{2}-m\right)^{4}\frac{1}{3\left(k-1\right)}\right)~{}.$

By using $\forall x\geq
1:\frac{1}{x}\left(\cos^{2}\sqrt{\nicefrac{{1}}{{x}}}\right)^{x}\geq\nicefrac{{1}}{{e\left(x+1\right)}}$
we get

$\displaystyle\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\left(\left(\frac{T}{2}-m\right)\theta\right)\right)$
$\displaystyle\geq\frac{1}{Tek}\sum_{m=1}^{T}\left(\left(\frac{T}{2}-m\right)^{2}-\left(\frac{T}{2}-m\right)^{4}\frac{1}{3\left(k-1\right)}\right)$
$\displaystyle=\frac{1}{Tek}\left(\frac{1}{12}T\left(T^{2}+2\right)-\frac{T\left(3T^{4}+20T^{2}-8\right)}{240\cdot
3(k-1)}\right)=\frac{1}{12ek}\left(T^{2}+2-\frac{3T^{4}+20T^{2}-8}{60\left(k-1\right)}\right)~{}.$

For $k\geq T^{2}$ we get

$\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\left(\left(\frac{T}{2}-m\right)\theta\right)\right)\geq\frac{1}{12ek}\left(T^{2}+2-\frac{3T^{4}+20T^{2}-8}{60\left(T^{2}-1\right)}\right)~{}.$
(17)

Note that for $T\geq 4$ we have
$\frac{1}{12ek}\left(T^{2}+2-\frac{3T^{4}+20T^{2}-8}{60\left(T^{2}-1\right)}\right)\geq\frac{T^{2}}{13ek}$.

Therefore for even $T\geq 4$ we have

$F_{\tau,S}\left(k\right)\geq\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\left(\left(\frac{T}{2}-m\right)\theta\right)\right)\geq\frac{T^{2}}{13ek}~{}.$

##### Odd $T$:

In this case we set $\forall
i\in\left[T-1\right]:\,\,\theta_{i,i+1}=\begin{cases}\theta&i<\frac{T-1}{2}\\\
-\frac{\theta}{2}&i=\frac{T-1}{2}\,\,\textrm{or}\,\,i=\frac{T+1}{2}\\\
-\theta&i>\frac{T+1}{2}\end{cases}~{}$, and since
$\cos\left(\nicefrac{{\theta}}{{2}}\right)\geq\cos\left(\theta\right)$ (for
small $\theta$, as we choose later) we have

$\frac{1}{T}\left(\prod_{i=1}^{k-1}\cos^{2}\theta_{\tau\left(i,i+1\right)}\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\theta_{m,T}\right)\geq\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\theta_{m,T}\right)~{}.$

Next,

$\sum_{m=1}^{T}\left(1-\cos^{2}\theta_{m,T}\right)=1-\cos^{2}\left(\left(\frac{T-2}{2}\right)\theta\right)+\sum_{m=1}^{T-1}\left(1-\cos^{2}\left(\left(\frac{T-1}{2}-m\right)\theta\right)\right)~{}.$

Therefore we get

$\displaystyle\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\theta_{m,T}\right)$
$\displaystyle=$
$\displaystyle\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\left(1-\cos^{2}\left(\left(\frac{T-2}{2}\right)\theta\right)\right)$
$\displaystyle+\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T-1}\left(1-\cos^{2}\left(\left(\frac{T-1}{2}-m\right)\theta\right)\right)$
$\displaystyle=$
$\displaystyle\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\left(1-\cos^{2}\left(\left(\frac{T-2}{2}\right)\theta\right)\right)$
$\displaystyle+\frac{T-1}{T}\frac{1}{T-1}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T-1}\left(1-\cos^{2}\left(\left(\frac{T-1}{2}-m\right)\theta\right)\right)~{}.$
(18)

We choose again $\theta=\sqrt{\nicefrac{{1}}{{k-1}}}$. For the first term in
Eq. (18) we have

$\displaystyle\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\left(1-\cos^{2}\left(\left(\frac{T-2}{2}\right)\theta\right)\right)$
$\displaystyle=\frac{1}{T}\left(\cos^{2}\sqrt{\frac{1}{k-1}}\right)^{k-1}\left(1-\cos^{2}\left(\left(\frac{T-2}{2}\right)\sqrt{\frac{1}{k-1}}\right)\right)$
$\displaystyle\geq\frac{1}{T}\left(\cos^{2}\sqrt{\frac{1}{k-1}}\right)^{k-1}\left(1-\cos^{2}\left(\frac{1}{2}\sqrt{\frac{1}{k-1}}\right)\right)\geq\frac{1}{4Tek}~{}.$

For the second term in Eq. (18) we use Eq. (17) and get

$\displaystyle\frac{T-1}{T}\frac{1}{T-1}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T-1}\left(1-\cos^{2}\left(\left(\frac{T-1}{2}-m\right)\theta\right)\right)$
$\displaystyle\geq\frac{T-1}{T}\frac{1}{12ek}\left(\left(T-1\right)^{2}+2-\frac{3\left(T-1\right)^{4}+20\left(T-1\right)^{2}-8}{60\left(\left(T-1\right)^{2}-1\right)}\right)~{}.$

Therefore in Eq. (18) we have

$\displaystyle\frac{1}{T}\left(\cos^{2}\theta\right)^{k-1}\sum_{m=1}^{T}\left(1-\cos^{2}\theta_{m,T}\right)$
$\displaystyle\geq\frac{1}{4Tek}+\frac{T-1}{T}\frac{1}{12ek}\left(\left(T-1\right)^{2}+2-\frac{3\left(T-1\right)^{4}+20\left(T-1\right)^{2}-8}{60\left(\left(T-1\right)^{2}-1\right)}\right)$
$\displaystyle=\frac{1}{ek}\left(\frac{1}{4T}+\frac{T-1}{12T}\left(\left(T-1\right)^{2}+2-\frac{3\left(T-1\right)^{4}+20\left(T-1\right)^{2}-8}{60\left(\left(T-1\right)^{2}-1\right)}\right)\right)$
$\displaystyle\left[T\geq 3\right]$ $\displaystyle\geq\frac{T^{2}}{24ek}~{},$

and thus for odd $T\geq 3$ we have
$F_{\tau,S}\left(k\right)\geq\nicefrac{{T^{2}}}{{24ek}}$, which concludes the
proof.

##### Regarding the rank.

Notice that the lower bound we derived used a construction consisting of tasks
of rank $d-1$. On the other hand, the lower bound in Theorem 5.5 should be
correct even when $r_{\max}<d-1$. In such a case, we can always use an
identical task collection using $T$ tasks spread on a $2$-d hyperplane, and
add to the tasks’ data matrices any number of directions which are orthogonal
to that hyperplane, but appear identically on _all_ tasks. Then, any
expression of the form
$\left\|{\big{(}{\boldsymbol{I}-{\boldsymbol{P}}_{m}}\big{)}\big{(}{{\boldsymbol{P}}_{T}\cdots{\boldsymbol{P}}_{1}}\big{)}^{n}}\right\|$
will disregard these added directions, since they are shared across all tasks
(hence they do not appear in $\boldsymbol{I}\\!-\\!{\boldsymbol{P}}_{m}$). The
remaining hyperplane’s behavior will remain unchanged as in the analysis
above. Thus our analysis above is valid for any task rank.

##  Appendix D Supplementary material: Random task orderings (Section 6)

  * Recall Theorem 6.2.Under the uniform i.i.d. task ordering $\tau$, the worst-case expected forgetting after $k$ iterations is

$\displaystyle\sup_{\begin{subarray}{c}S\in\mathcal{S}_{T}:\\\
\tfrac{1}{T}{\sum}_{m=1}^{T}\operatorname{rank}(\boldsymbol{X}_{m})=r_{\operatorname{avg}}\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\bar{F}_{\tau,S}\left(k\right)\leq\frac{9\left(d-r_{\operatorname{avg}}\right)}{k}~{}.$

######  Proof D.1 (Proof for Theorem 6.2).

Let $S=\left\\{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{T}\right\\}$ be a
given collection of $T$ arbitrary projection matrices sampled i.i.d. at each
iteration from a uniform distribution.

As in Eq. (8), we first express the expected forgetting on a task collection
$S\in\mathcal{S}_{T}$, defined in Definition 6.1, in terms of the projection
matrices induced by the $T$ data matrices in $S$. That is, we bound the
expected forgetting by

$\displaystyle\bar{F}_{\tau,S}\left(k\right)\\!\triangleq\mathop{\mathbb{E}}_{\tau}\\!\bigg{[}\frac{1}{k}\sum_{t=1}^{k}\\!\Big{\|}{\boldsymbol{X}_{\tau(t)}\boldsymbol{w}_{k}-\boldsymbol{y}_{\tau(t)}}\Big{\|}^{2}\bigg{]}\\!\leq\mathop{\mathbb{E}}_{\tau}\bigg{[}\frac{1}{k}\sum_{t=1}^{k}\\!\Big{\|}{\left(\boldsymbol{I}-{\boldsymbol{P}}_{\tau(t)}\right){{\boldsymbol{P}}_{\tau\left(k\right)}\cdots{\boldsymbol{P}}_{\tau\left(1\right)}}}\Big{\|}^{2}\bigg{]}~{}.$
(19)

###  D.1 Detour: Rephrasing and bounding a more natural expression

####  D.1.1 Rephrasing

Before we will bound the upper bound above, we start by bounding a slightly
different quantity which is easier to work with and can be seen as a
straightforward MSE loss over $T$ tasks (as studied in NLMS papers, e.g.,
Slock (1993); Sankaran and Beex (2000)). Instead of averaging the forgetting
(i.e., residuals) over _previously-seen_ tasks, we average over _all_ tasks in
the collection $S$. That is, we start by bounding.

$\displaystyle\mathop{\mathbb{E}}_{\tau}\bigg{[}\frac{1}{T}\sum_{m=1}^{T}\\!\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right){\boldsymbol{P}}_{\tau\left(k\right)}\cdots{\boldsymbol{P}}_{\tau\left(1\right)}\right\|_{2}^{2}\bigg{]}=\mathop{\mathbb{E}}_{\tau,{\boldsymbol{P}}}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{\tau\left(k\right)}\cdots{\boldsymbol{P}}_{\tau\left(1\right)}\right\|_{2}^{2}~{},$
(20)

where $\mathbb{E}_{{\boldsymbol{P}}}$ means averaging over all $T$ projection
matrices w.r.t. a uniform distribution.

To further ease reading, we slightly abuse notation such that instead of
explicitly sampling a task ordering $\tau$, we simply uniformly sample $k+1$
orthogonal projection operators,
${\boldsymbol{P}}_{1},{\boldsymbol{P}}_{2},\dots,{\boldsymbol{P}}_{k}$ and
${\boldsymbol{P}}$ from some i.i.d. uniform distribution (e.g., uniformly from
a finite set of $T$ such operators). Finally, we obtain the following
expression:

$\displaystyle\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{1}\right\|_{2}^{2}~{}.$
(21)

Next, we will bound Eq. (21) which is equivalent to Eq. (20). Then, we will
use Eq. (20) to bound the right hand side of Eq. (19) and conclude an upper
bound for the expected forgetting, as required.

####  D.1.2 Bounding Eq. (21)

We begin by using a known inequality between the spectral norm and the
Frobenius norm, that is,
${\left\|\boldsymbol{A}\right\|_{2}^{2}\\!=\\!\lambda_{1}\left(\boldsymbol{A}^{*}\boldsymbol{A}\right)\leq\operatorname{tr}\left(\boldsymbol{A}^{*}\boldsymbol{A}\right)\\!=\left\|\boldsymbol{A}\right\|_{F}^{2}}$,
and present an easier, but perhaps looser, surrogate quantity $f(k)$ which we
will bound:

$\displaystyle\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{1}\right\|_{2}^{2}\leq\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}_{k}\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{1}\right]\triangleq
f\\!\left(k\right)~{}.$ (22)

Key to our following derivations, is the fact that all the projection matrices
including ${\boldsymbol{P}}$ are identically distributed, allowing us to
freely change variables. This property, together with the linearity of the
expectation and trace operators, facilitates our derivations.

We now notice that the bound we got is _non-increasing_ in $k$, i.e.,

$\displaystyle f\\!\left(k-1\right)-f\\!\left(k\right)=$
$\displaystyle\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k-1},{\boldsymbol{P}}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}_{k-1}\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{k-1}\cdots{\boldsymbol{P}}_{1}\right]-$
$\displaystyle\hskip
0.0pt\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}_{k}\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{1}\right]$
$\displaystyle\left[\begin{subarray}{c}\text{identically}\\\
\text{distributed}\end{subarray}\right]=$
$\displaystyle\\!\\!\\!\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{2},\dots,{\boldsymbol{P}}_{k+1}}\operatorname{tr}\left[{\boldsymbol{P}}_{2}\cdots{\boldsymbol{P}}_{k}\left(\boldsymbol{I}-{\boldsymbol{P}}_{k+1}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{2}\right]-$
$\displaystyle\hskip
0.0pt\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k+1}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}_{k}\left(\boldsymbol{I}-{\boldsymbol{P}}_{k+1}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{1}\right]$
$\displaystyle\left[\text{linearity}\right]=$
$\displaystyle\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k+1}}\Bigg{[}\operatorname{tr}\bigg{[}\underbrace{{\boldsymbol{P}}_{2}\cdots{\boldsymbol{P}}_{k}\left(\boldsymbol{I}-{\boldsymbol{P}}_{k+1}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{2}}_{\triangleq\boldsymbol{M}}\bigg{]}-$
$\displaystyle\hskip
55.48277pt\operatorname{tr}\bigg{[}{\boldsymbol{P}}_{1}\underbrace{{\boldsymbol{P}}_{2}\cdots{\boldsymbol{P}}_{k}\left(\boldsymbol{I}-{\boldsymbol{P}}_{k+1}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{2}}_{\triangleq\boldsymbol{M}}{\boldsymbol{P}}_{1}\bigg{]}\Bigg{]}$
$\displaystyle=\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\bigg{[}\underbrace{\operatorname{tr}\left[\boldsymbol{M}\right]-\operatorname{tr}\left[{\boldsymbol{P}}_{1}\boldsymbol{M}{\boldsymbol{P}}_{1}\right]}_{\geq
0}\bigg{]}\geq 0~{},$

where in the last inequality we (again) used Von Neumann’s trace inequality to
show that

$\operatorname{tr}\left({\boldsymbol{P}}_{1}\boldsymbol{M}{\boldsymbol{P}}_{1}\right)=\operatorname{tr}\left({\boldsymbol{P}}_{1}{\boldsymbol{P}}_{1}\boldsymbol{M}\right)=\operatorname{tr}\big{(}{\underbrace{{\boldsymbol{P}}_{1}}_{\succeq
0}\underbrace{\boldsymbol{M}}_{\succeq
0}}\big{)}\leq\big{\|}{{\boldsymbol{P}}_{1}}\big{\|}_{2}\operatorname{tr}\left(\boldsymbol{M}\right)=\operatorname{tr}\left(\boldsymbol{M}\right)~{}.$

Since the bounds are non-increasing, we bound $f\\!\left(k\right)$ at
iteration k, using $f\\!\left(1\right),\dots,f\\!\left(k\right)$:

$\displaystyle f\left(k\right)$
$\displaystyle=\min_{t\in\left[k\right]}f\left(t\right)\leq\frac{1}{k}\sum_{t=1}^{k}f\left(t\right)=\frac{1}{k}\sum_{t=1}^{k}\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{t},{\boldsymbol{P}}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}{}_{t}\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{t}\cdots{\boldsymbol{P}}_{1}\right]$
$\displaystyle=\frac{1}{k}\sum_{t=1}^{k}\left(\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{t}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}_{t}\cdots{\boldsymbol{P}}_{1}\right]-\\!\\!\\!\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{t},{\boldsymbol{P}}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}{}_{t}{\boldsymbol{P}}{\boldsymbol{P}}_{t}\cdots{\boldsymbol{P}}_{1}\right]\right)$
$\displaystyle\left[\begin{subarray}{c}\text{identically}\\\
\text{distributed}\end{subarray}\right]$
$\displaystyle=\frac{1}{k}\sum_{t=1}^{k}\left(\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{t}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}_{t}\cdots{\boldsymbol{P}}_{1}\right]-\\!\\!\\!\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{t},{\boldsymbol{P}}_{t+1}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}{}_{t+1}\cdots{\boldsymbol{P}}_{1}\right]\right)$
$\displaystyle\left[\text{telescoping}\right]$
$\displaystyle=\frac{1}{k}\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\right]-\underbrace{\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots\boldsymbol{P}_{k+1}}\operatorname{tr}\left[{\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}{}_{k+1}\cdots{\boldsymbol{P}}_{1}\right]}_{\geq
0,\text{ because
${\boldsymbol{P}}_{1}\cdots{\boldsymbol{P}}{}_{k+1}\cdots{\boldsymbol{P}}_{1}\succeq\boldsymbol{0}$}}$
$\displaystyle\leq\frac{1}{k}\mathop{\mathbb{E}}_{{\boldsymbol{P}}}\operatorname{rank}\left({\boldsymbol{P}}\right)=\frac{1}{k}\cdot\frac{1}{T}\sum_{m=1}^{T}(d-\operatorname{rank}\left(\boldsymbol{X}_{m}\right))\triangleq\frac{d-r_{\operatorname{avg}}}{k}~{},$

and conclude that

$\displaystyle\mathop{\mathbb{E}}_{\tau}\bigg{[}\frac{1}{T}\sum_{m=1}^{T}\\!\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}_{m}\right){\boldsymbol{P}}_{\tau\left(k\right)}\cdots{\boldsymbol{P}}_{\tau\left(1\right)}\right\|_{2}^{2}\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle\ref{eq:expected-
average}\&\ref{eq:random-
projections}}}{{\equiv}}\\!\\!\\!\mathop{\mathbb{E}}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{k}\cdots{\boldsymbol{P}}_{1}\right\|_{2}^{2}$
$\displaystyle\stackrel{{\scriptstyle\ref{eq:trace_bound}}}{{\leq}}f\\!\left(k\right)\leq\frac{d-r_{\operatorname{avg}}}{k}~{}.$

###  D.2 Back to the expected forgetting

Recall that our initial goal in Eq. (19) was to bound
$\mathop{\mathbb{E}}_{\tau}\Big{[}\frac{1}{k}\sum_{t=1}^{k}\\!\big{\|}{\left(\boldsymbol{I}-{\boldsymbol{P}}_{\tau(t)}\right){{\boldsymbol{P}}_{\tau\left(k\right)}\cdots{\boldsymbol{P}}_{\tau\left(1\right)}}}\big{\|}^{2}\Big{]}$.
Instead, we started by bounding the slightly different quantities from Eq.
(20) and (21), i.e., we showed that
$\mathop{\mathbb{E}}_{\tau,{\boldsymbol{P}}}\left\|\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{\tau\left(k\right)}\cdots{\boldsymbol{P}}_{\tau\left(1\right)}\right\|_{2}^{2}\leq\tfrac{d-r_{\operatorname{avg}}}{k}$.
We now use the bound we proved to bound the original quantity of interest.

$\displaystyle\mathbb{E}_{\tau}\\!\left[\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t\right)}\cdots\boldsymbol{P}_{\tau\left(1\right)}\right\|_{2}^{2}\right]$
$\displaystyle=\mathbb{E}_{\tau}\\!\left[\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t+1\right)}\left(\boldsymbol{P}_{\tau\left(t\right)}+\boldsymbol{I}-\boldsymbol{I}\right)\boldsymbol{P}_{\tau\left(t-1\right)}\cdots\boldsymbol{P}_{\tau\left(1\right)}\right\|_{2}^{2}\right]$
$\displaystyle\left[{\text{Prop.~{}\ref{prop:norms}}}\right]$
$\displaystyle\leq
2\bigg{(}\mathbb{E}_{\tau}\\!\left[\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t+1\right)}\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(t-1\right)}\cdots\boldsymbol{P}_{1}\right\|_{2}^{2}\right]+$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,+\mathbb{E}_{\tau}\\!\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t+1\right)}\boldsymbol{P}_{\tau\left(t-1\right)}\cdots\boldsymbol{P}_{1}\right\|_{2}^{2}\bigg{)}$
$\displaystyle\left[\text{i.i.d.}\right]$
$\displaystyle=2\bigg{(}\mathbb{E}_{\tau}\\!\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t+1\right)}\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(t-1\right)}\cdots\boldsymbol{P}_{1}\right\|_{2}^{2}+$
$\displaystyle\,\,\,\,\,\,\,\,\,\,\,\,\,\,+\underbrace{\mathbb{E}_{\tau,\boldsymbol{P}}\\!\left\|\left(\boldsymbol{I}-\boldsymbol{P}\right)\boldsymbol{P}_{\tau\left(k-1\right)}\cdots\boldsymbol{P}_{1}\right\|_{2}^{2}}_{\leq\nicefrac{{(d-r_{\operatorname{avg}})}}{{\left(k-1\right)}}}\bigg{)}$
$\displaystyle\left[\text{norms}\right]$ $\displaystyle\leq
2\left(\mathbb{E}_{\tau}\\!\left[\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t+1\right)}\right\|_{2}^{2}\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(t-1\right)}\cdots\boldsymbol{P}_{1}\right\|_{2}^{2}\right]+\frac{d-r_{\operatorname{avg}}}{k-1}\right)$
$\displaystyle=2\left(\mathbb{E}_{\tau,\boldsymbol{P}}\\!\left[\left\|\left(\boldsymbol{I}-\boldsymbol{P}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t+1\right)}\right\|_{2}^{2}\left\|\left(\boldsymbol{I}-\boldsymbol{P}\right)\boldsymbol{P}_{\tau\left(t-1\right)}\cdots\boldsymbol{P}_{1}\right\|_{2}^{2}\right]+\frac{d-r_{\operatorname{avg}}}{k-1}\right)~{}.$

Recall that both the spectral norms above are upper bounded by 1. We upper
bound the norm consisting of less projections by 1 and keep the other one.

Assume $t>\nicefrac{{\left(k+1\right)}}{{2}}$, and thus $t-1>k-t$. We get,
$\mathbb{E}_{\tau,\boldsymbol{P}}\\!\left\|\left(\boldsymbol{I}-\boldsymbol{P}\right)\boldsymbol{P}_{\tau\left(t-1\right)}\cdots\boldsymbol{P}_{1}\right\|_{2}^{2}\leq\frac{d-r_{\operatorname{avg}}}{t-1}$.
Similarly, when $t\leq\nicefrac{{\left(k+1\right)}}{{2}}$ and $t-1\leq k-t$,
we get
$\mathbb{E}_{\tau,\boldsymbol{P}}\\!\left\|\left(\boldsymbol{I}-\boldsymbol{P}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t+1\right)}\right\|_{2}^{2}\leq\frac{d-r_{\operatorname{avg}}}{k-t}$.

Overall, we get a final bound of

$\displaystyle\frac{1}{k}\sum_{t=1}^{k-1}\mathbb{E}_{\tau}\left[\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{\tau\left(t\right)}\right)\boldsymbol{P}_{\tau\left(k\right)}\cdots\boldsymbol{P}_{\tau\left(t\right)}\cdots\boldsymbol{P}_{\tau\left(1\right)}\right\|_{2}^{2}\right]$
$\displaystyle\leq\frac{2}{k}\bigg{(}\left(k-1\right)\frac{d-r_{\operatorname{avg}}}{k-1}+\sum_{t=1}^{\left\lfloor\left(k+1\right)/2\right\rfloor}\frac{d-r_{\operatorname{avg}}}{k-t}+\sum_{t=\left\lfloor\left(k+1\right)/2\right\rfloor+1}^{k-1}\frac{d-r_{\operatorname{avg}}}{t-1}\bigg{)}$
$\displaystyle=\frac{2(d-r_{\operatorname{avg}})}{k}\bigg{(}1+\\!\\!\\!\sum_{t=k-\left\lfloor\left(k+1\right)/2\right\rfloor}^{k-1}\\!\\!\\!\nicefrac{{1}}{{t}}+\\!\\!\sum_{t=\left\lfloor\left(k+1\right)/2\right\rfloor}^{k-2}\\!\\!\\!\nicefrac{{1}}{{t}}\bigg{)}\leq\frac{2(d-r_{\operatorname{avg}})}{k}\bigg{(}1+2\\!\sum_{t=\left\lfloor
k/2\right\rfloor}^{k-1}\\!\\!\nicefrac{{1}}{{t}}\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle\left[k\geq
2\right]}}{{\leq}}\frac{2(d-r_{\operatorname{avg}})}{k}\bigg{(}1+2+2\intop_{\left\lfloor
k/2\right\rfloor}^{k-1}\frac{1}{t}dt\bigg{)}\leq\frac{2(d-r_{\operatorname{avg}})}{k}\left(3+2\left(\ln\left(k-1\right)-\ln\left(\left\lfloor
k/2\right\rfloor\right)\right)\right)$
$\displaystyle=\frac{2(d-r_{\operatorname{avg}})}{k}\left(3+2\ln\left(\frac{k-1}{\left\lfloor
k/2\right\rfloor}\right)\right)\leq\frac{2(d-r_{\operatorname{avg}})}{k}\underbrace{\left(3+2\ln\left(2\right)\right)}_{\leq
4.5}\leq\frac{9(d-r_{\operatorname{avg}})}{k}~{}.$

##  Appendix E Extension to the average iterate (Remark 6.4)

Here we briefly demonstrate how our results from Sections 5 and 6 can be
readily improved by considering the average iterate
$\overline{\boldsymbol{w}}_{k}\triangleq\frac{1}{k}\sum_{t=1}^{k}\boldsymbol{w}_{t}$
instead of the last iterate $\boldsymbol{w}_{k}$. The average iterate is known
to be easier to analyze, and yields generally stronger results when analyzing
the SGD algorithm Varre et al. (2021) and the Kaczmard method Morshed et al.
(2020). Of course, working with the average iterate requires maintaining a
running mean parameter vector, which is generally more memory consuming.

###  E.1 Proof sketch for the cyclic setting

As a proof of concept, we prove better bounds for an “easier” iterate that
averages only iterates at the end of cycles, i.e., for $k\\!=\\!nT$ we define
$\overline{\boldsymbol{w}}_{n}\\!=\\!\frac{1}{n}\sum_{n^{\prime}=1}^{n}\\!\boldsymbol{w}_{Tn^{\prime}}$.
For the first task, we get

$\displaystyle\left\|\boldsymbol{X}_{1}\left(\overline{\boldsymbol{w}}_{n}-\boldsymbol{w}^{\star}\right)\right\|^{2}$
$\displaystyle=\left\|\boldsymbol{X}_{1}\Big{(}{\frac{1}{n}\sum_{n^{\prime}=1}^{n}\boldsymbol{w}_{Tn^{\prime}}-\boldsymbol{w}^{\star}}\Big{)}\right\|^{2}=\frac{1}{n^{2}}\left\|\boldsymbol{X}_{1}\sum_{n^{\prime}=1}^{n}\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\left(\cancel{\boldsymbol{w}_{0}}-\boldsymbol{w}^{\star}\right)\right\|^{2}$
$\displaystyle\leq\frac{1}{n^{2}}\left\|\sum_{n^{\prime}=1}^{n}\left(\boldsymbol{I}-\boldsymbol{P}_{1}\right)\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}$
$\displaystyle\left[\begin{subarray}{c}\text{Lemma~{}\ref{lem:square_ineq}}\end{subarray}\right]$
$\displaystyle\leq\frac{1}{n}\sum_{n^{\prime}=1}^{n}\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{1}\right)\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}$
$\displaystyle=\frac{1}{n}\sum_{n^{\prime}=1}^{n}\left(\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}-\left\|\boldsymbol{P}_{1}\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}\right)$
$\displaystyle\leq\frac{1}{n}\sum_{n^{\prime}=1}^{n}\left(\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}-\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}+1}\boldsymbol{w}^{\star}\right\|^{2}\right)$
$\displaystyle=\frac{1}{n}\Big{(}{\underbrace{\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)\boldsymbol{w}^{\star}\right\|^{2}}_{\leq
1}-\underbrace{\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n+1}\boldsymbol{w}^{\star}\right\|^{2}}_{\geq
0}}\Big{)}\leq\frac{1}{n}~{}.$

Similarly, for a general task $m\in\left[{T}\right]$, we have

$\displaystyle\left\|\boldsymbol{X}_{m}\left(\overline{\boldsymbol{w}}_{n}-\boldsymbol{w}^{\star}\right)\right\|^{2}$
$\displaystyle\leq\frac{1}{n}\sum_{n^{\prime}=1}^{n}\left\|\left(\boldsymbol{I}-\boldsymbol{P}_{m}\right)\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}$
$\displaystyle=\frac{1}{n}\sum_{n^{\prime}=1}^{n}\left(\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}-\left\|\boldsymbol{P}_{m}\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}\right)$
$\displaystyle\left[\text{\ref{lem:bound_on_projection_to_m_task}}\right]$
$\displaystyle\leq\frac{m}{n}\sum_{n^{\prime}=1}^{n}\left(\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}}\boldsymbol{w}^{\star}\right\|^{2}-\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n^{\prime}+1}\boldsymbol{w}^{\star}\right\|^{2}\right)$
$\displaystyle=\frac{m}{n}\left(\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)\boldsymbol{w}^{\star}\right\|^{2}-\left\|\left(\boldsymbol{P}_{T}\cdots\boldsymbol{P}_{1}\right)^{n+1}\boldsymbol{w}^{\star}\right\|^{2}\right)\leq\frac{m}{n}~{}.$

Overall, we get the following bound on the forgetting in the cyclic setting:

$\displaystyle\begin{split}F_{\tau,S}(\overline{\boldsymbol{w}}_{n})=\frac{1}{T}\sum_{m=1}^{T}\left\|\boldsymbol{X}_{m}\left(\overline{\boldsymbol{w}}_{n}-\boldsymbol{w}^{\star}\right)\right\|^{2}\leq\frac{1}{T}\sum_{m=1}^{T-1}\frac{m}{n}=\frac{T-1}{2n}\leq\frac{T^{2}}{2k}~{}.\end{split}$

###  E.2 Proof sketch for the random setting

For this case, we will demonstrate how one can easily bound a similar expected
forgetting to the one in Eq. (21), by $\tfrac{1}{k}$ instead of
$\tfrac{d-r_{\operatorname{avg}}}{k}$.

Plugging in the average iterate we get,

$\displaystyle\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\Big{\|}{\left(\boldsymbol{I}-{\boldsymbol{P}}\right)\big{(}{\overline{\boldsymbol{w}}_{k}-\boldsymbol{w}^{\star}}\big{)}}\Big{\|}_{2}^{2}$
$\displaystyle=\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\Big{\|}{\left(\boldsymbol{I}-{\boldsymbol{P}}\right)\big{(}{\boldsymbol{w}^{\star}-\frac{1}{k}\sum_{t=1}^{k}\boldsymbol{w}_{t}}\big{)}}\Big{\|}_{2}^{2}$
$\displaystyle=\frac{1}{k^{2}}\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\Big{\|}{\left(\boldsymbol{I}-{\boldsymbol{P}}\right)\sum_{t=1}^{k}\big{(}{\boldsymbol{w}_{t}-\boldsymbol{w}^{\star}}\big{)}}\Big{\|}_{2}^{2}$
$\displaystyle\left[\begin{subarray}{c}\text{Lemma~{}\ref{lem:square_ineq}}\end{subarray}\right]$
$\displaystyle\leq\frac{1}{k}\sum_{t=1}^{k}\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\Big{\|}{\left(\boldsymbol{I}-{\boldsymbol{P}}\right)\big{(}{\boldsymbol{w}_{t}-\boldsymbol{w}^{\star}}\big{)}}\Big{\|}_{2}^{2}$
$\displaystyle\left[\begin{subarray}{c}\text{Lemma~{}\ref{total_contraction}}\end{subarray}\right]$
$\displaystyle=\frac{1}{k}\sum_{t=1}^{k}\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\Big{\|}{\left(\boldsymbol{I}-{\boldsymbol{P}}\right){\boldsymbol{P}}_{t}\cdots{\boldsymbol{P}}_{1}\boldsymbol{w}^{\star}}\Big{\|}_{2}^{2}$
$\displaystyle\left[\begin{subarray}{c}\text{Prop.~{}\ref{prop:projections}}\end{subarray}\right]$
$\displaystyle=\frac{1}{k}\sum_{t=1}^{k}\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k},{\boldsymbol{P}}}\left[\Big{\|}{{\boldsymbol{P}}_{t}\cdots{\boldsymbol{P}}_{1}\boldsymbol{w}^{\star}}\Big{\|}_{2}^{2}-\Big{\|}{{\boldsymbol{P}}{\boldsymbol{P}}_{t}\cdots{\boldsymbol{P}}_{1}\boldsymbol{w}^{\star}}\Big{\|}_{2}^{2}\right]$
$\displaystyle\left[\begin{subarray}{c}\text{i.i.d.}\end{subarray}\right]$
$\displaystyle=\frac{1}{k}\sum_{t=1}^{k}\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k}}\left[\Big{\|}{{\boldsymbol{P}}_{t}\cdots{\boldsymbol{P}}_{1}\boldsymbol{w}^{\star}}\Big{\|}_{2}^{2}-\Big{\|}{{\boldsymbol{P}}_{t+1}\cdots{\boldsymbol{P}}_{1}\boldsymbol{w}^{\star}}\Big{\|}_{2}^{2}\right]$
$\displaystyle\left[\begin{subarray}{c}\text{telescoping}\end{subarray}\right]$
$\displaystyle=\frac{1}{k}\mathbb{E}_{{\boldsymbol{P}}_{1},\dots,{\boldsymbol{P}}_{k}}\left[\Big{\|}{{\boldsymbol{P}}_{1}\boldsymbol{w}^{\star}}\Big{\|}_{2}^{2}-\Big{\|}{{\boldsymbol{P}}_{k+1}\cdots{\boldsymbol{P}}_{1}\boldsymbol{w}^{\star}}\Big{\|}_{2}^{2}\right]\leq\frac{1}{k}~{}.$

##  Appendix F Additional related works

###  F.1 Continual learning

##### Practical methods for continual learning.

Like we explained in Section 7, algorithmic approaches for preventing
catastrophic forgetting roughly partition into three categories:

  1. 1.

_Memory-based replay approaches_ actively repeat examples from previous tasks
to avoid forgetting. Some store examples from observed tasks (e.g., Robins
(1995)), while others replay _generated_ synthetic data from previous tasks to
the main model (e.g., Shin et al. (2017)).

  2. 2.

_Regularization approaches_ limit the plasticity of the learned model in order
to enhance its stability. One can perform regularization in the _parameter
space_ , to protect parameters that are important to previous tasks (e.g.,
Kirkpatrick et al. (2017); Nguyen et al. (2018); Zeno et al. (2021)), or in
the _function space_ , to protect the _outputs_ of previous tasks (e.g., Li
and Hoiem (2017); Lopez-Paz and Ranzato (2017); Farajtabar et al. (2020)). Few
recent works (Benzing (2022), Lubana et al. (2021)) focus on obtaining a
better understanding of popular quadratic regularization techniques like EWC
(Kirkpatrick et al., 2017), MAS (Aljundi et al., 2018), and SI (Zenke et al.,
2017).

  3. 3.

_Parameter isolation approaches_ allocate different subsets of parameters to
different tasks. This can be done by expanding the model upon seeing a new
task (e.g., Yoon et al. (2018)), or by compressing the existing architecture
after each task, to free parameters for future tasks (e.g., Mallya and
Lazebnik (2018); Schwarz et al. (2021)).

##### Understanding customary training techniques

Some recent papers also test the effect of common deep learning training
techniques that change the optimization dynamics and/or have an implicit
regularizing implications. For instance, Mirzadeh et al. (2020) study how
different training regimes affect the loss landscape geometry, thus
influencing the overall degree of forgetting in continual learning settings.
Goodfellow et al. (2013) were the first to suggest that training with the
_dropout_ technique can be beneficial to remedy catastrophic forgetting in
continual learning settings. Delange et al. (2021) also show that dropout is
fruitful in many continual learning methods (some of which are mentioned
above). They point out that it mainly improves the initial performance on
learned tasks (by mitigating overfitting), but leads to an increased amount of
forgetting when learning later tasks.

Optimization hyperparameters are known to change the geometry of the loss
landscape and affect generalization (see for instance Jastrzebski et al.
(2018)). Mirzadeh et al. (2020) point out that most empirical papers in this
field use small batch sizes and SGD with learning rate decay. They also
discuss how a large learning rate increases the plasticity of deep models,
thus having an ill-effect on forgetting.

Finally, Mirzadeh et al. (2022) pointed out that architectural decisions also
have implications on catastrophic forgetting, and specifically observe that
wide neural networks tend to forget less catastrophically.

###  F.2 Wider scope

Finally, we note that similar questions to those we ask here and that are
asked generally in the continual learning paradigm, are often asked on other
fields, such as multi-task learning, meta learning, transfer learning,
curriculum learning Weinshall and Amir (2020), and online learning. Despite
the similarities, there are differences though. For example, in multi-task
learning, the data from all tasks are simultaneously available, in transfer
learning the goal to adapt models for a new target tasks and preserving
performance on old source task is not a priority, and in online learning,
typically, training data for previously seen tasks are assumed to be available
in sequentially adapting to data from new tasks. However, a more detailed
review of these related areas is beyond the scope of this work.


# Moral-Trust Violation vs Performance-Trust Violation by a Robot: Which Hurts
More?

Zahra Rezaei Khavas, Russell Perkins, S.Reza Ahmadzadeh, Paul Robinette

###### Abstract

In recent years a modern conceptualization of trust in human-robot interaction
(HRI) was introduced by Ullman et al.(Ullman and Malle 2018). This new
conceptualization of trust suggested that trust between humans and robots is
multidimensional, incorporating both performance aspects (i.e., similar to the
trust in human-automation interaction) and moral aspects (i.e., similar to the
trust in human-human interaction). But how does a robot violating each of
these different aspects of trust affect human trust in a robot? How does trust
in robots change when a robot commits a moral-trust violation compared to a
performance-trust violation? And whether physiological signals have the
potential to be used for assessing gain/loss of each of these two trust
aspects in a human. We aim to design an experiment to study the effects of
performance-trust violation and moral-trust violation separately in a search
and rescue task. We want to see whether two failures of a robot with equal
magnitudes would affect human trust differently if one failure is due to a
performance-trust violation and the other is a moral-trust violation.

Keywords: moral-trust, performance-trust, trust violation in HRI,
multidimensional trust

## Introduction

Recent advances in human-robot interaction (HRI) and the autonomy of robots
have revolutionized the field of human-robot trust. Prospective robotic agents
are intended to work as social agents interacting with humans, rather than
tools that humans use (Khavas, Ahmadzadeh, and Robinette 2020). For a
successful interaction between humans and robots, robots need to respond to
the changes in human trust in real-time. So, real-time sensing of trust level
in humans is needed by robots. Similar to how (Hu et al. 2016) discussed
human-machine interaction trust issues.

There are two main classes of trust measurement strategies for assessing trust
in HRI. The first and most dominant methods for trust measurement in HRI are
subjective trust measurement strategies. These trust measurement techniques
involve assessing experiment participants’ answers to questionnaires designed
to gauge people’s trust in automated agents or specifically to the robots
(Flook et al. 2019; Baker et al. 2018). The second class of trust measurement
strategies is objective trust measurement methods that are based on analyzing
experiment participants’ behavior and interact with the robots (Flook et al.
2019; Baker et al. 2018). Objective trust measurement strategies can provide a
semi-real-time trust assessment, yet these methods are highly prone to error.

Recently, researchers have introduced methods for assessing trust using
physiological measurements in different fields such as human-automation
interaction (HAI), human-machine interaction (HMI), and also human-robot
interaction (Wang et al. 2018; Akash et al. 2018; Hald, Rehmn, and Moeslund
2020). Measuring trust using physiological measurements can provide us with
real-time assessment of trust (Ajenaghughrure et al. 2019; Khalid et al.
2016).

With the introduction of trust as a multidimensional concept in recent
years(Ullman and Malle 2019), and the introduction of subjective methods for
measuring different dimensions of trust (Malle and Ullman 2021), this question
arises that whether other trust measurement strategies will also be able to
assess different aspects of trust separately.

Our study aims to see if two similar robot failures with the same magnitude
would affect human trust differently if one failure is due to a moral-trust
violation and the other is due to a performance-trust violation? Later, we
will explore if moral-trust and performance-trust are separately measurable
using physiological measurements.

## Background and Research Questions

We situate our work in the studies on human-robot trust and considering trust
in HRI as a multidimensional concept.

### Effects of Moral and Performance Trust Violation on Human Trust

The framing of the trust violation based on two influential trustworthiness
factors, competency, and integrity, has a long history in human-human
interaction (Mayer, Davis, and Schoorman 1995; Kim, Dirks, and Cooper 2009;
Butler Jr and Cantrell 1984). Previous works in the field of human-human
interaction showed that positive and negative behaviors are weighted and
perceived differently with regards to a human’s competency and integrity.
Regarding a human’s competency, positive points are more heavily weighted
compared to negative points. However, when assessing human integrity, negative
points are weighted higher than positive points (Skowronski and Carlston
1989). This reversed weighting of positive and negative points for assessing
competency and integrity of people might be due to positive points being more
representative of one’s competence and negative points being more
representative of one’s integrity (Skowronski and Carlston 1987).

There is also some research in the field of human-human trust that shows
different trust repair strategies should be deployed for repairing trust after
competency-trust violation and integrity-trust violation (Ferrin et al. 2007;
Dirks et al. 2011; Kim et al. 2006).

Only a few studies are investigating the effects of automated systems and
robots violating different aspects of trust. Clark et al.(Clark 2018)
classifies trust violation in human-automation interaction under two classes,
competence-based trust violations (CBTV) and integrity-based trust violations
(IBTV), and states that IBTVs cause higher trust loss than CBTVs. Sebo et al.
(Sebo, Krishnamurthi, and Scassellati 2019) also stress the importance of
considering the trust violation type for designing the trust repair strategy
of a robot and suggest different trust repair strategies for each trust
violation type by a robot. While this study introduces different trust repair
strategies for different types of trust violations by robots, it is not clear
how human trust will be affected by each of these different trust violation
types. We therefore ask:

Research question 1: Do two robot failures with the same magnitude affect
human trust the same way if one failure is due to performance-trust violation
and the other is due to a moral-trust violation?

### Assessing the Effects of Moral and Performance Trust Violation on Human
trust using Physiological Measurements

Trust assessment based on physiological measurement methods does not have a
long history, but these methods gained much popularity among researchers in
different fields in the recent decade. The use of physiological signals for
trust measurement in HRI is motivated by the ability of the physiological
signal to capture human trust in real-time. Moberg et al. (Uvnas-Moberg and
Petersson 2005) assess trust in human-human interaction by measuring the
amount of oxytocin secretion in the human body. Khalid et al.(Khalid et al.
2016) measures trust in HRI using facial expressions, voice features, and
extracted heart-rate features of humans, and Wang et al.(Wang et al. 2018)
used Electroencephalogram (EEG) signal for assessing trust in human-automation
interaction. Many other researchers used a variety of different physiological
measurements for assessing trust in HRI. A physiological signal that many
researchers have recently used to assess the trust between humans and robots
is the EEG signal. EEG had been used alone or in combination with other
measurements for as assessing trust in many studies (Hu et al. 2016; Akash et
al. 2018; Park, Shahrdar, and Nojoumian 2018; Huang and Nam 2020; Hald, Rehmn,
and Moeslund 2020).

A recent study compared the reliability of different physiological
measurements, including EEG, electrodermal activity, electrocardiogram, eye-
tracking, and facial electromyogram, for assessing trust in HRI
(Ajenaghughrure, Sousa, and Lamas 2021). This study showed that while EEG
signal is most reliable among all other psycho-physiological measurements for
assessing trust, multimodal psycho-physiological signals (i.e., a combination
of all the above-mentioned psycho-physiological measurements) remain
promising. While this study stress on the reliability of EEG signal for
assessing trust, it does not clarify that which trust type can be assessed
using EEG signal, which leads to the second research question of our study:

Research question 2: Can EEG signals alone distinguish the difference between
a performance-trust violation and a moral-trust violation?

## Theory

We aim to investigate our research questions with a two-conditions experiment,
robot violating moral trust vs. robot violating performance trust, a between-
subject study. We designed a search game for this research. In the game, teams
of one human and one robot play 10 to 15 rounds of a search game. Members of
the team are supposed to find targets hidden in the area (Fig. 1).

Figure 1: Screen capture of the search page of the game: human and robot need
to search the area to find targets hidden in the area and gain score

The human can not see or control the robot’s work during the round. At the end
of each round, the human should decide to either integrate or discard the
score gained by the robot. The human should make this decision before seeing
the targets detected and the score gained by the robot in each round.
Therefore, it is a blind decision. Choosing to integrate will integrate the
robot’s score to the overall score, whether negative or positive. However,
choosing to discard will discard the robot’s scores, which will not affect the
team score (Fig. 2). After choosing to integrate or discard, the human will be
shown the targets the robot detected and the score gained by the robot
(Fig.3).

Figure 2: At the end of each round human should make a decision to integrate
or discard robot’s score Figure 3: Screen capture of the results page of the
game

We defined two types of scores in this game, team performance score (TPS) and
individual performance score (IPS), which contradict each other. So, one
should sacrifice TPS to optimize IPS and vice-versa.

There are three types of targets hidden in the area, gold targets that add 100
points to TPS, red targets that subtract 100 points from TPS, and pink targets
that subtract 100 points from the TPS and add it to the IPS. Teams will be
encouraged to optimize TPS by only picking gold targets in the search task. We
expect people to consider picking red targets by robots due to the robot’s low
performance and picking pink targets due to the robot’s lack of moral
integrity (Table 1).

  1. 1.

Performance-trust violation condition: in this condition robot picks red
targets in some rounds of the game. Red targets subtract 100 points from the
TPS.

  2. 2.

Moral-trust violation condition: in this condition robot picks pink targets in
some rounds of the game. Blue targets subtract 100 points from the TPS and add
100 points to the IPS.

The score gained by the robot in both conditions in corresponding rounds will
be precisely similar. The only difference is about the IPS. In the
performance-trust violation condition, the robot picks red targets, which
subtract 100 points from the TPS but do not affect the robot IPS. In the
moral-trust violation condition, the robot picks pink targets in some rounds,
subtracting 100 points from the TPS and adding them to the IPS. Each
participant only experiences one of the two conditions of the experiment.
Participants will play the search game multiple rounds, and in both
conditions, the scores gained by the robot in corresponding rounds will be the
same.

Table 1: Target types and effects of those on the scores

Target Types | Effect on TPS | Effect on IPS |  |
---|---|---|---|---
Gold Star | +100 | 0 |  |
Red Circle | -100 | 0 |  |
Pink Triangle | -100 | +100 |  |

## Methodology

This section will explain the details of the user study that we will perform.
As described in the Theory section, we want to study the effects of violating
performance and moral trust by robots on human trust.

### Participants

We will run this experiment in two phases, and we will need to recruit
participants separately for each phase.

  * •

In the first phase, we will only focus on the first research question. In this
phase, we will only need to have online participants playing the game. We will
expect to need a total of 100 online participants for this phase of the
experiment. Participants will be assigned to one of the experiment conditions
randomly.

  * •

In the second phase of the experiment, we will focus on the second research
question. We will need to have participants over in our lab to capture
physiological data while playing the game. We will expect to have 60
participants (i.e., 30 participants per condition) at this phase.

### Game Setup and Subjective Measurements

To assess the impact of the robot’s faulty behavior on the perceived
reliability of the robot by participants and the trust-related behavior of
participants toward the robot, we will focus our analysis on two different
moments following a faulty behavior from the robot side. The first will be the
moment after showing the results of each round. A list of three questions will
be asked from participants about the robot’s performance and reliability. The
second will be when participants are asked to make a trust decision in the
following round.

### System Setup and Objective and Physiological Measurements

In order to explore our research questions, we have built an online game that
allows us to construct two scenarios mentioned in the Theory Section. Two
scenarios of robot faulty behavior with the same magnitude, one robot
performance-trust violation, and the other shows robot moral-trust violation.

In the first phase of the experiment, we would only have online participants
for our experiment. So, we would not need any system setup but the online
game. However, as in the second phase of the experiment, we will need to have
participants in our lab. We will need a computer running the game, hardware,
and software for EEG recording, GSR recording, and eye-tracking during the
experiment.

We will also need a camera set up to capture video from participants while
playing the game for further analysis of their behavior and body language to
see if we can find reasonable differences in participants’ body language in
two game conditions.

## Conclusion and Future Work

This study aims to investigate the effects of a robot violating performance
and moral trust and compare the effects of a robot violating each of these two
trust aspects on human trust. We want to study if moral-trust violation would
affect human trust differently from a performance-trust violation with the
same magnitude. In the second phase of our experiment, we also aim to see if
these two trust types are distinguishable using physiological measurements.

As future work, we would expect to develop methods to classify gained/lost
trust in any type of human-robot interaction into two classes, moral-trust
gain/loss and performance-trust gain/loss. In later systems, we will need to
develop separate trust calibration policies for each class of violation.

Other than physiological measurements, researchers use other types of
measurements for the real-time assessment of trust. For example, Khalid et
al.(Khalid et al. 2016) used facial expressions and voice features in
conjugate with one physiological measurement related to heartbeats for trust
measurement. Some researchers also used machine learning methods to reason
about human behavior based on robot behavior in real-time to be able to modify
robot behavior based on human expectation (Chen et al. 2018).

Another interesting idea for future work is to see how many of these trust
measurement strategies have the potential to provide separate measures of
gain/loss of trust in each of the two different trust classes. More robust
trust classifiers (e.g., classifying trust gain/loss under two classes moral-
trust gain/loss, performance-trust gain/loss) and trust measurements
strategies can be developed combining these methods.

As a whole, we expect to develop more accurate trust measurements strategies
that provide real-time assessments of human trust to a robot. We expect these
methods to reason about the trust gain/loss in humans and add to the robot’s
intelligence for choosing appropriate trust dampening/repair strategies based
on the gained/lost trust type.

## Acknowledgment

This research is supported by the Army Research Lab contract W911NF-20-2-0089.

## References

  * Ajenaghughrure et al. (2019) Ajenaghughrure, I. B.; Sousa, S. C.; Kosunen, I. J.; and Lamas, D. 2019.  Predictive model to assess user trust: a psycho-physiological approach.  In _Proceedings of the 10th Indian conference on human-computer interaction_ , 1–10.
  * Ajenaghughrure, Sousa, and Lamas (2021) Ajenaghughrure, I. B.; Sousa, S. C. D. C.; and Lamas, D. 2021.  Psychophysiological modelling of trust in technology: Comparative analysis of algorithm ensemble methods.  In _2021 IEEE 19th World Symposium on Applied Machine Intelligence and Informatics (SAMI)_ , 000161–000168. IEEE.
  * Akash et al. (2018) Akash, K.; Hu, W.-L.; Jain, N.; and Reid, T. 2018.  A classification model for sensing human trust in machines using EEG and GSR.  _ACM Transactions on Interactive Intelligent Systems (TiiS)_ 8(4): 1–20.
  * Baker et al. (2018) Baker, A. L.; Phillips, E. K.; Ullman, D.; and Keebler, J. R. 2018.  Toward an understanding of trust repair in human-robot interaction: Current research and future directions.  _ACM Transactions on Interactive Intelligent Systems (TiiS)_ 8(4): 1–30.
  * Butler Jr and Cantrell (1984) Butler Jr, J. K.; and Cantrell, R. S. 1984.  A behavioral decision theory approach to modeling dyadic trust in superiors and subordinates.  _Psychological reports_ 55(1): 19–28.
  * Chen et al. (2018) Chen, M.; Nikolaidis, S.; Soh, H.; Hsu, D.; and Srinivasa, S. 2018.  Planning with trust for human-robot collaboration.  In _Proceedings of the 2018 ACM/IEEE International Conference on Human-Robot Interaction_ , 307–315.
  * Clark (2018) Clark, T. 2018.  Integrity-Based Trust Violations Within Human-Machine Teaming.  Technical report, Naval Postgraduate School Monterey United States.
  * Dirks et al. (2011) Dirks, K. T.; Kim, P. H.; Ferrin, D. L.; and Cooper, C. D. 2011.  Understanding the effects of substantive responses on trust following a transgression.  _Organizational Behavior and Human Decision Processes_ 114(2): 87–103.
  * Ferrin et al. (2007) Ferrin, D. L.; Kim, P. H.; Cooper, C. D.; and Dirks, K. T. 2007.  Silence speaks volumes: the effectiveness of reticence in comparison to apology and denial for responding to integrity-and competence-based trust violations.  _Journal of Applied Psychology_ 92(4): 893.
  * Flook et al. (2019) Flook, R.; Shrinah, A.; Wijnen, L.; Eder, K.; Melhuish, C.; and Lemaignan, S. 2019\.  On the impact of different types of errors on trust in human-robot interaction: Are laboratory-based HRI experiments trustworthy?  _Interaction Studies_ 20(3): 455–486.
  * Hald, Rehmn, and Moeslund (2020) Hald, K.; Rehmn, M.; and Moeslund, T. B. 2020.  Human-Robot Trust Assessment Using Motion Tracking & Galvanic Skin Response.  In _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 6282–6287. IEEE.
  * Hu et al. (2016) Hu, W.-L.; Akash, K.; Jain, N.; and Reid, T. 2016.  Real-time sensing of trust in human-machine interactions.  _IFAC-PapersOnLine_ 49(32): 48–53.
  * Huang and Nam (2020) Huang, J.; and Nam, C. S. 2020.  Decoding Trust in Human-Automation Interaction: A Dynamic Causal Modeling Study.  In _IIE Annual Conference. Proceedings_ , 1–6. Institute of Industrial and Systems Engineers (IISE).
  * Khalid et al. (2016) Khalid, H. M.; Shiung, L. W.; Nooralishahi, P.; Rasool, Z.; Helander, M. G.; Kiong, L. C.; and Ai-vyrn, C. 2016.  Exploring psycho-physiological correlates to trust: Implications for human-robot-human interaction.  In _Proceedings of the human factors and ergonomics society annual meeting_ , volume 60, 697–701. SAGE Publications Sage CA: Los Angeles, CA.
  * Khavas, Ahmadzadeh, and Robinette (2020) Khavas, Z. R.; Ahmadzadeh, S. R.; and Robinette, P. 2020.  Modeling trust in human-robot interaction: A survey.  In _International Conference on Social Robotics_ , 529–541. Springer.
  * Kim, Dirks, and Cooper (2009) Kim, P. H.; Dirks, K. T.; and Cooper, C. D. 2009.  The repair of trust: A dynamic bilateral perspective and multilevel conceptualization.  _Academy of Management Review_ 34(3): 401–422.
  * Kim et al. (2006) Kim, P. H.; Dirks, K. T.; Cooper, C. D.; and Ferrin, D. L. 2006.  When more blame is better than less: The implications of internal vs. external attributions for the repair of trust after a competence-vs. integrity-based trust violation.  _Organizational behavior and human decision processes_ 99(1): 49–65.
  * Malle and Ullman (2021) Malle, B. F.; and Ullman, D. 2021.  A multidimensional conception and measure of human-robot trust.  In _Trust in Human-Robot Interaction_ , 3–25. Elsevier.
  * Mayer, Davis, and Schoorman (1995) Mayer, R. C.; Davis, J. H.; and Schoorman, F. D. 1995.  An integrative model of organizational trust.  _Academy of management review_ 20(3): 709–734.
  * Park, Shahrdar, and Nojoumian (2018) Park, C.; Shahrdar, S.; and Nojoumian, M. 2018.  EEG-based classification of emotional state using an autonomous vehicle simulator.  In _2018 IEEE 10th Sensor Array and Multichannel Signal Processing Workshop (SAM)_ , 297–300. IEEE.
  * Sebo, Krishnamurthi, and Scassellati (2019) Sebo, S. S.; Krishnamurthi, P.; and Scassellati, B. 2019.  “I Don’t Believe You”: Investigating the Effects of Robot Trust Violation and Repair.  In _2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_ , 57–65. IEEE.
  * Skowronski and Carlston (1987) Skowronski, J. J.; and Carlston, D. E. 1987.  Social judgment and social memory: The role of cue diagnosticity in negativity, positivity, and extremity biases.  _Journal of personality and social psychology_ 52(4): 689.
  * Skowronski and Carlston (1989) Skowronski, J. J.; and Carlston, D. E. 1989.  Negativity and extremity biases in impression formation: A review of explanations.  _Psychological bulletin_ 105(1): 131.
  * Ullman and Malle (2018) Ullman, D.; and Malle, B. F. 2018.  What does it mean to trust a robot? Steps toward a multidimensional measure of trust.  In _Companion of the 2018 acm/ieee international conference on human-robot interaction_ , 263–264.
  * Ullman and Malle (2019) Ullman, D.; and Malle, B. F. 2019.  Measuring gains and losses in human-robot trust: Evidence for differentiable components of trust.  In _2019 14th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_ , 618–619. IEEE.
  * Uvnas-Moberg and Petersson (2005) Uvnas-Moberg, K.; and Petersson, M. 2005.  Oxytocin, a mediator of anti-stress, well-being, social interaction, growth and healing.  _Zeitschrift fur Psychosomatische Medizin und Psychotherapie_ 51(1): 57–80.
  * Wang et al. (2018) Wang, M.; Hussein, A.; Rojas, R. F.; Shafi, K.; and Abbass, H. A. 2018.  EEG-based neural correlates of trust in human-autonomy interaction.  In _2018 IEEE Symposium Series on Computational Intelligence (SSCI)_ , 350–357. IEEE.