Timezone: »

 
Poster
Parameter-free, Dynamic, and Strongly-Adaptive Online Learning
Ashok Cutkosky

Thu Jul 16 08:00 AM -- 08:45 AM & Thu Jul 16 08:00 PM -- 08:45 PM (PDT) @
in Poster Session 43 »
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 $\tilde O(\sqrt{N})$. Finally, our algorithm obtains an optimal ``dynamic'' regret bound: for any sequence of comparators with path-length $P$, our algorithm obtains regret $\tilde O(\sqrt{PN})$ 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.
Keywords: Online Learning / Bandits · Online Learning, Active Learning, and Bandits

Author Information

Ashok Cutkosky (Boston University)

More from the Same Authors