Learning with Noisy Labels
In this paper, we theoretically study the problem of binary classification in the presence of random classification noise -the learner, instead of seeing the true labels, sees labels that have independently been flipped with some small probability. Moreover, random label noise is class-conditional -the flip probability depends on the class. We provide two approaches to suitably modify any given surrogate loss function. First, we provide a simple unbiased estimator of any loss, and obtain performance bounds for empirical risk minimization in the presence of iid data with noisy labels. If the loss function satisfies a simple symmetry condition, we show that the method leads to an efficient algorithm for empirical minimization. Second, by leveraging a reduction of risk minimization under noisy labels to classification with weighted 0-1 loss, we suggest the use of a simple weighted surrogate loss, for which we are able to obtain strong empirical risk bounds. This approach has a very remarkable consequence -methods used in practice such as biased SVM and weighted logistic regression are provably noise-tolerant. On a synthetic non-separable dataset, our methods achieve over 88% accuracy even when 40% of the labels are corrupted, and are competitive with respect to recently proposed methods for dealing with label noise in several benchmark datasets.
Overall, I found the paper quite well-written. 
      I think the assertion in the abstract (and then again in the 
      Experiments section), that you learn with 88% accuracy when 80% labels 
      are flipped is incorrect. You are only flipping 40% of the labels (the 
      probability of flip is convex combination of \rho_+ and \rho_- and not 
      their sum). In any, case the goal is to get better accuracy as noise 
      rate goes to half, not one (where the problem is trivially easy with 
      just all labels flipped). I wonder if it is worthwhile to 
      compare your methods with Kearns' SQ setting. Since minimizing a 
      convex loss can be done by gradient methods (which have statistical 
      analogues). And so you would get tolerance to random classification 
      noise for free. (Kearns does not allow class-conditional noise, but I 
      think that part can be handled easily.) I'm not sure what kind of 
      excess risk bounds you would get by such SQ-simulation. Minor 
      quibbles: -------------- 1. You use the term PU learning, without 
      ever defining it. 2. You use "so-called" very often. Especially for 
      zero-one loss. Why is it so-called? If you have objection to the name 
      you should state it. --- Update: Regarding using the SQ model. 
      Even if you are using surrogate loss, your optimization problem can be 
      solved using an algorithm that only makes statistical queries rather than 
      data points.