More Supervision, Less Computation: Statistical-Computational Tradeoffs in Weakly Supervised Learning

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