Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
作者： Angelia Nedic , Alex Olshevsky
DOI:
关键词: Conic optimization 、 Convex analysis 、 Subderivative 、 Discrete mathematics 、 Drift plus penalty 、 Convex combination 、 Convex function 、 Combinatorics 、 Proper convex function 、 Convex optimization 、 Mathematics
摘要: We investigate the convergence rate of recently proposed subgradient-push method for distributed optimization over time-varying directed graphs. The can be implemented in a way without requiring knowledge either number agents or graph sequence; each node is only required to know its out-degree at time. Our main result $O \left((\ln t)/t \right)$ strongly convex functions with Lipschitz gradients even if stochastic gradient samples are available; this asymptotically faster than t)/\sqrt{t} previously known (general) functions.
arxiv.org参考文章(35)
Björn Johansson, On Distributed Optimization in Networked Systems KTH. ,(2008)
Michael G. Rabbat, Konstantinos I. Tsianos, Simple iteration-optimal distributed optimization european signal processing conference. pp. 1- 5 ,(2013)
Bo Yang, Mikael Johansson, Distributed Optimization and Games: A Tutorial Overview Lecture Notes in Control and Information Sciences. ,vol. 406, pp. 109- 148 ,(2010) , 10.1007/978-0-85729-033-5_4
Angelia Nedić, Asuman E. Ozdaglar, Dimitri P. Bertsekas, Convex Analysis and Optimization ,(2003)
John N. Tsitsiklis, Dimitri P. Bertsekas, Parallel and Distributed Computation: Numerical Methods ,(1989)
Bahman Gharesifard, Behrouz Touri, Tamer Basar, Cedric Langbort, Distributed optimization by myopic strategic interactions and the price of heterogeneity conference on decision and control. pp. 1174- 1179 ,(2013) , 10.1109/CDC.2013.6760041
Alejandro D. Dominguez-Garcia, Christoforos N. Hadjicostis, Distributed Matrix Scaling and Application to Average Consensus in Directed Graphs IEEE Transactions on Automatic Control. ,vol. 58, pp. 667- 681 ,(2013) , 10.1109/TAC.2012.2219953
Husheng Li, Zhu Han, Competitive Spectrum Access in Cognitive Radio Networks: Graphical Game and Learning wireless communications and networking conference. pp. 1- 6 ,(2010) , 10.1109/WCNC.2010.5506285
Alejandro D. Dominguez-Garcia, Christoforos N. Hadjicostis, Distributed strategies for average consensus in directed graphs conference on decision and control. pp. 2124- 2129 ,(2011) , 10.1109/CDC.2011.6160462
Angelia Nedić, Soomin Lee, On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averaging Siam Journal on Optimization. ,vol. 24, pp. 84- 107 ,(2014) , 10.1137/120894464