# Maximum level of label noise for binary classification so that dataset is “Learnable”?

Assume we have an imbalanced dataset (minority label frequency 1-20%), where subset of samples have their labels randomly flipped. Now, of all samples with positive label (the minority class) in this flipped dataset, if less than 50% are actually positive, is it still possible to "learn" about this class using any classifier?

This paper suggests at one place that "In order to guarantee the convergence", for any class $$k$$ , among all samples belonging to $$k$$ in flipped dataset, majority of samples should originally be of label $$k$$. It doesn't prove that claim, or cite anyone.

I'm currently working with a set of software defect predictions data with both label noise and imbalance, where this above mentioned condition is broken. I also have access to original labels, and can see that in some cases only 15% of samples labeled positive in flipped dataset are actually positive. So my question is, shouldn't it be impossible to learn from this flipped binary classification datasets? (most samples of negative class are actually negative)

With a Random Forest, these datasets usually have very low recall, both high & low precision, and pretty high roc-auc.