The convergence rate of the method is given by the following formula, for every ''i'':<ref name=":0" />{{Rp|___location=Prop.4.4.1}}<blockquote><math>c^T x_i - c^* \leq \frac{X2 M}{t_0} \left[1 + \frac{r}{\sqrt{M}}\right]^{-i} </math>, where <math>X = M+\frac{L}{1-L}\sqrt{M} </math></blockquote>The number of Newton steps required to go from ''x<sub>i</sub>'' to ''x<sub>i</sub>''<sub>+1</sub> is at most a fixed number, that depends only on ''r'' and ''L''. In particular, the total number of Newton steps required to find an ''ε''-approximate solution (i.e., finding ''x'' in ''G'' such that ''c''<sup>T</sup>''x'' - c* ≤ ''ε'') is at most:<ref name=":0" />{{Under constructionRp|placedby___location=ErelThm.4.4.1}}<blockquote><math>O(1) Segal\cdot \sqrt{M} \cdot \ln\left(\frac{M}{t_0 \varepsilon} + 1\right) </math></blockquote>where the constant factor O(1) depends only on ''r'' and ''L''.
