Discriminative Similarity for Data Clustering
Authors: Yingzhen Yang
Ping Li
Venue: ICLR 2022 Poster (2022)
Keywords: Discriminative Similarity
Rademacher Complexity
Generalization Bound
Data Clustering

Abstract: Similarity-based clustering methods separate data into clusters according to the pairwise similarity between the data, and the pairwise similarity is crucial for their performance. In this paper, we propose {\em Clustering by  Discriminative Similarity (CDS)}, a novel method which learns discriminative similarity for data clustering. CDS learns an unsupervised similarity-based classifier from each data partition, and searches for the optimal partition of the data by minimizing the generalization error of the learnt classifiers associated with the data partitions. By generalization analysis via Rademacher complexity, the generalization error bound for the unsupervised similarity-based classifier is expressed as the sum of discriminative similarity between the data from different classes. It is proved that the derived discriminative similarity can also be induced by the integrated squared error bound for kernel density classification. In order to evaluate the performance of the proposed discriminative similarity, we propose a new clustering method using a kernel as the similarity function, CDS via unsupervised kernel classification (CDSK), with its effectiveness demonstrated by experimental results.

Published as a conference paper at ICLR 2022
DISCRIMINATIVE SIMILARITY FOR DATA CLUSTERING
Yingzhen Yang
Ping Li
School of Computing and Augmented Intelligence Arizona State University
Cognitive Computing Lab
Baidu Research
Tempe, AZ 85281, USA yingzhen. yangeasu.ede
Bellevue, WA 98004, USA lipingl @baidu. com
ABSTRACT
Similarity-based clustering methods separate data into clusters according to the pairwise similarity between the data, and the pairwise similarity is crucial for their performance. In this paper, we propose Clustering by Discriminative Similarity (CDS), novel method which learns discriminative similarity for data clustering. CDS learns an unsupervised similarity-base and searches for the optimal partition of the data by minimizing the generalization error of the learnt classifiers associated with the data partitions. By generaliza- tion analysis via Rademacher complexity, the generalization error bound for the unsupervised similarity similarity between the data from different classes. is proved that the derived dis- criminative similarity can also be induced by the integrated squared error bound for kernel density classification. In order to evaluate the performance of the pro- posed discriminative similarity, we propose a new clustering method using a ker- nel as the similarity function, CDS via unsupervised kernel classification (CDSK), with its effectiveness demonstrated by experimental results.
classifier from each data partition,
classifier is expressed as the sum of discriminative
INTRODUCTION
Similarity bhased clustering methods segment the data based on the similarity measure between the data points, such as spectral clustering (Ng et al., 2001), pairwise clustering method (Shental al., 2003), K-means (Hartigan & Wong, 1979), and kernel K-means (Schölkopf et al., 1998). The suc- cess of similarity-basee clustering highly depends on the underlying pairwise similarity over the data, which in most cases are constructed empirically, e.g., by Gaussian kernel or the K-Nearest- Neighbor (KNN) graph. In this paper, we model data clustering as a multiclass classification prob- lem and seek for the data partition where the associated classifier, trained on cluster labels, can have low generalization error. Therefore, it is natural formulate data clustering problem as a problem of training unsupervised classifiers: classifier can be trained upon each candidate partition of the data, and the quality of the data partition can be evaluated by the performance the trained classi- fier. Such classifier trained on hypothetical labeling associated with data partition is termed an unsupervised classifier.
We present Clustering by Discriminative Similarity (CDS), wherein discriminative similarity is de- rived by the generalization error bound for an unsupervised limilarity-basee classifier. CDS is based on novel framework of discriminative clustering by unsupervised classification wherein un- supervised classifier is learnt from unlabeled data and the preferred hypothetical labeling should minimize the generalization error bound for the learnt classifier. When the popular Support Vector Machines (SVMs) is used in this framework, unsupervised SVM (Xu et al., 2004) can be deduced. In this paper, a similarity- -base classifier motivated by similarity learning (Balcan et al., 2008; Cortes et al., 2013), is used as the unsupervised classifier. By generalization analysis via Rademacher com- plexity, the generalization error bound for the unsupervised similarity- based classifier is expressed as sum of pairwise similarity between the data from different classes. Such pairwise similarity, param- eterized by the weights of the unsupervised similarity- -bsed classifier, serves as the discriminative similarity. The term "discriminative similarity" emphasizes the fact that the similarity is learnt as
Yingzhen Yang's work was conducted consulting researcher at Baidu Research- Bellevue, WA, USA.

---

Published as a conference paper at ICLR 2022
to improve the discriminative capability of certain classifier such as the aforementioned unsuper- vised similarity- based classifier.
1.1 CONTRIBUTIONS AND MAIN RESULTS
Firstly, we present Clustering by Discriminative Similarity (CDS) where discriminative similarity induced by the generalization error bound for unsupervised similarity-based classifier on unla- beled data. The generalization bound for such similarity-based classifier is of independent interest, which among the few results of generalization bounds for classification using general similar- ity functions (Section B.1 of Appendix). When the general similarity function is set to Positive Semi-Defiitte (PSD) kernel, the derived discriminative similarity between two data points x, is 5 2(a; ta, - - (x: - Xj), where K can be an arbitrary PSD kernel and az is the kernel weight associated with x,. With theoretical and empirical study, we argue that S should be used for data clustering instead of the conventional kernel similarity corresponding uniform kernel weights. In the case of binary classification, we prove that the derived discriminative similarity S has the same form as the similarity induced by the integrated squared error bound for kernel density classification (Section A of the appendix). Such connection suggests that there exists information- theoretic measure which is implicitly equivalent to our CDS framework for unsupervised learning, and our CDS framework is well grounded for learning similarity from unlabeled data.
Secondly, based on our CDS model, we develop clustering algorithm termed Clustering by Dis- criminative Similarity via unsupervised Kernel classification (CDSK) in Section 5. CDSK uses a PSD kernel as the similarity function, and outperforms competing clustering algorithms, including nonparametric discriminative similarity based clustering methods and similarity graph based cluster- ing methods, demonstrating the effectiveness of CDSK. When the kernel weights {a,} } are uniform, CDSK is equivalent to kernel K-Means (Schölkopf et al., 1998). CDSK is more flexible by learning adaptive kernel weights associated with different data points.
1.2 CONNECTION TO RELATED WORKS
Our CDS model is related to a class of discriminative clustering methods which classify unlabeled data by various measures on discriminative unsupervised classifiers, and the measures include gen- eralization error (Xu et al., 2004) or the entropy of the posterior distribution of the label (Gomes al., 2010). Discriminative clustering methods (Xu al., 2004) predict the labels of unlabeled data by minimizing the generalization error bound for the unsupervised classifier with respect to the hypothetical labeling. Unsupervised SVM is proposed in Xu al. (2004) which learns binary classifier to partition unlabeled data with the maximum margin between different clusters. The the- oretical properties of unsupervised SVM are further analyzed in Karnin et al. (2012). Kernel logistic regression classifier is employed in Gomes al. (2010), and it uses the entropy of the posterior dis- tribution of the class label by the classifier to measure the quality of the hypothetical labeling. CDS model performs discriminative clustering based on novel unsupervised classification framework by considering similarity-basee or kernel classifiers which are important classification methods in the supervised learning literature. In contrasts with kernel similarity with uniform weights, the induced discriminative similarity with learnable weights enhances its capability to represent complex inter- connection between data. The generalization analysis for CDS is primarily based on distribution free Rademacher complexity. While Yang et al. (2014a) propose nonparametric discriminative similarity for clustering, the nonparametric similarity requires probability density estimation which difficult for -igh-diimnsional data, and the fixed nonparametric similarity is not adaptive to complicated data distribution.
The paper is organized as follows. We introduce the problem setup of Clustering by Discrimina- tive Similarity in Section 3. We then derive the generalization error bound for the unsupervised similarity-baat based classifier for CDS in Section 4 where the proposed discriminative similarity is in- duced by the error bound. The application of CDS to data clustering is shown in Section 5. Through- this paper, the term kernel stands for the PSD kernel if no special notes made.
2

---

Published as a conference paper at ICLR 2022
2 SIGNIFICANCE OF CDSK OVER EXISTING DISCRIMINATIVE AND SIMILARITY-BASED CLUSTERING METHODS
Effective data similarity highly depends on the underlying probabilistic distribution and geometric structure of the data, and these two characteristics leads to "data-driven" similarity, such as Zhu et al. (2014); Bicego et al. (2021); Ng et al. (2001); Shental et al. (2003); Hartigan & Wong (1979); Schölkopf ct al. (1998) and similarity based on geometric structure of the data, such as the subspace structure (Sparse Subspace Clustering, or SSC in Elhamifar & Vidal (2013)). Note that the sparse graph method, e'-Graph (Yan & Wang, 2009), has the same formulation as SSC. Most existing clus- tering methods based data-driven geometric structure-driven similarity suffer from common deficiency, that is, the similarity is not explicitly optimized for the purpose of separating underlying clusters. In particular, the Random Forest-based similarity (Zhu et al., 2014; Bicego et al., 2021) is extracted from features in decision trees. Previous works about subspace- based similarity (Yan & Wang, 2009; Elhamifar & Vidal, 2013) try make sure that only data points lying on or close to the same subspace have nonzero similarity, so that data points from the same subspace can form a cluster. However, it is not guaranteed that features in the decision trees are discriminative enough to separate clusters, because the candidate data partition (or candidate cluster labels) do not participate in the feature or similarity extraction process. Note that synthetically generated negative class are suggested in Zhu et al. (2014); Bicego et al. (2021) to train unsupervised random forest, however, the synthetic labels are not for the original data. Moreover, it is well known that the existing subspace learning methods only obtain reliable subspace-based similarity with restrictive geometric assump- tions on the data and the underlying subspaces, such as large principal angle between intersecting subspaces (Soltanolkotahi & Candes, 2012; Elhamifar & Vidal, 2013).
Therefore, it is particularly important to derive similarity for clustering which meets two require- ments: (1) discriminative measure with information such as cluster partition is used derive such similarity so as to achieve compelling clustering performance: (2) it requires less restrictive assump- tions on the geometric structure of the data than current geometric structure-based similarity learning methods, such as subspace clustering (Yan & Wang, 2009; Elhamifar & Vidal, 2013).
Significance. The proposed discriminative similarity of this paper meets these two requirements. First, the discriminative similarity is derived by the generalization error bound associated with candi- date cluster labeling. and minimizing the objective function of our optimization problem for cluster- ing renders joint optimization of discriminative similarity and candidate cluster labeling in way such that the similarity -based classifier has small generalization error bound. Second, our framework only assumes mild classification model in Definition 3.1, which only requires an unknown joint distribution over data and its labels. In this way, the restrictive geometric assumptions are avoided in method. Compared to the existing discriminative clustering methods, such MMC (Xu et al., 2004), BMMC (Chen et al., 2014), RIM (Gomes et al., 2010), and the other discriminative clustering methods such as (Huang et al., 2015; Nguyen et al., 2017), the optimization problem of CDSK with discriminative similarity-baa based formulation is much easier to solve and it enjoys convexity and effi- ciency in each iteration of coordinate descent described in Algorithm 1. In particular, mentioned in Section D of the appendix, the first step (1I) of each iteration can be solved by efficient SVD or other randomized large-scale SVD methods, and the second step (12) of each iteration can be solved by efficient SMO (Platt, 1998). Moreover, the optimization problems in these two steps are either convex or having flosed-form solution. In contrast, MMC requires expensive semidefinite program- ming. RIM has to solve a nonconvex optimization problem and its formulation does not guarantee that the trained multi-class kernelized logistic regression has low classification error on candidate labeling, which explains why it has inferior performance compared to method. The discrimina- tive Extreme Learning Machine (Huang et al., 2015) trains ELM using labels produced by a simple clustering method such K-means, and the potentially poor cluster labels by the simple clustering method can easily result in unsatisfactory performance of this method. The discriminative Bayesian nonparametric clustering (Nguyen et al., 2017) and BMMC (Chen et al., 2014) require extra efforts of sampling hidden variables and tuning hyperparameters to generate the desirable number of clus- ters (or model selection), which could reduce the effect of discrininative measures used in these Bayesian nonparametric methods.
3

---

Published as a conference paper at ICLR 2022
3 PROBLEM SETUP
We introduce the problem setup of the formulation clustering by unsupervised classification. Given unlabeled data {x/}i_ C Rd clustering is equivalent to searching for the hypothetical la- beling which is optimal in some sense. Each hypothetical labeling corresponds to a candidate data partition. Figure illustrates four binary hypothetical labelings which correspond to four partitions of the data, and the data is divided into two clusters by each hypothetical labeling.
Figure 1: Illustration of binary hypothetical labelings
The discriminative clustering literature (Xu et al., 2004; Gomes et al., 2010) has demonstrated the potential of multi-class classification for clustering problem. Inspired by the natural connection between clustering and classification, Classification which models clustering problem as a multi-class classification problem. A classifier learnt from unlabeled data with hypothetical labeling, which is associated with candidate partition the unlabeled data. The optimal hypothetical labeling supposed to be the one such that its associated classifier has the minimum generalization error bound. To study the generalization bound for the classifier learnt from hypothetical labeling, the concept of classification model is needed. Given unlabeled data [x,]/=1- classification model My is constructed for any hypothetical labeling y = Ji as follows.
proposes the framework of Clustering by Unsupervised
Definition 3.1. The classification model corresponding to the hypothetical labeling y (wn } is defined as My = (S, F). S = (x1, yr )= are the labeled data by the hypothetical labeling V, and are assumed to be i.i.d. samples drawn from the some unknown joint distribution Pxy, where (X, Y) 1) is random couple, X E X C g represents the data in some compact domain X, and Y {1,2, c} is the class label of X, the number of classes. F classifier trained on S. The generalization error of the classification model My is defined as the generalization error of the classifier F in My.
The basic assumption of CDS is that the optimal hypothetical labeling minimizes the gener- alization error bound for the classification model. With being different classifiers, different discriminative clustering models can be derived. When SVMs is used as the classifier F in the above discriminative model, unsupervised SVM (Xu et al., 2004) is obtained.
In Balcan et al. (2008), the authors proposes a classification method using general similarity func- tions. The classification rule measures the similarity the test data each class, and then assigns the test data to the class such that the weighed average of the similarity between the test data and the training data belonging to that class is maximized over all the classes. Inspired by this classification method, now consider using general symmetric and continuous function S: X' x X - [0, as the similarity function our CDS model. We propose the following hypothesis,
hs(x, y)
Σ axS(xxx)). y.
(1)
In the next section, we derive generalization bound for the unsupervised similarity- based classifier based on the above hypothesis, and such generalization bound leads to discriminative similarities for data clustering. When is a PSD) kernel, minimizing the generalization error bound amounts to minimization of new form of kernel similarity between data from different clusters, which lays the foundation of new clustering algorithm presented in Section 5.
4 GENERALIZATION BOUND FOR SIMILARITY-BASER CLASSIFIER
In this section, the generalization eπror bound for the classification model in Definition 3.1 with the unsupervised similarity- based classifier is derived as a sum discriminative similarity between the data from different classes.

---

Published as a conference paper at ICLR 2022
4.1 GENERALIZATION BOUND
The following notations are introduced before our analysis. Let a = [an,...,aall be the nonzero weights that sum up to 1, ax(1) be x 1 column vector representing the weights belonging to class y such that ox (v) is 04 if y y/s and otherwise. The margin of the labeled sample (x, y) is defined as mag (x, y) = hs(x, y) - y hs (x,z'), the sample (x, y) is classified correctly if m/s (x, y) 2 0.
The general similarity- classifier fs predicts the label of the input x by fs(x) (I...cc (s,( v). We then begin to derive the generalization error bound for fs using the Rademacher complexity of the function class comprised of all the possible margin functions mAs-
The Rademacher complexity (Bartlett & Mendelson, 2003; Koltchinskii, 2001) of function class is defined below:
Definition 4.1. Let (o; j be n i.i.d. random variables such that Pr(o; = 1] = Pr(o; = 1] =
The Rademacher complexity of a function class A is defined as
((A) = (x.).
sup heA
,,,(x;))
(2)
In order to analyze the generalization property of the classification rule using the general similarity function, we first investigate the properties of general similarity function and its relationship to PSD) kernels in terms of eigenvalues and eigenfunctions of the associated integral operator. The integral operator (x) = f S(x, ft)( is well defined. It can be verified that Ls is compact operator since S is continuous. According the spectral theorem in operator theory, there exists an orthonormal basis {Φ1, d2..... of L which is comprised of the eigenfunctions of Lg, where L is the space of measurable functions which are defined over X' and square Lebesgue integrable. du is the eigenfunction of Ls with eigenvalue d if Lsdæ λROa. The following lemma shows that under certain assumption on the eigenvalues and eigenfunctions of Lg, a general symmetric and continuous similarity can be decomposed into two PSD kernels.
Lemma 4.1. Suppose S: X' X' [0, 1] is a symmetric continuous function, and {)+} and {dv} are the eigenvalues and eigenfunctions of L.g respectively. Suppose Σ )xlox(x)f < C for some #21
constant C' >>> 0. Then S(x, t)
Σ (x for any x, X, and it can be decomposed as 4>1
the difference between two positive semi-definite kernels: S(x, t) = St (x, - 5-(x,, t), with
(x)
Σ
(x)x(x)
(x = Σ (xlox(x)ox(t))
(3)
k: 2.20
We now use a regularization term to bound the Rademacher complexity for the classification rule using the general similarity function. Let 2 (a) Σ a(v) st and Ω (a)
=
y=1
Σ (w) s a (v) with |i S (x,, X3) and [S- S (xi,, The space Hy of all the
hypothesis hs(: y) associated with label y is defined as
Hs.y = ((x,)) + Σ S(x( 220222000 0, a = - 1,0 < B=2 5 (a) < B
à: vy=
with positive number B+ and B- which bound Ω+ and Ω respec- tively. Let the hypothesis space comprising all possible margin functions be H. = {(x( y) + mas (x, y): hs(x, v) E H. We then present the main result in this section about the generaliza- tion eиror of unsupervised similarity-bart based classifier fs-
for 1 S y
Theorem 4.2. Given the discriminative model My = (S,fs), suppose a (a) S B+2 Q (a) < B supxex |St (x, x)) < R², supxe SS x) < R² for positive constants B+, B and R. Then with probability 5 over the labeled data S with respect to any distribution in PXY, under
5

---

Published as a conference paper at ICLR 2022
the assumptions of Lemma 4.1, the generalization error of the general classifier fs satisfies R(Js) Pr * [s(X)
{fn(s)) + 8R(2c 1)((tt + BB+ + (166(20- 1)(Bt 1+ + B R²
log 3 2n
+ +1)
7
where (fs) = Σ ①
-agmax hs),)) is the empirical loss of fs the labeled
i=1
data, > 0 is constant and + is defined as ((x) = min (1, max (0, - x}}. Moreover, if 2 1, the empirical loss (fs) satisfies
Rn()s) S
n
a aa ((x; + ny Igisjšn
Σ
n
2(a; + ax) Xl)l (5)
NY fj=1
2
The indicator function E in (5) is if event F. is true, and O otherwise.
Remark 4.3. Lemma E.3 in the Appendix shows that the Rademacher complexity of Hly is bounded in terms of B and B=, and that is why these two quantities appear on the RHS of (4). In addition, when S is Positive Semi-Definite (PSD) kernel K, can be verified that S = 0, S St.
and
Remark 4.4. When the decomposition S = S S exists and S S are PSD kernels, S is the kernel some Reproducing Kernel Krein Space (RKKS) (Mary, 2003). Ong et al. (2004) and Loosli et al. (2016) analyzed the problem of learning SVM-style classifiers with indefinite kernels from the Krein space. However, their work does not show when and how an indefinite and general similarity function can have PSD decomposition,
well as the generalization analysis for the similarity- -based classifier using such general indefinite function as similarity measure. Our analysis deals with these problems in Lemma 4.1 and Theorem 4.2. It should be emphasized that generalization bound is of independent interest in supervised learning, because it is among the few results of generalization bounds using general similarity- classifier. Section B. shows that the our bound a principled result with strong connection to established generalization error bound for Support Vector Machines (SVMs) or Kernel Machines.
4.2
CLUSTERING BY DISCRIMINATIVE SIMILARITY
We let
(6) be the discriminative similarity between data from different classes, which is induced by the gener- alization error bound (4) for the unsupervised general similarity-base classifier fs. Minimizing the bound (4) motivates us to consider the optimization problem that minimizes R, (Js) + X(2+ (ax) +
S 2(a; + axx)S(x,,, x,) 2Aa,a, (xx,,,)(xx;;)))) 2Aa,a, -xx,,,,)-xxxxx
Ω (a:).. Replacing R,, (fs) by its upper bound in (5), consider the following problem,
min a.y
Ssim HI
y,,
as +
xx) T a
2
1gi<jSn
11=1
s.t. a 2 0,1 a= 1,y
where is the weighting parameter for the regularization term 22+ (a) + (a)).. Note that do not set \ to 16e(2o-1)R* (111)))22-8/222221-111 exactly matching the RHS of (4), because À controls V2y
the weight the regularization term which bounds the unknown complexity of the function class H.s. Note that (7) encourages the discriminative similarity Swim between the data from different classes small. The optimization problem (7) forms the formulation of Clustering by Discriminative Similarity (CDS).
By Remark 4.3, when S is a PSD kernel K, S- = 0, S = St, Ssim reduces to the following discriminative similarity for PSD kernels:
K 2(a; + aj Ao;a;) x,),1 S í,j S n,
(8)

---

Published as a conference paper at ICLR 2022
and Stj is the similarity induced by the unsupervised kernel classifier by the kernel K.
Without loss of generality, we K (x) exp( kernel with kernel bandwidth 7 > O, and we omit the constant that makes integral of K unit.
|| which is the isotropic Gaussian
When setting the general similarity function to kernel K,, CDS aims to minimize the error bound for the corresponding unsupervised kernel classifier, which amounts to minimizing the following objective function
min (1
Σ
S I
Σ i,=1
04 a
k K-(x: Xj) + do Ko.
2
isKjjS
where si is defined in (8) with K= K,. K R and Kij K,(x; - -x)). À is tuned such that 5 2 0. e.g., À S 2. In Section A, it is shown that the discriminative similarity (8) can also be induced from the perspective kernel density classification by kernel density estimators with nonuniform weights. It supports the theoretical justification for the induced discriminative similarity in this section.
5 APPLICATION TO DATA CLUSTERING
In this section, we propose novel data clustering method termed Clustering by Discriminative Similarity via unsupervised Kernel classification (CDSK) which is empirical method inspired by our CDS model when the similarity function a PSD kernel = Ky. accordance with the CDS model in Section 4.2, CDSK aims to minimize (9). However, problem (9) involves minimization with respect to discrete cluster labels y = {bk} which is NP-hard. In addition, it potentially results in a trivial solution which puts all the data in single cluster due to the lack of constraints the cluster balance. When Y is a binary matrix where each column is a membership vector for a
particular cluster,
SK Mn Tr( YY). Therefore, (9) is relaxed in the proposed Isiginn optimization problem for CDSK below:
TT -
a4 a K2 (x: X3) + do T Ka s.t. DD = Ics
min YER
2
1-1=1
(10)
where A fx:: a 2 a S
S D S the graph Laplacian computed with S" D is diagonal matrix with each diagonal element being the sum of the corresponding row of SK: [
22 sK. La is
e identity matrix, e is the number of clusters. The
constraint in (10) is used balance the cluster size. This is because minimizing (9) without any constraint on the cluster size results in a trivial solution where all data points form a single cluster. Inspired by spectral clustering (Ng et al., 2001), the constraint Y DDK = I. used in CDSK prevents imbalanced data clusters.
Problem (10) optimized by coordinate descent. In each iteration of coordinate descent, optimiza- tion with respect to Y is performed with fixed which is exactly the same problem as that of spectral clustering with a solution formed by the smallest e eigenvectors of the normalized graph Laplacian >
then the optimization with respect Y. which is standard constrained quadratic programming problem. The iteration of coordinate descent proceeds until convergence or the maximum iteration number M achieved. Each itera- tion solves two subproblems, (1I) and (12). In order to promote sparsity of a be initialized
performed with fixed
by solving Σ x; Ej X,aj +||aa lo for a positive weighting parameter 7 0.1. The algorithm of CDSK is described in Algorithm 1.
Furthermore, Section in the appendix explains the theoretical properties of the coordinate descent algorithm for problem (10).
The baseline named SC-NS performs spectral clustering on the nonparametric similarity proposed in Yang al. (2014a). The baseline named SC-MS first constructs similarity matrix between data
7

---

Published as a conference paper at ICLR 2022
Algorithm 1 Clustering by Discriminative Similarity via unsupervised Kernel classification (CDSK)
Input: Unlabeled dataset [xi]i=> parameter X, maximum iteration number M.
for 4- 1 to M do
With fixed a, solve
min Lx Y Yxauxe
stt YDDYY= =6
(11)
With fixed Y, solve
min TrY Ix aεA,
Σ
a, + 0f
K- x;) + + T Ka
i==1
s. Y D
(12)
end for Perform K-Means Clustering on rows of Y to obtain the clustering result.
denoted by W. where Wi (x; Xj). then optimize the kernel bandwidth h by minimizing Σ x + Σ W Weyx,ll lla where d, - Σ Wij. SC-MS then performs spectral clustering on W with
the kernel bandwidth h obtained from the optimization.
To demonstrate the advantage of the proposed parametric discriminative similarity, we compare CDSK to various baseline clustering methods. SC stands for Spectral Clustering, which is the best performer among spectral clustering with similarity matrix set by Gaussian kernel (SCK), spectral clustering with similarity matrix set by manifold-baid baseddddddadddd--eo similarity learning method (SC-MS) (Kara- suyama & Mamitsuka, 2013), and spectral clustering with similarity matrix set by the nonparametric discriminative similarity (SC-NS) in Yang al. (2014a). In SC-MS, Gaussian kernel is used as data similarity, and the parameters of the diagonal covariance matrix is optimized so as to minimize the data reconstruction error term. SC-NS minimizes nonparametric kernel similarity between data across different clusters, which is the same objective as that of kernel K-Means (Schölkopf et al., 1998), so its performance is the same as kernel K-Means. Please refer to Section for discussion about other baselines.
Datasets. We conduct experiments on the Yale face dataset, UCI Ionosphere dataset, the MNIST handwritten digits dataset and the Georgia Face dataset. The Yale face dataset has face images of 15 people with 11 images for each person. The lonosphere data contains 351 points of dimensionality 34. The Georgia Face dataset contains images of 50 people, and each person is represented by 15 color images with cluttered background. COIL-20 dataset has 1440 images of size 32 x 32 for 20 objects with background removed in all images. The COIL-100 dataset contains 100 objects with 72 images of size 32 x 32 for each object. CMU PIE face data contains 11554 cropped face images of size 32 32 for 68 persons, and there are around 170 facial images for each person under different illumination and expressions. The UMIST face dataset is comprised of 575 images of size 112 92 for 20 people. CMU Multi-PIE (MPIE) data (Gross et al., 2010) contains 8916 facial images captured in four sessions. The MNIST handwritten digits database has a total number of 70000 samples of dimensionality 1024 for digits from 0 to The digits are normalized and centered in a fixed-size image. The Extended Yale Face Database B (Yale-B) dataset contains face images for 38 subjects with 64 frontal face images taken under different illuminations for each subject. CIFAR- 10 dataset consists of 50000 training images and 10000 testing images in 10 classes, and each image is color one of size 32 32, and we perform data clustering using all the training and testing images. We also use the minilmageNet dataset used in Vinyals et al. (2016) to evaluate the potential of clustering methods. MinilmageNet consists of 60, 000 color images of size 84 x 84 with 100 classes, and each class has 600 images. MinilmageNet is known to be more complex than the CIFAR-I0 10 dataset, and we perform clustering on the 64 classes in minilmageNet which are used for few-shot learning, so 38, 400 images used for clustering. For every clustering method involving randomness such as K- M-Mens,, we report the average performance of running it for 10 times.
Performance Measures and Tuning À by Cross Validation. We use Accuracy (AC) and Normal- ized Mutual Information (NMI) (Zheng et al., 2004) as the performance measures. The results of different clustering methods are shown in Table I and Table 2 in the format of AC(NMI). Except
8

---

Published as a conference paper at ICLR 2022
for SC-MS, the kernel bandwidth in all methods is set as the variance of the pairwise Euclidean distance between the data. À is the weight for the regularization term in our derived generalization bound. As explained in Section B.1 of the appendix, À plays the same role the weight in the reg- ularization term of SVMs or Kernel Machines. Following the common practice in the literature of SVM or Kernel Machines, À can be tuned by Cross- Validation (CV). While this is an unsupervised learning task and these is no labeled data for CV, we still developed well-motivated CV proce- dure. Following the practice in Mairal et al. (2012), we randomly sampled 10% of the given data as the validation data, then perform CDSK on the validation data. The best À is chosen among the discrete values between [0.05, 05] with a step of 0.05 which minimizes the average entropy of the obtained embedding matrix Y E R by Algorithm 1, where the average entropy is compute as
This is because we would like to choose À which renders the most entropy(softmaxxYY)
R
confident clustering embedding. We perform CDSK on all the datasets using this tuning strategy and observe improved performance as shown in the above two tables. For clustering methods involving random operations, the average performance over 10 runs is reported.
Computational Complexity. Suppose the optimization of CDSK comprises M iterations of co- ordinate descent. The first subproblem (II) in Algorithm takes O(n'c) steps using truncated Singular Value Decomposition (SVD) by Krylov subspace iterative method. We adopt Sequen- tial Minimal Optimization (SMO) (Platt, 1998) solve the second subproblem (12), which takes roughly (nn..)) steps as reported in Platt (1998). Therefore, the overall time complexity of CDSK OMM en² Mn2-1). M is set to 20 throughout all the experiments.
Table 1: Clustering results on Yale-B, B, lonosphere, Georgia Face, COIL-20, COIL-100, CMU PIE and UMIST Face.
Methods
Dataset
Yale-B
Lonosphere
Georgia Face
COIL-20
COIL-100
CMU PIE
UMIST
K-Means
0.0%x0.13)
0.71(0.13)
0.50(0.69)
0.65(0.76)
0.4910.75)
0,08(0.19)
0.42(0.64) 64)
SC
0.11(0.15)
0.74(0.22)
0.52(0.70)
0.43(0.62)
0.28(0.59)
0007(0.18)
0.42(0.61)
2'-Graph (Ellaamitar Vidal, 2013)
0.79(0.78)
0.31(0.1))
0,54(0.70)
0.79(0.91)
0.330 80)
0.440.34)
0.44K0.63)
SMCE SMCE (Elhamifar & Vidal. 2011)
0.34(0.39)
0.68/0.09)
0.60(0.74)
0.880088))
0.5610.81)
0.16(0.34)
0.45(0.66)
Lap-2" -Graph ( (Yang al., 201-b)
0.70X0.78)
0.50(0.09)
0,38(0.7))
0.79(0.91)
0.56(0.81)
0.30(0.51)
0.50X0.69)
RAG (Zhu al., 2014)
0.13(0.19)
0.70(0.11)
0.17(0.38)
0,50(0.64)
0,58(0.81)
0.14(0.34)
0.26(0.28 (8)
MMC al. 2004)
(.71(0.69)
0,75(0.21)
0,42(0.55 585)
0.8000889
0.61(0.63)
22)
0.31(0.56)
3MMC al., 2014)
0.63(0.63)
0.7010.15)
0.34(0.41)
0.82(0.93)
0.64(0.69) 69)
0.18(0.23)
0.55(0.61)
RIM (Gomes el al., 2010)
0.62(0.74)
0.39(0308)
0,39(0.56)
0,77(0.82)
0.71(0.79)
0,26(0.34)
0.40XU.53)
KanooF al,, 2021)
0.39(0.33)
0.62(0.05)
0.180..00 40)
0.65(.75)
0.3610 64)
0,1500.56
0.2900.4)
CDSK (Ours)
0.83(0.86)
0.76(0.25)
0.64)0.74)
0,9310.97)
0.7810.92)
0.32(0.50)
0.67(0.80)
Table 2: Clustering results on CMU Multi-PIE which contains the facial images captured in four sessions (S1 to S4), MNIST, CIFAR-10, and Mini- Mini-ImageNet
Dataset
MPTE SI
S2
MPIE S3
MPTE S4
MNIST
CIFAR-10
Mini-ImageNer
Methods
KM
0.12(0.50)
0.13(0.48)
0.52(0.47) 0.13(149) 0,130.48)
0.1900.06)
0.27(0333)
SC
0.13(0.53)
0.14(0.51)
0.14(0.52)
0.15(0.53)
0.38(0.36)
0.21(0.04)
0.29(0.35)
(1 G.Grrah (Fllhmmifar & Vidal, 2013)
0.59(0.77)
0.70(0.81)
0.63(0.79)
0.68(0.81)
0.57(0.61)
0,28(0.24 24)
0.28(0.37)
SMCE (Elharmiar & Vidal, 2011)
0.17(0.55)
0.19(0.53)
0.19(0.52)
0.18(0,53)
0.65(0.67)
0.31(0.30)
0.29(0.37)
Lap-2" -Graph ( (Yang ot al., 2014b)
0.3910.77
0.7010.81)
0.63(0.79)
0.68(0.81)
0.56(0.60)
0.29(0.30)
0.29X0.37)
RAG (Zhu al., 2014)
0.3410.75)
0.30(0.69)
0,31(0.68)
0,29:0,705
0.59(0.51)
0.22(0.10)
0. 0.18(0.33)
MMC et ol., 2004)
0,4900.88)
0.31(0.60)
0.53(0.65)
0.30X0.61)
0.64(0.60)
0.31 28)
O. 19X0.44)
SMMC/Chen et al. 2014)
0.4010.51)
0.4410.59)
0.45(0.61)
0.49(0.66)
0.66(0.69)
0.29(0.26)
0.16(0.32)
RIM [Gomes et al., 2010)
0.50(0.63)
0.52(0.68)
0.55(0.71)
0,31(0.67)
0.34(0.62)
0.20(0.25)
0.17(0.38)
KanioF (Bicego al,, 2021)
0.54(0385)
0.55(0.86)
0.6400866)
0.62(0.86)
0.48/0.39
0.2010.99
0.20(0.38)
CDSK (Ours)
0.66(0.85)
0.72(0.88)
0.68(
0.73(0.89)
0.76(0.75)
0.46(0.39)
0.31(0..41
CONCLUSION
We propose a new clustering framework termed Clustering by Diseriminative Similarity (CDS), which searches for the optimal partition of data where the associated unsupervised classifier has minimum generalization error bound. Under this framework, discriminative similarity is induced by the generalization error bound for unsupervised similarity-based classifier, and CDS minimizes discriminative similarity between different clusters. It is also proved that the discriminative similar- ity can be induced from kernel density classification. Based on CDS, we propose new clustering method named CDSK (CDS via unsupervised kernel classification), and demonstrate its effective- ness in data clustering.

---

Published as a conference paper at ICLR 2022
REFERENCES
Maria-Florina Balcan, Avrim Blum, and Nathan Srebro. A theory of learning with similarity func- tions. Mach. Learn., 72(1-2):89-11 2008.
Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 3:463-482, March 2003.
Manuele Bicego, Ferdinando Cicalese, and Antonella Mensi. Ratiorf: a novel measure for random forest clustering based on the tversky's ratio model. IEEE Transactions Knowledge and Data Engineering, pp. 1-1, 2021.
Changyou Chen, Jun Zhu, and Xinhua Zhang. Robust bayesian max-margin clustering, In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 27: Annual Conference Neural Informa- tion Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pp. 532-540, 2014.
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Multi-class classification with maxi- mum margin multiple kernel. In Proceedings of the 30th International Conference Machine Learning (ICML), pp. 46-54, Atlanta, GA, 2013.
Ehsan Elhamifar and René Vidal. Sparse manifold clustering and embedding. Advances in Neural Information Processing Systems (NIPS). pp. 55-63, Granada, Spain, 2011.
Ehsan Elhamifar and René Vidal. Sparse subspace clustering: Algorithm, theory, and applications. IEEE Trans. Puttern Anal. Mach. Intell., 35(11))275--2781 2013.
Evarist Gine and Joel Zinn. Some limit theorems for empirical processes. Ann. Probah., 12(4): 929-989, 11 1984.
Mark Girolami and Chao He. Probability density estimation from optimally condensed data samples. IEEE Trans. Pattern Anal. Mach. Intell., (5(10):1253-1265 2003.
Ryan Gomes, Andreas Krause, and Pietro Perona. Discriminative clustering by regularized informa- tion maximization. Advances in Neural Information Processing Systems (NIPS), pp. 775-783, Vancouver, Canada, 2010.
Ralph Gross, lain A. Matthews, Jeffrey F. Cohn, Takeo Kanade, and Simon Baker. Multi-pie. Image Vis. Comput., 28(5)8807-813, 2010.
J. A. Hartigan and M. A. Wong. A K-means clustering algorithm. Applied Statistics, 28:100-108, 1979.
Gao Huang, Tianchi Liu, Yan Yang, Zhiping Lin, Shiji Song, and Cheng Wu. Discriminative clus- tering via extreme learning machine. Neural Networks, 70:1-8, 2015.
Masayuki Karasuyama and Hiroshi Mamitsuka. Manifold-based similarity adaptation for label prop- agation. In Advances Neural Information Processing Systems (NIPS), pp. 1547-1555, Lake Tahoe, NV, 2013.
Zohar Shay Karnin, Edo Liberty. Shachar Lovett, Roy Schwartz, and Omri Weinstein. Unsupervised SVMs: On the complexity of the furthest hyperplane problem. In Proceedings of the 25th Annual Conference on Learning Theory (COLT), pp. 2.1-2.17. Edinburgh, Scotland, 2012.
JooSeuk Kim and Clayton D. Scott. Performance analysis for 1.2 kernel classification. In Advances in Neural Information Processing Systems (NIPS), pp. 833-840, Vancouver, Canada, 2008
JooSeuk Kim and Clayton D. Scott. Robust kernel density estimation. J. Mach. Learn. Res., 13: 2529-2565, 2012.
V. Koltchinskii and D. Panchenko. Empirical margin distributions and bounding the generalization error of combined classifiers. Ann. Statist., 30(1):1-50, 02 2002. doi: 1312///3001366118.
10

---

Published as a conference paper at ICLR 2022
Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Trans. Inf. Theory, 17(5):1902-1914 2001.
James R. Lee, Shayan Oveis Gharan, and Luca Trevisan. Multi-way way spectral partitioning and higher- order cheeger inequalities. In Howard J. Karloff and Toniann Pitassi (eds.), Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 22, 2012, pp. 1117-1130. ACM, 2012.
Gaëlle Loosli, Stéphane Canu, and Cheng Soon Ong. Learning SVM in krein spaces. IEEE Trans. Pattern Anal. Mach. Intell., 38(6): 1204-1216, 2016.
Ravi Sastry Ganti Mahapatruni and Alexander G. Gray, CAKE: convex adaptive kemel density estimation. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 498-506, Fort Lauderdale, FL., 2011.
Julien Mairal, Francis Bach, and Jean Ponce. Task-driven dictionary learning. JEEE Transactions on Puttern Analysis and Machine Intelligence, 34(4):791-804 2012.
Xavier Mary. Hilbertian subspaces, subdualities and applications. Ph.D. Dissertation, Institut Na- lional des Sciences Appliquees Rouen, 2003.
Andrew Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems (NIPS), pp. 849-856, Vancouver, Canada], 2001.
Vu Nguyen, Dinh Q. Phung, Trung Le, and Hung Bui. Diseriminative bayesian nonparametric clustering. In Carles Sierra (ed.), Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19-25, 2017, pp. 2550-2556. ijcai.org, 2017.
the
Cheng Soon Ong, Xavier Mary, Stéphane Canu, and Alexander J. Smola. Learning with non- positive kernels. In Proceedings of the Twenty-first International Conference on Machine Learn- ing (ICML), Banff, Alberta, Canada, 2004.
John Platr. Sequential minimal optimization: A fast algorithm for training support vector machines. Technical report, 1998.
Bernhard Schölkopf, Alexander Smola, and Klaus-Robert Müller. Nonlinear component analysis as kernel eigenvalue problem. Neural Comput., 1995):129- July 1998.
Noam Shental, Assaf Zomet, Tomer Hertz, and Yair Weiss. Pairwise clustering and graphical mod- els. In Advances in Neural Information Processing Systems (NIPS), pp. 185-192, Vancouver and Whistler, Canada, 2003.
Mahdi Soltanolkotabi and Emmanuel J. Candes. A geometric analysis of subspace clustering with outliers. Ann. Statist., 40(4):2195-23) 2238, 08 2012.
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Match- ing networks for one shot learning. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pp. 5630-3638, 2016.
Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. In Advances in Neural Information Processing Systems (NIPS), pp. 1537-1544, Vancouver, Canada], 2004.
Shuicheng Yan and Huan Wang- Semi-supervised learning by sparse representation. In Proceedings of the SIAM International Conference on Data Mining (SDM), pp. 792-801, Sparks, NV, 2009.
Yingzhen Yang, Feng Liang, Shuicheng Yan, Zhangyang Wang, and Thomas S. Huang. On a theory of nonparametric pairwise similarity for clustering: Connecting clustering to classification. In Advances Neural Information Processing Systems (NIPS), pp. 145-153, Montreal, Canada, 2014a.
11

---

Published as a conference paper at ICLR 2022
Yingzhen Yang. Zhangyang Wang, Jianchao Yang. Jiangping Wang, Shiyu Chang, and Thomas S. Huang. Data clustering by laplacian regularized 11 11-graph. In Proceedings of the Twenty-Eighn AAAI Conference Artificial Intelligence (AAAI), pp. 3148-3144 Québec City, Canada, 2014b.
Xin Zheng, Deng Cai, Xiaofei He, Wei- Ma, and Xueyin Lin. Locality preserving clustering for image database. Proceedings of the 12th ACM International Conference on Multimedia (MM), pp. 885 891, New York, NY, 2004.
Xiatian Zhu, Chen Change Loy, and Shaogang Gong. Constructing robust affinity graphs for spectral clustering. In 2014 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1450- 1457, 2014.
A CONNECTION TO KERNEL DENSITY CLASSIFICATION
In this section, we show that the discriminative similarity (8) can also be induced from kernel den- sity classification with varying weights on the data, and binary classification is considered in this section. For any classification model My = (S. with hypothetical labeling y and the labeled data S = {x,, ) suppose the joint distribution Pxy over X' x {1, 2} has probabilistic density function p(x, y). Let Px be the induced marginal distribution over the data with probabilistic den- sity function pxx). Robust kernel density estimation methods (Girolami & He, 2003; Kim & Scott, 2008; Mahapatruni & Gray, 2011; Kim & Scott, 2012) suggest the following kernel density esti- mator where the kernel contributions of different data points are reflected by different nonnegative weights that sum up to 1:
xxx To Co, (x)xxxxxx,,x-a 20
(13)
where To (2.) Based (13), it is straightforward to obtain the following kernel density estimator of the density function p(x, y):
xxx v) TO Σ ax x;).
(14)
kyy=y
Kernel density classifier is learnt from the labeled data S and constructed by kernel density es- timators (14). Kernel density classifier resembles the Bayes classifier, and classifies the test data x based on the conditional label distribution P(Y
x), or equivalently, x is assigned class Intuitively, that the decision function F(x, a = p(x, 1) - f(x. 2) is close to the true Bayes decision func- tion r p(x, 1) - p(x, 2). Girolami & He (2003); Kim & Scott (2008) propose to use Integrated Squared Error (ISE) as the metric to measure the distance between the kernel density estimators and their true counterparts, and the oracle inequality is obtained that relates the performance of the L2 classifier in Kim & Scott (2008) to the best possible performance of kernel density classifier in the same category. ISE is adopted in our analysis of kernel density classification, and the ISE between the decision function i and the true Bayes decision function is defined as
to class 1 if p(x, 1) p(x, 2) 2 O, otherwise it is assigned
preferred
ISE(F, r) = || r122 = / (f (f-r) dx.
(15)
The upper bound for the ISE ISE(r, ?) also induces discriminative similarity between the data from different classes, which is presented in the following theorem.
Theorem A.1. Let n4 = Σ y and n2 = -T, With probability at least 1 2nz exp
f=1
:=1
2(n 1) - exx ( 2n over the labeled data S, the ISE between the decision function F(x, a) and the true Bayes decision function r(x) satisfies
To + 2Td n n-1 +6). (n-11=))
1 1111
ISE(F,r) n
(16)
where
ISE(F))) = Σ 18i3iSn
(a; + Wa+ta)),,e Kx) - -x, 11
Σ
(as + aay Kx) - -x,);
(17)
12

---

Published as a conference paper at ICLR 2022
K(()= a (K (2h)
CeagKVaN Xj) uerus
(18)
Isi<jSn
and K V2h is the gram matrix evaluated on the data fx with the kernel K V
Let A > 0 be a weighting parameter, then the cost function ISE + A ((),, designed according to the empirical term (SE(F,r) r) and the regularization term ((a) in the ISE error bound (16), can be expressed as
ISE + A(((
Σ ISicssn
S II
M - Σ
(a: ax))Kxxxxx xx) + A T K V 1,5
where the first term is comprised of sum of similarity between data from different classes with sim- ilarity S 4(a; + K - xj). and S is the discriminative similarity induced by the ISE bound for kernel density classification. Note that S has the same form as the discrim- inative similarity S (8) induced by our CDS model, up scaling constant and the choice of the balancing parameter X. The proof of Theorem A.1 is deferred to Section E.3.
B MORE EXPLANATION ABOUT THE THEORETICAL RESULTS IN SECTION 4.1
B.1 THEORETICAL SIGNIFICANCE OF THE BOUND (4)
To the best of our knowledge, generalization error bound (4) is the first principled result about generalization error bound for general similarity-basee classifier with strong connection to the es- tablished generalization error bound for Support Vector Machines (SVMs) Kernel Machines.
We now explain this claim. When the similarity function 5 is a PSD kernel function, we have S- = S = 5 explained in Remark 4.3. As reminder, S is the general similarity function used in the similarity-based classification, and S+ S are PSD kernel functions, and is proved that S can be decomposed by S S under the mild conditions of Lemma 3.1. follows that we can set (ax) = O and B 0. Plugging B = in the derived generalization error bound for the general similarity-bas based classification (4), have
Prob YY # fs(X)) Rn((s)+ 8R(2c 1)cB+
+ (160(20-1BB+R R²
+1)
log 4
3
(19)
7/n
2n
According to its definition, (2+(a)) = Σ (v) (x because
St. We define = B+
y=1
Because (ax) S B+ as mentioned Theorem 3.2, B satisfies
Σ a(v) Sa(1)) < B². As
#=1
result, when S is PSD keree function, inequality (19) becomes
Prob YY # fs(X)] < (fs))) 8R(2c 1)cB +
[16c(2c (16c(2c-1)RP2 1)R2B
+1)
log
(20)
2n
with Σ (v) Sa < B
Note that the bound (20) in fact the generalization error bound for supervised learning when using as the similarity function in the similarity-based classification. At the end of this subsection, we
provide lemma proving that Σ (v) (S(()) B² T Sa cB², where is the number of classes.
Now we compare the generalization enror bound (20) to the established generalization error bound for Kernel Machines in Bartlett & Mendelson (2003, Theorem 21) for the case that 2 with
13

---

Published as a conference paper at ICLR 2022
notations adapted our analysis. The bound in Bartlett & Mendelson (2003, Theorem 21) is for binary classification, which presented as follows:
Prob [Y # fs(X)] & (fs)s))+ + AVRB
log 4/6
TVn (11))
2n a
TT Sa S B².
(21)
Comparing our generalization error bound (2) with e 2 to the max-ma max-margin generalization error bound (21), it can be easily seen that the two bounds are equivalent up to constant scaling factor. In fact, our bound (2) is more general which handles multi-class classification.
Lemma B.I. When S' is a PSD kernel, then Σ
(v)
( <B² = a Sa S cBa
Proof. Let H. be the Reproducing Kernel Hilbert Space associated with the PSD kernel function S, and H. is also called the feature space associated with S. We use (::)x to denote the inner product in the feature space H. Then we have 5(x,, Xj) = Siz = (#(x,, ((x)))H where the feature Σ a², be verified that
mapping associated with H. Because
To
Σ E a < (x))
n n
Σ (x,() s c ②
#
(ey. ey)ms where eg y=1
j=1
Σ (x.). It follows that a Sa S E a Sa ())) s cB.
B.2 TIGHTNESS OF THE BOUND
Note
that the generalization error Pr h)(
f(X)) is bounded by (,)
Σ (x..))
in Theorem 4.2. The underlying principle behind this bound and
1=1
all such bounds the statistical machine learning literature such as Bartlett Mendelson (2003) is the following property about empirical process (adjusted using our notations):
R(H & Ex.y sup Ex (f( R,, < 2 hEH
(22)
where Ex,y indicates expectation with respect to random couple (x. v) ~ Pxy, and Pxy is a joint distribution discriminative model My = (S. (22) is introduced the classical properties of empirical process in Gine & Zinn (1984). By Lemma E.2 of this paper, with probability least lid.
1 - 8 over the data 1x ~ PXY.
R(H) < (2c- 1)c-1)e
In 2n
B VT
B V2Bc(2c 111/ Vn
O
(23)
for constant B. It follows from (22), (23), and concentration inequality (such as McDiarmid's inequality) that for each sufficiently large n, with large probability, SリPдEи Rxx R, (f)) is less than O ) Therefore, we can bound the expectation of the empirical loss, i.e., Ex,, Ru, (f),
tightly using the empirical loss (f. uniformly over the function space H.
C THEORETICAL PROPERTIES OF THE COORDINATE DESCENT ALGORITHM IN SECTION 5
In this subsection, we give detailed explanation about the theoretical properties of the coordinate descent algorithm presented Section 5. We first explain how the objective function CDSK (10) is connected to the objective function (9) developed in theoretical analysis. It should be empha- sized that (9) cannot be directly used for data clustering since cannot avoids the trivial solution where all the data in single cluster. We adopt the broadly used formulation of normalized
14

---

Published as a conference paper at ICLR 2022
and use
cut(Ar vol(Ax)
to replace
S {dj
Σ
pitu, in (9), leading to the following optimization
problem:
min aEA.)=(v:)
cut(AA A&)
Σ b1=1
04
a,+ay
Kr(x; xj) + doe A TK - Q(x,)))
(9))
vol(A:)
2
where {A k= are data clusters according to the cluster labels {ur A& the complement of Ag. S We have the following theorem, which
cut(A B)
S E
Σ
vol(A) xEAAIsii
E
can derived based on Theorem 4.1 in the work multi-way Cheeger incqualities (Lee et al., 2012).
Theorem C.1. minagA,y
.u,(AA,A.)) vol(At) 2 Σ (Irr), where Loo is the normalized graph [m]
Laplacian L nuo (D*))1/211 ) 1 S indicates a Cb for some constant C' and ox(+) indicates the i-th smallest singular value of matrix.
Based on Theorem C.I, we resort to solve the following more tractable problem, that is,
&
as taj Kx - xx) + aa Ka & Q((a).
min GEA
nor
(9")
2
because Q (9") is upper bound for Q (9') up constant scaling factor. It can be verified that problem (10) is equivalent to (9"), and (9") is the underlying optimization problem for data clustering in Section 5. The following proposition shows that the iterative coordinate descent algorithm in Section 5 reduces the value of Q at each iteration.
Proposition C.2. The coordinate descent algorithm for problem (10) reduces the value of the ob- jective function ((x)) at each iteration.
Proof. Let Q' Y) & L
Σ aatas K, (x: X2) + Xa Ka, and use
perseript to denote the iteration number of coordinate descent. At iteration m, after solving the subproblems (11) and (12), have ('(a!"), Y ((a(m)). At iteration m + 1, by solving the subproblems (4) and (3) in order again, have (((a(()))) y(m+1)) (m)())))) Be- cause of the nature of coordinate descent, Q' (m(+) y(m+1)) < (a(mm)) (m)),, it follows that Q(a((m))) < (()(
Based on Proposition C.2, the iterations of coordinate descent are similar to that of EM algorithms and they reduce the value of Q, where Y plays the role of latent variable for EM algorithms.
D MORE DETAILS ABOUT OPTIMIZATION OF CDSK
The optimization of CDSK comprises M iterations of coordinate descent, wherein each iteration solves the following two subproblems.
1) With constant ax,
min L st. D Y
(24)
2) With constant Y.
n
min I a,λ,
Σ
ai aj
K 7x; x,) + da TaTo Ka
2
1-=1
s.t. Y D
(25)
15

---

for any Published as a conference paper at ICLR 2022
The first subproblem (24) takes Onn'c) steps using truncated Singular Value Decomposition (SVD) by Krylov subspace iterative method. We adopt Sequential Minimal Optimization (SMO) (Platt, 1998) to solve the second subproblem (25), which takes roughly ( steps reported in Platt (1998). SMO is an iterative algorithm where each iteration of SMO solves the quadratic program- ming (25) with respect only two elements of the weights a, that each iteration of SMO can be performed efficiently. Therefore, the overall time complexity of CDSK is (M + M..
E PROOFS
E. PROOF OF LEMMA 4.1
Before stating the proof of Lemma 4.1, we introduce the famous spectral theorem in operator theory below.
Theorem E.1. (Spectral Theorem) Let be compact linear operator on a Hilbert space H. Then
there exists in H an orthonormal basis {Φ1. Ø2....; consisting of cigenvectors of L. If X is the eigenvalue corresponding to Φk: then the set {Ax} is either finite or X - when k oc. In addition, the eigenvalues are real if T. is self-adjoint.
Recall that the integral operator by S' is defined as
(Lss))x)= - s(x,t))(t)dt
and we are ready to prove Lemma 4.1.
Proof of Lemma 4.1. It can be verified that Lg is compact operator. Therefore, according to Theorem E.1, { an orthogonal basis of L Note that Φv the eigenfunction of Lg with eigenvalue A if Leda = λRda.
With fixed x E X, we then have
m++
Σ (x)
m++t
(x))3
Du (t))3) k=
k=m
m++t
<VC( (x)
follows that the series
Σ {xtx(x)ox( converges to continuous function uniformly on t.
#21
This is because Φ4 = Lote A
is continuous for nonzero Å
On the other hand, for fixed x E X, function in L?
S(x, = Σ (S(x, (x))) = Σ (x)x(())
k21
Therefore, for fixed x E X, S(x, Σ Au (x)ox = ex(+) almost surely w.r.t the Lebesgue
k21
measure. Since both are continuous functions, we must have S(x,t) Σ
t X. It follows that S(x, t) (x)x(x) for any x, t X.
We now consider two series which correspond to the positive eigenvalues and negative eigenvalues (x)))(())) Using similar argument, for fixed
of Ls. namely
Σ )xox(x))x() and
lo:
k:Ae
16

---

Published as a conference paper at ICLR 2022
both series converge continuous function, and we let
S (x, Σ (x)x(x)(x(t),
A0
S (x, =
Σ (x)
A=ApK00
(* t) and S S- t) are continuous function in x and t. All the eigenvalues of S and S are nonnegative, and it can be verified that both are PSD kernels since
Σ 11=1
GGj k:
Σ
(x)x(x))(xxx))
1-j=1
Ax20
Σ
A (c)ox(x)(xxxx)
k: A.
fJ=1
Σ
co((x))) 0.
k: Ac20
Similarly argument applies S Therefore, S is decomposed as S(x, t) S (xx,t) S --(xx t).
E.2 PROOF OF THEOREM 4.2
Lemma E.3 will be used in the Proof of Theorem 4.2. The following lemma is introduced for the proof of Lemma E.3, whose proof appears in the end of this subsection. Lemma E.2. The Rademacher complexity of the class Hy satisfies
R(Hs) $ (2c- - 1) ==1
Σ AHss))
(26)
Lemma E.3. Define (+x Σ av
St (v) and Ω- (a)) Σ a(w) s-a(v)
When
y=1
(+) < B+ St (a) B-² for positive constant B+ and B supxex 1 (x, | x) < R²
supxex |S- xx) R for some R > 0, then with probability at least 8 over the data (x:He the Rademacher complexity of the class Hy satisfies
A(Hs) S R(2c 1)e( B+ + B-)
In
+ +2lc2 - 1) B B
(27)
vn
2n
Proof of Lemma E.3. According Lemma 4.1, S is decomposed into two PSD kernels as S+ S Therefore, the are two Reproducing Kernel Hilbert Spaces H and Hg that are associated with 5+ and S respectively, and the canonical feature mappings in H3 and Hg are o+ and Φ= with S (x, t) (x), o (t)) 2 and S (x( t)) (x), の (t)) Hg In the following text, will omit the subscripts H k and H& without confusion.
For any 1 < c
hs(x, = Σ a;5(x, (w,, (x())) - , (x))
1: W=
with ||+ (v) (v) < B+ and || || = a(v) S- (v) < B-² Therefore,
H.s.y C H.. {(x, 8) + ar,.-t(s0 (
| 2 < B+ | 2 < B 2 s
17

---

Published as a conference paper at ICLR 2022
and R)Hs,y) - R(Hssyy) Since are deriving upper bound for R(Hs,y), we slightly abuse the notation and let H.s,y represent Hs. in the remaining part of this proof.
For x, t R² and any hi Hssy have
lhs(x) hts(t) (ww (x)) , (w (t)) (w : (t))
1ww o (x) 6* (w /tw.w//0000 (t) o (x))
S B$ f10l -100
SB* B ) (z
s 2B +B)).
We now approximate the Rademacher complexity of the function class Hssyy with its empirical
version R(Hs.) using the sample (xi). For each 1 S S Define E(2) R(Hs.)) =
(x.)
[m.))
Σ (x, wi then Σ R(Hs.)) = E [xx)) y=1
Σ E and
y=1 (x:}
E(y) 11
E(w)
sup
XnxX
hs(x v)
sup
[(r.)
sup Hs.
o, v)
sup he(-a))Hsss
Σ ipfte
oghs((,,,) v)
Xn...
h hs( v)
sup
[
sup his hss.
oshs(xi,1)
sup hs(.,))
Σ inght
(xhs(x;;0) v)
Xi..., X
o,hs((x,0)) + hs(x
sup
B(o+}
sup hs(-
oy X1, o,hs((x,,)) v)) Σ
Σ
XI........X.
i=1
ittt
n Σ
Σ oxhs((x,1)) v) hs(x 3)
sup Xi
Bioz)
sup hsl hs(-w)eH...v
o (xi, v)
n
his hs( v)
hs(21 y)
sup E 1ir, x
sup Ag(-)))Hss..
2R (B+ + B-)
n
It follows that
Σ
E 10 X .......
F (()) xi....x; 111
(B (B++++++)) Ac-
cording the McDiarmid's Inequality,
ng²
Pr
A (HHssy
Σ
A(Hs.y) 2 _0 < 2exp (- 2(B + BBB++BB)2RKK R
(28)
y=1
5=1
18

---

Published as a conference paper at ICLR 2022
Now derive the upper bound for the empirical Rademacher complexity:
Σ
RHHsy
[(a:)
sup hyE
(xis
(29)
im
os ((w
(x+(x))) ((w++o+(xx)))
- (xx))))
(m:)
sup
11
[|
SBB // 1|
(a,)
B
0 (x:)1 +B
Σ
0 (x+i]l
17
==1
1=1
==1
B+C [(a))
B
oit (xi)ll
+ -
Σ 0. (xi)ll
1=1
i=1
B+c
B + n
n
((o)))
0 (xx))?
((a))
1 0.0 (x,))1
n
B+c
B
Rc
Σ 5 (xi, x:)
+
Σ (xi, (xi, x:)
Vin
(B+ + B
Vn
By Lemma E.2, (28) and (29), with probability at least - 6, we have
R(2c- 1)((Bt BB)
In 3
RHss) $ (2c-1) 1) Σ R(Hs.)) 5
2e(2c 1)(B+ B RR²
Vn
2n
(30)
Proof of Theorem 4.2 According Theorem Koltchinskii Panchenko (2002), with proba- bility 1 - over the labeled data S with respect to any distribution in P, the generalization error of the kernel classifier fs satisfies
R(fs) < (Ss) + _o((Hs)
2/2
(31)
2n
where (fs) "2 1=1
Σ (
mag (x:.1)) empirical error of the classifier for y 0. Due the facts
that mAy (x, 1) h X1, Vi) argmax, y Yv hs (x(xx, y'), is positive vector and S is nonnegative,
have mag (x, 3) 2 hs hs(x;, (xi, vi)
Σ hs(xi, v). Note that o(-) non-increasing function,
87t6
follows that
hs(xi, v1)
Σ hs y)
Φ Mhy (xi, Ui) $
(32)
7
7
Applying Lemma E.3, (4) holds with probability 1 1 8. When 2 1, it can be verified that hs(x;, wi)
E ls((i,, w)
Σ
hs(xi, w)
04
S for all (xi, y:), that
y=1
h hs(x;. W1)
Σ hs((,,)) v)
h(x;, yi) Σ h(x;, y)
T
51
(33)
7
19

---

Published as a conference paper at ICLR 2022
Note that when (s(,,, Vi)
Σ
hs(x;,)) v) 2 0, then
hs hs(x,,
Σ
his (xs()) y)
E [0. 1] so
V#
( Σ (x
((x:th)- Σ h(x::1))
that +
(x., E hs(x;,)) y) < we
hs(x).D))~ Σ (xs,))))
(+x Σ h(x..9)
have +b
youu
2151-
Therefore, (33) always holds.
7
By the definition of (fs). (32), and (33), (5) is obtained.
Remark E.4. It can be verified that the image of the similarity function S in Lemma 4.1 and The- orem 4.2 can be generalized from [0. 1] to [0, a] for any a E IR, a 0 with the condition Y 2 replaced by z a. This is because Lg is compact operator for continuous similarity function
S: X [0, a). and (x,, ys)
Σ hs(x;, v) S Σ hs(x,, y) a. Furthermore, given u#
y=1
symmetric and continuous function S: X x X' [c, c, d R, c < d, we can obtain a symmetric and continuous function S": X' x X' + [0, 1] by setting S' = b-a
and then apply all the theoretical results of this paper to CDS with S' being the similarity function for the similarity-bast based classifier.
S-e
Proof of Lemma F.2. Inspired by Koltchinskii & Panchenko (2002), we first prove that the Rademacher complexity of the function class formed by the maximum of several hypotheses is bounded by two times the sum of the Rademacher complexity of the function classes that these hypothesis belong to. That is,
R(Hmax) S Σ RHSs.)) y=1
(34)
where Hiax (max(hh,..... hx): by Ns IS for 15
no confusion arises, the notations (fo,), {x,, y1}) are omitted in the subscript of the expectation operator in the following text, i.e.. (or)) (x..)) abbreviated to E. According to Theorem 11 of Koltchinskii & Panchenko (2002), it can be verified that
{ (C
1 Σ n2
n (osts((ss)) i=1
E (o..i
sup hE
( sup nEHS.y
n
E (xx))
oxtss(xs))
77
Therefore,
1
R(Hmax) = (x
sup he heHmax
ax)s(xx))
((os),
sup hE'maa n
(x)s((;)))*
sup he
axhss(xi))
2E (o
sup
oxhs((x))
beHama
1=1
2
13 (xwi
sup nEMss
oxhs(x)))*
"
20

---

Published as a conference paper at ICLR 2022
= 2 2 *
2
E fo 1. px.m
sup AENs,w
Σ oyhs (x:)
(Hss))
R
(35)
y=1
y=1
The equality in the third line of (35) is due to the fact that o, has the same distribution as o,- Using this fact again, (34), we have
R RHHs) = E (x.))
sup mag EHs
oamn (x1, 8i)
[=1
sup
mAg (x,, 1/ 0=
man EHl
i=1
n
sup mas EKg n
aymhs (x, 1/) 1I y=
y=1
E (ost..(x.11
sup mig EHS
Σ ==
J.mns (xi, (2 1/
2n
y=1
[o..
sup mag EHg
Σ aamhs (xi; vn)
==1
B(a,),(x)3
sup magERs
Σ arming (xi,
(36)
11
9=1
Also, for any given
Esysa
1
n
Jymbs (x,, w)
(x)
sup mag EHs
=-B(a.),(x.)
1
sup bss.wlEEssy.v I...
Σ
n
(x ochs(xx, v) orargmax, y (xx, 1/)
n
$ 1
Σ os wi
sup As(-w))Hs.s
n
im1
72
Σ a arggmax bys
+- n
sup ha(tar)) s W A
< 1 ((.)),(x.)) sup bs(-y))Hsss
Σ o.hs(xx,))) w)
+ Σ (x)))
Σ o.hi((x.8))
sup
n
(s(-)r))
iml
4'
(37)
Combining (36) and (37),
A(Hs) < y=1
E (x:)
sup
Σ oxhs((x.1) v)
hs(.:))
E [(x))((x))
sup
Σ ashs((x,
ns(-ar)EN's
8=1 y=1
(2c 1)
E [(a.).(x:)
sup As(-y)EHa.y
Σ ashss(x,10 v)
(2c 1) Σ
R(Hs.)
(38)
1=1
21

---

Published as a conference paper at ICLR 2022
E.3 PROOF OF THEOREM A.1
Proof. According to definition of ISE,
ISE(F,r) J (f (f- J f(x, a) dr
dx - o f(x, f(x, a))()) + f r(x)) dx.
(39)
Rd
For given distribution, SRL r(x)) dor is a constant. By Gaussian convolution theorem,
1 axx,a) TI E (v) (K /a -1 -1 1si<jsn
Σ
20,a, K2, I (40)
1=
where TI
(21)4/2(22A)2 Moreover,
f(x, (x))dd
Rd
= -fe p(x, 1)p(x, 1)dx + [ fxx, 2)p(xx, 2)dx / p(x, 1)p(x,, 2)dx J f(x, 2)p(x, 1)dx.
(41)
Note that
/ Rd
p(x, 1)p(x, 1)dr= = Σ / a2K=(x - x;)p(x, 1)dx,
3: M)=1
Σ s5y
ay (xi xx) y
then use the empirical term x,) xx)p(x, 1)dr. Since E (xiniiss
to approximate the integral SaL a , (x
n-1
Σ KyK, (x,-x;)),,--
Jge a,KK(x - x,)p(x, 1)dr, and
n-1
og K. (x; xx,)
bounded difference holds for
1: 191
therefore,
n-1
Σ aj Kr - 1 jgj
f aj KgKi(x - (ox((x-xx)p(xx 1)dr 2 ar8
Pr
S 2exp (-2(n 1)s
n
follows that with probability least 1 12nn exp (-2(n 1)E?), where n2 the number of data points with label i,
aj ax; - X2)
To JRd p(x, 1)p(x, 1)dx
S
Σ
age.
(42)
n
3: 81=1
Similarly, with probability least 1 2n2 exp ( 2(n 1)E2).
Σ
aj ax; X2)
<:z: (1
p(x, 2) 2)dx S Σ aje.
(43)
n
Rdd
1: v2=
It follows from (42) and (43) that with probability at least 1 - 2n (-2( 1)=?).
Σ
a, Kx; xj)
i.ji F..00
1 ff (p(x, 1)p((x 5(xx 2)xxx) 2)) Se.
(44)
To
Rd
In the same way, with probability least 1 2n (- 1-2n=?).
Σ
ag agKr (x, -x,)
j.ji #
1
+ p(x, 2)p(x 1)) Se.
(45)
n
To
22

---

Published as a conference paper at ICLR 2022
Based on (44) and (45), with probability at least 1 2nz exp (-2(n 2(n 1)E2)
22 exp (- (-2n=?),
Σ
aj (x; -x))
Σ
aj azKr(x; x₃)
f:f: #ı
[S r) S 2T0
2To
11
71
+ Ti
Σ av)) (v)
(K 22h aa()
2, K vth
(x: - xx) uy.tr + 2TOE
y=1
Isigjsn
Σ (a; + az Ky xz) A
Σ
(a; + ay)KK(x; - Xz)
SsicjSn
< 4To
71
(1) (K (2)))()-m IskjEn
Σ
2000 K /2h (x: Xj) yys
2To
1
+ te).
n
(46)
The conclusion of this theorem can be obtained from (46).
23


Reviews:
[{"review_id": "qa2MRyTpOi3", "reviewer": "Reviewer_dtfu", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\nThe proposed CDS framework seems interesting and it is a principled framework of data clustering. In fact, the maximum margin based clustering methods are implicitly based on such a framework, and it seems nice to explicitly formulate this framework in this paper. This paper also provides strong theoretical results for the generalization error bound of unsupervised similarity-based classifier using Rademacher complexity. As explained in Remark 3.4 and the appendix, the derived generalization bound is a generalized version of the well-established generalization bound for kernel machines, so it has an independent theoretical interest.\n\nThis paper also conducts extensive experimental results with various baselines from the similarity-based clustering and discriminative clustering literature. I particularly appreciate the detailed discussion in Section 5, which places CDSK in a clear position in the literature and explains its significance.\n\nWeakness: \n\nIt could add more value to this paper if the authors provide more examples showing why the derived discriminative similarity is better than conventional similarities, such as the regular kernel similarity and the similarity used in the sparse graph (especially subspace)-based clustering literature. \n", "summary_of_the_paper": "This paper proposes a new discriminative clustering framework by learning an unsupervised classifier from unlabeled data. An unsupervised classifier is learned from every hypothetical data partition, and the optimal data partition is then regarded as the partition corresponding to the minimum generalization error bound of the unsupervised classifier. The authors use a similarity-based classifier as the unsupervised classifier in this framework and derive its generalization error bound as the sum of discriminative similarity between different clusters. The proposed algorithm, CDS via unsupervised kernel classification (CDSK), then minimizes the between-cluster discriminative similarity. Extensive experimental results with the comparison with a broad range of baselines confirm the superior performance of the proposed algorithm.", "summary_of_the_review": "This paper presents a novel and interesting clustering method with theoretical explanations, and the detailed discussion with the similarity-based clustering and discriminative clustering literature is appreciated. I encourage the authors to add more examples showing the comparison between the derived discriminative similarity and conventional similarity used in data clustering.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "mB8_iPxD16_", "reviewer": "Reviewer_TUzr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength: \nThis paper presents a learnable similarity function that adaptively adjusts the weights of the similarity between one sample and the samples of some class. \nThe authors also provide theoretical results to support the propose algorithm and give the strict proofs. \nThe experimental results of the proposed algorithm outperform that of the other comparable clustering algorithms.\n\nWeaknesses:\n1. The expected loss in Eq. (4) seems to be not matched with the corresponding empirical loss. Moreover, the authors should explain how the empirical loss in Eq. (4) can be transformed into Eq. (5). The detailed derivative process should be listed in the appendix. This is important.\n2. It’s not suitable to use boldface to represent a scalar variable. \n3. There are some typos in this paper.\n4. Some variables lack necessary description, e.g., \\mathbb{1}_{y_i \\neq y_j} in Eq. (7).\n", "summary_of_the_paper": "This paper proposes a clustering algorithm by learning from the weighted similarity of each data partition. More precisely, the authors propose an unsupervised framework which aims to minimize an objective of a similarity-based classifier. Then, the upper bound of excess risk of this classifier is provided by Rademacher complexity. They show that the weighted kernel similarity is a special case of the general framework, and they apply it to discriminative clustering by iteratively optimizing the class labels and the weights of similarity. Finally, experiments are conducted to verify the effectiveness of the proposed algorithm.", "summary_of_the_review": "The details of the paper needs further refinement.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R2Q7iNjN7zd", "reviewer": "Reviewer_AedU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper is technically solid and it provides the theoretical analysis of the generalization bound.\n2. The paper proposes a simple yet effective clustering method and provide the hyper-parameter tuning strategy.\n3. The experimental results show the effectiveness of the proposed method.\n\nWeaknesses:\n1. The motivation is unclear for me. What are the benefits of the proposed discriminative similarity clustering method compared with other similarity based clustering methods?\n2. The compared methods in Experiments are not the most recent ones. Among the 10 compared methods, only one was proposed in 2021, and all other methods were proposed before 2015. It would be better to compare with some more recent state-of-the-art clustering methods.\n3. The computational complexity has been already analyzed in Page 6. I do not understand why  Section \"Computational Complexity\" is repeated in Experiments. Maybe the authors want to compare with other methods w.r.t. computational complexity? But I do not find such comparison. It would be better to show the comparison results of the  computational complexity and running time on the used data sets.\n4. The Captions of Table 1 and Table 2 are exactly the same, which need to be corrected. Moreover, in the Caption, it says \"$c$ in the left column is the cluster number\", but I do not find $c$ in Tables 1 and 2.", "summary_of_the_paper": "This paper proposes a discriminative similarity clustering method via unsupervised classification and provides the generalization bound for the similarity classification. The experimental results show the effectiveness of the proposed method.", "summary_of_the_review": "Although there are some concerns, the paper proposes an interesting and effective method and also provides some theoretical analysis.  Therefore I recommend for weak accept.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GH2Ku5SDxwe", "reviewer": "Reviewer_qsFw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Positive:\n(1) Under the framework of CDS, discriminative similarity is induced by the generalization error bound for unsupervised similarity-based classifier. The authors conduct a complete and detailed theoretical analysis, and the results provide theoretical guarantee on the discriminative similarity can be induced from kernel density classification.\n(2) Moreover, based on the CDS model, the authors develop a clustering algorithm termed Clustering by Discriminative Similarity via unsupervised Kernel classification (CDSK). \n(3) CDSK uses a PSD kernel as the similarity function, and outperforms competing clustering algorithms, including nonparametric discriminative similarity based clustering methods and similarity graph based clustering methods, demonstrating the effectiveness of CDSK. \n\nNegative:\n(1)\tClustering performance highly depends on the effective data similarity. One of the main contributions of this paper is to propose a discriminative similarity. As is known to all, there exists a lot of classic similarity learning paradigms, such as metric learning methods and subspace learning methods. What are the main differences between these methods and the proposed method in this paper. I hope that the authors will theoretically or experimentally discuss the specific similarities and differences in a more detail way. Taking LRR as an example, the authors hope to obtain the similarity matrix has a property of low rank. What kind of properties does the discriminative similarity contain in this paper. \n(2)\tThe authors let S^K_ij=2(\\alpha_i+\\alpha_j-\\lambda\\alpha_i\\alpha_j)K(x_i-x_j) be the discriminative similarity between data from different classes. The authors did not clearly explain what the essential definition of this formula is. Could the authors explain the physical meaning of this formula more specifically. I hope the author can give an example to explain how does the similarity with learnable weights reflect discrimination.\n(3)\tThe authors use Gaussian kernel as the predefined kernel, whether different predefined kernel have an impact on the final clustering results.\n(4)\tDoes there exist kernel learning methods based on samples weighting, I believe there may be exist. It is suggested that the authors make a deep analysis on the related work and summarize what are the key differences between these efforts and the proposed method in this paper.\n(5)\tThe authors conduct a complete and detailed theoretical analysis, but the description of the algorithm process is not clear and the optimization process is not detailed enough.\n(6)\tThe experiments are inadequate in this paper, it is hoped that the authors give the parameter analysis and convergence analysis of the algorithm in an experimental way. The authors should compare the efficiency of different algorithms through the running time of different algorithms.\n", "summary_of_the_paper": "This paper proposes a new clustering framework called Clustering by Discriminative Similarity (CDS). CDS learns an unsupervised similarity-based classifier from each data partition, and searches for the optimal partition of the data by minimizing the generalization error of the learnt classifiers associated with the data partitions. In contrasts with kernel similarity with uniform weights, the induced discriminative similarity with learnable weights enhances its capability to represent complex inter-connection between data. Based on CDS, CDSK is proposed as a new clustering method, with its effectiveness demonstrated by experimental results.", "summary_of_the_review": "The paper contributes some new ideas and the motivation of this paper is clear. This paper proposes a new clustering framework termed Clustering by Discriminative Similarity (CDS). Based on this model, the authors develop a CDSK clustering algorithm. The paper is well organized. The authors conduct a complete and detailed theoretical analysis. Experiments on real-world datasets validated the effectiveness of the proposed methods.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide a framework for unsupervised clarification based on minimizing a between-cluster discriminative similarity. It is more flexible than existing methods whose kernel similarity implicitly assumes uniform weights, and the authors connect to ideas such as max-margin and weighted kernel approaches. This yields a clustering algorithm naturally that alternates between updating class labels and similarity weights. Moreover the reviewers (and I) appreciate the analysis of generalization error through Rademacher complexity arguments and detailed author responses. I might add while the paper draws connections to weighted kernel methods and have since added references to sparse subspace clustering etc, there is recent interest in using similar arguments to derive error bounds and uniform concentration results for center-based methods that might be included in the survey of related work, for instance recent work from Swagatam Das and collaborators. The authors have importantly added details on the optimization using SMO, and the revision should include these details in a clear exposition together with the computational complexity discussion mentioned in their response.
Decision: Accept (Poster)