Parallel Momentum Methods Under Biased Gradient Estimations
This addresses the challenge of biased gradients in distributed optimization, which is incremental as it extends existing momentum methods to handle biases from compression, clipping, and other sources.
The paper tackles the problem of biased gradient estimations in parallel stochastic gradient methods for distributed machine learning, establishing worst-case convergence bounds for momentum methods on non-convex and PL problems and showing faster convergence than traditional biased gradient descent in experiments.
Parallel stochastic gradient methods are gaining prominence in solving large-scale machine learning problems that involve data distributed across multiple nodes. However, obtaining unbiased stochastic gradients, which have been the focus of most theoretical research, is challenging in many distributed machine learning applications. The gradient estimations easily become biased, for example, when gradients are compressed or clipped, when data is shuffled, and in meta-learning and reinforcement learning. In this work, we establish worst-case bounds on parallel momentum methods under biased gradient estimation on both general non-convex and $μ$-PL problems. Our analysis covers general distributed optimization problems, and we work out the implications for special cases where gradient estimates are biased, i.e. in meta-learning and when the gradients are compressed or clipped. Our numerical experiments verify our theoretical findings and show faster convergence performance of momentum methods than traditional biased gradient descent.