On Convergence of Model Parallel Proximal Gradient Algorithm for Stale Synchronous Parallel System
Yi Zhou, Yaoliang Yu, Wei Dai, Yingbin Liang, Eric P. Xing · International Conference on Artificial Intelligence and Statistics · 2016
Theorem 1 (Asymptotic consistency). Let Assumption 1 and 2 hold, and apply msPG to problem (P). If the step size η < (Lf + 2Ls) −1, then the global model and local models satisfy: 1. ∑∞ t=0 ‖x(t+ 1)− x(t)‖ <∞; 2. lim t→∞ ‖x(t+ 1)− x(t)‖ = 0, lim t→∞ ‖x(t)− x(t)‖ = 0; 3. The limit points ω({x(t)}) = ω({x(t)}) ⊆ critF . Proof. We start from bounding the difference between the global model x and the local model x (on any machine i). Indeed, at iteration t, by the definition of the global and local models in msPG: ‖x(t)− x(t)‖ = √√√√ p ∑