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

facebooktwittermailshare

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/(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.

up
0 users have voted:

Paper Details

Authors:
Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar
Submitted On:
27 November 2018 - 6:55pm
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Anit Kumar Sahu
Paper Code:
1223
Document Year:
2018
Cite

Document Files

globalsip_talk.pdf

(52)

Subscribe

[1] Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar, "Non-Asymptotic Rates for Communication Efficient Distributed Zeroth Order Strongly Convex Optimization", IEEE SigPort, 2018. [Online]. Available: http://sigport.org/3818. Accessed: May. 25, 2019.
@article{3818-18,
url = {http://sigport.org/3818},
author = {Anit Kumar Sahu; Dusan Jakovetic; Dragana Bajovic; Soummya Kar },
publisher = {IEEE SigPort},
title = {Non-Asymptotic Rates for Communication Efficient Distributed Zeroth Order Strongly Convex Optimization},
year = {2018} }
TY - EJOUR
T1 - Non-Asymptotic Rates for Communication Efficient Distributed Zeroth Order Strongly Convex Optimization
AU - Anit Kumar Sahu; Dusan Jakovetic; Dragana Bajovic; Soummya Kar
PY - 2018
PB - IEEE SigPort
UR - http://sigport.org/3818
ER -
Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar. (2018). Non-Asymptotic Rates for Communication Efficient Distributed Zeroth Order Strongly Convex Optimization. IEEE SigPort. http://sigport.org/3818
Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar, 2018. Non-Asymptotic Rates for Communication Efficient Distributed Zeroth Order Strongly Convex Optimization. Available at: http://sigport.org/3818.
Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar. (2018). "Non-Asymptotic Rates for Communication Efficient Distributed Zeroth Order Strongly Convex Optimization." Web.
1. Anit Kumar Sahu, Dusan Jakovetic, Dragana Bajovic, Soummya Kar. Non-Asymptotic Rates for Communication Efficient Distributed Zeroth Order Strongly Convex Optimization [Internet]. IEEE SigPort; 2018. Available from : http://sigport.org/3818