######  Inequality 1.

Let $N\in\mathbb{N}$ and $d\in\mathbb{N}$. For any sequence of vector
$(a_{i})_{i=1}^{N}\in\mathbb{R}^{d}$, we have the following inequalities:

$\left\|\sum_{i=1}^{N}a_{i}\right\|^{2}\leq\left(\sum_{i=1}^{N}\left\|a_{i}\right\|\right)^{2}\leq
N\sum_{i=1}^{N}\left\|a_{i}\right\|^{2}\,.$

The first part of the inequality corresponds to the triangular inequality,
while the second part is Cauchy’s inequality.

######  Inequality 2.

Let $x$ in $\mathbb{R}^{d}$ and $A$ in $\mathcal{M}_{d,d}(\mathbb{R})$, then
we have
$\|Ax\|\leq{|\kern-1.07639pt|\kern-1.07639pt|A|\kern-1.07639pt|\kern-1.07639pt|}\|x\|$.

Below, we recall Minkowski’s and Jensen’s inequalities. Additionally, we
recall the Cauchy-Schwarz inequality for conditional expectations.

Let a probability space $(\Omega,\mathcal{A},\mathbb{P})$ with $\Omega$ a
sample space, $\mathcal{A}$ a $\sigma$-algebra, and $\mathbb{P}$ a probability
measure.

##### Minkowski’s inequality.

Let $p>1$ and suppose that $X,Y$ are two random variables in
$\mathcal{L}^{p}(\Omega,\mathcal{A},\mathbb{P})$ (i.e. their $p^{\mathrm{th}}$
moment is bounded), we have the following triangular inequality:

$\displaystyle\mathbb{E}[\|X+Y\|^{p}]^{1/p}\leq\mathbb{E}[\|X\|^{p}]^{1/p}+\mathbb{E}[\|Y\|^{p}]^{1/p}\,.$
(S1)

##### Jensen’s inequality.

Suppose that $X:\Omega\longrightarrow\mathbb{R}^{d}$ is a random variable,
then for any convex function $f:\mathbb{R}^{d}\longrightarrow\mathbb{R}$ we
have:

$\displaystyle f\left(\mathbb{E}(X)\right)\leq\mathbb{E}f(X)\,.$ (S2)

##### Cauchy-Schwarz’s inequality for conditional expectations.

Suppose that $X,Y$ are two random variables in
$\mathcal{L}^{2}(\Omega,\mathcal{A},\mathbb{P})$ (i.e. their second moment is
bounded), then for any $\sigma$-algebra $\mathcal{F}\subset\mathcal{A}$ we
have a.s.:

$\displaystyle\mathbb{E}\left[XY\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}\right]^{2}\leq\mathbb{E}\left[X^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}\right]\mathbb{E}\left[Y^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}\right]\,.$ (S3)

##### Convergence in $L^{p}$-norm.

Suppose that $(X_{n})_{n\in\mathbb{N}}$ is a sequence of random variables in
$\mathcal{L}^{p}(\Omega,\mathcal{A},\mathbb{P})$, and that $X$ is a random
variable in $\mathcal{L}^{p}(\Omega,\mathcal{A},\mathbb{P})$. We say that
$(X_{n})_{n\in\mathbb{N}}$ converges in $L^{p}$-norm towards $X$ if
$\mathbb{E}(\|X_{n}-X\|^{p})\xrightarrow[n\to+\infty]{}0$, it is denoted by:
$X_{n}\xrightarrow[n\to+\infty]{L^{p}}X\,.$

In Subsection 3.3, we use ellipses to visual quadratic functions, therefore we
provide in Definition S1 the mathematical definition.

######  Definition S1 (Representing positive matrices through ellipsoids).

Any symmetric positive definite matrix $M$ in
$\mathcal{S}_{d}^{++}(\mathbb{R})$ defines an ellipsoid
$\mathcal{E}_{M}=\\{x\in\mathbb{R}^{d},x^{\top}M^{-1}x=1\\}$ centered around
zero. The eigenvectors of $M$ are the principal axes of the ellipsoid, and the
squared root of the eigenvalues are the half-lengths of these axes. The
ellipse corresponds to the sphere of radius 1 associated with the norm
$N_{M^{-1}}=\sqrt{x^{\top}M^{-1}x}$.

###  A.3 An auxiliary inequality

In this Section, we provide an auxiliary lemma that is specific to the
framework considered in Section 2. It will be used in the proof of Theorem 1
and corresponds to an adaptation of Lemma 1 from Bach and Moulines (2013).

######  Lemma S1 (Auxiliary inequality on
$\sum_{k=1}^{K}\mathbb{E}[\|H_{F}^{1/2}\eta_{k}\|^{2}]/K$).

Under Assumptions 1 and 2.1, for any $K$ in $\mathbb{N}^{*}$ and any step-size
$\gamma\in\mathbb{R}^{+}$ s.t. $\gamma(R_{F}^{2}+2\mathcal{M}_{2})\leq 1$, the
sequence $(w_{k})_{k\in\mathbb{N}^{*}}$ produced by a setting such as in
Definition 1, verifies the following bound:
$\displaystyle\frac{1}{K}\sum_{k=0}^{K-1}\mathbb{E}[\|H_{F}^{1/2}(w_{k}-w_{*})\|^{2}]\leq\frac{\displaystyle\left\|\eta_{0}\right\|^{2}}{\displaystyle
2\gamma K(1-\gamma(R_{F}^{2}+2\mathcal{M}_{2}))}+\frac{\displaystyle
5\mathcal{A}\gamma}{\displaystyle 1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\,.$

Proof  Let $k$ in $\mathbb{N}^{*}$, we start writing that by Definition 1, we
have $w_{k}=w_{k-1}-\gamma\nabla F(w_{k-1})+\gamma\xi_{k}(\eta_{k-1})$. Thus
taking the squared norm and developing it, gives:

$\displaystyle\left\|\eta_{k}\right\|^{2}$
$\displaystyle=\left\|\eta_{k-1}\right\|^{2}-2\gamma\left\langle\eta_{k-1},\nabla
F(w_{k-1})-\xi_{k}(\eta_{k-1})\right\rangle+\gamma^{2}\left\|\nabla
F(w_{k-1})-\xi_{k}(\eta_{k-1})\right\|^{2}\,.$ (S4)

We need to bound the last term. By Definition 2, we have
$\xi_{k}(\eta_{k-1})=\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)+\xi_{k}^{\mathrm{add}}$,
hence using Inequality 1, we have:

$\displaystyle\left\|\nabla F(w_{k-1})-\xi_{k}(\eta_{k-1})\right\|^{2}$
$\displaystyle\leq 2\|\nabla
F(w_{k-1})-\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}+2\|\xi_{k}^{\mathrm{add}}\|^{2}\,,$

taking expectation w.r.t the $\sigma$-algebra $\mathcal{F}_{k-1}$, developping
$\left\|\nabla
F(w_{k-1})-\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\right\|^{2}$ and
because
$\mathbb{E}\left[\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]=0$ (the random fields
$(\xi_{k})_{k\in\mathbb{N}^{*}}$ are zero-centered, see Definition 1), we
have:

$\displaystyle\mathbb{E}\left[\left\|\nabla
F(w_{k-1})-\xi_{k}(\eta_{k-1})\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\qquad\leq 2\mathbb{E}\left[\|\nabla
F(w_{k-1})\|^{2}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]+2\mathbb{E}\left[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]+2\mathbb{E}\left[\|\xi_{k}^{\mathrm{add}}\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\,.$

Now, we use Definition 1 and Assumptions 1 and 2.1: it leads to:

$\displaystyle\mathbb{E}\left[\left\|\nabla
F(w_{k-1})-\xi_{k}(\eta_{k-1})\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\qquad\qquad\leq
2R_{F}^{2}\|H_{F}^{1/2}\eta_{k-1}\|^{2}+4\mathcal{M}_{2}\|H_{F}^{1/2}\eta_{k-1}\|^{2}+8\mathcal{A}+2\mathcal{A}$
$\displaystyle\qquad\qquad\leq
2(R_{F}^{2}+2\mathcal{M}_{2})\|H_{F}^{1/2}\eta_{k-1}\|^{2}+10\mathcal{A}\,.$

Because the sequence of random field $(\xi_{k})_{k\in\mathbb{N}^{*}}$ is zero-
centered (Definition 1), we have:

$\mathbb{E}\left[\left\langle\eta_{k-1},\nabla
F(w_{k-1})-\xi_{k}(\eta_{k-1})\right\rangle\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]=\left\langle\eta_{k-1},H_{F}\eta_{k-1}\right\rangle=\|H_{F}^{1/2}\eta_{k-1}\|^{2}\,,$

hence back to Equation S4, we obtain:

$\displaystyle\begin{split}\mathbb{E}\left[\left\|\eta_{k}\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]&\leq\left\|\eta_{k-1}\right\|^{2}-2\gamma(1-\gamma(R_{F}^{2}+2\mathcal{M}_{2}))\|H_{F}^{1/2}\eta_{k-1}\|^{2}+10\mathcal{A}\gamma^{2}\,.\end{split}$
(S5)

It follows that if $\gamma(R_{F}^{2}+2\mathcal{M}_{2})\leq 1$, summing the
previous bound and taking full expectation gives:

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left[\|H_{F}^{1/2}\eta_{k-1}\|^{2}\right]\leq\frac{\displaystyle\left\|\eta_{0}\right\|^{2}-\mathbb{E}\left\|\eta_{K}\right\|^{2}}{\displaystyle
2\gamma K(1-\gamma(R_{F}^{2}+2\mathcal{M}_{2}))}+\frac{\displaystyle
5\mathcal{A}\gamma}{\displaystyle 1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\,,$

which allows concluding.

###  A.4 Asymptotic results: central limit theorem for (LSA)

The demonstration of Proposition 1 uses the following theorem from Polyak and
Juditsky (1992) guaranteeing the asymptotic normality of the Polyak-Ruppert
iterate.

######  Theorem S1.

From Polyak and Juditsky (1992, see Theorem 1).

For $k$ in $\mathbb{N}^{*}$, we denote $\eta_{k}=w_{k}-w_{*}$ and we define
$w_{k}=w_{k-1}-\gamma_{k}\nabla F(w_{k-1})+\gamma_{k}\xi(\eta_{k-1})$. If we
assume that:

  * •

$\gamma_{k}\xrightarrow[k\rightarrow+\infty]{}0$ and
$\gamma_{k}^{-1}(\gamma_{k}-\gamma_{k+1})=\underset{k\to+\infty}{o}(\gamma_{k})$,

  * •

$F$ is strongly convex and $\left\|\nabla^{2}F\right\|_{\infty}<\infty$,

  * •

the convergence in probability of the conditional covariance to a matrix
$\Sigma$ holds, i.e., we have a.s.
$\mathbb{E}[\xi(\eta_{k-1})\xi(\eta_{k-1})^{\top}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]\xrightarrow[k\rightarrow+\infty]{\mathbb{P}}\Sigma\,.$

Then for any $K$ in $\mathbb{N}^{*}$, we have the asymptotic normality of
$(\sqrt{K}\eta_{K-1})_{K\in\mathbb{N}^{*}}$:

$\sqrt{K}\overline{\eta}_{K-1}\xrightarrow[K\rightarrow+\infty]{\mathcal{L}}\mathcal{N}(0,\Sigma^{*})\text{
with
}\Sigma^{\star}=\left\\{\nabla^{2}F\left(w_{*}\right)\right\\}^{-1}\Sigma\left\\{\nabla^{2}F\left(w_{*}\right)\right\\}^{-1}.$

Below we present our CLT that gives the asymptotic normality of
$(\sqrt{K}\eta_{K-1})_{K\in\mathbb{N}^{*}}$ in the case of strongly-convex
case and decreasing step size.

######  Proposition S1 (CLT for (LSA) in the strongly convex-case and
deacreasing step-size).

Under Assumptions 1 and 2, consider a sequence $(w_{k})_{k\in\mathbb{N}^{*}}$
produced in the setting of Definition 1 using a step-size
$(\gamma_{k})_{k\in\mathbb{N}^{*}}$ s.t. $\gamma_{k}=k^{-\alpha}$,
$\alpha\in(0,1)$. Then $(\eta_{K})_{K\geq 0}$ converges in $L^{2}$-norm to 0,
i.e. $\eta_{K}\xrightarrow[K\to+\infty]{L^{2}}0$. Furthermore,
$(\sqrt{K}\overline{\eta}_{K-1})_{K\geq 0}$ is asymptotically normal with mean
zero and covariance such that:
$\sqrt{K}\overline{\eta}_{K-1}\xrightarrow[K\to+\infty]{\mathcal{L}}\mathcal{N}(0,H_{F}^{-1}\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}).$

Proof

First, we have that in the case of decreasing step size s.t. for any $k$ in
$\mathbb{N}$, $\gamma_{k}=k^{-\alpha}$, we have:
$\eta_{K}\xrightarrow[K\to+\infty]{L^{2}}0$. This is a classical computation
for SGD with bounded variance (Assumptions 1 and 2.1.). Detailed computations
are for instance given in lectures notes of Bach (2022, pages 164-167 and
182), and Kushner and Yin (2003). To apply Theorem 1 from Polyak and Juditsky
(1992, recalled in Theorem S1), which gives the desired result, it suffices to
prove the convergence in probability of the covariance of the noise
$\xi_{k}(\eta_{k-1})$ towards $\mathfrak{C}_{\mathrm{ania}}$, as $k\to\infty$.

In the following, we show that
$\underset{k\to+\infty}{\lim}\mathbb{E}\left[\xi_{k}(\eta_{k-1})\xi_{k}(\eta_{k-1})^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\stackrel{{\scriptstyle\mathbb{P}}}{{=}}\mathfrak{C}_{\mathrm{ania}}$.
We start writing:

$\displaystyle\xi_{k}(\eta_{k-1})\xi_{k}(\eta_{k-1})^{\top}$
$\displaystyle=(\xi_{k}^{\mathrm{add}}-\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right))(\xi_{k}^{\mathrm{add}}-\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right))^{\top}$
$\displaystyle=(\xi_{k}^{\mathrm{add}})^{{\otimes
2}}-\xi_{k}^{\mathrm{add}}\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)^{\top}-\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)(\xi_{k}^{\mathrm{add}})^{\top}+\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)^{{\otimes
2}}\,.$

(i) First, from Definition 2, it flows that
$\mathbb{E}\left[\xi_{k}^{\mathrm{add}}\otimes\xi_{k}^{\mathrm{add}}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]=\mathfrak{C}_{\mathrm{ania}}$.

(ii) Second, we show that
$\mathbb{E}[\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)^{{\otimes
2}}\leavevmode\nobreak\ |\leavevmode\nobreak\ \mathcal{F}_{k-1}]$ converges to
$0$ in probability: it is sufficient to show that:
$\mathbb{E}[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)^{{\otimes
2}}\|_{F}\leavevmode\nobreak\ |\leavevmode\nobreak\
\mathcal{F}_{k-1}]\xrightarrow[k\to+\infty]{}0\,.$ To do so, we use the fact
that $\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)^{{\otimes
2}}\|_{F}=\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|_{2}^{2},\,$ then
with Item 2.2:
$\mathbb{E}[\|\xi_{k}^{\mathrm{mult}}(w-w_{*})\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]\leq\mathcal{M}_{1}\|H^{1/2}\eta_{k-1}\|+\mathcal{M}_{2}\|H^{1/2}\eta_{k-1}\|^{2}$.
And we have the result as we showed that
$\eta_{k-1}\xrightarrow[k\to+\infty]{L^{2}}0$.

(iii) Third, it remains to show that
$\mathbb{E}[\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)(\xi_{k}^{\mathrm{add}})^{\top}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]\xrightarrow[k\to+\infty]{L^{1}}0$. We
use the Cauchy-Schwarz inequality’s S3 for conditional expectation:

$\displaystyle\mathbb{E}\left[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)(\xi_{k}^{\mathrm{add}})^{\top}\|_{F}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]^{2}$
$\displaystyle=\mathbb{E}\left[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|_{2}\|(\xi_{k}^{\mathrm{add}})^{\top}\|_{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]^{2}$
$\displaystyle\leq\mathbb{E}\left[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}_{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\mathbb{E}\left[\|\xi_{k}^{\mathrm{add}}\|_{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\,.$

The sequence of random vectors $(\xi_{k}^{\mathrm{add}})_{k\in\mathbb{N}^{*}}$
is i.i.d., and moreover we have shown previously that
$\mathbb{E}[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$ tends to 0, hence
$\mathbb{E}[\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)(\xi_{k}^{\mathrm{add}})^{\top}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$ converges to $0$ in probability.
Consequently, we can state that $\mathbb{E}[\xi_{k}(\eta_{k-1})^{{\otimes
2}}\leavevmode\nobreak\ |\leavevmode\nobreak\
\mathcal{F}_{k-1}]\xrightarrow[k\to+\infty]{\mathbb{P}}\mathfrak{C}_{\mathrm{ania}}\,.$

##  Appendix B Generalization of Bach and Moulines (2013).

In this section, we give the demonstration of Theorem 1 which extends Theorem
1 from Bach and Moulines (2013); the demonstration is close to the original
one.

###  B.1 Proof principle

For $k$ in $\mathbb{N}^{*}$, the proof relies (1) on decomposing
$\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}]$ in two terms using the
Minkowski inequality S1 to make appear a recursion
$(\eta_{k}^{0})_{k\in\mathbb{N}^{*}}$ without multiplicative noise, and
another $(\alpha_{k})_{k\in\mathbb{N}^{*}}$ without additive noise, (2) on an
expansion of $\eta_{k}^{0}$ and $\overline{\eta}_{k}^{0}$ as polynomials in
$\gamma$, and (3) on using the Hölder-type Item 2.2 to bound $\alpha_{k}$. We
define the sequence $(\eta_{k}^{0})_{k\in\mathbb{N}^{*}}$ such that it
involves only an additive noise:

$\displaystyle\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}+\gamma\xi_{k}^{\mathrm{add}}\,.$ (S6)

Then, we decompose $\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}]$ in
the following way using Minkowski inequality S1:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}\right]\leq\left(\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}\right]^{1/2}+\mathbb{E}\left[\|H_{F}^{1/2}(\overline{\eta}_{K-1}-\overline{\eta}_{K-1}^{0})\|^{2}\right]^{1/2}\right)^{2}\,.$
(S7)

The goal is then to establish a bound for the two above quantities.

1\. Bounding $\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}]$.

The bound on $\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}]$ is
given in Lemma S2. For $k$ in $\mathbb{N}^{*}$, the proof relies on an
expansion of $\eta_{k}^{0}$ and $\overline{\eta}_{k}^{0}$ as polynomials in
$\gamma$. The recursion defining the sequence
$(\eta_{k}^{0})_{k\in\mathbb{N}^{*}}$ is $\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}+\gamma\xi_{k}^{\mathrm{add}}$. If we denote
$M_{i}^{k}=\left(\mathrm{I}_{d}-\gamma H_{F}\right)^{k-i}$ and
$M_{i}^{i-1}=\mathrm{I}_{d}$, we have:

$\eta_{k}^{0}=M_{1}^{k}\eta_{0}^{0}+\gamma\sum_{i=1}^{k}M_{i+1}^{k}\xi_{k}^{\mathrm{add}}\,.$

For $K$ in $\mathbb{N}^{*}$, it leads to
$\overline{\eta}_{K-1}^{0}=\frac{1}{K}\sum_{k=0}^{K-1}M_{1}^{k}\eta_{0}^{0}+\frac{\gamma}{K}\sum_{k=1}^{K-1}\left(\sum_{i=k}^{K}M_{k+1}^{i}\right)\xi_{k}^{\mathrm{add}}$,
and with Minkowski inequality S1 to:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}\right]^{1/2}\leq\mathbb{E}\left[\left\|\frac{H_{F}^{1/2}}{K}\sum_{k=0}^{K-1}M_{1}^{k}\eta_{0}^{0}\right\|^{2}\right]^{1/2}+\mathbb{E}\left[\left\|\frac{\gamma
H_{F}^{1/2}}{K}\sum_{k=1}^{K-1}\sum_{i=k}^{K}M_{k+1}^{i}\xi_{k}^{\mathrm{add}}\right\|^{2}\right]^{1/2}.$
(S8)

The left term depends only on initial conditions $\eta_{0}^{0}$ ($=\eta_{0}$)
and the right term depends only on the additive noise. This is why, in the
proof, we expend $\eta_{k-1}^{0}$ and $\overline{\eta}_{k-1}^{0}$ separately
for the noise process (i.e., when assuming $\eta_{0}=0$) and for the noise-
free process that depends only on the initial conditions (i.e. when assuming
that the additive noise $(\xi_{k}^{\mathrm{add}})_{k\in\mathbb{N}^{*}}$ is
uniformly equal to zero). In the end, the two bounds computed separately may
be added.

2\. Bounding
$\mathbb{E}[\|H_{F}^{1/2}(\overline{\eta}_{K-1}-\overline{\eta}_{K-1}^{0})\|^{2}]$.

The bound on
$\mathbb{E}[\|H_{F}^{1/2}(\overline{\eta}_{K-1}-\overline{\eta}_{K-1}^{0})\|^{2}]$
is given in Lemma S3. For $k$ in $\mathbb{N}^{*}$, the demonstration is based
on an exact expression of $\alpha_{k}=\eta_{k}-\eta_{k}^{0}$ and
$\overline{\alpha}_{k}$ computed by unrolling the recursion from $\alpha_{k}$
to $\alpha_{0}$. Because $\alpha_{0}=0$ and because there is no additive noise
involved in $\alpha_{k}$, we obtain for $K$ in $\mathbb{N}^{*}$, an expression
of $\overline{\alpha}_{K-1}$ that depends only on the multiplicative noise at
iteration $k$ in $\\{1,\cdots,K\\}$:

$\displaystyle\overline{\alpha}_{K-1}$
$\displaystyle=\frac{\gamma}{K}\sum_{k=1}^{K-1}(\mathrm{I}_{d}-(\mathrm{I}_{d}-\gamma
H_{F})^{K-k})(\gamma H_{F})^{-1}\xi_{k}^{\mathrm{mult}}(\eta_{k-1})\,.$

We then show (Equation S11) that bounding
$\mathbb{E}[\|H_{F}^{1/2}(\overline{\eta}_{K-1}-\overline{\eta}_{K-1}^{0})\|^{2}]$
leads to bound the following sum
$\frac{1}{K^{2}}\sum^{K-1}_{k=1}\mathbb{E}[\|H_{F}^{-1/2}\xi_{k}^{\mathrm{mult}}(\eta_{k-1})\|^{2}\mid\mathcal{F}_{k-1}]$,
and this bound is established using the Hölder-type Item 2.2; which concludes
this part of the proof.

Figure S1: Proof principle of Theorem S2

###  B.2 Two bounds

In this subsection, we give two lemmas that provide a bound on
$\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}]$ and
$\mathbb{E}[\|H_{F}^{1/2}(\overline{\eta}_{K-1}-\overline{\eta}_{K-1}^{0})\|^{2}]$.
These bounds are required due to the decomposition of
$\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}]$ done in Equation S7.

  * •

The bound on $\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{k}^{0}\|^{2}]$ is given
in Lemma S2. It is established by decomposing the noise process and the noise-
free process. The bound on the noise process comes from Lemma 2 (Bach and
Moulines, 2013) and involves the additive noise’s covariance
$\mathfrak{C}_{\mathrm{ania}}$.

  * •

The bound on
$\mathbb{E}[\|H_{F}^{1/2}(\overline{\eta}_{K}-\overline{\eta}_{K}^{0})\|^{2}]$
is established in Lemma S3.

Note that in order to demonstrate Lemma S3, we need to bound
$\sum_{k=1}^{K}\|H_{F}^{1/2}\eta_{k}\|^{2}/K$. This is done in Lemma S1 which
is an adaptation of Lemma 1 from Bach and Moulines (2013) to random
mechanisms. This auxiliary lemma holds for any kind of multiplicative noise –
linear or non-linear.

Below lemma provides a bound on
$\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{k}^{0}\|^{2}]$.

######  Lemma S2 (Bound on
$\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{k}^{0}\|^{2}]$).

Under the setting considered in Definition 1, under Assumption 1, for any $K$
in $\mathbb{N}^{*}$ and any step-size $\gamma\in\mathbb{R}^{+}$ s.t. $\gamma
R_{F}^{2}\leq 1$, the sequence $(\eta_{k}^{0})_{k\in\mathbb{N}^{*}}$ defined
in Equation S6 verifies the following bound:
$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}\right]^{1/2}\leq$
$\displaystyle\frac{1}{\sqrt{K}}\left(\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|}{\displaystyle\gamma\sqrt{K}}\wedge\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}\right)\,.$

Proof

The proof relies on the proof presented by Bach and Moulines (2013) and is
done separately for the noise process and for the noise-free process that
depends only on the initial condition. The bounds may then be added (see the
discussion in Subsection B.1).

Noise-free process.

As in section A.3 from Bach and Moulines (2013), we assume in this section
that the random fields $(\xi_{k}^{\mathrm{add}})_{k\in\mathbb{N}^{*}}$ is
uniformly equal to zero and that $\gamma R_{F}^{2}\leq 1$. We thus have for
any $k$ in $\mathbb{N}^{*}$ that $\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}$.

First inequality. By recursion, we have $\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})^{k}\eta_{0}^{0}$, averaging over $K$ in $\mathbb{N}^{*}$ and computing
the resulting geometric sum, we have:

$\displaystyle\overline{\eta}_{K-1}^{0}=\frac{\displaystyle 1}{\displaystyle
K}\sum_{k=0}^{K-1}(\mathrm{I}_{d}-\gamma
H_{F})^{k}\eta_{0}^{0}=\frac{1}{K}(\mathrm{I}_{d}-(\mathrm{I}_{d}-\gamma
H_{F})^{K-1})(\gamma H_{F})^{-1}\eta_{0}^{0}\preccurlyeq\frac{\displaystyle
1}{\displaystyle\gamma K}H_{F}^{-1}\eta_{0}^{0}.$

And because $\eta_{0}^{0}=\eta_{0}$, it gives
$\mathbb{E}\left[\left\langle\overline{\eta}_{K-1}^{0},H_{F}\overline{\eta}_{K-1}^{0}\right\rangle\right]\leq\frac{\|H_{F}^{1/2}\eta_{0}\|^{2}}{\gamma^{2}K^{2}}$.

Second inequality. From the expression of $\eta_{k}^{0}$ flows:

$\mathbb{E}[\|\eta_{k}^{0}\|^{2}]=\mathbb{E}[\|\eta_{k-1}^{0}\|^{2}]-2\gamma\left\langle\eta_{k-1}^{0},H_{F}\eta_{k-1}^{0}\right\rangle+\gamma^{2}\left\langle\eta_{k-1}^{0},H_{F}^{2}\eta_{k-1}^{0}\right\rangle\,.$

Considering that
$H_{F}\preccurlyeq\mathrm{Tr}\left(H_{F}\right)\mathrm{I}_{d}\preccurlyeq
R_{F}^{2}\mathrm{I}_{d}$ (Definition 1) and that $\gamma R_{F}^{2}\leq 1$,
because $\eta_{0}^{0}=\eta_{0}$, by convexity we have:
$\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}]\leq\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}[\|H_{F}^{1/2}\eta_{k-1}^{0}\|^{2}]\leq\frac{\left\|\eta_{0}\right\|^{2}}{\gamma
K}\,.$

Putting things together.

In the end, we take the minimum of the two above bounds and obtain that:

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}]\leq\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|^{2}}{\displaystyle\gamma^{2}K^{2}}\wedge\frac{\displaystyle\left\|\eta_{0}\right\|^{2}}{\displaystyle\gamma
K}\,.$ (S9)

Noise process.

We assume in this part that $\eta_{0}^{0}=\eta_{0}=0$. We apply Lemma 2 from
Bach and Moulines (2013) to $\eta_{k-1}^{0}$. This sequence of iterates has an
i.i.d. noise process $(\xi_{k}^{\mathrm{add}})_{k\in\mathbb{N}^{*}}$ which is
such that
$\mathbb{E}\left[\xi_{k}^{\mathrm{add}}\otimes\xi_{k}^{\mathrm{add}}\right]=\leavevmode\nobreak\
\mathfrak{C}_{\mathrm{ania}}$ (existence guaranteed by Assumption 1).
Therefore we have:

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}]\leq\frac{\displaystyle\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}{\displaystyle
K}\,.$ (S10)

Putting things together. We now take results derived from the part without
noise and the part with noise, and we get from Minkowski inequality:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}\right]^{1/2}\leq$
$\displaystyle\frac{1}{\sqrt{K}}\left(\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|}{\displaystyle\gamma\sqrt{K}}\wedge\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}\right)\,.$

Below lemma provides a bound on
$\mathbb{E}[\|H_{F}^{1/2}(\overline{\eta}_{K}-\overline{\eta}_{K}^{0})\|^{2}]$.

######  Lemma S3 (Bound on
$\mathbb{E}[\|H_{F}^{1/2}(\overline{\eta}_{K}-\overline{\eta}_{K}^{0})\|^{2}]$).

Under the setting considered in Definition 1 with $\mu>0$, under Assumption 1
, under Items 2.1 and 2.2, for any $K$ in $\mathbb{N}^{*}$ and any step-size
$\gamma\in\mathbb{R}^{+}$ s.t. $\gamma(R_{F}^{2}+2\mathcal{M}_{2})<1$, the
sequence $(\overline{\eta}_{k}-\overline{\eta}_{k}^{0})_{k\in\mathbb{N}^{*}}$
verifies the following bound:
$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}(\overline{\eta}_{K}-\overline{\eta}_{K}^{0})\|^{2}\right]^{1/2}]$
$\displaystyle\leq\frac{1}{\sqrt{K}}\Bigg{(}\sqrt{\mathcal{M}_{1}\mu^{-1}}\left(\frac{\displaystyle
5\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)^{1/4}$
$\displaystyle\qquad\qquad+\sqrt{\mathcal{M}_{2}\mu^{-1}}\left(\frac{\displaystyle
15\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)^{1/2}\Bigg{)}\,.$

######  Remark S1.

To demonstrate Lemma S3, we use the Hölder-type Item 2.2. This is why we
obtain a term with a square root in the bound.

Proof

Let $k$ in $\mathbb{N}^{*}$, we denote $\alpha_{k}=\eta_{k}-\eta_{k}^{0}$,
with $\eta_{k}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}+\gamma\xi_{k}(\eta_{k-1})$ and
$\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}+\gamma\xi_{k}^{\mathrm{add}}$. First, we write the exact
expression of $\alpha_{k-1}$:

$\displaystyle\alpha_{k}$ $\displaystyle=(\mathrm{I}_{d}-\gamma
H_{F})\alpha_{k-1}+\gamma(\xi_{k}(\eta_{k-1})-\xi_{k}^{\mathrm{add}})$
$\displaystyle=(\mathrm{I}_{d}-\gamma
H_{F})^{k}\alpha_{0}+\gamma\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}(\xi_{i}(\eta_{i-1})-\xi_{i}^{\mathrm{add}})\,,$

and because $\eta_{0}^{0}=\eta_{0}$, it follows that
$\alpha_{0}=\eta_{0}-\eta_{0}^{0}=0$. Averaging over $K$ in $\mathbb{N}^{*}$,
we have the exact expression of $\overline{\alpha}_{K-1}$:

$\displaystyle\overline{\alpha}_{K-1}$
$\displaystyle=\frac{\gamma}{K}\sum_{k=0}^{K-1}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}(\xi_{i}(\eta_{i-1})-\xi_{i}^{\mathrm{add}}))$
$\displaystyle=\frac{\gamma}{K}\sum_{i=1}^{K-1}\left(\sum_{k=i}^{K-1}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\right)(\xi_{i}(\eta_{i-1})-\xi_{i}^{\mathrm{add}}))\,.$

Computing the geometric sum results in:

$\displaystyle\overline{\alpha}_{K-1}$
$\displaystyle=\frac{\gamma}{K}\sum_{k=1}^{K-1}(\mathrm{I}_{d}-(\mathrm{I}_{d}-\gamma
H_{F})^{K-k})(\gamma
H_{F})^{-1}(\xi_{k}(\eta_{k-1})-\xi_{k}^{\mathrm{add}})\,.$

And because for any $k$ in $\mathbb{N}$, $0\preccurlyeq(\mathrm{I}_{d}-\gamma
H_{F})^{k}\preccurlyeq\mathrm{I}_{d}$, we obtain:

$\overline{\alpha}_{K-1}\preccurlyeq\frac{1}{K}\sum_{k=1}^{K-1}H_{F}^{-1}(\xi_{k}(\eta_{k-1})-\xi_{k}^{\mathrm{add}})\,,$

hence
$\|H_{F}^{1/2}\overline{\alpha}_{K-1}\|^{2}=\|\frac{1}{K}\sum_{k=1}^{K-1}H_{F}^{-1/2}(\xi_{k}(\eta_{k-1})-\xi_{k}^{\mathrm{add}})\|^{2}$.
We take full expectation, because for any $k$ in $\mathbb{N}^{*}$, by
Definitions 1 and 2,
$\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)=\xi_{k}(\eta_{k-1})-\xi_{k}^{\mathrm{add}}$
is $\mathcal{F}_{k}$-measurable and
$\mathbb{E}\left[\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]=0$, we can unroll the
sum and we have in the end that the variance of the sum is the sum of
variances:

$\displaystyle\mathbb{E}\left[\left\|H_{F}^{1/2}\overline{\alpha}_{K-1}\right\|^{2}\right]\leq\frac{1}{K^{2}}\sum^{K-1}_{k=1}\mathbb{E}\left[\left\|H_{F}^{-1/2}\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\,.$ (S11)

Computing
$\mathbb{E}[\|H_{F}^{-1/2}\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$ for $k$ in $\mathbb{N}$, we first
have:

$\displaystyle\|H_{F}^{-1/2}\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}\leq{|\kern-1.07639pt|\kern-1.07639pt|H_{F}^{-1/2}|\kern-1.07639pt|\kern-1.07639pt|}^{2}\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}\,,$

where we used Inequality 2. Because $H_{F}$ is a symmetric semi-positive
matrix, we have
${|\kern-1.07639pt|\kern-1.07639pt|H_{F}^{-1/2}|\kern-1.07639pt|\kern-1.07639pt|}^{2}=1/\mu$,
hence:
$\|H_{F}^{-1/2}\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}\leq\mu^{-1}\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}$.
Taking expectation conditionally to the $\sigma$-algebra $\mathcal{F}_{k-1}$
and invoking Item 2.2 gives:

$\displaystyle\begin{split}\mathbb{E}[\|H_{F}^{-1/2}\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]\leq\mu^{-1}(\mathcal{M}_{1}\|H_{F}^{1/2}\eta_{k-1}\|+3\mathcal{M}_{2}\|H_{F}^{1/2}\eta_{k-1}\|^{2})\,.\end{split}$
(S12)

Combining equations S11 and S12, we obtain:

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\overline{\alpha}_{K-1}\|^{2}]$
$\displaystyle\leq\frac{\mathcal{M}_{1}}{\mu
K^{2}}\sum^{K-1}_{k=1}\mathbb{E}[\|H_{F}^{1/2}\eta_{k-1}\|]+\frac{3\mathcal{M}_{2}}{\mu
K^{2}}\sum^{K-1}_{k=1}\mathbb{E}[\|H_{F}^{1/2}\eta_{k-1}\|^{2}]\,.$

Now using Jensen’s inequality for concave function allows us to write:

$\displaystyle\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}[\|H_{F}^{1/2}(w-w_{*})\|]\leq\frac{1}{K}\sum_{k=1}^{K}\sqrt{\mathbb{E}[\|H_{F}^{1/2}(w-w_{*})\|^{2}]}\leq\sqrt{\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}[\|H_{F}^{1/2}(w-w_{*})\|^{2}]}\,,$

thus we have:

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\overline{\alpha}_{K-1}\|^{2}]$
$\displaystyle\leq\frac{\mathcal{M}_{1}}{\mu
K}\sqrt{\frac{1}{K}\sum^{K-1}_{k=1}\mathbb{E}[\|H_{F}^{1/2}\eta_{k-1}\|^{2}]}+\frac{3\mathcal{M}_{2}}{\mu
K^{2}}\sum^{K-1}_{k=1}\mathbb{E}[\|H_{F}^{1/2}\eta_{k-1}\|^{2}]\,.$

Using Lemma S1 (with $\eta_{0}=0$), we finally obtain:

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\overline{\alpha}_{K-1}\|^{2}]$
$\displaystyle\leq\frac{1}{K}\left(\mathcal{M}_{1}\mu^{-1}\sqrt{\frac{\displaystyle
5\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}}+\frac{\displaystyle
15\mathcal{A}\gamma\mathcal{M}_{2}\mu^{-1}}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)\,.$

In the end, we take the square root (and use that for any $a,b$ in
$\mathbb{R}_{+}$, $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$) which allows concluding:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}(\overline{\eta}_{K}-\overline{\eta}_{K}^{0})\|^{2}\right]^{1/2}$
$\displaystyle\leq\frac{1}{\sqrt{K}}\Bigg{(}\sqrt{\mathcal{M}_{1}\mu^{-1}}\left(\frac{\displaystyle
5\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)^{1/4}$
$\displaystyle\qquad\qquad+\sqrt{\mathcal{M}_{2}\mu^{-1}}\left(\frac{\displaystyle
15\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)^{1/2}\Bigg{)}\,.$

###  B.3 Final theorem

In this section, we gather the pieces of proof required to demonstrate Theorem
1.

######  Theorem S2 (Non-linear multiplicative noise).

Under Assumptions 2 and 1, considering any constant step-size $\gamma$ such
that $\gamma(R_{F}^{2}+2\mathcal{M}_{2})\leq 1/2$, then for any $K$ in
$\mathbb{N}^{*}$, the sequence $(w_{k})_{k\in\mathbb{N}^{*}}$ produced by a
setting such as in Definition 1 verifies the following bound:
$\displaystyle\mathbb{E}[F(\overline{w}_{K-1})-F(w_{*})]$
$\displaystyle\leq\frac{1}{2K}\Bigg{(}\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|}{\displaystyle\gamma\sqrt{K}}\wedge\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}+\left(10\mathcal{A}\gamma\right)^{1/4}\sqrt{\mathcal{M}_{1}\mu^{-1}}$
$\displaystyle\qquad\qquad+\left(30\mathcal{A}\gamma\right)^{1/2}\sqrt{\mathcal{M}_{2}\mu^{-1}}\Bigg{)}^{2}\,.$

Proof

As explained in the discussion in Subsection B.1 (Equation S7), we define the
sequence $(\eta_{k}^{0})_{k\in\mathbb{N}^{*}}$ which involves only an additive
noise $\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}+\gamma\xi_{k}^{\mathrm{add}}$. Then, we decompose
$\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|]$ using Minkowski’s
inequality S1:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}\right]\leq\left(\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}\right]^{1/2}+\mathbb{E}\left[\|H_{F}^{1/2}(\overline{\eta}_{K-1}-\overline{\eta}_{K-1}^{0})\|^{2}\right]^{1/2}\right)^{2}\,.$
(S13)

First term.

To bound the first term, we use Lemma S2 which gives:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}\right]^{1/2}\leq$
$\displaystyle\frac{1}{\sqrt{K}}\left(\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|}{\displaystyle\gamma\sqrt{K}}\wedge\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}\right)\,.$

Second term.

From Lemma S3, we have:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}(\overline{\eta}_{K}-\overline{\eta}_{K}^{0})\|^{2}\right]^{1/2}$
$\displaystyle\leq\frac{1}{\sqrt{K}}\Bigg{(}\sqrt{\mathcal{M}_{1}\mu^{-1}}\left(\frac{\displaystyle
5\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)^{1/4}$
$\displaystyle\qquad\qquad+\sqrt{\mathcal{M}_{2}\mu^{-1}}\left(\frac{\displaystyle
15\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)^{1/2}\Bigg{)}\,.$

Final bound. Hence, back to Equation S13, we get:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}\right]^{1/2}\leq$
$\displaystyle\frac{1}{\sqrt{K}}\Bigg{(}\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|}{\displaystyle\gamma\sqrt{K}}\wedge\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}$
$\displaystyle\qquad+\sqrt{\mathcal{M}_{1}\mu^{-1}}\left(\frac{\displaystyle
5\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)^{1/4}$
$\displaystyle\qquad+\sqrt{\mathcal{M}_{2}\mu^{-1}}\left(\frac{\displaystyle
15\mathcal{A}\gamma}{\displaystyle
1-\gamma(R_{F}^{2}+2\mathcal{M}_{2})}\right)^{1/2}\Bigg{)}\,,$

and considering $\gamma(R_{F}^{2}+2\mathcal{M}_{2})\leq 1/2$, it concludes the
proof because
$\mathbb{E}[F(\overline{w}_{K-1})-F(w_{*})]=\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}]/2$:

$\displaystyle\mathbb{E}[F(\overline{w}_{K-1})-F(w_{*})]$
$\displaystyle\leq\frac{1}{2K}\Bigg{(}\frac{\displaystyle\|H_{F}^{-1/2}\eta_{0}\|}{\displaystyle\gamma\sqrt{K}}\wedge\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}+\left(10\mathcal{A}\gamma\right)^{1/4}\sqrt{\mathcal{M}_{1}\mu^{-1}}$
$\displaystyle\qquad\qquad+\left(30\mathcal{A}\gamma\right)^{1/2}\sqrt{\mathcal{M}_{2}\mu^{-1}}\Bigg{)}^{2}\,.$

##  Appendix C Generalisation of Bach and Moulines (2013) for linear
multiplicative noise.

In this Section, we give the demonstration of Theorem 2 which extends Theorem
1 from Bach and Moulines (2013) to the case of linear multiplicative noise.
The demonstration follows the same steps as the one given by Bach and Moulines
(2013). The minor differences lie in the generality of the form of the
multiplicative noise in our approach. Bach and Moulines (2013) only analyse
LMS algorithm, while we here consider (LSA) with assumptions on the linear
multiplicative noise process. Moreover, our theorem decomposes into 3 terms
instead of 2.

###  C.1 Proof principle

For $k$ in $\mathbb{N}^{*}$, the proof relies on an expansion of $\eta_{k}$
and $\overline{\eta}_{k}$ as polynomials in $\gamma$. Because we consider a
linear multiplicative noise, there exists a matrix $\Xi_{k}$ in
$\mathbb{R}^{d\times d}$ s.t. for any $z$ in $\mathbb{R}^{d}$,
$\xi_{k}^{\mathrm{mult}}(z)=\Xi_{k}z$ (Assumption 3); hence the recursion
defined in Definition 1 can be rewritten as:

$\eta_{k}=\eta_{k-1}-\gamma\nabla
F(\eta_{k-1})+\gamma\xi_{k}^{\mathrm{mult}}(\eta_{k-1})+\gamma\xi_{k}^{\mathrm{add}}=(\mathrm{I}_{d}-\gamma
H_{F}+\gamma\Xi_{k})\eta_{k-1}+\gamma\xi_{k}^{\mathrm{add}}\,.$

We denote $M_{i}^{k}=\left(\mathrm{I}_{d}-\gamma
H_{F}+\gamma\Xi_{k}\right)\cdots\left(\mathrm{I}_{d}-\gamma
H_{F}+\gamma\Xi_{i}\right)$ and $M_{i}^{i-1}=\mathrm{I}_{d}$, then we have
that
$\eta_{k}=M_{1}^{k}\eta_{0}+\gamma\sum_{i=1}^{k}M_{i+1}^{k}\xi_{k}^{\mathrm{add}}.$

For $K$ in $\mathbb{N}^{*}$, it leads to
$\overline{\eta}_{K-1}=\frac{1}{K}\sum_{k=0}^{K-1}M_{1}^{k}\eta_{0}+\frac{\gamma}{K}\sum_{k=1}^{K-1}\left(\sum_{i=k}^{K}M_{k+1}^{i}\right)\xi_{k}^{\mathrm{add}}$,
and with Minkowski’s inequality S1 to:

$\displaystyle\sqrt{\mathbb{E}\left[\left\|H_{F}^{1/2}\overline{\eta}_{K-1}\right\|^{2}\right]}\leq\mathbb{E}\left[\left\|\frac{H_{F}^{1/2}}{K}\sum_{k=0}^{K-1}M_{1}^{k}\eta_{0}\right\|^{2}\right]^{1/2}+\mathbb{E}\left[\left\|\frac{\gamma
H_{F}^{1/2}}{K}\sum_{k=1}^{K-1}\sum_{i=k}^{K}M_{k+1}^{i}\xi_{k}^{\mathrm{add}}\right\|^{2}\right]^{1/2}.$
(S14)

The left term depends only on initial conditions and the right term depends
only on the noise process.

This is why, in the proof, we expend $\eta_{k-1}$ and $\overline{\eta}_{k-1}$
separately for the noise process (i.e., when assuming $\eta_{0}=0$) and for
the noise-free process that depends only on the initial conditions (i.e. when
assuming that the additive noise
$(\xi_{k}^{\mathrm{add}})_{k\in\mathbb{N}^{*}}$ is uniformly equal to zero).
In the end, the two bounds computed separately may be added.

To study the noise process, inspiring from Bach and Moulines (2013), we define
the following sequence:

$\left\\{\begin{aligned} &\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}+\gamma\xi_{k}^{\mathrm{add}}\\\
&\eta_{k}^{r}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{r}+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r-1}\right)\qquad\text{with}\qquad\forall
r\geq 0\,,\eta_{0}^{r}=0\,.\end{aligned}\right.$ (S15)

Then, we decompose $\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}]$ in
the following way using Minkowski’s inequality S1:

$\displaystyle\sqrt{\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}\right]}\leq\mathbb{E}[\|H_{F}^{1/2}\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i}\|^{2}]^{1/2}+\mathbb{E}[\|H_{F}^{1/2}(\overline{\eta}_{K-1}-\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i})\|^{2}]^{1/2}.$

The goal is then to establish a bound for the two above quantities.

Figure S2: Proof principle of Theorem S3.

###  C.2 Lemmas for the noise process

In this Subsection, we provide lemmas for the noise process, and thus we
suppose that $\eta_{0}=0$. The noise-free process is later considered in
Subsection C.3 and puts together with the results of the coming Subsection.
The sketch of the proof relies on establishing two bounds.

  * •

For $r,k$ in $\mathbb{N}\times\mathbb{N}^{*}$, noting
$\alpha_{k}^{r}=\eta_{k}-\sum_{i=0}^{r}\eta_{k}^{i}$, the first one is a bound
on $\mathbb{E}[\|H_{F}^{1/2}\overline{\alpha}_{K-1}^{r}\|^{2}]$ that tends to
zero when $r$ tends to $+\infty$.

  * •

The second one is on
$\sum_{i=0}^{r}\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{i}\|^{2}]$ and
is established using Lemma 2 from (Bach and Moulines, 2013). It will
correspond to the final variance term and it involves the additive noise’s
covariance $\mathfrak{C}_{\mathrm{ania}}$.

In the following, we provide Lemmas S6, S5 and S4. Let $r,k$ in
$\mathbb{N}\times\mathbb{N}^{*}$.

  * •

Lemma S4 builds a recursive expression of
$\alpha_{k}^{r}=\eta_{k}-\sum_{i=0}^{r}\eta_{k}^{i}$.

  * •

Lemma S5 provides a bound on
$\mathbb{E}[\|H_{F}^{1/2}\overline{\alpha}_{K-1}^{r}\|^{2}]$ which involves
$\mathbb{E}\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\|^{2}$.

  * •

Lemma S6 bounds the covariance of $\eta_{k-1}^{r}$, this result will be
necessary when computing the expectation of
$\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)^{{\otimes 2}}$.

Below, we provide the lemma that builds a recursive expression of
$\eta_{k}-\sum_{i=0}^{r}\eta_{k}^{i}$, with $k,r$ in $\mathbb{N}^{*}$.

######  Lemma S4 (A recursion on $\eta_{k}-\sum_{i=0}^{r}\eta_{k}^{i}$).

Under the setting given in Definition 1, considering that
$\xi^{\mathrm{mult}}_{k}\left(\cdot\right)$ is linear (Assumption 3), for any
$k$ in $\mathbb{N}^{*}$ and any step-size $\gamma>0$, considering
$(\eta_{k}^{r})_{r\in\mathbb{N}}$ as given by Equation S15, denoting for $r$
in $\mathbb{N}$, $\alpha_{k}^{r}=\eta_{k}-\sum_{i=0}^{r}\eta_{k}^{i}$, we have
the following recursive expression for the sequence of iterate
$(\alpha_{k}^{r})_{r\in\mathbb{N}}$: $\displaystyle\forall r\geq
0,\alpha_{k}^{r}=(\mathrm{I}_{d}-\gamma
H_{F})\alpha_{k-1}^{r}+\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\,.$

Proof  Let $k$ in $\mathbb{N}^{*}$, the proof is done by recursion. For $r=0$,
by Definitions 1 and 2, we have $\eta_{k}=\eta_{k-1}-\gamma\nabla
F(w_{k-1})+\gamma\xi_{k}(\eta_{k-1})=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}+\gamma\xi_{k}^{\mathrm{add}}+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)$,
which gives:

$\displaystyle\alpha_{k}^{0}=\eta_{k}-\eta_{k}^{0}$
$\displaystyle=\bigg{\\{}(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}+\gamma\xi_{k}^{\mathrm{add}}+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)\bigg{\\}}-\bigg{\\{}(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}+\gamma\xi_{k}^{\mathrm{add}}\bigg{\\}}$
$\displaystyle=(\mathrm{I}_{d}-\gamma
H_{F})(\eta_{k-1}-\eta_{k-1}^{0})+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}\right)$
$\displaystyle=(\mathrm{I}_{d}-\gamma
H_{F})(\eta_{k-1}-\eta_{k-1}^{0})+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}-\eta_{k-1}^{0}\right)+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{0}\right)\,,$

which is possible because $\xi_{k}^{\mathrm{mult}}$ is linear (Assumption 3).
To go from $r$ to $r+1$, we have
$\alpha_{k}^{r+1}=\eta_{k}-\sum_{i=0}^{r+1}\eta_{k}^{i}=\eta_{k}-\sum_{i=0}^{r}\eta_{k}^{i}-\eta_{k}^{r+1}$.
Then by definition of $\eta_{k}^{r+1}$ and using the hypothesis:

$\displaystyle\alpha_{k}^{r+1}$ $\displaystyle=(\mathrm{I}_{d}-\gamma
H_{F})\left(\eta_{k-1}-\sum_{i=0}^{r}\eta_{k-1}^{i}\right)+\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}-\sum_{i=0}^{r}\eta_{k-1}^{i}\right)+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)$
$\displaystyle\qquad-(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{r+1}-\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)$
$\displaystyle=(\mathrm{I}_{d}-\gamma
H_{F})\left(\eta_{k-1}-\sum_{i=0}^{r+1}\eta_{k-1}^{i}\right)+\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}-\sum_{i=0}^{r+1}\eta_{k-1}^{i}\right)+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r+1}\right)\,,$

again by linearity. This concludes the proof.

The next lemma is the adaptation to our settings of Lemma 1 from Bach and
Moulines (2013). We give a bound on
$\mathbb{E}[\|H_{F}^{1/2}\overline{\alpha}_{K-1}^{r}\|^{2}]$ with a quantity
that tends to $0$. This result will be used in the final demonstration of
Theorem S3.

######  Lemma S5 (Bound on $\eta_{K}-\sum_{i=0}^{r}\eta_{K}^{i}$).

Under the setting given in Definition 1, considering that
$\xi_{k}^{\mathrm{mult}}$ is linear (Assumption 3), for any $r,K$ in
$\mathbb{N}\times\mathbb{N}^{*}$ and any step-size $\gamma$ s.t.
$\gamma(R_{F}^{2}+\mathcal{M}_{2})\leq 1$, the recursion
$\alpha_{K}^{r}=\eta_{K}-\sum_{i=0}^{r}\eta_{K}^{i}$ verifies the following
bound: $\displaystyle\forall r\geq
0,(1-\gamma(R_{F}^{2}+\mathcal{M}_{2}))\mathbb{E}\left\langle\overline{\alpha}_{K-1}^{r},H_{F}\overline{\alpha}_{K-1}^{r}\right\rangle\leq\frac{\gamma}{K}\sum_{k=1}^{K}\mathbb{E}\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\|^{2}\,.$

Proof  Let $r,k$ in $\mathbb{N}\times\mathbb{N}^{*}$, we denote
$\alpha_{k}^{r}=\eta_{k}-\sum_{i=0}^{r}\eta_{k}^{i}$, then we have shown in
Lemma S4 that:

$\displaystyle\alpha_{k}^{r}=(\mathrm{I}_{d}-\gamma
H_{F})\alpha_{k-1}^{r}+\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)+\gamma\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\,.$

Taking the squared norm and developing it:

$\displaystyle\left\|\alpha_{k}^{r}\right\|^{2}$
$\displaystyle=\left\|\alpha_{k-1}^{r}\right\|^{2}+2\gamma\left\langle\alpha_{k-1}^{r},\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)+\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)-H_{F}\alpha_{k-1}^{r}\right\rangle$
$\displaystyle\qquad+\gamma^{2}\|\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)+\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)-H_{F}\alpha_{k-1}^{r}\|^{2}\,,$

and developing the last term with Inequality 1 leads to:

$\displaystyle\left\|\alpha_{k}^{r}\right\|^{2}$
$\displaystyle\leq\left\|\alpha_{k-1}^{r}\right\|^{2}+2\gamma\left\langle\alpha_{k-1}^{r},\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)+\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)-H_{F}\alpha_{k-1}^{r}\right\rangle$
$\displaystyle\qquad+2\gamma^{2}\bigg{\\{}\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\|^{2}+\|H_{F}\alpha_{k-1}^{r}-\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)\|^{2}\bigg{\\}}\,.$

Because $\alpha_{k-1}^{r}$ is $\mathcal{F}_{k-1}$-measurable and
$\mathbb{E}[\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]=0$ (expectation of
$\xi^{\mathrm{mult}}_{k}\left(\cdot\right)$ is zero, see Definitions 2 and 1),
taking expectation w.r.t. the $\sigma$-algebra $\mathcal{F}_{k-1}$, using
Assumption 3 and again Definition 1 gives:

$\displaystyle\mathbb{E}[\|H_{F}\alpha_{k-1}^{r}-\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$
$\displaystyle=\mathbb{E}[\|H_{F}\alpha_{k-1}^{r}\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$
$\displaystyle\qquad+\mathbb{E}[\|\xi^{\mathrm{mult}}_{k}\left(\alpha_{k-1}^{r}\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$
$\displaystyle\leq(R_{F}^{2}+\mathcal{M}_{2})\|H_{F}^{1/2}\alpha_{k-1}^{r}\|^{2}\,.$

Hence:

$\displaystyle\mathbb{E}[\|\alpha_{k}^{r}\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$
$\displaystyle\leq\|\alpha_{k-1}^{r}\|^{2}-2\gamma(1-\gamma(R_{F}^{2}+\mathcal{M}_{2}))\left\langle\alpha_{k-1}^{r},H_{F}\alpha_{k-1}^{r}\right\rangle$
$\displaystyle\qquad+2\gamma^{2}\mathbb{E}[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]\,,$

which gives when taking full expectation and averaging over $K$ in
$\mathbb{N}^{*}$:

$\displaystyle(1-\gamma(R_{F}^{2}+\mathcal{M}_{2}))\frac{1}{K}\sum_{k=1}^{K}\mathbb{E}\left\langle\alpha_{k-1}^{r},H_{F}\alpha_{k-1}^{r}\right\rangle$
$\displaystyle\leq\frac{1}{2\gamma}(\left\|\alpha_{0}^{r}\right\|^{2}-\left\|\alpha_{k-1}^{r}\right\|^{2})$
$\displaystyle\qquad+\frac{\gamma}{K}\sum_{k=1}^{K}\mathbb{E}[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\|^{2}]\,,$

and by convexity
$\left\langle\overline{\alpha}_{K-1}^{r},H\overline{\alpha}_{K-1}^{r}\right\rangle\leqslant\frac{1}{K}\sum_{k=1}^{K}\left\langle\alpha_{k-1}^{r},H_{F}\alpha_{k-1}^{r}\right\rangle$,
which allows to conclude as $\alpha_{0}^{r}=0$.

In below lemma, we bound
$\mathbb{E}\left[\eta_{k-1}^{r}\otimes\eta_{k-1}^{r}\right]$ for $r,k$ in
$\mathbb{N}\times\mathbb{N}^{*}$. It is required because we will use Lemma 2
from Bach and Moulines (2013) and apply it to the sequence
$(\eta_{k-1}^{r})_{k\in\mathbb{N}^{*},r\in\mathbb{N}}$. The noise process of
this sequence is equal to
$\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r-1}\right)$; and computing the
expectation of its covariance involves knowing
$\mathbb{E}\left[\eta_{k-1}^{r}\otimes\eta_{k-1}^{r}\right]$.

######  Lemma S6 (Bounding the covariance of $\eta_{k-1}^{r}$).

Under the setting in Definition 1, under Assumptions 3, 4 and 1, i.e.
considering that $\xi^{\mathrm{mult}}_{k}\left(\cdot\right)$ is linear, for
any $K$ in $\mathbb{N}^{*}$, any step-size $\gamma>0$, and for any $r\geq 0$,
we have the following bound on the covariance of $\eta_{k-1}^{r}$:
$\displaystyle\mathbb{E}\left[\eta_{k-1}^{r}\otimes\eta_{k-1}^{r}\right]\preccurlyeq\gamma^{r+1}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r}\mathrm{I}_{d}\,.$

Proof

Let $r>0$, we first prove by recursion that we have:

$\forall k>0\,,\eta_{k}^{r+1}=\gamma\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\xi^{\mathrm{mult}}_{i}(\eta_{i-1}^{r})\,.$

For $k=0$, we indeed have $\eta^{r+1}_{0}=0$. To go from $k$ to $k+1$:

$\displaystyle\eta_{k+1}^{r+1}$ $\displaystyle=(\mathrm{I}_{d}-\gamma
H_{F})\eta^{r+1}_{k}+\gamma\xi^{\mathrm{mult}}_{k+1}(\eta_{k}^{r})\qquad\text{by
definition,}$ $\displaystyle=\gamma\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\xi^{\mathrm{mult}}_{i}(\eta_{i-1}^{r})+\gamma(\mathrm{I}_{d}-\gamma
H_{F})^{(k+1)-(k+1)}\xi_{k+1}^{\mathrm{mult}}(\eta_{k}^{r})\,,$

by hypothesis, which allows concluding.

We now prove by recursion the main result of the lemma.

Initialization. For $r=0$, by definition, we have
$\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}+\gamma\xi_{k}^{\mathrm{add}}$, unrolling the sum gives
$\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})^{k}\eta_{0}^{0}+\gamma\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\xi_{i}^{\mathrm{add}}$. Because we consider $\eta_{0}^{0}=0$ and
given that the sequence of noise $(\xi_{i}^{\mathrm{add}})_{i\in\llbracket
1,k\rrbracket}$ is independent at each iterations, we have:

$\displaystyle\mathbb{E}\left[\eta_{k}^{0}\otimes\eta_{k}^{0}\right]$
$\displaystyle=\gamma^{2}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\mathbb{E}\left[\xi_{i}^{\mathrm{add}}\otimes\xi_{i}^{\mathrm{add}}\right](\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\,.$

Because the sequence of additive noise
$(\xi_{i}^{\mathrm{add}})_{i\in\mathbb{N}^{*}}$is i.i.d., for any $i$ in
$\\{1,\cdots,k\\}$, we have that
$\mathbb{E}\left[\xi_{i}^{\mathrm{add}}\otimes\xi_{i}^{\mathrm{add}}\right]=\mathfrak{C}_{\mathrm{ania}}\preccurlyeq\Sha_{\mathrm{add}}H_{F}$
(Item 4.1), hence:

$\displaystyle\mathbb{E}\left[\eta_{k}^{0}\otimes\eta_{k}^{0}\right]$
$\displaystyle\preccurlyeq\gamma^{2}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\Sha_{\mathrm{add}}H_{F}(\mathrm{I}_{d}-\gamma H_{F})^{k-i}\,.$

These matrices commute:

$\displaystyle\mathbb{E}\left[\eta_{k}^{0}\otimes\eta_{k}^{0}\right]$
$\displaystyle\preccurlyeq\gamma^{2}\Sha_{\mathrm{add}}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{2k-2i}H_{F}\,,\leavevmode\nobreak\ \text{and because it is a geometric
sum:}$
$\displaystyle\preccurlyeq\gamma^{2}\Sha_{\mathrm{add}}\left(\mathrm{I}_{d}-(\mathrm{I}_{d}-\gamma
H_{F})^{2k-2}\right)\left(\mathrm{I}_{d}-(\mathrm{I}_{d}-\gamma
H_{F})^{2}\right)^{-1}H_{F}$
$\displaystyle\preccurlyeq\gamma^{2}\Sha_{\mathrm{add}}\left(\mathrm{I}_{d}-(\mathrm{I}_{d}-\gamma
H_{F})^{2k-2}\right)\left(2\gamma H_{F}-\gamma^{2}H_{F}^{2}\right)^{-1}H_{F}$
$\displaystyle\preccurlyeq\gamma\Sha_{\mathrm{add}}H_{F}^{-1}H_{F}\qquad\text{because
$\gamma H_{F}\preccurlyeq\mathrm{I}_{d}$,}$
$\displaystyle\preccurlyeq\gamma\Sha_{\mathrm{add}}\mathrm{I}_{d}\,.$

Recursion. Let $r\geq 0$, to go from $r$ to $r+1$, we start writing:

$\displaystyle\eta_{k}^{r+1}\otimes\eta_{k}^{r+1}$
$\displaystyle=\gamma^{2}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-1-i}\xi^{\mathrm{mult}}_{i}(\eta_{i-1}^{r})\otimes\xi^{\mathrm{mult}}_{i}(\eta_{i-1}^{r})(\mathrm{I}_{d}-\gamma
H_{F})^{k-1-i}\,.$

Now we use linearity of the multiplicative noise (Assumption 3), thus there
exists a matrix $\Xi_{k}$ in $\mathbb{R}^{d\times d}$ s.t. for any $z$ in
$\mathbb{R}^{d}$, we have $\xi_{k}^{\mathrm{mult}}(z)=\Xi_{k}z$, and it leads
to:

$\displaystyle\eta_{k}^{r+1}\otimes\eta_{k}^{r+1}$
$\displaystyle=\gamma^{2}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\Xi_{i}(\eta_{i-1}^{r}\otimes\eta_{i-1}^{r})\Xi_{i}^{\top}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\,.$

Taking full expectation, we have:

$\displaystyle\mathbb{E}\left[\eta_{k}^{r+1}\otimes\eta_{k}^{r+1}\right]$
$\displaystyle=\gamma^{2}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\mathbb{E}\left[\mathbb{E}\left[\Xi_{i}(\eta_{i-1}^{r}\otimes\eta_{i-1}^{r})\Xi_{i}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\sigma(\Xi_{i})\right]\right](\mathrm{I}_{d}-\gamma H_{F})^{k-i}$
$\displaystyle=\gamma^{2}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\mathbb{E}\left[\Xi_{i}\mathbb{E}[\eta_{i-1}^{r}\otimes\eta_{i-1}^{r}\leavevmode\nobreak\
|\leavevmode\nobreak\
\sigma(\Xi_{i})]\Xi_{i}^{\top}\right](\mathrm{I}_{d}-\gamma H_{F})^{k-i}\,,$

and because for any $i$ in $\\{1,\cdots,k\\}$, $\eta_{i-1}^{r}$ is independent
of $\Xi_{i}$, we have
$\mathbb{E}\left[\eta_{i-1}^{r}\otimes\eta_{i-1}^{r}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\sigma(\Xi_{i})\right]=\mathbb{E}\left[\eta_{i-1}^{r}\otimes\eta_{i-1}^{r}\right]\preccurlyeq\gamma^{r+1}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r}\mathrm{I}_{d}$,
where we use the hypothesis for $r$. We have in the end:

$\displaystyle\mathbb{E}\left[\eta_{k}^{r+1}\otimes\eta_{k}^{r+1}\right]$
$\displaystyle\preccurlyeq\gamma^{r+3}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\mathbb{E}\left[\Xi_{i}\Xi_{i}^{\top}\right](\mathrm{I}_{d}-\gamma
H_{F})^{k-i}\,.$

Furthermore, by Item 4.2 we have
$\mathbb{E}\left[\Xi_{i}\Xi_{i}^{\top}\right]\preccurlyeq\Sha_{\mathrm{mult}}H_{F}$,
thus:

$\displaystyle\mathbb{E}\left[\eta_{k}^{r+1}\otimes\eta_{k}^{r+1}\right]$
$\displaystyle\preccurlyeq\gamma^{r+3}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r+1}\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{2k-2-2i}H_{F}$
$\displaystyle\preccurlyeq\gamma^{r+3}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r+1}\gamma^{-1}H_{F}^{-1}H_{F}\,,$

because $\sum_{i=1}^{k}(\mathrm{I}_{d}-\gamma
H_{F})^{2k-2-2i}=\left(\mathrm{I}_{d}-(\mathrm{I}_{d}-\gamma
H_{F})^{2k}\right)\left(2\gamma
H_{F}-\gamma^{2}H_{F}^{2}\right)^{-1}\preccurlyeq\gamma^{-1}H_{F}^{-1}$. In
the end, we have
$\mathbb{E}[\eta_{k}^{r+1}\otimes\eta_{k}^{r+1}]\preccurlyeq\gamma^{r+2}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r+1}\mathrm{I}_{d}$,
which concludes the proof.

###  C.3 Final theorem

In this section, we gather the pieces of proof required to demonstrate Theorem
2. As done in Appendix B, we consider separately the noise process and the
noise-free process, then put them together to obtain the final result.

######  Theorem S3 (Linear multiplicative noise, convex case).

Under Assumption 1, under Assumptions 3 and 4 i.e. with a linear
multiplicative noise, considering any constant step-size $\gamma$ such that
$\gamma(R_{F}^{2}+\mathcal{M}_{2})\leq 1$ and
$4\gamma\Sha_{\mathrm{mult}}R_{F}^{2}\leq 1$, then for any $K$ in
$\mathbb{N}^{*}$, the sequence $(w_{k})_{k\in\mathbb{N}^{*}}$ produced by a
setting such as in Definition 1, verifies the following bound:
$\displaystyle\mathbb{E}[F(\overline{w}_{K-1})-F(w_{*})]\leq\frac{1}{2K}\left(\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}+\frac{\displaystyle\left(\gamma
d\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}\right)^{1/2}}{\displaystyle
1-\sqrt{\gamma\Sha_{\mathrm{mult}}}}\right)^{2}\,.$

Proof  Let $K$ in $\mathbb{N}^{*}$, the proof relies on the proof presented by
Bach and Moulines (2013) and is done separately for the noise process and for
the noise-free process that depends only on the initial condition. The bounds
may then be added (see the discussion in Subsection C.1).

Noise-free process. As in section A.3 from Bach and Moulines (2013), we assume
here that the additive noise $(\xi_{k}^{\mathrm{add}})_{k\in\mathbb{N}^{*}}$
is uniformly equal to zero and that $\gamma(R_{F}^{2}+\mathcal{M}_{2})\leq 1$.
Using Definitions 2 and 1, we thus have for any $k$ in $\mathbb{N}^{*}$ that
$\eta_{k}=\eta_{k-1}-\gamma
H_{F}\eta_{k-1}+\gamma\xi_{k}^{\mathrm{mult}}(\eta_{k-1})$, it flows:

$\displaystyle\mathbb{E}[\|\eta_{k}\|^{2}]$
$\displaystyle=\mathbb{E}[\|\eta_{k-1}\|^{2}]-2\gamma\mathbb{E}[\left\langle\eta_{k-1},H_{F}\eta_{k-1}\right\rangle]+\gamma^{2}\mathbb{E}[\|H_{F}\eta_{k-1}-\xi_{k}^{\mathrm{mult}}(\eta_{k-1})\|^{2}]$
$\displaystyle=\mathbb{E}[\|\eta_{k-1}\|^{2}]-2\gamma\mathbb{E}[\left\langle\eta_{k-1},H_{F}\eta_{k-1}\right\rangle]+\gamma^{2}\mathbb{E}[\|H_{F}\eta_{k-1}\|^{2}]+\gamma^{2}\mathbb{E}[\|\xi_{k}^{\mathrm{mult}}(\eta_{k-1})\|^{2}]\,.$

Considering that
$H_{F}\preccurlyeq\mathrm{Tr}\left(H_{F}\right)\mathrm{I}_{d}\preccurlyeq
R_{F}^{2}\mathrm{I}_{d}$ and using Assumption 3, we obtain:

$\displaystyle\mathbb{E}[\|\eta_{k}\|^{2}]$
$\displaystyle\leq\mathbb{E}[\|\eta_{k-1}\|^{2}]-2\gamma\mathbb{E}[\|H_{F}^{1/2}\eta_{k-1}\|^{2}]+\gamma^{2}(R_{F}^{2}+\mathcal{M}_{2})\mathbb{E}[\|H_{F}^{1/2}\eta_{k-1}\|^{2}]\,.$

Because the step-size $\gamma$ is s.t. $\gamma(R_{F}^{2}+\mathcal{M}_{2})\leq
1$, we recover that in the absence of noise, we have:

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}]\leq\frac{\left\|\eta_{0}\right\|^{2}}{\gamma
K}\,.$ (S16)

Noise process. Now, all the following results comes from Subsection C.2 where
we assume that $\eta_{0}=w_{0}-w_{*}=0$, we start using Minkowski’s inequality
S1:

$\displaystyle\mathbb{E}\left[\|H_{F}^{1/2}\overline{\eta}_{K-1}\|^{2}\right]^{1/2}\leq\mathbb{E}\left[\|H_{F}^{1/2}\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i}\|^{2}\right]^{1/2}+\mathbb{E}\left[\|H_{F}^{1/2}(\overline{\eta}_{K-1}-\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i})\|^{2}\right]^{1/2}\,.$
(S17)

First term.

Let $r\in\mathbb{N}$, again using Minkowski’s inequality S1, we have

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i}\|^{2}]^{1/2}$
$\displaystyle\leq\sum_{i=0}^{r}\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{i}\|^{2}]^{1/2}$
$\displaystyle=\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}]^{1/2}+\sum_{i=1}^{r}\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{i}\|^{2}]^{1/2}\,.$
(S18)

By Equation S15, we have $\eta_{k}^{0}=(\mathrm{I}_{d}-\gamma
H_{F})\eta_{k-1}^{0}+\gamma\xi_{k}^{\mathrm{add}}$, hence to bound the first
term, we have to apply Lemma 2 from Bach and Moulines (2013) to the sequence
$(\eta_{k-1}^{0})_{k\in\mathbb{N}^{*}}$ and we obtain

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{0}\|^{2}]\leq\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)/K\,.$
(S19)

Let $i$ in $\\{1,\cdots,r\\}$, to bound the second term, we have to apply
Lemma 2 from Bach and Moulines (2013) to the sequence
$(\eta_{k-1}^{i})_{k\in\mathbb{N}^{*}}$. To do so, we bound the covariance of
the noise which is here equal to
$\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{i-1}\right)$ (by definition of
$\eta_{k-1}^{i}$, see Equation S15).

Because the multiplicative noise is linear, using Assumption 3, there exists a
matrix $\Xi_{k}$ in $\mathbb{R}^{d\times d}$ s.t.
$\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{i-1}\right)=\Xi_{k}\eta_{k-1}^{i-1}$.
It follows that taking the expectation w.r.t to the $\sigma$-algebra
$\sigma(\Xi_{k})$, and because $\eta_{k-1}^{i-1}$ is independent of it, using
Lemma S6, we have:

$\mathbb{E}\left[\eta_{k-1}^{i-1}\otimes\eta_{k-1}^{i-1}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\sigma(\Xi_{k})\right]=\mathbb{E}\left[\eta_{k-1}^{i-1}\otimes\eta_{k-1}^{i-1}\right]\preccurlyeq\gamma^{i}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{i-1}\mathrm{I}_{d}\,.$

Thus, the noise $\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{i-1}\right)$ is such
that:

$\displaystyle\mathbb{E}[\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{i-1}\right)\otimes\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{i-1}\right)\leavevmode\nobreak\
|\leavevmode\nobreak\ \sigma(\Xi_{k})]$
$\displaystyle=\Xi_{k}\mathbb{E}\left[\eta_{k-1}^{i-1}\otimes\eta_{k-1}^{i-1}\right]\Xi_{k}^{\top}\preccurlyeq\gamma^{i}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{i-1}\Xi_{k}\Xi_{k}^{\top}\,.$

Taking full expectation, we furthermore consider Item 4.2 which gives that:
$\mathbb{E}\left[\Xi_{i}\Xi_{i}^{\top}\right]\preccurlyeq\Sha_{\mathrm{mult}}H_{F}$,
hence:

$\displaystyle\mathbb{E}\left[\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{i-1}\right)\otimes\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{i-1}\right)\right]$
$\displaystyle\leq\gamma^{i}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{i}H_{F}\,.$
(S20)

Using Lemma 2 from Bach and Moulines (2013) results to:

$\displaystyle\sum_{i=1}^{r}\mathbb{E}[\|H_{F}^{1/2}\overline{\eta}_{K-1}^{i}\|^{2}]^{1/2}\leq\sum_{i=1}^{r}\gamma^{i}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{i}\mathrm{Tr}\left(H_{F}H_{F}^{-1}\right)/K\,.$
(S21)

In the end, we obtain from Subsection C.3:

$\displaystyle\mathbb{E}[\|H_{F}^{1/2}\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i}\|^{2}]^{1/2}$
$\displaystyle\leq\frac{\displaystyle\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}}{\displaystyle\sqrt{K}}+\frac{\displaystyle\sqrt{d\Sha_{\mathrm{add}}}}{\displaystyle\sqrt{K}}\sum_{i=1}^{r}\gamma^{i/2}\Sha_{\mathrm{mult}}^{i/2}$
$\displaystyle\leq\frac{\displaystyle\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}}{\displaystyle\sqrt{K}}+\frac{\sqrt{\gamma
d\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}}\left(1-(\gamma\Sha_{\mathrm{mult}})^{r/2}\right)}{\sqrt{K}\left(1-\sqrt{\gamma\Sha_{\mathrm{mult}}}\right)}\,.$

Second term.

If $\gamma(R_{F}^{2}+\mathcal{M}_{2})\leq 1$, Lemma S5 gives:

$\displaystyle\mathbb{E}\left\langle\overline{\eta}_{K-1}-\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i},H(\overline{\eta}_{K-1}-\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i})\right\rangle\leq\frac{\gamma}{(1-\gamma(R_{F}^{2}+\mathcal{M}_{2}))K}\sum_{k=1}^{K}\mathbb{E}\left[\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\|^{2}\right]\,.$
(S22)

Furthermore,
$\left\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\right\|^{2}=\mathrm{Tr}\left(\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)^{{\otimes
2}}\right)$, by reusing what has been written in the previous paragraph
(Equation S20), we obtain:

$\displaystyle\|\xi^{\mathrm{mult}}_{k}\left(\eta_{k-1}^{r}\right)\|^{2}$
$\displaystyle\leq\gamma^{r+1}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r+1}\mathrm{Tr}\left(H_{F}\right)$
$\displaystyle\leq\gamma^{r+1}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r+1}R_{F}^{2}\qquad\text{(\lx@cref{creftypecap~refnum}{def:class_of_algo}).}$

It follows that we have:

$\displaystyle\mathbb{E}\left\langle\overline{\eta}_{K-1}-\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i},H(\overline{\eta}_{K-1}-\sum_{i=0}^{r}\overline{\eta}_{K-1}^{i})\right\rangle\leq\frac{\gamma^{r+2}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r+1}R_{F}^{2}}{(1-\gamma(R_{F}^{2}+\mathcal{M}_{2}))}\,.$
(S23)

Putting things together. In the end, from the Minkowski decomposition done in
Equation S17, we combine the two terms and it leads to:

$\displaystyle\mathbb{E}\left[\left\langle\overline{\eta}_{K-1},H_{F}\overline{\eta}_{K-1}\right\rangle\right]^{1/2}$
$\displaystyle\leq\left(\frac{\gamma^{r+2}\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}^{r+1}R_{F}^{2}}{(1-\gamma(R_{F}^{2}+\mathcal{M}_{2}))}\right)^{1/2}+\frac{\displaystyle\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}}{\displaystyle\sqrt{K}}$
$\displaystyle\qquad+\frac{\sqrt{\gamma
d\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}}\left(1-(\gamma\Sha_{\mathrm{mult}})^{r/2}\right)}{\sqrt{K}\left(1-\sqrt{\gamma\Sha_{\mathrm{mult}}}\right)}\,.$

This implies that for any $\gamma\Sha_{\mathrm{mult}}\leq 1$, we obtain, by
letting $r$ tend to $+\infty$:

$\displaystyle\mathbb{E}\left[\left\langle\overline{\eta}_{K-1},H_{F}\overline{\eta}_{K-1}\right\rangle\right]^{1/2}$
$\displaystyle\leq\frac{\displaystyle
1}{\displaystyle\sqrt{K}}\left(\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}+\frac{\displaystyle\left(\gamma
d\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}\right)^{1/2}}{\displaystyle
1-\sqrt{\gamma\Sha_{\mathrm{mult}}}}\right)\,.$ (S24)

Final bound. We now take results derived from the part without noise, and the
part with noise, to get:

$\displaystyle\mathbb{E}[\left\langle\overline{\eta}_{K-1},H_{F}\overline{\eta}_{K-1}\right\rangle]^{1/2}\leq\frac{1}{\sqrt{K}}\left(\frac{\|\eta_{0}\|}{\sqrt{\gamma}}+\sqrt{\mathrm{Tr}\left(\mathfrak{C}_{\mathrm{ania}}H_{F}^{-1}\right)}+\frac{\displaystyle\left(\gamma
d\Sha_{\mathrm{add}}\Sha_{\mathrm{mult}}\right)^{1/2}}{\displaystyle
1-\sqrt{\gamma\Sha_{\mathrm{mult}}}}\right)\,,$

which leads to the desired result considering that
$4\gamma\Sha_{\mathrm{mult}}\leq 1$.

##  Appendix D Validity of the assumptions made on the random fields

In this section, we verify that all the assumptions on the random fields done
in Subsection 2.1 are fulfilled in the setting of compressed least-squares
regression analyzed in Section 3. To do so, we first need to define the
filtrations considered in this section.

For $k$ in $\mathbb{N}^{*}$, we note $u_{k}$ the noise that controls the
randomization $\mathcal{C}_{k}(\cdot)$ at round $k$. In Section 2, we have
denoted by $\mathcal{F}_{k}$ the $\sigma$-algebra generated by
$(x_{1},\varepsilon_{1},u_{1},\cdots,x_{k},\varepsilon_{k})$. In particular,
$w_{k}$ and $\overline{w}_{k}$ are $\mathcal{F}_{k}$-measurable. We also
consider the following filtrations.

######  Definition S2.

We note $(\mathcal{G}_{k})_{k\in\mathbb{N}}$ the filtration associated with
the features noise, $(\mathcal{H}_{k})_{k\in\mathbb{N}}$ the filtration
associated with the output noise, and $(\mathcal{I}_{k})_{k\in\mathbb{N}}$ the
filtration associated with the stochastic gradient noise, which is the union
of the two previous filtrations. Thus, we define
$\mathcal{F}_{0}=\\{\varnothing\\}$ and for $k\in\mathbb{N}^{*}$:

$\displaystyle\mathcal{G}_{k}$
$\displaystyle=\sigma\left(\mathcal{F}_{k-1}\cup\\{x_{k}\\}\right)$
$\displaystyle\mathcal{H}_{k}$
$\displaystyle=\sigma\left(\mathcal{F}_{k-1}\cup\\{\varepsilon_{k}\\}\right)$
$\displaystyle\mathcal{I}_{k}$
$\displaystyle=\sigma\left(\mathcal{F}_{k-1}\cup\\{x_{k},\varepsilon_{k}\\}\right)$
$\displaystyle\mathcal{F}_{k}$
$\displaystyle=\sigma\left(\mathcal{F}_{k-1}\cup\\{x_{k},\varepsilon_{k},u_{k}\\}\right)\,.$

Note that there are two filtrations $\mathcal{G}$ and $\mathcal{H}$ for the
two independent noises that are both involved to compute the stochastic
gradient. This will help us to compute the scalar product of these two
quantities.

We start by providing a bound on the distance between two compressions, this
lemma will be used to prove Property S3.

######  Lemma S7.

For any compressor $\mathcal{C}$ in $\mathbb{C}$ verifying Lemma 1, for all
$x,y$ in $\mathbb{R}^{d}$, we have:
$\mathbb{E}[\left\|\mathcal{C}(x)-\mathcal{C}(y)\right\|^{2}]\leq
2(\omega+1)\left\|x\right\|^{2}+2(\omega+1)\left\|y\right\|^{2}\,.$

Proof  Let a compressor $\mathcal{C}$ in $\mathbb{C}$ and $x,y$ in
$\mathbb{R}^{d}$, using Inequality 1, we have that:

$\displaystyle\left\|\mathcal{C}(x)-\mathcal{C}(y)\right\|^{2}$
$\displaystyle\leq
2\left\|\mathcal{C}(x)\right\|^{2}+2\left\|\mathcal{C}(y)\right\|^{2}\,.$

Taking expectation and using Lemma 1 allows to conclude:

$\displaystyle\mathbb{E}\left[\left\|\mathcal{C}(x)-\mathcal{C}(y)\right\|^{2}\right]$
$\displaystyle\leq
2(\omega+1)\left\|x\right\|^{2}+2(\omega+1)\left\|y\right\|^{2}\,.$

Now we prove that all the assumptions done in Section 2 are correct.

######  Property S1 (Validity of the setting presented in Definition 1).

Consider Algorithm 2 in the context of Model 2, we have that the setting
presented in Definition 1 is verified.

Proof  From Algorithm 2, we have for any $k$ in $\mathbb{N}^{*}$ and any $w$
in $\mathbb{R}^{d}$ $\xi_{k}(w-w_{*})=\nabla
F(w)-\mathcal{C}_{k}(\textsl{g}_{k}(w))$. Because
$(\textsl{g}_{k})_{k\in\mathbb{N}^{*}}$ and
$(\mathcal{C}_{k})_{k\in\mathbb{N}^{*}}$ are by definition two sequences of
i.i.d. random fields (Algorithm 2), it follows that their composition is also
i.i.d., _hence $(\xi_{k})_{k\in\mathbb{N}^{*}}$ is a sequence of i.i.d. random
fields._

Taking expectation w.r.t. the $\sigma$-algebra $\mathcal{I}_{k}$, we have
$\mathbb{E}\left[\mathcal{C}_{k}(\textsl{g}_{k}(w))\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]=\textsl{g}_{k}(w)$ (Lemma
1), next with the $\sigma$-algebra $\mathcal{F}_{k-1}$, we have
$\mathbb{E}\left[\textsl{g}_{k}(w)\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]=\nabla F(w)$ (Equation
2). _Hence, the random fields are zero-centered._

From Model 2, we have for any $k$ in $\mathbb{N}^{*}$ and any $w$ in
$\mathbb{R}^{d}$ that:

$\displaystyle F(w)$ $\displaystyle=\frac{1}{2}\mathbb{E}\left[(\left\langle
x_{k},w\right\rangle-
y_{k})^{2}\right]=\frac{1}{2}\mathbb{E}\left[(w-w_{*})^{\top}(x_{k}\otimes
x_{k})(w-w_{*})-2\varepsilon_{k}\left\langle
x_{k},w-w_{*}\right\rangle+\varepsilon_{k}^{2}\right]$
$\displaystyle=\frac{1}{2}((w-w_{*})^{\top}H(w-w_{*})+\sigma^{2})\,,$

hence $F$ is quadratic with Hessian equal to $H$ whose trace is equal to
$R^{2}$.

######  Property S2 (Validity of Assumption 1).

Considering Algorithm 2 under the setting of Model 2 with Lemma 1, for any
iteration $k$ in $\mathbb{N}^{*}$, the second moment of the additive noise
$\xi_{k}^{\mathrm{add}}$ can be bounded by $(\omega+1)R^{2}\sigma^{2}$, i.e.,
Assumption 1 is verified.

Proof  Let $k$ in $\mathbb{N}^{*}$. Because we consider Algorithm 2, with
Definitions 1 and 2, we first have
$\xi_{k}^{\mathrm{add}}=-\mathcal{C}_{k}(g_{k,*})$, then with Lemma 1 we
obtain
$\mathbb{E}[\left\|\mathcal{C}_{k}(g_{k,*})\right\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{I}_{k}]\leq(\omega+1)\left\|g_{k,*}\right\|^{2}$. Next, we first have
from Model 2 and Equation 2 that $g_{k,*}=\varepsilon_{k}x_{k}$, secondly
because $\left((\varepsilon_{k})_{k\in[K]}\right)$ is independent from
$\left((x_{k})_{k\in[K]}\right)$ (Model 2), we have that
$\mathbb{E}[\|\varepsilon_{k}x_{k}\|^{2}]\leq\sigma^{2}R^{2}$, hence it
results to:

$\displaystyle\mathbb{E}[\|\xi_{k}^{\mathrm{add}}\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]=\mathbb{E}[\|\xi_{k}^{\mathrm{add}}\|^{2}]\leq(\omega+1)\sigma^{2}R^{2}\,.$

######  Property S3 (Validity of Item 2.1).

Considering Algorithm 2, under the setting of Model 2 with Lemma 1, for any
iteration $k$ in $\mathbb{N}^{*}$, the second moment of the multiplicative
noise $\xi_{k}^{\mathrm{mult}}(w)$ can be bounded for any $w$ in
$\mathbb{R}^{d}$ by
$2(\omega+1)R^{2}\left\|H^{1/2}(w-w_{*})\right\|^{2}+4(\omega+1)\sigma^{2}R^{2}$,
i.e., Item 2.1 is verified.

Proof  Let $k$ in $\mathbb{N}^{*}$, we note $\eta=w-w_{*}$. First, because we
consider Algorithm 2, with Definitions 1 and 2, we have $\xi_{k}(\eta)=\nabla
F(w)-\mathcal{C}_{k}(\textsl{g}_{k}(w))$ and
$\xi_{k}^{\mathrm{add}}=-\mathcal{C}_{k}(g_{k,*})$, hence:

$\xi^{\mathrm{mult}}_{k}(\eta)=\xi_{k}(\eta)-\xi_{k}^{\mathrm{add}}=\nabla
F(w)-\mathcal{C}_{k}(\textsl{g}_{k}(w))+\mathcal{C}_{k}(g_{k,*})\,,$

thus developing the squared-norm of $\xi^{\mathrm{mult}}_{k}(\eta)$ gives:

$\displaystyle\|\xi^{\mathrm{mult}}_{k}(\eta)\|^{2}$
$\displaystyle=\left\|\nabla F(w)\right\|^{2}+2\left\langle\nabla
F(w),\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w))\right\rangle+\left\|\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w))\right\|^{2}\,.$

On the first side we have
$\mathbb{E}\left[\mathbb{E}\left[\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w))\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]=-\nabla F(w_{k-1})$. On
the second side, we use Lemma S7; this allows us to write:

$\displaystyle\mathbb{E}\left[\left\|\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w))\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]$ $\displaystyle\leq
2(\omega+1)\left\|\textsl{g}_{k}(w)\right\|^{2}+2(\omega+1)\left\|g_{k,*}\right\|^{2}\,.$

Note that this bound is far from being optimal when
$\textsl{g}_{k}(w)=g_{k,*}$ or if $\mathcal{C}$ is the identity. Next, we
decompose as follows:

$\displaystyle\mathbb{E}\left[\left\|\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w))\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]$ $\displaystyle\leq
2(\omega+1)\left\|\textsl{g}_{k}(w)-g_{k,*}\right\|^{2}$
$\displaystyle\quad+4(\omega+1)\left\langle\textsl{g}_{k}(w)-g_{k,*},g_{k,*}\right\rangle+4(\omega+1)\left\|g_{k,*}\right\|^{2}\,.$

Taking expectation w.r.t. the $\sigma$-algebra $\mathcal{G}_{k}$, recalling
that $\textsl{g}_{k}(w)-g_{k,*}$ is $\mathcal{G}_{k}$-measurable (Definition
S2) and considering Model 2 allows to write:

$\displaystyle\mathbb{E}\left[\left\|\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w)\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{G}_{k}\right]$ $\displaystyle\leq
2(\omega+1)\left\|g_{k,*}-\textsl{g}_{k}(w)\right\|^{2}+4(\omega+1)\sigma^{2}R^{2}$
$\displaystyle\leq 2(\omega+1)\left\|(x_{k}\otimes
x_{k})\eta_{k-1}\right\|^{2}+4(\omega+1)\sigma^{2}R^{2}\,,$

and now taking expectation w.r.t the $\sigma$-algebra $\mathcal{F}_{k-1}$
concludes the proof:

$\displaystyle\mathbb{E}[\left\|\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w))\right\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]\leq
2(\omega+1)R^{2}\|H^{1/2}(w_{k}-w_{*})\|^{2}+4(\omega+1)\sigma^{2}R^{2}\,.$

######  Property S4 (Validity of Item 2.2).

Considering Algorithm 2, under the setting of Model 2 with Lemma 1, for any
iteration $k$ in $\mathbb{N}^{*}$, the second moment of the multiplicative
noise $\xi_{k}^{\mathrm{mult}}(w)$ can be bounded for any $w$ in
$\mathbb{R}^{d}$ by $\Omega
R^{2}\sigma\|H^{1/2}(w-w_{*})\|+3(\omega+1)R^{2}\|H^{1/2}(w-w_{*})\|^{2}$,
i.e. Item 2.2 is verified.

Proof  Let $k$ in $\mathbb{N}^{*}$, we note $\eta=w-w_{*}$. Because we
consider Algorithm 2, with Definitions 1 and 2, we have the following
decomposition:

$\displaystyle\xi^{\mathrm{mult}}_{k}\left(\eta\right)$
$\displaystyle=\left\|\nabla F(w)\right\|^{2}+2\left\langle\nabla
F(w),\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w))\right\rangle+\left\|\mathcal{C}_{k}(g_{k,*})-\mathcal{C}_{k}(\textsl{g}_{k}(w))\right\|^{2}\,.$

We take expectation w.r.t. the $\sigma$-algebra $\mathcal{I}_{k}$ and use Item
L.2 of Lemma 1:

$\displaystyle\mathbb{E}\left[\xi^{\mathrm{mult}}_{k}\left(\eta\right)\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]$
$\displaystyle\leq\left\|\nabla F(w)\right\|^{2}+2\left\langle\nabla
F(w),g_{k,*}-\textsl{g}_{k}(w)\right\rangle$
$\displaystyle\qquad+\Omega\min(\|g_{k,*}\|,\|\textsl{g}_{k}(w)\|)\|g_{k,*}-\textsl{g}_{k}(w)\|+3(\omega+1)\|g_{k,*}-\textsl{g}_{k}(w)\|^{2}\,.$

Then, we have
$\min(\|g_{k,*}\|,\|\textsl{g}_{k}(w)\|)\|g_{k,*}-\textsl{g}_{k}(w)\|\leq\|g_{k,*}\|\|g_{k,*}-\textsl{g}_{k}(w)\|$,
taking expectation conditionally to the $\sigma$-algebra $\mathcal{F}_{k-1}$,
applying the Cauchy-Schwarz’s Equation S3 and considering Model 2, we have:

$\displaystyle\mathbb{E}[\|g_{k,*}\|\|g_{k,*}-\textsl{g}_{k}(w)\|\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]^{2}$
$\displaystyle\leq\mathbb{E}[\|g_{k,*}\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\
\mathcal{F}_{k-1}]\mathbb{E}[\|g_{k,*}-\textsl{g}_{k}(w)\|^{2}\leavevmode\nobreak\
|\leavevmode\nobreak\ \mathcal{F}_{k-1}]$
$\displaystyle\leq\sigma^{2}R^{4}\|H^{1/2}(w-w_{*})\|^{2}\,.$

Therefore, we can conclude:

$\displaystyle\mathbb{E}\left[\xi^{\mathrm{mult}}_{k}\left(\eta\right)\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\leq-\left\|\nabla F(w)\right\|^{2}+\sigma
R^{2}\Omega\|H^{1/2}(w-w_{*})\|+3(\omega+1)R^{2}\|H^{1/2}(w-w_{*})\|^{2}\,.$

######  Property S5 (Validity of Assumption 3).

Considering Algorithm 2, under the setting of Model 2 with Lemma 1, if the
compressor $\mathcal{C}$ is linear, then for any iteration $k$ in
$\mathbb{N}^{*}$, the multiplicative noise $\xi_{k}^{\mathrm{mult}}$ is
linear, thus there exist a matrix $\Xi_{k}$ in $\mathbb{R}^{d\times d}$ such
that for any $w$ in $\mathbb{R}^{d}$, $\xi_{k}^{\mathrm{mult}}(w)=\Xi_{k}w$.
Furthermore, the second moment of the multiplicative noise can be bounded for
any $w$ in $\mathbb{R}^{d}$ by
$(\omega+1)R^{2}\left\|H^{1/2}(w-w_{*})\right\|^{2}$, hence Assumption 3 is
verified.

Proof  Let $k$ in $\mathbb{N}^{*}$, we note $\eta=w-w_{*}$. First, because we
consider Algorithm 2, with Definitions 1 and 2, we have $\xi_{k}(\eta)=\nabla
F(w)-\mathcal{C}_{k}(\textsl{g}_{k}(w))$ and
$\xi_{k}^{\mathrm{add}}=-\mathcal{C}_{k}(g_{k,*})$, hence:

$\displaystyle\xi^{\mathrm{mult}}_{k}\left(\eta\right)=\xi_{k}(\eta)-\xi_{k}^{\mathrm{add}}=\nabla
F(w)-\mathcal{C}_{k}(\textsl{g}_{k}(w))+\mathcal{C}_{k}(g_{k,*})\,.$

Because the random mechanism $\mathcal{C}_{k}$ is linear, there exists a
random matrix $\Pi_{k}$ in $\mathbb{R}^{d\times d}$ such that for any $z$ in
$\mathbb{R}^{d}$, we have $\mathcal{C}_{k}(z)=\Pi_{k}z$, it follows that:

$\displaystyle\xi^{\mathrm{mult}}_{k}\left(\eta\right)=\nabla
F(w)+\mathcal{C}_{k}(g_{k,*}-\textsl{g}_{k}(w))=(H-\Pi_{k}(x_{k}\otimes
x_{k}))\eta\,.$

Hence, the first part of Assumption 3 is verified with
$\Xi_{k}=H-\Pi_{k}(x_{k}\otimes x_{k})$. Now, we compute the second moment of
the multiplicative noise. We start by developing its squared norm:

$\displaystyle\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\|^{2}$
$\displaystyle=\left\|\nabla F(w)\right\|^{2}+2\left\langle\nabla
F(w),\mathcal{C}_{k}(g_{k,*}-\textsl{g}_{k}(w))\right\rangle+\left\|\mathcal{C}_{k}(g_{k,*}-\textsl{g}_{k}(w))\right\|^{2}\,.$

Taking expectation conditionally to the $\sigma$-algebra $\mathcal{I}_{k}$,
and using Lemma 1 gives:

$\displaystyle\mathbb{E}\left[\|\xi^{\mathrm{mult}}_{k}\left(\eta\right))\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]$
$\displaystyle=\left\|\nabla F(w)\right\|^{2}+2\left\langle\nabla
F(w),g_{k,*}-\textsl{g}_{k}(w)\right\rangle+(\omega+1)\left\|g_{k,*}-\textsl{g}_{k}(w)\right\|^{2}\,.$

Finally, with $\sigma$-algebra $\mathcal{F}_{k-1}$ and considering Model 2 we
have:

$\displaystyle\mathbb{E}\left[\|\xi^{\mathrm{mult}}_{k}\left(\eta\right)\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle=-\left\|\nabla
F(w)\right\|^{2}+(\omega+1)R^{2}\|H^{1/2}(w-w_{*})\|^{2}\,,$

which allows to conclude.

######  Property S6 (Validity of Assumption 4).

Considering Algorithm 2 under the setting of Model 2 with Remarks 1 and 1, if
the compressor $\mathcal{C}$ is linear, then for any $k$ in $\mathbb{N}^{*}$,
there exists a constant $\Sha_{H}>0$ s.t.
$\mathfrak{C}_{\mathrm{ania}}\preccurlyeq\sigma^{2}\Sha_{H}H_{F}$ and
$\mathbb{E}\left[\Xi_{k}\Xi_{k}^{\top}\right]\preccurlyeq R^{2}\Sha_{H}H$;
Assumption 4 is thus verified.

Proof

Let $k$ in $\mathbb{N}^{*}$, we note $\eta=w-w_{*}$. We first need to compute
$\Sha_{H}$ in $\mathbb{R}^{d}$ for each compressor $\mathcal{C}$ in
$\\{\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{sq}},\mathcal{C}_{\mathrm{rd}1},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\Phi}$,
$\mathcal{C}_{\mathrm{PP}}\\}$, it comes from Proposition 2 which results
having a constant $\Sha_{H}$ s.t.:

$\displaystyle\mathfrak{C}(\mathcal{C},p_{{H}})=\mathbb{E}_{E\sim
p_{H}}[\mathcal{C}(E)^{{\otimes 2}}]\preccurlyeq\Sha_{H}H\,.$ (S25)

Indeed, $\mathrm{Diag}\left(H\right)$ car be bounded by
$\mathrm{Tr}\left(H\right)\mathrm{I}_{d}$, and then $\mathrm{I}_{d}$ by
$\mu^{-1}H$. This constant $\Sha_{H}$ can be computed from Proposition 2 for
any compressor:

Compressor | $\mathcal{C}_{\mathrm{rd}h}$ | $\mathcal{C}_{\mathrm{s}}$ | $\mathcal{C}_{\mathrm{PP}}$ | $\mathcal{C}_{\Phi}$
---|---|---|---|---
$\Sha_{H}$ | $\frac{h-1}{p(d-1)}+(1-\frac{h-1}{d-1})\frac{\tau}{p}$ | $1+\frac{(1-p)\tau}{p}$ | $\frac{1}{p}$ | $\frac{\alpha-\beta}{p}+\frac{\beta\tau}{p}$
$\Sha_{H}$ (if $H$ diagonal) | $\frac{1}{p}$ | $\frac{1}{p}$ | $\frac{1}{p}$ | $\frac{\alpha-\beta}{p}+\frac{\beta\tau}{p}$

Where $p=h/d$, $\tau=\mathrm{Tr}\left(H\right)/\mu$, and for sketching
$\alpha=\frac{h+2}{d+2}$ and $\beta=\frac{d-h}{(d-1)(d+2)}$.

We now show that the two inequalities given in Assumption 4 are valid.

First inequality.

By Definition 3, we have
$\mathfrak{C}_{\mathrm{ania}}=\mathbb{E}\left[\xi_{k}^{\mathrm{add}}\otimes\xi_{k}^{\mathrm{add}}\right]=\mathbb{E}\left[\mathcal{C}_{k}(\varepsilon_{k}x_{k})^{{\otimes
2}}\right]$, because $\left((\varepsilon_{k})_{k\in[K]}\right)$ is independent
from $\left((x_{k})_{k\in[K]}\right)$ (Model 2) and using compressor linearity
and Equation S25, it gives:
$\mathfrak{C}_{\mathrm{ania}}=\sigma^{2}\mathbb{E}\left[\mathcal{C}_{k}(x_{k})^{{\otimes
2}}\right]=\sigma^{2}\mathfrak{C}(\mathcal{C},p_{{H}})\preccurlyeq\sigma^{2}\Sha_{H}H\,.$

Second inequality.

Using Property S6, because the compressor $\mathcal{C}$ is linear, there
exists two matrices $\Pi_{k},\Xi_{k}$ in $\mathbb{R}^{d\times d}$ s.t. for any
$z$ in $\mathbb{R}^{d}$, we have $\mathcal{C}_{k}(z)=\Pi_{k}z$ and
$\xi_{k}^{\mathrm{mult}}(z)=\Xi_{k}z$, which gives that
$\Xi_{k}=H-\Pi_{k}(x_{k}\otimes x_{k})$. It follows that:

$\displaystyle\Xi_{k}\Xi_{k}^{\top}=HH^{\top}-H\Pi_{k}(x_{k}\otimes
x_{k})-\Pi_{k}(x_{k}\otimes x_{k})H+\Pi_{k}(x_{k}\otimes x_{k})(x_{k}\otimes
x_{k})\Pi_{k}^{\top}\,.$

Given that the compression is unbiased (Lemma 1) we have
$\mathbb{E}\left[\Pi_{k}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\mathcal{I}_{k}\right]=\mathrm{I}_{d}$, hence:

$\displaystyle\mathbb{E}\left[\Xi_{k}\Xi_{k}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]$
$\displaystyle=HH^{\top}-H(x_{k}\otimes x_{k})-(x_{k}\otimes
x_{k})H+\mathbb{E}\left[\Pi_{k}(x_{k}\otimes x_{k})(x_{k}\otimes
x_{k})\Pi_{k}^{\top}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\mathcal{I}_{k}\right]\,,$

and now taking expectation w.r.t the $\sigma$-algebra $\mathcal{F}_{k-1}$:

$\displaystyle\mathbb{E}\left[\Xi_{k}\Xi_{k}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle=-HH^{\top}+\mathbb{E}\left[\Pi_{k}(x_{k}\otimes
x_{k})(x_{k}\otimes x_{k})\Pi_{k}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\,.$

In the end, we have that
$\mathbb{E}\left[\Xi_{k}\Xi_{k}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\preccurlyeq\mathbb{E}\left[\Pi_{k}(x_{k}\otimes
x_{k})(x_{k}\otimes x_{k})\Pi_{k}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$, and if we consider
that the second moment of the features $(x_{k})_{k\in\mathbb{N}^{*}}$ is
almost surely bounded (Remark 1), we obtain:

$\displaystyle\mathbb{E}\left[\Xi_{k}\Xi_{k}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]$
$\displaystyle\preccurlyeq R^{2}\mathbb{E}\left[\Pi_{k}(x_{k}\otimes
x_{k})\Pi_{k}^{\top}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\mathcal{F}_{k-1}\right]\preccurlyeq
R^{2}\mathbb{E}\left[\mathcal{C}_{k}(x_{k})^{{\otimes 2}}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\,.$ (S26)

Thus, using Equation S25, we can state that
$\mathbb{E}\left[\Xi_{k}\Xi_{k}^{\top}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]\preccurlyeq
R^{2}\Sha_{H}H$, which concludes the second part of the verification of
Assumption 4.

##  Appendix E Compression operators

In this Section, we provide additional details about compression operators.
First, we prove in Subsection E.1 that Lemma 1 hold and compute the
compressor’s covariance given in Proposition 2. The specific computations for
sketching are given separately in Subsection E.2 because they are more
complex. Third, it allows to prove Propositions 3 and 4 in Subsection E.3. And
finally, in Subsection E.4, we plot the covariance matrix induced by
quantization and sparsification for quantum and cifar-10.

###  E.1 Computation of the variance and covariance of the compression
operators

In this Subsection, we first prove Lemma 1. Item L.1 is frequently established
in the literature and corresponds to the worst-case assumption, see the
introduction for references. On the other hand, Item L.2 is the Hölder-type
bound, which is not used in the literature up to our knowledge. Next, we
compute the compressors’ covariances that have been given in Proposition 2.

######  Lemma S8.

For any compressor
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{sq}},\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}\\}$,
there exists constants $\omega,\Omega\in\mathbb{R}^{*}_{+}$, such that the
random operator $\mathcal{C}$ satisfies the following properties for all
$z,z^{\prime}\in\mathbb{R}^{d}$.

  1. L.1:

$\mathbb{E}[\mathcal{C}(z)]=z$ and
$\mathbb{E}[\|\mathcal{C}(z)-z\|^{2}]\leq\omega\|z\|^{2}$ (unbiasedness and
variance relatively bounded),

  2. L.2:

$\mathbb{E}[\|\mathcal{C}(z)-\mathcal{C}(z^{\prime})\|^{2}]\leq\Omega\min(\|z\|,\|z^{\prime}\|)\|z-z^{\prime}\|+3(\omega+1)\|z-z^{\prime}\|^{2}\text{(Hölder-
type bound),}$

with $\omega=\sqrt{d}$ and $\Omega=12\sqrt{d}$ (resp. $\omega=(1-p)/p$ and
$\Omega=0$) for $\mathcal{C}_{\mathrm{q}}$ and $\mathcal{C}_{\mathrm{sq}}$
(resp. $\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\mathrm{s}}$,
$\mathcal{C}_{\Phi},\mathcal{C}_{\mathrm{PP}}$).

Proof

##### Value of $\omega$ (Item L.1 of Lemma 1).

For projection-based compressors, the proof is straightforward, for
quantization-based, the proof can be found in Alistarh et al. (2017).

##### Value of $\Omega$ (Item L.2 of Lemma 1).

For linear compressors, it is straightforward to obtain $\Omega=0$.

For quantization, we take $x,y$ in $\mathbb{R}^{d}$, we note
$(u_{i})_{i=1}^{d}$ the vector controlling the randomness of compression, and
we write $\mathcal{C}_{\mathrm{q}}(x)-\mathcal{C}_{\mathrm{q}}(y)=A+B+C$,
with:

  1. 1.

$A:=\|x\|\mathrm{sign}(x)\mathrm{Bern}(\frac{|x|}{\|x\|})-\|x\|\mathrm{sign}(x)\mathrm{Bern}(\frac{|x|}{\|y\|})$

  2. 2.

$B:=\|x\|\mathrm{sign}(x)\mathrm{Bern}(\frac{|x|}{\|y\|})-\|x\|\mathrm{sign}(y)\mathrm{Bern}(\frac{|y|}{\|y\|})$

  3. 3.

$C:=\|x\|\mathrm{sign}(y)\mathrm{Bern}(\frac{|y|}{\|y\|})-\|y\|\mathrm{sign}(y)\mathrm{Bern}(\frac{|y|}{\|y\|})$.

We note $\|\cdot\|$ the 2-norm and $\|\cdot\|_{1}$ the 1-norm. By symmetry, we
suppose that $\|y\|^{2}\geq\|x\|^{2}$.

First term. We have
$\|A\|^{2}=\|x\|^{2}\sum_{i=1}^{d}(\mathbb{1}_{u_{i}\leq\frac{|x_{i}|}{\|x\|}}-\mathbb{1}_{u_{i}\leq\frac{|x_{i}|}{\|y\|}})^{2}=\|x\|^{2}\sum_{i=1}^{d}\mathbb{1}_{\frac{|x_{i}|}{\|y\|}\leq
u_{i}\leq\frac{|x_{i}|}{\|x\|}}^{2}$ because $\|y\|^{2}\geq\|x\|^{2}$. Taking
expectation, it gives
$\mathbb{E}[\|A\|^{2}]=\|x\|^{2}\sum_{i=1}^{d}\frac{|x_{i}|}{\|x\|}-\frac{|x_{i}|}{\|y\|}=\|x\|^{2}\|x\|_{1}\frac{\|y\|-\|x\|}{\|y\|\|x\|}$.
Now with triangular inequality, we have:

$\mathbb{E}[\|A\|^{2}]\leq\frac{\|x\|}{\|y\|}\|x\|_{1}\|y-x\|\leq\|x\|_{1}\|y-x\|\leq\sqrt{d}\|x\|\|y-x\|\,,$

and by symmetry $\mathbb{E}[\|A\|^{2}]\leq\sqrt{d}\min(\|x\|,\|y\|)\|y-x\|$.

Second term.

We have
$\|B\|^{2}=\|x\|^{2}\sum_{i=1}^{d}(\mathrm{sign}(x_{i})\mathbb{1}_{u_{i}\leq\frac{|x_{i}|}{\|y\|}}-\mathrm{sign}(y_{i})\mathbb{1}_{u_{i}\leq\frac{|y_{i}|}{\|y\|}})^{2}$.
Let $i$ in $[d]$, if $\mathrm{sign}(x_{i})=\mathrm{sign}(y_{i})$, then:

$\mathbb{E}\left[\|B\|^{2}\right]=\|x\|^{2}\sum_{i=1}^{d}\mathbb{E}\left[\mathbb{1}_{\frac{\min(|x_{i}|,|y_{i}|)}{\|y\|}\leq
u_{i}\leq\frac{\max(|x_{i}|,|y_{i}|)}{\|y\|}}^{2}\right]=\frac{\|x\|^{2}}{\|y\|}\sum_{i=1}^{d}|y_{i}-x_{i}|\leq\|x\|\|x-y\|_{1}\,.$

If $\mathrm{sign}(x_{i})\neq\mathrm{sign}(y_{i})$, developping
$(\mathrm{sign}(x_{i})\mathbb{1}_{u_{i}\leq\frac{|x_{i}|}{\|y\|}}-\mathrm{sign}(y_{i})\mathbb{1}_{u_{i}\leq\frac{|y_{i}|}{\|y\|}})^{2}$,
we have:

$\displaystyle\mathbb{E}\left[\|B\|^{2}\right]$
$\displaystyle=\|x\|^{2}\sum_{i=1}^{d}\frac{|x_{i}|}{\|y\|}+\frac{|y_{i}|}{\|y\|}-2\mathrm{sign}(x_{i})\mathrm{sign}(y_{i})\frac{\min(|x_{i}|,|y_{i}|)}{\|y\|}$
$\displaystyle=\frac{\|x\|^{2}}{\|y\|}\sum_{i=1}^{d}\max(|x_{i}|,|y_{i}|)+3\min(|x_{i}|,|y_{i}|)\,.$

Next, we have
$\max(|x_{i}|,|y_{i}|)+\min(|x_{i}|,|y_{i}|)=|x_{i}|+|y_{i}|\overset{\mathrm{sign}(x_{i})\neq\mathrm{sign}(y_{i})}{=}|x_{i}-y_{i}|$,
which results to $\mathbb{E}\left[\|B\|^{2}\right]\leq
3\frac{\|x\|^{2}}{\|y\|}\sum_{i=1}^{d}|y_{i}-x_{i}|\leq 3\|x\|\|x-y\|_{1}\leq
3\sqrt{d}\|x\|\|x-y\|$.

Third term. We have
$\|C\|^{2}=(\|x\|-\|y\|)^{2}\sum_{i=1}^{d}\mathbb{1}_{u_{i}\leq\frac{|y_{i}|}{\|y\|}}^{2}$,
taking expectation, it gives:

$\mathbb{E}[\|C\|^{2}]=(\|x\|-\|y\|)^{2}\sum_{i=1}^{d}\frac{|y_{i}|}{\|y\|}\leq\|x-y\|^{2}\frac{\|y\|_{1}}{\|y\|}\leq\sqrt{d}\|x-y\|^{2}\,.$

Overall, using Inequality 1, we have:

$\displaystyle\mathbb{E}[\|\mathcal{C}_{\mathrm{q}}(x)-\mathcal{C}_{\mathrm{q}}(y)\|^{2}]$
$\displaystyle\leq 12\sqrt{d}\min(\|x\|,\|y\|)\|x-y\|+3\sqrt{d}\|x-y\|^{2}\,,$

which allows to conclude as for $1$-quantization, we have $\omega=\sqrt{d}$.

We now compute the compressors’ covariance given in Propositions 2 and 3.
However, sketching requires more involved computations, they are provided in
Subsection E.2.

######  Proposition S2 (Structure of the compressor’s covariance).

The following formulas of compressors’ covariance hold: •
$\mathfrak{C}(\mathcal{C}_{\emptyset},p_{{M}})=M$ •
$\mathfrak{C}(\mathcal{C}_{q},p_{{M}})\preccurlyeq
M+\sqrt{\mathrm{Tr}\left(M\right)}\sqrt{\mathrm{Diag}\left(M\right)}-\mathrm{Diag}\left(M\right)$
•
$\mathfrak{C}(\mathcal{C}_{s},p_{{M}})=M+\frac{1-p}{p}\mathrm{Diag}\left(M\right)$
•
$\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})=\frac{1}{p}\left((\alpha-\beta)M+\beta\mathrm{Tr}\left(M\right)\mathrm{I}_{d}\right)$
with $\alpha=\frac{h+2}{d+2}$ and $\beta=\frac{d-h}{(d-1)(d+2)}$ •
$\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{M}})=\frac{d(h-1)}{h(d-1)}M+\left(\frac{d}{h}-\frac{d(h-1)}{h(d-1)}\right)\mathrm{Diag}\left(M\right)$
• $\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})=\frac{1}{p}M$ .

Proof

In this proof, we denote $\mathcal{F}$ the $\sigma$-field generated by the
random sampling of $E\sim p_{M}\in\mathcal{P}_{M}$, and $\mathcal{G}$ the
$\sigma$-field generated by the noise from the compression process. Let $E\sim
p_{M}\in\mathcal{P}_{M}$.

Quantization. By definition, we have
$\mathcal{C}_{q}(E)=\|E\|_{2}\mathrm{sign}(E)\odot\chi$, with
$\chi=\left(\mathrm{Bern}(\frac{|E_{i}|}{\|E\|_{2}})\right)_{i=1}^{d}$. It
follows that $\mathcal{C}_{q}(E)^{\otimes
2}=\|E\|_{2}^{2}\mathrm{sign}(E)^{\otimes 2}\odot\chi^{\otimes 2}$.

Because:

$\displaystyle\mathbb{E}\left[\chi^{\otimes 2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}\right]=\left\\{\begin{array}[]{l}\frac{\displaystyle|E_{i}|}{\displaystyle\|E\|_{2}}\quad\text{if}\quad
i=j\vspace{1em}\\\ \frac{\displaystyle|E_{i}|\leavevmode\nobreak\
|E_{j}|}{\displaystyle\|E\|_{2}^{2}}\quad\text{else,}\end{array}\right.$

and considering that $\mathrm{sign}(E)^{\otimes
2}=\begin{pmatrix}1&&\mathrm{sign}(E_{i})\mathrm{sign}(E_{j})\\\ &\ddots&\\\
\mathrm{sign}(E_{i})\mathrm{sign}(E_{j})&&1\end{pmatrix}$ , we have:

$\displaystyle\mathbb{E}\left[\mathcal{C}_{q}(E)^{\otimes
2}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\mathcal{F}\right]=\left\\{\begin{array}[]{l}\|E\|_{2}\leavevmode\nobreak\
|E_{i}|\quad\text{if}\quad i=j\,,\vspace{1em}\\\
E_{i}E_{j}\quad\text{else.}\end{array}\right.$

Taking the complete expectation gives:

$\displaystyle\mathbb{E}\left[\mathcal{C}_{q}(E)^{\otimes
2}\right]=\left\\{\begin{array}[]{l}\mathbb{E}\left[\|E\|_{2}\leavevmode\nobreak\
|E_{i}|\right]\quad\text{if}\quad i=j\vspace{1em}\\\
M_{ij}\quad\text{else.}\end{array}\right.$

Changing the diagonal to make appear $M$, we obtain:

$\mathbb{E}\left[\mathcal{C}_{q}(E)^{\otimes
2}\right]=M+\mathbb{E}\left[\|E\|_{2}\mathrm{Diag}\left(|E_{i}|\right)_{i=1}^{d}\right]-\mathbb{E}\left[\mathrm{Diag}\left(E_{i}^{2}\right)_{i=1}^{d}\right]\,.$

Furthermore, we first have that
$\mathbb{E}\left[\mathrm{Diag}\left(E_{i}^{2}\right)_{i=1}^{d}\right]=\mathrm{Diag}\left(M\right)$
and secondly, by Cauchy-Schwarz Equation S3 that:

$\mathbb{E}\left[\|E\|_{2}\mathrm{Diag}\left(|E_{i}|\right)_{i=1}^{d}\right]^{2}\preccurlyeq\mathbb{E}\left[\|E\|_{2}^{2}\right]\mathbb{E}\left[\mathrm{Diag}\left(E_{i}^{2}\right)_{i=1}^{d}\right]=\mathrm{Tr}\left(M\right)\mathrm{Diag}\left(M\right)\,,$

which finally gives $\mathbb{E}\left[\mathcal{C}_{q}(E)^{\otimes
2}\right]\preccurlyeq
M+\sqrt{\mathrm{Tr}\left(M\right)}\sqrt{\mathrm{Diag}\left(M\right)}-\mathrm{Diag}\left(M\right)\,.$

Sparsification. By definition, we have $\mathcal{C}_{s}(E)=\frac{1}{p}B\odot
E\in\mathbb{R}^{d}$, with $B\sim\left(\text{Bern}(p)\right)_{i=1}^{d}$, thus
$\mathcal{C}_{s}(E)^{\otimes 2}=\frac{1}{p^{2}}B^{\otimes 2}\odot E^{\otimes
2}$. Taking the expectation w.r.t. to the $\sigma$-filtration $\mathcal{F}$,
we have $\mathbb{E}\left[\mathcal{C}_{s}(E)^{\otimes 2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}\right]=\frac{1}{p^{2}}P\odot
E^{\otimes 2}$ with $P=\begin{pmatrix}p&&p^{2}\\\ &\ddots&\\\
p^{2}&&p\end{pmatrix}\,,$ because for all $i,j$ in $\llbracket 1,d\rrbracket$,
we have $\mathbb{E}\left[B_{i}^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}\right]=p$ and
$\mathbb{E}\left[B_{i}B_{j}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\mathcal{F}\right]=p^{2}$. This naturally gives:
$\mathbb{E}\left[\mathcal{C}_{s}(E)^{\otimes 2}\right]=\frac{1}{p^{2}}P\odot
M$.

Sketching. The proof is more complex and therefore is given separately, in
Subsection E.2.3.

Rand-$h$. By definition, we have
$\mathcal{C}_{\mathrm{rd}h}(E):=\frac{d}{h}B(S)\odot E$ with
$S\sim\mathrm{Unif}(\mathcal{P}_{h}([d]))$ and $B(S)_{i}=\mathbb{1}_{i\in S}$,
thus $\mathcal{C}_{\mathrm{rd}h}(E)^{\otimes 2}=\frac{1}{p^{2}}B^{\otimes
2}\odot E^{\otimes 2}$ ($p=h/d$). We have that for any $i,j$ in
$\\{1,\dots,d\\}$, $B_{i}$ and $B_{j}$ are not independent and that
$B_{i}\sim\left(\text{Bern}(p)\right)$, therefore we have that
$\mathbb{E}[B_{i}^{2}]=p$ and that:
$h^{2}=\left(\sum_{i=1}^{d}B_{i}\right)^{2}=\sum_{i=1}^{d}B_{i}^{2}+\sum_{i\neq
j}B_{i}B_{j}$. Taking expectation, it gives
$h^{2}=h+d(d-1)\mathbb{E}[B_{i}B_{j}]$ i.e.
$\mathbb{E}[B_{i}B_{j}]=\frac{h(h-1)}{d(d-1)}$. Taking the expectation w.r.t.
to the $\sigma$-filtration $\mathcal{F}$, we have :

$\mathbb{E}\left[\mathcal{C}_{\mathrm{rd}h}(E)^{\otimes 2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\mathcal{F}\right]=\frac{d(h-1)}{h(d-1)}E^{{\otimes
2}}+\left(\frac{d}{h}-\frac{d(h-1)}{h(d-1)}\right)\mathrm{Diag}\left(E^{{\otimes
2}}\right)\,.$

And taking full expectation allows conclusion.

Partial Participation. This result is straightforward.

###  E.2 Variance and covariance of sketching

In this Subsection, we compute the expectation, the variance, and the
covariance of sketching. In Subsection E.2.1, we give the proof principle of
our computation, in Subsection E.2.2, we compute the expectation and the
variance, and in Subsection E.2.3, we compute the covariance.

We thank Baptiste Goujaud (École polytechnique, CMAP) who greatly helped to
prove the following.

####  E.2.1 Proof principle

Let $y$ in $\mathbb{R}^{d}$ with $\left\|y\right\|^{2}=1$, and $x$ in
$\mathbb{R}^{d}$. By Definition 4, for $\Phi$ in $\mathbb{R}^{h\times d}$, we
have $\mathcal{C}_{\Phi}(x)=\frac{1}{p}\Phi^{\dagger}\Phi x$ with
$\Phi^{\dagger}=\Phi^{\top}(\Phi\Phi^{T})^{-1}$ and $p=h/d$.

To compute the expectation, the variance, and the covariance of
$\mathcal{C}_{\Phi}(x)$, the idea is to compute
$\mathbb{E}[y^{\top}C_{\Phi}(x)]$ and $\mathbb{E}[(y^{\top}C_{\Phi}(x))^{2}]$
by establishing Equation S27 which allows controlling the randomness of
sketching by using Equation S28. To establish Equation S27, first observe that
$pC_{\Phi}(\cdots)$ is a projector into a subspace of dimension $h$, indeed we
have $(pC_{\Phi}\odot pC_{\Phi})(x)=pC_{\Phi}(x)$. Then there exists a random
matrix $P$ in $\mathcal{O}_{d}$ s.t. $pC_{\Phi}(x)=P^{\top}J_{h}Px$. It leads
to:

$\displaystyle y^{\top}C_{\Phi}(x)$
$\displaystyle=\frac{1}{p}y^{\top}P^{\top}J_{h}Px=\frac{1}{p}(Py)^{\top}J_{h}(Px)\,.$

Now we note $X=Px/\|x\|$ and $Y=Py$, hence
$y^{\top}C_{\Phi}(x)=\frac{\|x\|}{p}Y^{\top}J_{h}X$, and because $P$ is in
$\mathcal{O}_{d}$, we have:

$\displaystyle\left\\{\begin{array}[]{ll}\left\|X\right\|^{2}=1\\\
\left\|Y\right\|^{2}=\left\|y\right\|^{2}=1\\\ \left\langle
X,Y\right\rangle=\left\langle x,y\right\rangle/\|x\|\,.\end{array}\right.$

Furthermore, $P$ is a random projector, it follows that $X$ and $Y$ are
sampled uniformly from the zero-center sphere of radius 1; i.e.
$X\sim\mathrm{Unif}(\mathcal{S}_{d}(0,1))$ and
$Y\sim\mathrm{Unif}(\mathcal{S}_{d}(0,1))$. However, $X$ and $Y$ are not
independent, this is why, we consider that
$X\sim\mathrm{Unif}(\mathcal{S}_{d}(0,1))$ and write $Y$ s.t. $Y=aX+bu$ with
$u$ a random vector in $\mathbb{R}^{d}$ of norm $1$ orthogonal to $X$, that is
to say, $u|X$ is uniformly sampled on a zero-centered hyper-sphere of radius
$1$ orthogonal to the vector $X$ (see illustration on Figure S3). It comes
that:

$\displaystyle
y^{\top}C_{\Phi}(x)=\frac{\|x\|}{p}Y^{\top}J_{h}X=\frac{\|x\|}{p}(aX^{\top}+bu^{T})J_{h}X=\frac{\|x\|}{p}(aX^{\top}J_{h}X+bu^{\top}J_{h}X)\,.$
(S27)

Observe that for any $i,j$ in $\\{1,\cdots,d\\}$, $X_{i}$, $X_{j}$ (resp.
$u_{i}$, $u_{j}$) have the same law, it results to:

$\displaystyle\forall(i,j)\in\\{1,\cdots,d\\}^{2},\leavevmode\nobreak\ \forall
k\in\mathbb{N},\qquad\mathbb{E}[X_{i}^{k}]=\mathbb{E}[X_{j}^{k}]\quad\text{and}\quad\mathbb{E}[u_{i}^{k}]=\mathbb{E}[u_{j}^{k}]\,.$
(S28)

This property is the key to compute the expectation, the variance, and the
covariance of sketching.

Figure S3: Sphere zero-center with radius 1: $X$ and $u$ are orthogonal.

We now compute $a$ and $b$. First, by definition, we have:

$\displaystyle\frac{\left\langle x,y\right\rangle}{\|x\|}=\left\langle
X,Y\right\rangle=a\left\|X\right\|^{2}=a\,,$

then we write that:

$\displaystyle 1=\left\|Y\right\|^{2}=\frac{\left\langle
x,y\right\rangle^{2}}{\|x\|^{4}}\left\|X\right\|^{2}+b^{2}\left\|u\right\|^{2}=\frac{\left\langle
x,y\right\rangle^{2}}{\|x\|^{2}}+b^{2}\,,$

which gives $b=\sqrt{1-\frac{\left\langle x,y\right\rangle^{2}}{\|x\|^{2}}}$.

At the end, we have: $Y=aX+bu=\frac{\left\langle
x,y\right\rangle}{\|x\|}X+\sqrt{1-\frac{\left\langle
x,y\right\rangle^{2}}{\|x\|^{2}}}u$.

####  E.2.2 Expectation and variance of sketching

In this Subsection, we prove that sketching verifies Item L.1 in Lemma 1; for
this purpose, we show that it is unbiased, then we compute its variance.

######  Proposition S3.

Sketching is unbiased and its variance is relatively bounded, i.e., it
verifies Item L.1 in Lemma 1 with $\omega=(1-p)/p$ where $p=h/d$.

Proof  Starting from Equation S27, we have
$y^{\top}C_{\Phi}(x)=\frac{\|x\|}{p}(aX^{\top}J_{h}X+bu^{\top}J_{h}X)$. We
first compute the expectation w.r.t. the $\sigma$-algebra $\sigma(\\{X\\})$
generated by the noise involved in the random vector $X$, it gives:

$\mathbb{E}[y^{\top}C_{\Phi}(x)\leavevmode\nobreak\ |\leavevmode\nobreak\
\sigma(\\{X\\})]=\frac{\|x\|}{p}\sum_{i=1}^{h}aX_{i}^{2}+bX_{i}\mathbb{E}\left[u_{i}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \sigma(\\{X\\})\right]\,.$

Because $u$ is sampled uniformly from the zero-center sphere of radius $1$
s.t. it is orthogonal to $X$, for any $i$ in $\\{1,\cdots,d\\}$, we have
$\mathbb{E}[u_{i}\leavevmode\nobreak\ |\leavevmode\nobreak\
\sigma(\\{X\\})]=0$, hence taking full expectation, we obtain:

$\mathbb{E}[y^{\top}C_{\Phi}(x)]=\frac{\|x\|}{p}\sum_{i=1}^{h}a\mathbb{E}[X_{i}^{2}]\,.$

Using Equation S28, we have
$\mathbb{E}[X_{i}^{2}]=\frac{1}{d}\sum_{j=1}^{d}\mathbb{E}[X_{j}^{2}]$, next
recalling that $p=h/d$ and $\|X\|^{2}=1$, it leads to
$\mathbb{E}[y^{\top}C_{\Phi}(x)]=a\|x\|\mathbb{E}[\sum_{j=1}^{d}X_{j}^{2}]=a\|x\|\mathbb{E}[\|X\|^{2}]=a\|x\|$.
And because $a=\left\langle x,y\right\rangle/\|x\|$, we have at the end that
$\mathbb{E}[C_{\Phi}(x)]=x$. Now we compute the variance:

$\displaystyle\mathbb{E}[C_{\Phi}(x)^{\top}C_{\Phi}(x)]=\frac{1}{p^{2}}\mathbb{E}[x^{\top}P^{\top}J_{h}PP^{\top}J_{h}Px]=\frac{1}{p^{2}}\mathbb{E}[x^{\top}P^{\top}J_{h}Px]=\frac{\left\|x\right\|^{2}}{p^{2}}\mathbb{E}[X^{\top}J_{h}X]\,.$

$\mathbb{E}[X^{\top}J_{h}X]$ has been computed above and is equal to $p$, it
results that
$\mathbb{E}[C_{\Phi}(x)^{\top}C_{\Phi}(x)]=\left\|x\right\|^{2}/p$. In the
end, sketching verifies Lemma 1 with $\omega=(1-p)/p$.

####  E.2.3 Covariance of sketching.

In this Subsection, we compute the covariance of sketching. For the sake of
demonstration, we need to compute the $4^{\mathrm{th}}$-moment of $X_{1}$ and
the $2^{\mathrm{nd}}$-moment of $u_{1}$. For any $i$ in $[d]$ and any vector
$v$ in $\mathbb{R}^{d}$, we note $v_{-i}=(v_{j})_{j\in[d],j\neq i}$ in
$\mathbb{R}^{d-1}$.

Computing the $4^{\mathrm{th}}$-moment of $X_{1}$.

The marginal density of $X_{1}$ is $f_{X_{1}}:x\mapsto
B(\frac{d-1}{2},\frac{1}{2})^{-1}(1-x^{2})^{(d-3)/2}$ where $B$ is the beta
function defined as
$B:x,y\mapsto\int_{0}^{1}t^{x-1}(1-t)^{y-1}=2\int_{0}^{\pi/2}\sin^{2x-1}(t)\cos^{2y-1}(t)\mathrm{d}t$.
This result can be obtained either by an application of the formula for the
surface area of a sphere (Li, 2010; Sidiropoulos, 2014), either by writing
that $X_{1}=\frac{Z_{1}}{\|Z\|}$ with $Z$ a Gaussian vector with $d$
components. Therefore we have that:

$\mathbb{E}[X_{1}^{4}]=\frac{\int_{-1}^{1}x^{4}(1-x^{2})^{(d-3)/2}\mathrm{d}x}{2\int_{0}^{\pi/2}\sin^{d-2}(t)\mathrm{d}t}\stackrel{{\scriptstyle\mathrm{(i)}}}{{=}}\frac{2\int_{0}^{\pi/2}\cos^{4}(t)\sin^{d-2}(t)\mathrm{d}t}{2\int_{0}^{\pi/2}\sin^{d-2}(t)\mathrm{d}t}\stackrel{{\scriptstyle\mathrm{(ii)}}}{{=}}\frac{W_{d-2}-2W_{d}+W_{d+2}}{W_{d-2}}\,,$

where at (i) we set $x=\cos(t)$ and at (ii) we make appears the Wallis’
integrals defined for any $n$ in $\mathbb{N}$ as
$W_{n}=\int_{0}^{\pi/2}\sin^{n}(t)\mathrm{d}t$. Furthermore, we have the
following recursion using integration by parts:
$W_{d+2}=\frac{d+1}{d+2}W_{d}$, therefore, we have:

$\displaystyle\mathbb{E}[X_{1}^{4}]=\left(1-\frac{2(d-1)}{d}+\frac{(d-1)(d+1)}{d(d+2)}\right)=\frac{3}{d(d+2)}\,.$
(S29)

Computing the $2^{\mathrm{nd}}$-moment of $u_{1}$ w.r.t the $\sigma$-algebra
$\sigma({X})$.

Figure S4: Parallel hyperplanes $P$ and $P^{\prime}$ with the sphera $S$.

We define three $(d-2)$–dimensional manifolds, two parallel hyperplanes
$P,P^{\prime}$ and a sphere $S$, as follows:

$\left\\{\begin{array}[]{l}P=\\{\tilde{u}\in\mathbb{R}^{d-1}\mid\langle\tilde{u},X_{-i}\rangle=-X_{i}u_{i}\\}\\\
P^{\prime}=\\{\tilde{u}\in\mathbb{R}^{d-1}\mid\langle\tilde{u},X_{-i}\rangle=0\\}\\\
S=S_{d-1}(0,\sqrt{1-u_{1}^{2}})\end{array}\right.$

Obviously $u_{-i}$ is in $P\cap S$; then we decompose $u_{-i}$ in two terms
$n+v$, with $v\sim\mathrm{Unif}(P^{\prime})$ orthogonal to $X$ and independent
of $u_{i}$: $n$ is the center of the sphere $S\cap P$ and $v$ is its radius,
$n$ corresponds also to the normal vector of both $P,P^{\prime}$ with norm
equal to the distance between the two hyperplanes, hence $n=\frac{\langle
u_{-i},X_{-i}\rangle}{\|X_{-i}\|^{2}}X_{-i}=-\frac{u_{i}X_{i}}{\|X_{-i}\|^{2}}X_{-i}$.

First, because $u_{-1}\in S$, we have $\|n+v\|^{2}=1-u_{1}^{2}$, next by
Pythagorean theorem this is equivalent to
$\|v\|^{2}=1-u_{1}^{2}-\|n\|^{2}=1-\frac{u_{1}^{2}}{\|X_{-1}\|^{2}}$. Second,
because $u_{-1}\in P$, we have $u_{1}=\frac{-\langle
u_{-1},X_{-1}\rangle}{X_{1}}$, that is to say the probability density function
of $u_{1}\mid X$ is proportional to the number of possible values for
$u_{-1}$, which corresponds to the surface area of the hypersphere $P\cap S$.
This surface is proportional to the radius
$\|v\|^{d-4}=(1-\frac{u_{1}^{2}}{\|X_{-1}\|^{2}})^{(d-4)/2}$ given that $P\cap
S$ is a $(d-3)$–dimensional manifold, therefore:

$\displaystyle\mathbb{E}[u_{1}^{2}\leavevmode\nobreak\ |\leavevmode\nobreak\
\sigma(\\{X\\})]=\frac{\int_{-\|X_{-1}\|}^{\|X_{-1}\|}x^{2}\left(1-\frac{x^{2}}{\|X_{-i}\|^{2}}\right)^{(d-4)/2}\mathrm{d}x}{\int_{-\|X_{-1}\|}^{\|X_{-1}\|}\left(1-\frac{x^{2}}{\|X_{-i}\|^{2}}\right)^{(d-4)/2}\mathrm{d}x}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{(i)}}}{{=}}\frac{\|X_{-1}\|^{2}\int_{-1}^{1}y^{2}\left(1-y^{2}\right)^{(d-4)/2}\mathrm{d}y}{\int_{-1}^{1}\left(1-y^{2}\right)^{(d-4)/2}\mathrm{d}y}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{(ii)}}}{{=}}\|X_{-1}\|^{2}\frac{W_{d-3}-W_{d-1}}{W_{d-3}}\,,$

where at (i) we set $y=\frac{x}{\|X_{-1}\|}$ and at (ii) we reuse the previous
computations to make appear the Wallis’ integral. In the end, we obtain:

$\displaystyle\mathbb{E}[u_{1}^{2}\leavevmode\nobreak\ |\leavevmode\nobreak\
\sigma(\\{X\\})]=(1-\frac{d-2}{d-1})\|X_{-1}\|^{2}=\frac{\|X_{-1}\|^{2}}{d-1}\,.$
(S30)

Note that this result is consistent with the fact that
$\sum_{i=1}^{d}\mathbb{E}[u_{i}^{2}\leavevmode\nobreak\ |\leavevmode\nobreak\
\sigma(\\{X\\})]=\frac{d-\sum_{i=1}^{d}X_{i}^{2}}{d-1}=1$. Now we can compute
the covariance of the sketching operator.

######  Proposition S4.

Let $x$ in $p_{M}$, the covariance of sketching is equal to:

$\mathbb{E}[\mathcal{C}_{\Phi}(x)^{{\otimes
2}}]=\frac{1}{p}((\alpha-\beta)M+\beta\mathrm{Tr}\left(M\right)\mathrm{I}_{d})\,,\vspace{-0.5cm}$

with $\alpha=\frac{h+2}{d+2}$ and $\beta=\frac{d-h}{(d-1)(d+2)}$.

Proof

Let $x$ in $\mathbb{R}^{d}$ and $y$ in $\mathbb{R}^{d}$ with
$\left\|y\right\|^{2}=1$, starting from Equation S27, we have:

$\displaystyle(y^{\top}C_{\Phi}(x))^{2}$
$\displaystyle=\frac{\|x\|^{2}}{p^{2}}(aX^{\top}J_{h}X+bu^{\top}J_{h}X)^{2}$
$\displaystyle=\frac{\|x\|^{2}}{p^{2}}\Bigg{(}a^{2}(X^{\top}J_{h}X)^{2}+2ab(X^{\top}J_{h}Xu^{\top}J_{h}X)+b^{2}(u^{\top}J_{h}X)^{2}\Bigg{)}\,.$

First term. Taking expectation, we have
$\mathbb{E}[(X^{\top}J_{h}X)^{2}]=\sum_{i=1}^{h}\left(\mathbb{E}[X_{i}^{4}]+\sum_{j=1,j\neq
i}^{h}\mathbb{E}[X_{i}^{2}X_{j}^{2}]\right)$. However:

$\displaystyle\sum_{j=1,j\neq i}^{h}\mathbb{E}[X_{i}^{2}X_{j}^{2}]$
$\displaystyle=\mathbb{E}\left[X_{i}^{2}\sum_{j=1,j\neq
i}^{h}X_{j}^{2}\right]\stackrel{{\scriptstyle\mathrm{(i)}}}{{=}}\mathbb{E}\left[X_{i}^{2}\sum_{j=1,j\neq
i}^{h}\frac{1}{d-1}\sum_{k=1,k\neq i}^{d}X_{k}^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\mathrm{(ii)}}}{{=}}\frac{h-1}{d-1}\mathbb{E}\left[X_{i}^{2}(1-X_{i}^{2})\right]\,,$

where we use at line (i) Equation S28 and at line (ii)
$\sum_{i=1}^{d}X_{i}^{2}=1$. It follows that:

$\displaystyle\mathbb{E}[(X^{\top}J_{h}X)^{2}]$
$\displaystyle=\sum_{i=1}^{h}\left(\frac{d-h}{d-1}\mathbb{E}[X_{i}^{4}]+\frac{h-1}{d-1}\mathbb{E}\left[X_{i}^{2}\right]\right)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{(i)}}}{{=}}\frac{h(d-h)}{d-1}\mathbb{E}[X_{1}^{4}]+\frac{h-1}{d-1}\sum_{i=1}^{h}\mathbb{E}\left[X_{i}^{2}\right]$
$\displaystyle\stackrel{{\scriptstyle\mathrm{(iii)}}}{{=}}\frac{h(d-h)}{d-1}\mathbb{E}[X_{1}^{4}]+\frac{h(h-1)}{d(d-1)}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{eq.\leavevmode\nobreak\
\ref{app:eq:fourth_moment_X1}}}}{{=}}\frac{3h(d-h)}{d(d-1)(d+2)}+\frac{h(h-1)}{d(d-1)}=\frac{h(h+2)}{d(d+2)}:=\alpha^{\prime}\,.$

Where we considered at line (i) that for any $i$ in $\\{1,\cdots,h\\}$,
$\mathbb{E}[X_{i}^{4}]=\mathbb{E}[X_{1}^{4}]$, and at line (ii) that
$\sum_{i=1}^{h}\mathbb{E}\left[X_{i}^{2}\right]=\frac{h}{d}\mathbb{E}[\|X\|^{2}]=h/d$.

Second term. We compute the expectation w.r.t. the $\sigma$-algebra
$\sigma(\\{X\\})$ generated by the noise involved in the random vector $X$. It
gives $\mathbb{E}\left[X^{\top}J_{h}Xu^{\top}J_{h}X\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \sigma(\\{X\\})\right]=0$, because $u|X$ is
uniformly sampled on a zero-centered hyper-sphere, and thus for any $i$ in
$\\{1,\cdots,d\\}$, we have $\mathbb{E}[u_{i}\leavevmode\nobreak\
|\leavevmode\nobreak\ \sigma(\\{X\\})]\leavevmode\nobreak\
=\leavevmode\nobreak\ 0$.

Third term. We have
$(u^{\top}J_{h}X)^{2}=\sum_{i=1}^{h}u_{i}^{2}X_{i}^{2}+\sum_{j=1,j\neq
i}^{h}u_{i}u_{j}X_{i}X_{j}$. On one side, we compute the expectation w.r.t.
the $\sigma$-algebra $\sigma(\\{X\\})$ generated by the noise involved in the
random vector $X$:

$\displaystyle\sum_{i=1}^{h}\mathbb{E}\left[u_{i}^{2}X_{i}^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \sigma(\\{X\\})\right]$
$\displaystyle=\sum_{i=1}^{h}X_{i}^{2}\mathbb{E}\left[u_{i}^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\
\sigma(\\{X\\})\right]\stackrel{{\scriptstyle\mathrm{eq.\leavevmode\nobreak\
\ref{app:eq:second_moment_u1}}}}{{=}}\frac{1}{d-1}\sum_{i=1}^{h}X_{i}^{2}\|X_{-i}\|^{2}\,.$

Taking full expectation, we have
$\sum_{i=1}^{h}\mathbb{E}[u_{i}^{2}X_{i}^{2}]=\frac{1}{d-1}\sum_{i=1}^{h}\mathbb{E}[X_{i}^{2}(1-X_{i}^{2})]=\frac{h}{d-1}(\frac{1}{d}-\mathbb{E}[X_{1}^{4}])$,
because for any $i$ in $\\{1,\dots,h\\}$,
$\mathbb{E}[X_{i}^{4}]=\mathbb{E}[X_{1}^{4}]$ and
$\sum_{i=1}^{h}\mathbb{E}\left[X_{i}^{2}\right]=\frac{h}{d}\mathbb{E}[\|X\|^{2}]=h/d$.

Let $i$ in $[d]$, on the other side, we compute the expectation w.r.t. the
$\sigma$-algebra $\sigma(\\{X,u_{i}\\})$ generated by the noise involved in
the random vector $X$ and the random variable $u_{i}$, hence we requires to
compute $\mathbb{E}\left[u_{j}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \sigma(\\{X,u_{i}\\})\right]$. To do so, as
before, we decompose $u_{-i}$ in two terms $n+v$ (see Figure S4), with
$v\sim\mathrm{Unif}(P^{\prime})$ orthogonal to $X$ and independent of $u_{i}$,
hence $\mathbb{E}\left[v\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\sigma(\\{X,u_{i}\\})\right]=0$. It gives that
$\mathbb{E}\left[u_{-i}\leavevmode\nobreak\ \middle|\leavevmode\nobreak\
\sigma(\\{X,u_{i}\\})\right]=-\frac{u_{i}X_{i}}{\|X_{-i}\|^{2}}X_{-i}$.
Thereby, replacing for any coordinate $j\neq i$ in $[d]$ the value of $u_{-i}$
and taking expectation w.r.t. the $\sigma$-algebra $\sigma(\\{X\\})$, we
obtain:

$\displaystyle\sum_{i=1}^{h}\sum_{j=1,j\neq
i}^{h}X_{i}X_{j}\mathbb{E}\left[u_{i}u_{j}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \sigma(\\{X\\})\right]$
$\displaystyle=-\sum_{i=1}^{h}\sum_{j=1,j\neq i}^{h}\frac{\displaystyle
1}{\displaystyle\|X_{-i}\|^{2}}X_{i}^{2}X_{j}^{2}\mathbb{E}\left[u_{i}^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \sigma(\\{X\\})\right]$
$\displaystyle\stackrel{{\scriptstyle\mathrm{eq.\leavevmode\nobreak\
\ref{app:eq:second_moment_u1}}}}{{=}}-\frac{1}{d-1}\sum_{i=1}^{h}\sum_{j=1,j\neq
i}^{h}X_{i}^{2}X_{j}^{2}$
$\displaystyle=-\frac{1}{d-1}\sum_{i=1}^{h}\sum_{j=1,j\neq
i}^{h}X_{i}^{2}\frac{1-X_{i}^{2}}{d-1}\,.$

Finally, we have: $\sum_{i=1}^{h}\sum_{j=1,j\neq
i}^{h}\mathbb{E}[X_{i}X_{j}u_{i}u_{j}]=-\frac{h(h-1)}{d(d-1)^{2}}(1-\sum_{i=1}^{d}\mathbb{E}[X_{i}^{4}])$.
Putting together the two terms, we have that:

$\displaystyle\mathbb{E}\left[(u^{\top}J_{h}X)^{2}\right]$
$\displaystyle=\frac{h}{d-1}(\frac{1}{d}-\mathbb{E}[X_{i}^{4}])-\frac{h(h-1)}{d(d-1)^{2}}(1-d\mathbb{E}[X_{1}^{4}])\stackrel{{\scriptstyle\mathrm{eq.\leavevmode\nobreak\
\ref{app:eq:fourth_moment_X1}}}}{{=}}\frac{h(d-h)}{d(d-1)(d+2)}:=\beta^{\prime}\,.$

In the end, we have
$\mathbb{E}[(y^{\top}C_{\Phi}(x))^{2}]=\frac{\|x\|^{2}}{p^{2}}(a^{2}\alpha^{\prime}+b^{2}\beta^{\prime})$.
And because $\|y\|^{2}=1$, $a=\left\langle x,y\right\rangle/\|x\|$ and
$b=\sqrt{1-\left\langle x,y\right\rangle^{2}/\|x\|^{2}}$, replacing them by
their values gives:

$\displaystyle y^{\top}\mathbb{E}[C_{\Phi}(x))^{{\otimes 2}}]y$
$\displaystyle=\frac{\left\|x\right\|^{2}}{p^{2}}\left(\alpha^{\prime}\frac{\left\langle
x,y\right\rangle^{2}}{\|x\|^{2}}+\beta^{\prime}\left(y^{\top}y-\frac{\left\langle
x,y\right\rangle^{2}}{\|x\|^{2}}\right)\right)\,,$

hence $\mathbb{E}[C_{\Phi}(x))^{{\otimes
2}}]=\frac{1}{p^{2}}\left((\alpha^{\prime}-\beta^{\prime})xx^{\top}+\beta^{\prime}\left\|x\right\|^{2}\mathrm{I}_{d}\right)$.
To conclude, we consider that $x$ is a random variable sampled from a
distribution $p_{M}$, then taking expectation on this random variable we have:
$\mathbb{E}C_{\Phi}(x)^{{\otimes
2}}=\frac{1}{p}\left((\alpha-\beta)M+\beta\mathrm{Tr}\left(M\right)\mathrm{I}_{d}\right)$,
with $\alpha=\frac{\alpha^{\prime}}{p}=\frac{h+2}{d+2}$ and
$\beta=\frac{\beta^{\prime}}{p}=\frac{d-h}{(d-1)(d+2)}$.

###  E.3 Proof of Propositions 3 and 4

In this Subsection, we give the proof of Propositions 3 and 4 which provides
generic comparisons between the asymptotic convergence rate of compressors. We
first give a lemma resulting from the Cauchy-Schwarz’s inequality necessary to
establish these proofs.

######  Lemma S9 (Cauchy-Schwarz’s inequality on matrices’ traces).

For any matrix $M$ in $\mathbb{R}^{d\times d}$, we have
$\mathrm{Tr}\left(M\right)\mathrm{Tr}\left(M^{-1}\right)\leavevmode\nobreak\
\geq\leavevmode\nobreak\ d^{2}$, with strict inequalities if $M$ is not
proportional to $\mathrm{I}_{d}$. And if $M$ is with constant diagonal equal
to $c$ in $\mathbb{R}$, we have $c\mathrm{Tr}\left(M^{-1}\right)\geq d$.

Proof  Let $M$ in $\mathbb{R}^{d\times d}$, using the Cauchy-Schwarz
inequality, we have:

$d^{2}=\mathrm{Tr}\left(\mathrm{I}_{d}\right)^{2}=\mathrm{Tr}\left(M^{1/2}M^{-1/2}\right)^{2}\stackrel{{\scriptstyle\mathrm{C.S}}}{{\leq}}\mathrm{Tr}\left(M\right)\mathrm{Tr}\left(M^{-1}\right)\,,$

and we have equality if $M$ is proportional to $\mathrm{I}_{d}$.

Now we give the demonstration of Propositions 3 and 4. On Figure S5, we
complete the numerical illustration provided in Subsection 3.3.1 by
illustrating the scenario of standardized features, i.e., when the diagonal of
$M$ is the identity.

Figure S5: $H$ not diagonal, scenario using features standardization. Scatter
plot of $(x_{k})_{i=1}^{K}$/ $(\mathcal{C}(x_{k}))_{i=1}^{K}$ with its ellipse
$\mathcal{E}_{\mathrm{Cov}\left[x_{k}\right]}$/$\mathcal{E}_{\mathrm{Cov}\left[\mathcal{C}(x_{k})\right]}$.

######  Proposition S5 (Comparison between
${\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{s}},\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\Phi}}$,
$\omega=d/h-1$).

We consider
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{s}}$,
$\mathcal{C}_{\mathrm{rd}h},\mathcal{C}_{\Phi}\\}$ with $p=h/d$, such that
$\mathcal{C}$ always satisfies Lemma 1 with $\omega=d/h-1$. For any matrix
$M\in\mathbb{R}^{d\times d}$:

  1. 1.

If $M$ is diagonal, then:

     * •

$\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})=\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})=\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{M}})=\frac{d}{h}M$,

     * •

$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}/\mathrm{s}/\mathrm{rd}h},p_{{M}})M^{-1}\right)\leq\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})M^{-1}\right)$.

  2. 2.

Moreover, for any matrix $M$ with a _constant diagonal_ (e.g., after
standardization), we have:

$\mathrm{Tr}(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1})\leq\mathrm{Tr}(\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})M^{-1})\leq\mathrm{Tr}(\mathfrak{C}(\mathcal{C}_{s},p_{{M}})M^{-1})\leq\mathrm{Tr}(\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{M}})M^{-1})\,.$

With strict inequalities if $M$ is not proportional to $\mathrm{I}_{d}$.

Proof

Let $M$ in $\mathbb{R}^{d\times d}$ and take $p=h/d$.

##### Proof of Item 1 in Proposition 3.

In the diagonal case, the first equalities are straightforward as we have
$\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})=\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})=\mathfrak{C}(\mathcal{C}_{\mathrm{rd}1},p_{{M}})=\frac{d}{h}M$.
Next, we have (regardless if $M$ is diagonal or not):

$\displaystyle\mathrm{Tr}\left(\left(\mathfrak{C}(\mathcal{C}_{\mathrm{\Phi}},p_{{M}})-\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})\right)M^{-1}\right)$
$\displaystyle=(\frac{h+1}{d+2}+\delta_{hd}-1)\frac{\mathrm{Tr}\left(\mathrm{I}_{d}\right)}{p}+(1-\frac{h-1}{d-1})\frac{\mathrm{Tr}\left(M\right)\mathrm{Tr}\left(M^{-1}\right)}{p(d+2)}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{\lx@cref{creftypecap~refnum}{app:lem:cs_matrix}}}}{{\geq}}\frac{d}{p}\left(\frac{h+1}{d+2}+\delta_{hd}-1+\frac{d}{d+2}(1-\frac{h-1}{d-1})\right)$
$\displaystyle=0\,.$

##### Proof of Item 2 in Proposition 3.

Suppose now that $\mathrm{Diag}\left(M\right)=c\mathrm{I}_{d}$, then we have
$\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})=\frac{d}{h}M$,
$\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})=M+(\frac{d}{h}-1)c\mathrm{I}_{d}$,
$\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{M}})=\frac{d(h-1)}{h(d-1)}M+\frac{d}{h}(1-\frac{h-1}{d-1})c\mathrm{I}_{d}$
and
$\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})=\frac{d}{h}\left((\frac{h+1}{d+2}-\delta_{hd})M+\left(1-\frac{h-1}{d-1}\right)\frac{\mathrm{Tr}\left(M\right)}{d+2}\mathrm{I}_{d}\right)$.
Firstly, from previous item, we have

$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)\leq\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{\Phi}},p_{{M}})\right)M^{-1}\,.$

Secondly, we write:

$\displaystyle\mathrm{Tr}\left(\left(\mathfrak{C}(\mathcal{C}_{\Phi},p_{{M}})-\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})\right)M^{-1}\right)$
$\displaystyle=\frac{d}{p}(\frac{h+1}{d+2}+\delta_{hd}-\frac{h}{d})$
$\displaystyle\qquad+\frac{c\mathrm{Tr}\left(M^{-1}\right)}{p}\left(\frac{d}{d+2}(1-\frac{h-1}{d-1})-(1-\frac{h}{d})\right)$
$\displaystyle=\frac{d}{p}(\frac{h+1}{d+2}+\delta_{hd}-\frac{h}{d})-\frac{c\mathrm{Tr}\left(M^{-1}\right)}{p}\cdot\frac{(d-2)(d-h)}{d(d-1)(d+2)}$
$\displaystyle\stackrel{{\scriptstyle\mathrm{\lx@cref{creftypecap~refnum}{app:lem:cs_matrix}}}}{{\leq}}\frac{d}{p}\left(\frac{h+1}{d+2}+\delta_{hd}-\frac{h}{d}-\frac{(d-2)(d-h)}{d(d-1)(d+2)}\right)=0\,.$

Thirdly, we have:

$\displaystyle\mathrm{Tr}\left(\left(\mathfrak{C}(\mathcal{C}_{\mathrm{rd}h},p_{{M}})-\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})\right)M^{-1}\right)$
$\displaystyle=\frac{h-d}{h(d-1)}\mathrm{Tr}\left(\mathrm{I}_{d}\right)+\frac{d-h}{h(d-1)}c\mathrm{Tr}\left(M^{-1}\right)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{\lx@cref{creftypecap~refnum}{app:lem:cs_matrix}}}}{{\geq}}\frac{d}{h}\left(\frac{h-d}{d-1}+\frac{d-h}{d-1}\right)=0\,.$

######  Proposition S6 (Comparison between
${\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{s}}}$,
$\omega=\sqrt{d}$ ).

We consider
$\mathcal{C}\in\\{\mathcal{C}_{\mathrm{PP}},\mathcal{C}_{\mathrm{q}},\mathcal{C}_{\mathrm{s}}\\}$
with $p=(\sqrt{d}+1)^{-1}$, such that $\mathcal{C}$ always satisfies Lemma 1
with $\omega=\sqrt{d}$.

  1. 1.

For any symmetric matrix $M$ diagonal, we have:

$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)=\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{s},p_{{M}})M^{-1}\right)\overset{\text{possib.
}\ll}{\leq}\left(1+\frac{1}{\sqrt{d}}\right)\mathrm{Tr}\left(\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)M^{-1}\right)\,.$

  2. 2.

If $M$ is not necessarily diagonal but with a _constant diagonal_ (e.g., after
standardization), then

     * •

$\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)\preccurlyeq\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})$

     * •

$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)\leq\left(1+\frac{1}{\sqrt{d}}\right)\mathrm{Tr}\left(\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)M^{-1}\right)$
.

Proof

Let $M$ in $\mathbb{R}^{d\times d}$ and take $p=\frac{1}{1+\sqrt{d}}$.

##### Proof of Item 1 in Proposition 4.

In the diagonal case with $p=\frac{1}{1+\sqrt{d}}$, we have
$\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)=\sqrt{\mathrm{Tr}\left(M\right)}\sqrt{M}$
and $\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})=(1+\sqrt{d})M$, hence
$\mathrm{Tr}\left(\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)M^{-1}\right)=\sqrt{\mathrm{Tr}\left(M\right)}\mathrm{Tr}\left(\sqrt{M^{-1}}\right)$
and
$\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)=(1+\sqrt{d})d$.
Noting $(\lambda_{i})_{i\in[d]}$ the eigenvalues of $M$, and using the Cauchy-
Schwarz inequality’s, we have:

$\displaystyle d^{2}$
$\displaystyle=\left(\sum_{i=1}^{d}1\right)^{2}=\left(\sum_{i=1}^{d}\lambda_{i}^{1/4}\lambda_{i}^{-1/4}\right)^{2}\stackrel{{\scriptstyle\mathrm{C.S}}}{{\leq}}\left(\sum_{i=1}^{d}\lambda_{i}^{1/2}\right)\left(\sum_{i=1}^{d}\lambda_{i}^{-1/2}\right)$
$\displaystyle\stackrel{{\scriptstyle\mathrm{C.S}}}{{\leq}}\sqrt{\sum_{i=1}^{d}\lambda_{i}}\sqrt{\sum_{i=1}^{d}1}\left(\sum_{i=1}^{d}\lambda_{i}^{-1/2}\right)=\sqrt{d\mathrm{Tr}\left(M\right)}\mathrm{Tr}\left(M^{-1/2}\right)=\sqrt{d}\mathrm{Tr}\left(\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)M^{-1}\right)\,.$

Which follows that
$\mathrm{Tr}\left(\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)M^{-1}\right)\geq
d^{3/2}=\sqrt{d}(1+\sqrt{d})^{-1}\mathrm{Tr}\left(\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})M^{-1}\right)$
and it allows to conclude.

##### Proof of Item 2 in Proposition 4.

Suppose now that $\mathrm{Diag}\left(M\right)=c\mathrm{I}_{d}$, then we have
$\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})=(\sqrt{d}+1)M$,
$\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)=M+(\sqrt{d}-1)c\mathrm{I}_{d}$,
and
$\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})=M+c\sqrt{d}\mathrm{I}_{d}$.
Firstly, it follows that:

$\displaystyle\mathfrak{C}(\mathcal{C}_{\mathrm{s}},p_{{M}})-\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)=\left(M+\sqrt{d}c\mathrm{I}_{d}\right)-\left(M+(\sqrt{d}-1)c\mathrm{I}_{d}\right)=c\mathrm{I}_{d}\succcurlyeq
0\,,$

Secondly, we have
$(1+\frac{1}{\sqrt{d}})\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)-\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})=-(1-\frac{1}{\sqrt{d}})M+(\sqrt{d}-\frac{1}{\sqrt{d}})c\mathrm{I}_{d}$,
which gives:

$\displaystyle\mathrm{Tr}\left(\left((\sqrt{d}-\frac{1}{\sqrt{d}})\widetilde{\mathfrak{C}}(\mathcal{C}_{\mathrm{q}},M)-\mathfrak{C}(\mathcal{C}_{\mathrm{PP}},p_{{M}})\right)M^{-1}\right)$
$\displaystyle=(\sqrt{d}-\frac{1}{\sqrt{d}})c\mathrm{Tr}\left(M^{-1}\right)-(1-\frac{1}{\sqrt{d}})\mathrm{Tr}\left(\mathrm{I}_{d}\right)$
$\displaystyle\geq(\sqrt{d}-\frac{1}{\sqrt{d}})d-(1-\frac{1}{\sqrt{d}})d\text{\quad(\lx@cref{creftypecap~refnum}{app:lem:cs_matrix})}$
$\displaystyle\geq d(\sqrt{d}-1)\geq 0\,.$

And the proof is concluded.

###  E.4 Empirical covariances computed on quantum and cifar10

On Table S3, for both quantum and cifar-10, we first plot the covariance
matrix (1) without any processing and (2) with standardization. In this latter
case, we then plot the covariances induced by quantization and sparsification
for $\omega=1$ and $8$. For quantum, without standardization, only four points
are visible; it is caused by some rows having extremely large values at
features $27$ and $43$, resulting in a feature mean $100$ times greater than
the others.

Looking at the covariance induced by the compressors, we observe that for
small $\omega$, quantization better preserves the matrix structure compared to
sparsification. This fact is consistent with Figure 6 where is given the trace
of $\mathfrak{C}(\mathcal{C}_{M},p_{{H}})M^{-1}$ for these eight covariances:
the traces for quantization are indeed smaller than for sparsification. This
is also consistent with Figures 7(c) and 7(f) where $\omega=1$ and where
quantization outperforms sparsification.

Table S3: (1) Data covariances for quantum and cifar-10. (2) Covariance
$\mathfrak{C}(\mathcal{C}_{M},p_{{H}})$ w./w.o. standardization for
quantization and sparsification; see Figure 6 to have the corresponding trace
of $\mathfrak{C}(\mathcal{C}_{M},p_{{H}})M^{-1}$.

| $M$ | Quantization | Sparsification
---|---|---|---
| raw-data standardized |  $\omega=1$ $\omega=8$ |  $\omega=1$ $\omega=8$
quantum |  |  |
cifar-10 |  |  |

##  Appendix F Technical results on federated learning.

###  F.1 Validity of the assumptions made on the random fields in the case of
covariate-shift

In this Subsection, we examine the setting of federated and compressed LSR
under the scenario of covariate-shift (Subsection 4.1). Specifically, we
consider the case where for any $i,j$ in $\llbracket 1,N\rrbracket$, we have
heterogeneous covariances, i.e., $H_{i}\neq H_{j}$, but a unique optimal model
i.e. $w_{*}^{i}=w_{*}$. We verify that all the assumptions on the random
fields done in Subsection 2.1 are fulfilled in the setting. For this purpose,
we redefine the filtration given in Appendix D to align them with the FL
setting. For $k$ in $\mathbb{N}^{*}$ and for $i$ in $[N]$, we note $u_{k}^{i}$
the noise that controls the compression $\mathcal{C}_{k}^{i}(\cdot)$ at round
$k$.

######  Definition S3.

We note $(\mathcal{G}_{k})_{k\in\mathbb{N}}$ the filtration associated with
the features noise, $(\mathcal{H}_{k})_{k\in\mathbb{N}}$ the filtration
associated with the label noise, and $(\mathcal{I}_{k})_{k\in\mathbb{N}}$ the
filtration associated to the stochastic gradient noise, which is the union of
the two previous filtrations. For $k\in\mathbb{N}^{*}$, we define
$\mathcal{F}_{0}=\\{\varnothing\\}$ and

$\displaystyle\mathcal{G}_{k}$
$\displaystyle=\sigma\left(\mathcal{F}_{k-1}\cup\\{(x_{k}^{i})_{i=1}^{N}\\}\right)$
$\displaystyle\mathcal{H}_{k}$
$\displaystyle=\sigma\left(\mathcal{F}_{k-1}\cup\\{(\varepsilon_{k}^{i})_{i=1}^{N}\\}\right)$
$\displaystyle\mathcal{I}_{k}$
$\displaystyle=\sigma\left(\mathcal{F}_{k-1}\cup\\{(x_{k}^{i},\varepsilon_{k}^{i})_{i=1}^{N}\\}\right)$
$\displaystyle\mathcal{F}_{k}$
$\displaystyle=\sigma\left(\mathcal{F}_{k-1}\cup\\{(x_{k},\varepsilon_{k}^{i},u_{k}^{i})_{i=1}^{N}\\}\right)\,.$

Now we prove that all assumptions done in Section 2 are correct in this
setting.

######  Property S7 (Validity of the setting presented in Definition 1).

Consider Algorithm 3 in the context of Model 1, we have that the setting
presented in Definition 1 is verified.

Proof  From Algorithm 3, we have for any $k$ in $\mathbb{N}^{*}$ and any $w$
in $\mathbb{R}^{d}$, $\xi_{k}(w-w_{*})=\nabla
F(w)-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w))$.
Because $(\textsl{g}_{k}^{i})_{k\in\mathbb{N}^{*},i\in\llbracket
1,N\rrbracket}$ and $(\mathcal{C}_{k}^{i})_{k\in\mathbb{N}^{*},i\in\llbracket
1,N\rrbracket}$ are by definition two sequences of i.i.d. random fields
(Algorithm 3), it follows that their composition is also i.i.d., _hence
$(\xi_{k})_{k\in\mathbb{N}^{*}}$ is a sequence of i.i.d. random fields._

Taking expectation w.r.t. the $\sigma$-algebra $\mathcal{I}_{k}$ we have
$\mathbb{E}\left[\mathcal{C}_{k}^{i}(\textsl{g}_{k}^{i}(w))\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]=\textsl{g}_{k}^{i}(w)$
(Lemma 1), next with the $\sigma$-algebra $\mathcal{F}_{k-1}$, we have
$\mathbb{E}\left[\textsl{g}_{k}^{i}(w)\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{F}_{k-1}\right]=\nabla F_{i}(w)$
(Equation 2). And because $\frac{1}{N}\sum_{i=1}^{N}\nabla F_{i}(w)=\nabla
F(w)$, _we obtain that the random fields are zero-centered._

From Model 1, we have for any $k$ in $\mathbb{N}^{*}$ and any $w$ in
$\mathbb{R}^{d}$ that:

$\displaystyle F(w)$
$\displaystyle=\frac{1}{2N}\sum_{i=1}^{N}\mathbb{E}\left[(\left\langle
x_{k}^{i},w\right\rangle-y_{k}^{i})^{2}\right]$
$\displaystyle=\frac{1}{2N}\sum_{i=1}^{N}\mathbb{E}\left[(w-w_{*})^{\top}(x_{k}^{i}\otimes
x_{k}^{i})(w-w_{*})-2\varepsilon_{k}^{i}\left\langle
x_{k}^{i},w-w_{*}\right\rangle+(\varepsilon_{k}^{i})^{2}\right]$
$\displaystyle=\frac{1}{2N}\sum_{i=1}^{N}(w-w_{*})^{\top}H_{i}(w-w_{*})+\sigma^{2}=\frac{1}{2}((w-w_{*})^{\top}\overline{H}(w-w_{*})+\sigma^{2})\,.$

And we have from Model 1:
$\mathrm{Tr}\left(\overline{H}\right)=\frac{1}{N}\sum_{i=1}^{N}\mathrm{Tr}\left(H_{i}\right)=\frac{1}{N}\sum_{i=1}^{N}R_{i}^{2}=:\overline{R}^{2}$,
which concludes the verification.

######  Property S8 (Validity of Assumption 1).

Consider Algorithm 3 in the context of Model 1 with Lemma 1, for any iteration
$k$ in $\mathbb{N}^{*}$, the second moment of the additive noise
$\xi_{k}^{\mathrm{add}}$ can be bounded by
$(\omega+1)\overline{R}^{2}\sigma^{2}/N$ i.e. Assumption 1 is verified.

Proof  Let $k$ in $\mathbb{N}^{*}$. Because we consider Algorithm 3, with
Definitions 1 and 2, we first have
$\xi_{k}^{\mathrm{add}}=-\frac{1}{N}\sum_{i=1}^{N}\mathcal{C}_{k}^{i}(g_{k,*}^{i})$,
hence taking expectation w.r.t the $\sigma$-algebra $\mathcal{I}_{k}$ and
because the $N$ compressions are independent (Algorithm 3), using Lemma 1, we
have that:

$\displaystyle\mathbb{E}\left[\|\xi_{k}^{\mathrm{add}}\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]$
$\displaystyle=\frac{1}{N^{2}}\sum_{i=1}^{N}\mathbb{E}\left[\left\|\mathcal{C}_{k}^{i}(g_{k,*}^{i})\right\|^{2}\leavevmode\nobreak\
\middle|\leavevmode\nobreak\ \mathcal{I}_{k}\right]+\frac{1}{N^{2}}\sum_{i\neq
j}\left\langle g_{k,*}^{i},g_{k,*}^{j}\right\rangle$