Research map / Bandits and online learning / Online convex optimization and games
Online Convex Optimisation: The Optimal Switching Regret for all Segmentations Simultaneously
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes RESET, a parameter-free meta-algorithm that wraps any online convex optimisation base learner to achieve asymptotically optimal switching regret and adaptive dynamic regret simultaneously over all segmentations, with logarithmic per-trial time and space.
Problem
Online convex optimisation in non-stationary environments, where static regret is insufficient; the goal is to bound switching regret against any segmentation of the trial sequence (and dynamic regret against any comparator) optimally and efficiently without knowing the segmentation.
Approach
RESET stacks log2(T)+1 levels of base-algorithm instances restarted at dyadic intervals, combining their actions via mixing weights updated with Hedge-style exponential weights on two-expert losses. This yields switching regret O(sum_k sqrt(|I_k|)) for every segmentation simultaneously, removing the sqrt(ln T) factor of prior tracking methods, and dynamic regret O(sum_I sqrt((1+P(E,I))|I|)).
Key results
- RESET achieves switching regret O(sum_k sqrt(|I_k|)) for every segmentation simultaneously, matching the lower bound up to constants (theorem 2.2).
- Applied to Hedge, RESET gives optimal switching regret O(sum_k min(Λ_k, sqrt(ln(N) Λ_k))) for prediction with expert advice.
- Dynamic regret O(sum_I sqrt((1+P(E,I))|I|)) improves on ADER's O(sqrt((1+P)T)) and per-trial time and space are O(ln T) times the base algorithm's cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RESET with online gradient descent instead of the prior ADER bound | Online convex optimisation · Dynamic regret, any comparator sequence and segmentation | dynamic regret: O(√((1 + P)T)) -> O(∑ₖ √((1 + Pₖ)Λₖ)) | Helped |
| Use RESET to track all segmentations simultaneously instead of prior tracking algorithms | Online convex optimisation · Any segmentation | switching regret: O(∑ₖ √(Λₖ ln(T))) -> O(∑ₖ √Λₖ) | Helped |
| Use RESET with Hedge as the base algorithm | Prediction with expert advice · Any segmentation | switching regret: O(∑ₖ min(Λₖ, √(ln(N)Λₖ))) | Helped |
| Apply RESET using a base algorithm with per-trial time ξ and space ξ′ | Online convex optimisation · Online execution | per-trial time complexity: O(ξ ln(T)) | Helped |
Surprising findings
- Optimal switching regret for all segmentations simultaneously is achieved without the extra sqrt(ln T) factor that prior tracking algorithms incurred.
Limitations
- Dynamic regret bound holds only when online gradient descent is the base algorithm; the optimal switching bound uses any base algorithm.
- Purely theoretical; no experiments are reported.
- Not strongly adaptive: static regret on individual segments is not bounded.
Experimental setup
Metrics: switching regret dynamic regret space complexity per-trial time complexity
Baselines: SAOL ADER Fixed share online gradient descent
Builds on: online gradient descent Hedge mirror descent strongly adaptive online learner (SAOL) ADER
Closest papers by meaning
- Logarithmic Switching Regret for Online Convex Optimization (ICML 2026 · similarity 0.91)
- Dynamic Regret in Online Convex Optimization with Indicator Switching Costs (NeurIPS 2026 · similarity 0.91)
- An Equivalence Between Static and Dynamic Regret Minimization (NeurIPS 2024 · similarity 0.90)
- Dynamic Regret Reduces to Kernelized Static Regret (NeurIPS 2025 · similarity 0.89)
- On the Dynamic Regret of Following the Regularized Leader: Optimism with History Pruning (ICML 2025 · similarity 0.88)
- Small-loss Adaptive Regret for Online Convex Optimization (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.