Publication Date:
2022
Citation:
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.
(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.
IRIS type:
01 - Articolo su periodico
List of contributors:
N. Cesa Bianchi, P. Laforgue, A. Paudice, M. Pontil
Link to information sheet:
Full Text: