ANYTIME MINIBATCH: EXPLOITING STRAGGLERS IN ONLINE DISTRIBUTED OPTIMIZATION
Distributed optimization is vital in solving large-scale machine learning problems. A widely-shared feature of distributed optimization techniques is the requirement that all nodes complete their assigned tasks in each computational epoch before the system can proceed to the next epoch. In such settings, slow nodes, called stragglers, can greatly slow progress. To mitigate the impact of stragglers, we propose an online distributed optimization method called Anytime Minibatch. In this approach, all nodes are given a fixed time to compute the gradients of as many data samples as possible. The result is a variable per-node minibatch size. Workers then get a fixed communication time to average their minibatch gradients via several rounds of consensus, which are then used to update primal variables via dual averaging. Anytime Minibatch prevents stragglers from holding up the system without wasting the work that stragglers can complete. We present a convergence analysis and analyze the wall time performance. Our numerical results show that our approach is up to 1.5 times faster in Amazon EC2 and it is up to five times faster when there is greater variability in compute node performance.
Summary:
The paper considers the problem of online stochastic convex optimization in a fully distributed topology. In particular, the authors focus on the synchronous setting and to avoid the slow progress that can be obtained by slow nodes, called stragglers, they propose an online distributed optimization method called Anytime Minibatch (AMB). In the update of AMB rather than fixing the minibatch size, they fix the computation time in each epoch. This characteristic prevents the stragglers from holding up the entire network, while allowing nodes to benefit from the partial work carried out by the slower nodes. 
A convergence analysis of AMB is provided showing that the online regret achieves the optimum performance. Numerical evaluations where a comparison of AMB and the "Fixed MiniBatch" method (FMB)are also presented.
Comments:
I believe that the idea of the paper is interesting and the convergence analysis seems correct, however i have some concerns regarding  the presentation and the numerical evaluation. 
1) In the title the word "online" is mentioned but never explained  in the main text. What is this mean? What are the differences compare to the "static" setting? See for example the work of [Tsianos, Rabbat (2016)] for more details on that. What are the related literature on this setting?
2) In the last paragraph of Introduction is highlighted that the algorithm AMB has the optimum performance?  The authors should add an appropriate reference there and explain why this is optimum for their setting. I believe that for the convenience of the reader current Section 5 called "previous work" can move immediately after introduction and more details of AMB with the existing literature should be provided. Probably rename the section "Closely relate work".
3) Section 2 is devoted mostly on the formal presentation of algorithm AMB. I strongly suggest the addition of a pseudocode of the algorithm in the appendix (or even in the main text if there is a space) where the reader can easily understand how the algorithm works.
4) On the Algorithm:  if some nodes are very slow and they do not make any update during the given time T what will happen? How this will affect the performance of the method? In this case does it make sense to increase the value of T.
5) On numerical evaluation:  A comparison of AMB and FMB  is presented both in synthetic and real data showing that AMB can be faster than FMB in terms of wall clock time. 
I am not sure if the performance of the AMB is as good as one should expect especially for the case of synthetic data. Will it be possible to construct a synthetic example with extremely slow nodes where the improvement of the performance is much better than 50%?
In general i find the paper interesting, with nice ideas and I believe that will be appreciated from researchers that are interested on control theory/signal processing and information theory.  Since the paper is focused on convex optimization I am not sure if it will be particularly interesting for a substantial fraction of the ICLR attendees.