  A compression function is a map that slims down an observational set into a
subset of reduced size, while preserving its informational content. In multiple
applications, the condition that one new observation makes the compressed set
change is interpreted that this observation brings in extra information and, in
learning theory, this corresponds to misclassification, or misprediction. In
this paper, we lay the foundations of a new theory that allows one to keep
control on the probability of change of compression (which maps into the
statistical "risk" in learning applications). Under suitable conditions, the
cardinality of the compressed set is shown to be a consistent estimator of the
probability of change of compression (without any upper limit on the size of
the compressed set); moreover, unprecedentedly tight finite-sample bounds to
evaluate the probability of change of compression are obtained under a
generally applicable condition of preference. All results are usable in a fully
agnostic setup, i.e., without requiring any a priori knowledge on the
probability distribution of the observations. Not only these results offer a
valid support to develop trust in observation-driven methodologies, they also
play a fundamental role in learning techniques as a tool for hyper-parameter
tuning.
