Timezone: »

Stochastic and Adversarial Online Learning without Hyperparameters
Ashok Cutkosky · Kwabena A Boahen

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #53 #None
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 $O(\sqrt{T})$ regret, or performing well in stochastic settings where they can leverage some structure in the losses (such as strong convexity), typically achieving $O(\log(T))$ regret. Algorithms that focus on the former problem hitherto achieved $O(\sqrt{T})$ in the stochastic setting rather than $O(\log(T))$. Here we introduce an online optimization algorithm that achieves $O(\log^4(T))$ regret in a wide class of stochastic settings while gracefully degrading to the optimal $O(\sqrt{T})$ 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.

Author Information

Ashok Cutkosky (Google)
Kwabena A Boahen (Stanford University)

More from the Same Authors