Decentralized Communication-Efficient Multitask Representation Learning

Representation learning enables effective learning in data-scarce settings by extracting shared features from related tasks. While it is well studied in centralized settings, decentralized representation learning remains underexplored. In decentralized settings, data are distributed across nodes that must collaboratively learn without a central coordinator. In this work, we study decentralized multitask learning under a shared low-dimensional representation. We consider <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> source tasks each with <inline-formula><tex-math notation="LaTeX">$n$</tex-math></inline-formula> data points in <inline-formula><tex-math notation="LaTeX">$\mathbb {R}^{d}$</tex-math></inline-formula>. The goal is to recover the matrix <inline-formula><tex-math notation="LaTeX">$\Theta ^\star {}:= [\theta ^\star _{1}, \theta ^\star _{2}, \ldots, \theta ^\star _{T}] \in \mathbb {R}^{d \times T}$</tex-math></inline-formula>, which has rank <inline-formula><tex-math notation="LaTeX">$r \ll \min \lbrace d,T\rbrace$</tex-math></inline-formula>, from observations following the model <inline-formula><tex-math notation="LaTeX">$\bm {y}_{ti}:= \bm {x}_{ti}^\top \theta ^\star _{t},$</tex-math></inline-formula> for <inline-formula><tex-math notation="LaTeX">$t=1,2,{\ldots },T$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$i=1,2,\ldots, n.$</tex-math></inline-formula> We present a novel alternating projected gradient descent and minimization algorithm for recovering a low-rank feature matrix in a decentralized fashion. We obtain constructive provable guarantees that provide a lower bound on the required sample complexity and an upper bound on the iteration complexity (total number of iterations needed to achieve a certain error level) of our proposed algorithm. This latter bound allows us to analyze the time and communication complexity of our algorithm and show that it is fast and communication efficient. We perform numerical simulations to validate the performance of our algorithm and compare it with benchmarks.