Data di Pubblicazione:
2022
Citazione:
Multitask Online Mirror Descent / N. Cesa Bianchi, P. Laforgue, A. Paudice, M. Pontil. - In: TRANSACTIONS ON MACHINE LEARNING RESEARCH. - ISSN 2835-8856. - 2022:9(2022 Sep), pp. 1-30.
Abstract:
We introduce and analyze MT-OMD, a multitask generalization of Online Mirror Descent
(OMD) which operates by sharing updates between tasks. We prove that the regret of
MT-OMD is of order
p
1 + 2(N − 1)p
T, where 2 is the task variance according to the
geometry induced by the regularizer, N is the number of tasks, and T is the time horizon.
Whenever tasks are similar, that is 2 1, our method improves upon the p
NT bound
obtained by running independent OMDs on each task. We further provide a matching
lower bound, and show that our multitask extensions of Online Gradient Descent and
Exponentiated Gradient, two major instances of OMD, enjoy closed-form updates, making
them easy to use in practice. Finally, we present experiments which support our theoretical
findings.
Tipologia IRIS:
01 - Articolo su periodico
Elenco autori:
N. Cesa Bianchi, P. Laforgue, A. Paudice, M. Pontil
Link alla scheda completa:
Link al Full Text: