Learning, compression, and leakage: Minimising classification error via meta-universal compression principles

Learning and compression are driven by the common aim of identifying and\nexploiting statistical regularities in data, which opens the door for fertile\ncollaboration between these areas. A promising group of compression techniques\nfor learning scenarios is normalised maximum likelihood (NML) coding, which\nprovides strong guarantees for compression of small datasets - in contrast with\nmore popular estimators whose guarantees hold only in the asymptotic limit.\nHere we consider a NML-based decision strategy for supervised classification\nproblems, and show that it attains heuristic PAC learning when applied to a\nwide variety of models. Furthermore, we show that the misclassification rate of\nour method is upper bounded by the maximal leakage, a recently proposed metric\nto quantify the potential of data leakage in privacy-sensitive scenarios.\n