Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: In this paper, the authors studied the problem of training neural networks under data poisoning, i.e., when a small fraction of the training data is corrupted by the adversary. They considered two data corruption settings, one allows both the data x and supervision y to be corrupted, which is called general corruption,  and one with only supervision y corrupted. Their first algorithm, which removes the datapoints whose gradient norm is large when computing the average gradient, applies to the general supervision setting. They showed their algorithm has eps\sqrt(d) error or eps*L error, which can be quite large for high-dimensional and deep neural nets learning settings. Their second algorithm applies to the setting where only supervision y is corrupted, and the algorithm works by removing the datapoints whose output layer gradient is large. Assuming the clean data has bounded gradient, and the dimension of y is p, their algorithm achieves error eps*sqrt(p). 

Weakness: 
1.The authors claimed that compared to Diakonikolas 19, they improved the error from eps to sqrt(eps). However, the eps result relies on the fact that the gradient of good data has bounded norm, and I believe in that setting Diakonikolas 19 also achieves eps error. 
2. In paragraphs close to Lemma 1 and Lemma 3, the authors mentioned a randomized filtering algorithm, and proved Lemma 1 Lemma 3 for the algorithm. However, I can’t find the mentioned randomized filtering algorithm in the paper.
3. Theorem 1 and Theorem 4 have no formal proof.
4. Theorem 2 has no proof.
5. In the experiment section, there is no comparison to other state-of-the-art algorithms, for example Diakonikolas 19.

Overall, I think the theoretical result in the paper is incomplete, and the experimental evaluation is insufficient. 
review_title: Review

final_score: rating: 4: Ok but not good enough - rejection
review_content: 
1. The related work section misses MANY related results on corrupted data and robust mean estimation. 
2. The related work section forget to mention existing theoretical results that apply robust mean estimation for robust gradient calculation. 
3. The related work section does not provide an accurate overview of existing results. For example, "the algorithms themselves are NP-hard" is not the correct statement -- NP-hard describes the hardness of a problem, not an algorithm. 
4. Collaborative learning methods seem to have no solid theoretical understanding and it is unclear why the proposed algorithm build on top of it. 
5. Regarding the novelty of the theorems: Theorem 1 studies convergence of biased gradient, which is another known research topic and has been studied before, but the authors have not discuss/compare their results with existing ones and the novelty may be overclaimed. Theorem 3 is for robustness guarantee with corruption only in the supervision, and existing results have shown O(\epsilon) guarantee (for linear regression and its variants). 
6. I have not listed all the missing literature (I believe they are easy to find after a careful literature review), but I can add comment later if needed. 
review_title: Novelty of the results is questionable; combining robust gradient learning with collaborative learning lacks strong motivation. 

final_score: rating: 5: Marginally below acceptance threshold
review_content: pros 
1. The authors provide an insight that in noisy label learning, if the corrupted gradient is not far from the true one, then the learning algorithm could converge a sub-optimal result.
2. Detailed experiments show the empirical evidence of the proposed algorithm over different kinds of label noise.

cons 
1. The authors propose a method that only keeping the data with a small gradient norm in the training process to resist label noise. However, they do not verify that such a design is motivated by their theoretical results. Some important proofs for their key results are missing, e.g., Theorem 2 and Theorem 3, making this paper not self-contain. 
1. Many symbols are not well-defined mathematically. 


This paper proposes a robust algorithm for noisy label learning. By keeping the data with a small gradient norm in the training process, the proposed algorithm could resist the label noise. Instead of making assumptions on the label corruption, the authors assume that the difference between the clean mini-batch gradient and the corrupted mini-batch gradient is bounded. Thus the proposed method could converge to the $\epsilon$-optimal results. By dropping the data with a large gradient norm, the estimated gradient mean will not be far from the true one. The theoretical results make sense, but there lack detailed proofs to make this paper self-contain, e.g., for Theorem 2 and Theorem 3. The empirical studies on several datasets show the robustness of the proposed algorithm over different kinds of label noise.
review_title: A robust noisy label learning algorithm with meaningful insight but lack theoretical proofs

final_score: rating: 3: Clear rejection
review_content: # Summary

The papers studies the problem of robust machine learning, where the labels of the a fraction of samples are arbitrarily corrupted. The paper proposes an algorithm to tackle this problem and evaluates it on a standard datasets.  

# Positives

The paper studies an important problem prevalent in modern machine learning, and proposes two algorithms to solve these problems. The experiments suggest that the proposed algorithm is better than the baselines.

# Negatives 

The paper does not cite highly relevant papers, overclaims its results, and the theoretical results in this paper are immediate. Moreover, the paper is not well-written. More details are given below:
+ Page 1: "Instead of developing an accurate criterion for detection corrupted samples, we adopt a novel perspective and focus on limiting the collective impact of corrupted samples during the learning process through robust mean estimation of gradients."
+ This is not a novel perspective and has been known in robust machine learning community for some time [1,2]. These papers have the same underlying idea, but they are not discussed in this paper. [1] is only briefly mentioned in Remark 2, but the comparison is not fair. The results in [1] hold under fairly general conditions, where the results in this paper require the gradient to be uniformly bounded, which makes the problem significantly simple.
+ Theorem 2 is a trivial result, well-known in field.  Moreover, the way it is presented is misleading and confusing. The error would depend on the quantile of  norms in G, which has been hidden under the O(.) notation. The proof is also missing from the paper. 
+ Assumption 1, i.e., Lipschitz continuity of the loss function is very restrictive, which is not satisfied by popular choices of loss function. This assumption trivializes the problem and restricts its applicability.
+ In the same vein, Theorem 3 assumes unrealistic assumptions. The assumption that $||W||_{op} \leq C$ is very restrictive and does not hold for usual learning tasks.	This assumption in a sense is restricting that the covariates x in $R^d$ have bounded norms, whereas the norm of a typical vector in $R^d$ increases as $\sqrt{d}$.

# Score
I propose to reject this paper. Prior work ([1,2]) has studied this problem in a much greater generality, which are not discussed in this work. The assumptions in the present work are severely restrictive.
## Other major comments:
+ Robust linear regression, with arbitrary corruptions in responses, has been extensively studied in the literature but they have not been cited.  For example, see [3,4]. In particular, the least trimmed squares is an algorithm that removes outliers based on loss values, and comes with a theoretical guarantee via an alternating minimization algorithm [3,4].
+ Theorem 1 is a folklore, and this should be reflected in main text. Currently, this information is only given in Appendix.
+ The paper is not well written: 
 1.Proof of Theorem 2 is missing.
 2. $O(.)$ notation hides the dependence on the important quantity in the papers.
 3. Important notations have not been defined in the paper.
 4. Abbreviations should not be used, for example, Thm., Algo., Asm., etc.
 5. There are numerous typos and grammatical errors. For example, "has a remarkably impact". 

## Relevant papers
1. Diakonikolas, I., G. Kamath, D. M. Kane, J. Li, J. Steinhardt, and A. Stewart. “Sever: A Robust Meta-Algorithm for Stochastic Optimization.” In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 97:1596–1606. Proceedings of Machine Learning Research. PMLR, 2019. http://proceedings.mlr.press/v97/diakonikolas19a.html.
2. Prasad, A., A. S. Suggala, S. Balakrishnan, and P. Ravikumar. “Robust Estimation via Robust Gradient Estimation.” Journal of the Royal Statistical Society: Series B (Statistical Methodology) 82, no. 3 (July 2020): 601–27. https://doi.org/10.1111/rssb.12364.
3. Bhatia, K., P. Jain, P. Kamalaruban, and P. Kar. “Consistent Robust Regression.” In Advances in Neural Information Processing Systems 30, NeurIPS 2017, 2110–2119, 2017. http://papers.nips.cc/paper/6806-consistent-robust-regression.
4. Bhatia, K., P. Jain, and P. Kar. “Robust Regression via Hard Thresholding.” In Advances in Neural Information Processing Systems 28, NeurIPS 2015, 721–729, 2015. http://papers.nips.cc/paper/6010-robust-regression-via-hard-thresholding.

review_title: Simplistic assumptions, misses important prior work

Meta-review: The papers studies machine learning tasks in the presence of adversarially corrupt data (during training). In particular, it is assumed that the labels of a small constant fraction of the datapoints are arbitrarily corrupted.  The paper proposes a natural method to solve this problem and evaluates it on various datasets. As pointed out by the reviewers, the theoretical contributions of this paper are subsumed by a number of prior works (which were not initially cited). The experimental results of the paper are interesting. However, the method proposed  and evaluated is not particularly novel. In my opinion, the problems studied in this submission are important (in particular, the memory/space consideration in the context of robustness). However, this work still needs work and is not ready for publication.
Decision: Reject