Difficult Examples Hurt Unsupervised Contrastive Learning: A Theoretical Perspective
Authors: Yi-Ge Zhang
Jingyi Cui
Qiran Li
Yisen Wang
Venue: ICLR 2026 Oral (2026)
Keywords: Machine Learning. Self-Supervised Learning. Difficult Examples
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We introduce a similarity-based theoretical framework that shows how difficult boundary examples impair generalization in unsupervised contrastive learning, and we design  mechanisms that address this issue and boost downstream accuracy.

Abstract: Unsupervised contrastive learning has shown significant performance improvements in recent years, often approaching or even rivaling supervised learning in various tasks. However, its learning mechanism is fundamentally different from supervised learning. Previous works have shown that difficult examples (well-recognized in supervised learning as examples around the decision boundary),  which are essential in supervised learning, contribute minimally in unsupervised settings. In this paper, perhaps surprisingly, we find that the direct removal of difficult examples, although reduces the sample size, can boost the downstream classification performance of contrastive learning. To uncover the reasons behind this, we develop a theoretical framework modeling the similarity between different pairs of samples. Guided by this framework, we conduct a thorough theoretical analysis revealing that the presence of difficult examples negatively affects the generalization of contrastive learning. Furthermore, we demonstrate that the removal of these examples, and techniques such as margin tuning and temperature scaling can enhance its generalization bounds, thereby improving performance.
Empirically, we propose a simple and efficient mechanism for selecting difficult examples and validate the effectiveness of the aforementioned methods, which substantiates the reliability of our proposed theoretical framework.

Published as a conference paper at ICLR 2026
DIFFICULT EXAMPLES HURT UNSUPERVISED CON-
TRASTIVE LEARNING: A THEORETICAL PERSPECTIVE
Yi-Ge Zhang' Jingyi Cui Qiran Li
Yisen Wang!.3 1.3
1 State Key Lab of General AI, School of Intelligence Science and Technology, Peking University School of Engineering. Hong Kong University of Science and Technology Institute for Artificial Intelligence, Peking University
ABSTRACT
Unsupervised contrastive learning has shown significant performance improve- ments in recent years, often approaching or even rivaling supervised learning in various tasks. However, its learning mechanism is fundamentally different from supervised learning. Previous works have shown that difficult examples (well- recognized in supervised learning examples around the decision boundary), which are essential in supervised learning, contribute minimally in unsupervised settings. In this paper, perhaps surprisingly we find that the direct removal of difficult examples, although reduces the sample size, can boost the downstream classification performance of contrastive learning. To uncover the reasons behind this, we develop a theoretical framework modeling the similarity between differentt pairs of samples. Guided by this framework, we conduct a thorough theoretical analysis revealing that the presence of difficult examples negatively affects the generalization of contrastive learning. Furthermore, we demonstrate that the re- moval of these examples, and techniques such margin tuning and temperature scaling can enhance its generalization bounds, thereby improving performance. Empirically, we propose simple and efficient mechanism for selecting difficult examples and validate the effectiveness of the aforementioned methods, which substantiates the reliability of our proposed theoretical framework.
INTRODUCTION
Contrastive learning has demonstrated exceptional empirical per- formance in the realm of unsupervised representation learning, ef- fectively learning high-quality representations of high-dimensional data using substantial volumes of unlabeled data by aligning an an-
SAS
Our Solection
Impoovemnt 180
chor point with its augmented views in the embedding space (Caron
0.77
Etall 2020: Chen all 2020E;x 2021: He etal 2020). Unsuper- vised contrastive learning may own quite different working mech- anisms from supervised learning, as discussed Ioshi & Murza= soleiman (2023). For example, difficult examples (also known as difficult-to-learr examples in Ioshi Mirzasoleiman (2023)),
0.4
0.35
0.77
121
CHAR
STL.0
Figure 1: Excluding difficult examples improves unsuper- vised contrastive learning.
which contribute the most to supervised learning, contribute the least or even negatively to contrastive learning performance. They show that on image datasets such CIFAR- 100 and STL-10, excluding 20%-40% of the examples does not negatively impact downstream task performance. More surprisingly, their results showed, but somehow failed notice, that excluding these samples on certain datasets like STL-10 can lead to performance improvements in downstream tasks.
Taking a step further beyond their study, we find that this surprising result is not just a specialty of certain dataset, but universal phenomenon across multiple datasets. Specifically, we run SimCLR on the original CIFAR- 10, CIFAR-100, S0L- and Tinylmagene datasets, the SAS core subsets
* "Equal contribution
I Work was done when he was an undergraduate intern at Peking University 1 *Correspnniigg author: Yisen Wang (yisen.wan)) wang @ pku.edu.cn)

---

Published as a conference paper at ICLR 2026
(looshi & Mirzasoleiman, (023) selected with deliberately tuned size, and subset selected by sample removal mechanism to be proposed in this paper. In Figure M1 we report the gains of linear probing accuracy by using the subsets compared with the original datasets. We see that on all these benchmark datasets, excluding a certain fraction of examples results in comparable and even bet- ter downstream performance. This result is somewhat anti-intuitive because deep learning models trained with more samples, benefiting from lower sample error, usually perform better. Yet our ob- servation indicates that difficult examples can hurt unsupervised contrastive learning performances. This observation naturally raises a question:
What is the mechanism behind difficult examples impacting the learning process of unsupervised contrastive learning?
To comprehensively characterize such impact, we first develop a theoretical framework, i.e., the sim- ilarity graph, to describe the similarity between different sample pairs. Specifically, pairs containing difficult samples, termed as difficult pairs, exhibit higher similarities than other different-class pairs. Based on this similarity graph, we derive the linear probing eπror bounds of contrastive learning models trained with and without difficult samples, proving that the presence of difficult examples negatively affects performance. Next, we prove that the most straightforward idea of directly remov- ing difficult examples improves the generalization bounds. Further, we also theoretically demon- strate that commonly used techniques such margin tuning (Zhou et all (024)) and temperature scaling (Khaertdinov et all, 2022; Kukkleya et all, 2023; Zhang et al, 2021) mitigate the negative effects of difficult examples by modifying the similarity between sample pairs from different per- spectives, thereby improving the generalization bounds. Experimentally, we propose a simple but effective mechanism for selecting difficult samples that does not rely pre-trained models. The performance improvements achieved by addressing difficult samples through the aforementioned methods align with our theoretical analysis of the generalization bounds.
The contributions of this paper are summarized as follows:
We find that removing certain training examples boosts the performance of unsupervised contrastive learning universal empirical phenomenon multiple benchmark datasets. Through a mixing-image experiment, we conjecture that the removal of difficult examples is the cause.
We design theoretical framework that models the similarity between differrett pairs of sam- ples to characterize how difficult samples in contrastive learning affect the generalization of downstream tasks. Based on this framework, we theoretically prove that the existence of difficult samples hurts contrastive learning performances.
We theoretically analyze how possible solutions, i.e. directly removing difficult samples, margin tuning. and temperature scaling, can address the issue of difficult examples by im- proving the generalization bounds in different ways.
In experiments, we propose simple and efficient mechanism for selecting difficult exam- ples and validate the effectiveness of the aforementioned methods, which substantiates the reliability of our proposed theoretical framework.
2 DIFFICULT EXAMPLES HURT: A MIXING IMAGE EXPERIMENT
We start this section by revealing that difficult examples do hurt contrastive learning performances through a proof-of proof-of-concept toy experiment.
The concept of difficult examples is primarily motivated by supervised learning, where the learning difficulty depends on factors such as data quality (Li all 2019 Shin all 2020), sample neigh- bors (Chen et all, 202(a). and category distribution (Cui all 201% Santiago et all 2(21).. Difficult samples (also termed as difficult-to-learn examples or hard samples) usually lie around the Bayes decision boundary and therefore render high loss large gradient norm during training (loshi & Mizzsooleman, 2023), e.g., a cat that looks like a dog or a blurry image. In the purely unsuper- vised learning paradigm, labels and decision boundaries are absent, to represent difficult samples in a wiir-wise manner, i.c., difficult sample pairs are inter-class sam- ple pairs with high similarity, which leads to their susceptibility being wrongly clustered during
sample similarity
2

---

Published as a conference paper at ICLR 2026
self- supe-viper pre-training. It is somewhat related hard negative samples. a pure unsupervised learning concept defined as highly similar negative samples to the anchor point, but is different in nature. (See Appendix A. for more discussions.)
Original
In real datasets, as difficult examples rely on the specific classifier trained in the supervised learning manner, can not precisely know the ground truth difficult examples. Therefore, we in turn add addi- tional difficult examples and observe the effects of these examples. Specifically, we generate a mixing-iman image dataset containing more dif- ficult samples by mixing w fraction of images on CIFAR-10 dataset at the pixel level (these samples lic around the class difficult), termed as w-Mixed CIFAR-10 datasets. Then, we train the representative contrastive learning algorithm SimCLR (Chen et all 20206) on the original, 10%- and 20x-Mixed CIFAR-10 10 datasets using ResNet18 model. We report the linear probing accuracy in Figure 2
Mixiing Tiensset
Retrove Mixing Semples
85.07
88.0
67.9
67.8
07.73
87.7
07.8
10%
20%
Mixing Ratio Lo
Figure 2: Excluding (mixed) difficult examples improves performance.
Compared with the model trained on the original dataset, we find that with the mixed difficult ex- amples included in the training dataset, the performance of contrastive learning drops. This result indicates that the (mixed) difficult samples significantly negatively impact contrastive learning. As the mixing ratio w increases, the performance drops, indicating that more difficult examples lead to worse contrastive learning performances.
Moreover, show that removing the (mixed) difficult samples boost performance. Specifically, we compare performance on the Mixed CIFAR-10 10 datasets with that on the datasets removing the mixed examples. As shown in Figure D. despite being trained with a smaller sample size, models trained on datasets removing the mixed examples perform better than the ones trained with the mixed examples, which further verifies that difficult examples hurt unsupervised contrastive learning, and removal of these difficult examples can boost learning performance.
3 THEORETICAL CHARACTERIZATION OF WHY DIFFICULT EXAMPLES HURT CONTRASTIVE LEARNING
In this section, to explain why difficult examples negatively impact the performance of contrastive learning, we provide theoretical evidence on generalization bounds. Section H we present the necessary preliminaries that lay the foundation for our theoretical analysis. In Section 3 we intro- duce the similarity graph describing difficult examples. In Section B. we respectively derive error bounds of contrastive learning with and without difficult examples.
3.1 PRELIMINARIES
Notations. Given a natural data 5 X Rd. we denote the distribution of its augmentations by A(- and the set all augmented data by X, which is assumed to be finite but exponentially large. For mathematical simplicity, we assume blassbblaanced data with denoting the number of augmented samples per class and + denoting the number of classes, hence |/|| n(r + 1). Let n. represent the number of difficult examples per class and D2 the of difficult examples. In addition, we denote as the feature dimension contrastive representation learning.
Similarity Graph (Augmentation Graph). As described in HaoChen et all (202I), augmenta- tion graph G represents the distribution of augmented samples, where the edge weight Way signi- fies the joint probability of generating augmented views and x' from the same natural data, i.e., Wast = Egp AA( A)xx) where P denotes the distribution of natural data. The total prob- ability across all pairs of augmented data sums up to 1, i.e., Σz,'Ex Wex' 1. The adjacency matrix of the augmentation graph is denoted as
(War') and the normalized adjacency
matrix is = D 1/2 AD 1/2 where D == diag(w,)ess (w=))exx and w. := Ex'Ex 'Ex Wzz'. The con- cept of augmentation graph is further extended to describe similarities beyond image augmentation, such as cross-die cross-domain images (Shen et all, 2022), multi-modal data (Zhang et all, 2023), and labeled examples all (023)).
3

---

Published as a conference paper at ICLR 2026
Contrastive losses. For theoretical analysis, consider the spectral contrastive loss L(f) proposed by HaoChen et all (202T) as a good performance proxy for the widely used InfoNCE loss
Spor (f) = Bz,x B ff== + Er,
(1)
where æ, xt, and x' represent the anchor, positive sample, and negative sample, respectively. As proved in Balestrero & LeCun (2022); Lohnson et al (2022);; Tan aD (20ZE), the spectral con- trastive loss and the InfoNCE loss share the same population minimum with variant kernel deriva- tions. Further, the spectral contrastive loss is theoretically shown to be equivalent the matrix factorization loss. For F (ux)ZEX, where un // (<x),, the matrix factorization loss
(mf(FF) IA FF 1|3 (ppe(()) + const.
3.2 MODELING OF DIFFICULT EXAMPLES
We start by introducing a similarity graph, to describe the relationships between various samples. In contrastive learning, examples are used in pairwise manner, we define difficult sample pairs as sample pairs that include at least one difficult sample. As difficult examples lie around the deci- sion boundary, they should have higher augmentation similarity to examples from different classes. Therefore, it natural for to define the difficult pairs as different-class sample pairs with higher similarity. Correspondingly, easy pairs are defined as different-class sample pairs containing no difficult samples, different-class sample pairs with lower similarity.
Specifically, we define the augmentation similarity between a sample and itself as 1. Then we assume the similarity between same-class samples is (Figure [aa), the similarity between sample (conceptually far away from the class boundary) and all samples from other classes 3 (Figure 3(b)), and the similarity between different-class boundary samples (conceptually close to the class boundary) (Figure S.C).. Naturally, we have 3 < < a 1.
222
T3
24
α
B
3
1
8
3
3
1
(a) Similarity a.
(b) Similarity 8.
(c) Similarity 7-
(d) Adjacency matrix.
Figure 3: Modeling difficult examples. The similarity between same-class samples is a (a), the similarity between different-class difficult samples is y (c), and the similarity between other samples (b). The adjacency matrix of sampee subset shown in (d).
In Figure Bidy, we illustrate our modeling of adjacency matrix through a 4-sample subset ID, $1,42; Z3, where I and T2 belong to Class O, and I3 and Va belong to Class 1. We define ø and I' as difficult samples (assuming these two samples are distributed around the classification boundary as depicted in Figure B(c)), i.e. Z1, these samples are distributed far from the classification boundary) as easy samples, i.e. #2, 24 Da Daa. The relationship between each pair of samples in D4 can be mathematically formulated as an adjacency matrix shown Figure B
Da. Conversely, we define Z2 and (assuming
In addition, the above modeling could be relaxed by adding random terms to the similarity values. Specifically, for some constant > 0, for a similarity matrix A (āzj, we replace ag with ā. aú Ety for # j. where a; takes values in fa, 8, 7), Eij Eyi are i...d. random variables with mean and variance 1. We discuss the relaxation in detail Section HE
In what follows, theoretical analysis is based on the generalized similarity graph containing X = n(r + 1) samples. The formal definition of the generalized adjacency matrix in Appendix B
4

---

Published as a conference paper at ICLR 2026
3.3 ERROR BOUNDS WITH AND WITHOUT DIFFICULT EXAMPLES
Based on the similarity graph in Section 1.2 we derive the linear probing error bounds for contrastive learning models trained with and without difficult examples in Theorems 3.3 and 334 We mention that we adopt the label recoverability (with labeling error 8) and realizability assumptions from
HaoC Che al (202T).
Assumption 3.1 (Labels are recoverable from augmentations). Let E Px and (()) be its label. Let the augmentation a ~ A(- We assume that there exists a classifier that can predict y( given with
most 8, i.e. ( y(ā) with probability least 1 d.
Assumption 3.2 (Realizabilityy. Let JF be a hypothesis class containing functions from X' to R We assume that at least one of the global minima CSpec belongs to F.
Assumption G indicates that labels are recoverable from the augmentations, and Assumption 3.2 indicates that the universal minimizer of the population spectral contrastive loss can be realized by the hypothesis class. The proofs are shown in Appendix B.J.
Theorem 3.3 (Error Bound without Difficult Examples). Denote Ew.o. as the linear probing error of contrastive learning model trained on dataset without difficult examples. Then
48
1-a E.ro. S (1-a)+natarp
86.
Theorem 3.4 (Error Bound with Difficult Examples). Denote Ev,d. as the linear probing error of a contrastive learning model trained on dataset with na difficult examples per class. Then if r r+1 ++1sk < ne + 1, there holds
46
Ew.d. S
86.
(4)
(1-0)+
(1-a) tna
and (1-a)-na-nr+ we see the presence of difficult examples leads to a strictly worse linear probing error bound for a contrastive learning model. Moreover, more challenging diffieult examples (larger 7 3) result in worse error bounds. When B, i.e. difficult examples exist, the bound in Theorem 6.4 reduces to that in Theorem 3.
Discussions. (1 (1-a)+7()-8) 8)
By comparing
Theorems
also considering that
Intuitively, through the augmentation graph, contrastive learning could be understood spectral clustering problem (HaoChen et al, 2021).. As the difficult examples lie very close to the classi- fication boundary, they could fall into the wrong clusters during self-supervised pre-training. In the downstream applications, the wrongly clustered examples provide false prior knowledge to the downstream classification, which harms the performance of all test samples.
THEORETICAL CHARACTERIZATION ON ELIMINATING EFFECTS OF DIFFICULT EXAMPLES
Building on the above unified theoretical framework, we theoretically analyze that directly removing difficult samples (Section H.D. margin tuning (Section [.2), and temperature scaling (Section (.3)
can handle difficult examples by improving the generalization bounds in different ways.
4.1 REMOVING DIFFICULT SAMPLES
In Figures M and D empirical experiments demonstrated that removing difficult samples can improve learning performance. Corollary I.] provides theoretical explanation for this counter-intuitive phenomenon based on our established framework.
Corollary 4.1. Denote Eg as the linear probing error of a contrastive learning model trained on a selected subset removing all difficult examples D.. Then there holds
ER <
86.
(5)
1-o
(1
3
5

---

Published as a conference paper at ICLR 2026
Corollary I shows that when the difficult examples removed, the linear probing error bound has the same form as the case where no difficult examples are present (Theorem 3.3), but with n replaced by ndd- Compared with the case without removing difficult examples (Theorem B.))) the bound in equation B is smaller than that in equation when Y > (=(1=a)(atrr) (n-a)))n((aaaar)))))) This indicates that removing difficult examples enhances the error bound when these samples are significantly harder than the easy ones (i.e., large 7 (3) when the number of difficult samples is small (i.e., small nd).
4.2 MARGIN TUNING
Aside from sample removal, we also consider using the margin tuning technique to deal with difficult examples. Specifically, we add additional margin parameters to the similarity of difficult pairs in the loss function (see Eq. I. Here, we delve into how margin tuning can enhance the generalization in the presence of difficult examples.
Theorem 4.2. The margin tuning loss is equivalent to the matrix factoriiainn loss
(F) == II(A - (M)
) - FFF 1/2-
(6)
where A is the normalized adjacency matrix, and M is the normalized margin matrix.
Theorem ! indicates that adjusting margins alters the similarity graph by subtracting normalized
margin matrix M from the normalized similarity matrix A. Intuitively, by subtracting the additional similarity values of difficult examples with appropriately chosen margins, the remaining values will
match those of easy examples. Specifically, in the following Theorem R.3. we show that properly chosen margins can eliminate the negative impact difficult examples.
Theorem 4.3. Denote Es the linear probing error for the margin tuning loss equation 3 trained on a dataset with difficult samples Da. If we let
Ma,w" = -0/ (cf(c)))) (7-
(7)
for u(z) + (((x), x, x' E Bd where cp = (1- mar(y 3) and (1 a) na + nr and ma,w"
al-a) a) + na + (n - na) e1 := (1-a) a)+ na + nr
for x, x' $ Ba. then we have
Ex Ew.o..
(8)
Note that when is large enough, Ma,x' for or x' & Da higher-order infinitesimals relative to equation M and primarily affect normalization rather than the core problem. Thus, we focus on cases where x, x Da and defer specific forms of other mz,z'' values the proofs for brevity.
Theorem shows that with appropriately chosen margins, the linear probing error bound for the margin tuning loss in the presence of difficult examples becomes equivalent to the standard con- trastive loss without such examples, as indicated in Theorem 3.3. Since equation D > O, this sug- gests applying positive margin to the difficult example pairs. Additionally, the more challenging the example pairs are (i.e., the larger 7 - 3), the greater the margin value should be.
4.3 TEMPERATURE SCALING
We also consider the widely used temperature scaling technique in eliminating the negative effects of difficult examples. Specifically, we add an additional temperature scaling parameter to the base temperature of difficult pairs in the loss function and assign the base temperature to all the other pairs (see Eq. (1)). Here, we investigate how temperature scaling can enhance generalization. Theorem 4.4. The temperature scaling loss is equivalent the matrix factorization loss
Lut I
1
99)
where A is the normalized adjacency matrix of similarity graph. T O A is the element-wist product of matrices T and A. and ||wF is the weighted Frobenius norm (specified in the proof).
Theorem shows that adjusting temperatures modifies the similarity graph by multiplying the temperature values with the normalized similarity matrix A. Intuitively, by scaling the similarity values between difficult examples, mitigating the negative effects of difficult examples. Specifically, the following Theorem 8.5 outlines the appropriate temperature values to be chosen.
match these values to those of easy examples, thereby

---

Published as a conference paper at ICLR 2026
Theorem 4.5. Denote Ey the linear probing ervor for the temperature scaling loss equation !
trained on a dataset with difficult samples Da. If we let
Ta,x" = (c1/e2)11/7)
(10)
for y(x) + u(x'), E Dd. where 01 := (1 a) + na + nr + nar(y B) and C2 := (1 a+) + nr and Ta,w" for I, x' Da. then we have
&T S 4 (na/n) (x/5) (na
+ 86.
(11)
1-a
(1-a)+natur
Likewise, here we only focus on the temperature values between difficult examples, and defer the specific forms of other Ta, values to the proofs for brevity.
Theorem 4.. shows the linear probing error bound of the temperature scaling loss when trained on data containing difficult examples. Specifically, with large and na/n 0, we have E 1 (((a//n))) and be.dd/Ew.o. - 1 x O(1/n). This indicates that, when O(na) S O(n)/2), 8 X Ew.a./Ew.o. meaning Êτ converges faster to &w.o. Detailed calculations show that when ndd < / [(++)))1++)) B n/2 there holds &T < &w.dd, which means that temperature scaling
improves the error bound. Note that we have approximately Ta. & 8/7. This inspires us choose smaller temperature values for the difficult example pairs. The more difficult the example pairs (smaller 3/7), the smaller the temperature values that should be chosen.
5 VERIFICATION EXPERIMENTS
This paper primarily focuses on theoretical analysis, explaining how different samples in contrastive learning impact generalization. The experiments in this part mainly designed to validate the theoretical insights and demonstrate that the proposed directions for improving performance are sound. The experiments are not intended to achieve state-of-the-art results but rather to confirm the correctness of our theoretical findings. We hope that readers will appreciate the theoretical contributions of this work and not focus excessively on the experimental results.
we present an efficient mechanism for selecting difficult samples. We then evaluate the removal of difficult samples (Section 15.2), margin tuning (Section 5.3), and temperature scaling (Section 5.4), all of which are theoretically established to mitigate the impact of these difficult ex- amples. In Section E.S. we propose a combined method, and discuss the scalability under different paradigms and the connection between difficult samples and long-tail distribution. The specific loss forms can found Appendix A.2
In Section
5.1 DIFFICULT EXAMPLES SELECTION
In this section, we design a simple yet efficient selection mechanism to validate our theoretical analysis, without relling additional pretrained models or incurring extra computational overhead (loshi & Mirzasaleiman 2023).
To identify difficult sample pairs which from different classes but with high similarity, pute the cosine similarity of each sample to other samples in the same batch using features before projector mapping. We define PosHigh and posLow as percentiles of the similarity sorted in de- scending order, where Sim and SimpoosLow are the corresponding similarities. Generally, following the characterization in Section (72) and Appendix H we can roughly assume pos iigh corresponds to 1/(r + 1), where r + is the class number Sample pairs with cosine similarities above Sim iggh are considered from the same class, Sample pairs with the similarity between SimposHigh and SimposLoww are considered as difficult examples. Sample pairs with cosine simi- larities below Simpostoow are considered as easy-to-learn samples from different classes. Here for Low. we note that when optimizing ? of difficult examples, if some easy-to-learn samples are involved, the process will also optimize 18, which a good thing for the representation learning to
We do not need to know the exact label of each class. A rough class number is enough, which can be easily known by clustering.
7

---

Published as a conference paper at ICLR 2026
push samples from different classes further apart. Therefore, easily find value close the bottom of the sorted similarity for pos Low, even 100%. Experiments in Figure Haa and Figure [[ show that our method is not sensitive to the exact values of posHigh and posLow.
65
Accurecy
Accuracy
60
55
55
Baseline
Baseline
0.02
0.04
0.05
peshigh
Spock
(a) Different Hishigg
(b) Different Los
(c) Ratio trends in the training
Figure 4: Parameter sensitivity of difficult example interval ends posHigh (Haa and Low (b Parameter analysis CIFAR-I00: the trend of the ratio of sample pairs from different classes in (SimpooLowr High during the training process (H
Using this selection mechanism, for an augmented sample pair (z,, in the current batch, we define the selecting indicator of difficult pairs as
Pa.j 1 [SimporLow San Hisphs
(12)
where $tyj denotes the cosine similarity between the representations of I; and øy, and 1 [condition] denotes the indicator function returning the condition holds and otherwise. For each sample Ty we get a vector P: (Pt.)) representing the indicator of difficult pairs. After calculating these indicators for all samples in the current batch, we stack the vectors P. row-wise to create the selection matrix P. In practice, P; can be computed in parallel, making the computation of P efficient. The elements of P are either I, indicating whether pairs are difficult pairs or not.
We can use the class information to verify the proportions of sample pairs from different classes in (SimppoeLos> Sim igh) on CIFAR-10, which can demonstrate the effectiveness of our selection mechanism. As shown in Figure HCC along with the progress of training, the ratio of sample pairs from different classes approaches close to 100% within the range (SimposLow- SimppsHighh
5.2 REMOVING DIFFICULT SAMPLES
We here introduce simple and practical method for removing difficult samples based on pro- posed selection mechanism. Eliminating the impact of difficult samples means preventing sample pairs that include difficult samples from interfering with the training process. To achieve this, use the selection matrix P to identify and remove difficult samples.
Table 1: Classification accuracy with or without removing difficult examples on CIFAR-10, CIFAR- 100, STL-10 and Iinylmagenet dataset using SimCLR, Results are averaged over three runs.
Method
CIFAR-10
CIFAR-100
STL-10
Tinylmagenet
SimCLR (Baseline)
88.26
59.95
75.98
69.58
SimCLR (Removing)
89.03
60.31
76.10
71.06
can be observed from Table M that removing difficult examples yields a 0.8% performance boost on CIFAR- 10, 0.6% performance boost on CIFAR-100, and a 3.7% performance boost on Tinylm- agenet compared to the baseline method. We reach the same conclusion as in loshi & Mirzasoleman (2023); By removing difficult samples, we achieve comparable results or even slight improve- ments over the baseline. However, removing difficult samples may not be the most effective method for handling difficult samples. because it shrinks sample size. Next, investigate two techniques that handle difficult samples better, margin tuning in Section 5. and temperature scaling in Sec-
tion 5.4L
8

---

Published as a conference paper at ICLR 2026
5.3 MARGIN TUNING ON DIFFICULT SAMPLES
To effectively apply margin tuning in line with our theoretical analysis, we adopt margin tuning factor > For the selected difficult sample pairs identified by the selection matrix P. add margin to the similarity values, and for the unselected pairs, we use the original InfoNCE.
Table Classification accuracy with without margin tuning on CIFAR-I0, CIFAR-I00, STL-10 and Tinylmagenet dataset. Results are averaged over three runs.
Method
CIFAR-10
CIFAR-100
STL-10
TinyImagenet
Baseline
88.26
59.95
75.98
69.58
MT (All Samples)
88.52
60.09
76.02
70.06
MT (Selected Samples) 89.16
61.28
76.83
79.14
can be observed from Table that applying margin tuning to all samples directly only achieves comparable results the baseline SimCLR, highlighting the importance of the selection mecha- nism for difficult examples. While applying margin tuning to the selected samples brings consistent performance gains on CIFARIO, CIFARI00, and ImnyImageNet. These results validate both the effectiveness of our selection mechanism and the reliability of our analysis on margin tuning.
5.4 TEMPERATURE SCALING ON DIFFICULT SAMPLES
We define the temperature scaling factor p 0. Given the base temperature 0, attach temperature pr to the selected difficult sample pairs identified by the selection matrix P, whereas attach base temperature the unselected pairs.
Table 3: Classification accuracy with or without temperature scaling on CIFAR-I0, CIFAR-100, STL-10 and Tinylmagenet dataset. Results are averaged over three runs.
Method
CIFAR-10
CIFAR-100
STL-10
Tinylmagenet
Baseline
88.26
59,95
75.98
69.58
TS (All Samples)
88.38
59.20
75.76
69.36
TS (Selected Samples) 89.24
61.67
76.62
78.52
It can be observed from Table & that applying temperature scaling to all samples directly can even hurt the performance contrastive learning compared to baseline SimCLR, highlighting the im- portance of selecting difficult examples. In contrast, applying temperature scaling to the selected samples brings consistent performance gains on CIFARIO, CIFAR 100, and TinyImageNet. These results validate both the effectivvness of our selection mechanism and the reliability of our analysis on temperature scaling.
5.5 EXTENSIONS
Combined method. From Sections 222 and PK we observe that margin tuning and temperature seal- ing eliminate the effects of difficult examples in different ways. Therefore, is natural to combine the two methods, and see if the combined method could reach better performances.
Table Classification accuracy with or without combined method on CIFAR-I0, CIFAR-100, STL- 10 and Iinyemagenet dataset. Results are averaged over three runs.
Method
CIFAR-10
CIFAR-100
STL-10
TinyImagenet
Baseline
88,26
59.95
75.98
69.58
Margin Tuning
89.16
61.28
76.83
79.14
Temperature Scaling
89.24
61.67
76.62
78.52
Combined Method
89.68
62.86
77.35
80.00

---

Published as a conference paper at ICLR 2026
It can be observed from Table B that the combined method yields 1.6% performance improve- ment on CIFAR-10, 10, a 4.9% performance improvement on CIFAR-100 100 and a 15.0% performance improvement on Tinylmagen Imagenet compared to the baseline SimCLR. The improvement surpasses that achieved by using only margin tuning or temperature scaling. The combined method on the Mixed CIFAR-10 10 datasets also achieves performance improvements consistently as shown in Section A.S. The complete algorithm is presented in Algorithm M
Alternative contrastive learning paradigm. We delve deeper into the scalability of our methods across various self-supervised learning paradigms. Results in Table B demonstrate consistent perfor- mance enhancements comparable those achieved by SimCLR on the MoCo on CIFAR-10.
Complex classification scenarios. We explore our method by targeting difficult samples under the long-tail classification scenario, where difficult samples are even more difficult to learn according to the imbalanced distributions. The findings in Table & illustrate that our approach outperforms the baseline SimCLR in scenarios involving distributional imbalance, indicating the adaptivity of our approach to complex classification scenarios.
Table 5: The results of incorporating the Com- bined method with different architectures on CIFAR-10.
Table 6: Classification accuracy by using Com- bined method on Tiny Tinylmagenet-L7. We also use SimCLR as the baseline method.
Method
MoCo
SimCLR
Method
TinyImagenet-LT
Baseline
85.84
88.26
Baseline
43.34
Combined Method
86.82
89.68
Combined Method
47.62
Further discussions. We also provide sensitivity analysis of parameters in Section A and con- duct detailed analysis of results in Table B and Table B in Section A.S. Furthermore, discussions about which features are advantageous for selecting difficult examples are also presented in Sec- tion A.S. In Section A. we have also included the experimental results on IK, the trending of the derived bounds with Mixed CIFAR- dataset and the significance analysis of y and B.
CONCLUSION
In this paper, we construct theoretical framework specifically analyze the impact of difficult examples on contrastive learning. We prove that difficult examples hurt the performance of con- trastive learning from the perspective of linear probing error bounds. We further demonstrate how techniques such as margin tuning, temperature scaling, and the removal of these examples from the dataset can improve performance from the perspective enhancing the generalization bounds. The experimental results demonstrate the reliability of our theoretical analysis.
ACKNOWLEDGEMENT
Yisen Wang was supported by National Natural Science Foundation China (92370129, 62376010), Beijing Major Science and Technology Project under Contract Z251 100008425006, Beijing Nova Program (20230484344, 20240484642), and State Key Laboratory of General Artificial Intel- ligence.
ETHICS STATEMENT
Our research strictly adheres to ethical standards in the field of machine learning and artificial intel- ligence. This work makes use of publicly available datasets and models. No private sensitive data are involved, and no harmful content is included. Therefore, we believe this paper does not raise any ethical concerns.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Aviad Aberdam, Ron Litman, Shahar Tsiper, Oron Anschel, Ron Slossberg, Shai Mazor, R Man- matha, and Pietro Perona. Sequence-to-sequens contrastive learning for text recognition. In CVPR, 2021.
Sanjeev Arora, Hrishikesh Khandeparkar, Mikhail Khodak, Orestis Plevrakis, and Nikunj Saunshi. theoretical analysis of contrastive unsupervised representation learning. In ICML,, 2019.
Jordan Ash, Surbhi Goel, Akshay Krishnamurthy, and Dipendra Misra. Investigating the role of
negatives in contrastive representation learning. In AISTATS, 2022.
Randall Balestriero and Yann LeCun. Contrastive and non-contrastive self-supervised learning re- cover global and local spectral embedding methods. In NeurIPS, 2022.
Han Bao, Yoshihiro Nagano, and Kento Nozawa. On the surrogate gap between contrastive and supervised losses. In ICML, 2022.
Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin. Unsupervised learning of visual features by contrasting cluster assignments. In NeurlPS, 2020.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In AAAI, 2020a.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. ICML, 2020b.
Xinlei Chen and Kaiming He. Exploring simple siamese representation learning, In CVPR, 2021.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint arXiv:2003. 04297, 2020c.
Xinlei Chen, Saining Xie, and Kaiming He. An empirical study of training self supervupereieed vision transformers. arXiv preprint arXiv:2104.0205: 2021.
Romain Cosentino, Anirvan M. Sengupta, Salman Avestimehr, Mahdi Soltanolkotabi, Antonio Or- tega, Theodore L. Willke, and Mariano Tepper. Toward geometrical understanding of self- supervised contrastive learning. arXiv preprint wrXiv:2205.06922 2022.
Jingyi Cui, Weiran Huang, Yifei Wang, and Yisen Wang. Rethinking weak supervision in helping contrastive learning. In ICML, 2023.
Jingyi Cui, Hongwei Wen, and Yisen Wang. An augmentation-aware theory for self-supervised contrastive learning. In ICML, 2025.
Yin Cui, Menglin Jia, Tsung-Yo Yi Lin, Yang Song, and Serge Belongie. Class-balanced loss based on effective number of samples. In CVPR, 2019.
Cong Fang, Hangfeng He, Qi Long, and Weijie Su. Exploring deep neural networks via layer- peeled model: Minority collapse in imbalanced training. Proceedings of the National Academy of Sciences, 118(43)ee21030011 2021.
William Fulton. Eigenvalues, invariant factors, highest weights, and schubert calculus. Bulletin of the American Mathematical Society, 37(3):209-249, 2000.
Bran-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al. Bootstrap your own latent-a new approach to self-supervised learning. In NewrIPS, 2020.
Jeff Z HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self-supervised deep learning with spectral contrastive loss. In NeurIPS, 2021.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsu- pervised visual representation learning. In CVPR, 2020.
11

---

Published as a conference paper at ICLR 2026
Tianyang Hu, Zhili Liu, Fengwei Zhou, Wenjia Wang, and Weiran Huang. Your contrastive learning is secretly doing stochastic neighbor embedding. In ICLR, 2023.
Weiran Huang, Mingyang Yi, Xuyang Zhao, and Zihao Jiang. Towards the generalization of con- trastive self-supervised learning. In ICLR, 2023.
Daniel D Johnson, Ayoub EI Hanchi, and Chris Maddison. Contrastive learning can find an optimal basis for approximately view-invariant functions. In ICLR, 2022.
Siddharth Joshi and Baharan Mirzasoleiman. Data-efficient contrastive self-supervised learning:
Most beneficial examples for supervised learning contribute the least. In ICML, 2023.
Yannis Kalantidis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, and Diane Larlus. Hard negative mixing for contrastive learning. In NeurlPS, 2020.
Bulat Khaertdinov, Esam Ghaleb, and Stylianos Asteriadis. Contrastive self-supervised learning for sensor-based human activity recognition. In I/CB, 2021.
Bulat Khaertdinov, Stylianos Asteriadis, and Esam Ghaleb. Dynamic temperature scaling in con- trastive self- celf-super learning for sensor-based human activity recognition. IEEE Transactions on Biometrics, Behavior, and Identity Science, 4(4):498-507, 2022.
Ching- Bun Ko, Jeet Mohapatra, Sijia Liu, Pin- Yu Chen, Luca Daniel, and Lily Weng. Revisiting con- trastive learning through the lens of neighborhood component analysis: an integrated framework. In ICML, 2022.
Anna Kukleva, Moritz Böhle, Bernt Schiele, Hilde Kuchne, and Christian Rupprecht. Temperature schedules for self-supervised contrastive methods on long-tail data. In ICLR, 2023.
Sumin Lee, Hyunjun Eun, Jinyoung Moon, Seokeon Choi, Yoonhyung Kim, Chanho Jung, and Changick Kim. Learning discriminate information for online action detection: Analysis and application. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(5):591855934 2022.
Buyu Li, Yu Liu, and Xiaogang Wang. Gradient harmonized single-stage detector. In AAAI, 2019,
Kento Nozawa and Issei Sato. Understanding negative samples in instance discriminative self- supervised representation learning. In NeurIPS, 2021.
Zhuo Ouyang, Kaiwen Hu, Qi Zhang, Yifei Wang, and Yisen Wang. Projection head secretly an information bottleneck. In ICLR, 2025.
Joshua Robinson, Ching-Yas Yao Chuang, Suvrit Sra, and Stefanie Jegelka. Contrastive learning with hard negative samples. arXiv preprint arXiv:2010.04592, 2020.
Dvir Samuel and Gal Chechik. Distributional robustness loss for long-tail learning. In ICCV, 2021.
Carlos Santiago, Catarina Barata, Michele Sasdelli, Gustavo Cameiro, and Jacinto C Nascimento. Low: Training deep neural networks by learning optimal sample weights. Pattern Recognition, 110:107585, 2021.
Kendrick Shen, Robbie M Jones, Ananya Kumar, Sang Michael Xie, Jeff HaoChen, Tengyu Ma, and Percy Liang. Connect, not collapse: Explaining contrastive learning for unsupervised domain adaptation. In ICML, 2022.
Wonyoung Shin, Lung-Woo Ha, Shengzhe Li, Yongwoo Cho, Hoyean Song, and Sunyoung Kwon. Which strategies matter for noisy label classification? insight into loss and uncertainty. arXiv preprint arXiv:2008.062 2020.
Zhiquan Tan, Yifan Zhang. Jingqin Yang, and Yang Yuan. Contrastive learning is spectral clustering on similarity graph. ICLR, 2024.
Yifei Wang. Zhengyang Geng, Feng Jiang, Chuming Li, Yisen Wang. Jiansheng Yang, and Zhouchen Lin. Residual relaxation for multi-view representation learning. In NewrlPS, 2021a.
12

---

Published as a conference paper at ICLR 2026
Yifei Wang, Qi Zhang, Yisen Wang, Jiansheng Yang, and Zhouchen Lin. Chaos is ladder: A new theoretical understanding of contrastive learning via augmentation overlap. In ICLR, 2021b.
Yifei Wang, Qi Zhang, Tianqi Du, Jiansheng Yang, Zhouchen Lin, and Yisen Wang. A message passing perspective on learning dynamics of contrastive learning. In ICLR, 2023.
Yifei Wang. Qi Zhang, Yaoyu Guo, and Yisen Wang. Non-negative contrastive learning. In ICLR, 2024.
Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny. Barlow twins: Self-supervised learning via redundancy reduction. In JCML, 2021.
Oliver Zhang, Mike Wu, Jasmine Bayrooti, and Noah Goodman. Temperature as uncertainty in contrastive learning. arXiv preprint 1 2021.
Qi Zhang, Yifei Wang, and Yisen Wang. On the generalization of multi-mode contrastive learning. In ICML, 2023.
Qi Zhang, Yifei Wang, and Yisen Wang. An augmentation overlap theory of contrastive learning. Journal of Machine Learning Research, 26(228): 2025.
Xiong Zhou, Xianming Liu, Feilong Zhang, Gang Wu, Deming Zhai, Junjun Jiang, and Xiangyang Ji. Zero-mean regularized spectral contrastive learning. In ICLR, 2024.
Zhijian Zhuo, Yifei Wang, Jinwen Ma, and Yisen Wang. Towards a unified theoretical understanding of non-contrastive learning via rank differential mechanism. In ICLR, 2023.
Roland S Zimmermann, Yash Sharma, Steffen Schneider, Matthias Bethge, and Wieland Brendel. Contrastive learning inverts the data generating process. In ICML, 2021.
13

---

Published as a conference paper at ICLR 2026
A TECHNICAL APPENDICES AND SUPPLEMENTARY MATERIAL
A.1 RELATED WORKS
Self-supervised contrastive learning. Self-supervised contrastive learning (Chen et all, 20206 He all 2020: Wang et all 2021 aims to learn an encoder that maps augmentations (e.g. flips, random crops, etc.) of the same input to proximate features, while ensuring that augmentations of distinct inputs yield divergent features. The encoder, once pre-trained, is later fined-tuned on a specific downstream dataset. The effectiveness of contrastive learning methods are typically evalu- ated through the performances of the downstream tasks such as linear classification. Depending on the reliance of negative samples, contrastive learning methods can be broadly categorized into two kinds. The first kind (Chen et all 0020F:: He et 2020 Wang et all 2022) learns the encoder by aligning an anchor point with its augmented versions (positive samples) while at the same time explicitly pushing away the others (negative samples). On the other hand, the second kind does not depend on negative samples (Zhuo et all 2023). They often necessitate additional components like projectors (Grill et all 2020 Ouyang et all, (0225), stop-gradient techniques (Chen & He, 2021), or high-dimensional embeddings (Zhontar et all (02I).. Nevertheless, the first kind of methods continue be the mainstream in self-supervised contrastive learning and have been expanded into numerous other domains (Aherdam el all, 2022: Khaeridinoy el all, 202T: Lee el all, (022).. The analysis and discussions of this paper focus mainly on the first kind of contrastive learning methods that relies on both positive and negative samples.
Contrastive Learning Theory. The early studies of theoretical aspects of contrastive learning man- age to link contrastive learning to the supervised downstream classification. Arora et all (2019) proves that representations learned by contrastive learning algorithms can achieve small errors the downstream linear classification task.
(2022); Bao et al (2022); Nozawa & Said (2(21) incorporate the effect of negative samples and further extend surrogate bounds. Later on, HaoChen al (202I) focuses the unsupervised nature of contrastive learning by modeling the feature similarities between augmented samples and provides generalization guarantee for linear evaluation through borrowing mathematical tools from spectral clustering. The idea of modeling similarities is later extended to analyzing contrastive learning for unsupervised domain adaption (Shen et all 2022) and weakly supervised learning (Cui et all 2022).. In a similar vein, Wang et all (20211); Zhang et all (2025) put forward the idea of augmentation overlap to explain the alignment of posi- tive samples. Taking a step further, et (2125) proposes augmentation-aware error bound which enables the explanation of specific types of data augmentation. Besides, contrastive learning also interpreted through various other theoretical frameworks in unsupervised learning, such as nonlinear independent component analysis (Zimmermann et all 2021I), neighborhood component analysis (Ko et all, D022), stochastic neighbor embedding (Hu et all 2023), geometric analysis of embedding spaces (Huang et all, 2023), and message passing techniques (Wang et alj. 20233). In this paper, our basic assumptions are based on HanChen ci al (20211 and focus on modeling the similarities between difficult example pairs.
Difference between difficult examples and hard negative samples. Difficult examples and hard negative samples both significantly affect the performance of self-supervised learning. However, while difficult examples are associated with the classification boundary, hard negative samples (Kalantidis et all 2020: Robinson et all 2020) are defined in relation the anchor point. Previ- ous research on hard negative sampling typically modifies contrastive learning models to emphasize these challenging samples so to achieve better performance. In contrast, our findings indicate that unmodified contrastive learning models experience performance degradation due to the existence of difficult samples. Aside from ad hoc modifications, straightforward removal of these difficult sam- ples can also boost performance. As systematic explanation of this finding is lacking, we establish a unified theoretical framework that addresses this challenge.
A.2 Loss FUNCTIONS OF SAMPLE REMOVAL, MARGIN TUNING, AND TEMPERATURE SCALING
Based on the sample selection matrix P defined in equation 12 we adapt the InfoNCE loss into versions of sample removal, margin tuning, and temperature scaling, respectively.
14

---

Published as a conference paper at ICLR 2026
Sample Removal. We define the removal loss as follows:
(i.j)) == log exp (1 P(s))\TT
(13)
Ek=1 [egea]] exp ((5), - --.p))),
where $tj denotes the similarity between augmented instances H; and z.. If pt.j 0, the sample pair 3y and Ijj does not include difficult samples, so (8L, (1 Pt.))\T = 8t, St./T, retaining the original form of the InfoNCE loss. If Pi.j 1, the sample pair 24 and zj are difficult pairs, so (st.) (())/// 0, effectively removing them.
Margin Tuning. We start with the basic form of the widely used InfoNCE loss and define the margin tuning loss for each positive pair. Specifically, within each minibatch of size N, we generate 2. samples through data augmentation. Given the margin tuning factor o > 0, for an anchor sample x; and its corresponding positive sample I,,, we define the margin tuning loss as follows:
exp ((sL) P(.5o)TT)
(M( - log
(14)
2N Ek=1 [itss]] exp ((SL, + PI,,O)/T)*
where St,j denotes the similarity between augmented instances Hy and Tjj, and O denotes the temperature parameter. After the above operation, we assign the same margin value to all selected difficult sample pairs, achieving the goal of margin tuning for specific sample pairs.
Temperature Scaling. To apply temperature scaling consistent with our theoretical analysis, we start with the basic form of the InfoNCE loss and define the temperature scaling loss for each posi- tive pair. Specifically, within each minibatch, given the temperature scaling factor p. for an anchor sample 2, and its corresponding positive sample 2j. we define the temperature scaling loss as fol- lows:
( log
exp PL
PL.
(15)
2N k= 1 [ exp
ALA (1-P((lIPA
where St, denotes the similarity between augmented instances Ty and Zy. Combined Method. The combined loss function as
R1.1 P
cxp
((i.)) = - loog
IT
(16)
2N Ek=l
[[ exp
[ptxet(] PIN)
where st, denotes the similarity between augmented instances x; and xy. The whole training proce- dure of the combined method is shown in Algorithm
A.3 TRAINING DETAILS
We all experiments NVIDIA GeForce RTX 3090 24G GPU and run experiments with ResNet-18 18 on the CIFAR-10, C10AR-100 and STL-10 dataset and ResNet-50 on the Tinylmagenet dataset. We only deal with the difficult examples during training time.
For CIFAR-IO 10 we set batch size as 512, learning rate as 0.25 and base temperature as 0.5. We choose 0.15 as the PosHigh igh and 0.22 as the Low We set a as 0.03 and p as 0.6 for CIFAR-10. For both our method and SimCLR, we evaluate the models using linear probing, when evaluating we set batch size as 512 and learning rate as 1. This experimental setup is also applicable to the Mixed CIFAR-10 10 dataset.
For CIFAR-100 we set batch size as 512, learning rate as 0.5 and base temperature as 0.1. We choose 0.013 as the posliggh and 0.5 the posLow. We set as 0.1 and p 0.7 for CIFAR-100 100. For both our method and SimCLR, we evaluate the models using linear probing, when evaluating we set batch size 512 and learning rate as 0.1.
For STL-10 we set batch size as 256, learning rate as 0.5 and base temperature as 0.1. We choose 0.15 as the HosHigh and 0.22 as the Low. We set 0.1 and p 0.7 for 10. For both our method and SimCLR, we evaluate the models using linear probing, when evaluating we set batch size 256 and learning rate as 0.1.
15

---

Published as a conference paper at ICLR 2026
Algorithm Training procedure of Combined method
Input: batch size N. base temperature posHlggh and posLow for determining the size of the interval. margin tuning factor a, temperature scaling factor p. encoder f()), projector g()) and data augmentation T'
Output: encoder network f(-), and throw away g(-).
1: for sampled minibatch [==) do
2: for all E(I....NN do
3: Draw two augmentation functions t ~
4: D2k-1 f(āx) and
h2x-1 (x22-11 and hax fx22));
22k-1 = g (122x-1) and F22 = g (112z).
7:
end for
8:
for all & E[I....,NN do
Calculate P. (pr.) by using hy. E(I....,NN according Eq. IT: end for
11:
The matrix is obtained by splicing P., ((I...,2NN by rows.
12:
for all E[I....NN| and all E|I....2N| do
13:
8s,j 2, / (1|=|] 1,)]])
14:
end for
Calculate ((i.)) according to Eq. LG:
16:
Calculate L ZN Σ> [[(2k 1,2 ((2k, 2k 1)]; Update networks and minimize C.
end
For Tinylmagenet we set batch size as 512, learning rate as 0.5 and base temperature as 0.5. We choose 0.013 the posHigg and 0.5 the Low. We set a as 0.1 and p 0.7 for TinyImagenet. For both our method and SimCLR, we evaluate the models using linear probing, when evaluating set batch size 512 and learning rate 0.1.
For the experimental results presented in Figure II, we selected 20% SAS coreset for CIFAR-10, 95% SAS coreset for CIFAR-100, 80% SAS coreset for STL-10, and 60% SAS coreset for Tinylmagener, following the filtering method mentioned in (loshi & Mirzasoleimar 20233.
A.4 PARAMETER SENSITIVITY ANALYSIS
Evaluating different a used in margin tuning part. The intention of a is to add margins to the similarity terms between difficult example pairs. We show the performance with different in Figure b and the results show that when o = 0.1 the proposal achieves the best performance on CIFAR-108 100, and the performance does not degrade significantly with a changes. This demonstrates that our proposal is quite robust with the selection of a.
Evaluating different P used in temperature scaling part. P used for scaling downwards the temperatures on the difficult example pairs so that we can eliminate the negative effects of difficult examples. We show the performance with different P Figure 5TD and the results show that when = 0.7 the proposal achieves the best performance on CIFAR-100 and the performance does not degrade significantly with p changes. We figure out that different values of p can all result in performance improvements.
Beseline
Baseline
acc
BCC
20
20
0183 2005
0050
0.23
2.100
Aiie 4.50 2a1
0.022
064
0562
510
0
P
(a) Ace with different ø
(b) Acc with different P
Figure 5: (a) Parameter analysis margin tuning factor ob(b) temperature scaling factor p. all the above results are implemented on CIFAR- 100.
16

---

Published as a conference paper at ICLR 2026
A.5 FURTHER DISCUSSION
Which feature is better for difficult examples selection? In SimCLR, the authors found that the proposal of projector g(-) allows the model to learn the auxiliary task better thus having better downstream generalization. However, as mentioned in (Cosentimo etlll 2 they suggest the problem of representation dimensional collapse after using projector, therefore, we here explore whether it is better to use features before projector fx) for difficult examples selection or g( after projector.
Table 7: Classification accuracy by using Combined method on CIFAR- 10 and CIFAR-100 100. Features before projector means that use f (a:) for difficult examples selection and features after projector means that we use (((())) for difficult examples selection.
Features
Baseline
After projector
Before projector
CIFAR-I0
88.26
87.86
89.68
100
59.95
60.63
62.86
As shown in Table A We find that when using f(r) rather than ((f())) for difficult examples selection we can gain a 2.1% performance improvement on CIFAR-10 and 3.7% performance improvement on CIFAR- 100. These results suggest that utilizing features before projector is more beneficial for difficult examples selection.
The combined method is also effective for the Mixed CIFAR- 10 datasets. As we discussed earlier, the Mixed CIFAR- 10 datasets contain large number of mixed difficult samples, making the learn- ing difficulty of this dataset significantly greater than that of the original dataset. Based this fact, this section explores whether our proposed method can achieve performance improvements on the Mixed CIFAR-10 datasets that consistent with those CIFAR- 100, Tiny ImageNet, and other datasets. We use the 10%- and 20%-Mixed CIFAR-IO datasets as our baselines, while the 0%- Mixed CIFAR-10 datasets serve as our standard CIFAR-IO baseline. The experimental results are shown in Figure G. We found that using either margin tuning or temper- ature scaling alone can improve performance over the original baseline, while the combined method yields better results than using either approach individually. This finding consistent with the ex- perimental results on other datasets and further validates the effectiveness of our method.
Micing Radi u0l
Figure 6: Detailed experimen- tal results on the Mixed CI- FAR datasets.
The proposal is effective for real-world datasets. We evaluated our method on the Imagenet- 1k dataset, which contains 1,000 categories and 1,281,167 training samples. We used ResNet18 8 as our backbone, set the batch size to 1024, and resized each image to 96x96. We set the learning rate to 0.1 and the base temperature to 0.07. We chose 0.01 as the posHigh and 0.5 as the posLow, We set a to 0.1 and p to 0.7. We also evaluated the models using linear probing. When evaluating, we set the batch size to 1024 and the learning rate to 1. The specific results are shown in Table g
Table 8: Classification accuracy on Imagenet- 1k.
Methods
Baseline
Removing Temperature Scaling
Margin Tuning
Combined
Accuracy
37.62
37.79
38.48
38.59
38.98
From the results on the real-world dataset, Imagenet- Ik, which contains more categories, We can see that even after running for only 400 epochs, our method achieves performance improvement trend consistent with the results mentioned in the paper, compared to the bascline method. These results strengthen the findings and demonstrate broader applicability of this paper.
Focusing difficult examples and removing them are both effective methods. We use tem- perature scaling as an example to illustrate how we should handle difficult examples. We note that placing greater emphasis on difficult examples (by selecting smaller temperature) and discarding this sample (which is effectively equivalent to setting the temperature to infinity (we use a large value of 1, 1,00,00000000 000 approximate infinity here)) may seem contradictory. However, as shown
17

---

Published as a conference paper at ICLR 2026
in Table E both approaches are indeed valid. This means that effectively handling difficult samples is possible under sufficiently good conditions, while in the absence of such mechanisms, simply discarding them can also be effective.
Table 9: Classification accuracy with various temperature scaling factors on CIFAR-100 datasets. Setting the Temperature Scaling Factor to 0.7 represents using our proposed theoretical framework to specifically address difficult samples, while setting the Temperature Scaling Factor to 1e9 means discarding these difficult samples. Results are averaged over three runs.
Temperature Scaling Factor
0.7
10
100
1000
le9
Accuracy
61.67
59.95
59.63
59.82
60.05
60.31
The scalability of our proposal under other contrastive learning paradigms. As mentioned in (lohnson etl 2022), InfoNCE and Spectral contrastive loss share the same population minimum with variant kernel derivations. By using similar techniques of positive-pait kernel, our conclusions can also be further generalized to other self-supervised learning frameworks. To demonstrate the scalability of the combined method, we supplement the comparative experiments based on the MoCo (Chen et all 20213) algorithm. The experimental results demonstrate consistent improvements of our method over both MoCo and SimCLR and show the scalability of our proposal under different contrastive learning paradigms.
Connection between difficult examples and long-tailed distribution. Under the definition that difficult examples contribute least contrastive learning and that consequently difficult to dis- tinguish by contrastive learning models, we can easily draw the following conclusion: difficult ex- amples can lead to unclear classification boundaries for the classes they belong to.
Due to the significant difference in the number of samples in the head and tail classes, the boundary of tail classes difficult be accurately estimated due to the tail classes are prone to collapse when the data is distributed with long-tailed distribution, as mentioned in (Samuel & Chechuk, 202T).. In other words, tail classes can lead to unclear classification boundaries for the classes they belong to as mentioned in (Fang et al], 1021).
So in this view, tail classes samples can also be seen as difficult samples. To better illustrate this point, we will further validate the connection between them through the following experiments. We validate our proposed Combined method on the classical long-tailed distribution dataset tiny- Imagenet-LT to explore whether our proposed algorithm can achieve performance improvement over the comparison method SimCLR when distributional imbalance as another form of difficult samples also exists. results in Table B show that can achieve better performance when distri- butional imbalance also exists.
Analysis of the trending of the derived bounds. We analyze the trending of the derived bounds on the Mixed CIFAR- 10 dataset. Specifically, we vary the mixing ratios from 0% to 30%, where 0% represents the standard CIFAR-10 without mixing. The experimental parameter settings can be referenced to A. For each class of samples, we sort them based on the difference between the maximum and second-largest values after applying softmax the outputs, and select the 8% (the ratio is consistent with what is reported in the paper) smallest differences as the difficult examples, as described in the paper. For the calculation of a, we take the mean of the similarity between all samples of the same class. For the calculation of B, we take the mean of the similarity for the sample pairs from different classes that do not contain the difficult examples. For the calculation of y, we take the mean of the similarity for the sample pairs from different classes that contain the difficult examples.
In Table IIO, 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 is 1-ace, and the error bound (right hand side of Eg increases with the eigenvalue increasing. This result indicates that as the difficult examples increases, the classification error and the bound share the same variation trend, thus validating theorem 3.4 that larger 7 / results in worse error bound.
Significance analysis of y and 3. To verify the significance of y and 3., we tested yy and 3, as well as 7 B, on more real datasets. From the first three rows of Table I we found that the CIFAR- 100 dataset (which has 10 times more classes than CIFAR-10), the difference between y and / remained consistent with that on the CIFAR-10 dataset. On the ImageNet- 1k dataset (which has 100
18

---

Published as a conference paper at ICLR 2026
Table 10: The trends of a, B, y, and other metrics as the Mixing Ratio changes.
Mixing Ratio
0%
10%
20%
30%
acc (%)
88.3
88.0
87.7
86.2
47.2
44.0
41.2
38.7
S
19.1
19.5
20.1
20.8
y
20.9
22.1
23.1
24.1
Y 7 Eigenvalue (x10-5)
1.80
2.60
3.00
3.30
2.93
3.36
3.58
3.72
times more classes than CIFAR-10.for specific experimental details and results ImageNet-IKg the difference between y and 3 was even larger than on CIFAR-10. As possible intuitive explanation, conjecture that the higher y 3 might results from the higher complexity of imagenet images, e.g. different-class images with similar backgrounds can share higher similarity (higher ?), whereas CIFAR images have relatively simple and consistent backgrounds. These results demonstrate that even on real-world datasets, the difference between 7 and is significant.
Table 11: Comparison of 3. 7. I-statistic and value across different datasets.
Datasets
CIFAR-10
CIFAR-100
Imagenet-1k
B
19.1
35.6
39.8
Y
20.9
37.4
42.9
Y (-statistic
1.8
1.8
3.1
-502.63
-539.36
-3844.21
P value
0.0
0.0
0.0
To better illustrate the significant difference between y and B, conducted independent samples t-test to support our conclusion. Specifically, we first collected all the 3 and ? values, and due to the large sample size, chose to Welch's t-test, which does not assume equal variances between the two groups and is suitable for cases where the variances may differ. In the experiment, we focus on two key statisties:
t-statistic: This measures the difference between the means of the two groups relative to the variance within the samples. The t-statistic is standardized measure used to determine whether the mean difference between the two groups is significant or could be attributed to random fluctuations. The larger the t-statistic, the more significant the difference between the two groups
value: The p-value indicates the probability of observing the current difference or more extreme results under the assumption that the null hypothesis (i.e., no significant difference between the two groups) is true. If the p-value is less than 0.05, it suggests that the observed difference is highly unlikely under the null hypothesis, and we can reject the null hypothesis, concluding that there is significant difference between the two groups
As shown in the last two rows of Table I.I on datasets (CIFAR-10, 10, CIFAR-100, Imagenet- 1k), the absolute value of the T-statistic is very large, and the P-value is close to zero. This indicates that the mean difference between y and is highly statistically significant.
B PROOFS
Recall that in Section we introduce the adjacency matrix of the similarity graph based on 4- sample subset. Here we give the formal definition of the adjacency matrix generalized similarity graph containing X n + 1) samples, with denoting the number of augmented samples per class, and
12
denoting the number classes.
belong to Class i for 1..... r + 1. Denote n. as the number of difficult examples per class and D& as the set of difficult examples. Naturally,
Denote D 21....,
the dataset, where In(i-1)+1:.....
ny the number of casy-to-learn examples per class. Without loss of generality, we assume that the last n. examples in each class are difficult examples.
denote ne
Let B 7 a Then define the elements of the adjacency matrix A (Wzzzz af
19

---

Published as a conference paper at ICLR 2026
Wa,e' for x²; W2,z'' for x', v()) y(x'); Wa,x' ry for x, Da y(z) > y(=),, and Wz,x' == 3 otherwise.
Specifically, we have the adjacency matrix of similarity graph without difficult examples
Asame-clas class
A Aiiferrent class
Adifeerent class Adifforent-clar
Adifferont cllass
same-class class
Aw.o.
(17)
Adiffereut class
A Adiferrent cluss
A class
(++1)x(++1)
and the adjacency matrix of a similarity graph with difficult examples as
Agame cllas class
A different-cles
A Afffferenttelee class A differentt-llas class
A Aifferent-claas
Asame-class
Aw.d.
(18)
A different-clas
differenttccae claes
Aame- class (r+1)x(r+1)
where
a
a
(19)
same class
nxn
B
differentt class
(20)
B
XX
and
B
B
B
3
B
B
A differentt class
(21)
3
B
B
7 (netna)x(eett))
B. PROOFS RELATED TO SECTION
Proof of Theorem 1. For a dataset without difficult examples, the similarity between sample and itself is 1, the similarity between same-class samples is a, and the similarity between different-class samples is B. Then the adjacent matrix of the similarity graph can be decomposed into the sum of several matrix Kronecker products:
A = (1 a)( & I, + (a - -0- @ (1,, 1,,)) + 3(1,1 11,11 @ 1,,),
(22)
where I,41 and I denote the (r + 1) (r + 1) and n x n identity matrices respectively, and 1 1,41 (I....,1) 1)T E gr++1 and 1, (I....,1) 1)T E _ denote the all-one vectors.
First, we calculate the eigenvalues and eigenvectors of A. Note that 1 and I, have eigenvalues 1 with arbitrary eigenvectors, 1,, 1 has eigenvalue with eigenvector I, 1 1,, and eigenvalues vn
0 with cigenvectors {u , 1, 0}. and 1,41 1 has eigenvalue
with eigenvector 1, - l,+1 and eigenvalues with eigenvectors {v T 1 = 0). Therefore, A has the following sets of eigenvalues and eigenvectors:
\ (1 - a) + n(a 3) n(r + 1)3,
with eigenvector Ī,+1 @ In: with eigenvectors 69 I,;
A ... - A (1 a: + n(a (3)
20

---

Published as a conference paper at ICLR 2026
1x+2 Antr = at
with eigenvectors 1,+1 u, with eigenvectors u &
Axtr+1 = =... An(r+1) -1-a,
Next, we calculate the eigenvalues of A = D-1/2 AD-1/2 By definition, we have D diag (1....., (n(,,)))(()))))))))) = [1 a) na + nr Therefore, we have the eigenvalues of A
as
\ 11
A2 = = Art1 (1 a) n(aa - 3) (1 - a) + na + nr
1 a
Art2 An(r+1) (1 a) + na + nr
Then according to Theorem B.3 HaoChen et al (2021), when r, there holds
48
46
Ew.o. S 1 A6+1 + 85
+ 86.
(23)
1 (1 tao
Proof of Theorem 3.4 For dataset with na difficult examples per class, the similarity between a sample and itself is 1, the similarity between same-class samples a. the similarity between different-class easy-to-learn samples is 8, and the similarity between different-class hard-to-learn samples is 7. Without loss of generality, we assume that n is an integral multiple of na, i.c. there exist E 2t such that n Kng- Then the adjacent matrix of the similarity graph can be decomposed into the sum of several matrix Kronecker products:
A = a1+a & In + (a B) @ (1, 11)) + 3(1,41 1,+1) & (1, 17))
+ (1 1,41) @ (ex e @ Ina - -(--0 B) (ex e Ins:
(24)
where L,+1, In, and Ind denote the (r + 1) x (r + 1), n x n. and na X na identity matrices respectively, 1,+1 == (I,..., 1)T RT+1 and 1, = (I,..., 1)T E IR" denote the all-one vectors, and = (0,...,,,) 0,1) ER.
Similarly, we can decompose into
D I,+1 @ [101 a) na nr + nar(y ()( e Ind]
(25)
and therefore we have
D-1 I [ [In (ex -.,] (en e.)) 2 Ine
(26)
Ci
where we denote C₁ := (1 a) + na- - nr + nar(y - B) and C2 = (1 a) + na + nr3. Then have the decomposition of the normalized similarity matrix
À = D AD-1/2
[ (ex e, + 1 (ex ex)] I... ci
(1 I &
C2
1
+ ( ()
1.+1)
- (e. ex) & In
C1
(r I) @
(ex e In..
C1
(1, ex) + 1
+ (a 3) @
exl
(1x
- ex)
exl
2 (1na 11.))
vc
V0²
vo
+ 3(11+1 1,11) ②
(1, ex) + en]
1
1-
1
(1,
ex)
Ex T
(1ns 1.))
V22
Va
02
val
1 (1 (1-a) I, I.
22
21

---

Published as a conference paper at ICLR 2026
1
+ (1 () 1,+1) @ (ex e @ Ins
[ (7 B) +
( ) (1 a) 1++1 2 (ex e @ Ins
02
ci
+ (a- , @
[ (1n ex) +
1
exl
1
(1x - ex,) + V
exl TT @ (Ina ITTe)
v
V02
+ 8(1+1 1 1,+1) @
[ (1n ex) +
1
enl
1
(1x ex)
exl
17 2
(1ns
c
Vci
(27)
Now calculate the eigenvalues and eigenvectors of A. For notational simplicity, we denote the first three terms of equation ( as A₁ and the last two terms as A2. Note that 1,41. Ix, and Ina have eigenvalues 1 with arbitrary eigenvectors, 1,+1-1 has eigenvalue r+1 with eigenvector 1,+1 = VO+I I+1 and eigenvalues O with eigenvectors {u= uT 1,+1 = 0). and ex ee has eigenvalue 1 with eigenvector e = (1,0,...,,0) 0) E IR" and eigenvalues 0 with eigenvectors {ez.... e.). Let { E R denote an arbitrary vector. Then Ai has the following sets of eigenvalues and eigenvectors:
[ - 3) 4 (7 B) + .
1 (1 a))
111=- = :.. = A1.
(1 a) +
1
- (1 a) + (7 B), with eigenvectors 1,+1 @ e1 05
C1
c1
1
A1,nat1 A1,n
(1
a1: with eigenveetors 1, @ e, @ E 2, k;
02
A1,t1 E... 1icH1=...==..... -1,(r+1)n--m (1 a), with eigenvectors v & e, θg 2, ..
C2
( 1 -(1 (1 - a) - (7- (17-3) 3) +) +1 1 (1 -
[
a)
XL(0+l)a-Tmatl =... A1,(++10
02
C1
1
1
- (1 a) - (1- B), with eigenvectors v 8 E; &g
C1
C1
On the other hand, note that 1na 1T, has eigenvalue na with eigenvector I, == 1 1
yhd na and
eigenvalues with eigenvectors {n7 : 17 In, = 0}. and that by calculations,
Vez (1, e₂) +
1 exl 1/ (In ex) + ex] has eigenvalue s_م + 1 with eigenvector {n- -- ? =
0, 7m = (K- V) /22) } and eigenvalues 0 with eigenvectors (0: Σ 0, 0, mh 0}. Then
Ag has the following sets of eigenvalues and eigenvectors:
121 = (a B)
+
nd + B(r ((r [1 + T/d
C2
C1
1-
1
= (a + r3)
+
Ndd with eigenvectors I,+1 @ 3 Insi
62
K
+ _ nas with eigenvectors v @ 8 Ingi
222 ... = 22,+11 (a 3)
C2
12.-22.... -2..211 = 0, with other combinations of eigenvectors.
22(++11)
By Equation 13 in Fulton (2000), for two real symmetric na + 1) x n(r +1) 1) matrices A and Āg. we have the k + 1-th largest eigenvalue of Á == A, + Ag satisfies
AR+1 S min \1, + A2,j
+4 ++j=++2
(1 a) + r (y ( B) (a 3)
K K- 1
+ 91
nd:
for l < +r+1,
c1
min (1 - a)+ + r (7- - B)
1
1
(1 (1-a) a) + (a -3]
1--1 [
+ 1
nd
C1
02
02
c1
1 [1 a) + ( (t-3) })
for + 1 1 k < na +l
c
9
22

---

Published as a conference paper at ICLR 2026
Then according to Theorem B.3 in Hao TaoChennaen et (2021), when r ++1 k nd + + 1, there holds
46
46
48
E..d. S
86
+ 88
+ 86.
Ak+1
a)
- (7 -8)
(1-o) [1-0++(g +0
(1
( 3)
(28)
B.2 PROOFS RELATED TO SECTION
Proof of Corollary By removing the difficult examples, we have the adjacency matrix as
Asame cllass
A Adifferent-claa class
different class
Adifferent class
Asame class
Adiferent class
A =
(29)
A Adiforennt class
A Aifferent-class
same- class
(++1)x(r+1)
where
Adifferent-elass
(30)
Then the matrix A reduces to Aw.o. and the error bound reduces to that in Theorem replaced with n, = n n2z-
+ with
The spectral contrastive loss with a margin M (m defined as
(x 2EE,, f(x) T f(x*)=++++)))=) + Es, [(x) f(x') + mx,x
(31)
Proof of Theorem 4.2
LM 2m f(x) f(x*) + Ea [f()] ((())(((x) f(x') + m
- Σ Waadd f(x) f(xt) Σ Win [(x) f(x') + m
Σ 2wayer f(x) f(x') wawse f(a')) + 2w fm. f(x') ) + wow.
Wa W [(x)] s(x')) 2/W w W. 1f()) f(x') wx w.
[[[[=[(()) Wew ((e [a')]]
-2
Wansr'
v We mar
[V=z[(x)) [oll'Vlaae (V (w'))'))
2
Wwx v w ma 2w
Maja"
/
W
wa
Σ
Ma
Σ [w)) \ (('))
2
Wa /aa WWay
Wis W.g
2a
= (A M) FF 11 Σ 2w May
(32)
W2 Wart
where we denote A
D 1-1/22A--- 1/2 M = D A = (We,z') (arrat)aate an ( mir+)),
M = (mz,x) ( mine1)) = diag wT... W w)(++ and = (vW,f(I)) (
Note that given the adjacency matrix of the similarity graph A and the margin matrix M, the second term equation 52 is a constant. Therefore, minimizing the margin tuning loss Lv over f(x) is
equivalent minimizing the matrix factorization loss Luf = (I -M)- FFT T 1 over F. n
23

---

Published as a conference paper at ICLR 2026
Proof of Theorem 1
Recall that when difficult examples exist, we assume that for r = x',
a
for x # x' v(()) = y(х')
Waaw
(33)
for x, E (a, # y(x'), )
B
otherwise.
Then by definition we have
(1 a) + na + nr + nar(y - B),
for x Da:
Ug Σ
2x
(34)
(1 a) nr
for $ Da.
and correspondingly
for x - 1' x Dds
(1 a) + na + nr + nar(? - 9)
for x x x & Da.
a) + na nr
for x * x x y( (x)'). x, x' Dd.
(1 a) + na + nr + na 33
a
(1 0) + na nr - narly ()) nr
for x + x' n' (())(( - )()))
E Da or x' Das
Wx,z''
(35)
W2 Wr
for + v(r) v( x, Da.
(1 a) + na + nr
for v(x) * u(='), Das
(1 + na nr + (
8
(1 a) + na nr - nar(s 3) + na nr
for y(x) y(ا') ), E Tda or x' Da
for x(x) # u(x²),, ,,, Das
(1 a) + nr
If we let
narly 3)
+ na + nr + nar(T [3)][(11 -x) + na + nr
x x' E Da.
marly- - 3)
(1 - a) +n na + nr + narly - -o nr
for x', x())) = ( x. Da.
V(1 V -1
[1 - a) + na + 1r3 + Marrr (]][(1 a) na + nr
My.a!
for x # x' (v(()) = y( ). Thg or E Da.
(36)
(1 a) + na (n n
[1 0) + na nr + na(? - [1 o)) + no + nr
for v(x) # u(x'), e Da.
[1 (1-o))nnattrtttarrtt- -1
/ no
(1 + + nr + narly B]][(1 a) na + nr for w(x) + u(xx),,))))))))))))) ) Da or E Da.
otherwise,
then we have
V Wwz v WWa az
24

---

Published as a conference paper at ICLR 2026
nar(y - 3)
[1 - a) + na + nr + nnr(y 5)][(1 a) + na + nr
for x x', E Dd.
nar(y - -3)
[1 (1-a) 0) + na + nr + nar(" 8)][(1 - +o 0k, for x x1,(z)) y y(x'), xx,'' E Da.
(11 (:) + na nr + marly - (3) (1
nax nr
((1 a)) na + nr nar(7: 8) 0)) + na - =nr
(37)
for # x,, ,1(x)= u(x'), Da or a' E Da, [11 a) + (n (7
Q. na nr + 2 [3][(1 a) + na + nr
for (z) * f(xx((x))))))))))) xx, E Da.
(1 a) na nr marly B) 1(1 a) + na + nr B.
(11 a) na 3r nar(s 3)[(1 a) + na = for y(x) # v(x'), E Da or x' E Dd.
otherwise,
and accordingly
1
for x',
(1 a) +na + nr
Wz.xx
W /ell/Weree Meze
for x # 2', u(x) y(2²),
(38)
(1 a +na na + nr
W
B
otherwise.
(1 a) nr
In this case, A- - M is equivalent to the normalized similarity matrix of data without difficult examples. That is, we have
Ex4 = Ew.o.
(39)
The spectral contrastive loss with temperature T = (Tz,z²) ) is defined as
(x) s(x+) + Exz,x
(x; -2E,,
(40)
Tn.at
Tx
Proof of Theorem 4
Cr Eg, f(x) )/Tntt Ex, [f(a] (((a))(())//)) f(a')/TT,x)
-2 Σ Wa.x f(x))//+//// Σ wa War [f(z] f(x))((()))))) f(x')/(//)))))))) T/T,()) 2
2 a f(x) f(x+) + uy W / /2. (f(O) ((x))T(('////)))))))())) f(x')/ 13}
Wx,x'
[wwl(x)) IV Wo/ [(x')] []')]=
[Vwa(())) ( (w [(x')]
/ WW' War
T
a.ad
[[V (Wwrs( [
Taras Warns"
W w Www [(x))
/wiz /wwr
Th w Wy
Wy Wy!
25

---

Published as a conference paper at ICLR 2026
22 w
Σ 22,00
Wx,x''
IV f(a')) [wwzf(x)] [wa]fx)"\[Vva'''
2. 2..0
Tax
VW /
W2 Wey
Tx W Wx Wer
TOTA FOA-FF FF
1
2,2"
(41)
1/2, where we denote T == (Tx,z)) 2. (1(+1)) A = 1-1/2AD AD 1/2, A =
e. pritt),
(att) T A the clement-wise product of matrices T and A, and I/w the weighted Frobenius norm where | Ex, +2 62 for arbitrary matrix B = (be,.r) E [=(++1)xx(r+)),
D = diag(wl.................... wn(r-1)), F (VWzf(z) (a( j
Note that given the adjacency matrix of the similarity graph A and the temperature matrix T, the second term in equation A.l is a constant. Therefore, minimizing the temperature scaling loss Cr over (x) is equivalent to minimizing the matrix factorization loss Lmf-T a FF 2 over F.
Before we proceed to the proof of Theorem 155 (2022) to the temperature scaling loss by deriving the matrix factorization enror bound under the weighted Frobenius norm.
we first extend Theorem B.3 in HaoChen et all
Lemma B.1. Let fpop arg minf:x LT(F) be a minimizer of the population temperature- scaling loss LT(S). Then for any labeling function à X + [r]. there exists linear probe B e Brxk with norm [[ S 11((1 >u) such that
2
[1 B" Spop (x)
S
+ 43(y,0)
(42)
ARt1
where (()) is the one-hot embedding of yz)) and
Wx,x' 10(()) + 0(x')1
(43)
Furthermore, the error can bounded by
2
Σ9 = =P=PPaPp.aaAll
( Apopt (I) # v(σ)
A4+1 + +8A 9).
(44)
We also need the following two supporting lemmas prove Lemma
Lemma B.2. Let L be the normalized Laplacian matrix of some graph G, Us be the i-th smallest unit-norm eigenvector of with eigenvalue 1 >i and R(u) = u Lu for a vector NNN, where u = ( Then for any l E Z such that k < N and Aut1 > O. there exists a vector b E IR with norm |ibll2 & ||u||2 such that
R(uu)
Σ
b,00
5
d 1
(45)
where ||
denotes the weighted (-norm with weights - = (1/7?)
Proof of Lemma B We can decompose the vector u in the eigenvector basis as
N
(46)
Let b E R be the vector such that by G. Then have ||61|3 < ||ui[2 and
N
u
b.u
Σ
Cuulle
26

---

Published as a conference paper at ICLR 2026
N
Σ C/1
1=++
E
\1
$ A++1
i=k+1
C/T.0 (1 X,)Us
AR+1 x=k+1
Σ
1 Lea
Ak+1
k=1+1
Σ
(c//T v4)
L(Gi/TE-00 vz).
(47)
AR+1
i=k+1
Denote ū = Eimi Gi/T v, and R(u) = 1
Lü
Then we have
k
R(uu)
u
6.0%
||u|12
(48)
AR+1
Lemma B.3. In the setting of Lemma B.2 let ÿ be an extended labeling function. Fix E [r]. Define ww= 1[/(x) and up is the corresponding vector in RN Also define the
function u (z) following quantity
0y Enw'x We /ee. Ta 1[(((z) = iA ((xx)(())) + or (0(z) #1 ( = 0)
(49)
ExEX Wer 11;(x)= =
Then we have
A(u?) = 0.
(50)
Proof of Lemma B. Let f be any function X + R. define function u(z) V f(x). Let RNN be the vector corresponding u. Then by definition of Laplacian matrix, have
Lu = ||اي 1/21/2AD 1/2
Σ
wx/2)f(x)
Σ
Wx T (x)
Σ
Wn /
(51)
2
Therefore we have
R((1)) 1 Exxex Wa.s / -
(52)
Exex W.. (x)2
Setting f(x) = 1z)(x) = i] finishes the proof.
Proof of Lemma B 1 Let Fex [01, ......, Ui] be the matrix that contains the smallest & eigenvec- tors of L = A columns, and fae is the corresponding feature extractor. By Lemma B.A there
exists vector by e I² with norm bound llb:ll2 < |nn. [|2 such that
R(u)) A
|nu@ Fac 5
||u
(53)
27

---

Published as a conference paper at ICLR 2026
Combined with Lemma B we have
1u4 - Facbilli 2(1 Akt1)
ZEX 1p(x=(
1
Σ
Wx Te (((0(z)=in))) = ((') + or (0(x) # iA ((x') = i)] (54)
2(1- - -
Let matrix U=
:= (u)) and let u X - R be the corresponding feature extractor. Define matrix
B E RN such that B = (bl....,bb) Summing equation bcd over all i [k] and by definition of 64 we have
IU - P Pe S
Σ Weyz /T. 16((x) + i(x') a,a'Ex
(55)
2(1 )x+1)
2(1
1
By Theorem 44 for feature extractor Spop that minimizes the temperature scaling loss Lej, the function Jut (x) = /uzz Spop is minimizer of the matrix factorization loss Luf-T. Then we have
B" pop (1) (1)
- 2R 2 17(x)) - B" Soop (3) + 2k A( 101)))0(0)) - x(x)112
= 2 Σ Wz (1((r) B" Spop (x) + 41(y.0) 1)
ZEX
2 B T 1 + 43(3. 8)
$
+ ().
(56)
dk+1
Then we move on to the formal proof of Theorem 15
Proof of Theorem According to equation the proof of Theorem if let
0.) + na nr + marly B)
for v(x'), E Da.
a) + na + nrB
V(1 a) + na nr + narly - B)
for x E or E Da.
Tzta
v(1 -1-aa
nrB
(57)
a) + na nr + mar(y 8
for y(z) * 2(')), E Da.
[1 a) + na + 3r
1,
otherwise,
then we have
for x',
(1 a) +na nr
Ta.
(1 a)) nr
a
for x. + x', v(x) vvx'),
(58)
3
otherwise.
(1 a) + na + nr
In this case, T Q A is equivalent to the normalized similarity matrix of data without difficult exam- ples.
By Lemma we have
20j
ET <
+ 88(v. 9).
(59)
1 A6+1
28

---

Published as a conference paper at ICLR 2026
By Assumption 1.1. we have Ayy 9) I 8. Besides, since Tx,x' $ 1 for y(x) + y(x'), x, E De and otherwise Tu, 2 1, we have
Woaw Te. (})x + ((2')]
2,2'EX
Σ
Wz 1 [0((z) + (('')( +
Σ
(x/3)) We, 1(0(z) + 0(z')1
E
Ez-P, (A(I))) 10(x) + أ(''\1
+ (x/8)²
Σ
EENP A(c 10()) + ((x)))
a, ED
E
B (1 + (()) + 10((') + (())
+ (n/3)
E Ea [(x (1])() A -00) - 10((0 # (+)))
E.
2[1 (na/n)) Ba x A(r)(²) +
2(7 ( B Bx [A(x|=) 10(x) [())]
2(1 - (na/n)² + (7/ (na/n)²
(60)
Therefore we have
200
48
ET S 1- A++1
8A( $
+ 86. (61)
1-a
B.3 RELAXATION ON THE IDEAL ADIACENCY MATRIX
To enhance the connection of the theoretical modeling of difficult examples (Section 2 to real- world scenarios, we hereby discuss possible relaxation on the ideal adjacency matrix of the simi- larity graph.
The adjacency matrix could be relaxed by adding random terms the similarity values. Specifically, we replace A with Å (āg)) where âæ and ā.g āij + e- Ety for i * j. aiy takes values in {a, r. Esj_ = Eys are i.idd random variables with mean and variance 1, e >> 0 is small constant. Then A can be decomposed into
= A W - -.-- diag(En),
(62)
where W turns out to be a real Wigner matrix. Note that as Ezg = 0, the normalization matrix D - 1/2
ED D, as n(r + 1) - oc, and therefore have À D-1/2 1/2 D-1/2 AD-1/2 1/2
For mathematical convenience, in the following analysis, we instead perform the relaxation on the normalized adjacency matrix A, and investigate
À = A=A+e w' -'diia((ss))
-
(63)
where e and W is a Wigner's 's matrix.
Denote Ew.o. as the linear probing error of contrastive learning model trained a datasel without difficult examples. Under the general- ized assumption that A' = A + eW, where W is Wigner matrix with Es following the Dirac distribution, then if (r + 1) large enough, we have
Theorem B.4 (Generalized version of Theorem
48
Ex
+ 88,
(1 (1-a)+ +no nn (1-a) (n-a)+((atrz) (r To
where E (0,2) is the unique solution to the following Kepler's 's equation
2 nid r r n
2 TuV = + 2 arg sin(xo/2)
n.
29

---

Published as a conference paper at ICLR 2026
Theorem B.5 (Generalized version of Theorem 34 Denote Ew.d. as the linear probing ervor of a contrastive learning model trained on a dataset with na difficult examples per class. Under the generalized assumption that A' Dirac distribution, if + 1) is large enough and r + S k < Rd + 1, we have
cW, where W is Wigner matrix with En following the
46
Ew.d. S
88.
(1-0) tharly
(1 (a(tr3))
Remark 1. (Value of mn) We derive the value of zy through numerical methods for multiple datasets, by using the empirical values of a, B, and y calculated on the proxy augmentation graph. We have zn = 1.894 for CIFAR-10, vo = 1.976 for CIFAR-100, and 20 = 1.995 for Imagenet- lk Intuitively, according to Wigner's Semicircle Law, because Rid < n(rr + 1), the value of xo is near 2.
Remark 2. (Range of e) The bounds are valid if na-a)+ (a(a))) E < 1
(1-a)+r(0-0) and trr
+ (I-a)tn(a+)))) 2o 1. As (1-0)+r(1-01
+na we require ébound (-ajjnaatrrtan.
(3-0)e((++r3] 100
Remark 3. (Existing conclusions still hold) Note that the effect of the random similarity Eij is to add an additional term to the upper bound of the eigenvalue, and the effect is the same with and without the existence of difficult examples. When
Theorems B and [* degener- Moreover, as Corollary can be directly derived by Theorem 46
ates to Theorems + and 6
3.3. the generalized version becomes ER S [1a (t -a)i) (1=))=innnllo=- Zore + 88.
Similarly, as the bounds in Theorems I and A.5 are based on a modified similarity matrix, we have 4(1 (na/n)² (1/8) (n///(()))))))))))))))))))))))))
EM Ew.o. (Theorem and ET 1I af mix Ford TI nta 123
+68 (Theorem L. where
the theoretical insights of these two theorems remain unchanged. That is, even under the general- ized assumptions, we still have the conclusion that sample removal, margin tuning, and temperature scaling improve the error bound under the existence difficult examples.
Proof. Because EW O, when ntr + 1) is large enough, after normalization, we have A' A + (I=a)+n(o+rr)) eW. By Equation 13 in Fulton (2000), when r + 1 S k < nd + t + 1, we have the & + 1-th largest eigenvalue of Á' satisfying
X441 S min A + (1- n(a +B] Ety Ar+2 + (1-a) n(a r3)) EUnyy ++j=k+2
where X; is the i-th largest eigenvalue of A and vy is the j-th largest eigenvalue of W.
On the one hand, according to the proofs of Theorems 3 and 344 we have X [I-a)tn(atre]
(1-a)+r(y-3) (Theorem (.3 and \ S (==a)ta(att))taarrr>- (Theorem
On the other hand, Because W Wigner matrix, we have its empirical spectral measure
x(++1) In(r+1) 6v, converging weakly almost surely to the quarter-circle distribution on [o, 2]. with
density f(v) = 27 -4-=0 1 < 2]. When S n(( + 1)/2 and n(r + 1) large enough, by symmetry of f(V), have
1
2j
1 mSs f(y),
2n こ. 4 v3 + 22rg s2n
(64)
22 nrr + 1) J==0
Then combine the above calculations, have X111
[I [I=))+ Dj for the generalized (1-a)+n(a+r)] EVi, where Vj is the solution to equation 54. Then we complete the proof by deriving the error bounds using the upper bounds of X
Theorem 3.1 and X I (1-))+r(x-8)
30

---

Published as a conference paper at ICLR 2026
B.4 DISCUSSIONS ON THE TIGHTNESS OF BOUNDS
As possible extension, we discuss that potential lower bound related to the Ag. which according similar proofs of Theorem E.L. also increases with 7 8 increasing. Besides, in Appendix A. we empirically verify that the trending of the downstream classification error, which also verify the reliability of our upper bounds. Please see the following for more details.
To derive the potential lower bound, we are mainly required to modify Theorem B.6 in Haol Chen alll (202T) to an alternative "lower bound" form (because our analysis is based on Theorem B.3 in Hao Chen et all (202T) and key step to its proof is Theorem B.6). Specifically, with the notations of Theorem B.6 (while replacing A, with X be consistent with our submission), we have
N
N
||u
b
1
- -1-
AN)
k=++1
R| 2
Xv)) Σ
(65)
AN)
According to Emiton (2000), we have A 2 max++j=ntk A1. + 22,j that is, we have AN 2 [[1
a) - r(7 fc and 0 2 [11 a) + + /2 for & S nd. Additionally, by Claim B.7 and
Lemma B.8 in HaoChen et all (202I)) and some additional assumption that Σ ||b:l| S C, where
C' > 0 is constant, we obtain the lower bound as
r(7 - -3]
Ew.d. 2 (1-0)-r()-2 3)
(66)
C1
Note that (1--)-1(--8) decreases and
+r
increases as 7 - | increases.
Then when the labeling error d is relatively small, the lower bound gets larger with y 3 increasing, which coincides with the insight of Theorem (44
In addition, in Table III we empirically show the trending of our derived bounds, which also to some extend indicates the tightness of bounds. Specifically, a Mixed CIFAR synthetic dataset, we show that as the difficult examples increases, the classification error and the bound share the same variation trend, thus validating Theorem 3.4 that larger ? 3 results in worse error.
C USAGE OF LLM
We commit to using LLMs for text polishing based prompts. All polished text double-checked by authors to ensure accuracy, avoid over-claims, and prevent confusion.
31


Reviews:
[{"review_id": "JrZ3RNuqh6", "reviewer": "Reviewer_3ZD8", "summary": "Paper proves difficult examples (near decision boundaries) harm unsupervised contrastive learning, contrary to supervised learning. Develops similarity graph framework with α, β, γ parameters modeling sample pair relationships. Derives generalization bounds showing difficult examples worsen performance. Proposes three mitigation strategies—sample removal, margin tuning, temperature scaling—validated theoretically and empirically on CIFAR-10/100, STL-10, TinyImagenet.", "questions": "1. **Hyperparameters**: Why use simplified σ, ρ instead of theoretically optimal values from Eq. 7, 10? What performance is lost?\n\n2. **Hard negatives**: How do your methods compare against Robinson et al. 2020 and Kalantidis et al. 2020? Appendix A.1 claims distinction but no empirical comparison\n\n3. **Scalability**: Why do ImageNet gains (1.36%) diminish vs CIFAR (2-15%)? Is this fundamental or due to 400 vs 800 epochs? What is computational overhead?\n\n4. **Selection stability**: Figure 4c shows selection evolves during training. Are you removing \"intrinsically difficult\" or just \"not-yet-learned\" examples? Would different selection mechanisms yield same results?\n\n5. **Theorem 3.2 condition**: When does nd ≤ k ≤ nd + r + 1 restrict practical applicability? What happens outside this range?", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- **Novel counterintuitive finding**: Removing 8-20% of training data improves performance consistently across 4 datasets\n\n- **Rigorous theoretical framework**: Clean similarity graph model (Theorems 3.1-3.2) proves difficult examples increase error bound from 4δ/(1-λ) to 4δ/(1-λ') where λ' > λ\n\n- **Provided solutions with theory**: Margin tuning (Theorem 4.3), temperature scaling (Theorem 4.5), removal (Corollary 4.1) all improve bounds; experiments confirm (Table 4: Combined method +1.6% CIFAR-10, +4.9% CIFAR-100)\n\n- **Comprehensive extensions**: MoCo (Table 5), long-tail (Table 6), relaxed assumptions (Appendix B.3), ImageNet-1K (Table 8)", "weaknesses": "- **Circular difficult example definition**: Section 5.1 selects \"currently confusing\" examples via cosine similarity during training, not \"intrinsically difficult\" ones. Figure 4c shows ratio evolves to 90%+ suggesting selection is training-dependent\n\n- **Scalability concerns**: ImageNet-1K gains only 1.36% (Table 8) vs 2-15% on smaller datasets. Only 400 epochs vs standard 800+. No computational cost analysis in Algorithm 1\n\n- **Hyperparameter theory disconnect**: Theorems 4.3/4.5 derive exact margins (Eq. 7) and temperatures (Eq. 10) but experiments use simplified σ, ρ without justification. Dataset-dependent tuning required (Appendix A.3)\n\n- **Theorem 3.2 condition unclear**: Requires nd ≤ k ≤ nd + r + 1 but k (feature dim) is architecture choice, not dataset property. Restrictiveness in practice unexplained", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "awCctqsiv3", "reviewer": "Reviewer_Dph8", "summary": "The paper analyzes when and why \"difficult\" examples can hurt contrastive representation learning. It models pairwise similarities with a block structure using within-class, easy cross-class, and difficult cross-class.\nWithin a spectral view of CL, the authors derive linear probe error bounds showing that adding difficult examples worsens the bound. Conversely, removing them or correcting pairwise affinities via pair-specific margin tuning or temperature scaling improves it.  \nEmpirically, targeted adjustments on the selected pairs yield consistent gains across CIFAR-10/100, STL-10, and Tiny-ImageNet.", "questions": "1. Can the theory be relaxed to allow negative $\\beta$ and $\\gamma$?\n1. Is it possible to show the lower bound for the $\\mathcal{E}_{w.d}$?\n1. Tiny-ImageNet shows much larger gains under the targeted edits than CIFAR-10/100 and STL-10 (Table 2 and 3). I am curious on what derives this difference.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper theoretically explains the counterintuitive phenomenon that adding \"hard\" examples can hurt contrastive learning. The spectral framework is a natural fit and the analysis is clean. The block model exposes the role of $\\gamma-\\beta$ on linear-probe error. \n1. The authors propose practical interventions of margin and temperature adjustments motivated by the theory, with improved theoretical error bound. Consistent empirical improvements are observed when applying the interventions. Furthermore, combining selection with targeted adjustments produces the largest gains across datasets.", "weaknesses": "1. The theory assumes $0 \\leq \\beta < \\gamma < \\alpha < 1$, yet cosine similarity lies in $[-1,1]$. Are similarities shifted or computed from a PSD kernel where values are guaranteed to be nonnegative? If not, can the theorems be relaxed to allow $\\beta,\\gamma<0$?\n1. A brief discussion of the tightness of the presented bounds would be helpful in understanding the significance of the bound. Context on any known lower bounds or contrasting constructions, or even a heuristic level argument would help.\n1. Since the improvements are modest except for Tiny-ImageNet, it would be helpful to see the variation across multiple runs. I am also curious if the proposed adjustments can work for other modalities such as text.\n\n**Minor comments**\n1. Please provide a precise recipe for the $\\gamma$-Mixed CIFAR-10 dataset.\n1. Assumptions should appear prominently in the main body with a brief discussion of plausibility, as they are central to the theoretical results.\n1. Section 5.1 needs a clearer explanation.\n1. The writing can be improved. Some examples are as follows:\n  - In Section 4.2 (Margin Tuning), the method can be briefly introduced with a math expression.\n  - Similarly, in Section 4.3, temperature scaling can be briefly introduced with a math expression.\n  - In Corollary 4.1, should the $\\alpha$ appearing in the numerator be $\\delta$?\n  - Figure 3 is not helpful in understanding the role of $\\alpha$, $\\beta$, and $\\gamma$.\n  - In the definition of $w_{x,x'}$ in line 142, $\\mathbb{E}\\tilde x \\sim \\bar{\\mathcal{P}}$ should be $\\mathbb{E}_{\\tilde x \\sim \\bar{\\mathcal{P}}}$, where $\\bar{\\mathcal{P}}$ seems undefined.\n  - The spectral contrastive loss defined in Eq. (1) has an argument $\\mathbf{x}$, which seems unnecessary.\n  - In line 288, there is a missing space between \"pairs.\" and \"Here\".\n  - In line 101: possibly \"preciously\" is a typo for \"precisely\".\n  - In lines 1530 and 1540, theorem numbers are missing in the titles of each theorem. Also a typo: \"erorr\" should be \"error\".\n  - Theorem B.7 defines $\\mathcal{E}{w.d.}$, whereas the inequality has $\\mathcal{E}{w.o.}$.\n  - Line 1537: \"folowing\" $\\rightarrow$ \"following\".\n  - Line 163: \"decision difficult\" $\\rightarrow$ \"decision boundary\".\n  - Line 331: \"an combined method\" $\\rightarrow$ \"a combined method\".\n  - Title of Section 5.4: \"DIFFICLUT\" $\\rightarrow$ \"DIFFICULT\".\n  - Lines 743 and 748: \"Eq. equation 12\" $\\rightarrow$ \"Eq. 12\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EXfpHvq7fh", "reviewer": "Reviewer_Vvxq", "summary": "This paper builds upon the theoretical framework for spectral contrastive learning on population data by HaoChen et al. (2021) by defining a similarity graph. The authors utilize properties of the aforementioned framework to demonstrate in theory that difficult examples (samples near a class decision boundary in a supervised setting) hurt the generalization performance of unsupervised contrastive learning. The authors validate their theoretical work by proposing and validating the performance of mechanisms for detecting and dealing with difficult examples.", "questions": "What exactly does the mixing process itself look like in the mixing image experiment (Section 2)?\n\nSection 3.2 Figure 3(d) shows the adjacency matrix defined as a 4x4 matrix for 4 samples, but the example makes no mention of whether these are empirical or augmented samples. \n\nDiscussion in the appendix indicates that the work follows that of HaoChen et al. (2021), where the adjacency matrix is defined as NxN for N total augmented samples. Does this model of difficult examples make no distinction between samples of the same class and samples augmented from the same empirical sample?\n\nTypo in section 5.1? According to equation 12, posHigh is supposed to be greater than posLow, but Figures 4(a) and 4(b) denote otherwise.\n\nPlot the bounds in Theorems 3.1 and 3.2 for values of $\\beta, \\gamma$, and $\\alpha$ for a clear comparison. \n\nUnless I am mistaken, some old and some recent papers show that hard-negative sampling improves performance in contrastive learning - do the theoretical claims in the paper challenge this observation? \n\nIt will be good to see the results on purely synthetic data - say a mixture of Gaussians where each mixture is a class. Can the authors produce a table for this case?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The mathematical framework utilized is a simplified (neural collapsed) version of a proven one used in HaoChen et al., 2021. The mathematical derivations in this framework are sound. The theoretical results here can be important for choices of contrastive learning samples.", "weaknesses": "The experimental section is only partially sound, with a limited number of experiments and hyperparameter tuning.\n\nThe presentation needs to be significantly improved. There are typographical errors throughout the paper. Figures 1, 2, 4 contain text that is too small to read. Certain ideas are not explained clearly enough.\n\nThe theoretical framework of this paper is based heavily on (HaoChen et al., 2021), which argues extensively about the similarities and differences between the empirical and augmented sets. None of this discussion is reflected here.\n\n\nThe results of experimentation in Section 5 are only averaged out of 3 runs. This makes most results (almost all that are not on TinyImagenet) close enough to be within margin of error. This is exacerbated by the fact that, as shown in Appendix A.3-A.4, only limited hyperparameter tuning is done. Moreover, TinyImagenet is the only dataset that uses a ResNet-50 model instead of ResNet-18 - a natural question arises: could the performance increase be related to the complexity of the model?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Oral)