Recently, we introduced a novel synchronous technique called Anytime
Minibatch (AMB) in [1]}. Our main idea was to fix the
per-epoch compute time across all workers rather than fixing the job
size as is typical. Since workers progress at different rates, fixing
the compute time results in a variable amount of work being completed
by each worker in each epoch. A drawback of AMB is that when workers
submit their results to the master, they idle while waiting to receive
back the updated optimization parameters. When this wait time is long,
the wall time convergence can be greatly prolonged. To alleviate this
deficiency, in this paper we propose Anytime Minibatch with
Delayed Gradients (AMB-DG). In AMB-DG, workers keep processing data
points and calculate gradients at all times while the master updates
the parameters using delayed gradients. We analyze the performance
of AMB-DG for a convex smooth objective function under the assumption
of fixed gradient staleness. Under these assumptions, we prove that
the expected regret bound attained is \(O(\sqrt{{m}})\)  where \(m\) 
is the number of samples observed across all nodes. This bound is
well-known to be the optimal regret bound achievable by gradient-based
methods on arbitrary convex objective functions [2]}.
We also show that under the same assumptions the expected convergence
rate (i.e., optimality gap) achieved is \(O(1/\sqrt{m})\) . Our theoretical
derivations show that asymptotically in the number of data points
observed, the impact of the fixed delay on convergence is negligible
for smooth convex loss functions. We compare the performance of AMB-DG
with that of AMB and observe that under long communication delays
AMB-DG converges faster than AMB in terms of wall clock time. We also
implement AMB-DG on the SciNet high performance computing platform
and compare the performance of AMB-DG with existing asynchronous delayed-gradient-based
methods. AMB-DG converges almost 2 times faster in our examples.
