Online to Offline Conversions, Universality and Adaptive Minibatch Sizes
This work addresses optimization efficiency for machine learning practitioners by offering adaptive methods that improve convergence rates without requiring parameter tuning, though it is incremental in building on existing online-to-offline conversion ideas.
The paper tackles convex optimization by converting online adaptive algorithms into offline methods, achieving adaptive guarantees based on the harmonic sum of gradients and implicitly adapting to the objective's smoothness without prior knowledge. It extends to stochastic settings with adaptive minibatch sizes, providing a principled approach for choosing them.
We present an approach towards convex optimization that relies on a novel scheme which converts online adaptive 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 \emph{adaptively} depending on the magnitude of the gradients. Thus providing a principled approach towards choosing minibatch sizes.