  Federated multi-task learning (FMTL) has emerged as a natural choice to
capture the statistical diversity among the clients in federated learning. To
unleash the potential of FMTL beyond statistical diversity, we formulate a new
FMTL problem FedU using Laplacian regularization, which can explicitly leverage
relationships among the clients for multi-task learning. We first show that
FedU provides a unified framework covering a wide range of problems such as
conventional federated learning, personalized federated learning, few-shot
learning, and stratified model learning. We then propose algorithms including
both communication-centralized and decentralized schemes to learn optimal
models of FedU. Theoretically, we show that the convergence rates of both
FedU's algorithms achieve linear speedup for strongly convex and sublinear
speedup of order $1/2$ for nonconvex objectives. While the analysis of FedU is
applicable to both strongly convex and nonconvex loss functions, the
conventional FMTL algorithm MOCHA, which is based on CoCoA framework, is only
applicable to convex case. Experimentally, we verify that FedU outperforms the
vanilla FedAvg, MOCHA, as well as pFedMe and Per-FedAvg in personalized
federated learning.
