Learning Under Delayed Feedback: Implicitly Adapting to Gradient Delays

Abstract

We consider stochastic convex optimization problems, where several machines act asynchronously in parallel while sharing a common memory. We propose a robust training method for the constrained setting and derive non asymptotic convergence guarantees that do not depend on prior knowledge of update delays, objective smoothness, and gradient variance. Conversely, existing methods for this setting crucially rely on this prior knowledge, which render them unsuitable for essentially all shared-resources computational environments, such as clouds and data centers. Concretely, existing approaches are unable to accommodate changes in the delays which result from dynamic allocation of the machines, while our method implicitly adapts to such changes.

arXiv commentto be published in ICML 2021

References in corpus (10)

• Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms
• Optimal Distributed Online Prediction using Mini-Batches
• Asynchronous Stochastic Gradient Descent with Delay Compensation
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• Accelerated Mini-Batch Stochastic Dual Coordinate Ascent
• Improved asynchronous parallel optimization analysis for stochastic incremental methods
• Distributed Mini-Batch SDCA
• A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
• AdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization
• UniXGrad: A Universal, Adaptive Algorithm with Optimal Guarantees for Constrained Optimization