Optimal Comparator Adaptive Online Learning with Switching Cost
This addresses a key trade-off in adaptive online learning for practical applications like sequential investment, though it is incremental in refining existing bounds.
The paper tackles the problem of online learning with switching costs on unconstrained domains, achieving an optimal comparator adaptive regret bound that improves upon prior work.
Practical online learning tasks are often naturally defined on unconstrained domains, where optimal algorithms for general convex losses are characterized by the notion of comparator adaptivity. In this paper, we design such algorithms in the presence of switching cost - the latter penalizes the typical optimism in adaptive algorithms, leading to a delicate design trade-off. Based on a novel dual space scaling strategy discovered by a continuous-time analysis, we propose a simple algorithm that improves the existing comparator adaptive regret bound [ZCP22a] to the optimal rate. The obtained benefits are further extended to the expert setting, and the practicality of the proposed algorithm is demonstrated through a sequential investment task.