More Supervision, Less Computation: Statistical-Computational Tradeoffs
  in Weakly Supervised Learning
  We consider the weakly supervised binary classification problem where the
labels are randomly flipped with probability $1- {\alpha}$. Although there
exist numerous algorithms for this problem, it remains theoretically unexplored
how the statistical accuracies and computational efficiency of these algorithms
depend on the degree of supervision, which is quantified by ${\alpha}$. In this
paper, we characterize the effect of ${\alpha}$ by establishing the
information-theoretic and computational boundaries, namely, the minimax-optimal
statistical accuracy that can be achieved by all algorithms, and
polynomial-time algorithms under an oracle computational model. For small
${\alpha}$, our result shows a gap between these two boundaries, which
represents the computational price of achieving the information-theoretic
boundary due to the lack of supervision. Interestingly, we also show that this
gap narrows as ${\alpha}$ increases. In other words, having more supervision,
i.e., more correct labels, not only improves the optimal statistical accuracy
as expected, but also enhances the computational efficiency for achieving such
accuracy.
