# Multitask Online Mirror Descent

arXiv: https://arxiv.org/abs/2106.02393 · HTML: https://mlsanity.com/paper/2106.02393/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 46 references that are in the map.
- First posted on arXiv 4 Jun 2021.

## Builds on (most cited first, 11 of 11)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [A Survey on Multi-Task Learning](https://mlsanity.com/paper/1707.08114/) (2017)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Meta-Learning: A Survey](https://mlsanity.com/paper/1810.03548/) (2018)
- [Provable Guarantees for Gradient-Based Meta-Learning](https://mlsanity.com/paper/1902.10644/) (2019)
- [A Gang of Bandits](https://mlsanity.com/paper/1306.0811/) (2013)
- [A Principled Approach for Learning Task Similarity in Multitask Learning](https://mlsanity.com/paper/1903.09109/) (2019)
- [Regret Bounds for Lifelong Learning](https://mlsanity.com/paper/1610.08628/) (2016)
- [Multi-Task Learning with Labeled and Unlabeled Tasks](https://mlsanity.com/paper/1602.06518/) (2016)
- [A Distributed Method for Fitting Laplacian Regularized Stratified Models](https://mlsanity.com/paper/1904.12017/) (2019)

## Built on by (most cited first, 6 of 6)

- [Trace norm regularization for multi-task learning with scarce data](https://mlsanity.com/paper/2202.06742/) (2022)
- [Nonparametric Teaching for Multiple Learners](https://mlsanity.com/paper/2311.10318/) (2023)
- [AdaTask: Adaptive Multitask Online Learning](https://mlsanity.com/paper/2205.15802/) (2022)
- [Multitask Online Learning: Listen to the Neighborhood Buzz](https://mlsanity.com/paper/2310.17385/) (2023)
- [POMRL: No-Regret Learning-to-Plan with Increasing Horizons](https://mlsanity.com/paper/2212.14530/) (2022)
- [Meta-learning of shared linear representations beyond well-specified linear regression](https://mlsanity.com/paper/2501.18975/) (2025)

## Abstract (arXiv)

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 + σ2(N-1)√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 √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.