Generalization Analysis for Supervised Contrastive Representation Learning under Non-IID Settings

We truly value your thoughtful feedback. Below, we do our best to allay your concerns within the character limit, and stand ready to answer any questions in further detail during the rolling discussion.

Firstly, we clarify that our work assumes $N$ labeled examples $x_{1:N}$ are used to form valid tuples $(x,x^+,x^-_{1:k})$ (where $x,x^+$ share a label) for training an unsupervised loss. Thus, we agree that our setting aligns more with supervised contrastive learning, differing from [4, 5, 6], which rely on data augmentation for positive pairs. We promise to clarify these distinctions in our revision.

However, we note that using CRL loss in a supervised setting is valid. For instance, both [2, 3] assume access to i.i.d. tuples where $x,x^+$ come from the same conditional distribution, which cannot be simulated without labels. Empirically, using the unsupervised loss at the feature representation stage enhances downstream classification performance (See Fig. 2), aligning with previous findings [7, 10, 11].

Our work vs. [4, 5, 6]:

• The main results in [5] are Thms. 4.2 and 4.8, which bound the population downstream classification risk in terms of population contrastive learning risk. In [6], bounds are derived for the error rate of nearest-neighbor classifiers built on representation functions in terms of misalignment probability $R_\epsilon$. Thus, results in [5,6] are all at population level. In contrast, we focus on the excess contrastive risk.

• Thm. 4.1 in [4] tackles excess contrastive risk for a loss taking two arguments $x,x^-$. Somewhat like ours, they construct the empirical contrastive risk from a fixed dataset $\bar x_{1:n_{pre}}$ using all pairs. Since there are only two arguments, their proof closely resembles [12], ignoring dependence on $k$. Crucially, the lack of labels allows all pairs to be included, removing the nuance of class-collision. In contrast, our work focuses on the interaction between $k$ and class labels, raising many technical challenges. Meanwhile, [4] emphasizes the link between population classification risk and contrastive risk, as well as the impact of data augmentation, which we do not consider.

Q1a: Re formula of $\mathcal{\bar D}\_c$.

Re: In Eqn. (2) of [2], the negative distribution is defined as $\mathcal{D}\_\mathrm{neg}(x)=\mathbb{E}\_{c\sim\rho}[\mathcal{D}_c(x)]$, which allows negative samples to be drawn from any class regardless of the anchor's class, effectively allowing class-collision. In our definition, class-collision is excluded, resulting in the definition in Eqn. (2) of our work. Disallowing class collision is associated to better performance [2, 8, 9].

Q1b: Are results affected by Eqn. (2)?

Re: Yes, our definition of negative distributions results in a class-collision free version of the population risk in Eqn. (3). Thus, our results concern the concentration of empirical risks around this version. However, our techniques readily extend to class-collision case: we believe the quantity $\widetilde N$ (Thm. 5.1 and 5.2) would then be replaced by $N\min(\rho_{\min}/2,1/2k)$ and we expect the results on the estimation error to be marginally tighter (although the practical performance would suffer from reduced alignment between the unsupervised loss and classification objective [2, 9]).

Q2: Re Sections 3.2 and 3.3.

Re: Our Sec. 3 compares the tuples sampling methods in [2] and our work. Under [2] (Sec 3.2), the tuples are drawn i.i.d. from a distribution over $\mathcal{X}^{k+2}$, i.e., each whole tuple is observed independently as the reviewer stated and no data reuse occurs. Under our framework (Sec. 3.3), the procedure in P. 3 is used to select tuples from a labeled dataset $\mathcal{S}$ drawn i.i.d. from a distribution over $\mathcal{X}\times\mathcal{C}$. Hence, while independence holds for elements of $\mathcal{S}$, it does not hold for the selected tuples. For instance, if $k=1, \mathcal{S}=(x,y,v,z)$ with labels $1,1,1,2$, then both $(x,y,z)$ and $(u,v,z)$ are valid tuples but they are dependent due to a shared negative sample $z$. This process allows data reuse across tuples, adhering to practice [7] where recycling samples is desired to create large tuples datasets.

Q3: Why is $S$ labeled?

Re: As clarified above, our work indeed targets supervised contrastive learning rather than truly unsupervised settings. We promise to emphasize this in the revision.

We thank you again for your suggestions, which we believe will help us better frame our contribution in a broader context beyond [2, 3]. We promise to thoroughly discuss all the proposed references. If the reviewer and AC deem it appropriate, we are open to changing the title to `Generalization Analysis for supervised contrastive learning in non i.i.d. settings'. We hope our rebuttal has helped improve your opinion of our contributions. Please do not hesitate to let us know if you have any further questions.

Dear reviewer, we truly appreciate your recognition of the strength and novelty of our contributions. We are also particularly grateful for your detailed review and the effort you put into carefully checking our technical proofs in Appendices B and C.

To answer your question - yes - the techniques presented in our paper can be useful in semi-supervised learning depending on the unsupervised risk formulation. Below, we list several examples.

Overview: Suppose that there exists a distribution $\mathcal{P}$ over $\mathcal{X}\times\mathcal{C}$ where $\mathcal{X}$ denotes the data space and $\mathcal{C}$ denotes the labels space (which is accessible to the learner). In semi-supervised classification, two sets of data $S=\\{(x\_j, y\_j)\\}\_{j=1}^{n}\sim\mathcal{P}^n$ and $S_U = \\{(u\_j, \bar y\_j)\\}\_{j=1}^m\sim\mathcal{P}^m$ are given. While both $S, S_U$ are drawn i.i.d. from $\mathcal{P}$, the labels $(\bar y_j)_{j\in[m]}$ are hidden, making $S_U$ unlabelled. In general, the overall risk for a representation functions $f\in\mathcal{F}$ is a combination of both supervised and unsupervised risks. As the supervised risk has been well-studied [13, 16, 17], we focus on possible formulations of unsupervised risk below instead.

Consistency regularization [14, 15]: Under this regime, the unsupervised loss aims to ensure consistency of representations under different augmentations of inputs. Specifically, let $\mathcal{A}$ be a distribution over augmentation schemes, the unsupervised risk can be defined as $L_\mathrm{un}(f)=\mathbb{E}_{\substack{u\sim\mathcal{P} \\\ \alpha,\alpha^+\sim\mathcal{A}^2}}\Big[\\|f(\alpha[u])-f(\alpha^+[u])\\|\Big]$

where $\\|\cdot\\|$ is a distance measure in $\mathbb{R}^d$. Under this regime, we are implicitly given a set of augmented pairs $S_U^\mathrm{aug}=\{(\alpha_j[u_j], \alpha_j^+[u_j])\}_{j=1}^{m}$ drawn i.i.d. from a distribution dependent on both $\mathcal{P, A}$ (where $a_j$'s are drawn i.i.d. from $\mathcal{A}$). Here, the loss function only relies on augmented views $\alpha(x)$ and $\alpha^+(x)$ which comes from the same natural sample, which precludes reusing natural samples in different pairs/tuples. Thus, we can analyze this regime using standard results in learning theory without the decoupling technique.

Self-supervised CL [4, 5, 6]: In this case, the unsupervised risk can be defined as L\_\mathrm{un}(f)=\mathbb{E}\_{\substack{u, u^-\_{1:k}\sim\mathcal{P}^{k+1}\\\ \alpha,\alpha^+, \beta\_{1:k}\sim\mathcal{A}^{k+2}}}\Big[\ell\Big(\Big\\{f(\alpha[u])^\top[f(\alpha^+[u])-f(\beta\_i[u\_i^-])]\Big\\}_{i=1}^k\Big)\Big].

Intuitively, the augmented views of the same input should be similar to each other while being dissimilar to augmented views of other samples. Since $S_U$ consists of i.i.d. data points in this setting, it is natural to formulate a $(k+2)$-order U-Statistics from $S_U$, generalizing our results to this setting. While such a learning setting involves reused samples, the lack of supervised information removes much of the subtleties of class-collision in our work. Thus, the analysis would be close to (a $k$-wise extension of) [12], making the result simpler than our case when class constraints are present.

Extension: Extension to semantic segmentation is natural: we then have $\mathcal{X}\subseteq\mathbb{R}^{C\times H\times W}$, $\mathcal{C}\subseteq \\{0, 1\\}^{C\times H\times W}$ where $C, H, W$ represents image channels, height, width and $\mathcal{F}$ is a class of CNNs. Under consistency regularization, $\\|\cdot\\|$ can be the MSE loss between tensors. Under self-supervised contrastive learning, the contrastive loss can be any common loss functions (hinge/logistic).

Lastly, as explained in the response to Reviewer t8eS, we note that our results concern the excess unsupervised risk: the connection between the unsupervised (population) risk and the (population) downstream classification risk is an orthogonal line of research which has been studied in various works [4, 5, 6].

Conclusion: Once again, we thank the reviewer for the interesting suggestion that extends our work to potential new directions. In our revised manuscript, we promise to discuss such extension to semi-supervised learning at length and propose future directions accordingly. Please do let us know if you have any further questions or points to discuss.

References:

[12] Clemencon et al., Ranking and Empirical Minimization of U-Statistics. Ann. Statist., 2006.

[13] Bartlett et al., Spectrally-normalized Margin Bounds for Neural Networks. NIPS, 2017.

[14] Ting Chen et al., A Simple Framework for Contrastive Learning of Visual Representations. ICML, 2020.

[15] Sajjadi et al., Regularization With Stochastic Transformations and Perturbations. NIPS, 2016.

[16] Long & Sedghi, Generalization bounds for deep convolutional neural networks. ICLR, 2020.

[17] Golowich et al., Size-Independent Sample Complexity of Neural Networks. COLT, 2018.

Many thanks for your thorough review. We especially appreciate your efforts in checking the correctness of our theoretical analysis as well as raising an interesting question regarding the proof techniques. Please refer to our response below regarding the difference between the technicality of our work and that of [3].

Re (Weakness 1): Many thanks for your keen observation! Indeed, our Theorem 5.1 is free of any logarithmic factors in either $N$ or $k$. However, the right hand side involves the quantities $K_{\mathcal{F},c}$, which each bounds the Rademacher complexity of the loss class associated to tuples corresponding to positive class $c$: applying the bounds to concrete function classes, as we do in Appendix B.3, does incur logarithmic factors of both $k$ and $N$ when bounding these complexities via covering numbers and Dudley's entropy formula.

In contrast, bounds in [3] incur logarithmic factors as early as in Theorem 4.8, even though the Rademacher complexities $\mathfrak{R}\_{S_{\mathcal{H}},nk}(\mathcal{H})$ have yet to be bounded. This is because [3] relies on inequalities between different complexity measures (Lemma C.3 in [3]) earlier in the proof. Still, since our analysis on concrete function classes subsequently incurs log factors, we have chosen not to dwell on this particular improvement to not obscure our main contributions.

Details on Proof Technique: The core similarity of our work and [3] is the fact that we both bound the (empirical) Rademacher complexity of the loss class, denoted as $\mathfrak{\widehat R}\_{S}(\mathcal{G})$ through the $L_\infty$ covering number of $\mathcal{H}=\\{(x, x^+, x^-)\mapsto f(x)^\top[f(x^+) - f(x^-)]:f\in\mathcal{F}\\}$. Specifically, suppose that the loss is $\ell^\infty$-Lipschitz with constant $\eta>0$:

Where $S$ is a set of $n$ independent tuples and $S_\mathcal{H}$ is the set of triplets incurred from $S$ (See [3], Section 4.2). At this point, the difference lies in the methods by which we estimate $\mathcal{N}(\mathcal{H}, \epsilon/\eta, L_\infty(S_\mathcal{H}))$. In our work, the $L_\infty$ covering number of $\mathcal{H}$ is directly estimated by the $L_{\infty, 2}$ covering number of $\mathcal{F}$ (Lemma B.12). In [3], the estimation is done via fat-shattering dimension and worst-case Rademacher complexity. Below, we show how the additional costs in terms of $n, k$ and their logarithmic terms propagate through complexity measures:

where $\mathfrak{R}\_{WC}(\mathcal{H})$ denotes the worst-case Rademacher complexity of $\mathcal{H}$ (note that $\mathfrak{R}\_{WC}(\mathcal{H})\in\widetilde O(1/\sqrt{nk})$) and $\mathrm{fat}\_\epsilon(\mathcal{H})$ denotes the fat-shattering dimension. This yields the final inequality (See [3], Eqn. (C.6)):

Re (Weakness 2): We thank the reviewer for their suggestion. In our revised manuscript, we will certainly re-phrase the subtlety of formulating a $(k+2)$-order U-Statistics more succinctly.

Conclusion: Aside from the concerns addressed above, we promise to correct any other existing typos in our revised manuscript. We thank the reviewer once again for their effort in making our work clearer for readers. We stand ready to answer any further questions you may have and hope that our answer has helped further improve your opinion of our work.

References:

[2] Arora et al., A Theoretical Analysis of Contrastive Unsupervised Representation Learning. ICML, 2019.

[3] Lei et al., Generalization Analysis for Contrastive Representation Learning. ICML, 2023.

[4] HaoChen et al., Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss. NeurIPS, 2021.

[5] Wang et al., Chaos is a ladder: A new theoretical understanding of Contrastive Learning via augmentation overlap. ICLR, 2022.

[6] Huang et al., Towards the generalization of contrastive Self-supervised Learning. ICLR, 2023.

[7] Khosla et al., Supervised Contrastive Learning. NeurIPS, 2020.

[8] Awasthi et al., Do More Negative Samples Necessarily Hurt In Contrastive Learning? ICML, 2022.

[9] Ash et al., Investigating the Role of Negatives in Contrastive Representation Learning. AISTATS, 2022.

[10] Schroff et al., FaceNet: A Unified Embedding for Face Recognition and Clustering. CVPR, 2015.

[11] Sohn, Improved Deep Metric Learning with Multi-class N-pair Loss Objective. NIPS, 2016.

Many thanks for the thoughtful and detailed response. We sincerely appreciate your recognition of the novelty in our decoupling techniques. Below, we provide our responses to address your concerns.

Re (Remark 4.2): To clarify your concern, suppose we have an one-sample, $m$-order U-Statistic as defined in Eqn. (12) and pick an arbitrary integer $i\in[q]$ where $q=\lfloor n/m\rfloor$. Additionally, denote $P_m[n]$ and $C_m[n]$ as the sets of $m$-permutations and $m$-combinations selected from $[n]$, respectively. Then, for any $l_1, \dots, l_m \in P_m[n]$, there are $(n-m)!$ re-arrangements $\pi\in S[n]$ (line 220) such that $\pi[mi-m+u]=l_u, \forall u\in[m]$. In other words, when we shuffle $[n]$ brute-forcedly, the tuple $l_1, \dots, l_m$ appears $(n-m)!$ times (in exact order) from position $mi-m+1$ to $mi$. Hence, we can write:

When $h$ is symmetric, any permutation of its arguments does not alter its value. Thus, we can further simplify the right-hand-side to a sum over the set of $m$-combinations:

Combining all of the above:

which is exactly Eqn. (11).

Re (Weakness 1): We thank the reviewer for the suggestion to improve our presentation. To summarize, our U-Statistics formulation is motivated by the task of creating an (asymptotically) unbiased estimator for $\mathrm{L_{un}}(f)$ by estimating each conditional risk $\mathrm{L_{un}}(f|c)$ then combining the estimators, resulting in Eqn. (8). The reason for this separation lies in the nuance of estimating $\mathrm{L_{un}}(f)$ directly through a $(k+2)$-order U-Statistics (Lines 240 - 245). We acknowledge that we can make the intuition clearer for the readers and we will make sure to improve our presentation in the revised manuscript.

Re (Weakness 2): Thank you for the keen observation. In the procedure described in Section 3.3, the tuples are subsampled independently from the pool of 'valid' tuples where samples are unique within tuples. This means that the samples within each tuple are dependent conditionally given the full sample $x_1,\ldots,x_N$ (but independent without condition), whilst the tuples are independent with or without conditioning. This approach corresponds to calculating U-statistics.

It is also possible to allow replacement within tuples, in which case the samples within each tuple would instead be independent conditioned on the full sample $x_1,\ldots,x_N$ but dependent if no conditioning is applied. This approach corresponds to calculating V-statistics. Our techniques readily extend to this case and would only incur an additive term of $\widetilde{O}\Big(\frac{1}{ N\min(\rho_{\min}/2, (1-\rho_{\max})/k)}\Big)$, which does not worsen the order of magnitude in our bounds. To see why, let us consider the one-sample case (described before Eqn. (11)) for simplicity. The V-Statistics of order $m$ for some kernel $h$ is defined as:

Generally, $V_n(h)$ is not an unbiased estimator of $\mathbb{E}h(x_1, \dots, x_m)$ due to the terms with repeated samples. By [1], we can write $V_n(h)$ as follows:

As a result:

where $|[n]^m\setminus C_m[n]|\in O(n^{m-1})$. Therefore, if $|h(x_1, \dots, x_m)|\le M$, then $V_n(h)-U_n(h)\in O(M/n)$, which means the effect of biasedness dissipates when $n$ increases (as the reviewer remarked). Thus, while biasedness slightly complicates analysis, we can leverage results on the concentration of U-statistics to study the concentration of V-statistics around the population risk, with a small incurred cost. Once again, we really appreciate the reviewer's feedback that help extend the scope of our work to a very interesting regime.

Other Modifications: As per reviewer's suggestions, we have made the following changes:

• Reiterate the definition of $k$ in definition 3.1 (Eqn. (3)).

• Move the definition of the i.i.d. dataset $S$ before Eqn. (5) for better flow.

• Define $C_m[n]$ before Eqn. (11).

Furthermore, we promise to add a more detailed experiment set-up description in the appendix as well as a pointer to the appendix in the main text. We thank the reviewer once again for their efforts in making our work clearer for readers.

References:

[1] Wassily Hoeffding, A Class of Statistics with Asymptotically Normal Distribution. Ann. Math. Statist., 1948.