AdaTask: Adaptive Multitask Online Learning
This work addresses the challenge of efficient learning across multiple tasks in online settings, offering a significant theoretical improvement for scenarios with stochastically activated tasks.
The paper tackles the problem of multitask online learning with unknown task structure by introducing AdaTask, an algorithm that adapts to this structure and achieves a regret improvement of up to √N compared to running independent algorithms per task.
We introduce and analyze AdaTask, a multitask online learning algorithm that adapts to the unknown structure of the tasks. When the $N$ tasks are stochastically activated, we show that the regret of AdaTask is better, by a factor that can be as large as $\sqrt{N}$, than the regret achieved by running $N$ independent algorithms, one for each task. AdaTask can be seen as a comparator-adaptive version of Follow-the-Regularized-Leader with a Mahalanobis norm potential. Through a variational formulation of this potential, our analysis reveals how AdaTask jointly learns the tasks and their structure. Experiments supporting our findings are presented.