Thank you for your thoughtful review. We are glad that you find our theoretical analysis and the proposed metric valuable. We would like to answer your questions as follows:

1. Efficiency

For extracting the top singular functions, the time complexity of kernel PCA is the same as eigendecomposition, which is about $O(m^3)$, where $m$ is the number of pretrain samples. The time complexity of extracting the singular functions using a pretraining objective (the deep learning method) depends on the optimizer, and there is a rich body of work on the convergence rate of popular optimizers such as Adam and SGD. Moreover, there exist many deep-learning-based methods that can extract the eigenfunctions, including VICReg, which is used in the experiments, NeuralEF (Deng et al., 2022), and NeuralSVD (Ryu et al., 2024). The complexity of these methods grows linearly with the size of the dataset and does not suffer from the scalability issues of kernel PCA. For instance, for a mini batch of size $B$, NeuralSVD only has complexity $O(B^2 d + d^2 B)$, where $d$ is the dimension of representation. In other words, the deep learning method is scalable and much faster than kernel PCA, though it is not guaranteed to find the exact singular functions because the optimization problem is non-convex. We will add this discussion to the paper.

Deng et al. "NeuralEF: Deconstructing kernels by deep neural networks." ICML 2022.

Ryu et al. "Operator SVD with neural networks via nested low-rank approximation." ICML 2024.

2. Evaluation metric

We evaluate a context with a task-agnostic metric because we would like the encoder to be transferable to various tasks. Moreover, foundation models are often applied to tasks they are not designed for, so we might not know all the tasks at pretrain time. On the contrary, a probing classifier only evaluates the context on a specific task, so it cannot reflect the transferability of the encoder. There is a strong connection between our theory and alignment metrics, which we discuss in Section 4.2. Alignment metrics compare two encoders (focusing on their relative relationship), while our metric evaluates the contexture of one context (assessing its intrinsic information-capturing properties).

3. Noisy contexts

The effect of a noisy context depends on how noisy is defined. We can think of two possible definitions.

1. The noise reduces the compatibility between the context and the task (Section 4.1). In this case, our analysis shows that the learned representation will have a lower quality.
2. The noise weakens the association between $X$ and $A$. Section 5 shows that a good context should have a moderate association. If the association level of the original context is already moderate, then the noise will make it worse. However, if the association level of the original context is strong, then adding noise might even have a positive effect. For example, it is widely observed in self-supervised learning that strong augmentations make the learned representations better. For example, the authors of SimCLR attribute its success largely to the aggressive crop ratio and color distortion it uses.

4. Paper updates

We added a new limitation paragraph in the conclusion (see below), and a new related work section (please see our response to reviewer R5n1).

We appreciate your feedback and hope that our response answers all your questions. We are happy to address any follow-up questions.

Updated limitation and open problem paragraph (to be added to conclusion)

Our analysis has three limitations, which lead to three open problems. First, our analysis focused on the minimizers of the objectives. However, Cohen et al. (2021) showed that deep models trained by popular gradient methods do not find the minimizers, but instead oscillate around the edge of stability. The open problem is how this phenomenon affects our results. Second, we did not discuss the impact of the inductive bias of the model architecture, such as the translation invariance of convolutional neural networks. Such inductive biases can affect the context and, therefore, the encoder. We pose how to integrate the effect of these biases into our theory as an open problem. Third, our theory assumes that $P_X$ is fixed. In practice, however, there is always a data distribution shift from upstream to downstream. Refining our theory to handle such distribution shifts is an exciting direction for future work.

Thank you for your review.

1. Experiments in Section 4.2 (scaling) are updated

We changed the embedding dimension from $d=16$ to $d=128$ (which is more common in practice) and reran the experiment. The results are plotted in https://i.postimg.cc/FRncq3Zb/alignment.jpg

The main observation is that the alignment becomes much higher (CCA generally $>0.8$ and can be $\approx 0.9$). Also, as the model becomes wider/deeper, the alignment first increases and then decreases. We interpret the results as follows:

• Effect of $d$: The previously used $d=16$ was too small. For instance, the $16^{th}$ eigenvalue is quite large ($>0.3$), and is close to the $25^{th}$ eigenvalue. Thus, it is hard to distinguish which of the top-$25$ singular functions belong to the top-$16$, which is why the original alignment was low. In contrast, the $128^{th}$ eigenvalue is close to zero, so when $d=128$, the network can learn the top singular functions pretty well. Prior work mostly used $d \ge 128$, such as Kornblith et al., 2019 and Huh et al., 2024, so using $d = 128$ is more reasonable. Moreover, CCA$\approx 0.9$ is considered very high in prior work.
• Alignment trend: When the model gets larger, the alignment first increases, because the function class of $\Phi$ becomes closer to the entire $L^2$ space, so the optimizer of the pretraining objective is closer to the top eigenfunctions. However, when the model is already large enough, making it larger makes optimization harder. Hence, with the same number of pretraining steps, a larger model will be farther away from the minima, and the alignment decreases.

2. Updated related work

Based on the suggestions of the reviewers, we extend the discussion of the present paper's relation to the prior work as follows, which will be moved to the main body in the final version.

Related Work

Understanding the representations learned by an encoder has long been a central topic in machine learning research. Prior work has developed quite different theoretical frameworks for different pretraining methods, but these frameworks are typically not transferable across different settings. This paper provides a unified framework that has a very broad scope, covering learning, SSL based on augmentation, supervised learning, graph representation learning, and more.

In the pre-deep-learning-boom era, early work on manifold learning revealed the connection between representation learning and extracting the top eigenfunctions of a kernel (Bengio et al., 2004; Coifman & Lafon, 2006). Moreover, using the eigenvectors of the graph Laplacian as node representations on graphs was a classical technique in graph applications (Belkin & Niyogi, 2002; Zhu et al., 2003).

On the theoretical understanding of deep representations, there are two lines of work that are closely related to this paper. The first line studies representation alignment (Kornblith et al., 2019; Canatar et al., 2021; Huh et al., 2024; Fumero et al., 2024). Representation similarity has also been studied in neuroscience (Kriegeskorte et al., 2008). These papers mainly focus on comparing two representations. While we aim to evaluate a single representation and the context on which it is trained, we use the tools developed by these papers in our analysis.

The second line develops the spectral theory of self-supervised learning (SSL). SSL has achieved remarkable success in recent years (Radford et al., 2019; Chen et al., 2020; Zbontar et al., 2021; Bardes et al., 2022; He et al., 2022; Assran et al., 2023). HaoChen et al. (2021); Johnson et al. (2023) related contrastive learning to the spectrum of the augmentation graph and the positive-pair kernel, and Munkhoeva & Oseledets (2023) related SSL to matrix completion. Later, Zhai et al. (2024) extended the spectral theory to all SSL methods, not just contrastive ones. The present work further extends this theory to representation learning in its most general form, beyond SSL.

Besides, other prior theoretical work on SSL studied its training dynamics (Damian et al., 2022; Jing et al., 2022; Tian, 2022) and built its connection to information theory (Achille & Soatto, 2018; Balestriero & LeCun, 2022; Shwartz-Ziv et al., 2023).

Another line of work for characterizing the representations aims to learn disentangled or causally associated representations (Higgins et al., 2018; Scholkopf et al., 2021). It is shown that such representations can be provably recovered, provided there is sufficient variability in the environments, for instance by indexing the environments via sufficiently varying auxiliary variables or interventions (Khemakhem et al., 2020; Varıcı et al., 2024; Buchholz et al., 2023; Yao et al., 2024). Some of these results further require stringent parametric assumptions.

Thank you for your thoughtful review. We address your concerns as follows:

1. Our results are applicable to larger datasets

We conduct more experiments on larger datasets such as MNIST and CIFAR-10. We initially used datasets with $<$ 30K samples (largest: 28,155; see App. F) since most experiments compare the pretrained $\Phi$ with kernel PCA, which does not scale well to large datasets. However, our theoretical results are independent of dataset size, and our metric is applicable more broadly. Here we show it on MNIST and CIFAR-10.

On MNIST, we use LeNet as $\Phi$ and random cropping with various crop ratios as contexts. Spectra of these contexts are estimated using the method in lines 356–368. For instance, see the estimated spectrum for crop ratio of $0.3$: https://i.postimg.cc/bYQP1N46/mnist1.jpg.

We plot the prediction error of a linear probe on $\Phi$ (blue) alongside $\tau_d$ (orange, scaled) at crop ratio 0.3 here: https://i.postimg.cc/3rg4SGkm/mnist3.jpg, which shows that $\tau_d$ tracks the actual error across different $d$. We further vary the crop ratio from 0.1 to 0.9 and compare $\tau$ with the prediction error of a linear probe trained on $\Phi$. The result (https://i.postimg.cc/2yzTMwGX/mnist2.png) shows a strong correlation.

On CIFAR-10, we use ResNet-18 with SimCLR augmentation as the context. See the estimated spectrum at https://i.postimg.cc/hGTcDLW0/cifar1.jpg. In https://i.postimg.cc/ZqQcWJpL/cifar2.png, we plot the prediction error of a linear probe trained on $\Phi$ (blue) with $\tau_d$ (orange, scaled to fit the image). Again, $\tau_d$ tracks the actual error, supporting its usefulness in choosing dimension $d$.

We will add these experiments to the paper.

2. The benefits of designing better contexts

We proved that for a fixed context, making the model larger has diminishing returns, so it follows as a natural logical consequence that better contexts are necessary for further improvement. Thus, we only intended our experiments to provide a simple empirical illustration rather than corroboration. We also note the increasing empirical evidence in the literature: many recent advancements in pretraining are due to better contexts. For example, as the authors of SimCLR noted, its success owed greatly to its aggressive crop ratio and color distortion.

3. The usefulness of representations

The experiment in Section 4.2 aims to show that as the model gets larger, $\Phi$ becomes more aligned with the top-d eigenfunctions. However, a better alignment does not necessarily imply better performance at a downstream task. Whether $\Phi$ is good on a particular task depends on the compatibility between the context and the task, which we prove in Section 4.1.

We also improved this experiment. See point 1 in our response to Reviewer R5n1.

4. CCA versus CKA

We use CCA but not CKA because our setting is different from that in Kornblith et al. In their setting, they want the alignment metric to be invariant under orthogonal transformations, but not under other invertible linear transformations on $\Phi$. That's why they used CKA. In contrast, we want the metric to be invariant under invertible linear transformations on $\Phi$ because they do not affect the performance of the downstream linear probe, so we use CCA.

Moreover, CCA is equivalent to linear CKA if both representations are centered and whitened. We also evaluate the CKA when the representation is $[s_1 \mu_1, \cdots, s_d \mu_d]$, that is each singular function is multiplied by the singular value. We run the experiment in Section 4.2 with a fixed width 512 and varied depths. The result is plotted at https://i.postimg.cc/Jzrbc00M/Picture1.png. The plot shows that the trends of CCA and CKA are very similar.

5. Reproducibility

We will add details to the appendix. We also kindly point out that we have attached our code in the supplementary material, and all experiments are run with fixed random seeds, so all results can be exactly reproduced.

6. Neural collapse and scaling laws

Our remarks show that our theory can explain many empirical phenomena and cover different ML paradigms. We believe that including these remarks is important since they show that our theory has real explanatory power. These should be viewed similar to brief remarks in a later section such as conclusions where such discussions are common. We are happy to move these to a later section if the reviewers see fit.

7. Paper updates

We have updated the related work section. See our response to Reviewer R5n1.

We appreciate your feedback and hope that our response answers all your questions. We are happy to answer any follow-up questions.

Thank you for your thoughtful review. We're glad that you find our theory generally good, interesting and valuable. We address your concerns below:

1. Experiments in Section 4.2 (scaling) updated

We improved the setting and observed much higher alignments. Due to the 5000-character limit, please see point 1 in our response to Reviewer R5n1.

All experiments use 15 different random seeds. The standard deviation plot (of one experiment) at https://i.postimg.cc/2651NYg4/Picture3.png shows low variation.

2. Our results are applicable to larger datasets

We added experiments on larger datasets such as MNIST and CIFAR-10. See point 1 in our response to Reviewer RMLf.

3. Figure 2

This figure illustrates how the association between $X$ and $A$ affects the spectrum’s decay rate, and how $\tau_d$ tracks the prediction error of a $d$-dimensional encoder. We divide $\tau$ by 5 for visualization. We’ll enlarge the figures to improve readability.

4. Metrics in [2, 3] do not fit our problem

There is a fundamental difference between our metric $\tau$ and those in [2, 3]. They use the eigenvalues $\lambda_i$ of $\Phi \Phi^{\top}$: $\langle \Phi, \Phi \rangle f_i = \lambda_i f_i$. In contrast, our theory is based on the spectrum of the context: $\langle \Phi, T_{P^+}\Phi\rangle f_i=s_i^2 \langle\Phi, \Phi\rangle f_i$. These spectra are fundamentally different. $s_i^2$ is invariant under invertible linear transformations on $\Phi$, whereas $\lambda_i$ is not. Since such transformations don’t affect downstream linear probe performance (weights can be adjusted accordingly), metrics in [2, 3] are not suitable for our setting.

5. Elaboration on the two failure cases of our metric

Both failure cases stem from the fact that the metric depends only on the spectrum (singular values) of the context.

• Case 1: The association of the context is too weak/strong. Our metric will indicate that the context is bad, but it is still possible that for a particular task, the context is good.
• Case 2: The metric might not be able to compare different types of contexts. It may indicate similarity, though one context may perform well on a specific task while the other does not.

However, the experiment in Sec.5 shows that such failure cases are rare.

6. Why we use kernel PCA and VICReg

Kernel PCA is the standard way to extract the exact top eigenfunctions. It is not scalable, and we compare deep learning based methods with it.

We only use VICReg in the experiments because, as shown in Section 3, many objectives such as spectral contrastive loss and masked autoencoders, are equivalent to VICReg in that they are all minimized by the top-d singular functions. To demonstrate this, we run the experiment in Sec.4.1 with both VICReg and spectral contrastive loss (with width 512, varied depths). Results at https://i.postimg.cc/Hncjj2Yn/Picture2.png show very similar performance, differing slightly due to optimization. Hence, we use a single method in experiments, given their equivalence.

7. Whether the methods "solve the task"

No encoder solves all tasks. While we proved that many pretraining objectives learn the contexture, they are not guaranteed to solve arbitrary tasks. In Sec. 4.1, we proved that the encoder’s performance depends on the compatibility between the task and the context. If they are compatible, then an encoder that learns the contexture is guaranteed to succeed.

8. Whether the context variable depends on the encoder

In general, the context is defined prior to training the encoder, so it does not depend on the encoder. There are two ways to encode additional context in the encoder:

• The inductive bias of the architecture (such as translation invariance of CNNs)
• "Smoothed" encoders, such as adding Gaussian noise to the input

The first method changes the model and the second method changes the input. In both cases, adding additional context weakens the association, hence implicitly changes the level of association. Our theory does not analyze the effect of the inductive bias, and we pose it as an open problem.

9. What is $g$ in supervised learning?

In supervised learning, $\Phi$ extracts the eigenfunctions of $T_{P^+}\Lambda T_{P^+}^*$, so $g(a) = (T_{P^+}^* \Phi)(a) = E[\Phi(X) | \text{class } a]$. By neural collapse, the representations of samples from the same class $a$ collapse to a cluster, and $g(a)$ is the center of that cluster.

10. Paper updates

We have updated the related work section. See our response to Reviewer R5n1.

We also added a new limitation paragraph. See our response to Reviewer rV84.

We appreciate your feedback and hope that we've answered all your questions. We are happy to address any remaining concerns.