# Scaling Federated Linear Contextual Bandits via Sketching

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 39 references that are in the map.
- First posted on arXiv 1 May 2026.

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

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Federated Optimization in Heterogeneous Networks](https://mlsanity.com/paper/1812.06127/) (2018)
- [Federated Learning: Strategies for Improving Communication Efficiency](https://mlsanity.com/paper/1610.05492/) (2016)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [Federated Multi-Armed Bandits](https://mlsanity.com/paper/2101.12204/) (2021)
- [Distributed Clustering of Linear Bandits in Peer to Peer Networks](https://mlsanity.com/paper/1604.07706/) (2016)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Learning Equilibria in Matching Markets from Bandit Feedback](https://mlsanity.com/paper/2108.08843/) (2021)
- [Asynchronous Upper Confidence Bound Algorithms for Federated Linear Bandits](https://mlsanity.com/paper/2110.01463/) (2021)
- [A Simple and Provably Efficient Algorithm for Asynchronous Federated Contextual Linear Bandits](https://mlsanity.com/paper/2207.03106/) (2022)
- [Sketching for First Order Method: Efficient Algorithm for Low-Bandwidth Channel and Vulnerability](https://mlsanity.com/paper/2210.08371/) (2022)
- [Subspace Embedding and Linear Regression with Orlicz Norm](https://mlsanity.com/paper/1806.06430/) (2018)
- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (2022)
- [Efficient Linear Bandits through Matrix Sketching](https://mlsanity.com/paper/1809.11033/) (2018)
- [Decentralized Randomly Distributed Multi-agent Multi-armed Bandit with Heterogeneous Rewards](https://mlsanity.com/paper/2306.05579/) (2023)
- [Federated Combinatorial Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2405.05950/) (2024)
- [Federated Online Clustering of Bandits](https://mlsanity.com/paper/2208.14865/) (2022)
- [Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Users](https://mlsanity.com/paper/2402.16312/) (2024)
- [Beyond Johnson-Lindenstrauss: Uniform Bounds for Sketched Bilinear Forms](https://mlsanity.com/paper/2509.21847/) (2025)
- [Traffic Simulations: Multi-City Calibration of Metropolitan Highway Networks](https://mlsanity.com/paper/2501.04783/) (2025)
- [Mathematical Computation on High-dimensional Data via Array Programming and Parallel Acceleration](https://mlsanity.com/paper/2506.22929/) (2025)

## Abstract (arXiv)

In federated contextual linear bandits, high data dimensionality incurs prohibitive computation and communication costs: local agents perform O(d3)-time determinant computation and upload O(d2) parameters, making existing algorithms unscalable, where d is the dimension of data. To relieve these scaling bottlenecks, this paper proposes Federated Sketch Contextual Linear Bandits (FSCLB). On the computation side, FSCLB uses SVD to indirectly obtain the determinant required for communication, eliminating the prohibitive cost of direct determinant calculation and cutting complexity from O(d3) to O(l2d) per round, where l< d is the sketch size. On the communication side, FSCLB introduces a double-sketch strategy that reduces both upload and download costs from O(d2) to O(ld). Naively involving sketch update into federated contextual linear bandits can destroy the local increment and invalidate the asynchronous communication condition; FSCLB solves this by replacing the covariance matrix with the sketch matrix when deciding whether to communicate. Theoretically, FSCLB achieves a regret bound of widetildeO ((√d+√Mvarepsilonl)√lT), where varepsilonl is the upper bounded by the spectral tail of the covariance matrix; when l exceeds the rank of the covariance matrix, the bound simplifies to widetildeO(√ldT), matching the optimal no-sketch regret. Experiments on both synthetic and real-world datasets show that FSCLB significantly reduces computational and communication costs by over 90 % while sacrificing only a negligible amount of cumulative reward.