Towards Understanding Why FixMatch Generalizes Better Than Supervised Learning
Authors: Jingyang Li
Jiachun Pan
Vincent Y. F. Tan
Kim-chuan Toh
Pan Zhou
Venue: ICLR 2025 Oral (2025)
Keywords: deep semi-supervised learning
generalization error
feature learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Semi-supervised learning (SSL), exemplified by FixMatch (Sohn et al., 2020), has shown significant generalization advantages over supervised learning (SL), particularly in the context of deep neural networks (DNNs). However, it is still unclear, from a theoretical standpoint, why FixMatch-like SSL algorithms generalize  better than SL on DNNs. In this work, we present the first theoretical justification for the enhanced test accuracy observed in  FixMatch-like SSL applied to DNNs by taking  convolutional neural networks (CNNs) on classification tasks as an example. Our theoretical analysis reveals that the semantic feature learning processes in FixMatch and SL are rather different. In particular, FixMatch learns all the discriminative features of each semantic class, while SL only randomly captures a subset of features due to the well-known lottery ticket hypothesis. Furthermore, we show that our analysis framework can be applied to other FixMatch-like SSL methods, e.g., FlexMatch, FreeMatch, Dash, and SoftMatch. Inspired by our theoretical analysis, we develop an improved variant of FixMatch, termed Semantic-Aware FixMatch (SA-FixMatch). Experimental results corroborate our theoretical findings and the enhanced generalization capability of SA-FixMatch.

Published as a conference paper at ICLR 2025
TOWARDS UNDERSTANDING WHY FIXMATCH GENER- ALIZES BETTER THAN SUPERVISED LEARNING
Jingyang Li' Jiachun Pan' Vincent Y. Tan Kim-Chuan Toh'
Pan Zhou?*
National University of Singapore
2 Sinnaporee Management University
1i si_jingyangeu. nus edu {vtan, mattohkc @ edu.sg
pan ban.jjachuneouttoon com
panzhou8smu.c edu. sg
ABSTRACT
Semi-superviin learning (SSL), exemplified by FixMatch (Sohn et al., 2020), has shown significant generalization advantages over supervised learning (SI.), partieu- larly in the context of deep neural networks (DNNs). However, it is still unclear, from a theoretical standpoint, why FixMatch-likke SSL algorithms generalize better than SL DNNs. In this work, present the first theoretical justification for the enhanced test accuracy observed in FixMatch- SSL applied to DNNs by taking convolutional neural networks (CNNs) classification tasks as example. Our theoretical analysis reveals that the semantic feature learning processes in FixMatch and SL rather different, In particular, FixMatch learns all the discriminative features of each semantic class, while SL. only randomly captures a subset of fea- tures due to the well-known lottery ticket hypothesis. Furthermore, we show that our analysis framework can be applied to other FixMatch-like SSL methods, e.g., FlexMatch, FreeMatch, Dash, and SoftMatch. Inspired by our theoretical analysis, we develop an improved variant of FixMatch, termed Semantic-Aware FixMatch (St-FixMatch). Experimental results corroborate our theoretical findings and the enhanced generalization capability of SA-FixMatch.
INTRODUCTION
Deep learning has made significant strides in various domains, including computer vision and natural language modeling (He al., 2016; Vaswani et al., 2017; Radford al., 2018; Dosovitskiy et al., 2020; Ho et al., 2020; Mildenhall et al., 2021; Ouyang et al., 2022: Schick et al., 2023). These advancements largely stem from scalable supervised learning. where increasing both network size and labeled dataset size typically enhances performance. However, in real-world scenarios, labeled data are often scarce. The benefits of larger datasets come a high cost, as labeling requires human effort and can be prohibitively expensive, particularly in domains that rely expert annotation (Sohn et al., 2020; Ouali et al., 2020; Zhou et al., 2020; Zhang et al., 2021a; Pan et al., 2022).
To address this challenge, semi-supervised learning (SSL) (Berthelot et al., 2019b; Sohn et al., 2020; Zhang et al., 2021a) has emerged as promising solution, demonstrating effectiveness across various tasks. The methodology of SSL involves training a network on both labeled and unlabeled data, where pscudo-labels for the unlabeled data are generated during training. As a leading SSL approach, FixMatch (Sohn al., 2020) first generates pseudo-label using the current model's prediction on a weakly augmented unlabeled image. then selects the highly-confident pseudo-label as the training label of the cronnly-augmented version of the same image, and trains the model together with the vanilla labeled data. By accessing large amount of cheap unlabeled data with minimal human effort, FixMatch has effortlessly and greatly improved supervised learning. Moreover, thanks to its effectiveness and simplicity, FixMatch has inspired many SoTA FixMatch- like SSL works, e.g., Fltx (Zhang et al., 2021a), FreeMatch (Wang et al., 2022b), Dash (Xu et al., 2021), and SoftMatch (Chen et al., 2023), and is seeing increasing applications across many deep learning tasks (Xie al., 2020; Xu et al., 2021; Schmutz et al., 2022; Wang al., 2022b; Chen al., 2023).
Despite FixMatch's 's practical success, its theoretical foundations lag behind its applications. Specif- ically, it remains unclear how FixMatch and its SL counterpart perform on deep neural networks,
"ooresponding author.

---

Published as a conference paper at ICLR 2025
despite strong interest. Moreover, few theoretical studies investigate why SSL outperforms SL in test performance on networks, let alone FixMatch. Most existing works (He et al., 2022; Tifrea et al., 2023) analyze oversimplified models, such linear learners, which differ significantly from the highly nonlinear and non-convex networks used in real-world SSL. Consequently, these studies fail to capture FixMatch's learning mechanism. Other works (Rigollet, 2007; Van Engelen & Hoos, 2020; Guo et al., 2020) treat models as black-box functions under restrictive conditions, offering insights that do not account for the CNN dependencies crucial FixMatch's superiority.
Contributions. To address these issues, we theoretically justify the superior test performance of FixMatch-like SSL over SL in classification tasks, using FixMatch as a case study. We analyze the semantic feature learning processes in FixMatch and SL, explaining their test performance differences and inspiring an improved Fitcatch variant. Our key contributions are summarized as follows:
Firstly, we prove that FixMatch achieves superior test accuracy over SL on three-layer CNN. Specif- ically, under the widely acknowledged multi-view data assumption (Allen-Zhu & Li, 2023), where multiple/single semantic features exist in multi/single-view view data, FixMatch consistently achieves zero training and test classification errors on both multi-view and single-view data. In contrast, while SL achieves zero test classification error on multi-view data, it suffers up to 50% test error on single-view data, showcasing FixMatch's 's superior generalization capacity compared to SL.
Secondly, our analysis highlights distinct feature learning processes between FixMatch and SL, directly affecting their test performance. We show that FixMatch comprehensively captures all semantic features within each class, virtually eliminating test classification errors. But SL learns only a partial set of these semantic features, and often fails on single-view samples due to the unlearned features, explaining its poor test classification accuracy on single-view data.
Finally, inspired by these insights, we introduce an improved version of FixMatch termed Semantic- Aware FixMatch (SA-FixMatch). This variant enhances FixMatch by masking learned semantics in unlabeled data, compelling the network to learn the remaining features missed by the current network. Our experimental evaluations confirm that SA-FixMatch achieves better generalization performance than FixMatch across various classification benchmarks.
RELATED WORKS
Modern Deep SSL Algorithms. Pseudo-labeling (Scudder, 1965; McLachlan, 1975) and consis- tency regularization (Bachman et al., 2014; Sajjadi et al., 2016; Laine & Aila, 2016) are the two important principles responsible for the success of modern deep SSL algorithms (Berthelot et al., 2019b;a; Xie et al., 2020; Zhang al., 2021a; Xu al., 2021; Wang al., 2022b; Chen et al., 2023). FixMatch (Sohn et al., 2020), as a remarkable deep SSL algorithm, combines these principles with weak and strong data augmentations, achieving competitive results especially when labeled data is limited. Following FixMatch, several works, e.g., FlexMatch (Zhang et al., 2021a), Dash (Xu al., 2021), FreeMatch ( (Wang et al., 2022b), and SoftMatch (Chen et al., 2023), try to improve FixMatch by adopting a flexible confidence threshold rather than the hard and fixed threshold adopted by FixMatch. These modern deep SSL algorithms can achieve remarkable test accuracy even trained with one labeled sample per semantic class (Sohn et al., 2020; Zhang et al., 2021a; Chen et al., 2023).
SSL Generalization Error. Previous works on generalization capacity of SSL focus on general machine learning setting (Rigollet, 2007; Singh et al., 2008; Van Engelen & Hoos, 2020; Wei et al., 2020; Guo et al., 2020; Mey & Loog, 2022). In particular, the authors here view the model black-box function under certain assumptions which does not reveal the dependence on model design. Some recent works (He al., 2022; Tifrea al., 2023) analyze the generalization performance of SSL under the binary Gaussian mixture data distribution for linear learning models. The over-simplified model is significantly different from the highly nonlinear and non-convex neural networks.
Feature Learning. Prior works on feature learning has shed light on how neural networks learn and represent data (Wen & Li, 2021; 2022; Allen-Zhu & Li, 2022; 2023). For instance. Allen-Zhu & Li (2023) explored how ensemble methods and knowledge distillation enhance generalization, while Wen & Li (2021) explained how contrastive learning captures sparse features and avoids spurious dense ones. Empirically, Park al. (2018) proposed adversarial dropout to adapt neural networks based on their learning status, improving test performance. Despite these advances, to the best of our knowledge, this work is the first to analyze feature learning of neural networks in semi-supervised settings, with our theory-inspine SA- FixMatch achieving superior generalization performance.
2

---

Published as a conference paper at ICLR 2025
Figure I: Visualization of pretrained ResNet-50 (He et al., 2016) using Grad-CAM. ResNet-50 locates different regions for different images, e.g., wheel, rearview mirror, front light, and door.
3 PROBLEM SETUP
Here we first introduce the necessary nulti-view data assumption used in this work, and then present FixMatch, a popular and classic SSL. approach, to train three-layered CNN on a k-class classification problem. For brevity, we use O(), (-) to hide constants w.r.t. ho and use ((), (()) to hide polylogarithmic factors. Let poly(k) and polylog(k) respectively denote ((kC) and (log k) with constant C > O. We use [nx] to denote the set of 21. .n..
3.1 MULTI-VIEW DATA DISTRIBUTION
Following Allen-Zhu & Li (2023), adopt the multi-view data assumption, which posits that each semantic class comprises multiple distinct semantic independently facilitate correct classification. To empirically validate this, we use Grad-CAM (Sel- varaju et al., 2017) to identify class-specific regions in images. As shown in Figure 1, Grad-CAM highlights distinct, non-overlapping regions, such as different parts of a car, that contribute recog- nition. These results support the findings of Allen-Zhu & Li (2023), confirming the existence of multiple independent semantic features within each class.
as car lights and wheels-thar can
Now we introduce the multi-view data assumption in Allen-Zhu & Li (2023), which considers dataset with k semantic classes. Let each sample pair (X. 3) consists of the sample X, which is comprised of set of P patches (dtp E [R pp=1: and y E [A:] as the class label. We assume each class has two semantic features, vi, and 1222 in Rd, capable of independently ensuring correct classification. While this analysis focuses on two features per class, the methodology extends to multiple features. Below we define as the of all semantic features across the it classes:
(1) The conditions ensure the distinction of each class and its semantic features. Accordingly, we define the multi-view and singe-view distributions Pm, and D., where data from Dm has two semantic features, and those from DD have only one. Set sparsity parameter s = polylog(k) and constant Cp-
y= (15,1, U1 || = ||v,,2ll2 1, 1. uy.r if (i, + (f',"))
Definition (Informal, Data distribution (Allen-Zhh Zhu & Li, 2023)). The data distribution D contains data from the multi-view data distribution Dm with probability 1 - μ, and data from the single-view data distribution D, with probability μ = poly(k) We define (X, v) ~ D by randomly uniformly selecting label y [k] and generate data X accordingly follows.
(a) Sample a set of noisy features V uniformly at random from {vr,1, 2222 ip each with probability s/k. Then the whole feature set of X is V(X)= = ( 2. ),,),, i.e. the noisy feature set V plus the main features {1y,1, Vy.23-
(b) For each E V(X), pick Cp disjoint patches in [P] and denote them as Px(X). For patch = Zp "noises" E IRd, where the coefficients 2p 2 0 satisfy: (bl) For "multi-view" data (X,y) D.n EpEP.(X) Zp E [1,0 when E Uy,21 and
p E Px(X), we sel xp.
EpERA(X) Zp E 0.4] when e E V(X) \ (1y,1, 2.
(b2) For "single-view" data (X,y) E DD,, pick a value i E [2) randomly uniformly as the index of the main feature. Then Epep.(x) 2p [1,) when Vy.. EpEP. Zp E [p, 0(p) (p k -0.01) when v = v V- and ΣpEP.(x) 2p = polyloR(R) when V E V(X) \ (ey.1,uy22h (c) For euch purely noisy patch p E [P] UX). we set Xp "noises".
For the details of Def. 1, please see Def. 7 in Appendix A, and also see more explanations in Appendix L. According to the definition, multi-view sample (X, y) E Dm has patches with two semantic features 1 and Uy.2 plus some noises, while a single-view sample (X, E D, has patches with only one semantic feature 1 or uy22 plus noises.
3

---

Published as a conference paper at ICLR 2025
3.2 FIXMATCH FOR TRAINING NEURAL NETWORKS
Here we introduce the representative SSL approach, FixMatch and its variants, on a k-class classifica- tion problem. the most popular task in SSL.
Neural Network For the network, we assume it as three-layer CNN which has mk convolutional kernels (wirrhee(t),rr rej)) Its classification probability logit, (F.)) on class E [A] is defined as
(Fgit,(F,X) exp(F((X)) Σ Sjel ex)(F)(X)),
where F(X) (FI F&(()) R is defined as (X( = Ere(m) Eperr ReI.
Vi E [M].
Here ReLU (Allen-Zhu & Li, 2023) is smoothed ReLU that outputs zero for negative values, reduces small positive values to diminish noises, and maintains a linear relationship for larger inputs. This ensures ReLU to focus important features while filtering out noises. See details in Appendix A.
This three-layer network, comprising linear mapping, activation, and softmax layer, captures essential neural network components, offering valuable insights into SSL training. Notably, many theoretical studies also use shallow networks (e.g.. two-layer models) to gain insights into deep networks (Li & Yuan, 2017; Arora et al., 2019; Zhang et al., 2021b). Moreover, this setup matches the architecture in Allen- & Li (2023), enabling direct comparisons between our FixMatch results and their SL findings in Sec. 4.2.
SSL Training For FixMatch like SSLs, at t-th iteration, it has two types of losses: 1) a supervised one (d) on labeled data, and 2) an unsupervised one ( on unlabeled data, For _ it is cross- entropy loss on labeled dataset Z₁:
(4) where (X) is weak augmentation applied to input X. In practice, a(X) typically consists of random horizontal flip and a random crop that retains most region of the image (Sohn et al., 2020; Zhang et al., 2021a), which often do not alter the semantic features. Hence, treat the weak augmentation as an identity map to simplify our analysis. Additionally, experiments in Appendix K.2 confirm that weak augmentation has minimal impact on SSL training.
0 = -[(xE) (1) (X1,8) = B(x,,)) log logig,ooit.oooo (F())
For the unsupervised loss _ (Xw). a weakly-augmented unlabeled sample a (X.) is fed into the net- work to obtain classification probabilities (Eg),,(F'*), a(X))) for i E [k]. If the maximal probability exceeds a confidence threshold T, E (0, 1]. i.e. max; ()g(t,(FF() a(X..) 2 Tr, FixMatch-like SSLs use it as the pseudo-label supervise the corresponding strongly augmented sample A(X.):
( =Ex_~z,1 1 (X.) = Ex,~z, [ (2T)) log (X),
(5)
where is the pseudo-label = arg max (logit, (x.))) Here, FixMatc--like SSLs use pseudo-labels generated from weakly-augmented samples to supervise the corresponding strongly- augmented ones, enforcing consistency regularization on model predictions, which we will show in Sec. 4.2 is erucial for the superior generalization performance of SSL compared to SL. For threshold T. FixMatch (Sohn et al., 2020) sets it as a constant threshold T = T (e.g. 0.95) for high pseudo-label quality. Current SoTA SSLs, e.g., Match (Zhang et al., 2021a), Free (Wang et al., 2022b), Dash (Xu et al., 2021), and SoftMatch (Schick et al., 2023), follow FixMatch framework, and often design their own confidence threshold in Eq. (5). This decides the applicability of our theoretical results on FixMatch in Sec. 4 to these FixMatch-like SSLs. See details in Appendix G.
For strong augmentation A(-), it often uses CutOut (DeVries & Taylor, 2017) and Rundenttent (Cubuk et al., 2020). CutOut randomly masks a large square region of the input image, potentially removing partial semantic features. Experimental results in Appendix K. confirm the significant impact of CutOut on image semantics and model performance. RandAugment includes various trans- formations, e.g., rotation, translation, solarization. Appendix K. reveals that those augmentations that may remove data semantics also have a large impact on model performance. Based on these findings, model the probabilistic feature removal effect of A(-) for analysis in Sec. 4.1.
Now given the training loss (t)) ! gradient descent (GD) to update the model parameters {wi, (eee)) in the network:
XL at the f-th iteration, we adopt the widely used
((+1)
w v/ usrr I!!!) V
(1)
(6)
4

---

Published as a conference paper at ICLR 2025
where 17 2 0 is learning rate, and À > is the weight balance the two losses. According the common practice (Sohn et al., 2020; Zhang et al., 2021a; Xu et al., 2021: Wang et al., 2022b; Chen et al., 2023), set À 1 in both our theoretical analysis and experiments.
MAIN RESULTS
In this section, we first prove the superior generalization performance of FixMatch compared with SL. Next we analyze the intrinsic reasons for its superiority over SI. via revealing and comparing the semantic feature learning process. Finally, inspired by our theoretical insights, we propose a Semantic-Awand FixMatch (SA-FixMatch) to better learn the semantic features.
4.1 RESULTS ON TEST PERFORMANCE
Here we analyze the performance of FixMatch, and compare it with its SL counterpart, whose implementation is simply setting the weight À = 0 for the unsupervised loss in Eq. (6).
As discussed in Sec. 3.1, we assume the training dataset Z follows the multi-view distribution D (Def. 1), with multi-view and single-view sample ratios of 1 - and respectively. Each class i [k]] has two i.i.d. semantic features %1 and 22 both of which are capable of predicting label i. -ulw samples contain both features, while single-view samples have only one. For clarity, we denote the labeled multi-view viet and vielleview subsets as Zi,m and Zt,s; and the unlabeled subsets as Zu,m and Zu.s. Below, we outline the necessary assumptions on the dataset and model initialization. Assumption 2. (a) The training dataset follows the distribution D, and the size of the unlabeled data satisfies Nu, = =Zz,m U Zu, = Zt. U 2 poly
(b) Each convolution kernel Wir (i E [k), r E [ml) is initialized by a Gaussian distribution N N(00 afT). where o0 1/k and q 2 3 is given in the definition of ReLU.
Assumption 2(a) indicates that number of unlabeled data significantly exceeds that of the labeled data, a common scenario given the lower cost of acquiring unlabeled versus labeled data. The Gaussian initialization in Assumption 2(b) accords with the standard initialization in practice, and is mild. Moreover, we also need assumptions on the strong augmentation A(-) to formulate the effect of consistency regularization in unsupervised loss Eq. (5).
Assumption 3. Suppose for a given image, strong augmentation A(-) randomly removes its semantic patches and noisy patches with probabilities सं and 1 22, respectively.
1) For a single-view image, the sole semantic feature is removed with probability 
2) For a multi-view image, either of the two features, Vs,1 or 04,2, is removed with probabilities πT and (1 - T2) respectively. We define strong augmentation A(-) for multi-view data: for E [P].
<2) max (2))
if fgg11 is in the patch Tp: if Vy in the patch Zp- otherwise (noisy patch),
A(x,)
max(1 62 E2
(1-c2)=pp -2))=p
where 61 and (2 i.i.d. Bernoulli variables, respectively equaling to 0 with probabilities xa and m2-
As discussed in Sec. 3, for strong augmentation A(-). we focus on its probabilistic feature removal effect on the input image, caused by techniques like CutOut and certain operations in RandAugment, such as solarization. The use of the max function ensures that 6j is active when 62 = 0, indicating that A(-) removes one feature at time. Further details are provided in Appendix A.
Based on the above assumptions, we analyze the training and test performance of FixMatch, and summarize our main results in Theorem 4 with its proof in Appendix F.
Theorem 4. Suppose Assumptions 2, 3 hold. For sufficiently large k and m polylog(k), setting S 1/poly(k) and running FixMatch for T = poly(k) (k)/ iterations ensures:
(a) Training performance is good. For all training samples (X,y) Z, with probability at least
1 - e R(lag" k), we have
FXT) 2 max,+y
+ 21 k).
(b) Test performance is good. With probability least e eS(llog? M) over the selection of any nil test sample (X,8) Dm and single-view test sample (X,u) ~ Dz, we have
F(T( max (X)
5

---

Published as a conference paper at ICLR 2025
Theorem 4(a) shows that after T poly(k)/n training iterations, the network F(I) trained by FixMatch can well fit the training dataset Z, achieving zero classification error. Specifically, for any training sample (X, y) 2, the predicted value (X) for the true label y consistently exceeds the predictions F (X) for all * y. ensuring correct classification. More importantly, Theorem 4(b) establishes that the trained network FF(2) can also accurately classify test samples (X, Dm UD2.
validating FixMatch's s strong generalization performance.
Now we compare FixMatch with SL (i.e. À = 0 in Eq. (6)) under the same data distribution and the same network. According to Allen-Zhu & Li (2023), under the same assumption of Theorem 4, after running standard SL for I = poly(k)/n iterations, SL can achieve good training performance in Theorem 4(a). However, SL exhibits inferior test performance compared to Fix Specifically, both methods achieve zero classification enror on multi-view samples (X, y) 'Dmm while on single- view data (X, y) ~ D., SL achieves only about 50% classification accuracy, significantly lower than FixMatch's 's nearly 100% accuracy. See Appendix B for more details on SL.
For other FixMatch-like SSLs such as Flex (Zhang et al., 2021a), FreeMatch (Wang et al., 2022b), Dash (Xu et al., 2021), and SoftMatch (Chen et al., 2023), our theoretical results in Theorem and the comparison with SL are also broadly applicable. Due to space limitations, we defer the discussions Appendix G. These theoretical results justify the superiority of FixMatch- SSLs over SL. aligning with empirical evidence from several studies (Sohn et al., 2020; Zhang et al., 2021a; Wang et al., 2022b; Xu et al., 2021; Chen et al., 2023).
4.2 RESULTS ON FEATURE LEARNING PROCESS
Here we analyze the feature learning process in FixMatch and SL, and explain their rather different test performance as shown in Sec. 4. To monitor the feature learning process, we define
Σ, [ e.,))+, E E
I [2]
rE(m)]
as an indicator of feature learning for Ui, in class i. It represents the total positive correlation between feature 1ia and all m convolution kernels wi,r (r E (m]) at iteration I. A larger $ indicates better capture and utilization of U/.1 for classification. See Appendix D for further discussion.
Next, FixMatch applies a confidence threshold (T) to regulate the unsupervised loss in Eq. (5), dividing its feature learning process into Phase I and Phase II. In Phase I, the network relies primarily on supervised loss, as it cannot yet generate confident pseudo-labels. As training progresses, the network learns partial features, improving its ability to predict confident pseudo-labels for unlabeled data. This transition marks the start of Phase II. where the unsupervised loss plays larger role, driven by consistency regularization between weakly and strongly augmented samples.
Now we are ready to present the feature learning process of FixMatch and SL in Theorem 5. Theorem 5. Suppose Assumptions 2, 3 hold. For sufficiently large i and m polylog(k), setting 7 S 1/poly(k) and r = - ((1/s²) ensures that, with probability at least e -2(0oo R):
(a) FixMatch. At the end of Phase I, which runs for Tı voly(k)/7) iterations,
(TT)) 2 2llog)) k),
1 I 1/polylog(k),, Vi E [k]], e [2].
(8)
After Phase II, which runs for another T2 = poly(k)/n iterations,
(T) +2) 2 S(llog k),
Vi E [k], [2].
(9)
(b) Supervised Learning. After T > poly(k)) iterations, Eq. (8) always holds.
See its proof in Appendix F. Theorem 5(a) indicates that Phase I in FixMatch continues for Ti poly(k)/n iterations. During this phase, the network learns only one of the two semantic features per class. Specifically, in Eq. (8), for any class E [k), there exists an index E [2] so that the correlation
score क (7T) exceeds 22llg k),, showing feature Vi,t is captured; and the score Tb (Ti)
5.3-1 remains low, indicating failure of learning V1,3-1. Then we analyze classification performance when Eq, (8) holds.
Corollary Under the same conditions as Theorem Assume Eq. (8) holds for the trained network F(T). For any sample X from class containing the feature Ug the network (T) can correctly predict label i. Conversely, if X contains only the feature Vi,3-1, to F(T) would misclassify X.

---

Published as a conference paper at ICLR 2025
See its proof in Appendix D. According Corollary 6, after Phase I, the network correctly classify multi-view samples, as each contains two semantic features and the network learns at least one of them. However, for single-view samples, which contain only one semantic feature, the classification accuracy is around 50% since the network may not learn the specific feature present. Then by running another T2 iterations in Phase II, Theorem 5(a) shows that Fix enables the network to capture both semantic features 11 and Vi, for each class E [A:]. As indicated by
Eq. (9), all features achieve large correlation scores 4 (T)+72) for all i E [k]. I E [2]. Therefore, by Corollary 6, the network trained by FixMatch can correctly classify all training and test samples with high probability, explaining the strong generalization performance observed in Theorem 4.
For Phase II of FixMatch, the reason for it learn the semantic features missed in Phase is as follows. Having learned one semantic feature per class in Phase I. the network is capable of generating highly confident pseudo-labels for weakly-augmented multi-view samples. As the confidence threshold close to 1 (e.g., T 0.95), it ensures the correctness of these pseudo-labels. Then, FixMatch uses these correct pseudo- to supervise the corresponding strongly-augmentt samples via consistency regularization. As shown in Eq. (7), strong augmentation A(-) randomly removes the learned features in unlabeled multi-view samples with probabilities π I22 (1 )T2,, effectively converting these samples into single-view data containing the unlearned feature. Given the large volume of unlabeled data specified in Assumption 2, these transformed single-view samples are sigmificant in their size. Accordingly, they dominate 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. Consequently, the unsupervised loss enforces the network to learn the unlearned feature in Phase II.
7 7= 1 (1/
For SL, Theorem 5(b) shows that with high probability, SL learns only one of the two features for each class, consistent with Phase in FixMatch. By Corollary 6, SL can correctly classify multi-view data using the single learned feature but achieves only about 50% test accuracy on single-view data due to the unlearned feature, aligning with Sec. 4.1. In contrast, FixMatch achieves nearly 100% test accuracy on both multi-view and single-view data, as it learns both semantic features for each class.
The key difference between FixMatch and SL lies in the additional unsupervised loss, which es- sentially serves as consistency regularization. Beyond SSL, consistency regularization also plays a crucial role in other learning paradigms. For example, self-supervised learning, promotes the acquisition of richer semantic features during pretraining. Our theoretical analysis offers valuable insights into these broader settings, and we leave the exploration as future work.
Comparison to Other SSL Analysis. This work differs from previous works from two key aspects. (a) Our work provides the first analysis for FixMatch-like SSLs on CNNs. In contrast, many other works (He et al., 2022; Tifrea et al., 2023) analyze over-simplified models, e.g., linear learning models, that differs substantially from the highly nonlinear and non-conver networks used in SSL. Some other works (Rigollet, 2007; Singh al., 2008; Van Engelen & Hoos, 2020) view the model as a black-box function and do not reveal insights to model design. (b) This work is also the first one to reveal the feature learning process of SSL., deepening the understanding to SSL. and unveiling the intrinsic reasons of the superiority of SSL over its SI. counterpart.
4.3 SEMANTIC- FIXMATCH
The analysis of feature learning Phase II in Sec. 4.2 shows the crucial role of strong augmentation A(-) via consistency regularization in Eq. (5) learn the features missed in Phase I. However, according to Eq. (7), A(-) only removes the learned feature with probabilities T2 or (1- )22 This means given Nu.m unlabeled multi-view samples, A(-) can generate at most N = (2, (1 π2 ) samples containing only the missed features to enforce the network to learn them in Phase II. So FixMatch does not fully utilize unlabeled data in Phase II to learn comprehensive features, especially when iT2 is small, which usually happens when semantics only occupy small portion of the image so that strong augmentation A(-) like CutOut (DeVrics & Taylor, 2017) and RandAugment has small probability to remove semantics (e.g., .. in ImageNet, see Appendix K.6).
Motivated by this finding, we propose Semantic- FixMatch (SA- 3A-FixMatch) to improve the probability of removing learned features by replacing random CutOut in FixMatch's strong augmen- tation A(-) with Semantic- Aware CutOut (SA-CutOut). Specifically, if the unlabeled sample X has highly confident pseudo-label, SA-CutOut first performs Grad-CAM (Selvaraju al., 2017) on the
7

---

Published as a conference paper at ICLR 2025
network F to localize the learned semantic regions which contribute to the network's class prediction and can be regarded as features. Then for each semantic region, SA-CutOut finds its region center, ie., the point with highest attention score in the region, and then averages attention score within 9xq bounding box centered at this point (e.g.. Q q= 16). Finally, SA-CutQut selects one semantic region with the highest average score for masking. Here masking semantic region with the highest score can enforce the network to learn the remaining features that are not well learned or missed in Phase I, as they will not be detected by Grad-CAM or detected with relatively low attention scores. In this way, Match can enhance vanilla FixMatth to better use unlabeled data to learn comprehensive semantic features. For analysis, see our formulation of A(-) with SA-CutOut in Appendix E.
In Theorem 13 of Appendix A, we prove that SA-hh enjoys the same good training and test accuracy in Theorem 4, but reduces the required number of unlabeled data samples Nº in vanilla FixMatch to N₂ = max n T2; (1 - π (22 J.Nu. where Nu is given in Assumption 2. This data efficiency stems from SA- Satch's 's use of SA-CutOut, which selectively removes the well- learned features, thereby compelling the network to focus on learning previously missed or unlearned features. Detailed theoretical discussions and proof' are presented in Appendix E, illustrating how SA-FixMatch outperforms vanilla FixMatch in terms of data efficiency and better test performance.
Moreover, our analysis of SA AA-FixMatch remains valid even when the labeled and unlabeled datasets contain the same images, as SA-CutOut deterministically removes the learned features. This ensures the network continues to learn new semantic features in Phase II even with the same images as unlabeled data. Experiments in Sec. 5.4 further confirm that SA-FixMatch outperforms FixMatch and SL in this setting, validating the effectiveness of SA-CutOut in enhancing feature learning.
As discussed in Sec. 3.2, SoTA deep SSLs, including FlexMatch (Zhang et al., 2021a), FreeMatch (Wang et al., 2022b), Dash (Xu et al., 2021). and SoftMatch (Chen et al., 2023), of- ten build upon FixMatch, and only modify the confidence threshold Te in Eq. (5). Hence, SA-CutOut is also applicable to these FixMatch-likk SSLs to enhance performance. Experimental results in Sec. 5.3 validates the effectiveness and compatibility of SA-CutOut.
5 EXPERIMENTS
To corroborate our theoretical results, we evaluate SL, FixMatch, and SA-FixMatch on CIFAR-
100 (Krizhevsky et al., 2009), STL-I0 (Coates al., 201 1), Imagewoof (Howard & Gugger, 2020), and ImageNet (Deng et al., 2009). Following standard SSL evaluation protocols (Sohn et al., 2020; Zhang et al., 202 la; Wang et al., 2022a), we use WRN-28-8 (Zagoruyko Komodakis, 2016) for CIFAR-100, WRN-37-2 (Zhou et al., 2020) for STL-10 and Imagewoof. and ResNet-50 (He et al., 2016) for Ietge We also apply SA-CutOut to other FixMatch-like SSL. methods and compare their performance against the originals. All experiments are repeated three times, reporting the mean and standard deviation. Further experimental details are provided in Appendix K.4 and K.5.
5.1 CLASSIFICATION RESULTS
Here evaluate the generalization performance of SL, FixMatch, and SAtFixMatch under varying amounts of labeled data. Following standard SSL benchmarks (Sohn et al., 2020; Zhang et al., 2021a; Chen et al., 2023), we use the entire training dataset unlabeled dataset.
Table shows that on STL-10, Fixch and SA-FixMatch outperform SL by over 28% in test accuracy across all settings. Similar substantial improvements are observed on other datasets, such as 13%+ on 100 and Imagewoof, and 6%+ on ImageNet. These results highlight the superiority of SSL methods over conventional SL and align with our theoretical findings in Sec. 4.
Meanwhile, Table shows that SA-FixMatch outperforms vanilla FixMatch across all datasets. On Imagewoof, it improves average test accuracy by over 1.5%, while on ImageNet, it achieves a 1.38% gain. On CIFAR- and STL-10, SA-FixMateh also consistently surpasses FixMatch, though with a smaller margin. This variation arises because, in CIFAR-100 and STL-110, the semantic subject occupies most of the image (see Appendix K.6), allowing random square mask in CutOut to effectively remove partial semantic features with high probability, producing similar masking effects as SA-CutOut. However, reducing the CutOut mask size lowers the likelihood of masking semantic features, leading to performance degradation (Table 4). In contrast, on Imagewoof and ImageNet, where the semantic subject occupies less than a quarter of the image (see Appendix K.6), a random square mask in CutOut is less likely to remove semantic features, making SA-CutOut significantly more effective and resulting in SathixMatch achieving much better test performance than Fix Match.
8

---

Published as a conference paper at ICLR 2025
Table I: Comparison of Test Accuracy (%) using the entire training dataset as unlabeled data.
Datireet
CIEAR-100
STL-10 250
Imsrgewoo 1000
ImageeNe 100K
Label Amount
400
2500
10000
40
1000
250
2000
St.
11.4 2012
40,45
+ 0.50
63.77
0.29
23.61
1: 1.60
38.83
1: 1.12
64.88
:: 0:47
25.04
+: 1.54
42.04
1.000
60.77
= 1.04
44.62 1:16
FixMatch
55.16 + 063
71.36
+ 644
71.25
0.22
70,00
+ 4.00
88.73 + 0.92
93.45
0.19
43.00
1.46
64.91
= 111
74.05
0.15
50.80
0:73
MA-FiaMatchh
2:43
72.12
77,46
71.81
46.73
52.18 0.33
Figure 2: Visualization of WRN-28-8 via Grad-CAM on CIFAR-100. Each group of three images corresponds to models trained with SL (left), FixMatch (middle), and SA-FixMatch (right).
The superior test accuracy of SathixMatch over FixMatch aligns with our theoretical analysis in Sec. 4.3. To achieve strong test performance in Theorem 4, Phase II of SSL must effectively remove well-learned features to enforce learning of missed semantic features from Phase I. While FixMatch relies on CutOut to randomly mask learned features, SAtFixMatch consistently masks them using SA-CutOut (Sec. 4.3). As result, with a fixed unlabeled dataset size, SA-FixMatth utilizes unlabeled data more effectively for feature learning, leading to better test performance.
5.2 SEMANTIC FEATURE LEARNING
To visualize the semantic features learned by networks trained by SL, FixMatch, and SA-FixMatch, we use Brad-CAM (Selvaraju et al., 2017) to highlight regions of input images that contribute to the model's 's class-specifie predictions. For SL, FixMatch, and 3Atiihhatch, we follow the default setting of Grad-CAM, and apply it to the last convolutional layer of the WRN-28-8 network on CIFAR-100.
Figure shows that the network trained by SL often captures single semantic feature since Grad- CAM only localizes one small image region, e.g., bicycle front wheel. Differently, networks trained by FixMatch can often grab multiple features for some classes, e.g.. bicycle front and back wheels, but still misses some features for certain classes, e.g., bus compartment. By comparison, networks trained by SA-FixMaath reveals better semantic feature learning performance, since it often captures multiple semantic features, e.g., bicycle front and back wheels, bus front and compartment. The reason behind these phenomena is that as theoretically analyzed in Sec. 4.2, for classes which have multiple semantic features, SL. can only learn a single semantic feature, while FixMatch and Mathh are capable of learning all the semantic features via the two-phase (supervised and unsupervised) learning process. Moreover, as shown in Sec. 4.3, compared with FixMatch, SA-FixMatch can more effectively use unlabeled data as it better removes well-learned features for enforcing network to learn missed features in data. Thus, SA-FixMaath is more likely to capture all semantic features of the data in practice with fix number of unlabeled training data observed in Figure 2.
5.3 SA-CUTOUT ON FIXMATCH VARIANTS
SA-CutOut is compatible with other deep SSL methods, such as FlexMatch (Zhang et al., 2021a), FreeMatch (Wang et al., 2022b), Dash (Xu et al., 2021), and SoftMatch (Chen et al., 2023), since as discussed in Sec. 3.2, the main difference between these deep SSL methods and FixMatch is their choice of confidence threshold Te, Here we apply SA-CutOut to these algorithms and compare their test accuracies with the original methods on ST and CIFAR- 100 dataset. From Table 2, one can observe that on STL-10, application of SA-CutOut increases the test accuracies of FlexMatch and FreeMatch by 2.6%+ and the test accuracies of Dash and SoftMatch by 5.4%+ On CIFAR- 1000 SA- CutOut increases the test accuracies of Free and Dash by 0.65%+, SoftMatch and FlexMatch by 0.5%+. This validates our analysis in Sec. 4.3 that SA-CutOut can more effectively use unlabeled data to learn comprehensive semantic features and thereby achieve higher test accuracy.
5.4 ABLATION STUDY
Same Training Dataset We evaluate (SA-)FixMatce and SL under the same training dataset setting, as described in Sec. 4.3. As shown in Table 3, SA-Fix Match significantly outperforms SI, reaffirming

---

Published as a conference paper at ICLR 2025
Table 2: Comparison of Test accuracy (%) of SSL. algorithhs with CutOut and SA-CutOut STL.-10 with 40 labeled data and CIFAR-100 100 with 400 labeled data.
Dataset
STI-110
CIFAR- 100
Algorithm
FlexMarch
FrocMatch
Dash
SoftMatch
Flex
Froc
Dash
SoftMatch
CurOut
72.13 a: 5.66
75.29
1.29
67.51
1.47
78.55
a: 2,90
59.65
a 1.14
58.44
1.92
48.56
2.16
60.16 1: 2.22
SA-CuiOut
75.91
5.59
77.91
2.11
78.41
84.04
4.67
60.16
1.06
59.12
50.24
1882
60.69 1,95
Table 3: Comparison of Test Accuracy (%) using the
Table 4: Effect of (SA-)CutOut mask size test accuracy (%) on CIFAR-100 with 400 labeled data.
same training dataset for (SA-) FixMaach and SL.
Dataset
STL-10
CHFAR-10
ImageNet 100K
Data Amount
40
250
1000
400
2500
10000
Mask Size
4
8
12
16
SI.
19.93
44.06
67.29
9.87
40.98
63.48
41.82
FixMatch
38 38.88
64.70
79.15
18.58
47.20
67.94
43.34
FixMatch SA-FixMatch
48.65
50.11
53.48
55.21
SA-FixMatch
40.25
65.85
79.74
19.72
47.71
68.30
44.88
52.71
52.95
55.37
55.78
the superiority of SSL over SL and further validating our theoretical insights in See. 4.3, Moreover, SA-FixMatch surpasses FixMatch, demonstrating the effectiveness of our proposed method.
Maske Size Here we investigate the effect of the mask size in (SA-)CutOut on the performance of (SA-) FixMahh. For CIFAR-100 whose image size 32 32, we set the mask size (St-)CutOut as 4, 8, 12, and 16 to train the WRN-28-8 8 network. Table 4 shows that 1) as mask size grows, both the test accuracy of FixMatch and SA-FixMatch improves; 2) when mask size is small, SA-FixMatch makes significant improvement over FixMatch, e.g., 4%+ when using mask size of 4; 3) mask size grows, the improvement of SA-FixMatch over FixMatch becomes reduced, c.g., 0.55% when using mask size of 16. For 1). as mask size in (SA-)Cu(Out increases, the learned features in the image are more likely to be removed, which is the key for (SA-)FixMatch to learn comprehensive semantics in Phase II as analyzed in Sec. 4.2. This explains the better performance of Fix.attc and SA-FixMatch when their mask sizes increase. For 2), when using small masks, a random mask in CutOut has much lower probability remove learned features compared with SA-CutOut. Thus, SA-FixMatch has much better performance than FixMatch. For 3), as mask size grows, a random mask in CutOut also has large probability to mask learned features in the image. This explains the reduced gap between SA-FixMatch and FixMatch.
CONCLUSION
By examining the classical FixMatch, we first provide theoretical justifications for the superior test performance of SSL over SL on neural networks. Then uncover the differences in the feature learning processes between FixMatch and SL, explaining their distinct test performances. Inspired by theoretical insights, a practical enhancement called Sathi is proposed and validated through experiments, showcasing the potential for our newly developed theoretical understanding to inform improved SSL methodologies. Apart from FixMatch-likk SSL, there are also other effective SSL frameworks whose analyses and comparisons are left as our future work.
Limitations. (a) Apart from -ixMatc-llike SSLs, we did not analyze other SSL frameworks, like Mean Teacher (Tarvainen & Valpola, 2017) and MixMatch (Berthelot et al., 2019b). However, current SoTA deep SSLs like FlexMatch, FreeMatch, Dash, and SoftMatch all follow the FixMatch framework, indicating the generalizability of our theoretical analysis on them. See details in Sec. 3.2 and Appendix G. (b) Due to limited GPU resources, we use small datasets, egg. STL- 10 and CIFAR- 100, instead of large datasets like ImageNet to test SA-CurOut on other SoTA SSLs. Future work involves testing SA-CutOut on other SSLs methods (other than FixMatch) and on larger datasets.
ACKNOWLEDGMENT AND AUTHOR CONTRIBUTIONS
J. Pan and V. Y. F. Tan are supported by a Singapore Ministry of Education (MOE) AcRF Tier grant (A-8000423-00-44 -00-00). J. Li led the development of the theoretical framework, provided the rigorous proofs, and also led the experimental design and implementation. J. Pan contributed the initial sketch of the main proof. All authors discussed the results and contributed to the final manuscript.
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 977-988. IEEE, 2022. 2
Zeyuan Allen-Zhu and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self- distillation in deep learning. In The Eleventh International Conference on Learning Representations, 2023. 2, 4, 6, 15, 16, 17, 18, 19, 20, 21, 22, 23, 25, 26, 28, 30, 31, 32, 33, 34
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- suue-graind analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019. 4
Philip Bachman, Ouais Alsharif, and Doina Precup. Learning with pseudo-ensembles. Advances in neural information processing systems, 27, 2014. 2
David Berthelot, Nicholas Carlini, Fkin D Cubuk, Alex Kurakin, Kihyuk Sohn, Han Zhang, and Colin Raffel. Remixmatch: Semi-super learning with distribution alignment and augmentation anchoring. arXiv preprint arXiv: 2019a. 2
David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: A holistic approach to cumi-supervised learning. Advances in neural information
processing systems, 32, 2019b. 2, 10
Hao Chen, Ran Tao, Yue Fan, Yidong Wang, Jindong Wang, Bernt Schiele, Xing Xie, Bhiksha Raj. and Marios Savvides. Softmatch: Addressing the quantity-qualing trade-off in semi-supervised learning. arXiv preprint arXiv:2301.1092., 2023. 1, 2, 6, 8, 9, 32, 36
Adam Coates, Andrew Ng. and Honglak Lee. An analysis of angle-layer networks in unsupervised feature learning. Proceedings of the fourteenth international conference on artificial intelligence and statistics, pp. 215 223. JMLR Workshop and Conference Proceedings, 2011. 8
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pp. 702-703, 2020. 4, 16, 34
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 JEEE conference computer vision and pattern recognition, pp. 245-255. Icee, 2009.
Terrance Vries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv: 045522 2017. 4, 7, 16
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929) 2020.
Lan-Zhe Guo, Zhen Yu Zhang, Yuan Jiang, Yu-Feng Li, and Zhi-Hua Zhou. Safe deep semi- supervised learning for unseen-class unlabeled data. In International Conference Machine Learning, pp. 3897-3906. PMLR, 2020.
Haiyun He, Hanshu Yan, and Vincent YF Tan. Informatiin-thheortie characterization of the general- ization error for iterative cnn-suuere learning. The Journal of Machine Learning Research, 23(1):13041-13992 2022. 2,7
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 770-778, 2016. 1,
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840-6851, 2020.
11

---

Published as a conference paper at ICLR 2025
Jeremy Howard and Sylvain Gugger. Fastai: A layered api for deep learning. Information. 11(2):108. 2020. 8
Jungdae Kim. Pytorch implementation of fixmatch. httpp:://gituu..com wttp://..ccoookkkeooeeoooo. FixMatch-pytorra 2020. 36
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. arXiv preprint arXiv:1610.02242., 2016. 2
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. Advances in neural information processing systems, 30, 2017. 4
lyy Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts. arXiv preprint arXiv:1608.0339 2016. 36
Geoffrey J McLachlan. Iterative reclassification procedure for constructing an asymptotically optimal rule of allocation discriminant analysis. Journal of the American Statisticul Association, 70 (350):365-369, 1975.
Alexander Mey and Marco Loog. Improved generalization in semi-supervised learning: A survey of theoretical results. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45(4):
4747-4767, 2022.
Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng. Nerf: Representing scenes as neural radiance fields for view synthesis. Communications of the ACM, 65(1):99-11) 106, 2021.
Yassine Ouali, Céline Hudelot, and Myriam Tami, An overview of deep semi-supervised learning. arXiv preprint arXiv:2006.05278 2020.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35: 27730-27744 2022. 1
Jiachun Pan, Pan Zhou, and Shuicheng Yan. Towards understanding why mask reontttconttt pretraining helps in downstream tasks. arXiv preprint arXiv:2206.03882 2022. 1
Sungrae Park, JunKeon Park, Su-Jin Shin, and Il-Chul Moon. Adversarial dropout for supervised and superviue learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018. 2
Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. Improving language understanding by generative pre-training. 2018.
Philippe Rigollet. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(7), 2007. 2,
Mehdi Sajjadi, Mehran Javanmardi, and Tolga Tasdizen. Regularization with stochastic transfor- mations and perturbations for deep semi-supervised learning. Advances in neural information processing systems, 29, 2016.
Timo Schick, Jane Dwivedi- Yu, Roberto Dessi, Roberta Raileanu, Maria Lomeli, Luke Zettlemoyer, Nicola Cancedda, and Thomas Scialom. Toolformer: Language models can teach themselves to use tools. arXiv preprint arXiv:23322.04761, 2023. 1,4
Hugo Schmutz, Olivier Humbert, and Biere-AAlexane Mattei. Don't fear the unlabelled: safe semi-supervised learning via debiasing. In The Eleventh International Conference on Learning Representations, 2022.
Henry Scudder. Probability of error of some adaptive pattemn-recognition machines. IEEE Transac- fions Information Theory, 11(3):63-371, 1965.
12

---

Published as a conference paper at ICLR 2025
Ramprasaath R Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-baseed localiza- tion. In Proceedings of the IEEE international conference on computer vision. pp. 618-626, 2017.
3, 7,9
Aarti Singh, Robert Nowak, and Jenry Zhu. Unlabeled data: Now it helps, now it doesn't tt. Advances in neural information processing systems, 21, 2008. 2, 7
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Do- gus Cubuk, Alexey Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi cemi-supervised learning with consistency and confidence. Advances neural information processing systems, 33:596-608 2020. 1, 2, 4, 5, 6, 8, 34, 36
lya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initialization and momentum in deep learning. In International conference on machine learning, pp. 1139-1147.
PMLR, 2013. 36
Antti Tarvainen and Harri Valpola. Mean teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results. Advances in neural information processing systems, 30, 2017. 10
Alexandru Tifrea, Gizem Yüce, Amartya Sanyal, and Fanny Yang. Can semi-supervised learning use all the data effectively? a lower bound perspective. arXiv preprint 188557, 2023. 2,
Jesper E Van Engelen and Holger H Hoos. A survey semi-supervised learning. Machine learning, 109(2):373-444) 4400 2020. 2.7
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Yidong Wang, Hao Chen, Yue Fan, Wang Sun, Ran Tao, Wenxin Hou, Renjie Wang. Linyi Yang. Zhi Zhou, Lan-Zhe Guo, Heli Qi, Zhen Wu, Yu-Feng Li, Satoshi Nakamura, Wei Ye, Marios Savvides, Bhiksha Raj, Takahiro Shinozaki, Bernt Schiele, Jindong Wang, Xing Xie, and Yue Zhang. Usb: A unified semi-supervised learning benchmark for classification. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022a. doi: 0044850/ARXIV.2208.007 072204. URL https: / /aaxivi.vv/.../////// org/ abs 2208 07204. 8, 36
Yidong Wang, Hao Chen, Qiang Heng, Wenxin Hou, Yue Fan, Zhen Wu, Jindong Wang. Marios Savvides, Takahiro Shinozaki, Bhiksha Raj, et al. Freematch: Self-adaptive thresholding for semi-supervised learning. arXiv preprini arXiv:205.007246, 2022b. 1. 4, 6, 32, 36
Colin Wei, Kendrick Shen, Yining Chen, and Tengyu Ma. Theoretical analysis of self-training with deep networks on unlabeled data. arXiv preprint arXiv:2010.03622 2020. 2
Zixin Wen and Yuanzhi Li. Toward understanding the feature learning process of self superviud contrastive leaming. In International Conference on Machine Learning, pp. 11112-11122. PMLR,
2021. 2
Zixin Wen and Yuanzhi Li. The mechanism of prediction head in non-contrastive self-supervised learning. Advances in Neural Information Processing Systems, 35:24794-24809, 2022. 2
Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoc Le. Unsupervised data augmentation for consistency training. Advances in neural information processing systems, 33:6256-6268, 2020. 2
Yi Xu, Lei Shang, Jinxing Ye, Qi Qian, Yu-Feng Li, Baigui Sun, Hao Li, and Rong Jin. Dash: Semi-supervised learning with dynamic thresholding. In International Conference on Machine Learning, pp. 11525-11536. PMLR, 2021. 1, 2, 5, 6, 8, 9, 32, 36
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. arXiv preprint 1rXiv:1605.07111 2016. 8
13

---

Published as a conference paper at ICLR 2025
Bowen Zhang, Yidong Wang. Wenxin Hou, Hao Wu, Jindong Wang. Manabu Okumura, and Takahiro Shinozaki. Flexmatch: Boosting seni-supervised learning with curriculum pseudo labeling. Advances in Neural Information Processing Systems, 1848888888449, 2021a. 32, 36
1, 4, 5, 9,
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communicattonn of the ACM, 64(3):107-115, 2021b.
Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Time-consistent self-supervision for semi-supervised learning. In International Conference on Machine Learning, pp. 11523-11533, PMLR, 2020. 1,
14

---

Published as a conference paper at ICLR 2025
A THEOREM STATEMENT
In this section, we formally state the relevant data assumptions and theorems. Building on the proof framework of Allen-Zhu & Li (2023), our results extend their findings from supervised learning (SL) to semi-supervised learning (SSL). To maintain consistency, we adopt their notation throughout our proof. Specifically, we follow their data distribution assumptions and extend their analysis from SL to SSL. through a two-phase learning process.
To formally define the data distribution, we set global constant Cp. sparsity parameter polylog(k). feature noise parameter
poly(R). and random noise parameter op Va (olylog(4) to control noises in data. Here, feature noise implies that a sample from class i primarily exhibits feature Ven (with E [2]). but also includes minor scaled features Vj,r (with j o i) from other classes. Each sample pair (X, y) consists of the sample X. which is comprised of a set of P = k² patches {or E RR ) and y E [k] as the class label. The following describes the data generation process.
Definition 7 (data distributions for single-view DD and multi-view data Din (Allen-Zhu & Li, 2023)). Data distribution DD consists of data from multi-view data Dnn with probability 1 1- ps and from 1/poly (k)) We define (X,y) v> by randomly uniformly selecting label y [k] and generating data X as follows.
single-view data DD with probability
1) Sample a set of noisy features V uniformly at random from (ui, Vi,2) each with probability 8/k.
2) Denote V(X)= = U (Uy,1, as the set of feature vectors used in data X.
3) For each E VXX,, pick Cp disjoint patches in [P] and denote it as (x(X) (the distribution of these patches can be arbitrary). We denote P(X) = (eevxx)P(())
4) If DD is the single-view distribution, pick value i(X) [2] uniformly at random.
5) For each E Px(X) for some v E <VX)), given feature noise Otppo E [0,7]. we set
Tp z, + Ever "p + +Ep:
where & E NO Ii is an independent random Gaussian noise. The coefficients 2p 2 0 satisfy
- For "multi-view" data (X,y) v) E Di. when v E (,,2), Eper, E [1))
and EpEP.(X) 23 E [1,0 for integer q 2 3, and the marginal distribution of Epep,(x) Zp is left-llose. When V(X) (V vy.2), EpER.(X) Ep [9(1), 0.4). and the marginal distribution of EpEp,(x) &p is right-close.
For "single-view" data (X, E D., when = yn ExER,(x) 2p E [1, [1)) the integer q 2 3. When v = yy E EpEP.(X) 2p Op)] (we set p 00001 for simplicity). When v E V(X) \ (2,,1, 12y2)). EpER.(X) 2p E []) where r 1/polylog(k), and the marginal distribution of Epep. 2p is right-close.
6) For each p [PI(P(X), with an independent random Gaussian noise &p ~(0, 2k? I).
Ip = -' appp + Ep-
where each ap.. E [0, 7 is the feature noise.
Based on the definition of data distribution D, we define the training dataset Z follows.
Definition 8. Assume the distribution D consists of samples from Dm w.p. 1- a and from D. w.p.
μ. We are given N, labeled training samples and N., unlabeled training samples from D, where typically N₂ > N₁. The training dataset is denoted as Z = Z1,m U Zi, U Zu,m U Zu,s, where Zt, and Zi, represent the multi-view and single-view labeled data, respectively, and Zum and Z represent the view and view unlabeled data, respectively. We denote (X, v) ~ Z as a pair (X, y)) sampled uniformly at random from the empirical training dataset 2.
15

---

Published as a conference paper at ICLR 2025
Then, we introduce the smoothed ReLU function ReLU (Allen-Zhh Zhu & Li, 2023) in detail: for an integer 2 3 and a threshold _ = polylog(R) (2) = = < 0, Re)
(o0e 1
2 E [0, e] and ReLU(z) - - (1 4 if = 2 e. This configuration ensures a linear relationship for large 2 values while significantly reducing the impact of oo-maanitude noises for small values, thereby enhancing the separation of true features from noises.
We also introduce our assumption on FixMatch's 's strong augmentation A(-), which is composed by CutOut VDeVries & Taylor, 2017) and Rundent (Cubuk et al., 2020). As discussed in Sec. 3.2 and Appendix K.1, we focus on its probabilistic feature removal effect.
Assumption 9. Suppose that for given image, strong augmentation A(-) randomly removes its semantic patches and noisy patches with probabilities TT and 1 -T2, respectively. For single-view image, the sole semantic feature is removed with probability T2. For a multi-view image, either of the two features, V1,1 or U22, is removed with probabilities Ti Ri and (1 TT TT2, respectively. We define the strong augmentation A(-) for multi-view data as follows: for p E (P).
max <2)
if Vyy1 is in the patch Fp- Vy in the patch Tp: max (1 e1, 52)
A(xp)
(10)
(1 (1--62) =2)
otherwise (noisy patch),
where 61 and 62 are independent Bernoulli random variables, each equal to 0 with probabilities T and T2, respectively.
Here we use the "max" function to ensure is active when = O. which implies that A(-) selects one feature to remove at time. The reason behind this assumption is that as we can observe from Figure 1 and 2, different semantic features in a multi-view image are spatially distinct. Consequently, the likelihood of a square patch from random CutOut and transformations from RandAugment to remove both features is substantially lower than removing just one. To simplify analysis, we therefore assume that A(-) targets a single feature for removal in each instance.
theoretical
Then we introduce the parameter assumption necessary to the proof. As we follow the proof framework of Allen-Zhu & Li (2023), the assumptions on most of the parameters are similar.
Parameter Assumption 10. We assume that
q 423 3 and o 2 1/k, where do gives the initialization magnitude.
7 s (())) and 78 (( where y controls the feature noise.
The size of single-view labeled training data Nt., = =o(k/p) and Ni,s S 122 10011
Ni 2 Nr., (k)y(k), r/T 2 Ni- poly(k)), and vd 2 r/I'i poly(k).
The weight for unsupervised loss X 1 and the confidence threshold 1-
The number of unlabeled data for FixMatch Nu 2 1/122 poly(k) with n/T's 2 poly(k), and the ratio of single-view unlabeled data Nu. < k2a
NN 7575
Here the first four parameter assumptions are followed from Allen-Zhu & Li (2023) for supervised learning Phase and the last two parameter assumptions are specific to the unsupervised loss Eq. (5)
in learning Phase II. Define (1) : Ere(m) [m]] [m [ v,,)) and of()) : ΣiE & (1) We have the fil
following theorem for vanilla FixMatch under CutOut:
Theorem 11 (Peformance on FixMatch). For sufficiently large k > forevery every polylog(k), 1 S (R) setting T = Ti T2 with Ti poly(k) and T2 poly(k) when Parameter Assumption 10 satisfied, with probability at least 1 - Allgg2 k).
(training accuracy is perfect) for every (X,y) E Z:
Vi # y: (X) 2 F. (X) + 2(log k).
16

---

Published as a conference paper at ICLR 2025
(mulli-view testing is good) for every i,j [k], we have Õ(1) 2 0/ 0 and thus
+ +S2(log
Pr
(X)
2 max F3 (X) + Dilog k:) 2 R(ing 3 k).
(X.
jfy
(single-view testing is good) for every i E [k] and E [2], we have b 2 (log k), and thus
Pr (X,y)ED,
F FX)
2 max ( (X) ((lgg)) 2 21-6 -St[lo k). jzy
For Semantic-Aware FixMatch (SA-Fix.Mas Fi-FFixaatch), we denote the number of unlabeled data in this case as No. Then we have the following assumption on No.
Parameter Assumption 12. No max ( 22, (1 m ) No.
Here T1 E (0, 1) and T2 E (0, 1) are the probabilities defined Assumption 9, where T2 is typically small (1/pol((k)) as explained in Appendix H. From Parameter Assumption 12, we observe that the requirement for the number of unlabeled samples SA-FixMatch is significantly smaller compared to that in FixMatch.
Under Parameter Assumptions 10 and 12, SA-FixMatch achieves the same performance results as Theorem 11, but with reduced requirement for the number of unlabeled data, decreasing from N, to No. Thus, we state the following theorem regarding the performance of SA-FixMatch.
Theorem 13 (Performance SA-FixMatch). Under Parameter Assumption 10 and 12, SA-FixMatch can achieve the same training and test performance as FixMatch in Theorem 11.
Our main proof of Theorem 11 and Theorem 13 for FixMatch and SA-FixMatch includes analyses on two-phase learning process. In Phase I, the network relies primarily the supervised loss due to its inability to generate highly confident pseudo-labels and the large confidence threshold 7 in Eq. (5). According to the results in Allen-Zhu & Li (2023), partial features are learned during the supervised learning Phase I. We review the results on supervised training in Appendix B.
Then in Phase II, the network predicts highly confident pseudo-labels for weakly-augment augmented samples and uses these correct pscudo-labels to supervise the corresponding consistency regularization. To theoretically analyze the learning process in Phase II, build on the proof framework of Allen-Zitt & Li (2023) and demonstrate how the network learns the unlearned features while preserving the learned features during Phase II. Specifically, we present the induction hypothesis for Phase in Appendix C, along with gradient calculations and function approximations for the unsupervised loss Eq. (5) Appendix in Appendix E and extend the results to FixMatch in Appendix F. Finally, we generalize our proof to other FixMatch-like like SSL methods in Appendix G.
-augenee samples via
We then provide a detailed proof of SAtFixMatch
B RESULTS ON SUPERVISED LEARNING
In this section, first recall the results in SL that were derived in Allen-Zhu & Li (2023). Before showing their main results, we first introduce some necessary notations. For every E [k], define (t)
Ereimi wx,))++ and क Eiera) (f)
P.. Define
A re(m),1e(2)
Kw!? ex1i)+ and 1 max relm
(w +;,))++
where Arr indicates the largest correlation between the feature vector Uay and neurons wir (r E [m]) from class i. Then we define the "view lottery winning" set:
M M (1,11) E [K] x A 2 10
2
log2 m
The intuition behind M is that, subject to model initialization, if (i, 1) -,, then the feature i.r will be learned by the model during supervised learning process and the feature V,,-1 will be missed. The set M satisfies the following property (refer to the Proposition C.2. of Allen-Zhu & Li (2023)):
17

---

Published as a conference paper at ICLR 2025
Proposition 14. Suppose I poly(k). For every E [k], Pr((i, E Mor (1,2) M] 2 (1)
Based on Theorem I of Allen-Zhu & Li (2023), after training for T' iterations with the supervised training loss I_ B(x,)>z |- log logit, (F(t, x)] the training accuracy on labeled samples is perfect and La (T) approaches zero, i.e., for every (X, y) Z,.
Vi vi (X) 2 F. (x) + 2llog k),
and we have T I poly(k)- Besides, it satisfies that 0.4 (7)
8) Σ 2(oog k) for every pair 2,2 for all i [ki] increase to a large scale of
j E [k]. This means that at least one of (T) or Φ (T) (log(k))) which means at least of v1 and 222 for all i [k] is learned after supervised training for I' iterations. Thus, all multi-view training data are classified correctly. For single-view training data without the learned features, they classified correctly by memorizing the noises in the data during the supervised training process. Then for the test accuracy, for the multi-view data point
(X, 3) Dm, with the probability at least 1 - e -2(lo 8), it has
logit, (F 2 2 x3
and
Pr (X.
(X)
max ( (X) 2(log 2 1- -Ailog" k)
jFy
This means that the test accuracy of multi-view data is good. However, for the single-view data (X, ~ D., whenever (i,1*) E EM, we have (
polylog(E] and
Pr (X.
F (X)
2 max (0 (X) 379
1
+1+
$ 1
polylog(k)]
which means that the test accuracy single-view data is nearly 50%.
The results in Allen-Zhu & Li (2023) fully indicate the feature learning process of SL. The main reason for the imperfect performance of SL is that, due to "lottery winning", it only captures one of the two semantic features for each class during the supervised training process. Therefore, for single-view data without this feature, it has low test accuracy.
In the following, we will consider the effect of loss _ on unlabeled data for training:
T Ex [mmax; (1)) log logit,(FF'
(FX)),(X))) .A(X))]
where = arg max logit, (F (). F is the confidence threshold and a, A are the weak and strong augmentations, respectively. For the simplicity of proof, we set be identity mapping. In the following, will prove Theorem 11. By setting the supervised network F(G) with the unsupervised loss _ for an additional T2 = poly(k) epochs,
1 (1//²),. we will show that after training
the FixMatch-trained network F(T) learns complete semantic features for all classes, achieving perfect test performance on both multi-view and single-view data.
C INDUCTION HYPOTHESIS
In this section, to prove our theorem, similar to Allen-Zhu & Li (2023), we present an induction hypothesis for every training iteration in Phase II. We first show the loss function in Phase II.
F,00)
Loss Function. Recall (F,X)
Eyenye e 5505- In learning Phase I, before the network
learned partial features to make confident prediction, only the supervised loss (((h) takes effect
| log logit, (F(0), .x)]
L
E E(x,))=
18

---

Published as a conference paper at ICLR 2025
In Phase II, after we train the network F for Ti poly(k) epochs using L in the Phase I, according to the results in Appendix B, one of the features in each class is captured. Then we consider to optimize the network F(T1) using the following combination of losses:
[ -E(x,)~2;
| log logit, (F(1), x)]
+ AEx=2, [[maxx logit, ((X))2r) ((())) - log logit, (F()) A((1))] (F())
where b = arg maX (Fl),,(Fl)),, (x))) Recall 1- Ó(11/²)), when 2 Ti and we use F(() to classify the unlabeled data X ~ Zu. we will get a correct pseudo-label with high probability. i.c. b = y. where y denotes the ground truth label of X. This means that for X Zu,ms with probability
at least 1 - -Q(ls" k) llogii,, (4((1) .X) 2 T and for X ~ Zu.e. when (y. (*) E M and i(X) 1", 2 T. We denote the samples in Zu that satisfy logit, (F(1) X) 2 as Z, and let No Zu/ In this way, further simplify the loss as
with the probability at least e -Atlogg k), logit, logit,((E
( - + AL
(11)
-E(x,))~2 [ log logit, (F x)] (F))
| logit, (F(), A(X)) ((()))
+ AE xx
We introduce the following induction hypothesis:
Induction Hypothesis 15. During Phase II (t 2 Tı). for every E for every r E [m], for every
X E En and i E [A:]
(a) For every p E Pu,y( we have: ( = (wif un)) + o(oo).
(b) For every P(X) \ (Pe,, UP),P (X)), we have: (w 2p)l S Ō(oo).
(c) For every p (P) (PX),, we have (w/ ap)l s Ö(oork).
Moreover, we have for every [k), every 2).
(d) ( 2 ((oo) and ( < Ô(1)
(e) for every E [m], it holds that (w v2.)) 2 -((a))
Recall that $10 = Eru +1,i and ( = Eie(2) (1))
The intuition behind Induction Hypothesis 15 is that training with semi-supervised loss Eq. (11) filters out feature noises and background noises for both multi-view data and single-view data. This can be seen in comparison with Induction Hypothesis C.3 of Allen-Zhu & Li (2023). With the help of Induction Hypothesis 15, we can prove that the correlations between W/sr and learned features in Phase I are retained in Phase II, and the correlations between Wirr and unlearned features will increase to a large scale (log(k)) in the end of learning Phase II.
D GRADIENT CALCULATIONS AND FUNCTION APPROXIMATION
Gradient Calculation. We present the gradient calculations for the cross-entropy loss (F;F), -og logit, (F, A(X)) on unlabeled data X with correctly predicted pseudo-label With slight abuse of notation, we use (X, v) ~ Ż., to denote unlabeled data X ~ 2,, along with its corresponding ground truth label y.
19

---

Published as a conference paper at ICLR 2025
Fact 16. Given data point (X, y) ~ Zu. for every E [k], [m].
V way Lea (F; X, v) = (1 - logit, (F,A(X)))
Σ
ReLU ((z)):
when i = y,
pE[M
(12)
-V Lur,,LaFF: v) logit,
Σ
ReLU ((ur,,
when + y.
PE[P]
(13)
Definition 17. For each data point X, we define value (X) as
Vir,(X) EV()))
Σ
ReLU ((w,,, A(zz)))A(zp))
PEPuta (X)
Definition 18. We also define small error terms which will be frequently used:
E = 0 )7s
(x),(()) = (V, + 2 (X)))
& : ((0onk)*~1
(X) 0 (ey)))())
Then we have the following bounds for positive gradients, i.e., when i y: Claim 19 (positive gradients). Suppose Induction Hypothesis 15 holds at iteration t. For every (X, 3) E 2n, every E [m], every E [2]. and = y, we have
(a) L. X, y), vx.) 2 ( logit (F A(X)))
(b) (-V (.((0 X, X.v), v.)) S (X) + & + &2) (1 logit, (F(1) ((X))
(c) For every E [k] \ {i),
Lo (F X, (). 2ل,ر & (E1 + (X) + Es + (X), (1 (1- (F())(())
We also have the following claim about the negative gradients (i.e., i y). The proof of positive and negative gradients is identical to the proof in Allen-Zhu & Li (2023), except that in our case, we have the augmentation operations on the data patches.
Claim 20 (negative gradients). Suppose Induction Hypothesis 15 holds at iteration I. For every (X,9) E.,. every E [m)) every 1 [2], and i E [k] \ {v), we have
(a) (-V Lu (1((((); X, y), v..) 2 -logit, (F(O),(X)) (E, + + Vinn(X)).
(b) For every j E [k]: (-V wer (F()) X. v), 15,)) < logit, (F(1), A(x)))((o,P))
(c) For every j. llogit, A(X)), + &g
E
[k]
(i):(VV wt, (F(1), X. v), vz,))
(X).
Function Approximation. Let us denote (x) = Evx() (Epep (X) A(zp)) we can casily derive the following result on function approximation.
Claim 21 (function approximation). Suppose Induction Hypothesis 15 holds at iteration & and and S Ö ((p7 we have:
suppose < Ō mmm!
for every I, every (X, v) E 2, and i E [k), we have
(1) (x)) 0 polylog(k)
SE(2]
for every (X, D, with probability least Aillog k), it satisfies for every i [k].
(x) = Σ ( 2.1 + O polylog(k))
12
20

---

Published as a conference paper at ICLR 2025
Claim 22 (classification test performance). Suppose Parameter Assumption 10 holds. Assume for Vi E [I E [2] such that D.,1 2 Siloo k) and 21,3-1 S polylog(k) in the trained network F. Then the following statements hold with probability at least - e ---llo'' k);
For any (X,y) ~ D which contains Vy as the main semantic feature, network can correctly predict the label y of X.
For any (X.y) .) DD only with 3-t as the main semantic feature, the network F would mistakenly predict the label of X.
Proof. Based on our definition of multi-view and single-view data, for any multi-view data (X, y)
Dm, when we have D; 2 Sl(log k) (Vi [k]), according to Claim 21 and Claim D.16 in Allen-Zhu & Li (2023), we have 0.44; 43 I (1oo k), which means (X) maxjøy (X) + 22 k). For any single-view data (X, y) ~ DD with By. as the main semantic feature, according to Claim 21, (X) 2 Milog k) and for & y. (X(X < O(T). Thus, we have (X) Z maxi (X) Qllog k). In the above two cases, the network F can correctly predict the label of X.
For any single-view data (X,y) ~ D with U9,3-1 as the main semantic feature, according to Claim 21, (X) S O(p) + polylog(k) and with probability at least 1 - e -((lo k) there exists i E [k]] and i o such that Fi(X): 2 Q(T). This means that (X) I maxişy Fx(X) (olylog(A) In this case, the network F will mistakenly predict the label of X.
1
E PROOF FOR SEMANTIC- AWARE FIXMATCH
Here we consider to prove the SA-FixMatch case first. SA-FixMatch replaces CutOut operation in strong augmentation of FixMatch with SA-CutOus which deterministically removes the learned features in Phase I. This helps to reduce the number of unlabeled samples needed during the Phase II training as shown in Assumption 12. Since the learned features of Phase I are deterministically removed in SA-FixMatch, for the simplicity of theoretical analysis, we first prove the results under easily generalize the results to FixMatch.
SA-FixMatte and then
For theoretical proof, we assume that Grad-CAM in SA-CutOut can correctly identify the learned feature after the first stage. In this case, the formulation of strong augmentation A(-) with SA-CutOut for X ~ Z,, and (), E M N V(X) (1* varies depending i) is
A(x,) = f0,
if E Pu... (X), otherwise.
(14)
(ppr
In the following, we will begin prove Theorem 13. We first introduce some useful claims as consequences of the Induction Hypothesis 15.
E.1 USEFUL CLAIMS
Based on the results from Allen Zhu & Li (2023), at the end of learning Phase I, for (i,1*) E M. //3 S 1/polylog(k). Below the first claim addresses the initial growth of the correlations between W,,r and the unlearned feature ($ (b{2 in learning Phase II, (.- are preserved during learning Phase II. Here we first give naive bound on the logit function based on function approximation result Claim 21.
we have $ 2,1- 2 (log k) while o (2h)
and the second claim asserts that the correlations between wi,r and the learned feature (1
Claim 23 (approximation of logits). Suppose Induction Hypothesis 15 holds at iteration t, and suppose < O ogm (g and - O (oM(mp)1a) then
for every (X,y) Zu,m and (1,1*) E M: (F(), =0 .6
for every (X, y) En,s and every [k)] logit, (F(1) A(X)) = =t)).
21

---

Published as a conference paper at ICLR 2025
Proof. Recall F. (A(X) Erefm) Eperry ((w,( According Claim 21, data distribution Def. 7 and data augmentation defined in Eq. (14), we have that for (X; y) Zu,m and (i,1*) E M (I" varies depending on i),
0 M F (A())) & (0) 1,3-1" 0(1) O
polylog(k)
and for i E [k] (v).
0 (A(X)) S 2 i,3-1- 0.4 0
polylog(k)) )
Thus, combining the above results, for every (X,y) 2,,m and (i,, (M) E M, we have for every i [k)]
logit, (F A(X)) (FOO, =0
0
+
On the other hand, for the single-view data Zu.s, as the only class-specific semantic feature is removed after we conduct strong augmentation, only noisy unlearned features and background noises remain. Thus, for (X, v) Zu,e and (i,1") E M, we have for i * y.
S (A(X)) = O(1) and 0 (A(X)) S (t) 1-3-1- O(T) + O polylog(k) s 0()),
and thus we have for every E [k].
(F!o, 0 (1)
Now we are ready to prove the following claim on the initial growth of (1 1,3-1- with (i,1*) E M.
Claim 24 (initial growth). Suppose Induction Hypothesis 15 holds at iteration t, then for every i [k]] with (i,1*) E M, suppose (t) < O1)), then it satisfies
1-3-1-
(++)) = (t) 1,3-1- + θ (7) 3-1
ReLU (4 (.3-.))
Proof. For any wir and 1- (i E [k], E [m]), we have (++1)
(w (..-))) = (w, / 11,3-1-) 1/E (X. wi, (2((0) (),),, 0(3-1)]
(t)
y) - -1) (( wi, Le (x)) v(,--1))]
For the loss term on Z,, we have
E(x,)) ((V w.,- (F(1)) v,,)),,,3-11 11,3-1)>]
= -E(x,)~2 Ti=y logit, ( (F, X)) Σ PE(P) ReLU --3))
Logylogit, (F, Σ
ReLU (w Tp) (2rp) (1,3-r))
pE(P)
Based on the results from Allen Li (2023), when Ti, we have
((x,))22 [11 logit, y (F, X))]
and Exx,02 [Tty logit, S pk)y(k))
poly(k)
which means
- E(x,)) VV,,, LF() v). 01,3-1-)1 (kly
ie.. the supervised loss is fully minimized in Phase and contributes little in Phase II.
22

---

Published as a conference paper at ICLR 2025
Then, from Claim 19 and Claim 20, we know (++1) (Wir (1,3-1)) 2 i 01,3-1) (x.)) (0- (((,, P))(1 logit,(F%) (F
(t)
1y + E3 Ue, (P(() 1- (X))logit, (X))oo(()))) A(X))]
Consider r = arg [| ( (w (1) f1,3- then as m pklylog(k), we know (w 11,3-1))
( Recall V1,,,3-1- 1- (X) = -v.a-r)((x) EpeP (x) ReI.U ((w) (1) A(xp)) A((p))
according to Induction Hypothesis 15(a) and definition in Eq. (14), we have
(X) = leee (V)(
Σ
ReLU ((w 01.-11)22 2(
Pe P (X)
When = y, at least for (X, ~ Zu.m. we have EpePera (x) (x)
2 1, and together
with |Pr,.-u. & Cp. we know V1,13-1- 2 2(1) ReLU ((w) 2,r (1,3-1-)).
When * y and when 01,3-1 E P(X), we can use Σ a (X) 2p S 0.4 to derive that
Vo,,3-1- S 0.4 ReLU ((wf) 01,3-1)).
Moreover, when $ (1) 1-3-1- S O(1), by Claim 23, have logit, (F(9,, S OO.) Then derive that
Lyzti Inpii EP(X) (w 11,3-11) 2 v4,1) + nB (x F/y= -
(w(+()
ReLU (wif (-) , ppp E
k:
Finally, recall that Pr(vi,s-r E P(X) + y) < [(]),, we have that
( (1,3-1)) 2 (w ( ,1,--1-) + 52 (7) ReLU (wwf) v.3-1-)).
Similarly, using Claim 19 and 20, can derive:
(wer (..--r) S (w v1,3--) ( 2 (X) E & (f(0, X))
(++1)
OoytoO(o,PP)oiitt, (F(1) .)]]
With similar analyses to the upper bound, we can derive the lower bound
(1o((t)) 01,3-1)) I (w! 11,3-1-) + + (7) ReLU (1w/)) (1,3-1))-
With initial growth analysis in Claim 24, similar to Claim D.11 in Allen-Zhi & (2023), we can obtain the following result:
Claim 25. Define iteration threshold To : θ ( = then for every i E (1, E M and
t t2 Ti + To. it satisfies that D 4/1 = (11)
As we stated in Claim 23, model prediction for the augmented single-view data in Z are kept to the scale of O (t), since after strong augmentation there remains only noises. Now we present the convergence of multi-view data in E,,m from Ti + To till the end.
Claim 26 (multi-view error till the end). Suppose that the Induction Hypothesis 15 holds for every N.. N. t² then S nsT2'
iteration Ti < Ti T2, and suppose
TL Σ
k 7
E
((x,)) [1 logit, Dogit,,(F' (FX0)A(X)) So
+T
23

---

Published as a conference paper at ICLR 2025
Proof. For any war and 11,3-1" (i E [k], r [m]), we have
(mr(r) (1+1) , ((3-1-) = (w 11,3-1 1y (x)) wx, (F(1) X, v), (x3---)]
- (X,)), (V Lu (F ;X, y). 01)3-1))]
For the loss term 2,, as discussed above, we have
(VV.)) (. poly(A)
Again, by Claim 19 and Claim 20, we know (1+1) (w , (1,-11) 2 ( f,r, 01,3-1-) + (, - -(a,) P))(1 logit,
Iyvi(Ei + E3 + lea EP(( :x (X))logit, A(X))]
Take = arg m|m] / (w )1,--)),, then by m = polylog(k) we know (w 01,3-1) 2
(( 1,3-1-) = (1) for 2 Ti + Tb-
Recall V1,,,31--X) (X) == - Eperon (x) ReLU ((x))).(2p)) A(zp))) A((p) and our defini-
tion of A, using the Induction Hypothesis 15, we have that for (X, y) 2u,m: satisfies
V1r,3-1 1- (X) Σ EpEPo,. .,, (X) RcLU ((w 013-1) =(0)))
Since we have (w/ )1,-rr) 2 2(1) >> e and PPu.a- (X)l S (1)), for most of p E P Peiaa- we have alreadly in the linear regime of ReLU so
0.9 Σ PEP PEP (x) 2p S Vin3-1 (X) S E
DEP pEP (X) =p.
Thus, when v) ~ Zu,m and y = i, we have V (X)= 2 0.9; when (X, ~ Zu,mi y # i
and V1.3-1- E P(X), we have Vx,r,3---(X) S 0.4. When (X,y) ~ En.o and y i, we have Vi 2 O; when (X,y) ~ Lu y F i and 11,3-1 E P(X), we have Vx.1,-1-(X)) S O(I)) < ((1). Then we can derive that (wir (tttt)) ,013-11))
2 (w 04,3 01,3-1)) ).) (x.)))) [0.89 1-= - logit, (1:11) A(X)))] (((x))
(t)
T (x,)) v) B... [U + + + 0.4T, - logit, (F(1) A(X))]
NN.e
B B(x.))=2n, P)T=p logit, (1) (F(),(()))))
No
NNo,s
E B(x.)) [Toti(E + Es +
A(X))
No
(1) E ((x,))=eem [a- logit, (F()) 0 n) Nas
2 (w))) 01,3 +
A(())))
1:2 N.
where the last step is based on Claim 23 and the fact that Pr(vc, E P(X) + y) = 1/2 < o(1). Thus, when summing up all (m)) and telescoping from Ti + To to Ti T2, have
Ti+Ta
TensNe. k2N.
(T++Ta) 13--1
(Ti+To) 1-3-1
á
Σ
E ((.,))
[a-
logit, (Fgit,,(F') A(X))))
T=Ti+T
Then combining that (1)
2.3-1- < Ö(1) from the Induction Hypothesis 15(d), we have:
Ti T+TTB
Σ
E ((x.))=m..
A(()))]
kk ( +0 Nass
S0 k
ANo
IT+
24

---

Published as a conference paper at ICLR 2025
Now are ready to prove the following claim the correlations between model kernels and the learned feature ( retained during learning Phase II.
Claim 27 (learned is retained), Suppose that the Induction Hypothesis 15 holds for every iteration T < $ Tı + T2, under Parameter Assumption 10 and 12, we have for every iteration Ti t S
T + T2:
v(i,t") EM,
2 2 (loog(k)).
Proof. For any wa,r and ViLt- (i E [k],r [m]), have
((+1) (u vgr-) (wirr 0/11) (V., v) v1
(1)
nyI (x,))~ (V wes Lu (F(t;; U),)),
For the loss term on 21, as discussed in Claim 24, we have
1
Exx,))~ m.,, L. x,v),, s
poly(k))
Again, by Claim 19 and Claim 20, we know
(++1) (wir (urr)) 2 (w0 var-) + (x) Po ( (1) - logit, (F A(X)))
((X))
1y + E3 + Iu. Vini (X))logit, (((
Recall Vi (X) = (v,x))(()) EpEr y (x) ReLU ((w A(x))) and our definition of
strong augmentation in Eq. (14), we have Vina (X) = 0, so we have by Claim 23 that
(w (w((+)), .x11)) 2 v..))) δ (
(
E (X,,), [1 logit logit,(F'), [(X))] o (n(Ei + &x) )
-
k
Summing up all E [m] and using m = polylog(k), we have
(++1) 1. 1.1 24 (1-1) n0p k E E(x,)) logit, ( (FX)) - |ml63 s (oo7k))-1P)
In the following, we separate the process into Ti < < Ti To and 1 2 Ti + To-
When Ti <1 S Ti + To. Recall at the end learning Phase we have " (Ti) > ((log(k)). Using
To = θ
k 7 and our Parameter Assumption 10, we have & (t) 1.1- 2 [(log(k)) for every iteration
no
of Ti t $ Ti + To-
When Ti Too < <tSTi+7, By the upper bound on multi-view error Claim 26, we know (t) 1.1 2 ((log(k)) for every iteration of Ti + To < t < T, + T2.
Next, we present our last claim on individual error similar to Claim D.16 in Allen-Zhu & Li (2023). states that when training error on Zu,m is small enough, the model has high probability to correctly classify any individual data.
Claim 28 (individual error). When E ((..)) [1 logit, (F(), s t is sufficiently small, we have for any (i, 3 - l), (j.3 1') $ M,
0.44 1-1 j.3-r' S (A())()))
(!) (c)
1.3-1: -. 2 2((log(k)).
and therefore for every (X, v) E Z (and every (X, v) E D w.p. -2(100g (1)))
(X) 2 max (1) (x) + 2log k).
3$
25

---

Published as a conference paper at ICLR 2025
Proof. Denote by Zú, for the sample (X, y) Zu,m such that - (X) 3p S 1 100 log()
where (y,1*) E M. For a sample (X,y) E Zi.m denote by H(X) as the set of all i [}] \ {y} such that EpePo,
3p 2 0.4 lkg(k) where (i, E M.
1
Now, suppose 1 logit, y (F(O, x) {(),, with min(1, s 2(1 I43) we have
min(1, Σ e et (x)- S 2X
MEl
By Claim 21 and our definition of H()), this implies that
201) min(1, > 0.40!! 1.- 0,3-1") S 4E()..
If we denote by sb E (x,))~ [1 logit,, (F()) x)], then
E (x,)))ZZumm min Σ (EH(X)
0.4010
4,3 - (01)
xx3-1-)
50(1))
1 (())) Everco min(
0.40
(1)
1,3-1 k
2.3 m))
5 50(b).
Notice that we can rewrite the LHS so that
Σ ΣSEts jEjH T Enen MEN(X) min( 7.
0.00f3 - ).3-1)
E ((x,))=
s s0(v),
Σ jE(A] E EEEN Ix [=)))))))) min( 1 0.40 :3- )3-1) (V)).
where (i,0) E M. Note for every the probability for every i * E [k]. the probability of generating sample (X,y) y) E Zi
with y= = j and i E H(X) is at least 21 ( This implies
Σ (EMMM min(
0.4090) 000 13-1) ) S Ō i.5
k3
e
87 2
Then, with 1 T4B min we have for every v), E Zu,m.
- logit, (F(0, < minn(, Σ
MER 2c 0.10/1
1,3
(t)
v.3-1")
(15)
Sk Σ EiemnNe min( (t)
1,51
-4(t)
613-1- 5
Thus, we can see that when v I
1 is sufficiently small, we have for any i E [k] \ {y}
ba
0.44
(1)
1
0.4%
110) v.3-1- S -(((log(k)).
k
1,311
By symmetry and non-ncgativity of + (1)
1.3-1 we know for any (i,3 - 1), (j,3 - & M, we have:
0.44
(t) (3-1 - j.3-v 5 (((og(A))
(t)
(
1.3-1 1 13- 2 [llog(k)).
(t)
(16)
Since Eq. (16) holds for any (i,3 1), (j,3 1') M at iteration t such that
E (x, - logit,, (F(0) x)] I şr. and from Claim D.16 in Allen-Zhu & Li (2023) we
know Eq. (16) also holds for &,,, 2yr for any (i.0) (i,1)) e M during learning Phase II, so we have
for every (X,y) Zm. by Claim 21 we have
(X) 2 1 2, O( ((poyybg(())) 2 max D + ((log(k) > max P. (X) + 2(oog k). j7y
polylog(k)
379
26

---

Published as a conference paper at ICLR 2025
for every (X, y) e suppose Uyy is its only semantic feature, by Claim 21 we have
F 2 1. By. O polylog(k) 2 Sk(log(k)):
F (x) - O(T) $311 + O 1 (x)
polylog(k)) ) - 0(1) for j + y.
Therefore, we have
y (x) 2 max (x) +(logk).
jzy
Let Ti + +. be the first iteration that ((x.))~ logit, (F((),, x)] ,.. then we know for
t 2 T Eq. (16) always holds, since the objective (*) = _ - ALL (A = 1) is O11s-iipschtzz smooth and
using full gradient descent, which means the objective value is monotonically
non-increasing. Since in Phase II, _ is kept at small value, ( is monotonically non-increasing.
E.2 MAIN LEMMAS TO PROVE THE INDUCTION HYPOTHESIS 15
In this section, we show lemmas that when combined together, shall prove the Induction Hypothesis 15 holds for every iteration.
E.2.1 CORRELATION GROWTH
Lemma 29, Suppose Parameter 10 holds and suppose Induction Hypothesis 15 holds for all iteration
< starting from Tı. Then, letting (10) Ere(mi(ud v,))+,, have for every i [K], 1 [2].
Φ 1.1 < Ô(1).
Proof. For every E [k] and every (i,1) M, after the Phase we have 1 as in SA-CutOut, the learned features (i,4) are removed and so the correlations between gradients and learned features are kept small. This means that (t) < Ô(1) holds true in learning Phase II for T < t < Ti + T2-
(Ti) < Ö(1) In Phase II,
1,
Then for the unlearned feature (i, 3 I), we suppose > Tj TV is some iteration so that 1,3-1 2 polylog(k). We will prove that if we continue from iteration t for at most T2 iterations, still have (1) 1.3-1 S Ö(1). Based on Claim 19, we have that
(wirr v4,3-1)
(t+1)
< (w/rr 11,3-1) (x [T=y(E) (E1 + Es Vi,na1)(11 - logit,(F()) (F(A)
(1)
.(())))
npNeee KN
S (w v1 O(n) E (x.))~
[1 logit, (F A(X)))
This is because that when (X,)) ~ 3,,,, we have Vi S (11) and when (X, Bu,so we have Vir,3-1 I Opp). For every (X.y) Zum. when y i, have
(A(X) N
(1) 1.3-1 Epep
20 0 0 polylog(k)
2 (11) 1,3 O 1
polylog(k)) )
Then when j y and (j.1)) M, we have
F/0 (A(X)) < 4 j,3-"" Σ EpEr
2p + O
) - (.4
3.3-P + O
PEPoza-
polylog(k)
polylog(k)
27

---

Published as a conference paper at ICLR 2025
So by Eq. (16), we have
logit, 1- ((;)())))) S k:(logg) kj
Summing up over all r E [m], we have
noNo.
(++1) 1-- S -.3- +
mm A kj
+ Ô
KNo
Therefore, if continue for T2 iterations, we still have $
1,3-1" - Ó(1)
(T++2))
E.2.2 OFF-DIAGONAL CORRELATIONS ARE SMALL
Lemma 30. Suppose Parameter 10 holds and suppose Induction Hypothesis 15 holds for all iteration < t starting from Ti. Then,
Vi E [N], E [m]. Vj E [b] \ (i), Kw 2g11 & Ō(7o).
Proof. In Phase when 1 S Ti, from Lemma D.22 in Allen-Zhu & Li (2023), we have Kw for اzyil & Ö(oo). Now we consider Phase II when t Ti. and denote by R!!) == maxrgmml.jE(MMki (ww uzuوl. According to Claim 19 and Claim 20, we have
R (1+1) <R!") + BB ( [1= & + Es + E1,; logit,
logit, (ogi
+ +n [uzz (E1 Eg + logit (F .x)
For single-view data (X, v) ~ Zn, by Claim 23, we have logit, (F(1) A(())) (+) for every i [k). In the following, we separate the process into Ti < 1 L Ti + To and Ti + To <15 + T22
When Ti < < T1 + To. During this stage, by Claim 23 we know ( = O
(vi E [k) for any (X,y) E. We also have (X) S (()(1 3--1--9-1111-- with (i,
M, and have (X) < ((00))-11 evy by definition. Recall when Ti < S Ti + To. by
Claim 24, we have t (1+1) $1)
i.3-1- i.3-1" + (2) ReL.U' ReI.U'(( (- STierTT+D 7 (0)
1,3-1 )-1
Ō(k). Also, Pr(vis-1- E P(X)li + y) z Therefore, for every Ti < 1 S Ti + To with
To = θ
we have
R2D0 S R (T)) + Ō(0o) + + (0(T.) (10) (10 (oo7k) + (00))-12
1 S Ö(
When Ti + To <1S Ti + Tz. During this stage, we have the naive bound on (X) S 7, so again by Claim 19 and Claim 20, we have
((+1) < (t) + E Exxx) [(7 + (ag-1>s (2o7k)) + (00)a-13))) ) - logit, (F(),
Nea 4a N. n5T5. we know R² < I
Therefore, by the upper bound multi- enror in Claim 26 and Ö(G)) for To <t Ti T22-
E.2.3 NOISE CORRELATION IS SMALL
Lemma 31. Suppose Parameter 10 holds and suppose Induction Hypothesis 15 holds for all iteration
<. l starting from Ti. For every 1 [2), for every E [mn), for every (X, v) E 2n, and i E [k)]
(a) For every p E Po,,, we have: (w Ep)l S ō(0o)-
(b) For every p P(X) \ (Pr,, (X) U P Pun,a (X)), we have: ( & Ô(Gr).
28

---

Published as a conference paper at ICLR 2025
(c) For every p [P] (()), we have: Ku (8) Eph S ((00kk).
Proof. Based on gradient calculation Fact 16 and K &phi S (Ot ol 72 if + X or Fp.
we have that for every (X, v) E,, and E [P]. if
(wir
(8) (+++)) Ep) (w Ep) + σ " ReLU ((w))) (1) logit, (X) = Vd
(0)
No
Else i # y, (1+1) (1
Ep} = (w Sp) - 0 11
ReLL ((1g)) xp) (Fogi,,(Fl X) + vd
No
rplil s A for every < to where to is any iteration T₁ S 5 Ti + T2. When Ti I t S Ti + To. we have that
Suppose that it satisfies that Kw
(1)
(w 12) Ep) S (wer Ep) +
(TT)
(onnA-11)
Ton
No
va
kAV-1
Ton
S 6(0o) +
+
Noog
where the last step is because To = O 100
When T1 + +To
< 1 < Ti + Tg. for multi-view data
(X, 3) Zu,m. based on (15) in Claim 28, we can obtain that En)
A5A9 1
(T2 - -To)
(w (wirr: Ep) S (w
(11+7b)
:.) + Ô
+
S2N
Vd
KA
1.5 A9-11
T2n
Neog
--2
+
s²N,
Vd
For single-view data (X,y) ~ En,s, we have that
T2nAr-1 )
(T2 To)n
(wppp))) Ep) < (w
(Ti+To)
.sp) +0
Ne
Vd
σ KAV-1
+ Tande-1)
T2n
+
Noog-2
No
Vd
When p E Pe Pu. (X), we have (w0 (t)
mpll I Ö(1) from Induction Hypothesis 15. Then plugging in
A = Ō N. 2 á N. 2 á
and N. 1/Tapoly(k)) can obtain that (w E,) S
(4)
oo
ō(aa).
When p E P(X) \ (Po,, (X) U 2x),())), we have kw xpحil S Ö(pp) from the Induction Hypothesis 15. Then plugging A Ö(oo), No 2 1. and N. 2 n/l2poly(k). we can obtain that (w/) sp) < Ö(ro).
When p E [P] \ P(X), we have Kw/pprpp) < Ō(ookk) from Induction Hypothesis 15. Then plugging in A = Ö(ann)), N. 2 155 and N. 2 m/T2poly(k), we can obtain that ((e Sp>l S Ö(Go7k).
E.2.4 DIAGONAL CORRELATIONS ARE NEARLY NON-NEGATIVE
Lemma 32. Suppose Parameter Assumption 10 holds and suppose Induction Hypothesis 15 holds for all iteration t starting from Tí. Then,
Vi [k), Vr [m), VI [2]. (1 v2.) -Ō(go)-
29

---

Published as a conference paper at ICLR 2025
Proof. From Lemma D.27 in Allen-Zhu & Li (2023), we know (1)
(wirr v4,) 2 -(())) for every (0) v.)) (a))) We start from
iteration S Ti, Now we consider any iteration > Ti so that (w0 this iteration to see how negative the next iterations can be. Without loss of generality, we consider
the case when (wi v4,) I (o(()) holds for every t' 2 t. By Claim 19 and Claim 20,
(1+1) maa) 2 2 v/11 + 7 (x.)~ [T= Ö P))(1 - logit, ( (F(), x)) (Wir
Myzt (& + Es + (P(()) (i)))))))))))))) logit, (F (F)0, xx]
Recall by Induction Hypothesis 15(a).
Vx) = =E = (x) ReLT (fr0 (( xp)) E pXP ReLU ((w))) v.)22 + o(0o)) sp.
Since we have assumed (10 un1) S -((o)): so Vine(X) = O, and we have
(w!(+ v.a)) ( v1,1) 1/ (x,)) ((1p0 logi, (17)
+ Ty E + Eg) logit, (Flit,(Fl),) x)]
We first consider every 5 Ti + To. Using Claim 23 we have logit,(Fl), (F(9, 0 (t), which implies
(w U.,)) 2 (())) o Too (& ((+ (Ooo). -0(o)))-((0)
As for > Ti+TT combining with Claim 26 and the fact that logit, (F((t, X) S 1 - logit, (F(9, X) for * y, we have
(Tp) (u vx11) (T. anu) Ō()) + Ex) 2 (wff7) (Ta) c..) (ao) 2 -Ō(ov).
L
E.2.5 PROOF OF INDUCTION HYPOTHESIS 15
Now are ready to prove Induction Induction Hypothesis 15, the proof is similar to Theorem D.2 in Allen-Zhu & Li (2023).
Lemma 33. Under Parameter Assumption 10, for any m polylog(k) and sufficiently small
< poly(Ry our Induction Hypothesis 15 holds for all iterations / = TT,T, + 1...., Ti + T2
Proof. At iteration t, we first calculate
Vp (X):(): (wif xp)) (w Ug1) +p+ + Σ ape (w u') + (w (m
(18)
WEV
Vp E [P] P(X): (w] Σ v'EV
Eap (w e') + (w Ep)-
(19)
By Allen-Zhu & Li (2023) we already know Induction Hypothesis 15 holds at iteration t Ti. Suppose Induction Hypothesis 15 holds for all iterations t starting from T1. We have established several lemmas:
Lemma 29
Vi E [k], Vr [m]. VI E [2]
(w v..)) < Ö(1),
(20)
(1) Vi E [k], Vr [m] Vj [k] (i) Kw v11i < Ô(oo).
Lemma 30
(21)
Lemma 32 Vi E [b), Vr [m] AI E [2] (w v.)) 2 -((o))-
(22)
To prove Induction Hypothesis 15()), it suffices to plug Eq. (21), Eq. (22) into Eq. (18), use Opp,e [0, 7). use |V] 2k, and use (1o & S o(an) from Lemma 31.
30

---

Published as a conference paper at ICLR 2025
To prove Induction Hypothesis 15(b), it suffices plug Eq. (20), Eq. (21) into Eq. (18),
Op,e' [0, 7]. use |V] 2k: and use (w {p)l S (()) from Lemma 31.
To prove Induction Hypothesis 15(c), it suffices to plug Eq. (20), Eq. (21) into Eq. (19), use ppp"" [0, 7l. use [V] = 2k, and use (w SpYl - (k))k)) from Lemma 31.
To prove Induction Hypothesis 15(d), it suffices to note that Eq. (20) implies & 1,1 - Ó()) and note that Claim 24 implics ( 2 ( 2 (2())))
To prove Induction Hypothesis 15(c), it suffices invoke Eq. (22).
E.3 PROOF OF THEOREM 13
Recall training objective is
T 1.50 + AL (x log logit, (F(1)
x)] ( E Ex |- log logit, (F(*) AA())))))
(F(T)) logit, ,x] poly(kj holds the end of learning Phase and according Claim 27 we now this continues to hold true during learning Phase II. For Ex xx~__ [- log logit, (PX(),((()) since have for every data (X,y) 3. (y b):
From Allen-Zhu & Li (2023) know E(x,y)=, (- log-ooggoo,,,,,oo logit,
if logit, ,, ((X)) 2 then we know log logit Nogit,,(F) (F A(X)) <
0 (( logit, (F()) A(X)))
if (P A(X)) S 2. this cannot happen for too many tuples (X, thanks to Claim 26, and when this happens we have naive bound - log logit, (F(t), A(X)) [0, (()) using Claim 23.
Therefore, by Claim 26, we know when T3 > poly(k)
Σ T2 TToo ((x,))22
1 Ti T1
|- log logit, logit,((()))) S poly(k)
Moreover, since we are using full gradient descent and the objective function is O1))-Lipschizz continuous, the objective value decreases monotonically. Specifically, this implies that
E E(x.,)= [1 - logit, (F(T) ((())) S E ( log logit, l (F()) A(X)) poly(k)
for the last iteration Ti T2, which directly implies that the training accuracy perfect.
As for the test accuracy, from Claim 28 and Claim D.16 in Allen-Zhu & Li (2023), we have for every i [k].
① (T) 0.44) (T) 2 ((log(k))
+ (2)
1. ( + j.1 j.2 2 ((log(k))
(T)
(T)
(T)
This combined with the function approximation Claim 21 shows that with high probability (X)
( 2 maxjøyy (x))( 2(log k) for every (X, y) E Dm, D., which implies that the test accuracy on both multi-view data and single-view data is perfect.
F PROOF FOR FIXMATCH
In this section, we consider proving Theorem 11 on FixMatch. In this case, the formulation of strong augmentation A(-) is defined in Eq. (10), For (X,z) E Z... with i(X) 1* the feature 0g is removed with the probability σ2- When the patches of learned feature are removed, the left part is pure noise. In this way, same Claim 23, for every i [k), (F()) (F(),((X)) 0 { and
31

---

Published as a conference paper at ICLR 2025
Vari xv( EpePar,(x (X) ReLU (WW.::z))) o( polylog(R) ). When the patches of noises are removed, the left part is semantic patches of feature uy Since we have already captured this feature in learning Phase I, we have logit,, (F(t), A(X)) 2 1 Ō( ). In both above cases, by Claim 19 and Claim 20, the training samples (X,y) E Zn..s contribute little to the weight update process.
For multi-view data (X, y) Zu.m. when the patches of noises are removed with probability 1 1- T22 since the learned feature V'y of Phase I is still in the data, we have logit, logit,,(Ft)) (FX)) 2 1 ( (+))) When the patches of unlearned feature Uy,3-1- are removed with probability T2 or (1 m1 ) (depending on the value of 3 - 1", the learned feature of Phase is also still in the data. Thus we also have logit, (F(()) A(X)) 2 1 - ( ). In this way, the loss on all data points (X, v) E Ê,, that belongs to the above two cases keeps small (S poly(k)) and contributes negligible to the learning of unlearned features in Phase II. Finally. when the patches of learned feature Vg are removed with probability Ti 22 or (1 π I (depending on the value of ), the remaining patches of feature yy.3-1- unlearned and the approximation of initial loss this part of samples is the same as Claim 23. The loss on samples (X, v) Zu,.. with learned features removed dominates the training objective in learning Phase II, and the rest proof schedule is the same as the proof of SA-FixMatch. However, now the size of data with learned features removed for class i E [k] is either м 22 No or (1 - TI ) N:t Thus, similar to the proof of Theorem 13 and for the simplicity of notation, the requirement on the size of unlabeled data for FixMatch should be N. 2 1/l22- (012-oooy()))) min [ I2: (1- ( )r2) Accordingly, we can derive that the relationship between the size of the unlabeled data in SA-FixMatch Ne and FixMatch N₂ is given by N₂- = max T2,
u
(1 T2, T2)
G PROOF FOR FLEXMATCH, FREEMATCH, DASH, AND SOFTMATCH
Our analysis framework and theoretical results are also applicable to other FixMatch-like SSL, e.g., FlexMatch (Zhang al., 2021a), FreeMatch (Wang et al., 2022b), Dash (Xu al., 2021), and SoftMatch (Chen et al., 2023). since the main difference is the choice of confidence threshold To in unsupervised loss Eq. (5). Here we first introduce their choice of T and then explain how our theoretical results in Sec. 4 can be generalized to their case.
FlexMatch (Zhang et al., 2021a) designs an adaptive class-specific threshold T, = (b)r at iteration t, where (b) E [0. 1] is the model's prediction confidence for class b (L. normalized). FreeMatch (Wang et al., 2022b) replaces in FlexMatch with an adaptive тr, which is the average prediction confidence of the model on unlabeled data and increases as the training progresses. SoftMatch uses the average prediction confidence Ti of the model as the threshold and sets the sample weight as 1.0 logit,, (+)) (xx))) 2 Tt, otherwise a smaller constant according to a Gaussian function. Dash adopts the cross-entropy loss to design the indicator function 1 log logit, (PO))a(X,, )) where Pe decreases as training processes. This is equivalent to a dynamically increasing threshold T, in Eq. (5). Below we detail how our theoretical findings apply to each of these SSL algorithms.
FlexMatch (Zhang et al., 2021a) differentiates itself from FixMatch by modifying the constant threshold 7 include an adaptive class-specific threshold (b)b) for each class b. Under our multi-view data assumption as defined in Def. 7, the data distribution for each class is the same. Consequently, as suggested by Claim 24 and Claim D. 10 in Allen-Zhu Li (2023), all classes progress a similar rate during training. This uniformity over all classes allows us to standardize (,(b) 1, Vb E [K)] thereby aligning the proof for FlexMatch with that of FixMatch.
For FreeMatch (Wang et al., 2022b) and SoftMatch (Chen et al., 2023). instead of applying large constant threshold t during the training process, they use an adaptive Tr to involve more unlabeled data with pordectl pscudo-label in the training of the network. Under our multi-view data assumption Def. 7, the majority of the data in training dataset is of multi-viww (with probability 1 poly(k) ) so we only consider the network's prediction confidence for multi- data to determine
Te. We set the adaptive threshold T; as follows:
maxx M E.... [logit, (F71), X)],
1 1= Too
(23)
[T--11 + (1- 3) maxxez... logit,(Fl), (F(),
t > To
32

---

Published as a conference paper at ICLR 2025
where 3 is the momentum parameter, 6 arg max; (F(),, ,X), and To = l: Here no0 do not consider the unsupervised loss term Eq. (5) before To-th iteration in our analysis, since the model is bad at generating correct pseudo-label at the initial phase of training. We use max function here to ensure the high quality of pseudo-labe labell for unlabeled data involved at each training step. After To-th iteration, according to Claim D.11 and Lemma D.22 in Allen-Zhu & (2023), the feature correlations increase to A (1) for t 2 To. while the off-diagonal correlations (wir (01) (i + j) keep small at the scale of Ō(o)). Denote ((1) max,,e()) $1 recall from Claim D.9 in Allen- & Li (2023), for every X E arg max [logit, (F (X) with ground truth label v. we have F/ (X) s 0.80014(1) for j + y and (x) 2 0.99994(() (1) with probability least 1 - e 8), Accordingly, we have Fy( (X) 2 maxjzy (x) Ô(1), which means that F()) can correctly classify the unlabeled data with high probability (i.e., b y). Therefore, when t 2 To. both the supervised loss Eq. (4) and unsupervised loss Eq. (5) take effect. Same as in Sec. 4, we use
( here to monitor the feature learning process. For (i, E M,, feature 1a,t is partially learned (Tb) @1) (l(oo(k)), while feature v1,3-1 is missed in that $ 1,3-1 = Ō(o)) < ((1). Start from To, feature T is continued to be better learned with the help
during the first To iterations in that $ (76)
of supervised loss and unsupervised loss until o 2 S2(log k). and feature V1,3-1 start to be learned with the help of unsupervised loss. We can analyze this feature learning process using similar approach as in Sec. E. The key intuition for the extension of the proof of FixMatch to FreeMatch and SoftMatch is that by setting an adaptive confidence threshold, the learning process of unlearned features begin at To instead of Ti poly(k)/n >> To in FixMatch.
For Dash, it uses cross-entropy loss as the threshold indicator function rather than prediction confi- dence Il[ [- log (FX),, where Pr decreases as the training progresses. Since we have
- -log ((())) < P = (ogit,((""),((..))) > e
we can set P. = - log Tr and the rest of the analysis is the same as in SoftMatch and FreeMatch.
H EFFECT OF STRONG AUGMENTATION ON SUPERVISED LEARNING
In this section, we show why using strong augmentation with probabilistic feature removal effect, such as CutOut, in supervised learning (SL) has minimal alternation to the feature learning process. In SL, strong augmentation A(-) is utilized at the start of training. before any feature has been effectively learned, corresponding to Phase I of SSL. According to Assumption 9, A(-) randomly removes its semantic patches and noisy patches with probabilities of π. and 1 T2, respectively. Then for single-view image, its only semantic feature is removed with probability π2. For multi-view image, one of the two features, U;,1 or Vi,2 is removed with probabilities कi T2 and (1 (1-ao mi ) respectively. Thus, the size of single-view data in training dataset 2, is increased, as A(.) transfers N2,i multi-vior samples to single-view.
However, m2 (0, 1) is small, since based on our data assumption in Def. 7, the number of patches associated with certain semantic feature is constant C, while the total number of patches is P = k22 Therefore, when we do random masking in A(-) (usually masks 1/4 of all patches), we can approximate n2 as (Cp/Pl C),,, which is 0(1/AC, based on our definition of A(-) in Eq. (10).
Consequently, strong augmentation A(-) only slightly increases the proportion of single-view data, and the majority of the training dataset remains multi-view, which dominates the supervised training loss Eq. (4) since no feature has been learned. The assumptions on the number of labeled single- view data N,,, < o(k/p) and N; 2 Ni.- poly(k) still hold after strong augmentation A(-). Thus, according to Allen-Zhu & Li (2023) and Appendix B, the network learns one feature per class to correctly classify the majority multi-view data due to "view lottery winning", and memorizes the single-view data without learned feature during the training process of SL. We also validate the limited effect of CutQut on SL through experimental results in Appendix K.3.
33

---

Published as a conference paper at ICLR 2025
I COMPARISON WITH PIONEERING WORK
While this work follows the data assumption and proof framework of Allen-Zhu & Li (2023), analysis of the feature learning process is significantly different. Firstly, this work focuses on SSL, where supervised loss on labeled data and unsupervised loss on unlabeled data result in rather different feature learning processes compared with supervised distillation loss on only labeled data Allen- Zhu & Li (2023). Secondly, SSL uses the on- on-training model as an online teacher which varies along training iterations, while the SL. setting Allen-Zhu & Li (2023) uses well-trained and fixed model as an offline teacher. Indeed, the online teacher in SSL. setting is more challenging to analyze, as the cvolution of its performance is harder to characterize, and has rather different learning process.
J (SA-)FIXMATCH ALGORITHM
In this section, we present the detailed algorithm framework for FixMatch (Sohn et al., 2020) and SA-FixMatth. At iteration I, we first sample a batch of B labeled data x(() from labeled dataset Z,, and batch of μB unlabeled data 2t(t) from unlabeled dataset zu. Then, according to Algorithm calculate the loss for current iteration, and use for the update of the neural network model F())
The only difference between FixMatch and SA-FixMatch is in line 6, where FixMatch adopts CutOut in its strong augmentation of unlabeled data A. while SA-FixMatch adopts SA-CutOut.
Algorithm 1 FixMachh algorithm.
1: Input: Labeled batch 2²(1 ((X,, i (1,..., B)), unlabeled batch (((()
{U4 :1:: (B)). confidence threshold т, unlabeled data ratio μ., unlabeled loss weight A.
2: L B Σ :=1 log logit,, (F(1) a(X)))) (Cross-entropy loss for labeled data)
3: for
to μB do
4: 0 arg maxxx(oggt (F (F()),(U))) (Compute prediction after applying weak data augmen-
tation U.)
5: end for
6: L
BB D (ogit (FtO, (FtO) ((U,)))2 log logit,, (F" (009,A(U3))) (Cross-entropy loss with pseudo-label label and confidence for unlabeled data)
return: (0) + XT!
7:
K. EXPERIMENTAL DETAILS
K.1 EFFECT OF STRONG AUGMENTATION
In this section, we conduct experiments to evaluate the impact of different strong augmentation operations employed in FixMatch (Sohn et al., 2020). We assess their effects by applying these strong augmentations to test images and observing the resulting changes in test accuracy. To ensure fair comparison, we train neural networks using reakly-augmentee augmentation consists of random horizontal flip and slight extension of the image around its edges before cropping the main portion. Subsequently, we apply a single strong augmentation operation at time to the test dataset and record the corresponding test accuracy the pretrained model. The pool of strong augmentation operations from RandAugment (Cubuk et al., 2020) includes: Colorization, Equalize, Posterize, Solarize, Rotate, Sharpness. ShearX, ShearY, TranslateX, and Translate Y. The experimental results are summarized in Tables 5 and 6.
labeled data, where the weak
Original
CutOut
ShearX
Solarize
TranslationX
80.95
38.67
78.38
52.70
80.69
Sharpness
Posterize
Equalize
Rotate
Color
72.99
76.17
60.14
67.97
69.71
Table 5: Pretrained model test accuracies (%) with different strong augmentation operations for test images on CIFAR-100.
34

---

Published as a conference paper at ICLR 2025
Original 86.44
CutOut 62.94
ShearX 85.01
Solarize
TranslationX
78.94
84.44
Sharpness
Posterize
Equalize
Rotate
Color
82.17
86.19
80.74
82.29
84.34
Table Pretrained model test accuracies (%) with different strong augmentation operations for test images on STL-100.
From Tables 5 and 6, we observe that CutOut is the strong augmentation operation with the most significant impact on model performance. Additionally, transformations such as Solarize and Equalize from RandAugment also have noticeable effect model performance. To better understand the influence of these transformations on input images, we visualize the effects of CutOut, Solarize, and Equalize on CIFAR-100 images in Figure From the first and second rows of Figure 3, can see that both CutOut and Solarize have the potential to remove semantic features by masking parts of the images. From the third row of Figure we observe that Equalize tends remove color features of images while retaining shape features. In all cases, these effective strong augmentation operations have the potential remove partial semantic features. Therefore, in Assumption 3 for strong augmentation A(-), we focus on its probabilistic feature removal effect
Figure 3: Visualization of the effects of CutOut row), Solarize (second row), and Equalize (third row) on CIFAR-100 images.
K.2 EFFECT OF WEAK AUGMENTATION
Since weak augmentation consists only of random horizontal flip and random crop with small padding of 4 pixels, followed by cropping the padded image back to the original size, minimally alters the semantic features of the image. This allows us to treat weak augmentation a(-) as identity mapping for our thcoretical analysis in Sec. 4. In this section, we conduct experiments by training Fix without weak augmentation STL-10 10 with 1000 labeled samples, comparing the test performance to that of the original FixMatch. As shown in Table 7, weak augmentation does not significantly impact the model's performance.
CIFAR- 100 with 10000 labeled samples and
Dataset
STL-10
CIFAR-100
Weak Augmentation
92.65
77.27
No Weak Augmentation
91.83
77.19
Table 7: Comparison of test accuracies (%) of FixMatch with and without weak augmentation.
K.3 COMPARISON OF CUTOUT IN SL AND FIXMATCH
Data augmentation operations like CutOut help SI., but cannot improve much in deep SSL with limited labeled data. On STL-100 dataset with 40 labeled data, when we remove CutOut from SI, the test accuracy (%) does not drop lot as shown in Table 8. In contrast, removing CutOut from the strong augmentation A(-) in FixMatch's unsupervised loss (!)) leads to a severe performance degradation.
35

---

Published as a conference paper at ICLR 2025
Method SL
FixMatch
CutOut
23.98
68.30
No CutOut
22.88
53.64
Table 8: Comparison of test accuracies (%) of SL and Fix.Match with and without CutOut.
K.4 DATASET STATISTICS
For each experiment in Sec. 5, following Sohn et al. (2020); Zhang al. (2021a); Xu et al. (2021); Wang et al. (2022b); Chen et al. (2023), we randomly select image-label pairs from the entire training dataset according labeled data amount, set images from the whole training dataset without labels as unlabeled dataset, and we use the standard test dataset. The table below details data statistics across different datasets.
Dataset
Total Training Data
Total Labeled Data in Training Data
Test Data
STL-10
105000
5000
8000
CIFAR-100
50000
50000
10000
Imagewoof
9025
9025
3929
ImageNet
1281167
128 I 167
50000
Table Summary Datasets.
K.5 TRAINING SETTING AND HYPER-PARAMETER
All experiments are conducted on four RTX 3090 GPUs (24GB memory). Due to resource limitations, we did not follow Sohn et al. (2020) by training for 1024 epochs with 1024 iterations per epoch (220 iterations in total). Instead, we run 150 epochs with 2048 iterations per epoch (307,200 200 iterations) for the standard setting in Sec. 5.1, and 50 epochs with 2048 iterations per epoch (102,400 iterations) for same training dataset setting in Sec. 5.4. As shown in Sec. 5, our test accuracy results closely match those of Sohn et al. (2020). For FixMatch experiments, we base our implementation on Kim (2020), while all other experiments follow Wang et al. (2022a). Each SSL experiment takes 48 to 120 hours on single RTX 3090 GPU, depending the model and dataset.
For CIFAR- 100, STL-10, Imagewoof, and ImageNet, their input image size are respectively 32 x 32, 96 96, 96 96, 224 224 and their mask size in CutOut are respectively 16 x 16, 48 x 48, 48 x 48 112 x 112. For the application of SA-CutOut, according to our theoretical analysis in Sec. 4 and Appendix G, we only need after partial feature already been learned to learn comprehensive features in the dataset. Therefore, in practice, we only apply SA-CutOut to deep SSL methods in the last 32 epochs of training, and the total running time of Mathh is roughly 1.15 times of FixMatch.
For hyper-parameters, we use the same setting following FixMatch (Sohn et al., 2020). Concretely, the optimizer for all experiments is standard stochastic gradient descent (SGD) with a momentum of 0.9 (Sutskever et al., 2013). For all datasets, we use an initial learning rate of 0.03 with cosine learning rate decay schedule (Loshchilov Hutter, 2016) as r To cos [ ). where JJ is the initial learning rate, & is the current training step and K is the total training step that is set to 307200. We also perform an exponential moving average with the momentum of 0.999. The hyper-parameter settings are summarized in Table 10.
K.6 SAMPLES IN CIFAR-100, STL- 10, IMAGEWOOF, AND IMAGENET
As observe from Figure 4, for images in CIFAR- and STL-10, the semantic subject in the image occupies the majority of the image. On the other hand, for images in Imagewoof and ImageNet dataset, most semantic subject only occupies less than quarter of the image.
36

---

Published as a conference paper at ICLR 2025
Dataset
CIFAR-T00
STL-10
Imagewoof WRN-37-2
ImageNet
Model
WRN-28-8
WRN-37-2
ResNet-50
Weight Decay
le-3
5e-4
5e-4
3e-4
Batch Size
64
128
Unlabeled Data Raion μ
Threshold 7
0.95
0.7
Learning Rate !/
0.03
SGD Momentum
0.9
EMA Momentum
0.999
Unsupervised Loss Weight À
Table 10: Complete hyper- pyreme- setting.
Figure 4: Samples from CIFAR- 100, STL-10, Imagewoof, and ImageNet datasets. Samples in the first row are from 100, samples the second row are from STL- 10, samples in the third row from Imagewoof, and samples in the last row are from ImageNet.
L EXPLANATION OF MULTI-VIEW DATA ASSUMPTION
In this section, make more detailed explanations of multi-view data assumption Def. by breaking down and explain each part with specific examples from car images in ImageNet.
From Figure 1 know that wheel and front light be viewed as two discriminative semantic features of car, and each can be used independently for the learning model to make correct class prediction. In Figure that contains either only one of the two features or both. Then, we use them as examples to explain the multi-view data assumption Def. in detail.
give some examples of single-view data and multi-view data in car images
In Def. 1, the data distribution D is composed of samples from the multi-view data distribution Dm,. with probability
μ, and from the single-view data distribution D, with probability μ= poly(k)) In the context of car images, this implies that the majority of images are multi-view, containing both wheel and front light features, while small fraction of images single-view, containing only one of these features.
Then, Def. defines (X, ~D by first randomly selecting label y [k] uniformly, and generate the data X as follows:
(a) A set of noisy features V is sampled uniformly random from {ur 02. heghe each with probability s/k. The complete feature set of X is then defined as V(X) = 1" U (Uy, 2y which
includes both the noisy features y" and the main features (My,1 Uy
37

---

Published as a conference paper at ICLR 2025
90UNTS3
Figure 5: The first single-view image contains only the front light feature, while the middle two multi-view images contain both wheel and front light features, and the last single- view image contains only the wheel feature.
In the context of car images, (a) corresponds to the semantic features specific to cars (wheel and front light) being present in car images, along with noisy features from other classes, such as houses or trees in the background.
(b) For each u E V(X), pick Cp disjoint patches in [P] and denote them as (X) For patch p E (X). we set zp = zp. + "noises" E Rdd where the coefficients 2p 2 0 satisfy:
(b1) For "multi-view" data (X, E Dm, EpEP.(x) 30 E [I,) when E (2y,1, 2222) and Exep,(x) 3p E [Q((). when v E V(X) \ (uy,1, 2y.2).
(b2) For "single-view" data (X,v) E D.. pick value i E [2] randomly uniformly the index of the main feature. Then EpEp. 2p E [(1) when v = uy. EpEP,(X) 2p E [p, O(p)] (p- 00001) when "y ". and ΣpEp. 2p polylog(k) when E V(X) (02.1, U2,2).
In the context of car images, (b1) indicates that multi-view data features a significant presence of two prominent class-specific semantic features, while the proportion of noisy features in the image relatively small. For example, the middle two multi-view car images shown in Figure 5, the wheel and front light features more prominent than the background elements, such as houses and trees. (b2) indicates that single- view data contains only one prominent class-specific semantic feature, with the other semantic feature and noisy features being minimal. As shown in the first and last single-view car images in Figure 5, these images prominently display either the wheel or the front light, while the other semantic feature and noisy background elements are scarcely present.
(c) For each purely noisy patch p E [P] \ (X), we set Up "noises".
In the context of images, purely noisy patches correspond regions such road sky patches that do not contain semantic information relevant to classification.
For neural network capable of learning comprehensive semantic features after training-such both the wheel feature and the front light feature for car images-can accurately predict both multi-view samples, such as the middle two images in Figure and the single-view samples, such as the first and last images in Figure 5. However, if the network only learns partial semantic features, either the wheel or the front light feature, will misclassify the single-vier view images that do not contain this feature, either the first or the last image in Figure and result in inferior generalization performance.
38


Reviews:
[{"review_id": "sAISYtcHgM", "reviewer": "Reviewer_WDKZ", "summary": "The paper studies the feature learning process of neural networks trained with the FixMatch method, which is a semi-supervised learning method, demonstrating its theoretical advantages on data distributions with a “multi-view” structure. The authors characterize the FixMatch learning process as a two-stage process: initially, the model learns like supervised learning and learns most of the features, followed by a second stage where it learns the missing features through unsupervised learning from augmented data. Based on these theoretical insights, the authors introduce a semantic-aware augmentation in FixMatch to enhance its performance.", "questions": "1. Why can’t the augmentation be agnostic about what the patch contains, what is the theoretical bottleneck here? What impact would a uniformly random mask have? Could there be a more realistic setting where distribution-agnostic data augmentation could still achieve similar results?\n2. While the theory here follows very closely to that of AllenZhu and Li [2023], it seem to have missed some previous works exploring the effects of augmentation on feature learning process [1,2]. The authors can refer to the designs of augmentations and their corresponding analysis in these papers.\n\n[1] Toward Understanding the Feature Learning Process of Self-supervised Contrastive Learning. Zixin Wen, Yuanzhi Li [ICML 2021]\n\n[2] The Mechanism of Prediction Head in Non-contrastive Self-supervised Learning. Zixin Wen, Yuanzhi Li [NeurIPS 2022]", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. This paper provides a new theoretical analysis of the FixMatch method, particularly on multi-view structured data distributions, demonstrating its effectiveness in learning features and its advantages over supervised learning. The characterization of FixMatch's two-stage learning process is insightful, offering a clearer understanding of how the model learns from both supervised and unsupervised data.\n\n2. The authors propose a new semantic-aware augmentation technique that aligns with their theoretical findings, which improved the performance of FixMatch.", "weaknesses": "1. The assumptions regarding data augmentation appear artificial. The augmentation method knows which feature is in each patch and can distinguish between feature and noise patches. The augmentation randomly mask the noise patch and one of the feature, to enable the FixMatch to focus on the unlearned features. Even though such augmentation can be easily achieved in the theoretical setting, it is smarter than what is originally used in FixMatch.\n2. The proposed SA-FixMatch, although is interesting and shares closer connection to the theory, introduces added complexity by using Grad-CAM for augmentation, which can slow down training.", "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": "ymV5yp5xBC", "reviewer": "Reviewer_V3gi", "summary": "This paper proposes two contributions:\n1. A theoretical analysis to explain why semi-supervised learning (SSL) techniques such as FixMatch generalize better than classical supervising learning (SL).\n2. A new method FixMatch-SA (semantically aware) which builds on the analysis to further enhance FixMatch.\nThe improved performance of FixMatch serves to experimentally corroborate the theoretical analysis.\n\nI understood the substantiating argument of the theoretical analysis as follows: the correct classification of sample is typically based on multiple features (at least 2). In SL, learning of all features is not necessary to minimize the loss. Meanwhile, in FixMatch, the strong augmentation drops some features and therefore requires the network to learn all the features to minimize the loss. \n\nDisclaimer: the theoretical analysis felt above my skill, mathematically speaking. I tried to follow it to the best of my ability but there could be alternate conjectures which I am not aware of to explain the observed generalization gains.", "questions": "1. 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? Or did you already try multiple variants of such schemes and found the one you eventually presented in the paper to be the best?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1. The paper is well-written and gave me the impression that I was able to follow its goal.\n2. The results from FixMatch-SA seem to confirm the pertinence of the analysis, and intuitively I found it made logical sense.\n   - Some gains from CutOut-SA are truly impressive, including for recent FixMatch derivatives.\n3. I particularly liked that the paper didn't limit itself to a theoretical analysis but also provided an experimental validation on common SSL benchmarks.\n4. I find the FixMatch-SA method very elegant and effective and appears simple to implement which I consider a quality.", "weaknesses": "1. My own lack of knowledge on the theoretical side made it hard for me to estimate the originality of the approach. It's not per-se a weakness of the paper but rather a warning that I simply don't know.\n\nTypos (obviously this didn't influence my rating, it's for authors to polish their manuscript)\n- Line 87, wrong citation \"FixMatch (Xie)\" => \"FixMatch (Sohn)\"", "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": "yH4ZDY14st", "reviewer": "Reviewer_S4MR", "summary": "- This paper provides a theoretical analysis, aimed at answering why FixMatch-like algorithms (for Semi-Supervised Learning, or, SSL) generalizes better than supervised learning. \n- The analysis is focused on CNNs (unlike previous comparison works that provide analysis by using linear model assumptions)\n- The paper proposes a improvement to FixMatch, called Semantic-Aware FixMatch (SA-FixMatch). The SA-FixMatch essentially masks out the semantically relevant parts of a high-confidence image sample (the region that is identified by GradCAM) in a CutOut-like fashion.", "questions": "Questions were asked in the section above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The presentation of this work is impressive. The paper is not only easy to read, but the authors do a good job of highlighting their contributions and how it differs from previous works. The writing is clear and concise, and the figures and tables (although there are not that many) are not needlessly overcomplicated.\n- The proposed SA-FixMatch seems like a intuitive improvement to FixMatch, and does show to improve on the performance of FixMatch.\n- The theoretical justification in Section 4 seem to be sound.", "weaknesses": "- My main concern of this paper is the overall motivation. My main question for the authors is: Why do we need to have a good theoretical understanding of why FixMatch generalizes better than Supervised Learning? The following is my thought process: Let's say we have a dataset that is fully labeled. In this case, we would obviously use supervised learning (since we have all labels) to train the model. But now, let's consider the case where only 10% of the data is labeled. Obviously, given that SSL can leverage 90% of the dataset while SL can only leverage 10% (9x the size), we would apply SSL to train the model. We already know that leveraging more data will lead to better performance - so then what is the point of trying to theoretically understand why FixMatch generalizes better then SL, given that SL in this case is using a subset of the data that FixMatch is using? The worst case for SSL is that it performs equally as SL. As shown in the paper, FixMatch learns more semantic features, but that seems a bit obvious, since FixMatch is able to utilize the unlabeled samples, while SL receives no training from these unlabeled samples. Perhaps a fairer (and more interesting) setting would be to compare SSL vs Supervised learning, given the same number of total training samples (where the 'unlabeled' samples of the SSL dataset is labeled for SL). I hope I am not coming across as too offensive with this comment, but I am just trying to understand the significance of such analysis. I hope the authors can convince me otherwise. \n\n- The implications of the analysis is somewhat underwhelming. \n  - The proposed SA-Cutout does not feel like a novel contribution, given that there are previous works that use guided data augmentation for other tasks (e.g., \"Crafting Better Contrastive Views for Siamese Representation Learning\" in CVPR 2022). Also, there are some gradient-based masking techniques, such as \"Adversarial Dropout for Supervised and Semi-supervised Learning\" in AAAI 2018 that have very similar motivations as SA-Cutout, and the resulting solution is quite similar as well (masking out highly semantic regions).\n  - Are there any other takeaways from this analysis? For example, could this type of analysis be extended to a broader scope?\n\n---\n\n**Post Rebuttal**\n\nMy concerns have been addressed.", "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": "X7B0SbcpyL", "reviewer": "Reviewer_6Nkk", "summary": "This paper explores the theoretical aspects of why the SSL method FixMatch outperforms supervised learning method in generalization for deep neural networks (DNNs). Previous studies have shown that SSL methods like FixMatch achieve higher test accuracy, but the mechanisms behind this advantage are not obvious. The authors provide theoretical justification for the enhanced generalization of FixMatch for convolutional neural networks. Their analysis reveals that FixMatch captures all relevant discriminative features for each class, whereas SL approaches tend to capture only a random subset of features, an effect attributed to the lottery ticket hypothesis. This framework is shown to extend to other SSL methods similar to FixMatch, such as FlexMatch, FreeMatch, Dash, and SoftMatch. Based on these findings, the authors propose an enhanced version of FixMatch, called Semantic-Aware FixMatch (SA-FixMatch), which is validated experimentally, demonstrating improved generalization.", "questions": "1. The theory relies on 3-layer ConvNets. However, the experiments obviously hold for a wider range of architectures. Is it possible to extend it to more sophisticated architectures. For example, ConvNets with residual connections, additional layers, ViTs? If so, would it change the results somehow? Can we derive conclusions that certain architectures generalize better with SL compared to other architectures? That could be really exciting!\n\n2. Can you explain in theorem 4 why the margin scales as log(k) (where k is the number of classes). How come we get better classification margin for a more complex task with more classes? \n\n3. In theorem 4 you use $T=poly(k)/\\eta$ to represent the amount of iterations until convergence. What should I expect the degree of the polynomial and its leading coefficient to be? I want to have some concept of how many iterations we need.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "The theory presented is compelling. The authors provide a strong argument, without relying on overly strict assumptions, that training a realistic neural network (a 3-layer ConvNet) with FixMatch-type algorithms allows us to (1) fit the training data and (2) generalize well to unseen samples. This stands in contrast to supervised learning, where the model often fails to generalize well to certain types of samples within the distribution.\n\nAdditionally, the authors propose an improved variation of a FixMatch algorithm, demonstrating that their theory not only explains the success of this family of algorithms but also predicts new results.", "weaknesses": "The main weakness of this paper lies in its technical presentation.\n\nWhile I appreciate that the theoretical framework developed here is complex, making it challenging to present in an accessible way, I believe certain aspects could have been simplified for clarity.\n\nThis could be achieved by following these guidelines:\n1. Use standard notations. For instance, the authors use symbols like $Z_l$ to denote a labeled dataset, whereas $S$ is typically used for sample sets.\n2. Avoid re-using variables. In lines 126-128, for example, the symbol $i$ is used for multiple purposes, such as indexing both patches and classes, which can be confusing.\n3. Simplify complex definitions. Concepts like Definition 1 could be broken down and explained in more detail, with examples illustrating each component. Providing an example of a distribution that meets these conditions would clarify the distinction between single- and multi-view samples and help readers appreciate the significance of the conclusions in lines 284-287.\n\nMinor comment:\nIn the theorems (e.g., Theorem 4), instead of writing \"for any \\((x,y) \\sim D\\) with probability ..., we have ...,\" I would suggest phrasing it as \"with probability ... over the selection of \\((x,y) \\sim D\\), we have ...\". It is just more mathematically accurate and is consistent with the appendix.", "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)