Symmetric Kernels with Non-Symmetric Data: A Data-Agnostic Learnability Bound

• Transformer results.

Response: We thank the reviewer for shedding light on this issue. We now further explain the result and also give a back-of-the-envelope calculation that shows the appearance of induction heads in large-scale experiments much the scaling given by our bound. We cite here the new paragraph:

“Assuming a long context $L \gg 1$, a large vocabulary $V \gg 1$ and normalized kernel $\mathbb{E}_{X \sim q}[k(X,X)] \simeq 1$, the sample complexity bound simply reads

$

P^* \gtrsim \sigma^2 (1-\epsilon) L V.

$

In simple terms, the number of samples has to scale like the product of the context length and the vocabulary size to learn copying heads. This result can be seen as a limit to when models in the kernel limit can start performing in-context learning. We note (Olsson et al. 2022) used $V=2^{16}$ and $L=8192$ (giving $L\cdot V\approx0.5\cdot10^9$) and found induction heads appear after training on around $2 \cdot 10^9$ tokens for a wide range of model sizes.”

• I found the paragraph beginning ‘taking a Bayesian viewpoint’ (line 63) difficult to parse...

Response: We greatly appreciate the attention to the manuscript and this valuable comment. We agree that this paragraph was a weak point in the introduction and have changed it in the updated version.

• As minor typographical points…

Response: We are grateful for the reviewer's help in improving the manuscript! We fixed these in the new version.

• Can the authors comment more on the relationship between conventional measures of learnability and their new scheme?

Response: We thank the reviewer for highlighting the question, we now address it more fully in the text and in the experiments. This part is given below

“Comparing equations (4), (6) the inner product (equivalently expectation) in the cross-data learnability is taken over the auxiliary measure instead of on the dataset. This change can be intuitively understood as learning from $D_P$, but judging how good the reconstruction is based on functional similarity on $q(x)$. Such a change can have the advantage of weighting all possible inputs evenly, perhaps capturing a notion of out-of-distribution generalization but the disadvantage of being uninformed about the details of the specific dataset. The issue of judging similarity differently based on different measures is exemplified and discussed further in Section 4.2.
Cross-dataset learnability agrees with the common one when learning from the true underlying probability density of the dataset $p(x)$ (rather than the empirical $D_P$) and choosing $q(x) = p(x)$. However, The underlying density $p(x)$ is often inaccessible, in these cases, one can still use our generalized learnability to estimate learnability from the empirical dataset $D_P$.
We note that while the on-dataset learnability in Eq.(4) is bounded $\mathcal{L}_t \in [0,1)$, the cross-dataset learnability is unbounded from above. As a consequence, maximizing cross-dataset learnability does not imply good learning; instead, one must require it to be close to unity.”

The experiments now compare the two kinds of learnability and show sample complexity derived by cross-dataset learnability is relevant for on-dataset learnability. This relationship is even strengthened when the distributions are more similar as the experiments with whitened data show.

• Can the authors provide interpretation of the sample complexity bound in Eq. 26, especially the dependence $L$ on and $V$?

Response: This can be seen as a case of the curse of dimensionality: larger context and vocabulary make it harder to learn and require more samples. We note that this is also seen in a range of real-world large transformers outside the kernel regime. Olsson et al. 2022 consistently found it takes more than a billion tokens before induction heads are learned, this is a non-trivial amount. A billion tokens are approximately 10 times more than the large version of WikiText or roughly 1% of the gigantic C4 dataset.

• Can the authors clarify the discussion about the rotational symmetry of the FCN on line 54?

Response: These references may indeed not be the most approachable, we cite more approachable ones in section 3.1. We now cite them on line 54 as well. To give the (approximate) gist of these results:

Fully connected networks result in rotationally symmetric kernels. Rotationally symmetric kernels with rotationally symmetric distributions are diagonalized in the basis of the hyperspherical harmonics. The hyperspherical harmonics are arranged in irreps labeled by $\ell$ which corresponds to their degree. Since the dimension of the $\ell$’th irrep scales as $d^\ell$ the associated eigenvalue scales as $\lambda_\ell \sim d^{-\ell}$.

The works cited in the manuscript give a much more fine-grained understanding of the spectrum, including results that account for the depth of the network, the specific activation functions used, etc.

We thank the reviewer for the in-depth review of our work and the insightful comments. We have made several changes to the manuscript based on these and we believe they have greatly improved the paper. Below we respond to the specific questions and comments.

• Articulation of the relationship between conventional and cross-dataset learnability.

Response: We thank the reviewer for drawing our attention to this issue. We have made the similarity between the definitions of the two quantities more explicit, added a fuller discussion to section 2, and moved the discussion from section 4.2 up to section 2. Moreover, we have performed new experiments and now present new results in the main text, we believe these help address this issue. Specifically, Figure 1 now shows the “ordinary” learnability together with the cross-dataset learnability to make the relation between the two more tangible; Figure 2 now shows results for whitened data which has a spherically symmetric covariance thereby bringing it closer to $q$, and compares these results with non whitened data.

• Utility on real-world data and Figures 1 and 2.

Response: We apologize for this, it seems the figures failed to communicate the results. First, we clarify some of the points raised by the reviewer

• Note that what is shown in those figures is the ratio between the cross-dataset learnability and our bound. The drop in those figures is not the result of the cross-dataset learnability decreasing but rather a result of it reaching a constant value (saturating) while the bound continues to grow linearly with P indefinitely.
• We delegated these figures to an appendix and now use figures that show the common learnability alongside the cross-dataset learnability and indicate the bound on the number of samples required for learning.

In the new figures, the cross-dataset learnability is seen to be indicative of the on-dataset learnability, and the sample complexity bound is shown to be practical.

Reducing the dimension was merely a numerical convenience, we wanted to work with a not-too-large dataset of $~10000$ samples (2 classes of CIFAR/MNIST/F-MNIST) but still be able to have non-negligible cross-dataset learnability. Since the eigenvalue associated is a quadratic feature of a rotationally invariant kernel would scale as $d^{-2}$ taking, for example, $d=100$ would already give $P^* \approx 10000$, forcing us to use a large dataset. The new experiments use larger dimension ($d=14$ for Fig.1 and $d=20$ for Fig. 2) these dimensions match the effective dimension of these datasets as was measured empirically [1-4]

• Choosing $q(x)$.

Response: This is an interesting point, we thank the reviewer for bringing it up. While giving an exact answer to this question lies beyond the scope of the current work, we did perform new experiments to address it. In the new experiments, shown in the new Fig.2, we use PCA whitening rather than regular PCA, resulting in a covariance matrix that is spherically symmetric. The results are indeed closer together in this case.

Additionally, we can certainly provide guidelines on choosing $q(x)$. One wants to balance maximizing the symmetries and choosing a distribution similar to the true one. On the one hand, larger symmetry gives a tighter bound on the eigenvalues and more freedom in choosing a relevant target feature within each irrep (as the irreps are larger). On the other hand, one does not want to create a distribution that would make the cross-dataset learnability very different from the on-dataset learnability. As shown in the new experiments, there is quite a large range of choices that will yield useful results; e.g. Fashion MNIST images are certainly not uniformly sampled from the hypersphere yet we get good sample complexity results for this $q$.

Finally, We thank the reviewer for the advice on the table of symmetries, architectures, and eigenvalues, while not present yet in the current version we will add one to the final version. Such a table could include FCNs and their rotational symmetry, transformers and their permutation symmetry, as well as architectures designed to respect specific symmetries like G-CNNs [5]. We hope this work will motivate even further work along this line.

[1] Pope P, Zhu C, Abdelkader A, Goldblum M and Goldstein T 2021 THE INTRINSIC DIMENSION OF IMAGES AND ITS IMPACT ON LEARNING

[2] Aumüller M and Ceccarello M 2021 The role of local dimensionality measures in benchmarking nearest neighbor search

[3] Facco E, d’Errico M, Rodriguez A and Laio A 2017 Estimating the intrinsic dimension of datasets by a minimal neighborhood

[4] Spigler S, Geiger M and Wyart M 2020 Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm

[5] Cohen T S and Welling M 2016 Group Equivariant Convolutional Networks

Thanks for the response and the comprehensive answers to my questions. I closed my review by saying 'If they can explain the relationship to conventional learnability and the practical implications of their scheme (or convince me why these things shouldn’t matter), I will be happy to raise my score.'

1. Relationship to conventional learnability. I think the manuscript has improved on this point -- Fig. 1 now shows the relationship between learnability computed empirically and cross-data learnability, along with the authors' bounds. This helps convince the reader these things are at least somewhat related. Fig. 2 captures how whitened PCA makes the bound tighter, which heuristically makes sense because the dataset and auxiliary measure become more similar. I think the manuscript would benefit from more discussion like this: perhaps an experiment showing how the strength of correlation between conventional and cross-dataset learnability and bound tightness change as the dataset and auxiliary measure become more similar in a smooth way (beyond either whitened vs regular PCA), or better some theoretical results relating the two beyond agreement when learning from $p(x)$ (rather than $D_p$) and when $q(x)=p(x)$.
2. Practical implications of the scheme. The manuscript has also improved on this point. Thanks for adding extra interpretation of the Transformer bound (now Eq. 25). Reading the responses to other reviewers and the revised text, I can see that the goal is to find a necessary condition for learnability, and that the authors note that the bound to the learnability is always within an order of magnitude of the true learnability during the learning phase. I think this (line 246) could still be spelled out a little more explicitly.

Whilst some progress has been made (thanks for your efforts), unfortunately I'm still not totally convinced on either of these accounts. The relationship to conventional learnability is still only described heuristically and with brief experiments. Whilst the interpretation of the Transformer bound is better and I can see that this method might (roughly) capture a necessary condition for learnability, I think there is still limited evidence of any really practical conclusions or outcomes. For these reasons, I'll stick with my current score, but will be willing to reconsider if the reviewers can convince me I'm wrong on these points before the end of the discussion period.

We thank the reviewer for taking the time to discuss our revised version and response. Below we address the reviewer’s remaining concerns.

theoretical result. We can add the following comments (1) when $q(x)$ makes some sense for the task at hand the cross-dataset learnability has significance beyond its ability to serve as a proxy for the on-dataset learnability. (2) Cross-dataset learnability can certainly be related theoretically to performance on the original distribution $p(x)$ under assumptions on $p(x)$; one such assumption and bound pair are: Assuming $p(x)/q(x) \leq C \quad \forall x \in {\rm supp} ~ p$ the MSE error on $p(x)$ is bounded from below

$$\frac{1}{C}\sum_{i}(L_{i}^{q}-1)^{2}\left\langle \phi_{i},y\right\rangle_q ^{2}=\frac{1}{C}\int dxq(x)[f(x)-y(x)]^{2}\leq\int dxp(x)[f(x)-y(x)]^{2}.$$

This is a concrete bound on the generalization error on the data distribution of interest $p(x)$.

Practical implications. We addressed both natural language and vision domains in non-toy-setting scenarios. Moreover, our own experimental results encompass three real dataset. Considering many theoretical works use synthetic or hand-crafted data and stylized neural networks the authors believe practical significance is not a weak point of the current theoretical work.

We agree there are many interesting directions for future research and we believe this is a good indication that this work and the concept of cross-dataset learnability will be of much interest to the community.

• It looks like the learnability for a feature defined in Eq. (4) takes Tikhonov regularization...

Response: This is an interesting question. The regularizer is indeed essential in our derivation as it allows us to bound the spectral norm of $[K+I\sigma^2]^{-1}$, where the kernel is evaluated on the dataset $D_P$. While none of the authors is an expert on spectral regularization, it seems the most straightforward way to extend the results of this paper is bounding the spectral norm of the spectral filter used in the spectral regularized algorithm. For Tikhonov the answer is extremely simple, it is the inverse of the ridge, for Landweber iterations it seems the spectral norm of the filter would scale linearly with the number of iterations (see for example [1]).It seems truncated SVD regularization would require knowledge of the spectrum of the kernel evaluated on the dataset $D_P$, which is a requirement we would like to avoid.

We add two remarks. (1) Tikhonov regularization is well-motivated in the context of kernels from neural networks as it relates to the noise in the gradients (Naveh et al., 2021). (2) This regularization arises naturally when learning from an empirical dataset rather than a distribution as shown in Canatar et al., (2021), Simon et al., (2023).

• Although it is a theoretical bound, I’m curious about its role in practice; how do you estimate the expectations in Eq. (7), especially for those expectations over. If one uses the empirical counterparts, it is weird as the r.h.s. of Eq. (7) also concerns sample size.

Response: We thank the reviewer for the question and now mention the answer in the text explicitly. Indeed one would calculate it empirically, this should be relatively cheap computationally (much cheaper than inverting a kernel). The bound will indeed fluctuate a little as one changes P and more samples are accounted for. As an alternative, one can calculate it on the full dataset and scale $P$ alone. Moreover, This can often be estimated analytically given that some target functions have a simple out structure, e.g. classification targets usually have norm 1.

• Notations a.

Response: In general, this form makes sense as is, as the spectral filter (inverse of the kernel with ridge) would normally connect the two quantities by matrix multiplication, these indices just spell out this matrix multiplication (see for example equation 1). We hope we have answered the point the reviewer was referring to, if not we would be happy to clear this matter further.

• Notations b.

Response: Indeed this quantity is dubbed cross-dataset learnability.

[1] L. Rosasco. Lecture 7 of the Lecture Notes for 9.520: Statistical Learning Theory and Applications. Massachusetts Institute of Technology, Fall 2013. Available at https://www.mit.edu/~9.520/fall13/slides/class07/class07_spectral.pdf

We thank the reviewer for taking the time to review our work and providing thoughtful comments. We further thank the reviewer for recognizing the novelty of our work, indeed we believe this is the first time the idea of using an idealized measure to understand real data is introduced in this form. Regarding the specific points and questions

• ...Can authors explain more about the challenges (technically) and consequences presented by non-symmetric data?

Response: Indeed many theoretical works in the NN community assume uniform data and this assumption facilitates the theoretical analysis, however, these assumptions rarely hold for real-world data. Our work capitalizes on the fact the symmetry of the kernel is a far more valid assumption than the symmetry of the data.

Specifically, for the case of kernel regression, If one wishes to give theoretical predictions one has to solve an eigenvalue problem for the kernel on the data to estimate the learnability for example. In general, for real-world data, this task cannot be carried out analytically. One way of accomplishing this task is by relying on symmetries, but these have to be respected by both the kernel and the dataset (see Def. 3.2,3.3). This fact is especially “disappointing” considering that kernels that arise as the limit of neural networks often have large symmetries (that is, the group of symmetries they respect is large). If the symmetry is not a dataset symmetry, naively, it cannot be used to simplify the eigenvalue problem; this work shows it can still be used, but in that case, the results are weaker.

We hope we have answered the point raised by the reviewer but we are not certain. If this is not the case we would be happy to clarify any further issue.

• Why is cross-data learnability considered to take the form of Eq. (6)? How does it link to the original definition of Eq. (4)?

Response: We thank the reviewer for drawing our attention to this issue. We agree the paper can greatly benefit from such an explanation. First, we add to the definition in equation (4) another form of the quantity which makes the connection much more apparent. We also added an explanation addressing this issue to the paper below Eq. 6. We give it here:

“Comparing equations 4,6 the inner product (equivalently expectation) in the cross-data learnability is taken over the auxiliary measure instead of on the dataset.
This change can be intuitively understood as learning from $D_P$ but judging how good the reconstruction is based on functional similarity on $q(x)$. This choice can have positive effects, like weighting all possible inputs evenly, perhaps capturing a notion of out-of-distribution generalization; the issue of judging similarity differently based on different measures is exemplified and discussed further in Section 4.2.
Cross-dataset learnability agrees with the common one when learning from the true underlying probability density of the dataset $p(x)$ (rather than the empirical $D_P$) and choosing $q(x) = p(x)$. However, The underlying density $p(x)$ is often inaccessible, in these cases, one can still use our generalized learnability to estimate learnability from the empirical dataset $D_P$.
We note that while the on-dataset learnability in Eq.4 is bounded $\mathcal{L}_t \in [0,1)$, the cross-dataset learnability is unbounded from above. As a consequence, maximizing cross-dataset learnability does not imply good learning; instead, one must require it to be close to unity.”

I thank the authors for the detailed replies to my questions, which helped me understand the paper better. After reading other reviewers' comments, I think they have more expertise on this topic than I do, so I decided to keep my score and confidence.

One additional comment about extending the result to spectral algorithms is that: if the authors need to bound the spectral norm of $[K+\sigma^{2}I]^{-1}$ (or its counterpart in spectral algorithms $\phi_{\lambda}(K)$ where $\phi_{\lambda}$ is the filter function), this can be directly done by directly using the properties of the filter function, which leads to the spectral norm bounded by $\lambda^{-1}$. I hope this can provide some useful insights if the authors would like to expand the content of this paper.

• The vignettes considered in Section 4 are not that convincing...

Response: The vignettes serve a double purpose in this manuscript, (1) exemplifying how the bound can be used and shedding light on its different aspects, while also (2) providing some new results. The Gaussian vignette serves mainly the first purpose. Regarding the parity vignette, parity is used to model a high-degree, complicated, feature that is shown to be unlearnable in image classification for instance with FCN kernels using our bound. Moreover, although the ML folklore says high-degree polynomials such as parity (in the noiseless case) are hard to learn from data by FCN-kernels, we are not aware of a result that shows it in any case but under strong symmetry assumptions of the distribution.

Concerning the copying heads vignette, induction heads (Olsson et al., 2022) were shown empirically to be responsible for some of the in-context learning in LLMs. In turn, learning copying heads is a necessary step in learning induction heads, and thus a necessary step for a fundamental in-context learning capability. This case is brought forth as an example where we have a simple closed-form expression for a target function that has relevance in real-world performance. The result in the paper is a concrete lower bound on the sample complexity of in-context learning induced by induction heads for transformers in the lazy regime. Specifically, the result shows a form of “curse of dimensionality” where the sample complexity scales with the product of the context and the vocabulary. We note that this is also seen in a range of real-world large transformers outside the kernel regime. Olsson et al., (2022) consistently found it takes more than a billion tokens before induction heads are learned, this is a non-trivial amount. A billion tokens are approximately 10 times more than the large version of WikiText or 1% of the gigantic C4 dataset.

• For example, Figure 1 shows some results related to CIFAR-10, but they seem to be very far from answers to real practical questions such as "how big must be the data set to achieve accuracy x?"

Response: The reviewer is asking for an extremely challenging type of prediction that involves real-world datasets with all their complexity together with networks as complicated as transformers. Still, we believe we rise to this challenge. Given one knows the target function we give the user useful predictions. Our cross-dataset learnability is shown (in the new figures) to be of the same order of magnitude as the on-dataset learnability which is directly related to the mean square error. As aforementioned we can do that for real-world and complicated networks at the kernel regime.

• line 705: "while the eigendecomposition of the operator... depends on the measure, the Mercer decomposition of the kernel function does not" - that's not correct, Mercer's decomposition does depend on the measure (otherwise how would we define orthogonality?)

Response: We thank the reviewer for helping us make this statement more precise. This statement was meant to communicate the fact that the Mercer representation found on one dataset can be used on another (given the condition on their support). We agree with the reviewer that the statement, taken at face value, is incorrect and have rephrased it to “the representation of the kernel found by Mercer decomposition holds for all datasets within the support on q”

• Line 174: "The learnability computed empirically divided by our learnability bound"- The bound established in Theorem 3.1 is for the number of samples, not the learnability. Also, it is not clear to me what is in Eq. (10), and how this equation was derived.

Response: The reviewer's comments made clear the experiments were not communicated well enough, we are sincerely thankful for this input. This figure is now delegated to an appendix, where we give a better explanation for what we depict in it. To give a short answer, we did not use the sample complexity bound, but the bound on the cross-dataset learnability derived in the appendix, we can see how that can be confusing, and we now present things differently. We hope the reviewer will be able to comment on the new figures too.

• Typos

Response: We thank the reviewer again for catching all of these! We apologize for any inconvenience they may have caused during the reading.

We sincerely thank the reviewer for the time spent reviewing and commenting on our work. These comments have been valuable to us and enabled us to sharpen the messages significantly. We further thank the reviewer for recognizing the novelty in the approach taken in this work. We hope the revision made to the paper communicates the results better and can convince the reviewer that cross-dataset learnability is not only an interesting new quantity but also a useful one. Below we address the reviewer's specific concerns.

• My main issue with the paper is that I don't see it resulting in clear and important new findings.

Response: We thank the reviewer for pinpointing this issue. One of the main theoretical contributions of this work is the definition of cross-dataset learnability and the demonstration of its tractability, this is now complemented by better experiments that show its usefulness. The fact that this quantity can be bounded by a straightforward argument is not a disadvantage in our view. Additionally, while the derivation is rather direct, to the best of our knowledge, the result is novel. Regarding the significance of the results, we believe the new experiments and the rest of our answers address this concern, if this is not the case, we would be happy to discuss it further.

• There are some issues with the proposed definition (6) of cross-dataset learnability...

Response: We agree with the reviewer. We would like to apologize for a typo in the main text, one should require $L=1-\epsilon$, as in the last equation in Appendix A, rather than $L \geq 1-\epsilon$, Eq. (7) (now Eq. 8) then follows. The requirement $L=1-\epsilon$ does indeed rule out the case of overlearning. We would also like to note we did not claim the cross-dataset learnability is bounded by 1. We now state this explicitly in the text to avoid this misunderstanding.

Regarding the specific example presented by the reviewer, we note our bound in Eq.(7) (now 8) gives $P^* \geq 0$ which holds trivially. We stress our bound is a necessary, but not a sufficient condition for learning, i.e. an upper bound on the (cross-dataset) learnability. There are indeed cases where our bound does not prove useful, but it is able to give relevant sample complexity bounds in real-world scenarios, we show evidence for that in new figures that we have added to the paper (see next point).

• I cannot say that the paper convincingly demonstrates the importance and usefulness

Response: We thank the reviewer for bringing up this point. We believe it has greatly helped us in presenting the results of the paper. According to the comments by the reviewers, we see the figures were ineffective in communicating the message of the paper. Therefore we decided to perform new experiments and add new figures while delegating the existing ones to an appendix.

The new experiments compare the regular learnability, the cross-dataset learnability, and our sample complexity bounds. We see these as evidence for our sample complexity bound as an indicator of when learning occurs.

To comment on the specific point, the old Figure 1, left panel, is actually rather tight during the learning phase (to the left of the horizontal line) allowing us to give good predictions for the sample complexity. This can be seen by the fact the ratio of the bound to the learnability is always within an order of magnitude during the learning phase. The old Figure 2, left panel, also shows the bound is within an order of magnitude from the exact learnability throughout the learning phase. The bound naturally becomes very loose as it grows linearly with $P$ even after the learnability saturates, but again our aim is to give a necessary condition for learnability, below a certain complexity some functions cannot be learned.

We would like to follow up on this and see if our new experiments, revisions, and comments answered the questions and concerns posed by this reviewer. Please let us know if any further clarifications are needed or if any concerns still remain.

We would also like to highlight that under assumptions on the distribution of interest $p(x)$ the cross-dataset learnability can be related to the performance on $p(x)$. For example, assuming $p(x)/q(x) \leq C \quad \forall x \in {\rm supp} ~ p$ the MSE error on $p(x)$ is bounded from below

$$\frac{1}{C}\sum_{i}(L_{i}^{q}-1)^{2}\left\langle \phi_{i},y\right\rangle_q ^{2}=\frac{1}{C}\int dxq(x)[f(x)-y(x)]^{2}\leq\int dxp(x)[f(x)-y(x)]^{2}.$$

• Theorem 3.1 does not deal with symmetry, and the role of the proposed workflow is unclear to me.

Response: The reviewer is correct, theorem 3.1 holds regardless of any symmetry considerations. However, one would likely find very little use for it if the distribution $q(x)$ does not yield a simpler kernel eigenvalue problem. Here is the relevant use case: one is interested in the performance on $D_P$, but solving the eigenvalue problem on $D_P$ proves intractable. In this case, we suggest solving it on a symmetric auxiliary distribution $q(x)$, making the solution practical.

Symmetries enter the picture as a tool to simplify kernel eigenvalue problems, but they can be used only when the data distribution obeys them too. Our work, and specifically theorem 3.1 gives a sample complexity bound when learning from a dataset of interest but being able to solve the kernel eigenvalue problem only on a simpler data distribution $q(x)$.

We hope the changes to the introduction will help make this clearer for future readers.

We thank the reviewer for investing the time in reviewing our paper and providing constructive feedback. We further thank the reviewer for keeping an open mind regarding our future response. Below we respond to the specific points.

• the contribution of the paper is not clear; I didn't understand it by reading the paper
• the intro section does not provide anything about the paper because it is too general
• The introduction section is not clear--there are a lot of generic arguments, including all those in the 'our contributions' part (e.g., 'We generalize ... is tested on another.'). One cannot understand what exactly the contribution of the paper is based on the introduction section. This, in my opinion, should be clarified and revised.

Response: We thank the reviewer for their honest opinion. We made several changes to the text, including sharpening the “main contributions” and working out through the introduction, hopefully removing ambiguities and presenting points more clearly. We also performed new experiments which we believe make the overall presentation more clear and cohesive.

• typo in equation 1: comma is missing in the summation
• Equation 2 is not clear--are $\psi$ functions vector? Then what does mean$[\psi_i,\psi_j]$? Is that inner product? The paper would benefit from a more clear notation.

Response: We thank the reviewer for taking the time to help us clear such typos. We added the comma in equation 1 and removed the comma in equation 2 this is just an expectation over a product of two psi’s. One can indeed define an inner product with this expectation over products but we chose not to, to avoid introducing unnecessary notation. This is now consistent with our definition of cross-dataset learnability which uses the same expectation over a product notation instead of an inner product. The introduction of the inner product is delegated to the appendix.

Regarding the status of psi, it is a function as suggested by the notation, and as given by Mercer’s theorem. In equation 2 this function is restricted to the dataset $D_P$ (notice this restriction on the rightmost part of equation 2). This notation unifies the treatment for both discrete and continuous distribution, which may also be relevant to the reviewer’s next point.

• In Equation 2, can you explain why the expectation is over the data set, not data distribution?

Response: We thank the reviewer for the question. If the “data distribution” in the question is to be interpreted as an empirical data distribution (say sum of delta distributions) then the two are the same. If, on the other hand, the reviewer means the “theoretical” underlying distribution, e.g. uniform measure on the hypersphere compared to P points sampled uniformly on the hypersphere, then in real-world scenarios this distribution is often unknowable - we do not know the true underlying distribution of images of handwritten digits for example. Defining the learnability on the dataset allows us to treat such real-world examples.

• The setup considered in Section 2 (Equation 6) is called the study of distributional shift, and some recent works are missing in references such as [1]. Moreover, recent works are missing for learning kernels with symmetries [2,3]. These are just instances, and please find similar papers for reference.

Response: We thank the reviewer for bringing up this interesting point. The setup in equation 6 indeed resembles that of a distributional shift but we would like to draw several distinctions between them. In a distributional shift, one learns from one dataset but would ideally want to learn from another, the question is then: given we learned from the “wrong” dataset what can be said about performance on the “correct” one. Instead, this work assumes detailed knowledge of the would-be “shifted” distribution $q(x)$, not the training dataset $D_P$. Furthermore, In this work, the distribution $q(x)$ has only an auxiliary nature. One has the freedom to handcraft a simple and analytically tractable $q(x)$ so quantities like learnability can be analytically calculated on it. Nevertheless, this is an interesting connection and we now mention it in a new appendix on further related works.

Regarding refs. [2,3]; we would like to thank the reviewer again for broadening the scope of the discussion. While our references so far discussed symmetries that appear naturally in the architecture of neural networks the two papers mentioned by the reviewer refer to the case where one imposes more symmetries. This is indeed an interesting topic as well and we included it in the above-mentioned new appendix on further related works.