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

We thank the reviewer for the constructive comments. We address the issues raised one by one.

(0) We agree that our proposed LSPCA method is tailored to our specific case of a mixture of two Gaussians. However, we believe that the insights of our work, proposing a two step SSL scheme, using the labeled data for feature screening could motivate the future development of practical SSL methods for high dimensional settings.

(1) We will add an explanation near L133 why vectors with non-zero entries of size $\sqrt{\lambda/k}$ are the most difficult.

(2) Our text is correct. The reason is that we work with an equivalent model where the noise level is $\sigma=1/\sqrt{\lambda}$ instead of $\sigma=1$. We will clarify the text.

(3) The lower bound in Corollary 2.4 is indeed not necessarily tight. We will explicitly mention this in the revision. Please note that given $S$, by the definition of our model, the labeled and unlabeled samples have statistically independent Gaussian noises, so this is not an extra assumption.

(4) Regarding tightness of Theorem 2.3: Please note that its proof is based on Fano's lemma. Hence, whenever this lemma is not tight then the theorem would be not tight as well.

(5) Indeed the proof of Theorem 2.6 is incorrectly referenced as proof of Theorem 4. Thanks for catching this typo. which we will correct.

(6) In the proof of Theorem 2.6, the distibutions $\mathbb{Q}$ and $\mathbb{P}$ are exactly those in equations (8) and (9). Critically, even in the SSL setting the distribution $\mathbb{Q}_{L+n}$ consists of pure isotropic Gaussian noise vectors. We test between (8) and (9) since we follow the machinery of the low-degree likelihood ratio framework, which provides us with lower bounds. We will revise the first few sentences of the proof to better explain all of these points.

(7) Regarding theorem 3.2, please note that it is stated for $k$ sparse vectors whose non-zero entries are $\pm \sqrt{\lambda/k}$, see second line of theorem, L302.

We thank the reviewer for the positive comments and encouraging feedback.

Regarding the question in L59 "On the computational side, is there a computational-statistical gap in SSL?" The answer is yes. We will modify the text in lines L70-76 to explicitly mention that by adding too few labeled samples, there is still a computational statistical gap (the orange region in Figure 1).

Regarding the white "hole" in Figure 1, we do not know if the computational-statistical gap remains. We conjectured that the gap still remains in this region. See the text L107-8.

We will revise the paragraph starting on L86 to clarify what are novel results and include references to the relevant theorems that appear later on in the manuscript.

Regarding the reduction in Eq. (3), we will clarify this reduction in the revised version.

Regarding an information theory lower bound in the white "hole" region: From an information-theoretic perspective, for $\gamma>1$, there exists a non-polynomial-time algorithm that succeeds in recovering the support, that uses only the unlabeled samples. Hence, since the white "hole" region is a sub-region of $\gamma>1$, the same holds for this region as well.

Regarding an analysis of LS$^2$PCA, please note that this would depend on the specific sparse-PCA method employed. In our manuscript we employed the IPU method of Tian el al. We currently do not have insight how to analyze it in our context. This is an intersting question for future work.

We thank the reviewer for the constructive comments.

We agree with the referee regarding context of figure 1. We will add that the red and green regions follow from previous works, whereas the orange and blue are our novel contributions. We also reference the relevant theorems for these.

Regarding Theorem 2.3 and Corollary 2.4, we will rewrite it with $\alpha$ replaced by some other symbol, say $q\in(0,1)$ to avoid possible confusion with the sparsity level $k=p^\alpha$. The goal of this theorem and corollary was to derive an information theoretic lower bound in the SSL case. We will clarify this and the meaning of the two theoretical statements in the revision.

Regarding Theorem 2.1, we agree that as originally stated it is weaker than the result of Donoho and Jin. The reason is that we considered the case where the probability of error in exact support recovery is bounded by 1/2. In the revision we will replace it by the following result (which still follows from the original proof without any required changes): Let $\delta \in (0,1)$. If $L < (1-\delta)\frac{2k}\lambda \log(p-k+1)$, then for any support estimator $\hat S$ based on $\mathcal D_L$, $\Pr(\hat S\neq S) \geq \delta$. This results shows that exact support recovery is not possible with probability tending to one even for $\beta > 1-\alpha$. We will also discuss the relation between this result and those of Donoho and Jin (which are not about exact support recovery, but rather for approximate support recovery, namely $|\hat S \cap S|/k\to 1$ as $p\to \infty$).

Regarding motivation for our conjecture: As derived by Donoho and Jin (05'), in the fully supervised (SL) setting there is a detection-recovery gap; Namely for a range of number of labeled samples, it is possible to detect that a sparse signal is present, but it is not possible to reliably recover its support. Intuitively, adding a few unlabeled samples should not resolve this gap. We will add a discussion about this issue in the revision.

We thank the reviewer for the thoughtful review.

We agree that our work considers a limited case of two Gaussians. We remark that many previous authors also considered a same or similar setting. Indeed, it would be interesting to extend to larger number of Gaussians. However, as the SSL analysis was far from trivial already for only two Gaussians, such an extension is beyond the scope of this work.

Regarding the benefit of unlabeled data. First, note that if $n=k^\gamma$ with $\gamma > 2$, recovering the support is computationally tractable using only the unlabeled samples. Indeed, in the regime $n=k^\gamma$ with $\gamma<2$ and $k=p^\alpha$, the unlabeled data decreases the number of labeled samples by a factor $(1-\alpha)/(1-\gamma\alpha)$. This factor can be much larger than 2 if $\alpha$ is close to 1/2 and $\gamma$ is close to 2. We will clarify this in the revision.

The regime where our computationally efficient SSL provably works is the blue triangle in figure 1. We will add in the introduction a precise description of this region, in particular the formula for the blue line $\beta = 1-\gamma \alpha$.