AsySVRG Lock-free Analysis:update sequence Since u(1)can only be changed by at most one thread at any absolute time,theseare different from eachother.So we can: 。Sort these号as8<t<.<t得1(W=p×M: 。△o,△l,,△M-n are the corresponding update vectors.. Since it is lock-free,for each update vector Am,the real update vector is BmAm because of over-written.The Bm is a diagonal matrix whose diagonal elements are 0 or 1. After all the inner-loop stop,we can get: M-1 w+1=u0+∑Bm△nm (1) m=0 4口，4@，4242，定分Q0 Wu-Jun Li (http://cs.nju.edu.cn/lwj) PDSL CS.NJU 12 /36AsySVRG Lock-free Analysis: update sequence Since u (1) can only be changed by at most one thread at any absolute time, these t (1) i,j are different from each other. So we can: Sort these t (1) i,j as t (1) 0 < t(1) 1 < . . . < t(1) M˜ −1 (M˜ = p × M); ∆0, ∆1, . . . , ∆M˜ −1 are the corresponding update vectors. Since it is lock-free, for each update vector ∆m, the real update vector is Bm∆m because of over-written. The Bm is a diagonal matrix whose diagonal elements are 0 or 1. After all the inner-loop stop, we can get: wt+1 = u0 + M X˜ −1 m=0 Bm∆m (1) Wu-Jun Li (http://cs.nju.edu.cn/lwj) PDSL CS, NJU 12 / 36