Federated Nearest Neighbor Classification With A Colony Of Fruit-flies: With Supplement

Abstract

The mathematical formalization of a neurological mechanism in the olfactory circuit of a fruit-fly as a locality sensitive hash (Flyhash) and bloom filter (FBF) has been recently proposed and "reprogrammed" for various machine learning tasks such as similarity search, outlier detection and text embeddings. We propose a novel reprogramming of this hash and bloom filter to emulate the canonical nearest neighbor classifier (NNC) in the challenging Federated Learning (FL) setup where training and test data are spread across parties and no data can leave their respective parties. Specifically, we utilize Flyhash and FBF to create the FlyNN classifier, and theoretically establish conditions where FlyNN matches NNC. We show how FlyNN is trained exactly in a FL setup with low communication overhead to produce FlyNNFL, and how it can be differentially private. Empirically, we demonstrate that (i) FlyNN matches NNC accuracy across 70 OpenML datasets, (ii) FlyNNFL training is highly scalable with

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyram2021federated

Related papers

• Neural Neighborhood Encoding For Classification (2020)0.00
• Improving Similarity Search With High-dimensional Locality-sensitive Hashing (2018)0.00
• Can A Fruit Fly Learn Word Embeddings? (2021)0.00
• In-memory Nearest Neighbor Search With Fefet Multi-bit Content-addressable Memories (2020)11.85
• Fast Nearest-neighbor Classification Using RNN In Domains With Large Number Of Classes (2017)0.00
• Fast And Bayes-consistent Nearest Neighbors (2019)0.00
• An Adjusted Nearest Neighbor Algorithm Maximizing The F-measure From Imbalanced Data (2019)0.00
• Falconn++: A Locality-sensitive Filtering Approach For Approximate Nearest Neighbor Search (2022)2.26