Learning, compression, and leakage: Minimising classification error via meta-universal compression principles
This work addresses classification accuracy and privacy leakage in learning scenarios, offering a novel integration of compression principles, but it appears incremental as it builds on existing NML techniques.
The paper tackles the problem of supervised classification by proposing a decision strategy based on normalised maximum likelihood (NML) coding, which attains heuristic PAC learning for various models and shows that its misclassification rate is upper bounded by maximal leakage, a privacy metric.
Learning and compression are driven by the common aim of identifying and exploiting statistical regularities in data, which opens the door for fertile collaboration between these areas. A promising group of compression techniques for learning scenarios is normalised maximum likelihood (NML) coding, which provides strong guarantees for compression of small datasets - in contrast with more popular estimators whose guarantees hold only in the asymptotic limit. Here we consider a NML-based decision strategy for supervised classification problems, and show that it attains heuristic PAC learning when applied to a wide variety of models. Furthermore, we show that the misclassification rate of our method is upper bounded by the maximal leakage, a recently proposed metric to quantify the potential of data leakage in privacy-sensitive scenarios.