A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent
This addresses robustness in distributed learning systems, but it is incremental as it adapts existing mirror descent ideas to a new corruption scenario.
The paper tackles the problem of adversarial corruptions in distributed gradient descent by designing a mirror descent-based algorithm, achieving convergence for strongly convex losses with optimized stepsize schedules.
Distributed gradient descent algorithms have come to the fore in modern machine learning, especially in parallelizing the handling of large datasets that are distributed across several workers. However, scant attention has been paid to analyzing the behavior of distributed gradient descent algorithms in the presence of adversarial corruptions instead of random noise. In this paper, we formulate a novel problem in which adversarial corruptions are present in a distributed learning system. We show how to use ideas from (lazy) mirror descent to design a corruption-tolerant distributed optimization algorithm. Extensive convergence analysis for (strongly) convex loss functions is provided for different choices of the stepsize. We carefully optimize the stepsize schedule to accelerate the convergence of the algorithm, while at the same time amortizing the effect of the corruption over time. Experiments based on linear regression, support vector classification, and softmax classification on the MNIST dataset corroborate our theoretical findings.