Stochastic Gradient Push and Overlap SGP (SGP and tau-OSGP for Distributed Deep Learning)

An asymmetric push-only decentralized stochastic optimization algorithm over time-varying B-strongly-connected column-stochastic mixing matrices P^{(k)} (1^T P^{(k)} = 1^T, Assran et al. 2019, Section 2, Algorithm 1) in which each worker i maintains a biased parameter vector x_i^{(k)}, a scalar PushSum weight w_i^{(k)} initialized at w_i^{(0)} = 1, and a de-biased model z_i^{(k)} = x_i^{(k)} / w_i^{(k)} at which stochastic gradients nabla F_i(z_i^{(k)}; xi_i^{(k)}) are evaluated before pushing p_{j,i}^{(k)}(x_i^{(k)} - gamma nabla F_i(z_i^{(k)}; xi_i^{(k)})) and p_{j,i}^{(k)} w_i^{(k)} to out-neighbors j, together with its tau-step communication-overlapped variant tau-Overlap SGP (tau-OSGP) that hides communication latency over up to tau gradient steps.