Sample Compression Unleashed: New Generalization Bounds for Real Valued Losses

The sample compression theory provides The sample compression theory is rich and multiple generalization guarantees for predictors that different approaches exist. For example, Attias et al. can be fully defined using a subset of the (2018); Ben-David et al. (2024); David et al. (2016); training dataset and a (short) message string, Floyd and Warmuth (1995); Hanneke and Kontorovich generally defined as a binary sequence. Previous (2021); Hanneke et al. (2018, 2019, 2024); Moran and works provided generalization bounds for Yehudayoff (2016); Rubinstein and Rubinstein (2012) the zero-one loss, which is restrictive notably propose theoretical results relating the VC dimension when applied to deep learning approaches. In (Vapnik and Chervonenkis, 1971) and the compression this paper, we present a general framework for analysis. By relating the probability of change of deriving new sample compression bounds that compression to the true risk, Campi and Garatti (2023); hold for real-valued unbounded losses. Using Paccagnan et al. (2024) express very tight guarantees for the Pick-To-Learn (P2L) meta-algorithm, the consistent case, i.e., when the error on the training which transforms the training method of set is zero. Finally, Laviolette et al. (2005); Marchand any machine-learning predictor to yield et al. (2003); Marchand and Shawe-Taylor (2002); Marchand sample-compressed predictors, we empirically and Sokolova (2005); Shah (2007) give computable demonstrate the tightness of the bounds and risk certificates valid even in the non-consistent case.