Our results in Theorem REF  and Corollary REF 
can be interpreted as follows. As long as gradient staleness \(\tau \le \mathcal {O}\big (m^{1/4}\big ),\) 
then the expected regret \(\mathbb {E}[R(T)]\le \mathcal {O}\big (\sqrt{m}\big )\) 
and the convergence rate \(\mathbb {E}\big [G(T)\big ]\le \mathcal {O}\big (1/\sqrt{m}\big )\) .
These are the optimal achievable bounds for each metric. We highlight
that in AMB-DG, we can control the gradient staleness by choosing
the appropriate fixed computation time, \(T_{p}\) . Since in AMB-DG
\(\tau =\lceil T_{c}/T_{p}\rceil \) , if we choose \(T_{p}\)  such that
\(\lceil T_{c}/T_{p}\rceil \le \mathcal {O}\big (m^{1/4}\big )\) , we can
guarantee \(\tau \le \mathcal {O}(m^{1/4})\) . Unlike other existing schemes
such as those in [1]}, [2]}, the gradient staleness
does not depend on the number of workers. It only depends on the ratio
of \(T_{c}\)  to \(T_{p}\) . Hence, AMB-DG can scale to larger cluster
sizes without experiencing the performance degradation that can result
from larger staleness due to larger cluster.
