  We formulate the problem of performing optimal data compression under the
constraints that compressed data can be used for accurate classification in
machine learning. We show that this translates to a problem of minimizing the
mutual information between data and its compressed version under the constraint
on error probability of classification is small when using the compressed data
for machine learning. We then provide analytical and computational methods to
characterize the optimal trade-off between data compression and classification
error probability. First, we provide an analytical characterization for the
optimal compression strategy for data with binary labels. Second, for data with
multiple labels, we formulate a set of convex optimization problems to
characterize the optimal tradeoff, from which the optimal trade-off between the
classification error and compression efficiency can be obtained by numerically
solving the formulated optimization problems. We further show the improvements
of our formulations over the information-bottleneck methods in classification
performance.
