mlsanityData to 7 Oct 2026

Multitask Online Mirror Descent

arXiv 2106.02393 ↗First posted 4 Jun 2021cs.LGcited by 6

Not on the map. Why?

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.

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

Builds on

11 of 46 references.

References · 11

  1. 2021Convex optimizationcited by 2,479
  2. 2017A Survey on Multi-Task Learningcited by 838
  3. 2019Introduction to Online Convex Optimizationcited by 793
  4. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  5. 2018Meta-Learning: A Surveycited by 254
  6. 2019Provable Guarantees for Gradient-Based Meta-Learningcited by 67
  7. 2013A Gang of Banditscited by 49
  8. 2019A Principled Approach for Learning Task Similarity in Multitask Learningcited by 32
  9. 2016Regret Bounds for Lifelong Learningcited by 19
  10. 2016Multi-Task Learning with Labeled and Unlabeled Taskscited by 17
  11. 2019A Distributed Method for Fitting Laplacian Regularized Stratified Modelscited by 7

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 2; 2024: 0; 2025: 1.

6 papers.

  1. 2022Trace norm regularization for multi-task learning with scarce datacited by 10
  2. 2023Nonparametric Teaching for Multiple Learnerscited by 7
  3. 2022AdaTask: Adaptive Multitask Online Learningcited by 1
  4. 2023Multitask Online Learning: Listen to the Neighborhood Buzzcited by 1
  5. 2022POMRL: No-Regret Learning-to-Plan with Increasing Horizonscited by 0
  6. 2025Meta-learning of shared linear representations beyond well-specified linear regressioncited by 0