# A Multi-Token Coordinate Descent Method for Semi-Decentralized Vertical Federated Learning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 67 references that are in the map.
- First posted on arXiv 18 Sep 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [Multi-view Convolutional Neural Networks for 3D Shape Recognition](https://mlsanity.com/paper/1505.00880/) (2015)
- [Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent](https://mlsanity.com/paper/1705.09056/) (2017)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization](https://mlsanity.com/paper/1709.08765/) (2017)
- [Vertical Federated Learning: Concepts, Advances and Challenges](https://mlsanity.com/paper/2211.12814/) (2022)
- [VAFL: a Method of Vertical Asynchronous Federated Learning](https://mlsanity.com/paper/2007.06081/) (2020)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [Vertical Federated Learning: Challenges, Methodologies and Experiments](https://mlsanity.com/paper/2202.04309/) (2022)
- [Semi-Decentralized Federated Learning with Cooperative D2D Local Model Aggregations](https://mlsanity.com/paper/2103.10481/) (2021)
- [Multi-Stage Hybrid Federated Learning over Large-Scale D2D-Enabled Fog Networks](https://mlsanity.com/paper/2007.09511/) (2020)
- [SplitNN-driven Vertical Partitioning](https://mlsanity.com/paper/2008.04137/) (2020)
- [BEER: Fast O(1/T) Rate for Decentralized Nonconvex Optimization with Communication Compression](https://mlsanity.com/paper/2201.13320/) (2022)
- [Compressed-VFL: Communication-Efficient Learning with Vertically Partitioned Data](https://mlsanity.com/paper/2206.08330/) (2022)
- [Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1804.06568/) (2018)
- [COLA: Decentralized Linear Learning](https://mlsanity.com/paper/1808.04883/) (2018)
- [A Survey on Vertical Federated Learning: From a Layered Perspective](https://mlsanity.com/paper/2304.01829/) (2023)
- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [A principled framework for the design and analysis of token algorithms](https://mlsanity.com/paper/2205.15015/) (2022)
- [Semi-Decentralized Federated Learning with Collaborative Relaying](https://mlsanity.com/paper/2205.10998/) (2022)
- [Hybrid Federated Learning: Algorithms and Implementation](https://mlsanity.com/paper/2012.12420/) (2020)
- [Convergence rate analysis of several splitting schemes](https://mlsanity.com/paper/1406.4834/) (2014)
- [Decentralized Consensus Optimization Based on Parallel Random Walk](https://mlsanity.com/paper/1911.09747/) (2019)
- [Markov Chain Block Coordinate Descent](https://mlsanity.com/paper/1811.08990/) (2018)
- [Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning](https://mlsanity.com/paper/2202.03263/) (2022)

## Built on by (most cited first, 3 of 3)

- [Communication-efficient Vertical Federated Learning via Compressed Error Feedback](https://mlsanity.com/paper/2406.14420/) (2024)
- [Robust Collaborative Inference with Vertically Split Data Over Dynamic Device Environments](https://mlsanity.com/paper/2312.16638/) (2023)
- [Multi-Token Random-Walk Learning via Meeting-Triggered Information Exchange](https://mlsanity.com/paper/2610.14716/) (2026)

## Abstract (arXiv)

Most federated learning (FL) methods use a client-server scheme, where clients communicate only with a central server. However, this scheme is prone to bandwidth bottlenecks at the server and has a single point of failure. In contrast, in a (fully) decentralized approach, clients communicate directly with each other, dispensing with the server and mitigating these issues. Yet, as the client network grows larger and sparser, the convergence of decentralized methods slows down, even failing to converge if the network is disconnected. This work addresses this gap between client-server and decentralized schemes, focusing on the vertical FL setup, where clients hold different features of the same samples. We propose multi-token coordinate descent (MTCD), a flexible semi-decentralized method for vertical FL that can exploit both client-server and client-client links. By selecting appropriate hyperparameters, MTCD recovers the client-sever and decentralized schemes as special cases. In fact, its decentralized instance is itself a novel method of independent interest. Yet, by controlling the degree of dependency on client-server links, MTCD can also explore a spectrum of schemes ranging from client-server to decentralized. We prove that, for sufficiently large batch sizes, MTCD converges at an O(1/T) rate for nonconvex objectives when the tokens roam across disjoint subsets of clients. To capture the aforementioned drawbacks of the client-server scheme succinctly, we model the relative impact of using client-server versus client-client links as the ratio of their "costs", which depends on the application. This allows us to demonstrate, both analytically and empirically, that by tuning the degree of dependency on the server, the semi-decentralized instances of MTCD can outperform both client-server and decentralized approaches across a range of applications.