Distributed Proximal Gradient Algorithm for Partially Asynchronous Computer Clusters

With ever growing data volume and model size, an error-tolerant, communication efficient, yet versatile distributed algorithm has become vital for the success of many large-scale machine learning applications. In this work we propose m-PAPG, an implementation of the flexible proximal gradient algorithm in model parallel systems equipped with the partially asynchronous communication protocol. The worker machines communicate asynchronously with a controlled staleness bound $s$ and operate at different frequencies. We characterize various convergence properties of m-PAPG: 1) Under a general non-smooth and non-convex setting, we prove that every limit point of the sequence generated by m-PAPG is a critical point of the objective function; 2) Under an error bound condition of convex objective functions, we prove that the optimality gap decays linearly for every $s$ steps; 3) Under the Kurdyka-Łojasiewicz inequality and a sufficient decrease assumption, we prove that the sequences generated by m-PAPG converge to the same critical point, provided that a proximal Lipschitz condition is satisfied. [abs] [ pdf ][ bib ] &copy JMLR 2018. ( edit, beta )

Authors

• Yi Zhou Southeast University Key Laboratory of New Generation Artificial Intelligence Technology and Its Interdisciplinary Applications, Ministry of Education, China
• Yingbin Liang The Ohio State University
• Yaoliang Yu University of Waterloo Vector Institute
• Wei Dai The Chinese University of Hong Kong, Shenzhen
• Eric P. Xing

Keywords

No keywords are indexed for this paper.