Online to Offline Conversions, Universality and Adaptive Minibatch Sizes
We present an approach towards convex optimization that relies on a novel scheme which converts adaptive online algorithms into offline methods. In the offline optimization setting, our derived methods are shown to obtain favourable adaptive guarantees which depend on the harmonic sum of the queried gradients. We further show that our methods implicitly adapt to the objective's structure: in the smooth case fast convergence rates are ensured without any prior knowledge of the smoothness parameter, while still maintaining guarantees in the non-smooth setting. Our approach has a natural extension to the stochastic setting, resulting in a lazy version of SGD (stochastic GD), where minibathces are chosen adaptively depending on the magnitude of the gradients. Thus providing a principled approach towards choosing minibatch sizes.
This paper considers two striking problems in optimizing empirical loss in learning problems: adaptively choosing step size in offline optimization, and mini-batch size in stochastic optimizations. 
With a black-box reduction to into AdaGrad algorithm and utilizing gradient normalization and importance weighting in averaging the intermediate solutions, this paper presents a variant of AdaGrad algorithm that attains same convergence rates as GD in convex and smooth optimization without the knowledge of smoothness parameter in setting the learning rate or any linear search (except strongly convex setting, where the algorithm still needs to know the strong convexity parameter H). In stochastic setting, the paper presents a LazySGD algorithm that adaptively chooses the mini-batch size according to the norm of sampled gradients.  The paper is reasonably well written, and the structure and language are good. The paper is technically sound and the proofs seem to be correct as far as I checked. The authors also included some preliminary experiments on a toy example to demonstrates some their theoretical insights. Overall, the paper is well written and has some nice contributions.