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

Shihong Ding, Fangyu Du, Cong Fang
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:24843-24879, 2026.

Abstract

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 $\widetilde{\mathcal{O}}(1)$ iterations and attains a near-optimal estimation error of $\widetilde{\mathcal{O}}(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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-ding26b, title = {Near-Optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representation}, author = {Ding, Shihong and Du, Fangyu and Fang, Cong}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {24843--24879}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/ding26b/ding26b.pdf}, url = {https://proceedings.mlr.press/v306/ding26b.html}, abstract = {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 $\widetilde{\mathcal{O}}(1)$ iterations and attains a near-optimal estimation error of $\widetilde{\mathcal{O}}(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.} }
Endnote
%0 Conference Paper %T Near-Optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representation %A Shihong Ding %A Fangyu Du %A Cong Fang %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-ding26b %I PMLR %P 24843--24879 %U https://proceedings.mlr.press/v306/ding26b.html %V 306 %X 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 $\widetilde{\mathcal{O}}(1)$ iterations and attains a near-optimal estimation error of $\widetilde{\mathcal{O}}(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.
APA
Ding, S., Du, F. & Fang, C.. (2026). Near-Optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representation. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:24843-24879 Available from https://proceedings.mlr.press/v306/ding26b.html.

Related Material