Chapter 5 Summary of PuSh-Pull and DSGT

In the Push-Pull method, if we set graph \(\mathcal{G}\) is connected and undirected, then \(\mathcal{G}=\mathcal{G}_R=\mathcal{G}_C\),i.e.,\(R=C:=W\). The algorithm 3.1 becomes the form of \[\begin{align} X_{k+1} &= W(X_{k}-\boldsymbol\alpha Y_k),\\ Y_{k+1} &= WY_k+\nabla F(X_{k+1})-\nabla F(X_k) \tag{3.1} \end{align}\]

If we further assume we only have noisy estimates of \(\nabla F(X)\), i.e. \(G(X,\boldsymbol\xi)\), we get DSGT 4.1.

In the proof of \(\rho(A_{pp})<1\), the spectral radius of \(A\) of the linear system of inequalities in the Push-Pull method, the authors use \(1>(1-a_{22})\geq\frac{1-\sigma_R}{2}\),and \(1>(1-a_{33})\geq\frac{1-\sigma_C}{2}\) to build a sufficient condition for \(\hat\alpha\), which avoid discussing the sign of \(c_i,i=1,2,3\) in \(c_{3}-c_{2} \hat{\alpha}-c_{1} \hat{\alpha}^{2}\).

5.1 Questions

• In two methods, the matrices \(R-\frac{\mathbf{1}u^T}{n}, C-\frac{v\mathbf{1^T}}{n}\), and \(W-\frac{\mathbf{1}\mathbf{1}^T}{n}\) and their (approximated) spectral radii seem important. How to interpretate them? Is it because the following relationships?

\[ \lim _{k \rightarrow \infty} \mathbf{R}^{k}=\frac{1 u^{\top}}{n}, \lim _{k \rightarrow \infty} C^{k}=\frac{v 1^{\top}}{n} \]

• In (4.7), \(\left\langle Y_{k+1}-\mathbf{1}\bar y_{k+1},\mathbf{1}(\bar y_k-\bar y_{k+1})\right\rangle\stackrel{?}{=}0\)

• In the following inequality, \(2n\sigma^2\) seems come from 4.1, the others? \[\begin{align} 2 \mathbb{E}\left[\left\langle\nabla_{k+1}-\nabla_{k}, G_{k+1}-\nabla_{k+1}-G_{k}+\nabla_{k}\right\rangle | \mathcal{F}_{k}\right]&+\\ &\mathbb{E}\left[\left\|G_{k+1}-\nabla_{k+1}-G_{k}+\nabla_{k}\right\|^{2} | \mathcal{F}_{k}\right]\\ &\leq 2 \mathbb{E}\left[\left\langle\nabla_{k+1},-G_{k}+\nabla_{k}\right\rangle | \mathcal{F}_{k}\right]+2 n \sigma^{2} \end{align}\]

Todo: \(E\left[\Vert Y_{k+1}-\mathbf{1}\bar y_{k+1}\Vert^2|\mathcal{F}_k\right]\leq?\)

Todo: \(\rho(A_{pp})\approx1-\alpha'\mu\),when \(\hat\alpha\) is sufficiently small