Skip to yearly menu bar Skip to main content


Optimal Comparator Adaptive Online Learning with Switching Cost

Zhiyu Zhang · Ashok Cutkosky · Yannis Paschalidis

Hall J (level 1) #1036

Keywords: [ adaptive online learning ] [ switching cost ] [ parameter-free online learning ]


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.

Chat is not available.