Proof of Proposition 8. Define \(z_k=y_k-y^*\), it satisfies \[z_{k} = (I_d-\alpha h_k)z_{k-1} -\alpha (h_ky^*-b_k) \;\text{ with }\; z_0 = y_0-y^*.\] Observe that \(-\alpha (h_ky^*-b_k)\) plays the role of a source term. Therefore, by linearity (or Duhamel’s principle), we get that \(z_k=w_k+\eta_k\), where \(w_k\) and \(\eta_k\) are defined by induction as \[\begin{align} w_{k} &= (I_d-\alpha h_k)w_{k-1}\text{ with }w_0 = y_0-y^*, \\ \eta_{k} &= (I_d-\alpha h_k)\eta_{k-1} -\alpha (h_ky^*-b_k)\text{ with }\eta_0 = 0. \end{align}\] In the following, we will prove \[{\mathbb{E}}\left[{\overline{w}}_k^{\top} \Sigma{\overline{w}}_k\right] \leq \frac{c_{\Sigma}|w_0|^2}{\alpha(2-\alpha\beta_1) k} \;\text{ and }\; {\mathbb{E}}\left[{\overline{\eta}}_k^{\top}\Sigma{\overline{\eta}}_k\right] \leq \frac{2\sigma^2}{(2-\alpha\beta c_{\Sigma})k} {\mathcal{S}}_k.\] so that we will be able to conclude using the inequality \({\mathbb{E}}\left[{\overline{z}}_k^{\top} \Sigma{\overline{z}}_k\right] \leq \left({\mathbb{E}}\left[{\overline{w}}_k^{\top} \Sigma{\overline{w}}_k\right]^{\frac{1}{2}} +{\mathbb{E}}\left[{\overline{\eta}}_k^{\top}\Sigma{\overline{\eta}}_k\right]^{\frac{1}{2}}\right)^2\).

First step: dealing with the initial condition (corresponding to \(w\)).

For \(k\geq1\), using \({\mathbb{E}}\left[h_k^{\top}h_k\right]\leq \beta_1S\), observe that \[\begin{align} {\mathbb{E}}\left[|w_k|^2\right] &= {\mathbb{E}}\left[w_{k-1}^{\top}(I_d-\alpha h_k-\alpha h_k^{\top}+\alpha^2 h_k^{\top}h_k)w_{k-1}\right] \\ &\leq {\mathbb{E}}\left[w_{k-1}^{\top}(I_d-2\alpha S+\alpha^2\beta_1 S)w_{k-1}\right] \\ &\leq {\mathbb{E}}\left[w_{k-1}^{\top}(I_d-\alpha(2-\alpha\beta_1) S)w_{k-1}\right] \\ &= {\mathbb{E}}\left[|w_{k-1}|^2\right] -\alpha(2-\alpha\beta_1){\mathbb{E}}\left[w_{k-1}^{\top}Sw_{k-1}\right]. \end{align}\] Taking the sum from \(1\) to \(k\) in the latter inequality and using that \(u\mapsto u^{\top}Su\) is convex, we obtain \[{\mathbb{E}}\left[{\overline{w}}_k^{\top} S{\overline{w}}_k\right] \leq \frac{1}{k}\sum_{i=0}^{k-1}{\mathbb{E}}\left[w_i^{\top} Sw_i\right] \leq \frac{1}{\alpha k}\sum_{i=1}^{k} \left({\mathbb{E}}\left[|w_{k-1}|^2\right] -{\mathbb{E}}\left[|w_k|^2\right]\right) \leq \frac{|w_0|^2}{\alpha(2-\alpha\beta_1) k}.\] This and \(\Sigma\leq c_{\Sigma}S\) conclude the part on the bias.

Second step: getting bounds on the uncentered covariances of variance term (corresponding to \(\eta\)).

Using a straightforward induction, we have \({\mathbb{E}}[\eta_k]=0\) for \(k\geq0\). We will now prove by induction that \[\label{eq:etaketakt} {\mathbb{E}}\left[\eta_k\eta_k^{\top}\right] \leq \frac{\sigma^2\alpha c_{\Sigma}}{2-\alpha\beta c_{\Sigma}}I_d.\tag{6}\] Recall that \(\eta_0=0\) so the above inequality holds for \(k=0\). Then, for \(k\geq1\), we assume that it holds at index \(k-1\). Since \(\eta_{k-1}\) and \((h_k,b_k)\) are independent, we obtain \[{\mathbb{E}}\left[(I_d-\alpha h_k)\eta_{k-1}(h_ky^*-b_k)^{\top}\right] = {\mathbb{E}}\left[(I_d-\alpha h_k){\mathbb{E}}\left[\eta_{k-1}\right](h_ky^*-b_k)^{\top}\right] = 0.\] Using the latter equality, Inequality ?? , \(\Sigma\leq c_{\Sigma}S\), and the second inequality in Assumption [hypo:ineq95LSA], we obtain \[\begin{align} {\mathbb{E}}\left[\eta_k\eta_k^{\top}\right] &= {\mathbb{E}}\left[(I_d-\alpha h_k)\eta_{k-1}\eta_{k-1}^{\top}(I_d-\alpha h_k^{\top})\right] +\alpha^2{\mathbb{E}}\left[(h_ky^*-b_k)(h_ky^*-b_k)^{\top}\right] \\ &\leq \frac{\sigma^2\alpha c_{\Sigma}}{2-\alpha\beta c_{\Sigma}} {\mathbb{E}}\left[(I_d-\alpha h_k)(I_d-\alpha h_k^{\top})\right] +\sigma^2\alpha^2\Sigma \\ &\leq \frac{\sigma^2\alpha c_{\Sigma}}{2-\alpha\beta c_{\Sigma}} (I_d-\alpha(2-\alpha\beta c_{\Sigma}) S) +\sigma^2\alpha^2 c_{\Sigma}S \\ &\leq \frac{\sigma^2\alpha c_{\Sigma}}{2-\alpha\beta c_{\Sigma}}I_d. \end{align}\] This concludes the induction and the proof of Inequality 6 .

Third step: introduce an appropriate decomposition for \(\eta\).

Let us then define \((\eta^r_k)_{k\geq0,0\leq r\leq k+1}\) and \((\chi^r_k)_{1\leq r\leq k}\) by induction by, for \(1\leq r\leq k\), \[\begin{align} \eta^r_k &= (I_d-\alpha H)\eta^r_{k-1} +\chi_k^r\text{ with }\eta^0_{k-1} = \eta^{k}_{k-1} = 0, \\ \chi_k^{r} &= -\alpha(h_k-H)\eta^{r-1}_{k-1} -\alpha(h_ky^*-b_k) \delta_{\left\{r=1\right\}}. \end{align}\] Let us check by induction on \(k\geq1\) that \(\eta_k=\sum_{r=1}^k\eta^r_k\). The case \(k=1\) is a simple consequence of the above initial condition. Now assume that it holds for \(k-1\), for \(k\geq2\), and let us prove it for index \(k\): \[\begin{align} \eta_k &= (I_d-\alpha h_k) \sum_{r=1}^{k-1}\eta^r_{k-1} +\chi^1_k \\ &= (I_d-\alpha H) \sum_{r=1}^{k-1}\eta^r_{k-1} -\alpha(h_k-H) \sum_{r=2}^{k}\eta^{r-1}_{k-1} +\chi^1_k \\ &= \sum_{r=1}^{k} \left((I_d-\alpha H) \eta^r_{k-1} +\chi^r_k\right) \\ &= \sum_{r=1}^{k} \eta^r_k. \end{align}\]

In fact, \(\eta^r_k\) can be rewritten as a sum of terms, each of which admits exactly \(r\) different multiplicative centered noises (of the form \(h_j-H\) or \(h_jy^*-b_j\) for some \(1\leq j\leq k\)). Therefore, for \(r'\neq r\), any term from the development of \(\eta^{r'}_k(\eta^{r}_k)^{\top}\) contains at least one multiplicative centered noise that appears only once and is independent of the rest of this same term (i.e., is of the form \(R_1(h_j-H)R_2\) or \(R_1(h_jy^*-b_j)\) with neither \(R_1\) or \(R_2\) containing \(h_j\) or \(b_j\)). This implies that \({\mathbb{E}}\left[\eta^{r'}_k(\eta^{r}_k)\right]=0\), so that we get \[\label{eq:decomp95eta} {\mathbb{E}}\left[\eta_k(\eta_k)^{\top}\right] = \sum_{r=1}^k \sum_{r'=1}^k {\mathbb{E}}\left[\eta^r_k(\eta^{r'}_k)^{\top}\right] = \sum_{r=1}^k {\mathbb{E}}\left[\eta^r_k(\eta^{r}_k)^{\top}\right].\tag{7}\] Using similar arguments, we also have that, for \({\overline{\eta}}_k:=\frac{1}{k}\sum_{j=0}^{k-1}\eta_k\) and \({\overline{\eta}}^r_k:=\frac{1}{k}\sum_{j=0}^{k-1}\eta^r_k\), \[\label{eq:decomp95etao} {\mathbb{E}}\left[{\overline{\eta}}_k^{\top}\Sigma{\overline{\eta}}_k\right] = \sum_{r=1}^k {\mathbb{E}}\left[({\overline{\eta}}^r_k)^{\top}\Sigma{\overline{\eta}}^r_k\right].\tag{8}\]

Fourth step: obtaining the convergence rate.

For \(1\leq r\leq k\), the induction relation of \(\eta^r_k\) implies \[\eta^r_k = \sum_{j=1}^k (I_d-\alpha H)^{k-j}\chi^r_j.\] For \(k\geq2\), define \({\overline{\eta}}^r_k=\frac{1}{k}\sum_{i=1}^{k-1}\eta^r_k\), it satisfies \[{\overline{\eta}}^r_k = \frac{1}{k} \sum_{i=1}^{k-1} \sum_{j=1}^i (I_d-\alpha H)^{i-j}\chi^r_j = \frac{1}{k} \sum_{j=1}^{k-1} \sum_{i=j}^{k-1} (I_d-\alpha H)^{i-j}\chi^r_j = \frac{1}{\alpha k} \sum_{j=1}^{k-1} M_{k-j}H^{-1}\chi^r_j = \frac{1}{\alpha k} \sum_{j=0}^{k-1} M_{j}H^{-1}\chi^r_{k-j}.\] where \(M_{j}=I_d-(I_d-\alpha H)^{j}\). Observe that \(M_{j}\) commutes with \(H\) and \(H^{-1}\) (but not with \(H^{\top}\) and \(H^{-\top}\)). On the one hand, using Inequality ?? , we get \[\begin{align} {\mathbb{E}}\left[({\overline{\eta}}^1_k)^{\top}\Sigma{\overline{\eta}}^1_k\right] &= \frac{1}{\alpha^2 k^2} \sum_{j=0}^{k-1} {\mathbb{E}}\left[(\chi^1_{k-j})^{\top}H^{-\top} M_{j}^{\top}\Sigma M_{j} H^{-1}\chi^1_{k-j}\right] \\ &= \frac{1}{\alpha^2 k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[\chi^1_{k-j}(\chi^1_{k-j})^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &= \frac{1}{k^2} \sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}y^*-b_{k-j})(h_{k-j}y^*-b_{k-j})^{\top})\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\sigma^2}{k^2} \sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1}\Sigma H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \end{align}\] On the other hand, we have \[\begin{align} \sum_{r=2}^k {\mathbb{E}}\left[({\overline{\eta}}^r_k)^{\top}\Sigma{\overline{\eta}}^r_k\right] &= \frac{1}{\alpha^2 k^2} \sum_{r=2}^k \sum_{j=0}^{k-1} {\mathbb{E}}\left[(\chi^r_{k-j})^{\top}H^{-\top} M_{j}^{\top}\Sigma M_{j} H^{-1}\chi^r_{k-j}\right] \\ &= \frac{1}{\alpha^2 k^2} \sum_{r=2}^k \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[\chi^r_{k-j}\otimes\chi^r_{k-j}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &= \frac{1}{k^2} \sum_{r=2}^k \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}-H)\eta^{r-1}_{k-j-1}(\eta^{r-1}_{k-j-1})^{\top}(h_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &= \frac{1}{k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}-H) \sum_{r=2}^k {\mathbb{E}}\left[\eta^{r-1}_{k-j-1}(\eta^{r-1}_{k-j-1})^{\top}\right] (h_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &= \frac{1}{k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}-H) {\mathbb{E}}\left[\eta_{k-j-1}(\eta_{k-j-1})^{\top}\right] (h_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\sigma^2\alpha c_{\Sigma}}{(2-\alpha\beta c_{\Sigma})k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}-H)(h_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\sigma^2\alpha\beta c_{\Sigma}}{(2-\alpha\beta c_{\Sigma})k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j} H^{-1}\Sigma H^{-\top} M_{j}^{\top}\Sigma^{\frac{1}{2}}\right), \end{align}\] where we used Equality 7 to get the fifth line, the second step of this proof to get the sixth line and the first inequality of Assumption [hypo:ineq95LSA] to obtain the last one. The latter two chains of inequalities and Equality 8 imply \[\begin{align} {\mathbb{E}}\left[{\overline{\eta}}_k^{\top}\Sigma{\overline{\eta}}_k\right] &= \sum_{r=1}^k {\mathbb{E}}\left[({\overline{\eta}}^r_k)^{\top}\Sigma{\overline{\eta}}^r_k\right] \\ &\leq \frac{\sigma^2}{k^2}\left(1+\frac{\alpha\beta c_{\Sigma}}{2-\alpha\beta c_{\Sigma}}\right) \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j} H^{-1}\Sigma H^{-\top} M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &= \frac{2\sigma^2}{(2-\alpha\beta c_{\Sigma})k^2} \sum_{j=0}^{k-1} {\left\| \Sigma^{\frac{1}{2}}\left(I_d-(I_d-\alpha H)^j\right)H^{-1}\Sigma^{\frac{1}{2}} \right\|_{F}^{2}} \\ &= \frac{2\sigma^2}{(2-\alpha\beta c_{\Sigma})k^2} \sum_{j=0}^{k-1} {\left\| \left(I_d-(I_d-\alpha \Sigma^{\frac{1}{2}}H\Sigma^{-\frac{1}{2}})^j\right)\Sigma^{\frac{1}{2}} H^{-1}\Sigma^{\frac{1}{2}} \right\|_{F}^{2}} \\ &= \frac{2\sigma^2}{(2-\alpha\beta c_{\Sigma})k} {\mathcal{S}}_k. \end{align}\]

To conclude, it only remains to prove that \({\mathcal{S}}_k\leq c_{\Sigma}^2(3d+ \widetilde{\mathcal{S}}_k)\), which is a consequence of the following computations, \[\Sigma^{\frac{1}{2}}H^{-1}\Sigma H^{-\top}\Sigma^{\frac{1}{2}} \leq c_{\Sigma}\Sigma^{\frac{1}{2}}H^{-1}S H^{-\top}\Sigma^{\frac{1}{2}} = c_{\Sigma}\Sigma^{\frac{1}{2}}\frac{H^{-1}+H^{-\top}}{2}\Sigma^{\frac{1}{2}} = c_{\Sigma}\Sigma^{\frac{1}{2}}S^{-1}\Sigma^{\frac{1}{2}} \leq c_{\Sigma}^2I_d,\] where we used \(\Sigma\leq c_{\Sigma}S\), Heinz’s inequality \(H^{-1}+H^{-\top}\leq 2S^{-1}\) and \(S^{-1}\leq c_{\Sigma}\Sigma^{-1}\); and \[{\left\| \left(I_d-Q^j\right)\Sigma^{\frac{1}{2}} H^{-1}\Sigma^{\frac{1}{2}} \right\|_{F}^{2}} \leq c_{\Sigma}^2 {\left\| I_d-Q^j \right\|_{F}^{2}} = c_{\Sigma}^2\left({\rm tr}(I_d) -2{\rm tr}(Q^j) +{\left\| Q^j \right\|_{F}^{2}}\right) \leq c_{\Sigma}^2(3d+{\left\| Q^j \right\|_{F}^{2}}),\] where we used \(|{\rm tr}(Q^j)|=|{\rm tr}((I_d-\alpha H)^j)| \leq d\|I_d-\alpha H\|_{\rm op}^j\leq d\). This concludes the proof. ◻

Proof of Theorem 9. This is a consequence of Proposition 8 and Lemma 2 below. ◻

Proof. Let us prove the first inequality. Using \(M_j=I_d-(I_d-\alpha H)^j\) and \(N_j=(I_d-\alpha H)^j\) for \(j\geq1\), we have for \(k\geq1\): \[\begin{align} {\mathcal{S}}_k &= \frac{1}{k}\sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1}\Sigma H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{c_{\Sigma}}{k}\sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1}S H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{c_{\Sigma}}{k}\sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}\frac{H^{-1}+H^{-\top}}{2} M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{c_{\Sigma}}{k}\sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}S^{-1} M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &= \frac{c_{\Sigma}}{k}\sum_{j=1}^{k-1} {\rm tr}\left( S^{-\frac{1}{2}}M^{\top}_{j}\Sigma M_{j}S^{-\frac{1}{2}}\right) \\ &\leq \frac{c_{\Sigma}^2}{k}\sum_{j=1}^{k-1} {\rm tr}\left( S^{-\frac{1}{2}}M^{\top}_{j}S M_{j}S^{-\frac{1}{2}}\right) \\ &= \frac{c_{\Sigma}^2}{k}\sum_{j=1}^{k-1} {\rm tr}\left( I_d+ 2{\rm tr}(N_j) +S^{-\frac{1}{2}}N^{\top}_{j}S N_{j}S^{-\frac{1}{2}}\right) \\ &\leq 3c_{\Sigma}^2d +\frac{c_{\Sigma}^2}{k}{\rm tr}\left(S^{-\frac{1}{2}}\left(\sum_{j=1}^{k-1}N_j^{\top}SN_j\right)S^{-\frac{1}{2}}\right) \\ &\leq c_{\Sigma}^2\left(3d+\frac{{\rm tr}(S^{-1})}{\alpha(2-\alpha\beta_1)k}\right) \\ &\leq c_{\Sigma}^2d\left(3+\frac{1}{\alpha(2-\alpha\beta_1)\mu k}\right), \end{align}\] where we used \(\Sigma\leq c_{\Sigma}S\) to get the second and sixth lines, Heinz’s inequality (Lemma 4) to get the fourth one, \({\rm tr}(N_j)\leq{\rm tr}(I_d)^{\frac{1}{2}}{\rm tr}(N_j^{\top}N_j)^{\frac{1}{2}}\leq {\rm tr}(I_d)=d\) (since \((I_d-\alpha H)^{\top}(I_d-\alpha H)\leq I_d\)) and Inequality ?? to get the eighth one, and \(S^{-1}\leq\mu^{-1}I_d\) to get the last one.

To get the second inequality, we write \[{\mathcal{S}}_k = \frac{1}{k}\sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}^{\top}H^{-\top}\Sigma H^{-1}M_{j}\Sigma^{\frac{1}{2}}\right),\] using that \(H\) and \(M_j\) commutes. Then, we repeat similar arguments as the ones for the first inequality. This concludes the proof. ◻

Proof. The proof follows a strategy similar to that of Proposition 8 and uses similar notations. Only the second and fourth step changes, as shown below.

Changes in the second step.

First, let us notice that using minibatches allows us to improve Inequality ?? , we have \[\label{eq:LSA95minibatch95aux} \begin{align} {\mathbb{E}}\left[(I_d-\alpha h_k^B)(I_d-\alpha h_k^B)^{\top}\right] &= \frac{1}{B}{\mathbb{E}}\left[(I_d-\alpha h)(I_d-\alpha h)^{\top}\right] +\frac{B-1}{B}(I_d-\alpha H)(I_d-\alpha H^{\top}) \\ &\leq \frac{1}{B}\left(I_d-\alpha(2-\alpha\beta c_{\Sigma})S\right) +\frac{B-1}{B}\left(I_d-\alpha(2-\alpha\beta_1)S\right) \\ &= I_d-\alpha\left(2-\frac{\alpha \beta c_{\Sigma}}{B}-\frac{(B-1)\alpha\beta_1}{B}\right)S, \end{align}\tag{9}\] where we used ?? and ?? to get the second line.

This then allows us to improve Inequality 6 . More precisely, we are going to prove by induction: \[\label{eq:etaketakt95minibatch} {\mathbb{E}}\left[\eta_k\eta_k^{\top}\right] \leq \frac{\sigma^2\alpha c_{\Sigma}}{2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1)}I_d.\tag{10}\] The case \(k=0\) is straightforward. Let us assume that the inequality holds at index \(k-1\) and prove it at \(k\), \[\begin{align} {\mathbb{E}}\left[\eta_k\eta_k^{\top}\right] &= {\mathbb{E}}\left[(I_d-\alpha h^B_k)\eta_{k-1}\eta_{k-1}^{\top}(I_d-\alpha h^B_k)^{\top}\right] +\alpha^2{\mathbb{E}}\left[(h^B_ky^*-b^B_k)(h^B_ky^*-b^B_k)^{\top}\right] \\ &\leq \frac{\sigma^2\alpha c_{\Sigma}}{2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1)} {\mathbb{E}}\left[(I_d-\alpha h^B_k)(I_d-\alpha h^B_k)^{\top}\right] +\frac{\sigma^2\alpha^2}{B}\Sigma \\ &\leq \frac{\sigma^2\alpha c_{\Sigma}}{2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1)} \left(I_d-\alpha\left(2-\frac{\alpha \beta c_{\Sigma}}{B}-\frac{(B-1)\alpha\beta_1}{B}\right)S\right) +\frac{\sigma^2\alpha^2c_{\Sigma}}{B}S \\ &\leq \frac{\sigma^2\alpha c_{\Sigma}}{2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1)}I_d, \end{align}\] where we used 9 to get the third line. This concludes the induction.

Changes in the fourth step. Recall the notation \(M_{j}=I_d-(I_d-\alpha H)^{j}\). On the one hand, using Inequality ?? , we get \[\begin{align} {\mathbb{E}}\left[({\overline{\eta}}^1_k)^{\top}\Sigma{\overline{\eta}}^1_k\right] &= \frac{1}{\alpha^2 k^2} \sum_{j=0}^{k-1} {\mathbb{E}}\left[(\chi^1_{k-j})^{\top}H^{-\top} M_{j}^{\top}\Sigma M_{j} H^{-1}\chi^1_{k-j}\right] \\ &= \frac{1}{k^2} \sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h^B_{k-j}y^*-b^B_{k-j})(h^B_{k-j}y^*-b^B_{k-j})^{\top})\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\sigma^2}{Bk}{\mathcal{S}}_k \end{align}\] On the other hand, using similar arguments as in the proof of Proposition 8, we have \[\begin{align} \sum_{r=2}^k {\mathbb{E}}\left[({\overline{\eta}}^r_k)^{\top}\Sigma{\overline{\eta}}^r_k\right] &= \frac{1}{\alpha^2 k^2} \sum_{r=2}^k \sum_{j=0}^{k-1} {\mathbb{E}}\left[(\chi^r_{k-j})^{\top}H^{-\top} M_{j}^{\top}\Sigma M_{j} H^{-1}\chi^r_{k-j}\right] \\ &= \frac{1}{k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h^B_{k-j}-H) {\mathbb{E}}\left[\eta_{k-j-1}(\eta_{k-j-1})^{\top}\right] (h^B_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\sigma^2\alpha c_{\Sigma}}{(2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1))k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h^B_{k-j}-H)(h^B_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\sigma^2\alpha\beta c_{\Sigma}}{B(2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1))k} {\mathcal{S}}_k, \end{align}\] where we used Inequality 10 to obtain the third line, and the first inequality of Assumption [hypo:ineq95LSA] to obtain the last one. The latter two chains of inequalities and Equality 8 imply \[\begin{align} {\mathbb{E}}\left[{\overline{\eta}}_k^{\top}\Sigma{\overline{\eta}}_k\right] &= \sum_{r=1}^k {\mathbb{E}}\left[({\overline{\eta}}^r_k)^{\top}\Sigma{\overline{\eta}}^r_k\right] \\ &\leq \frac{\sigma^2}{Bk}{\mathcal{S}}_k +\frac{\sigma^2\alpha\beta c_{\Sigma}}{B(2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1))k}{\mathcal{S}}_k \\ &= \frac{\sigma^2(2B-(B-1)\alpha\beta_1)}{B(2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1))k}{\mathcal{S}}_k \\ &\leq \frac{2\sigma^2}{(2B-\alpha(\beta c_{\Sigma}+(B-1)\beta_1))k}{\mathcal{S}}_k. \end{align}\] From there, we conclude with similar arguments as in the proof of Proposition 8. ◻

Proof of Theorem 14. It is a direct consequence of Proposition 16 and Lemma 2. ◻

Proof of Theorem 15. It is a direct consequence of Proposition 17 and Lemma 2. ◻

Proof of Proposition 16. The three last point of the proof of Proposition 8 holds when removing the third inequality in [hypo:ineq95LSA]. Therefore, to prove Proposition 16, it is sufficient to prove that \[{\mathbb{E}}\left[{\overline{w}}_k^{\top} \Sigma{\overline{w}}_k\right] \leq \frac{c_{\Sigma}|y_0-y^*|^2}{(2-\alpha\beta c_{\Sigma})\alpha k} +\frac{\beta|y_0-y^*|^2}{k}{\mathcal{S}}_k.\] Similarly as in the third step of the proof of Proposition 8, we define \((w^r_k)_{k,r\geq0}\) such that \(w_k=\sum_{r=0}^kw_k^r\) and, for \(r\geq0\) and \(k\geq1\), \[\begin{align} w^r_k &= (I_d-\alpha H)w^r_{k-1} +\chi_k^r\text{ with }w^r_{0} = w_0\mathbb{1}_{\{r=0\}}, \\ \chi_k^{r} &= -\alpha(h_k-H)\eta^{r-1}_{k-1}\mathbb{1}_{\{r\neq 0\}}. \end{align}\]

First step: getting a bound on \(({\overline{w}}^0_k)^{\top}S{\overline{w}}^0_k\).

Take \({\widetilde{\alpha}}=\frac{2}{\beta c_{\Sigma}}\), ?? implies that \((I_d-{\widetilde{\alpha}}H)(I_d-{\widetilde{\alpha}}H)^{\top}\leq I_d\). This implies that the operator norm of \((I_d-{\widetilde{\alpha}}H)\) is upper bounded by one and that \[(I_d-{\widetilde{\alpha}}H)^{\top}(I_d-{\widetilde{\alpha}}H)\leq I_d.\] This then implies \[\begin{align} (I_d-\alpha H)^{\top}(I_d-\alpha H) &= \frac{\alpha^2}{{\widetilde{\alpha}}^2} (I_d-{\widetilde{\alpha}}H)^{\top}(I_d-{\widetilde{\alpha}}H) +\left(1-\frac{\alpha^2}{{\widetilde{\alpha}}^2}\right)I_d -2\left(\alpha -\frac{\alpha^2}{{\widetilde{\alpha}}}\right)S \\ &\leq I_d-\alpha(2-\alpha\beta c_{\Sigma})S. \end{align}\] As a consequence, for \(k\geq1\), we obtain \[\begin{align} |w^0_k|^2 &= (w^0_{k-1})^{\top} (I_d-\alpha H)^{\top}(I_d-\alpha H) w^0_{k-1} \\ &\leq |w^0_{k-1}|^2 -\alpha(2-\alpha\beta c_{\Sigma}) (w^0_{k-1})^{\top}Sw^0_{k-1} \end{align}\] Taking the sum from \(1\) to \(k\) in the latter inequality and using that \(u\mapsto u^{\top}Su\) is convex, we obtain \[({\overline{w}}^0_k)^{\top} S{\overline{w}}_k^0 \leq \frac{1}{k}\sum_{i=0}^{k-1}(w_i^0)^{\top} Sw_i^0 \leq \frac{1}{\alpha k}\sum_{i=1}^{k} \left(|w^0_{k-1}|^2 -|w^0_k|^2\right) \leq \frac{|w_0|^2}{\alpha(2-\alpha\beta c_{\Sigma}) k}.\] This and \(\Sigma\leq c_{\Sigma}S\) yield \[({\overline{w}}^0_k)^{\top} \Sigma{\overline{w}}_k^0 \leq \frac{c_{\Sigma}|w_0|^2}{\alpha(2-\alpha\beta c_{\Sigma}) k}.\]

Second step: getting the bound on the bias term.

Then, using similar arguments as in the third step of the proof of Proposition 8, we have \[\begin{align} \sum_{r=1}^k {\mathbb{E}}\left[({\overline{w}}^r_k)^{\top}\Sigma{\overline{w}}^r_k\right] &= \frac{1}{k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}-H) {\mathbb{E}}\left[w_{k-j-1}(w_{k-j-1})^{\top}\right] (h_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{|y_0-y^*|^2}{k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}-H) (h_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\beta|y_0-y^*|^2}{k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} \Sigma H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &= \frac{\beta|y_0-y^*|^2}{k}{\mathcal{S}}_k. \end{align}\] In the end, we obtain \[{\mathbb{E}}\left[{\overline{w}}_k^{\top}\Sigma{\overline{w}}_k\right] = \sum_{r=0}^k {\mathbb{E}}\left[({\overline{w}}^r_k)^{\top}\Sigma{\overline{w}}^r_k\right] \leq \frac{c_{\Sigma}|w_0|^2}{\alpha(2-\alpha\beta c_{\Sigma}) k} +\frac{\beta|y_0-y^*|^2}{k}{\mathcal{S}}_k.\]

Third step: deal with the cross term and conclude.

We have \[{\mathbb{E}}\left[{\overline{z}}_k^{\top}\Sigma{\overline{z}}_k\right] = {\mathbb{E}}\left[{\overline{w}}_k^{\top}\Sigma{\overline{w}}_k\right] +{\mathbb{E}}\left[{\overline{\eta}}_k^{\top}\Sigma{\overline{\eta}}_k\right] +2{\mathbb{E}}\left[{\overline{w}}_k^{\top}\Sigma{\overline{\eta}}_k\right],\] where the last term is the cross term and satisfies \[\begin{align} {\mathbb{E}}\left[{\overline{w}}_k^{\top}\Sigma{\overline{\eta}}_k\right] &= {\mathbb{E}}\left[\left(\sum_{r=0}^k{\overline{w}}^r_k\right)^{\top} \Sigma\left(\sum_{r=1}^k{\overline{\eta}}^r_k\right)\right] \\ &= {\mathbb{E}}\left[\left(\sum_{r=1}^k{\overline{w}}^r_k\right)^{\top} \Sigma\left(\sum_{r=1}^k{\overline{\eta}}^r_k\right)\right] \\ &= {\mathbb{E}}\left[\left(\sum_{r=1}^k{\overline{w}}^r_k\right)^{\top} \Sigma\left(\sum_{r=1}^k{\overline{w}}^r_k\right)\right]^{\frac{1}{2}} {\mathbb{E}}\left[\left(\sum_{r=1}^k{\overline{\eta}}^r_k\right)^{\top} \Sigma\left(\sum_{r=1}^k{\overline{\eta}}^r_k\right)\right]^{\frac{1}{2}} \\ &\leq \left(\frac{\beta|y_0-y^*|^2}{k}{\mathcal{S}}_k\right)^{\frac{1}{2}} \left(\frac{2\sigma^2{\mathcal{S}}_k}{(2-\alpha\beta c_{\Sigma})k}\right)^{\frac{1}{2}}. \end{align}\] The above inequalities imply the upper bound in Proposition 16. ◻

Proof of Proposition 17. Let us use \(z_k=y_k-y^*\) and the decomposition \(z_k=w_k+\eta_k\), similarly as defined in the proof of Proposition 8.

Repeating the first step of the proof of Proposition 8, we obtain \[{\mathbb{E}}\left[{\overline{w}}_k^{\top} \Sigma{\overline{w}}_k\right] \leq \frac{c_{\Sigma}|w_0|^2}{\alpha(2-\alpha\beta_1) k}.\] Therefore, using inequality \({\mathbb{E}}\left[{\overline{z}}_k^{\top} \Sigma{\overline{z}}_k\right] \leq 2{\mathbb{E}}\left[{\overline{w}}_k^{\top} \Sigma{\overline{w}}_k\right] +2{\mathbb{E}}\left[{\overline{\eta}}_k^{\top}\Sigma{\overline{\eta}}_k\right]\), to conclude it only remains to prove that \[{\mathbb{E}}\left[{\overline{\eta}}_k^{\top}\Sigma{\overline{\eta}}_k\right] \leq \frac{1}{k} \left(\sigma^2 +\frac{\alpha\beta{\widetilde{\sigma}}^2}{(2-\alpha\beta_1)\mu }\right) {\mathcal{S}}_k.\]

First step: getting an upper bound on \({\mathbb{E}}[|\eta_k|^2]\)

Recall that, using a straightforward induction, we have \({\mathbb{E}}[\eta_k]=0\) for \(k\geq0\). We will now prove that \[\label{eq:etak942} {\mathbb{E}}\left[|\eta_k|^2\right] \leq \frac{\alpha{\widetilde{\sigma}}^2}{(2-\alpha\beta_1)\mu}.\tag{11}\] For \(k=0\), the result holds since \(\eta_0=0\). Then, for \(k\geq1\), we assume that it holds for index \(k-1\). Since \(\eta_{k-1}\) and \((h_k,b_k)\) are independent, we obtain \[{\mathbb{E}}\left[\eta_{k-1}^{\top}(I_d-\alpha h_k)^{\top}(h_ky^*-b_k)\right] = {\mathbb{E}}\left[\eta_{k-1}^{\top}\right]{\mathbb{E}}\left[(I_d-\alpha h_k)^{\top}(h_ky^*-b_k)\right] = 0.\] This and inequality ?? imply that \[\begin{align} {\mathbb{E}}\left[|\eta_k|^2\right] &= {\mathbb{E}}\left[|(I_d-\alpha h_k)\eta_{k-1}|^2\right] +\alpha^2 {\mathbb{E}}\left[|h_ky^*-b_k|^2\right] \\ &\leq {\mathbb{E}}\left[\eta_{k-1}^{\top}(I_d-\alpha(2-\alpha\beta_1)S)\eta_{k-1}\right] +\alpha^2{\widetilde{\sigma}}^2 \\ &\leq (1-\alpha(2-\alpha\beta_1)\mu) {\mathbb{E}}\left[|\eta_{k-1}|^2\right] +\alpha^2{\widetilde{\sigma}}^2 \\ &\leq \frac{\alpha{\widetilde{\sigma}}^2}{(2-\alpha\beta_1)\mu}, \end{align}\] which concludes the induction.

Second step: obtaining the convergence rate.

Let us use the same decomposition \(\eta_k=\sum_{r=1}^k\eta_k^r\) as introduced in the proof of Proposition 8. Similarly as in the third step of the latter proof, we get \[{\mathbb{E}}\left[({\overline{\eta}}^1_k)^{\top}\Sigma{\overline{\eta}}^1_k\right] \leq \frac{\sigma^2}{k^2} \sum_{j=1}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1}\Sigma H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) = \frac{\sigma^2}{k}{\mathcal{S}}_k,\] and \[\begin{align} \sum_{r=2}^k {\mathbb{E}}\left[({\overline{\eta}}^r_k)^{\top}\Sigma{\overline{\eta}}^r_k\right] &= \frac{1}{k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}-H) {\mathbb{E}}\left[\eta_{k-j-1}(\eta_{k-j-1})^{\top}\right] (h_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\alpha{\widetilde{\sigma}}^2}{(2-\alpha\beta_1)\mu k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j}H^{-1} {\mathbb{E}}\left[(h_{k-j}-H)(h_{k-j}-H)^{\top}\right] H^{-\top}M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &\leq \frac{\alpha\beta{\widetilde{\sigma}}^2}{(2-\alpha\beta_1)\mu k^2} \sum_{j=0}^{k-1} {\rm tr}\left( \Sigma^{\frac{1}{2}}M_{j} H^{-1}\Sigma H^{-\top} M_{j}^{\top}\Sigma^{\frac{1}{2}}\right) \\ &= \frac{\alpha\beta{\widetilde{\sigma}}^2}{(2-\alpha\beta_1)\mu k}{\mathcal{S}}_k, \end{align}\] where we used \({\mathbb{E}}\left[\eta_{j}(\eta_{j})^{\top}\right]\leq {\mathbb{E}}\left[|\eta_{j}|^2\right]I_d \leq \frac{\alpha{\widetilde{\sigma}}^2}{(2-\alpha\beta_1)\mu k^2}I_d\) to get the second line, and the first inequality of Assumption [hypo:ineq95LSA] for the third line. This concludes the proof. ◻

Proof. The first inequality in ?? is straightforward. Then, we have, \[{\mathbb{E}}\left[(I_d-\alpha h)(I_d-\alpha h)^{\top}\right] = I_d-2\alpha S+\alpha^2{\mathbb{E}}[hh^{\top}] \leq I_d-\alpha(2-\alpha\beta c_{\Sigma}) S,\] using \({\mathbb{E}}[hh^{\top}]\leq \beta \Sigma\leq \beta c_{\Sigma} S\). Inequality ?? can be proved with a similar computation.

In particular, the operator norm of \(I_d-\frac{2}{\beta_1} H\) is bounded by one, so is the one of \(I_d-\frac{2}{\beta_1} H^{\top}\), i.e., \[\left(I_d-\frac{2}{\beta_1} H\right) \left(I_d-\frac{2}{\beta_1} H\right)^{\top} \leq I_d.\] This allows us to prove ?? as follows, for \(\alpha\leq \frac{2}{\beta_1}\), \[\begin{align} (I_d-\alpha H)(I_d-\alpha H)^{\top} &= I_d-2\alpha S+\alpha^2HH^{\top} \\ &= \frac{\alpha^2\beta_1^2}{4} \left(I_d-\frac{2}{\beta_1}H\right) \left(I_d-\frac{2}{\beta_1}H\right)^{\top} +\left(1- \frac{\alpha^2\beta_1^2}{4}\right)I_d -2\left(\alpha-\alpha^2\beta_1\right)S \\ &\leq I_d +\left(1- \frac{\alpha^2\beta_1^2}{4}\right)I_d -\left(2\alpha-\alpha^2\beta_1\right)S \\ &= I_d-\alpha (2-\alpha\beta_1)S. \end{align}\]

Then, using the notation \(N_i=(I_d-\alpha H)^i\), we have \[\begin{align} I_d \geq I_d-N_k^{\top}N_k &= \sum_{i=0}^{k-1} N_i^{\top}N_i -N_{i+1}^{\top}N_{i+1} \\ &= \sum_{i=0}^{k-1} N_i^{\top}N_i -N_i^{\top}(I_d-\alpha H^{\top}) (I_d-\alpha H)N_i \\ &= \sum_{i=0}^{k-1} N_i^{\top}(I_d-(I_d-\alpha H^{\top})(I_d-\alpha H))N_i \\ &= \sum_{i=0}^{k-1} N_i^{\top}(2\alpha S-\alpha^2H^{\top}H)N_i \\ &\geq \alpha(2-\alpha\beta_1)\sum_{i=0}^{k-1}N_i^{\top}SN_i, \end{align}\] where we used \(\alpha H^{\top}H\leq (2-\alpha\beta_1)S\) to get the last line. ◻

Proof. First, let us prove that \(H^{-1}+H^{-\top}\) is positive definite. Take \(x\in \mathbb{R}^d\backslash\{0\}\), define \(y=H^{-1}x\) we have \[x^{\top}(H^{-1}+H^{-\top})x = 2x^{\top}H^{-\top}x = 2y^{\top}Hy = y^{\top}(H+H^{\top})y >0.\] Then, let us prove that \({\rm tr}(SH^{-\top}) \leq d\) is a consequence of \(H^{-1}+H^{-\top}\leq 2S^{-1}\): \[{\rm tr}(SH^{-\top}) = \frac{1}{2}{\rm tr}(S^{\frac{1}{2}}(H^{-1}+H^{-\top})S^{\frac{1}{2}}) \leq {\rm tr}(S^{\frac{1}{2}}S^{-1}S^{\frac{1}{2}}) = d.\] Now, observe that \[\begin{align} \left(S^{\frac{1}{2}}(H^{-1}+H^{-\top})S^{\frac{1}{2}}\right)^2 &= 2S^{\frac{1}{2}}H^{-1}SH^{-\top}S^{\frac{1}{2}} +2S^{\frac{1}{2}}H^{-\top}SH^{-1}S^{\frac{1}{2}} \\ & -\left(S^{\frac{1}{2}}(H^{-1}-H^{-\top})S^{\frac{1}{2}}\right)\left(S^{\frac{1}{2}}(H^{-1}-H^{-\top})S^{\frac{1}{2}}\right)^{\top} \\ &\leq 2S^{\frac{1}{2}}H^{-1}SH^{-\top}S^{\frac{1}{2}} +2S^{\frac{1}{2}}H^{-\top}SH^{-1}S^{\frac{1}{2}}. \end{align}\] Therefore, to conclude, it is sufficient to prove \(S^{\frac{1}{2}}H^{-1}SH^{-\top}S^{\frac{1}{2}}\leq I_d\) and \(S^{\frac{1}{2}}H^{-1}SH^{-\top}S^{\frac{1}{2}}\leq I_d\). For the former inequality, invert the matrix and use the notation \(A=\frac{H-H^{\top}}{2}\), we get \[\begin{align} (S^{\frac{1}{2}}H^{-1}SH^{-\top}S^{\frac{1}{2}})^{-1} &= S^{-\frac{1}{2}}H^{\top}S^{-1}HS^{-\frac{1}{2}} \\ &= S^{-\frac{1}{2}}(S-A)S^{-1}(S+A)S^{-\frac{1}{2}} \\ &= I_d-S^{-\frac{1}{2}}AS^{-1}AS^{-\frac{1}{2}} \\ &= I_d+\left(S^{-\frac{1}{2}}AS^{-\frac{1}{2}}\right)\left(S^{-\frac{1}{2}}AS^{-\frac{1}{2}}\right)^{\top} \\ &\geq I_d, \end{align}\] which, indeed, implies \(S^{\frac{1}{2}}H^{-1}SH^{-\top}S^{\frac{1}{2}}\leq I_d\). Then, applying the later inequality to \({\widetilde{H}}=H^{\top}\), we obtain \(S^{\frac{1}{2}}H^{-1}SH^{-\top}S^{\frac{1}{2}}\leq I_d\). This concludes the proof. ◻

Proof. Fix \(k\geq2\) and take \(c_k\in(0,1)\) such that \(c_k^2=1-\frac{1}{k}\). In particular, observe that \[c_k^{-2(k-1)}=\left(\frac{k}{k-1}\right)^{k-1}=\left(1+\frac{1}{k-1}\right)^{k-1}\leq e.\] Recall that \(Q\) is defined by \[Q=I_d-\alpha\Sigma_0^{\frac{1}{2}}H\Sigma_0^{-\frac{1}{2}} = I_d-\alpha \Sigma_0(I_d-\gamma U),\] and \({\mathcal{S}}_k\) satisfies \[\label{eq:aux95cSk} {\mathcal{S}}_k = {\rm tr}\left( \frac{1}{k}\sum_{\ell=0}^{k-1} (I_d-\gamma U)^{-\top} (I_d-Q^{\ell})^{\top}(I_d-Q^{\ell}) (I_d-\gamma U)^{-1} \right).\tag{12}\] Define \({\widetilde{Q}}=c_kQ\), we have \[c_k^{2(k-1)} \sum_{\ell=0}^{k-1} (I_d-Q^{\ell\top})(I_d-Q^{\ell}) \leq \sum_{\ell=0}^{k-1} c_k^{2\ell} (I_d-Q^{\ell\top})(I_d-Q^{\ell})\] Then, Lemma 6 yields \[\begin{align} \sum_{\ell=0}^{k-1} (I_d-Q^{\ell\top})&(I_d-Q^{\ell}) \\ &\leq \frac{1}{2i\pi c_k^{2(k-1)}} \int_{|z|=1} {\overline{z}}\left(({\overline{z}}-c_k)^{-1}I_d-({\overline{z}}I_d-{\widetilde{Q}})^{-\top}\right) \left((z-c_k)^{-1}I_d-(z I_d-{\widetilde{Q}})^{-1}\right)dz \\ &= \frac{1}{2\pi c_k^{2(k-1)}} \int_{-\pi}^{\pi} \left((e^{-i\psi}-c_k)^{-1}I_d -(e^{-i\psi} I_d-{\widetilde{Q}})^{-\top}\right) \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi} I_d-{\widetilde{Q}})^{-1}\right)d\psi \\ &\leq \frac{e}{2\pi} \int_{-\pi}^{\pi} \left((e^{-i\psi}-c_k)^{-1}I_d -(e^{-i\psi} I_d-{\widetilde{Q}})^{-\top}\right) \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi} I_d-{\widetilde{Q}})^{-1}\right)d\psi \end{align}\] In the following, we will use both the notation \(z\) or \(e^{i\psi}\), depending on the situation. This and 12 imply the following upper bound on \({\mathcal{S}}_k\) \[\label{eq:bound95cS} {\mathcal{S}}_k \leq \frac{e}{2\pi k} \int_{-\pi}^{\pi} {\left\| \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi}I_d-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{F}^{2}}d\psi.\tag{13}\] We are going to separate the latter integral into three parts corresponding to:

1. \({\mathcal{R}}(z)\geq1-(1-\gamma)^2\), i.e., \(|\psi|\leq\psi_{\gamma}\)

2. \(|{\mathcal{R}}(z)|<1-(1-\gamma)^2\), i.e., \(\psi_{\gamma}<|\psi|<\pi-\psi_{\gamma}\)

3. \({\mathcal{R}}(z)\leq-1+(1-\gamma)^2\), i.e., \(|\psi|\geq\pi-\psi_{\gamma}\)

where \(\mathcal{R}(z)\) is the real part of \(z\) and \(\psi_{\gamma}\) is defined by \(\psi_{\gamma}=\arccos(1-(1-\gamma)^2)\).

First step: dealing with case [case:1].

Observe that \[\begin{align} z-{\widetilde{Q}} &= (z-c_k)I_d+c_k\alpha\Sigma_0(I_d-\gamma U) \\ &= (z-c_k)\left(I_d+\frac{c_k\alpha}{|z-c_k|}\frac{{\overline{z}}-c_k}{|z-c_k|}\Sigma_0(I_d-\gamma U)\right) \\ &= (z-c_k)\left(I_d+{\widetilde{z}}\Sigma(I_d-\gamma U)\right), \end{align}\] with \({\widetilde{z}}=\frac{{\overline{z}}-c_k}{|z-c_k|}\) and \(\Sigma=\frac{c_k\alpha}{|z-c_k|}\Sigma_0\). Using Lemma 5, for any \(x\in \mathbb{C}^d\), we have \[\begin{align} \left|\left((z-c_k)^{-1}I_d-(z-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1}x\right| &= |z-c_k|^{-1}\left|\left(I_d-(I_d+{\widetilde{z}}\Sigma(I_d-\gamma U))^{-1}\right) (I_d-\gamma U)^{-1}x\right| \\ &\leq \frac{2}{1-\gamma^2}|z-c_k|^{-1}, \end{align}\] which holds only if \(-{\mathcal{R}}({\widetilde{z}})=-{\mathcal{R}}(\frac{{\overline{z}}-c_k}{|z-c_k|})\leq\frac{1-\gamma}{\sqrt2}\), that we prove as follows, \[\begin{align} -{\mathcal{R}}\left(\frac{{\overline{z}}-c_k}{|z-c_k|}\right) = \frac{c_k-{\mathcal{R}}(z)}{\sqrt{(c_k-{\mathcal{R}}(z))^2+{\mathcal{I}}(z)^2}} &\leq \frac{1-{\mathcal{R}}(z)}{\sqrt{(1-{\mathcal{R}}(z))^2+{\mathcal{I}}(z)^2}} \\ &= \frac{1-{\mathcal{R}}(z)}{\sqrt{(1-{\mathcal{R}}(z))^2+1-{\mathcal{R}}(z)^2}} \\ &= \frac{1-{\mathcal{R}}(z)}{\sqrt{2-2{\mathcal{R}}(z)}} \\ &= \sqrt{\frac{1-{\mathcal{R}}(z)}{2}} \\ &\leq \sqrt{\frac{1-(1-(1-\gamma)^2)}{2}} =\frac{1-\gamma}{\sqrt{2}}, \end{align}\] where the first line is due to \(u\mapsto\frac{u}{u^2+v^2}\) is non-decreasing for any \(v\in \mathbb{R}\), and the last one comes from \({\mathcal{R}}(z)\geq 1-(1-\gamma)^2\). Let us integrate for \(\psi\in[-\psi_{\gamma},\psi_{\gamma}]\) and use \(\|\cdot\|^2_F\leq d\|\cdot\|^2_{\rm op}\), \[\begin{align} \frac{e}{2\pi} \int_{-\psi_{\gamma}}^{\psi_{\gamma}} {\left\| \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi}I_d-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{F}^{2}}d\psi &\leq \frac{e}{2\pi} \int_{-\psi_k}^{\psi_k} {\left\| \frac{4I_d}{(1-\gamma^2)^2|e^{i\psi}-c_k|^2} \right\|_{F}^{2}}\,d\psi \\ &\leq \frac{2de}{\pi(1-\gamma^2)^2} \int_{-\pi}^{\pi} \frac{1}{|e^{i\psi}-c_k|^2}d\psi \\ &\leq \frac{4de}{(1-\gamma^2)^2(1-c_k^2)} \\ &= \frac{kde}{(1-\gamma)^2}\frac{4}{(1+\gamma)^2} \\ &\leq \frac{kde}{(1-\gamma)^2}(4-3\gamma), \end{align}\] where the third line is obtained using the residue Theorem, and the last line uses \(\frac{4}{(1+\gamma)^2}\leq 4-3\gamma\). This concludes the case [case:1].

Second step: dealing with case [case:2].

For cases [case:2] and [case:3], we will use the following inequalities \[\label{eq:case23} \begin{align} {\left\| \left((z-c_k)^{-1}I_d-(z-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{F}^{}} &\leq {\left\| (z-c_k)^{-1}I_d-(z-{\widetilde{Q}})^{-1} \right\|_{F}^{}} {\left\| (I_d-\gamma U)^{-1} \right\|_{\rm op}^{}} \\ &\leq \frac{\sqrt{d}}{1-\gamma} {\left\| (z-c_k)^{-1}I_d-(z-{\widetilde{Q}})^{-1} \right\|_{{\rm op}}^{}} \\ &\leq \frac{\sqrt{d}}{1-\gamma} \left(|z-c_k|^{-1} +{\left\| (z-{\widetilde{Q}})^{-1} \right\|_{{\rm op}}^{}}\right), \end{align}\tag{14}\] where \({\left\| \cdot \right\|_{{\rm op}, \mathbb{R}^d}^{}}\) is the operator norm restricted to vectors on \(\mathbb{R}^d\). Define \(Q_R:={\mathcal{R}}(z)-{\widetilde{Q}}={\mathcal{R}}(z)-c_k+\alpha c_k\Sigma_0(I_d-\gamma U)\), so that \(z-{\widetilde{Q}}=Q_R+i{\mathcal{I}}(z)\). Take \(x\in \mathbb{R}^d\) and \(y_1+iy_2=y=(z-{\widetilde{Q}})^{-1}x\), we have \[\mathbb{R}^d\ni x = (z-{\widetilde{Q}})y = (Q_R+i{\mathcal{I}}(z))(y_1+iy_2) = Q_Ry_1-{\mathcal{I}}(z)y_2+i(Q_Ry_2+{\mathcal{I}}(z)y_1),\] which implies \(Q_Ry_2=-{\mathcal{I}}(z)y_1\), so that we obtain \[\label{eq:aux95case2} \begin{align} |(z-{\widetilde{Q}})y|^2 &= (y_1-iy_2)^{\top}(Q_R^{\top}-i{\mathcal{I}}(z))(Q_R+i{\mathcal{I}}(z))(y_1+iy_2) \\ &= |Q_Ry_1|^2 +|Q_Ry_2|^2 +{\mathcal{I}}(z)^2|y|^2 -2{\mathcal{I}}(z)y_1^{\top}(Q_R^{\top}-Q_R)y_2 \\ &= |Q_Ry_1|^2 +{\mathcal{I}}(z)^2(2|y_1|^2+|y_2|^2) -2\alpha c_k\gamma{\mathcal{I}}(z)y_1^{\top}(\Sigma_0U-U^{\top}\Sigma_0)y_2 \\ &\geq {\mathcal{I}}(z)^2(2|y_1|^2+|y_2|^2) -\frac{8\gamma{\mathcal{I}}(z)^2}{(1+\gamma)^2}|y_1||y_2| \\ &\geq {\mathcal{I}}(z)^2(2|y_1|^2+|y_2|^2) -2{\mathcal{I}}(z)^2|y_1||y_2| \\ &\geq {\mathcal{I}}(z)^2(2|y_1|^2+|y_2|^2) -{\mathcal{I}}(z)^2\left(\frac{3}{2}|y_1|^2+\frac{2}{3}|y_2|^2\right) \\ &= {\mathcal{I}}(z)^2\left(\frac{1}{2}|y_1|^2+\frac{1}{3}|y_2|^2\right) \geq \frac{{\mathcal{I}}(z)^2}{3}|y|^2 \end{align}\tag{15}\] where we used \(|Q_Ry_2|^2={\mathcal{I}}(z)^2|y_1|^2\) and \(Q_R^{\top}-Q_R=\alpha c_k\gamma(\Sigma_0U-U^{\top}\Sigma_0)\) to get the third line; \(|{\mathcal{I}}(z)|\geq\sqrt{1-(1-(1-\gamma)^2)^2}\geq\sqrt{1-(1-(1-\gamma)^2)}=1-\gamma\), \(\alpha<\frac{2(1-\gamma)}{(1+\gamma)^2}\leq \frac{2|I(z)|}{(1+\gamma)^2}\), \(c_k\leq1\), \(\|\Sigma_0U\|_{\rm op}\leq\|\Sigma_0\|_{\rm op}\|U\|_{\rm op}\leq1\) to obtain the fourth line; \(4\gamma\leq(1+\gamma)^2\) to get the fifth line; and the Young’s inequality \(2|y_1||y_2|\leq\frac{3}{2}|y_1|^2+\frac{2}{3}|y_2|^2\) to obtain the last one. This implies \[{\left\| (z-{\widetilde{Q}})^{-1} \right\|_{\rm op}^{}} \leq \sqrt{\frac{3}{{\mathcal{I}}(z)^2}} = \frac{\sqrt{3}}{|\sin(\psi)|}\] for \(z=e^{i\psi}\) such that \(|{\mathcal{R}}(z)|\leq\gamma(2-\gamma)\). Similarly, we have \(|z-c_k|^{-1}\leq \frac{1}{|\sin(\psi)|}\). Then using the above computations and \((\sqrt3+1)^2\leq 8\) we obtain \[\begin{align} &\frac{e}{2\pi} \int_{|\psi|\in(\psi_{\gamma},\pi-\psi_{\gamma})} {\left\| \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi}I_d-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{F}^{2}}d\psi \\ &\leq \frac{8de}{\pi(1-\gamma)^2} \int_{\psi_{\gamma}}^{\pi-\psi_{\gamma}} \frac{1}{\sin(\psi)^2} d\psi \\ &\leq \frac{8de}{\pi(1-\gamma)^2} \bigl[-{\rm cotan}(\psi)\bigr]_{\psi_{\gamma}}^{\pi-\psi_{\gamma}} \\ &= \frac{16de}{\pi(1-\gamma)^2} {\rm cotan}(\psi_{\gamma}) \\ &= \frac{16de}{\pi(1-\gamma)^2} \frac{\gamma(2-\gamma)}{\sqrt{1-\gamma^2(2-\gamma)^2}} \\ &\leq \frac{16de}{\pi(1-\gamma)^2} \frac{1+(1-\gamma)}{\sqrt{(1-\gamma)^2(1+2\gamma-\gamma^2)}}\gamma \\ &\leq \frac{16de}{\sqrt{2}\pi(1-\gamma)^3} (1+(1-\gamma)) \\ &\leq \frac{4de}{(1-\gamma)^3} (1+(1-\gamma)), \end{align}\] where we used that the primitive of \(\frac{-1}{\sin^2}\) is \({\rm cotan}\), \({\rm cotan}(\arccos(a))=\frac{a}{\sqrt{1-a^2}}\) for \(a\in(0,1)\), \(\frac{\gamma}{\sqrt{1+2\gamma-\gamma^2}}\leq\frac{\gamma}{\sqrt{1+\gamma}}\leq \frac{1}{\sqrt2}\) and \(\frac{16}{\sqrt{2}\pi}\leq4\).

Third step: dealing with case [case:3].

Once again take \(x\in \mathbb{C}^d\) and \(y=(z-{\widetilde{Q}})^{-1}x\in \mathbb{C}^d\), we have \[\begin{align} |x|=|(z-{\widetilde{Q}})y| &\geq |(z-c_k+c_k\alpha\Sigma_0)y| -\alpha\gamma|\Sigma_0Uy| \\ &\geq \left(\min_{\lambda\in {\rm Sp}(\Sigma_0)} |z-c_k+c_k\alpha\lambda| -\alpha\gamma\right)|y| \\ &\geq \left(\min_{u\in[0,1]} |z-c_k+c_k\alpha u| -\alpha\gamma\right)|y| \end{align}\] Then, let us focus on the term \(|z-c_k+c_k\alpha u|\). Define \(s=1-c_k^{-1}{\mathcal{R}}(z)\in[1,1+c_k^{-1}]\), we get \[\begin{align} |z-c_k+c_k\alpha u|^2 &= ({\mathcal{R}}(z)-c_k+c_k\alpha u)^2+{\mathcal{I}}(z)^2 \\ &= c_k^2(\alpha u-s)^2+1-c_k^2(s-1)^2 \\ &= c_k^2(\alpha^2u^2-2s\alpha u+2s-1) +1 = f(u,s), \end{align}\] where \(f(u,s):= c_k^2(\alpha^2u^2+2s(1-\alpha u)-1)+1\) for \(u\in[0,1]\) and \(s\in[1,1+c_k^{-1}]\). We distinguish two cases. First, if \(\alpha u\leq1\), we have \[\min_sf(u,s) = f(u,1) = c_k^2(\alpha^2u^2+ 2(1-\alpha u)-1) +1 = c_k^2(\alpha u-1)^2+1 \geq 1,\] which implies \[|x| \geq (1-\alpha\gamma)|y| \geq \left(1-\frac{2\gamma(1-\gamma)}{(1+\gamma)^2}\right)|y| \geq \left(1-\frac{1-\gamma}{2}\right)|y| \geq \frac{|y|}{2},\] where we used the above computations, \(\alpha<\frac{2(1-\gamma)}{(1+\gamma)^2}\) and \(4\gamma\leq(1+\gamma)^2\). Second, assume \(\alpha u>1\), we have \[\begin{align} \min_sf(u,s) = f(u,1+c_k^{-1}) &= c_k^2(\alpha^2u^2+2(1+c_k^{-1})(1-\alpha u)-1)+1 \\ &= c_k^2(\alpha^2u^2 -2(1+c_k^{-1})\alpha u +2+2c_k^{-1}-1+c_k^{-2}) \\ &= c_k^2(\alpha^2u^2 -2(1+c_k^{-1})\alpha u +(1+c_k^{-1})^2) \\ &= c_k^2(\alpha u-(1+c_k^{-1}))^2 \\ &= (1-c_k(\alpha u-1))^2 \\ &\geq (1-(\alpha u-1))^2 \\ &= (2-\alpha u)^2 \geq (2-\alpha)^2, \end{align}\] where we used \(1-c_k(\alpha u-1)\geq0\), \(\alpha u-1>0\) and \(c_k\leq1\) to get the sixth line; \(\alpha<2\) and \(u\leq1\) to get the last one. This implies \[|x| \geq (2-\alpha-\gamma\alpha)|y| = (2-(1+\gamma)\alpha)|y|,\] where we have \((1+\gamma)\alpha<\frac{2(1-\gamma)}{1+\gamma}\leq 2\). In all cases, we obtain \[|(z-{\widetilde{Q}})^{-1}x| \leq \min\left(\frac{1}{2},2-(1+\gamma)\alpha\right)^{-1}|x| = \max\left(2,\frac{1}{2-(1+\gamma)\alpha}\right)|x| \leq \left(2 +\frac{1}{2-(1+\gamma)\alpha}\right)|x|\] This, 14 and \(|z-c_k|\geq\sqrt{1+c_k^2}\geq1\), since \({\mathcal{R}}(z)\leq0\), imply \[\begin{align} {\left\| \left((z-c_k)^{-1}I_d-(z-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{F}^{2}} &\leq \frac{2d}{(1-\gamma)^2} \left(|z-c_k|^{-2} +{\left\| (z-{\widetilde{Q}})^{-1} \right\|_{{\rm op}}^{2}}\right) \\ &\leq \frac{2d}{(1-\gamma)^2} \left(3 +\frac{1}{2-(1+\gamma)\alpha}\right), \end{align}\] and then \[\begin{align} \frac{e}{2\pi} \int_{|\psi|\in[\pi-\psi_{\gamma},\pi]} {\left\| \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi}I_d-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{F}^{2}}d\psi \leq \frac{2de}{(1-\gamma)^2} \left(3 +\frac{1}{2-(1+\gamma)\alpha}\right). \end{align}\]

Final step: concluding. From 13 and the three previous steps of the proof, we obtain \[\begin{align} {\mathcal{S}}_k &\leq \frac{de}{(1-\gamma)^2}(1+3(1-\gamma)) +\frac{4de}{(1-\gamma)^3k} (1+(1-\gamma)) +\frac{2de}{(1-\gamma)^2k} \left(3 +\frac{1}{2-(1+\gamma)\alpha}\right) \\ &\leq \frac{de}{(1-\gamma)^2} \left(1+ \frac{4}{k(1-\gamma)} +3(1-\gamma) +\frac{10}{k}+\frac{1}{k(1-\frac{(1+\gamma)\alpha}{2})} \right). \end{align}\] ◻

Proof. Define \(A=I_d-\gamma U\) and \(M=I_d+z\Sigma A\), we have \[\begin{align} \left(I_d-(I_d+z\Sigma(I_d-\gamma U))^{-1}\right) (I_d-\gamma U)^{-1} &= (I_d-M^{-1})A^{-1} \\ &= M^{-1}(M-I_d)A^{-1} \\ &= z(I_d+z\Sigma A)^{-1}\Sigma \\ &= z\Sigma(I_d+zA\Sigma)^{-1}. \end{align}\] Therefore, to conclude, it is sufficient to prove that, for an arbitrary \(x\in \mathbb{C}^d\), \[\label{eq:near95one95aux} |\Sigma(I_d+zA\Sigma)^{-1}x| = |z\Sigma(I_d+zA\Sigma)^{-1}x| \leq \frac{2}{1-\gamma^2}|x|,\tag{16}\] The remainder of the proof is dedicated to prove the latter inequality. Take \(u=(I_d+zA\Sigma)^{-1}x\) and \(r=\Sigma u\). Let us start with the subsequent observation, \[|{\overline{r}}^{\top}Ar-|r|^2| =\gamma|{\overline{r}}^{\top}Ur| \leq \gamma|r|^2,\] so that \(\frac{{\overline{r}}^{\top}Ar}{|r|^2}\) belongs to \(\overline{B}_{ \mathbb{C}}(1,\gamma)\) the closed ball of center \(1\) and radius \(\gamma\). Then, using \(x=\Sigma^{-1}r+zAr\), we have \[\begin{align} \frac{|{\overline{r}}^{\top}x|}{|r|^2} = \left| \frac{{\overline{r}}^{\top}\Sigma^{-1} r}{|r|^2} +z\frac{{\overline{r}}^{\top}A r}{|r|^2}\right| = \left| \frac{{\overline{r}}^{\top}A r}{|r|^2} +{\overline{z}}\frac{{\overline{r}}^{\top}\Sigma^{-1} r}{|r|^2} \right| \geq d_{|\cdot|}(\overline{B}_{ \mathbb{C}}(1,\gamma),-{\overline{z}} \mathbb{R}_+), \end{align}\] where we used \({\overline{r}}^{\top}\Sigma^{-1} r\geq0\), and \(d_{|\cdot|}\left(\overline{B}_{ \mathbb{C}}(1,\gamma),-{\overline{z}} \mathbb{R}_+\right)\) is the distance between the sets \(\overline{B}_{ \mathbb{C}}(1,\gamma)\) and \(-{\overline{z}} \mathbb{R}_+\). Then, using Cauchy-Schwarz’ inequality \(|{\overline{r}}^{\top}x|\leq |r||x|\), we obtain \[\begin{align} |x|\geq \frac{|{\overline{r}}^{\top}x|}{|r|} \geq d_{|\cdot|}(\overline{B}_{ \mathbb{C}}(1,\gamma),-{\overline{z}} \mathbb{R}_+)|r|. \end{align}\] It only remains to derive an appropriate lower bound for the latter distance. Let us consider two cases. First, if \({\mathcal{R}}(z)\geq0\), it is easy to check that this distance is equal to \(1-\gamma\) that is reached for \(1-\gamma\in\overline{B}_{ \mathbb{C}}(1,\gamma)\) and \(0\in {\overline{z}} \mathbb{R}_-\). Second, if \(0\geq {\mathcal{R}}(z)\geq -\frac{1-\gamma}{\sqrt2}\). we have \[\begin{align} d_{|\cdot|}\left(\overline{B}_{ \mathbb{C}}(1,\gamma),-{\overline{z}} \mathbb{R}_+\right) &= d_{|\cdot|}\left(1,-{\overline{z}} \mathbb{R}_+\right)- \gamma \\ &= \inf_{t\in \mathbb{R}_+} |1+t{\overline{z}}| -\gamma \\ &= \inf_{t\in \mathbb{R}_+} \sqrt{|1+t{\mathcal{R}}(z)|^2+t^2(1-|{\mathcal{R}}(z)|^2)} -\gamma \\ &= \inf_{t\in \mathbb{R}_+} \sqrt{1+2t{\mathcal{R}}(z)+t^2} -\gamma \\ &\geq \inf_{t\in \mathbb{R}_+} \sqrt{1-\sqrt{2}(1-\gamma)t+t^2} -\gamma \\ &= \sqrt{1-\frac{(1-\gamma)^2}{2}} -\gamma \\ &\geq 1-\frac{(1-\gamma)^2}{2}-\gamma \\ &= \frac{1-\gamma^2}{2} \end{align}\] where we used the fact that the minimum of \(t\in \mathbb{R}_+\mapsto 1-2at+t^2\) equals \(1-a^2\) for \(a\geq0\) to get the sixth line, and \(1-\frac{a}{2}\geq(1+a)^{-1}\) for \(a\in[0,1]\) to get the last one. Using the above calculations, we obtain \[|\Sigma(I_d+zA\Sigma)^{-1}x| = |r| \leq d_{|\cdot|}\left(\overline{B}_{ \mathbb{C}}(1,\gamma),-{\overline{z}} \mathbb{R}_+\right)^{-1}|x| \leq \frac{2}{1-\gamma^2}|x|,\] which is exactly Inequality 16 . This concludes the proof. ◻

Proof. Since the spectral radius of \(M\) is lower than \(1\), it is power-bounded, i.e., \(\sup_{k\geq0}\|M^k\|_{\rm op}<\infty\). Therefore, the series \[F_0(z) = \sum_{\ell=0}^{\infty} c^{\ell}z^{-\ell-1}M^{\ell},\] is uniformly convergent on \(\Gamma:=\{z\in \mathbb{C}, |z|=1\}\). This implies that \((I_d-cz^{-1}M) F_0(z)=z^{-1}I_d\) and then \[F_0(z) = z^{-1}(I_d-cz^{-1}M)^{-1} = (zI_d-cM)^{-1}.\] Similarly, we obtain \[F(z) := (z-c)^{-1}-(zI_d-cM)^{-1} = \sum_{\ell=0}^{\infty} c^{\ell}z^{-\ell-1}(I_d-M^{\ell}),\] so that, we get \[\begin{align} z^{-1} F(z^{-1})^{\top}F(z) &= z^{-1}\left(\sum_{\ell=0}^{\infty} c^{\ell}z^{\ell+1}(I_d-M^{\ell})\right)^{\top} \left(\sum_{\ell=0}^{\infty} c^{\ell}z^{-\ell-1}(I_d-M^{\ell})\right) \\ &= \sum_{k,\ell\geq0} c^{k+\ell}z^{k-\ell-1}(I_d-M^k)^{\top}(I_d-M^{\ell}). \end{align}\] For similar arguments as above, the latter double series is uniformly convergent on \(\Gamma\) which allows us to interchange summation and integration as follows, \[\begin{align} \int_{|z|=1} z^{-1} F(z^{-1})^{\top}F(z)dz &= \sum_{k,\ell\geq0} c^{k+\ell}(I_d-M^k)^{\top}(I_d-M^{\ell}) \int_{|z|=1} z^{k-\ell-1}dz \\ &= 2i\pi\sum_{k,\ell\geq0} c^{k+\ell}(I_d-M^k)^{\top}(I_d-M^{\ell}), \end{align}\] where we used that \(\int_{|z|=1}z^{k-\ell-1}=2i \pi\) by Residue theorem. This concludes the proof. ◻

Proof of Theorem 1. This is a straightforward consequence of Propositions 8 and 12, with \(\beta=(1+\gamma)^2\), \(\beta_1=1+\gamma\), \(c_{\Sigma}=(1-\gamma)^{-1}\) and \(\sigma^2=\sigma_0^2\). ◻

Proof of Proposition 2. In this case, the matrices \(\Sigma_0,\Sigma_1,H,S\) are straightfoward to compute. In particular, we have \[\Sigma_0=\Sigma_1=\omega I_d\text{ and }H=S=(1-\gamma)\omega I_d.\] Moreover, we have \(b={\mathbb{E}}[R_k\varphi(X_k)]=0\) so that \(\theta^*=0\). Therefore, we have \[{\mathbb{E}}_{X\sim m}\left[|v(X,{\overline{\theta}}_k)-v(X,\theta^*)|^2\right] = \omega{\mathbb{E}}\left[|{\overline{\theta}}_k|^2\right].\] For \(1\leq i\leq d\), we have \(\theta_{k,i}\) satisfies \[\theta_{k,i} = (1-d\alpha(1-\gamma)\omega B_{k,i})\theta_{k-1,i} +\alpha\sqrt{d\omega}B_{k,i}R_k,\] where \((B_{k})_{k\geq1}\) are i.i.d. \(d\)-dimensional random variables, with \(B_{1,i}\sim\)Ber\((\frac{1}{d})\) and \(\sum_{i=1}^dB_{1,i}=1\) a.e..

On the one hand, from Lemma 7, under the regime described in Proposition 2, for \(C=5.5\), \[\label{eq:sharpness95aux} {\mathbb{E}}_{X\sim m}\left[|v(X,{\overline{\theta}}_k)-v(X,\theta^*)|^2\right] \gtrsim \frac{(1-e^{-C})^2|\theta_0|^2}{C\alpha(1-\gamma)k} +\frac{\sigma_0^2}{(1-\gamma)^2 k} \left(1-\frac{3-4e^{-C}+e^{-2C}}{2C}\right).\tag{17}\] On the other hand, under the same convergence regime, observe that the upper bound in Theorem 1 is equivalent to \[\begin{align} E &= \left(\left(\frac{|\theta_0|^2}{2\alpha(1-\gamma)k}\right)^{\frac{1}{2}} +\left(\frac{e\sigma_0^2}{(1-\lambda)(1-\gamma)^2 k}\right)^{\frac{1}{2}}\right)^2 \\ &\leq \frac{(1+A)|\theta_0|^2}{2\alpha(1-\gamma)k} +\frac{2(1+A^{-1})e\sigma_0^2}{(1-\gamma)^2 k}, \end{align}\] where we take \(A=2.7\). Then, we can easily check that \(1.85=\frac{1+A}{2}<11\frac{(1-e^{-C})^2}{C}\approx1.98\) and \(7.45\approx2e(1+A^{-1})< 11\left(1-\frac{3-4e^{-C}+e^{-2C}}{2C}\right)\approx 8.02\). Therefore we obtain \[{\mathbb{E}}_{X\sim m}\left[|v(X,{\overline{\theta}}_k)-v(X,\theta^*)|^2\right] \gtrsim 11E,\] which concludes the proof. ◻

Proof. Similarly as in the proof of Proposition 2, for \(k\to\infty\), \(\gamma\to1\) and \(k(1-\gamma)\to1.25\), the asymptotic inequality 17 holds for \(C=1.25\). This implies \[{\mathbb{E}}_{X\sim m}\left[|v(X,{\overline{\theta}}_k)-v(X,\theta^*)|^2\right] \gtrsim \frac{(1-e^{-C})^2|\theta_0|^2}{C\alpha(1-\gamma)k}\] which implies the first inequality in Corollary 1, since \(\frac{2(1-e^{-C})^2}{C}\geq\frac{1}{1.25}\).

Now consider for \(\gamma\to1\) and \(k(1-\gamma)\to\infty\). Repeating the arguments in the proof of Lemma 7, we obtain \[{\mathbb{E}}_{X\sim m}\left[|v(X,{\overline{\theta}}_k)-v(X,\theta^*)|^2\right] \gtrsim \frac{d\sigma_0^2}{(1-\gamma)^2k} \sim \frac{1-\frac{\alpha}{\alpha_0(\gamma)}}{e} \frac{de\sigma_0^2(1+\varepsilon_{k,\gamma})}{(1-\frac{\alpha}{\alpha_0(\gamma)})(1-\gamma)^2k}.\] This concludes the proof. ◻

Proof of Lemma 7. Using superposition principle, we get \(Y_k=Y^b_k+Y^v_k\), with \[\begin{align} Y^b_{k} &= (1-\lambda B_k)Y^b_{k-1}, Y^b_0=y_0 \\ Y^v_{k} &= (1-\lambda B_k)Y^v_{k-1} +B_kZ_k, Y^v_0=0. \end{align}\] Moreover, using that \(Z_k\) is centered and independent with \(Y^b_k\), we get \({\mathbb{E}}[Y_k^v]=0\) and \({\mathbb{E}}\left[Y_k^bY_k^v\right]=0\). Therefore, we obtain \[{\mathbb{E}}\left[Y_k^2\right] = {\mathbb{E}}\left[(Y_k^b)^2\right] +{\mathbb{E}}\left[(Y_k^v)^2\right]\]

First step: the bias.

In this step, we only consider \(Y_k^b\). We have \[{\mathbb{E}}\left[Y^b_k\right] = p(1-\lambda){\mathbb{E}}\left[Y^b_{k-1}\right] +(1-p){\mathbb{E}}\left[Y^b_{k-1}\right] = (1-p\lambda){\mathbb{E}}\left[Y^b_{k-1}\right] = (1-p\lambda)^ky_0,\] so that we get \[{\mathbb{E}}\left[({\overline{Y}}^b_k)^2\right] \geq {\mathbb{E}}\left[{\overline{Y}}^b_k\right]^2 = \left(\frac{1}{k}\sum_{i=0}^{k-1} (1-p\lambda)^iy_0^2\right) = \frac{(1-(1-p\lambda)^k)^2y_0^2}{\lambda^2p^2k^2}.\] Therefore, for \(k\to \infty\), \(\lambda\to 0\) and \(k\lambda p\to C>0\), using \((1-p\lambda)^k\to e^{-C}\), we obtain \[{\mathbb{E}}\left[({\overline{Y}}^b_k)^2\right] \gtrsim \frac{(1-e^{-C})^2y_0^2}{C\lambda pk}.\]

Second step: the variance term.

Recall that \({\mathbb{E}}[Y^v_k]=0\). Then, for \(\lambda'=2\lambda-\lambda^2\in(0,1)\), we have \[\begin{align} {\mathbb{E}}\left[(Y^v_k)^2\right] &= \left(p(1-\lambda)^2+(1-p)\right) {\mathbb{E}}\left[(Y^v_{k-1})^2\right] +p\sigma^2 \\ &= \left(1-p(2\lambda-\lambda^2)\right) {\mathbb{E}}\left[(Y^v_{k-1})^2\right] +p\sigma^2 \\ &= p\sigma^2\sum_{i=0}^{k-1} \left(1-p\lambda'\right)^i \\ &= \frac{(1-(1-p\lambda')^k)\sigma^2}{\lambda'}. \end{align}\] Let \(({\mathcal{F}}_k)_{k\geq1}\) be the filtration associated to \((Z_k,B_k)_{k\geq1}\). Using similar arguments as in the first step, for \(1\leq i\leq j\), we get \[{\mathbb{E}}\left[Y^v_j\,|\,{\mathcal{F}}_i\right] = (1-p\lambda)^{j-i} Y^v_i.\] This implies that \[{\mathbb{E}}\left[Y^v_jY^v_i\right] = (1-p\lambda)^{j-i} {\mathbb{E}}\left[(Y^v_i)^2\right] = (1-p\lambda)^{j-i} \frac{(1-(1-p\lambda')^i)\sigma^2}{\lambda'}.\] Therefore, we obtain \[\begin{align} {\mathbb{E}}\left[({\overline{Y}}^v_k)^2\right] &= \frac{1}{k^2} \left( 2\sum_{0\leq i\leq j\leq k-1}{\mathbb{E}}\left[Y^v_jY^v_i\right] -\sum_{i=0}^{k-1}{\mathbb{E}}\left[(Y^v_i)^2\right] \right) \\ &= \frac{\sigma^2}{\lambda'k^2} \sum_{i=0}^{k-1} \left( (1-(1-p\lambda')^i) \left(2\sum_{j=i}^{k-1}(1-p\lambda)^{j-i} -1\right)\right) \\ &= \frac{\sigma^2}{\lambda'k^2} \sum_{i=0}^{k-1} \left( (1-(1-p\lambda')^i) \left(\frac{2(1-(1-p\lambda)^{k-i})}{p\lambda} -1\right)\right) \\ &= \frac{2\sigma^2}{p\lambda\lambda'k^2} \sum_{i=0}^{k-1} \left( 1 -(1-p\lambda')^i -(1-p\lambda)^{k-i} +(1-p\lambda)^{k}\left(\frac{1-p\lambda'}{1-p\lambda}\right)^{i} \right) -\frac{\sigma^2}{\lambda'k^2} \sum_{i=0}^{k-1}(1-(1-p\lambda')^i) \\ &= \frac{2\sigma^2}{p\lambda\lambda'k^2} \left(k -\frac{1-(1-p\lambda')^k}{p\lambda'} -\frac{1-(1-p\lambda)^k}{p\lambda} +(1-p\lambda)\frac{(1-p\lambda)^k-(1-p\lambda')^k}{p(\lambda'-\lambda)}\right) \\ & -\frac{\sigma^2}{\lambda'k^2} \left(k-\frac{1-(1-p\lambda')^k}{p\lambda'}\right). \end{align}\] Therefore, for \(k\to \infty\), \(\lambda\to 0\) and \(k\lambda p\to C>0\), we obtain the following asymptotic equivalent \[\begin{align} {\mathbb{E}}\left[({\overline{Y}}^v_k)^2\right] &\sim \frac{\sigma^2}{p\lambda^2 k} \left( 1-\frac{1-e^{-2C}}{2C} -\frac{1-e^{-C}}{C} +\frac{e^{-C}-e^{-2C}}{C}\right) -\frac{\sigma^2}{2\lambda k} \left(1-\frac{1-e^{-2C}}{2C}\right) \\ &= \frac{\sigma^2}{p\lambda^2 k} \left( 1-\frac{3-4e^{-C}+e^{-2C}}{2C}\right) -\frac{\sigma^2}{2\lambda k} \left(1-\frac{1-e^{-2C}}{2C}\right) \\ &\sim \frac{\sigma^2}{p\lambda^2 k} \left( 1-\frac{3-4e^{-C}+e^{-2C}}{2C}\right), \end{align}\] where we used \(\lambda'\sim2\lambda\), \((1-p\lambda)^k\sim e^{-C}\) and \((1-p\lambda')^k\sim e^{-2C}\) to get the first line, \(\lambda\to0\) and \(1-\frac{3-4e^{-C}+e^{-2C}}{2C}>0\) for \(C>0\) to get the last one.

This concludes the proof. ◻

Proof. The convergence rate is a consequence of Theorem 15 with \(\beta=(1+\gamma)^2\), \(\beta_1=1+\gamma\), \(c_{\Sigma}=(1-\gamma)^{-1}\) and \(\sigma^2=\sigma_0^2\).

Therefore, it only remains to prove the second part of the theorem. Take the Markov Process on \({\mathcal{X}}=\{1,-1\}\) such that \(X'=-X\) a.e.. Take \(m\equiv\frac{1}{2}\) the uniform probability distribution, \(d=1\) and \(\phi(x)=x\). Consider \((R_k)_{k\geq1}\) i.i.d. with \(R_1\sim{\mathcal{N}}(0,\sigma_0^2)\). For \(\alpha\geq\alpha_1(\gamma)=\frac{2}{1+\gamma}\), \(k\geq1\), we have \[\theta_k = (1-\alpha(1+\gamma))\theta_{k-1} +\alpha R_k = r^k\theta_0 +\alpha\sum_{i=0}^{k-1}r^{i}R_{k-i},\] with \(r=1-\alpha(1+\gamma)<-1\). Therefore, we obtain \[{\mathbb{E}}\left[|\theta_k|^2\right] = r^{2k}\theta_0^2 +\alpha^2\sigma_0^2\sum_{i=0}^{k-1}r^{2i} = r^{2k}\theta_0^2 +\alpha^2\sigma_0^2 \frac{r^{2k}-1}{r^2-1} \underset{k\to\infty}{\longrightarrow}+\infty.\] Similarly, we have \[{\mathbb{E}}_{m}\left[|v(X,{\overline{\theta}}_k)-v(X,\theta^*)|^2\right] = {\mathbb{E}}\left[|{\overline{\theta}}_k|^2\right] = \frac{(r^k-1)^2}{(1-r)^2k^2}|\theta_0|^2 +\frac{\alpha^2\sigma_0^2}{(1-r)^2k^2}|\theta_0|^2 \sum_{i=1}^{k-1}|r^i-1|^2 \underset{k\to\infty}{\longrightarrow}+\infty.\]

This concludes the proof. ◻

Proof of Theorem 4. This is a straightforward consequence of Proposition 13, the equality \({\mathcal{S}}_k={\rm tr}(T_k)\) and Proposition 18, with \(\beta=(1+\gamma)^2\), \(\beta_1=1+\gamma\), \(c_{\Sigma}=(1-\gamma)^{-1}\) and \(\sigma^2=\sigma_0^2\). ◻

Proof. Using similar arguments as in the beginning of the proof of Proposition 12, we have \[\label{eq:bound95Tk} {\left\| T_k \right\|_{\rm op}^{}} \leq \frac{e}{2\pi k} \int_{-\pi}^{\pi} {\left\| \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi}I_d-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{\rm op}^{2}}d\psi.\tag{18}\] Then, continuing similarly as in the proof of Proposition 12, we obtain \[\frac{e}{2\pi} \int_{-\psi_{\gamma}}^{\psi_{\gamma}} {\left\| \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi}I_d-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{\rm op}^{2}}d\psi \leq \frac{ke}{(1-\gamma)^2}(4-3\gamma),\] where we recall that \(\psi_{\gamma}\) satisfies \(\psi_{\gamma}=\arccos(1-(1-\gamma)^2)\).

It only remains to deal with the part of the integral in 18 on \([-\pi,\pi]\backslash[-\psi_{\gamma},\psi_{\gamma}]\), or more simply on \([\psi_{\gamma},\pi]\) using parity. First, for \(\psi\in[\psi_{\gamma},\pi]\), we have \[{\left\| \left((e^{i\psi}-c_k)^{-1}I_d-(e^{i\psi}I_d-{\widetilde{Q}})^{-1}\right)(I_d-\gamma U)^{-1} \right\|_{\rm op}^{2}} \leq \frac{2}{(1-\gamma)^2} \left(|e^{i\psi}-c_k|^{-2} + {\left\| (e^{i\psi}-{\widetilde{Q}})^{-1} \right\|_{\rm op}^{2}}\right).\] Let us start with the first term in the above sum. Using \(|e^{i\psi}-c_k|^2\geq {\mathcal{I}}(e^{i\psi}-c_k)^2=\sin(\psi)^2\) when \(\psi\in[\psi_{\gamma},\frac{\pi}{2}]\), we obtain \[\begin{align} 2\int_{\psi_{\gamma}}^{\frac{\pi}{2}}|e^{i\psi}-c_k|^{-2}d\psi \leq 2\int_{\psi_{\gamma}}^{\pi}\sin(\psi)^{-2}d\psi \leq\frac{\sqrt{2}(2-\gamma)}{1-\gamma} \leq \frac{\pi}{1-\gamma}, \end{align}\] where we used a similar argument as in the second step of the proof of Proposition 12 to get the second inequality. Then, when \(\psi\in[\frac{\pi}{2},\pi]\), we have \(\Re(e^{i\psi})\leq 0\) so that \(|e^{i\psi}-c_k|^2\geq {\mathcal{R}}(e^{i\psi}-c_k)^2\geq c_k^2\geq 4\) and then \[2\int_{\frac{\pi}{2}}^{\pi}|e^{i\psi}-c_k|^{-2}d\psi \leq 4\pi.\] From the above computations and 18 , we deduce \[\label{eq:bound95Tk2} {\left\| T_k \right\|_{\rm op}^{}} \leq \frac{e}{(1-\gamma)^2}(4-3\gamma) +\frac{5e}{(1-\gamma)^3k} +\frac{2e}{\pi(1-\gamma)^2k} \int_{\psi_{\gamma}}^{\pi} {\left\| (e^{i\psi}-{\widetilde{Q}})^{-1} \right\|_{\rm op}^{2}}d\psi.\tag{19}\] The remainder of the proof is inspired by the third step of the proof of Proposition 12.

First step: preliminary considerations.

Take \(z=e^{i\psi}\) with \(\psi\in[\psi_{\gamma},\pi]\). For \(x\in \mathbb{C}^d\) and \(y=(z-{\widetilde{Q}})^{-\top}x\), we have \[\begin{align} c_k^{-1}|x| = c_k^{-1}|(z-{\widetilde{Q}})^{\top}y| &= |(c_k^{-1}z-(I_d-\alpha(I_d-\gamma U^{\top})\Sigma_0))y| \\ &\geq |(c_k^{-1}z-1+\alpha\Sigma_0)y| -\alpha\gamma|U^{\top}\Sigma_0y|. \\ &\geq |(c_k^{-1}z-1+\alpha\Sigma_0)y| -\alpha\gamma|\Sigma_0y|. \end{align}\] Recall that \(\Sigma_0\) is symmetric positive definite. Let us denote \((\lambda_i)_{1\leq i\leq d}\) the eigenvalues of \(\Sigma_0\), associated with the eigenvectors \((e_i)_{1\leq i\leq d}\). Let us decompose \(y\) in the basis of eigenvectors as \(y=\sum_{i=1}^dy_ie_i\). Recall the notations \(s=1-c_k^{-1}{\mathcal{R}}(z)\) and \(f(u,s)=|z-c_k+c_k\alpha u|^2\) \[\begin{align} |(z-c_k+c_k\alpha\Sigma_0)y|^2 &= \sum_{i=1}^d |z-c_k+c_k\alpha\lambda_i|^2y_i^2 \\ &= \sum_{i=1}^d f(\lambda_i,s)y_i^2 \\ &= c_k^2\sum_{i=1}^d (\alpha^2\lambda_i^2+2s(1-\alpha \lambda_i)-1+c_k^{-2})y_i^2 \\ &= c_k^2\left(\alpha^2u^2 +2s(1-\alpha{\overline{\lambda}})-1+c_k^{-2}\right)|y|^2 \\ &\geq c_k^2\left(\alpha^2u^2 +2s(1-\alpha u)-1+c_k^{-2}\right)|y|^2 \\ &= f(u,s), \end{align}\] with \({\overline{\lambda}}:=\sum_{i=1}^d\lambda_i\frac{y_i^2}{|y|^2}\) and \(u=\sqrt{\sum_{i=1}^d\lambda_i^2\frac{y_i^2}{|y|^2}}\), where the computations to get the third line are detailed in the third step of the proof of Proposition 12, and the fifth line is obtained by Cauchy-Schwarz inequality \({\overline{\lambda}}\leq u\).

As in the third step of the proof of Proposition 12, we distinguish two cases. First, if \(\alpha u>1\), we have once again \(f(u,s)\geq (2-\alpha)^2\) and then \[\label{eq:aux95alphau} |x| \geq (2-\alpha-\gamma\alpha)|y| = (2-\alpha(1+\gamma))|y|.\tag{20}\] Only the case \(\alpha u\leq1\) remains to be dealt with. To do so, we introduce further materials in this step, starting with \(\delta=c_k^{-1}-1>0\), \(w=\alpha u\) and \(g(w,s)\) defined by \[g(w,s) = c_k^{-1}\sqrt{f(u,s)}-\gamma w = \sqrt{w^2+2s(1-w)-1+c_k^{-2}} -\gamma w = \sqrt{(w-s)^2+(2+\delta -s)(s+\delta)} -\gamma w,\] with \(s\in[(1-\gamma)^2(1+\delta)-\delta,2+\delta]\subset[(1-\gamma)^2-\delta,2+\delta]\). Using the above computations, we have \[\label{eq:aux95g} |x|\geq c_kg(w,s)|y|.\tag{21}\] Therefore, to conclude it is sufficient to obtain a convenient lower bound on \(g\). Observe that \[\begin{align} \partial_w g &= \frac{w-s}{\sqrt{(w-s)^2+(2+\delta -s)(s+\delta)}} -\gamma\text{ and } \\ \partial^2_{w,w} g &= \frac{1}{\sqrt{(w-s)^2+(2+\delta -s)(s+\delta)}} -\frac{(w-s)^2}{\left((w-s)^2+(2+\delta -s)(s+\delta)\right)^{\frac{3}{2}}} \geq 0. \end{align}\] Therefore, \(g\) is convex in \(w\). We are now in position to derive useful estimates to deal with the remaining term in 19 . In the two subsequent steps, we consider separately the case \(\Re(z)\leq \gamma\) and \(\Re(z)\in[1-(1-\gamma)^2,\gamma]\), always under the assumption \(w=\alpha u\leq 1\).

Second step: the case of \(\Re(z)\leq \gamma\).

Observe that \[g(1,s) = \sqrt{1+2\delta+\delta^2}-\gamma = 1-\gamma +\delta\text{ and }\partial_wg(1,s) = \frac{1-s}{1+\delta}-\gamma = c_k(1-s)-\gamma.\] Then, assuming \(\Re(z)\leq \gamma\), we have \(\partial_wg(1,s)\leq 0\) for \(w\in[0,1]\). Therefore, using a convex inequality, we obtain, \[\begin{align} g(w,s) &\geq g(1,s)-(1-w)\partial_wg(1,s) \\ &\geq 1-\gamma. \end{align}\] Consequently, using the latter inequality, 20 and 21 , for \(\Re(z)\leq \gamma\), we obtain \[\begin{align} {\left\| (e^{i\psi}-Q)^{-1} \right\|_{\rm op}^{-2}} &\leq \max((2-\alpha(1+\gamma))^{-2},c_k^{-2}(1-\gamma)^{-2}) \\ &\leq (2-\alpha(1+\gamma))^{-2} +c_k^{-2}(1-\gamma)^{-2}. \end{align}\] We conclude this step with the following estimate \[\int_{{\widetilde{\psi}}_{\gamma}}^{\pi} {\left\| (e^{i\psi}-Q)^{-1} \right\|_{\rm op}^{-2}} d\psi \leq \frac{\pi}{(2-\alpha(1+\gamma))^{2}} +\frac{\pi}{c_k^{2}(1-\gamma)^{2}},\] where \({\widetilde{\psi}}:=\arccos(\gamma)\).

Third step: the case of \(\gamma\leq \Re(z)\leq 1- (1-\gamma)^2\).

The minimum of \(g(\cdot,s)\) on \([0,1]\) is lower or equal to the minimum on \(\mathbb{R}\) that is reached for \(w(s)\) such that \(\partial_wg(w(s),s)=0\), i.e., \[w(s) = s+\gamma\sqrt{\frac{(2+\delta-s)(s+\delta)}{1-\gamma^2}}.\] The latter minimum then satisfies \[\begin{align} g(w(s),s) &= \sqrt{(2+\delta -s)(s+\delta)\left(\frac{\gamma^2}{1-\gamma^2}+1\right)} -\gamma\left(s+\frac{\gamma^2}{\sqrt{1-\gamma^2}}\sqrt{(2+\delta -s)(s+\delta)}\right) \\ &= \sqrt{(1-\gamma^2)(2+\delta -s)(s+\delta)} -\gamma s \\ &\geq \sqrt{(1-\gamma^2)c_k^{-1}(1+\gamma)(s+\delta)} -\gamma \sqrt{(1-\gamma)c_k^{-1}(s+\delta)} \\ &= \sqrt{(1-\gamma)c_k^{-1}(s+\delta)} \\ &= c_k^{-1}\sqrt{(1-\gamma)(1-{\mathcal{R}}(z))} \end{align}\] where the third line is obtained using \(c_k(s+\delta)=1-\Re(z)\leq 1-\gamma\) and \(c_k^{-1}=1+\delta\), so that we have \(2+\delta-s\geq 2+2\delta-c_k^{-1}(1-\gamma)=c_k^{-1}(1+\gamma)\) and \(s\leq s+\delta\leq\sqrt{c_k^{-1}(1-\gamma)(s+\delta)}\). Recall that \(|z|=1\), so that \[|z-1|^2 = (1-{\mathcal{R}}(z))^2+{\mathcal{I}}(z)^2 = (1-{\mathcal{R}}(z))^2+1-{\mathcal{R}}(z)^2 = 2(1-{\mathcal{R}}(z)).\]

Final step: getting the desired bound.

Recall that 20 holds for \(\alpha u>1\) and 21 for \(\alpha u\leq1\). Therefore, in both cases, we have \[\begin{align} {\left\| (e^{i\psi}-Q)^{-1} \right\|_{\rm op}^{-2}} &\leq \max\left(\frac{1}{(2-(1+\gamma)\alpha)^2}, \frac{1}{c_k^2g(w,s)^2}\right) \\ &\leq \frac{1}{(2-(1+\gamma)\alpha)^2} +\frac{1}{c_k^2g(w,s)^2}. \end{align}\] Using the lower bound on \(g\) obtained in the two previous steps, we obtain, for \({\widetilde{\psi}}_{\gamma}=\arccos(\gamma)\), \[\begin{align} \int_{\psi_{\gamma}}^{\pi} {\left\| (e^{i\psi}-Q)^{-1} \right\|_{\rm op}^{-2}} d\psi &\leq \frac{(\pi-\psi_{\gamma})}{(2-\alpha(1+\gamma))^{2}} +\int_{\psi_{\gamma}}^{\pi} \frac{1}{(1-\gamma)^2} +\int_{\psi_{\gamma}}^{{\widetilde{\psi}}_{\gamma}} \frac{2}{(1-\gamma)|1-z|^2} d\psi \\ &\leq \frac{\pi}{(2-\alpha(1+\gamma))^{2}} +\frac{\pi}{(1-\gamma)^2} +\frac{1}{1-\gamma} \int_{\psi_{\gamma}}^{{\widetilde{\psi}}_{\gamma}} \frac{2}{\sin(\psi)^2}d\psi \\ &\leq \frac{\pi}{(2-\alpha(1+\gamma))^{2}} +\frac{\pi}{(1-\gamma)^2} +\frac{\sqrt{2}}{(1-\gamma)^2}, \end{align}\] where the derivation of the upper bound of the integral from the second line is detailed in the second step of the proof of Proposition 12. This and 19 imply \[{\left\| T_k \right\|_{\rm op}^{}} \leq \frac{e}{(1-\gamma)^2}(4-3\gamma) +\frac{5e}{(1-\gamma)^3k} +\frac{2e}{(2-\alpha(1+\gamma))^{2}(1-\gamma)^2k} +\frac{2e}{(1-\gamma)^4k} +\frac{2\sqrt{2}e}{\pi(1-\gamma)^4k}.\] This and \(\frac{2\sqrt2}{\pi}\leq1\) lead to the desired inequality, this concludes the proof. ◻

Proof of Lemma 1. We consider \(\varphi\) as in the first case in Lemma 1 and \((\theta_k)_{k\geq0}\) the induced sequence obtained using TD(0). Similarly, we define \({\widetilde{\varphi}}\) and \(({\widetilde{\theta}}_k)_{k\geq0}\) according to the second case. We are going to prove by induction on \(k\geq0\) \[\varphi(x)^{\top}\theta_k = {\widetilde{\varphi}}(x)^{\top}{\widetilde{\theta}}_k \;\text{ for any }x\in{\mathcal{X}}.\] First for \(k=0\), we have \[{\widetilde{\varphi}}(x)^{\top}{\widetilde{\theta}}_0 = {\widetilde{\theta}}_{0,1} +{\widetilde{\varphi}}_{(-1)}(x)^{\top}{\widetilde{\theta}}_{0,(-1)} = C\theta_{0,1} +\varphi_{(-1)}(x)^{\top}\theta_{0,(-1)} = \varphi(x)^{\top}\theta_0.\] Then, for \(k\geq1\), assume that the equality holds at index \(k-1\). Observe that \({\widetilde{\varphi}}(x)^{\top}{\widetilde{\alpha}}{\widetilde{\varphi}}(y)=\alpha\varphi(x)^{\top}\varphi(y)\), so that we obtain \[\begin{align} {\widetilde{\varphi}}(x)^{\top}{\widetilde{\theta}}_k &= {\widetilde{\varphi}}(x)^{\top} \left({\widetilde{\theta}}_{k-1} -{\widetilde{\alpha}}{\widetilde{\varphi}}(X_k)\left(({\widetilde{\varphi}}(X_k)-\gamma{\widetilde{\varphi}}(X_k'))^{\top}{\widetilde{\theta}}_{k-1}-R_k\right)\right) \\ &= \varphi(x)^{\top}\theta_{k-1} -\alpha\varphi(x)^{\top}\varphi(X_k) \left((\varphi(X_k)-\gamma\varphi(X_k'))^{\top}\theta_{k-1}-R_k\right) \\ &= \varphi(x)^{\top} \left(\theta_{k-1} -\alpha\varphi(X_k) \left((\varphi(X_k)-\gamma\varphi(X_k'))^{\top}\theta_{k-1}-R_k\right)\right) \\ &= \varphi(x)^{\top}\theta_k. \end{align}\] ◻

Proof. Observe that \(\Sigma_0\theta_1=\mu=\Sigma_1^{\top}\theta_{\mathbb{1}}\), which implies \(\theta_{\mathbb{1}}^{\top}(\Sigma_0-\gamma\Sigma_1) =\theta_{\mathbb{1}}^{\top}H=(1-\gamma)\mu^{\top}\), so that we get \[{\mathbb{E}}\left[v(X,\theta^*)\right] = \mu^{\top}\theta^* = (1-\gamma)^{-1}\theta_{\mathbb{1}}^{\top}H\theta^* = (1-\gamma)^{-1}\theta_{\mathbb{1}}^{\top}b = (1-\gamma)^{-1}{\mathbb{E}}[R].\] Recall that \(\mu\neq 0\), otherwise \(\theta_{\mathbb{1}}\) cannot exist. The second inequality in the lemma is straightforward. ◻

Proof. Observe that \(H\) and \(b\) write as \[H = \begin{pmatrix} (1-\gamma)^{-1} &\mu_{(-1)}^{\top}\\ \mu_{(-1)}& {\widetilde{H}}, \end{pmatrix}b = \begin{pmatrix} (1-\gamma)^{-1}{\mathbb{E}}[R]\\ {\widetilde{b}} \end{pmatrix}\] with \({\widetilde{H}}={\mathbb{E}}\left[\varphi_{(-1)}(X)(\varphi_{(-1)}(X)-\gamma \varphi_{(-1)}(X'))^{\top}\right]\) and \({\widetilde{b}}={\mathbb{E}}[R\varphi_{(-1)}(X)]\). From the first line in \(H\theta^*=b\), we obtain \[\label{eq:bound95param95trick95theta1} \theta^*_1 = {\mathbb{E}}[R]-(1-\gamma)\mu_{(-1)}^{\top}\theta^*_{(-1)}.\tag{22}\] Using this and the other lines from \(H\theta^*=b\), we get \[{\widetilde{H}}\theta^*_{(-1)} = {\widetilde{b}} -{\mathbb{E}}[R]\mu_{(-1)},\] where \({\widetilde{H}}=H-(1-\gamma)\mu_{(-1)}\mu_{(-1)}^{\top}\).

On the one hand, using similar arguments as in the proof of Theorem 7, we have \[(\theta^*_{(-1)})^{\top}{\widetilde{H}}\theta^*_{(-1)} \geq (1-\gamma(1-g)) (\theta^*_{(-1)})^{\top}{\widetilde{\Sigma}}_0\theta^*_{(-1)} \geq (1-\gamma(1-g)) {\widetilde{\omega}}|\theta^*_{(-1)}|^2,\] where \({\widetilde{\Sigma}}_0={\mathbb{E}}\left[(\varphi_{(-1)}(X)-\mu_{(-1)})(\varphi_{(-1)}(X)-\mu_{(-1)})^{\top}\right]\) and \({\widetilde{\omega}}>0\) is the smallest eigenvalue of \({\widetilde{\Sigma}}_0\) which is positive using the linear independence of the features and the fact that \(\varphi_1\) is constant.

On the other hand, we have \[(\theta^*_{(-1)})^{\top}{\widetilde{H}}\theta^*_{(-1)} = (\theta^*_{(-1)})^{\top}({\widetilde{b}}-{\mathbb{E}}[R]\mu_{(-1}) \leq |\theta^*_{(-1)}|{\mathbb{E}}[R(\varphi_{(-1)}-\mu_{(-1)})]| \leq C_R^{\frac{1}{2}}|\theta_{(-1)}|,\] where \(C_R\) is defined in Assumption [hypo:R].

Consequently, we obtain \[\label{eq:bound95param95trick95theta-1} |\theta^*_{(-1)}| \leq \frac{C_R^{\frac{1}{2}}}{{\widetilde{\omega}}(1-\gamma(1-g))} \leq \frac{C_R^{\frac{1}{2}}}{{\widetilde{\omega}}g},\tag{23}\] and then \(|\theta^*_1|\leq C_R^{\frac{1}{2}}+\frac{C_R^{\frac{1}{2}}}{{\widetilde{\omega}}}\). This concludes the uniform boundedness of \(\theta^*\).

Let us now prove the uniform boundedness of \(\sigma_0^2\) that is given by \[\begin{align} \sigma_0^2 &= \sup_{x\in\mathop{\mathrm{\mathop{\rm supp}}}m} {\mathbb{E}}\left[|(\varphi(X)-\gamma\varphi(X'))^{\top}\theta^*-R|^2\,|\,X=x\right] \\ &= \sup_{x\in\mathop{\mathrm{\mathop{\rm supp}}}m} {\mathbb{E}}\left[|\theta^*_1+(\varphi_{(-1)}(X)-\gamma\varphi_{(-1)}(X'))^{\top}\theta_{(-1)}^*-R|^2\,|\,X=x\right] \\ &= \sup_{x\in\mathop{\mathrm{\mathop{\rm supp}}}m} {\mathbb{E}}\left[| {\mathbb{E}}[R]-(1-\gamma)\mu_{(-1)}^{\top}\theta^*_{(-1)} +(\varphi_{(-1)}(X)-\gamma\varphi_{(-1)}(X'))^{\top}\theta_{(-1)}^*-R|^2\,|\,X=x\right] \\ &\leq \sup_{x\in\mathop{\mathrm{\mathop{\rm supp}}}m} 2{\mathbb{E}}\left[|{\mathbb{E}}[R]-R|^2\,|\,X=x\right] +2{\mathbb{E}}\left[ (\varphi_{(-1)}(X)-\gamma\varphi_{(-1)}(X')-(1-\gamma)\mu_{(-1)})^{\top}\theta_{(-1)}^*|^2\,|\,X=x\right] \\ &\leq 8C_R+18|\theta^*_{(-1)}|^2 \\ &\leq C_R\left(8 +\frac{18}{{\widetilde{\omega}}^2g^2}\right), \end{align}\] where we used 22 to get the third line, and 23 to obtain the last one. This concludes the proof. ◻

Proof of Theorem 5. From the inequalities stated in Lemma 12, we can apply Proposition 16 with \(\Sigma=\Sigma_0\), \(\beta=1+(1+\gamma)^2\), \(c_{\Sigma}=(1-\gamma)^{-1}\) and \(\sigma^2=\sigma_0^2\). It only remains to upper bound \({\mathcal{S}}_k\) using Proposition 19 to obtain the desired rate.

The uniform boundedness of \(\theta^*\) with respect to \(\gamma\) is given by Lemma 9. ◻

Proof. First observe that \(Q=\Sigma_0^{\frac{1}{2}}(I_d-\alpha H)\Sigma_0^{-\frac{1}{2}}\), thus it admits the same spectrum as \(I_d-\alpha H\). Moreover, using ?? , ?? we can take \(c_{\Sigma}=(1-\gamma)^{-1}\) \(\beta=1+(1+\gamma)^2\) so that ?? applies for \(\alpha<\frac{2}{\beta c_{\Sigma}} =\frac{2(1-\gamma)}{1+(1+\gamma)^2}=\alpha_2(\gamma)\). Then ?? implies that the spectrum of \(I_d-\alpha H\) is contained in the complex unit sphere. Therefore, Lemma 6 applies to \(Q\) and Inequality 13 holds.

Then, the first step of the proof of Proposition 12 can be repeated without any change. Concerning the second step, the only change occurs to obtain the fourth line in the chain of inequalities 15 : it requires that \({\left\| \Sigma_0U-U^{\top}\Sigma_0 \right\|_{\rm op}^{}}\leq 2\) is indeed satisfied under the present assumption as stated in 24 .

Therefore, there only remains the third step, i.e., for \(\Re(z)\leq -1+(1-\gamma)^2\), that we handle with a different approach using \(\gamma\geq\frac{1}{2}\). First, we have \[\alpha < \frac{2(1-\gamma)}{1+(1+\gamma)^2} \leq \frac{2(1-\gamma)}{1+\left(1+\frac{1}{2}\right)^2} = \frac{8}{13}(1-\gamma),\] then, using Inequality ?? , we get \[\begin{align} \alpha^2{\left\| \Sigma_0(I_d-\gamma U) \right\|_{\rm op}^{2}} &\leq \frac{(1-\gamma)^2}{4}{\left\| \Sigma_0(I_d-\gamma U) \right\|_{F}^{2}} \\ &\leq \frac{8^2(1-\gamma)^2}{13^2} \left((1-\gamma)^2(((1-\gamma)^{-2}+1)^2+1)+2(1+\gamma)^2\right) \\ &= \frac{8^2}{13^2}\left((1+(1-\gamma)^2)^2+(1-\gamma)^4)+2(1-\gamma^2)^2\right) \\ &\leq \frac{8^2}{13^2}\left(\frac{25}{16}+\frac{1}{16}+\frac{9}{8}\right) \leq 1.01^2. \end{align}\] Moreover, using \(-{\mathcal{R}}(z)\geq 1-(1-\gamma)^2\geq \frac{3}{4}\), we obtain \[|z-c_k|^2 = (c_k-{\mathcal{R}}(z))^2+{\mathcal{I}}(z)^2 = c_k^2-2{\mathcal{R}}(z)c_k+1 \geq c_k^2+\frac{3}{2}c_k+1.\] Therefore, the above inequalities imply that, for \(y\in \mathbb{C}^d\) with \(|y|=1\), we have \[\begin{align} |(z-{\widetilde{Q}})y| &= |\left((c_k-z)I_d -\alpha c_k\Sigma_0(I_d-\gamma U)\right)y| \\ &\geq |c_k-z||y| -\alpha c_k{\left\| \Sigma_0(I_d-\gamma U) \right\|_{\rm op}^{}}|y| \\ &\geq \sqrt{c_k^2+\frac{3}{2}c_k+1} -1.01c_k=f(c_k), \end{align}\] where \(f:x\in[0,1]\to\sqrt{x^2+\frac{3}{2}x+1}-1.01x\). We have \[f'(x) = \frac{x+\frac{3}{4}x}{\sqrt{1+\frac{3}{2}x+x^2}}-1.01 = \sqrt{\frac{x^2+\frac{3}{2}x+\frac{9}{16}}{1+\frac{3}{2}x+x^2}}-1.01 \leq 0.\] Consequently, we obtain \({\left\| (z-{\widetilde{Q}})^{-1} \right\|_{\rm op}^{}} \leq f(1)^{-1}=\left(\sqrt{\frac{7}{2}}-1.01\right)^{-1} \leq2\).

The remainder of the proof is similar to that of Proposition 12. ◻

Proof of Theorem 7. Define \({\widehat{\varphi}}=\varphi-\mu\), \({\widehat{\Sigma}}_0={\mathbb{E}}[{\widehat{\varphi}}(X){\widehat{\varphi}}(X)^{\top}]=\Sigma_0-\mu\mu^{\top}\), \({\widehat{\Sigma}}_1={\mathbb{E}}[{\widehat{\varphi}}(X){\widehat{\varphi}}(X')^{\top}]=\Sigma_1-\mu\mu^{\top}\), \({\widehat H}={\widehat{\Sigma}}_0-\gamma {\widehat{\Sigma}}_1\), \({\widehat{S}}=\frac{{\widehat H}+{\widehat H}^{\top}}{2}\) and \({\widehat b}={\mathbb{E}}[R{\widehat{\varphi}}(X)]=b-{\mathbb{E}}[R]\mu\). From Lemma 14, we can apply Proposition 8 with \(\Sigma={\widehat{\Sigma}}_0\), \(\beta=2(1+\gamma)^2\), \(\beta_1=2(1-\gamma)\), \(c_{\Sigma}=1-(1-g)\gamma\), this implies \[{\mathbb{E}}_{X\sim m}\left[|{\widehat v}(X,{\overline{\theta}}_k)-{\widehat v}(X,\theta^*)|^2\right] \leq \frac{1}{k} \left(\left(\frac{|\theta_0-{\widehat \theta}^*|^2}{2\left(1-\frac{\alpha}{{\widehat \alpha}_1(\gamma)}\right) \alpha(1-(1-g)\gamma)}\right)^{\frac{1}{2}} +\left(\frac{2{\widehat{\sigma}}_0^2{\mathcal{S}}_k}{1-\frac{\alpha}{{\widehat \alpha}_0(\gamma)}}\right)^{\frac{1}{2}}\right)^2.\] It only remains to prove that Proposition 12 holds with \(\gamma\) replaced by \((1-g)\gamma\). This is what we prove in the remainder of this proof.

Let us define \({\widetilde{U}}\) by \({\widetilde{U}}=(1-g)^{-1}{\widehat{\Sigma}}_0^{-\frac{1}{2}}{\widehat{\Sigma}}_1{\widehat{\Sigma}}_0^{-\frac{1}{2}}\), it satisfies \(\|{\widetilde{U}}\|_{\rm op}\leq 1\) by Inequality ?? . Then we obtain \[{\widehat H}={\widehat{\Sigma}}_0^{\frac{1}{2}}(I_d-(1-g)\gamma{\widetilde{U}}){\widehat{\Sigma}}_0^{\frac{1}{2}},\] which is the same structure as for TD(0) but with \(\gamma\) replaced with \((1-g)\gamma\).

The only property of \(U\) used to prove Proposition 12 was its operator norm bounded by one. Therefore, we can repeat all the proof in the case of \({\widehat H}\) with \(\gamma\) replaced by \((1-g)\gamma\).

This concludes the extension of Theorem 1 to PCTD(0) as stated in Theorem 7. The extensions of Theorems 3 and 4 works exactly the same. ◻

Proof. Let \(G=\{z\in \mathbb{C}, |z|=1\}\), we have \[\begin{align} \int_0^{2\pi} \frac{d\theta}{|e^{-i\theta}-u|^2} &= \int_G \frac{1}{|z-u|^2} \frac{dz}{iz} \\ &= \int_G \frac{dz}{(z-u)(z^{-1}-u)iz} \\ &= \int_G \frac{dz}{i(z-u)(1-zu)}. \end{align}\] Recall that the function \(\frac{1}{i(z-u)(1-zu)}\) is holomorphic on \(D(0,1)\backslash\{u\}\) with a pole in \(u\). Therefore, we can use the Residue Theorem to get \[\int_0^{2\pi} \frac{d\theta}{|e^{-i\theta}-u|^2} = 2\pi i \;{\rm Res}_u \left(z\mapsto\frac{1}{i(z-u)(1-zu)}\right) = 2\pi i \frac{1}{i(1-u^2)} = \frac{2\pi}{1-u^2}.\] This concludes the proof. ◻

Proof. To get ?? , it is sufficient to observe \[S^{\rm TD} = \Sigma_0-\frac{\gamma}{2} {\mathbb{E}}\left[\varphi(X)\varphi(X')^{\top} +\varphi(X')\varphi(X)^{\top}\right],\] and use Cauchy-Schwarz inequality.

To get ?? , we compute \[\begin{align} {\mathbb{E}}\left[h^{\rm TD}(h^{\rm TD})^{\top}\right] &= {\mathbb{E}}\left[|\varphi(X)-\gamma\varphi(X')|^2\varphi(X)\varphi(X)^{\top}\right] \\ &\leq (1+\gamma)^2{\mathbb{E}}\left[\varphi(X)\varphi(X)^{\top}\right] = (1+\gamma)^2\Sigma_0. \end{align}\] Now let us prove ?? \[\begin{align} {\mathbb{E}}\left[(h^{\rm TD})^{\top}h^{\rm TD}\right] &= {\mathbb{E}}\left[|\varphi(X)|^2 (\varphi(X)-\gamma\varphi(X')) (\varphi(X)-\gamma\varphi(X'))^{\top}\right] \\ &\leq {\mathbb{E}}\left[ (\varphi(X)-\gamma\varphi(X')) (\varphi(X)-\gamma\varphi(X'))^{\top}\right] \\ &= {\mathbb{E}}\left[ (1+\gamma^2)\varphi(X)\varphi(X)^{\top} -\gamma(\varphi(X)\varphi(X')^{\top}+\varphi(X')\varphi(X))\right] \\ &= (1+\gamma^2)\Sigma_0 -\gamma(\Sigma_1+\Sigma_1^{\top}) \\ &= (1+\gamma)S^{\rm TD} -\gamma(1-\gamma)\left(\Sigma_0+\frac{\Sigma_1+\Sigma_1^{\top}}{2}\right) \\ &\leq (1+\gamma)S^{\rm TD}. \end{align}\] We conclude the proof with ?? : \[{\mathbb{E}}\left[(h^{\rm TD}\theta^*-b^{\rm TD})(h^{\rm TD}\theta^*-b^{\rm TD})^{\top}\right] = {\mathbb{E}}\left[|\delta(X,X',\theta^*)|^2\varphi(X)\varphi(X)^{\top}\right] \leq \sigma_0^2\Sigma_0.\] ◻

Proof. The proofs of ?? and ?? are similar as the ones of ?? and ?? . To get ?? , we compute \[\begin{align} {\mathbb{E}}\left[h^{\rm TD}(h^{\rm TD})^{\top}\right] &= {\mathbb{E}}\left[|\varphi(X)-\gamma\varphi(X')|^2\varphi(X)\varphi(X)^{\top}\right] \\ &\leq ((1-\gamma)^2c_{\gamma}^2+(1+\gamma)^2)\Sigma_0, \end{align}\] where we used that \(|\varphi(X)-\gamma\varphi(X')|^2=(1-\gamma)^2c_{\gamma}^2+|\varphi_{(-1)}(X)-\gamma\varphi_{(-1)}(X')|^2 \leq (1-\gamma)^2c_{\gamma}^2+(1+\gamma)^2\).

It only remains to prove ?? . Let us define \({\widetilde{\Sigma}}_0,{\widetilde{\Sigma}}_1\in \mathbb{R}^{(d-1)\times(d-1)}\) by \[{\widetilde{\Sigma}}_0 = {\mathbb{E}}\left[(\varphi_{(-1)}(X)-\mu_{(-1)})(\varphi_{(-1)}(X)-\mu_{(-1)})^{\top}\right]\text{ and }{\widetilde{\Sigma}}_1 = {\mathbb{E}}\left[(\varphi_{(-1)}(X)-\mu_{(-1)})(\varphi_{(-1)}(X')-\mu_{(-1)})^{\top}\right].\] Define \({\widetilde{U}}={\widetilde{\Sigma}}_0^{-\frac{1}{2}}{\widetilde{\Sigma}}_1{\widetilde{\Sigma}}_0^{-\frac{1}{2}}\). Consider \[L = \begin{pmatrix} c_{\gamma} & 0\\ \mu_{(-1)} & {\widetilde{\Sigma}}_0^{\frac{1}{2}} \end{pmatrix}\text{ so that}LL^{\top}={\widetilde{\Sigma}}_0,L\begin{pmatrix} 1&0\\ 0&{\widetilde{U}} \end{pmatrix}L^{\top}={\widetilde{\Sigma}}_1,L^{\top}L = Q^{\top}{\widetilde{\Sigma}}_0Q\text{ and }U=Q\begin{pmatrix} 1&0\\ 0&{\widetilde{U}} \end{pmatrix}Q^{\top},\] where \(Q:={\widetilde{\Sigma}}_0^{-\frac{1}{2}}L\in {\mathcal{O}}( \mathbb{R}^{d-1})\). This implies that \[\begin{align} Q^{\top}(\Sigma_0U-U^{\top}\Sigma_0)Q &= L^{\top}L \begin{pmatrix} 1&0\\ 0&{\widetilde{U}} \end{pmatrix} -\begin{pmatrix} 1&0\\ 0&{\widetilde{U}}^{\top} \end{pmatrix}L^{\top}L \\ &= \begin{pmatrix} c_{\gamma}^2+|\mu_{(-1)}|^2& \mu_{(-1)}^{\top}{\widetilde{\Sigma}}_0^{\frac{1}{2}}\\ {\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}&{\widetilde{\Sigma}}_0 \end{pmatrix} \begin{pmatrix} 1&0\\ 0&{\widetilde{U}} \end{pmatrix} -\begin{pmatrix} 1&0\\ 0&{\widetilde{U}} \end{pmatrix} \begin{pmatrix} c_{\gamma}^2+|\mu_{(-1)}|^2 &\mu_{(-1)}^{\top}{\widetilde{\Sigma}}_0^{\frac{1}{2}}\\ {\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}&{\widetilde{\Sigma}}_0 \end{pmatrix} \begin{pmatrix} 1&0\\ 0&{\widetilde{U}} \end{pmatrix} \\ &= \begin{pmatrix} c_{\gamma}^2+|\mu_{(-1)}|^2 &\mu_{(-1)}^{\top}{\widetilde{\Sigma}}_0^{\frac{1}{2}}{\widetilde{U}}\\ {\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}&{\widetilde{\Sigma}}_0{\widetilde{U}} \end{pmatrix} -\begin{pmatrix} c_{\gamma}^2+|\mu_{(-1)}|^2& \mu_{(-1)}^{\top}{\widetilde{\Sigma}}_0^{\frac{1}{2}}\\ {\widetilde{U}}^{\top}{\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}&{\widetilde{U}}^{\top}{\widetilde{\Sigma}}_0 \end{pmatrix} \\ &= \begin{pmatrix} 0&\mu_{(-1)}^{\top}{\widetilde{\Sigma}}_0^{\frac{1}{2}}({\widetilde{U}}-I_d)\\ (I_d-{\widetilde{U}}^{\top}){\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}&{\widetilde{\Sigma}}_0{\widetilde{U}}-{\widetilde{U}}^{\top}{\widetilde{\Sigma}}_0 \end{pmatrix}. \\ &= \begin{pmatrix} 0&-y^{\top}\\ y &0 \end{pmatrix} +\begin{pmatrix} 0&0\\ 0&{\widetilde{\Sigma}}_0{\widetilde{U}}-{\widetilde{U}}^{\top}{\widetilde{\Sigma}}_0 \end{pmatrix}, \end{align}\] where \(y:=(I_d-{\widetilde{U}}^{\top}){\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}\). Therefore, we obtain \[\label{eq:aux95antisym} {\left\| \Sigma_0U-U^{\top}\Sigma_0 \right\|_{\rm op}^{}} \leq |y|^2 +{\left\| {\widetilde{\Sigma}}_0{\widetilde{U}}-{\widetilde{U}}^{\top}{\widetilde{\Sigma}}_0 \right\|_{\rm op}^{}}.\tag{24}\] On the one hand, we have \[\begin{align} |y|^2 \leq 2{\left\| {\widetilde{\Sigma}}_0^{\frac{1}{2}} \right\|_{\rm op}^{}}|\mu_{(-1)}| \leq {\left\| {\widetilde{\Sigma}}_0 \right\|_{\rm op}^{}}+|\mu_{(-1)}|^2 &\leq {\rm tr}({\widetilde{\Sigma}}_0)+|\mu_{(-1)}|^2 \\ &= {\mathbb{E}}\left[|\varphi_{(-1)}(X)-\mu_{(-1)}|^2\right]+\mu_{(-1)}^2 = {\mathbb{E}}\left[|\varphi_{(-1)}(X)|^2\right] \leq 1. \end{align}\] On the other hand, take \((\lambda_i,v_i)_{1\leq i\leq d-1}\) the couples of eigenvalues and eigenvectors of \({\widetilde{\Sigma}}_0\), we have \[\begin{align} {\left\| {\widetilde{\Sigma}}_0{\widetilde{U}}-{\widetilde{U}}^{\top}{\widetilde{\Sigma}}_0 \right\|_{\rm op}^{}} &= \sum_{i=1}^{d-1} \lambda_i(v_i({\widetilde{U}}^{\top}v_i)^{\top}-({\widetilde{U}}^{\top}v_i)v_i^{\top}) \\ &\leq \sum_{i=1}^{d-1} \lambda_i {\left\| v_i({\widetilde{U}}^{\top}v_i)^{\top}-({\widetilde{U}}^{\top}v_i)v_i^{\top} \right\|_{\rm op}^{}} \\ &\leq \sum_{i=1}^{d-1} \lambda_i |v_i||{\widetilde{U}}^{\top}v_i| \\ &\leq \sum_{i=1}^{d-1}\lambda_i ={\rm tr}({\widetilde{\Sigma}}_0)\leq 1. \end{align}\] where we used Lemma 13 to get the third line, \(\|{\widetilde{U}}\|_{\rm op}\leq1\) to get the last line. We conclude using 24 and the above inequalities.

Let us now prove Inequality ?? . Using similar computations as above, we have \[\begin{align} Q\Sigma_0(I_d-\gamma U)Q^{\top} = L^{\top}L \left(I_d-\gamma \begin{pmatrix} 1&0\\ 0&{\widetilde{U}} \end{pmatrix}\right) &= \begin{pmatrix} c_{\gamma}^2+|\mu_{(-1)}|^2& \mu_{(-1)}^{\top}{\widetilde{\Sigma}}_0^{\frac{1}{2}}\\ {\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}&{\widetilde{\Sigma}}_0 \end{pmatrix} \begin{pmatrix} 1-\gamma&0\\ 0&I_{d-1}-\gamma{\widetilde{U}} \end{pmatrix} \\ &= \begin{pmatrix} (1-\gamma)(c_{\gamma}^2+|\mu_{(-1)}|^2)& \mu_{(-1)}^{\top}{\widetilde{\Sigma}}_0^{\frac{1}{2}}(I_{d-1}-\gamma {\widetilde{U}})\\ (1-\gamma){\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}&{\widetilde{\Sigma}}_0(I_{d-1}-\gamma {\widetilde{U}}) \end{pmatrix}. \end{align}\] Therefore, we obtain \[\begin{align} {\left\| \Sigma_0(I_d-\gamma U)Q^{\top} \right\|_{F}^{2}} &= (1-\gamma)^2(c_{\gamma}^2+|\mu_{(-1)}|^2)^2 +\left|(I_d-\gamma {\widetilde{U}}^{\top}){\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}\right|^2 \\ &+\left|(1-\gamma){\widetilde{\Sigma}}_0^{\frac{1}{2}}\mu_{(-1)}\right|^2 +{\left\| {\widetilde{\Sigma}}_0(I_{d-1}-\gamma {\widetilde{U}}) \right\|_{F}^{2}} \\ &\leq (1-\gamma)^2(c_{\gamma}^2+1)^2 +(1+\gamma)^2 +(1-\gamma)^2 +(1+\gamma)^2 \\ &= (1-\gamma)^2((c_{\gamma}^2+1)^2+1)+2(1+\gamma)^2, \end{align}\] where we used \(\|{\widetilde{U}}\|_{\rm op},\|{\widetilde{\Sigma}}\|_{\rm op}\leq 1\) and \({\left\| {\widetilde{\Sigma}}_0(I_{d-1}-\gamma {\widetilde{U}}) \right\|_{F}^{2}} \leq(1+\gamma)^2{\rm tr}({\widetilde{\Sigma}}_0^2)\leq (1+\gamma)^2{\rm tr}({\widetilde{\Sigma}}_0)\leq (1+\gamma)^2\) since \({\rm tr}({\widetilde{\Sigma}}_0)={\mathbb{E}}[|\varphi_{(-1)}(X)|]\leq1\). ◻

Proof. It is sufficient to prove the result for \(|u|=|v|=1\). Take \(v=\lambda_1 u+\lambda_2w\), with \(\lambda_1^2+\lambda_2^2=1\), \(w\in u^{\perp}\) and \(|w|=1\). We have \[uv^{\top}-vu^{\top} = \lambda_2(uw^{\top}-wu^{\top}).\] Moreover, since \(u\perp w\), for any \(x\in \mathbb{R}^d\), we have \[|(uw^{\top}-wu^{\top})x|^2 = |w^{\top}x|^2+|u^{\top}x|^2 = \left|\Pi_{{\rm Span}(u,w)}x\right|^2 \leq |x|^2,\] where \(\Pi_{{\rm Span}(u,w)}\) is the orthogonal projection on Span\((u,w)\). Therefore, we obtain \[{\left\| uv^{\top}-vu^{\top} \right\|_{\rm op}^{}} \leq \lambda_2 {\left\| uw^{\top}-wu^{\top} \right\|_{\rm op}^{}} \leq \lambda_2 \leq 1.\] This concludes the proof. ◻

Proof. Let \(x,y\in \mathbb{R}^d\) with \(|x|=|y|=1\), define \(\theta_x={\widehat{\Sigma}}_0^{-\frac{1}{2}}x\) and \(\theta_y={\widehat{\Sigma}}_0^{-\frac{1}{2}}y\), we have \[\begin{align} x^{\top}{\widehat U}y = \theta_x^{\top}{\widehat{\Sigma}}_1\theta_y &= {\mathbb{E}}\left[{\widehat v}(X,\theta_x){\widehat v}(X',\theta_y)\right] \\ &= {\mathbb{E}}\left[{\widehat v}(X,\theta_x){\mathbb{E}}\left[{\widehat v}(X',\theta_y)\,\big\|\,X\right]\right] \\ &\leq {\mathbb{E}}\left[{\widehat v}(X,\theta_x)^2\right]^{\frac{1}{2}} {\mathbb{E}}\left[{\mathbb{E}}\left[{\widehat v}(X',\theta_y)\,\big\|\,X\right]^2\right]^{\frac{1}{2}} \\ &\leq (1-g) {\mathbb{E}}\left[{\widehat v}(X,\theta_x)^2\right]^{\frac{1}{2}} {\mathbb{E}}\left[{\widehat v}(X,\theta_y)^2\right]^{\frac{1}{2}} \\ &= (1-g) (\theta_x^{\top}{\widehat{\Sigma}}_0\theta_x)^{\frac{1}{2}} (\theta_y^{\top}{\widehat{\Sigma}}_0\theta_y)^{\frac{1}{2}} \\ &= (1-g) |x||y| =1-g, \end{align}\] which implies Inequality ?? . Using this, Inequality ?? is straightforward. Finally, the proofs of the remaining inequalities are similar as the ones of their counterparts from Lemma 11. ◻