AsySVRG Lock-free Analysis In all the GD or SGD methods to solve the objective function,the key step can be written as u←-u+△ Notation Aij:thejth update vector computed by the iththread; 。u E Rd and u=(u),u(②)，，ud)i 。ty:the time when the operation"←u+△has been completed(Not the time when the operation begins); Assuming i,j.which can be easily guaranteed by programming 4口，4@下424，分QC Wu-Jun Li (http://cs.nju.edu.cn/lwj) PDSL CS.NJU 11 /36
AsySVRG Lock-free Analysis In all the GD or SGD methods to solve the objective function, the key step can be written as u ← u + ∆ Notation ∆i,j : the j th update vector computed by the i th thread; u ∈ R d and u = (u (1), u(2), . . . , u(d) ); t (k) i,j : the time when the operation “u (k) ← u (k) + ∆(k) i,j ” has been completed (Not the time when the operation begins); Assuming ∀i, j, t (1) i,j < t(2) i,j < . . . < t(d) i,j , which can be easily guaranteed by programming Wu-Jun Li (http://cs.nju.edu.cn/lwj) PDSL CS, NJU 11 / 36
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 /36
AsySVRG 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