Generalization Bounds via Meta-Learned Model Representations: PAC-Bayes and Sample Compression Hypernetworks

We thank the reviewer for his insightful feedback.

1. “People are applying bounds on models like 100M~7B parameters.”

Indeed, interesting works have successfully computed tight generalization bounds for large models. It does not undermine the need for tighter generalization bounds for smaller models, as they are still used for many applications. Moreover, the submitted manuscript focuses on investigating a new way of obtaining bounds in meta-learning, which we conceive as a stepping stone for undertaking larger experiments.

2. “Missing literature review on PAC Bayes for LLMs”

Following the reviewer's comments, we will include a literature review of PAC-Bayes for LLMs in Section 2.1 and mention these two works: “Unlocking Tokens as Data Points for Generalization Bounds on Larger Language Models” and “Non-Vacuous Generalization Bounds for Large Langage Models”.

3. “The proposed subspace compression is similar to the hypernetwork idea [ in SubLoRA (https://arxiv.org/abs/2312.17173) ].”

We would like to emphasize the following differences between SubLoRA and our approach: the representation in SubLoRA (and in LoRA) is learned via SGD and is composed of tunable parameters. In our case, though the representation is a function of tunable parameters, it mostly depends on the input dataset. The task is not to encode the weights of a model working well on a single task but to ensure the versatility of the representation for any related task. The way the representation is treated is also quite different: in our case, it is fed to a hypernetwork whose output is the weights of the downstream predictor. (See also 6. for a conceptual difference.)

4. “Empirical results in Tables 1 and 2 are a bit weak. Some of the bound values are higher than the strawman baseline.”

We report empirical evaluation in both unfavorable (Table 1) and favorable (Table 2) environments. Table 1 illustrates that a fixed model can perform well across the tasks in terms of both error and bound. This highlights that the commonly used pixel swap environment does not account for all meta-learning scenarios. See “Rebuttal XmYz, 2.2” for a numerical investigation.

The strawman bounds are essentially test bounds: they are valid for a single predictor. Since no predictor is learned on the query set, the empirical error is an unbiased test error estimate (close to 0.5 in Table 2). Hence, the gap between the bounds and the test error is small in these cases. In contrast, the train bounds underlying the other methods are valid uniformly for all learnable predictors. The price to obtain train bounds is a larger complexity term that increases the gap. For the CIFAR100 experiment, all training bounds are greater than the one of the baseline, but we achieved the lowest one with our SCH- model.

5. “I’m a bit skeptical about why meta-learning the parameters of a downstream predictor is a good idea. Too restrictive for very large models?”

Since our bound relies on the latent representation instead of the complexity of the downstream predictor and decoder, we expect it to be suited for fine-tuning of the last few layers of large models. Also, one could consider a “prior” over the downstream predictor, which would correspond to the random initialization in the LoRA nomenclature, and predict the weights of LoRA-like matrices to modify this “prior”. Finally, note that our bounds hold for any bounded loss function, which is necessary in some settings for bounding models generating sequences of tokens. These are all promising future works that we will mention in our conclusion.

6. “How does this meta-learning approach compare to other types of model compression like [...]?”

Although both our approach and the aforementioned methods are compression-based, ours is not a model-compression approach. Our primary goal is to compress the dataset into a subset of datapoints and a message, which is a less explored strategy. By creating a bottleneck, we compress the information contained in the dataset and use it to learn a model instead of compressing the model itself. Therefore, to our knowledge, we compared ourselves to the works closest to ours in the field of meta-learning: PAC-Baysian approaches.

7. “The paper can benefit from more analysis figures [...]."

During the rebuttal period, we crafted additional figures following the Reviewers' suggestions:

• We present the contribution of each of the terms in the bound to the bound value for a few algorithms on the 200 pixels swap (see https://imgur.com/a/9d4fOvB) and on the CIFAR100 binary task (see https://imgur.com/a/GSyoggu). See “Rebuttal to Reviewer 5RkH, 2.4” for a discussion on these figures.
• We depict the test error and generalization bound for PB SCH as a function of both the compression set size and the message size. (see https://imgur.com/a/r45Wq56 and “Rebuttal to Reviewer 5RkH, 2.3” discussion).

We thank the reviewer for his feedback, which will help us highlight the precise nature of our contribution. We undertake to add these clarifications to the manuscript.

1. First concern (the theoretical results are not novel enough)

1.1. We agree that our theoretical results are moderately novel, and we respectfully suggest that our work should not be judged on this basis. Our main contributions are not new PAC-Bayesian and sample compression generalization bounds or advanced proof techniques. Instead, we propose an original way to leverage existing results in a meta-learning framework. We are the first to apply PAC-Bayesian and sample compression to hypernetworks. With this in mind, we undertake to present various kinds of generalization bounds in a unified setting, advancing the idea that each bound can inspire a particular hypernetwork architecture. To our knowledge, this unconventional perspective is fresh, and we argue that it deserves to be shared with the machine learning community.

1.2. Hence: “What is the main technical difficulty of [...] to obtain new bound in Theorem 2.4?” There is no technical difficulty here for those being familiar with the usual PAC-Bayes and sample compress proof schemes; our result is indeed based on existing ones. The interest in our results does not lie in their complexity. In the proof of Theorem B.1 and Theorem B.2, we unify and generalize the proof techniques of previous results. Doing so, we present Theorem B.1, which recovers a version of the theorem of Laviolette & Marchand (2005) for real-valued losses and a version of the theorem of Thiemann et al. (2017) for different sizes of compression sets. Theorem B.2 is a tighter version of previous works and a correct version of Theorem 39 of Germain et al. (2015). Indeed, as pointed out in lines 809-839, their proof was only correct for one size of compression set.

Finally, Theorem 2.4 is a direct consequence of Theorem B.1. The idea of using a Dirac distribution to obtain “sample-compression” style bounds is not novel, as it was explored in Marchand & Laviolette (2005). Nevertheless, mixing probabilistic messages and deterministic compression sets is entirely new and follows our peculiar way of looking at generalization bounds to inspire original hypernetworks. This enables us to use real-valued messages instead of binary messages, which is pivotal to optimizing the parameters of the PB SCH architecture bounds with respect to the message in a continuous way.

2. Second concern (the experimental results are not convincing)

2.1. We rigorously reported the empirical evaluation in both unfavorable (Table 1) and favorable (Table 2) environments. On the binary MNIST task, our methods compare very favorably to others. On the CIFAR100 task, our method achieves the best bound by a reasonable margin.

2.2. The reviewer asks “how to demonstrate the posterior and the prior is similar?” To better illustrate our claim, we computed the prior-posterior KL term of both Pentina & Lampert (2014) and Zakerinia et al. for a few tasks (see https://imgur.com/a/tcIJlNZ). This shows that the KL values are lower for a small amount of pixel swap and larger for the binary MNIST task.

2.3. As to “why the test bounds in Table 1 are smaller than the test bound of benchmark methods”, it partly relies on the fact that our bounds are based on the $kl(q,p)$ comparator function (see Eq. 1) instead of being linear as in Pentina (2014). Also, a small compression set and message are selected; thus, only a small complexity term enters the computation of the bound.

2.4. Concerning the performances of PB SCH, we study in a new figure (see https://imgur.com/a/r45Wq56) the test error and generalization bound for PB SCH as a function of both the compression set size and the message size. See “Rebuttal to Reviewer 5RkH, 2.3” for a discussion of these results.

3. “Theorems 2.1-2.3 are existing results [... and] can be deferred to the supplementary material.”

We thank the reviewer for the suggestion. We will move these parts to the appendix and use the freed space to clarify the abovementioned points.

4. “In the experimental setting, each training task including 2000 images [...] of these 2000 images?”

This is right: half the images (the support set) are used to generate the predictor, while the other half (the query set) is used to compute the meta train loss. However, a new random support/query split is performed at each epoch for every train dataset.

5. “Some crucial explanations should be added to make the whole proof clearer and more readable. For example, in line 1069, why [...].”

On Line 1069, the expectation is on discrete distributions $P_J$, and $Q_J$, the latter being a Dirac on $\mathbf{j}$ such that $Q(\mathbf{j})=1$, explaining the equality. We will add this clarification and comment on the many other steps of the proof.

We thank the reviewer for his careful reading of the paper.

1. Claims And Evidence

The reviewer correctly says that “the generalization bounds proved in this paper are not meta-learning generalization bounds.” Instead, our framework shows a new way of using generalization bounds in a meta-learning framework. We will clarify this further to avoid misconceptions, especially in the Related Works part of the introduction.

2. Experimental Designs Or Analyses:

2.1. Concerning the comparison with the benchmarks: for our algorithms, we naturally used the support set for the computation of the bound, and the query set for the computation of the test error. Though the benchmarks do not require support/query splits, it is necessary to compute the bound and the test error on independent sets to ensure the reliability of the results. Since the query/support split is done in a random 50/50 fashion for our approaches, we split similarly the datasets for the benchmarks to compute the bound and the test error.

2.2 Concerning the labels shuffle experiment, we agree it would be an interesting use case for our algorithms and will add this experiment to the revised version of our manuscript.

2.3 Concerning PB SCH and $c > 0$: we produce new results (see: https://imgur.com/a/r45Wq56) depicting the test error and generalization bound for PB SCH as a function of both the compression set size and the message size. We see that the message is better-suited for the minimization of the test error, but a trade-off between the compression set size and the message size is required to obtain the best bounds (In Table 1 and 2, we used the validation error to select the compression set size and message size). Interestingly, when we enforce a small message size, the benefit of using $c>0$ becomes apparent.

2.4 We also present the contribution of each of the terms in the bound to the bound value for a few algorithms on the 200 pixels swap (see here: https://imgur.com/a/9d4fOvB) and on the CIFAR100 binary task (see here: https://imgur.com/a/GSyoggu). In the figures, the cumulative contributions are displayed, while in the tables, the marginal contributions are displayed. The bounds are decomposed as follows:

• The observed meta train “error”
• The “confidence penalty”, which corresponds to the term $-\ln(\delta)$ in Theorem 2.1 and the similar terms in other bounds
• The “complexity term”, which corresponds to the KL factor in the PAC-Bayes bounds. The latter is further decomposed into the compression set probability and the message probability in our sample compression-based bounds.

When considering the decomposition on the 200 pixels swap experiment, we see that our approach, despite having a larger error term, relies on a small message probability and a null compression set probability to yield competitive bounds. In contrast, for Pentina & Lampert, the complexity term profoundly impacts the bound, making it non-competitive. As for the decomposition on the CIFAR100 experiments, it is interesting to see that the bound from Zakerinia et al. and the one from PB SCH have a similar decomposition, whereas SCH$_+$, despite being penalized by the message probability, relies on a better treatment of its error and confidence term to obtain best bound of the four considered algorithms. This is empirical evidence of the tightness of our bounds compared to those of the runner-ups, all factors (error, confidence $\delta$, …) being kept equal, thanks to the non-linear comparator function $\Delta$ (see Theorem 2.1).

3. Essential References Not Discussed

We agree that discussing and conceptually comparing prior work on hypernetworks will enrich the paper. We thank the reviewers for the references from the federated learning literature. They are great examples of the benefits of meta-learned representations and hypernetworks. On a similar note, kindly point toward “Rebuttal KTTB, points 2. and 6.” where the differences between our approaches and model compression approaches.

4. Questions For Authors

Concerning the large bound values, many bounds mathematical expressions can give values greater than one. This is especially true when the bound is linear, i.e., of the form “true error $\leq$ empirical error + complexity term” (which is the case for many benchmarks) since the complexity term is usually not upper-bounded. The calculated bound values for Amit & Meir (2018) in Table 2 are truly around 1000, for the complexity term here is too important. We point to the fact that all of our bounds enjoy being bounded in the interval [0,1], so that no vacuous (trivial, >1) bound can be outputted.

We thank the reviewer for his careful reading of the paper.

1. Other Strengths And Weaknesses

1.1. Concerning the complexity of the proposed framework, the encoder-decoder architectures are central to our contributions; each component has its unique role in the whole. We are open to performing new experiments if the reviewer has a suggestion on simplifications. That said, we suggest extending the current Appendix G, accompanying Figures 7 to 9 with a comprehensive description and motivation of every choice we made concerning the encoder-decoder architecture.

1.2. Concerning the mixed empirical performances, we report empirical evaluation in unfavorable (Table 1) and favorable (Table 2) environments to investigate a new family of methods honestly. Nevertheless, we agree that adding more experiments could reinforce the encouraging performances on the meta-learning binary variants of MNIST and CIFAR100.

That is why we crafted new heatmaps (see https://imgur.com/a/r45Wq56) depicting the test error and generalization bound for PB SCH as a function of both the compression set size and the message size (Recall that Tables 1 and 2 report the performances of the models obtaining the best validation error). These detailed results help in grasping the inner workings of our proposed approach. They depict that using a large message is better-suited for minimizing the test error, but a trade-off between the compression set size and the message size is required to obtain the best bounds. Interestingly, when the message size is restricted to be small, we clearly see the benefit of using $c>0$.

2. Other Comments Or Suggestions

Many thanks for pointing out the typos and ambiguities. We will give an example of “message” in Section 2.2 and explain our bounds compared to the ones from the literature in the appendix.

3. Questions For Authors

3.1. Concerning the choice of a prior distribution over the compression set and the (discrete) message, one can think of using a prior that gives more importance to smaller compression sets and shorter messages. In our current approach, these values are hyperparameters that are fixed, but as discussed in 1.2, the elaboration of an algorithm that selects these quantities as parameters would benefit from such priors. These are interesting options that we will mention as future research directions.

3.2. In our tables, the bolded values correspond to the smallest bound values, not those with the smallest gaps.