Cluster-aware Semi-supervised Learning: Relational Knowledge Distillation Provably Learns Clustering
Authors: Yijun Dong
Kevin Miller
Qi Lei
Rachel Ward
Venue: NeurIPS 2023 poster (2023)
Keywords: Relational knowledge distillation
Semi-supervised learning
Spectral clustering
Sample complexity

Abstract: Despite the empirical success and practical significance of (relational) knowledge distillation that matches (the relations of) features between teacher and student models, the corresponding theoretical interpretations remain limited for various knowledge distillation paradigms. In this work, we take an initial step toward a theoretical understanding of relational knowledge distillation (RKD), with a focus on semi-supervised classification problems. We start by casting RKD as spectral clustering on a population-induced graph unveiled by a teacher model. Via a notion of clustering error that quantifies the discrepancy between the predicted and ground truth clusterings, we illustrate that RKD over the population provably leads to low clustering error. Moreover, we provide a sample complexity bound for RKD with limited unlabeled samples. For semi-supervised learning, we further demonstrate the label efficiency of RKD through a general framework of cluster-aware semi-supervised learning that assumes low clustering errors. Finally, by unifying data augmentation consistency regularization into this cluster-aware framework, we show that despite the common effect of learning accurate clusterings, RKD facilitates a "global" perspective through spectral clustering, whereas consistency regularization focuses on a "local" perspective via expansion.

Cluster-aware Semi-supervised Learning: Relational Knowledge Distillation Provably Learns Clustering
Yijun Dong"
Kevin Miller"
Courant Institute of Mathematical Sciences
Oden Institute for Computational
New York University
Engineering & Science
New York, NY 981331@nyy..dd
University of Texas at Austin
Austin, TX
kmm www.eutexasse...... edd
Qi Lei
Rachel Ward
Courant Institute Mathematical Sciences & Center of Data Science New York University New York, NY q151 86 8@nyu.edu
Oden Institute for Computational Engineering & Science University of Texas at Austin Austin, TX rwarddmathh www.ss.tteeasee.m..m edu
Abstract
Despite the empirical success and practical significance of (relational) knowledge distillation that matches (the relations of) features between teacher and student models, the corresponding theoretical interpretations remain limited for various knowledge distillation paradigms. In this work, we take an initial step toward a theoretical understanding of relational knowledge distillation (RKD), with focus on eumi-suped classification problems. We start by casting RKD as spectral clustering nopulation-induces graph unveiled by teacher model. Via notion clustering error that quantifies the discrepancy between predicted and ground truth clusterings, we illustrate that RKD over the population provably leads low clustering error. Morcover, we provide sample complexity bound for RKD with limited unlabeled samples. For semi-supervised learning, we further demon- strate the label efficiency of RKD through general framework of cluster- aware semi-supervised learning that assumes low clustering errors. Finally, by unifying data augmentation consistency regularization into this cluster-aware framework, show that despite the common effect of learning accurate clusterings, RKD facilitates a "global" perspective through spectral clustering, whereas consistency regularization focuses "local" perspective via expansion.
Introduction
The immense volume of training data is vital driving force behind the unparalleled power of modern deep neural networks. Nevertheless, data collection can be quite eesource-intensive in particular, data labeling may be prohibitively costly. With an aim lessen the workload associated with data labeling. semi-supervised learning capitalizes on more easily accessible unlabeled data via diverse approaches of pseudo-labeling. For instance, data augmentation consistency regularization [Sohn et al., 2020, Berthelot et al., 2019] generates laeudo-labels from the current model predictions on carefully designed data augmentations. Alternatively, knowledge distillation [Hinton al., 2015] can be leveraged to gauge representations of unlabeled samples via pretrained teacher models.
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

A(x)
A(x
Figure I: The complementary perspectives of RKD and DAC regarding the data. RKD learns the pairwise relations among data (e.g., edge tixx' that characterizes the similarity between x and x') over the population "globally" via spectral clustering, as illustrated in Section 4. Alternatively, DAC discovers the "local" clustering structure through the expansion of neighborhoods based on overlapping augmentation sets (e.g., A(x) A + 0), as elaborated in Section 6.
Meanwhile, as the scale of training state-of-the-arr models explodes, computational costs and limited data are becoming significant obstacles to learning from scratch. In this context, (data-free) knowledge distillation [Liu et al., 2021, Wang and Yoon, 2021] I (where pretrained models are taken as teacher oracles without access to their associated training data) is taking increasingly crucial role in learning efficiently from powerful existing models.
Despite the substantial progresses in knowledge distillation (KD) in practice, its theoretical under- standing remains limited, possibly due to the abundant diversity of KD strategies. Most existing theoretical analyses of KD [Ji and Zhu, 2020, Allen-Zhu and Li, 2020, Harutyunyan al., 2023, Hsu et al., 2021, Wang et al., 2022] focus on feature matching between the teacher and student models [Hinton et al., 2015], while a much broader spectrum of KD algorithms [Liu al., 2019, Park et al., 2019, Chen et al., 2021, Qian et al., 2022] demonstrates appealing performance in practice. Recently, relational knowledge distillation (RKD) [Park al., 2019, Liu al., 2019] has achieved remarkable empirical successes by matching the inter-feature relationships (instead of features them- selves) between the teacher and student models. This drives us to focus on RKD and motivates our analysis with the following question:
What perspective of the data does relational knowledge distillation learn, and how efficiently?
(RKD learns spectral clustering,) In light of the connection between RKD and instance relation- ship graphs (IRG) [Liu al., 2019] intuitively, RKD learns the ground truth geometry through graph induced by the teacher model. We formalize this intuition from a spectral clustering perspective (Section 4). Specifically, for multi-class classification problem, error (Definition 3.1) that measures the difference between the predicted and ground truth class partitions. Through low clustering error guarantees, illustrate that RKD learns the ground truth partition (presumably unveiled by the teacher model) via spectral clustering (Section 4.1.. Moreover, RKD sufficiently many unlabeled samples learns a similar partition with low clustering error (Section 4.2). By appealing to standard generalization analysis (Wainwright, 2019, Bartlett and Mendelson, 2003, Wei and Ma, 2019] for unbiased estimates of the parameterized RKD loss, we show that the unlabeled sample complexity of RKD is dominated by a polynomial term in the model complexity (Theorem 4.2, Theorem 4.3).
introduce notion of clustering
the population
As one of the most influential and classical unsupervised learning strategies, clustering remains an essential aspect of modern learning algorithms with weak/no supervision. For example, contrastive learning [Caron et al., 2020, Grill et al., 2020, Chen and He, 2021] has proven to learn good representations without any labels by encouraging (spectral) clustering [HaoChen et al., 2021, Lee et al., 2021, Parulekar et al., 2023]. However, the effects of clustering in the related schemes of semi- supervised learning (SSL) are less well investigated. Therefore, we pose a follow-up question:
How does cluster-aware semi-supervised learning improve label efficiency and generalization?
2 An IRG is graph with samples vertices and sample relationships, characterized by their mutual distances a feature space, edges. RKD encourages the student model learn such IRGs from the teacher model.

---

(Cluster-aware SSL is label-efficient.) We formulate a cluster-aware SSL framework (Section 5) where assuming low clustering error (Definition 3.1) endowed by learning from unlabeled data, the label complexity scales linearly in the number of clusters, up to logarithmic factor (Theo- rem 5.1).
Since clustering is rather generic notion that can be facilitated from various perspectives, to better understand spectral clustering as learned by RKD, we compare the clustering mechanism of RKD with that of another common example of cluster-aware regularization, while exploring the following question:
augmentation consistency (DAC)
What are the similarities and discrepancies between different cluster-award strategies?
(RKD and DAC learn clustering from complementary perspectives.) We unify the existing analysis (Yang et al., 2023] tailored for DAC regularization [Sohn et al., 2020] into the cluster-aware SSL framework (Section 6). In particular, while facilitating clustering similarly to RKD, DAC reduces the clustering error through an expansion-based mechanism characterized by "local" neighborhoods induced by data augmentations (Theorem 6.2). This serves as a complementary perspective to RKD which approximates spectral clustering graph Laplacian that reflects the underlying "global" structure of the population (Figure 1).
2 Related Works
Relational knowledge distillation. Since the seminal work of Hinton et al. [2015], knowledge dis- tillation has become a foundational method for time and memory-efficient deep learning. Recent years have seen different KD strategies. Some works learn to directly match the output (response) [Hinton et al., 2015, Chen al., 2017, Ba and Caruana, 2014] or intermediate layers (features) [Romero et al., 2014, Zagoruyko and Komodakis, 2016a, Kim et al., 2018] of the teacher network. More recently, Park al. [2019] introduced the idea of relational knowledge distillation (RKD), and concurrent work [Liu et al., 2019] introduced the "instance relationship graph" (IRG). They essentially presented similar ideas to learn the
relationship between samples instead of matching models' responses or features individually. A comprehensive survey of relational (relation-based) KDD can be found in [Gou et al., 2021].
Despite the empirical success stories, the theoretical understanding of KD remained limited. Prior theoretical work is mostly constrained to linear classifier/nets [Phuong and Lampert, 2019, Ji and Zhu, 2020] or neural tangent kernel (NTK) analysis [Harutyunyan et al., 2023]. Hsu et al. [2021] leverages knowledge distillation improve the sample complexity analysis of large neural networks with potentially vacuous generalization bounds.
Data augmentation consistency regularization. Data augmentation serves as an implicit or explicit regularization to improve sample efficiency and avoid overfitting. Initially, people applied simple transformations to labeled samples and add them to the training set [Krizhevsky et al., 2017, Simard et al., 2002, Simonyan and Zisserman, 2014, He et al., 2016, Cubuk et al., 2018). Traditional transformations preserve image semantics, including (random) perturbations, distortions, scales, crops, rotations, and horizontal flips. Subsequent augmentations may alter the labels jointly with the input samples, c.g. Mixup [Zhang et al., 2017], Cutout [De Vries and Taylor, 2017], and Cutmix [Yun al., 2019]. Theoretical works have demonstrated different functionalities of data augmentation such as incorporating invariances [Mei et al., 2021]. ]. amplifying strong features [Shen et al., 2022], or reducing variance during the learning procedure [Chen et al., 2020].
Recent practices explicitly add consistency regularization to enforce prediction or representation similarities [Laine and Aila, 2016, Bachman et al., 2014. Sohn al., 2020]. Not only does this way incorporates unlabeled samples, but Yang et al. [2023] also theoretically demonstrated other benefits: explicit consistency regularization reduces sample complexity more significantly and handles misspecification better than simply adding augmented data into the training set.
Graph-based learning. Although we leverage graphs to model the underlying clustering structure of the population, the RKD algorithm that we study applies to generic data distributions and does not involve any graph constructions over the training data. The latter is crucial for modern learning settings graph construction can be prohibitively expensive common large-scale datasets.
Nevertheless, assuming that explicit graph construction affordable/available, there exists rich history of nonparametric graph-based based semi-supervised classification models for transductive learn-
3

---

ing [Zhu et al., 2003, Bertozzi and Merkurjev, 2019, Zhou et al., 2003, Belkin et al.. 2004, Belkin and Niyogi, 2004]. These methods have seen success in achieving high accuracy results in the low-label rate regime [Calder et al., 2020, Bertozzi and Merkurjev, 2019]. Furthermore, assuming inherited graph structures of data, recent progress in graph neural networks (GNN) [Zhou et al., 2020] and graph convolutional networks (GCN) [Welling and Kipf, 2016] has provided a connection between these classical graph-based methods and powerful deep learning models for a variety of problem settings [Zhou et al., 2020].
3 Problem Setup
Notations.
For any event e, let {e} = if is true, and 1 {e} = otherwise. For any positive in-
tegers n, E N, we denote [n]] = n. and Ax { (PI..... .p) E [0, Ek Pk = } For finite set X. |x|| denotes the size of X, and Unif (2) denotes the uniform distribution over X' (i.e,, (x)
| for all x E 2). For distribution P over X' and any E N, P" rep- resents the joint distribution over X such that (xilietn) P is a set of i.i.d. samples. Given
any matrix M E T (n 2 k without loss of generality), let (M) fa, (M) i E [K]] be the singular values of M with 01 (M) > ... 2 os (M). While for any symmetrie M E IR*X", let A (M)- = (A: (M) i E [n]] be the eigenvalues of M such that λ (M) .... S Xn (M). Given any
labeling function y : X > [K], let y X + {0, 1]
K be its one-hot encoding.
3.1 Spectral Clustering on Population-induuee Graph
We consider K-class classification problem over unknown data distribution P: X [K] (0, 1] (while overloading P for the probability measure over X' without ambiguity). Let y/+ X [K] be the ground truth classification that introduced a natural partition {dis (&s]ketK]) where X₂ & {x E X'| y+ (x) = }} such that U Ns = X' and N₂ n Be = @ for all l * K'. Mcanwhile, we specify a function class F C {f : X' + Rk} to learn from where each f E F is associated with a prediction function yy (x) argmaxke[K] (x)).
We characterize the geometry of the data population' X' with an undirected weighted graph Gx (X, W(X), such that: (i) For every vertex pair x, E X, the edge weight Uxxx 2 0 characterizes the similarity between (x, x'). For example, Wxxx between pair of samples from the same class larger than that between a pair from different classes (ii) P(x) = wx - Exexx Wxx' such that Exex Ex'x Wxx' = 1, intuitively implying that more representative instance (corresponding to a larger wxx) has a higher probability of being sampled. We remark that such population-induce graph Gx is reminiscent of the population augmentation graph for studying contrastive learning* (HaoChen et al., 2021].
Let W (X) with W (X) "'xx' be the weighted adjacency matrix of Gx; let D (X) be the diagonal matrix of the weighted degrees {wx)xext The (normalized) graph Laplacian takes the form
L (XX) =I I- W(X) where W(X) & D (X) 1/2 w (x) D (X))-/2 is the normalized adjacency matrix. Then, the spectral clustering [von Luxburg, 2007] on Gx can be expressed as a (rank-K)
Nyström approximation of ((X) in terms of the weighted outputs f
FL(x) & arggmin fEF
(f) & ((2)) - f
(1)
To quantify the alignment between the ground truth class partition and the clustering predicted by f F, we introduce the notion of clustering error.
'For demonstration purposes, we assume an arbitrarily large, but finite, population |X| < oc (as in HaoChen al. [2021], e.g., X' Fd where F is the of all floating-point numbers with finite precision). Meanwhile, our analyses can generalized to any compact set via functional analysis tools (e.g., replacing the adjacency matrix W(X) with an adjacency operator).
"The key difference between the population augmentation graph [HaoChen et al., 2021] and the population- induced graph described here is that for analyzing RKD, we consider a graph over the original, instead of the augmented, population. It's also worth highlighting that we introduce such graph structure only for the sake of analysis, while our data distribution is generic. Therefore, we focus on learning from a general function class F without constraining to graph neural networks.

---

Definition 3.1 (Clustering error). Given any f F, we define the majority labeling
yf (x) - argmax P(x) (B=(xx) y)((2))) = yy
(2)
kE[K]
along with the minority subsets associated with f: M (J) 1xE y. (x)) such that P (f)(f) quantifies the clustering error of For any F' F let (le)((()) sup P (M (f)).
Intuitively, Mf) characterizes the difference between K- K-partition of X' by the ground truth y, and by the prediction function y associated with f: while μ (F') quantifies the worse-case clustering error of all functions f F.. In Section 4.1, will demonstrate that spectral clustering on Gx (Equation (1)) leads to provably low clustering error (FL(x))
3.2 Relational Knowledge Distillation
For RKD, we assume access to a proper teacher model &i X W (for latent feature space W) that induces a graph-revealing kernel: ky (x, x')xx)= = "'xx' Then, the spectral clustering on Gx in Equation (I) can be interpreted as the population RKD loss:
R (f) Exxx [(ky (x, f(x)) f(x) f(x))²
While with only limited unlabeled samples X xx) jE [N]] ~ P(x)" N in practice, we consider the analogous empirical RKD loss:
N/2
FL(X") A argmin
Rx-
(1) A (xx (x2+ - kp (x x
N Σ
(3)
JEF
where Rx-( (f) serves as an unbiased estimate for R(f) (Proposition D.1).
Further, for semi-supervised setting with small set of labeled samples (X, y) ((xi:ii))stt) P P(x,v) ((xy)) y)" (usually n < N) independent of X", let E I x [K] + {0, 1) be the zero-one 1 (uy(x) + y}. We denote E (f) & ((x.)) (e (f y)] and (f) & E (f((x).))) wx) as the population and empirical losses, respectively, and consider a proper learning setting with the ground truth S. - argmin & (f). Then, SSL with RKD aims to find minser E(f)+ Rx_ (f). Alternatively, for an overparameterized setting² with (argmin (f) FL(x") # 0, SSL with RKD can be formulated as: minffFr..x.. ε()).
loss: (f(x),
4 Relational Knowledge Distillation as Spectral Clustering
In this section, we show that minimizing either the population RKD loss (Section 4.1) or the empirical RKD loss (Section 4.2) leads to low clustering errors μ (FL(x)) and (FL(x))), respectively.
4.1 Relational Knowledge Distillation over Population
Starting with minimization of the population RKD loss f E FL(x) = argmin fer R (f) (Equa- tion (1)), let A (L (X)) = (Ai...., ^/x) be the eigenvalues of the graph Laplacian in the ascending order, \ S S dز with an arbitrary breaking of ties.
A key assumption of RKD is that the teacher model 1 (with the corresponding graph-revealing kemnel kw)) is well aligned with the underlying ground truth partition, formalized as below:
Assumption 4.1 (Appropriate teacher models). For Gx unveiled through the teacher model kg. (s-),, we assume Ak+1 > (i.e., Gx has at most K disconnected components): while the ground truth classes (&& YεEjK] are well-separated by Gx such that a 2 _nE(K) EXERg Exter Wase the fraction of weights of inter-class edges is sufficiently small).
< (i.e.,
2ExEx Extex Wore"
"Overparameterization is ubiquitous scenario when learning with neural networks: f E F is parameterized by 0 O with dim(@)= N + n such that the minimization problem has infinitely many solutions.
5

---

In particular, E [0. 1] reflects the extent to which the ground truth classes {Xx [E[K] are separated from each other, quantified by the fraction of edge weights between nodes of disparate classes. In the ideal case, a = 0 when the ground truth classes are perfectly separated such that every Xr is a connected component of Gx, while AK- > AK= = O.
Meanwhile, to reduce the generic function class F down to a class of reasonable prediction functions, we introduce the following regularity conditions on the boundedness and margin:
Assumption 4.2 (3-skeleton boundedness and y-margin). For any F with P (M(f) S P (Ax) for all k E [K], we assume there exists a skeleton subset S = (si..... ;8k] E X with Sg- arginax XEX' (x)x such that yf (Sx) k for every [K] and rank (S(S)) K.
(i) We say that f is B-skeleton bounded if o1 (f(S)) S for some reasonably small B.
(i) Let the k-th margin of f be Tik. _ _ (8x) - (()x J (x) We say that f has a 2-margin if minse(K] Tkk > 7 7ffor some sufficiently large 7 > 0.
Intuitively, S can be viewed as set of K samples where makes the "most confident" prediction in each class. Assumption 4.2 ensures the boundedness of predictions made on such a skeleton subset Ilf (S)]l2 S 8, well as margin 7 by which the "most confident" prediction of f in each class sk can be separated from the minority samples predicted to lie in other classes {x E M M(f)uu # k). As toy example, when yr X + [K] is surjective, and the columns in f (X) E æ consist of identity vectors of the predicted clusters f (x); {y, (x) = k). Assumption 4.2 satisfied with 3 and 7 = 1. Meanwhile, the following Remark 4.1 highlights that although Assumption 4.2 cannot be guaranteed with spectral clustering alone, it is generally satisfied in the superviide
learning setting with additional supervision/regulaiizaiio (cf. Example C.I).
Remark 4.1 (Limitation of spectral clustering alone). Notice that for a generic function class F, spectral clustering alone is not sufficient to guarantee Assumption 4.2, especially the existence of a skeleton subset S or a large enough margin 7/. As counter-exemplifed in Example C.I, Equa- tion (1) can suffer from large clustering error μ (FL(x) when applied alone and failing to satisfy Assumption 4.2.
To learn predictions with accurate clustering, RKD requires either (i) additional supervistonnreguuar ization in end-to-ent settings like semi-supervised learning (ii) further fine-tuning in unsupervised representation learning settings like contrastive learning [HaoChen et al., 2021]. For end-to-end learning practice, RKD is generally coupled with standard KD (i.e., feature matching) and weak supervision [Park el al., 2019, Liu el al., 2021, Ma el al., 2022], both of which help the learned function I satisfy Assumption 4.2 with a reasonable margin 7,
Throughout this work, we assume F is sufficiently regularized (with weak supervision in Section 5 and consistency regularization in Section 6) such that ssumption 4.2 always holds. Under Assumption 4. and Assumption 4.2, the clustering error of RKD over the population μ (Fu(x) is guaranteed to be small given a good teacher model &b that leads to a negligible a:
Theorem 4.1 (RKD over population, proof in Appendix C.I). Under Assumption 4.1 and Assump- tion 4.2 for every f E FL(x)) the clustering error with the population (Equation (1)) satisfies
# (F((x) S 2 max
Ak+1
Theorem 4.1 suggests that the clustering error over the population is negligible under mild regularity assumptions (i.e., Assumption 4.2) when (i) the ground truth classes are well-separated by Gx revealed through the teacher model k (:: -) (i.e. << 1 in Assumption 4.1) and (ii) the (K- + 1)th eigenvalue Ax+1 of the graph Laplacian ((x) not too small. As we review in Appendix C.3, the existing result Lemma C.4 [Louis and Makarychev, 2014] unveils the connection between Ax+1 and the sparsest K -partition (Definition C.I) of Gx. Intuitively, a reasonably large AK+1 1 implies that the partition of the K ground truth classes is the "only" partition of Gx into K components by removing a sparse set of edges (Corollary C.5).
'Recall the majority labeling (Equation (2)) and the associated minority subset M (f) which intuitively describes the difference between clustering of the y. and that of yy. We denote f(x) = [f(x)....... f(x)x]

---

4.2 Relational Knowledge Distillation on Unlabeled Samples
We now turn our attention to a more practical scenario with limited unlabeled samples and bound the clustering error μ (Ft.(x))) granted by minimizing the empirical RKD loss (Equation (3)).
To cope with F f X IR* recall the notion of Rademacher complexity for vector-valued functions from Maurer [2016]. Let Rad(p) be the Rademacher distribution (i.e., with uniform
probability & over 1)) and p ~ Rad X K be a random matrix with i.i.d. Rademacher entries.
Given any N E N, with fx))x denoting the k-th entry of f(x) E RK we define
N
Rx (F) A E p-Rad Nx W
sup JEF N
Psk f (x
(4)
i=1
i=1
as the Rademacher complexity of the vector-valued function class Fe f: - KK
Since the empirical RKD loss is an unbiased estimate of its population correspondence (Proposi- tion D.I), we can leverage the standard generalization analysis in terms of Rademacher complexity to provide an unlabeled sample complexity for RKD.
Theorem 4.2 (Unlabeled sample complexity of RKD, proof in Appendix D.2). Assume there exist By, BKy > 0 such that [1 1 S By and ky (x,x') S Bkg for all x, x' X, f Given any fix E FFixx>> fix E FL(Z). (0,1), with probability least - 6/2 over X P(x)
(By + BR.)) RN/2 (F) + (Br, + B,)² log (4/6) R (JIx)) (f)x)) s 16
N
Theorem 4.2 implies that the unlabeled sample complexity of RKD is dominated by the Rademacher complexity of F. In Appendix D.3, we further concretize Theorem 4.2 by instantiating RN/2 (F)
via existing Rademacher complexity bounds for neural networks [Golowich et al., 2018].
With A + 0 as increasing (Theorem 4.2), the clustering error of minimizing the empirical RKD loss be upper bounded as follows.
Theorem 4.3 (RKD on unlabeled samples, proof in Appendix D.4). Under Assumption 4.1 and Assumption 4.2 for every f E FL(x"), given any 8 E (0, 1). if there exists < (1 - >x)² such that R (( < R (fix) + for all Jix" E FL(x") and fix E FL(X) with probability at least 1 - 5/2 over X ~ P(x)", then error of clustering with the empirical graph (Equation (3)) satisfies the
follows: for any Ko E [K] such that AKo < -AK+1 and CKo A (1 (1-xxa) )2 -11-xx)* >xx² O(1)
(1+ Ko) Cko) (2211) (AK+1 + (1 (1
B2
# (Fi(x)) & 2 max
(1- \x+1)²
Theorem 4.3 ensures that given sufficient unlabeled samples (proportional to the Rademacher com- plexity of F) such that A + O, the clustering error (FL(x=)) from empirical RKD is nearly as low as μ (F)))) from population RKD. up to an additional error term that scales linearly in A.
5 Label Efficiency of Cluster-aware Semi-supervised Learning
In this section, we demonstrate the label efficiency of learning from a function class with low clustering eиror (Definition 3.1), like the ones endowed by RKD discussed in Section 4.
Specifically, given any cluster-aware function subclass F C F with low clustering error (e.g.. FL(X) and F))x))), for set of i.i.d. labeled samples (X,y) P(x, y)"" we have the following generalization guarantee:
Theorem 5.1 (Label complexity, proof in Appendix B.I). Given any cluster-aware F' J with u(F') & 1, assuming that (X, contains at least one sample per class, for any 8 E (0,1), with probability at least - 8/2 over (X,y) ~ P(x. u)" f E argmin E(f) satisfies
E {T) - < <V
2K log(2n) 2/ (F') + 2log (4/8)
log
(5)
e.g. conditioned on X fxx- Eargmin ε()) satisfies Equation (5) with 1 (FL(x)).
7

---

Theorem 5.1 implies that with low clustering error (e.g., endowed by unsupervised methods like RKD in Theorem 4. I/Thorrm 4.3, DAC in Theorem 6.2), the labeled sample complexity is as low as Ô (K), linear in the number of clusters and asymptotically optimal' up to a logarithmic factor.
Remark 5.1 (Class imbalance, elaborated in Appendix B.2). Theorem 5. while the label
complexity scales as n = ((K) with i.idd sampling, we meanwhile assume that (X. y) contains at least one labeled sample per class. Intuitively, when the K classes are balanced (i.e., [Kyl | for all k E [K], an analogy to the coupon collector problem implies that n = O (K log ()) i.i.d. labeled samples are sufficient in expectation. Nevertheless, with class imbalance, the label complexity can be much worse (e.g. when |xx| & Xxk for all k E [K - 1), collecting one label K takes 1/P (Xx) >> K labeled samples). In Appendix B.2. we show that such label inefficiency can be circumvented by leveraging a cluster-aware prediction f E F and drawing O (log(K)) labeled samples uniformly from each of the K predicted clusters, instead of ii.dd from the entire population.
Remark 5.2 (Coreset selection). While Theorem 5.1 yields an asymptotically optimal label complexity guarantee with i.i.d. sampling. it is of significant practical value to be more judicious in selecting labeled samples, especially for the low-label-rate regime (c.g.. n = O(K)). Therefore, in the ii.d. sampling*
experiments (Appendix A), we further investigate-aloneee selection method [Bilmes, 2022, Krause and Golovin, 2014], where the coreset y) is statistically more representative of the data distribution P.
popular coreset
In particular. coreset selection can be recast as a facility location problem [Krause and Golovin, 2014] characterized by the teacher model: maxxcx Exex maxxex ky (x, x)), whose optimizers can be approximated heuristically via the stochastic greedy [Mirzasoleiman et al., 2015] submodular optimization algorithm [Schreiber et al., 2020]. Intuifively, the facility location objective encourages the coreset X to be representative of the entire population X' in pairwise similarity sense, and the coreset approximation identified by the stochastic greedy method is nearly optimal (in the facility location objective) up to multiplicative constant [Mirzasoleiman et al., 2015].
6 Data Augmentation Consistency Regularization as Clustering
In light of the broadness of the notion of clustering, investigating the discrepancy between different types of cluster-awareness is crucial for understanding the effect of spectral clustering brought by RKD beyond the low clustering error demonstrated in Section 4. In this section, we leverage the existing theoretical tools from Wei and Ma [2019], Cai et al. [2021] to unify DAC regularization into the cluster-aware semi-supervised learning framework in Theorem 5.1. Specifically, we demonstrate the effect of DAC as "local" expansion-based clustering [Yang et al., 2023], which works in complement with the "global" spectral clustering facilitated by RKD.
Start by recalling the formal notion of expansion-based data augmentation (Definition 6. and data augmentation consistency (DAC) error (Definition 6.2) from Wei et al. [2021]:
Definition 6.1 (Expansion-basse data augmentation ([Wei al., 2021] Definition 3.1)). For any X E X. we consider set of class-invarian data augmentations A C. X such that {x} E A(x) S. Xy-(z). We say x,x'= E X lie in neighborhoods of each other if their augmentation (x' E X A(xx) A # 0} for x E X; and NB(S) e UxES NB (x) for S C X. Then, we quantify strength of such data augmentations via the c-expansion property (c > 1): for any S S X such that P n Xx) I P(Xx)/2 l E [K].
sets have a non-empty intersection: NB (x)
P (NB(S) Xx) min fc P(S Xx) P(K)) VkE [K].
Definition 6.2 (DAC error (Wei et al., 2021] (3.3)). For any J E F and F' C let
v (f) A Px-P(x) Bx' E A(x) s.t. (x) # {z(x,,,, v (FF) & sup v(f).
tEF
Notice that assuming least labeled sample per class (i..., K) is necessary for any generalization guarantees. Otherwise, depending on the missing classes, the excess risk in Equation (5) can be arbitrarily bad. For the low-label-rad ratel-rate experiments, to ensure consistent performance, we follow the common practice [Calder al., 2020] and slightly deviate from the assumption by sampling i.i.d. from each ground truth class instead.
8

---

We adopt the theoretical framework in Wei et al. [2021] for generic neural networks with smooth activation function & and consider
{ f(x)) f(x)= - (.. (
A, E Rd.xd-1 V [p], d= max d } -= P
F
With such function class F of p-layer neural networks with maximum width d and weights {A, } we recall the notion of all-layer margin from Wei et al. [2021] Appendix C.2. By decomposing J2p-1 o ... fi such that f2.-1 (2) = A, for all E [p] and f2. ((z) for all E [p 1], we consider a perturbation 8 == (ő1, 52p-1) (where 82.-1, 62. E R to each layer of
f1 (x, f. (x - fx 51. 6.) = f. (fi-1 (x, 6)) + 6, (x,
(x, 61) fi(x) + 81 ||x||
such that f(x, f2p-1 (x, 5). Then, the all-layer margin m F X [K] + Ego is defined as the minimum norm of that is sufficient to perturb the classification of f(x):
18.112 s.t. m vf min Σ
argmax f (x, 8), + y. kE[A]
(6)
Moreover, Wei al. [2021] introduced the robust margin for the expansion-based data augmentation A (Definition 6.1), which intuitively quantifies the worst-case preservation of the label-relevant information in the augmentations of x, measured with respect to
A (f,
min U x'EA(x)
We say the expansion-based data augmentation is margin-robust with respect to the ground truth fa if minxex m. x),,))= >> is reasonably large.
Then, we cast DAC regularization" as reducing the function class F via constraints on the robust margins at the N unlabeled samples X": for some O < < minxex mA (f,,x),
Fx
U E mA (J. x!)) Vie [N]).
(8)
Leverage the existing unlabeled sample complexity bound for DAC emor from Wei et al. [2021]:
Proposition 6.1 (Unlabeled sample complexity of DAC ([Wei et al., 2021] Theorem 3.7)), Given any (0, 1), with probability at least 8/2 over X",
Vdllllle
+ +0
log (1/6) + log (N)
(Fx-) S
TVN
N
where (-) suppresses polylogarithmic factors in N and d.
The clustering error of Equation (8) is low as its DAC error, up to constant factor that depends on augmentation strength, characterized by c-expansion (Definition 6.
Theorem 6.2 (Expansion-basse clustering, proof in Appendix E.3). For Equation (8) with A ad- mitting c-expansion (Definition 6.1), the clustering error is upper bounded by the DAC error in Proposition 6.1:
222) v (Fx.). 1--1
# (F max
In Theorem 6.2, (i) e characterizes the augmentation strength (i.e., the perturbation on label-irrelevant information), whereas (ii) quantifies the margin robustness (i.e., the preservation of label-relevant information) for the expansion-based data augmentation. Ideally, we would like both and t to be reasonably large, while there exist trade-off's between the augmentation strength and margin robustness (e.g., overly strong augmentations inevitably perturb label-relevant information).
'In Appendix E.2, we further bridge the conceptual notion of DAC regularization in Equation (8) with common DAC regularization algorithms in practice like FixMatch [Sohn al., 2020].

---

Remark 6.1 (Clustering with DAC v.s. RKD). As Figure I demonstrated, in contrast to RKD that unveils the spectral clustering of population-induee innduced- graph from "global" perspective. DAC alternatively learns "local" clustering structure through the expansion of neighborkoods NB (.) characterized by sets of data augmentations A(:) (Definition 6.1).
Therefore, DAC and RKD provide complementary perspectives for each other. On one hand, the "local" " clustering structure revealed by DAC effectively ensures a reasonable margin in Assumption 4.2 (Remark 4.1). On the other hand, when the angmentation strength с is insufficient (i.e., A(-) is not expansive enough) for DAC to achieve low clustering error y (Fxx) (Theorem 6.2), the supplementary "global" perspective of RKD connects the ooverlapppinng neighborhoods in the same classes and brings better classification accuracies, as we empirically verified in Appendix
Discussions, Limitations, and Future Directions
This work provides a theoretical analysis of relational knowledge distillation (RKD) in the semi- supervised classification setting from clustering perspective. Through cluster-aware semi- supervised learning (SSL.) framework characterized by a notion of low clustering error, we demon- strate that RKD) achieves nearly optimal label complexity (linear in the number of clusters) by learning the underlying geometry of the population as revealed by the teacher model via spectral clustering. With unified view of data augmentation consistency (DAC) regularization in the cluster- aware SSL framework, we further illustrate the complementary "global" and "local" perspectives of clustering learned by RKD and DAC, respectively.
As an appealing future direction, domain adaptation in knowledge distillation is a common scenario in practice where the training data of the teacher and student models come from different distributions. Although distributional shifts can implicitly reflect the alignment between the ground truth and the teacher model (Assumption 4.1) in our analysis, explicit and specialized study RKD in the domain adaptation setting may lead to better theoretical guarantees and deeper insights.
Another avenue for future exploration involves RKD on different (hidden) layers of the neural network. In this work, we consider RKD on the output layer following the standard practice [Park et al., 2019], whereas RKD on additional hidden layers has been shown to further improve the performance [Liu et al., 2019]. While the analysis in Section 4 remains valid for hidden-layer features of low dimensions ( K), Assumption 4.1 tends to fail (i.e., can be large) for high-dimensional features, which may require separate and careful consideration.
Acknowledgement
YD was supported in part by the Office of Naval Research 900014-18-1-22 NSF DOE ASCR SCOS20022,5, and UT Austin Graduate School Summer Fellowship. KM was sup- ported by the Peter J. O' O'Donllll Jr. Postdoctoral Fellowship at the Oden Institute at the University of Texas, Austin. QL acknowedees the support of NYU Research Catalyst Prize and Whitehead Fellow- ship for Junior Faculty in Biomedical and Biological Sciences. RW was supported in part by AFOSR MURI FA9550-19- 19-0-000---005,, NSF DMS- 1952735, NSF IFML grant 2019844, NSF DMS-N2109155, and NSF 221 7033. The authors wish to thank IFML for generously providing computational resources, as well as the anonymous reviewers for their helpful comments and suggestions.
References
Z. Allen-Zhu and Y. Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.098166 2020.
J. Ba and R. Caruana. Do deep nets really need be deep? Advances in neural information processing systems, 27, 2014.
P. Bachman, O. Alsharif, and D. Precup. Learning with pseudo-ensembles Advances in neural information processing systems, 27, 2014.
P. L. Bartlett and S. Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. J. Mach. Learn. Res., 333411) Mar. 2003. ISSN 1532-4435.
M. Belkin and Niyogi. Semi-supervised learning on Riemannian manifolds. Machine learning, 56: 209-239 2004.
10

---

M. Belkin, I. Matveeva, and P. Niyogi. Regularization and semi remi-supervised learning on large graphs. In Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4, 2004. Proceedings 17, pages 624 638. Springer, 2004.
D. Berthelot, N. Carlini, I. Goodfellow, N. Papernot, A. Oliver, and C. A. Raffel. Mixmatch: A holistic approach to semi-supervised learning. Advances in neural information processing systems, 32, 2019.
A. L. Bertozzi and E. Merkurjev. Graph-based optimization approaches for machine learning, uncertainty quantification and networks. Handbook of Numerical Analysis, volume 20, pages 503-531. Elsevier, 2019.
J. Bilmes. Submodularity In Machine Learning and Artificial Intelligence. Arxiv, ab//2202.00111 Jan 2022.
T. Cai, R. Gao, Lee, and Q. Lei. A theory of label propagation for subpopulation shift. In International Conference Machine Learning, pages 1170-1182, PMLR, 2021.
Calder, B. Cook, M. Thorpe, and D. Slepčev. Poisson learning: Graph-based semi-supervised learning at very low label rates. In Proceedings of the 37th International Conference on Machine Learning, pages 1306-1316. Proceedings of Machine Learning Research, Nov. 2020.
M. Caron, I. Misra, J. Mairal, P. Goyal, P. Bojanowski, and A. Joulin. Unsupervised learning of visual features by contrasting cluster assignments. 2020.
B. Chen, P. Li, Z. Yan, B. Wang, and L. Zhang. Deep metric learning with graph consistency. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 982-999998 990, 2021.
G. Chen, W. Choi, X. Yu, T. Han, and M. Chandraker. Learning efficient object detection models with knowledge distillation. Advances in neural information processing systems, 30, 2017.
S. Chen, E. Dobriban, and J. H. Lee. A group- theoretic framework for data augmentation. The Journal of Machine Learning Research, 21(1):9885-
2020.
X. Chen and K. He. Exploring simple siamese representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 15750-15758, 2021.
E. D. Cubuk, B. Zoph, D. Mane, V. Vasudevan, and Q V. Le. Autoaugment: Learning augmentation policies from data. arXiv preprint
2018
E. D. Cubuk, B. Zoph, J. Shlens, and Q. V. Le. Randaugment: Practical automated data augmentation with reduced search space. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pages 702-703, 2020.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pallern recognition, pages 255-255. leee, 2009.
T. DeVries and G. W. Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv: 1708v:770..000 07777000455.. 2017.
C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika. 1(3)2211-218, Sep 1936. ISSN 1860-0980.
N. Golowich, A. Rakhlin, and O. Shamir. Size- independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR. 2018
G. H. Golub and C. Van Loan. Matrix computations. JHU press, Baltimore, MD, USA, 2013.
Gou, B. Yu, S. J. Maybank, and Tao. Knowledge distillation: A survey. International Journal of Computer Vision, 129:1789-188 2021.
J.BB. Grill, F. Strub, F. Altché, C. Tallec, P. Richemond, E. Buchatskaya, C. Doersch, B. Avila Pires, Z. Guo, M. Gheshlaghi Azar, al. Bootstrap your own latent-a new approach to self-supervised learning, Advances in neural information processing systems, 33:21271 12122224,, 2020.

---

J. Z. HaoChen, C. Wei, A. Gaidon, and T. Ma. Provable guarantees for self superviseeidd deep learning with spectral contrastive loss. Advances in Neural Information Processing Systems, 34:5000-501. 2021.
H. Harutyunyan, A. S. Rawat, A. K. Menon, Kim, and S. Kumar. Supervision complexity and its role in knowledge distillation. arXiv preprint arXiv:2301.122444 2023.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
G. Hinton, O. Vinyals, and J. Dean. Distilling the knowledge in neural network. arXiv preprint arXiv: 1503.0233,, 2015.
D. Hsu, Z. Ji, M. Telgarsky, and L. Wang. Generalization bounds via distillation. arXiv preprint a1Xiv:2104.05641, 2021.
G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger. Densely connected convolutional networks. Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
G. and Z. Zhu. Knowledge distillation wide neural networks: Risk bound, data efficiency and imperfect teacher. Advances in Neural Information Processing Systems, 33:20823-20833. 2020.
Kim, Park, and N. Kwak. Paraphrasing complex network: Network compression via factor transfer. Advances in neural information processing systems, 31, 2018.
A. Krause and D. Golovin. Submodular function maximization. In Tractability: Practical Approaches to Hard Problems. Cambridge University Press, February 2014.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Technical Report 0, University of Toronto, Toronto, Ontario, 2009.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84-9)) 90, 2017.
S. Laine and T. Aila. Temporal ensembling for semi-supervised learning. arXiv preprint arXiv:1610.02247 2016.
M. Ledoux and M. Talagrand. Probability in Banach Spaces: isoperimetry and processes. Science & Business Media, 2013.
Springer
J. D. Lee, Q. Lei, N. Saunshi, and J. Zhuo Predicting what you already know helps: Provable supe-supe learning. Advances Neural Information Processing Systems, 34:309-323, 2021.
Y. Liu, J. Cao, B. Li, C. Yuan, W. Hu, Y. Li, and Y. Duan. Knowledge distillation via instance relationship graph. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7096-7104, 2019.
Y. Liu, W. Zhang, J. Wang, and J. Wang. Data-free knowledge transfer: A survey, arXiv preprint a1Xiv:2112.15278, 2021.
A. Louis and K. Makarychev. Approximation algorithm for sparsest k-partitioning. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithmss, pages 12555 SIAM, 2014.
Y. Ma, Y. Chen, and Z. Akata. Distilling knowledge from self-supervised teacher by embedding graph alignment. arXiv preprint wtxXi:22/1./32260 2022.
A. Maurer. A vector-comtraction incquality for rademacher complexities. International Conference Algorithmic Learning Theory, pages 3-17. Springer, 2016.
Mei, T. Misiakiewicz, and A. Montanari. Learning with invariances in random features and kernel models. In Conference Learning Theory, pages 3351-3418. PMLR, 2021.
12

---

B. Mirzasoleiman. Big Data Summarization Using Submodular Functions. PhD thesis, ETH Zurich, 2017.
B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrák, and A. Krause. Lazier than lazy greedy. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
W. Park, D. Kim, Y. Lu, and M. Cho. Relational knowledge distillation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3967-3976, 2019.
A. Parulekar, L. Collins, K. Shanmugam, A. Mokhtari, and S. Shakkottai. Infonce loss provably learns cluster-preserving representations. arXiv preprint arXiv:2302.007920 2023.
H. Phan. auyymphan/pytorchhccffattt cifar10, jan 2021.
M. Phuong and C. Lampert. Towards understanding knowledge distillation. International Conference on Machine Learning, pages 5142-5151. PM....1..R... 2019.
Q. Qian, H. Li, and J. Hu. Improved knowledge distillation via full kereel matrix transfer. In Proceedings of the 2022 SIAM International Conference on Data Mining (SDM), pages 612-620. SIAM, 2022.
A. Romero, N. Ballas, S. E. Kahou, A. Chassang, C. Gatta, and Y. Bengio. Fitnets: Hints for thin deep nets, arXiv preprint 111.5514,, 2014.
J. Schreiber, J. Bilmes, and W. S. Noble. apricot: Submodular selection for data summarization in python. Journal of Machine Learning Research, 21(161):1-6, 2020.
R. Shen, S. Bubeck, and S. Gunasekar. Data augmentation as feature manipulation. In International Conference on Machine Learning, pages 19773-19808. PMLR, 2022.
P. Y. Simard, Y. A. LeCun, J. S. Denker, and B. Victorri. Transformation invariance in pattern recognition- tangent distance and tangent propagation. In Newral networks: tricks of the trade, pages 339-27444 Springer, 2002.
K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1556, 2014.
K. Sohn, D. Berthelot, N. Carlini, Z. Zhang, H. Zhang, C. A. Raffel, E. D. Cubuk, A. Kurakin, and C.-L. Li. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Advances in neural information processing systems, 33:596-608 2020.
U. von Luxburg. tutorial on spectral clustering. Statistics and Computing, 17(4):395 Dec. 2007. ISSN 1573-1375.
M. J. Wainwright. High- Bigh--Dimesiooal Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
H. Wang, S. Lohit, M. J. Jones, and Y. Fu. What makes a" good" data augmentation in knowledge distillation-a statistical perspective. In Advances in Neural Information Processing Systems, 2022.
L. Wang and K.-J. Yoon. Knowledge distillation and student-teacher learning for visual intelligence: A review and new outlooks. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2021.
C. Wei and T. Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. Advances in Neural Information Processing Systems, 32, 2019.
C. Wei, K. Shen, Y. Chen, and T. Ma. Theoretical analysis of self- telf-training with deep networks unlabeled data. In International Conference on Learning Representations, 2021.
M. Welling and N. Kipf. Semi-supervised classification with graph convolutional networks. J. International Conference Learning Representations (ICLR 2017), 2016.
S. Yang, Y. Dong, R. Ward, I. S. Dhillon, S. Sanghavi, and Q Lei. Sample efficiency of data augmentation consistency regularization. In International Conference on Artificial Intelligence and Statistics, pages 3825-3853, PMLR, 2023.
13

---

S. Yun, D. Han, J. Oh, S. Chun, J. Choe, and Y. Yoo. Cutmix: Regularization strategy to train strong classifiers with localizable features. Proceedings of the IEEE/CVF international conference on computer vision, pages 6023-6032, 2019.
S. Zagoruyko and N. Komodakis. Paying more attention to attention: Improving the performance of convolutional neural networks via attention transfer. arXiv preprint arXiv:1612.03998, 2016a.
Zagonuyko and N. Komodakis. Wide residual networks. arXiv preprint arXiv::605.00 146, 201
H. 7hang, M. Cisse, N. Dauphin, and D. Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.09411 2017.
D. Zhou, O. Bousquet, Lal, Weston, and Schölkopf. Learning with local and global consistency. In S. Thrun, L. Saul, and B. Schölkopf, editors, Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003.
Zhou, G. Cui, Hu, Z. Zhang, C. Yang, Z. Liu, Wang, C. Li, and M. Sun. Graph neural networks: A review of methods and applications. Al Open, 1:57-81, 2020. ISSN 2666-6510.
X. Zhu, Z. Ghahramani, and J. Lafferty. Supi-supe learning using Gaussian fields and harmonic functions. In Proceedings of the 20th International Conference on International Conference on Machine Learning, pages 912-919, Washington, DC, USA, Aug. 2003. AAAI Press. ISBN 978-1-57735-189-4.
14

---

A Experiments
In this section, we present experimental results on CIFAR-10/100 [Krizhevsky and Hinton, 2009] to demonstrate the efficacy of combining DAC and RKD (i.e. the "local" and "global" perspectives of clustering) for semi-supprvvise learning in the low-label-rate regime. The experiment code can be <nwpriidddd_Koleeeeeeeee
found at
We consider the (data-free) knowledge distillation setting, wherein the student model cannot access the training data of the teacher model. That is, the student models only have access to limited training samples, with very few labels, drawn from a potentially different data distribution than which the teacher model pretrained on. More precisely, given labeled sample set (X.y) y) of size and an unlabeled sample set X of size N (n < N) we train a student model (WideRes- Net [Zagoruyko and Komodakis, 2016b]) in the low-label-rate regime with as few as 4 labeled samples per class (i.e., 4K, or = 40 for CIFAR- 10 and 400 for CIFAR-100), along with N = 25000, 40000, and 50000 unlabeled samples (i.e., 50%, 80%; 100% of the entire CIFAR-10/100 training set).
Then, combining DAC and RKD, we solve the following objective in the experiments:
min FEF
CE (X.y)
+ ADAC ERAC (f) + ARKD Rx (f).
Supervised cross entropy
Unsupervised DAC loss
empirical RKD loss
ZCE where ((xx) (f) = 1 E.= lCE (VilJ (x:)) denotes the supervised cross-entropy loss with
ECE (ylf (x)) = = log ssoftmax (f(x)),, The DAC and RKD losses are as described in Equa- tion (9) and Equation (3), respectively. For the regularization hyper-parameters, we have ADAC = 1 and ARKD = 0 for DAC (only), while ARKD = 0.001 for DAC + RKD.
DAC via FixMatch. We take FixMatch [Sohn et al., 2020]-a state-of-the-art algorithm in the low-label-rate regime-as the semi eeni-supervised learning baseline. By combining RKD with FixMatch, we show that RKD brings additional boosts to the classification accuracy, especially with unsuitable data augmentations and/or limited unlabeled data.
Following the formulation and implementation in Sohn et al. [2020], FixMatch involves a pair of weak and strong data augmentations (x", x²) for each unlabeled sample x". For a current model f. the DAC loss given by FixMatch can be expressed as
(f) CRAC())
mean (AROr (ur (xx) (x))) max softmax
[(xx)) T
MAC, i i INT)):
where T' = 1 is fixed temperature hyper-parameter. DAC is the threshold below which the pseudo-label gauged on x!" is considered "with low confidence" and therefore discarded. We set TDAC = 0.95 for CIFAR-10 10 and TDAC = 0.8 for CIFAR-100.
In FixMatch, the weak augmentations include random flips and crops, whereas the strong augmen- tations additionally involve RandAugment [Cubuk et al., 2020]. To investigate the scenarios with unsuitable data augmentations and/or limited unlabeled data, we conduct experiments with various (i) augmentation strength (i.e., magnitude of transformations) m = 2, 6, 10 in al., 2020] and (ii) unlabeled sample size N 25000, 40000, 50000 (i.e., 50%, 80%, 100% of the entire CIFAR- 10/100 training set).
[Cubuk
We warm up with the in-distribution case in the CIFAR- 10 experiments (Table 1) where the teacher and student models are (pre)trained on the same dataset (i.e., CIFAR-10), Concretely, the teacher model e X' + W is a Densenet 161 [Huang et al., 2017, Phan, 2021] pretrained on the entirety of the CIFAR-10 training set (via supervised ERM).
RKD.
Taking a step further, we consider an out-of-distribution scenario in the CIFAR-100 experiments (Table 2) where the teacher model is pretrained on ImageNet [Deng et al., 2009] via unsupervised contrastive learning method-Sw [Caron et al., 2020]. Intuitively, we choose teacher models
1It is worth mentioning that, in practice, we relax the assumption of the independence between (X,y) and X and recycle X in X
15

---

pretrained via SwAV as it encourages both data clustering and consistency of cluster assignment under data augmentations without involving supervision. which tends to provide representations that generalize better in cluster-aware semi-supervised learning setting.
Given the teacher models, the output (response) of each sample is taken as the corresponding teacher
feature such that W I= In light of the empirical success of RKD based simple kernel functions [Park et al., 2019, Liu et al., 2019], we focus on the (shifted) cosine kernel, Kys (x, x') 1 1+
((x) v(x') in the experiments.
With data augmentation (e.g., when coupling with FixMatch), we assume that weak augmentations (i.e., random flips and crops) bring little perturbations on responses of the teacher model (i.e.. the teacher features), intuitively the predictions made by good teacher model ought be invariance under weak augmentations. Thereby, we can considerably reduce memory burden and accelerate the RKD process by storing the teacher features & (x) of the original data X offline, instead of inferring every augmented sample E A(x) with the large teacher model v (x') online.
Labeled data selection. As alluded to in Remark 5.2, the success of low-label-rate (i.e., < N) semi-supervised classification naturally depends on the quality of the (extremely) limited amount of labeled data to represent the underlying population. We perform experiments in which the selection of labeled data is non-adaptive (Uniform) or adaptive (StochastiGGreedy) The non-adaptive setting, Uniform, selects labeled data uniformly in each ground truth class" This contrasts with the strictly i..d sampling assumption used in our theoretical results but constitutes a reasonable alternative that has been used in other low-label rate supissupe classification works (e.g., [Calder et al., 2020]).
We also utilize coreset selection strategy (StochastiGGreedy) for identifying "representative" in- puts to use as labeled data in an adaptive manner. This labeled set is selected via stochastic greedy [Mirzasoleiman et al., 2015] optimization problem to (approximately) minimize facility location o An in-depth discussion of coreset selection methods is outside the scope of the current work, but we refer the interested reader the enlightening references [Bilmes, 2022, Krause and Golovin, 2014, Mirzasoleiman, 2017] regarding submodular optimization methods in machine learning.
Table 1:
Top-1 accuracy CIFAR-10.
Augmentation Strength Medium
Label selection
Sample sizes (n, N)
SSL algorithm
Hlgh
Weak
FixMatch
89.47 + 3.83
87.89 1.43
81.36 + 1.41
50000)
FixMatch RKD
89.88 0.41
89.10 1.14
84.61 + 1.23
Uniform
HixMatch
87.60 + 1.21
85.30 + 1.35
83.74 + 3.07
(40, 40000)
FixMatch + RKD
90.19 + 0.19
88.65 + 1.81
86.68 : 1.06
FixMatch
81.73
1.27
81.43 2.98
76.84 + 1.98
(40, 25000)
FixMatch + RKD
87.06 2.04
87.24 0.39
82.75 + 2.35
FixMatch
85.48
1.67
89.39 + 0.82
78.98 + 0.52
(40, 50000)
FixMatch RKD
91.19 + 0.26
90.00 + 0.64
87.11 + 4.33
StochasticGreedy
FixMatch
84.51
1.34
84.88 + 6.68
70.70 + 5.32
(40, 40000)
FixMatch + RKD
85.68 + 1.19
88.31 + 1.36
85.12 = 3.49
FixMatch
79.74
8.02
73.97
1.98
73.86 + 3.29
(40, 25000)
FixMatch RKD
83.72
4.73
82.09
3.27
80.65 + 3.67
Results. From Table I and Table 2, we observe that the incorporation of RKD with FixMatch (i.e., adding the "global" perspective of RKD to the "local" perspective of DAC) generally brings additional improvements to the classification accuracy, especially when the data augmentation strength is inappropriate and/or the number of unlabeled data is limited.
For fair comparison and consistent performance among different configurations in the experiments, a separate random number generator with a fixed random seed to ensure that the same set labeled samples selected for all experiments. We use the Apricot [Schreiber al., 2020J submodular optimization codebase in Python.
16

---

Table Top-1 accuracy on CIFAR-100
Augmentation Strength Medium
Lahel selection
Sample sizes N)
SSI. algorithm
High
Weak
FixMatch
46.85 1.68
45.67 0.51
45.84 + 0.35
FixMatch RKD
49.33 0.42
47.97 0.37
47.65 = 0.17
Uniform
FixMatch
44.11 + 0.51
42.98 + 0.56
42.74 = 0.42
(400, 40000)
FixMatch RKD
46.24 0.64
45.78 + 0.94
45.13 + 1.08
FixMatch
36.60 0.03
35.86 + 0.51
33.59 + 1.54
(400, 25000)
FixMatch + RKD
37.87 0.98
36.69 + 0.41
35.69 = 1.51
FixMatch
47.45 0.30
48.64 0.35
46.79 = 1.05
(400,, 50000)
FixMatch RKD
50.41 1.41
50.67 1.62
49.09 + 1.31
StochasticGreedy
HixMatch
45,93 + 0.21
44.78 + 1.51
44.62 + 0.72
(400, 40000)
FixMatch + RKD
47.62 + 0.67
47.28 + 0.56
46.07 = 0.86
FixMatch
39.40
0.68
38.22 = 0.42
(400, 25000)
FixMatch RKD
40.88
40.73 0.46
39.20 = 0.73
Training details. Throughout the experiments, we used weight decay 0.0005. We train the student model via stochastic gradient descent (SGD) with Nesterov momentum 0.9 for 2 iterations (batches) with batch size 64 8 = 2 (consisting of 64 labeled samples and 64 unlabeled samples). The initial learning rate 0.03, decaying with cosine scheduler. The test accuracies are evaluated 2 times in total evenly throughout the 217 iterations (i.e., one test evaluation after every 2 iterations) on an EMA model with a decay rate 0.999. The average and standard deviation of the best test accuracy (i.e., early stopping with the maximum patience 128) reported for each experiment over 3 arbitrary random seeds. Both CIFAR-I0/100 experiments are conducted on one NVIDIA A40 GPU.
B Proofs and Discussions for Section 5
B.1 Proof of Theorem 5.1
Lemma B.1 (Rademacher complexity with cluster-aware functions (generalization of Yang al. [2023] Theorem 8)). For fixed FL(x"). let
lo F = - (0,1) FL(X)}
be the loss function class. Then, its Rademacher complexity can be upper- upper-bounded by
2K log(2n)
Ri FL(x))) S
2p (Fr(x")).
(10)
n
Proof of Lemma B.I. Given a set of i.i.d. samples (X,y) ~ P(x, y)" 10",,, let
G (lo FL(x.)) ((((
(f un))
FL(x))]
denote the number of distinct patterns over y) in o Fi(x"). Then, by Massart's 's finite lemma, the empirical Rademacher complexity with respect to (X,y) is upper bounded by
2 2og (6xx)) (eo FL(X")))
Rix)) (e Fr(x)) s

---

By the concavity of Vlog (.), we know that,
Ri FL(x))) -b(x)))
D (xx)) (e FL(X-))
2 (G(x.)) (ko F(ix))
(11)
2 log (Bxx,) (6xx (e (((x))))))
n
Since P (M())) E (Frxx)) s for all f E Fiixo,; by union bound, we have
Exx)) (xxM)) (eo FL(x)))
( "1 ---+1 min (K, 1}
pb (FExH)) (1 p (Fr(x))))
A=0
n {(2 Σ
(12)
(2 (Fixx))) (1- (Fi(x)))
=(2m)* K (1- 1 (Frxx)) + 2p (Frxx=)))"
S(2n) K (F
where & counts the number of minority samples in the samples. Plugging in this last line into Equation (11) yields Equation (10).
Proof of Theorem 5.1.
Since 6 F is 1-bounded with the zero-one loss f, Lemma F.1 implies that with probability at least 1 - 8/2 over (X
& (fxx)) E (f+) S 4R, (eo FL(X")) + 2 log (4/8)
Then, incorporating the upper bound of R. (e FI(())) from Lemma B.1 completes the proof.
B.2 Cluster-wise Labeling with Cluster-aware Predictions
Recall the notions of majority labeling (-) (Equation (2)) and minority subset M (f) (Definition 3.1). We first specify the cluster-aware predictions that are useful for labeling with the following non- degeneracy assumption.
Assumption B.1 (mm, co) -en-eeeeeraeee predictions). For any prediction function F, say if is (mo: co) -nonddegeneatee if the following properties are satisfied:
(i) Vf X [K] is surjective (i.e., {us (x) x X) = (K])
(ii) X 2 for all le [K]. where define x A fxE (x(x) k}
(iii) There exists some co such that co P (M()) < P (x() for all k [K].
It is worth pointing out that although the majority labeling ūy(:) depends on the ground truth and therefore remains unknown without label acquisition, under Assumption B.1, the associated partition over X' depends only f and is known without labeling. This is because yy (-) and { [xf (x KE[K]
(-(-) induce the same partition over &' when both y-(-) and 7-(+) are non-degenerate (i.e., being surjective functions onto [K] a necessary condition of Assumption B. (i) and (ii)). We also notice that Assumption B. (iii) can be generally satisfied with reasonably large when learning via Equation (3) with a sufficiently small μ (Fi(x")) (cf. Theorem 4.1 or Theorem 4.3). For example, when co y (FL(x))) S minkek P (x:() Assumption B.1 (iii) is automatically satisfied.
18

---

With the cluster aware predictions in Assumption B.1, we show that O (log( K)) i...d. labeled samples per predicted cluster are sufficient ensure at least one labeled sample per class. That is. the cluster-wise labeling with (mo; (o)-non- non-degenerate predictions guarantees a label complexity of O (K log(R) ()) even with class imbalance.
Proposition B.2 (Cluster-wise labeling). Given any (mo, co) -non-degenerate prediction function f F (Assumption B. 1) with sufficiently large my > logco (2K) and co 2 2, for each k E [K]
acquire labels of m (m S ma) unlabeled samples {x [sm[m)] ~ Unif (x)) drawn ii.d. i..d. from Xy-
2K 1)). when m +Logeo (2 {y- (x)))) RE[[]) [K] have at least one
Then, for any å E
ground truth label per class with probability at least - 6.
Proof of Proposition B.2. We first observe that
P [v/ (xx+ (eEKK))) [K]]
-P -P E [K], 3 le E [K] i [m]] s.t. ya (x%+ k']
PP 1: E [K], li [m]] s.t. ya (xxx) k)
K
II
P [xx (xj Un)((())) Bi E [m]] s.t. y- (x%+) k),,
k=
where
P PBic E [m]] s.t. y+ (xxx) = k] =1 P A i [m]] yo (xxx) # k]
P XxxUUii(xx() [vo (x) + of (x))
=1
(P (xxUii((xx)) [x M()))) m
P (M(())
=1
P ((x)
Since Assumption B.1 implies P ( (M())x
/ (xz)
S L for all k E [K]. we have 6u
K
PP [v. (x (E()) = [K]] 2
[
1
2 exp
2K
2 1
2K 6
where the second and the third inequalities follow from the facts that 1 - q 2 exp (-2g) for all
1 and exp (-q) 2 q for all S q S 1, respectively. It is straightforward to observe S g S 2 that when m 2 logco (2x) ). we have 2K < 8. With minke[K]
x = mp. taking up to m S mo
2K unlabeled samples for each k E [K], we can achieve as small as òmin 2
C Proofs and Discussions for Section 4.1
In Appendix C.1, we proceed with the proof of low clustering error guarantee (Theorem 4.1) for minimizing the population RKD loss (Equation (I)). In Appendix C.2, we extend the discussion in Remark 4.1 on the limitation of spectral clustering alone the end-to-end setting via an illustrative toy counter-example, In Appendix C.3, we clarify the connection between our results and corresponding spectral graph theoretic notions of sparsest k-partitions.
C.1 Proof of Theorem 4.1
Given any labeling function y X + [K], let / X + 10.13* be the one-hot encoded la- beling function such that for y (X') E [K|| (x) 10, 1 Further, given E F,
= denote Ux A D (2) Dy (2'), Fx A D (2) f (x), and Yx - (2x) (X²) such that
Uv. Fx, Yx g|
19

---

Since L(x) = I (()), the classical argument with Gershgorin circle theorem [Golub and Van Loan, 2013, Theorem 7.2.1] implies that x ((x) < 21, whereas ky being positive semi- definite further implies that ((+) > and therefore 0 & L(x) < (see the proof of Claim C.3). Consider the spectral decomposition of L (2) = I ((X),
IX
A (1- -v.V (13)
L
Σ 1=1
A
V.V.
s.t. D( 1/2 W (X)
Σ ==1
where {v; E
J "Elli ] are the orthonormal eigenvectors associated with \1 S ... S Ax1 S
1, respectively, that form a basis of [Rl
Lemma C.I. Given any f E F that satisfies Assumption 4.2, we have
(M(()) = Ex-r [1 (ūp(x) # (x))) & max
72 (2:1)
182
Y - Fx ZERAXK
min
Proof of Lemma C.I. Without ambiguity, we overload the notation of each sample E X as the corresponding index in [[x[]] such that, given any sample subset S = [(S))e][ss] C X, following
the MATLAB notation for matrix indexing, I |x] () R|xx 31 where ||x denotes the
| x | identity matrix. With respect to S, we also denote Fs - Fx (S,:) = _J x and
Y s - Y x (S.:) = I1 Xx.
We first show that for any S ssi.... E X that satisfies rank (Fs) = K,
Yx x Fx Y
< min F
-XxxFxx> - Ex
(14)
ZERKXK
To see this, we start by replacing Z on the right-hand side of Equation (14) with the corresponding least square solution such that
|| Fx Yx - FXF Yx |
min ZERK X
where F Fx)
FT. Then, we can decompose the left-hand side of Equation (14) via the
orthogonal projection Fx F
Y - Fx s Y s11 2
I (I- ExF1 (Yx - Fx Y
F + Fx (Yx - Fx
Yx - FxF Y
[Pp [PF-FB Pps) Xxll.
where Pp A Fx
Fx (F)F.)) F and Ps Fx (II,Fx)
"I. By observing that
PsPF = Fx [15
F2 (FXEx)
FI = Pf = PFPF,
we can upper bound ||(P Ps) Y xx1 such that
[(Pr - Ps) Yx1 = |PPr Ps) (I PP)
S S (I Yx112
Yx -x= p
which leads to Equation (14).
Now, consider the sample subset S E K described in Assumption 4.2. For given E F, partitioning X' into the majority and minority subsets, X²) (J) and M(),, respectively yields
Y - FxF5'Y
= =(1- (1- P(M())) Exx
f(S)- [[T (S) [(S) T f(x) x x M[n]
+P(M(f)) ExxP(())
P(x)
f()) [|] 11610 x M(S]]
2P(M()) ExxP(x)
[x) [(S)) [
20

---

Since 8& & M(S, we have (S) 3
()( whose rows lie in the canonical bases of for IR. ] whereas for E Mf), we have vx(x) # (x). Therefore, in the case when (x(x) = (8x) for some & E [K],
[x) V. (S) ( ((())-T((x))
-||(S)) T (S(S) T (S) (x) f(x))
2 (S(S)-T)² [(x) Σ [(8k)
(x)=), (8x)
where ox (I(S)-T) 1/8, and with (8() va(a)) (x(x) # ū)(() implying (sL)) # vr(x),
((x) Σ
[(Ax) 27,
(x)
we have
12
[x2(x) (S)
((S))S(TA- f(x) 11 2
Meanwhile, in the case when y. (x) # yo (sx) for all & E [K], we have (S())) (x) 0, and therefore
(x) - (S) f(s) - f(x) 2 ス (x)
- (Z) f(s) TT f(x)))l² 1.
Overall, we' ve shown that
Exx [ - - f(S)- T
f(x))12 ( (115)-T((x)))
x 2 min
Ba 1)
which leads
1.2 || - FxFF Y|
P(M()) < max
(15)
Finally, combining Equation (14) and Equation (15) completes the proof.
Lemma C.2. With yı E [0, 1] x1 denoting the k-tth column Y - DxX) ( [0, 1]
Σ y L (x) =a.
KE(K]
Proof of Lemma C.2. It is sufficient to observe that, by construction, for every ls E [K],
[x) y - (2 -122
Σ uxx (xx(x)= k} - Σ Σ
Wxx 1 (y=(x) = =k] 1 tu (x') = =b}
XEX
XEXX'XX
Σ 18 (x)= = =k} Uxx Σ
Wxxx 1 (x+ = vx((2))
xeX
X'EX
Σ 1y, = =b} Σ
W Wxxx (xa # y. (x')).
XEA
x'E
Meanwhile, since ExEx ExEE Wxx = 1, we have a = EkE[K] ExEx, Exeex Wxx and
Σ ( = Σ
Wxxx (1-(x) + y. (x')
Σ I (x) k]
KE[K]
XEA X'EX'
kE[K]
Σ Σ Wxxx (va(x) + xx')3
xEXx'R
Uxxx = a.
xE(K)xxXxx X
21

---

Claim C.3. For all f E FL(x) minimizing Equation (1), Range (D(X)
span (V1y...; VKk).
Proof of Claim C.3. Since 0 & L(X) & 21, we have -I & ky (X E R x be the population kernel matrix such that kw (2, X) x)xx = ky (x,x'). Then
W(X) I. Meanwhile, let
by defintion, ky (X, X) = ((X) - (()))(())))))) and therefore
W (2) = (x) ((2) = D (X, D(2)* > O.
That is, the eigenvalues of (( and those W (At) satisfies
A _ X; (L())
- ((()) ViE e |x]]
while the cigenvectors are shared such that, with the spectral decomposition of L(X) in Equation (13),
((X) = Σ (1-A).v.V) ==1
Therefore, the K eigenvalues of (2)) of maximal modulus correspond exactly to the eigenvalues of ((x) that closest the eigenvalues whose eigenspaces relevant for spectral clustering.
Recalling Fxx (x)* f (X), we can rewrite Equation (1) as
R()) W (X) Fx x
follows directly from the Eckart- Young- Mirsky theorem [Eckart and Young, 1936] that Range (Fx) the subspace spanned by the eigenvectors VK = .V.....,V.. E x|* associated with the maximum K eigenvalues of WXX):
FL(Z) = { E F E kxk s.t. D (X)= (x) Vxz}.
Proof of Theorem 4.1. Recall Fx & 1x) (X), Yx & (X) V. (X),
1/2 [0, X be the k-th column of x. Leveraging Lemma C.I, we have for any F,
X)), and let Ys
82
(M)()) 52 max
min ZERRXK XK
| Fx
722
=2 max
72
min
Σ lly Fx
(2*ER BREERJaeIM R[(K]
jel x associated with eigenvalues \1 s For every & [K], (yx Fxzz) R|22 can be decomposed as the linear combination of (vi]seliz)) such that
Recall that the orthonormal eigenvectors {v, [R! & lalk of L (X) form basis of IR x
Iyx F 2
Σ i=1
(v. (yx Fxzz))
Meanwhile, Claim C.3 implies that, for f E FL()) with Vx = [VV..... vKl E XXX,, we have
Range (Fx) Range (Vx). That is, v. Fx = 0 for all > K, and by taking
K
2 = Fx) Vkya
(v. (y Fx2x))²
Overall, for every & E [K], there exists Z E R such that
|
y: L <
|lyx - F Ex20112
Σ
(vTyk) S AR+1 i=K+1
Σ
A 4-vV
Ax+1
i=
22

---

and Lemma C.2 implies that
yk L a
min
Σ
1ive
Fxzi
Σ kE[K]
( JEEINI RE[K]
AK+1
AK+1
which completes the proof.
C.2 Limitation of Spectral Clustering Alone
To ground the discussion in Remark 4.1, here, we raise toy counter-example where spectral clustering alone fails to satisfy Assumption 4.2 and suffers from a large clustering error. Intuitively, such a pitfall of spectral clustering is caused by suboptimal choice of basis for the predictions f() in Equation (1) due to the inherited rotation invariance of the minimizers of R(f).
Example C.1 (Pitfall of spectral clustering alone). We consider binary classification problem with two balanced ground truth classes {X,, X2) perfectly partitioned in Gx as disconnected components. Then, when the prediction yf (x) 2 argmnaak K] (x)x is made with uniformly random break of ties, Equation (1) alone suffers from p (F((X) 2 3 in expectation, due the violation of Assumption 4.2.
Nevertheless, with few one labeled sample per class {(x;,)) | 1,2), weak supervision via the cross-entropy loss
2
Ler (f) (f) Elog (softmax (ʃ (xx)):
min JEFU
facilitates satisfaction of Assumption 4.2 with a provably large margin 7,. For instance, assuming [x)(x) S (I)( S 3 and ux = 1/1x1 for all x E X (simplified for illustration purposes), for any f FL(X) under weak supervision such that
S { log (1 (1+6-v20) s Ecr(f) < log (1+ + +
Assumption 4.2 is satisfied with
72 - log (cEce()) -1) 2,32 - log (cBee(1))) -
In particular, with the minimum feasiblle cross-entropy loss Σce(f) log (1+e))2)) we have 2 v28.
We remark that with DAC regularizations like FixMatch [Sohn et al., 2020] and MixMatch (Berthelot et al., 2019], model predictions are matched against pseudo-labels that are gauged based on data augmentations, usually via the cross-entropy loss. Therefore, DAC has analogous effects the margins of the learned prediction functions f as the additional supervision described above.
Moreover, when coupling Equation (1) with the conventional KD (i.e., feature matching), the learned prediction functions f inherit the boundedness and margin of the teacher model, which are presumably satisfactory.
Rationale for Example C.I. Recall that A .... lakly are the eigenvalues of the graph Laplacian (X) = W (x), and ( | } be the associated normalized eigenvectors. For binary classification with (21,21) perfectly separated in Gx, we can write λ1 A2 0, while {x X+}
V1, V2 are the scaled identity vectors of N2. respectively, such that vx(x)
for 1,2.
By denoting V Iv1, val x| the Eckart- Young- Mirsky theorem [Eckart and Young, 1936] implies that, for any orthogonal matrix Q = [q qul E 2
(x) = (x)- Vz diag (1 Λ1, 1 - x2) = VvQ
V2Q qi for E X;, i = 1,2.
is a minimizer of R(f) in Equation (1). That is, f(x)
1
23

---

Spectral clustering alone. However, by taking qı = 1 [1:1] and q2 - [-1 with
y2 uniformly random break of ties, the corresponding E FL()) will misclassify half of x Xi as X2 in expectation. Then, since P ((t)) P (2) 2. by Definition 3.1, we have M(f) {x Ei (x) = 2} such that μ (FLex) 2 P (M()) = in expectation.
Spectral clustering in Example C.I fails to yield low clustering enror due to the potential violation of Assumption 4.2. For example, consider any prediction function f E FL(xx described in Example C.I.
(i) When x Wx S Hi recalling Sk = x f(x)& and f(x) =
V qi for x E X; such that, since | |/2]/
81 E XI,
82 E arginax f(x)= argmax XEX\M()
argmin wx C Ni,
(( V u X
xEX)M(()
there does not exist a skeleton subset S = [s1: 82] as described in Assumption 4.2. (ii Otherwise, suppose one can find a skeleton subset Without loss of generality, by taking (argmin wxx ( n. (f) A 0 in the problem setup, there exists M(f) Xi (with ys yx(x) 2) such that ux I Wai Therefore,
[$1; 82] as described in Assumption 4.2.
71 - (S1)
max
f fxx) S
S
XE M() (1)
(2wss
22nxx X
implies trivial margin y S O, which violates 7 > O in Assumption 4.2.
With additional weak supervision. We first observe that for both E [2].
log (softmax (f (xx)), S eCCR(f),
which implies that f (xx1] - 2 - log (foe((-11) f (x2), f (x2); 2 -log (cRee(()- -1)
where - log (c(cu(1))) 0 since [CE(s) < log (1 + (e < <2)g(2).
Since we assume [1](x)]12 S B for all x E X. (x:)] + (xi)² S B2 for both 1,2, we therefore have
(xx); - (x2), 2 llog (
V232 -log (clcx(1) -1) -1)²
This similarly holds for (x2)2 f (x1)2
Recall now that f(x) /usl/xs qi for x X, i 1,2 and x4 E X, for i 1,2. Assuming
Wx = 1/ |X| for all x E X. we have
Wey f (x1)
(xi), x X
f(x)
ux
Ux2
f (x²) f (Xe), X X2
mxx
Therefore, 71 2 f (x1); / (x2), and 72 2 [x222 - (x1))2 which together imply that
7 2 - log (goou()))) 12 2,32 llgg (GEce(()11 2
Now examine the two extremes of log (1+ (1+0) s [CE(f) < llog (1 + e-²). When the cross-entropy loss achieves its minimum feasible value ECE(f) = log (1+E- v28)) we have that
2 /28, whereas the margin can be nearly trivial y 2 <CB with ECE - 0 when the cross-entropy
loss is on the larger side (CE(f) + log (1 + 9).
24

---

C.3 Connection with Sparsest k k-partition
We now identify the connection between the eigenvalue Ak+1 and spectral graph theoretic notions of clusteredness of the underlying graph. We recall the notion of sparsest k- E-partitions [Louis and Makarychev, 2014] based on the Dirichlet conductance of subgraphs.
Definition C.I (Sparsest k- h-partition, HaoChen et al. [2021] Definition 3.4, Louis and Makarychev [2014] Problem 1.1). Given a weighted undirected graph
(X, w). for any E [[X]], ler
(S UsETa S; X, St Sj 0, S; + 0 Vi + J. i,j E [k]] be the set of all k-partitions of G. The sparsest k-partition of G is defined as
Øk min max (S;)), (8iliejM ES vE[k)
where (5( & ExxsExees wxxx)
(Exes wx) is the Dirichlet conductance of S S X.
It is worth mentioning that dhe is non-decreasing function in k [HaoChen al., 2021]. In partieular, dx = 0 when the graph has at least k disconnected components; whereas Ax+1 > 0 (Assumption 4.1) implies that ΦK+1 >
Meanwhile, Louis and Makarychev [2014] unveils the following connection between the sparsest k-partition of the graph and the k w'th smallest eigenvalue of its graph Laplacian:
Lemma C.4 (Louis and Makarychev [2014] Proposition 1 1.2). Given any weighted undirected graph G= (X, w), ler 0 = x1 S .... I laly be the eigenvalues of the normalized graph Laplacian in the ascending order. For any k, k E []. k < W, there exists partition {Si)se(w) E S of X such that, for all i E [k).
- k1)
Φa (Si) S poly
Vlog (k:) AR-
Leveraging the existing result Lemma C.4 [Louis and Makarychev, 2014] from spectral graph theory, we have the following corollary.
Corollary C.5 (Clustering in terms of sparsest k- d-partitions. Under Assumption 4.1 and Assump- tion 4.2 for every FL(X), error of clustering with the population (Equation (1)) satisfies that, if 0 and ΦR for all l [K], then
32 (Fr,x)) S max (22 poly K K+1-
k
log(k) a ØK
We also notice that when a = 0, Theorem 4. automatically implies that (Fi(x)) = O. Intuitively,
Corollary C.5 implies that except for the partition of the K ground truth classes {~' [J] (i.e., when
a > 0), Gx cannot be partitioned into other components by removing a sparse set of edges from Gx-
Proof of Corollary C.S. Lemma C.4 implies that for any &s [K], there exists partition {Si)eeH) of X' such that
k
Φk max de (St) S poly
K (+1-k)
v
Vlog (k) AK+1,
<E(k)
and therefore
k poly
1
<
log(k)
AK+1
K +
0
which completes the proof when recalling Theorem 4.1.
D Proofs and Discussions for Section 4.2
Here, we show that Rx- (f) shares the same minimizer the population Laplacian regularizer
R(f) in expectation (Proposition 1. and provide generalization bounds for Rx- (f) (Theorem 4.2)
accordingly.
25

---

D.1 Unbiased Estimations of Population Laplacian
Proposition D.1. Rx-(f) (f) (Equation (3)) serves as an unbiased estimate for R(f) (Equation (1)):
R (f) Exx~ P(x) Rxx (1)
Proof of Proposition D.I. We first observe that R(f) can be expanded as following:
R() -
W ((X) - D())) T D(2)
| 1.- [ D(X)+ 2
- 2tr (W(x))(2)
"
Σ Σ
2wxx f(x) _ f(x' + wx (f(x) f(x'))
Wxxxx'
Σ Σ WxWxx' ((
Wxxx WxxWx
2
200xxx' f(x)) f(x') + (f(x) (f(x) f(x2)))
Wx Wix
XEXX'XX
Then, with ks (x,x') = Woee! "
Rx (f) in Equation (3), Uxx = P (xx), and wix = P (x'), we have
R (J) = Pxxx Ri (x,x') 2kgp (x, x') f(x) f(x') (f(x) [(x)))]
(J(x) [xx)= kis (x, x |
P(xx
N/2
Σ
T f (xx) ( (xx
Ks (x xxxx)
R (5)
=Exe~P(xNN
D.2 Proof of Theorem 4.2 Proof of Theorem 4.2. By defining
(f) (f(x) - kp (x,x'))²
we have R(f) Ex.x' Fxx (f) and Rix (f) 3/ >N// Fx:: Px x2x (f) as
2 N/2
xx (f)
T f (xx)) ky (x (x²%
1, x
N iml
N/2 where (xx%)11)X)) ==1 are i.ddd given X P(x) N. Consider the function class
oF (F. X RRS
Since 0 < x') < BRg and by Cauchy-Schware inequality, f(x) f(x') < (x((x))l2 [1((x))1 S By, we have 0 S (f) S (Be, + B,)² for all x, x' E X, which means that F.. Fis (Bx, + B,)² 2 -bounded. Leveraging Lemma F.I gives that, with probability at least 1 - -/22 over X",
log (4/5)
R (f(x.) - -R (fix) 1 44Rn/2 o +2 + +B))²
V
N
26

---

S Now, it remains to show that 2x/2 oF) / (By + Bx RNyz2 (F). For this, we recall Equation (4) and observe that
N/2
Ryy2 (P., o F) =Ex ~Px)
sup FEF N
Σ Pi (f(x)))) (x2x:) kv (xi) 1x x25 1=1
PrRRad
where with Talagrand's lemma [Ledoux and Talagrand, 2013, Theorem 4.12] for compositions with scalar Lipschitz functions,
N/2
2 N
RN/2 (f., oF 22 + BRO) Exx,
sup FEF
Σ
Pi f (xx (xx)+))
(x f [(x)) S (IIs (xx; 11+ I11 (x))
Since
N/2
Ex p
sup
Σ Ps. (x) f (xxx1)
SEF N
t=1
N/2
<Bx',p .p
sup
Σ 1 i=1
(Iss (xx, (x + IIS (xx))
FEF N
N/2
2 N/2
1
Ex
sup /EF
Σ i=1
Pi ||ʃ (x 1
+ Exup
sup (EF
Σ ps . ||ʃ (xx))1
2
N
N/2
=Ex=.p
sup /EF
Σ
Pi |l (xx))1
By the vector-contraction inequality for Rademacher complexities [Maurer, 2016, Corollary 4], since Ilf (x)1l2 2 is B in f(x), with f(x)x denoting the k-th entry of f(x) E R
N/2
2 N/2
2 N
Ex
sup feF
Σ Pt
(x%)
< 2 E
sup JEF N
ΣΣ
Psk f (x+))
X(x) Rad 2 X
==
=2 22//2
Overall, we have Rxy2 (f,, FF) 4/2B, (By + BRx) RN/2 (F) which completes the proof.
D.3 Unlabeled Sample Complexity with Deep Neural Networks
Here, ground Theorem 4.2 by exemplifying (x)2(F) leveraging the existing generalization bound [Golowich et al., 2018] for deep neural networks.
Claim D.2 (Rademacher complexity of deep neural networks [Golowich al., 2018)) Recall the notion of Rademacher complexity for vector-valued function class F 3 f X + R from Equation (4), Adopting the existing results in Golowich et al. [2018] and following the notations in Section 6, we consider F as a class of deep neural networks:
F = (f(x)= = AA (... A2x(A1 .... ||A.||F V.E (p)
with weight matrices (A [p]} and 1 1-Lipschirz, positive-hoomogenen activation function & (-) (e.g., ReLU) applied entry-wisely. Let B, = II B and ||x|| & Bx for all x E X. Then, by Golowich et al. (2018) Theorem I, we have
Rx)2(F) < (2/llo((2) v²) KBx
N
27

---

D.4 Proof of Theorem 4.3
Proof of Theorem 4.3. Let Uxx _ D (2) f(x (x), & (x)) fix (2), and y E [0, 1]
be the k-th column of Yx A D (x) 1/2 (X). We denote Pu & UxUU2 as the orthogonal projection onto Range (Ux)) and PJ - I as the orthogonal complement of Pu.
Recalling from the proof of Theorem 4.1, Lemma C. implies that for all Six
E FFL(X")
g Σ KE[K]
182
P (MM(fxx)) $2 max
min Ily: Ux = max ZERK
Σ kE(K]
|
?2
where the second equality comes from taking z; = Uxy+ for every & E [K].
Consider the spectral decomposition of L (X² in Equation (13). Since the orthonormal eigenvectors
{v: E TR! ]
associated with eigenvalues 0 = A1 .... I laxy S 1 form a basis of TR. TR!
by denoting Vx= - [Vi...., E
IR x| and V _ [VK+I....., Maxi E g for every
E [K].
[
P 1
Σ p
V ((V)) P
i=1
is shown the proof of Theorem 4.1 that
Σ
(Vv)
Puya | S Σ ((vb) yx S a kE(K]
Ax+1
KE[K]
whereas by observing that 1ly = ExEx uxx 1 {y- (x) k- = P (XX))
Σ
Σ
lly 1 PPUVl = |
Σ ((t)) |
KE[K]
KE[K]
kE[K]
Overall, have
1 ( Xx=1
((M(f(x)) S 2 max
(16)
Upper bounding
V We first recall from Equation (13) that W(X)
Σ (1 A.) For fIx E FL(X), Eckart- Young-Mirsky theorem [Eckart and Young, 1936]
implies that Fx = E (1 - Ax) V.V. and
R((xx) W(X) - Fx Fx F
11-A))
11-
F
iS
Therefore, R((xx) S RR (fix)
A implies that
Σ (1 11) +A 2 W (X) U
Pu -
+ (Po U l
O
P W(X) + PU (WX)) - Ux 12
(since PU and Pt are orthogonal)
= = W (x)
F +
PU (W(X) U2 U
|2
> PP
(1 Ax) (Ptv.) vT
Σ ΣΣO
(1- X.) ()) viv, v
tr
1=
|20
(1 x
Ptv.
(17)
28

---

Meanwhile, the assumption A < (1 xx)² implies that rank (Pt) = | - K, and thus
Σ
P 1 = | = tr (Pt) = rank (Pt) = | - K.
(18)
Otherwise by contradiction, suppose rank (Pu) rank (Ux) < K, then Eckart- Eckart-Young- Young-Mirsky theorem [Eckart and Young, 1936] implies that
[ Ea- 11-~)>> + (((x)) +A.
min < W(A) - U UXU
2 K
1
which contradicts R (fixa)= S R (fix) +
Furthermore, since ||vil12 and p is orthogonal projection, for all E [[2]],
P S1.
(19)
For every E [|x]]] denote & be recast as a linear programming problem:
Then, upper bounding || xll
EEE E can
2"
K Σ
(P)
max EERIAT
i=1
s.t.
S & 1
K
(20)
Σ & = ||| - K,
Σ (1- S
E
k>
whose dual can be expressed as
(D): (Wi w )
min
Σ Wi (121 K)ws +
A A+E (1
E(-- (1-11)² 21)3 WA
s.t. W1, ... ilxim: W,. w. Ws 20,
(21)
wi W. + (1 - -1, 2 VisK,
wi We + (1 (1- 20 vi>K.
By taking
Wi O Vi S Ko.
(1 AKo 1 (1 2x)²
W1
Kg, <isk,
Axo)) (1 Ak+1)
(1 2x+1)) - -(1 22,)²
Wi
AK vK+1 |I|
(1 Ako)) - -11 =
1-Ax+11) )
We
(1 >xo)² 12 -(1 >x+1)) 2
1
WA
(1 (1-xxo) -(1 ->xx+1) 21
)xx))
29

---

the dual optimum can be upper bounded by
K
(D)
W
WA
1=1
A
(1- Ako) - (1-
(1 AKo) 2 - (1 - Ak+1)
k= (1- \xo) )= - - -11-1
(1 (K Ko) Cx.)
(1 ) )² -(1 2K+1)²
given Ck. & (1-Ak,) -(1xxxx) O())
A
With both the primal Equation (20) and the dual Equation (21) being feasible and bounded, the strong duality then implies that
K - (P) (D) (P)
(1 + (K Ko) Cko) A
(1 Xx,) )² - )x+1) 2'
which, when plugging back into Equation (16), completes the proof.
E Proofs and Discussions for Section 6
E.1 Expansion- based Data Augmentation
For the detailed analysis, we further recall the following notion of constant expansion and its relation with the concept of c-expansion Definition 6.1 from Wei al. [2021].
Definition E.1 ((q, connstannt expansion [Wei et al., 2021J). We say the expansion-based data
augmentation (Definition 6. I) satisfies (4, -constant expansion for afforayyS... S C X such that P(S) q and P (S) < P (Xx) for all k E [K].
P (NN((S)) > min (P(S), P(S).
Lemma E.1 (c-expansion implies constant expansion [Wei et al., 2021]). The c-expansion property (Definition 6.1) implies ( cconttant expansion (Definition E. for any >>
Proof of Lemma E.I. Consider a subset 5 C X such that P(S) 2 and P (Sn & P (2k)) /2.
Let Sn A SS N4 for every k E [K].
(i) c (1,2), since P (Xx) P (SS) 2 (Sa)) 2 1)P(ss)
K
P(NB (S) \ 5) >
P (NB (St) ((L)
k=
min ((c-1)P(Ss)) P -Px)) (Sk)
K
2 k=1
> (c- (0--)))(s)) = (c 1) 2 (c- 11-
(ii If 2, since c 12 and P P(X))) P (Sk) 2 (Sk), we have
K
P(NB(S)(S)> > Σ min ((c- P(G) ((S)) > Σ P(S))=((S)
1=1
Overall, have
PNB((S) = P (NB (S) > min (P(S), P(S).
30

---

E.2 Data Augmentation Consistency Regularization
To bridge Equation (8) with common DAC regularization algorithms in practice, in Example E. we instantiate FixMatch [Sohn et al., 2020] stat-ooftthe-ar remi-supervised learning algorithm that leverages DAC regularization by encouraging similar predictions of proper weak and strong data augmentations x" x E A(x) of the same sample
Example E.1 (FixMatch [Sohn et al., 2020]). FixMatch minimizes the loss between the outputs of the strong augmentation f(x²) and the pseudo-label of the weak augmentation yf (xx) when the confidence of such pseudo-labeling
high (i.e., max I (xx)x, is larger than threshold).
To connect FixMatch with Equation (8), we consider a fixed (unknown) margin-robust neighborhood F' 2 Fxx f. where the strong augmentation characterizes the worst-case (minimum) robust margin x E ENJEF argmit)xreAs) m. (f, x,, (x)); while the weak augmentation preserves the classification yf (xx)= = (x).
Then, for any E F' during learning, minimizing the cross-entropy loss between softmax (f(x²) and the one-hot label yf (xx) is equivalent to enforcing a large enough margin m (f.x* ,3, (x)x 2 whereas m (f,x', My,(x))
m x (xf,,(((x) 2 T for all x' A(xx) by construction implies MA (J,x) 2 T as required by the constraints in Equation (8).
E.3
Proof of Theorem 6.2
Proof of Theorem 6.2. We first recall from Lemma E.1 that e-expansion implies (2-11) 2v (f)
constant expansion (Definition E.1) for any S E F. Therefore, it is sufficient to show that with (g. 2v( expansion (i.e., 9 c-1 20(l)) )
P (M & max 2v)) FEE
(22)
For any I E Fxx,, we notice that Equation (22) is automatically satisfied when P (M(J)) < q.
Otherwise, when P (M) 2 g. then along with P() S P (Xx)) /2 for all k E [K] (g, (voo)-cconstant expansion implies
P (NB (M())) > min (P(M()),2V()) + P(M()).
(23)
Mcanwhile, we observe that by union bound,
PNB (M)) M()) I 2P 2x A(x) s. (x) # y, (x'] 2v(f)
(24)
because for any x E NB (M()) \ M(S), there exists x' E M() such that one can find some x" E A(x) n A (x'); and therefore exactly one of the follows must hold
()) xf E M(f), then Vy (x") A v. (x) Vy (x) implies ys (x") ys (x) for E A(x);
(ii) ifx" & Mf), then Df (x") = y+ (x) + yf (x') implies yf (x") H ys (x') for x" E (x').
Leveraging Equation (23) and Equation (24), we have
P (M) >P (NB (M())) (NB (M)) \ M())
> min (P (M())) 2w(()) + P (M(()) - 2x(s), which leads to min (P (M))), ( < 2v( and implies P (M)() < 2v()).
F
Technical Lemmas
Here, we briefly review the standard Rademaccher-oomplxityy based generalization analysis based on McDiarmid's inequality and classical symmetrization argument Wainwright [2019], Bartlett and Mendelson [2003].
Lemma F.1 (Generalization guarantee with Rademacher complexity). Given distribution over set 1 we consider a set of i.i.d. samples [Z]]iejn) ~ Z" with Z [Z]...., ......,,u) and a B-bounded
function class H. = [h: Z + R [M(z) - h(z')l < B zz E Z}. By denoting
(h) A Ez~z [b(2)] and A1)hh)
1
h(zz) s.l.
EN
[Aa(h)] H(h),
Without ambiguity, overload the notation Z the set well the distribution over the set.
31

---

then ht E argmin (h) and h E argminnew (h),), we have that with probability at least 1 1-82 over Z.
2 log(4/6)
H (())-((h))) v 49,, (H) +
where R, (H) is the Rademacher complexity of H.
1/2, p= -1
n
Rn (H) 2 Z= p-Radd
sup - REH 12
Σ Ps h(zi))
Rad(p) =
1/2, p p=1 1
0,
p +1
Proof of Lemma F.I. Let 9 (Z,,..., Znd - (Z)) A suPnEn (1)) Hz(h)). Then h E H being B-bounded implies that for any 2 ~ Z and E [n]]
B
19 Z Zn) g( ................................ Z, ...... ......,,)) S
n
Therefore, by McDiarmid's inequality [Bartlett and Mendelson, 2003],
PP (Z) E[g(Z)) +1 exp
(-B3)
122tt²
B
where exp
2n B
when
Ba log(4/8) 2n
Meanwhile, by a classical symmetrization argument (e.g., proof of Wainwright [2019] Theorem 4. 40),), we can bound the expectation [Zg( for independent sample set Z' 2 that is also independent of Z.
E (g(( [Z]
=Ez
sup kEE
H(h) (1)
=Ez
sup
Ez'
H2z (h) (h)
z]
LiEH
<Ezz
Ezz'
sup LIEH
Hz (h) - (1)
Z
Az (l:) flz((1)
= (E
sup
where in the last line we have used the law of iterated conditional expectation. Then, with Rademacher random variables (pI,..., Pr.) ~ Rad", we have
E [Z) <E
sup WCH n
Pr (h(z)) - m(zz))
<2F.z.p)
sup hER
Ps
h(zz)
$2R,, (H)
Therefore, with probability at least 5/4 over Z. we have
B
sup (hh) - (l) S 29R, (H) +
NEW
2n
while the same tail bound holds for SuрлEи - (h) + Hz (h) via analogous argument.
By recalling the definition of h and li*,, can decompose the excess risk (()) H(hi)) as
H (i)) H(h)) (m) fzz(m)) + (fzz(h) -f1((1')) + (fz((h)) - H(h²))
(H()) Azz (h) + (fiz(h)) - H(h)))
32

---

where Hz) - Hz(hh)) - O by the basic inequality. With both h, h² E H, we have
( H(h)) S 2 sup
H(h) A12(1))
hc7
and therefore
H(h) + Hz(()) 2 2
TP ( H(h)) 2 1 S
sup (h) Hz)(h) 2
IP
sup LEe
LiEH
Overall, with probability at least
5/2 over Z.
B (4/8)
- (hh)) - 49h, (H) +
33


Reviews:
[{"review_id": "ZoaY8EVQYt", "reviewer": "Reviewer_mtgh", "summary": "The paper provides a comprehensive theoretical proof of the relationship between RKD and clustering from the perspective of spectral clustering. The theoretical proof presented in the paper is detailed and reasonable. Firstly, RKD is regarded as a spectral clustering problem of the teacher model, and then the introduced clustering error is used to prove that RKD leads to low clustering error. Finally, the paper presents the sampling complexity bound of RKD in the case of limited unlabeled samples.", "questions": "As I am less familiar with purely theoretical work, I find that in Section 7, the author continues to discuss the theoretical analysis of RKD in different settings. While providing relevant theoretical proofs is important based on previous empirical work, it would be beneficial to consider adding a discussion section that explores potential new directions for practical applications.", "limitations": "1. The research presented in the paper holds significant theoretical value. It would be beneficial to enhance the overall clarity and organization of the paper's structure. This will improve the readability and friendliness of the paper for fellow researchers in the field.\n2. In the field of machine learning, it is highly recommended to conduct necessary experiments to strengthen the scientific rigor of the study.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.The theoretical proof presented in the paper is detailed and reasonable. \n2. Label efficiency of cluster-aware SSL is demonstrated as well.\n", "weaknesses": "1. It appears that the author attempts to convey numerous viewpoints in this paper, resulting in a somewhat confused logical structure. As a result, the paper is somewhat difficult to read and understand, possibly due to my unfamiliarity with the writing style of purely theoretical papers.\n2. While the author's arguments are generally reasonable, there seems to be a lack of strong correspondence between the presented problem and the method of reasoning. It would be beneficial to understand the author's motivations and thought process behind exploring RKD at a theoretical level, particularly in relation to demonstrating its label efficiency in the SSL setting.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to first thank the reviewer for appreciating the theoretical contribution of this work, as well as for bringing up constructive questions and suggestions in the review. On the detailed concerns:\n\n__[Motivations and improvements on presentation]__ \nWe understand and value the reviewer’s concern and feedback on the accessibility of our presentation to the audience who are less familiar with theory works. In the following paragraphs, we clarify the motivations and outline of this work. Meanwhile, we will try to improve the presentation and accessibility of the paper in the revision.\n1. __RKD learns spectral clustering__: Clustering is a well-established and fundamental idea in machine learning that suggests that data can be more efficiently learned from via the inherent geometric structure of the available data set of points. Inputs that are more “similar” to each other (in the appropriate sense of similarity for the machine learning task at hand) should have “similar” outputs. We establish the connection to RKD by considering that the teacher model, which has learned these inherent similarities, imparts knowledge regarding the clustering structure over the population data, $\\mathcal{X}$ to the student model and its observed empirical data, $\\mathbf{X}^u$. Viewing clustering from a graph perspective, the knowledge imparted from teacher to student can be interpreted as spectral clustering on an underlying population-induced graph.\n2. __Cluster-awareness of RKD leads to better label efficiency__: One of the most celebrated virtues of (data-free) knowledge distillation in general, including RKD, is to leverage the power of existing pretrained models to __enable more efficient learning__ in terms of both the computation and sample complexity. With the established connection between RKD and spectral clustering, we then demonstrate the label efficiency achieved by RKD through a more general framework of “cluster-aware SSL”.\n3. __Different perspectives of cluster-awareness: DAC v.s. RKD__: Given that the notion of clustering is quite broad, we ask a natural question: __what is special about spectral clustering as learned by RKD?__ To answer this question, we further investigate data augmentation consistency (DAC) regularization, another example of cluster-aware SSL that learns clustering from a perspective that is complementary to RKD.  By __comparing the distinct mechanisms of RKD and DAC in providing upper bounds for the same notion of clustering error__, we show that __DAC learns clustering “locally”__ through “expansion of neighborhoods”, whereas __RKD learns clustering “globally”__ through spectral clustering.\n\n__[Future works from an empirical perspective]__ There are two immediate insights from our theoretical analysis. First, by unveiling the mechanism of RKD as a form of spectral clustering from a “global” perspective, we illustrate __when and how we can incorporate RKD efficiently in practice__. For example, semi-supervised learning with DAC encourages clustering from a “local” perspective (Sec. 6), but when the data augmentations are not strong (expansive as defined in Def. 6.1) enough to reveal the clustering structure through the local connectivity/overlap of neighborhoods (cf. the “weak” augmentations in Appendix A), the additional “global” perspective offered by RKD generally helps the student model better capture the underlying clustering structure and achieve better accuracy. Our experiments in Appendix A empirically demonstrate this. \n\nSecond, through the analysis of RKD as spectral clustering, we identify a pitfall of applying RKD alone in end-to-end learning (Example C.1) that violates the boundedness and margin assumptions. This provides __a theoretical explanation for the practical wisdom that RKD is generally used to reinforce standard KD__, instead of as a standalone end-to-end learning algorithm. Through the lenses of “global” and “local” perspectives of RKD and DAC, along with the experiments in Appendix A, we show that __RKD can be leveraged not only to boost standard KD but also to improve upon DAC in semi-supervised learning__.\n\nFrom a broader perspective and motivated by the improvement brought by RKD to DAC, especially in the data-scarce setting, it would be particularly interesting to __design practical (semi-supervised) learning algorithms that leverage both the local and global perspectives on the clustering structure__. \n\n__[(More) experiments]__ Due to the page limit, we defer the experiments to Appendix A. For various label-rate (i.e., amounts of labeled vs unlabeled data) and augmentation strength levels, we evaluate the utility of RKD for improving a baseline SSL method. We use the recent state-of-the-art FixMatch as our baseline SSL method, which can be considered as a DAC method in our theoretical framework. Furthermore, for each of the datasets that we include in our experimental evaluation, we consider the effect of the selection of the limited amount of labeled data on the performance in each setting. We find that RKD does indeed help to improve student model performance, with the greatest gains in performance in especially data-scarce settings wherein smaller amounts of labeled and unlabeled data are available to the student model. This reflects the importance of the global perspective of the clustering structure offered by RKD for data-scarce applications of data-free knowledge distillation (where the student model does not have access to the data that the teacher model was trained on). \n\nWhile we think that more empirical evaluation would be very useful, we kindly suggest that our main contributions in this work lie in the important steps we have taken to establish a more rigorous theoretical understanding of the empirical success of RKD. \n\nWe hope this will help address the confusion and concerns raised in the review, and if so, we would truly appreciate a re-evaluation accordingly."}, {"review_id": "HMoFgwSaOL", "reviewer": "Reviewer_APrr", "summary": "This paper points out that RKD over a population-induced graph given by a teacher model leads to low clustering error (Spectral Clustering), which provably benefits to semi-supervised learning and other downstream tasks. Consequently, it provides a theoretical analysis of relational knowledge distillation (RKD) in the semi-supervised classification setting from a clustering perspective.", "questions": "My principle concern is the inadequate empirical study. As mentioned above, there are mainly two issues should be addressed. First, in the current results (Table 1 and Table 2), why the performance of the proposed approach cannot consistently outperform the baseline? Second, what is the performance of the proposed method on other large-scale datasets? If these issues can be resolved, I will recommend this work.", "limitations": "I agree with the limitations provided in the last section. Besides, please see the Weaknesses and Questions parts for my concern. I hope the review is helpful for this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper mainly focuses on expounding the close relationship between RKD and Spectral Clustering from a theoretic perspective, which definitely contributes to the increase of attention on RKD. According to this seminal work, RKD can be regarded as a principle choice to extract knowledge from a pre-trained large model.", "weaknesses": "The weakness of this paper is obvious: The experimental part is too weak. There is no empirical study in the main text, and the experimental results in the appendix are limited. In addition, in some cases, RKD even deteriorates the Top-1 performance. The authors provided no explanation on these cases. Besides, CIFAR-10 and CIFAR-100 are not quite challenging datasets, and they are too similar. It is suggested conducting experiments on the large-scale datasets to better demonstrate the effectiveness of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for appreciating our novelty, as well as for raising constructive suggestions and questions concerning our experiments. \n\nNevertheless, from a high-level perspective, we would like to kindly point out that this work is __a novel theoretical study on a family of existing methods__ that is empirically well-known—RKD and cluster-aware semi-supervised learning. Therefore, __the goal of our experiments is to ground the insights unveiled by our theoretical results__, instead of demonstrating the power of a novel algorithm on a broad spectrum of large-scale benchmarks. \n\nMoreover, as we briefly touched on in the introduction (line 27-31), an essential virtue of (data-free) knowledge distillation in general is to leverage the power of existing teacher models for more affordable learning in both computational and sample complexities. Therefore when designing the experiments, with limited computational resources, we purposefully put our focus on fully investigating the more relevant factors to our theory (e.g., the unlabeled sample sizes and the choices of data augmentations, as explained in the next paragraphs).\n\n__[Consistency of performance I: when and how RKD helps improve DAC]__ Thanks for the great question. This leads to the interesting point on when and how RKD helps improve DAC. The answer can be provided from both the analysis and experiment perspectives as follows.\n\nFrom the __analysis perspective__, as elaborated in __Remark 6.1__, DAC learns a “local” clustering structure through the expansion of neighborhoods characterized by the data augmentations. This is complementary to RKD which learns the spectral clustering from a “global” perspective. Therefore, RKD helps improve DAC when the data augmentations on the unlabeled samples fail to reveal the “local” clustering structure: \n1. when the data augmentations are not expansive enough (characterized by the $c$-expansion property in Def. 6.1), and/or\n2. when there are insufficient numbers of unlabeled samples.\nThat is, in our experiments, RKD brings more improvements to FixMatch when the augmentation strength is weaker or the unlabeled sample size $N$ is smaller, whereas when the data augmentations are strong and $N$ is large, the gap between FixMatch and FixMatch+RKD may not be noticeable.\n\nFrom the __experiment perspective__, the choice of teacher model in practice becomes another critical factor for the performance of RKD. Recall that in theory, we assume the access to a teacher model that reveals the underlying structure of the data, whose accuracy is characterized by a constant $\\alpha$ in Def. 4.1 such that $\\alpha \\ll 1$ for a good teacher model. However, in practice, different pretrained teacher models can lead to different $\\alpha$. For example, in our experiments, the teacher model for CIFAR-10 pretrained with supervised ERM on CIFAR-10 and that for CIFAR-100 pretrained with unsupervised contrastive learning (SwAV) on ImageNet can have different $\\alpha$’s that lead to different performance.\n \n__[Consistency of performance II: experiments with multiple random seeds]__ Thanks to the reviewer's suggestion, we ran more experiments with multiple random seeds to improve the reliability of our results. Please refer to the general response for details.\n\nWe hope this will help address the concerns raised in the review, and if so, we would genuinely appreciate a re-evaluation accordingly."}, {"review_id": "L4vvsW5EgG", "reviewer": "Reviewer_T9nK", "summary": "This paper studies relational knowledge distillation (RKD) on semi-supervised learning setting. This is different from the previous theoretical results on knowledge distillation, which mostly focus on feature matching (not relational). They introduce a new notion called low clustering error, which quantifies the difference betweeen the predicted and ground truth clusterings, and show that RKD can provably produce low clustering error. They also have a few other results, including the label efficiency theorm on a cluster-aware semi-supervised learning framework with low clustering errors, and unifying data augmentation consistency regularization with RKD, showing that consistency reuglarization focuses on the local perspective, while RKD improves over the global perspective. ", "questions": "I do not have other questions. ", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: Since we already have seen a few papers on connecting spectral clustering with contrastive learning or other learning methods, the spectral clustering part of this paper is not particularly surprising. However, I do like the relational part, which focuses on the relationships between the features, rather than the feature matching itself. I think this is a very interesting and important direction to pursue. Moreover, the authors also investigate the benefit of clustering awareness in the semi-supervised learning scenario, which is novel. \n\nQuality: I think this is a well written paper with rigorous definitions, theorems and proofs. \n\nClarity: Since this is a theory paper, I will not say it is straightforward to read. However, I think the authors did a very good job in the introduction to demonstrate the main contributions of this paper, and present the technical theorems and assumptions in a structured way. Therefore I would say this paper is well written. \n\nSignificance: I think this paper is indeed interesting, because it provides an interesting connection between relational knowledge distillation learning and spectral clustering, and also provide theoretical characterization on various aspects. \n\n", "weaknesses": "It is a bit difficult for me to understand the intuition of Assumption 4.2, and the toy example after assumption 4.2 is too special, which does not explain much about the complicated definitions. It would be nice to further elaborate on the intuitions, and perhaps give a non-trivial example of this assumption, and why this assumption is a mild assumption. \n\nPersonally I like Theorem 4.1 better, and I do not feel it is really necessary to consider the limited unlabeled samples setting (because usually we may assume the unlabeled samples are cheap). Therefore, it might improve the presentation of this paper, if the author can add more motivations on Sec 4.2. (if there is no such motivation, it's also fine, I think it is a minor spot.)\n\nThe current connections between different results are weak. Specifically, I cannot easily understand how the last DAC result connects with the previous two. I might be wrong, but I initially felt that the third result says the combination of DAC and RKD can improve the performance. However, the statement of Theorem 6.2 seems only contains DAC, not RKD. Therefore, it seems to me that the first and third results are in parallel: both of them are providing upper bounds of clustering error. Is it true? \n-- if this is true, I think the presentation of the introduction should be updated, to avoid potential misconceptions. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for appreciating the novelty and presentation of this work, as well as for the insightful comments and questions. \n\n__[Intuition of Ass 4.2]__ Ass 4.2 can be intuitively summarized as assumptions on the __boundedness $\\beta$__ and __reasonably large margins $\\gamma$__ of the prediction functions $f$. In other words, Ass 4.2 pivots $f$ down to a reasonable prediction function. \n\nIn the submitted version, we tailor Ass 4.2 to provide better upper bounds for the clustering error. Thanks to the reviewer’s feedback, we realize that this can lead to non-standard descriptions. We will include further clarifications on these in the revision:\n* __Skeleton subset__: Given a prediction function $f: \\mathcal{X} \\to \\mathbb{R}^K$ for K-class classification, the skeleton subset $S = [s_1; \\cdots; s_K]$ can be intuitively viewed as $K$ samples where $f$ makes the __“most confident” prediction__ in each class, i.e., $f(s_k)_k = \\max_x f(x)_k$. For $f$ to be a reasonable prediction function, we assume\n1. $f$ indeed assigns $s_k$ to class $k$ and \n2. $f(S) \\in \\mathbb{R}^{K \\times K}$ is full rank (i.e., $f(s_k)$ for different $k \\in [K]$ are linearly independent). \nThe latter is a milder assumption than other alternatives like “$f(S)$ is strictly diagonally dominant” (which is a sufficient condition for being full rank while generally holds for reasonable prediction functions). Intuitively, this enforces each prediction $f(s_k)$ in the skeleton subset to have a dominating k-th entry $f(s_k)_k$.\n* __Boundedness $\\beta$__: $\\sigma_1(f(S))\\le\\beta$ is again a milder version of some arguably more common forms of boundedness, e.g., $|f(x)_k|<\\beta/K$ for all $x \\in \\mathcal{X}$, $k \\in [K]$ (a sufficient condition).\n* __Margin $\\gamma$__: This ensures that for each class $k \\in [K]$, $f$ can easily distinguish its “most confident” prediction $s_k$ from those samples predicted to lie in other classes by at least a margin $\\gamma$. Notice that this is a slightly simplified description–but a stronger assumption–than what appeared in Ass 4.2. \n\nIt is worth highlighting that these assumptions __cannot be guaranteed with RKD alone__ but are generally __satisfied with additional supervision/regularization__. Following the toy example after Ass 4.2, we refer the reader to __Example C.1__, which demonstrates such __pitfall of RKD alone (violating Ass 4.2)__ and how __additional supervision/regularization can help__. This also provides an explanation of why, RKD is never applied in practice as a standalone algorithm for end-to-end learning but is commonly coupled with supervision and/or standard KD. We will further emphasize this critical point in the revision.\n\n__[Importance of the limited unlabeled sample setting]__ While we agree with the reviewer that considering the limited unlabeled sample setting inevitably leads to more complicated results, we kindly argue that such effort is worthwhile beyond theoretical completeness. Although the unlabeled samples are oftentimes much more accessible than the labeled ones, in practice, we generally only have __finite (limited) unlabeled samples__ but not access to the __unlabeled population__ (what is assumed in Thm 4.1). \n\nMore importantly, analyzing the limited unlabeled sample setting provides insight into the **unlabeled sample complexity**—how many unlabeled samples are needed to achieve a low clustering error. In particular, Thm 4.2 and 4.3 imply that the unlabeled sample complexity is dominated by the Rademacher complexity of the function class. Intuitively, larger neural networks will then require more unlabeled samples to sufficiently learn the clustering structure.\n\n__[Connection and difference between RKD and DAC]__ At a high level, RKD, cluster-aware SSL, and DAC are motivated and connected through the three research questions raised in the introduction:\n* In Sec 4, we show that RKD leads to low clustering error via spectral clustering.\n* In Sec 5, we show how such cluster awareness brings label efficiency through a more general cluster-aware SSL framework.\n* As the reviewer mentioned, __clustering is a generic notion__ that is widely studied from various perspectives. Then, it is natural to ask __what is special about spectral clustering as learned by RKD?__ In Sec 6, the analysis of DAC is leveraged as __another example of cluster-aware SSL that facilitates clustering from a different perspective complementary to RKD__. By __comparing the distinct mechanisms of RKD and DAC in providing upper bounds for the same notion of clustering error__, we show that __DAC learns “locally”__ through expansion of neighborhoods, whereas __RKD learns “globally”__ through spectral clustering.\n\nThe reviewer is right about that Thm 6.2 connects low DAC error to low clustering error and does not involve RKD. However, we kindly point out that the key message conveyed in Sec 6 is not the upper bound on clustering error itself, __but the different mechanism that leads to clustering—the “local” expansion of neighborhoods through data augmentation (Def. 6.1 and 6.2)__. Based on such distinct mechanisms, we further discuss the complementary perspectives of RKD and DAC in __Remark 6.1__. \n\nWe will try to further clarify these connections and address the potential confusion in the revision.\n\nAs a minor remark from the technical perspective, Thm 6.2 does not involve RKD because the analysis on DAC is conducted in a different setting from that for RKD (e.g., data population $\\mathcal{X}$ is a set in Sec 6 without a graph structure), exactly because of their distinct perspectives of learning clustering. Although it is possible to combine both settings and derive unified bounds, this would lead to unnecessary complications for our goal of demonstrating the complementary perspectives of RKD and DAC.\n\nWe hope this will help address the confusion and concerns raised in the review, and if so, we would genuinely appreciate a re-evaluation accordingly."}]

Author rebuttal:
First, we would like to thank all the reviewers for their efforts and valuable suggestions. We will share an update on our experiments (in Appendix A) here globally while addressing individual questions and concerns posed in the reviews separately.

__[Additional experiments with multiple random seeds]__
Thanks to the suggestion of Reviewer APrr, we ran more experiments with multiple random seeds to improve the reliability of our results. We will update the following results in the revision: (Here, "High", "Medium", and "Weak" refer to the augmentation strength described in Appendix A.)

**Table 1: Top-1 accuracy on CIFAR-10.**
| Label selection | Sample sizes $(n, N)$ | SSL algorithm | **High** | **Medium** | **Weak** |
|:---------------:|:----------------------:|:-------------:|:--------:|:----------:|:--------:|
| **Uniform**     | (40, 50000)            | FixMatch      | 89.47 ± 3.83 | 87.89 ± 1.43 | 81.36 ± 1.41 |
|                 |                        | FixMatch + RKD| **89.88 ± 0.41** | **89.10 ± 1.14** | **84.61 ± 1.23** |
|                 | (40, 40000)            | FixMatch      | 87.60 ± 1.21 | 85.30 ± 1.35 | 83.74 ± 3.07 |
|                 |                        | FixMatch + RKD| **90.19 ± 0.19** | **88.65 ± 1.81** | **86.68 ± 1.06** |
|                 | (40, 25000)            | FixMatch      | 81.73 ± 1.27 | 81.43 ± 2.98 | 76.84 ± 1.98 |
|                 |                        | FixMatch + RKD| **87.06 ± 2.04** | **87.24 ± 0.39** | **82.75 ± 2.35** |
| **StochasticGreedy** | (40, 50000)      | FixMatch      | 85.48 ± 1.67 | 89.39 ± 0.82 | 78.98 ± 0.52 |
|                 |                        | FixMatch + RKD| **91.19 ± 0.26** | **90.00 ± 0.64** | **87.11 ± 4.33** |
|                 | (40, 40000)            | FixMatch      | 84.51 ± 1.34 | 84.88 ± 6.68 | 70.70 ± 5.32 |
|                 |                        | FixMatch + RKD| **85.68 ± 1.19** | **88.31 ± 1.36** | **85.12 ± 3.49** |
|                 | (40, 25000)            | FixMatch      | 79.74 ± 8.02 | 73.97 ± 1.98 | 73.86 ± 3.29 |
|                 |                        | FixMatch + RKD| **83.72 ± 4.73** | **82.09 ± 3.27** | **80.65 ± 3.67** |

**Table 2: Top-1 accuracy on CIFAR-100.**
| Label selection | Sample sizes $(n, N)$ | SSL algorithm | **High** | **Medium** | **Weak** |
|:---------------:|:----------------------:|:-------------:|:--------:|:----------:|:--------:|
| **Uniform**     | (400, 50000)           | FixMatch      | 46.85 ± 1.68 | 45.67 ± 0.51 | 45.84 ± 0.35 |
|                 |                        | FixMatch + RKD| **49.33 ± 0.42** | **47.97 ± 0.37** | **47.65 ± 0.17** |
|                 | (400, 40000)           | FixMatch      | 44.11 ± 0.51 | 42.98 ± 0.56 | 42.74 ± 0.42 |
|                 |                        | FixMatch + RKD| **46.24 ± 0.64** | **45.78 ± 0.94** | **45.13 ± 1.08** |
|                 | (400, 25000)           | FixMatch      | 36.60 ± 0.03 | 35.86 ± 0.51 | 33.59 ± 1.54 |
|                 |                        | FixMatch + RKD| **37.87 ± 0.98** | **36.69 ± 0.41** | **35.69 ± 1.51** |
| **StochasticGreedy** | (400, 50000)     | FixMatch      | 47.45 ± 0.30 | 48.64 ± 0.35 | 46.79 ± 1.05 |
|                 |                        | FixMatch + RKD| **50.41 ± 1.41** | **50.67 ± 1.62** | **49.09 ± 1.31** |
|                 | (400, 40000)           | FixMatch      | 45.93 ± 0.21 | 44.78 ± 1.51 | 44.62 ± 0.72 |
|                 |                        | FixMatch + RKD| **47.62 ± 0.67** | **47.28 ± 0.56** | **46.07 ± 0.86** |
|                 | (400, 25000)           | FixMatch      | 39.40 ± 0.31 | 39.01 ± 0.68 | 38.22 ± 0.42 |
|                 |                        | FixMatch + RKD| **40.88 ± 0.61** | **40.73 ± 0.46** | **39.20 ± 0.73** |

Meta-review: The paper explores the issue of relational knowledge distillation. It frames the problem as that of Spectral clustering and draws theoretical insights. This paper should be of interest to Neurips audience.
Decision: Accept (poster)