  In learning with noisy labels, the sample selection approach is very popular,
which regards small-loss data as correctly labeled during training. However,
losses are generated on-the-fly based on the model being trained with noisy
labels, and thus large-loss data are likely but not certainly to be incorrect.
There are actually two possibilities of a large-loss data point: (a) it is
mislabeled, and then its loss decreases slower than other data, since deep
neural networks "learn patterns first"; (b) it belongs to an underrepresented
group of data and has not been selected yet. In this paper, we incorporate the
uncertainty of losses by adopting interval estimation instead of point
estimation of losses, where lower bounds of the confidence intervals of losses
derived from distribution-free concentration inequalities, but not losses
themselves, are used for sample selection. In this way, we also give large-loss
but less selected data a try; then, we can better distinguish between the cases
(a) and (b) by seeing if the losses effectively decrease with the uncertainty
after the try. As a result, we can better explore underrepresented data that
are correctly labeled but seem to be mislabeled at first glance. Experiments
demonstrate that the proposed method is superior to baselines and robust to a
broad range of label noise types.
