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

arXiv:2605.00473v1 Announce Type: new 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{O}(1) iterations and attains a near-optimal estimation error of widetilde{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.

Source: arXiv cs.LG | 2026-05-04