Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data
Authors: Eyar Azar
Boaz Nadler
Venue: NeurIPS 2024 spotlight (2024)
Keywords: semi-supervised learning
gaussian mixture models
high-dimensional statistics
sparsity
statistical-computational gaps
Primary area: learning_theory
TL;DR: Our work highlights the provable benefits of combining labeled and unlabeled data for classification and feature selection in high dimensions.

Abstract: The premise of semi-supervised learning (SSL) is that combining labeled and unlabeled data yields significantly more accurate models.
Despite empirical successes, the theoretical understanding of SSL is still far from complete. 
In this work, we study SSL for high dimensional sparse Gaussian classification. 
To construct an accurate classifier a  key task is feature selection, detecting the few variables that separate the two classes.
For this SSL setting, we analyze information theoretic lower bounds for accurate feature selection as well as computational lower bounds, 
assuming the low-degree likelihood hardness conjecture. 
Our key contribution is the identification of a regime in the problem parameters (dimension, sparsity, number of labeled and unlabeled samples) where SSL is guaranteed to be advantageous for classification.
Specifically, there is a regime where it is possible to construct in polynomial time an accurate SSL classifier.
However, any computationally efficient supervised or unsupervised learning schemes, that separately use only the labeled or unlabeled data would fail.  
Our work highlights the provable benefits of combining labeled and unlabeled data for classification and feature selection in high dimensions. 
We present simulations that complement our theoretical analysis.

Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data
Eyar Azar Weizmann Institute of Science eyar. azar@weizzn zmann. ac il
Boaz Nadler
Weizmann Institute of Science boaz nadl eee immann ac
Abstract
The premise of semi-supervised learning (SSL) is that combining labeled and unla- beled data yields significantly more accurate models. Despite empirical successes, the theoretical understanding SSL is still far from complete. In this work, we study SSL for high dimensional sparse Gaussian classification. To construct an accurate classifier a key task is feature selection, detecting the few variables that separate the two classes. For this SSL setting, we analyze information theoretic lower bounds for accurate feature selection well as computational lower bounds, assuming the low-degree likelihood hardness conjecture. Our key contribution is the identification of regime the problem parameters (dimension, sparsity, num- ber of labeled and unlabeled samples) where SSL is guaranteed to be advantageous for classification. Specifically, there is a regime where it is possible to construct in polynomial time an accurate SSL classifier. However, any computationally efficient supervised or unsupervised learning schemes, that separately use only the labeled unlabeled data would fail. Our work highlights the provable benefits of combining labeled and unlabeled data for classification and feature selection high dimensions. We present simulations that complement our thcoretical analysis.
Introduction
The presumption underlying Semi-Supervised Learning (SSL.) is that accurate predictors may be learned by leveraging both labeled and unlabeled data. Over the past 20 years, many SSL methods have been proposed and studied (Chapelle et al.) 2006 Zhu & Goldberg 2009). Indeed, on many datasets SSL yields significant improvements over supervised learning (SL) and over unsupervised learning (UL). However, there are also cases where unlabeled data does not seem help. A fundamental theoretical issue in SSL is thus to understand under which settings can unlabeled data help to construct more accurate predictors and under which its benefit, if any, negligible.
To address this issue, SSL was studied theoretically under various models. Several works proved manifold assumption, with sufficient unlabeled data, SSL significantly
that under cluster outperforms SI. (Rigollet) 2007 Singh et al., 2008). In some cases, however, SSL performs similarly to UI. (i.e., clustering, up label permutation ambiguity). In addition, Ben-David et al. (2008) described family of distributions where SSL achieves the same еттог rate as SL.
In the context of the cluster assumption, a popular model for theoretical analysis is Gaussian classification, in particular binary classification for a mixture two spherical Gaussians. In this case, the label Y E {+1} has probabilities P(Y x IR follows a Gaussian distribution,
Ty and conditional on a label value y, the vector
y (1
(1)
where μ1, p-1 E R are both unknown. This model and related ones were studied theoretically in supervised, unsupervised and supervisd settings, see for example Li et al. (2017); Tifrea et al.)
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

(202)) : Wu & Zhou (,021) and references therein. Without assuming structure on the vectors My or on their difference (such as sparsity), there are computationally efficient SL and UL algorithms that achieve the corresponding minimax rates. Moreover, Tifrea et al. (2023) proved that for the model I no SSL. algorithm simultaneously improves upon the minimax-optimal error rates of SL. and UL.. In simple words, there do not seem to be major benefits for SSL under the model
In this paper we consider a mixture of two Gaussians in a sparse high dimensional setting. Specifically, we study balanced binary classification with sparse difference in the class means, which is a specific instance of [I Here, the joint distribution of a labeled sample (x, y) is given by
y ~ Unif(=1}. x ~ (My. Ip).
The class means M-11 E IPP are unknown, but their difference 14: 14 p is assumed to be k-sparse, with k < p. In supervised setting, model (2) is closely related to the sparse normal means problem, for which both minimax rates and computationally efficient (thresholding based) algorithms have been developed and analyzed, c.g. (Johnstone (1994 2002). In an unsupervised setting, inference on the model (2) is closely related to clustering and learning mixtures of Gaussians (Azizyan al. 2013 Jin & Wang. 2016). A key finding is that in an unsupervised setting with sparsity assumption, there is a statistical compsiicall-mppattinnnni gap (Fan et al.] 2018: Löffler et al., (022). Specifically, from information viewpoint number of unlabeled samples proportional to k suffices to accurately cluster and to detect the support of Aqa. However, under under various hardness conjectures, unless n x k², no polynomial time algorithm able even detect if the data came from one or from two Gaussians (namely, distinguish between Ap = 0 and || = O()).
In this work we study the model 22 in SSL setting, given L labeled samples and unlabeled samples, all ii.d. from (2). Despite extensive works on the SL and UL settings for the model (2). the corresponding SSL setting has received relatively little attention far. This gives rise to several
questions: On the theoretical front, what is the information lower bound for accurate classification and for recovering the support of Apt? On the computational side, is there computationall-satiinee gap in SSL? In addition, are there values of and n for which SSL is provably beneficial as compared to SL and UL separately?
Our Contributions. (i) We derive information theoretic lower bounds for exact support recovery in the SSL setting. As described in Section 2.2, our lower bounds characterize sets of values for the number of labeled and unlabeled samples, where any estimator based on both types of data is unable to recover the support. To derive these bounds, view SSL data fusion problem involving the merging of samples that come from two measurement modalities: the labeled set and the unlabeled set. In Theorem 2.3 present general non-asymptotic information-theonee
result for recovering a discrete parameter in this setting. This general result is applicable to other data fusion problems and may thus be of independent interest.
(ii) We present SSL computational lower bounds. These are based on the low-degree likelihood ratio hardness conjecture (Hopkins & Steurer, 2017 Kunisky et al. (002)), in asymptotic setting where dimension p + oo and a suitable scaling of the sparsity k, and of the number of labeled and unlabeled samples. Our main result is that there is a region of the number of labeled and unlabeled samples, whereby in a SSL setting, accurate classification and feature selection are computationally hard. Our analysis extends to the SSL case previous computational lower bounds that were derived only in UL settings. In particular, if the number of the labeled samples is too small then the statistical- computational gap still remains. To the best of our knowledge, our work is the first to extend this framework to a SSL setting.
(iii) Building upon (i) and (ii), our key contribution is the identification of region where SSL is provably computationally advantagcous for classification and feature selection. Specifically, in Section 3 we develop polynomial time SSL algorithm, denoted LSPCA, to recover the support of Au and consequently construct a linear classifier. We then prove that in a suitable region for the number of labeled and unlabeled samples, LSPCA succeeds in both feature selection and accurate classification. In contrast, under the low degree ratio hardness conjecture, any computationally efficient SL or UL schemes, that use only the labeled or unlabeled data separately, would fail. In Section 4 we show via simulations the superiority of LSPCA, in both support recovery and classification error, in comparison to several SL and UL. methods, a self-training SSL scheme and the SSL method of Zhao et al. (2008).
Figure T summarizes the picture emerging from our work in combination with previous papers that analyzed the UL and SL settings of (2) namely, the r-axis and y-axis in Figure [ As in prior

---

Labeled
2
1
Computationally Feasible
(supervised)
1
SSL Succeeds
β
Computationally
Feasible (unsupervised)
Impossible
1/2
Computationally Hard
1
2 Unlabeled
Y
(n=
Figure I: Semi-supervised classification and support recovery regions. The red and green regions follow from previous works. Contributions of our work include identification of the orange and the blue regions.
works we consider fixed separation =
0(1), where Au is k-sparse. The asymptotic setting is that (k, L, p) all tend to infinity with the following scaling, which arises naturally for this problem (see Section 2p: the number of labeled samples is L = 22k Log(p) the number of unlabeled samples scales
x k7 k²/x², , and the sparsity scales as ie pd for some (0, 1/2). The figure shows different regions unlabeled and labeled samples, where classification and feature selection or computationally easy. We say that classification is impossible if for any classifier there is a k-sparse vector Ap whose corresponding accuracy no better than random. Similarly, say that feature selection is impossible if for any estimator S of size k there is a k-sparse Ap with support such that (S n SI + 0 as p + oc. Feature selection is easy if it is possible construct polynomial time a set S of size such that n S1/k + 1. This implies that the corresponding classifier has an excess risk that asymptotically tends to zero. The green region 7 > 2 follows from Deshpande & Montanari 2014)), since in this case support estimation is computationally feasible using only the unlabeled data. The region depicted in red is where classification and support recovery are impossible. The impossibility of support recovery follows from Ingster 1 Donoho & Jin (2004), who proved that support recovery is feasible if and only if 3 I - The same condition holds for classification as well, as described in the supplement. The orange and blue regions in Figure T from novel results of this paper. In the orange region, defined as 3 lower bound Theorem [u.gsss that any polynomial-time scheme will not succeed in accurate classification. In the blue region, characterized by / E ya, a) and 7 2, our proposed polynomial time SSL method is guaranteed to construct an accurate classifier. This is proven in Theorem 3.2 In addition, note that in this regime, the availability unlabeled data allows decrease the number of labeled samples by factor of 1-a Under the low degree hardness conjecture, in T-
the (y, plane, namely as a function of the number of
either impossible, hard
or and 1 <?
our computational
this blue region no computationally efficient SL or UL method that separately analyze the labeled or unlabeled samples, respectively, would succeed. We conjecture that the remaining white region, no polynomial-time algorithm exists that is able to recover the support able to construct an accurate classifier. summary, our work highlights the provable computational benefits of combining labeled and unlabeled data for classification and feature selection in a high dimensional sparse setting.
The cardinality of a set B is BB]. For a vector IRP, we denote its restriction to subset T C [p] by v/7. For vectors b, their inner product (a, b), and ||a|] denotes the Eg norm. We say that f()) w(g(p)) if for any e > 0, there exists Po > 1 such that fp) > cg(p) ) for every p 2 po.
Notation For an integer p. we write [p] =
3

---

2 Theoretical Results
In this section we present our first two contributions, namely an information- lower bound for exact support recovery of Ajt, and a computational lower bound for classification and support recovery, in a SSL setting. To this end, in Section 2.1 we first review lower bounds for SL and UL settings. As present their proofs, based on Fano's 's inequality. in the supplementary. Our main contribution here, described in Section 2.2 is SSL lower bound. To derive it, we view SSL as a data fusion problem with two types of data (the labeled set and the unlabeled set). The SSL. lower bound then follows by a combination of the lower bounds for SL. and UI..
not able to find these precise results in the literature, for completeness
To derive lower bounds, it suffices to consider a specific instance of (2). where the two Gaussian means are symmetric around the origin, with μ1 ---1- μ. Hence,
y Unif(#1), øly Ip),
Here, μ E IRP is an unknown k-sparse vector with & norm of VX. We denote its support by supp( (ilms + 0}. and by S the set of all (?) possible k-sparse support sets. We denote by and D., = { the i.i.d. labeled and the unlabeled datasets, respectively.
D,. =
To derive information and computational lower bounds for support recovery, it is necessary impose a lower bound on minges |4,/- As in Amini & Wainwright (2009); Krauthgamer et al. (2015). suffices to study the set of most difficult k-sparse vectors with such a lower bound their entries. In case this translates to the nonzero entries of Іu belonging to /=/A/K) Clearly, if some signal coordinates had magnitudes larger that / A/kk then the problem of detecting them and constructing an accurate classifier would both be easier. Throughout our analysis, we assume is of this form and the sparsity & known. All proofs appear the supplementary.
2.1 Information Lower Bounds (Supervised and Unsupervised)
The next theorem states non-asymptotic result for exact support recovery in the SL case.
Theorem 2.1. Fix 5 (0, For any (T.p. k) such that
L 2(1 8)k log (p 1),
and for any support estimator S based DL, it follows that maxses TP >
log
log(p (og))
Donoho & Jin 2004) proved a similar result in an asymptotic regime. Specifically, they proved that
2 log p. approximate support recovery is possible if and only if ,3 > 1 Theorem 2.T states a stronger non-an asymatyttooiic result for exact support recovery. implies that even >
for k = pd and L.
is still impossible to recover the exact support with probability tending to one if 3 < 1.
Next present an information lower bound for exact support recovery in UL. Here we observe vectors 2; from 3 but not their labels
Theorem 2.2. Fix ā E (0, For any kn, + oo with & - 0 and
2(1 - 8)k:
n < X2
log (p- - k: + 1) max (1,A)
(5)
for any support estimator 5 based on Dr,, as p > 50. then maxses IP ($+ 2
The scaling in Eq. (5) appeared in several prior works on related problems. Azizyan et al. (013) showed that for À < I. with number of samples < && log(p/k), no clustering method can achieve accuracy better than random. Verzelen data came from single Gaussian or from mixture of two Gaussians. In Proposition 3 of their paper, they proved that for < & log( (P) max (1, A). any testing procedure is asymptotically powerless.
Castro (2017) studied hypothesis testing whether the
X
Note that for pd with a < 1, the lower bound derived Verzelen & Arias-Castme Castro (0177) has
similar form to ( with factor of 1 a, which is slightly smaller. Thus the bound in (5) is sharper.

---

2.2 Semi-Supervised Setting
In the SSL. case, the observed data consists of two subsets, one with L labeled samples and the other with n unlabeled ones. We now develop information-theorete and computational lower bounds for this setting. The information lower bound is based on the results in Section SL and UL settings. The computational lower bound relies on the low-degree likelihood hardness conjecture. Over the past 10 years, several authors studied problems. For the sparse Gaussian mixture 33) both Fan et al. (2018) and Löffler et al. (2022) derived such gaps in an UL setting. To the best of our knowledge, our work is amongst the first to explore computational-stainn -taatsssia gaps in SSL setting. Our analysis, described below, shows that with relatively few labeled samples, the computational statistical gap continues to hold. In contrast, we describe Section 3 with a sufficiently large number of labeled samples, but not enough so solve the problem using only the labeled set, the cmmputational-statsiiiiei gap is resolved. In particular, we present polynomial time SSL. algorithm that bridges this gap.
gaps for various high dimensional
Information Lower Bounds. Before presenting results for the mixture model 3 we analyze
more general case. We study the recovery of latent variable that belongs large finite set S, given measurements from two different modalities. Formally, the problem is to recover S from two independent sets of samples { and { of the following form,
(a. (a]
(2 (=(S))
Here, (x)))) and (=|S)) are known probability density functions. These functions encode infor- mation on S from the two types of measurements. In our SSL setting, æ represents an unlabeled sample, whereas
(z. y) a labeled one, and is the unknown support of μ.
Our goal is to derive information lower bounds for this problem. To this end, we assume that S is random variable uniformly distributed over a finite set S, and denote by Ia = [xx; S) and 1, = S2 the mutual information æ with S and of z with S, respectively, Further, recall a classical result in information theory that to recover S from N i.i.d. samples of æ, N must scale least linearly with log [S] A similar argument applies to z. For further details, see Scarlett & cetrmmation-hhoorette result for recovering from the above two sets of samples. Hence, it is applicable to other problems involving data fusion from multiple sources and may thus be of independent interest.
1s Cevher (2021). The following theorem states a general non-asymptotic
Theorem 2.3. Fix 8 E (0, 1). Let N, . be integers that satisfy max {N - Tu, M 12} < <1
5) log [S]. Let Ng = [gN] and Mg = 1(1 M)M for E [0, Then, any estimator S based on {xx ) and {2,] {zz}ş=1 satisfies
M4
log 2
P SS >
log S
This theorem implies that with any convex combination of samples from the two modalities, qN from the first and (1 (1-q) M) from the second, accurate recovery of S not possible if N and M are both too small. Essentially this follows from the additivity of mutual information.
Combining Theorem 2.3 with the proofs of Theorems and 2.2 yields the following information lower bound for the semi supervised case.
Corollary 2.4. Let DL and D,, be sets of L and n i.i.d. labeled and unlabeled samples from the p + 0, be such that
mixture model 33). Fix 8 E 10. 1). Let (La.no, no. p.k) + oo, with k
Lu 2(1 - 8)k log (p- - k + 1), no < 2(1 - 8)k
log (p - k + 1) max {1, A}.
X2
Suppose the number of labeled and unlabeled samples satisfy L. = [To)] and n = [(1 no for some 9 [0, 1]. Then, for any estimator S based DL U D',, as p
max P ($ 4 8 2 6.
5

---

Computational Lower Bounds. Our SSL computational lower bound is based on the low-degree framework, and its associated hardness conjecture (Hopkins & Steurer, 2017 Kunisky et al.) 2022). This framework was used to derive computational lower bounds for various unsupervised high dimensional problems including sparse-PCC PCA and sparse Gaussian mixture models (I (Lfffler al. 2022, [Schramm& & Wein 2022, Ding et al.) 2023). To the best of our knowledge, our work is the first to adapt this framework to a SSL setting.
For our paper to be self-contained, we first briefly describe this framework and its hardness conjecture. We then present its adaptation to our SSL setting. The low degree likelihood framework focuses on unsupervised detection problems, specifically the ability to distinguish between two distributions P and Q, given i.i.d. samples. Specifically, denote the null distribution of n samples by Qn. whereby all 2, ~ Q and denote by P., the alternative distribution, with all æ; ~ I..
Under the low-degree framework, one analyzes how well can the distributions P. and Qn be distinguished by a low-degree multivariate polynomial f TRxx - R. The idea is to construct polynomial f which attains large values for data from I", and small values for data from Q.. Specifically, the following metric plays key role in this framework,
Ex-P, [f(x))
| || = max
dog(f) VEx-C. [f(X)²)
where the maximum is over polynomials f of degree at most The value | characterizes how well degree- D polynomials can distinguish P,, from Q.. If || 011,, then P,, and Q. cannot be distinguished via degree-D polynomial. Computational hardness results that use the low-degree framework are based on the following conjecture, which we here state informally, and refer the reader to Löffler et al. (2022) for its precise statement.
Conjecture 2.5 (Informal). Let Qn and P,, be two distinet distributions. Suppose that there exists D (log(pn)) for which ||C remains bounded as p cc. Then, there is polynomial-time test T R
+ (0, 1} that satisfies
Ex<P, [XX)]+Xxxx [1- (x)] o(1)
In simple words, Conjecture 2.5 states that || distinguish between In, and Qu using a polynomial-time algorithm, as no test has both a low false alarm as well as low mis-detection rate (the two terms in the equation above).
as as co, then is not possible to
We now show how to extend this framework, focused on unsupervised detection, to our SSL setting. To this end, consider + n samples, distributed according to either a null distribution Qr+n or an alternative distribution I' Ltn. In our case, the null distribution is
Qlen
C; = & ~ (0, Ip), E [L + n|],
(8)
whereas the alternative belongs to the following set of distributions,
c; S1a E.r i [4)
FLtn:
(9)
ax; y:p Ei, L<is +
Here, S is uniformly distributed over S. n²( - Villie S}. and unobserved Rademacher random variables.
The next theorem presents a low-degree bound for our SSL testing problem. The scalings of L, n and k with p and are motivated by those appearing in Theorems 2.1 and 2.2
Theorem 2.6. Let = [eip"]
28k X
log(p - k)), n = Loz and D ()og for some
8, 7, X, C, 02 E R and a E (0, 1). With the null and alternative distributions defined in 8 and 9
B < 1 and < 2, then as p +
| I. =
Theorem 2.6 together with the hardness conjecture 2.5 extendss to the SSL case previous computational lower bounds that were derived only in UL settings (B = 0) (Fan et al. 2018: Löffler al. 2022). Next, we make several remarks regarding the theorem.

---

SSL statistical comppiaaioooottiiiooooallll gap. In the rectangular region 3 < and 1 < < 2. depicted in orange in Figure !I under the hardness conjecture 2.5 distinguishing between IP and Q is computationally hard. Since testing is easier than variable selection and classification (Verzelen & Fan et al.) 2018), in this region these tasks are computationally hard as well.
Arias-Castro 2017
Tightness of condition < 2 in Theorem 2.6 This condition is sharp, since for Y 2 2, namely A2 2 x2, the support can be recovered by a polynomial-ting algorithm, such thresholding the covariance matrix followed by PCA, see Deshpande & Montanari (2014) and Krauthgamer et al. (2015).
Tightness of condition < - a. This condition is tight for detection, though not necessarily for feature selection or classification. The reason that for 3 > - a, it is possible to distinguish between I and Q using only the labeled data (Ingster 1997 Donoho & Jin 2004).
Combining Theorems 2.1 2.6 leaves a rectangular region < < SSL support recovery Is reasible from an information view, but we do not know if it possible in computationally efficient manner. the next section we present a polynomial time SSL method that in part of this rectangle, depicted in blue in Figure is guaranteed to recover S and construct an accurate classifier. We conclude with the following conjecture regarding the remaining white region: Conjecture 2.7. Let Dr,, D,, be sets of I. and n. i.i.d. labeled and unlabeled samples from the model K" 3 Assume, as in Theorem 2.6 that 1e x p", L = | 2.3k log(p k) and n x Xa Then in the white region depicted in Figure I no polynomial-tine tirtee algorithm is able to recover the support S to construct an accurate classifier.
and 3-0- < 3 < where
3 Semi-Supervised Learning Scheme
We present a SSL scheme, denoted LSPCA, for the model (2. that is simple and has polynomial runtime. In subsection 3.2 we prove that in the blue region of Figure recovers the support, and thus constructs an accurate classifier. In this region, under the hardness conjecture 2.5] computationally efficient algorithms that rely solely on either labeled or unlabeled data would fail.
Preliminaries. To motivate the derivation of LSPCA, we first briefly review some properties of the sparse model (2) First, note that the covariance matrix of x is Σx = 1 Apuup + Ip. This is a rank-one spiked covariance model, whose leading cigenvector is Au, up + sign. Hence, with enough unlabeled data, Ap can be estimated by vanilla PCA on the sample covariance or by some sparse-PCA procedure taking advantage of the sparsity of Ap.. Unfortunately, in high dimensions with limited number of samples, these procedures may output quite inaccurate estimates, see for example Nadler (2008); BBirbbum et al. (2013). The main idea of our approach to run these procedures after an initial variable screening step that uses the labeled data to reduce the dimension.
3.1 The LSPCA Scheme
Our SSL scheme, denoted LSPCA, stands for Label Screening PCA. As described in Algorithm 1, LSPCA has two input parameters: the sparsity & and a variable screening factor 3 < 1. The scheme consists of two main steps: (i) removal of noise variables using the labeled samples; (ii) support estimation from the remaining variables using the unlabeled samples via PCA. Finally, a linear classifier is constructed via the leading eigenvector of the covariance matrix the estimated support.
The first stage screens variables using only the labeled samples. While our setting different, this stage is similar in spirit to Sure Independence Screening (SIS), which was developed for high- dimensional regression (Fan & Lv 2008). To this end, our scheme first constructs the vector,
WL
x
1
Σ C 0y==1
(10)
L+
iyy=1
where I.- = 1( [Z]] V: 1} and --= = I
L.p With balanced mixture P(Y = +1) 1.1 it follows that wT z Ap 2. N( I,). Hence, wt be viewed as noisy estimate of Aμe. If the number of labeled samples were large enough, then the top k coordinates of w, would coincide with the support of Aμ. With few labeled samples, while not necessarily the top-k, the entries of wz at
VI.
7

---

Algorithm LSPCA
Input: Dr = (( 1:)) D,, (ax) parameters k,
Step I: Labeled Data
Compute wt via Eq. (10)
Select its top p== entries, denoted by St
Step II: Unlabeled Data
Compute the sample covariance Els, by Eq.
Compute leading cigenvector VPCa of Di 9t.
Set S to be the top k entries of |vPCAl Compute leading eigenvector V of Eig Output: Estimated support S, and vector V.
the support indices still have relative large magnitudes. Given the input parameter 3 > 0, the scheme retains the indices that correspond to the largest p² p' entries in absolute value of w.. We denote this set by St. Note that for any B > O, this step significantly reduces the dimension (as 8 > 0 then p² pl < p). In addition, as analyzed theoretically in the next section, for some parameter regimes, this step retains in Sy. (nearly all of) the k support indices. These two properties are essential for the success of the second stage, which now describe.
The second step estimates the support using the unlabeled data. Specifically, LSPCA constructs the sample covariance matrix restricted to the set St.
El..
Σ 72 i=L+1
1
n+L
(a.
Is)s (2. 0)15
(11)
R where क 21=--1 H; is the empirical mean of the unlabeled data. Next, it computes the leading eigenvector VPCA of Els-- The output support set Ô consists of & indices VPCa with largest magnitude. Finally, the vector Ap is (up to scaling) estimated by the leading eigenvector of Σ restricted to Š, with its sign determined by the labeled data.
Remark 3.1. After the removal of variables in the first step, the input dimension to the second step is much lower, ò p Despite this reduction in dimension, as long as the vector Aμ is sufficiently sparse with k < p. or equivalently sparse eigenvector. Hence, instead of vanilla PCA, we may replace the second step by any suitable (polynomial time) sparse-PCA. procedure. We refer to this approach LSPPCA (Labeled Screening Sparse-PCA). As illustrated the simulations, for finite sample sizes, this can lead to improved support recovery and lower classification errors.
1 B, then in the second step goal is still find
3.2 Support Recovery and Classification Guarantees for LSPCA
Before presenting our main result, we first recall two standard evaluation metrics. The classification error of classifier C' IRP + {+1} is defined as R(C) = (P(((())) # v). Its excess risk is defined as
E(C) R(C) R = R(C)) - inf R(C").
(12)
C
As Verzelen & Arias Arias-Castro 2017). the accuracy of support estimate S defined by its normalized overlap with the true support, namely 1Š Sl To simplify the analysis, we focus on the symmetric setting where μn = - μ.. The next theorem presents theoretical guarantees for LSPCA, in terms of support recovery and the excess risk of the corresponding classifier.
Theorem 3.2. Let DL, Dn be labeled and unlabeled sets of L and i.i.d. samples from (3) with k- sparse whose non-zero entries are / Suppose that k [cIp" J, L 22k log(p - k)] n
102 J. for some fixed 0 < a < 1 1/2,0 3 < ax, > and X, C1 02 E RR.. Let S, be the
output of Algorithm I with input k and screening factor B. 1f 3 > 1 - 1- and 3 E (1 ya, B), then
lim P D-000
S
-e) 1, Ve > 0,
(13)
8

---

and the excess risk of the corresponding classifier ((x) -iignV, x) satisfies
lim {(C) = 0.
(14)
p0000
The interesting region where Theorem 3.2 provides a non-trivial recovery guarantee is the triangle depicted in blue Figure Indeed, in this region, LSPCA recovers the support and constructs an accurate classifier. In contrast. any SL algorithm would fail, and under the low degree hardness conjecture, any computationally efficient UL scheme would fail as well. To the best of our knowl- edge, our work is the first to rigorously prove the computational benefits of SSL, in bridging the compurationall-satiittnn
gap in high dimensions. As mentioned above, we conjecture that in the remaining white region in Figure T it is not possible to construct in polynomial time accurate SSL classifier. The intuition underlying this conjecture is based on the work of Donoho & Jin (2004), where in the fully supervised (SL) setting, the authors show that there is defection-recovery gap. Namely for a range of number of labeled samples, it is possible to detect that a sparse signal is present, but it is not possible reliably recover its support. Intuitively, adding few unlabeled samples should not resolve this gap.
4 Simulation Results
We illustrate via several simulations some of our theoretical findings. Specifically, we compare LSPCA and LS'PCA to various SL, UL and SSL schemes, in terms of both accuracy of support recovery and classification error. The sparse PCA method used in LS²PCA was iteratively proxy update (IPU) Tian et al. 2020 We generate L + n labeled and unlabeled samples according to the model 3 with a k-sparse l whose non-zero entries are ///k. The quality of a support estimate is measured by
its normalized accuracy |8 n S1/k. For all methods compared assume the sparsity A is known. Hence, each method outputs a k k-sparse unit norm vector p., so its corresponding linear classifier is sign (ft, a:) Given the model 3 its generalization error is ( 14)) We our SSL schemes with / 3 (3 -1)) which satisfies the requirements of Theorem 3.2 We present experiments with p 10 k p
100 and À = 3, though the behavior is simila ar for other settings as well. The error of the Bayes classifier is 4 (V(A) z 0.042. We report the average (with 11 standard deviation) of the support recovery accuracy and the classification error over M 50 random realizations. All experiments were run on a Intel i7 CPU 2.10 GHz.
We empirically evaluate the benefit of L 200 labeled samples in addition compare our SSL schemes LSPCA and PSP to the following UL methods, taking all L L+ n samples as unlabeled: ASPCA (Birnbaum al. 2013), and IPU TTan al. 2020). The SSL methods that we compare are LSDF (Zhao et al.) 2008). and self-training (self-train). The self-training algorithm similar to the approach in Oymak & Guleu (021), but explicitly accounts for the known sparsity k: (i) compute w of (IO) using the labeled samples, and keep its k largest entries, denote the result by (k). w ; (ii) compute the dot products c; (wl (k) .x,) and the pseudo labels O sign(c;); ; (iii) let nair be the cardinality of the set {i: |c|| > r}, for some threshold value 2 O: (iv) estimate the support
unlabeled ones. We
by the top-k coordinates in absolute value of the following vector:
Ltn
Σ yaa +
Σ 1(la) T)gm: i=L+1
Wself
L + Bell
In the experiments we used I = 0.8, which gave the best performance. Also, we implemented the SL scheme Top-K Labeled that selects the indices of the top-k entries of |w,,] of (10). As shown in the supplementary, this is the maximum-likelihon
estimator for S based on the labeled data.
Figure iillustrates our key theoretical result- that in certain cases SSL can yield accurate classification and feature selection where SL and UL simultancously fail. The left panel of Figure 2 shows the average accuracies of support estimation for the different schemes as function of number of unlabeled samples n. Except at small values of n, LS² achieved the best accuracy out of all methods compared. The right panel shows the classification errors of the different methods. The black horizontal line is the error of the Bayes optimal (Oracle) classifier. As seen in the figure, our SSL schemes come close to the Bayes enror while SL and UL schemes have much higher errors.
We present further experiments that empirically illustrate the benefit of using a fixed number of = 1000 unlabeled samples while varying the number of labeled samples L. Specifically,

---

1.0
0.8
classification ervor
0.4
accuracy
0.6
0.3
0.2
0.1
0.0
0.0
1500
500
1000
1500
LSPCA
Se.Ftrain
Top labeled
IPU
LS'PCA
LSDF
ASPCA
Oracle
Figure 2: Empirical simulation results. (Left) Support recovery, (Right) Classification error.
1.0
0.8
classification error
0.4
accuracy
0.6
0.3
9.4
0.2
0.2
0.1
0.0
0.0
100
200
300
400
500
600
700
100
200
300
400
500
600
700
L
LSPCA
LS*PCA
Self-train
LSDF
Top k labeled
Oracle
Figure 3: Empirical simulation results. (Left) Support recovery, (Right) Classification error.
compare our SSL algorithms LSPCA and LS²PCA to the SSL methods self -train and LSDF, as well as to the SL scheme Top-K Labeled, which uses only the L labeled samples. Figure iillustrate the support recovery accuracies and the classification error as function of the number of labeled samples L. As seen in the figure, adding n 1000 unlabeled samples significantly improves the classification and support recovery accuracies.
Summary and Discussion
In this work, analyzed classification of mixture of two Gaussians in sparse high dimensional setting. Our analysis highlighted provable computational benefits of SSL. Two notable limitations of our work that studied mixture of only two components, both of which spherical Gaussians. It is thus of interest to extend our analysis to more components and to other distributions.
From broader perspective, many SSL methods for feature selection have been proposed and shown empirically to beneficial, see for example the review by (Sheikhpour et al. 2017). An interesting open problem is to theoretically prove their benefits, over purely SL or UL. In particular it would be interesting to find cases where SSI. improves over both SI. and UL in error rates, not only computationally.
10

---

Acknowledgements
The research of B.N. was partially supported by ISF grant 2362/22. B.N. is an incumbent of the William Petschek professorial chair of mathematics. We thank Gil Kur and Jonathan Weed for interesting discussions. We also thank the anonymous reviewers for their valuable feedback that improved the quality of our manuscript.
References
Amini, A. A. and Wainwright, M. J. High-dimensional analysis of semidefinite relaxations for sparse principal components. Annals Statistics, 37(5B):2877 2921, 2009.
Azizyan, M., Singh, A., and Wasserman, L.. Minimax theory for nigh-dimensional Gaussian mixtures with sparse mean separation. Advances in Neural Information Processing Systems, 26, 2013.
Ben-David, S., Lu, T., and Pál. D. Does unlabeled data provably help? worst-case analysis of the sample complexity of supervupe learning. In COLT, pp. 33-44, 2008.
Birnbaum, A., Johnstone, I. M., Nadler, B., and Paul, D. Minimax bounds for sparse pea with noisy high-dimensional data. Annals Statistics, 1163):1055-1084 2013.
Chapelle, O., Schölkopf, B., and Zien, A. Semi-Supervised Learning. MIT press, 2006.
Chernoff, Measure of Asymptotic Efficiency for Tests Hypothesis Based on the sum of Observations. Annals of Mathematical Statistics, 23(4):493 -077, 1952.
Cover, T. M. and Thomas, J. A. Elements of Information Theory (Second Edition). Wiley-Interscience, 2006.
Deshpande, Y. and Montanari, A. Sparse pea via covariance thresholding. Advances in Neural Information Processing Systems, 27, 2014.
Ding, Y., Kunisky, D., Wein, A. S., and Bandeira, A. S. Subexponential-time algorithms for sparse pea. Foundations of Computational Mathematics, pp. 1-50, 2023.
Donoho, D. and Jin, J. Higher criticism for detecting sparse heterogeneous mixtures. Annals of Statistics, 32(3):962 994, 2004.
Fan, and Lv, Sure Independence Screening for Ultrahigh Dimensional Feature Space. Journal of the Royal Statistical Society Series B: Statistical Methodology, 70(5):849-99 -911,1111111111111111 2008.
Fan, J., Liu, H., Wang. Z., and Yang, Z. Curse of heterogeneity: Computational barriers in sparse mixture models and phase retrieval. arXiv preprint arXiv: 1808. 00988. 2018
Hopkins, S. B. and Steurer, D. Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. 2017 IEEE 58th Annual Symposium Foundations of Computer Science (FOCS), pp. 379-390, 2017.
Ingster, Y. I. Some problems of hypothesis testing leading to infinitely divisible distributions. Math.
Methods Statist., 6(1):47-69) 1997.
Jin, Impossibility of successful classification when useful features are rare and weak. Proceedings of the National Academy of Sciences, (06(22):8859-886) 2009.
Jin, J. and Wang, W. Influential features PCA for high dimensional clustering. Annals of Statistics, 44(6):2323 2359, 2016.
Johnson, N. L., Kemp, A. W., and Kotz, S. Univariate discrete distributions, volume 444, John Wiley & Sons, 2005.
Johnstone, I. M. On Minimax Estimation of a Sparse Normal Mean Vector. Annals of Statistics, 22 (1):271 289, 1994.
Johnstone, I. M. Function estimation and Gaussian sequence models. Unpublished, 2002.

---

Krauthgamer, R., Nadler, B., and Vilenchik, D. Do semidefiite relaxations solve sparse PCA up to the information limit? Annals of Statistics, 43(3):1300-1333 1322, 2015.
Kunisky, D., Wein, A. S., and Bandeira,
Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio. In Cerejeiras, P. and Reissig, M. (eds.), Mathematical Analysis, its Applications and Computation, pp. 1-50. Springer, 2022.
Li, T., Yi, X., Caramanis, C., and Ravikumar, P. Minimax Gaussian classification & clustering. In Artificial Intelligence and Statistics, pp. 1-9. PMLR, 2017.
Löffler, M., Wein, A. S., and Bandeira, S. Computationally efficient sparse clustering, Information and Inference: A Journal of the IMA, 11(4):2255-1266 2022.
Nadler, B. Finite sample approximation results for principal component analysis: A matrix perturba- tion approach. Annals of Statistics, 36(6):2711-2817 2008.
Oymak, S. and Gulcu, T. C. A theoretical characterization of semi-supervised learning with self- training for Gaussian mixture models. In International Conference Artificial Intelligence and Statistics, pp. 3601-3609, 2021.
Rigollet, P. Generalization error bounds in semi-supervised classification under the cluster assumption. Journal of Machine Learning Research, 8(7), 2007.
Scarlett, J. and Cevher, V. An introductory guide Fano's inequality with applications in statistical estimation. In Rodrigues, M. R. D. and Eldar, Y. C. (eds.), Information-Theoreii Methods in Data Science, pp. 187-528. Cambridge University Press, 2021.
Schramm, T. and Wein, A. Computational barriers to estimation from low-degree polynomials. Annals of Statistics, 1833-188838888 2022.
Sheikhpour, R., Sarram, M. A.. Gharaghani, S., and Chahooki, M. A. Z. A survey sumi-supervised feature selection methods. Pattern Recognition, 64:141-158, 2017.
Singh, A., Nowak, R., and Zhu, J. Unlabeled data: Now it helps, now it doesn't. Advances in neural information processing systems, 21, 2008.
Tian, L., Nie, Wang, R., and Li, X. Learning feature sparse principal subspace. Advances in neural information processing systems, 33: 33:14997-15008 2020.
Tifrea, A., Yüce, G., Sanyal, A., and Yang. F. Can semi-supervised learning use all the data effectively? lower bound perspective. In l'hirty-svventh Conference on Neural Information Processing Systems, 2023.
Verzelen, N. and of Statistics, 1900-1999, 2017.
E. Detection and feature selection in sparse mixture models. Annals
Wu, Y. and Zhou, H. H. Randomly initialized EM algorithm for two-component Gaussian mixture achieves near optimality in ((v)) iterations. Mathematical Statistics and Learning, 4(3), 2021.
Yang, Y. and Barron, A. coermatiio-thhoreetie determination of minimax rates of convergence. Annals of Statistics, 11111564-1999 1999.
Zhao, J., Lu, K., and He, X. Locality sensitive semi-supervised feature selection. Neurocomputing, 11410-12) 2008
Zhu, X. and Goldberg, A. B. Introduction to semi-supervised learning. Morgan & Claypool Publishers, 2009.
12

---

A Auxiliary Lemmas
We first present several auxiliary lemmas used to prove our theorems. We denote the complement of the standard normal cumulative distribution function by (t(1) = P (Z > t), where Z ~ (0, 1). The following lemma states well known upper bound on 4p.
Lemma A.1. For any >> 1,
(1) S
1/12
(15)
2
Lemma A.2 (Chernoff 1952
Suppose {aili= are ii.d Bernoulli random variables, with Pr[m, 1] q. Let X denote their sum. Then, for any 8 2 0.
22ng 248
PXX (1+001m)) Se
(16)
for any 8 E [0,1]
P(X (1-5)nq) Se Aqg
(17)
A common approach to prove lower bounds is using Fano's 's inequality, Here, we use the following version of Fano's lemma, see Yang Barron (1999).
Lemma A.3. Let 0 be random variable uniformly distributed over a finite set Q Let #1, 2...... An be ii.dd samples from density f (z]0). Then, for any estimator 0(2), Zn) O
P (0 + 0) 21 1
I(0; Z") + log
(18)
log
where T(0; ?²) is the mutual information between 0 and the samples n = (21, 22, zn).
In our proofs we use several well known properties of the entropy function. For convenience we here state some of them. First, recall the explicit expression for the entropy of a multivariate Gaussian. Lemma A.4. Let x ~ Nu, E). Then, its entropy is given by
H(x) (11 + log(2 + log logd).(E).
(19)
Next, the following lemma states that the multivariate Gaussian distribution maximizes the entropy over continuous distributions with the same covariance (Cover & Thomas 2006 pg. 254).
Lemma A.S. Let be a continuous random variable with mean μ R2 and covariance E E IR2*P and let y ~ N(, E). If the support of x is all of IRP then
H(x) S H
(20)
The next lemma states the sub-additive property of the entropy function. Lemma A.6. Let x and be jointly distributed random variables. Then,
H(x,y) y) S H(x) + H
(21)
To prove Theorem 2.2 we use the following lemma.
Lemma A.7. Ler X E 10, and let k be positive integer. Then, for w ~ N(0, k-1)
E tanh(A + VXw) 1
tanh? (2 v s (2+3V
1
(22)
Proof of Lemma A.7 Let q(w) = tanh + Vaw) - tanh 2 + /ww. In terms of g(w), the left
hand side of (2 may be written follows
E tanh(A + vxw)=
tanh2 (* + vxu)
E
(tanh(A + v.w] + E (((ww)) (23)
2
2
13

---

We now upper bound the two terms in the RHS of (23). We start by showing that E [q(w)] S ///k. Let L wE [w(] be the Lipschitz constant of the function q(w). It is easy show that
bg S 3v.. Let 2 ~ NO, 1) be independent of w. Using the first order Taylor expansion yields
Eu,, 9 (w) 1 w + 1
Lu
Ez |=||| = 3
33
(24)
Vk"
Next, note that (w + 2) N(0, 1). Therefore
1
)
12
9
w
g(v)
dv
Vk
22T
e-0812
(aanb(A (A + vAv) tanh + vXu)
du.
22
Making a change of variables x = X + Vv, gives
Rnoz q (w +122 L (tanh(x) - (x)) (anh?))
)
dr.
Vk
V2TAA
Define tx(x) (tanh(x) tanh 2 (z)) (0-AA1/22A Note that tx (z) is an absolutely integrable
VenA
function which satisfies (x() = - (-(x) for any X. Therefore, the above integral is equal to zero, namely I_ (x())d = O. Inserting this into 24 gives
Ew (q (w)) S 3/A/k.
(25)
Next, we upper bound the first term on the RHS of Eq. (33 Denote by fw (w) the probability density function w ~ NO, ) Then, writing the expectation explicitly gives
E
tanh(A (A + v.w)]
tanh(A + vXw) (w))f(()dd)
Making the change of variables x = X + v /vw yields
E taanh(A (A + VXwo)] = Vx
tanh(x)fw
2-d V2
dx
(x) ffw
B-d - fw
2+1 dx.
0. for all x 2 0. Therefore, bound this expectation it suffices to construct function g(x) such that g(x) > tanh(x) for any > 0 and for which we can compute explicitly the corresponding integral. Consider the function g(x) = r. is well-known that x 2 tanh(x), for all x 2 0. Thus,
Since À 0, it follows that fw
Sw
vX
1 // (Jw (5x²) fw (xt) dr VX
E (A v.w]] =
xfw
x dr
v
Substituting w (x \)/ VX, yields
E tanh(A + vxw) L (A + Vuu)fw = =E A vXw =
(26)
Combining 23 235 and 26 gives
tanh(A + vdw) tanh? vxw) s (A+3v///))
14

---

Lemma A.8. Consider sequence of classification problem of the form, ~ Unif(+1)) x ~ Nyyu,,I,;
where the dimension p - but || vX is fixed. Let Pbp be sequence of unit norm estimators and (x)x) = sign(βt, ②) the corresponding classifier. Assume that every > 0
lim P((p/VA, Ap) =1-)==1 p-020
(27)
Then, the excess risk of the classifier T,((r) sign at) tends zero as p tends infinity.
Proof. By definition, the excess risk of the classifier Tр that corresponds to Pp can be written as
{Tp)) = PP (Pp i + E) < 0) - (V(
Since & is independent of üy and P, has unit norm, then 2 = (pp. E) ~ NO 1), and the excess risk may be written as
E(T)) = P(= > (Ap. 1)) 4- (V
Let > 0, and consider the event A. 1///V,, (p))
c). Then,
E(T,) S { 45 (-(4(( - 6))
(V(x) with probability P(A.)
1
with probability 1 P(A.)
Since by assumption P(Ac) - for any 0, then the excess risk tends to zero as p - 00.
B Lower Bounds Proofs of Results in Section 2
B.1 Proof of Theorem 2.1
Our proof relies on Fano's inequality, and is conceptually similar to the proof of Theorem in Amini Wainwright 2009). First, note that for any sub-collection $ C S, we have the following
max IP (
$ s).
SES
S
SE3
The right hand side in the above display is the error probability of an estimator ò, where S is considered as random variable uniformly distributed over the set S. In other words, the right hand side may be written as follows,
(error) Σ P (S
( s s|S= P(S
.
In our proof, consider the following sub-collection
$ =
L.., T}.
(28)
which consists of all k-element subsets that contain the first l support indices {1...., Ac 1} and one from (k: (k....,pp) To lower bound the probability of error, we focus on a specific class of
means: given the support S, the mean entries have the form Hy = / ati S}. So, with S known,
is deterministic and we write as S
In the proof we consider an equivalent model of 3 whose observations are divided by vă,
c; = 0:05 + a i I,
where 0²(]) V 1 0)
1 and & NO I.). Since for each observation æ; also know corresponding label y/ E (-1, 1}. we may consider the following transformed observations
म; = y. = 0 + - i == ==1... 1.....a
(29)
15

---

where E: = Bi has the same distribution as &. Denote by X",X', Y the sets of L i.i.d samples (ar)/=1: { ;=1 and {y: - respectively. To apply Fano's lemma, we consider the joint mutual information ((X², y "); S). Note that,
= -s)
1
where the last equality follows from the fact that the labels Y are independent of the support S and the observations X Hence, it is enough to consider the samples X² from the model in (2))
Let be a subset chosen uniformly at random from S. Then, from Lemma A.3
follows that
P (error) 2 1 I(X":)) 5) + log = log(p k 1)
1 5) + log
(30)
log [
We now derive an upper bound on I(X4; First, from the relation between mutual information and conditional entropy, S) = _(+*) - (S)) By the sub-additivity of the entropy function H(X²) S LH) Also, since the samples 2; are conditionally independent given S, the joint entropy H(* can be expressed as
H(X = Σ
H( (a)s))
VE[L]
where ë is single observation from the model
29 Therefore,
1(8 L (H)))) - (+])))
(31)
By the definition of conditional entropy,
( = Σ P(S (#1S) (f f()lS)da,
where [(a the probability density function of single random sample z given S. For any S E $ the vector ( (S) is a p-dimensional Gaussian with mean 0 and covariance matrix I Its entropy
is independent of its mean, and is given by E (1 + log(2ma²)). Hence,
H ()ls)) (1 + log(2x) + log(o²))
(32)
The final step is to upper bound (.)) To this end, note that w is distributed as a mixture of (p k+ Gaussians, each centered at 0 for S E S. Let us denote its mean and covariance by Vn EE [ and Σ = [( - (# =²2²T respectively. By the maximum entropy property of the Gaussian distribution (Lemma A.5 and Eq. (19) for the entropy of multivariate Gaussian, we have
H()) S H(N(,,, E))
P (1 + log(2r)) + log det (E).
(33)
2
Combining
31
32
and
33
gives
1(84:5) < (log del((e))))))) p (2)g))).
(34)
The following lemma, proved in Appendix D provides an upper bound for log det
Lemma B.1. Let E, be the covariance matrix of the random vector of Eq. 29
with the S
uniformly distributed on S of Eq. 28 Then,
1
)
log det (E) S p
(p- 1) 1+
(35)
k(p k + 1)02
Substituting this upper bound into (34 leads to
I 1 1s l)log log 1 k(p k + 1)02
1
L
LA
I(x+:5
5
(36)
2ko
2k
where the last inequality follows from log(1 + z) < x. for all
0.
Inserting
36
into 30
implies that sufficient condition for the error probability to be greater than 8
log 2
log (P
k+
LA 2(1 - 5) k + 1), which completes the proof.
16

---

B.2 Proof of Theorem 2.2
To prove Theorem 2.2 we use the following lemma, proven in Appendix D
Lemma B.2. Let be random vector from the model (3) with vector μ where the random variable S is uniformly distributed over the set $ of Eq. (28). and let I(x; be their mutual
information. Consider an asymptotic setting where p - do and k/p + cc. Then, for X < L. and for p and k sufficiently large with k/p sufficiently small
1 1
T(a; 5) - (1 o()).
(37)
First, note that for 2 1, the information lower bounds proven in Theorem 2.1 and those we aim to prove in Theorem 2.2 coincide. Clearly, Theorem 2.1 which considers all possible estimators based on ((z;, y:)] includes in particular all unsupervised estimators that ignore the labels. Hence, for A A 1, Theorem 2.2 follows from Theorem 2.1 Therefore, we consider the case
The proof, similar to that of Theorem 1, is also based on Fano's inequality. To lower bound the probability of error, we view as subset uniformly distributed over S, where is the sub-collection of support sets defined in (28). Then, using the same arguments in the proof of Theorem
1
2 1(X"; S) + log
max P (8 SES
Σ PP
+
(38)
log [$]
SEa
where X" = vn) and 1(x"; S) is the mutual information between the n unlabeled samples and S.
We now derive an upper bound for IX";; 5). The sub-additivity of the entropy function, and the fact that xi are conditionally independent given S imply
1(X"; S (H (x) - H (x) = no (x;
(39)
where x single sample from the model 3). Hence, for p and sufficiently large, with k/p sufficiently small, combining (37) and 39
gives :) < a\²
o(1). By Fano's bound in X² log(p - + +1).
26 (1 o(1)).
388 the error probability is at least if < 2(1-8)k
B.3 Proof of Theorem
Recall that the random variable S is uniformly distributed over the set S. For X = (x,) No and MM. { their combined mutual information with the random variable S is
T(XN., 7 MM; H(X* ,,M,) H 2 (S).
Since the two sets of samples { ررك Mr are conditionally independent given = 8, then
T(X~., Zdl;; S) -H(X ZMH.) - H(X* H(ZM.1s)
= =x ZMo) - N. Hxr()) MzHH(zlS).
(40)
By the sub-additivity property of the entropy function.
H(X No My) < "') Mu) S NoH(2) MaH(2).
(41)
Hence, combining 44 and
yields
T(XN=, 7 M S) S No Ta + M. Tz.
(42)
Combining Fano's inequality with the upper bound in (42 gives
P ($ ( $ 5) > No 1 + Ma 1. + log 2
log [S]
Finally, the assumption max(N- In. M 12) (1 8) log [S] yields that P ($ (
log log [S]
17

---

B.4 Proof of Corollary 2.4
To lower bound the error probability, we view S as a random variable uniformly distributed over the discrete set defined in (28). By the same arguments as the proofs of Theorems and 2,
$ ( 2 P swUis) ( (5
max SEB
We apply Theorem 2.3 with the æ; of i.i.d. unlabeled samples from 3 and the second set = (2 31) of i.i.d. labeled samples from model (3)
Next, in the proof' of Theorems 2.1 and 2.2
the following upper bounds for L and La were derived,
X
1 2k'
min min(1, A1 o()).
(43)
2k
Finally, by the conditions of the Corollary, the number of labeled and unlabeled samples isfy L = LgLoo] and n = [(1 g)moj, with Lo 201 log (p + 1) and vi <
2(1-6kk log (p + 1) max (1, AJ. Hence, for sufficient large p. combining these conditions with
gives
Lo I,, no La < (1 log(p - k + 1)
Therefore, by Theorem 2.3 the error probability is at least
B.5 Proof of Theorem 2.6
Even though we analyze a SSL setting, the observed data still belongs to the additive Gaussian noise model (see Section 2 in Kumisky et al. (2022)). This key point allows to simplify the low-degree norm in our setting. Specifically, let = (Z....., *L+n) be the following set of random vectors, which are the noise-free underlying signals from the alternative FL+n of Eq. (9) in the main text,
n ie [4] y.pu -<is
In the equation above, S is uniformly distributed on S (the set of all size-k subsets over variables), S is a k-sparse vector with support S and non-zero entries /A/k and are Rademacher random variables. Similarly, let Ż (ž) (....... ..... kr.n) be an independent set of the underlying noise-free signals, with possibly different support S, and independent labels ÿt- Then, by Theorem I in Kunisky et al. (2022) the low degree norm ||C
Lta 112 can be expressed as
)
| =1/==EE2.222
Σ d!
Σ 22 (2..2.))
2,)
d=0
Inserting the expressions for z; and 2; into the equation above, gives
D Σ d=o
Ltx
(yate Drpe )
C
E
Σ u HS)
+ Σ Tm
d!
where the expectation over the two random sets S. Š and over the random labels ys and Dr- Since all these random variables are independent, the right hand side above simplifies to
E
L (u(u,,
+
Σ
yeTh
us ..
d!
d=0
L+1
l++
))
E
L
Σ
d!
d=n
i= L+1
18

---

Denote R, = yr and note that RG are Rademacher random variables, independent of S and S. Thus, the expectation above can be factored into the product of two separate expectations,
D 1 Σ
Kno 11
(1+
[++I
L+n
||
12
S
B(Bsbs
R
(44)
di
d=0
==++1
We now separately analyze each of these two expectations, starting from the second one. By the Binomial formula,
L
E
L
Σ
Ra
Σ
L
EE E
Σ
R
1=L-1
t=0
1==+1
Note that for any odd integer the f-th moment of the Rademacher's sum zero. Therefore,
I++
[d/2]
d
L+z Σ
2
E
L+
Ra
Id-
28
E
Ra
28
A=
L++1
i=L+1
As analyzed in Löffler et al.
22022
pg. 1274)
L+n
28
E
Ra
I n (2f 1)1!,
Tot1
where (2l 1)!! = (2 1)(2( - ......3..... 3.1
(28) 2 Thus,
4/2
[d/2]
E
L
+
Ri
< Ld
d!
L
d
d
n
(d - E)!
(d 28)! E!
212
21.2
(d 26)!
i= ++1
t=
8=0
Since (d- (2 (2-2
(d 8) ... ...(d- 28 + 1) s d',
then
Ltn
47
|d/2|
E
L
Ri
S Ld
Σ
(=++
8=
< 1
2
nd
= I.d (1
+
nd )a 212
T +
nd
2L
d
(45)
t=
Next, we analyze the first expectation Es, (4x $1 in
Recall that p3 V Ati e S}.
Hence, (ns), )وس n 8). Denote by G S the size of the overlap between the sets. Then G is hypergeometric random variable with the following probability distribution, for 0 I m S k,
(()
( p - A m k
P(G = m)
m
From (Johnson et al.
2005
pg.268) this probability is upper bounded as follows
A: k
IP(G m) S
m
p
Therefore,
Es,3 ( 1 1
d kd
E
IS
3/d
d IPG
m)
<
X
m
k
k
kd
kdd
m
p
m=0
m==0
(46)
Inserting 45 and 46 into 44
gives
|C 2
A
L +
nd)
d &
Σ md
( kk) (=))
(
k
dlkd
2L
m
p - le
d=0
m=0
19

---

In the above expression, since d < D, we may upper bound nd/2L by nD/2L. Furthermore, changing the order of summation between the two sums above, gives
k
LA
RAD
d
| 11
711
m
k
2Lk
mm0
d=0
k
k
m
LA
nAD
exp
m
p
k
2Lk
m=0
According to the conditions of the Theorem, I.
28k log(p k)] and n = L x for some (2 > 0
and 7 < 2. Hence, for sufficiently large p, L log(p E). Then, inserting these values into the above gives
3k:
1
Σ
k
m
c2k 23 20log( k)) + 2Bh2 log(p k:)
exp
m
k
mm0
Setting D (log(p- - k))), yields
|| 1 S
h
m log(p - k) 2/ + C2
exp
23 k2-7
m=0
Since 7 < 2, for any fixed > it follows that
I E for sufficiently large k. Therefore 2
tak"
2/3 ))
exp (m [oo(g k)
22 (2-T))
exp emp(moog(e - A:) (2.3 + +)) = (p k)) mm
2/3
Combining the above two displays gives
k
k
|C 2
<
(p - m)m(((+e)
m
p
k
m=0
k
=(1+
k
1+
m
(p k)) 23
(p k)1 23
m=0
Finally, recall that by the assumptions of the theorem, k = |cpp" for some a E (0, 2)) c1 > 0 and
that B < a. Choosing c = 1 - a - B > 0, gives
1 bnn 112 - (1 (p k)1/2+a-B
k
Since h |c,p"], then as p - co, the above behaves
[ (1+
C1
Therefore, for 3 < a, as + xx, 12 0(1).
C SSL Algorithm
C.1 Proof of Theorem 3.2
We prove the theorem, assuming that LSPCA is run with the correct sparsity k and with a slightly smaller sereening factor 3 = for a fixed (though potentially arbitrarily small) ē > 0, which implies the first stage retains bit more than p1-B
-8 of the original p variables.
Our proof relies on the following two key properties: (i) The set Sz of size p= [p' which is the output of the first step of LSPCA, contains nearly all indices of the true support; (ii) since the reduced dimension 5 & n, the leading eigenvector of PCA is asymptotically consistent, thus allowing recovery nearly all support indices.
The following lemma formally states the first property. Its proof appears in Appendix D
20

---

implies that || + Vd, as Lemma C.1. Let ((2,, Wi) be L i..d labeled samples from the mixture model (3) with vector
of sparsity k = [eip"] and nonzero entries + LV//k. Suppose that L 2,8h log(n-k)
for some
A
E (0, a.. Let 3 é where 0 is sufficiently small that B3 0. Let Sr. be the indices of the top p - [p'- entries of the vector WL of Eq. (0)) Then, for any e > 0,
(1S [1
lim P P-000
11-5)
(47)
k
As described above, rum LSPCA with 3 = B-- é, and denote by Sr. the set found by the first step of the algorithm. By Lemma C.1 this set satisfies Eq. (47). Denote by Σ st and Σ ss the population and sample covariance matrices restricted to the set of indices Sz. Note that,
Proof of Theorem 3.2
S) = 14ls 14 I
Hence, up sign, the leading eigenvector of E|s, is
Mise Denote by VPCa the unit norm leading || I|
cigenvector of the sample covariance E We now show that these two eigenvectors are close to each other. Indeed, since > 1 - any, we have n/p = pay (>²(p"=*) + cc, + co. Then, combining this observation with Theorem 2.3 in (Nadler 2008). implies that with probability tending to 1,
>
lim
VPCA.
1.
|| Sz.
Since μ E Rp is k-sparse with non-zero entries +V - Eq. 47
p + 00. Hence,
uls2 VA
lim
VPCA,
= 1,
(48)
p-100
which implies that with the correct sign,
lim p-000
VPCA
14 14
0. vX
From now we extend VPCA which originally had dimension |Sr. to a -imeemniioo vector with zeros in Si. Hence, since || + 0, follows
lim p-200
VPCa
0.
(49)
Vā
Next, let us assume by contradiction that there exist co, do E (0, 1) such that for every p N, with probability at least ón
IS ISn
<
k
where S is the set of top-k coordinates of |Pecal- Combining this assumption and Eq. 449 with probability at least 5n
SS
lim /PcAllll lim p-000
||ماا||
lim p-cc
|
lim p-000
I 1 ED.
(50)
p-o
k
where the last inequality follows from the above assumption and | / A/K, for all j S.
Next, from (47 and (49 it follows that for any subset T' that satisties S₁ ns T C St. and [T' =
lim 1 p ā ||/4/=|12 lim p-toc
SSn
lim
(51)
k
However, since S is the set of the top-k indices of /PCAAl for any [T] = h T C St
|PCA| |s|| PCCA
|T
which is a contradiction to 50 and Hence, for any as p tends to infinity, IP sSn
I. which completes the first part of the proof.
The second part of the proof follows from combining (48) and Lemma A.8
21

---

D Proofs of Additional Lemmas Proof of Lemma
B.1 First, note that the mean V
[ Es [0$]
is given by
1 1 -
(V=)
k kiisp
Vk p++
To derive explicit expression for the covariance matrix E we use the law of total expectation
=
Σ B (a) vo) sz].
(52)
p
where 82 = - a member of By definition,
((0- - vx) ) IS = 85) = (0": - vz) + of Vk ej
Vk(p u + of
(53)
where u [0 of S, inserting
and {ej}selo denote the standard basis of IRP. Since is independent
p-
(33
into
52
gives
Σ
p k
1
E
1
Cj
(p-k + +1) u
1)
+oē)
(1/
VT
1
(e;
(p k 1p- + +of
P
(p- + 1) Σ e
+ Σ
ejuu
+ uuu + +
k(p - k + 1)2
u
]
f=k
j=k
j=k
Note that 2/ Ej- Thus,
= k(p k 1)2
(p- k 1)
Σ ee
-uu T
+
j=k
3 k(p - k + 1)
Σ
ejee + I
j=n
1
((--1)((-11)
0(-1)x(p-kt)
+
k(p 1)
0 ((-
(p k+1)
Therefore,
p-k+1
log det (E)= < log (a²)0 1+ k(p k 1)02
1
p log (o²) (p - x + 1)log
1+ k(p 1)02
Proof of Lemma B.2 By definition [(x; S) = H (x) Hxx()) Hence, we first derive expressions for these two terms. Since follows the mixture model (3) is of the form Sadd + &. Given
is distributed as mixture of two Gaussians with centers =44 and identity covariance matrix. Its density is
S S s, μ² is deterministic with μ / 1ij s}. Thus, the vector (æ)
11=1==-"112 /|/ + e [0 11 /12/2
1=|2+A
e (2.11") + ((0,
f s) = (2/7)//2
(2T)p/2
2
(54)
22

---

By the definition of conditional entropy,
H(x[S)= = P(S= / f(x] = 5) log f(a|S s)dæ.
SEa
Given the structure of the vectors μ¹ for all S, all the integrals in the sum above give the same value. Therefore, it suffices to consider a single set 80 = (1....,k) k),
H(x|S) / (z)S = so) log {a|S so) so)dx.
(55)
Inserting
54) into 55
gives
live +A
(x]SS) Em|so log
(2T)P/2 cosh (2c, / 22))))
Note that for any S, E |||]|||| s s] x + p. Thus,
(x = Ap, Exj so [log (ar,((ar
(56)
where C(p, 1) = x+ + [ + (2g()
Consider the following two independent random variables,
1
Σラ Es ~
N (0, (x) and
VB
{ = Ek NNO,1) 1). For S = 80+
V1
(a, )0)) = (ypee0 +0, xy + VAW +
E.
Vk
Inserting the above into 556 gives
H(x[S) Cp. A) E log cosh (Ay + Vxw + v\/kE)]
where the expectation is over y and ç. Note that w, y and & are independent random variables with zero mean and symmetric distributions around zero. Further, recall that y attains the values +1 with equal probabilities. Hence, by symmetry argument we may set y 1 and take the expectation only over w and g. This gives
P (1 + log 2T) - EE log cash (A + vaw + Vx/kt)
H(rSS) x+
(57)
2
Next, we derive an expression for (xx). Recall that x depends on vector S with S distributed
uniformly at random from & of size p le + 1. Note that 3 = Up= where = [k 11) (e). By the law of total probability
f(x) =
Σ [(xSS = 8) x)=
[x = 8²)
k + t=k
SE3
Using the same analysis as before, it follows that
1im
e (a
+ elaa
((x)
(2m)a/2 P k
2
t=
Hence,
+ elom
H(x) - log fx)) C(p, A) - E log
(58)
p
t=k
We now simplify the expectation in 558) First, by symmetry argument, we may assume the label that corresponds to x is simply y = Let us simplify the inner product (x, )
k k-1
+ (E (EE))
(a. )) = (Vxie + = A
+ VXw +
k
k
23

---

Hence, the expectation above can be written as
(a (ل-ا) An- & (PES)) + ( (1 A/Rket (
log
p
2
where the expectation is over S, and {5r) Since S is uniformly distributed over 3 and for any s the expectation is the same, we may thus set s* [k], and take the expectation only over w and {Ee)e=k
Next, we decompose the inside the logarithm as S1 S2, where
(-x Viw
k-1
Si exp
2
p
t=k
S2 exp k k-1 vXw)
ev /eeetti
k:
t=
We now analyze each of these terms in asymptotic setting where p, k and l o(p). To this end we write the sum in S2 as follows
eVi + p- k +1
eVtaa (ck-1)
k +
By the central limit theorem, asymptotically, the first sum may be written as eA/2h Op(
which
Vkp
follows from the fact that Ez~ = 122 The second term above is Op(
which is
Tp
A/26 -1
negligible w.r.t. to the previous Op term. Note that its expectation is finite and given by The sum S1 can be analyzed similarly. In summary we obtain that
p p-b+1
S S2 = A/2k cosh (**= ( + vxw)
(1+ (1+0p
V1 Vkp
Hence, the expectation above simplifies to
A
( x (= vxw) )
VX
El S2)
EE log cosh
+0
2k
k
vkp
Inserting the above into 588 gives
(x ]] +0 A + vxw
v
H(x)= = C(p, A) log cosh
(59)
Vkp
Next, we derive upper-bound for the mutual information 7 (x=;5) Hxx) (7 and 59 the constant C(p, A) cancels out, and we obtain
H (x)S)) Combining
A
(x (k- (k-1)
+ Xwo )1
A
T(x;; S)
E
log cosh
A Vxw +
log cosh
+0
k
k
2k
Vkp
A
E
Ow
k
Iw
k
2k
+
o
Tep
(60)
where (t) = log cosh X + VAw +
t).
For future use, note that de 9w (t) = tanh(A A + VAw + t).
To upper bound (wx; 5) we split the expectation (60) into two parts as follows,
A
A
A
[(x; S) E ghu
+ E gi (0) 9m (-x)
+0
(61)
2k
Vkp

---

The Taylor expansion of 9w (t) is given by
t² gu (t) 9w (0) + f tanh(A + vdwc + 2 - ta-hn VAw)) +
to
3 gn " (T.).
Here Te is some number between 0 and and g (Tr) -2 ttan((A+ + vxw + Tx) tanh VAw + Te). Note that for all TR.
2 tanh(A + VAw + m1) (1 -1- (1- tanh?
+ Vxw + T)) - 2
(Ta)
3!
3!
Since 2, w are independent and B[z] follows that
EE
gu
Iw (0)
K
tanh (a+ vxxe)
=² (1 tanh?
(*+ vxu))
2
IE
3//3/2
X
E 1 tanh? (a+ vxvo) +0 (V
A
(62)
2k
1-3
For the second term in (61. for any value of w, by the mean value theorem, it follows that
tanh(A + VAw + Sw) S k A
Iw (w) gw
tanh(A + /Xw)
k
where S. [-A/k: 0J. and the last inequality follows from the fact that tanh(-) is a monotonically increasing function. Hence,
gw (0) Iw
S E tanh(A + vdw)|
(63)
k
Hence, combining 66
662 and 663 yields
X
E tanh? (a+ vxw) ]
A E [aanh(A viw)
A3
((:;5)
+
2h
K
2k
1:3
Vkp
>
E
ta + vxw)=
1
tanh? (* vXw) +0
13
+
VT
(64)
k
k3
Vkp
By Lemma A.7
the expectation above can be bounded as follows:
taanh(A + vdw) 2
tanh? 2 (* -xw)
( + 3v //kk)
S
2
Hence, inserting this upper bound into (64). gives
12
Vī Vkp
+ V29/K3)
I(x; S) <
+0
(65)
Asymptotically, as p + oo with k/p 0 then 1/2
kkp Thus, the term 1 12 is asymptotically
larger than the O()) terms in the display above. Hence, the inequality (37 of the lemma follows. L
Proof of Lemma C.1 The main idea of the proof to show that with a suitable choice of threshold nearly all entries wr, (j) for E S are above this threshold, in absolute value, whereas the number of noise magnitudes above smaller than p - Since we prove the lemma for the case of two symmetric Gaussians P1 - n. for simplicity we consider the following formula
25

---

for wy = 1 E== yie, With minor adaptations one can also prove the Lemma with the original formula (TO) of wt.
Fix > 0, and let Ar denote the event that Sr SS 2 Ae(1 - c). For any threshold define the following two events,
B(r) = ((wm(()) k(1 0
jES
and
C(7) = Σ
<}
JES
By their definition, it follows that for any 7 0
B( ((T))
Furthermore, note that the events B(r) and C(r) independent. Hence, to prove that (P(A). 1, suffices to prove that for a suitable threshold 7,
P (((T) (((T)))())
(B(r)) P (π(T)) +
(66)
In other words, it suffices to show that each of these events occurs with probability tending to one.
We start by showing that Pr[B(r)] + 1. First, let us define an even simpler event, with the absolute value removed,
B(T)
Σ 1 (w)) jES
1=1 e)
Clearly B(r) B(T) and thus it suffices to show that IP(((T)) p -
To this end, we consider a threshold of the form v TT, with the value of T specified below. By the sparse mixture model 3 at support coordinates,
A sign(H;) Ej
sign(1;))u1 =
VL
where E; ~ (0, 1). Inserting this expression with L > the dependence on 7 in B(T), gives
23% log(p-k) into the above, and suppressing
PBB)
2 P
Σ jES
1111+
1+
23 log(p - k) (R)T]/ r) k(1 -)
1
P
Σ
165 > -(1 -) 2olog(e k)} k(1 -0)
(67)
jES
Next, we choose
T = (23 log(p 1))
(68)
and define
9: P (N(0, 1) > (23logg k))2/4). Since the E₁' 's are all independent and |S| = k; with this choice of T, Eq. 67 simplifies to
IP (B) 2 P (Bin(k, q1) k(1 e))
26

---

Note that limp-to 91 = 1. Thus, for sufficiently large it holds that Q1 - mn(1=/22- -- c. Hence, instead of the right hand side above we may bound IP ((.in(k..) qi) kqi (1 e/2)). Indeed, by Chernoff's bound 17
2km
PP (B) 2
which tends to one p, k +
Next, we show that the second term in Eq. 666) P(C), also tends to one as + oc. First of all, since & [cpp] and sufficienlly large, we may instead consider the following event
1 B, then k < p p'-ă, and thus ý - k p/2. Hence, for p
C(r) = Σ 1(wr..)) > T)
1 2
Binly- - k. k2 <
jEs
where (2(T) = - (vTr). Clearly C(r) C C(T), and we now prove that with
V T. and T
given (68) P(C(T)) + 1, by applying Chernoff bound.
To this end, we write
p c2 k1
2
where 8
1.
2[p-k kJ 92
To use Chernoff's ss inequality first need to show that 2 0. Indeed, p with 7 - V and using Lemma A. which bounds the tail function $5,
p1-
lim (6 1) lim p-000
p-000 2(p k) (T' 223 lo k))
VTB lim
T Toooo k)
VTB
T VVog(p k)
lim
(p 5) (69)
2 p000
(p- k cxp( (-pp--T2,10 Blo(p k:)
2 p00
Note that for sufficiently large p.
-- 3(1-T") log(p 13)114 (2
(23 log(p- log(p=3))) -
2 (2 log(p k))1/4 -50
Combining the above and (69 gives
VTB
lim (5 + 1)+ p-o
lim T TVoog( k) = 00.
2 100
Since 3 B, for sufficiently large p. and 7 given in (68 it follows that B - 372 < 0. Therefore, for sufficiently large p. it follows that > 0. By Chernoff's bound (66
PP (c ((VVT))
(Bin(p- k2) < 92(p k) 8)) 2 (- klog 2
(70)
We now prove that the term in the exponent tends to infinity. First, note that since å + oc then 2(p-k)
Tpp kigz Hence,
(p k)ga
p (p k)g2 oo.
lim p0000
lim 8(p k)gz 2 lim
2+8
4(p k)g2
Combining the above and 70 gives pom cc ((EE)) = which completes the proof.
27

---

E The MLE in the Supervised Setting
The following proposition states the form the maximum likelihood estimator (MLE) for the support S in a SL setting, where the sparsity k is known, and the non-zero entries of have magnitude vV
Proposition E.1. Let {(zs, (:) be L i..dd labeled samples from model 3 where p is k-sparse with non-zero entries ///, and let wt, F. Eve(r,) y; Assuming the sparsity k is known, the MLE for S = supp (4) is given by the indices corresponding to the top-k magnitudes of wL.
Proof. Under our assumptions, the set of all possible vectors has a one-to-one mapping to support set 5 E S and a vector D {-1,1} containing the signs of the l non-zero entries of μa. We thus denote D), and 2x by
LA Vk
Dj,
JES, j
0.
Let us denote by (x, y; 0) the joint probability density function of single sample (æ, y) from the model (3) with parameter 6. Since is a Rademacher random variable with a distribution not dependent on 8, may write
(x, y: 0) (x y: (1) 1 (aly: 0).
Since æly (y,, Ip), the conditional density Pxly (alg) g: 0) simplifies
1
(x,y 0) (2
exp [-1| yp 1111112 112
(71)
By definition, the maximum likelihood estimator of given by
((ML)) = arg max log Px,y (xx,xxyyxx., U;
Inserting 7I into the above, and using || || = V (fixed for all 0), gives
((ML) = arg max
(- 1|= vipe"12) arg max
Ui: n²) arg max (WL,
Therefore, the maximum value of (wL, ( is obtained for ((ML) being the set of indices correspond- ing the & largest magnitude entries wv, and (ML)) (sign(wL)) S(ML)
The proposition shows that with sufficient number of labeled samples the MLE for S has significant overlap with the true support set S.
Proposition F.2. Let Dr. = ((x, =1 be a set of L, i.i.d. labeled samples from the model 3 with a k-sparse vector whose non-zero entries are + /A/k. Assume that for some E (0, 1), k = [c,p"' and that L 20h log(p- k) for some 3 E (0, 1). Let Sy be the indices of the k largest magnitudes of the vector wt + Eie(r) yiwe, If
then for every E (0, 1),
lim P p0000
> 1 11-6) =
k
Proof. Fix O, and let Ar denote the event that 12 n k(1 c). For any threshold define the following two events,
) ((7)= =
B(T) = Σ [(lwz(() > k(1-6) - e) }
Σ
((wwr()) > 7} < ke
jES
jds
28

---

By their definition, it follows that for any 0, (() C Az. Since the two events B(r) and ((T) are independent,
P(A)) 2 (B)))))()) (B(T)) (c(7)
(72)
Hence, for P(AL) + 1, suffices that for suitable threshold т, both probabilities on the right hand side tend to one, We start with Pr(B(rr). To this end, we define an even simpler event, with the absolute value removed,
B(T) - Σ
(oiggn(())wrtii)) >T k(1 -c)
JES
Clearly B(r) C B(r) and thus it suffices to show that P(B(T)) - mixture model (3), for S.
as p
By the sparse
À
sign(u;)
sign(u;)wr,
Sy:
Te
VL
where Ey No 1). Combining threshold value
1--48 28
and the assumption that
1 log(p-k) with this expression, gives that
E E3 [
- a a+ B
V2logg/ > k(1 -((--))
P(B(T)) 2 P
(73)
2
jES
Let F1 be the probabiity of each event in the above sum,
= PP N(O,
VB
a +
3
V /ogg
2
Since the Ej's are all independent and |S| = k with this choice of T, Eq. simplifies to
P(((()) 2 PPi q1) k(1-))).
Note that since 3 > a, then limp- = 1. Thus, for sufficiently large it holds that q1 e/2) > 1 e. Hence, the right hand side above may be bounded by P(Bin((k.q) > kq - e/2)). Indeed, by Chernoff's bound (17). P(B(T)) + as - since
(BB)
Next, we show that the second term Eq. [22. P(C)), also tends to one as p -> co. First, note that
Č(T) = (in k. (2(T)) < kc}
where (2(r) = (vLr) = 2 ( + 3) log(p k)). We now prove that (P(((T)) + 1, by applying Chernoff bound. To this end, write
kc = 42(p k1 + 5)
where 5 = ke 1 - 1. To use Chernoff's ss inequality we first need to show that 5 2 0. Indeed, as (p- #2
p co, using Lemma A.l which bounds the tail function d
lim (6 1) Z lim ek p-000
1
p p k 2
(1
+ B8 log(p k:)
TT1 a 3)
Vlg(p - k)
2 cc1
lim p p exp(
2
I-até log(p k))
3
Tog(p
601
lim 100
xC,
29

---

where the last equality follows from / > 1 a. By Chernoff's bound 16
P ((C(T))= = P (Bin(p - k, 92) < (2(P - (1 + 6)) 2 1
22 (p- Al82
(74)
We now prove that the term in the exponent tends to infinity. Since å + oo it follows that
0 k)g2
(1 + 5) - k)g2 lim
ke
lim p-+00
lim 8(p p-+00
k)g2 2
lim p0000
0c.
2+6
2
Combining the above and (4) gives that limp- P (d(T) 1, which completes the proof.
The above proposition implies the following result regarding accurate classification: Let T(x) sign(β, z), with μ wL St. be linear classifier that is constructed using only the set of labeled samples L. If 3 > 1 a, then combining Proposition E.2 and Lemma A.8 implies that the excess risk of tends zero as p Co.
E. Impossibility of Classification
In this section we prove a lower bound for classification in the SL setting. To do that, we consider slightly different model, known as the rare and weak model. Here the sparsity of the vector fe is not fixed at exactly k. Instead the vector generated randomly with entries μj VYKBB,. where B₁ ~ Ber(ep) are i.i.d. Bernoulli random variables with ép _/ = p (1-a), The next theorem implies that in the red region (impossible) of figure I vectors for which any classifier would asymptotically be better than random.
indeed there exists (approximately) k-sparse
Theorem E.3. Let Dr {( yi be set of L i.i.d labeled samples from the rare weak model Wyp, 1) where all non-zero entries of μ are /A/k. Suppose L 2 1og.2 and k x for some a < 1. If 3 p co.
< 1- -a- a then the classification error of any classifier based on Dt., tends to 1/2 as
Proof. This proof is similar to the one Jim (2009). First, let us denote the vector of z-scores by = VT. Eiele) yee; Since the entries of f are generated independently under the rare-weak model, the entries of z are also independent and all have the same density, which denote by f(=). Given z, we denote the conditional probability that the j-th entry contains a feature by " P(j E S]z) P(j S|z, 2). By Bayes theorem,
T==) P(j (>f( E
Epp(2 Tp)
f(z)
(1 - (-)pp()()) :) + Ep0l2 - Tp)
where Tp = LLAk = 2,3 log p. and & is the density of ().
From Lemmas 1,2 and 4 in Jin (009)), the misclassification error of any classifier T constructed using the set Dz, can be bounded
- - ((LL(((((())))))
(75)
E, (1 (O, <N((Tp: 1).
(() 11) 1/2
where H(2) =E,
with NOO, 1), and z (1
Our goal is to show that EE [H()] = + o(1/p). which implies that asymptotically the accuracy and the inequality
of T' is no better than random. First, combining that Eg (eV//ku-A/22
WI+ - t/2 < Ct2, for any t > -1, gives
H()) - 1 - B[n(2)] BleV 11 1| -
-(x)
< <cT((2)) (c/ATke-N/2+-1)) -
30

---

For sufficiently large p, e/ 1 _ 24/k. Since &o x p", then, [H(2) 1| - Öp (z). Hence, to prove that I. [x[] = 1 + o(1/p), it suffices to show that E. [2] = olp opp-pp11--0 (1-a) = =<(p)) To this end, we first note
[x)] = (1 - cp) Ely ( + cg + Tp) S ([))(w) + Ewn Tp)l.
where (O, 1). Write (2) I + 11 III + IV, where have split each of the expectations into two separate integrals, with the split at suitably chosen values t and t2,
I = b)
11= [, ((())(w)do.
(w)))(w))d,
and
rf(w (p)d( IV IV cp L rf(w + Tp)o(w)dm
III (p
As we see below, the following values will be suitable to derive the required bounds: 4 1-0+0 and l22
2/ Tp
1-a-8 23 Tp-
Starting with I, note that
1= f_ (1
cpd(w Tp)
)
2 ó(w)dw 1 "ppo(o Tp) ) Φ(w)dw (1 (1-c))
((1-6))0()) (p)(ww epp(u Tp)
For large enough the above can be bounded via
Q2(w- Tp) (x))
Mw)dw = Ce I"
pl 13
I 1 26,
(76)
where the equality follows from the definition <(w). Completing the square, the above can be written as
I I 1 I - 2wm221))/2 d...
Changing the variable
w 2Tp reads
I IS Oezer I' p1-25 -2 Ce -1) s SCfere- (77)
Finally, since 3 < 1 it follows that Ceferie C2 = o(tp).
Next, since ()w) < it follows that
II r'(w)ó(w)22 < f o(w)du= ='(l)))))(()) < $e -1//2
(78)
Similar to the above, under the condition 3 < - a holds that - = o(ep). Next, note that
f&
f2
(G((w)
I11 Ep
d(w)dw
-00
kp]o( + tp) tep((w)
2/2
G)((w))
I Ep
o(w)dw.
(1 - (p)[() + Tp)
-00
For large enough p
(nd(ww) 2 p(w + Tp)
b(w)du =C f 2wopt x² dw
ITT Ccp
Completing the square reads
f2 TTT S 3r 1
(ww d2 CG.e (2Tp 12) Ce -(2rp
31

---

Since 3 $ 1 a it holds that III = o(Ep).
Finally, since v7(w)) IV can be bounded as follows
IV cp [ o(w)dw = (t20(t2) S e,e 2//- -//2
Again, by < a, IV o(p)).
32

---

NeurIPS Paper Checklist
Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: See Section S
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
33

---

Justification: All the assumptions are clearly stated at the beginning of Section 2 The proofs can be found in the supplemental material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: See Section 4
Guidelines:
The answer NA means that the paper does include experiments. If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
34

---

Answer: [No]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/dde/eeee Cooeeeoodeesssseeeeee 7/nips.com /ttc://dllllliiiiee////eeeuaaass ssiniiiiccypyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: All the necessary details regarding the experimental settings are provided in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
See Section
A
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
35

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
As mentioned in Section 4 the experiments were run on a CPU Intel i7 2.10
GHz.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
36

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
37

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
38


Reviews:
[{"review_id": "8R0SRQqYgN", "reviewer": "Reviewer_NrxF", "summary": "The paper studies semi-supervised learning in a simple mixture of two Gauss(ians setting.  Specifically, there is a uniform mixture of two Gaussians in $p$ dimensions with unknown means $N(\\mu_1, I_p), N(\\mu_{-1}, I_p)$.  We assume that the difference between the means $\\Delta\\mu = \\mu_1 - \\mu_{-1}$ is a $k$-sparse vector and for simplicity, we also assume all nonzero entries are $\\pm \\sqrt{\\lambda/k}$ for some parameter $\\lambda$ that controls the signal-to-noise ratio.  Now the learner receives both unlabeled samples from the mixture (which are just points in $\\mathbb{R}^p$) and some labeled samples which also include the label of $+1$ or $-1$.  The goal of the learner is to learn the support of $\\Delta \\mu$ (say with at most $o(k)$ errors) , which then gives a classifier that separates the two Gaussians.  Information theoretically, with only labeled samples or only unlabeled samples, the optimal rates are well-understood (in a bit of an over-simplification and ignoring log factors, they are $\\sim k/\\lambda$ and $\\sim k/\\lambda^2$ respectively).  If we let $L$ and $n$ be the number of labeled and unlabeled samples, the paper shows that interpolating between the two rates, using a mixed number of labeled vs unlabeled samples cannot help.  Thus, up to constant factors, there is no benefit, information-theoretically, from combining labeled and unlabeled data.  This portion of the results are very similar to [Tifrea et. al. 2023], which proves the same type of result in the setting with no sparsity.\n\nTHe main contribution of the paper is identifying a regime where there are potential computational benefits to combining labeled and unlabeled data.  There is evidence (namely low-degree/SQ lower bounds) that solving the unsupervised variant of the problem is computationally hard with fewer than $k^2/\\lambda^2$ samples.  Now consider a regime where we have a slightly subquadratic number, say $k^\\gamma/\\lambda^2$ for $\\gamma < 2$, unlabeled samples. This paper shows that in this regime, even if we combine with a small amount of labeled data, the problem remains computationally hard.  On the other hand, the paper also shows that if we combine with a larger amount of labeled data (but still not enough to just solve the supervised setting by itself), then the problem becomes computationally tractable.  There is a constant factor gap between the amount of labeled data in the upper and lower bounds, but nevertheless, this identifies a region where combining labeled and unlabeled data makes the problem computationally tractable whereas using either only the labeled or unlabeled data individually would be intractable.", "questions": ".", "limitations": "Yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper makes advances in an important research direction of theory for understanding semi-supervised learning\n\nThe paper has a nice conceptual message in identifying a setting where there is a provable benefit to combining labeled and unlabeled data, proving both upper and lower bounds (under commonly believed computational assumptions).  It is also nice that the main algorithm gives a clean way to combine two different types of information.\n\n\nThe algorithm in the paper is simple enough to implement and the authors are able to support their conclusions with numerical experiments", "weaknesses": "The paper only studies a limited setting of a mixture of two Gaussians\n\nThe benefit from the unlabeled data, (in terms of reducing the number of labeled examples required), is only a fairly small (less than $2$) constant factor\n\nIt is a bit technical to actually describe/understand the setting where the algorithm in the paper has provable gains", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review. \n\nWe agree that our work considers a limited case of two Gaussians. We remark that many previous authors also considered a same or similar setting. Indeed, it would be interesting to extend to larger number of Gaussians. However, as the SSL analysis was far from trivial already for only two Gaussians, such an extension is beyond the scope of this work. \n\nRegarding the benefit of unlabeled data. First, note that if $n=k^\\gamma$ with $\\gamma > 2$, \nrecovering the support is computationally tractable using only the unlabeled samples.\nIndeed, in the regime $n=k^\\gamma$ with $\\gamma<2$ and $k=p^\\alpha$, the unlabeled data decreases the number of labeled samples by a factor $(1-\\alpha)/(1-\\gamma\\alpha)$. This factor can be much larger than 2 if $\\alpha$ is close to 1/2 and $\\gamma$ is close to 2. We will clarify this in the revision. \n\nThe regime where our computationally efficient SSL provably works is the blue triangle in figure 1. We will add in the introduction a precise description of this region, in particular the formula \nfor the blue line $\\beta = 1-\\gamma \\alpha$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LEW9x1TEth", "reviewer": "Reviewer_uoYb", "summary": "This paper studies the classical problem of clustering Gaussians with sparse means. While this problem was previously considered under the unsupervised (Sparse PCA) and supervised settings, the main innovation of the authors is to identify a phase where labeled and unlabeled data can be used together to estimate the cluster means, even when this task would be impossible using only either of them.\n\nThis semi-supervised algorithm is complemented by various informational and computational lower bounds; in particular, the authors establish the existence of an information-computation gap for the detection task in the semi-supervised setting.They also provide numerical simulations for their algorithm, showing how to improve it by using out-of-the-box sparse-PCA algorithms in its second step.", "questions": "- You conjecture in the paper that the white region is actually computationally hard; do you have any (informal) arguments to support this conjecture ?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I found this paper very interesting to read; it considers a very interesting and natural question, and fills most of the blank parts of the phase diagram with novel results. The main achievement of the paper, the SSL algorithm, is both completely new and very easy to understand.", "weaknesses": "I think the exposition of the paper could be slightly improved. In particular:\n- it would be nice to mention which part of Figure 1 comes from which theorem, and which are novel to the paper;\n- Theorem 2.3 and Corollary 2.4 are presented very dryly, and it is hard to understand exactly what they aim to prove (in particular because I'm not fully sure when $\\alpha$ refers to an arbitrary constant or the sparsity level $\\log_p(k)$).\n- I didn't exactly get the point of Theorem 2.1: it seems to give a lower bound at $\\beta = 1/2$ instead of $1 - \\alpha$, which is weaker in the regime $\\alpha \\in (0, 1/2)$. What does it bring compared to the results of Donoho and Jin ?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments.\n\nWe agree with the referee regarding context of figure 1. We will add that the red and green regions follow from previous works, whereas the orange and blue are our novel contributions. We also reference the relevant theorems for these. \n\nRegarding Theorem 2.3 and Corollary 2.4, we will rewrite it with $\\alpha$ replaced by some other symbol, say $q\\in(0,1)$ to avoid possible confusion with the sparsity level $k=p^\\alpha$. \nThe goal of this theorem and corollary was to derive an information theoretic lower bound in the SSL case. We will clarify this and the meaning of the two theoretical statements in the revision. \n\nRegarding Theorem 2.1, we agree that as originally stated it is weaker than the result of Donoho and Jin. The reason is that we considered the case where the probability of error in exact support recovery is bounded by 1/2. In the revision we will replace it by the following result (which still follows from the original proof without any required changes): \nLet $\\delta \\in (0,1)$. If $L < (1-\\delta)\\frac{2k}\\lambda  \\log(p-k+1)$, then for any support estimator $\\hat S$ based on $\\mathcal D_L$, $\\Pr(\\hat S\\neq S) \\geq \\delta$. \nThis results shows that exact support recovery is not possible with probability tending to one even for $\\beta > 1-\\alpha$. We will also discuss the relation between this result and those of Donoho and Jin (which are not about exact support recovery, but rather \nfor approximate support recovery, namely $|\\hat S \\cap S|/k\\to 1$ as $p\\to \\infty$). \n\nRegarding motivation for our conjecture: As derived by Donoho and Jin (05'), in the fully supervised (SL) setting there is a detection-recovery gap; Namely for a range of number of labeled samples, it is possible to detect that a sparse signal is present, but it is not possible to reliably recover its support. Intuitively, adding a few unlabeled samples should not resolve this gap. We will add a discussion about this issue in the revision.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "V1nzpxnoXb", "reviewer": "Reviewer_3M9B", "summary": "The authors identify a regime where semi-supervised learning has computational advantage over (purely) supervised or unsupervised learning. They propose an algorithm that achieves it and demonstrates the efficacy of the algorithms in simulations.", "questions": "- Do you have a conjecture for the information theory lower bound in the white \"hole\" region?\n- Do you have any insights as to how one might analyze LS^2PCA?", "limitations": "Yes", "rating": 9, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- Extremely well-written paper\n- The theoretical results I believe will become landmark results in the area of semi-supervised learning\n- The literature review is thorough", "weaknesses": "- What is the answer to the question on L59, namely \"On the computational side, is there a computational-statistical gap in SSL?\" For the white \"hole\" in Figure 1, the computational-statistical gap remains, is this correct? It would be good to state this explicitly.\n- Also, it would be nice to add references to the results in Section 2 to the paragraph starting on L86.\n- It would be nice to rigorously explain the reduction on Eqn (3), even if in the appendix.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive comments and encouraging feedback.\n\nRegarding the question in L59\n\"On the computational side, is there a computational-statistical gap in SSL?\"\nThe answer is yes. We will modify the text in lines L70-76 to explicitly mention that by adding too few labeled samples, there is still a computational statistical gap (the orange region in Figure 1). \n\nRegarding the white \"hole\" in Figure 1, we do not know if the computational-statistical gap remains.\nWe conjectured that the gap still remains in this region. See the text L107-8. \n\nWe will revise the paragraph starting on L86 to clarify what are novel results and include references to the relevant theorems that appear later on in the manuscript. \n\nRegarding the reduction in Eq. (3), we will clarify this reduction in the revised version. \n\nRegarding an information theory lower bound in the white \"hole\" region:\nFrom an information-theoretic perspective, for $\\gamma>1$, there exists a non-polynomial-time algorithm that succeeds in recovering the support, that uses only the unlabeled samples. \nHence, since the white \"hole\" region is a sub-region of $\\gamma>1$,  the same holds for this region as well.\n\nRegarding an analysis of \\texttt{LS$^2$PCA}, please note that this would depend on the specific \nsparse-PCA method employed. In our manuscript we employed the IPU method of Tian el al. We currently do not have insight how to analyze it in our context. This is an intersting question for future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b9Nl1spbL6", "reviewer": "Reviewer_6RTo", "summary": "In this paper, the authors studied the problem of semi-supervised learning in a 2-class classification problem with a special distribution setting. They assumed that the samples in each class came from an isotropic Gaussian distribution with unknown mean vectors $\\mu_1$ and $\\mu_{-1}$. They also assumed that the vector $\\Delta \\mu = \\mu_1 - \\mu_{-1}$ is sparse, with $k << p$ non-zero elements, where $p$ is the dimension of the feature space, and $\\lambda = \\|\\Delta\\mu\\|_2^2/4 = \\mathcal{O}(1)$.\nThe claims of the paper are as follows:\n\n* Derive information-theoretic lower bounds for exact support recovery in the semi-supervised learning (SSL) setting.\n    \n* Establish computational lower bounds for classification and support recovery in SSL as $(k, L, n, p) \\to \\infty$, where $L$ and $n$ are the number of labeled and unlabeled samples, respectively.\n\n* Identify a region where SSL is computationally advantageous for classification and feature selection.\n\nThe authors derive lower bounds on the number of labeled and unlabeled samples needed to efficiently recover the support set of $\\Delta\\mu$ and classify data. They also propose an SSL algorithm that can efficiently recover the support set of $\\Delta\\mu$ and classify data, outperforming any supervised or unsupervised learning algorithm that relies solely on labeled or unlabeled samples.", "questions": "*1*-  In line 133, it is stated that the most difficult $k$-sparse vector with a lower bound on the absolute value of the non-zero terms is a $k$-sparse vector where its non-zero elements belong to $\\{\\pm\\sqrt{\\frac{\\lambda}{k}}\\}$. Is there any proof for this? Is it obvious?\n\n*2*- I think in line 823, $\\Theta^S(j)$ should be $\\sqrt{\\frac{\\lambda}{k}}1(j\\in S)$. Is that correct? If it is, I think it changes the result in some of the theorems.\n\n*3*- I believe the lower bound in Corollary 2.4 is not tight, or at least it is not proven to be tight in the paper. One reason is the assumption that given $S$, labeled and unlabeled samples are independent.\n\n*4*- Is there any proof that the bound in Theorem 2.3 is tight?\n\n*5*- The proof for Theorem 2.6 is indexed as the proof of Theorem 4 in the supplementary material.\n\n*6*- In the proof of Theorem 2.6, the distributions $\\mathbb{P}$ and $\\mathbb{Q}$ are different from those in equations (8) and (9). Can you please explain this? Also, why should we test between the distributions in equations (8) and (9)? It seems that the distributions in the proof make more sense.\n\n*7*- In Theorem 3.2, is it sufficient to solve the problem just for the case where non-zero elements are $\\pm\\sqrt{\\frac{\\lambda}{k}}$?", "limitations": "Please check the questions.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The theoretical results are interesting, and the proofs are rigorous.\n* The writing is very good and easy to follow.\n* The messages of the paper are very clear.", "weaknesses": "* It seems that the algorithm named LSPCA cannot be used as a semi-supervised algorithm on real-world data and only has theoretical value in the special setting of the problem. It would be more interesting if the authors proposed an algorithm that could be applied to real-world data, yielding good results in practice while also having strong theoretical guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive comments. We address the issues raised one by one.\n\n(0) We agree that our proposed LSPCA method is tailored to our specific case of a mixture of two Gaussians. However, we believe that the insights of our work, proposing a two step SSL scheme, using the labeled data for feature screening could motivate the future development of practical SSL methods for high dimensional settings. \n\n(1) We will add an explanation near L133 why vectors with non-zero entries of size $\\sqrt{\\lambda/k}$\nare the most difficult. \n\n(2) Our text is correct. The reason is that we work with an equivalent model where\nthe noise level is $\\sigma=1/\\sqrt{\\lambda}$ instead of $\\sigma=1$. We will clarify the text. \n\n(3) The lower bound in Corollary 2.4 is indeed not necessarily tight. We will explicitly mention this in the revision. \nPlease note that given $S$, by the definition of our model, the labeled and unlabeled samples\nhave statistically independent Gaussian noises, so this is not an extra assumption. \n\n(4) Regarding tightness of Theorem 2.3: Please note that its proof is based on Fano's lemma. Hence,\nwhenever this lemma is not tight then the theorem would be not tight as well. \n\n\n(5) Indeed the proof of Theorem 2.6 is incorrectly referenced as proof of Theorem 4. Thanks for catching this typo. which we will correct. \n\n\n(6) In the proof of Theorem 2.6, the distibutions $\\mathbb{Q}$\n and $\\mathbb{P}$ are exactly those in equations (8) and (9).\n Critically, even in the SSL setting the distribution $\\mathbb{Q}_{L+n}$ consists of pure isotropic Gaussian noise vectors. We test between (8) and (9) since we follow the machinery of the low-degree likelihood ratio framework, which provides us with lower bounds. \n  We will revise the first few sentences of the proof to better explain all of these points. \n\n\n(7) Regarding theorem 3.2, please note that it is stated for $k$ sparse vectors whose non-zero entries are $\\pm \\sqrt{\\lambda/k}$, see second line of theorem, L302.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers are unanimous to praise a theoretical contribution paper with an interesting and timely question in high-dimensional statistics/learning theory. It establishes the provable benefit in using jointly labeled and unlabeled data in the prototypical 2-class (sparse) Gaussian model in high dimension, which has generated a lot of attention in the recent years in order to establish precise phase diagrams for feasibility/infeasibility of learning in function of master parameters of the problem (dimension, sparsity, sample size -- here both for labeled and unlabeled data).
The reviews laud the high quality of writing of the paper (main paper presentation as well as clarity of proofs), the clear formulation of the overall message, the novelty and interesting technical aspects of the contribution, and the fact that the final picture is very thorough (upper and lower bounds)
Decision: Accept (spotlight)