Sorry, you need to enable JavaScript to visit this website.

Non-Asymptotic Rates for Communication Efficient Distributed Zeroth Order Strongly Convex Optimization

Citation Author(s):
Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar
Submitted by:
Anit Kumar Sahu
Last updated:
27 November 2018 - 6:55pm
Document Type:
Presentation Slides
Document Year:
Anit Kumar Sahu
Paper Code:


This paper focuses on the problem of communication efficient distributed zeroth order minimization of a sum of strongly convex loss functions. Specifically, we develop distributed stochastic optimization methods for zeroth order strongly convex optimization that are based on an adaptive probabilistic sparsifying communications protocol. Under standard assumptions on the cost functions and the noises corrupting the function evaluations, we establish with the proposed method O(1/(Ccomm)2/3−ζ ) mean square error (MSE) convergence rates, for the zeroth order optimization, where Ccomm is the number of per-node communications and ζ > 0 is arbitrarily small. In the distributed setting considered, the established rate is the best known rate in terms of the MSE- communication cost trade off for zeroth order optimization. Finally, through empirical evaluations we illustrate the proposed algorithm’s theoretical guarantees.

0 users have voted: