When Self-Supervised Learning Meets Unbounded Pseudo-Label Generation

I am not an expert on theoretical analysis. Therefore, please pay more attention to addressing concerns from other reviewers. Here are my concerns:

1. Referring to instance discrimination (ID) as SSL is somewhat an overstatement. I recognize that the scope of this paper is the theoretical analysis of ID-based SSL methods, but there also exists a wide range of other SSL methods such as masked autoencoding [A, B], predictive learning [C, D], and image colorizing [E]. It is better to replace SSL with ID.

2. This paper contains some overclaims. The authors claim that the proposed method manages to "model the dynamic relationship precisely". Similar claims appear frequently in this paper. However, it is almost impossible without ground-truths.

References

[A] K. He et al. Masked autoencoders are scalable vision learners. In CVPR 2022.

[B] H. Wang et al. Hard patches mining for masked image modeling. In CVPR 2023.

[C] M. Noroozi and P. Favaro. Unsupervised learning of visual representations by solving jigsaw puzzles. In ECCV 2016.

[D] H. Wang et al. DropPos: Pre-Training Vision Transformers by Reconstructing Dropped Positions. In NeurIPS 2023.

[E] R. Zhang et al. Colorful image colorization. In ECCV 2016.

1. The main concern is the formulation of the objective function Eq. (7) and the corresponding update rules: The constraint requires $f, f_{ph}$ to minimize $\mathcal{L}\_{PAR}$, which sets $f, f\_{ph}$ to the global minimizer, while the outer objective requires them to be minimizer of $\mathcal{L}\_{align} + \mathcal{L}\_{prior}$. It is not a bi-level optimization problem but a combination of two problems. As a result, it is hard to determine whether the update rules are reasonable.
2. At the beginning of Sec. 4.3, it is claimed that the mislabeling rate can approach 1, however, according to Theorem 4.1 we can only conclude that the misleading rate is greater than 0.
3. In Theorem 4.2, $g(\sigma) \rightarrow \infty$ as $\sigma \rightarrow 0$ is not obvious since both the numerator and denominator tend to 0. Please provide more details.
4. The novelty of the proposed Precise Adjustment Regularization (PAR) needs more explanation. It seems that $\mathcal{L}_{PAR}$ directly uses the discretized similarity as pseudo labels. Besides, the motivation for using moving average predictions as pseudo labels seems unclear.
5. In Sec. 6.2, the objective $\mathcal{L}\_{SSL} + \mathcal{L}\_{PAR}$ is shown to be less effective than the iterative update. However, the computational cost of the iterative update is double according to my understanding. Therefore, it should be compared under the same computational cost for a fair comparison.

• In the abstract, the statement "it is difficult for SSL to accurately gather samples of the same category and separate samples of different categories in the training stage", is causing confusion. The interpretation behind this is quite different from the challenge presented in the introduction. It would be helpful to provide more examples to clarify the challenge presented in the introduction.
• I recommend including a formal mathematical definition when introducing the concept of pseudo-label generation, specifically in the context of discussing both the target network and online network. What exact the online network is. For example, in Section 4.4, it is suggested to move the formula for generating pseudo-labels earlier in the discussion.
• Further clarification and details are required to support the PAR regarding the $out$ function introduced in Eq. 5.
• This paper can be challenging to follow because of its excessively long sentences.