Near-optimal Swap Regret Minimization for Convex Losses
arXiv:2602.08862v1 Announce Type: cross Abstract: We give a randomized online algorithm that guarantees near-optimal $widetilde O(sqrt T)$ expected swap regret against any sequence of $T$ adaptively chosen Lipschitz convex losses on the unit interval. This improves the previous best bound of $widetilde O(T^{2/3})$ and answers an open question of Fishelson et al. [2025b]. In addition, our algorithm is efficient: it runs in $mathsf{poly}(T)$ time. A key technical idea we develop to obtain this result is to discretize the […]