Communication-Efficient Distributed Multilinear Multitask Learning

In multi-task learning (MTL), the parameter of each task is often multidimensional and exhibits high-order intra-task relatedness. Meanwhile, multiple multidimensional parameters in MTL naturally induce the multi-way inter-task relatedness. This paper proposes a distributed multilinear MTL method that models these two types of relatedness through a shared multilinear representation, which models the parameter of each task through mode-wise factors shared across tasks and a task-specific core tensor. We instantiate our method for the multi-task high-dimensional tensor linear regression (MTTLR) problem. A two-stage communication-efficient distributed method, termed D-AltMin-PGD, is developed to minimize the induced non-convex loss to jointly learn the models. For the Gaussian input and additive noise, we prove that from initialization via the proposed distributed power-iteration, D-AltMin-PGD converges linearly to a statistical neighborhood of truth parameters despite nonconvexity. The resulting statistical error separates into a shared-factor term that benefits from the samples across all tasks and a task-specific core term determined by the per-task samples, thereby establishing a provable multi-task gain. We further propose a preconditioned variant, D-AltMin-P2GD, to accelerate convergence in ill-conditioned regimes with negligible extra communication cost. Finally, we establish minimax lower bound for proposed MTTLR under Gaussian input and noise. Extensive experiments validate our theoretical results and demonstrate the efficiency of the proposed method.