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- α$. 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 $α$. In this paper, we characterize the effect of $α$ by establishing the information-theoretic and computational boundaries, namely, the ...