Local SGD Periodic Model Averaging Parallel Stochastic Gradient Descent

A communication-efficient parallel stochastic optimization algorithm (Local SGD) in which K workers independently advance local parameter vectors via x_{t+1}^k = x_t^k - eta_t * grad f_{i_t^k}(x_t^k) and synchronize by global averaging x_{t+1}^k = (1/K) sum_{j=1}^K (x_t^j - eta_t * grad f_{i_t^j}(x_t^j)) only at communication steps t + 1 in I_T with maximum synchronization gap gap(I_T) <= H, bounding the mean squared worker drift from the virtual average x_bar_t = (1/K) sum_{k=1}^K x_t^k by 4 * eta_t^2 * G^2 * H^2 and achieving the optimal O(sigma^2 / (mu * K * T)) linear K-worker speedup with up to H = O(sqrt(T / K)) fewer communication rounds.