Abstract-We analyze the convergence of gradient-based optimization algorithms that base their updates on delayed stochastic gradient information. The main application of our results is to gradient-based distributed optimization 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. We take motivation from statistical problems where the size of the data is so large that it cannot fit on one computer; with the advent of huge datasets in biology, astronomy, and the internet, such problems are now common. Our main contribution is to show that for smooth stochastic problems, the delays are asymptotically negligible and we can achieve order-optimal convergence results. We show n-node architectures whose optimization error in stochastic problems-in spite of asynchronous delays-scales asymptotically as O(1/ √ nT ) after T iterations. This rate is known to be optimal for a distributed system with n nodes even in the absence of delays. We additionally complement our theoretical results with numerical experiments on a logistic regression task. We focus on stochastic convex optimization problems of the form min x∈X f (x) for where X ⊆ R d is a closed convex set, P is a probability distribution over Ξ, and F (· ; ξ) is convex for all ξ ∈ Ξ, so that f is convex. Classical stochastic gradient algorithms [7, 6] iteratively update a parameter x(t) ∈ X by sampling ξ ∼ P , computing g(t) = ∇F (x(t); ξ), and performing the update x(t + 1) = Π X (x(t) − α(t)g(t)), where Π X denotes projection onto the set X and α(t) ∈ R is a stepsize. In this paper, we analyze asynchronous gradient methods, where instead of receiving current information g(t), the procedure receives out of date gradients g(t − τ (t)) = ∇F (x(t − τ (t)), ξ), where τ (t) is the (potentially random) delay at time t. The central contribution of this paper is to develop algorithms that-under natural assumptions about the functions F in the objective (1)-achieve asymptotically optimal convergence rates for stochastic convex optimization despite delays. Our model of delayed gradient information is particularly relevant in distributed optimization scenarios, where a master maintains the parameters x while workers compute stochastic gradients of the objective (1) using a local subset of the data.  gn(t − 1) Fig. 1 . Cyclic delayed architecture. Workers compute gradients in parallel, passing out-of-date (stochastic) gradients g i (t − τ ) = ∇f i (x(t − τ )) to master. Master responds with current parameters. Diagram shows parameters and gradients communicated between rounds t and t + n − 1.
Similar to us, Agarwal et al. REF describe and analyse a gradient-based optimization algorithm based on delayed stochastic gradient information.
Distributed delayed stochastic optimization
2012 IEEE 51st IEEE Conference on Decision and Control (CDC)
2012 IEEE 51st IEEE Conference on Decision and Control (CDC)
Mathematics Computer Science