A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical
  Federated Learning
Pedro Valdeira Yuejie Chi Cláudia Soares João Xavier
Communication efficiency is a major challenge in federated learning (FL). In
client-server schemes, the server constitutes a bottleneck, and while
decentralized setups spread communications, they do not necessarily reduce them
due to slower convergence. We propose Multi-Token Coordinate Descent (MTCD), a
communication-efficient algorithm for semi-decentralized vertical federated
learning, exploiting both client-server and client-client communications when
each client holds a small subset of features. Our multi-token method can be
seen as a parallel Markov chain (block) coordinate descent algorithm and it
subsumes the client-server and decentralized setups as special cases. We obtain
a convergence rate of $\mathcal{O}(1/T)$ for nonconvex objectives when tokens
roam over disjoint subsets of clients and for convex objectives when they roam
over possibly overlapping subsets. Numerical results show that MTCD improves
the state-of-the-art communication efficiency and allows for a tunable amount
of parallel communications.