Semi-Supervised Sparse Gaussian Classification: Provable Benefits of Unlabeled Data
Eyar Azar Boaz Nadler

Global prescribed-time control of a class of uncertain nonholonomic systems by smooth
time-varying feedback
    Kang-Kang Zhang, Bin Zhou, Chenchen Fan, James Lam,  Fellow, IEEE



This work was supported by the National Science Found for
Distinguished Young Scholars (62125303), the Science Center Program of
National Natural Science Foundation of China (62188101), the
Fundamental Research Funds for the Central Universities
(HIT.BRET.2021008), and HKU CRCG (2302101740). (Corresponding authors: Bin Zhou)
Kang-Kang Zhang is with the Department of Mechanical Engineering, University of Hong Kong,
Hong Kong, China, and the Department of Computer Science, KU Leuven, B-3001 Heverlee, Belgium; James Lam is with the Department of Mechanical Engineering, University of Hong Kong,
Hong Kong, China;
Bin Zhou is with the Center for Control Theory and Guidance Technology, Harbin Institute of Technology, Harbin, 150001, China; Chenchen Fan is with the Department of Rehabilitation Sciences, The Hong Kong Polytechnic University, Hong Kong, China  (email: kang-kang.zhang@kuleuven.be, binzhou@hit.edu.cn, chenchen.fan@polyu.edu.hk, james.lam@hku.hk).


    Received ?? ; accepted ??
================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================





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








§ 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
<cit.>. 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 <cit.>. 
In some  cases, however, SSL performs similarly to UL (i.e., clustering, up to a label permutation ambiguity). 
In addition, <cit.> 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 (Y=y)=π_y and conditional on a label value y, 
the vector ∈ℝ ^p follows a Gaussian distribution, 

    |y ∼𝒩(μ_y,  I_p)

where μ_1,μ_-1∈ℝ^p are both unknown. 
This model and related ones were studied theoretically in supervised, unsupervised and semi-supervised settings, see for example  
<cit.>, 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, <cit.> proved that
for the model (<ref>), 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 (<ref>).

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 (<ref>). 
Here, the joint distribution of a labeled sample
(,y) is given by

    y ∼Unif{± 1},   |y ∼𝒩(μ_y,  I_p).

The class means μ_1, μ_-1∈ℝ^p are unknown, 
but their difference Δμ = μ_1- μ_-1
is assumed to
be k-sparse, with k≪ p. 
In a supervised setting, model
(<ref>) 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. <cit.>. 
In an unsupervised setting, inference on the model (<ref>) is closely related to clustering and learning mixtures of Gaussians <cit.>. 
A key finding is that in an unsupervised setting with a sparsity assumption, there is a statistical-computational gap <cit.>. 
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 (<ref>) in a SSL setting, 
given L labeled samples and n unlabeled samples, all i.i.d. from (<ref>). 
Despite extensive works on  the SL and UL settings for the model (<ref>), 
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 <ref>, 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 <ref> 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 <cit.>,  
    
    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 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 a region where SSL is provably computationally advantageous for
    classification and feature selection. 
    Specifically, in Section <ref> we develop a 
    polynomial time SSL algorithm, denoted , 
    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,  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 <ref> we show via simulations the superiority 
    of , 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 <cit.>.  
   
    


    Figure  <ref> summarizes the 
    picture emerging from our work in combination with previous papers that analyzed the
    UL and  SL settings of (<ref>) , namely, the x-axis and y-axis in Figure <ref>. 
    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 <ref>): 
    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 <cit.>, 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 <cit.>, 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  <ref> follow from 
    novel results of this paper.
    In the orange region, defined as β<1-α and 1<γ<2, our computational lower bound in Theorem <ref> 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 <ref>. 
    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 ∈ℝ^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) > c g(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 <ref> 
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
<ref>, 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 (<ref>), where the two Gaussian means are symmetric around the origin, with μ_1 = - μ_-1 = μ. Hence,

    y ∼Unif{± 1},   |y ∼𝒩(yμ ,  I_p).

Here, μ∈ℝ^p is an unknown k-sparse vector with  ℓ_2 norm of √(λ).
We denote its support by S=(μ) = {i|μ_i≠ 0}, 
and by 𝕊  the set of all 
()0pt2pk possible k-sparse support sets.
We denote by _L = {( x_i, y_i)}_i =1^L and _n = {_i}_i =L+1^L+n 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 <cit.>, 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.




 §.§ Information Lower Bounds (Supervised and Unsupervised)

    

     
    The next theorem states a non-asymptotic result for exact support recovery in the SL case.

     
    
    Fix δ∈(0,1).
    For any (L,p,k) such that
    
    L < 2(1-δ)k/λlog(p-k+1),

    and for any support estimator Ŝ based on _L, 
    it follows that
    max_S ∈𝕊(Ŝ≠ S) > δ - log 2/log(p-k+1) .
    
     
   
<cit.> 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 <ref> 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 _i from (<ref>) but not their labels y_i.
 
    
   Fix δ∈ (0,1).
    For any (n,p,k) →∞ with k/p→ 0 and 
    
    n< 2(1-δ)k/λ^2log(p-k+1)max{1, λ},

    for any support estimator Ŝ based on _n, 
    as p→∞ , then
    
    max_S ∈𝕊(Ŝ≠ S) ≥δ
    .


The scaling in Eq. (<ref>)
appeared in several prior works on related problems.  
<cit.> showed that for λ<1, with number of samples n<C k/λ^2log(p/k), no clustering method can achieve accuracy better than random. 

<cit.>
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/λ^2log(ep/k) max{1, λ}, any testing procedure is asymptotically powerless. Note that for k = p^α with α < 1, the lower bound derived in <cit.> has a similar form to (<ref>) with a factor of 1 - α, which is slightly smaller. 
Thus the bound in (<ref>) is sharper. 









 §.§ 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-theoretic and computational lower bounds for this setting. 
The information lower bound is based on the 
results in Section <ref>
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 (<ref>) both <cit.> and
<cit.> 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 <ref>, 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  
(<ref>), we analyze a more general case.
We study the recovery of a latent variable S that belongs to a large finite set 𝕊, given 
measurements from 
two different modalities.


Formally, 
the problem is to recover S from  two independent sets of samples {_i}_i=1^N and {_j}_j=1^M of the following form, 

    {_i}_i=1^N ∼ f_x(|S),   {_j}_j=1^M ∼ g_z(|S).

Here,
f_x(|S) and g_z(|S) are known probability density functions. 
These functions encode information on S from the two types of measurements. 
In our SSL setting, 
 represents an unlabeled sample, whereas =(,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 𝕊, 
and denote by I_x = I(; S) and I_z = I(; S) the mutual information of  with S and of  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 at least linearly with log |𝕊|/I_x.
A similar argument applies to .
For further details, see <cit.>.

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.




    
    Fix δ∈(0,1).
    Let N, M be integers that satisfy 
    max{N· I_x,  M· I_z }< (1-δ)log|𝕊|.
    Let N_q = ⌊ q N⌋ and M_q = ⌊(1-q) M⌋, for q∈[0,1].
    Then, any estimator Ŝ based on {_i}_i=1^N_q and {_j}_j=1^M_q satisfies
    
    ( Ŝ≠ S) > δ - log 2/log |𝕊|.






This theorem implies that with any convex combination of samples from the two modalities, q N 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 <ref> with 
the proofs of 
Theorems <ref> and <ref> yields the following information lower bound for the semi-supervised case. 



    
    Let _L and  _n 
    be sets of L and n i.i.d. labeled and unlabeled samples from the mixture model (<ref>).
    Fix δ∈ (0,1).
    Let (L_0,n_0,p,k) →∞, with k/p→ 0,  be such that
    
    
    L_0 < 2(1-δ)k/λlog(p-k+1),  
            n_0< 2(1-δ)k/λ^2log(p-k+1)max{1, λ}.

    
    Suppose the number of labeled and unlabeled samples satisfy L = ⌊ q L_0⌋ and n = ⌊(1-q)n_0⌋ for 
    some q∈[0,1].
    Then, for any estimator Ŝ based on _L ∪_n, 
    as p→∞
    
    max_S ∈𝕊( Ŝ≠ S) ≥δ.







  
Computational Lower Bounds.
Our SSL computational lower bound is based on the low-degree framework, and its associated hardness conjecture <cit.>.
This framework was used to derive computational lower bounds for various unsupervised
high dimensional problems including sparse-PCA and sparse Gaussian mixture models
<cit.>.
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 ℙ and ℚ, given n
i.i.d. samples. Specifically, denote the null distribution of n samples by ℚ_n,
whereby all _i∼ℚ, and denote by ℙ_n the alternative distribution, with
all _i∼ℙ. 

Under the low-degree framework, one 

analyzes how
well can the distributions ℙ_n and ℚ_n be distinguished by a low-degree
multivariate 
polynomial  f: ℝ^p× n→ℝ. 
The idea is to construct a polynomial f 
which attains large values

for data from ℙ_n and small values
for data from ℚ_n. 
Specifically, the following metric
plays a key role in this framework, 

    ℒ_n^≤ D := max_deg(f) ≤ D_X ∼ℙ_n[ f(X)]/√(_X ∼ℚ_n[ f(X)^2]),

where the maximum is over polynomials f of degree at most D.

The value ℒ_n^≤ D 
characterizes how well degree-D polynomials can distinguish ℙ_n from ℚ_n.
If ℒ_n^≤ D = O(1), then ℙ_n and ℚ_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 


<cit.> 

for its precise statement.  



    Let ℚ_n and ℙ_n be two distinct distributions.
    
    Suppose that there exists D = ω(log(pn)) for which ℒ_n^≤ D remains bounded as p →∞. 
    Then, there is no polynomial-time test T:ℝ^p× n→{0,1} that satisfies
    
    _X ∼ℙ_n[T(X)] + _X ∼ℚ_n[1-T(X) ] = o(1).



In simple words, Conjecture <ref> states that 
if ℒ_n^≤ D = O(1) as p→∞, then it is not possible to distinguish between ℙ_n and ℚ_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 ℚ_L+n or
an alternative distribution ℙ_L+n.
In our case, the null distribution 
is

    ℚ_L+n:   _i = ξ_i∼𝒩(0, I_p) ,   i∈[L+n],

whereas the alternative belongs to the following set of distributions,  

    ℙ_L+n:   {   _i =  μ^S + ξ_i ,    i∈[L],  
       _i =  y_i μ^S + ξ_i ,   L< i≤ L+n.

Here, S is uniformly distributed over 𝕊, μ ^S (j) = √(λ/k){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 <ref> and <ref>. 


    
    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 ∈ℝ_+ and α∈ (0, 1/2).
    With the null and alternative distributions defined in (<ref>) and (<ref>), 
    if β<1/2 - α and γ<2, then as p→∞
    
    ℒ_L+n^≤ D^2 = O(1).



Theorem <ref> together with the hardness conjecture <ref> extends to the SSL case previous computational lower bounds that were derived only in 
UL settings (β=0) 
<cit.>. 

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 <ref>, under the hardness conjecture <ref>, distinguishing between ℙ and ℚ is computationally hard. 
    Since testing is easier than variable selection and classification
    <cit.>,
    
    in this region these tasks are computationally hard as well.


Tightness of condition γ<2 in 
    Theorem <ref>.

 
    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 <cit.> 
    and <cit.>.


Tightness of condition β<12-α. 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 ℙ
and ℚ, using only the labeled data  <cit.>.

Combining Theorems <ref>-<ref> 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 <ref>, is guaranteed to recover S
and construct an accurate classifier.
    We conclude with the following conjecture regarding the remaining white region:

    

    
    Let _L, _n be sets of L and n i.i.d. labeled and unlabeled samples from the model (<ref>).
Assume, as in Theorem <ref> that
    k∝ p^α, L = ⌊2β k/λlog(p-k)⌋ and n ∝k^γ/λ^2.
    Then in the white region depicted in Figure <ref>, 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 , for the model (<ref>), that 
is simple and 
has polynomial runtime. 
In subsection <ref> we prove that in the blue region of Figure <ref> it recovers the support, and thus constructs an accurate
classifier. In this region, under the hardness conjecture <ref>, computationally efficient algorithms that rely solely on either labeled or unlabeled data would fail.




  
Preliminaries. To motivate the derivation of , we first briefly review some properties of the sparse model (<ref>). 
First, note that the covariance
matrix of  is Σ_x =  14ΔμΔμ^⊤ +  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 
<cit.>. 
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. 




 §.§ The  Scheme


Our SSL scheme, denoted  , stands for Label Screening PCA. 
As described in Algorithm 1,  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 high-dimensional regression <cit.>.  

To this end, our scheme first constructs the vector, 

    _L = 1/L_+∑_i:y_i=1x_i - 
            1/L_-∑_i:y_i=-1x_i
            ,

where L_+=|{i∈[L]:y_i=1}| and L_-=L-L_+.
With a balanced mixture (Y=±1) = 12, it follows that _L ≈Δμ + 
2/√(L) N(0, 𝐈_p). 
Hence, _L can be viewed as a noisy estimate of Δμ.
If the number of labeled samples were large enough, then the top k coordinates of _L would coincide with the support of Δμ. With few labeled samples, while not necessarily the top-k, the entries of _L at 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 _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,  constructs the sample covariance matrix restricted to the
set S_L, 

    Σ̂|_S_L = 1/n∑_i=L+1^n+L (_i - )|_S_L(_i -)|_S_L^⊤,

where = 1/n∑_i=L+1^n+L_i is the empirical mean of the unlabeled data.
Next, it computes the leading eigenvector v̂_PCA of Σ̂|_S_L.
The output support set Ŝ
consists of the k indices
of v̂_PCA
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. 








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  (Labeled Screening Sparse-PCA). 
As illustrated in the simulations, for finite sample sizes, this can lead to improved support recovery and lower classification errors. 









    



 §.§ Support Recovery and Classification Guarantees for 


Before presenting our main result, we first recall two standard evaluation metrics.
The classification error of a classifier C: ℝ^p →{±1} is defined as 


ℛ (C) =  (C()≠ y).

Its excess risk is defined as

    ℰ(C) = ℛ(C) - ℛ^* = ℛ(C) - inf_C'ℛ(C').


As in <cit.>, 
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
, in terms of support recovery and the excess risk of the corresponding classifier. 

    
    
    Let _L,_n be labeled and unlabeled sets
    of L and n i.i.d. samples 

    from 
    (<ref>)
    with a k-sparse μ whose non-zero entries are ±√(λ/k).
    Suppose that k= ⌊ c_1p^α⌋, 
    L = ⌊2β k/λlog(p-k)⌋, n = ⌊ c_2k^γ/λ^2⌋, 
    for some fixed
    0<α <1/2, 0<β<1-α, γ>1 and λ,c_1,c_2 ∈ℝ_+.
    Let Ŝ, v̂ be the output of Algorithm 1 with input k and screening factor β̃.
    If β> 1-γα
    and β̃∈ ( 1-γα, β), then 
    
    lim_p →∞(|S ∩Ŝ|k≥ 1-ϵ) = 1,   ∀ϵ > 0,

    and the excess risk of the corresponding classifier C() = ⟨v̂,⟩, satisfies 
    
    lim_p →∞ℰ (C) = 0.


The interesting region where Theorem <ref> provides a non-trivial recovery guarantee
is the triangle depicted in blue in Figure <ref>. 
Indeed, in this region,  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 <ref>, it is not possible to construct in polynomial time an accurate SSL classifier.
 The intuition underlying this conjecture is based on the work of <cit.>, 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  and  to various SL, UL and 

SSL
schemes, in terms of both accuracy of support recovery  and classification error. 
The sparse PCA method used in  was iteratively proxy update () <cit.> .
We generate L+n labeled and unlabeled samples according to the model (<ref>) 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 ↦⟨μ̂ ,⟩. 
Given the model (<ref>), its generalization error is
Φ^c(⟨μ̂ ,μ⟩).
We run our SSL schemes with β̃= β-(β-(1-γα))/4 which satisfies the requirements of Theorem <ref>. 

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  and  to the following UL methods, taking all L+n samples as unlabeled:
 <cit.>, and  <cit.>.
The SSL methods that we compare are  <cit.>, and self-training ().
The self-training algorithm is 
similar to the approach in 
<cit.>, but explicitly accounts for the known sparsity k: (i) compute _L of (<ref>) using the labeled samples, and keep its k largest entries,

denote the result by _L^(k); (ii) 
compute the dot products c_i = ⟨_L^(k), _i ⟩ and the pseudo labels ỹ_i = (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:

    _self = 1/L+n_eff(∑_i=1^Ly_i_i + ∑_i=L+1^L+n{|c_i|>Γ}ỹ_i _i )

 In the experiments  we used Γ = 0.8, which gave the best 
performance.
Also, we implemented the SL scheme  that selects the indices of the top-k entries of | w_L| of  (<ref>). 
As shown in the supplementary, 
this is the maximum-likelihood estimator for S based on the labeled data.

Figure <ref>
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 <ref> 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,  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 () 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 compare our SSL algorithms  and  to the SSL methods
 and , as well as to the SL scheme , which uses only the L labeled samples.
Figure <ref> illustrates the support recovery accuracies and the classification error as a 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, 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 <cit.>. 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.
    







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









neurips_2024




















§ 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 Φ^c(t) = (Z > t), where Z ∼𝒩(0, 1). The following lemma states a well known upper bound on Φ^c.




    
    For any t>1,
    
    Φ^c(t) ≤1/√(2π)t e^-t^2/2.

    
    
    
    








     Suppose {x_i}_i=1^n are i.i.d. Bernoulli random variables, with [x_i = 1]=q.  
     Let X denote their sum. 
     Then, for any δ≥0,
     
    (X ≥(1+δ)
             nq) ≤ e^-δ^2 nq/2+δ,

    and for any δ∈ [0,1]
     
    (X ≤(1-δ)
             nq) ≤ e^-δ^2 nq/2.



A common approach to prove lower bounds is using Fano's inequality. Here, we use the 
following version of Fano’s lemma, see <cit.>.



    
    Let θ be a random variable uniformly distributed over a finite set Θ. 
    Let _1,_2,…, _n be n i.i.d. samples from a density f(|θ). 
    Then, for any estimator θ̂(_1,…,_n) ∈Θ,
    
    
    (θ̂≠θ) ≥ 1 - I(θ; Z^n) + log 2/log |Θ|,

    where I(θ; Z^n) is the mutual information between θ and the samples Z^n = (_1,_2,…, _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. 

    Let ∼𝒩(μ, Σ).
    Then, its entropy is given by 
    
    H() = p/2(1+log(2π)) + 1/2logdet (Σ).



Next, the following lemma  states that the multivariate Gaussian distribution maximizes the
entropy over all continuous distributions with the same covariance
<cit.>.


    Let  be a continuous random variable with mean μ∈ℝ^p and covariance Σ∈ℝ^p× p, and let y ∼𝒩(μ, Σ). 
    If the support of  is all of ℝ^p then
    
    H() ≤ H( y).



The next lemma states the sub-additive property of the entropy function.

    
    Let  and y be jointly distributed random variables. Then,
    
    H(, y) ≤ H() + H( y).



To prove Theorem <ref> we use the following lemma.



 

Let λ∈ (0,1), and let k be a positive integer.
Then, for w ∼ N(0, k-1/k) 

    [tanh (λ + √(λ)w ) - 1/2tanh^2(λ +√(λ)w )] ≤1/2(λ + 
        
        3√(λ/k))







    

    Let  q(w) = tanh (λ + √(λ)w ) - tanh^2 (λ + √(λ)w ).
    
    
    
    
    In terms of q(w), the left hand side of (<ref>) may be written as follows
    
    [tanh (λ + √(λ)w ) - 1/2tanh^2(λ +√(λ)w )] = 
             1/2([tanh (λ + √(λ)w) ]  +[q(w)]).


     We now upper bound the two terms in the RHS of (<ref>).
     We start by showing that [q(w)]≤ 3√(λ/k). 
     Let L_q = max_w∈ℝ|q'(w)| be the Lipschitz constant of the function q(w).
     It is easy to show that  L_q ≤ 3√(λ).
     Let z∼(0,1) be independent of w.
     Using the first order Taylor expansion yields
    
    _w,z[q(w ) - q(w +1/√(k)z)] ≤ L_q1/√(k)_z[|z|] = 
            3√(λ/k)√(2/π)≤ 3√(λ/k).

    
    Next, note that (w +1/√(k)z) ∼ N(0,1).
    Therefore 
    
    
    _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, gives
    
    _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 (<ref>) gives
    
    _w[q(w )] ≤ 3√(λ/k).



    Next, we upper bound the first term on the RHS of  Eq. (<ref>).
    
    Denote by f_W(w) the probability density function of w∼(0, k-1k).
    
    Then, writing the expectation explicitly gives
    
    [tanh (λ + √(λ)w )]= ∫_-∞^∞tanh (λ + √(λ)w ) f_W(w) dw.


    Making the change of variables x = λ + √(λ)w yields
    
    [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,
    
    [tanh (λ + √(λ)w )]
            ≤1/√(λ)∫_0^∞x
            (f_W(x-λ√(λ))- f_W(x+λ√(λ)) )dx 
            = 1/√(λ)∫_-∞^∞x
            f_W(x-λ√(λ))dx

    
     Substituting  w = (x-λ)/√(λ), yields
    
    [tanh (λ + √(λ)w )]≤∫_-∞^∞ (λ + √(λ)w ) f_W(w) dw = [ λ + √(λ)w ] = λ.

    
     Combining (<ref>),(<ref>) and (<ref>) gives
    
    [tanh (λ + √(λ)w ) - 1/2tanh^2(λ +√(λ)w )] ≤1/2(λ+ 3√(λ/k)).





 




    Consider a sequence of classification problem of the form, 
    
    y ∼Unif{± 1},   |y ∼ N(yμ, 𝐈_p),

    where the dimension p →∞ but =√(λ) is fixed.
    Let _p be a sequence of unit norm estimators and T_p() = (μ̂_p,) the corresponding classifier.
    Assume that every ϵ>0 
    
    lim_p →∞(⟨μ/√(λ) , _p⟩>1-ϵ ) = 1.

    Then, the excess risk of the classifier T_p() = ⟨μ̂_p,⟩ tends to zero as p tends to infinity.


    By definition, the excess risk of the classifier T_p that corresponds to _p can be written as 
    
    ℰ (T_p)    = 
            _∼ N( 0,𝐈_p)(⟨_p,  + ⟩ <0 ) - Φ^c(√(λ)).

    Since  is independent of _p and
    _p has unit norm, then z=⟨_p,⟩∼𝒩(0,1), and the excess risk may be written as
    
    ℰ (T_p) = 𝒫(z > 
              ⟨_p,⟩) - Φ^c(√(λ))

    Let ϵ>0, and consider the event 𝒜_ϵ = {⟨μ/√(λ) , _p⟩>1-ϵ}.
    Then, 
    
    ℰ (T_p) ≤{[ Φ^c(√(λ)(1-ϵ))
                    - Φ^c(√(λ))                                     𝒫(𝒜_ϵ);                                          1                                   1-P(𝒜_ϵ) ].

    Since by assumption 𝒫(𝒜_ϵ)→ 1  for any ϵ>0, then
    the excess risk tends to zero as p →∞.






§ LOWER BOUNDS - PROOFS OF RESULTS IN SECTION <REF>







 §.§ Proof of Theorem <ref>


Our proof relies on Fano's inequality, and is conceptually similar to the proof of Theorem 3 in <cit.>. 
First, note that for any sub-collection 𝕊̃⊂𝕊, we have the following

    max_S ∈𝕊(Ŝ≠ S)≥1/|𝕊̃|∑_S ∈𝕊̃(Ŝ≠ 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 
𝕊̃. In other words, the right hand side may be written as follows, 

    ( error) = 
        ∑_s ∈𝕊( Ŝ≠ s |  S=s) ·(S=s).

In our proof, we consider the following sub-collection 


    𝕊 := {T ∈𝕊: 1, …, k-1∈ T },

which 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){j ∈ S}. 
So, with S known, μ is deterministic and we write it as μ^S.

In the proof we consider an equivalent model of (<ref>), whose observations are divided by √(λ),

    x_i =  y_i  θ^S + σξ_i,    i= 1,…,L ,

where θ^S(j) = 1√(k){j ∈ S}, σ = 1/√(λ) and _i ∼𝒩(0, 𝐈_p). 

Since for each observation x_i we also know its corresponding label 
y_i∈{-1,1}, we may consider the following transformed observations

    _i = y_i _i = θ^S + σξ̃_i,    i= 1,…,L.

where ξ̃_i=y_i ξ_i has the same distribution as ξ_i. 
Denote by X^L, ^L, Y^L the sets of L i.i.d. samples {_i}_i=1^L, {_i}_i=1^L and {y_i}_i=1^L, 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(( ^L, Y^L);S) =I( ^L;S),

where the last equality follows from the fact that the labels Y^L are independent of the support S and the observations ^L. 
Hence, it is enough to consider the samples ^L from the model in (<ref>).

Let S be a subset chosen uniformly at random from 𝕊. 
Then, from Lemma <ref>, it follows that

    ( error) ≥ 1 - I(^L; S) + log 2/log|𝕊| = 1 - I(^L; S) + log 2/log(p-k+1).



We now derive an upper bound on I(^L ; S). 
First, from the relation between mutual information and conditional entropy, I(^L ; S) = H(^L) - H(^L|S).
By the sub-additivity of the entropy function H(^L) ≤ L H(). 

Also, since the samples _i are conditionally independent given S, the joint entropy H(^L|S) can be expressed as 

    H(^L|S) = ∑_i∈[L]H(_i|S) = L H(|S).

where  is a single observation from the model (<ref>). 
Therefore,

    I(^L ; S) ≤ L (H() - H(|S)).


By the definition of conditional entropy, 

    H(|S)    =  
      -  ∑_s ∈𝕊  P(S=s) ∫ 
      f( |S) log f(|S) d ,

where f(|S)  the probability density function of a single random sample  given S. 
For any S ∈𝕊, the vector ( |  S) is a p-dimensional Gaussian with 
mean θ^S and covariance matrix σ^2 𝐈_p. Its entropy is independent of 
its mean, and is given by p2(1 + log(2πσ^2) ).

Hence,

    H(|S) =  p/2(1 + log(2π) + log(σ^2)  ).



The final step is to upper bound H(). To this end, note that  is distributed as a mixture of (p-k+1) Gaussians, each centered at θ^S for S∈𝕊̃. 
Let us denote its mean and covariance by ν_x = [] and Σ = [ (-ν_x)(- ν_x)^T], respectively. 

By the maximum entropy property of the Gaussian distribution (Lemma <ref>), 
and Eq. (<ref>) for the entropy of a multivariate Gaussian, we have 

    H() ≤ H(𝒩(ν_x,Σ)) =p/2(1 + log (2π) ) + 1/2logdet(Σ) .




Combining (<ref>), (<ref>) and (<ref>)  gives

    I(^L;S) ≤L/2(
        log (Σ) -  p logσ^2
        ) .


The following lemma, proved in Appendix <ref>, provides an upper bound for log (Σ).




    
    Let Σ be the covariance matrix of the random vector  of Eq. (<ref>), with the set S uniformly distributed on 𝕊 of Eq. (<ref>). 
    Then, 
    
    logdet(Σ) ≤ p log(σ^2) + (p-k+1)log(1+ 1/k(p-k+1)σ^2).



 



Substituting this upper bound into (<ref>) leads to

    I(^L;S) = L/2 (p-k+1)log(1+ 1/k(p-k+1)σ^2)
        ≤L/2kσ^2 = Lλ/2k

where the last inequality follows from log(1+x) ≤ x, for all x>0. 
Inserting (<ref>) into  (<ref>), 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.















 §.§ Proof of Theorem <ref>

To prove Theorem <ref> we use the following lemma,  proven in Appendix <ref>.






    Let  be a random vector from the model (<ref>),
    with a vector μ^S, where the random variable S is uniformly distributed over the set 𝕊̃ of Eq. (<ref>), and let I(;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 small 

    
    I(;S) ≤1/2λ^2/k(1+o(1)).








First, note that for  λ≥1, the information lower bounds proven
in Theorem <ref> and those we aim to prove in Theorem <ref>  coincide. 
Clearly, Theorem <ref> which considers all possible estimators based on {(_i, y_i)}_i=1^L, includes in particular all unsupervised estimators that ignore the labels.
Hence, for λ≥ 1, Theorem <ref> follows from Theorem <ref>.
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 𝕊, where 𝕊 is the 
sub-collection of support sets defined in (<ref>). 
Then, using the same arguments as in the proof of Theorem 1,

    max_S ∈𝕊(Ŝ≠ S)≥1/|𝕊̃|∑_S ∈𝕊̃(Ŝ≠ S) ≥ 1 - I(X^n;S) + log 2/log |𝕊|,

where X^n = (_1,...,_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 _i are conditionally independent given S=s, imply

    I(X^n;S) ≤ n(H() - H( |S)) = n I(;S),

where  is a single sample from the model (<ref>).  

Hence, for p and k sufficiently large, with k/p sufficiently small, combining (<ref>) and (<ref>)  gives 

    
I(X^n;S) ≤nλ^2/2k(1+o(1)). 
    

By  Fano's bound in (<ref>), the error probability is at least δ if 

n< 2(1-δ)k/λ^2 log(p-k+1)
.








 §.§ Proof of Theorem <ref>


Recall that the random variable S is uniformly distributed over the set 𝕊. 
For X^  = {_i}_i=1^ and Z^ = {_i}_i=1^,
their combined mutual information with the random variable S is

    I(X^, Z^ ; S)    = H(X^,Z^) - H(X^,Z^|S).

Since the two sets of samples {_i}_i=1^, {_j}_j=1^ are conditionally independent given S=s, then

    I(X^, Z^ ; S)    = H(X^,Z^) - H(X^|S) - H(Z^|S)  
       = H(X^, Z^) -  H(x|S) -  H(z|S).


By the sub-additivity property of the entropy function, 

    H(X^,Z^)    ≤ H(X^) + H(Z^)
        ≤ H(x) +  H(z).


Hence,  combining (<ref>) and (<ref>) yields

    I(X^, Z^ ; S)    ≤
        
        · I_x + · I_z.

Combining Fano's inequality with the upper bound in (<ref>) gives 
    
    ( Ŝ≠ S)    ≥ 1 - · I_x + · I_z +log2/log|𝕊| .

    Finally, the assumption max{N· I_,  M· I_} < (1-δ)log|𝕊| yields that ( Ŝ≠ S)> δ-log2/log|𝕊|
    









 §.§ Proof of Corollary <ref>

To lower bound the error probability, we view S as a random variable uniformly distributed over 
the discrete set 𝕊 defined in (<ref>). 
By the same arguments as in the proofs of Theorems 1 and 2, 

    max_S ∈𝕊(Ŝ≠ S)≥_S ∼ U(𝕊)(Ŝ≠ S).

We apply Theorem <ref>, with the set _i of i.i.d. unlabeled samples from (<ref>), 
and the second set z_i = (_i,y_i) of i.i.d. labeled samples from model (<ref>).

Next, in the proofs of Theorems <ref> and <ref> 
the following upper bounds for I_ and I_ were derived, 

    I_≤λ/2k,   I_≤λ/2kmin{1,λ}(1+o(1)).

Finally, by the conditions of the Corollary, 
the number of labeled and unlabeled samples satisfy L = ⌊ q L_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 (<ref>) gives

    L_0 · I_,   n_0 · I_≤ 
        (1-δ)log(p-k+1)

Therefore, by Theorem <ref> the error probability is at least δ.








 §.§ Proof of Theorem <ref>


Even though we  analyze a SSL setting, the observed data still belongs to the 
additive Gaussian noise model (see  Section 2 in <cit.>). 

This key point allows to simplify the low-degree  norm in our setting.

Specifically, let Z = (_1, …, _L+n) be the following set of random vectors, which
are the noise-free underlying signals from the alternative ℙ_L+n
 of Eq. (<ref>) in the main text, 

    _i =    {   μ^S  ,    i∈[L],  
         y_i μ^S ,   L< i≤ L+n.

In the equation above, S is uniformly distributed on 𝕊 
(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̃ = (_1, …, _L+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 <cit.> the low degree norm ℒ_L+n^D^2 can be expressed as

    ℒ_L+n^D^2 = _Z,[∑_d=0^D 
        1/d!( ∑_i=1^L+n⟨_i, _i ⟩)^d
        ].


Inserting the expressions for _i and _i into the equation above, gives

    ℒ_L+n^D^2 
            = ∑_d=0^D 
         1/d![
         ( 
         ∑_i=1^L⟨μ^S ,  μ^S̃⟩  
         +
         ∑_i=L+1^L+n⟨ 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 to 

    ∑_d=0^D 
         1/d![
         ( 
          L ⟨μ^S,  μ^S̃⟩  +
         ∑_i=L+1^L+n y_i _i⟨μ^S,  μ^S̃⟩)^d
        ] 
    
        =   ∑_d=0^D 
         1/d![( 
         ⟨μ^S,  μ^S̃⟩(L +
         ∑_i=L+1^L+n 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, 

    ℒ_L+n^D^2     = ∑_d=0^D 
         1/d!_S,S̃[ 
         ⟨μ^S,  μ^S̃⟩ ^d ]
         _{R_j}_j[(L +
         ∑_i=L+1^L+nR_i
        )^d
        ].


We now separately analyze each of these two expectations, starting from the second one. 
By the Binomial formula,

    [(L +
         ∑_i=L+1^L+nR_i
        )^d
        ]    = 
         ∑_ℓ = 0^ddℓL^d-ℓ[
         (
         ∑_i=L+1^L+nR_i
        )^ℓ ] .

Note that for any odd integer ℓ,  the ℓ-th moment of the Rademacher's sum is zero. Therefore,

    [(L +
         ∑_i=L+1^L+nR_i
        )^d
        ] 
           = ∑_ℓ = 0^⌊d/2⌋d2ℓL^d-2ℓ[
         (
         ∑_i=L+1^L+nR_i
        )^2ℓ ] .


As analyzed in <cit.>

    [
         (
         ∑_i=L+1^L+nR_i
        )^2ℓ ] 
        ≤ n^ℓ (2ℓ - 1)!! 
          ,

where (2ℓ -1 )!! = (2ℓ - 1)(2ℓ - 3)⋯ 3· 1 =  
(2ℓ)!/2^ℓ ℓ!. Thus, 




    [(L +
         ∑_i=L+1^L+nR_i
        )^d
        ] 
           ≤ L^d∑_ℓ = 0^⌊d/2⌋d!/(d-2ℓ)! ℓ!(n/2L^2)^ℓ
        = L^d∑_ℓ = 0^⌊d/2⌋dℓ(n/2L^2)^ℓ(d-ℓ)!/(d-2ℓ)!.

Since (d-ℓ)!/(d-2ℓ)!
 = (d-ℓ)⋯ (d-2ℓ+1)≤ d^ℓ, then

    [(L +
         ∑_i=L+1^L+nR_i
        )^d
        ] 
          ≤  L^d∑_ℓ = 0^⌊d/2⌋dℓ(n d2L^2)^ℓ
    
            ≤ L^d∑_ℓ = 0^ddℓ(n d2L^2)^ℓ
         =L^d(1 +nd2L^2)^d
         = (L + nd/2L)^d.

Next, we analyze the first expectation 
_S,S̃[ 
     ⟨μ^S,  μ^S̃⟩ ^d ]
     in (<ref>). 
Recall that μ^S_j = √(λk){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,

    (G = m) = kmp-kk-mpk^-1.

From <cit.> this probability is upper bounded as follows

    (G = m) ≤km(k/p-k)^m.

Therefore, 

    _S,S̃[ 
         ⟨μ^S,  μ^S̃⟩ ^d ] 
         = λ^d/k^d[ 
         | S ∩S̃ | ^d ] = 
         λ^d/k^d∑_m=0^k m^d (G=m)
         ≤λ^d/k^d∑_m=0^k m^d km(k/p-k)^m.




Inserting (<ref>) and (<ref>) into  (<ref>) gives

    ℒ_L+n^D^2   ≤∑_d=0^D λ^d/d! k^d(L+nd/2L)^d ∑_m=0^k m^d km(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+n^D^2   
             ≤
          ∑_m=0^k  km(k/p-k)^m 
          ∑_d=0^D 
         1/d!(m(Lλ/k + nλ D/2Lk) )^d
          
       ≤∑_m=0^k  km(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_2k^γ/λ^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+n^D^2    ≤∑_m=0^k  km(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+n^D^2 ≤∑_m=0^k  km(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
c_2k^γ/2β k^2≤ϵ 
for sufficiently large k.
Therefore

    exp(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+n^D^2
           ≤∑_m=0^k  km(k/p-k)^m 
        (p-k)^m(2β +ϵ)
       =  ∑_m=0^k  km(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+n^D^2
           ≤(1+k/(p-k)^1/2 + α - β)^k .

Since k=⌊ c_1 p^α⌋, then as p→∞, the above behaves as

    (1+c_1/p^1/2-β(1+o(1)))^c_1 p^α

Therefore, for β < 1/2-α, as p→∞, 
ℒ_L+n^D^2 → O(1).







§ SSL ALGORITHM



 §.§ Proof of Theorem <ref>


We prove the theorem, assuming that 
 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 , 
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 <ref>.

    
    Let {(_i, y_i)}_i=1^L be L i.i.d. labeled samples from the mixture model (<ref>)
    with a vector μ of sparsity k=⌊ c_1 p^α⌋
    and nonzero entries ±√(λ/k). 
    Suppose that L = ⌈2β klog (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
    _L of Eq. (<ref>). 
    
    Then, for any  ϵ >0,
    
    lim_p→∞(|S ∩  S_L|/k≥ 1-ϵ) = 1.

    



As described above, we run  with β̃= β - ϵ̃, and denote by S_L the set found by the first step of the algorithm.
By Lemma <ref> this set satisfies Eq. (<ref>).

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 v̂_PCA 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 <cit.>, implies that with probability tending to 1, 

    lim_p→∞|⟨v̂_PCA, μ|_S_L/μ|_S_L⟩|= 1.

Since μ∈ℝ^p is a k-sparse with non-zero entries ±√(λk),  Eq. (<ref>) implies that μ|_S_L→√(λ), as p→∞.
Hence,

    lim_p→∞|⟨v̂_PCA, μ|_S_L/√(λ)⟩|= 1,



which implies that with the correct sign,

    lim_p→∞v̂_PCA - μ|_S_L√(λ)= 0.


From now we extend v̂_PCA which originally had dimension |S_L, to a p-dimensional vector with zeros in S_L^c. Hence, since μ|_S_L ^c→ 0, it follows 




    lim_p→∞v̂_PCA - μ/√(λ)= 0.



Next, let us assume by contradiction that there exist ϵ_0,δ_0 ∈ (0,1) such that for every p∈ℕ, 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. (<ref>), with probability at least δ_0

    lim_p→∞v̂_PCA |_Ŝ^2 = 
       lim_p→∞1/λμ |_Ŝ^2 
        = lim_p→∞1/λμ |_Ŝ∩ S^2
        = lim_p→∞|Ŝ∩ S|/k≤ 1-ϵ_0,

where the last inequality follows from the above assumption and |μ_j| = √(λ/k), for all j ∈ S.

Next, from (<ref>) and (<ref>) it follows that for any subset T that satisfies S_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.

However, since Ŝ is the set of the top-k indices of |v̂_PCA|, for any |T|=k, T⊂ S_L

    v̂^PCA |_Ŝ≥v̂^PCA |_T ,

which is a contradiction to (<ref>) and (<ref>).
Hence, for any ϵ>0, as p tends to infinity, (|S ∩Ŝ|k≥ 1-ϵ)→ 1, which  completes the first part of the proof. 

The second part of the proof follows from combining (<ref>) and Lemma <ref>.









§ PROOFS OF ADDITIONAL LEMMAS







First, note that the mean ν_x = [] = _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 expectation
    
    Σ = 
            
            1/p-k+1∑_j=k^p[ (-ν_x)(-ν_x)^⊤ |  S=s_j].

    where s_j = [k-1]∪{j} is a member of 𝕊̃.
    By definition, 
    
    ((-ν_x) | S=s_j) 
            
            = (θ^S_j - ν_x) + σξ
            =1/√(k) e_j - 1/√(k)(p-k+1) u   + σξ

    where 
    u = [ 0^⊤ _k-1 ,  1^⊤ _p-k+1 ]^⊤ 
    and { e_j}_j∈ [p] denote the standard basis of ℝ^p.
    Since ξ is independent of S, inserting (<ref>) into (<ref>) gives
    
    Σ   = 1/p-k+1∑_j=k^p[ 
            (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)∑_j=k^p  e_j  e_j^T
            -( u∑_j=k^p e_j^⊤
             + ∑_j=k^p  e_j  u^⊤) 
             +  u  u^⊤) + σ^2 𝐈_p

    
    Note that ∑_j=k^p e_j =  u. Thus,
    
    Σ
               = 1/k(p-k+1)^2( 
            (p-k+1)∑_j=k^p  e_j  e_j^T
            - u  u^⊤) + σ^2 𝐈_p
            
       ≼1/k(p-k+1)∑_j=k^p  e_j  e_j^T + σ^2 𝐈_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 𝐈_p.

    Therefore, 
    
    logdet(Σ)    ≤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)    .







By definition I(;S) = H() - H(|S). Hence, we first derive expressions for these two terms.

Since  follows the mixture model 
(<ref>), it is of the form = yμ^S + ξ. Given S=s, μ^s is deterministic with μ^s_j = √(λ/k) {j ∈ s}.



Thus, the  vector ( | S=s) is distributed as a mixture of two  Gaussians with centers ±μ^s and identity covariance matrix. Its density is

    f(|S=s)  = 1/(2π)^p/2( e^--μ^s^2 /2 + e^-+μ^s^2 /2/2)  = 
             e^-^2 + λ/2/(2π)^p/2(e^-⟨,μ^s⟩ + e^⟨,μ^s⟩/2).

By the definition of conditional entropy, 

    H(|S) =  
      -  ∑_s ∈𝕊  P(S=s) ∫ 
      f( |S=s) log f(|S=s)  d.

Given the structure of the vectors μ^s for all s∈𝕊̃, all the integrals in the sum above give the same value. 
Therefore, it suffices to consider a single set 
s_0 = {1, …,k},

    H(|S) = - ∫ f( |S=s_0) log f(|S=s_0) d.


Inserting (<ref>) into (<ref>), gives

    H(|S)    = -_|s_0[ log( e^-^2 + λ/2/(2π)^p/2cosh (⟨,μ^s_0⟩)
        
        
        ) ]  .

Note that for any s ∈𝕊̃, [^2|    S=s] = λ+p.
Thus, 

    H(|S)    = C(p,λ)  
        - _|s_0[ logcosh (⟨,μ^s_0⟩)
        
        ].

where C(p,λ) = λ +p/2(1+log(2π)). 

Consider the following two independent random variables, 
w = 1/√(k)∑_j=1^k-1ξ_j ∼ N(0, k-1/k) and ξ = ξ_k ∼ N(0,1). 
For S=s_0, 


    ⟨,μ^s_0⟩   = ⟨ y μ^s_0 + ξ,μ^s_0⟩ = 
        λ y + √(λ)w + √(λ)/√(k)ξ.

Inserting the above into (<ref>) gives

    H(|S)    = C(p,λ)
        -[ logcosh (λ 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 gives

    H(|S) = λ + p/2(1+log2π) 
        -[ logcosh(λ + √(λ)w + √(λ/k)ξ)
        ].






Next, we derive an expression for H(). Recall that  depends on
a vector μ^S with S distributed uniformly at random from 𝕊̃
of size p-k+1.
Note that 𝕊̃ = ⋃_ℓ=k^p s_ℓ
where s_ℓ = [k-1]∪{ℓ}. 
By the law of total probability 

    f() = 
         1/|𝕊|∑_s ∈𝕊 f(|S=s) = 1/p-k+1∑_ℓ=k^p f(|S=s^ℓ) .



Using the same analysis as before, it follows that

    f() = 
        e^-^2 + λ/2/(2π)^p/2·1/p-k+1∑_ℓ=k^p
         e^-⟨,μ^s^ℓ⟩ + e^⟨,μ^s^ℓ⟩/2.

Hence,

    H() = -[log f()] = C(p,λ) - [ log( 1/p-k+1∑_ℓ=k^p
         e^-⟨,μ^s^ℓ⟩ + e^⟨,μ^s^ℓ⟩/2)]




We now simplify the expectation in (<ref>).
First, by a symmetry argument, we may assume the label that corresponds to
 is simply y=1. Let us
simplify the inner product ⟨, μ^s_ℓ⟩.

    ⟨,μ^s_ℓ⟩   = ⟨√(λ)μ^S + ξ,μ^s_ℓ⟩
        =  λ(k-1/k + {ℓ∈ S}/k) + √(λ)w + √(λ)/√(k)ξ_ℓ.


Hence, the expectation above can be written as

    [ log( 1/p-k+1∑_ℓ =k^p
         e^-(λ(k-1)/k + √(λ)w + √(λ/k)ξ_ℓ + λ/k{ℓ∈ S})
         + e^(λk-1/k + √(λ)w +√(λ/k)ξ_ℓ+ λ/k{ℓ∈ S})/2)]

where the expectation is over S, w and {ξ_ℓ}_ℓ=k^p. 
Since S is uniformly distributed over 𝕊̃ 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 {ξ_ℓ}_ℓ=k^p.


Next, we decompose the sum inside the logarithm as S_1+S_2, where  

    S_1     =    exp(-λk-1/k - √(λ)w)/2·1/p-k+1∑_ℓ=k^p e^-√(λ/k)ξ_ℓ-λ/k{ℓ = k}
    
    S_2     =    exp(λk-1/k + √(λ)w)/2·1/p-k+1∑_ℓ=k^p e^√(λ/k)ξ_ℓ+λ/k{ℓ = 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 follows

    1/p-k+1∑_ℓ=k^p e^√(λ/k)ξ_ℓ
    +
    1/p-k+1 e^√(λ/k)ξ_k (e^λ/k -1 )

By the central limit theorem, asymptotically, the first sum may be written as
e^λ/2k + O_P(√(λ)/√(k p)), which follows from the
fact that 𝔼_Z∼𝒩(0,1) [e^t Z] = e^t^2/2. 
The second term above is O_P(√(λ)/k p), which is negligible w.r.t. to the
previous O_P term. 
Note that its expectation is finite and given by e^λ/2k(e^λ/k -1 )p-k+1.
The sum S_1 can be analyzed similarly. In summary we obtain that

    S_1 +S_2 = e^λ/2k·cosh(λk-1/k + √(λ) w) ·(1 + O_P(√(λ)/√(kp)) )

Hence, the expectation above  simplifies to

    [log(S_1+S_2)] = λ/2k + [logcosh(λk-1/k + √(λ) w)] + O(√(λ)/√(kp))


Inserting the above into (<ref>) gives
 
    H() = C(p,λ) - 
        [logcosh(λk-1/k + √(λ) w)] + O(√(λ)/√(kp))
            .





Next, we derive an upper-bound for the mutual information I(;S) = H() - H(|S). Combining (<ref>) and (<ref>), the constant 
C(p,λ) cancels out, and we obtain 

    I(;S)    =[ logcosh(
        λ + √(λ)w + √(λ/k)z
        ) - logcosh(λ(k-1)/k + √(λ)w)
        ] - λ/2k + O(√(λ)/√(kp)). 
       =[  g_w(√(λ/k)z ) - g_w (-λ/k) ] - λ/2k +
         O(√(λ)/√(kp)).



where g_w(t) =  logcosh( λ + √(λ)w + t). 
For future use, note that d/dt g_w(t) = tanh(λ + √(λ)w + t).
To upper bound I(;S) we split the expectation in (<ref>) into two parts as follows, 

    I(;S) = [ g_w(√(λ/k)z ) - g_w(0)] + 
         [g_w(0) - 
        g_w (-λ/k)
        ] -λ/2k + 
        O(√(λ)/√(kp)).

The Taylor expansion of g_w(t) is given by

    g_w(t) = g_w(0) + t tanh(λ + √(λ)w) + t^2/2(1 -  tanh^2(λ + √(λ)w)) + t^3/3!g_w^(3)(τ_t).

Here τ_t is some number between 0 and t, and g_w^(3)(τ_t) = -2tanh(λ + √(λ)w + τ_t) + 2tanh^3(λ + √(λ)w + τ_t).
Note that for all t∈ℝ, 

    t^3/3!g_w^(3)(τ_t)≤2|t^3|tanh(λ + √(λ)w + τ_t)/3! (1 -  tanh^2(λ + √(λ)w +τ_t))≤2|t^3|/3!.

Since z,w are independent and [z]=0, it follows that

    [ g_w(√(λ/k)z ) - g_w(0)]  
    ≤   [ √(λ/k)z tanh( λ +√(λ)w) + λ/2kz^2 (1 - tanh^2 (λ +√(λ)w )) +  2λ^3/2|z^3|/3! k^3/2] 
    
         =   λ/2k[1 - tanh^2(λ +√(λ)w )] + O(√(λ^3/k^3)).


For the second term in (<ref>), for any value of w,  
by the mean value theorem, it follows that

    g_w(0) - 
        g_w (-λ/k)
        = λ/ktanh (λ + √(λ)w +ζ_w) 
        ≤λ/ktanh (λ + √(λ)w)

where ζ_w ∈ [-λ/k,0], and the last inequality follows
from the fact that  
tanh(·) is a monotonically increasing function. Hence, 

    [g_w(0) - 
        g_w (-λ/k)
        ]≤λ/k[tanh (λ + √(λ)w )].

Hence, combining (<ref>),  (<ref>) and (<ref>), yields

    I(;S)    ≤λ/2k[1 - tanh^2(λ +√(λ)w )] + λ/k[tanh (λ + √(λ)w )] 
        - λ/2k +
        O(√(λ^3/k^3) + 
        √(λ)/√(kp)) 
       =λ/k[tanh (λ + √(λ)w ) - 1/2tanh^2(λ +√(λ)w )]
         +O(√(λ^3/k^3) + 
         √(λ)/√(kp)).



  

By Lemma <ref>, 


the expectation above can be bounded as follows:

    [tanh (λ + √(λ)w ) - 1/2tanh^2(λ +√(λ)w )] 
     ≤1/2(λ + 
      
      3√(λ/k)).

Hence, inserting  this upper bound into (<ref>), gives

    I(;S)    ≤1/2λ^2/k
            +O( 
            √(λ)/√(kp)+ √(λ^3/k^3))

Asymptotically, 
as p,k→∞ with k/p→ 0 then 1/k≫1/√(kp). 
Thus, the term 

1/2λ^2/k 
is asymptotically larger than the O(·) terms
in the display above. 
Hence, the inequality (<ref>) of the lemma follows.











    The main idea of the proof is to show that with a suitable choice of threshold τ, 
    nearly all entries _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 _L = 1/L∑_i=1^Ly_i_i.
    With minor adaptations one can also prove the Lemma with the original formula (<ref>) of _L.
    
   

    Fix ϵ > 0, and let 𝒜_L denote the event that |S_L ∩ S| ≥ k(1-ϵ). 
    For any threshold τ  define the following two events, 
    
    ℬ̃(τ) = {∑_j ∈ S{|_L(j)|>τ}> k(1-ϵ) },

    and
    
    𝒞̃(τ) = {∑_j ∉ S{|_L(j)|>τ}< p̃-  k }.

    By their definition, it follows that for any τ > 0
    
    ℬ̃(τ) ∩𝒞̃(τ) ⊆𝒜_L .

    Furthermore, note that the two events ℬ̃(τ) and 𝒞̃(τ) are independent. 
    Hence, to prove that (𝒜_L) → 1, it suffices to prove that for a suitable threshold τ, 
    
    (ℬ̃(τ) ∩𝒞̃(τ)) = 
        ( ℬ̃(τ) ) ·( 𝒞̃(τ) ) → 1

    In other words, it suffices to show that each of these events occurs with probability tending to one. 

    We start by showing that [ℬ̃(τ)]→ 1. First, let us define an even simpler event, with the absolute value removed, 
    
    ℬ(τ) = {∑_j∈ S{(μ_j) _L(j) > τ} > k (1-ϵ)
        }

    Clearly ℬ(τ) ⊂ℬ̃(τ) and thus it suffices to show that
    (ℬ(τ)) → 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 (<ref>), at support coordinates, 
    
    (μ_j) _L(j) = √(λ/k) + (μ_j)/√(L)ξ_j

    where ξ_j∼𝒩(0,1). 
Inserting this expression with L ≥2β k log (p-k)/λ into the above, and suppressing the
dependence on τ in ℬ(τ), gives

    (ℬ) 
           ≥   (∑_j ∈ S{
        1+√(1/2βlog (p-k))ξ_j> T}>k(1-ϵ)) 
        =    (∑_j∈ S{ξ_j > -(1-T)√(2βlog(p-k))} > k(1-ϵ)  ).

Next, we choose 


    T = 1 - 1/(2βlog(p-k))^1/4,

and define 

    q_1 = (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. (<ref>) simplifies to

    (ℬ) 
           ≥(
        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 (Bin(k,q_1) > kq_1(1-ϵ/2)). 
Indeed, by Chernoff's bound (<ref>), 

    (ℬ)≥
       1 - e^ϵ^2 kq_1/8

which tends to one as p,k→∞. 

Next, we show that the second term in Eq. (<ref>), (𝒞̃), also tends to one
as p→∞. 
First of all, since k=⌊ c_1p^α⌋ and α < 1-β < 1-β̃, then k ≪ p^1-β̃, and thus p̃ -k ≪p̃/2. 
Hence, for p sufficiently large, we may instead consider the following event

    𝒞(τ) = {∑_j∉ S{|_L(j)| > τ} < p̃/2}  = {
    Bin(p-k,q_2(τ)) < p̃/2}

where q_2(τ) =2 Φ^c(√(L)τ). 
Clearly 𝒞(τ) ⊂𝒞̃(τ), and we now prove that with τ = √(λk)T, and T  given in (<ref>)
(𝒞(τ)) → 1, by applying a Chernoff bound. 

To this end, we write

    p̃/2 = q_2 (p-k) (1+δ)

where δ = p̃/2(p-k)1/q_2 - 1.

To use Chernoff's inequality we first need to show that δ≥0.
Indeed, as p→∞, with τ = √(λ/k) T, and using Lemma <ref>
which bounds the tail function Φ^c, 

    lim_p→∞ (δ+1)    = 
    lim_p→∞p^1-β̃/2(p-k)1/ 2Φ^c(T√(2βlog(p-k)))
       ≥
    √(πβ)/2lim_p→∞ T√(log(p-k))/(p-k)^β̃exp(- T^2 βlog(p-k))
    = √(πβ)/2lim_p→∞ T√(log(p-k))/(p-k)^β̃- β T^2


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 (<ref>) gives 

    lim_p→∞ (δ+1) ≥√(πβ)/2lim_p→∞ T √(log(p-k)) = ∞.

Since  β̃<β, for sufficiently large p, and T  given in (<ref>) it follows that  β - β T^2<0.

Therefore, for sufficiently large p, it follows that δ>0.
By Chernoff's bound (<ref>) 


    (𝒞(√(λk)T)) = 
        (Bin(p-k,q_2) <  q_2 (p-k) (1+δ))
        ≥ 1-e^-δ^2(p-k)q_2/2+δ.


We now prove that the term in the exponent tends to infinity.
First, note that since δ→∞ then δ = p̃2(p-k)q_2 -1  ≥p̃4(p-k)q_2.
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 (<ref>) gives 
lim_p→∞(𝒞(√(λk)T)) = 1
which completes the proof.






    













§ THE MLE IN THE SUPERVISED SETTING







The following proposition presents the form of the maximum likelihood estimator (MLE) for the support S in a fully supervised setting, where the sparsity k is assumed known, and the non-zero entries of μ have magnitude ±√(λ/k).


        
        Let {(_i, y_i)}_i = 1^L be L i.i.d. labeled samples  
        from model (<ref>) where  is k-sparse with non-zero entries
        ±√(λ/k), 
and let _L = 1/L∑_i∈ [L]y_i _i. 
         Assuming the sparsity k is known,
         the MLE for S=() is  given by the indices corresponding to the top-k magnitudes of _L.
        


    
    Under our assumptions, the set of all possible vectors μ has a one-to-one mapping to 
    a support set 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.

    
    Let us denote by p_X,Y(,y; θ) the joint probability density function of a single sample (,y) 
    from the model (<ref>) with parameter θ.
    Since y is a Rademacher random variable with a distribution not dependent on θ, we may write
    
    
    p_X,Y(,y ;θ) = p_X|Y(|y; θ)   p_Y(y) =12 p_X|Y(|y; θ) .

    Since |y ∼𝒩(yμ,𝐈_p), 
    
    the conditional density p_X|Y(|y; θ) simplifies to
    
    p_X,Y(|y, θ) = 1/(2π)^p/2exp(- - y μ^θ^2 /2 ).


    By definition, the maximum-likelihood estimator of θ  is given by 
    
    θ̂^() = 
            
            _θ∑_i=1^L
            log p_X,Y(,y ;θ),

    
    Inserting (<ref>) into the above, and using μ ^θ=√(λ) (fixed for all θ), gives
    
    
    θ̂^() = _θ∑_i=1^L
            (-_i - y_i μ^θ^2)= 
            _θ̂∑_i=1^L ⟨ y_i_i, μ^θ⟩ =  
           
           _θ⟨_L , μ^θ⟩.

    
    Therefore, the maximum value of ⟨_L , μ^θ⟩ is obtained for Ŝ^() being the set of indices corresponding to the k largest magnitude
    entries of _L, and 
    D̂^() = {(_L)_j:   j ∈Ŝ^()}.











The next proposition shows that with sufficient number of labeled samples the MLE
for S has significant overlap with the true support set S. 



    
    Let 𝒟_L = {(_i, y_i)}_i=1^L be  a set of L i.i.d. labeled samples from the model (<ref>) 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β klog (p-k)/λ⌉, for some β∈ (0,1).
    Let S_L be the indices of the  k largest magnitudes  of the vector
    _L = 1/L∑_i∈ [L]y_i _i. 
    
    If β>1-α, then for every ϵ∈ (0,1),
    
    lim_p →∞(|S ∩ S_L |/k>1-ϵ)  = 1.

    


    Fix ϵ > 0, and let 𝒜_L denote the event that |S_L ∩ S| ≥ k(1-ϵ). 
    For any threshold τ define the following two events, 
    
    ℬ̃(τ) = {∑_j ∈ S{|_L(j)|>τ}> k(1-ϵ) },
        𝒞̃(τ) = {∑_j ∉ S{|_L(j)|>τ}< kϵ}.

    By their definition, it follows that for any τ > 0, ℬ̃(τ) ∩𝒞̃(τ) ⊂𝒜_L.
    Since the two events ℬ̃(τ) and 𝒞̃(τ) are independent, 
    
    (𝒜_L) ≥(ℬ̃(τ) ∩𝒞̃(τ)) = 
        ( ℬ̃(τ) ) ·( 𝒞̃(τ) )

    Hence,  for (𝒜_L) → 1, it suffices that for a suitable threshold τ, both probabilities on the right hand side tend to one, 

    We start with (ℬ̃(τ)). To this end, we define an even simpler event, with the absolute value removed, 
    
    ℬ(τ) = {∑_j∈ S{(μ_j) _L(j) > τ} > k (1-ϵ)
        }

    Clearly ℬ(τ) ⊂ℬ̃(τ) and thus it suffices to show that
    (ℬ(τ)) → 1 as p→∞. 
    By the sparse mixture model (<ref>), for j ∈ S,
    
    (μ_j) _L(j) = √(λ/k) + (μ_j)/√(L)ξ_j,

    where ξ_j ∼𝒩(0,1).
    Combining a threshold value τ = √(λ/k1-α +β/2β) 
    and the assumption that L ≥2β k log(p-k)/λ 
    with this expression, gives that
    
    ( ℬ(τ)) ≥(∑_j ∈ S{ξ_j>- (√(β) - √(1-α+β/2))√(2log p)}>k (1-ϵ)).

    Let q_1 be the probabiity of each event in the above sum, 
    
    q_1 = (N(0,1)>-(√(β) - √(1-α+β/2))√(2log p)).

    Since the ξ_j's are all independent and |S|=k, with this choice of τ, Eq. (<ref>) simplifies to
    
    ( ℬ(τ)) ≥(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 (Bin(k,q_1) > kq_1(1-ϵ/2)).  
    Indeed, by Chernoff's bound (<ref>), (ℬ(τ))→ 1 as p,k→∞, since 
    
    (ℬ)≥
           1 - e^-ϵ^2 kq_1/8.



    
Next, we show that the second term in Eq. (<ref>), (𝒞̃), also tends to one
as p→∞. 
First, note that

    𝒞̃ (τ) =  {
    Bin(p-k,q_2(τ)) < kϵ}

where q_2(τ) =2 Φ^c(√(L)τ) = 2 Φ^c(√((1-α +β)log(p-k))). 
We now prove that (𝒞̃(τ))→ 1, by applying a Chernoff bound. 
To this end, we write

    kϵ = q_2 (p-k) (1+δ)

where δ = kϵ/(p-k)1/q_2 - 1.

To use Chernoff's inequality we first need to show that δ≥0.
Indeed, as p→∞,  using Lemma <ref>
which bounds the tail function Φ^c, 

    lim_p→∞ (δ+1)    ≥lim_p→∞ϵ k/p-k1/ 2 Φ^c(√((1-α +β)log(p-k)))
    
       ≥ϵ c_1 √(π(1-α + β)/2)lim_p→∞√(log(p-k))/p^1-αexp(-1-α +β/2log(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 (<ref>) 


    (𝒞̃(τ)) = 
        (Bin(p-k,q_2) <  q_2 (p-k) (1+δ))
        ≥ 1-e^-δ^2(p-k)q_2/2+δ.


We now prove that the term in the exponent tends to infinity.
Since δ→∞ it follows that 



    lim_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 (<ref>) gives that lim_p→∞(𝒞̃(τ)) = 1, 
which completes the proof.

The above proposition implies the following result regarding accurate classification: 
Let T() = ⟨, ⟩, with = _L |_S_L, be a linear classifier that is constructed using only the set of labeled samples _L.  If β > 1-α, 
then combining Proposition <ref> and Lemma <ref> implies that the excess risk of T tends to zero as p→∞. 














 §.§ Impossibility of Classification

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 = √(λ / k) B_j, where B_j ∼ Ber (ϵ_p) are i.i.d. Bernoulli random variables with 
ϵ_p = kp = p^-(1-α).
The next theorem implies that in the red region (impossible) of figure <ref>, indeed there exists (approximately) k-sparse vectors for which any classifier would asymptotically be no better than random. 

        Let 𝒟_L={(_i, y_i)}_i=1^L  be  set of L i.i.d. labeled samples from the rare weak model 
        𝒩(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 𝒟_L, tends to 1/2 as p→∞.
        
    
    

    This proof is similar to the one of <cit.>.
    First, let us denote the vector of z-scores by = 1√(L)∑_i∈[L]y_i _i.
    Since the entries of  are generated independently under the rare-weak model, 
    the entries of  are also independent and all have the same density, which we denote by f(z). 
    Given , we denote the conditional probability that the j-th entry contains a feature by η = (j∈ S | )= (j∈ S| z_j = z). 
    By Bayes theorem,
    
    η(z) = (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 <cit.>, the misclassification error of any classifier T constructed using the set _L, can be bounded as
    
    | (T()≠ y ) - 1/2 |< 
            C (1-(_z[H(z)])^p )^1/2,

    where  H(z) =_x[(1 + η(z)(  e^√(λ/k)x - λ/2k-1))^1/2] 
    
    with x∼ N(0,1), and z ∼ (1-ϵ_p)N(0,1) + ϵ N(τ_p,1).
    

    Our goal is to show that  _z[H(z)] = 1+o(1/p), which implies that asymptotically the accuracy of T is no better than random.
    First, combining that _x[e^√(λ/k)x - λ/2k - 1] = 0 and the inequality |√(1 + t) - 1 - t/2|≤ Ct^2, for any t>-1, gives
    
    
    |H(z) - 1|  
               =
            |H(z) - 1- 12[η(z)][e^√(λ/k)x - λ/2k - 1] |
            
       ≤ 
            Cη^2 (z) _x[(e^√(λ/k)x - λ/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|  ≤C̃ p^-αη^2 (z). 
    Hence, to prove that  _z[H(z)] = 1+o(1/p), it suffices to show
    that _z[η^2 (z)] = o(p^-(1-α)) = o(ϵ_p).
    To this end, we first note
     
    [η^2(z)] = (1-ϵ_p)[η^2(w)] + ϵ_p[η^2(w+τ_p)] ≤[η^2(w)] + ϵ_p[η^2(w+τ_p)],

     where w∼ N(0,1).
     Write (η^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, 
    
    I = ∫_-∞^t_1η^2(w) ϕ(w) dw,
            
              
            II = ∫_t_1^∞η^2(w) ϕ(w) dw,

    and
    
    III = ϵ_p∫_-∞^t_2η^2(w+τ_p) ϕ(w) dw,
            
              
            IV = ϵ_p ∫_t_2^∞η^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 =  ∫_-∞^t_1(ϵ_p ϕ(w-τ_p)/(1-ϵ_p)ϕ(w) + ϵ_p ϕ(w-τ_p))^2 ϕ(w) dw 
        
           ≤∫_-∞^t_1(ϵ_p ϕ(w-τ_p)/(1-ϵ_p)ϕ(w))^2 ϕ(w) dw

    For large enough p, the above can be bounded via
    
    I ≤2ϵ_p ^2∫_-∞^t_1ϕ^2(w-τ_p)/ϕ^2(w)ϕ(w)dw
        
        
        
        = Cϵ_p ^2∫_-∞^t_1 e^2wτ_p - τ_p^2 - w^2/2dw,

    where the equality follows from the definition of ϕ(w).
    
    Completing the square, the above can be written as
    
    I   ≤   Cϵ_p ^2∫_-∞^t_1 e^-(w - 2τ_p)^2 / 2  e^τ_p^2 dw.

    Changing the variable x = w-2τ_p reads
    
    I    ≤   Cϵ_p ^2 e^τ_p^2∫_-∞^t_1-2τ_p e^-x^2 / 2 dx =    Cϵ_p ^2 e^τ_p^2Φ^c (2τ_p - t_1)
           ≤ C ϵ_p ^2 e^τ_p^2 e^-(2τ_p - t_1)^2 /2

    Finally, since β<1-α, it follows that C ϵ_p ^2 e^τ_p^2 e^-(2τ_p - t_1)^2 /2 = o(ϵ_p).

    Next, since η(w)<1 it follows that
    
    II     =  ∫_t_1^∞η^2(w) ϕ(w) dz 
        ≤∫_t_1^∞ϕ(w) dw  = Φ^c(t_1) ≤ e^-t_1^2/2.

    Similar to the above, under the condition β<1-α it holds that e^-t_1^2/2 = o(ϵ_p).

    Next, note that
    
    III    =  ϵ_p∫_-∞^t_2(ϵ_p ϕ(w)/(1-ϵ_p)ϕ(w+τ_p) + ϵ_p ϕ(w))^2 ϕ(w) dw 
       ≤ϵ_p∫_-∞^t_2(ϵ_p ϕ(w)/(1-ϵ_p)ϕ(w+τ_p))^2 ϕ(w) dw.

    For large enough p
    
    III ≤ 
        Cϵ_p∫_-∞^t_2(ϵ_p ϕ(w)/ϕ(w+τ_p))^2 ϕ(w) dw 
        =Cϵ_p ^3∫_-∞^t_2 
          e^2wτ_p + τ_p^2 - w^2/2dw  
        .

    Completing the square reads
    
    III ≤ 
            Cϵ_p ^3 e^3τ_p^2∫_-∞^t_2 
          e^-(w-2τ_p)^2 /2dw = 
           Cϵ_p ^3 e^3τ_p^2Φ^c(2τ_p - t_2) ≤ Cϵ_p ^3 e^3τ_p^2 e^-(2τ_p - t_2)^2 /2.

    Since β≤ 1-α it holds that III = o(ϵ_p).
    
    Finally, since η(w)<1, IV can be bounded as follows
    
    IV = ϵ_p ∫_t_2^∞ϕ(w) dw = ϵ_pΦ^c(t_2) ≤ϵ_p e^-t_2^2 /2  .

    Again, by β<1-α, IV = o(ϵ_p).




