# Beyond Centralization: Provable Communication Efficient Decentralized Multi-Task Learning

arXiv: https://arxiv.org/abs/2512.22675 · HTML: https://mlsanity.com/paper/2512.22675/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 44 references that are in the map.
- First posted on arXiv 27 Dec 2025.

## Builds on (most cited first, 22 of 22)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Taskonomy: Disentangling Task Transfer Learning](https://mlsanity.com/paper/1804.08328/) (2018)
- [Exploiting Shared Representations for Personalized Federated Learning](https://mlsanity.com/paper/2102.07078/) (2021)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [On the Convergence of Decentralized Gradient Descent](https://mlsanity.com/paper/1310.7063/) (2013)
- [D2: Decentralized Training over Decentralized Data](https://mlsanity.com/paper/1803.07068/) (2018)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [NEXT: In-Network Nonconvex Optimization](https://mlsanity.com/paper/1602.00591/) (2016)
- [The Noisy Power Method: A Meta Algorithm with Applications](https://mlsanity.com/paper/1311.2495/) (2013)
- [An improved convergence analysis for decentralized online stochastic non-convex optimization](https://mlsanity.com/paper/2008.04195/) (2020)
- [On Nonconvex Decentralized Gradient Descent](https://mlsanity.com/paper/1608.05766/) (2016)
- [NLP From Scratch Without Large-Scale Pretraining: A Simple and Efficient Framework](https://mlsanity.com/paper/2111.04130/) (2021)
- [Representation Learning Beyond Linear Prediction Functions](https://mlsanity.com/paper/2105.14989/) (2021)
- [Active Multi-Task Representation Learning](https://mlsanity.com/paper/2202.00911/) (2022)
- [Improved Active Multi-Task Representation Learning via Lasso](https://mlsanity.com/paper/2306.02556/) (2023)
- [Multi-Task Learning with Summary Statistics](https://mlsanity.com/paper/2307.02388/) (2023)
- [Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Bandits](https://mlsanity.com/paper/2410.02068/) (2024)
- [A Decentralized Primal-Dual Framework for Non-convex Smooth Consensus Optimization](https://mlsanity.com/paper/2107.11321/) (2021)
- [Fully Decentralized and Federated Low Rank Compressive Sensing](https://mlsanity.com/paper/2112.13412/) (2021)

## Abstract (arXiv)

Representation learning is a widely adopted framework for learning in data-scarce environments, aiming to extract common features from related tasks. While centralized approaches have been extensively studied, decentralized methods remain largely underexplored. We study decentralized multi-task representation learning in which the features share a low-rank structure. We consider multiple tasks, each with a finite number of data samples, where the observations follow a linear model with task-specific parameters. In the decentralized setting, task data are distributed across multiple nodes, and information exchange between nodes is constrained by a communication network. The goal is to recover the underlying feature matrix whose rank is much smaller than both the parameter dimension and the number of tasks. We propose a new alternating projected gradient and minimization algorithm with provable accuracy guarantees. We provide comprehensive characterizations of the time, communication, and sample complexities. Importantly, the communication complexity is independent of the target accuracy, which significantly reduces communication cost compared to prior methods. Numerical simulations validate the theoretical analysis across different dimensions and network topologies, and demonstrate regimes in which decentralized learning outperforms centralized federated approaches.