Near-optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representation
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 \emph{near-optimal} estimation error of $\widetilde{\mathcal{O}}(dk/(TN))$, \emph{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.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Task LearningSimilar Papers 제목 키워드 기반
Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix
Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data by performing clustering on the learned optimal embedding across views. Though demonstrating promising performance in vario…
ClusteringVocal Bursts Intensity PredictionTime- and frequency-limited H2-optimal model order reduction of bilinear control systems
In the time- and frequency-limited model order reduction, a reduced-order approximation of the original high-order model is sought to ensure superior accuracy in some desired time and frequency intervals. We first consid…
Deep Learning for Dynamic Programming with Recursive Utility Using First-order Conditions
This paper proposes the certainty-equivalent first-order learning (CEFOL) algorithm, a deep learning algorithm for solving discrete-time dynamic programming problems with recursive utility. Dynamic programming with recur…
Decoupling Learning and Decision-Making: Breaking the $\mathcal{O}(\sqrt{T})$ Barrier in Online Resource Allocation with First-Order Methods
Online linear programming plays an important role in both revenue management and resource allocation, and recent research has focused on developing efficient first-order online learning algorithms. Despite the empirical …
Decision MakingManagementSmooth Quasar-Convex Optimization with Constraints
Quasar-convex functions form a broad nonconvex class with applications to linear dynamical systems, generalized linear models, and Riemannian optimization, among others. Current nearly optimal algorithms work only in aff…