Adv-SSL: Adversarial Self-Supervised Representation Learning with Theoretical Guarantees

We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.

Comment

• The experimental results comparison only covers a few existing self-supervised learning methods.
• For the experimental results, why did the authors select some of the existing methods from [14] for comparison? Any reason for choosing only these self-supervised learning methods for comparison?
• Why is the comparison not made with more state-of-the-art self-supervised learning methods? For example, what about those self-supervised learning methods that are mentioned in the introduction of this paper?

Response Thank you for your valuable suggestions. We have add the comparison with [a] VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning, ICLR 2022. [b] Geometric View of Soft Decorrelation in Self-Supervised Learning, KDD 2024. The preliminarily results are shown below

Comment For the question the authors raised in line 187, do the authors aim to answer this question just by the empirical experiments in Table 1? Or can this question also be answered from the theoretical perspective? Please elaborate on this question in more detail.

Response Exactly. The question you raised is undeniably important and extremely valuable. We posit that the improvements can be explained from an unbiased perspective, as discussed in the introduction. Roughly speaking, the original iteration method is driven by a biased sampling-level risk, while our revision leads to an unbiased sampling-level risk. This unbiasedness results in better performance of our methods.

Comment The structure of the paper may be incomplete. The authors could at least include a conclusion in the main paper to provide a complete structure of the paper.

Response Thank you for your suggestions. I will add a conclusion in the main paper to provide a complete structure of the paper.

Comment More details about the insights and remarks could be given in the main text, for example, the experiments in Section 4. In the current version, it seems that some important information is missing.

Response Thank you for your suggestions. Due to the limitation of the space, we move some remarks and illustrations to the appendices. For example, we provide explanations and toy examples of the assumptions in Appendix F, and the experimental details are offered in Appendix E. Some insightful ablation experiments are deferred to Appendix E. In our revised version, we reorganize our manuscript and move some important insights and remarks to our main text.

Thank you once again for your careful reading, professional suggestions, and inspiring recognitions. If you have any questions, please feel free to contact us.

We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.

Comment The theoretical guarantees rely on a number of assumptions (Section 3.3), particularly regarding data augmentations (Assumption 4) and the shift between source and target domains (Assumption 5). These assumptions, such as the existence of an augmentation sequence where distances between similar samples converge to zero, might be difficult to verify or guarantee in practice. Could the authors provide more intuition on why these assumptions are reasonable for standard computer vision datasets and augmentation pipelines?

Response Thank you for your question. As you mentioned, it might be difficult to verify in practice. To provide more intuitions, we have illustrated Assumption 4 in Appendix F.2 with toy examples. Meanwhile, the corresponding explanation of Assumption 5 can be found in Appendix F.3. Thank you for your understanding.

Comment The paper introduces an alternating optimization algorithm (Algorithm 1) but does not analyze its practical implications in detail. There is no discussion of the computational overhead of the adversarial updates compared to the simpler direct minimization in methods like Barlow Twins.

Response We highly value this important question. First, it is clear that the additional cost of adversarial updates is negligible, as the inner maximization problem has an analytical solution, as shown in Step 8 of Algorithm 1. To further support this view, we provide the costs related to timing and memory below.

All experiments were conducted using a single Tesla V100 GPU. The time mentioned refers to the time spent per epoch.

Comment The ablation study on the regularization parameter $\lambda$ shows that its optimal value varies significantly across datasets (e.g., 5.0×10−2 for CIFAR-10 vs. 1.0×10−2 for CIFAR-100). This suggests the method may be sensitive to this choice, requiring expensive tuning for new applications. A more in-depth analysis of this sensitivity would be valuable.

Response Thank you for your suggestion. We recognize that tuning costs are inevitable for almost all new methods. Additionally, we must emphasize that the results in Table 4 significantly outperform the biased methods shown in Table 1, regardless of the value of $\lambda$, indicating that the tuning parameters do not impact our experimental advantages. Thank you for your understanding.

Comment The baselines in the key comparison table (Table 1) are re-implementations by the authors. While the authors state that their results are close to those in the LightlySSL library, a direct comparison to the numbers reported in the original papers (e.g., [22, 38]) would provide a stronger and more objective benchmark. This would help ensure that the observed performance gap is entirely due to the methodological improvement of ASSRL and not differences in implementation

Response Thank you for your suggestion. However, the original papers did not report corresponding results on the datasets used in our study. To facilitate a comparison, we are actively working to obtain results on ImageNet, but we will need more time to achieve this. Thank you for your understanding.

Comment The paper's checklist (Question 7) states that the experimental results report the best performance over three runs, rather than providing error bars or other measures of statistical significance. While the reported performance gains are large, this approach makes it difficult to assess the stability and variance of the results. Standard practice would be to report the mean and standard deviation over multiple runs, which would make the empirical claims much more robust and convincing.

Response Thank you for your valuable suggestion. Our preliminary results are shown as below:

Thank you once again for your careful reading, professional suggestions, and inspiring recognitions. If you have any questions, please feel free to contact us.

We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.

Comment

• Empirical evaluations are limited in scope. While primary focus is the theory, so I am largely okay with this, evaluations beyond CIFAR and tiny ImageNet would further bolster their results.
• Additionally, empirical results are all positive, but it is unclear how significant this is in terms of actual utility in situations where self-supervised learning is used in practice--CIFAR and tiny ImageNet are primarily used for small scale testing rather than real world use.
• How well does training scale with image/model size (the empirical evaluations all use relatively small image and model sizes).

Response Thank you for your valuable suggestion. We are working to obtain experimental results on ImageNet, but we will need more time to do so. Thank you for your understanding.

Comment Table 2 compares the author's results with results from a prior paper. I think this is mostly fine, but it does slightly detract from the results, since training conditions may not be identical.

Response Thank you for your valuable questions. All implementations totally aligns with the experimental setting in [a] except for $\lambda$. Therefore, the training conditions are identical.

[a] Whitening for Self-Supervised Representation Learning, ICML 2021

Comment How much of an impact does the method have on (empirical) training time?

Response We highly value this important question. First, it is clear that the additional cost of adversarial updates is negligible, as the inner maximization problem has an analytical solution, as shown in Step 8 of Algorithm 1. To further support this view, we provide the costs related to timing and memory below.

All experiments were conducted using a single Tesla V100 GPU. The time mentioned refers to the time spent per epoch.

Thank you once again for your careful reading, professional suggestions, and inspiring recognitions. If you have any questions, please feel free to contact us.

We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.

Comment Theorem 1's guarantee doesn't hold for the result of Algorithm 1. Of course, this is common in the literature as the problem is non-convex. A note just specifying that Algorithm 1 likely doesn't return the RERM in Theorem 1 may be useful to the reader.

Response Thank you for your professional comment and understanding. As you mentioned, the algorithm does not return the RERM involved in Theorem 1. We have emphasized this difference in the revised manuscript.

Comment To my eye, which doesn't include much familiarity with prior work, I do not find the rate in Theorem 1 very interpretable. I'd appreciate more remarks on interpreting the rate of decay for each term in Theorem 1 perhaps, if possible, an example.

Response Thank you for your invaluable suggestion. We found a typo regarding the term $\epsilon_{n_s} \asymp n_s^{-\frac{\min\\{\alpha, \nu, \varsigma, \epsilon_\mathcal{A}\\}}{8(\alpha + d + 1)}}$ in our theorem, it should be $\epsilon_{n_s} \asymp n_s^{-\frac{\min\\{\alpha, \epsilon_\mathrm{ds}, \epsilon_\mathcal{A}\\}}{8(\alpha + d + 1)}}$. we have revised our manuscript according to your advice. The rate respected to $n_s$ is $-\frac{\min\\{\alpha, \epsilon_\mathcal{A}, \epsilon_\mathrm{ds}\\}}{32(\alpha + d + 1)}$. We will interpret it term by term.

• First, as the dimensionality of the data $d$ increases, the convergence rate of ASSRL with respect to the sample size $n_s$ slows down.
• The term $\epsilon_{\mathcal{A}}$ represents the quality of the data augmentation used. As $\epsilon_{\mathcal{A}}$ increases, it indicates a higher quality of data augmentation, which in turn leads to a faster convergence rate of the upper bound on the misclassification rate with respect to $n_s$.
• The term $\epsilon_{\mathrm{ds}}$ indicates the extent of the shift between the source domain and the target domain. As it increases, the degree of shifting decreases, meaning that the difference between the source and target domains becomes smaller. This makes the transfer learning task significantly easier. Consequently, the convergence rate with respect to $n_s$ will increase as $\epsilon_{\mathrm{ds}}$ rises.
• As for the term $\alpha$, Consider the case that both $\epsilon_{\mathcal{A}}$ and $\epsilon_{\mathrm{ds}}$ are larger than $\alpha$, In this scenario, the convergence rate takes on a typical form found in nonparametric statistics: $-\frac{\alpha}{32(\alpha + d + 1)}$.

Comment Concretely there are with the several $\min$s that make it to tell which setting achieves which argument therein.

Response Thanks for your constructive suggestions. Let's consider a special case that $\epsilon_{\mathrm{ds}} > \alpha$ and $\epsilon_{\mathcal{A}} > \alpha$. This indicates that the distribution shift is minimal but significant enough to consider, while the augmentations used are sufficiently strong. In this context, the rate involved in our theorem degenerates to $n_s^{-\frac{\alpha}{\alpha + d + 1}}$, which is a typical rate in nonparametric statistics [a].

[a] Nonparametric regression using deep neural networks with ReLU activation function

Comment Theorem 1's rate is a mixture of asymptotic and finite bounds. Asymptotic for the source task and finite for the target task.

Response Thank you for your valuable comment. As you mentioned, our result does not provide a complete non-asymptotic upper bound for $n_s$. The primary challenge lies in the difficulty of determining a specific sample size $n_s$ based on the discussion from Lines 1000-1003 in our manuscript as the formulation of it is quite complex. Therefore, we adopt asymptotic analysis to circumvent this issue. This approach does not hinder our ability to further explore the finite-sample bound, provided that $n_s$ is sufficiently large. Thank you for your understanding.

Comment Although perhaps implicit in context I think the reader would be aided in learning that ReLU neural networks for classification is the model used.

Response Thanks for your valuable advice. We have revised our manuscript according to it.

Comment Line 150, the authors say that $m$ could be infinite, yet later we consider a uniform density over all augmentations. Could the authors clarify this? It seems to me that a covering based argument over continuous augmentation classes would be more direct. Can the authors comment on the difficulty or feasibility of adapting their argument to this setting? In order to approximate some augmentation classes we require a cover that is exponential in dimension. e.g., rotational transformations. Thus, there can be additional dimensional dependence for augmentations commonly used. How does this affect the rate?

Response Thank you for your question. We adopted a uniform distribution on a finite set $\mathcal{A}$, which refers to a discrete distribution, as we considered the case where $m$ is finite. In fact, it is reasonable since only a finite number of augmentations will be used in numerical experiments or practical applications.

Comment Is the $1/\min_k\sqrt{n_t(k)}$ natural here should we expect something that is more balanced as as we get more data for all classes except for one.

Response Exactly! In the scenario you mentioned, the model's performance on the exclusive class will be very poor, but it performs well on the others. This makes a lot of sense in the context of meta-learning. In fact, this case can be also captured by our theory. Thanks for your valuable questions.

Comment Biggest concern.

Response Thank you for your question. As you mentioned, it is incorrect that $\mathbb{E}\_{\widetilde{D}_{s}} \sup\_{G \in \widehat{\mathcal{G}}(f)} \widehat{\mathcal{R}}(f, G) = \mathcal{R}(f, G)$. We only have $\mathcal{R}(f,G)=\mathbb{E}\_{\widetilde{D}\_{s}}\widehat{\mathcal{R}}(f,G)$. As we discussed in Section 3.2, this unbiased property reduces the gap between the population risk and the empirical risk. It is sufficient to establish our theoretical analysis with the help of this unbiasedness.

Comment Are ReLU networks a Holder class? As their partials may not exist everywhere.

Response The ReLU networks used in this work belong to a H"older's class. Since ReLU networks we used is Lipschitz continuous, they are H{"o}lder continuous with index $\alpha=1$. It worth noting that we assume the target function $f^{*}$ belongs to a H{"o}lder's class, instead of ReLU neural networks.

If you have any questions, please feel free to further contact us. Thank you once again for your careful reading, professional suggestions, and inspiring recognitions.

We thank you for your thorough review of our manuscript and for your constructive suggestions. We have revised our manuscript by incorporating all of your suggestions. The revised version is much strengthened. Our point-by-point responses to your comments are given below.

Comment The maximization step is realized by directly setting G equal to the empirical estimate, rather than through a dynamic min–max game. The main paper does not clarify this equivalence, which may lead readers to overinterpret the “adversarial” aspect. In practice, the procedure is not truly adversarial.

Response Thank you for your feedback. Our algorithm is still within a min-max framework (thus called "adversarial"), while the maximization step can be solved explicitly. Hence we directly set $G$ equal to the empirical estimate, which is the analytical solution to the inner maximization step.

Comment The empirical improvements, while consistent, are modest. Table 2 should include additional recent decorrelation-based non-contrastive methods, notably VICReg [a] and LogDet [b]. The reported accuracies slightly exceed VICReg but are below LogDet. Moreover, more recent contrastive and non-contrastive baselines should be included.  [a] VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning, ICLR 2022.  [b] Geometric View of Soft Decorrelation in Self-Supervised Learning, KDD 2024.

Response Thank you for your valuable feedback. We highly value your professional suggestions. We notice that the paper you mentioned didn't provide their implementations. Therefore, we try to implement the methods your mentioned ([a], [b]) with the same setting as ours and successfully get The preliminary results shown as follows:

Additionally, we have achieved improvements of 6% to 12% compared to the biased methods.

Comment The claim that “ASSRL-learned representations cluster downstream data by class” should be supported by visualizations or quantitative metrics

Response To provide empirical evidence for our claim, we follow the definition of divergence term from [c], which is expressed as the average of $\Big(\frac{1}{\vert C_t(i)\vert}\sum_{x_t \in C_t(i)}f(x_t)\Big)^{\top}\Big(\frac{1}{\vert C_t(j)\vert}\sum_{x_t \in C_t(j)}f(x_t)\Big)$ among all $i \neq j$. This quantity measures the divergence between representations of data in different latent classes. Further, lower divergence term implies more divergence. We compute the divergence term of the representations learned by our method in CIFAR-10, resulting in a value of 0.231, which reveals that our representations cluster downstream data by class. Moreover, this quantity is smaller than the corresponding values of the other methods reported in [c].

[c] Towards the Generalization of Contrastive Self-Supervised Learning, ICLR 2023.

Comment Assumptions 4 and 5 depend on parameters such as $\sigma_s^{(n)}, \sigma_t^{(n)}, \sigma_s^{(n)}, \sigma_t^{(n)}$ for augmentations and $\epsilon_{\mathrm{ds}}$ for domain shift. These should be measured in experiments and toy examples to validate the assumptions. Assumptions 4 and 5 are particularly stringent and difficult to verify.

Response Thank you for your comments. We have illustrated Assumption 4 in Appendix F.2 of our initial manuscript with a toy example. Additionally, the corresponding explanation for Assumption 5 can be found in Appendix F.3. However, in practical applications, these assumptions are challenging to verify since we cannot access the image distribution. Thank you for your understanding.

Comment The required network width and depth, sample sizes, augmentation constraints, and downstream domain settings are stricter than those used in practice. Assumptions 4 and 5 are particularly stringent and difficult to verify.

Response Thank you for your comments. As you mentioned, our assumptions may indeed be stricter than those typically used in practice. However, we want to emphasize that the width and depth represent only a sufficient but not necessary condition. Meanwhile, the sample sizes serve merely as a theoretical guarantee to illustrate the effectiveness of our proposed method. Additionally, the augmentation constraints provide insight into the types of augmentations we require. Overall, from a theoretical perspective, it is common to explore theoretical understanding in an ideal scenario. Thank you for your understanding.

Comment Additionally, a lower bound on the error is absent.

Response Thank you for your feedback. The mini-max lower bound of self-supervised contrastive learning remains an open problem. It is undoubtedly a valuable and promising area for future research.

Thank you once again for your careful reading, professional suggestions, and inspiring recognitions. If you have any questions, please feel free to contact us.

Comment Taking everything into consideration, I tend to increase the score.

Response We feel incredibly grateful and inspired by your recognition. We would like to express our appreciation once again for your professional reviews and invaluable suggestions.

Comment In my point of view, the maximization step is naturally exist and there is no need to “direct set G to the empirical estimate”. As such, I can not agree there is a proposed step used for explicitly maximization. The name of the method seems to be overdecorated.

Response We have deeply understood your concerns and are considering revising our name according to your suggestions. However, we are unsure if this is permitted for NeurIPS 2025. If it is not allowed, we will emphasize this in the main text of our revised manuscript. Thank you.

Comment Could you specify the difference between the setting of results reported in LogDet[b]. As I understand, compared with results in LogDet[b], your results, e.g., 93.01 of Linear on CIFAR-10, 68.94 of Linear on CIFAR-100, still not satisfied enough.

Response Thank you for your thoughtful question. Unfortunately, the authors did not provide a link to their implementation and specific parameters in their paper [b]. While there is a GitHub link related to logDet on the author's homepage, it appears that the practical code corresponds to other papers rather than [b].

According to the limited information provided in the paper, they mentioned, 'we employ both the same logistic regression classifier.' In contrast, our implementation uses a linear classifier to evaluate the classification error, which is a standard paradigm in this field. Thank you for your understanding.

Comment Additionally, the results are lack of direct comparison with existing theories, e.g., results on ImageNet and ImageNet-100.

Response We highly value your suggestions and believe that they are indeed helpful in improving the quality of our paper. We are working hard to implement them and thank you for your understanding.

Comment The divergence value is meaningful in the response. Actually, it also needs to be compared with other methods.

Response Thank you for your professional suggestion, we individually calculate the same quantity of other methods, the primary result is shown as following table:

Comment Comment 4-6 Before pointing out these weaknesses, I had already read the author's discussion on Assumption 4 and 5. It should be admit the authors have try to derive the meaningful theory by leveraging some existing assumptions. I appreciate the authors efforts. However, in my point of view, the guidance of the proposed theory for practical implementation in real-world is limited. Because the theoretical guarantee rely on these strict assumptions that the current advanced learning paradigms can not satisfy explicitly.

Response Thank you for your professional comments. We attach great importance to your opinions. The key reason for the strong assumptions is the overly rough estimation of Lipschitz constants in actual networks. To the best of our knowledge, there have been numerous studies focused on improving the precision of Lipschitz constants. We believe that this theoretical work can help us improve our results further. Thank you once again for your suggestions.