Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes two regularization methods for learning on noisily labeled data: the first penalizes the distance w.r.t. Euclidean norm from an initial point and the second uses an additional auxiliary variable for each example to learn a noise. In the theoretical part, the paper shows that an original clean dataset can be learned from a noisily labeled dataset based on NTK-theory. Finally, the effectiveness of proposed regularization methods is well verified empirically for 2-layer NN, CNN, and ResNet on image classification tasks (MNIST, CIFAR-10).

Contributions:
- Propose two simple regularization techniques for learning from a noisily labeled dataset.
- Give generalization guarantees for these methods

Clarity:
The paper is well organized and easy to read.

Quality:
The work is of good quality and is technically sound.

Significance:
Since proposed methods are in some sense related to the early-stopping for the (stochastic) gradient descent, the developed theory is useful in understanding the generalization ability of over-parameterized neural networks falling into NTK-regime. Although an additive noise setting for the regression problem is rather common in statistical learning theory, an artificially flipped label setting for the classification problem may be new except for a few recent studies [Li+(2019)]. A result (Theorem 5.1) for the regression problem with the squared loss is not so surprising because the generalization error of gradient descent in a high-dimensional space (e.g., over-parameterized NNs) or an RKHS (i.e., infinite-dimensional model) has been well studied and the generalization error is composed of the (constant) variance and the distance between the model output and the true label. Thus, existing results of generalization error analyses for the regression are directly applied to bound the prediction error for clean labels. However, I basically like this paper and I think this paper makes a certain contribution to understanding the effect of over-parameterization.

A few questions:
- Usually, the regularization parameter goes to zero as the number of examples increases. Conversely, the regularization parameter in the proposed methods also increases. Could you explain why this difference happens?
- In classification tasks, the original problem setting is recovered by setting $p=lamba=0$. However, the generalization bound by Theorem 5.3 is still affected by $\lambda$. Is this theorem tight?

-----
Update: 
I thank the authors for the response. I have read the revised version of the paper and have confirmed an improvement of Theorem 5.2. I will keep my score. This paper is of good quality.
review_title: Official Blind Review #1

final_score: rating: 8: Accept
review_content: In this paper, based on the effectiveness of early stopping in the training of noisily labeled samples, the authors proposed two intuitive (and novel) regularization methods: (1) regularizing using distance to initialization (2) adding an auxiliary variable b_i for every input x_i during training. In terms of theory, the authors showed that in the NTK regime, both regularization methods trained with gradient descent are equivalent to kernel ridge regression.  Moreover, the authors also provided a generalization bound of the solution on the clean data distribution when trained with noisy label, which was not addressed in previous research.

Overall, the paper is very well-organized and well-written. The contribution of the paper is significant, and numerical results also vindicate the theory developed in the manuscript. I recommend accepting the paper.

Two minor questions that are not going to affect my rating:
1. The theory developed in the paper depends highly on NTK. What if the network is not sufficiently wide (which is usually the case in practice), and the loss function is not L2?
2. In the second method using the auxiliary variable, it seems that every training sample x_i needs a variable b_i. Is this going to cause any problem in practice if data augmentation is used?

review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: This paper studies the topic of learning with noisy labels, in particular, classification problem where the labels are randomly flipped with some probability. The main technical contributions of this paper are two folds: 1) proof of generalization bounds for kernel ridge regression solutions that depends on the clean labels only. 2) two regularization techniques that are shown to be equivalent to the kernel ridge regression when the neural networks approach the neural tangent kernel regime.

Numerical experiments are performed to verify that the proposed methods indeed helps over the baseline at fighting noisy labels. One weak point of the paper is that there is no comparison to any other methods designed to learn under noisy labels. Even though the paper states that the primary advantage of the proposed methods is simplicity, it would still be good to have some empirical comparison for reference.

I like that the paper has a section to explicit check whether the neural networks used in the experiments are in neural tangent kernel regime. However, I'm not very sure how to interpret the scale of the Frobenius norm in the change of the weights. Maybe one alternative approach is to compare the difference between the two neural tagent kernel --- one defined by theta(0), and one defined by theta(t) after training. Alternatively, maybe the experiments can be carried out with recent techniques to perform learning directly on infinite width networks (e.g. https://arxiv.org/abs/1904.11955 ).
review_title: Official Blind Review #2

Meta-review: This paper studies the effect of various regularization techniques for dealing with noisy labels. In particular the authors study various regularization techniques such as distance from initialization to mitigate this effect. The authors also provide theory in the NTK regime. All reviewers have positive assessment about the paper and think is clearly written with nice contributions but do raise some questions about novelty given that it mostly follows the normal NTK regime. I agree that the paper is nicely written and well-motivated. I do not think the theory developed here fully captures all the nuances of practical observations in this problem. In particular, with label noise this theory suggests that test performance is not dramatically affected by label noise when using regularization or early stopping where as in practice what has been observed (and even proven in some cases) is that the performance is completely unaffected with small label noise. I think this paper is a good addition to ICLR and therefore recommend acceptance but recommend the authors to more clearly articulate the above nuances and limitations of their theory in the final manuscript.  
Decision: Accept (Poster)