The Lazy Online Subgradient Algorithm is Universal on Strongly Convex Domains

We study Online Lazy Gradient Descent for optimisation on a strongly convex domain. The algorithm is known to achieve O( √ N ) regret against adversarial opponents; here we show it is universal in the sense that it also achieves O(log N ) expected regret against i.i.d opponents. This improves upon the more complex metaalgorithm of Huang et al [20] that only gets O( √ N log N ) and O(log N ) bounds. In addition we show that, unlike for the simplex, order bounds for pseudo-regret and expected regret are equivalent for strongly convex domains.