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.
Strengths
The paper makes advances in an important research direction of theory for understanding semi-supervised learning
The paper has a nice conceptual message in identifying a setting where there is a provable benefit to combining labeled and unlabeled data, proving both upper and lower bounds (under commonly believed computational assumptions). It is also nice that the main algorithm gives a clean way to combine two different types of information.
The algorithm in the paper is simple enough to implement and the authors are able to support their conclusions with numerical experiments
Weaknesses
The paper only studies a limited setting of a mixture of two Gaussians
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