Online Minimum Description Length Passive-Aggressive Algorithms

We present an algorithm for margin-based online learning using lossless compressors (like zip) via the Minimum Description Length Principle. The technique, we call MDL-PA, can be viewed as an analogue of Passive-Aggressive algorithms for probability distributions (equivalently viewed as lossless compression schemes) where we consider a code length margin. Separate models are maintained per class, and the update rule is an information projection correcting the true-class model's prediction on a margin-violating sample. To bridge theory and practice, we demonstrate a practical approximation to this online learning setup via adaptive Lempel-Ziv-style compression dictionaries to classify sequences in the text and malware domains.