Distributed Delayed Stochastic Optimization
We analyze the convergence of gradient-based optimization algorithms whose updates depend on delayed stochastic gradient information. The main application of our results is to the development of distributed minimization algorithms where a master node performs parameter updates while worker nodes compute stochastic gradients based on local information in parallel, which may give rise to delays due to asynchrony. Our main contribution is to show that for smooth stochastic problems, the delays are asymptotically negligible. In application to distributed optimization, we show $n$-node architectures whose optimization error in stochastic problems---in spite of asynchronous delays---scales asymptotically as $\order(1 / \sqrt{nT})$, which is known to be optimal even in the absence of delays.
Code (0)
등록된 구현이 없습니다.
Tasks
Distributed OptimizationStochastic OptimizationSimilar Papers 제목 키워드 기반
Delayed Algorithms for Distributed Stochastic Weakly Convex Optimization
This paper studies delayed stochastic algorithms for weakly convex optimization in a distributed network with workers connected to a master node. Recently, Xu~et~al.~2022 showed that an inertial stochastic subgradient …
A Tight Convergence Analysis for Stochastic Gradient Descent with Delayed Updates
We provide tight finite-time convergence bounds for gradient descent and stochastic gradient descent on quadratic functions, when the gradients are delayed and reflect iterates from $\tau$ rounds ago. First, we show that…
Distributed OptimizationDelayed Projection Techniques for Linearly Constrained Problems: Convergence Rates, Acceleration, and Applications
In this work, we study a novel class of projection-based algorithms for linearly constrained problems (LCPs) which have a lot of applications in statistics, optimization, and machine learning. Conventional primal gradien…
Distributed OptimizationPrivacy PreservingAdaDelay: Delay Adaptive Distributed Stochastic Convex Optimization
We study distributed stochastic convex optimization under the delayed gradient model where the server nodes perform parameter updates, while the worker nodes compute stochastic gradients. We discuss, analyze, and experim…
Convex and Non-convex Federated Learning with Stale Stochastic Gradients: Diminishing Step Size is All You Need
We propose a general framework for distributed stochastic optimization under delayed gradient models. In this setting, $n$ local agents leverage their own data and computation to assist a central server in minimizing a g…
Stochastic OptimizationFederated Learning