# Tiny, Hardware-Independent, Compression-based Classification

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 54 references that are in the map.
- First posted on arXiv 6 Mar 2026.

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

- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [HopSkipJumpAttack: A Query-Efficient Decision-Based Attack](https://mlsanity.com/paper/1904.02144/) (2019)
- [High Accuracy and High Fidelity Extraction of Neural Networks](https://mlsanity.com/paper/1909.01838/) (2019)
- [Imbalanced-learn: A Python Toolbox to Tackle the Curse of Imbalanced Datasets in Machine Learning](https://mlsanity.com/paper/1609.06570/) (2016)
- [Membership Leakage in Label-Only Exposures](https://mlsanity.com/paper/2007.15528/) (2020)
- [Sleeper Agent: Scalable Hidden Trigger Backdoors for Neural Networks Trained from Scratch](https://mlsanity.com/paper/2106.08970/) (2021)
- [Bypassing Backdoor Detection Algorithms in Deep Learning](https://mlsanity.com/paper/1905.13409/) (2019)
- [Copycat CNN: Stealing Knowledge by Persuading Confession with Random Non-Labeled Data](https://mlsanity.com/paper/1806.05476/) (2018)
- [Dark Patterns after the GDPR: Scraping Consent Pop-ups and Demonstrating their Influence](https://mlsanity.com/paper/2001.02479/) (2020)
- [Quantifying Membership Inference Vulnerability via Generalization Gap and Other Model Metrics](https://mlsanity.com/paper/2009.05669/) (2020)
- [The Devil is in the GAN: Backdoor Attacks and Defenses in Deep Generative Models](https://mlsanity.com/paper/2108.01644/) (2021)
- [Less is More: Parameter-Free Text Classification with Gzip](https://mlsanity.com/paper/2212.09410/) (2022)
- [Gzip versus bag-of-words for text classification](https://mlsanity.com/paper/2307.15002/) (2023)
- [A Strong Inductive Bias: Gzip for binary image classification](https://mlsanity.com/paper/2401.07392/) (2024)
- [A Training Rate and Survival Heuristic for Inference and Robustness Evaluation (TRASHFIRE)](https://mlsanity.com/paper/2401.13751/) (2024)

## Abstract (arXiv)

The recent developments in machine learning have highlighted a conflict between online platforms and their users in terms of privacy. The importance of user privacy and the struggle for power over user data has been intensified as regulators and operators attempt to police online platforms. As users have become increasingly aware of privacy issues, client-side data storage, management, and analysis have become a favoured approach to large-scale centralised machine learning. However, state-of-the-art machine learning methods require vast amounts of labelled user data, making them unsuitable for models that reside client-side and only have access to a single user's data. State-of-the-art methods are also computationally expensive, which degrades the user experience on compute-limited hardware and also reduces battery life. A recent alternative approach has proven remarkably successful in classification tasks across a wide variety of data -- using a compression-based distance measure (called normalised compression distance) to measure the distance between generic objects in classical distance-based machine learning methods. In this work, we demonstrate that the normalised compression distance is actually not a metric; develop it for the wider context of kernel methods to allow modelling of complex data; and present techniques to improve the training time of models that use this distance measure. We demonstrate that the normalised compression distance works as well as and sometimes better than other metrics and kernels -- while requiring only marginally more computational costs and in spite of the lack of formal metric properties. The end results is a simple model with remarkable accuracy even when trained on a very small number of samples allowing for models that are small and effective enough to run entirely on a client device using only user-supplied data.