Skip to contentSkip to filters

We use cookies for analytics.

The Role of Curvature in Non-stationary Online Learning

Yu-Jie Zhang

University of Washington

Abstract

Online learning makes decisions sequentially and improves them from incoming feedback, and curvature of the loss is known to enable much faster learning when the goal is to compete with the best fixed decision. Yu-Jie Zhang asks what happens when the best decision changes over time. With bounded gradients, curvature can accelerate learning on arbitrary bounded convex domains without the out-of-domain predictions earlier studies required; when gradients can be unbounded, as in classical online portfolio selection, faster rates depend critically on the geometric structure of the changing comparators, in particular their position relative to the boundary. The results come from a dynamic-regret analysis that introduces new mixability-based arguments to exploit loss curvature.

Topics