mlsanityData to 14 Oct 2026

Near-optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representation

arXiv 2605.00473 ↗First posted 1 May 2026cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

Multi-task learning (MTL) has emerged as a pivotal paradigm in machine learning by leveraging shared structures across multiple related tasks. Despite its empirical success, the development of likelihood-based efficiently solvable algorithms--even for shared linear representations--remains largely underdeveloped, primarily due to the non-convex structure intrinsic to matrix factorization. This paper introduces a first-order algorithm that jointly learns a shared representation and task-specific parameters, with guaranteed efficiency. Notably, it converges in widetildeO(1) iterations and attains a near-optimal estimation error of widetildeO(dk/(TN)), improving over existing likelihood-based methods by a factor of k, where d, k, T, N denote input dimension, representation dimension, task count, and samples per task, respectively. Our results justify that likelihood-based first-order methods can efficiently solve the MTL problem.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 40 of its 70 references that are in the map. First posted on arXiv 1 May 2026.

Builds on

40 of 70 references.

References · 40

  1. 2018GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understandingcited by 4,899
  2. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,897
  3. 2017Prototypical Networks for Few-shot Learningcited by 3,015
  4. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,492
  5. 2017Federated Multi-Task Learningcited by 672
  6. 2019Implicit Regularization in Deep Matrix Factorizationcited by 405
  7. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  8. 2020Curriculum Learning for Reinforcement Learning Domains: A Framework and Surveycited by 373
  9. 2020Kernel and Rich Regimes in Overparametrized Modelscited by 306
  10. 2019On The Power of Curriculum Learning in Training Deep Networkscited by 286
  11. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  12. 2020Few-Shot Learning via Learning the Representation, Provablycited by 214
28 more
  1. 2019Competence-based Curriculum Learning for Neural Machine Translationcited by 202
  2. 2017Reverse Curriculum Generation for Reinforcement Learningcited by 198
  3. 2015The Benefit of Multitask Representation Learningcited by 195
  4. 2021Federated Multi-Task Learning under a Mixture of Distributionscited by 192
  5. 2020Provable Meta-Learning of Linear Representationscited by 161
  6. 2020Towards Resolving the Implicit Bias of Gradient Descent for Matrix Factorization: Greedy Low-Rank Learningcited by 150
  7. 2018CurriculumNet: Weakly Supervised Learning from Large-Scale Web Imagescited by 126
  8. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 125
  9. 2018Curriculum Learning by Transfer Learning: Theory and Experiments with Deep Networkscited by 114
  10. 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
  11. 2019Implicit Regularization for Optimal Sparse Recoverycited by 80
  12. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 78
  13. 2019Variational Federated Multi-Task Learningcited by 69
  14. 2016Harder, Better, Faster, Stronger Convergence Rates for Least-Squares Regressioncited by 64
  15. 2024Distribution Matching for Multi-Task Learning of Classification Tasks: a Large-Scale Study on Faces & Beyondcited by 60
  16. 2019Simple and Effective Curriculum Pointer-Generator Networks for Reading Comprehension over Long Narrativescited by 59
  17. 2023Understanding Incremental Learning of Gradient Descent: A Fine-grained Analysis of Matrix Sensingcited by 42
  18. 2019Sharp Analysis for Nonconvex SGD Escaping from Saddle Pointscited by 40
  19. 2021Last Iterate Risk Bounds of SGD with Decaying Stepsize for Overparameterized Linear Regressioncited by 38
  20. 2022Adaptive and Robust Multi-Task Learningcited by 34
  21. 2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
  22. 2023Learning from Similar Linear Representations: Adaptivity, Minimaxity, and Robustnesscited by 28
  23. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  24. 2023Provable Multi-Task Representation Learning by Two-Layer ReLU Neural Networkscited by 16
  25. 2022Subspace Recovery from Heterogeneous Data with Non-isotropic Noisecited by 14
  26. 2025Towards Real Unsupervised Anomaly Detection Via Confident Meta-Learningcited by 8
  27. 2013Convex Discriminative Multitask Clusteringcited by 5
  28. 2024Few-shot Multi-Task Learning of Linear Invariant Features with Meta Subspace Pursuitcited by 2

Built on by

Not cited yet.