Cesa-Bianchi, Nicolò;
Laforgue, Pierre;
Paudice, Andrea;
Pontil, Massimiliano;
(2022)
Multitask Online Mirror Descent.
Transactions on Machine Learning Research
, 2022
(9)
, Article 198.
Preview |
Text
198_multitask_online_mirror_descen.pdf - Published Version Download (660kB) | Preview |
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 √1+o²(N-1) √T, where o² 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 o² ≤ 1, our method improves upon the √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.
| Type: | Article |
|---|---|
| Title: | Multitask Online Mirror Descent |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://openreview.net/forum?id=zwRX9kkKzj |
| Language: | English |
| Additional information: | © The Author(s), 2024. This is an Open Access article distributed under the terms of the Creative Commons Attribution Licence (CC BY 4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. https://creativecommons.org/licenses/by/4.0/ |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10191482 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
