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 minimax-optimal statistical accuracy that can be achieved by all algorithms, and polynomial-time algorithms under an oracle computational model. For small α, 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 α 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.
This paper proposes to investigate the theoretical limits, both from a statistical point of view (minimax theory) and from a computational point of view the limits of estimators in the context on weakly supervised learning. In their model, a fix proportion of the labels are draw according to a uniform sampling (the complement are the true labels). The authors provides bound showing that there are regimes where the corruption of the label slows down both the minimax rates and the computationally feasible rate. Their technical tools really on testing theory as well as on a "computational (oracle) model". 
This paper is interesting and deals with new kind of results introducing computational aspects in standard minimax theory. The phenomenon illustrated is new to me, and present some limitation of the computationally tractable algorithm w.r.t. "theoretical" ones that could be considered in the classical minimax theory. However, due to the relative novelty of the framework, it would be important that basic definitions and properties be better presented.   specific comments:   l18:remove / clarify this part. In the following there is only one model investigated. Please introduce only the one used (no missing values later on...).  l24/27/29: "See e.g. [...] for a survey" repeated 3 times in 3 lines...  l43: by a standard reduction argument [39]. Please provide details page/results for books.  l49: log d/n is ambiguous. Please use adapted parenthesis everywhere.  l74: the drawback raised "hinge on planted clique" should be described with more details and explain why the authors do not suffer the same issue here.  l86: notations - > notation. Also it could be given earlier since some quantities where used before being introduced (eg max sign, \Omega etc.)  l138 (Definition 2.2). This definition could be more commented and written more carefully. For instance, what the index T stands for is not that clear, especially in (2.5) there is no T, though the line below refers to R(\xi,n,T,\eta) as the set of oracles satisfying (2.5)...  I believe that this part is for the community the one with the main novelty, so spending more time on describing it, and giving examples could be helpful. For instance the point raised on line 154 could be explained with more details.  l167: why is \eta chosen of the order d^\eta?  l214: (3.7) could be written with the expression given in the Appendix, l477. That would make it easier to understand where it the test is coming from.  l225: "the" is missing before "test function".  l234: "not computationally tractable": this term is not defined/precise here. To me it is tractable... in a long long time...So this difficulty should be linked with the framework introduced by the authors.  l276: in in  - > in  l283: the quantity z_q_j and \tilde z_q_j are not clearly introduced. What are they?  l296: "the" is missing before "test function", and "an diagonal" should be "a diagonal"  l302: q(Y,X,Y',X) should be q(Y,X,Y',X').  l314: I guess if one estimate \Delta_\mu an estimator of this quantity should be written \widehat{\Delta_\mu} rather than \Delta_\hat{\mu}  l398: the year is wrong in the citation, it should be 2009  Appendix:  l420: Pinsker's inequality could be given a (book) reference for the interested reader.  l454: ".." one dot is enough.  l466: "we introduce random vector W" - >  we introduce the random vector W  l482: the lemma cited give the inequality for the operator norm. Please provide the similar version for the l2 norm considered, or the way to derive it from the other.  l489: I suspect a typo in the control of the probability. Please double check.  l492: "Recall that \phi_1" - >  Recall that \phi_2  l585: please use align correctly.  l629: the sentence is weird...  l640: before you used another sign for the max of two quantities. Please be consistent.