cs.LGMar 6, 2026

Tiny, Hardware-Independent, Compression-based Classification

Authors: Charles Meyers, Aaron MacSween, Erik Elmroth, Tommy Löfstedt

Organizations: Institute for Experiential AI, Northeastern University, Boston, United States · Department of Computer Science, Umeå University, Umeå, Sweden

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

FIGURE 1: This figure depicts the accuracy broken down by string metric (left and centre plots) as well as by dataset and model (right plot). The left and centre plots depict the test accuracy for all best-fit dataset-model-symmetrisation-metric combinations with the error bar indicating the 95% interval. The left plot compares the performance between models that use kernel methods (blue) and models that use distance alone (orange, KNN only). The centre plot compares the RBF kernel (blue) to the Hamming kernel (orange)—the latter is only defined for the “Ratio” metric. In contrast, the right plot depicts test accuracy on only the best NCD-kernelised model (denoted with a “ κ\kappa -” prefix) and the best distance-based KNN proposed by Jiang et. al. [ 27 ] (denoted with a “ dd -” prefix).
FIGURE 2: The distance calculation time (left) and accuracy (right) across each dataset (columns), distance metric (first-axis, left plot), dataset (first-axis, right plot), model (left plot, colour), and symmetrisation method (right plot, colour). For both plots, the bars represent the mean and the error bars represent 95% confidence intervals and colour represents the symmetrisation method. The left plot was calculated using 1000 training samples for each metric-algorithm combination. The right plot was calculated using the test accuracies and 95% confidence interval for the best fit NCD-kernelised model, calculated for each of the symmetrisation-data-model-compressor combination.
More in this topic

Kernel Methods

Kernel methods use similarity functions and reproducing kernel spaces to model nonlinear relationships, quantify uncertainty, and compare data.

See all 223 papers

Explore similar work

CardsList
Sep 18, 2026

An Introduction to Compression-Based Machine Learning

Any lossless compression algorithm (like gzip) may be converted into a machine learning method, via either Normalized Compression Distance or the Minimum Description Length principle. Any auto-regressive model may be converted into a lossless compression method via entropy coding. This seemingly circular dependence has unrealized potential in modern artificial intelligence and machine learning, and we survey and formalize the various strategies that have been used to leverage compression for machine learning. We introduce and empirically validate a design framework for compression-based ML, finding compression-based methods competitive with conventional baselines and decisively stronger on malware. We find that varying these design choices yields accuracy gains of up to 0.62.

John Hurwitz, Edward Raff, Charles K. Nicholas

University of Maryland, Baltimore County · CrowdStrike · Syracuse University

Minimum Description Length
AskPDF
Apr 8, 2026

Variational Feature Compression for Model-Specific Representations

As deep learning inference is increasingly deployed in shared and cloud-based settings, a growing concern is input repurposing, in which data submitted for one task is reused by unauthorized models for another. Existing privacy defenses largely focus on restricting data access, but provide limited control over what downstream uses a released representation can still support. We propose a feature extraction framework that suppresses cross-model transfer while preserving accuracy for a designated classifier. The framework employs a variational latent bottleneck, trained with a task-driven cross-entropy objective and KL regularization, but without any pixel-level reconstruction loss, to encode inputs into a compact latent space. A dynamic binary mask, computed from per-dimension KL divergence and gradient-based saliency with respect to the frozen target model, suppresses latent dimensions that are uninformative for the intended task. Because saliency computation requires gradient access, the encoder is trained in a white-box setting, whereas inference requires only a forward pass through the frozen target model. On CIFAR-100, the processed representations retain strong utility for the designated classifier while reducing the accuracy of all unintended classifiers to below 2%, yielding a suppression ratio exceeding 45 times relative to unintended models. Preliminary experiments on CIFAR-10, Tiny ImageNet, and Pascal VOC provide exploratory evidence that the approach extends across task settings, although further evaluation is needed to assess robustness against adaptive adversaries.

Zinan Guo, Zihan Wang, Chuan Yan +3

The University of Queensland, Brisbane, Australia · University of Wollongong, Wollongong, Australia · City University of Hong Kong, Hong Kong SAR, China

Privacy-Preserving Representation LearningPrivacy-Preserving MLRepresentation Learning
AskPDF
Oct 15, 2026

FedPix: Learning What to Share with Less Leakage in Federated Intelligence

Existing federated intelligence paradigms primarily focus on how models are trained or aggregated, while overlooking a more fundamental question: what information should leave the client? Existing methods often share model updates that users cannot easily inspect, or data representations that may reveal sensitive information. Moreover, generating these representations can be computationally expensive for resource-constrained clients. We observe that image classification does not require all the visual details needed to reconstruct the original image. This suggests that clients could share less information while preserving task performance. However, learning what to preserve is challenging when the server cannot access raw client data. To address this challenge, we propose FedPix, which learns to share compact, visually inspectable images instead of model updates or intermediate features. The key idea is to use the shared representations themselves to learn what information should be preserved and what can be discarded. By balancing task utility and reconstruction resistance, FedPix enables the server to improve the representations without accessing raw client data, while keeping client-side computation lightweight. Extensive experiments on BloodMNIST, CIFAR-10, FashionMNIST, and MNIST demonstrate that FedPix achieves strong reconstruction resistance, with reconstruction PSNR as low as 6.87dB and synthetic PSNR as low as 6.74dB. Meanwhile, FedPix reduces client runtime by up to 96.0% (from 1223s to 49s on CIFAR-10), while maintaining competitive classification accuracy of 99.18% on MNIST, 89.97% on FashionMNIST, 82.24% on BloodMNIST, and 65.63% on CIFAR-10.

Jingwei Zhao, Tiantong Sun, Yuanyuan Song +6

Huazhong University of Science and Technology, Wuhan, China · George Mason University, Fairfax, VA, USA

Privacy-Preserving Representation LearningPrivacy-Preserving MLFederated LearningLearned Image Compression
AskPDF