# Large-Scale Distributed Learning via Private On-Device Locality-Sensitive Hashing

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 37 references that are in the map.
- First posted on arXiv 5 Jun 2023.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [On Using Very Large Target Vocabulary for Neural Machine Translation](https://mlsanity.com/paper/1412.2007/) (2014)
- [Federated Multi-armed Bandits with Personalization](https://mlsanity.com/paper/2102.13101/) (2021)
- [SLIDE : In Defense of Smart Algorithms over Hardware Acceleration for Large-Scale Deep Learning Systems](https://mlsanity.com/paper/1903.03129/) (2019)
- [PipAttack: Poisoning Federated Recommender Systems forManipulating Item Promotion](https://mlsanity.com/paper/2110.10926/) (2021)
- [FedAttack: Effective and Covert Poisoning Attack on Federated Recommendation via Hard Sampling](https://mlsanity.com/paper/2202.04975/) (2022)
- [Scalable and Sustainable Deep Learning via Randomized Hashing](https://mlsanity.com/paper/1602.08194/) (2016)
- [In Defense of MinHash Over SimHash](https://mlsanity.com/paper/1407.4416/) (2014)
- [Circulant Binary Embedding](https://mlsanity.com/paper/1405.3162/) (2014)
- [Revisiting Winner Take All (WTA) Hashing for Sparse Datasets](https://mlsanity.com/paper/1612.01834/) (2016)
- [Distributed SLIDE: Enabling Training Large Neural Networks on Low Bandwidth and Simple CPU-Clusters via Model Parallelism and Sparsity](https://mlsanity.com/paper/2201.12667/) (2022)

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

- [Adaptive Self-Supervised Learning Strategies for Dynamic On-Device LLM Personalization](https://mlsanity.com/paper/2409.16973/) (2024)

## Abstract (arXiv)

Locality-sensitive hashing (LSH) based frameworks have been used efficiently to select weight vectors in a dense hidden layer with high cosine similarity to an input, enabling dynamic pruning. While this type of scheme has been shown to improve computational training efficiency, existing algorithms require repeated randomized projection of the full layer weight, which is impractical for computational- and memory-constrained devices. In a distributed setting, deferring LSH analysis to a centralized host is (i) slow if the device cluster is large and (ii) requires access to input data which is forbidden in a federated context. Using a new family of hash functions, we develop one of the first private, personalized, and memory-efficient on-device LSH frameworks. Our framework enables privacy and personalization by allowing each device to generate hash tables, without the help of a central host, using device-specific hashing hyper-parameters (e.g. number of hash tables or hash length). Hash tables are generated with a compressed set of the full weights, and can be serially generated and discarded if the process is memory-intensive. This allows devices to avoid maintaining (i) the fully-sized model and (ii) large amounts of hash tables in local memory for LSH analysis. We prove several statistical and sensitivity properties of our hash functions, and experimentally demonstrate that our framework is competitive in training large-scale recommender networks compared to other LSH frameworks which assume unrestricted on-device capacity.