The Pick-to-Learn Algorithm: Empowering Compression for Tight Generalization Bounds and Improved Post-training Performance
Authors: Dario Paccagnan
Marco Campi
Simone Garatti
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Statistical learning theory
Compression theory
Generalization bounds

Abstract: Generalization bounds are valuable both for theory and applications. On the one hand, they shed light on the mechanisms that underpin the learning processes; on the other, they certify how well a learned model performs against unseen inputs.  In this work we build upon a recent breakthrough in compression theory to develop a new framework yielding tight generalization bounds of wide practical applicability.  The core idea is to embed any given learning algorithm into a suitably-constructed meta-algorithm (here called Pick-to-Learn, P2L) in order to instill desirable compression properties. When applied to the MNIST classification dataset and to a synthetic regression problem, P2L not only attains generalization bounds that compare favorably with the state of the art (test-set and PAC-Bayes bounds), but it also learns models with better post-training performance.

The Pick-to-Learn Algorithm: Empowering Compression for Tight Generalization Bounds and Improved Post-training Performance
Dario Paccagnan Dept. of Computing
Marco C. Campi
Dip. di Ingegnerira dell' Informazione Università di Brescia marco campi @unibs. it
Imperial College London
d. paccagnan@imperiall.c ac.
Simone Garatti
Dip. di Elettronica Informazione Bioingeggeria Politecnico di Milano
simone, garatti @polimi.it
Abstract
Generalization bounds are valuable both for theory and applications. On the one hand, they shed light on the mechanisms that underpin the learning processes; on the other, they certify how well a learned model performs against unseen inputs. In this work we build upon recent breakthrough in compression theory (Campi Garatti] (2023) to develop new framework yielding tight generalization bounds of wide practical applicability. The core idea is to embed any given learning algorithm into duitably-constructer meta-algorithm (here called Pick-to-Leart P2L) in order instill desirable compression properties. When applied to the MNIST classification dataset and synthetic regression problem, P2L not only attains generalization bounds that compare favorably with the state the art (test-set and PAC- -ay-ssyes bounds), but it also learns models with better post-training performance.
Introduction
Machine learning has achieved remarkable results in the last decades, with successful stories ranging from digit recognition (Dosovitskiy et al.) 2020). to protein folding (Jumper et al.) (021). traffic prediction (Li et al., 2017), medical diagnosis (Knnnnenko 2001). and beyond. Contrary to that, the understanding of the mechanisms underpinning generalization, and the availability of bounds for its evaluation, still limited. This is unfortunate because generalization bounds are important both to develop trust in learning methods as well as to allow for a fair comparison among alternatives, which relevant syper-parrmeter tuning.
Among the various tools that have been introduced to provide generalization bounds, we recall the VC- dimension (Vapnik & Chervonenkis, 1971), Radamacher complexity (Bartlett Mendelson 2002), mutual information (Xu & Raginsky (017)), sharpness (Keskar et al. 2017). compression schemes (Littlestone & Warmuth 1986; Floyd & Warmuth 1995 Graepel al.] 2005). and PAC-Bayes approaches (Dziugaite & Roy 2017 Perez-Ortiz et al., 2021 Each of these frameworks is applicable to specific contexts. For example, the approach based on the VC-theory requires that model is selected from class with finite VC-dimension, while compression schemes are applicable provided the existence of an informative subset of data points from which the model can be reconstructed. has also to be said that the level of precision of the available bounds is highly problem-dependent and they often take a significant margin from the actual performance.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

While bounds based on the VC-dimension, and some other aforementioned approaches, are often conservative (resulting in untight, or even vacuous, evaluations), the sharpest approach evaluate generalization across various learning domains is still that based on test-set bounds (Langford 2005). However, the test-set approach requires holding out a portion of the training set for testing, which makes it data-ine cata-innfficient with negative impact on the post-training performance. In view of these considerations, it would be highly desirable to develop a new general-purpose technique able to set the data free in their double role of (i) delivering the information that is needed to learn, while also (ii) providing evaluations on the attained generalization result.
In this paper, we move towards the goal expressed in (i) and (ii). To this aim, we build upon a recent breakthrough in the field of compression schemes, (Campi & Garatti 2023). Therein, the authors have established new and tight bounds for the so-called probability of change of compression that hold under certain properties: under the property of preference, tight upper bounds have been obtained that link the probability of change of compression to the size of the compressed set" moreover, under a so-called non-associativityy property and a property of non-concentrated mass, lower bound has also been obtained. Hence, under these additional properties, the change of compression is put in sandwich between two bounds, which are shown to rapidly converge one on top of the other as the number of data points increases. The interest of these results in the context of statistical learning lies on the fact that some learning algorithms naturally define a compression scheme and the probability be used to bound the probability of wwwsec/sssfccatooommspreeeeeeeee
of change of compression However, the challenge is that many other learning algorithms (including most algorithms for deep learning) do not exhibit any compression property.
With this paper, we give new, significant, thrust to the above findings. Specifically, we present a meta-algorithmm, called Pick-to-Learn (P2L), that incorporates any learning algorithm given as a black box and makes it into a compression scheme, so licensing the use of results from compression to establish generalization bounds in virtually any learning problem. More precisely, the meta-algorithm constructs a loop around the original learning algorithm that elects at each iteration a new data point to be included in the set of those used for training. Independently of the inner algorithm (which can be any algorithm. e.g., GD Gradient Descent - for regression). we show that the meta- algorithm possesses the properties of preference, -ssociaicttyyvityy and non-concentrated mass by which, as mentioned above, one can secure extremely tight bounds on the change of compression. By further linking the change of compression the probability of misclassification (or misprediction, in regression problems). powerful and informative generalization bounds are obtained without requiring the use of test-sets. When using our approach on various setups, of which here present the MNIST classification problem and a synthetic regression problem, we find that P2L returns bounds that are comparable, or superior, those attained via test-set and PAC-Bayes bounds, while it learns models with better post-training performance.
The idea and the theoretical apparatus behind P2L is presented for the first time in this paper. which also provides a complete set of proofs (given in the appendices) to establish the ensuing generalization results. On the other hand, it has to be said that the usage of the meta-algorithh P2L requires the user to choose a rule by which a new data point is selected at each iteration of the external loop, a choice that is problem-dependent and cannot be part of the general theory. Therefore, the present contribution lays the groundwork of a general new methodology and we expect that this methodology will thrive in the coming few years by adapting it to various specific contexts.
While our demonstrative focus in this paper is on classification and regression, P2L bears a promise of applicability to any data-driven learning problem, including large-scale constrained optimization. Interestingly, in recent years, selection rules to iteratively find "core" " examples in the training dataset have been studied in various learning problems, see, e.g., (Toneva et al. 2018 Paul et al.) |022 Yang ct al. 2022). These works differ from the present contribution both in their motivations (pruning the training dataset is motivated by computational issues) and results (none of these works provide a compression scheme according to the classical definition and certainly they do not enforce any preference property). Nonetheless, these selection rules can be adopted in the external loop of P2L
1 'The notion of preference known in the machine learning literature before CCampi & Garatti 2023
where it is often referred to as stability. Under stability, previous contributions, e.g., (Bousquet et al. Hanneke & Kontorovich| 2021), have provided valuable generalization results and the approach we propose may as well build upon these results; however, the bounds in (Campi & Garatti (023) largely improve over all previous findings.
2020
2

---

and we envisage synergy of our results with these methods. This opens exciting perspectives for future research.
Structure of the paper. After introducing the mathematical preliminaries (Section 2 we present the meta-algorithm P2L. (Section B) and its generalization results (Section 4 For the sake of generality, these sections adopt an abstract viewpoint that accommodates various learning frameworks. Applications MNIST classification and synthetic regression can be found in Sections 5 and 6 Appendix contains the proof of the main result and various additional results, including an extended version of P2L. Appendix [B] instead includes some implementation details and additional material for the MNIST application. Finally, Appendix provides a further numerical experimentation to study the interpretability of the results of P2L. The source code necessary to reproduce all our numerical results can be found in the Supplementary Material, and at at pottps://githhe com/ het//dario.. dario-p/P21
2 Mathematical Preliminaries
We use 2 to denote example, which is an element from generic set Z. For instance, in supervised classification, z is an input-label pair (z, y) and Z = X x (1, instead, in supervised regression, 2 X' R. We assume to have access N examples, which we collect in dataset D; that is, = {21. 22,.... }. Throughout, we model D as a multiser This is motivated by the fact that P2L's output will not depend on the order of appearance of the examples but it will account for (possibly) repeated observations. With multisets, the set operations U, \, S extend from their definitions for sets in an obvious wayF) All multisets encountered in our mathematical derivations have a finite number of elements and - denotes the cardinality where each element is counted as many times as is its multiplicity. The multiset of examples D is modeled as realization of D = {=1, ........ æN}, J. where 21, 22...... NN are independent and identically distributed (i.i.d.) random elements taking value in and detined over probability space (S2, F, P)
We wish to utilize D to construct a hypothesis from a hypothesis space H. which can be any generic space. For example, if we are tasked with making predictions the label/output of previously unseen inputs, H. can be the space of classifiers/predictors obtained by suitably parameterized neural networks. We assume to be given a learning algorithm L that maps a list of examples hypothesis (this is the inner black-box of P2L). Unlike multisets, lists come with a positional order of their elements and our approach works rigorously with learning algorithms L. whose returned hypothesis either depends on this positional order or does not. Considering list (as opposed to a multiset) as input to L gives setup that embraces the most general perspective. This is important as many commonly employed algorithms, c.g., SGD for the training of neural networks, are of the first type.
3 The Meta-Algorithm P2L
As anticipated, our goal is that of utilizing a given learning algorithm L as building block to con- struct a meta-algorithm (P2L) that induces a compression scheme with desired properties, regardless of whether the initial learning algorithm has such properties. For this, we need two ingredients: (i) an initial hypothesis ho E H: (ii) a suitable criterion of appropriateness, and a corresponding appropriateness threshold. The criterion of appropriateness quantifies to what extent given hy- pothesis h is appropriate for an example x E Z, while the threshold is used to assess - in the form of yes/no answer whether the given hypothesis h is deemed sufficiently appropriate for 2. We formalize the idea of criterion of appropriateness, and the corresponding threshold, by introducing total order Sn. over the extended set Za = Z U (Stop), where Stop is an external element that is added to Z for algorithmic reasons. Given a hypothesis h (our meta-algorithm iterates over subsequent choices of h before exiting and S.. will be used at each iteration with the current h). Sn orders the elements in Z and, in particular, allows us to determine the element that
bypothesis-dependee
This means that, c.g., {1, 1, 2] is the same as {1, 2, 1}, but both are different from {1,2) 2} because in a multisct, like in a set, there is no concept of order of the elements but account is taken of their multiplicity. 'This casily achieved using the multiplicity function na for a multiset U, which counts how many times each element of occurs in U. Then, (z)))()) = nn (2) + (z), ponu = min (nr(2)) per (2)).
and po (2) = max (0, (z) - (=)(2)), ). Finally, U C U' iff (2) S por(2) for all
'Throughout, boldface denotes random quantities and we tacitly assume that all random quantities that we introduce are measurable.
3

---

is the least appropriate. The outside element Stop is instead used to model the appropriateness threshold: h is "enough appropriate" for 2 E if Sa Stop while it not appropriate enough if Stop SA 2. Note that the two conditions cannot be satisfied simultaneously because * Stop (recall that Stop is an outside element) and SA is a total order. While remarking the generality of this setting, we provide two examples for concreteness and clarity of presentation.
Example 3.1 (Classification). Consider binary classification problem where (xt, y) with E X and y E 1). Commonly employed hypotheses (e.g., neural networks) return the probability that feature vector is mapped either of the two classes. A possible criterion measuring the appropriateness of h for is given by the cross-entropy between the label and the probability distribution returned by h in correspondence of x, (Bishop & Nasrabadi [Sec) 4.3.4]. Then, the appropriateness threshold can be used to certify if is correctly classified by h by assessing if the cross-entropy is above or below the threshold (0....)). This setting is captured by the following total order: for 21, 22 E Z, we define
Sn 22 if the cross-entropy of 21 is no bigger than the cross-entropy of 22 (and ties are broken according to any given rule), while Stop Sa if 2 has cross-entropy larger than (0.5) and x Ss Stop otherwise.
Example 3.2 (Regression). In regression, 2 = (a.,) with x E X' and, for example, y E R. In this setting, a hypothesis is typically a predictor that maps æ into an estimate ((x) for y. A possible criterion measuring the appropriateness of h for z is given by y ;(x)), while the appropriateness threshold can be specified by requiring that by - [x)) S y for given y for which the predictions are sufficiently informative. In this case, the dypothesis-dependeent total order can be defined follows.
For 21; 2/ E Z. 21 Sh 22 when 13/1 [(11) I l/2- [(22) (when 1/1 x(x1)) = 1y2 - ((22)l
but 21 * 22 the tie can be broken according to any given rule); otherwise, Stop SA when
ly - ú(z) > 7 and 2 Sk Stop when ly - x(x) < 7-
We are now ready to introduce the meta-algorithm P2L (Algorithm D. P2L works by iteratively feeding the learning algorithm L with a growing list of training examples taken from D, while terminating when the current hypothesis is deemed sufficiently appropriate (as assessed by the appropriateness threshold) for all the remaining examples that have not been used for training. If this is not the case, P2L appends to the current training examples the example among those not yet used for which the current hypothesis is least appropriate (according the criterion of appropriateness). P2L returns both the multiset 7 of the employed training examples and the final hypothesis h.
Formally, given (I,, ho, Sn). the meta- algorithm P2L is a map from a dataset D to two objects: an hypothesis h E H. and a multiset T C D. We denote this with Th A(D). P2L is composed of an initialization, and a main loop where three steps are performed. See Algorithm[]] [ where Ds = D U (Stop} and [T], is the list of the elements in T with positional order of each element corresponding to the iteration in which that element is selected by P2I..
Algorithm A(D) The meta- algoritgg P2L
1: Initialize: T= 0, h = ho, 2 = maxi, (Ds)
2:
while 2 / Stopp do
3:
T (E)
D Augment T
h L(T(()))
D Learn hypothesis D Compute max
5:
*-max (Dg \T)
end while
7: return h, T > Hypothesis h and multiset T
In the initialization, we let the multiset of training examples be empty, the hypothesis be ho- and compute the maximal element in Dg = D U (Stop) according to Sho. which we denote with = max ( Ds) F In the main loop, we first check if the maximal element is Stop. so, the meta- algorithm terminates (thus our naming Stop). Else, the training multiset is augmented with E. We then produce new hypothesis by running the learning algorithm on [T] i.e., we set h + L(T))a). Finally, compute the maximal element in Ds \ T according to the new hypothesis h, that is, 2 + max, (Ds \ T), and repeat. When the meta-algorithm terminates, it returns both the hypothesis h, and the multiset T.
We conclude with two important remarks. First, note that the choice of the learning algorithm I. ordering Sa. and initial hypothesis ho are arbitrary. Interestingly, strong generalization guarantees can be secured at this high level of abstraction (Thcorem 4.2) and this allows one to tackle multiple learning problems, including both classification and regression (Sections 5 and 6). Second, observe that the generalization guarantees we will provide rely crucially on the fact that the meta-algorithm
RRcaall that the maximal element is unique.

---

P2L possesses key feature: P2L compresses the multiset D into the multiset T, and applying P2L
D or to T reconstructs the same output.
4 Statistical Risk and Main Result
In this section we provide formal generalization guarantees on the performance of the hypothesis obtained by running the meta-algorithm P2L. Towards this goal, we introduce the notion of statistical risk, which we will then bound.
Definition 4.1 (Statistical Risk). The statistical risk of given hypothesis h E H. is R(h) = P(Stop Sa z). where a random example independent of and distributed as each z;.
Informally, the statistical risk of a hypothesis measures the probability that f is not appropriate for new, satple, example z. Given the generality of Sn. this notion can embody various specifica- tions. For instance. in the context of Example 3.T the statistical risk coincides with the probability of misclassification; in the context of Example 3.2 with the probability of misprediction above a level 7.
In the result stated below, D is seen random element (with unknown probability distribution) as to capture the variability in the dataset. Correspondingly, h is a random element and the risk R(h) random variable. Our objective is to show that R(hh can be assessed based on the compression level achieved by P2L., i.e., on the cardinality of T. We aim to make a statement of the form "With high probability 8 with respect the N i.i.d. draws generating the dataset (i.e, with respect to the unknown probability distribution of D), the statistical risk is upper bounded by E(TT), 8)", for suitable choice ... Towards defining E(,,,, we need introduce the following function 2R.5 (-o0, 1) + R indexed by k = 0, 0, N and by the confidence parameter E (0, 1):
N-1
AN
V k.
11 (1-8) (1-8)-(N-))))) (N (N-m)
e)m
2N
6N
m=
m==
where the first summand evaluates to zero when = N. We are now ready to state our main result.
Theorem 4.2 (Bound on Statistical Risk). Let (h, T) = A(D). the output of P2I., For any 5 E (0, it holds that
P(R(h) S (( 11 Ekk 6) is the unique solution to the equation Kx,((E) = 1 in the
(1)
where, for le = 0, O.......,NN ......... interval [M/N, 1), while (N, 1.
See Appendix [A] for proof. Theorem 4.2 unveils a deep connection between the level of compres- sion achieved by A, measured by the cardinality (T), and the generalization level of the hypothe- sis. Quantitatively. the link dictated by 3k: d), whose trend is exemplified in Figure for different values of 8.
1
0.8
0.6
0.4
Three important observations are in order. First, higher compression, i.e., lower [T], corresponds to better generalization guarantees. Second, the dependence of E(k, 8) on is provably logarith- mic. Hence, selecting a very small value of 8, say 10-6, i.e., asking for R(h) < E(TT), 5) hold with high confidence, say 0.999999, in practice with certainry, has little cost. Third, we notice that the bound can be applied without knowledge of the probability distribution by which data are generated (distribution-free result).
0.2
0 0
100
200
300
400
500
Figure 1: Function E(K, 6).
10
10
10 2 (top to bottom). N = 500. The dotted line is k/N.
Application to MNIST Classification
In this section apply P2L to the MNIST digit recognition problem. Our goal is compare the post- training performance and generalization bounds obtained with an implementation of P2I., PAC-Bayes and test-set approaches. The latter two are known to give the best generalization bounds to date.
5

---

More precisely, we consider binary version of the MNIST dataset introduced in the seminal work of (Dzuugate Roy 2017) for the specific purpsse comparing the generalization guarantees of PAC- Bayes and other approaches, and later employed in, e.g., (Rivasplata et al. 2019). In this problem, the digits 0-4 and 5-9 are mapped the labels and To classify the imputs, we employ fully connected ford-forward neural network with three hidden layers each with 600 nodes and ReL.u activation functions. The input has 784 nodes and the output has two nodes which are passed to a softmax function. This architecture, employed in the above-cited works, is used across all our experiments.
= 0.035
0.001
0.3
0.3
Risk
0.2
Risk
0.2
0.1
0.1
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Train/pretrain portion
Train/pretrain portion
0.3
0.3
Risk on the test dataset
Risk on the test dataset
0.2
0.2
0.1
0.1
0
0
0.1
0.2
0.3
0.1
0.2
0.3
Bound on risk
Bound risk
Figure 2: Top Average bounds the risk (dashed) and misclassification the test dataset (solid) + one standard deviation for P2L O, test-set O, and PAC-Bayes A with a confidence of ô 0.035 (left) and 6 0.001 (right). The solid markers denote the best bounds achieved and their corresponding post-training performance. Bottom row: Distribution of the upper bounds on the risk and misclassification
the test dataset for the models achieving the best bounds for P2L test-set +, and PAC-Bayes +. Precisely, each point in these figures corresponds to the pair (generalization bound, actual misclassification level) achieved in one of the 60 partitions of the MNIST training dataset we use. The means are indicated with a solid diamond, circle, and triangle, respectively.
MNIST consists of a training dataset containing 60000 examples and test dataset with 10000 examples. In our experiments, we train all models only on 1000 samples from the training dataset time. We particularly care of this "small" dataset setting, which one has to make the most of the data for both training and assessing the generalization. This is setting of interest to various fields where data are a limited, possibly costly, resource Specifically, we shuffle original MNIST training dataset and extract 60 disjoints datasets with 1000 data points each. All approaches we compare are run on the resulting 60 datasets, which are used to both train the network and provide generalization bounds. The full test dataset, containing 10000 examples, is never used in any training phase. instead used to evaluate the actual post-training performance of each trained model. We
*Our experience ranges from applications to cardiac defibrillation in which patients in out-of-hospital cardiac arrest are classified as being able not able to positively react to a defibrillation shock (in the latter, alternatives are possible, chiefly administrating cardiac massage prior to the shock), to applications with spacesuit testing in which suits artificially bombarded with particles mimic the condition encountered in the outer space. While in the first example the number of recorded cases potentially very high (modern defibrillators automatically collect ECG traces), still these data not made public and easy to secure in large quantities, while in the second example each single data point can be quite costly, suggesting that the dataset has to be kept small possible.

---

now present the specific algorithmic choices made for P2L. Due to space limitations, the details concerning the test-set approach and PAC-Bayes can be found in Appendix [..]
P2I. As discussed, P2L is fully specified once a learning algorithm L, an initial hypothesis ho. and hypothesis-dependes
total ordering Ss. with criterion of stop defined. For the learning algorithm L, we choose the widely employed GD (gradient descent) with momentum, which we run for 200 epochs with a learning rate of 0.01, momentum of 0.95, dropout probability of 0.2. For the sake of clarity, we remark that each time GD is called by P2L, GD iterates until convergence (or until reaching the allowed number of epochs) so as to perform the minimization of the empirical risk. As initialization of GD, we take the h returned at the previous iteration of P2L Regarding yu it clear that when starting from an educated guess the choice of the worst example to be inserted in T tends to be more meaningful, allowing P2L to terminate with smaller T and, thus, better generalization bound. To this purpose, one can use a portion of each training dataset to pretrain ho (using GD again), while P2I. and, therefore, the ensuing generalization bound rely on the remaining part of the training dataset. In our computation, we experiment with multiple sizes of the pretraining portion. As for Sh. given an hypothesis h, i.e., neural network, we use the total order induced by the cross-entropy of its output as discussed in Example 3.1 (ties are broken according to the lexicographic order of the examples' bit representation). This choice ensures that the statistical risk of Definition 4. corresponds to the probability of misclassification, and thus a bound on the statistical risk coincides with bound on the misclassification. The final bound we present on the misclassification is that of the main result in Theorem 4.2 where the number of samples equals N minus those used to pretrain the initial hypothesis ho-
Experimental results. The results are presented in Figure 2 for different values of the confidence. The top row depicts, the average (over the 60 trials) generalization bounds as well as the average misclassification levels on the test dataset (post-training performances) with their dispersion for the three approaches. The values are plotted as functions of the portion of the dataset (called train/pretrain portion) used to train the the model in GD+test-set, to pretrain the prior distribution in PAC-Bayes, and to pretrain the initial hypothesis hgg in P2L. The joint distribution of the returned bound and actual post-training misclassification level for the best models (corresponding to train/pretrain portion equal to 0.5, 0.6, 0.7 for P2L. PAC-Bayes, and test-set approach, respectively) are shown in the bottom row The average bounds and misclassification levels for these best models are also presented in Table [ for 8 0.035. For the sake of completeness, Table also reports the average running times of one execution (i.e., for one dataset with 1000 examples) of the three approaches (computational resource: Apple MacBook Pro with M1 Pro CPU and 32Gb of ram).
Table 1: Risk of best models for 8 = 0.035. Risk on the test dataset Difference
Bound on risk
Average running time
P2L
0.143
0.072
0.071
2m Is
Test-set 0.129
0.079
0.050
Om 5s
Pac-Bau Pac-Bayes 0.177
0.088
0.089
4m Is
Conclusions. Four important observations are in order. First, it is evident that, in the present application, the implementation of P2L with GD outperforms the PAC-Bayes approach with respect to both the provided upper bound on the risk and the post-training performance the test dataset. This is true not just for the best model learned with each approach (cfr. the solid diamonds and the solid triangles in Figure 2). but it holds uniformly across all train/pretrain portions we tried (cfr. the green and red curves). Notably, the model returned by P2L+GD when using only 10% of the data to pretrain the initial hypothesis ho has risk bound that is comparable to that of the best PAC-Bayes model (whose prior is trained on 60% of the data) while it achieves a better post-training performance. Second, P2L+GD provides best risk bounds that are comparable to those of GD+test-set approach, albeit slightly inferior (0.143 vs 0.1 for = 0.035 and 0.163 vs 0.155 for 5 = 0.001). However, P2L+GD provides better post-training performance uniformly across all train/pretrain portions. As matter of fact, for any choice of pretrain portion, P2L+GD's performance is equal to that obtained when GD is run the whole data set (N- 1000), for which the test-set approach cannot provide
As an alternative, one could also re-train model from seratch every iteration. This implementation of GD can be seen as a slightly different choice the inner algorithm L for P2L. The selected implementation of GD is motivated by the ensuing computational advantage, since fewer gradient steps are typically needed to converge, and the fact that this implementation makes h less sensitive to the addition of one example in T', which is helpful in later stages of P2L to speed up its termination.
7

---

any meaningful bound since no data are left for testing the model. This is a clear indication of the important feature that P2L utilizes all data to jointly learn a good model and provide risk bound. Third, the post-training performance of PAC-Bayes and GD+test-set approaches are similar. This suggests that in PAC-Bayes the training of the posterior does not exploit the additional available data to improve the model, but rather to certify it, in a similar vein as in the test-set approach. This fact has also been observed recently in (Lotfi et al. [Fig [(a).. Fourth, as for the tightness of the bounds (i.e., the difference between the upper bounds and risk on the test dataset), GD+test-sct approach provides the tightest results, while P2L+GD and PAC-Bayes approaches alternate depending on the specific train/pretrain portion selected.
6 Application to synthetic regression problem
In this section we apply methodology to syn- thetic regression problem in order to showcase the flexibility of the approach introduced in Section 4
Examples
1
Specifically, we consider 100 distinct training datasets with N 200 examples (x, y) and then another 100 distinct training datasets with N 500 examples (z, y). The input
y (x)
P2L
y 0.5
Test-set
[-0.5,1.3] is extracted uniformly at random and the output is y f(x)+++ +e with fxx) sin(2.5mxx) //.5x//(mmmm)))))) and e extracted according to a normal distribution with zero mean and standard deviation 0.05, see F For each dataset, our objective is twofold: finding model that fits the data well, and providing a bound on the probability that the model mispredicts the output by more than threshold y = 0.1 (bounds of this sort matters in relation to many applications).
0
-..5
0
0.5
1.5
Figure 3: gression. The crosses are examples (z, y). The black line depicts the function fax = (in(2.5xz//(2 (2.5)))) around which noise is added. The red dashed and blue solid lines represent the fit obtained with a choice of train/pretrain portion equal 0.3 (best) for P2L and test-set approaches. The red shaded re- gion depicts tube of radius 0.1 around the red model. The risk of the red model is the probability that an unseen example falls out- side the shaded region.
An instance of dataset used for re-
In pursuing this goal, we compare the generaliza- tion bounds and post-training performances attained using P2L and test-set bounds. For illustration pur- poses, in all our experiments we consider a simple network architecture comprising one input node, one output node, and one hidden layer with six nodes, each equipped with a tanh activation function. To evaluate the post-traing tost-training performance, we use an additional test dataset with 20000 examples. The value of ò is set to 0.035.
P2L. In deploying P2L we use GD as learning algorithm L, and, similarly to the MNIST example, we experiment with initial hypotheses fng trained on different fractions of the training dataset (including the null fraction in which case ho is the network with all weights set to 0). We fix the same total order Sa. of Example 3.2 with 7 0.1. In this context, the risk introduced in Definition 4.1 measures the probability that the output y is mispredicted by more than 7 thus giving us a guarantee on the quality of the model. The generalization bound we use is that in Theorem 4.2] where the number of samples equals N minus those used to pretrain the initial hypothesis hg. We use a learning rate of 0.1, momentum of 0.95, 1000 epochs, and dropout.
Test-set approach. We apportion each dataset in two, with one portion used for training, and the other for deriving the generalization bounds. We run GD for 1000 epochs, perform grid search over learning rates [0.001, 0.005, 0.01], momentum [0.9, 0.95] (no dropout), and select those giving the best generalization bound. As in the MNIST example (see Appendix [B.I) we use the binomial test-set bound of (Langford [T0m 3.3] with a number of samples equal to N minus those used for training.
Experimental results. The first two panels of Figure present the average (over the 100 trials) upper bounds on the risk and the average risk on the test dataset jointly with their dispersion, as a function of the data portion used to train the model (GD+test-set) or to pretrain the initial hypothesis (P2I.). The third and fourth panels depict the distribution of the upper bound and of the risk on the test dataset
8

---

N 200
N 500
0.4
0.4
0.3
0.3
Risk
Risk
0.2
0.2
0.1
0.1
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Train/pretrain portion
Train/pretrain portion
0.4
0.4
Risk on the test dataset
Risk on the test dataset
0.3
0.3
0.2
0.2
0.1
0.1
0
0.1
0.2
0.3
0.4
0.1
0.2
0.3
0.4
Bound on risk
Bound on risk
Figure 4: Top row: Average bounds on the risk (dashed) and risk on the test dataset (solid) + one standard deviation for P21. O and test-set O approaches, with 200 (left) and N 500 (right). The solid markers denote the best average bounds and the corresponding risks the test dataset. Bottom row: Empirical distribution of the bound and risk on the test dataset for the data split returning the best average bound for P2L + and test-set +. Their means indicated with solid diamond and circle, respectively. Note that the test-set approach not considered for zero train portion, as it always requires non-zero amount of data to train the model. Observe that three instances in the test-set case (out of one hundred) in the bottom row violate the upper bound. This is in line with the choice of 8 0.035, suggesting that the bound will fail, average, 3.5 datasets out of one hundred.
for the data proportion 0.3, returning the best learned models for both P2L and the test-set approach. Their averages are compared in Table 2 which also includes the average runtime (computational resource: Apple MacBook Pro with MI Pro CPU and 32Gb of ram).
Table 2: Risk of best models for N = 200, 8 = 0.035
Bound on risk Risk on the test dataset Difference
Average running time
P2L Test-set
0.172
0.064
0.108
1.18s
0.250
0.173
0.077
0.21s
Conclusions. First, appears evident that, in this synthetic regression problem, the application of P2L with GD provides superior results to those achieved by GD with the test-sct approach, regardless of the size of the datasets used for training. This holds true jointly for the upper bound and the risk the test dataset uniformly across all train/pretrain portions (cfr. the red and blue dashed lines, similarly for the solid ones). We ascribe this result to the fact that P2L does not set aside data for testing, and yet it also provides rigorous evaluations the risk. Second, the test-set approach provides bounds that are closer the risk it incurs the test dataset for N 500, while this effect is less clear with N 200. Third, as expected, when the size the training dataset grows, both the upper bounds and the risk the test dataset improve.
To conclude, it is fair to notice that GD does not pursue directly the goal obtaining prediction error smaller than 7, and this may justify the large gap in the post-training performance between

---

the two approaches also when almost all the dataset is used for training in the test-set approach. Although GD is used as inner algorithm L in P2L, it seems that good performance with respect to the chosen appropriateness criterion can be obtained thanks to the structure of the meta-algorithm. This is another interesting feature of P2I..
Conclusions, Limitations and Future research
We have proposed a novel framework called P2L to provide virtually any learning algorithm with sharp generalization bounds. Our approach is based on making a given learning algorithm into a compression scheme with desirable properties, thus enabling the of powerful generalization results. Numerical results show that P2L capable of learning hypotheses with post-training performances and generalization bounds equal superior to the state of the art.
Computational aspects. While P2L requires learning a hypothesis over a training set of increasing size, and thus might be less efficient than learning the hypothesis only once over the full dataset, it is important to look at it from the appropriate perspective: we are concerned with settings where data is limited or costly to acquire (see, c.g., Footnote 6 and ensuing discussion) while computations performed off-line and fast execution does not represent a primary concern (a setup also considered in other recent work, c.g., (Foong al. (02T).
Source of conservatism. In our framework, as revealed by the proof of Theorem 4.2 the risk is controlled by bounding the probability of change of compression (as defined in Equation (2) in Appendix A.T]. Notably, the mismatch between the risk and the probability change compression is the only source of conservatism our approach needs to resolve since the upper and lower bounds on the probability of change of compression from Theorem A.44 exiremely light - see Remark A.9 The magnitude of this conservatism is determined by the choices we make in specializing the proposed meta-algorithm. For a given learning algorithm L, these choices entail selecting an initial hypothesis ho and hypothesis-depeee dependent total order used to select which data points are fed to the learning algorithm L. Our experimenting with multiple initial hypotheses (trained with different portions of the dataset) was solely geared at reducing this gap. Indeed, after training ho. P2L allows the data to "freely speak", and thus improve the resulting hypothesis, as it can be appreciated from the fact that the misclassification
the test dataset for P2L is constant across all prior/train portions (see Figure [ top row). This is in stark contrast with the test-set approach and even PAC-Bayes. In the former, data either used to train the model the posterior are effectively used to compute a risk bound as opposed to significantly improving the quality of the prior (see first row in Figure 2 We conclude noting that our choices of the initial hypothesis and total order is but one of many possible. Depending on the specific learning problem, other choices can be made (see for examples the last part of the Introduction). We believe that the overall fact that the theoretical apparatus in our approach clearly identifies the sole source of conservatism will put us and others in the position build upon the P2L framework beyond this work.
provide a risk bound. In the latter, data employed train
Acknowledgments
This paper was partly supported by FAIR (Future Artificial Intelligence Research) project, funded by the NexIGenerationBU program within the PNRR-PE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence); and the EPSRC grant EP/Y001001/1, funded by the International Science Partnerships Fund (ISPF) and UKRI.
10

---

References
Bartlett, P. L. and Mendelson, S. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463-40 482, 2002.
Bishop, C. M. and Nasrabadi, N. M. Pattern recognition and machine learning, volume Springer, 2006.
Bousquet, O., Hanneke, S., Moran, S., and Zhivotovskiy, N. Proper learning, Helly number, and an optimal SVM bound. In Proceedings of 33rd Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 582-609, 2020.
Campi, M. C. and Garatti, S. Compression, geririlizannnniiiiiinon and learning. Journal of Machine Learning Research, 24(339):1-74, 2023.
Clerico, E., Deligiannidis, G., and Doucet, A. Conditionally gaussian PAC-Bayes. In International Conference on Artificial Intelligence and Statistics, pp. 2311-2329, PMLR, 2022.
Cortes, C. and Vapnik, V. Support vector networks. Machine Learning, 20:273-297, 1995.
Dosovitskiy, A., Beyer, L.,, Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.1199 2020.
Dziugaite, G. K. and Roy, D. M. Computing nonvacuous generalization bounds deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 703. 1008, 2017.
Floyd, S. and Warmuth, M. Sample compression, learnability, and the Vapmik-Chervonenkis dimen- sion. Machine Learning, 21 21:269-304, 1995.
Foong, A., Bruinsma, W., Burt, D., and Turner, R. How tight can PAC-Bayes be in the small data regime? Advances in Neural Information Processing Systems, 34:4093-4100 2021.
Graepel, T., Herbrich, R., and J.Shawe- Taylor. PAC-Bayesian compression bounds on the prediction error of learning algorithms for classification. Machine Learning, 59:55-76, 2005.
Hanneke, S. and Kontorovich, A. Stable sample compression schemes: New applications and an optimal svm margin bound. In Proceedings of the 32nd International Conference Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pp. 697-721, 2021.
Jumper, J., Evans, R., Pritzel, A., Tim Green, M. F., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., Bridgland, A., Meyer, C., Kohl, S. A., Ballard, A. J., Cowie, A., Romera-Paredes B., Nikolov, S., Jain, R., Adler, J., Back, T., Petersen, S., Reiman, D., Clancy, E., Zielinski, M., Steinegger, M., Pacholska, M., Berghammer, T., Bodenstein, S., Silver, D., Vinyals, O., Senior, A. W., Kavukeuoglu, K., Kohli, P., and Hassabis, D. Highly accurate protein structure prediction with alphafold. Nature, 596:583-589, 2021.
Keskar, N. S., Mudigere, D., Nocedal, J., Smelyanskiy, M., and Tang, P. On large-batch training for deep learning: Generalization gap and sharp minima. In Proceedings of the International Conference on Learning Representations (ICLR), 2017.
Kononenko, I. Machine learning for medical diagnosis: history, state of the art and perspective. Artificial Intelligence in medicine, Elsevier, 1:89-109, 2001.
Langford, J. Tutorial on practical prediction theory for classification. Journal of machine learning research, 6(3), 2005.
Li, Y.. Yu, R. Shahabi, C., and Liu, Y. Diffusson convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint arXiv:1707.0192: 2017.
Littlestone, N. and Warmuth, M. Relating data compression and learnability. Unpublished manuscript, 1986.

---

Lotfi, S., Finzi, M., Kapoor, S., Potapezynski, A., Goldblum, M., and Wilson, A. G. PAC-Bayes compression bounds tight that they can explain generalization. arXiv preprint arXiv:2211.13609, 2022.
Paul, M., Ganguli, S., and Dziugaite, G. K. Deep learning data diet: Finding important examples early in training. Advances in Neural Information Processing Systems, 14-20596-20607 2021.
Perez-Ortiz, M., Rivasplata, O., Shawe-Taylor, J., and Szepesvari, C. Tighter risk certificates for neural networks. Journal of Machine Learning Research, 22:1 2021.
Rivasplata, O., Tankasali, V. M., and Szepesvári, C. PAC-Bayes with backprop. arXiv preprint arXiv:1908.07380 2019.
Smola, A. and Schölkopf, B. A tutorial on support vector regression. Statistics and Computing, 14: 199-224, 2004.
Toneva, M., Sordoni, A., Combes, R. d., Trischler, A., Bengio, Y., and Gordon, G. An empirical study of example forgetting during deep neural network learning. arXiv preprint arXiv:1812.0511 2018.
Vapnik, V. and Chervonenkis, A. On the uniform convergence relative frequencies of events to their probabilities. Theory of probability and its applications, 16:264-280, 1971.
Wu, Y.-.. and Seldin, Y. Split-kl and PAC-Bayes-splitkkl inequalities for ternary random variables. In Proceedings of the 35th conference on Advances in Neural Information Processing Systems (NeurIPS 2022), 2022.
Xu, A. and Raginsky, M. Information-theorrtie analysis of generalization capability of learning algorithms. In Proceedings of the I Conference on Neural Information Processing Systems (NIPS), 2017.
Yang, S., Xie, Z., Peng, H., Xu, M., Sun, M., and Li, P. Dataset pruning: Reducing training data by examining generalization influence. arXiv preprint 2rX1v:2205.00332,, 2022.
12

---

Appendix
A Proof of Theorem 4.2 and Additional Results
In this section prove Theorem En route to this goal, we will also present additional results that help better position our contribution. Doing so will allow us to highlight directions where we believe there is room for exciting future work. The section is conceptually divided in three portions: in Appendix [ we recall a relevant result from (Campi Garatti 2023) along with the necessary mathematical background; this result is then leveraged in Appendix A.. A..2 to prove Theorem 4.2 and other related results; finally, in Appendix [A.4 we revisit the P2L framework the light of some technical details revealed by the proof of Theorem 4.2
A.1 Preferent Compression Gives Tight Risk Bounds
We begin with introducing two properties of a compression function с (preference and non- associafivity) and the property of non-concentrated mass from which strong generalization guarantees follow. Recall that compression function с is a map from any multiset 1) of elements 2 to a sub- multiset c(D) C D Throughout, we c(D, =) as shorthand for c(D U {z}), and likewise for c(D, 2p)) Moreover, denotes random example independent of and identically distributed as each zi. Property A.1 (Preference). For any pair of multisets V and of elements of 2 with D. <(D) #V = c(D, + V, V2 E Z.
Zp).
The preference property asserts that, if the multiset V was not chosen when compressing D, it will also not be chosen when compressing the set augmented with one more element z. Under the preference property, it is easy to prove that c(c(D)) c(D), i.e., the compression of compressed multiset must be the compressed multiset itself.
Property A.2 (Non-associativitty. For any multiset D of elements of Z and for any 21, , E Z, p c(D, 2) c(D), Vi E [l....,p} p = c(D, 21.,...... ................................ zp) c(D).
The non-associativity property ensures that, if the compression does not change by adding one element at time, it must also not change when adding all the elements together
Property A.3 (Non-concentrated mass). P(z =} 0, Vz E Z.
The property of non-concentrated mass ensures that every point E 2 is drawn with probability zero.
Under these three properties, strong results on the probability of change of compression, formally defined as
D) = P(c(c(D)) c(D) D}
(i.e., change of compression occurs when the compression of c D) augmented with one element is different from (D)) are established in (Campi & Garatti 2023
Theorem A.4 (Thm. in (Campi & Garatti 2023 5 E (0, 1),
Assume Properties
Then, for any
PP (( where e(k, 8) for k = 0, 1,.,...,
S (DD) s e((c(D)), 2 8,
(3)
......... N while Z(N, 8) 1, and g(k, 5) for k 0, 1......, N is the maximum between O and the unique solution to V (s) = 1 in the interval (-oo, k/N) (function V2,((E) is defined in Section 4.
is the unique solution to (x, = 1 in the interval [K/N, 1].
The previous statement asserts that, with probability 5 over the draws of D, the probability of change of compression is contained in an interval with upper and lower extremes given by E(k, 5)
Note that this definition, and the properties that we shall introduce later in the section, apply not only to the multiset of actually observed examples, they apply to arbitrary multisets of any cardinality. Although we have used D to avoid proliferation of the symbols, D is used here, and elsewhere when needed, to denote generic multisets.
"Theorem A.4 continues to hold if the non aa--asociativityy property is required to apply P-almost surely (as opposed to realization-wist We use realization-wiz wise version for the sake of simplicity and also because this formulation suffices for the goals of this paper.
13

---

and E(k, 6), where l is evaluated at the cardinality of the compression of the draw, Prompted by one of the reviewers, we gladly provide a concise outline of the proof structure for Theorem A. in the following Remark A.5
Remark A.5 (Gist of the proof of Theorem A.4 The proof of Theorem A.4 in (Campi & Garatii
2023) starts by associating any compression scheme that satisfies Properties A.7 1o to A.3 proba- bility measure from which one can compute IP <((c(D) 5) S ((D) S a(|c DJ
and then by characterizing the class of all such probability measures in terms of certain conditions. The next step consists in obtaining an upper bound to P PeE((c(D)), 5) S (D) S EE((((D),, 5) } by maximizing this quantity over the class of probability measures that has been previously characterized. The ensu- ing maxinization problem is infinite dimensional and its solution is obtained by duality. Interestingly, no conservatism is introduced this stage because strong duality holds. See (Campi & Garatti
2023) for details.
The interest of Theorem A.4 in the context of statistical learning lies in the fact that, whenever the compression function ties in with the learning algorithm so that inappropriateness (e.g., misclas- sification or misprediction) implies change of compression, then the probability of inappropriate examples dominated by the probability of change of compression and, therefore, it can be upper
bounded with high confidence based on (3). See also Section 4 in (Campi & Garatti| 2023). This means that we can prove Theorem 4.2 by exhibiting a compression function that enjoys the result of Theorem A.4 and for which whenever hi( D) is inappropriate for i.e., Stop SA(D) 2, we also have c(c(D), 2) c(D). This is indeed the demonstration path pursued in the next Appendix A.2
A.2 Proof of main result
Note that Theorem 4.2 does not assume the non- non-concentrated mass Property A.3 To ease the
presentation, however, Theorem 4.2 will be first proven by assuming Property A.3 which allows
for a more direct application of Theorem A.4 later, we will show how this extra assumption can be
removed.
Suppose thus for the time being that Property A.3 holds true. Throughout this section, we denote with C the compression function obtained by A when it compresses multiset D into T C D (recall that (h, T)- = A(D)). We show that C.A enjoys the preference and non-associativity Properties A. and A.2] This licenses the use of Theorem A.4 obtain upper and lower bounds on the probability of change of compression. We shall then relate these bounds on the probability of change compression to the statistical risk as in Definition 4.1 so closing the proof when Property A.3) is assumed. We
shall use A(D,2) 2) and CD(DD2) 2) as shorthand for A(D U {z}) and CA (2)).
We begin by showing that ca(() is preferent.
Lemma A.6. The compression
C satisfies the preference Property A.
Proof. Consider multiset D of elements of 2 and further let E 2. Suppose that C.A (D.z) + c (D). Our goal is to show that in this case (D, * V for any V C D, from which Property A. immediately follows.
Denote by Tk, hy and Tú Aig the multisets T and hypotheses h constructed in A(D) and A(D,z), 2). respectively, iteration & of the "while" loop. To = 0 = TV and ho = hi instead denote the empty multisets T and initial hypotheses in the initialization step. Finally, let D/ = Ds U (z} (where we recall that D3 = D U (Stop)).
Since (D, =) A caa there must exist a 1: 2 such that the executions of A(D) and A(D,=)
match for & < 1e (which implies that T/ = Tk and Ayg- = h2 for A: < R), but they differ at iteration
because, for A: = k., the maximal element computed in A(D) (line 5 if k 2 1 or line 1 if = 0) is different from the one computed in A(D,=) 2). That is, maxig (Ds TT)) # max (D's T =
maxkg (D's \ TT)) where the last equality holds because, as previously noticed, T/ T and h hū- We claim that it must be that max,, (D's TT) = = and = & D3 T Indeed, if this was not the case, would be that maxi: (D's (TT) D3 .Tg which would imply that max (D')TT) maxi, (Ds
since D3 \ Th C D' \ Te. The latter would contradict max,, (Ds TT)) A max (D's \ Tt)) Since max (D') \ TR) a Stop, a(D,z) executes at least one more iteration after the k-th, and
14

---

$ Ds \ Tg yields that T+ = T3 U {2} contains the element as many times as it appears in D [={=), i.e., as many times as it appears in D plus one. Therefore T T & D and, since the multiset Ty is increasing with k must be that T g D for all 2 ++1. This implies ca(D,z) g D; that is, CA(D, 2) + V for any V S D.
We now show that C, non-associative. Lemma A.7. The compression function с satisfies the non-associativity Property A.2
Proof. Fix any multiset D of elements of 2 and further let 21,-..:22 2p 2. We will prove the claim by contrapositive. Towards this goal, assume that CA(D, 21,..., xp) + cA(D). We will then show that there exists an i .I,...,,1 p} such that (D, 21) + C We first focus on the executions of A(D) and A(D, 21...., 2p). Similarly to the proof of Lemma A.6 denote by Tk: hy and T(T), ( the multisets and hypotheses constructed A(D) and A(D, ... =p), respectively, at iteration k (k: = 0 corresponds to the initialization). Finally, let Dg = Dg U (z1,...,Zph, Since EI(D,z1...... :zp) + CA(D)), also in the present context there must exist a K such that the executions of A(D) and A(D, .i......p 2p) match for is (so that 73 T and hus hg for k S k), but they differ at iteration le because, for k = k. the maximal element computed in A(D) (line 5 if l 2 or line 1 if k 0) is different from the one computed in A(D, ..,....,,,))) zp). That is, maxn, (Ds Th) * max, (D T(P) Then, following an argument identical that in the proof of Lemma [A.6] one observes that it must be that max, (D=") T = for some E (1..... and 2; $ D3 TE-
Now compare the executions of A(D) and A(D, z:), and denote by T hig. the multiset I' and the hypothesis h constructed in the execution of A(D, 2;) at iteration k (A: = O still corresponds to the ini- tialization). Further, let D2- Ds U ) One can first observe that also the executions of A(D) and A(D, 2i) for < & must be identical. Notice indeed that: T3 = To = T(()) and hi = hn = nig (P) (P) for k < k. the maximal element selected at
i. when T' Th I((P) and hi h2 = =n iteration & of A(D) and A(D, 2.) is the same since this is so for the maximal element of A(D) and A(D, ... 2p) and Dg Th S D's \T C DDP) T(P);
iii. this in turn gives T241 TT+1 Tk+1 (p))
and M/41 = het1 (p)
k+11 At iteration k instead, the identity of executions ends, and it must be kig (D') ( = z; because 2; is maximal over ( (:(P) and E D's T S D \ VT("")
(surely 2 still belongs to D' Th because T/ = TE S and Dig DU {z) (Stop)). Further, recall that 2; & D3 \ Tg. Since A(D, =1) executes at least one more iteration after the k-th (because z # Stop) and since the T 's are increasing, we have that any T/. for 2 + 1 is different from any of the Tg's 's. This implies c =,) + (D)) thus concluding the proof.
Given that Properties A.I and A.2 hold true, and since Property A.3 is assumed, Theorem A.4 applies, yielding P(E( D ))))) < (D( S E(Ic((D),, 5)} 2 1-
6- -, where A P(c,(c.(D),2) * (D( D}. As anticipated, to obtain from this the sought result for the statisti- cal risk, it is enough to show that, given D and the hypothesis h returned by A(D), every realization such that Stop SA 2 also changes the compression, i.e., cu(cu(D),2) + CD)... As a matter of fact, this implies that for every D the event (Stop Sn. =} is sub-event of (c)(c.(D), & (D)), and hence that R(h)= S (D) almost surely. Then, Theorem 4.2 claim readily follows since
P(R(h) s (E)), P()a(D) S (e(lc(())),))
WM
P(E((ca(D) (D) (D( s (D))
w 1-
Thus, we are left to prove the following lemma. Lemma A.8. Let be any multiset of elements of 2, 2 E 2 be any example, and (h, = A(D). If z is such that Stop Sn. 2, then cA(cA(D), 2) * (D))
15

---

Proof. We prove the contrapositive and show that, if 2 is such that cx(ca(D), - ca(D), then 2 S. Stop.
Note that (h, T A(D) means that T = (D) and h = M([T]A) thanks to line 4 in Algorithm
Consider the execution of (() (z))). By definition of c.A. the condition c (
(D) means that A(c U {2}) terminates with (D) = T. Hence, the maximal elements are the same as those selected by A(D). Further, by the properties of max operators, the elements selected by A(c J {2})
selected by (D) U {z})
and A(D) match at each iteration. This implies that A(c (D) (z)) terminates returning h, besides T. For this to occur, must be that Stop (line 2). This is equivalent to max; (f Stop)) = Stop,
max, (
ie., 2 Sn Stop.
Having proven Lemma A.8 we have completed the derivation of the main result under the additional assumption that Property holds true, an assumption that, however, does not appear in the statement of Theorem 4.2 To remove this assumption, and thus complete the proof of Theorem 4.2 we can proceed as follows.
Augment each random element 2; with a random variable u, that is uniformly distributed over [0, 1] and independent of z;. Moreover, define the u; 's so that the random elements 21, .2...., ΣN, where 2, = (z,, u.) for all i, are independent and identically distributed (i.i.d.). Also, let 2 (z, u) be independent of and identically distributed as each E.. Let 2 2 x [0, 1]. which is the space where the 2;'s 's take value. For any 2 = (z, 2) E 2 and '' = (z/, u') E 2 define & Sa. E' 2 Sn and u', while define - S Stop [resp. Stop SA 2] if Sn Stop [resp. Stop Sn 2]. Also, for any n, define L( ) (221..... 2n), where
(z,, u.), i 1, ...... n, are elements of Z.
Consider now the executions of A over multisets of elements of E according to the redefinition of Sa and L, and let (h, T' A(D), where D 1 _v J. As is clear, the non-concentrated mass Property A.3 applies for the 2,'s and an application of the results obtained so far gives P(((h) v (TT),)) 2 1- - 6, where Rh) = P' Sn z}. On the other hand, by virtue of the redefinition of SA and L. one can notice that, for every realization of D, the execution of A(D) matches step by step that of A(D), with the sole difference that elements in T that are otherwise indistinguishable are incorporated in T with their "u" counterparts (and the highest values are selected first). Thus, the multiset T is equal to the multiset of the "z" components of the elements of T, yielding (T) |T. Moreover, since the addition of elements in T and T occurs in the same order, we also have that h h. Finally, noticing that R(h) R(h) because SA Stop } Sh. Stop. one has that
((R(h) S ((((). (P)(() E [()))) 2 6,
and this concludes the proof of Theorem 4.2
Remark A.9 (On the tightness of Theorem 4.2 Although both upper and lower bounds that hold with confidence 1 - ö are available for the probability of change of compression, only the upper bound ports over to the statistical risk, because any realization for which Stop Sh. z (i.e., realization that is inappropriate) is also a realization that changes the compression, but the opposite does not hold. Given that the lower and the upper bounds are provably close to each other even for relatively small values of N, this means that E([T), 8) is an accurate evaluation of the probability of change of compression, but it can be loose for the statistical risk whenever this deviates from the probability of change of compression. Interestingly, this is the only source of looseness in the evaluation of the risk provided by Theorem
A.3 An extension of P2L: adding multiple examples in T simultaneously
A simple extension of the meta- meta-algorithm P2L described in Algorithm consisss in adding at every iteration multiple, say
1, examples in T at a time. A possible implementation then formalized in Algorithm 2 below, where max (U)) returns the R maximal points (the maximum, the 2nd maximum, the R-th maximum) of U according to the total order Sn (if U has less than elements, then the whole U is returned).
16

---

Algorithm (D) Meta-algorithm P2L with R examples added time
1: Initialize: T 0, h ho. ,,,...,, AR + max Rt (Ds)
2: while * Stop for all = = do
3: T + TUTU (?,.. Zn}
b Augment T Learn hypothesis >> Compute max
4:
h L(TTA)
5:
, & max; (Ds \2)
end while
7: T' TUTU 2 24 Stop)
D Complete '' Hypothesis and multiset T
return h T
Interestingly, Theorem 4.2 continues to hold true (with modification in the statement) also when the pair h, T the output of Algorithm 2 instead of Algorithm [ To prove this, it is enough to observe that Algorithm is completely equivalent to the following sequential Algorithm 3 which is identical to Algorithm I so that only one point added to at each iteration, except for the fact that f is updated every R iterations (mod R) is the remainder of the division of iter by R). This equivalence secures the result because the proof of Theorem 4.2 can be repeated for Algorithm word for word, without any modification.
Algorithm 3
Initialize: T 0, h 2: while : + Stop do
hg. - maxi, (Ds), iter
iter + iter +
4: T + TU {z}
Augment T
if mod(iter, R) 0 then
6:
h < A((T)A)
Learn hypothesis
end if
8:
E < max, (Ds \ TT)
Compute max
9: end while
10: return h,
Hypothesis h and multiset T
As is clear, Algorithm| Tis a particular case of Algorithm Sasiimmm@simi since the former is re-obtained from the latter when R = 1. We notice that adding more than example to T at every iteration might might not have beneficial effect on P2L. Indeed, on one hand, adding more examples simultaneously might result in building better h earlier (and save computational time). However, by introducing examples in groups (and thus not allowing for the fine-grained choice of adding them one-by-one) might also result in larger T, which could worsen the final bound the risk. In this regard, modulation of A across iterations seems to be a promising line of investigation, which however is beyond the scope of the present paper and is therefore left for future work.
A.4 discussion on the P2L framework in retrospect
reveals that these two lemmas strongly rely on the fact that the max, operator a compression function from many elements to just one with the following properties: i) it is preferent (as matter of fact, for any multiset A and additional element either max, (A U {6})
A close inspection of the proofs of the key Lemmas A.6]and reveell
or max (A {b}) = max, (A)); and ii) it non-associative (max, (A U {b:)) max, (A) for all i E {1, {1,..., p implics that there is an element ā of A such that c Sn a for all E AU {bi,..., .ay....,,,, b,} and, therefore, max, (A (bi..... ,,,,) = max, (A)).
Importantly, these are the only two properties of max, that are used and, therefore, one could have formulated Algorithm [ in an (apparently, see below) more general form: instead of introducing depeeeesisddependent total ordering Sh. one might have considered in its place a hypothesis- dependent preferent and non-associative compression function from many to one example. Mulatis mulandis, Theorem 4.2 and the arguments to prove it would have remained the same. This gener- alization extends to the context which multiple examples are selected at a time as suggested in Appendix A.3
17

---

We feel advisable to also notice that the above generalization is indeed a real generalization only in the case of selection of multiple example a time. Instead, in the context of one example selected at time the alternative setup illustrated above turns out not to be more general than that of Section + (this why we wrote "apparently" in parenthesis). In fact converse property holds: any compression function from many examples to one that is preferent and non-associative always defines a total ordering whose notion of max coincides with the compression function itself. This fact follows from the following proposition (see few lines down for proof).
Proposition A.10. Any preferent compression function w from many examples to one defines a total ordering Su for which it holds that w(a1. an)) max, (a1.............. C.))
Note that, as byproduct of Proposition A.10. we have that any preferent compression function from many examples to one is also non-associative (since max, is non-associative). Therefore, the notion of max from a total ordering and that of preferent and non-associative compression function from many examples to one are equivalent. Interestingly, this equivalence crucially relies on the fact that the compression selects only one example, while, provably, the class of preferent and non-associative compression functions offers more freedom than using a total ordering when selecting more than one example at time. This is important for the development of alternative implementations of Algorithm 2 the version of P2L where multiple examples are selected at a time.
Proof of Proposition A.10 For any and define Sy if w(a b) b (and thus b Sx if w(a, b) = a). To show that S. is indeed an ordering, we have to prove that S. enjoys the reflexive, antisymmetric, and transitive properties.
a. Since w always selects one element, we have that w(a, a) a, i.e., a So a, which is the reflexive property.
b. If a Sx b and b S. a, then w(a, b) b and w(a, b) a. Thus, a Su b and S. a =
a = b, which is the antisymmetric property.
c. Suppose that a S. b and b Su c, which corresponds to u( b) = b and w(b, = c. Since w is preferent, it must be that w(a, c) = (indeed, w(a, c) cannot be a because is not selected by w(a, b); it cannot be b either because is selected by w(b, c)). Then, an application of preference again gives w(a. c) c. This means that a S. b and b S. c implies that a S. C, which is the transitive property.
We next prove that the max, operator associated to S. corresponds indeed to w; that is, holds that Su w(a)...., .(n) for all i E (1...., The proof is by contrapositive. Suppose thus that x(11,--. ((11,-..,,,, a,)) = ag for some i, but ag <g aj (i.e., dg S. aj and a; * a,) for some j. Condition a,. By preference, adding another element a to a, and aj would
a <u aj means that w(a.,a)) give w(a,, aj, ax)) # a, But then, preference again would give that the compression of a,, aj, and ag plus fourth element cannot be a;, and so forth and so Thus, proceeding iteratively would eventually lead to w(a an) F a;, which is a contradiction.
B Additional material for the application to MNIST Classification
B.1
Implementation details for SGD and PAC-Bayes
GD & test-set approach. Here we follow classical test-set approach, whereby a fraction of the dataset is used for training, and the remaining portion is sacrificed to certify the quality of the resulting model. We experiment with different sizes of these fractions. As for training, we use GD with momentum and fix the number of training epochs to 200. To compute the generalization bound, we use the tightest- samples equal to N minus those used for training. That is, letting N be the number of examples out
Binomial test-set bound"" of (Langford [005) 3.3] with a number of
10e Binomial test set bound is tighter then the commonly utilized Chernoff bound.
18

---

of N used for training and h = GD( be the returned hypothesis, we have that
R(h) $ max { E (0, 1]: Σ
p² (1-p) -)N--N- 2226 8, N ( 3
(4)
j=0
where l is the number of zz. Ñ +1.1...... N, misclassified by h.)
with high confidence 1-6. 8. We also perform grid search over the following set of parameters: learn- ing rate in |0.001, 0.005, 0.01]. momentum in [0.9, 0.95), dropout probability in [0.01, 0.05, 0.1, 0.2]. We then select the combination of parameters that return the lowest generalization bound 11
PAC-Bayes approach. Here we learn a model and provide generalization bounds based on the recent results presented in (Clerico al., 2022 Perez-Ortiz et al.. [202]), which build on earlier work in (Dziugaite & Roy| 2017) while providing tighter generalization bounds. Specifically, we utilize the same PaC-Bayes implementation of (Perez-Ortiz et al., 202T) adapted the considered binary classification problem, with one main difference: instead of training by optimizing a surrogate of the generalization bound as in (Perez-Ortiz et al. (02T), we optimize the exact bound as proposed in (Clerico et al. 2022, Eq 4.a), which provides the sharpest results to date T2] As the PAC-Bayes approach requires prior distribution over the networ weights to start, we split, as it customary. the training dataset in two and use the first part to pretrain the prior through SGD, while the remaining data are used to obtain the posterior distribution (contrary to P2I. and GD+test-set where the final hypothesis consists of deterministic network, the PAC-Bayes approach is forced to work with stochastic networks). We experiment with different sizes of the data portion to be used to pretrain the prior. In running PAC-Bayes we employ a batch size of 250, 100 prior and posterior training epochs, and 10-6 as lower bound for the minimum probability of the softmax output. We also perform grid search over the remaining parameters: prior standard deviation in [0.01, 0.020..0...... 0.03, 0.04, 0.05, 0.1]; dropout probability in [0.01, 0.05, 0.1, 0.2]; prior/posterior learning rate in [0.001. 0.005. 0.01]: prior/posterior momentum in [0.9, 0.95). The final bound we present is that in (Perez-Ortiz et al. 202T) [Sec 6.2], by using 10000 Monte Carlo samples from the learned distribution over the models to approximate the average empirical risk. When experiment with 5 = 0.035 (6- = 0.001), we use a confidence of 0.025 (0.00072) for the KI. bound and of 0.01 (0.00028) for Monte Carlo sampling as done in Peeezz-Otiz same philosophy as described in Footnote I1 regarding not introducing a union bound correction. The post-training performance is evaluated again by sampling the distribution over the network weights, computing the empirical misclassification on the full test dataset, and averaging over 10000 samples of the weights. As a matter of fact, the generalization bounds derived through the PAC-Bayes approach apply precisely to this quantity.
al. [SeT][Sec 6.2]. We apply here the
C
Some examples when the inner algorithm L has already in itself compression scheme
In this section, also prompted by a reviewer, we perform some synthetic numerical experiments to investigate how P2L performs when the inner algorithm L already exhibits compression in itself: specifically, we consider SVM (Support Vector Machine, (Cortes & Vapnik (1955) and SVR (Support Vector Regression, (Smola & Schölkopi 2004)) as inner algorithms for P2L and compare the returned output with that output by SVM and S VR alone. The so-called support vectors returned by SVM and SVR known compress the original dataset in way that is informative for the underlying learning problem. With these experiments, we want to verify whether P2L returns the same or a similar compression.
"I Formally, should introduce union bound correction because perform grid scarch over multiple hyper-parameters. Notably, this correction would enlarge (i.e., worsen) the risk bound. However, the union bound might conservative, we do not pursue this approach and give this advantage to both the test-set and, later, the PAC-Bayes approach.
The research in the field of PAC-Bayes is extremely active, and we would like acknowledge paper Wu & Seldin 2022), which has introduced improved PAC-Bayes bounds based on novel concentration inequalities for random variables with ternary values. However, in a binary setup (as in the present application), (Wu & Seldin
2022) itself notices that there is no advantage over the existing literature. Thus, to the best of our knowledge, the
bounds proposed by (Clerico et al. 2022) are currently the tightest for problem.
19

---

Figure 5: Comparison of learned classifiers and compressed sets returned by SVM and VV. Markers +, X represent examples with labels +1. The dashed blue and solid red lines (--.-), which are completely overlapped, represent the classifier returned by SVM and P2L+SVM. The blue triangles and red squares (A, D) represent the support vectors returned by SVM and the compressed set T returned by P2L+SVM.
In classification problem, consider datasets with N = 1000 examples (x. y). where instances
I are uniformly sampled from [-1, 1]2 ç R² and labels are if (x) - 0.3)² + x3 S 0.7 and -1 the whole dataset when called by P2I. inner algorithm) implemented with kernel k(x, .) = x H' || | separable. P2I. is run by selecting ho the classifier corresponding setting all the parameters in the SVM parameterization to 1. As for Sh. we consider the order induced by the distance in the lifted feature space of examples from the separating hyperplane corresponding when examples are misclassified and by- -1 otherwise (this yields that the worst examples are those misclassified and furthest away from the separating hyperplane). Distance equal to is taken as the threshold for appropriateness, which corresponds to consider classifier h appropriate for an example (x, y) when (zz.) 3) not misclassified by h.
otherwise. SVM (either when
2 for which the two classes defined above
h, multiplied by 1
Figure displays the results for two realizations of the considered classification problem, which are representative of what have observed in multiple trials. Each plot depicts: the examples in the instance domain as markers + (label 1), x (label -1); the separation boundaries of the SVM and of the P2L+SVM classifiers (dashed blue and solid red lines, which are completely overlapped); the support vectors returned by SVM (red squares) and the examples in T returned by P2L+SVM (blue triangles).
In the left panel of Figure 5 the compressed multiset T returned by P2L+SVM contains all the support vectors of SVM with the addition of few other examples, which are incorporated in T during the first iterations, while P2L is still exploring the problem. As it is clear, by the definition of support vectors, the classifier returned by P2L+SVM coincides with the classifier obtained by running SVM. In the right panel of Figure 5, only part of the support vectors are also elements of T. Nonetheless the classifiers obtained with P2L+SVM and SVM are still the same (at least up negligible approximation). Hence, it appears that P2L+SVM compensates the deficiency of support vectors with other alternative examples that are anyway capable recover the SVM classifier. The amount of support vectors appearing in 7' depends on the realization of the dataset, but in all our trials the classifier returned by P2L+SVM matches that obtained by running SVM on the same dataset.
As for SVR, we consider the same regression problem as in Section 6 when = 200. SVR is run using a radial basis function k(z, X) = exp( exp(-0.11] = as kernel, tube size equal to 0.1, and coefficient C' = 1 (C' modulates the trade-off between the flatness of the predictor and the penalty for deviations from the predictor larger than 0.1). P2L instead starts with a predictor hn corresponding to setting all the parameters in the SVR parameterization to 0, while we consider the same total order Sn. of Example 3.2 with y = 0.1. In this context, h is appropriate for an example (æx, y) if the deviation of the output y from the prediction corresponding to æ is more than 0.1.
Figure(ddisplay the results obtained for one dataset, which also representative of other realizations of data. In the plot, examples are represented as black crosses, while the dashed blue and red lines,
20

---

y 0.5
0.4 0.2
0.2
0.4
0.6
0.8
1
1.2
1.4
Figure 6: Comparison of learned predictors and compressed sets returned by SVR and P2L+SVR. Markers represent examples. The dashed blue and solid lines (--.-), which are completely overlapped, represent the predictor returned by SVR and P2L+SVR. The red shaded region depicts tube of radius 0.1 around such predictors. The blue triangles and red squares (A, [)) represent the support vectors returned by SVR and the compressed set 7 returned by P2L+SVR.
which are completely overlapped, depict the predictors returned by SVR and P2L+SVR respectively. The support vectors returned by SVR are displayed by blue triangles, while the examples T returned by P2L+SVR by red squares.
Similarly to the SVM case, in all our trials the predictor returned P2L+SVR is identical to the predictor obtained by running SVR on the same dataset. In the present example, however, it is always the case that the compressed multiset T returned by P2L+SVR contains all the support vectors of SVR, with the addition of few other examples incorporated in T during the first iterations during which P2I. is still exploring the problem.
21


Reviews:
[{"review_id": "k0k4f87J65", "reviewer": "Reviewer_3uwv", "summary": "In this paper, the authors present a novel framework called P2L, which aims to derive generalization guarantees for black-box supervised learning algorithms. P2L operates as a meta-algorithm that utilizes a learning algorithm to induce a compression scheme. The algorithm relies on two main components: a *criterion of appropriateness* and an *appropriateness threshold*. The criterion of appropriateness serves as a generalization of the loss function, measuring how well a hypothesis describes a given data point. The appropriateness threshold determines when the meta-algorithm terminates by ensuring that the hypothesis is appropriate for all unselected data points. At each step, the algorithm selects the example with the highest loss, according to the criterion of appropriateness, from the set of selected training data ($T$). This example, denoted as $\\bar{z}$, is added to $T$, and the learning algorithm produces a hypothesis ($h$) based on $T$. Using this new hypothesis, a new $\\bar{z}$ is selected, and the process iterates until h becomes appropriate for all examples in the original dataset ($D_S$). An important property of P2L is that running the algorithm on $T$ yields the same hypothesis as running it on the full dataset $D_S$. Consequently, $T$ effectively compresses $D_S$, similar in spirit to dataset distillation or identifying core examples within a dataset. To provide generalization guarantees, a theorem demonstrates that the cardinality of $T$ can be utilized to derive tight upper bounds on a suitable measure of statistical risk. The effectiveness of P2L is evaluated through experiments on binary MNIST and synthetic regression datasets. The results indicate that P2L outperforms the PAC-Bayes bound and performs competitively with using a hold-out set, all without requiring additional data.", "questions": "- The role of $h_0$ is somewhat unclear to me from the text. What does \"*pre-training $h_0$ on different portions of the dataset, again through GD*\" mean (line 235)? Why is the model not initialized from scratch? In algorithm 1, where is $h_0$ used? Is it only used for selecting the initial $\\bar{z}$?\n- Why did you use GD instead of SGD? Wouldn’t this result in worse models? How do the bounds compare if you use SGD?\n- In the inner loop, does the training have to be done from scratch or can it rely on the hypothesis from the previous iteration? If it is done from scratch, it feels like the algorithm would be extremely impractical since every iteration has to train a new neural network. If it is done starting from the weights from the previous iteration, wouldn’t the weights be prone to overfitting, especially if the problem is non-convex?\n- Is post-training performance just the test performance? If so, could you elaborate on the following statement “*utilizes all data to jointly learn a good model and provide a risk bound*\"? Do you have a theoretical justification for this statement? It feels like this could have some relationship to curriculum learning or boosting.\n- Is there a relationship between $\\gamma$ and the notion of margin? Why does $\\gamma$ not show up in the bound? Is the dependency implicit in $T$?\n- Is the total ordering determined by the most recent hypothesis $h$ or the meta-algorithm? There seem to be some conflicting statements in the paper. “$[T]_A$ *is a list that contains the elements in* $T$ *ordered according to the order in which they are selected by P2L*” (line 150) but in the conclusion *“a hypothesis-dependent total order used to select which data points are fed to the learning algorithm L.”* (line 346). In a similar vein, how is the ordering used in the experiment since GD does not care about the order of the data at all?\n- Does this framework have a relationship to the algorithmic stability framework?", "limitations": "See the weakness section.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- To the best of my knowledge, the proposed algorithm is novel and quite elegant (computational complexity notwithstanding). It is another realization of the principle “compression is intelligence”. \n- I find the technical tools used interesting and believe that this framework can potentially lead to many future works.\n- The resulting bounds are tighter than PAC-Bayes bounds.\n- The presentation of the algorithm is very clean and easy to follow. Most technical concepts are explained carefully and illustrated with examples. This is quite rare for theory papers.\n- The algorithm exhibits some very interesting properties that are potentially desirable for learning algorithms. (*\"the misclassification on the test-set for P2L is constant across all prior/train portions\"*)\n", "weaknesses": "- In contrast to many existing generalization bounds, P2L can only be used for risk certification, that is, it does not offer an immediate way to make the bound tighter (which may improve the performance of the model) nor does it provide an understanding of why particular algorithms or architecture work well. Of course, this is partially due to the fact that P2L is designed to be as general as possible (i.e., black-box) but depending on the goal, the latter is sometimes more important than the risk certification itself.\n- The algorithm seems not particularly efficient which limits its practicality, especially for deep learning with very large datasets. If the model is trained from scratch at every iteration, the complexity could be quadratic in the number of data points (i.e., $N^2$). On the other hand, it seems more suited for applications where the dataset is small. Perhaps it's better to phrase the paper in that direction. If this is not the case, please correct me. The authors do already address this point in the conclusion but note that PAC-Bayes generalization bounds for deep learning often use Gaussian posterior which is easy to sample from and empirically the estimate concentrates quite fast. Furthermore, these bounds can be made deterministic (Nagarajan et al., 2018).\n- Related to the previous point, the paper would benefit from more empirical evaluation such as those in (Lotfi et al., 2022) who provided the SOTA PAC-Bayes bounds for several benchmarks. The field of PAC-Bayes bounds for deep learning has made significant progress in the past couple of years and only having binary MNIST results makes it hard to judge the empirical value of the proposed algorithm.\n- The paper is generally well-written and clear but there are several important clarifications needed (see questions).\n\n**Reference**\n\n- PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization. Lotfi et al., 2022\n- Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience. Nagarajan et al., 2018", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the Reviewer for their positive review and constructive comments. We include our responses below, which we hope can help better understand and position our paper.\n\n**Weaknesses**\n\n* “In contrast…”: while it is true that our bound cannot be directly optimized, the size of the compression set T (and the corresponding bound on the risk) are informative indicators of whether the chosen architecture had worked well. When this is not the case, the flexibility of P2L allows to accommodate and test a different inner algorithm with the goal of improving the result.\n\n* “The algorithm seems…”: we agree with the Reviewer that P2L is, in its current form, more suited to offline problems with dataset of relatively small size – a point that we will emphasize more. However, please also note that, in situations where P2L works well (i.e. a small size of the compression is achieved), P2L halts at early stages, during which the inner algorithm can be executed efficiently since it is run over a smaller portion of the dataset.\n\n**Questions**\n\n* “The role of $h_0$…”: As you pointed out, $h_0$ is used to select the first $\\bar{z}$ to be put in T. From that step on, $h$ is computed via the inner learning algorithm fed with T. As natural, note that $h_0$ has an impact on the algorithm: if $h_0$ is already good, then the algorithm just needs to refine it and will likely terminate at early stages with a small size of the compression set; if $h_0$ is poor, P2L may need some additional iterations to construct a set T from which to obtain a sensible hypothesis. In this respect, pre-training is introduced solely to guide the selection of $h_0$. In particular, a portion of the training dataset is used to generate a sensible $h_0$ to start from, and then P2L is used on the remaining data. We apologize if this was not clear and will work to better explain this point in the final version of the paper. \n\n* “Why did you use GD…”: We tried both GD and SGD and they gave similar results. We will mention this in the paper.\n\n* “In the inner…”: the generality of P2L allows one to choose either of the following approaches: one can either re-train a hypothesis from scratch at every iteration or keep the previously obtained hypothesis as initialization (this was our choice in the simulations). The two implementations can be seen as slightly different inner learning algorithms for P2L. Interestingly, the certification on the risk that we provide allows one to understand whether overfitting has arisen (in which case the risk certification will turn out to be close to 1) and therefore to opt for a different approach, or inner algorithm altogether.  \n\n* “Is post-training…”: yes, by post-training performance we mean the performance on a test dataset. To be precise, we use a test dataset to assess the actual performance of the three methods (e.g., 10000 examples for MNIST), in addition to the dataset D employed by each of the methods. At the same time, we note that, while P2L and PAC-Bayes are allowed to utilize the whole dataset D to optimize the hypothesis, SGD+test-set is forced to further divide D in D1 and D2 where D1 is used for training and D2 to return a certification of the risk. The sentence you mentioned is motivated by the experimentally verified fact (see Figure 2) that P2L always obtains an actual performance (as measured on the hold-out dataset) which coincides with that obtained by SGD+test-set when one takes D1 = D (the “good model” in the sentence). For this model, SGD+test-set cannot provide any risk certification since D2 is empty, while P2L instead is able to provide meaningful risk bounds. We apologize if this was not clear and aim to further discuss this point in the final version of the paper. \n\n* “Is there a relationship...”: within our setting, the “margin” is the difference between gamma and the distance of the worst example from the chosen model. As correctly pointed out by the Reviewer, the risk depends on gamma, but gamma does not appear in the bound because the dependence is implicit in T. Indeed, T and the compression size depend on the chosen value of gamma: for example, if gamma is selected to be very large, the corresponding compression T will likely be small because a coarse model will be sufficient to accommodate the points within a (large) threshold of gamma.\n\n* “Is the total ordering…”: there are two different ordering coming into play here, and we apologize if this was not clearly conveyed. On the one hand, we have an ordering relation over the datapoints in $D_s\\setminus T$ that depends on $h$, and which is used to select the worst example for the present $h$ to augment T. On the other hand, the order of the elements in the list $[T]_A$ simply refers to the position of the elements in the list and is solely used to enable inner learning algorithms that depend on the order with which they are fed with data, e.g., the output of SGD depends on the order with which the points in the dataset T appear. In case of order-of-feeding independent algorithms, like e.g. GD, the order of the elements in $[T]_A$  is simply ignored by the algorithm and has no effect on the final result.\n\n* “Does this framework…”: While the framework is not related to the algorithmic stability framework of [A], the notion of stable compression schemes (introduced by [B] and recently reconsidered in [C]), which is equivalent to the notion of preferent compression scheme, is instead central. Many thanks for the question, we will mention this equivalence in the paper. \n\n**References**\n* [A] Bousquet & Elisseff. Stability and Generalization, JMLR, 2022\n* [B] V. Vapnik and A. Chervonenkis. Theory of Pattern Recognition, 1974\n* [C] Hanneke & Kontorovich, Stable sample compression schemes: new applications and an optimal SVM margin bound. PMLR, 2021\n"}, {"review_id": "ZxfpQOTL7A", "reviewer": "Reviewer_pkHc", "summary": "This work elaborates on the recent breakthroughs of Campi&Garatti 2023, by exploiting compression theory results to design a novel meta-algorithm, namely the Pick-To-Learn (P2L) algorithm. This algorithm aims to compress the dataset to a smaller, truly impacting one, this notion of impact being defined through a hypothesis dependent order $\\leq_h$. Authors provably show high-probability generalisation bounds for P2L and experimentally shows that P2L with gradient descent as subroutine yields better theoretical results and experimental performances than both the test-set approach and PAC-Bayes learning.\n\n\nIn conclusion, I am convinced by the P2L algorithm, and it could be enough for acceptance at this point. However, I remain doubtful about the experimental process, see the Questions part. \n\n**References**\nWu et al. 2022 : Split-kl and PAC-Bayes-split-kl Inequalities for Ternary Random Variables", "questions": "- To perform their experiments, authors split MNIST in 60 datasets of size 1000 to enlighten how well works P2L when few data are available, which corresponds to many real-life situations. However, there is other situation where a huge amount of data is available. Thus, I am wondering about the performance of all three methods when trained on all, 60000 data simultaneously. Did the authors try to perform this experiment? \n- Appendix B: is the bound 4.a of Clerico et al. truly the tightest? It seems that Wu et al. 2022 improved on this.\n- I understand that the current experiments aim to express the interest of the proposed meta algorithm, but I remain doubtful about the comparison with the PAC-Bayes learning objective. Indeed, the comparison with the test method is meaningful as it shows how P2L improves on classical GD. Why not taking the PAC-Bayes minimisation routine as a subroutine of P2L and compare it to PAC-Bayes without P2L (plotted in green in this work)?\n- Does it exist similar procedures than P2L in the literature which selects meaningful data?\n- What is the time complexity for plotting the bounds and running P2L comparing to other methods?", "limitations": "None.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I found the theoretical part of this work utterly interesting as it offers a breath of fresh air in the generalisation field (at least up to my knowledge).", "weaknesses": " I have several concerns about the experimental setup (in particular the comparison with PAC-Bayes theory). See the 'Questions' part.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First of all, we would like to thank the Reviewer for their valuable time and feedback on the work, which we found useful and to the point.\n\n**Questions**\n\n* “To perform their experiments…”: Considering the small-data regime was motivated both by applications and by the fact that, in these settings holding out a portion of the training set for testing deteriorates the post-training performance.\nAt the same time, we completely agree with the Reviewer that there are many learning problems for which large amount of labelled data is available (including MNIST). As suggested, we have performed similar experiments to the case where all three methods are applied the 60000 datapoint simultaneously (employing a pre-training fraction of 0.5), with similar results to those found when using a dataset of size 1000. In particular, the bound / post-training performance achieved are included in the table below.\\\nRegarding the bounds: In the present setting, the generalization bound attained by test-set is slightly better compared to that achieved by P2L, and P2L's bound still outperform Pac Bayes’. Regarding the post-training performance: once again P2L and SGD+test-set provide post-training performances that are slightly superior to Pac-Bayes. More precisely, in the present setting P2L slightly outperforms SGD+test-set. These results are due to the fact that, in this regime, leaving out datapoints from the training phase (as done with SGD+test-set and a pre-training fraction of 0.5) has little cost, since the size of the training dataset remains large enough to reach (almost) the optimal model. We aim to clarify these points in final version of the manuscript.\n| Method       | Risk bound | Post-training performance |\n|--------------|------------|---------------------------|\n| P2L          | 2.31%      | 0.99%                     |\n| Pac-Bayes    | 2.54%      | 1.65%                     |\n| SGD+Test-set | 1.65%      | 1.52%                     |  \n\n* “Appendix B: is …”: The work of Wu et al. 2020 is certainly interesting, as it provides novel concentration bounds for random variable with ternary values, e.g., with values in {-1,0,1} as opposed to the classical binary setting of {0,1}. At the same time, we note that our work considers an appropriateness criterion that correspond to a binary loss function (either h is appropriate or not). In the binary settings, the same authors observe that their novel bound behaves similarly to existing kl-bounds [Wu et al, lines 5/6 of Introduction, lines 3/5 of Discussion]. Still, we find the work of interest and make sure to mention this point in our final version of the manuscript.\n\n* “I understand that …”: We thank the Reviewer for the insightful comment. We wish to emphasize that the aim of our work is to show that, by using P2L, we can learn a hypothesis that has both post-training performance and risk bounds that are equally good or better compared to state of the art PAC-Bayes or SGD+test-set. In this respect, P2L is not designed with the aim of improving the performance of *any* internal algorithm, but rather that of providing *an* internal algorithm with a generalization bound -- when this is not readily available -- while maintaining a desirable post-training performance. Thus, we believe our comparison to be meaningful and our numerical analysis to support this statement. Certainly, it is interesting to investigate whether P2L can improve the performance of other inner algorithms, in particular P2L+PAC-Bayes, as suggested by the Reviewer. This is a direction we will investigate.\n\n* “Does it exist …”: There certainly is a growing body of literature referred to as “data compression” / “dataset selection” / “coreset selection”, e.g., [A,B,C] that aims at reducing a given dataset’s size while ensuring that the performance of the resulting trained models is comparable. However, these works are different both in their motivation (compressing the dataset is motivated by a computational issue), and in their results. Indeed, none of these works produces a compression scheme in the sense of the classical definition (i.e., such that the model’s output is identical), and certainly they do not enforce the property of *preferent* compression. Both of these properties are crucial to derive a generalization bound such as ours, and we believe our work to be the first -- to the best of our knowledge.\n\n  * [A]: Dataset pruning: reducing training data by examining generalization influence.\n  * [B]: Deep Learning on a Data Diet: Finding Important Examples Early in Training.\n  * [C]: An Empirical Study of Example Forgetting during Deep Neural Network Learning\n\n* “What is the time …”: The following are running times for one instance of MNIST, i.e., a single dataset with 1000 datapoints (pretraining factor =0.5) on the following machine: MBPro 2021, Apple M1 Pro CPU, 32gb ram:\n| Method       | Execution time |\n|--------------|:--------------:|\n| P2L          |     2min 1s    |\n| Pac-Bayes    |     4min 4s    |\n| SGD+Test-set |     0min 5s    |"}, {"review_id": "fTnUM8LfeE", "reviewer": "Reviewer_q61g", "summary": "This paper introduces a meta-learning algorithm which compresses a training set $D$ of size $|D|$ into a smaller training set $T\\subset D$ of size $|T|$. The algorithm can be defined for any *base learner*, i.e. any training strategy which outputs a trained hypothesis $h$ when given a training set. The set $T$ is selected in such a way that the performance of the base algorithm trained on $T$ and evaluated on $D$ is better than a predetermined threshold. Relying on some powerful recent results from [1], the authors show that one can obtain tight generalization bounds for the result of the algorithm expressed as a function of the size  ratio $|T|/|D|$: intuitively, if the model is able to compress the dataset $D$ into a much smaller dataset $|T|$ whilst maintaining the performance of the base learner trained on $T$, it must be that the sample size is already sufficient to train the model well. Thus, the results can be interpreted as a middle way between on the one hand  the traditional approach to generalization bounds via direct study of the function class searched by a given algorithm, and on the other hand,  the even simpler *test-set bounds*[2]. The function of the ratio $|T|/|D|$ which gives a bound on the probability of error is a complex implicitly defined function inherited from [1] with a very mild dependence on the failure probability $\\delta$. \n\nThe algorithm functions as follows: start with an initial hypothesis $h_0$, then find the element of the training set $D$ which is the least well explained by $h$ (for instance, the one with the largest loss function value), and include this element in the set $T$. Retrain the hypothesis based on $T$ and repeat the procedure until either every element of the set $D\\setminus T$ has a loss function value below a given predetermined threshold. \n\nThe proof of the generalization bounds is a reasonably direct consequence of Theorem A.4., which is a powerful result from [1] concerning compression schemes. The key is to show that the compression function defined by the algorithm (the function which compresses $D$ into $T$ satisfies the properties of *preference* and *non associativity*, which are proved in Lemmas A.5. and A.6 respectively, and that the failure event which is bounded in Theorem A.4, which is the *probability of change of compression* is implied by the failure of prediction event (this is shown in Lemma A.7.). A technical condition of non concentrated mass which is required to be satisfied for Theorem A.4 to hold, is also removed by a straightforward argument augmenting each datapoint by a continuous random variable which doesn't affect the loss function/order. It is also shown (Proposition A.9) that any compression scheme which outputs a single element and is preferent must correspond to a maximum function with respect to some well defined notion of order. \n\nExperiments on the MNIST dataset and on a synthetic regression dataset demonstrate that the proposed algorithm yields superior generalization performance and tighter bounds than the Pac-Bayesian baseline, and proide slightly inferior bounds compared to a test-set approach. It is still worth noting nonetheless that the test performance is still superior to the test set approach due to a better indirect exploitation of the whole training set in the compression step. \n\n\n==============Post-rebuttal==========\n\nAs seen in the comments below, my discussion with the authors and the extra material promised (especially the experiments in the rebuttal concerning support vectors) have increased my opinion of the paper, resulting in me raising my score to 6. I believe this paper is above the threshold and tackles very interesting questions, with the main downside being a relatively small amount of material and original proofs (which should not necessarily disqualify a paper for publication). \n\n=====\n\n\n**References** \n\n[1] Marco C. Campi, Simone Garatti. Compression, Generalization and Learning. ArXiv 2023.\n[2] Langford, J. and Shapire, R. Tutorial on practical prediction theory for classification. JMLR 2017.", "questions": "Do you think your algorithm will be able to recover support vectors in a simple linear classification problem? \n\nIn Table 1 on page 7, which proportion of the training set is used for pretraining?", "limitations": "Mostly the reliance on intialization, the limited evaluation of interpretability and the coverage only of the case where a single element is added to the set $T$ at each iteration. See  \"weaknesses\" for more details\".\n\nAssuming there is really no comparable result in the literature (i.e. no generalization bounds expressed in terms of the success of a compression method), this is still a **very interesting paper opening up a new direction**. However, the amount of content included in this first contribution is surgically small.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This is a very interesting direction, not just in terms of providing generalization bounds (which is the main aspect presented in the paper) but also in terms of potential practical interpretation: this is a simple algorithm that, in principle, allows one to compress a dataset into a much smaller one, allowing us to derive interpretable information about which datapoints are key to the training procedure. \n\n2. This is a novel application of a mathematical result from [1] into a machine learning context, and has a distinctly novel flavor compared to many existing generalization bounds. \n\n3. The paper is relatively well written and a pleasure to read. The proofs are clean despite the fact that they must have been a bit annoying to write: It is quite trivial to convince oneself that the results (lemmas A.5, A.6, A.7 and Proposition A.9.) hold, but not so much fun to write down explicitly.", "weaknesses": "1. The results are essentially straightforward applications of existing results from [1], there isn't really any non trivial difficulty that had to be vanquished in the proofs. In short, this paper isn't a lot of work from the authors. \n\n2. The experimental evaluation is still relatively preliminary, there is so much more to explore: Other datasets and architectures, better baselines, and more importantly, the implications in terms of interpretability. For instance, the following follow-up experiments could be performed: \n\n2.1 Compare to more baselines on more datasets (Cifar, other Pac Bayesian bounds). In footnote 7 on page 7, the authors claim that \"Pac-Bayesian approaches have been developed only for linear regression problems\". This is a highly doubtful or (at best misleading) statement. In addition, generalization bounds based on function class capacity could also be evaluated in the synthetic regression dataset. \n\n2.2 (most important) Investigate the interpretability of the results: for instance, it would be interesting and rather key to evaluate the method on a synthetic binary classification dataset with a simple kernel method. It seems that in an ideal situation, the set $T$ should eventually correspond to, or at least strongly overlap, the set of support vectors. Even in the case of MNIST, it would be very interesting to visualize the chosen datapoints and see if they have something qualitatively different from the non-chosen ones. \n\n3 A very big issue is that the algorithm, as presented, is not that applicable in practice. Indeed, to make the algorithm work in the examples considered, the authors needed to pretrain the model on a significant proportion of the training set. In particular, the algorithm cannot select which datapoints in the set used for pretraining are more important than others. Since the algorithms used rely on gradient descent and the authors interpret the call to the base learner as a single gradient step, the initialization is key. It remains to be seen whether the algorithm in its pure form, with a base learner that performs exact empirical risk minimization on $T$, can work in any practical scenario. At the very minimum, it should be checked whether training the network on $T$ from random initialization (rather than pretraining it to obtain $h_0$ and then continuing training with $T$, which is what is done here) yields comparable performance.  \n\n3.2 (related to 3) It seems like the extension to the case where several datapoints are introduced into $T$ simultaneously (perhaps in a hierarchical way) would not be too much to ask in a first submission, since it is key to solving the problem of the overreliance on initialization. \n\n4. I feel like the description of the previous results could be more extensive, for the benefit of the reader. For instance, the following things could improve the paper's reach and interest to a broader audience: \n\n4.1 Explain the gist of the proof of theorem A.4., at least in terms of intuitive reason why the function $\\Psi$ from line 187 appears. \n\n4.2.  Write down the result (theorem 3.3) from [2] which is used to evaluate the test set bounds and discuss it. \n\n4.3 In line 472, the sentence \"See also Section 4 in [1]\" appears to suggest that the connection between the probability of change of compression and the classification/regression error is already established in [1]. If that is the case, how much of the present paper is truly not covered or implied by the discussion in [1]? \n\n5. I feel like a more detailed description of existing literature on training set compression schemes and how they relate to the present method is needed. It is hard to believe that no such literature exists. \n\n\n\n\n**Minor comments/typos**\n\nThe concept of \"probability of change of compression\" is frequently used in the main paper (cf., e.g., line 341, but it is only defined in the appendix (455-457)\n\nLine 28: \"the precision of available bounds is much problem dependent\" ===>  \"the precision of available bounds is highlyproblem dependent\" \n\nline 64: \"is laying the groundwork\" ==> \"lays the groundwork\"\n\nline 110 \"is add to\"  ===> \"is added to\" \n\nLines 114 and 115: \"enough appropriate\" ==> \"appropriate enough\" \n\nLine 175:  \"an hypothesis\" ==> \"a hypothesis\" \n\nLine 280: \"fits well the data\" ==> \"fits the data well\" \n\nlines 480 and 560: I would use \"remove the condition\" instead of \"release the condition\" \n\n\n\n\n\n\n\n\n\n**References** \n\n[1] Marco C. Campi, Simone Garatti. Compression, Generalization and Learning. ArXiv 2023.\n[2] Langford, J. and Shapire, R. Tutorial on practical prediction theory for classification. JMLR 2017.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for the positive review and constructive comments. In addressing them, we have produced additional material (see attached pdf and below) that we believe will improve the quality of the manuscript. \n\n**Weaknesses**\n\n* 2.1. We concur that our sentence on PAC-Bayes methods in regression problems can be misleading and aim to remove it. We will also evaluate generalization bounds based on class capacity as suggested.\n\n* 2.2. Many thanks for this valuable comment that touches upon an important aspect. We are already able to offer some insights. Specifically, we ran: i) SVM and P2L+SVM as inner algorithm on a (new) synthetic 3d linearly separable classification problem; ii) SVR using RBF kernels and P2L+SVR as inner algorithm on the regression problem presented in Section 6. Interestingly, in both cases, the behaviour is that expected by the Reviewer: the compressed dataset T eventually contains all the support vectors with the addition of few other examples that are added to T in the first iterations, while the algorithm is still learning what are the significant examples. Please see Figures 1 and 2 in the attached PDF. We will add this material to the paper along with some considerations on the chosen examples in the MNIST classification problem.\n\n* 3.&nbsp;We would like to clarify two important points.\n  * First, the inner algorithm, referred by the reviewer as “base learner” (denoted by $L$ in the paper), does not perform a single step of gradient descent, but instead iterates gradient descent until convergence, i.e., “performs empirical risk minimization on T”. As such, the algorithm is given enough freedom to move towards a more informative hypothesis, as guided by the points in T. This is why in the numerical examples the post-training performance of P2L is independent of the portion of data used for pre-training (Fig 2 in manuscript, red line). We apologies if this was not clear -- we will do so in the final version.\n  * Second, we observe that P2L works also without the use of pretraining, see for example the application to synthetic regression in Figure 4 (top panels, red curve at abscissa equal to zero). The motivation for introducing the pre-training is solely that of improving the resulting bound to the risk. Indeed, when starting from an educated guess (i.e., using some data to pretrain $h_0$), the choice of “worst misclassified” point is more meaningful allowing the algorithm to terminate with a smaller set T and thus providing better generalization bounds. Still, good results can be obtained without pre-training and we plan to include evidence for this also for the MNIST example.\\\nIn this context, it is also worth remarking that the choice of pre-training factor can be thought of as a hyper-parameter, for which our generalization bound provide a methodology to make an optimal choice. Such optimal choice is application specific (e.g., 50% for MNIST, while only 10% for the regression problem).\n\n* 3.2. We thank the Reviewer for their interesting comment. As for the possibility of introducing datapoints in T simultaneously, we note that this can be readily achieved and that our methodology directly accommodates this extension.\\\nWhile we plan to include a discussion on this point in the final version of the manuscript, we observe that adding more than one point to T might or might not have a beneficial effect on P2L. Indeed, on one hand, adding more datapoints might allow to build a better estimate of $h_0$ earlier on. However, by introducing these datapoints in groups (and thus not allowing for the fine-grained choice of adding them one-by-one) might also result in a larger set T, which could worsen the final bound.\\\nTo illustrate this, we have run the same synthetic regression problem considered in Section 6 (with no pretraining) comparing the case in which, at each iteration, we select only the one/two/three/four/five worst datapoints. The results are presented in Figure 3 in the attached PDF and showcase how, for the problem considered, adding a single data-point at a time is optimal.\n\n* 4.1 and 4.2. We will do so.\n\n* 4.3. In [1] it is only observed that whenever inappropriateness implies a change of compression, then the probability of inappropriateness (the risk) is no bigger than the probability of change of compression. To use this result, however, one has then to show that inappropriateness indeed implies a change of compression, a property which is not straightforward since it is not satisfied by many learning algorithms. The fact that this property always applies for the P2L algorithm is proved here for the first time (Lemma A.7).\nIn general, apart from Section A.1, which is a summary of results used in this paper, all the material is new.\n\n* 5.&nbsp;We will improve the description of the existing literature. In particular, we will mention the literature referred to as “data compression” that aims at reducing a given dataset for computational purposes [Toneva et al]. However, these works differ from our since they are not amenable of the generalization bound. We will also contrast our work with existing compression schemes, which include [1]. These works provide generalization bounds but are typically applied to learning algorithms that have built-in compression properties, e.g., SVM. Our contribution departs significantly from them by offering a methodology to enforce a (preferent) compression also when starting from algorithms that do not have this property, e.g., neural nets. To the best of our knowledge this is the first contribution in this space.\n\n* Minor comments/typos: Many thanks for your accurate reading of our paper. All the suggested modifications will be implemented.\n\n**Questions**\n\n* “Do you think …”: Please, see the response to your point 2.2\n\n* “In Table 1 …”: The Table reports the results for pre-training proportions leading to the lowest risk bounds for each method, i.e., 50% for P2L, 70% for SGD+test-set, 60% for PAC-Bayes. \n"}]

Author rebuttal:
We would like to take this opportunity to thank all the Reviewers and PCs for their valuable time and feedback. Below, we address each of the reviews individually, while we attach here a pdf containing additional figures used in the responses. 


Meta-review: A very well-written paper that proposes a novel and elegant method for obtaining generalizing guarantees for black box models. The main idea is to propose a modification to the traditional learning algorithm in a way that leads to data compression. Then some recent work on data compression is exploited to obtain guarantees. This does not require any prior knowledge of the learning algorithms. This paper was well received. The results are correct and clearly stated. Reviewer q61g highlighted that the proofs are not very complex and rely on some previous work. However this is not a very big criticism as the main contribution is not theoretical but rather methodological and conceptual. I  recommend this paper to be accepted as a spotlight.
Decision: Accept (spotlight)