Decoupling "when to update" from "how to update"
Deep learning requires data. A useful approach to obtain data is to be creative and mine data from various sources, that were created for different purposes. Unfortunately, this approach often leads to noisy labels. In this paper, we propose a meta algorithm for tackling the noisy labels problem. The key idea is to decouple "when to update" from "how to update". We demonstrate the effectiveness of our algorithm by mining data for gender classification by combining the Labeled Faces in the Wild (LFW) face recognition dataset with a textual genderizing service, which leads to a noisy dataset. While our approach is very simple to implement, it leads to state-of-the-art results. We analyze some convergence properties of the proposed algorithm.
Summary
The paper proposes a meta algorithm for training any binary classifier in a manner that is robust to label noise. A model trained with noisy labels will overfit them trained for too long. Instead, one can train two models at the same time, initialized at random, and update by disagreement: the updates are performed only when the two models' prediction differ, a sign that they are still learning from the genuine signal in the data (not the noise); and instead, defensively, if the models agree on their predictions and the respective ground truth label is different, they should not perform an update, because this is a sign of potential label noise. A key element is the random initialization of the models, since the assumption is that the two should not give the same prediction unless they are close to converge; this fits well with deep neural networks, the target of this work.
The paper provides a proof of convergence in the case of linear models (updated with perceptron algorithm and in the realizable case) and a proof that the optimal model cannot be reach in general, unless we resort to restrictive distributional assumptions (this is nice since it also shows a theoretical limitation of the meta-algorithm). The method works well in practice in avoiding to overfit labels noise, as shown by experiments with deep neural networks applied to gender classification on the LFW dataset, and additional tests with linear models and on MNIST.
Comments
The paper is very well written: the method is introduced intuitively, posed in the context of the relevant literature, proven to be sound in a simple theoretical setting and shown to be effective on a simple experimental set up, in realistic scenario with noise. Additionally, this work stands out from the large set of papers on the topic because of its simplicity and the potential of use in conjunction with others methods.
Proofs are easy to follow and seem flawless. Experimental results are promising on simple scenarios but will need future work to investigate the robustness and effectiveness on at scale and in multi-class  --- although I don't consider this a major issue because the paper is well balanced between theory and practice.
Also, do you find any interesting relation with boosting algorithms? In particular I am referring to "The strenght of weak learnability" by R. Schapire, that introduced a first form (although impractical) of boosting of weak classifier. The algorithm presented back then uses a form of "update by disagreement" for boosting, essentially training a third model only on data points classified the same way by the former two models.
Minors
25 -> better
107 -> probabilistic
183 -> algorithm