Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses
This work addresses the problem of restrictive generalization bounds in sample compression for practitioners in machine learning, particularly in deep learning, by extending it to real-valued losses, though it is incremental as it builds on existing theory.
The paper tackles the limitation of sample compression theory to zero-one loss by introducing a framework for deriving generalization bounds for real-valued unbounded losses, and empirically demonstrates tightness and versatility using the Pick-To-Learn meta-algorithm on random forests and neural networks.
The sample compression theory provides generalization guarantees for predictors that can be fully defined using a subset of the training dataset and a (short) message string, generally defined as a binary sequence. Previous works provided generalization bounds for the zero-one loss, which is restrictive notably when applied to deep learning approaches. In this paper, we present a general framework for deriving new sample compression bounds that hold for real-valued unbounded losses. Using the Pick-To-Learn (P2L) meta-algorithm, which transforms the training method of any machine-learning predictor to yield sample-compressed predictors, we empirically demonstrate the tightness of the bounds and their versatility by evaluating them on random forests and multiple types of neural networks.