Abstract 

Most online optimization algorithms focus on one of two things: performing well in adversarial settings by adapting to unknown data parameters (such as Lipschitz constants), typically achieving regret, or performing well in stochastic settings where they can leverage some structure in the losses (such as strong convexity), typically achieving regret. Algorithms that focus on the former problem hitherto achieved in the stochastic setting rather than . Here we introduce an online optimization algorithm that achieves regret in a wide class of stochastic settings while gracefully degrading to the optimal regret in adversarial settings (up to logarithmic factors). Our algorithm does not require any prior knowledge about the data or tuning of parameters to achieve superior performance.