Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909526043656192 |
|---|---|
| author | Pasteris, Stephen Hicks, Chris Mavroudis, Vasilios Herbster, Mark |
| author_facet | Pasteris, Stephen Hicks, Chris Mavroudis, Vasilios Herbster, Mark |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_20824 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously Pasteris, Stephen Hicks, Chris Mavroudis, Vasilios Herbster, Mark Machine Learning 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. |
| title | Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2405.20824 |