Non-asymptotic rates for communication efficient distributed zeroth order strongly convex optimization

Authors Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar
Title Non-asymptotic rates for communication efficient distributed zeroth order strongly convex optimization
Abstract 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/(C comm ) 2 / 3-ζ ) mean square error (MSE) convergence rates, for the zeroth order optimization, where C comm 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.
ISBN 978-1-7281-1295-4
Conference 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP)
Date 26 - 29 November, 2018
Location Anaheim, CA, USA
Url https://zenodo.org/record/3333576#.XZMbw0YzYuV
DOI https://doi.org/10.1109/GlobalSIP.2018.8646406