Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data

Authors: eyar  azar
boaz  nadler
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 06:58:56

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.

Main paper: 
 introduction: 
 The presumption underlying Semi-Supervised Learning (SSL) is that more 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 to 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, is negligible.To address this issue, SSL was studied theoretically under various models. Several works proved that under a cluster or a manifold assumption, with sufficient unlabeled data, SSL significantly outperforms SL (Rigollet, 2007; Singh et al., 2008) . In some cases, however, SSL performs similarly to UL (i.e., clustering, up to a label permutation ambiguity). In addition, Ben-David et al. (2008) described a family of distributions where SSL achieves the same error 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 of two spherical Gaussians. In this case, the label Y ∈ {±1} has probabilities P(Y = y) = π y and conditional on a label value y, the vector x ∈ R p follows a Gaussian distribution, x|y ∼ N (µ y , I p )(1)where µ 1 , µ -1 ∈ R p are both unknown. This model and related ones were studied theoretically in supervised, unsupervised and semi-supervised settings, see for example Li et al. (2017) ; Tifrea et al. (2023) ; Wu & Zhou (2021) , and references therein. Without assuming structure on the vectors µ y 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 (1), 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 (1).In this paper we consider a mixture of two Gaussians in a sparse high dimensional setting. Specifically, we study balanced binary classification with a sparse difference in the class means, which is a specific instance of (1). Here, the joint distribution of a labeled sample (x, y) is given by y ∼ Unif{±1}, x|y ∼ N (µ y , I p ).(2)The class means µ 1 , µ -1 ∈ R p are unknown, but their difference ∆µ = µ 1 -µ -1 is assumed to be k-sparse, with k ≪ p. In a 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, see e.g. Johnstone (1994 Johnstone ( , 2002)) . In an unsupervised setting, inference on the model ( 2) is closely related to clustering and learning mixtures of Gaussians (Azizyan et al., 2013; Jin & Wang, 2016) . A key finding is that in an unsupervised setting with a sparsity assumption, there is a statistical-computational gap (Fan et al., 2018; Löffler et al., 2022) . Specifically, from an information viewpoint a number of unlabeled samples n proportional to k suffices to accurately cluster and to detect the support of ∆µ. However, under under various hardness conjectures, unless n ∝ k 2 , no polynomial time algorithm is able to even detect if the data came from one or from two Gaussians (namely, distinguish between ∆µ = 0 and ∥∆µ∥ = O(1)).In this work we study the model (2) in a SSL setting, given L labeled samples and n unlabeled samples, all i.i.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 so 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 ∆µ? On the computational side, is there a computational-statistical gap in SSL? In addition, are there values of L 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, we view SSL as a 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 we present a general non-asymptotic information-theoretic 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., 2022) , in an asymptotic setting where dimension p → ∞ 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 statisticalcomputational 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 a region where SSL is provably computationally advantageous for classification and feature selection. Specifically, in Section 3 we develop a polynomial time SSL algorithm, denoted LSPCA, to recover the support of ∆µ 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 1 summarizes the picture emerging from our work in combination with previous papers that analyzed the UL and SL settings of (2) , namely, the x-axis and y-axis in Figure 1 . As in prior works we consider a fixed separation λ = ∥∆µ∥ 2 2 /4 = O(1), where ∆µ is k-sparse. The asymptotic setting is that (k, L, n, p) all tend to infinity with the following scaling, which arises naturally for this problem (see Section 2): the number of labeled samples is L = ⌊2kβ log(p)/λ⌋, the number of unlabeled samples scales as n ∝ k γ /λ 2 , and the sparsity scales as k ∝ p α for some α ∈ (0, 1/2).The figure shows different regions in the (γ, β) plane, namely as a function of the number of unlabeled and labeled samples, where classification and feature selection are either impossible, hard or computationally easy. We say that classification is impossible if for any classifier there is a k-sparse vector ∆µ whose corresponding accuracy is no better than random. Similarly, we say that feature selection is impossible if for any estimator Ŝ of size k there is a k-sparse ∆µ with support S such that | Ŝ ∩ S|/k → 0 as p → ∞. Feature selection is easy if it is possible to construct in polynomial time a set Ŝ of size k such that | Ŝ ∩ S|/k → 1. This implies that the corresponding classifier has an excess risk that asymptotically tends to zero. The green region γ ≥ 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 (1997); Donoho & Jin (2004) , who proved that support recovery is feasible if and only if β > 1 -α. The same condition holds for classification as well, as described in the supplement. The orange and blue regions in Figure 1 follow from novel results of this paper. In the orange region, defined as β < 1 -α and 1 < γ < 2, our computational lower bound in Theorem 2.6 suggests that any polynomial-time scheme will not succeed in accurate classification. In the blue region, characterized by β ∈ (1 -γα, 1 -α) and 1 < γ < 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 of unlabeled data allows to decrease the number of labeled samples by a factor of 1-α 1-γα . Under the low degree hardness conjecture, in this blue region no computationally efficient SL or UL method that separately analyze the labeled or unlabeled samples, respectively, would succeed. We conjecture that in the remaining white region, no polynomial-time algorithm exists that is able to recover the support or able to construct an accurate classifier. In 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.Notation For an integer p, we write [p] = {1, ..., p}. The cardinality of a set B is |B|. For a vector v ∈ R p , we denote its restriction to a subset T ⊂ [p] by v| T . For vectors a, b, their inner product is ⟨a, b⟩, and ∥a∥ denotes the ℓ 2 norm. We say that f (p) = ω(g(p)) if for any c > 0, there exists p 0 ≥ 1 such that f (p) > cg(p) for every p ≥ p 0 . 
theoretical results: 
 In this section we present our first two contributions, namely an information-theoretic lower bound for exact support recovery of ∆µ, 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 we were not able to find these precise results in the literature, for completeness we present their proofs, based on Fano's inequality, in the supplementary. Our main contribution here, described in Section 2.2, is a 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 UL.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}, x|y ∼ N (yµ, I p ).(3)Here, µ ∈ R p is an unknown k-sparse vector with ℓ 2 norm of √ λ. We denote its support by S = supp(µ) = {i|µ i ̸ = 0}, and by S the set of all ( p k ) possible k-sparse support sets.We denote byD L = {(x i , y i )} Li=1 and D n = {x i } L+n i=L+1 the i.i.d. labeled and the unlabeled datasets, respectively. To derive information and computational lower bounds for support recovery, it is necessary to impose a lower bound on min i∈S |µ i |. As in Amini & Wainwright (2009) ; Krauthgamer et al. (2015) , it suffices to study the set of most difficult k-sparse vectors with such a lower bound on their entries. In our case this translates to the nonzero entries of µ belonging to {± λ/k}. Clearly, if some signal coordinates had magnitudes larger that λ/k, 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 k is known. All proofs appear in the supplementary.The next theorem states a non-asymptotic result for exact support recovery in the SL case. Theorem 2.1. Fix δ ∈ (0, 1). For any (L, p, k) such thatEQUATIONand for any support estimator Ŝ based on D L , it follows that max S∈S P Ŝ ̸ = S > δ -log 2 log(p-k+1) .Donoho & Jin (2004) proved a similar result in an asymptotic regime. Specifically, they proved that for k = p α and L = 2βk λ log p, approximate support recovery is possible if and only if β > 1 -α. Theorem 2.1 states a stronger non-asymptotic result for exact support recovery. It implies that even if β > 1 -α, it is still impossible to recover the exact support with probability tending to one if β < 1.Next we present an information lower bound for exact support recovery in UL. Here we observe n vectors x i from (3) but not their labels y i . Theorem 2.2. Fix δ ∈ (0, 1). For any (n, p, k) → ∞ with k p → 0 andEQUATIONfor any support estimator Ŝ based on D n , as p → ∞ , then max S∈S P Ŝ ̸ = S ≥ δ.The scaling in Eq. ( 5) appeared in several prior works on related problems. Azizyan et al. (2013) showed that for λ < 1, with number of samples n < C k λ 2 log(p/k), no clustering method can achieve accuracy better than random. Verzelen & Arias-Castro (2017) studied hypothesis testing whether the data came from a single Gaussian or from a mixture of two Gaussians. In Proposition 3 of their paper, they proved that for n ≤ k λ 2 log( ep k ) max{1, λ}, any testing procedure is asymptotically powerless. Note that for k = p α with α < 1, the lower bound derived in Verzelen & Arias-Castro (2017) has a similar form to (5) with a factor of 1 -α, which is slightly smaller. Thus the bound in (5) is sharper.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-theoretic and computational lower bounds for this setting. The information lower bound is based on the results in Section 2.1 for SL and UL settings. The computational lower bound relies on the low-degree likelihood hardness conjecture. Over the past 10 years, several authors studied statistical-computational gaps for various high dimensional problems. For the sparse Gaussian mixture (3) 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-statistical gaps in a SSL setting. Our analysis, described below, shows that with relatively few labeled samples, the computational statistical gap continues to hold. In contrast, as we describe in Section 3, with a sufficiently large number of labeled samples, but not enough so solve the problem using only the labeled set, the computational-statistical gap is resolved. In particular, we present a polynomial time SSL algorithm that bridges this gap.Information Lower Bounds. Before presenting results for the mixture model (3), we analyze a more general case. We study the recovery of a latent variable S that belongs to a large finite set S, given measurements from two different modalities. Formally, the problem is to recover S from two independent sets of samples {x i } N i=1 and {z j } M j=1 of the following form,EQUATIONHere, f x (x|S) and g z (z|S) are known probability density functions. These functions encode information on S from the two types of measurements. In our SSL setting, x represents an unlabeled sample, whereas z = (x, y) a labeled one, and S is the unknown support of µ.Our goal is to derive information lower bounds for this problem. To this end, we assume that S is a random variable uniformly distributed over a finite set S, and denote by I x = I(x; S) and I z = I(z; S) the mutual information of x 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 x, N must scale at least linearly with log |S| Ix . A similar argument applies to z. For further details, see Scarlett & Cevher (2021) . The following theorem states a general non-asymptotic information-theoretic result for recovering S 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. Theorem 2.3. Fix δ ∈ (0, 1). Let N, M be integers that satisfy max {N • I x , M • I z } < (1 - δ) log |S|. Let N q = ⌊qN ⌋ and M q = ⌊(1 -q)M ⌋, for q ∈ [0, 1].P Ŝ ̸ = S > δ - log 2 log |S| .This theorem implies that with any convex combination of samples from the two modalities, qN from the first and (1 -q)M from the second, accurate recovery of S is 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 2.1 and 2.2 yields the following information lower bound for the semi-supervised case.Corollary 2.4. Let D L and D n be sets of L and n i.i.d. labeled and unlabeled samples from the mixture model (3). Fix δ ∈ (0, 1). Let (L 0 , n 0 , p, k) → ∞, with k p → 0, be such thatL 0 < 2(1 -δ)k λ log (p -k + 1) , n 0 < 2(1 -δ)k λ 2 log (p -k + 1) max {1, λ} .Suppose the number of labeled and unlabeled samples satisfy L = ⌊qL 0 ⌋ and n = ⌊(1 -q)n 0 ⌋ for some q ∈ [0, 1]. Then, for any estimator Ŝ based onD L ∪ D n , as p → ∞ max S∈S P Ŝ ̸ = S ≥ δ.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-PCA and sparse Gaussian mixture models (Löffler et 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 n i.i.d. samples. Specifically, denote the null distribution of n samples by Q n , whereby all x i ∼ Q, and denote by P n the alternative distribution, with all x i ∼ P.Under the low-degree framework, one analyzes how well can the distributions P n and Q n be distinguished by a low-degree multivariate polynomial f : R p×n → R. The idea is to construct a polynomial f which attains large values for data from P n and small values for data from Q n . Specifically, the following metric plays a key role in this framework,EQUATIONwhere the maximum is over polynomials f of degree at most D. The value ∥L ≤D n ∥ characterizes how well degree-D polynomials can distinguish P n from Q n . If ∥L ≤D n ∥ = O(1), then P n and Q n cannot be distinguished via a 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 Q n and P n be two distinct distributions. Suppose that there exists D = ω(log(pn)) for which ∥L ≤D n ∥ remains bounded as p → ∞. Then, there is no polynomial-time test T : R p×n → {0, 1} that satisfiesE X∼Pn [T (X)] + E X∼Qn [1 -T (X)] = o(1).In simple words, Conjecture 2.5 states that if ∥L ≤D n ∥ = O(1) as p → ∞, then it is not possible to distinguish between P n and Q n using a polynomial-time algorithm, as no test has both a low false alarm as well as a low mis-detection rate (the two terms in the equation above).We now show how to extend this framework, focused on unsupervised detection, to our SSL setting. To this end, consider L + n samples, distributed according to either a null distribution Q L+n or an alternative distribution P L+n . In our case, the null distribution isEQUATIONwhereas the alternative belongs to the following set of distributions, P L+n :EQUATIONHere, S is uniformly distributed over S, µ S (j) = λ k 1{j ∈ S}, and y i are 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 k = ⌊c 1 p α ⌋, L = ⌊ 2βk λ log(p -k)⌋, n = ⌊c 2 k γλ 2 ⌋ and D = (log p) 2 , for some β, γ, λ, c 1 , c 2 ∈ R + and α ∈ (0, 1 2 ). With the null and alternative distributions defined in (8) and (9), if β < 1 2 -α and γ < 2, then as p → ∞ ∥L ≤D L+n ∥ 2 = O(1).Theorem 2.6 together with the hardness conjecture 2.5 extends to the SSL case previous computational lower bounds that were derived only in UL settings (β = 0) (Fan et al., 2018; Löffler et al., 2022) . Next, we make several remarks regarding the theorem.SSL statistical-computational gap. In the rectangular region β < 1 2 -α and 1 < γ < 2, depicted in orange in Figure 1 , under the hardness conjecture 2.5, distinguishing between P and Q is computationally hard. Since testing is easier than variable selection and classification (Verzelen & Arias-Castro, 2017; Fan et al., 2018) , in this region these tasks are computationally hard as well.Tightness of condition γ < 2 in Theorem 2.6. This condition is sharp, since for γ ≥ 2, namely n ≳ k 2 λ 2 , the support can be recovered by a polynomial-time algorithm, such as thresholding the covariance matrix followed by PCA, see Deshpande & Montanari (2014) and Krauthgamer et al. (2015) .Tightness of condition β < 1 2 -α.This condition is tight for detection, though not necessarily for feature selection or classification. The reason is that for β > 1 2 -α, it is possible to distinguish between P and Q, using only the labeled data (Ingster, 1997; Donoho & Jin, 2004) .Combining Theorems 2.1-2.6 leaves a rectangular region 1 < γ < 2 and 1 2 -α < β < 1 -α where SSL support recovery is feasible from an information view, but we do not know if it possible in a computationally efficient manner. In the next section we present a polynomial time SSL method that in part of this rectangle, depicted in blue in Figure 1 , 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 D L , D n be sets of L and n i.i.d. labeled and unlabeled samples from the model (3). Assume, as in Theorem 2.6 that k ∝ p α , L = ⌊ 2βk λ log(p -k)⌋ and n ∝ k γ λ 2 .Then in the white region depicted in Figure 1 , no polynomial-time algorithm is able to recover the support S or to construct an accurate classifier. 
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 1 it 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 4 ∆µ∆µ ⊤ + I p . This is a rank-one spiked covariance model, whose leading eigenvector is ∆µ, up to a ± sign. Hence, with enough unlabeled data, ∆µ can be estimated by vanilla PCA on the sample covariance or by some sparse-PCA procedure taking advantage of the sparsity of ∆µ. Unfortunately, in high dimensions with a limited number of samples, these procedures may output quite inaccurate estimates, see for example Nadler (2008) ; Birnbaum et al. (2013) . The main idea of our approach is to run these procedures after an initial variable screening step that uses the labeled data to reduce the dimension.Our SSL scheme, denoted LSPCA, stands for Label Screening PCA. As described in Algorithm 1, LSPCA has two input parameters: the sparsity k and a variable screening factor β < 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 on the estimated support.The first stage screens variables using only the labeled samples. While our setting is different, this stage is similar in spirit to Sure Independence Screening (SIS), which was developed for highdimensional regression (Fan & Lv, 2008) . To this end, our scheme first constructs the vector,EQUATIONwhereL + = |{i ∈ [L] : y i = 1}| and L -= L -L + . With a balanced mixture P(Y = ±1) = 1 2 , it follows that w L ≈ ∆µ + 2 √ L N (0, I p ).Hence, w L can be viewed as a noisy estimate of ∆µ. If the number of labeled samples were large enough, then the top k coordinates of w L would coincide with the support of ∆µ. With few labeled samples, while not necessarily the top-k, the entries of w L at Algorithm 1 LSPCAInput: D L = {(x i , y i )} L i=1 , D n = {x i } L+n i=L+1 , parameters k, βStep I: Labeled Data Compute w L via Eq. ( 10) Select its top p (1-β) entries, denoted by S LStep II: Unlabeled Data Compute the sample covariance Σ| S L by Eq. ( 11) Compute leading eigenvector vPCA of Σ| S L Set Ŝ to be the top k entries of |v PCA | Compute leading eigenvector v of Σ| Ŝ Output: Estimated support Ŝ, and vector v.the support indices still have relative large magnitudes. Given the input parameter β > 0, the scheme retains the indices that correspond to the largest p 1-β entries in absolute value of w L . We denote this set by S L . Note that for any β > 0, this step significantly reduces the dimension (as β > 0 then p 1-β ≪ p). In addition, as analyzed theoretically in the next section, for some parameter regimes, this step retains in S L (nearly all of) the k support indices. These two properties are essential for the success of the second stage, which we now describe.The second step estimates the support S using the unlabeled data. Specifically, LSPCA constructs the sample covariance matrix restricted to the set S L ,EQUATIONwhere x = 1 n n+L i=L+1 x i is the empirical mean of the unlabeled data. Next, it computes the leading eigenvector vPCA of Σ| S L . The output support set Ŝ consists of the k indices of vPCA with largest magnitude. Finally, the vector ∆µ 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 = p 1-β . Despite this reduction in dimension, as long as the vector ∆µ is sufficiently sparse with k ≪ p, or equivalently α < 1 -β, then in the second step our goal is still to find a 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 as LS 2 PCA (Labeled Screening Sparse-PCA). As illustrated in the simulations, for finite sample sizes, this can lead to improved support recovery and lower classification errors.Before presenting our main result, we first recall two standard evaluation metrics. The classification error of a classifier C : R p → {±1} is defined as R(C) = P(C(x) ̸ = y). Its excess risk is defined asEQUATION)As in Verzelen & Arias-Castro (2017) , the accuracy of a support estimate Ŝ is defined by its normalized overlap with the true support, namely | Ŝ ∩ S|/k. To simplify the analysis, we focus on the symmetric setting where µ 1 = -µ -1 = µ. 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 D L , D n be labeled and unlabeled sets of L and n i.i.d. samples from (3) with a ksparse µ whose non-zero entries areEQUATIONand the excess risk of the corresponding classifierEQUATIONThe interesting region where Theorem 3.2 provides a non-trivial recovery guarantee is the triangle depicted in blue in Figure 1 . 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 knowledge, our work is the first to rigorously prove the computational benefits of SSL, in bridging the computational-statistical gap in high dimensions. As mentioned above, we conjecture that in the remaining white region in Figure 1 , it is not possible to construct in polynomial time an 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 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. 
simulation results: 
 We illustrate via several simulations some of our theoretical findings. Specifically, we compare LSPCA and LS 2 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 2 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 µ whose non-zero entries are ± λ/k. The quality of a support estimate Ŝ is measured by its normalized accuracy | Ŝ ∩ S|/k. For all methods compared we assume the sparsity k is known. Hence, each method outputs a k-sparse unit norm vector μ, so its corresponding linear classifier is x → sign ⟨ μ, x⟩. Given the model (3), its generalization error is Φ c (⟨ μ, µ⟩). We run our SSL schemes with β = β -(β -(1 -γα))/4 which satisfies the requirements of Theorem 3.2. We present experiments with p = 10 5 , k = p 0.4 = 100 and λ = 3, though the behavior is similar for other settings as well. The error of the Bayes classifier is Φ c ( √ λ) ≈ 0.042. We report the average (with ±1 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 to n unlabeled ones. We compare our SSL schemes LSPCA and LS 2 PCA to the following UL methods, taking all L + n samples as unlabeled: ASPCA (Birnbaum et al., 2013) , and IPU (Tian et al., 2020) . The SSL methods that we compare are LSDF (Zhao et al., 2008) , and self-training (self-train). The self-training algorithm is similar to the approach in Oymak & Gulcu (2021) , but explicitly accounts for the known sparsity k: (i) compute w L of (10) using the labeled samples, and keep its k largest entries, denote the result by w(k) L ; (ii) compute the dot products c i = ⟨w (k)L , x i ⟩ and the pseudo labels ỹi = sign(c i ); (iii) let n eff be the cardinality of the set {i : |c i | > Γ}, for some threshold value Γ ≥ 0; (iv) estimate the support by the top-k coordinates in absolute value of the following vector:w self = 1 L + n eff L i=1 y i x i + L+n i=L+1 1{|c i | > Γ}ỹ i x iIn the experiments we used Γ = 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 L | of (10). As shown in the supplementary, this is the maximum-likelihood estimator for S based on the labeled data.Figure 2 illustrates our key theoretical result -that in certain cases SSL can yield accurate classification and feature selection where SL and UL simultaneously fail. The left panel of Figure 2 shows the average accuracies of support estimation for the different schemes as a function of number of unlabeled samples n. Except at small values of n, LS 2 PCA 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 error while SL and UL schemes have much higher errors.We present further experiments that empirically illustrate the benefit of using a fixed number of n = 1000 unlabeled samples while varying the number of labeled samples L. Specifically, we We first present several auxiliary lemmas used to prove our theorems. We denote the complement of the standard normal cumulative distribution function by Φ c (t) = P (Z > t), where Z ∼ N (0, 1). The following lemma states a well known upper bound on Φ c . Lemma A.1. For any t > 1,EQUATION)Lemma A.2 (Chernoff (1952) ). Suppose {x i } n i=1 are i.i.d. Bernoulli random variables, with Pr[x i = 1] = q. Let X denote their sum. Then, for any δ ≥ 0,EQUATIONand for any δ ∈ [0, 1]EQUATION)A common approach to prove lower bounds is using Fano's inequality. Here, we use the following version of Fano's lemma, see Yang & Barron (1999) . Lemma A.3. Let θ be a random variable uniformly distributed over a finite set Θ. Let z 1 , z 2 , . . . , z n be n i.i.d. samples from a density f (z|θ). Then, for any estimator θ(z 1 , . . . , z n ) ∈ Θ,EQUATIONwhere I(θ; Z n ) is the mutual information between θ and the samplesZ n = (z 1 , z 2 , . . . , z n ).In our proofs we use several well known properties of the entropy function. For convenience we here state some of them. First, we recall the explicit expression for the entropy of a multivariate Gaussian. Lemma A.4. Let x ∼ N (µ, Σ). Then, its entropy is given byEQUATIONNext, the following lemma states that the multivariate Gaussian distribution maximizes the entropy over all continuous distributions with the same covariance (Cover & Thomas, 2006, pg. 254 ). Lemma A.5. Let x be a continuous random variable with mean µ ∈ R p and covariance Σ ∈ R p×p , and let y ∼ N (µ, Σ). If the support of x is all of R p thenEQUATIONThe next lemma states the sub-additive property of the entropy function.Lemma A.6. Let x and y be jointly distributed random variables. Then,EQUATION)To prove Theorem 2.2 we use the following lemma.Lemma A.7. Let λ ∈ (0, 1), and let k be a positive integer. Then, for w ∼ N (0, k-1 k )E tanh(λ + √ λw) - 1 2 tanh 2 λ + √ λw ≤ 1 2 λ + 3 λ/k (22) Proof of Lemma A.7. Let q(w) = tanh(λ + √ λw) -tanh 2 (λ + √ λw).In terms of q(w), the left hand side of ( 22) may be written as followsEQUATION)We now upper bound the two terms in the RHS of ( 23). We start by showing that E [q(w)] ≤ 3 λ/k. Let L q = max w∈R |q ′ (w)| be the Lipschitz constant of the function q(w). It is easy to show that L q ≤ 3 √ λ. Let z ∼ N (0, 1) be independent of w. Using the first order Taylor expansion yieldsEQUATIONNext, note that (w + 1√ k z) ∼ N (0, 1). Therefore E w,z q w + 1 √ k z = ∞ -∞ q(v) e -v 2 /2 √ 2π dv = ∞ -∞ tanh(λ + √ λv) -tanh 2 (λ + √ λv) e -v 2 /2 √ 2π dv.Making a change of variables x = λ + √ λv, givesE w,z q w + 1 √ k z = ∞ -∞ tanh(x) -tanh 2 (x) e -(x-λ) 2 /2λ √ 2πλ dx. Define t λ (x) = tanh(x) -tanh 2 (x) e -(x-λ) 2 /2λ √ 2πλ. Note that t λ (x) is an absolutely integrable function which satisfies t λ (x) = -t λ (-x) for any λ. Therefore, the above integral is equal to zero, namely ∞ -∞ t λ (x)dx = 0. Inserting this into (24) givesEQUATIONNext, we upper bound the first term on the RHS of Eq. ( 23). Denote by f W (w) the probability density function of w ∼ N (0, k-1 k ). Then, writing the expectation explicitly givesE tanh(λ + √ λw) = ∞ -∞ tanh(λ + √ λw)f W (w)dw.Making the change of variables x = λ + √ λw yieldsE tanh(λ + √ λw) = 1 √ λ ∞ -∞ tanh(x)f W x-λ √ λ dx = 1 √ λ ∞ 0 tanh(x) f W x-λ √ λ -f W x+λ √ λ dx. Since λ > 0, it follows that f W x-λ √ λ -f W x+λ √ λ≥ 0, for all x ≥ 0. Therefore, to bound this expectation it suffices to construct a function g(x) such that g(x) ≥ tanh(x) for any x ≥ 0 and for which we can compute explicitly the corresponding integral. Consider the function g(x) = x. It is well-known that x ≥ tanh(x), for all x ≥ 0. Thus,EQUATIONCombining ( 23),( 25) and ( 26) givesE tanh(λ + √ λw) - 1 2 tanh 2 λ + √ λw ≤ 1 2 λ + 3 λ/k .Lemma A.8. Consider a sequence of classification problem of the form,y ∼ Unif{±1}, x|y ∼ N (yµ, I p ),where the dimension p → ∞ but ∥µ∥ = √ λ is fixed. Let μp be a sequence of unit norm estimators and T p (x) = sign( μp , x) the corresponding classifier. Assume that every ϵ > 0EQUATION)Then, the excess risk of the classifier T p (x) = sign⟨ μp , x⟩ tends to zero as p tends to infinity.Proof. By definition, the excess risk of the classifier T p that corresponds to μp can be written asE(T p ) = P ξ∼N (0,Ip) (⟨ μp , µ + ξ⟩ < 0) -Φ c ( √ λ).Since ξ is independent of μp and μp has unit norm, then z = ⟨ μp , ξ⟩ ∼ N (0, 1), and the excess risk may be written asE(T p ) = P(z > ⟨ μp , µ⟩) -Φ c ( √ λ)Let ϵ > 0, and consider the eventA ϵ = {⟨µ/ √ λ, μp ⟩ > 1 -ϵ}. Then, E(T p ) ≤ Φ c ( √ λ(1 -ϵ)) -Φ c ( √ λ) with probability P(A ϵ ) 1with probability 1 -P (A ϵ )Since by assumption P(A ϵ ) → 1 for any ϵ > 0, then the excess risk tends to zero as p → ∞.B.1 Proof of Theorem 2.1Our proof relies on Fano's inequality, and is conceptually similar to the proof of Theorem 3 in Amini & Wainwright (2009) . First, note that for any sub-collection S ⊂ S, we have the followingmax S∈S P Ŝ ̸ = S ≥ 1 | S| S∈ S P Ŝ ̸ = S .The right hand side in the above display is the error probability of an estimator Ŝ, where S is considered as a random variable uniformly distributed over the set S. In other words, the right hand side may be written as follows,P (error) = s∈ S P Ŝ ̸ = s | S = s • P (S = s) .In our proof, we consider the following sub-collectionEQUATIONwhich consists of all k-element subsets that contain the first k -1 support indices {1, . . . , k -1} and one from {k, . . . , p}. 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 µ j = λ k 1{j ∈ S}. So, with S known, µ is deterministic and we write it as µ S .In the proof we consider an equivalent model of (3), whose observations are divided by √ λ,x i = y i θ S + σξ i , i = 1, . . . , L, where θ S (j) = 1 √ k 1{j ∈ S}, σ = 1 √λ and ξ i ∼ N (0, I p ). Since for each observation x i we also know its corresponding label y i ∈ {-1, 1}, we may consider the following transformed observationsEQUATIONwhere ξi = y i ξ i has the same distribution as ξ i . Denote by X L , XL , Y L the sets of L i.i.d. samples {x i } L i=1 , {x i } L i=1 and {y i } L i=1 , respectively. To apply Fano's lemma, we consider the joint mutual information I (X L , Y L ); S . Note that,I X L , Y L ; S = I XL , Y L ; S = I XL ; S ,where the last equality follows from the fact that the labels Y L are independent of the support S and the observations XL . Hence, it is enough to consider the samples XL from the model in (29).Let S be a subset chosen uniformly at random from S. Then, from Lemma A.3, it follows thatEQUATION)We now derive an upper bound on I( XL ; S). First, from the relation between mutual information and conditional entropy, I( XL ; S) = H( XL ) -H( XL |S). By the sub-additivity of the entropy function H( XL ) ≤ LH(x). Also, since the samples xi are conditionally independent given S, the joint entropy H( XL |S) can be expressed asH( XL |S) = i∈[L] H(x i |S) = LH(x|S).where x is a single observation from the model (29). Therefore,EQUATIONBy the definition of conditional entropy,H(x|S) = - s∈ S P (S = s) f (x|S) log f (x|S)dx,where f (x|S) the probability density function of a single random sample x given S. For any S ∈ S, the vector (x | S) is a p-dimensional Gaussian with mean θ S and covariance matrix σ 2 I p . Its entropy is independent of its mean, and is given by p 2 1 + log(2πσ 2 ) . Hence,EQUATION)The final step is to upper bound H(x). To this end, note that x is distributed as a mixture of (p-k +1) Gaussians, each centered at θ S for S ∈ S. Let us denote its mean and covariance by ν x = E [x] and Σ = E (x -ν x )(x -ν x ) T , respectively. By the maximum entropy property of the Gaussian distribution (Lemma A.5), and Eq. ( 19) for the entropy of a multivariate Gaussian, we haveEQUATIONCombining ( 31), ( 32) and (33) givesEQUATION)The following lemma, proved in Appendix D, provides an upper bound for log det(Σ). Lemma B.1. Let Σ be the covariance matrix of the random vector x of Eq. (29), with the set S uniformly distributed on S of Eq. (28). Then,EQUATION)Substituting this upper bound into (34) leads toEQUATIONwhere the last inequality follows from log(1 + x) ≤ x, for all x > 0. Inserting (36) into (30), implies that a sufficient condition for the error probability to be greater than δ -log 2 log(p-k+1) is Lλ k < 2(1 -δ)log(p -k + 1), which completes the proof.To prove Theorem 2.2 we use the following lemma, proven in Appendix D. Lemma B.2. Let x be a random vector from the model (3), with a vector µ S , where the random variable S is uniformly distributed over the set S of Eq. (28), and let I(x; S) be their mutual information. Consider an asymptotic setting where p → ∞ and k/p → ∞. Then, for λ < 1, and for p and k sufficiently large with k/p sufficiently smallEQUATIONFirst, note that for λ ≥ 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 {(x i , y i )} L i=1 , includes in particular all unsupervised estimators that ignore the labels. Hence, for λ ≥ 1, Theorem 2.2 follows from Theorem 2.1. Therefore, we consider the case λ < 1.The proof, similar to that of Theorem 1, is also based on Fano's inequality. To lower bound the probability of error, we view S as a subset uniformly distributed over S, where S is the sub-collection of support sets defined in (28). Then, using the same arguments as in the proof of Theorem 1, maxEQUATION)where X n = (x 1 , ..., x n ) and I(X n ; S) is the mutual information between the n unlabeled samples and S.We now derive an upper bound for I(X n ; S). The sub-additivity of the entropy function, and the fact that x i are conditionally independent given S = s, implyEQUATIONwhere x is a single sample from the model (3). Hence, for p and k sufficiently large, with k/p sufficiently small, combining (37) and (39) gives I(X n ; S) ≤ nλ 2 2k (1 + o(1)). By Fano's bound in (38), the error probability is at least δ if n < 2(1-δ)k λ 2 log(p -k + 1) .Recall that the random variable S is uniformly distributed over the set S. For X Nα = {x i } Nα i=1 and Z Mα = {z i } Mα i=1 , their combined mutual information with the random variable S isI(X Nα , Z Mα ; S) = H(X Nα , Z Mα ) -H(X Nα , Z Mα |S).Since the two sets of samples {x i } Nα i=1 , {z j } Mα j=1 are conditionally independent given S = s, thenEQUATION)By the sub-additivity property of the entropy function,EQUATIONHence, combining (40) and (41) yieldsEQUATION)Combining Fano's inequality with the upper bound in (42) givesP Ŝ ̸ = S ≥ 1 - N α • I x + M α • I z + log 2 log |S| .Finally, the assumption max{N• I x , M • I z } < (1 -δ) log |S| yields that P Ŝ ̸ = S > δ -log 2 log |S| □ B.To lower bound the error probability, we view S as a random variable uniformly distributed over the discrete set S defined in (28). By the same arguments as in the proofs of Theorems 1 and 2, maxS∈S P Ŝ ̸ = S ≥ P S∼U ( S) Ŝ ̸ = S .We apply Theorem 2.3, with the set x i of i.i.d. unlabeled samples from (3), and the second set z i = (x i , y i ) of i.i.d. labeled samples from model (3).Next, in the proofs of Theorems 2.1 and 2.2 the following upper bounds for I z and I x were derived,EQUATIONFinally, by the conditions of the Corollary, the number of labeled and unlabeled samples satisfyL = ⌊qL 0 ⌋ and n = ⌊(1 -q)n 0 ⌋, with L 0 < 2(1-δ)k λ log (p -k + 1) and n 0 < 2(1-δ)k λ 2log (p -k + 1) max{1, λ}. Hence, for sufficient large p, combining these conditions with (43) givesL 0 • I z , n 0 • I x ≤ (1 -δ) log(p -k + 1)Therefore, by Theorem 2.3 the error probability is at least δ. □Even though we analyze a SSL setting, the observed data still belongs to the additive Gaussian noise model (see Section 2 in Kunisky et al. (2022) ). This key point allows to simplify the low-degree norm in our setting. Specifically, let Z = (z 1 , . . . , z L+n ) be the following set of random vectors, which are the noise-free underlying signals from the alternative P L+n of Eq. ( 9) in the main text,z i = µ S , i ∈ [L], y i µ S , L < i ≤ L + n.In the equation above, S is uniformly distributed on S (the set of all size-k subsets over p variables), µ S is a k-sparse vector with support S and non-zero entries λ/k and y i are Rademacher random variables. Similarly, let Z = (z 1 , . . . , zL+n ) be an independent set of the underlying noise-free signals, with a possibly different support S, and independent labels ỹi . Then, by Theorem 1 in Kunisky et al. (2022) the low degree norm ∥L D L+n ∥ 2 can be expressed as∥L D L+n ∥ 2 = E Z, Z   D d=0 1 d! L+n i=1 ⟨z i , zi ⟩ d   .Inserting the expressions for z i and zi into the equation above, gives∥L D L+n ∥ 2 = D d=0 1 d! E   L i=1 µ S , µ S + L+n i=L+1 y i µ S , ỹi µ S d   ,where the expectation is over the two random sets S, S and over the random labels y i and ỹi . Since all these random variables are independent, the right hand side above simplifies toD d=0 1 d! E   L µ S , µ S + L+n i=L+1 y i ỹi µ S , µ S d   = D d=0 1 d! E   µ S , µ S L + L+n i=L+1 y i ỹi d   .Denote R i = y i ỹi , and note that R i are Rademacher random variables, independent of S and S. Thus, the expectation above can be factored into the product of two separate expectations,EQUATIONWe now separately analyze each of these two expectations, starting from the second one. By the Binomial formula,E   L + L+n i=L+1 R i d   = d ℓ=0 d ℓ L d-ℓ E   L+n i=L+1 R i ℓ   .Note that for any odd integer ℓ, the ℓ-th moment of the Rademacher's sum is zero. Therefore,E   L + L+n i=L+1 R i d   = ⌊d/2⌋ ℓ=0 d 2ℓ L d-2ℓ E   L+n i=L+1 R i 2ℓ   .As analyzed in Löffler et al. (2022 Löffler et al. ( , pg. 1274 )EQUATIONNext, we analyze the first expectation E S, S ⟨µ S , µ S ⟩ d in (44). Recall that µ S j = λ k 1{j ∈ S}.Hence, ⟨µ S , µ S ⟩ = λ k |S ∩ S|. Denote by G = |S ∩ S| the size of the overlap between the sets. Then G is a hypergeometric random variable with the following probability distribution, for 0 ≤ m ≤ k,P(G = m) = k m p -k k -m p k -1 .From (Johnson et al., 2005, pg.268) this probability is upper bounded as followsP(G = m) ≤ k m k p -k m . Therefore, E S, S ⟨µ S , µ S ⟩ d = λ d k d E |S ∩ S| d = λ d k d k m=0 m d P(G = m) ≤ λ d k d k m=0 m d k m k p -k m . (46)Inserting ( 45) and ( 46) into (44) gives∥L D L+n ∥ 2 ≤ D d=0 λ d d!k d L + nd 2L d k m=0 m d k m k p -k m .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∥L D L+n ∥ 2 ≤ k m=0 k m k p -k m D d=0 1 d! m Lλ k + nλD 2Lk d ≤ k m=0 k m k p -k m exp m Lλ k + nλD 2Lk .According to the conditions of the Theorem, L = ⌊ 2βk λ log(p -k)⌋ and n = ⌊c 2 k γ λ 2 ⌋ for some c 2 > 0 and γ < 2. Hence, for sufficiently large p, L > βk λ log(p -k). Then, inserting these values into the above gives∥L D L+n ∥ 2 ≤ k m=0 k m k p -k m exp m 2β log(p -k) + c 2 k γ D 2βk 2 log(p -k).Setting D = (log(p -k)) 2 , yields ∥L D L+n ∥ 2 ≤ k m=0 k m k p -k m exp m log(p -k) 2β + c 2 2β 1 k 2-γ .Since γ < 2, for any fixed ϵ > 0 it follows that c2k γ 2βk 2 ≤ ϵ for sufficiently large k. Thereforeexp m log(p -k) 2β + c 2 2β 1 k 2-γ ≤ exp (m log(p -k) (2β + ϵ)) = (p -k) m(2β+ϵ)Combining the above two displays gives∥L D L+n ∥ 2 ≤ k m=0 k m k p -k m (p -k) m(2β+ϵ) = k m=0 k m k (p -k) 1-2β-ϵ m = 1 + k (p -k) 1-2β-ϵ k .Finally, recall that by the assumptions of the theorem, k = ⌊c 1 p α ⌋ for some α ∈ (0, 1 2 ), c 1 > 0 and that β < 1 2 -α. Choosing ϵ = 1 2 -α -β > 0, gives∥L D L+n ∥ 2 ≤ 1 + k (p -k) 1/2+α-β k .Since k = ⌊c 1 p α ⌋, then as p → ∞, the above behaves as1 + c 1 p 1/2-β (1 + o(1)) c1p α Therefore, for β < 1 2 -α, as p → ∞, ∥L D L+n ∥ 2 → O(1). □ C SSL Algorithm C.1 Proof of Theorem 3.2We prove the theorem, assuming that LSPCA is run with the correct sparsity k and with a slightly smaller screening factor β = β -ε for a fixed (though potentially arbitrarily small) ε > 0, which implies the first stage retains a bit more than p 1-β of the original p variables.Our proof relies on the following two key properties: (i) The set S L of size p = ⌈p 1-β ⌉, which is the output of the first step of LSPCA, contains nearly all indices of the true support; (ii) since the reduced dimension p ≪ 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.Lemma C.1. Let {(x i , y i )} L i=1 be L i.i.d. labeled samples from the mixture model (3) with a vector µ of sparsity k = ⌊c 1 p α ⌋ and nonzero entries ± λ/k. Suppose that L = 2βk log(p-k) λ , for some β ∈ (0, 1 -α). Let β = β -ε where ε > 0 is sufficiently small so that β > 0. Let S L be the indices of the top p = ⌈p 1-β ⌉ entries of the vector w L of Eq. (10). Then, for any ϵ > 0,EQUATION)Proof of Theorem 3.2. As described above, we run LSPCA with β = β -ε, and denote by S L the set found by the first step of the algorithm. By Lemma C.1 this set satisfies Eq. ( 47). Denote by Σ| S L and Σ| S L the population and sample covariance matrices restricted to the set of indices S L . Note that, Σ| S L = µ| S L µ| ⊤ S L + I p. Hence, up to sign, the leading eigenvector of Σ| S L is µ| S L ∥µ| S L ∥ . Denote by vPCA the unit norm leading eigenvector of the sample covariance Σ| S L . We now show that these two eigenvectors are close to each other. Indeed, since β > 1 -αγ, we have n/p = p αγ /λ 2 (p 1-β * ) → ∞, as p → ∞. Then, combining this observation with Theorem 2.3 in (Nadler, 2008) , implies that with probability tending to 1,lim p→∞ vPCA , µ| S L ∥µ| S L ∥ = 1.Since µ ∈ R p is a k-sparse with non-zero entries ± λ k , Eq. ( 47) implies that ∥µ|EQUATIONwhich implies that with the correct sign,lim p→∞ vPCA - µ| S L √ λ = 0.From now we extend vPCA which originally had dimension |S L , to a p-dimensional vector with zeros in S c L . Hence, since ∥µ| S c L ∥ → 0, it follows lim p→∞ vPCA -EQUATION)Next, let us assume by contradiction that there exist ϵ 0 , δ 0 ∈ (0, 1) such that for every p ∈ N, with probability at leastδ 0 |S ∩ Ŝ| k < 1 -ϵ 0 .where Ŝ is the set of top-k coordinates of |v PCA |. Combining this assumption and Eq. ( 49), with probability at least δ 0EQUATION)where the last inequality follows from the above assumption and |µ j | = λ/k, for all j ∈ S.Next, from ( 47) and ( 49) it follows that for any subset T that satisfiesS L ∩ S ⊂ T ⊂ S L and |T | = k, lim p→∞ ∥v PCA | T ∥ 2 = lim p→∞ 1 λ ∥µ| T ∥ 2 = lim p→∞ |S ∩ S L | k = 1. (51)However, since Ŝ is the set of the top-k indices of |v PCA |, for any|T | = k, T ⊂ S L vPCA | Ŝ ≥ vPCA | T ,which is a contradiction to ( 50) and ( 51). Hence, for any ϵ > 0, as p tends to infinity,P |S∩ Ŝ| k ≥ 1 -ϵ → 1, which completes the first part of the proof.The second part of the proof follows from combining (48) and Lemma A.8.Proof of Lemma B.1. First, note that the mean ν x = E [x] = E S θ S is given by(ν x ) j = 1 √ k 1 ≤ j ≤ k -1 1 √ k 1 p-k+1 k ≤ j ≤ p.To derive an explicit expression for the covariance matrix Σ we use the law of total expectationEQUATION)whereEQUATION)whereu = 0 ⊤ k-1 , 1 ⊤ p-k+1⊤ and {e j } j∈[p] denote the standard basis of R p . Since ξ is independent of S, inserting ( 53) into ( 52) givesΣ = 1 p -k + 1 p j=k E 1 √ k e j - 1 (p -k + 1) u + σ ξ 1 √ k e j - 1 (p -k + 1) u + σ ξ ⊤ = 1 k(p -k + 1) 2   (p -k + 1) p j=k e j e T j -   u p j=k e ⊤ j + p j=k e j u ⊤   + uu ⊤   + σ 2 I pp j=k e j = u. Thus,Σ = 1 k(p -k + 1) 2   (p -k + 1) p j=k e j T j -uu ⊤   + σ 2 I p ⪯ 1 k(p -k + 1) p j=k e j e T j + σ 2 I p = 1 k(p -k + 1) 0 (k-1)×(k-1) 0 (k-1)×(p-k+1) 0 (p-k+1)×(k-1) I (p-k+1)×(p-k+1) + σ 2 I p .Therefore,log det (Σ) ≤ log (σ 2 ) p 1 + 1 k(p -k + 1)σ 2 p-k+1 = p log σ 2 + (p -k + 1) log 1 + 1 k(p -k + 1)σ 2 .Proof of Lemma B.2. By definition I(x; S) = H(x) -H(x|S). Hence, we first derive expressions for these two terms. Since x follows the mixture model (3), it is of the form x = yµ S + ξ. Given S = s, µ s is deterministic with µ s j = λ k 1{j ∈ s}. Thus, the vector (x|S = s) is distributed as a mixture of two Gaussians with centers ±µ s and identity covariance matrix. Its density isf (x|S = s) = 1 (2π) p/2 e -∥x-µ s ∥ 2 /2 + e -∥x+µ s ∥ 2 /2 2 = e -∥x∥ 2 +λ 2 (2π) p/2e -⟨x,µ s ⟩ + e ⟨x,µ s ⟩ 2 .(54)By the definition of conditional entropy,H(x|S) = - s∈ S P (S = s) f (x|S = s) log f (x|S = s)dx.Given the structure of the vectors µ s for all s ∈ S, all the integrals in the sum above give the same value. Therefore, it suffices to consider a single set s 0 = {1, . . . , k},EQUATIONInserting ( 54) into (55), givesH(x|S) = -E x|s0 log e -∥x∥ 2 +λ 2 (2π) p/2 cosh(⟨x, µ s0 ⟩) .Note that for any s ∈ S, E ∥x∥ 2 S = s = λ + p. Thus,EQUATIONwhere C(p, λ) = λ + p 2 (1 + log(2π)). Consider the following two independent random variables, w = 1√ k k-1 j=1 ξ j ∼ N 0, k-1 k and ξ = ξ k ∼ N (0, 1). For S = s 0 , ⟨x, µ s0 ⟩ = ⟨yµ s0 + ξ, µ s0 ⟩ = λy + √ λw + √ λ √ k ξ.Inserting the above into (56) givesH(x|S) = C(p, λ) -E log cosh(λy + √ λw + λ/kξ) ,where the expectation is over w, 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 a symmetry argument we may set y = 1 and take the expectation only over w and ξ. This givesEQUATIONNext, we derive an expression for H(x). Recall that x depends on a vector µ S with S distributed uniformly at random from S of size p -k + 1. Note that S = p ℓ=k s ℓ where s ℓ = [k -1] ∪ {ℓ}. By the law of total probabilityf (x) = 1 | S| s∈ S f (x|S = s) = 1 p -k + 1 p ℓ=k f (x|S = s ℓ ).Using the same analysis as before, it follows thatf (x) = e -∥x∥ 2 +λ 2 (2π) p/2 • 1 p -k + 1 p ℓ=k e -⟨x,µ s ℓ ⟩ + e ⟨x,µ s ℓ ⟩ 2 .Hence,EQUATIONWe now simplify the expectation in (58). First, by a symmetry argument, we may assume the label that corresponds to x is simply y = 1. Let us simplify the inner product ⟨x, µs ℓ ⟩. ⟨x, µ s ℓ ⟩ = ⟨ √ λµ S + ξ, µ s ℓ ⟩ = λ k -1 k + 1 {ℓ ∈ S} k + √ λw + √ λ √ k ξ ℓ .Hence, the expectation above can be written asE   log   1 p -k + 1 p ℓ=k e -λ (k-1) k + √ λw+ √ λ/kξ ℓ + λ k 1{ℓ∈S} + e λ k-1 k + √ λw+ √ λ/kξ ℓ + λ k 1{ℓ∈S} 2    where the expectation is over S, w and {ξ ℓ } p ℓ=k . Since S is uniformly distributed over S and for any S = s j the expectation is the same, we may thus set S = s k = [k], and take the expectation only over w and {ξ ℓ } p ℓ=k . Next, we decompose the sum inside the logarithm as S 1 + S 2 , whereS 1 = exp -λ k-1 k - √ λw 2 • 1 p -k + 1 p ℓ=k e - √ λ k ξ ℓ -λ k 1{ℓ=k} S 2 = exp λ k-1 k + √ λw 2 • 1 p -k + 1 p ℓ=k e √ λ k ξ ℓ + λ k 1{ℓ=k}We now analyze each of these terms in an asymptotic setting where p, k → ∞ and k = o(p). To this end we write the sum in S 2 as follows1 p -k + 1 p ℓ=k e √ λ k ξ ℓ + 1 p -k + 1 e √ λ k ξ k e λ k -1By the central limit theorem, asymptotically, the first sum may be written as e λ/2k + O P ( √ λ √ kp ), which follows from the fact that E Z∼N (0,1) [e tZ ] = e t 2 /2 . The second term above is O P ( √ λ kp ), which is negligible w.r.t. to the previous O P term. Note that its expectation is finite and given bye λ/2k e λ k -1 p-k+1. The sum S 1 can be analyzed similarly. In summary we obtain thatS 1 + S 2 = e λ/2k • cosh λ k -1 k + √ λw • 1 + O P √ λ √ kpHence, the expectation above simplifies toE[log(S 1 + S 2 )] = λ 2k + E log cosh λ k -1 k + √ λw + O √ λ √ kpInserting the above into (58) givesEQUATIONNext, we derive an upper-bound for the mutual information I(x; S) = H(x) -H(x|S). Combining ( 57) and ( 59), the constant C(p, λ) cancels out, and we obtainEQUATION)where g w (t) = log cosh λ + √ λw + t . For future use, note that d dt g w (t) = tanh(λ + √ λw + t).To upper bound I(x; S) we split the expectation in (60) into two parts as follows,EQUATIONThe Taylor expansion of g w (t) is given byg w (t) = g w (0) + t tanh(λ + √ λw) + t 2 2 (1 -tanh 2 (λ + √ λw)) + t 3 3! g (3) w (τ t ).Here τ t is some number between 0 and t, and g(3)w (τ t ) = -2 tanh(λ + √ λw + τ t ) + 2 tanh 3 (λ + √ λw + τ t ).Note that for all t ∈ R,t 3 3! g (3) w (τ t ) ≤ 2|t 3 | tanh(λ + √ λw + τ t ) 3! (1 -tanh 2 (λ + √ λw + τ t )) ≤ 2|t 3 | 3! .Since z, w are independent and E[z] = 0, it follows thatEQUATION)For the second term in (61), for any value of w, by the mean value theorem, it follows thatg w (0) -g w - λ k = λ k tanh(λ + √ λw + ζ w ) ≤ λ k tanh(λ + √ λw)where ζ w ∈ [-λ/k, 0], and the last inequality follows from the fact that tanh(•) is a monotonically increasing function. Hence,EQUATIONHence, combining (61), ( 62) and ( 63), yieldsEQUATIONBy Lemma A.7, the expectation above can be bounded as follows:E tanh(λ + √ λw) - 1 2 tanh 2 λ + √ λw ≤ 1 2 λ + 3 λ/k .Hence, inserting this upper bound into (64), givesI(x; S) ≤ 1 2 λ 2 k + O √ λ √ kp + λ 3 /k 3 (65) Asymptotically, as p, k → ∞ with k/p → 0 then 1 k ≫ 1 √ kp . Thus, the term 1 2 λ 2k is asymptotically larger than the O(•) terms in the display above. Hence, the inequality (37) of the lemma follows.Proof of Lemma C.1. The main idea of the proof is to show that with a suitable choice of threshold τ , nearly all entries w L (j) for j ∈ S are above this threshold, in absolute value, whereas the number of noise magnitudes above it is smaller than p -k. Since we prove the lemma for the case of two symmetric Gaussians µ 1 = -µ -1 = µ, for simplicity we consider the following formula for w L = 1 L L i=1 y i x i . With minor adaptations one can also prove the Lemma with the original formula (10) of w L .Fix ϵ > 0, and let A L denote the event that |S L ∩ S| ≥ k(1 -ϵ). For any threshold τ define the following two events,EQUATIONC(τ ) =    j / ∈S 1{|w L (j)| > τ } < p -k    .By their definition, it follows that for any τ > 0B(τ ) ∩ C(τ ) ⊆ A L .Furthermore, note that the two events B(τ ) and C(τ ) are independent. Hence, to prove that P(A L ) → 1, it suffices to prove that for a suitable threshold τ ,EQUATIONIn other words, it suffices to show that each of these events occurs with probability tending to one.We start by showing that Pr[ B(τ )] → 1. First, let us define an even simpler event, with the absolute value removed,B(τ ) =    j∈S 1{sign(µ j )w L (j) > τ } > k(1 -ϵ)   Clearly B(τ ) ⊂ B(τ ) and thus it suffices to show that P(B(τ )) → 1 as p → ∞.To this end, we consider a threshold of the form τ = λ k T , with the value of T specified below. By the sparse mixture model (3), at support coordinates,sign(µ j )w L (j) = λ k + sign(µ j ) √ L ξ jwhere ξ j ∼ N (0, 1). Inserting this expression with L ≥ 2βk log(p-k) λ into the above, and suppressing the dependence on τ in B(τ ), givesEQUATIONNext, we chooseEQUATIONand defineq 1 = P N (0, 1) > -(2β log(p -k)) 1/4 .Since the ξ j 's are all independent and |S| = k, with this choice of T , Eq. ( 67) simplifies toP (B) ≥ P (Bin(k, q 1 ) > k(1 -ϵ))Note that lim p→∞ q 1 = 1. Thus, for sufficiently large p, it holds that q 1 (1 -ϵ/2) > 1 -ϵ. Hence, instead of the right hand side above we may bound P(Bin(k, q 1 ) > kq 1 (1 -ϵ/2)). Indeed, by Chernoff's bound (17) ,P (B) ≥ 1 -e ϵ 2 kq 1 8which tends to one as p, k → ∞.Next, we show that the second term in Eq. ( 66), P( C), also tends to one as p → ∞. First of all, since k = ⌊c 1 p α ⌋ and α < 1 -β < 1 -β, then k ≪ p 1-β , and thus p -k ≪ p/2. Hence, for p sufficiently large, we may instead consider the following eventC(τ ) =    j / ∈S 1{|w L (j)| > τ } < p 2    = Bin(p -k, q 2 (τ )) < p 2where q 2 (τ ) = 2Φ c ( √ Lτ ). Clearly C(τ ) ⊂ C(τ ), and we now prove that with τ = λ k T , and T given in ( 68) P(C(τ )) → 1, by applying a Chernoff bound.To this end, we writep 2 = q 2 (p -k)(1 + δ) where δ = p 2(p-k) 1 q2 -1.To use Chernoff's inequality we first need to show that δ ≥ 0. Indeed, as p → ∞, with τ = λ k T , and using Lemma A.1 which bounds the tail function Φ c ,lim p→∞ (δ + 1) = lim p→∞ p 1- β 2(p -k) 1 2Φ c (T 2β log(p -k)) ≥ √ πβ 2 lim p→∞ T log(p -k) (p -k) β exp(-T 2 β log(p -k)) = √ πβ 2 lim p→∞ T log(p -k) (p -k) β-βT 2 (69)Note that for sufficiently large p,β -βT 2 = β(1-T 2 )-ε = β (2β log(p -k)) 1/4 2 - 1 (2β log(p-k)) 1/4 -ε < 2β (2β log(p -k)) 1/4 -ε < 0.Combining the above and (69) giveslim p→∞ (δ + 1) ≥ √ πβ 2 lim p→∞ T log(p -k) = ∞.Since β < β, for sufficiently large p, and T given in (68) it follows that β -βT 2 < 0. Therefore, for sufficiently large p, it follows that δ > 0. By Chernoff's bound ( 16)EQUATION)We now prove that the term in the exponent tends to infinity. First, note that since δ → ∞ then δ= p 2(p-k)q2 -1 ≥ p 4(p-k)q2 . Hence, lim p→∞ δ 2 (p -k)q 2 2 + δ = lim p→∞ δ(p -k)q 2 ≥ lim p→∞ p 4(p -k)q 2 (p -k)q 2 = ∞.Combining the above and (70) gives lim p→∞ P C λ k T = 1 which completes the proof.The following proposition states the form of 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 ± λ/k.Proposition E.1. Let {(x i , y i )} L i=1 be L i.i.d. labeled samples from model (3) where µ is k-sparse with non-zero entries ± λ/k, and let w L = 1 L i∈[L] y i x i . Assuming the sparsity k is known, the MLE for S = supp(µ) is given by the indices corresponding to the top-k magnitudes of w L .Proof. Under our assumptions, the set of all possible vectors µ has a one-to-one mapping to a support set S ∈ S and a vector D ∈ {-1, 1} k containing the signs of the k non-zero entries of µ. We thus denote θ = (S, D), and µ θ by µ θ j = √ λ √ k D j , j ∈ S, 0, j ̸ ∈ S.EQUATION)By definition, the maximum-likelihood estimator of θ is given by θ(ML) = arg max Therefore, the maximum value of w L , µ θ is obtained for Ŝ(ML) being the set of indices corresponding to the k largest magnitude entries of w L , and D(ML) = {sign(w L ) j : j ∈ Ŝ(ML) }.The next proposition shows that with sufficient number of labeled samples the MLE for S has significant overlap with the true support set S. Proposition E.2. Let D L = {(x i , y i )} L i=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 ± λ/k. Assume that for some α ∈ (0, 1), k = ⌊c 1 p α ⌋ and that L = 2βk log(p-k) λ , for some β ∈ (0, 1). Let S L be the indices of the k largest magnitudes of the vector wL = 1 L i∈[L] y i x i . If β > 1 -α, then for every ϵ ∈ (0, 1), lim p→∞ P |S ∩ S L | k > 1 -ϵ = 1.Proof. Fix ϵ > 0, and let A L denote the event that |S L ∩ S| ≥ k(1 -ϵ). For any threshold τ define the following two events,B(τ ) =    j∈S 1{|w L (j)| > τ } > k(1 -ϵ)    , C(τ ) =    j / ∈S 1{|w L (j)| > τ } < kϵ    .By their definition, it follows that for any τ > 0, B(τ ) ∩ C(τ ) ⊂ A L . Since the two events B(τ ) and C(τ ) are independent,EQUATIONHence, for P(A L ) → 1, it suffices that for a suitable threshold τ , both probabilities on the right hand side tend to one, We start with Pr( B(τ )). To this end, we define an even simpler event, with the absolute value removed,B(τ ) =    j∈S 1{sign(µ j )w L (j) > τ } > k(1 -ϵ)    Clearly B(τ ) ⊂ B(τ )and thus it suffices to show that P(B(τ )) → 1 as p → ∞. By the sparse mixture model (3), for j ∈ S,sign(µ j )w L (j) = λ k + sign(µ j ) √ L ξ j ,where ξ j ∼ N (0, 1). Combining a threshold value τ = λ kand the assumption thatL ≥ 2βk log(p-k)λ with this expression, gives thatEQUATION)Let q 1 be the probabiity of each event in the above sum,q 1 = P N (0, 1) > - β - 1 -α + β 2 2 log p .Since the ξ j 's are all independent and |S| = k, with this choice of τ , Eq. ( 73) simplifies to P(B(τ )) ≥ P(Bin(k, q 1 ) > k(1 -ϵ)).Note that since β > 1 -α, then lim p→∞ q 1 = 1. Thus, for sufficiently large p, it holds that q 1 (1 -ϵ/2) > 1 -ϵ. Hence, the right hand side above may be bounded by P(Bin(k, q 1 ) > kq 1 (1 -ϵ/2)). Indeed, by Chernoff's bound (17) , P(B(τ )) → 1 as p, k → ∞, sinceP (B) ≥ 1 -e -ϵ 2 kq 1 8 .Next, we show that the second term in Eq. ( 72), P( C), also tends to one as p → ∞. First, note thatC(τ ) = {Bin(p -k, q 2 (τ )) < kϵ} where q 2 (τ ) = 2Φ c ( √ Lτ ) = 2Φ c ( (1 -α + β) log(p -k)). We now prove that P( C(τ )) → 1, by applying a Chernoff bound. To this end, we writekϵ = q 2 (p -k)(1 + δ) where δ = kϵ (p-k) 1 q2 -1.To use Chernoff's inequality we first need to show that δ ≥ 0. Indeed, as p → ∞, using Lemma A.1 which bounds the tail function Φ c ,lim p→∞ (δ + 1) ≥ lim p→∞ ϵk p -k 1 2Φ c ( (1 -α + β) log(p -k)) ≥ ϵc 1 π(1 -α + β) 2 lim p→∞ log(p -k) p 1-α exp(-1-α+β 2 log(p -k)) = ϵc 1 π(1 -α + β) 2 lim p→∞ log(p -k) p 1-α-β 2 = ∞,where the last equality follows from β > 1 -α. By Chernoff's bound ( 16)EQUATIONWe now prove that the term in the exponent tends to infinity. Since δ → ∞ it follows thatlim p→∞ δ 2 (p -k)q 2 2 + δ = lim p→∞ δ(p -k)q 2 ≥ lim p→∞ (1 + δ)(p -k)q 2 2 = lim p→∞ kϵ 2 = ∞.Combining the above and (74) gives that lim p→∞ P C (τ ) = 1, which completes the proof.The above proposition implies the following result regarding accurate classification: Let T (x) = sign⟨ μ, x⟩, with μ = w L | S L , be a linear classifier that is constructed using only the set of labeled samples D L . If β > 1 -α, then combining Proposition E.2 and Lemma A.8 implies that the excess risk of T tends to zero as p → ∞.In this section we prove a lower bound for classification in the SL setting. To do that, we consider a slightly different model, known as the rare and weak model. Here the sparsity of the vector µ is not fixed at exactly k. Instead the vector is generated randomly with entries µ j = λ/kB j , where B j ∼ Ber(ϵ p ) are i.i.d. Bernoulli random variables with ϵ p = k p = p -(1-α) . The next theorem implies that in the red region (impossible) of figure 1 , indeed there exists (approximately) k-sparse vectors for which any classifier would asymptotically be no better than random. Theorem E.3. Let D L = {(x i , y i )} L i=1 be set of L i.i.d. labeled samples from the rare weak model N (yµ, I) where all non-zero entries of µ are ± λ/k. Suppose L = ⌈ 2βk log p λ ⌉ and k ∝ p α , for some α < 1. If β < 1 -α then the classification error of any classifier based on D L , tends to 1/2 as p → ∞.Proof. This proof is similar to the one of Jin (2009) . First, let us denote the vector of z-scores by z = 1 √ L i∈[L] y i x i . Since the entries of µ are generated independently under the rare-weak model, the entries of z are also independent and all have the same density, which we denote by f (z). Given z, we denote the conditional probability that the j-th entry contains a feature by η = P(j ∈ S|z) = P(j ∈ S|z j = z). By Bayes theorem,η(z) = P(j ∈ S)f (z|j ∈ S) f (z) = ϵ p ϕ(z -τ p ) (1 -ϵ p )ϕ(z) + ϵ p ϕ(z -τ p ),where τ p = Lλ/k = √ 2β log p, and ϕ is the density of N (0, 1).From Lemmas 1,2 and 4 in Jin (2009) , the misclassification error of any classifier T constructed using the set D L , can be bounded asEQUATIONwhereH(z) = E x 1 + η(z)(e √ λ/kx-λ/2k -1) 1/2with x ∼ N (0, 1), and z ∼ (1ϵ p )N (0, 1) + ϵN (τ p , 1).Our goal is to show that E z [H(z)] = 1 + o(1/p), which implies that asymptotically the accuracy of T is no better than random. First, combining that E x e √ λ/kx-λ/2k -1 = 0 and the inequality| √ 1 + t -1 -t/2| ≤ Ct 2 , for any t > -1, gives |H(z) -1| = H(z) -1 -1 2 E[η(z)] E[e √ λ/kx-λ/2k -1] ≤ Cη 2 (z) E x e √ λ/kx-λ/2k -1 2 = Cη 2 (z)(e λ/k -1). For sufficiently large p, e λ/k -1 ≤ 2λ/k. Since k ∝ p α , then, |H(z) -1| ≤ Cp -α η 2 (z). Hence, to prove that E z [H(z)] = 1 + o(1/p), it suffices to show that E z [η 2 (z)] = o(p -(1-α) ) = o(ϵ p ).To this end, we first noteE[η 2 (z)] = (1 -ϵ p ) E[η 2 (w)] + ϵ p E[η 2 (w + τ p )] ≤ E[η 2 (w)] + ϵ p E[η 2 (w + τ p )],where w ∼ N (0, 1). Write E(η 2 (z)) = I + II + III + IV , where we have split each of the expectations into two separate integrals, with the split at suitably chosen values t 1 and t 2 ,EQUATIONIII = ϵ p t2 -∞ η 2 (w + τ p )ϕ(w)dw, IV = ϵ p ∞ t2 η 2 (w + τ p )ϕ(w)dw,As we see below, the following values will be suitable to derive the required bounds:t 1 = 1-α+β 2β τ p and t 2 = 1-α-β 2β τ p . Starting with I, note that I = t1 -∞ ϵ p ϕ(w -τ p ) (1 -ϵ p )ϕ(w) + ϵ p ϕ(w -τ p ) 2 ϕ(w)dw ≤ t1 -∞ ϵ p ϕ(w -τ p ) (1 -ϵ p )ϕ(w) 2 ϕ(w)dwFor large enough p, the above can be bounded viaEQUATIONwhere the equality follows from the definition of ϕ(w). Completing the square, the above can be written asI ≤ Cϵ 2 p t1 -∞e -(w-2τp) 2 /2 e τ 2 p dw.Changing the variable x = w -2τ p readsEQUATIONFinally, since β < 1 -α, it follows that Cϵ 2 p e τ 2 p e -(2τp-t1) 2 /2 = o(ϵ p ).Next, since η(w) < 1 it follows thatEQUATIONSimilar to the above, under the condition β < 1 -α it holds that e -t 2 1 /2 = o(ϵ p ). Next, note thatIII = ϵ p t2 -∞ ϵ p ϕ(w) (1 -ϵ p )ϕ(w + τ p ) + ϵ p ϕ(w) 2 ϕ(w)dw ≤ ϵ p t2 -∞ ϵ p ϕ(w) (1 -ϵ p )ϕ(w + τ p ) 2 ϕ(w)dw. For large enough p III ≤ Cϵ p t2 -∞ ϵ p ϕ(w) ϕ(w + τ p ) 2 ϕ(w)dw = Cϵ 3 p t2 -∞ e 2wτp+τ 2 p -w 2 /2 dw.Completing the square readsIII ≤ Cϵ 3 p e 3τ 2 p t2 -∞ e -(w-2τp) 2 /2 dw = Cϵ 3 p e 3τ 2 p Φ c (2τ p -t 2 ) ≤ Cϵ 3 p e 3τ 2 p e -(2τp-t2) 2 /2 . Since β ≤ 1 -α it holds that III = o(ϵ p ).Finally, since η(w) < 1, IV can be bounded as followsIV = ϵ p ∞ t2 ϕ(w)dw = ϵ p Φ c (t 2 ) ≤ ϵ p e -t 2 2 /2 .Again, by β < 1 -α, IV = o(ϵ p ).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It 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 a 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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.• If this information is not available online, the authors are encouraged to reach out to the asset'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/model 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. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS 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.Summary and DiscussionIn this work, we analyzed classification of a mixture of two Gaussians in a sparse high dimensional setting. Our analysis highlighted provable computational benefits of SSL. Two notable limitations of our work are that we studied a mixture of only two components, both of which are spherical Gaussians. It is thus of interest to extend our analysis to more components and to other distributions.From a broader perspective, many SSL methods for feature selection have been proposed and shown empirically to be 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 SSL improves over both SL and UL in its error rates, not only computationally. 
 
 Appendix:  


Decision: 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)

Reviews: review: paper_summary: paper_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.

THe 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.
strength_weakness: strength_weakness: The paper only studies a limited setting of a mixture of two Gaussians

The 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

It is a bit technical to actually describe/understand the setting where the algorithm in the paper has provable gains
questions: questions: .
limitations: limitations: Yes
paper_summary: paper_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.

This 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.
strength_weakness: strength_weakness: I think the exposition of the paper could be slightly improved. In particular:
- it would be nice to mention which part of Figure 1 comes from which theorem, and which are novel to the paper;
- 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)$).
- 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 ?
questions: 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- Also, it would be nice to add references to the results in Section 2 to the paragraph starting on L86.
- It would be nice to rigorously explain the reduction on Eqn (3), even if in the appendix.
questions: questions: - Do you have a conjecture for the information theory lower bound in the white "hole" region?
- Do you have any insights as to how one might analyze LS^2PCA?
limitations: limitations: Yes
paper_summary: paper_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)$.
The claims of the paper are as follows:

* Derive information-theoretic lower bounds for exact support recovery in the semi-supervised learning (SSL) setting.
    
* 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.

* Identify a region where SSL is computationally advantageous for classification and feature selection.

The 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.
strength_weakness: strength_weakness: * 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.
questions: 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?

*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.

*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.

*4*- Is there any proof that the bound in Theorem 2.3 is tight?

*5*- The proof for Theorem 2.6 is indexed as the proof of Theorem 4 in the supplementary material.

*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.

*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: limitations: Please check the questions.

Comments: comment: Thank you for your detailed responses. I will keep my score.
Yes, this is correct.
Thank you for the response and addressing my concerns/questions.  Is it correct that if the parameters are bounded away from the boundaries of $\alpha = 1/2, \gamma = 2$ then the gain is only a constant factor?
I thank the authors for their answers. They addressed my questions, so I increased my score accordingly.