Paper ID: 2405.20824 • Published May 31, 2024
Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
Stephen Pasteris, Chris Hicks, Vasilios Mavroudis, Mark Herbster
TL;DR
Get AI-generated summaries with premium
Get AI-generated summaries with premium
We consider the classic problem of online convex optimisation. Whereas the
notion of static regret is relevant for stationary problems, the notion of
switching regret is more appropriate for non-stationary problems. A switching
regret is defined relative to any segmentation of the trial sequence, and is
equal to the sum of the static regrets of each segment. In this paper we show
that, perhaps surprisingly, we can achieve the asymptotically optimal switching
regret on every possible segmentation simultaneously. Our algorithm for doing
so is very efficient: having a space and per-trial time complexity that is
logarithmic in the time-horizon. Our algorithm also obtains novel bounds on its
dynamic regret: being adaptive to variations in the rate of change of the
comparator sequence.