  Prior works have shown that semi-supervised learning algorithms can leverage
unlabeled data to improve over the labeled sample complexity of supervised
learning (SL) algorithms. However, existing theoretical analyses focus on
regimes where the unlabeled data is sufficient to learn a good decision
boundary using unsupervised learning (UL) alone. This begs the question: Can
SSL algorithms simultaneously improve upon both UL and SL? To this end, we
derive a tight lower bound for 2-Gaussian mixture models that explicitly
depends on the labeled and the unlabeled dataset size as well as the
signal-to-noise ratio of the mixture distribution. Surprisingly, our result
implies that no SSL algorithm can improve upon the minimax-optimal statistical
error rates of SL or UL algorithms for these distributions. Nevertheless, we
show empirically on real-world data that SSL algorithms can still outperform UL
and SL methods. Therefore, our work suggests that, while proving performance
gains for SSL algorithms is possible, it requires careful tracking of
constants.
