Random Matrix Analysis to Balance between Supervised and Unsupervised Learning under the Low Density Separation Assumption
Authors: Vasilii Feofanov
Malik Tiomoko
Aladin Virmaux
Venue: Submitted to ICLR 2023 (2023)
Keywords: Random Matrix Theory
semi-supervised learning
high dimensional statistics

Abstract: We propose a theoretical framework to analyze semi-supervised classification under the low density separation assumption in a high-dimensional regime. In particular, we introduce QLDS, a linear classification model, where the low density separation assumption is implemented via quadratic margin maximization.
The algorithm has an explicit solution with rich theoretical properties, and we show that particular cases of our algorithm are the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime, and a class of semi-supervised graph-based approaches. As such, QLDS establishes a smooth bridge between these supervised and unsupervised learning methods. Using recent advances in the random matrix theory, we formally derive a theoretical evaluation of the classification error in the asymptotic regime.
As an application, we derive a hyperparameter selection policy that finds the best balance between the supervised and the unsupervised terms of our learning criterion.
Finally, we provide extensive illustrations of our framework, as well as an experimental study on several benchmarks to demonstrate that QLDS, while being computationally more efficient, improves over cross-validation for hyperparameter selection, indicating a high promise of the usage of random matrix theory for semi-supervised model selection.

Under review as a conference paper at ICLR 2023
RANDOM MATRIX ANALYSIS TO BALANCE BETWEEN SUPERVISED AND UNSUPERVISED LEARNING UNDER THE Low DENSITY SEPARATION ASSUMPTION
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a theoretical framework to analyze semi-supervised classification under the low density separation assumption in a high-dimensional regime. In particular, we introduce QLDS, a linear classification model, where the low density separation assumption is implemented via quadratic margin maximization. The algorithm has explicit solution with rich theoretical properties, and we show that particular cases of our algorithm are the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime, and a class of semi-supervised graph-based approaches. As such, QLDS establishes a smooth bridge between these supervised and unsupervised learning methods. Using recent advances in the random matrix theory, we formally derive a theoretical evaluation of the classification error in the asymptotic regime. As an application, we derive hyperparameter selection policy that finds the best balance between the supervised and the unsupervised terms of our learning criterion. Finally, we provide extensive illustrations of our framework, as well as an experimental study on several benchmarks to demonstrate that QLDS, while being computationally more efficient, improves over cross- volsdaaalo for hyperparameter selection, indicating a high promise of the usage of random matrix theory for semi- cmmi-supervised model selection.
INTRODUCTION
Semi-supervised learning (SSL, Chapelle et al., 2010; van Engelen and Hoos, 2019) aims to learn using both labeled and unlabeled data at once. This machine learning approach received a lot of attention over the past decade due to its relevance to many real-world applications, where the annotation of data is costly and performed manually (Imran et al., 2020), while the data acquisition cheap and may result in an abundance of unlabeled data (Fergus et al., 2009). As such, semi- supervised learning could be seen as learning framework that lies in between the supervised and the unsupervised settings, where the former occurs when all the data is labeled, and the latter is restored when only unlabeled data is available. Generally, a semi-supervised algorithm is expected to outperform its supervised counterpart trained only on labeled data by efficiently extracting the information valuable the prediction task from unlabeled examples.
In practice, integration of unlabeled observations to the learning process does not always affect the performance (Singh et al., 2008), since the marginal data distribution p(x) must contain information on the prediction task pyy x). Consequently, most semi-supervised approaches rely on specific assumptions about how p(x) and p(y) x) are linked with each other. It is principally assumed that examples similar to each other tend to share the same class labels (van Engelen and Hoos, 2019), and implementation of this assumption results in different families of semi-supervised learning models. The first approaches aim to capture the intrinsic geometry of the data using graph Laplacian (Chong et al., 2020; Song et al., 2022) and suppose that high-dimensional data points with the same label lie on the same low-dimensional manifold (Belkin and Niyogi, 2004). Another family of semi-supervised algorithms suggests that examples from a dense region belong to the same class. While some methods explicitly look for such regions by relying on a clustering algorithm (Rigollet, 2007; Peikari et al., 2018), another idea is to directly restrict the classification model to have a decision boundary that only passes through low density regions. This latter approach is said to rely on the Low Density

---

Under review as a conference paper at ICLR 2023
Separation (LDS) assumption (Chapelle and Zien, 2005; van Engelen and Hoos, 2019), and it has been widely used in practice in recent decades, combined with the support vector machine (Bennett and Demiriz, 1998; Joachims, 1999), ensemble methods (d' dlAch-BBuu et al., 2001; Feofanov et al., 2019) and deep learning methods (Sajjadi et al., 2016; Berthelot et al., 2019).
Despite its popularity, the study of the low density separation assumption still has many open questions. First, there is a deficiency of works devoted to theoretical analysis of the algorithm's 's performance under this assumption, and most approaches focus on the methodological part (van Engelen and Hoos, 2019). Second, in real applications, it always remains unclear how a semi- supervised algorithm should balance the importance of the labeled and the unlabeled examples in order to not degrade the performance with respect to supervised and unsupervised baselines, This implies in particular that the hyperparameter selection for supervise classífication model crucial, and it is known that using the validaaaloo for model selection may be suboptimal in the semi-supervised case due to the lack of labeled examples (Madani al., 2005).
Motivated by the aforementioned reasons. this paper proposes framework to analyze semi-supervised classification under the low density separation assumption using the power of the random matrix theory (Paul and Aue, 2014; Marchenko and Pastur, 1967). We consider simple yet insightful quadratic margin maximization problem. QLDS, that seeks for an optimal balance between the labeled part represented by the Least Square Support Vector Machine (LS-SVM, Suykens and Vandewalle, 1999) and the unlabeled part represented by the spectral clustering (Ng et al., 2001). In addition, the considered algorithm recovers the graph-based approach proposed by Mai and Couillet (2021) as a particular case.
The main contributions of this paper may be summarized as follows:
We propose a large dimensional analysis of QLDS and derive a theoretical evaluation of the classification error in the asymptotic regime under the data concentration assumption (Louart and Couillet, 2018). The results allow a strong understanding of the interplay between the data statistics and the hyperparameters of the model.
Based on the proposed theoretical result, we propose a hyperparameter selection approach to optimally balance the supervised and unsupervised term of QLDS. We empirically validate this approach on synthetic and real-word world data showing that it outperforms a hyperparameter selection by the cross-vas cross-validation both in terms of performance and running time.
The remainder of the article is structured as follows. In Section 2, we review the related work. Section 3 introduces the semi-supervised framework well the optimization problem of QLDS. Under mild conditions on the data distribution, Section 4 provides the large dimensional analysis of the proposed algorithm along with several insights and discusses its application for hyperparameter selection. Section 5 provides various numerical experiments to corroborate the pertinence of the theoretical analysis and to hyperparameter selection policy. Section 6 concludes the article.
RELATED WORK
LDS in Semi-supervised Learning. Formally introduced by Chapelle and Zien (2005), the LDS assumption imposes the optimal class boundary to lie in a low density region. This assumption is usually implemented by margin maximization, which underlies either explicitly or implicitly many semi-supervised algorithms such as the Transductive SVM (TSVM) (Joachims, 1999; Ding et al., 2017), self-training (Tür et al., 2005; Feofanov et al., 2019) or entropy minimization approaches (Grandvalet and Bengio, 2004; Sajjadi et al., 2016). As the margin's 's signs for unlabeled data are unknown, various unsigned alternatives have been proposed (d' Alché-Bus et al., 2001; Grandvalet and Bengio, 2004), where the classical approach is to consider the margin's 's absolute value (Joachims, 1999; Amini et al., 2008). In practice, the latter is usually replaced by an exponential surrogate function for gradient-based optimization of TSVM (Chapelle and Zien, 2005; Gieseke et al., 201 4).. In this paper, we will consider TSVM with the quadratic margin that is both differentiable and convex, which allows us to perform theoretical analysis and obtain graph-based semi-supervised learning as a particular case. A similar framework of the quadratic margins was considered by Belkin et al. (2006) whose work considered more general case with kemnel-based SVM and the Laplacian matrix integrated to the objective, for which they proved Representer theorem. While our work focuses on explicitly deriving a theoretical expression of the classification error, their paper may complement
2

---

Under review as a conference paper at ICLR 2023
us from the algorithmic point of view showing a direct extension of QLDS to non-linear case. It is important to mention other theoretical studies of approaches based on the low density separation, including upper-bounde of the classification error of TSVM (Derbeko et al., 2004; Wang et al., 2007) and analysis of the self-training algorithm (Feofanov et al., 2021; Zhang et al., 2022).
Graph-based Semi-Supervised Learning. The principle of a graph- based approach is to 1) build a suitable graph with all the labeled and the unlabeled examples as the nodes connected by the weighted edges measuring the pairwise similarities (graph construction step). 2) search for a function / over the graph that is close as possible to the given labels, and that is smooth on the entire constructed graph (label inference step). The graph structure can be naturally used as reflection for the manifold assumption in SSL that suggests that samples located near to each other on a low-dimensional manifold should share similar labels. Among the graph construction methods, the K-nearest neighbor (KNN) graph (Ozaki et al., 2011; Vega-Oliveros et al., 2014) and b-Matching methods (Jebara et al., 2009; Dhillon et al., 2010). along with their extensions, are the most popular ones. Several extensions have considered labeled samples as prior knowledge to refine the generated graph (Rohban and Rabice, 2012; Berton and Lopes, 2014). Depending on the particular choice of loss functions, the label inference methods can be divided in label propagation approaches (Xiaojin and Zoubin, 2002; Zhou et al., 2003), manifold regularization (Belkin et al., 2006; Xu al., 2010), Poisson learning (Calder et al., 2020) and deformed Laplacian regularization (Gong et al., 2015). Recently, Mai and Couillet (2021) proposed a theoretical analysis
unified framework for label inference in graph that encompasses label propagation, manifold, and Laplacian regularization as special cases. In this paper, we recover (Mai and Couillet, 2021) as a special case of QLDS.
Large Dimensional Analysis for Machine Learning, Recently, Random Matrix Theory (RMT) has received particular attention in the machine learning community for studying the asymptotic performance in a regime when the dimension is of the same order of magnitude as the sample size. Recent advances include analysis of the linear discriminant (Niyazi et al., 2021), spectral clustering (Couillet and Benaych-GGerges,, 2016), least square SVM (Liao and Couillet, 2019), wraph-bases semi- cepe-super learning (Mai and Couillet, 2021). In this paper, we show that theoretical findings of the last three aforementioned works are recovered from our theoretical analysis of QLDS provided in Section 4. We derive our theoretical results under the assumption that observations follow a vector- concentration inequality (Louart and Couillet, 2018), which can be particularly interesting for deep learning representations that preserve concentration property (Seddik et al., 2020). It is interesting to mention that number of machine learning algorithms have been theoretically analyzed using methods from theoretical physics, especially glassy physics (Agliari et al., 2020; Carleo et al., 2019; Loureiro al., 2021; Cui et al., 2021; d' Ascoli et al., 2020). To continue with physical statistics-based methods, we highlight the work of Lelarge and Miolane (2019) who derived Asymptotic Bayes risk using information theory and the cavity method (Mézard et al., 1987). Although statistical physics and RMT-based approaches share the same objectives, the techniques used and the interpretations make them two different but complementary methods. To the best of our knowledge, we are not aware of any analysis of the algorithm studied in this paper using statistical physics approach, which we believe is however possible and could be an interesting future work. For completeness, let us also mention the works based on the Convex Gaussian MinMax Theorem (Thrampoulidis et al., 2015; 2016) that allows the analysis of many machine learning algorithms but is mathematically different from the approach used in this paper.
3 FRAMEWORK
Notations Matrices will be represented by bold capital letters (e.g., matrix A). Vectors will be represented in bold minuscule letters (e.g., vector v) and scalars will be represented without bold [n] letters (e.g., variable a). The canonical vector of size n is denoted by em E RR" 1 < m S n. where the i-th element is 1 if i m, and 0 otherwise. The diagonal matrix with diagonal x and 0 elsewhere is denoted by Dx, while A,, denotes the i-th line of the matrix A.
Semi-supervised Setting We consider binary classification problems, where observation x E Rd is described by d features and belongs either to the class C₁ with a label y = -1 or to the class C2 with a label y = +1. We assume that training data consists of ny labeled examples (X,, Ye)
3

---

a Under review as a conference paper at ICLR 2023
(x,, Vo)i=1 E Rdxas {-1,+1) and n, unlabeled examples X. )
Rax given without labels. Following the transductive setting (Vapnik, 1982), we formulate the goal of semi- supervised learning to learn classification model R + (-1, +1} that yields the minimal error on the unlabeled data X,, For convenience, we denote the concatenation of labeled and unlabeled observations by X [X,, X.). For each class Cj. jE (1, we denote the observations from this class as x = [X]
" where X = [ x and 711 + = =yg The same convention used for the unlabeled data X.. By n, m + Ruj we denote the total number of samples in class Cj J E (1,
(1)
QLDS Based on the training set [X,, X.]. we seek for separating hyperplane (linear decision boundary) wt that is solution of the following optimization problem:
te Σ
w arg min
Uk
T
+
w|l
2
n
2
i=1
V=
lahel fidelity
low density separation
regalarization
The first term is the label fidelity term that involves the labeled data only, and it represents the classical beast-square loss used in the LS-SVM. The second term implements the low density separation regularization by maximizing the square of the margin of each unlabeled example, thereby pushing the decision boundary away from the unlabeled points. The third term is the classical Tikhonov regularization although we fix À to the maximum eigenvalue of X see Appendix C.2 and E.6). The first two terms are considered up to a (1/ the notations of the thcoretical derivations of Section
X X.. (for more details,
factor in order to ease
Note that the label fidelity term can be alternatively represented by the hinge loss the log-loss, which slightly alters the overall behavior of the algorithm. Our choice of the least square loss is primarily motivated by the possibility of obtaining more explicit, tractable and insightful results, let alone numerically cheaper implementation. The question of the optimal choice for the loss of the supervised part highly interesting question in the literature. Although it is difficult to formulate strong statement valid for all practical situations, some asymptotic attempts have been made such as (Aubin et al., 2020; Mai and Liao, 2019). More related to our hypothesis, (Mai and Liao, 2019) shows that for isotropic Gaussian mixture models in the high dimensional regime, quadratic cost functions are optimal and outperform alternatives costs such as SVM or logistic approaches. Table 4 in Appendix summarizes the classification eтror by using three losses for labelled parts (hinge, logistic, and quadratic) and two losses for unlabelled parts (quadratic and absolute value). This table shows that the selection of losses presented in the article has competitive performance.
The optimization problem in Equation (1) convex (as soon as Amaz where Amar is the
maximum eigenvalue of (o., X. ar X,X] and admits unique solution (all details are given
in the supplementary material, Section A) given by
1 Vn
X T
-1 X,X. n
ALa
+ ag
X,yr.
It worth remarking that for the fully-supervised case (az, a.) (1, (1, we recover the Least Square SVM (Suykens and Vandewalle, 1999). Another extreme case is to take (ay, a.,) = (0, 1) that leads to the optimal decision boundary of the graph-based approach proposed by Mai and Couillet (2021) (further denoted by GB-SSI.). Moreover, if additionally to (ae, a.,) (0, 1) take À as the maximum cigenvalue of the unlabeled data (1/n) X, we recover spectral clustering (See Section B of the supplementary material for complete derivation).
Given the optimal decision boundary as per Equation (2), the decision score function for any example Rd is given
f(x) = w
-yTx
1 - 0.
x
(Ar
X,
T + or
X.X] n
-1
x.
(3)
Vn
n
4

---

Under review as a conference paper at ICLR 2023
4 THEORETICAL ANALYSIS AND ITS APPLICATION
In this section, we theoretically analyze the statistical behavior of QLDS and its decision function fxx). First, we state the assumptions used for theoretical analysis. Then, we present the main results and describe an application for hyperparameter selection.
4.1 ASSUMPTIONS
In the following, we assume the following classical concentration property.
Assumption (Concentration of D(X)) For two classes Cj. j (1,2, we assume that all vectors x
Xay E Cj are i.i.d. and in particular Cov(x! (2) Id. Moreover we assume that there exist two constants C, > 0 (independent of n, d) such that, for any fiiisschittfuncciii f IRá - R,
Vt 0, 0,
IP xx)D)( (lf(x) - m)(0) 2 2) S Ce-(t/e)
where mg is median of the random variable Z.
Assumption notably encompasses the following scenarios: the columns of X are (a) indepen- dent Gaussian random vectors with identity covariance, (b) independent random vectors uniformly distributed on the IR sphere of radius vd, and, most importantly, (c) any Lipschitz continuous transformation thereof, such as GAN as it has been recently theoretically shown in (Seddik et al., 2020). In the appendix (Section D), have further explained the concentrated vector assumption and complemented its relevance and generality for the study of machine learning algorithms. In Assumption
only consider identity covariance matrix keep this presentation simple. The more general case of arbitrary covariance matrix Σ, is fully derived in the supplementary material, Section C. We should mention that it is convenient to "center" the data X for the sake of simplicity. This centering operation is performed on the whole data set X by substracting the global mean from the training points i.e., X + X E[X]. Furthermore, we place ourselves into the following large dimensional regime:
Assumption (Hiigh-dimensional asymptotics)) As - oc, we consider the regime where d = (n) and assume d/n Co > Furthermore, for j 1,2, ney /n - Cej and Rwss - Cuj- We denote by C = [Ce1. cr2] and C. = [Cu1, Cu2).
This assumption of the commensurable relationship between the number of samples and their dimension corresponds to realistic regime and differs from classical asymptotic where the number of samples often assumed to be exponentially larger than the feature size. Note that this chosen asymptotic regime classical in Random Matrix Theory fits most real-life applications and has been successfully applied in telccommunications (Couillet and Debbah, 2011), finance (Potters et al., 2005) and more recently in machine learning (Liao, 2019; Mai and Couillet, 2021; Tiomoko et al., 2020).
4.2 MAIN RESULTS
We introduce the mean matrix M [u [2]] Rdx2, where μ.j Exec, [x] E IRd is the theoretical mean of the class Cj.j E 2]. Further, we define matrices M and G that will play an important role the core formulation of the statistics of f(x).
Definition (Data statistics matrices M and 9) We define data matrices M and G
M = (D= 1 6MMM) G G- ---(11-" The (1,1- a.,)
+a 8M M,
6--(m(1-an,)
where the vectors a, d and k. are the unique positive solution of the following fixed point equations
82
Co
d, == (1- 52 n(1 )
(1 +1+ +25)2
(1- al-a)
Ctj(t
Cujau
8 + 14 R2
Ki + aạd
a
5

---

Under review as a conference paper at ICLR 2023
The existence of a, d, K. 6 are direct application of (Louart and Couillet, 2018, Proposition 3.8)). These quantities are common in Random Matrix Theory in order to correct large biases in high dimensions (for more details, we refer to the supplementary material, Section D). We are now in position to introduce the asymptotic theoretical analysis of the score f(x) of any unlabeled sample x.
Theorem Let X E Rdxxn be data set that follows Assumptions I and 2. For any Xu, with Cj and f(x) tn w defined by Equation (3), have almost surely for both classes
f(xix - i
where fy ~ N (mz.
The mean my and the variance o² are defined as
(-1)) (os (ef - ) Me
Ny(1 and)(1 az0d
o²= (e -e (DAMGMD, + DaDee) ee
with s (/1 (1 + azd)), (12/(1221 + azz)).
Finally, the theoretical classification error is asymptotically given by
Ex (1 - erf
mi1 ( 2v/20
m2
where erf(2) = S/ e dt the Gauss error function.
A fundamental aspect of Theorem 1 is that the performance of the large dimensional (large n, large d) classification problem under consideration merely concentrates into wwo-dimessional sufficient statistics, all objects defined in the theorem are most of size 2. All quantities defined in Theorem are a priori known, apart from the proportion of classes in X,, and the matrix M MM M E R2x2, whose (i,j)-entries are the inner products μ μy that have to be estimated from data. From practical perspective, these inner products are easily amenable to fast and efficient estimation as per Proposition 2, requiring few training data samples.
Proposition 2 (On the estimation of my and σ) The following estimates holds:
M NTTM,,, -{ (4/mg) IT
(()
X (8)
+ (1/V
ifi=
E11
(1/ (ne ne;)) IT
Ing + O (emin otherwise.
with x = = x() an even-sized division of x()) E.1
Note that a single sample (two when i =) per class is sufficient to obtain consistent estimate for all quantities as long as d is large. In the semi-supervised setting, when only few labeled examples available, it thus still possible to estimate M M. is important to remark that the convergence rate of the estimation is a quadratic improvement over the convergence rate of the usual central-limit theorem. Finally, to estimate the proportion of classes in the unlabeled set, known a priori, we assume that the distribution of classes to be the same for the labeled and unlabeled data, so that nc. for j E 2). We show the supplementary material (Section E) that this
we have Cuj Ct Ru assumption has little impact on the theoretical insights as well as in the experiments.
As an application of Theorem 1, we provide in Figure 5 of the Appendix "phase diagram" (relative gain with respect to supervised learning as a function of the labeled sample size and the task difficulty) which shows that a non-trivial gain with respect to fully supervised case is obtained when few labeled samples are available and when the task difficult. This conclusion similar to existing conclusion from (Mai and Couillet, 2021; Lelarge and Miolane, 2019).
4.3 APPLICATION TO HYPERPARAMETE SELECTION
Following the discussion in Section 3, we obtain that the theorem allows us to recover the asymptotic performance of the spectral clustering, the graph-based approach GB-SSL of Mai and Couillet (2021)

---

Under review as a conference paper at ICLR 2023
Table 1: Running time comparison between theory- hyperparameter hyyrrataasccyyeerrrrnnteeee selector and cross-valldation based with 10 folds, with Rey = Raj d for j E (1.
dimension
5
8
16
32
64
128
256
512
1024
2048
QLDS (th)
.01 s s32s
.01 s
.01
.01 s
.017
.02 s
.04 s
.17 s
.95 s
8.58 $
QLDS (cv)
s38
s43
.64
1.02
2.71 s
14
95 s
587
4970 s
and the LS-SVM (Suykens and Vandewalle, 1999). This generality of the theorem represents an important asset in the unification of some SSL learning schemes. In particular, the theoretical error can be regarded as a function of ag and au. below we propose to use Equation (4) as a criterion to automatically select Oug and a, through the grid search over different values. This leads to Algorithm 1. Note that the classification error is invariant to a scaling of (see Equation (3)). Thus, we fix the value of À in experiments to be Amax with Amax the maximum eigenvalue of X [X X.): and optimize only and Qu. The fixed value corresponds to the one also proposed in (Mai and Couillet, 2021). We give more details about this choice for À and its numerical stability in Appendix C.2.
Our proposition to select and On by the theorem is motivated by several practical reasons. Firstly, the importance of labeled and unlabeled examples varies, making the graph-based based learning more effective in some cases, and the LS-SVM more effective in the others. By properly choosing and On one can find the best balance between the GB-SSL and LS-SVM. Secondly, the classical approach of selecting hyperparameters by cross-val voss-validation suffers from high computational time and prone to bias the semi-supervised setting due the scarcity of the labeled set (Madani al., 2005).
Algorithm 1 QLDS algorithm with optimal selection of ag and Cu
Input: labeled data X; and unlabeled data X,
grid of hyperparameter values {(a 0a (4)
)
Preprocessing: center data X < X E[X]. where X= [X, Output: estimated label ý E 11, for each unlabeled example x X
estimate inner product M M using Proposition 2 choose as the maximum eigenvalue of X
for / = 1,..., grid-search steps do
take (t) and o'
estimate classification error ( by Theorem with a2 a and oz 02 end for
(1)
select a and a; by finding t that yields minimal classification error (t)
compute the decision score f(x) using Equation (3) with an a and az = o²
-1 if fxx) <
return label ý = 1
otherwise
Complexity analysis. Algorithm 1 or QLDS (th) may be sequentially described as in 1) training of QLDS, estimation M M. selection ag and au over the grid. As QLDS has an explicit solution, its complexity is equivalent to the computation of the decision scores f(x) which requires solving a system of linear equations, yielding complexity O(n²). The computation of M M of complexity O(dn + d) (estimation + product). Hyperparameter selection consists of iterating T times the error estimation from Theorem and its complexity is OTT). Finally, the global complexity of QLDS (th) is (n²)) in the regime of Assumption 2.
is important to mention that an alternative way to optimize as and au is cross-validation (OLDS (ev), which requires optimizing QLDS for each candidate (ağ, for K folds, leading to complexity OTK'n²). This indicates a clear advantage of using Theorem in terms time complexity as highlighted in Table 1.
7

---

Under review as a conference paper at ICLR 2023
5 EXPERIMENTAL RESULTS
In this section, we illustrate the robustness of the different algorithms and the optimization of the hyperparameters ag and au proposed in the previous section. More specifically, Section 5.1 confirms empirically the robustness the concentrated random vector assumption on real data by comparing the empirical distribution of the decision
with the theoretical prediction of Theorem 1. Section 5.2 analyzes the performance of QLDS when increasing the number of labeled examples, and Section 5.3 benchmark with several baselines for wide range of real data sets. We perform comparison between the following methods:
QLDS (0, 1) with 0t 0, Ox which stands for the graph-based approach proposed in (Mai and Couillet, 2021);
QLDS (1, 0) with a₂ = 1, d = 0 which stands for LS-SVM;
Self-training with the Least-Square SVM as the base classifier, where the confidence threshold is optimized as proposed by Feofanov al. (2019) denoted ST (LS-SVM);
QLDS (cv) with model selection of ag and Oa by the 10-fold cross-validation;
QLDS (th) with model selection of ag and a performed theoretically using Theorem 1;
QLDS (or) Oracle measure the efficiency of the proposed algorithm: QLDS, where model selection of ag and 0a, is performed on the ground truth (as if the labels for the unlabeled examples would be known). It represents the croo-claasifiiation lower-bound for the previous approaches.
Through the experimental part, will use several data sets described follows (see more details in Section E of the supplementary material);
Synthetic: Gaussian mixture model with ( ~ (Htj, La) with μn -2
Amazon Review data set (McAuley et al., 2015: He and McAuley, 2016) from tex- tual user reviews, positive negative, on books (books), DVDs (dvd), electronics (electroni es), and kitchen (kitchen) items respectively. The data encoded as d 400-dimensional tf-idf feature vectors of bag-of-words unigrams and bigrams;
Adult data set (Kohavi et al., 1996) which consists in predicting whether income exceeds 50 000 per year based census data;
Mushrooms data set from UCI Machine Learning repository (Dua and Graff, 2017) which classifies between poisonous and edible mushrooms based on their physical characteristies;
Splice ice data set from UCI Machine Learning repository (Dua and Graff, 2017) which aims to recognize two types of splice junctions DNA sequences.
5.1 ROBUSTNESS OF THEORETICAL ANALYSIS REAL DATA
This section illustrates the close fit of the theoretical performance (i.e., Theorem 1) on the synthetic and two real-life data sets. To do so, we compare the empirical decision function represented by the histograms on Figure versus the Gaussian statisties m, and o² from Theorem 1.
5.2 ANALYSIS OF SAMPLE SIZE
Figure 2 represents the classification error as function the number of labeled examples. The picture shows that the theoretical model selection outperforms the cross-validation scheme and close to the oracle selection (which uses the ground truth labels). general, we observe that OLDS (th) is very stable in comparison with the cross cros-validattio selector QLDS (cv).
5.3 COMPARATIVE PERFORMANCE ON SEVERAL DATA SETS
This section compares through Table the performance obtained by fixing the number of labeled and unlabeled data several data sets to analyze the performance of the hyperparameter selection and also to validate the theoretical intuitions formulated in this article.
The experimental results show that
8

---

Under review as a conference paper at ICLR 2023
Syithatic
<: (Th)
Ch 61
(Th)
G111
40
(Emp))
Dng
Dng!
Drel
Errpl
Donaty
30
(Emp)
Derilry
20
10
0.04
0.04
-313
-6.5
600
015
6.30
-2.6 -004 -5.2 882
function 670
Decsion gtx)
Decamot fandionnnnnnn
Figure 1: Empirical versus theoretical density of decision score f(x) for (Left) Synthetic data set with d 100, figı = Ty2 = 100, 1h111 = Th22 = 000 (Center) Review-kitchen classification
d = 400, 1411 72g2 100 (Right) Review-books classification d = 400, 7441 n42 100. For both review data sets, the empirical histogram is computed using 400 unlabeled samples.
kitchen
dvd
electronics
0.375
0.300
0:26
0.325
0.275
0.24
0.300
0.250
0.22
0.250
0.200
0.225
2024 32
54
70
92
118154200
2024
54
70 118154 200
20244
54 70 118154200 200
Number labeled examples,
Number labeled examples,
Number labeled examples,
OLDS/O.1)
STILS SVMI
QLDS (cv)
QLDS (8h)
OLDS (or)
Figure 2: Classification error depending on the number of labeled examples different data sets. Positive vs. negative review for different products (Lefft) kitchen (Center) dvd and (Right) electronics with Ru1
n222 200, d = 400.
Table The classification error of different methods under consideration on the real benehmark data sets. indicates statistically significantly worse performance than the best result (shown in bold), according to the Mann- Wain-Whitney test (p < 0.01) (Mann and Whitney, 1947).
Baselines
Model Selection
Orucle
Data set
OLDS (1,0) (LS-SVM)
QLDS (0, (GB-SSL)
OLDS (1
(LS-SVM)
(cv)
QLDS (th)
QLOS (or)
books
37.47 + 2.25
26.47 + 0.72
49.13 + 0.65
35.83* + 2.48
27.91
+ 3.32
26.03
0.79
25.7 + 0.93
dud
38.33* + 1.72
29.12 + 1.35
49.251 + 0.68
36,46
+ 1.94
29.53
+ 3.48
28.53
1,33
26.94
+ 1.47
electronics
34.15' + 3.25
19.4
0.29
48.67'
+ 1.05
31.69
+ 3,56
20.1
1.03
19.41
+ 0.46
19.11
+ 0.58
kitchen
32,391 +: 3.02
19,31
0.16
49.07!
+ 0.64
29.62
+ 3.03
19.98
+ 2.28
19.11
+ 0.32
18.67 + 0.43
splice
39.81 2.93
35.48
+ 0.86
44,36'
2.3
39,36*
3.12
37.02
3.04
35,35
1.26
33.63
1.75
adult
33.35 +: 0.68
36.28
+ 0.06
32.55
+ 1.47
35.45+
0.75
32.25 + 1.92
32.88
2,46
31.9
+ 1.74
mushrooms
6.55+ + 2.07
11,33
+ 0.04
33.94
+ 10.67
6.62
2.39
2.57 + 1.86
8.49
+ 3.63
1.75 + 1.31
QLDS benefits from both labelled and unlabelled data and significantly outperforms LS SVM and GB-SSL on datasets 5 and 2 respectively.
Fine tunning of a and a, provides better results than setting them to the default values.
Hyperparameter selection using Theorem outperforms at the same time being more robust according to the error's standard deviation.
comparable to cross-validation,
There still room for improvement when we compare QLDS (or) with QLDS (th).
6 CONCLUDING REMARKS
In this paper, we proposed a theoretical analysis of a simple yet powerful linear semi-supervised classifier that relies on the low density separation assumption. Moreover, approach builds bridge

---

Under review as a conference paper at ICLR 2023
between several existing approaches such the least square support vector machine, the spectral clustering. and graph-based -umissupereiee learning. The key approach to our analysis was to use modern large dimensional statistics to quantify the classification error through the data statistics of the decision function. Based on this result, we proposed a hyperparameter selection criterion that demonstrated promising experimental results compared to the time-consuming coss-validation. The proposed theoretical study opens broad perspectives for analysis of the LDS assumption in more challenging settings such as the multi-class classification, the non-linear case, fully unsupervised domain adaptation.
REFERENCES
Agliari, E.,, Barra, A., Sollich, P., and Zdeborova, L. (2020). Machine learning and statistical physics: theory, inspiration, application. Journal of Physics A: Special, (2020).
Amini, M., Laviolette, F., and Usunier, N. (2008). A transductive bound for the voted classifier with an application to semi-supervised learning. In Advances in Neural Information Processing Systems, pages 65-72.
Aubin. B., Krzakala, F., Lu, Y., and Zdeborová, L. (2020). Generalization error in sigh-dimensional perceptrons: Approaching bayes error with convex optimization. Advances in Neural Information Processing Systems, 13:12199-15 11111919922211
Belkin, M. and Niyogi, P. (2004). Semi-supervised learning on riemannian manifolds. Machine Learning, 56(1-3) (111-3):209-221 239.
Belkin, M., Niyogi, P., and Sindhwani, V. (2006). Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. Journal of machine learning research, 7(11).
Bennett, K. and Demiriz, A. (1998). Semi-supervised support vector machines. Advances in Neural Information processing systems, 11.
Berthelot, D., Carlini, N., Goodfellow, I., Papernot, N., Oliver, A., and Raffel, C. A. (2019). Mixmatch: A holistic approach to semi-supervised learning. Advances in Neural Information Processing Systems, 32.
Berton, L. and Lopes, A. D. (2014). Graph construction based on labeled instances for semi- supervised learning. In 2014 22nd International Conference on Pattern Recognition, pages 2477-2482. IEEE.
Calder, J., Cook, B., Thorpe, M., and Slepcev, (2020). Poisson learning: Graph based semi- supervised learning at very low label rates. In International Conference on Machine Learning. pages 1306-1316. PMLR.
Carleo, G., Cirac, I., Cranmer, K., Daudet, L.,, Schuld, M., Tishby, N., Vogt-Maranto, L., and 7deborová, I.. (2019). Machine learning and the physical sciences. Rev. Mod. Phys., 91:045002.
Chapelle, O., Schölkopf, B., and Zien, A. (2010). Semi-Supervised Learning. The MIT Press, 1st edition.
Chapelle, O. and Zien, A. (2005). Semi-supervised classification by low density separation. In International workshop on artificial intelligence and statistics, pages 57-64. PMLR.
Chong, Y., Ding, Y., Yan, Q. and Pan, S. (2020). Graph-based semi-supervised learning: A review. Neurocomputing. 408:216-230.
Couillet, R. and Benaych-Georges, F. (2016). Kernel spectral clustering of large dimensional data. Electronic Journal of Statistics, 10(1):193-1454.
Couillet, R. and Debbah, M. (2011). Random matrix methods for wireless communications. Cam- bridge University Press, New York, NY, USA, first edition.
Cui, H., Loureiro, B., Krzakala, F., and Zdeborová, L. (2021). Generalization error rates in kernel regression: The crossover from the noiseless to noisy regime. Advances in Neural Information Processing Systems, 34:10131-10143.
10

---

Under review as a conference paper at ICLR 2023
d' d'Alché-Buc Buch F., Grandvalet, Y., and Ambroise, C. (2001). Semi-supervised marginboost. Advances in Neural Information Processing Systems, 14:553-560.
Derbeko, P., El-ianiv, R., and Meir, R. (2004). Explicit learning curves for transduction and application to clustering and compression algorithms. Journal of Artificial Intelligence Research, 22:117-142.
Dhillon, S., Talukdar, P., and Crammer, (2010). Learning better data representation using inference- metric learning. In Proceedings of the acl 2010 conference short papers, pages 377-381.
Ding, S., Zhu, Z., and Zhang, X. (2017). An overview on semi-supervised support vector machine. Neural Computing and Applications. 28(5):969-977
Dua, D. and Graff, C. (2017). UCI machine learning repository.
d' Ascoli, S., Refinetti, M., Biroli, G., and Krzakala, F. (2020). Double trouble in double descent: Bias and variance (s) in the lazy regime. In International Conference on Machine Learning, pages PMLR.
Feofanov, V., Devijver, E., and Amini, M.-R. (2019). Transductive bounds for the multi-class majority vote classifier. Proceedings of the AAAI Conference on Artificial Intelligence, (3(00)::56663377
Feofanov, V., Devijver, E., and Amini, M.-R. (2021). Multi-class probabilistic bounds for self-learning. arXiv preprint arXiv:2109.14:01
Fergus, R., Weiss, Y., and Torralba, A. (2009). Semi-supervised learning in gigantic image collections. Advances in neural information processing systems, 22.
Fleury, B., Guédon, O., and Paouris, G. (2007). A stability result for mean width of Ip-centroid bodies. Advances in Mathematics, 214(2):6658877.
Gieseke, F. Airola, A., Pahikkala, T., and Kramer, O. (2014). Fast and simple gradient-based based optimization for semi-supervised support vector machines. Neurocomputing. 123:23-32.
Gong, C., Liu, T.. Tao, D., Fu, K., Tu, E., and Yang, J. (2015). Deformed graph laplacian for semisupervised learning. IEEE transactions on neural networks and learning systems, 26(10):2261- 2274.
Grandvalet, Y. and Bengio, Y. (2004). Semi-supervised learning by entropy minimization. Advances in Neural Information Processing System, 17.
He, R. and McAuley, J. (2016). Ups and downs: Modeling the visual evolution of fashion trends with one-class collaborative filtering. In Proceedings of the 25th International Conference on World Wide Web, WWW '1, page 507-517, Republic and Canton of Geneva, CHE. International World Wide Web Conferences Steering Committee.
Imran, A.-A.-Z.. Huang, C., Tang, H., Fan, W., Xiao, Y., Hao, D., Qian, Z., and Terzopoulos. D. (2020). Partly supervised multi-task learning. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 769-774.
Jebara, T., Wang, J., and Chang, S.-F. (2009). Graph construction and b-matching for semi-supervised learning. In Proceedings of the 26th annual international conference machine learning, pages 441-448.
Joachims, T. (1999). Transductive inference for text classification using support vector machines. In Proceedings of the Sixteenth International Conference on Machine Learning, ICMI. '99, pages 209, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
Kingma, D. P. and Ba, J. (2015). Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015.
Klartag, B. (2007). A central limit theorem for convex Inventiones mathematicae, 168(1):91-13))

---

Under review as a conference paper at ICLR 2023
Kohavi, R. al. (1996). Scaling up the accuracy of naive-bayes classifiers: A decision-tree hybrid. In Kdd, volume 96, pages 202-207.
Lelarge, M. and Miolane, L. (2019). Asymptotic bayes risk for gaussian mixture in semi-supervised setting. In 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pages 639-643. IEEE.
Liao, Z. (2019). A random matrix framework for large dimensional machine learning and neural networks. PhD thesis, Université Paris-Saclay
Liao, Z. and Couillet, R. (2019). A large dimensional analysis of least squares support vector machines. IEEE Transactions on Signal Processing, 67(4):1065-1074
Louart, C. and Couillet, R. (2018). Concentration of measure and large random matrices with an application to sample covariance matrices. arXiv preprint 1805.0880009299
Loureiro, B., Gerbelot, C.,, Cui, H., Goldt, S., Krzakala, F., Mezard, M., and Zdeborová, L. (2021), Learning curves of generic features maps for realistic datasets with a teacher-student model. Advances in Neural Information Processing Systems, 34:18137-18151.
Madani, O., Pennock, M., and Flake, G. W. (2005). Co-validation: Using model disagreement on unlabeled data to validate classification algorithms. In Advances in neural information processing systems, pages 873-880.
Mai, X. and Couillet, R. (2018). random matrix analysis and improvement of semi-supervised learning for large dimensional data. The Journal of Machine Learning Research, 19(1):304--110.
Mai, X. and Couillet, R. (2021). Consistent semi-supervised graph regularization for high dimensional data. J. Mach. Learn. Res., 22:94:1-92: 1-94:48.
Mai, X. and Liao, Z. (2019). High dimensional classification via regularized and unregularized empirical risk minimization: Precise error and optimal loss. arXiv preprint arXiv: 13742.
Mann, H. B. and Whitney, D. R. (1947). On test of whether one of two random variables is stochastically larger than the other. The Annals of Mathematical Statistics, 18(1)500-60.
Marchenko, V. A. and Pastur, L. A. (1967). Distribution of eigenvalues for some sets of random matrices. Matematicheski Shornik, 114(4):007-536
McAuley, J., Targett, C., Shi, Q., and den Hengel, A. (2015). Image-based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '15, page 43-52, New York, NY, USA. Association for Computing Machinery.
Mézard, M., Parisi, G., and Virasoro, M. A. (1987). Spin glass theory and beyond: An Introduction to the Replica Method and Its Applications, volume 9. World Scientific Publishing Company.
Ng, A., Jordan, M., and Weiss, Y. (2001). On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14.
Niyazi, I. B., Kammoun, A., Dahrouj, H., Alouini, M.-S., and Al-Naffouri, T. (2021). Weight vector tuning and asymptotic analysis of binary linear classifiers. arXiv preprint arXiv:21 10.00567.
Ozaki, K., Shimbo, M., Komachi, M., and Matsumoto, Y. (2011). Using the mutual k-nearest neighbor graphs for semi-supervised classification on natural language data. In Proceedings of the fifteenth conference on computational natural language learning, pages 154-162.
Paul, D. and Aue, A. (2014), Random matrix theory in statistics: A review. Journal of Statistical Planning and Inference, 150:1-29.
Peikari, M., Salama, S., Nofech-Mozes, S., and Martel, A. L. (2018). A tluster-then-labll semi- supervised learning approach for pathology image classification. Scientific reports, 8(1):1-13.
Potters, M., Bouchaud, J.-P., and Laloux, L. (2005). Financial applications of random matrix theory: Old laces and new pieces. Acta Physica Polonica B, 3769):2767.
12

---

Under review as a conference paper at ICLR 2023
Rigollet, P. (2007). Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(7).
Rohban, M. H. and Rabiee, H. R. (2012). Supervised neighborhood graph construction for semi- supervised classification. Pattern Recognition, 15(4):1363-1372.
Sajjadi, M., Javanmardi, M., and Tasdizen, T. (2016). Mutual exclusivity loss for semi-supervised deep learning. In 2016 IEEE International Conference on Image Processing (ICIP), pages 1908- 1912. IEEE
Seddik, M. E. A., Louart, C., Couillet, R., and Tamaazousti, M. (2021). The unexpected deterministic and universal behavior of large softmax classifiers. In International Conference on Artificial Intelligence and Statistics, pages 1045-1053. PMLR.
Seddik, M. A., Louart, C., Tamaazousti, M., and Couillet, (2020). Random matrix theory proves that deep learning representations of gan-data behave as gaussian mixtures. In International Conference on Machine Learning, pages 8573-8582. PMLR.
Singh, A., Nowak, R., and Zhu, J. (2008). Unlabeled data: Now it helps, now it doesn't. Advances in neural information processing systems, 21.
Song, Z., Yang, X., Xu, Z.,, and King, I. (2022). Graph-based supervise learning: A compre- hensive review. IEEE transactions on neural networks and learning systems, PP.
Suykens, J. A. and Vandewalle, J. (1999). Least squares support vector machine classifiers. Neural processing letters, 93)):933-300.
Thrampoulidis, C.,, Abbasi, E., and Hassibi, B. (2016). Precise high-dimensional error analysis of regularized m-estimators. In 2015 53rd Anmual Allerton Conference on Communication, Control, and Computing (Allerton), pages 410-417. IEEE.
Thrampoulidis, C., Oymak, S., and Hassibi, B. (2015). Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory, pages 1683-1709, PMLR.
Tiomoko, M., Ali, H. T., and Couillet, R. (2020). Deciphering and optimizing multi-task learning: random matrix approach. International Conference on Learning Representations.
Tür, G., Hakkani-Tühr D. Z., and Schapire, R. E. (2005). Combining active and semi-supervised learning for spoken language understanding. Speech Communication, 45:171-186.
van Engelen, J. E. and Hoos, H. H. (2019). A survey on semi-supervised learning. Machine Learning, 109:373-440.
Vapnik, V. (1982). Estimation of Dependences Based Empirical Data: Springer Series in Statistics (Springer Series Statistics). Springer- Verlag New York, Inc., Secaucus, NJ, USA.
Vega-Oliveros, D. A., Berton, L.., Eherle, A. M., de Andrade Lopes, A., and Zhao, L.. (2014). Regular graph construction for semi-supervised learning. In Journal of physics: Conference series, volume 490. IOP Publishing.
Wang, J., Shen, X., and Pan, W. (2007). On transductive support vector machines. Contemporary Mathematics, 443:7-20. Xiaojin. Z. and Zoubin, G. (2002), Learning from labeled and unlabeled data with label propagation. Tech. Rep., Technical Report CMU-CALD-022-07,, Carnegie Mellon University.
Xu, Z., King, I., Lyu, M. R.-T., and Jin, R. (2010). Discriminative semi- semi-supervised feature selection via manifold regularization. IEEE Transactions on Neural networks, 2137):1033-1047.
Zhang, S., Wang, M., Liu, S., Chen, P.-Y,, and Xiong, J. (2022). How does unlabeled data im- mie-hidee-llayr thcoretical analysis. arXiv preprint
prove generalization in self-training? arXiv:2201.08514.
Zhang, Т. and Oles, F. J. (2001). Text categorization based on regularized linear classification methods. Information retrieval, 4(1):5-31.
Zhou, D.,. Bousquet, O., Lal, T., Weston, J., and Schölkopf, B. (2003). Learning with local and global consistency. Advances in neural information processing systems, 16.
13

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
B SOLUTION OF QLDS
We recall the optimization problem of QLDS without bias
w = arg min ((w),
(5)
w
where
((w) 2
+
07
X
w)
auu
X
(6)
2
2
i=
The loss L(w) can be rewritten in more convenient and compact matrix formulation
((w) X w
at
lIv
X
w
aa w
X
w
2
2
Vn
Taking the derivative the loss function [(w) with respect to w leads to
al(w) = Aw - at
Xx Vn
X
X
Ye
w
au
a
w
dw
vn
X
X,X,,
X
PIK + at
au
The optimal value of w (up to a scaling of ai)) is found by setting the gradient to zero
X
X
X
- AAaa
Ye-
The decision function for the unlabeled data x., is given as
X
fu w
(8)
Vn
X
X
X,
ALa +
au
(9)
n
We would like to mention importantly that the hessian of the loss reads as
VL(w) (AIl: + ag
X,X,
X
Ouu
n1
(-av X,X + au x,
Note that V((w) > 0 if and only if > Amarx the maximum eigenvalue of the matrix M. Therefore the loss function is convex as soon À >
where (m) denotes
n
Amaz (-ar X. + 0.a X.
C LINK TO RELATED WORK
C.I LINK CRAPH-BASHE SEMI- SUPERVISED LEARNING
Given generally few labeled examples and comparatively many unlabeled ones, the idea of graph- based SSL to construct a connected graph that propagates effective labeled information to the unlabeled data. More specifically, the data are represented by a finite weighted graph G = (N, E, W) consisting of a of nodes N based on the data samples X [X,, X.), set of edges & and its associated weight matrix W [war in fi,'=1 where measures the similarity between data points x; and X,y
Way = h (f(xixx))
for some non decreasing non negative function so that similar data vectors x, X² are connected with large weight. Graph-based learning algorithms estimate the label of each node based
14

---

Under review as a conference paper at ICLR 2023
smoothness assumption the graph. Specifically, the algorithm estimates class attachment "score" fi for each node by solving the optimization problem:
min
Whr (f: fv)
(10)
s.t. f. - y: V Sisni
(11)
Here, the term Way (fi fe) imposes label consistency of nearby samples (smoothness condition on the labels of the graph). The optimization problem in Equation (10) the classical Laplacian regularization algorithm studied in depth in (Mai and Couillet, 2018). There, the authors showed the fundamental importance to "center" the weight matrix W. This centering approach corrects an important bias in the regularized Laplacian which completely annihilates the use of unlabeled data in a large dimensional setting. A significant performance increase was reported, both in theory and in practice in (Mai and Couillet, 2021) when this basic, yet counter-intuitive, correction is accounted for. More specifically the centering is performed as follows
W
with P (I, 1,1,)) the centering projector.
However, the optimization problem described in (10) now becomes non convex since the entries of the weight matrix W may take negative values (this must actually be the case as the mean value of the entries of W is zero). To deal with this problem, Mai and Couillet (2021) proposes to constrain the norm of the unlabeled data score vector f, (that is, the score vector restricted to unlabeled data) by appending regularization term az| e||f,, |l to the previous minimization problem. This leads, under a more convenient matrix formulation, to min E.ERna
ax|f, [|2 - f Wf
s.f. f = yt-
(12)
This problem is now convex for all a W wull where Wan is the restriction of the matrix W to the unlabeled data.
The optimization problem is a quadratic optimization problem with linear equality constraints, and f. be obtained explicitly and its solutions are best described under the matrix formulation (using linear kernel, i.e., h(x)= = x):
X,,
f.
y, x,
PI
X.
(13)
The graph-based SSL solution given in Equation (13) is partieular case of QLDS solution given in Equation (9) with at = 1 and ag O.
C.2 LINK TO SPECTRAL CLUSTERING AND CHOICE OF À
Spectral clustering particular case of (13) when À is the maximum eigenvalue of X
Indeed, using the eigenvalue decomposition 1 XT = UAUT Σ Nu Equation (13) can
be rewritten
PL - 1 x
f,
y[x
X.
n
1
nuu x A; X
When À + Amaz max A and denoting by Unaz the eigenvector corresponding the largest eigenvalue Amaz, we obtain,
f, y.X, Umax U X Amax
X...
which unfolds projecting' the unlabeled data X. into the largest eigenvector of X come sponding to the spectral clustering algorithm with linear kernel.
uu scaling y: X. User which does not impact the classification error
15

---

Under review as a conference paper at ICLR 2023
The parameter À In order for QLDS to specialize to spectral clustering in the unlabelled regime, we fix the parameter = Amax to be the maximum eigenvalue of X IXtXxal For numerical reasons, in all the experiments have been tried out, we do not find substantial improvements at considering as an hyper-parameter and therefore fix it.
use À (1 =) with 1003 Although many choices of
D THEORETICAL ANALYSIS OF QLDS
We recall the solution of the optimization problem of QLDS as
f y (AIa+ Or
X,X!
Cht X
X
(14)
n
71
The goal is to understand the statistical behavior of f, in particular its distribution, and the moments of the distribution. To that end, we will assume the following concentration property on the data
X= = X.).
Assumption (Distribution of D(X)) There exist two constants C, 0 (independent of n, d) such that, for any 1- Liliisshit,,uucttiio f Rex + R.
Px-D(X) (If(x)-m5(* sxx 2) S CC-((//0) Vt O,
where my is a median of the random variable Z. We require that the columns of X are independent Xut are i.i.d. such that Cov(x.)) (1) Σg. We further denote the mean and covariance for the columns of respectively as μe = E[x and C, Σ; +ppu
and that for E E {1, (8) ,
As discussed in the main article, Assumption notably encompasses the following scenarios: the columns of X are (i) independent Gaussian random vectors with identity covariance, (ii) independent random vectors uniformly distributed on the RP sphere of radius vp. and, most importantly, (iii) any Lipschitz continuous transformation thereof. Scenario (iii) is of particular relevance for practical data settings it recently shown (Seddik et al., 2020). Indeed, random data generated by GANs (for example, images) can be modeled as case (iii).
An intuitive explanation of Assumption I is that the transformed random variables f(x) for any f: Rd + IR Lipschitz has a variance of order (()). In particular, it implies that does not depend on the initial dimension d. Although data follow this assumption, line of reasoning suggests that this concentration property is most likely present in many real data. Indeed, most machine learning algorithms are Lipschitz applications that transform data of high dimension into a scalar (the decision score). If the data were not concentrated the decision score f=)) would have very large variance (depending on the dimension d) which would in turn lead to random performance. The fact that machine algorithm is supposed obtain non-trivial performance (different from randomness) combined with the fact that common machine learning algorithms are Lipschitz applications suggests that the concentration assumption is not meaningless for real applications.
not aware of any formal method to check whether some
As an example, we perform the following experiment: for the books data set, we take subset of examples and a subset of features, learn QLDD((1, (1,0) on them, and plot the empirical distribution of f(x). With conduct this experiment with the increasing and d, and see in Figure 3 that the variance with this increase remains to of the same order.
Furthermore, we place ourselves into the following large dimensional regime.
Assumption (Growth Rate) As + 0o, we consider the regime where d O(n), we assume d/n + > 0. Furthermore, nej/n + Czj and nug/n n. + Cuj for j = 1, 2. We denote by C₂ [ce1 Gr2] and c. [cu1, Cuz].
This assumption of the commensurable relationship between the number of samples and their dimension corresponds to a realistic regime and differs from classical asymptotic where the number of samples is often assumed to be exponentially larger than the feature size, which very unlikely in real-life applications.
Under Assumptions and 4, the objective of this section is fhree-folds: (i) determine the distribution of f,, (ii) determine the first order moment of f, and (iii) determine the second order moments of f,,
16

---

Under review as a conference paper at ICLR 2023
books
(n-200,d-40)
(n=400,d-80)
(n=600,d=120)
0.6
|n=800,d=160)
(n-1000.6-200)
0.5
(0=1200,6-240)
(n=1400,d=280
in-1600.6-320
in-1800,
0.3
|n=2000,d=
0.2
0.1
Figure 3: Practical illustration of the concentration property books data set. With increasing and d, every colored histogram corresponds to the empirical distribution the g(x) of QLDS(1,0).
D.1 DISTRIBUTION OF f,
The proof of the gaussian distribution of the decision score of several learning schemes has been provided recently in (Tiomoko et al., 2020) (for the thcoretical analysis of Multi-Tass Learning), (Seddik et al., 2021) (in the case of the theoretical analysis of softmax). follow a similar approach that is described follows.
Proof under Gaussian mixture model. Under a Gaussian mixture assumption for the input data X, the convergence in distribution of the statisties of the classification score f(x) is immediate as the projection of the deterministic vector w on the Gaussian random vector x, it follows that w x is asymptotically Gaussian.
Extension to concentrated random vector assumption. Since conditionally on the training data X, the classification score gxx expressed the projection of the deterministic vector w on the concentrated random vector the CLT for concentrated vector unfolds by proving that projections of deterministic vector on concentrated random vector is asymptotically gaussian. This is ensured by the following result.
Theorem (CLT for concentrated vector (Klartag, 2007; Fleury et al., 2007)) If x is concen- trated random vector as defined Assumption with E[x] 0, E[xx"] Ip and a be the uniform measure the sphere SD-1 C. IRP of radius 1, then for any integer O(1), there exist two constants C, and set θ C (8p-11k such that @ 2 ( vpCe eVB and
40 = (01...., E O.
Va E Rk sup P(aa OT x -(0)00)))))( <cp
tER
with G(t) the cumulative distribution function of N
Then the result unfolds naturally. Since g(x) is asymptotically Gaussian, we will focus computing its first and second order moment.
D.2 FIRST ORDER MOMENT OF f,
Using Equation (14), the first order moment of f,, can be computed as
E[C.] = E -yTx XT (Al an X,X,
X
an.
X,
(15)
17

---

Under review as a conference paper at ICLR 2023
Let's define for convenience the data matrix X being the concatenation of the labeled and unlabeled data matrix X and X i.e. = [,] E Rdxn,, Then the expectation in (15) can be rewritten in the more convenient compact formulation
F(..] = F Q Q (AI++ XAXI n
actine Onn One x
O Xnu -aaInn
A
I
To proceed, we furthermore introduce the matrices St
Raxme and S.
0 On xnz
In
Rex* such that X XS, and X, XS.. This lead to the following com-
Ong x pact expression depending only on the random matrix X
E[G.] = Ely? S X QX S.l.
(16)
Furthermore, let us recall the concept of deterministic equivalents, classical object in random matrix theory.
Definition 2 ((Couillet and Debbah, 2011, Chapter 6)) A deterministic matrix F (Raxd is said to be a deterministic equivalent of a given random matrix F E RRxdd denoted F < F, if for any deterministic linear functional fn. : Raxd R of bounded norm (uniformly over d, n),
fn [F F) 0 almost surely n, d DC.
In particular if F + F, then u (F- F)v S. for u, v two unit vectors, and for all deterministic matrix A of bounded norm we also have 1 A - F) a.a 0.
Deriving deterministic equivalents of the various objects under consideration will be a crucial tool to derive the main result. In particular, deterministic equivalents are particularly suitable to handle bilinear forms involving the random matrix F, in particular for the statistics of f, where the bilinear
form X QX appears (see Equation (16)).
Deterministic equivalent of X'Qx
Let unit vectors for the f--nomm we develop:
F(u T
[xQv]
Qxyuş]
n
n
$,==1
n
E [ux]] Qx + Σ
[uxx Qx,u,]-
Furthermore, let us define for convenience the matrix X which is the matrix X with a vector of Op on its i-th column such that XX X + xxX, Applying the Sherman -herrannMorrison matrix
inversion lemma (i.e., , (M uv TV- 1 M- M-'uy 'uv" M- vectors u, to leads to
for any invertible matrix M and 14v 14v M-
1 1 x
X AX + ALd
Q Q Q
Q
n1
A Q_ix;
The latter allows to disentangle the strong dependency between Q and x; as
Q-
Qx =
(17)
1 4 A Q_ix;
Using Equation (17) we rewrite QX as
1 1 Eluu X [QQVV== - n
Σ
T.X, Q -2
1 1
U.X, Q -iyK,
n
1 + Ago;
n
(1 + A1:5:) + A550,)
+
18

---

Under review as a conference paper at ICLR 2023
with 8, - Q Q-
Assumption ensures that (5) x1 Ang 2, i.i.d. data vectors,
(
we impose the natural constraint of equal ô1 ... Sn, within every class j 1,2. As such, may reduce the complete score vector ó E RR under the form
g = [6i 11 nex 82 82 51 1 mul 82 Ru2l
(18)
where 6j - [ Q
x X C,] # tr(E,Q) defined for each class 1,2.
Using the shortcut notation x, E[x:] and the independence between samples and xj for i + j. the expectation can finally be obtained as
1 L(u X QXx)
Σ
u;dous A
U Q i18yyy O(I/Vn).
A, +1,)))))))
We therefore deduce deterministic equivalent for X
QX
x
T
QX
+ A - JM, QM3J
where A is the diagonal matrix Au
Mg
m4
and
I+Ano,
Ita00
Itaco2
1-0.01 1-0
1 nm
0
0
1 1
The expectation can finally obtained as
E[G.] = y
A JMJ (M.JT S. n
1 y, s JM QM,J S.
It then remains find deterministic equivalent Q for Q. Similarly performed in (Louart and Couillet, 2018), the deterministic equivalent for Q can be obtained as
accer C1
+ CrCr2
auCal C1
OuGuz C2
Q + Q
AIa
(19)
1 + ag81
1 azd2
and
andz
Further defining
Ita,o1
I-and; N22 Ita,os
Lugaly we can further write
Q Q - M (Dx= + Q6M Qo
Qo = (AI K1 + 22)
Therefore M2 QM, = D= I - (Dx + M Ma - Dz=1! ADū where 5
[L/(1 + aroi), 1/(1 + azd2), 1/(1 -a,d1,, 1/(1 d2,d2)l and A = [2].
We then deduce the expectation as
m, = Elf Cy] (e(²) c Dj, D-1 L 1D= + + QoM) +MQQ 'D=' Dz. e.
with M (Dx M Q) - ., 111=1/(110) + agōi), 1/(1 + agd2)] and o. [1/(1
M agdz), 1/(1 02)].
In the case identity covariance tackled in the main article we have d = 61 = =ō and
D M M M
M
(20)
Ki
+ K2
Therefore the mean reads as
(-1) ctj
(e [2] e T De, D MM
m = Elfilx E CC,]=
(21)
Ki -
(1 0) + ox))
19

---

Under review as a conference paper at ICLR 2023
D.3
SECOND ORDER MOMENT OF fu
The second order moment of tu can be computed as
E Ef ful n² E
y. S X
S QXS.y.].
Let's define by convenience the matrix B S.S. As previously we are looking for deterministic equivalent for X QXBX Qx. We proceed in the same way by computing Eu X QXBX QXv) for all v.vo of unit norm:
1 E(u X QXBX QXv] n2
Σ
uxx;
Byyx Qx
n
1,,k==
Eluxx Qx, Qx +
Elux Qx, Qx
n²
n
1
+ n
E|uxx Qxx QXeun]
Eluxx Qx, [x,x) 0x
n
1,k=1 1
1
+
Elu,x, 2,, Qx,ui
n
and we reuse Equation (17) in order to continue
1
E B,,x, Q 2z
Elux B, 0-nkXaul
2
(1 + 8,;
n
(1 4416, + ARKdR)
2
Σ
Fluxx] Qi Bzj X P-131
F T -jx, Bj,,, Q ijx;ti
O(L/V7)
n12
+ (+
(1 (1 Ā
ifj
n
87
Σ
u.p: QC Q (1+ A:z:)(1 + AnrŌs)
04
Buut + n
(1 + 5,
if
U Q8 B
tr (C,QCCCus Q) u.u.
+
+ O(1/M),
(1+ A 8.1 + 8,3
n
(1 + And;))
1=1
where Cus is defined as
1 Σ
B
Cuj C
(22)
1=1 (1+ A,o,))
(1 ,,
Let's denote for convenience by E the deterministic equivalent of QC then deterministic equivalent for X T QXBX QX given as:
TXXXX QX + A JM EM n!
1
ABJM, QM&J
+2
+
n
where E is the diagonal matrix containing its diagonal En
1 [[( (C.QC Q)] irCCEE
n
We therefore deduce the variance of f, as
Var (f.)) = E(F fw] E(f.,]
JM, EM
ABJM QM&JT
= S
A +
2
+ + Saye
y.S.. ST
A + JMM QM;J
B
A
JM QM&JT Seye
JJM] EM
=yTs]
EE) Siye-
n
20

---

Under review as a conference paper at ICLR 2023
The last step consists in finding a deterministic equivalent of QC Q denoted E. To that end let's
evaluate for any deterministic vector v, u E Rd unit norm, - El us Q Q)v]. Applying the matrix identity A -1 B- A A (B - A)B-I for any invertible matrix A, B to Q Q and using algebraic simplifications in partieular Equation (17) allow successively obtain
-E J QC (Q QQv] = _ u TTQ...QQ
(C&
XAX n
Q
1
A QC.ss x Qv
+ QC QC
+ O(I/VT)
n
n
1+ AnO;
1
1 1A A Qu, Q x Qv
n
1 A T x-xx, Qu Qv + +011/M)
F
11
1 And;
(1 + And.)²
1
A QC
E
tr Qu
O(IvVn),
1
71
(1 + A,,d,
where
(II + Cs) C8
aren C1
Cuery
avCai C2
auCuz
I+ao
I+ae02
I-a.01
I-ay02
Therefore
cxaade
Curagie
QC Q + E QC Q
QC
Σ
QC
(23)
(1 + axdk)²
0z
A=
where de
1 tr (C& Q). Right Multiplying Equation (23) by Cj and taking the trace allows retrieve an expression for D = Da, with d [d1, d2] as
D Di 12 12-Da
D&V)
VAA 1 (Cx
1 (C,, ãR
C
4
n
(1 + ardr)²
(1- a1,
02)
Similarly as performed for the mean, the variance can be furthermore simplified as
Var(fi) = (e: -22 DD.MDDD MGMMD.'DD
DDDDe, (er e2)
where G = M CO C = Cus + Σ Cr. In the case of identity covariance matrix
tackled in the main article,
g
Σ
dzdk
5M M
k=1
with dy and ã which simplifies as
1 d+ (1-a,, (A+ N2)2 coāz
CpCu
CE
Cub
(1 + az0)2 + (1 0)5)2
This leads the theorem in the general covariance matrix
Theorem 4 Let X Rdx be a data set that follows Assumptions and and consider the notation convention defined previously. For any x E X., with x E Cj and f(x) surely for both classes j
1 w x, we have almost
vn
f(x|x E C2) -f; -5,
4.g 0, where i3 N Z~~Nmi;,03 (m;
The mean my and the variance o² are defined as
1 yy Sy JMJ QM,J S...
m, =
of (e) _T (Da, DDDT MG. DaD.,, (el -2);
21

---

Under review as a conference paper at ICLR 2023
E EXPERIMENTS
This section complements Section 5 of the main paper by giving more details of the experimental setup and performing two additional experiments.
E. EXPERIMENTAL SETUP
Table 3 sums up the characteristics of publicly available real data sets used in our experiments. As we are interested in the practical use of the proposed approach in the semi-supervised regime, we test the performance in the case when T4 < Ru. Thus, instead of using the original train/test splits proposed by data sources, we set our own labeled/unlabeled splits to fit the semi-supervised context. For each data set, perform experiment 20 times by randomly splitting original data labeled and an unlabeled sets fixing their sample sizes to the values shown Table 3. For the results, we evaluate the transductive error on the unlabeled data and display the average and the standard deviation (both in %) over the 20 trials. All experiments were performed on a laptop with an Intel(R) Core(TM) 17-8565U CPU @ 1.80GHZ, 16GB RAM. The implementation code for reproducing the experimental results of the paper will be released upon acceptance of the article.
Table 3: Characteristics of data sets used in our experiments.
Data set
# of lab. examples, # of unlab. examples, Dimension, Class Proportions
Books
20
1980
400
0.5:0.5
DVD
19
1980
400
0.5:0.5
Electronics
1979
400
0.5:0.5
Kitchen
19
1980
400
0.5:0.5
Splice
990
0.48:0.52
Mushrooms
81
8043
112
0,48:0.52
Adult
325
32236
14
0.76:0.24
E.2
ESTIMATION OF CLASS PROPORTIONS FOR UNLABELED DATA
Synthetic data (p = 200)
MNIST (p= 100)
Amazon review (p 400)
0.05
0.18
0.4
0.04
0.17
0.04
0.35
0.16
0.03
0.3
0.5
0
0.5
0.5 RejRu Puy
Rej Puy
Bin Optimal error (with Cuj = Cr. mz Ground truth optimal error
Figure 4: Optimal Classification error as a function of discrepancy between class proportion in labeled and unlabeled set Mi Mi
In the first experiment, we analyze the influence of the assumption Cuj = Ctj I and class the same in unlabeled and labeled set) by representing the optimal classification under this assumption and the optimal classification error knowing the true value of cuj function of the violation of this assumption represented by the ratio neyua n. As recall, this assumption is needed since the theoretical performance depends Cuj which is not known priori and needs to
ax (proportion of class
22

---

Under review as a conference paper at ICLR 2023
be estimated. As shown in Figure 4, this assumption doesn't alter the overall behavior of the model selection approach since the model selection is the Same even though the proportion of class and different in labeled set and unlabeled set MM 1)
Ruy
E.3 IMPROVEMENT OVER THE SUPERVISED BASELINE
In second experiment, we represent the gain with respect LSSVM (=(af, - az)) of QLDS when optimizing the hyperparameters (as performed theoretically in Algorithm of the main paper) as function of the difficulty of the task (implemented through the norm of the matrix M) and the number of labeled samples. Figure 5 which looks like "phase diagram" shows that non-trivial gain is obtained with respect to a fully supervised case. In particular, one can see that the gain of using semi ceni-supervised approach is relevant when few labeled samples are available and when the task is difficult. This conclusion is similar to existing conclusion from (Mai and Couillet, 2021; Lelarge and Miolane, 2019).
0.30
18
0.5
Talk difficitty
16
14
12
10
3.0
Figure 5: (Left) Relative gain with respect to supervised learning as function of the labeled sample size and the task difficulty (through the choice of the distance between the mean of class I and class 2 || - (22l) on synthetic gaussian mixture model. A higher value of || #2ll means that the task easy and a smaller value means that the task is difficult. On the left lower corner (difficult task and small number of labeled samples non-trivial gain is obtained with respect to fully supervised case. The task difficulty in the y-axis is || Pall which measures the distance between the mean of the two classes.
E.4 COMPARISON OF DIFFERENT SEMI-SUPERVISED LOSSES
In this section, we additionally support our choice of the learning objective given by Eq. 1 and compare different possibilities to construct the loss function for semi-supervised linear classification. More specifically, we compare for the labeled part
1. the quadratic loss Σx (1: - x xX[W]] w)²
2. differentiable surrogate of the hinge loss Em ,/4 log(1 exp (>(1 vix w)}) vix(w))) with y set to 20 (Zhang and Oles, 2001),
3. the log-loss Σm ys log o (x, w) + (1 y:) log(1 - ((xTw))
and for the unlabeled part
1. the quadratic margin Li=n (wT x,
2. the differentiable surrogate of the absolute value of the margin Σ (Chapelle and Zien, 2005).
net Dimnetl expl-3(wTT
We consider all possible combinations of the labeled and the unlabeled parts which result in semi- cumi-supervieed losses. We optimize them using Adam optimizer (Kingma and Ba, 2015) fixing the learning rate and the weight decay to 10-3 and 10-5, respectively. Note that when the square loss and the quadratic margin considered, have gradient-based version of QLDS.
23

---

Under review as a conference paper at ICLR 2023
books (error)
(a²)
books (a.)
0.400
400
200
200
50
0.300
0.275
0.5
0.200
0.2
0.8
0.06
Number of labeled examples, frr
Number labeled examples, fh
Number labeled examples, /h
dvd (error)
dvd (ay)
dvd (a.)
700
0.35
1-
0.3
0.3
0.06
0.5
2024 22 42 54 70 119154200
20 32 42 54 70 92 118154200
20
32 42 70 118154200
Number labeled examples,
Number labeled examples,
Number labeled examples,
QLDS(O.1)
STILS-SVMI
GLDS (c9)
QLDS (UP)
OLDS (o1)
Figure 6: The performance and model selection results on different data sets with the increase of the number labeled examples.
For fair comparison, for each loss, perform grid search over possible values of Ozg, Ou.y À and choose the best solution according to the oracle, namely, the performance on the unlabeled data. Table 4 illustrates the performance results on 7 real data sets, One can see that in most of cases the quadratic margin outperforms the absolute value of the margin. In general, the combination of the square loss and the quadratic margin appears to be stable leading to the second-best solution in many cases. Thus, by choosing this learning objective, we do not lose much efficiency, having a convex objective and the ability conduct theoretical analysis.
Table The classification error of different supervipe losses on the real benchmark data sets. Square Loss Quadratic Margin corresponds to QLDS. The smallest and the second smallest error values are highlighted bold and italics, respectively.
Square Loss
Hinge Loss
Log-Loss
Data set
Quadratic
Abs Value
Quadratic
Abs Value
Quadratic
Abs Value
books
25.82 = 1.23
34.13
+: 2.71 23,83 + 0.85 33.38
2.78
36,2 :: 1.99
36.67 +: 2.05
24.81 2.97
34.74
+:
23.33
34,86
2.72
37.34 = 2,37
37.69 1: 2.22
electronics
19.82 0.57
26.07
+: 2.88
19.22
26.37
2.89
32.52
2.55
33.27
2.83
kitchen
18.75 + 0.85
24.02
+ 2,86
17.93 0.57
22.95 +: 1.84
31.04 = 3.04
31.75
3.3
splice
34.47 + 2.59
34.29
+: 3.8
34.42
34.3
3.73
3.27
38.72
2.22
mushrooms
+
0.66
2.33
adult
19.63 0.88
19.65
+: 0.9
18.38 +: 0.73
18.5 0.81
18.43 0.64
18.47 0.72
E.5 PERFORMANCE DEPENDING ON NUMBER OF LABELED EXAMPLES
This section extends Section 5.2 of the main paper by providing experimental results for different size labeled set. addition, we depict the values of a and a, (averaged over splits) taken by OLDS (th), QLDS (cv) and QLDS (or). All the results can be seen in Figure 6 and Figure 7.
E.6 CHOICE OF
In Section 5, have fixed the value of À as the maximum eigenvalue of X X,, for all versions of QLDS. To support this choice and make sure that it does not harm the baselines, this section provide additional experiment, where compare the fixed value of À with the case
24

---

Under review as a conference paper at ICLR 2023
electronics (error)
electronics (ay)
elect ron (a²)
0.35
500
300
200
100
0.30
0.25
0.6
0.20
0.5
0.2
0.1
0.05
118154200
154200
118154200
examples, fr
examples,
examples,
OLDSIO.1)
STILS
QLDS (th)
kitchen (error)
tchen (az)
kitchen (aty)
100
0.275
4-
0.250
6-
0.0
1-
0.2
0.175
0.001
2024 32 42 119154200
20
42 1181154200
20
1181152200
Number of labeled examples,
Number of labeled examples,
Number of labeled examples,
OLDS1O.1)
STILS OLDS (cv)
GLDS (th)
OLDS (on)
sp Lice (error)
Lice (ar)
splice (a.))
500
200
0.25
0.30
0.04
0.6
0.006
0.2
0.001
0.05
1181442000
11515420 examples,
examples, fr
examples,
OLD%(011)
STULS-5VMI
QLDS
OLDS (th)
(or)
adult (errar)
adult (az)
adult t (ay)
0.38
200
100
0.36
0.34
10
3-
0.32
0.1
2024 32 42 54 70 92 118154200
20.4 32 42 118154200
20.24 32 42 118154200
Number of labeled examples,
Number of labeled examples,
Number of labeled examples,
0ID%/o.1)
STULS-UMM GLBS
QUBS (1h)
. DLDS (or)
mushroans (error)
mushrooms (ay)
mushrooms (a.)
0.20
300
300
50
0.15
2-
0.10
0.05
0.206
0.04
0.01
0.06
0.00
0.001
118154000
1181552000
1i9154200
examples, fr
examples, f
examples, f,
OLDS(0.1)
STILS
QLDS
Figure 7: The performance and model selection results different data with the increase of the number labeled examples.
25

---

Under review as a conference paper at ICLR 2023
when À is tuned by the 10-fold cross-validation on the available labeled set. Table depicts this comparison for QLDS (1, 0) (LS-SVM) and QLDS (0, (GB-SSL)... As one can see on of data sets the maximum eigenvalue heuristics outperforms the cross- vross-validation. The experimental results suggests that the cross-validation policy more relevant for the cases where the labeled data is more informative than unlabeled data (adult and mush rooms). Otherwise, the maximum cigenvalue heuristics seems to be more appropriate, which is accorded with (Mai and Couillet, 2021).
Table 5: The classification error of the supervised and the unsupervised baselines when the hyperpa- rameter À is fixed to the maximum eigenvalue, and when it's tuned using the cross-validation on the labeled set. The smallest error for each baseline is highlighted in bold.
QLOS (1, 0) (DS-8VM)
QLDS (0, 1) (SB-S5L)
Data
Fixed
CV
Fixed
CV
books
37.47 + 2.25 38.32 # 2.37
26.47 = 0.72 32.84 + 8.65
dvd
38.33 + 1.72
38.56 2.03
29.12 + 1.35
32.74 + 7.26
eLectronice
34.15 + 3,25
3.0
19.4
23.
kiLchen
3.02
19.31 4.44
22.05
eplice
39.81 + 2.93
40.38
35.48 0.86 39.53 3:53
adult
33.35 + 0.68
32.13
36.28 - 0.06
34,0 + 0.73
mushrooms
6.55
2.07
2.53 1.38
0.04
1.47
26


Reviews:
[{"review_id": "qfApXYWglk4", "reviewer": "Reviewer_xxab", "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": "", "summary_of_the_paper": "This work investigates the performance of a linear semi-supervised learning method named QLDS. The method in formulated in terms of an empirical risk minimisation problem consisting of the standard ridge risk (square loss + $\\ell_2$ penalty) for the labelled data and a quadratic term for the unlabelled data encouraging low-density solutions. Since the risk is quadratic, one can write down an explicit solution, therefore mapping the question of computing the performance of QLDS to a random matrix theory problem. The key question of interest is how to optimally tune the hyperparameters gauging the trade-off between the supervised and unsupervised parts in order to minimise the population misclassification error. The main contributions are:\n\n1. Under a concentration assumption on the data, to show that the predictor is an asymptotically Gaussian random variable with mean and standard deviation given by the solution of a set of self-consistent equations (Theorem 1). In particular, this can be used to derive an exact asymptotic formula for the misclassification error depending on the hyperparameters of the problem.\n\n2. The equations above depend on the Gram matrix of the population means of the data. The second result provides a theoretical guarantee on the estimation of these means depending on the quantity of labelled data available (Proposition 2).\n\nTogether, these two results are used to study how to design a procedure to tune the hyperparameters in the model (relative strength between supervised and unsupervised terms), summarised in Algorithm 1. Some numerical experiments on both synthetic and real data are provided, comparing cross-validation to the procedure proposed, and the performance of optimally tuned QLDS to other methods from the literature.", "summary_of_the_review": "This works provides a sharp asymptotic analysis of a semi-supervised setting, providing a theory-driven efficient algorithm to optimally tune the hyperparameters, and provides numerical support for the theory. Most of the concerns raised by the reviewers in the previous version have been fixed, and I hope the additional suggestions will further improve the work.\n\nOverall, I believe this work is of interest to the ICLR community.", "strength_and_weaknesses": "**Disclaimer**: For full transparency, I have previously reviewed this submission at a different venue where it was evaluated by four referees and the AC as a borderline rejection, with a recommendation to review and resubmit. Quoting the decision:\n\n> *\"Ultimately this was a borderline decision, and I reviewed the paper myself to make a final decision. I believe that the paper is in need of a major revision to address the issues raised by the reviewers, and thus cannot recommend acceptance at this time. But I do hope the authors revise and re-submit this paper to another top conference soon.\"*\n\nAlthough the content of the work is essentially the same, I am happy to see that the authors have taken most of the suggestions raised by the reviewers into account in this new submission. In my (fresh) review below, I revisit some of the points previously discussed with the authors in view of further improving the submission.\n\n**Strengths**: The paper is well-written and easy to follow. The exact asymptotic analysis of a semi-supervised task adds to a literature which has mostly focused on supervised and unsupervised settings.\n\n**Weaknesses**: On the other hand, on a technical level this work doesn't bring any new significant technical contribution, but rather combine existing tools to analyse a task of interest.\n\n**Comments**\n\n- **[C1]**: I appreciate the authors have made an effort to diversify their bibliography. Just a small note on a new sentence in the *Related work* section:\n\n>To continue with physical statistics-based methods, we highlight (Lelarge and Miolane, 2019) which derived Asymptotic Bayes\nrisk using theoretical information and a replica method.\n\n[Lelarge, Miolane '19] *do not* employ the replica method. Instead, they do give a heuristic derivation of their result based on the *cavity method*, which is closely related to the \"leave-one-out\" method from RMT (and which I believe the authors are more familiar). This result is then proven using Guerra's interpolation technique [Guerra '03] and the Aizenman-Sims-Starr scheme [Aizenman et al. '03].\n\n- **[C2]**: Although this is now mentioned en passant below eq. (1), the assumption that the regularisation $\\lambda$ needs to be fixed to the top singular value of the features in order to make the empirical risk convex is very important for Theorem 1. This should be made more explicit in the assumptions.\n\n- **[C3]**: In my previous review, I noted to the authors that the claim that it is a *\"well-stablished fact that quadratic cost function are asymptotically optimal\"* is both strong and inaccurate in the stated generality, since it is setting specific. For instance, for a simple binary classification task in a teacher-student setting with Gaussian covariates, optimally regularised ridge regression has a generalisation decay of $\\sim n^{-1/2}$ while optimally regularised logistic regression has a generalisation decay rate of $\\sim n^{-1}$, which matches the Bayes-optimal rate for this problem [Aubin et al. '20]. But other examples of settings where there is a clear benefit of using other losses over the square loss abound, e.g. random features model [Gerace et al. '20] or kernel classification with source and capacity conditions [Cui et al. '22] to mention a few.\n\nThe authors now mention they added a Table 4 in the appendix justifying this claim in their setting, but I was surprised to find Table 4 doesn't exist in the appendix.\n\nHonestly, I don't understand why the authors insist in such a strong claim which is setting specific and wrong in general.\n\n\n- **[C4]**: One of the key points of the paper is that SSL improves over the supervised baseline by using the theory motivated Algorithm 1 (QLDS). Therefore, a fair comparison should benchmark QLDS against both the fully supervised and unsupervised settings at *optimal* (and not fixed) regularisation (as done in the main text). Unless I missed it, this is only discussed in Appendix G:\n\n>[...] Figure 5 which looks like a \"phase diagram\" shows that a non-trivial\ngain is obtained with respect to a fully supervised case. In particular, one can see that the gain of\nusing a semi-supervised approach is relevant when few labeled samples are available and when the\ntask is difficult. This conclusion is similar to existing conclusion from (Mai and Couillet, 2021;\nLelarge and Miolane, 2019).\n\nI believe the discussion of when one gains using SSL with respect to the baseline is quite a quite relevant outcome of this work. Therefore, I would strongly suggest the authors to mention it in the discussion of the theoretical results in the main text.\n\n\n**Small typos**:\n\n- *\"[...] using theoretical information\"* -> *\"[...] using information theory\"*\n\n**References**:\n\n[[Aizenman et al. '03]](https://journals.aps.org/prb/abstract/10.1103/PhysRevB.68.214403) M Aizenman, R Sims, and SL Starr. *Extended variational principle for the Sherrington-Kirkpatrick spin-glass model*. Physical Review B, 68(21):214403, 2003.\n\n[[Guerra '03]](https://link.springer.com/article/10.1007/s00220-002-0773-5) F Guerra. *Broken replica symmetry bounds in the mean field spin glass model*. Communications\nin mathematical physics, 233(1):1–12, 2003.\n\n[[Aubin et al. '20]](https://proceedings.neurips.cc/paper/2020/hash/8f4576ad85410442a74ee3a7683757b3-Abstract.html) B Aubin, F Krzakala, Y Lu, L Zdeborová, \"Generalization error in high-dimensional perceptrons: Approaching Bayes error with convex optimization\", Part of Advances in Neural Information Processing Systems 33 (NeurIPS 2020)\n\n[[Gerace et al. '20]](https://proceedings.mlr.press/v119/gerace20a.html) F Gerace, B Loureiro, F Krzakala, M Mézard, L Zdeborová, \"Generalisation error in learning with random features and the hidden manifold model\", Proceedings of the 37th International Conference on Machine Learning, PMLR 119:3452-3462, 2020.\n\n[[Cui et al. '22]](https://arxiv.org/abs/2201.12655) H Cui, B Loureiro, F Krzakala, L Zdeborová, \"Error Rates for Kernel Classification under Source and Capacity Conditions\", arXiv: 2201.12655 [stat.ML]", "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": "on1gq1BleU", "reviewer": "Reviewer_Cq3e", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "The paper proposes a linear semi-supervised classification model, where the low density separation assumption is implemented via quadratic margin maximization. \n\nIt bridges supervised and unsupervised learning - the least-square support vector machine in the supervised case, the spectral clustering in the fully unsupervised regime.", "summary_of_the_review": "The proposed method bridges supervised and unsupervised learning, and this is very new to me.", "strength_and_weaknesses": "* Strength\n\nThe proposed method bridges supervised and unsupervised learning.\n\n* Weakness\n\nThere is a lack of non-asymptotic results.", "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": {}}, {"review_id": "g4oZ9swIr5", "reviewer": "Reviewer_LHdi", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "The authors of this paper present a semisupervised adaptation of the linear least squares-SVM. This formulation trivially contains the LS-SVM and linear spectral clustering as special cases. The bulk of the paper and perhaps its most interesting contribution is its theoretical analysis of the method which utilizes random matrix theory to analyze the asymptotic behavior of the estimator and gives a way to choose hyperparameters. The efficacy of the classifier is experimentally verified against some simple baselines.", "summary_of_the_review": "It seems as though the topic presented here may be a valid line of research, but the paper presented here is not in state that I can recommend acceptance. Additionally the limited experimental evaluation and theoretical contributions are make this work very niche, I do not think this would be of significant interest to the ICLR crowd. ", "strength_and_weaknesses": "Strengths:\n* Formulation is new as far as I know.\n* Asymptotic analysis is nice.\n\nWeaknesses:\n* The theory isn't very well-explained and there are small mistakes or at least unclear statements in the math.\n* The contributions aren't very significant: the experimental results don't include any strong competitors, the theory is a fairly straightforward application of existing results, and the classifier formulation isn't particularly novel.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject