Multitask Online Mirror Descent
This provides an incremental improvement for multitask online learning algorithms, benefiting scenarios with similar tasks by reducing regret.
The paper tackles the problem of multitask online learning by introducing MT-OMD, a method that shares updates between tasks, and proves it achieves a regret bound of √(1 + σ²(N-1))√T, improving upon independent methods when tasks are similar (σ² ≤ 1).
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 $\sqrt{1 + σ^2(N-1)}\sqrt{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 \le 1$, our method improves upon the $\sqrt{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.