A Unified Theoretical Framework for Understanding Difficult-to-learn Examples in Contrastive Learning

Q4: Can your analysis be generalized to InfoNCE loss? As paper [1] shows through augmentation graph that InfoNCE is also closely related to the decomposition of similarities graphs. [1]: Contrastive Learning Is Spectral Clustering On Similarity Graph, ICLR 2024

A4: Yes, the analysis of difficult-to-learn examples could potentially be generalized to the similarity graph defined in [1] through the stochastic block model (Holland et al., 1983), which is a widely used random graph model $G=(\mathcal{X},E)$. The graph node is the same as that of augmentation graph, and the edge (undirected and unweighted) is in the edge set with probability $w\_{xx'}$. The similarity graph defined in [1] has edge weight \pi\_{ij}=1/(\\#\mathrm{aug}),where \\#\mathrm{aug} denotes the number of augmentations per sample. Therefore, its similarity matrix can be viewed as the normalized ajacency matrix of the random graph $G$, i.e., denoting $\boldsymbol{A}$ as the adjacency matrix of augmentation graph defined in our paper, and $\boldsymbol{\pi}$ as the similarity matrix defined in [1], then we have $\boldsymbol{\pi} = \bar{\boldsymbol{A}'}$, where $\mathbb{E}\boldsymbol{A}'=\boldsymbol{A}$. Note that according to [1], on each of the randomly sampled $\boldsymbol{\pi}$, InfoNCE is equivalent to running spectral clustering on $\boldsymbol{\pi}$, i.e. its error bound is related to the top eigenvalues of $\boldsymbol{\pi}$. Then by Lemmas 3 and 4 in Shen et al.(2022), we could use matrix concentration bounds to concentrate the top eigenvectors of $\boldsymbol{A}$ to those of $\boldsymbol{A}=\mathbb{E}\boldsymbol{A}'$ and use matrix perturbation analysis to show that the predictor learned using $\boldsymbol{A}'$ is close to the “ideal” one learned using $\boldsymbol{A}$. By this, we can show that the error bound of InfoNCE is in expectation related to the top eigenvalues of $\boldsymbol{A}$. Finally, according to the analysis in our paper on how difficult-to-learn samples affect the eigenvalues of $\boldsymbol{A}$, we can get the influence of difficult-to-learn samples on the error bound of InfoNCE.

Please also note that "as proved in Johnson et al. (2022), the spectral contrastive loss and the InfoNCE loss share the same population minimum with variant kernel derivations" (line 157). This result could be a simpler way of showing that our theoretical results on the negative impact of difficult-to-learn examples also applies to InfoNCE.

• Holland et al. Stochastic blockmodels: First steps. Social Networks, 1983.
• Shen et al. Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation. in ICML, 2022.
• Johnson et al. Contrastive learning can find an optimal basis for approximately view-invariant functions. In ICLR, 2022.

---

Thanks for your insightful and constructive comments. Hope our explanations, analysis, and additional experiments can address your concerns.

We express our sincere gratitude to Reviewer yxey for appreciating our proposed theoretical framework based on difficult-to-learn examples in contrastive learning, as well as for recognizing the positive results of our empirical experiments. We address your concerns below.

---

Q1: The tightness of the derived bounds should be validated through experiments.

A1: Unfortunately, according to the definition in HaoChen et al., it is scarcely possible to reveal the ground truth augmentation graph, making it impossible to get the real values of $\alpha$, $\beta$, $\gamma$, and $\delta$ in the error bounds. On the one hand, in the population augmentation graph, the vertex set is all augmentation data across the distribution, which is exponentially large. On the other hand, it is hard to measure the ground truth similarity between these augmentations. Directly measuring the pixel-level similarity does not typically makes sense, and human labeling on such data can be subjective and impractical. (This difficulty has also been discussed in [1].) Nonetheless, here we use the cosine similarity matrix of the learned representations with two augmented views per sample as a proxy of the augmentation graph, and hopefully we could cast a glance at the relative values (but of course not the ground truth values) of $\alpha$, $\beta$, and $\gamma$. Based on this, we validate the trending of the derived bounds (the bound getting worse with difficult-to-learn examples increasing) instead of the specific bound values.

Specifically, we use the mixed CIFAR-10 datasets with mixing ratios varying from 0% to 30%, where 0% represents the standard CIFAR-10 without mixing. The experimental parameter settings can be referenced to Appendix A.3 of the original paper. For each class of samples, we sort them based on the difference between the maximum and second-largest values after applying softmax to the outputs, and select the 8% （the ratio is consistent with what is reported in the paper）smallest differences as the difficult-to-learn examples, as described in the paper. For the calculation of $\alpha$, we take the mean of the similarity between all samples of the same class. For the calculation of $\beta$, we take the mean of the similarity for the sample pairs from different classes that do not contain the difficult-to-learn examples. For the calculation of $\gamma$, we take the mean of the similarity for the sample pairs from different classes that contain the difficult-to-learn examples.

In the above table, we show that as the mixing ratio increases, the linear probing accuracy drops, and the $(K+1)$-th eigenvalue increases. Note that the classification error (left hand side of Eq.(4)) is 1-acc, and the error bound (right hand side of Eq.(4)) increases with the eigenvalue increasing. This result indicates that as the difficult-to-lean examples increases, the classification error and the bound share the same variation trend, thus validating Theorem 3.2 that larger $\gamma-\beta$ results in worse error bound.

---

Dear Reviewer yxey,

We would like to express our sincere gratitude for the time and effort you have dedicated to reviewing our manuscript and providing thoughtful feedback. We understand that this is a particularly busy period, and we greatly appreciate the demands on your time.

We have made every effort to carefully address your comments and to conduct additional experiments as per your suggestions. As the Author-Reviewer discussion period is drawing to a close, we would be truly grateful if you could kindly let us know whether our responses have adequately addressed your concerns.

Once again, thank you for your invaluable contributions to our work.

Best regards, Authors

Dear Reviewer yxey,

We have made new progress regarding the ImageNet-1k experiment that we responded to a week ago. We have now obtained the results after running for 100 epochs, and the experimental results are as follows:

From the experimental results, it is clear that our proposed method can achieve performance improvements on the real-world dataset, ImageNet-1k, similar to those observed on other datasets. Our experiments are still ongoing, and we will provide timely updates with new results as they become available.

In addition, we have addressed each of your other concerns one by one. We eagerly look forward to your feedback on the rebuttal and further discussion, as we believe this is crucial for enhancing the quality of this paper.

Dear Reviewer yxey,

We have carefully addressed your concerns and we are still looking forward to your reply.

Best regards,

The Authors

We express our sincere gratitude to Reviewer KG9m for appreciating both the novel insights our paper offers into the impact of difficult-to-learn examples in contrastive learning and the robustness of the theoretical analysis, as well as the straightforward implementation of the proposed solutions. We address your concerns below.

---

Q1: Although the authors find that removing certain training examples consistently improves unsupervised contrastive learning performance, the theoretical results are limited to spectral contrastive learning. It may be more accurate to reflect this focus in the title.

A1. Thank you for the advice. We replace the title with "Understanding Difficult-to-learn Examples in Contrastive Learning: A Theoretical Framework for Spectral Contrastive Learning" in our revised manuscript. It is also worthwhile mentioning that "as proved in Johnson et al. (2022), the spectral contrastive loss and the InfoNCE loss share the same population minimum with variant kernel derivations" (line 157). This indicates that our theoretical results could potentially be extended to other contrastive learning paradigms, e.g. methods using the InfoNCE loss.

---

Q2: The experiments are relatively small in scale, with the largest dataset being Tiny ImageNet. Evaluating the approach on larger datasets could strengthen the findings and demonstrate broader applicability.

A2: Following your suggestion, we evaluated our method on the Imagenet-1k dataset, which contains 1,000 categories and 1,281,167 training samples. Due to limited computing resources and time, we used ResNet18 as our backbone, set the batch size to 256, and resized each image to 96x96. We set the learning rate to 0.5 and the base temperature to 0.1. We chose 0.01 as the posHigh and 0.5 as the posLow. We set $\sigma$ to 0.1 and $\rho$ to 0.7. We also evaluated the models using linear probing. When evaluating, we set the batch size to 256 and the learning rate to 1. The specific results are shown in the table below.

From the results on the real-world dataset, Imagenet-1k, which contains more categories, we can see that even after running for only 50 epochs, our method achieves a performance improvement trend consistent with the results mentioned in the paper, compared to the baseline method. We will update as soon as we have new results and we hope that this set of experiments will strengthen the findings and demonstrate broader applicability of this paper.

---

Thanks for your insightful and constructive comments. Hope our explanations and additional experiments can address your concerns.

Dear Reviewer KG9m,

We would like to express our sincere gratitude for the time and effort you have dedicated to reviewing our manuscript and providing thoughtful feedback. We understand that this is a particularly busy period, and we greatly appreciate the demands on your time.

We have made every effort to carefully address your comments and to conduct additional experiments as per your suggestions. As the Author-Reviewer discussion period is drawing to a close, we would be truly grateful if you could kindly let us know whether our responses have adequately addressed your concerns.

Once again, thank you for your invaluable contributions to our work.

Best regards, Authors

Dear Reviewer KG9m,

We have made new progress regarding the ImageNet-1k experiment that we responded to a week ago. We have now obtained the results after running for 100 epochs, and the experimental results are as follows:

From the experimental results, it is clear that our proposed method can achieve performance improvements on the real-world dataset, ImageNet-1k, similar to those observed on other datasets. Our experiments are still ongoing, and we will provide timely updates with new results as they become available.

In addition, we have addressed each of your other concerns one by one. We eagerly look forward to your feedback on the rebuttal and further discussion, as we believe this is crucial for enhancing the quality of this paper.

Dear Reviewer KG9m,

We have carefully addressed your concerns and we are still looking forward to your reply.

Best regards,

The Authors

Q3: A visualization and/or quantitative assessment of the augmentation similarity graph in small-scale datasets (perhaps not feasible, though). 1) To what extent do $\beta$ and $\gamma$ differ in real-world datasets (under this work's intuitive assumption)? 2) In what kind of dataset $\beta$ and $\gamma$ are further separated, compared to other datasets?, etc.

A3: Unfortunately, according to the definition in HaoChen et al., it is scarcely possible to reveal the ground truth augmentation graph. Firstly, in the population augmentation graph, the vertex set is all augmentation data across the distribution, which is exponentially large. Secondly, it is hard to measure the ground truth similarity between these augmentations. (Directly measuring the pixel-level similarity does not typically makes sense, and human labeling on such data can be subjective and impractical.) Nonetheless, we use the cosine similarity matrix of the learned representations with two augmented views per sample as a proxy of the augmentation graph, and hopefully we could cast a glance at the relative values (but of course not the ground truth values) of $\alpha$, $\beta$, and $\gamma$.

Specifically, we use the mixed CIFAR-10 datasets with mixing ratios varying from 0% to 30%, where 0% represents the standard CIFAR-10 without mixing. The experimental parameter settings can be referenced to Appendix A.3 of the original paper. For each class of samples, we sort them based on the difference between the maximum and second-largest values after applying softmax to the outputs, and select the 8% (the ratio is consistent with what is reported in the paper) smallest differences as the difficult-to-learn examples, as described in the paper. For the calculation of $\alpha$, we take the mean of the similarity between all samples of the same class. For the calculation of $\beta$, we take the mean of the similarity for the sample pairs from different classes that do not contain the difficult-to-learn examples. For the calculation of $\gamma$, we take the mean of the similarity for the sample pairs from different classes that contain the difficult-to-learn examples.

We show that in this case, 1) the differences between $\beta$ and $\gamma$ lie in the range $[1.8\%,3.3\%]$, and 2) datasets with less separable inter-class samples (the mixed-CIFAR datasets with higher mixing ratio), have higher $\gamma-\beta$ values.

---

Q4: In results like Table 1, it is perhaps beneficial to show more statistics beyond classification accuracy, e.g., the number of removed datapoints (overall and in each class), etc.

A4: To better understand the results in Table 1, we present the distribution of the removed sample pairs from different classes in the CIFAR-10 dataset using our method. The results are shown in the table below.

We can observe that there are more difficult-to-learn example pairs removed between categories that are easily confused with each other (for example, the 3-5 sample pair represents two similar and easily confused animals, cats and dogs, with a count of 241,832, while the 0-9 pair, representing two types of vehicles—car and truck—has a count of 256,489). This observation aligns with our intuition. We hope that this data presentation helps you better understand Table 1.

Q5: The inequality around line 212, $\frac{(1-\alpha) + r(\gamma - \beta )}{(1-\alpha) + n\alpha + nr\beta + n_dr (\gamma - \beta )} > \frac{1-\alpha}{(1-\alpha) + n\alpha + nr\beta}$ When does this hold? Is it practical for it to hold in most datasets?

A5: This inequality holds as long as $\frac{1}{n_d} > \frac{1-\alpha}{(1-\alpha) + n\alpha + nr\beta}$ or equivalently $\frac{n_d-1}{n} < \frac{\alpha+r\beta}{1-\alpha}$. That is, given $\alpha$, $\beta$, and $r$, as long as $n_d/n$ is small, this inequality always holds. For CIFAR-10, $n_d/n \approx 0.08$ in our experiments, whereas according to A3, $\frac{1-\alpha}{(1-\alpha) + n\alpha + nr\beta} = 4.51$, significantly greater than $\frac{n_d-1}{n}$.

---

Q6: In line 1019, "when $n_d < k \leq n_d + r + 1$" - This seems rather a strict condition, are there further explanations on this? (or perhaps it is explained but I have overlooked?)

A6: We apologize for the typo here. It should be $r+1\leq k<n_d+r+1$. On the one side, it is natual to assume that in most datasets, the dimension $k$ is larger than the number of classes $r+1$, since the number of classes typically cannot be too large. On the other side, the number of difficult-to-learn samples $n_d$ is usually larger, as the overall augmented sample size is usually large. Specifically, we have $n_d = n_{aug} \cdot \rho_d \cdot n$, where we denote $n_{aug}$ as the number of augmented views of each sample and $\rho_d$ as the fraction of difficult-to-learn samples in the dataset. Theoretically, $n_{aug}$ should be sufficiently large since the augmentation graph describes the similarity between all kinds of augmentations (despite that it is usually chosen to be 2 in empirical settings). According to our experiments, $\rho_d$ is around $8\\%$. Therefore, it is easy for $n_d + r + 1$ to exceed $k$.

---

Q7: What is the "pixel-mixing" method in Section 2 line 107?

A7: The "pixel-mixing" method involves selecting a random image from a different class and then stitching the two images together by splitting each image into halves. Specifically, we take the first half of the current image and the second half of a randomly selected image from another class and combine them to form a new mixed image. This process is used to augment the data, creating a dataset with more difficlut-to-learn examples.

---

Q8: In line 344-345, what features are being used? Is the network being pre-trained on some dataset before the unsupervised contrastive learning process?

A8: We do not use any other pre-trained models, but instead, we train the model from scratch based on the optimization objective detailedly described in Appendix A.2, specifically addressing the presence of difficult-to-learn examples.

---

Q9: In Figure 4 & 5, what are the other hyper-parameters when using the tuned parameter?

A9: Figures 4 & 5 present ablation studies conducted on the CIFAR-100 dataset. As described in Section A.3, we set the batch size to 512, the learning rate to 0.5, and the base temperature to 0.1. We chose 0.013 as the posHigh and 0.5 as the posLow. We set $\sigma$ to 0.1 and $\rho$ to 0.7. We also evaluated the models using linear probing. During evaluation, we set the batch size to 256 and the learning rate to 1. Specifically, in Fig 4(a), we only changed posHigh, in Fig 4(b), we only changed posLow, in Fig 5(a), we only changed $\sigma$, and in Fig 5(b), we only changed $\rho$, with all other parameters remaining consistent with the above settings.

---

Q10: Is Section A.4 talking about the combined method?

A10: Yes, Section A.4 is talking about the combined method.

---

Thanks for your insightful and constructive comments. Hope our explanations, analysis, and additional experiments can address your concerns.

We express our sincere gratitude to Reviewer aLaR for appreciating the theoretical framework we propose and the theoretical analysis we made on Margin Tuning and Temperature Scaling. We address your concerns below.

---

Q1: The simplification is made such that the direct computation of eigenvalues of $A$ is possible, yet I feel that there lacks an intuitive, or preferably, empirical justification for the connection between the idealized theoretical framework and the practical case. The only direct explanation I could find is around Sec 3.2, "As difficult-to-learn examples lie around the decision boundary, they should have higher augmentation similarity to examples from different classes." (lines 164-166), which is a rather ambiguous intuition or belief.

A1: Firstly, through a simple example of binary classification, we intuitively show that sample pairs with higher augmentation similarity are guaranteed to have at least one sample located near the boundary. Let $x_1$ and $x_2$ be two examples belonging to Class 0 and Class 1 with confidence $p$ and $q$, respectively, i.e., $\mathrm{P}(y=0|x_1)=p$ and $\mathrm{P}(y=1|x_2)=q$, where $p, q \in (1/2,1]$. Then the similarity originated from label posterior probability (concept referring to https://arxiv.org/abs/2306.04160) is $s=(p, 1-p)\cdot(q,1-q)^\top=p+q-2pq$. If $x_1$ lies around the boundary, i.e. $p=1/2+\varepsilon$, $\varepsilon\to 0$, then $s=1/2+(1-2q)\varepsilon$, which is greater than the average different-class similarity 3/8 (Assuming $p,q \sim \mathrm{Unif}(1/2,1]$, then $\mathbb{E}_{p,q}s=3/8$). Therefore, if we select different class pairs with similarity higher than 1/2, the selected difficult-to-learn pairs are guaranteed to have at least one difficult-to-learn sample.

Secondy, we discuss that a relaxation on the ideal adjacency matrix (randomizing the similarity values) does not affect our main theoretical results (refer to A2). Thirdly, using a proxy of augmentation graph, we empirically assess the relative values of $\alpha$, $\beta$, and $\gamma$.

---

Q2: A relaxation on the ideal adjacency matrix, e.g., allowing entries to take values such as $(\alpha - \epsilon, \alpha + \epsilon) \dots$; or being stochastic with some distribution.

A2: Thank you for the valuable advice. The adjacency matrix could be relaxed by adding random terms to the similarity values. Specifically, we replace $\boldsymbol{A}$ with $\boldsymbol{A}'=(a'\_{ij})$, where $a'\_{ii}=1$, and $a'\_{ij}=a_{ij}+\epsilon \cdot \varepsilon\_{ij}$ for $i\neq j$, $a\_{ij}$ takes values in $\{\alpha, \beta, \gamma\}$, $\varepsilon\_{ij}=\varepsilon\_{ji}$ are i.i.d. Gaussian random variables with mean 0 and variance 1, $\epsilon>0$ is a small constant. Then $\boldsymbol{A}'$ can be decomposed into $\boldsymbol{A}'=\boldsymbol{A} + \epsilon\cdot\boldsymbol{W} - \epsilon \cdot \mathrm{diag}(\varepsilon_{ii})$, where $\boldsymbol{W}$ turn out to be a real Wigner matrix. According to Wigner’s semicircle law, we have the eigenvalues of $\boldsymbol{W}$ with the probability density function $f(\nu)=\frac{1}{2\pi}\sqrt{4-x^2}\boldsymbol{1}[|x|\leq 2]$. Them following the similar approach in the proof Theorem 3.2, we are able to calculate the upper bound of (the expected value of) the $K+1$ largest eigenvalue of $\boldsymbol{A}'$, and accordingly reach a downstream error bound. Note that the effect of this random similarity $\epsilon \cdot \varepsilon_{ij}$ is to add an additional term to the upper bound of the eigenvalue, and the effect is the same regardless of $\boldsymbol{A}$ (e.g. with and without the existence of difficult-to-learn examples). Therefore, our theoretical results still hold under this relaxation.

Dear Reviewer aLaR,

We would like to express our sincere gratitude for the time and effort you have dedicated to reviewing our manuscript and providing thoughtful feedback. We understand that this is a particularly busy period, and we greatly appreciate the demands on your time.

We have made every effort to carefully address your comments and to conduct additional experiments as per your suggestions. As the Author-Reviewer discussion period is drawing to a close, we would be truly grateful if you could kindly let us know whether our responses have adequately addressed your concerns.

Once again, thank you for your invaluable contributions to our work.

Best regards, Authors

We express our sincere gratitude to Reviewer eRke for appreciating the intuitive and interesting idea of determining difficult-to-learn examples. We address your concerns below.

---

Q1: The terminology difficulty-to-learn examples seems to be confusing because indeed, the paper focuses on difficulty-to-learn pairs (different classes and stay closely to the boundary).

A1: The concept difficulty-to-learn examples is important in the motivation of our work, i.e., difficulty-to-learn examples (boundary examples), which are vitally important in supervised learning, can actually hurt the performance of unsupervised contrastive learning. As contrastive learning leverages examples in a pairwise manner, we require the concept of difficult-to-learn sample pairs, i.e., sample pairs that include at least one difficult-to-learn sample. To avoid possible confusion, we clearly emphasize the relationship between "difficult-to-learn samples" and "difficult-to-learn pairs" at the beginning of Section 3.2 in our revised manuscript.

---

Q2: The definitions of difficulty-to-learn or easy-to-learn pairs are not rigorous.

A2: In this paper, we define difficult-to-learn sample pairs as sample pairs that include at least one difficult-to-learn sample. "In real image datasets, as difficult-to-learn examples rely on the specific classifier trained in the supervised learning manner, we can not preciously know the ground truth difficult-to-learn examples" (line 102-104). Therefore, we instead define the difficulty-to-learn pairs as different-class sample pairs with higher similarity, because "pairs containing difficult-to-learn samples exhibit higher similarities than other different-class pairs" (line 63). Correspondingly, easy-to-learn pairs are defined as different-class sample pairs containing no difficult-to-learn samples, or different-class sample pairs with lower similarity. We add these definitions at the beginning of Section 3.2 in our revised manuscript.

---

Q3: In the theory development in Theorems 3.1, 3.2, and so on, it is unclear how to train the feature extractor f for obtaining feature vectors. If it is learned using Eq. (1) similar to HaoChen et al., it is unclear how alpha beta gamma are relevant.

A3: First, we clarify that $\alpha$, $\beta$, and $\gamma$ are not parts of the algorithm. Instead, they are part of the theoretical modeling, representing the similarities between different kinds of sample pairs, based on which we derive our main theoretical results that difficult-to-learn samples hurt unsupervised contrastive learning, and this negative effect can be fixed through methods such as sample removal, margin tuning, and temperature scaling. In Theorems 3.1 and 3.2, $f$ is trained under standard (spectral) contrastive learning, but trained with different dataset (whether containing difficult-to-learn example or not). In Corollary 4.1, Theorem 4.3, and Theorem 4.5, $f$ is trained under contrastive learning with sample removal, margin tuning, and temperature scaling, repectively. In Theorems 4.3 and 4.5, we point out that the corresponding contrastive losses are Eq.(31) and Eq.(40) (lines 263 and 295). Besides, "the specific loss forms and algorithms can be found in Appendix A.2" (line 343).

---

Q6: The experiments are humble and the paper does not have strong practical implication.

A6: We respectfully acknowledge the reviewer’s concern about the practical implications of our work. However, as we emphasized at the beginning of Section 5, our primary focus is on the theoretical analysis, where we explore how different types of samples in contrastive learning impact generalization. The experiments are designed to validate these theoretical insights and demonstrate that the proposed approaches for improving performance are sound and applicable.

In summary, our experimental results demonstrate that the proposed method consistently achieves robust performance improvements on widely recognized contrastive learning datasets such as CIFAR-10, CIFAR-100, STL-10, and TinyImageNet (refer to Table 4). We also provide ablation studies (refer to Table 4) and hyperparameter analyses (refer to Figure 5 and Table 8).

Furthermore, during this discussion period, we conduct additional experiments validating our theoretical insights.

1. We conducted experiments on the ImageNet-1K dataset, which contains 1,000 categories and 1,281,167 training images. Due to limited computing resources and time, we used ResNet18 as our backbone, set the batch size to 256, and resized each image to 96x96. We set the learning rate to 0.5 and the base temperature to 0.1. We chose 0.01 as the posHigh and 0.5 as the posLow. We set $\sigma$ to 0.1 and $\rho$ to 0.7. We also evaluated the models using linear probing. When evaluating, we set the batch size to 256 and the learning rate to 1. The experimental results show that our method achieves consistent performance improvements on real-world datasets with a larger number of categories when running 50 epoches, we will update as soon as we have new results.

2. We use the cosine similarity matrix of the learned representations with two augmented views per sample as a proxy of the augmentation graph, and validate the trending of our derived bounds. Specifically, we use the mixed CIFAR-10 datasets with mixing ratios varying from 0% to 30%, where 0% represents the standard CIFAR-10 without mixing. We show that 1) datasets with less separable inter-class samples (higher mixing ratio), have higher $\gamma-\beta$ values, and 2) the classification error (1-acc, left hand side of Eq.(4)) and the bound (positively correlated with the $K+1$-th largest eigenvalue, right hand side of Eq.(4)) share the same variation trend.

These results highlight the practical relevance of our method, as it demonstrates effectiveness across datasets with varying complexity. We believe this set of experiments reinforces our theoretical framework and demonstrates the broader applicability of our work.

---

Thanks for your comments. Hope our explanations and additional experiments can address your concerns.

Dear Reviewer eRke,

We would like to express our sincere gratitude for the time and effort you have dedicated to reviewing our manuscript and providing thoughtful feedback. We understand that this is a particularly busy period, and we greatly appreciate the demands on your time.

We have made every effort to carefully address your comments and to conduct additional experiments as per your suggestions. As the Author-Reviewer discussion period is drawing to a close, we would be truly grateful if you could kindly let us know whether our responses have adequately addressed your concerns.

Once again, thank you for your invaluable contributions to our work.

Best regards, Authors

Dear Reviewer eRke,

We have made new progress regarding the ImageNet-1k experiment that we responded to a week ago. We have now obtained the results after running for 100 epochs, and the experimental results are as follows:

From the experimental results, it is clear that our proposed method can achieve performance improvements on the real-world dataset, ImageNet-1k, similar to those observed on other datasets. Our experiments are still ongoing, and we will provide timely updates with new results as they become available.

In addition, we have addressed each of your other concerns one by one. We eagerly look forward to your feedback on the rebuttal and further discussion, as we believe this is crucial for enhancing the quality of this paper.

Dear reviewer eRke,

We have carefully addressed your concerns and we are still looking forward to your reply. As there is some time left, we sincerely ask you to specify your concern about the experiments, so that we could possibly provide additional results in the remaining limited time to address your concerns better. As the description of your last concern is quite vague, would you please specify which part of the experiment you find "humble" and lacking "strong practical implication"? This could really help in further improving our paper.

In addition, we sincerely ask you to rethink about the confidence score. There seems to be a severe misunderstanding of our paper, as especially evidenced by Q3 and Q5.

Looking forward to your reply and further discussions.

Best regards,

The Authors.

Thanks the authors for your response.

Although in the main paper, we do not mention explicitly how you use the adjacency matrix in Figure 3d. However, when I check your proof for Theorems 3.1 and 3.2, in Eq. (22) and Eq. (23), you use the discretized adjacency matrix $A$ in Figure 3d for solving $||\bar{A}-FF^{T}||_{F}^{2}$ where $\bar{A}$ is the normalized matrix of $A$. This is more evident for this use because in Line 1035 to 1039, you obtain very specific eigenvalues and eigenvectors for A which is impossible for a general similarity matrix A. This means that to develop theories, you use the discretized adjacency matrix in Figure 3d which does not convince me. Similar observation for other theorems and corollaries.

Thank you for the timely response. We address your concern below.

---

Q. To develop theories, you use the discretized adjacency matrix in Figure 3d which does not convince me. Similar observation for other theorems and corollaries.

A. We would like to point out that in A4 of our previous response (and also in Appendix B.3), we discuss that the discretized values in the adjacency matrix can be easily extended to a generalized one by adding element-wise random variables, without harming the theoretical insights. To further elaborate, the effect of this randomization is to add an additional term to the upper bound of the eigenvalue. (Please note that different from Theorem 3.1, in the proof of Theorem 3.2 (Lines 1148-1155), we use the same mathematical tool to derive an upper bound of the eigenvalues instead of the specific values.) That means, the eigenvalues of the general similarity matrix are decomposed into two parts. The first part is the upper bound of the discretized adjacency matrix we derived in the proofs, and the second part is the eigenvalues of the mean-zero random matrix. (This could be roughly understood as a bias-variance decomposition, where the discretized matrix forms the bias term, and the randomized matrix forms the variance term.) As the "variance" term is the same regardless of the adjacency matrix, the relative quantity of the linear probing error bound relies only on the "bias" term, i.e. eigenvalues of the discretized matrix, and therefore our theoretical results still hold even under generalized modeling.

Perhaps easier to understand, we summarize it in a non-mathematical way. In the main paper we use the discretized adjacency matrix to keep the simplicity and clarity of the theorems and the theoretical insights. This framework "allows easier (tractable) analysis with the spectral contrastive loss" as commented by Reviewer aLaR. In Appendix B.3, we discuss how to extend the discretized adjacency matrix to a generalized one, and why our theoretical insights still hold under this extension. However, if you strongly insist the general similarity matrix should be reflected in the main paper, we can replace Figure 3d and the proofs of theorems according to Appendix B.3 in our next version (considering that the pdf revision period is now over after several rounds of our discussions).

---

We are still open to further discussions. If any of our previous responses have not fully addressed your questions, please do let us know.

Thank you for conducting more experiments and the detailed response.

Indeed, as you have shown in the new experiment, there's a significant difference between the mean of considered $\beta$ and $\gamma$ measures for real-world datasets. I appreciate your effort and this result. That being said, even with the proposed relaxation, the theoretical framework is very interesting yet still a bit unconvincing for me, so that I'd like to keep my current score. The main reason is that, as also pointed out by reviewer eRke, it is still unconvincing that the discretized $A$ resembles the real $A$, since the distribution or overlap between $\beta$ and $\gamma$ might be critical to the behavior of the training and trained models. Although such a relaxation is possible, it is still unclear that 1) to what extent can we add a noisy $W$ to the ideal $A$ without hurting the results (i.e., any bounds etc.) and 2) If the only difference between the ideal $A$ and real $A$ in datasets is a GOE $W$. I believe that such limitation can better (only) be covered by a further research with intensive experiments and/or theoretical discussions to support the claims, which might be beyond the scope of current work. Therefore, although I lean towards to acceptance, I cannot raise my score to 8. Nevertheless, I really appreciate the fruitful discussion and experiments provided by the authors.

Thank you for the reply. We address your concerns with further relaxation of the assumptions (verified empirically) (A1) and with additional error bounds (A2). (For better explanations, we change the question order.)

---

Q1. If the only difference between the ideal $A$ and real $A$ in datasets is a GOE $W$.

A1. Unfortunately, this is not guaranteed. However, to derive the generalized theoretical bounds, the difference between the ideal $A$ and real $A$ does not have to be a GOE. Instead, the generalized results only require the difference $\boldsymbol{W}=(\varepsilon_{ij})$ to be a Wigner matrix so we can use Wigner’s Semicircle Law to get the eigenvalues of $\boldsymbol{W}$. That is, the GOE assumption could be further relaxed to a Wigner matrix, i.e. a symmetric random matrix where $\varepsilon_{ii}$ are i.i.d. distributed with $\mu(\varepsilon_{ii})$ and $\sigma(\varepsilon_{ii})$ bounded, and $\varepsilon_{ij}$ ($i<j$) are i.i.d. distributed with $\mu(\varepsilon_{ij})=0$ and $\sigma(\varepsilon_{ij})=1$.

We use the proxy augmentation graph to verify this generalized assumption. We denote $\boldsymbol{W}'$ as the difference between the proxy matrix $\boldsymbol{A}'$ and the ideal matrix $\boldsymbol{A}$, i.e. $\boldsymbol{A}' = \boldsymbol{A} + \boldsymbol{W}'$. By calculations, $W'$ has mean zero and standard deviations 0.1138 (CIFAR-10), 0.0821 (CIFAR-100), and 0.1232 (Imagenet-1k). That is, we can normalize $\boldsymbol{W}'$ to be a Wigner matrix $\boldsymbol{W}$ with $\varepsilon_{ii}$ following the Dirac distribution ($\mu(\varepsilon_{ii})=\sigma(\varepsilon_{ii})=0$). (The diagonal elements of $\boldsymbol{A}'$ and $\boldsymbol{A}$ are both 1, so the diagonal elements of $\boldsymbol{W}'$ is 0.) Then we have $\boldsymbol{A}' = \boldsymbol{A} + \epsilon\boldsymbol{W}$, with $\epsilon=0.1138$ (CIFAR-10), $0.0821$ (CIFAR-100), or $0.1232$ (Imagenet-1k).

---

Q2. To what extent can we add a noisy $W$ to the ideal $A$ without hurting the results (i.e., any bounds etc.)

A2. Under the generalized assumption discussed in A1 ($\boldsymbol{A}' = \boldsymbol{A} + \epsilon\boldsymbol{W}$), we derive additional error bounds to show the effect of $W$. The range of $\epsilon$ is especially discussed in Remark 2.

Theorem 3.1 (Generalized version) Denote $\mathcal{E}\_{\mathrm{w.o.}}$ as the linear probing erorr of a contrastive learning model trained on a dataset without difficult-to-learn examples. Under the generalized assumption that $\boldsymbol{A}' = \boldsymbol{A} + \epsilon\boldsymbol{W}$, where $\boldsymbol{W}$ is a Wigner matrix with $\varepsilon_{ii}$ following the Dirac distribution, then if $n(r+1)$ is large enough, we have

$$\mathcal{E}_{\mathrm{w.o.}} \leq \frac{4\delta}{1 - \frac{1-\alpha}{(1-\alpha)+n\alpha+nr\beta}-\frac{1}{(1-\alpha)+n(\alpha+r\beta)}x_0\cdot\epsilon}+8\delta,$$

where $x_0 \in (0,2)$ is the unique solution to the folowing Kepler's equation

$$\frac{1}{2}x_0\sqrt{4-x_0^2}+2\arg\sin(x_0/2)=\Big[1-\frac{2}{r+1}\frac{n_d}{n}\Big]\pi.$$

Theorem 3.2 (Generalized version) Denote $\mathcal{E}\_{\mathrm{w.d.}}$ as the linear probing erorr of a contrastive learning model trained on a dataset with $n_d$ difficult-to-learn examples per class. Under the generalized assumption that $\boldsymbol{A}' = \boldsymbol{A} + \epsilon\boldsymbol{W}$, where $\boldsymbol{W}$ is a Wigner matrix with $\varepsilon_{ii}$ following the Dirac distribution, if $n(r+1)$ is large enough and $r+1 \leq k < n_d+r+1$, we have

$$\mathcal{E}_{\mathrm{w.o.}} \leq \frac{4\delta}{1 - \frac{(1-\alpha)+r(\gamma-\beta)}{(1-\alpha)+n\alpha+nr\beta+n_dr(\gamma-\beta)}-\frac{1}{(1-\alpha)+n(\alpha+r\beta)}x_0\cdot\epsilon}+8\delta.$$

Remark 1. (Value of $x_0$) We derive the value of $x_0$ through numerical methods for multiple datasets, by using the empirical values of $\alpha$, $\beta$, and $\gamma$ calculated on the proxy augmentation graph. We have $x_0=1.894$ for CIFAR-10, $x_0=1.976$ for CIFAR-100, and $x_0=1.995$ for Imagenet-1k. Intuitively, according to Wigner's Semicircle Law, because $n_d \ll n(r+1)$, the value of $x_0$ is near $2$.

A2. (continued)

Remark 2. (Range of $\epsilon$) The bounds are valid if $\frac{1-\alpha}{(1-\alpha)+n\alpha+nr\beta}+\frac{1}{(1-\alpha)+n(\alpha+r\beta)}x_0\cdot\epsilon <1$ and $\frac{(1-\alpha)+r(\gamma-\beta)}{(1-\alpha)+n\alpha+nr\beta+n_dr(\gamma-\beta)}+\frac{1}{(1-\alpha)+n(\alpha+r\beta)}x_0\cdot\epsilon < 1$. As $\frac{(1-\alpha)+r(\gamma-\beta)}{(1-\alpha)+n\alpha+nr\beta+n_dr(\gamma-\beta)} > \frac{1-\alpha}{(1-\alpha)+n\alpha+nr\beta}$, we require $\epsilon < \epsilon_{\mathrm{bound}} = \frac{1-\frac{(1-\alpha)+r(\gamma-\beta)}{(1-\alpha)+n\alpha+nr\beta+n_dr(\gamma-\beta)}}{\frac{1}{(1-\alpha)+n(\alpha+r\beta)}x_0}$. According to the empirical values of $\alpha$, $\beta$, $\gamma$, and $x_0$, we calculate the upper bounds of $\epsilon$ as $\epsilon_{\mathrm{bound}} = 6288$ for CIFAR-10, $\epsilon_{\mathrm{bound}} = 91297$ for CIFAR-100, and $\epsilon_{\mathrm{bound}} = 998839$ for Imagenet-1k. Besides, according to the discussions in A1, we have empirically $\epsilon \ll \epsilon_{\mathrm{bound}}$ for all three datasets.

Remark 3. (Existing conclusions still hold) The effect of $W$ is to add an additional term to the eigenvalue, and the effect is the same for both situations (with and without difficult-to-learn examples). That is, even under the generalized assumptions, we still have the conclusion that "the presence of difficult-to-learn examples leads to a strictly worse linear probing error bound". Moreover, as Corrollary 4.1 can be directly derived by Theorem 3.1, the generalized version becomes $\mathcal{E}\_\mathrm{R} \leq \frac{4\delta}{1 - \frac{1-\alpha}{(1-\alpha)+(n-n_d)\alpha+(n-n_d)r\beta}-\frac{1}{(1-\alpha)+(n-n_d)(\alpha+r\beta)}x_0\cdot\epsilon}+8\delta$. Similarly, as the bounds in Theorems 4.3 and 4.5 are based on a modified similarity matrix, we have $\mathcal{E}\_\mathrm{M} = \mathcal{E}\_{\mathrm{w.o.}}$ (Theorem 4.3) and $\mathcal{E}\_{\mathrm{T}} \leq \frac{4[1-(n_d/n)^2+(\gamma/\beta)^2(n_d/n)^2] \delta}{1-\frac{1-\alpha}{(1-\alpha)+n\alpha+nr\beta}-\frac{1}{(1-\alpha)+n(\alpha+r\beta)}x_0\cdot\epsilon} + 8\delta$ (Theorem 4.5), where the theoretical insights of these two theorems remain unchanged. That is, even under the generalized assumptions, we still have the conclusion that sample removal, margin tuning, and temperature scaling improve the error bound under the existence of difficut-to-learn examples.

Proof sketch. Because $\mathbb{E}\boldsymbol{W}=\boldsymbol{0}$, when $n(r+1)$ is large enough, after normalization, we have $\bar{\boldsymbol{A}}' = \bar{\boldsymbol{A}} + \frac{1}{(1-\alpha)+n(\alpha+r\beta)}\cdot\epsilon\boldsymbol{W}$. By Equation 13 in Fulton (2000), when $r+1 \leq k < n_d+r+1$, we have the $k+1$-th largest eigenvalue of $\bar{\boldsymbol{A}}'$ satisfying

$$\lambda'\_{k+1} \leq \min_{i+j=k+2} \lambda_i + \frac{1}{(1-\alpha)+n(\alpha+r\beta)}\cdot\epsilon \nu_j \leq \lambda_{r+2} + \frac{1}{(1-\alpha)+n(\alpha+r\beta)}\cdot\epsilon\nu_{n_d},$$

where $\lambda_i$ is the $i$-th largest eigenvalue of $\bar{\boldsymbol{A}}$ and $\nu_j$ is the $j$-th largest eigenvalue of $\boldsymbol{W}$.

On the one hand, according to the proofs of Theorems 3.1 and 3.2 in our paper, we have $\lambda_{r+2} = \frac{1-\alpha}{(1-\alpha)+n(\alpha+r\beta)}$ (Theorem 3.1) and $\lambda_{r+2} \leq \frac{(1-\alpha)+r(\gamma-\beta)}{(1-\alpha)+n(\alpha+r\beta)+n_dr(\gamma-\beta)}$ (Theorem 3.2).

On the other hand, Because $\boldsymbol{W}$ is a Wigner matrix, we have its empirical spectral measure $\nu=\frac{1}{n(r+1)}\sum_{i=1}^{n(r+1)} \delta_{\nu_i}$ converging weakly almost surely to the quarter-circle distribution on $[0, 2]$, with density $f(\nu)=\frac{1}{2\pi}\sqrt{4-x^2}\boldsymbol{1}[|x|\leq 2]$. When $j \leq n(r+1)/2$ and $n(r+1)$ large enough, by symmetry of $f(\nu)$, we have

$$\frac{1}{2}\Big[1-\frac{2j}{n(r+1)}\Big] = \int_{x=0}^{\nu_j} f(\nu) \,d\nu = \frac{1}{2\pi} \Big[\frac{1}{2}\nu_j\sqrt{4-\nu_j^2} + 2\arg\sin(\nu_j/2)\Big]. \text{ (*)}$$

Then combine the above calculations, we have $\lambda'\_{k+1} \leq \frac{1-\alpha}{(1-\alpha)+n(\alpha+r\beta)} + \nu_j$ for the generalized Theorem 3.1 and $\lambda'\_{k+1} \leq \frac{(1-\alpha)+r(\gamma-\beta)}{(1-\alpha)+n(\alpha+r\beta)+n_dr(\gamma-\beta)} + \frac{1}{(1-\alpha)+n(\alpha+r\beta)}\cdot\epsilon \nu_j$, where $\nu_j$ is the solution to (*). Then we complete the proof by deriving the error bounds using the upper bounds of $\lambda'_{k+1}$.

---

We appreciate that your reply always lead to potential improvements of our paper. Hope our responses can address your remaining concerns.