Optimal Comparator Adaptive Online Learning with Switching Cost. (arXiv:2205.06846v3 [cs.LG] UPDATED)

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 …

arxiv cost online learning