Parameter-free, dynamic, and strongly-adaptive online learning
MetadataShow full item record
Citation (published version)Ashok Cutkosky. 2020. "Parameter-free, Dynamic, and Strongly-Adaptive Online Learning." International Conference on Machine Learning
We provide a new online learning algorithm that for the first time combines several disparate notions of adaptivity. First, our algorithm obtains a “parameter-free” regret bound that adapts to the norm of the comparator and the squared norm of the size of the gradients it observes. Second, it obtains a “strongly-adaptive” regret bound, so that for any given interval of length N, the regret over the interval is Õ (√N). Finally, our algorithm obtains an optimal “dynamic” regret bound: for any sequence of comparators with path-length P, our algorithm obtains regret Õ (√𝑃𝑁) over intervals of length N. Our primary technique for achieving these goals is a new method of combining constrained online learning regret bounds that does not rely on an expert meta-algorithm to aggregate learners.
RightsCopyright © The authors and PMLR 2021. MLResearchPress.