Understanding the Bias of Markov Chain SGD with Intermittent Node Availability

This paper studies stochastic gradient descent when the sampling process follows a Markov chain (Markov chain SGD). Specifically, we consider a token-based setting for distributed learning, where a token carrying the shared model moves sequentially among the nodes according to a Markov chain, and the node holding the token performs one gradient update. In practical distributed systems, nodes may be intermittently unavailable because of resource constraints. We analyze the convergence of Markov chain SGD with intermittent node availability. The derived upper and lower bounds of convergence rates show that different node availability rates can cause a non-vanishing optimization bias with respect to the intended objective, and that correction weights can correct for the bias at the cost of slower convergence. Experiments on quadratic functions and neural networks support our theoretical findings.