Towards Understanding Why FixMatch Generalizes Better Than Supervised Learning

Thank you for the insightful and positive comments! Below, we provide a point-by-point response to your concerns.

The main weakness of this paper lies in its technical presentation.

We greatly appreciate your suggestions for improving the technical presentation of our paper to enhance its clarity and accessibility. In response, we have addressed the re-use of variables and restated Theorem 4(b) in our revision, as per your recommendation. Note that Theorem 4(a) remains unchanged, as the probability there stems from network initialization rather than dataset sampling.

To further clarify Definition 1, we have deconstructed it in Appendix L and provided detailed explanations with specific examples to better illustrate the data assumption. Additionally, we will adopt standard notations, such as using $\mathcal{S}$ instead of $\mathcal{Z}$ to represent the dataset, in the final revision. However, we have refrained from making this change in the current revision to avoid causing confusion for other reviewers.

The theory relies on 3-layer ConvNets. Is it possible to extend it to more sophisticated architectures? Would it change the results somehow? Can we prove certain architectures generalize better with SL compared to other architectures?

While our experiments on SSL and SL are applicable to deeper and more sophisticated neural network architectures, our theoretical analysis focuses on a 3-layer convolutional neural network (CNN). This choice allows us to align with Allen-Zhu & Li (2023) and directly compare our (SA-)FixMatch results with their SL analysis. Extending the current theoretical framework to deeper and more sophisticated architectures poses significant challenges due to the highly non-convex nature of the loss surfaces. These complexities lead to local minima and saddle points, making the semantic feature learning process more difficult to analyze.

Specifically, such an extension would require identifying a suitable indicator $\Phi_{i,l}^{(t)}$ to represent the learning status of each semantic feature $v_{i,l}$ and more fine-grained control of the noise in the images, which becomes increasingly necessary with more sophisticated networks. Nevertheless, we believe our two-phase feature learning analysis for FixMatch-like SSLs can be generalized to other network architectures with appropriate configurations. We leave this as an avenue for future work.

Regarding the results, we hypothesize that the improved generalization performance and more comprehensive semantic feature learning exhibited by SSL compared to SL will persist across other neural network architectures under the multi-view data assumption. As for proving that certain architectures generalize better with SL compared to others, we agree this is a fascinating direction. However, achieving this within our current proof framework would require additional time and exploration.

Why does the margin scale as $\log(k)$ in Theorem 4 (where $k$ is the number of classes)? How do we get better classification margins for a more complex task with more classes?

In Theorem 4, the margin scales as $\log(k)$ due to the following reasons:

1. According to Theorem 5, the feature learning indicator $\Phi_{i,l}^{(T)} \geq \Omega(\log k)$ after FixMatch's two-phase feature learning process. Further details can be found in Claim 28 in Appendix E.1.

2. From Claim 21 in Appendix D, we approximate the prediction function $F_i^{(t)}(X)$ as: $F_i^{(t)}(X) = \sum_{l \in [2]} \left( \Phi_{i,l}^{(t)} \times Z_{i,l}^{(t)}(X) \right) \pm O\left(\frac{1}{\text{polylog}(k)}\right),$ where $Z _{i,l}^{(t)}(X) = \mathbb{I} _{v _{i,l} \in \mathcal{V}(X)} (\sum _{p \in \mathcal{P} _{v _{i,l}}(X)} z _p )$ for $i \in [k]$ and $l \in [2]$.

Based on the multi-view data assumption in Definition 1, for $(X, y) \in \mathcal{D}_m$, we have the following:

• $\sum _{p \in \mathcal{P} _v(X)} z_p \in [1, O(1)]$ when $v \in \{v _{y, 1}, v _{y, 2}\}$.
• $\sum _{p \in \mathcal{P} _v(X)} z_p \in [\Omega(1), 0.4]$ when $v \in \mathcal{V}(X) \setminus \{ v _{y, 1}, v _{y, 2} \}$.

Thus, the margin satisfies: $F_y^{(T)}(X) \geq \max_{j \neq y} F_j^{(T)}(X) + \Omega(\log k).$

To achieve better classification margins for more complex tasks with an increasing number of classes, we recommend employing more sophisticated data augmentation techniques, such as CutMix, or training the network for additional iterations. Applying more sophisticated data augmentations, such as CutMix, increases the classification difficulty for each training sample. This, in turn, contributes to a larger $\Phi_{i,l}^{(T)}$ at the end of training, as the network must learn more robust semantic features to achieve a low training loss. Additionally, training the network for more iterations further reduces the training loss. According to the proof in Claim 28, this results in a larger $\Phi_{i,l}^{(T)}$ at the conclusion of training.

Why need a good theoretical understanding of why FixMatch generalizes better than SL?

(1) We appreciate your thoughtful feedback and understand your concerns about the motivation behind the theoretical investigation of SSL in this work, as well as in numerous prior studies (e.g., Rigollet, 2007; Guo et al., 2020, and see more in submission). We would like to address this with three key points:

a) The additional data in SSL are unlabelled and are fundamentally different from labeled data in SL: Unlabelled data lack explicit supervision, and thus do not guarantee improved performance. Indeed, unlabeled data can sometimes degrade performance, particularly when their pseudo-labels are highly inaccurate. This distinction makes it critical to understand why and how SSL algorithms like FixMatch achieve superior generalization than SL. This question is far from trivial, and has been the subject of extensive prior research (see them in submission). These observations underscore the importance of developing a robust theoretical foundation to explain SSL's strengths, limitations, and the conditions under which it excels.

b) Unlabeled data are abundant and easily accessible (e.g., from the web), whereas labeled data require costly and time-consuming manual annotation, often in limited supply. This is particularly relevant in domains like medical imaging, where acquiring labeled data can be prohibitively expensive. SSL's ability to leverage unlabeled data makes it a practical and scalable solution for such settings. Understanding the theoretical principles behind SSL's effectiveness can help unlock its full potential, ensuring that it reliably outperforms SL in resource-constrained scenarios.

c) A solid theoretical understanding of why SSL generalizes better than SL is not just academic. Indeed, it directly informs the design of better SSL algorithms. For instance, in our analysis of FixMatch's feature learning process (Section 4.2), we discover the critical role of strong augmentation $\mathcal{A}(\cdot)$. This augmentation removes learned semantic features in Phase I from input images, forcing the model to learn new, unobserved semantic features in Phase II, thereby enhancing generalization. Inspired by this insight, we developed SA-FixMatch with SA-CutOut, which deterministically removes learned semantic features during Phase II. This strategy improves the efficiency of unlabeled data usage, enabling the model to learn a more comprehensive set of semantic features and achieve better generalization performance.

Moreover, our theoretical analysis also provides a novel perspective on semantic feature learning that can guide future SSL research. By extending our two-phase feature learning framework (Section 4) to other neural network architectures, researchers can develop more sophisticated SSL algorithms tailored to these architectures. Such advancements can further facilitate the learning of comprehensive semantic features with limited labeled data, ultimately leading to even better generalization performance across diverse domains.

compare SSL vs SL with same number of total training samples

(2) With the same labeled training dataset $\mathcal{D}$, SSL still outperforms SL both theoretically and empirically. In this setting, SL uses $\mathcal{D}$ for supervised training, while SSL uses $\mathcal{D}$ as its labeled dataset and simultaneously treats the label-ignored $\mathcal{D}$ as its unlabeled dataset.

Theoretically, our analysis for SA-FixMatch can be extended to this scenario where SL and SSL share the same data. This is because SA-FixMatch assumes that the strong augmentation $\mathcal{A}_{SA}(\cdot)$ deterministically removes semantic features learned during Phase I from the unlabeled images (see Appendix E). As a result, even with the same labeled and unlabeled dataset, SA-FixMatch can still exploit the two-phase feature learning process to learn a more comprehensive set of semantic features compared to SL, ultimately achieving better generalization performance. This conclusion is rigorously supported by our proof in Appendix E.

To validate this theory empirically, we conducted experiments comparing SA-FixMatch with SL under controlled settings. Following the experimental protocols of our manuscript and FixMatch, we trained WRN-28-8 on CIFAR-100 with 10,000 labeled samples and WRN-37-2 on STL-10 with 1,000 labeled samples. In both cases, SL and SA-FixMatch shared the same labeled dataset $\mathcal{D}$, with SA-FixMatch treating the label-ignored $\mathcal{D}$ as unlabeled dataset.

The test accuracy (%) results are below, demonstrating that SA-FixMatch significantly outperforms SL even when both using the same training dataset. This not only highlights the superiority of SSL over SL but also further validates our theoretical insights. We have included the discussions and results in Appendix K.7 in our revision.

I'd like to thank authors for engaging in discussions.

---

On the motivation of the paper

I understand the importance of SSL, given that obtaining labeled samples can be difficult in certain domains (e.g., Medical, as you mentioned).

My concern was that when you frame it as an SSL vs SL analysis, it is not an apples to apples comparison, since SSL inherently gets access to more data; if the SSL algorithm is able to receive any amount of learning signal from this unlabeled data, it would outperform SL. This is not just true for FixMatch-based SSL algorithms, but other types as well.

Based on the contents of the paper and your response, I would say it's more suitable to frame this type of analysis as a theoretical understanding of why consistency regularization can help generalization. Ultimately, the underlying paradigm that FixMatch (and perhaps other SSL algorithms) is using is a form of consistency regularization, where two differing inputs are made to produce consistent outputs. In fact, this type of theoretical understanding, I would say, is intriguing, and also has the added benefit of having a broader impact (could also be relevant to self-supervised learning). However, when you frame it more narrowly as just SL vs SSL (FixMatch), maybe not so much.

With that said, I appreciate the comparison of SSL vs SL on the same number of training samples. I think this experimental setup is very appropriate and serves as a great demonstration of not just the proposed SA-FixMatch algorithm, but also the theoretical analysis presented in this paper. Do you also have some results using FixMatch, instead of SA-Fixmatch? Also, I'd love to see this experimental setup in the main paper instead of the Appendix, but ultimately it is your choice whether to make this change or not.

---

On the novelty of SA-Cutout

I don't agree that Adversarial Dropout [2] takes a "completely different approach". Dropout operates on the activations of a given layer. If you consider the NN as a recursive-like function, dropout is essentially masking the output of one layer, which is the input of the subsequent layer. If we generalize adversarial dropout to drop out the very first input, i.e., the input image, we could draw parallels between SA-CutOut and Adversarial Dropout (as both methods use the gradient to select which "activations" to mask).

In my original comment, I mentioned that SA-Cutout does not feel like a novel contribution. I still stand by this statement, particularly due to similarities with other gradient-based masking methods (Adv. dropout being one of them; there are a couple examples in the Continual Learning and Domain Generalization fields as well). However, I do acknowledge that this is more of a gut feeling, than a fact that I can ground with strong evidence.

---

By the way, I am inclined to improve my evaluation, but I am still interested in what the authors think about my POV. Thanks,

Do you feel there is more potential to be extracted from the CutOut-SA line of thinking? For example, could doing multiple cutouts on the image to enforce exactly one classifying feature being present in the strong augmentation be a future avenue of improvement?

Thank you for your insightful comments. As described in Sec. 4.3, our current implementation of SA-CutOut leverages Grad-CAM to localize learned semantic regions and applies a mask centered on the region with the highest average attention score. To ensure a direct and fair comparison, we kept both the mask size and the number of masks identical to those in the original CutOut.

You raise an excellent point about applying multiple square masks to more effectively eliminate learned semantic features. However, this approach carries an inherent risk of also removing unlearned semantic features. To explore your suggestion, we experimented with a "Double SA-CutOut" strategy. In this variant, after placing the initial mask centered on the region with the highest average attention score, we added a second mask centered on the point with the next-highest attention score outside the area covered by the first mask.

Using the same experimental setup as detailed in our manuscript and FixMatch, we evaluated this approach by training WRN-28-8 on CIFAR-100 with 10,000 labeled samples and WRN-37-2 on STL-10 with 1,000 labeled samples. The test accuracy (%) results below show that "Double SA-FixMatch" can further improve SA-FixMatch’s performance, albeit with marginal gains in certain cases, such as STL-10.

We will incorporate this multiple SA-CutOut approach into a full ablation study in our final revision to further analyze its effects.

Additionally, we see further potential in the SA-CutOut methodology. As analyzed in Sec. 4.2, removing learned semantic features through strong augmentations $\mathcal{A}(\cdot)$ enforces the learning of unlearned semantic features during Phase II of training. Furthermore, if we can not only remove the learned semantic features from input images but also increase the presence of unlearned features, the learning of comprehensive features in Phase II can be further facilitated, according to analysis in Appendix E.

To leverage this insight, we propose an extension to SA-CutOut. Instead of replacing the learned semantic region with a gray patch (as in the current SA-CutOut), we suggest pasting a patch from another part of the same image that has low attention value, as detected by Grad-CAM, and is more likely to contain unlearned semantic features. This approach not only removes learned semantic features but also enriches the input image with unlearned features, making the learning of comprehensive features in Phase II more effective.

While this idea appears promising, it requires additional implementation and experimental validation, which we aim to explore in future work.

Line 87, wrong citation "FixMatch (Xie)" => "FixMatch (Sohn)"

Thank you for your kind reminder. We have corrected this in our revised version, and the change has been highlighted in blue for clarity.

Thank you for the insightful comments. Below we provide our point-by-point response and hope to address your concerns.

The assumptions regarding data augmentation appear artificial.

For our assumption on strong augmentation $\mathcal{A}(\cdot)$ in Assumption 3, we focus on its probabilistic feature removal effect as explained in Sec. 3.2. According to multi-view data assumption in Def. 1, the inpute image is composed of feature patches of $v_{y,1}$ and $v_{y,2}$, and the noise patches. Therefore, for simplicity and clarity of analysis, we assume $\mathcal{A}(\cdot)$ to have probability $1-\pi_2$ to remove only the noise patches while retaining the feature patches of $v_{y,1}, v_{y,2}$, probability $\pi_1 \pi_2$ to remove only the patches of feature $v_{y,1}$ while retaining noise patches and patches of feature $v_{y,2}$, and probability $(1-\pi_1) \pi_2$ to remove only the patches of feature $v_{y,2}$. The reason for this assumption on strong augmentation $\mathcal{A}(\cdot)$ is that we want to represent the probability that $\mathcal{A}(\cdot)$ removes learned semantic feature of Phase I from the multi-view images, which is either $\pi_1 \pi_2$ or $(1-\pi_1) \pi_2$ according to Assumption 3. This portion of strongly-augmented unlabeled data containing only the unlearned feature and noise patches dominates the unsupervised loss, since the rest samples containing the learned feature are already correctly classified by the network after Phase I and contribute minimally to the training loss. Then, according to our analysis in Sec. 4.2, the network is able to learn the unlearned semantic features in Phase II and therefore achieve better generalization performance.

Why can’t the augmentation be agnostic about what the patch contains

In practice, data-agnostic strong augmentation $\mathcal{A}$ may simultaneously remove portions of both the feature patches $v_{y,1}, v_{y,2}$ and noise patches. Nonetheless, our analysis remains valid under this setting. Under this setting, with probability $p = O(\frac{1}{k^{C_p}})$, strong augmentation $\mathcal{A}$ removes all $C_p$ feature patches of the learned feature from Phase I while preserving the $C_p$ feature patches of the unlearned feature. Assuming sufficient unlabeled data, where $|\mathcal{Z}_u| = \text{poly}(k) |\mathcal{Z}_l|$ and $p|\mathcal{Z}_u| > |\mathcal{Z}_l|$, the subset of strongly augmented unlabeled data that contains only the unlearned feature and noise patches becomes substantial in size and dominates the training loss since the rest samples containing the learned feature are already correctly classified by the network after Phase I and contribute minimally to the training loss. As outlined in Sec. 4.2, this enables the network to effectively learn comprehensive semantic features during Phase II of training.

The proposed SA-FixMatch can slow down training.

According to our analysis in Section 4.2, the strong augmentation $\mathcal{A}$ only begins to take effect after the network has learned partial features during Phase I of the learning process. Based on this insight, we apply SA-CutOut exclusively during the final 32 epochs of training, as detailed in Appendix K.5. This selective application ensures computational efficiency while maintaining the intended benefits of SA-CutOut. As a result, the total runtime of SA-FixMatch is approximately 1.15 times that of FixMatch on all datasets, which we consider a reasonable trade-off given the significant improvement in generalization performance.

missed some previous works exploring the effects of augmentation on feature learning process

Thank you for pointing out the missing references. While [1] analyzes the feature learning process of contrastive learning and emphasizes the critical role of data augmentation, our work focuses on semi-supervised learning (SSL) and its ability to learn comprehensive semantic features. In contrast, [1] targets contrastive learning, aiming to learn sparse features and avoid spurious dense features.

Similarly, [2] investigates the significant role of the projection head in enabling non-contrastive self-supervised learning methods to learn comprehensive features. Their work also divides the learning process into multiple phases based on the nature of non-contrastive self-supervised learning. However, our study centers on FixMatch-like SSL methods, where the two-phase feature learning process arises from the combination of supervised and unsupervised loss objectives unique to SSL.

We have incorporated these references into our revision and included a discussion of their relevance, with the updates highlighted in blue for clarity.

[1] Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning. Zixin Wen, Yuanzhi Li [ICML 2021]

[2] The Mechanism of Prediction Head in Non-contrastive Self-supervised Learning. Zixin Wen, Yuanzhi Li [NeurIPS 2022]