Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This is a theoretical work studying a widely used heuristic in classification with label corruption. The algorithm of interest is trimmed maximum likelihood estimation, i.e., finding the parameters with maximum likelihood over all subsets of training data that have the same size as the clean set. The algorithm is widely used but existing theoretical guarantees only apply to Gaussian regression model. The paper proved improved and minimax near-optimal results for a broader class of generalized linear models.
strengths_and_weaknesses: ## Strengths
* The result is a clear step beyond existing work towards the theoretical understanding of a heuristic but widely used algorithm. 
* Particularly, the results improved existing constant error bounds to ~O(eps) (the minimax optimal), with a dependence on the corruption level. 
* The writing is clear. Proof sketch is appreciated. 

## Weaknesses

* The proof relies on sub-gaussian data and its “resilience” property, which can be a strong assumption that the original data is from “nice” distribution. 

questions: * Should there be an asumption that eps < 1?
* In algorithm 1, |T| = (1 - 2eps) n is assigned to the new S_hat. Should it be (1-eps)n according to the description elsewhere and in [26]? This is related to my next question
* If |S_hat| = (1 - eps)n, then how could you ensure that T\S_hat has the same number of data points as S_hat \intersect E? 

limitations: This is pure theoretical work. The author pointed out the limitations in applying their SDP-based algorithm to covariate corruptions problems.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies generalized linear models when a fraction of data is corrupted by an adversary. The main focus is on analyzing Trimmed Maximum Likelihood Estimator(TML), a popular estimator for this setting. TML is defined as a solution to a non-convex optimization problem and the standard off-the-shelf guarantees for convex optimization do not apply. The main contribution of the paper is to develop strong finite-time guarantees for the statistical properties of this estimator for various link functions. In particular, the results are significantly tighter than that of Bhatia et al. 2015 and 2017. The paper begins by analyzing the setting where the covariates are clean and only the labels are corrupted. Then the results are extended to the setting where the covariates may also have been corrupted.
strengths_and_weaknesses: 
## Strengths
The main contribution is to show any approximate stationary point of TML, which can be obtained by an alternating minimization algorithm, has desirable statistical properties. This result is technically interesting and practically relevant. Thus, it would be of interest to the NeurIPS community.

## Preliminary Recommendation
I like the paper, and my preliminary recommendation is "Accept".  I look forward to reading the authors' response addressing the points below.

## Weaknesses
However, the paper needs significant improvements on several fronts mentioned below, and I look forward to reading the authors' response addressing these points.

1. Related work: I feel the literature review of the current paper should include the following:

	+ (Covariate Filtering approach of [PJL20]) The paper's approach in Section 5 to handle corruptions in covariates is very similar to [PJL20]. Please include a detailed comparison. In particular, the lines 36 and 241 need to be modified.

	+ Other works in robust statistics (and ML in general) show that approximate stationary points of a non-convex problem have good statistical properties, for example, [CDGS20, CDKGGS21, ZJS20].


2. Technically imprecise statements: I feel the writing is sloppy at times. For example, 
	+ Line 35: trimmed MLE estimator does not achieve the minimax error rate (Error is off by a logarithmic factor).
	+ In the current form, the writing in Line 27 gives the impression that [33] is minmax optimal when the noises are heavy-tailed. I am not sure if that is the case.
	+ Line 130: It is not readily obvious to me that the results adapt to the unknown covariance setting in the label corruption model; I recommend adding explicit details and precise proofs.
	+ Line 96: I believe the results in [PJL20] are tighter for the Gaussian regression.
      
	+ I recommend adding explicit dependence on the norm of R in the error guarantees instead of hiding it in the big-O.

 

3. Writing:
	+ I liked that the paper gives a brief proof sketch of the proof of stationary points being statistically efficient. However, the proof sketch is unclear in several places. For example, "resilience" is not defined in the main body (the paper can use the additional space available on the 9th page). I strongly suggest improving the prose in this proof sketch in the next version because it is the main technical contribution.

     + (Appendix) The Appendix in particular needs to be heavily revised. Some specific comments are below:
         -    The proofs in Appendix are written in a very unorganized manner. It is not obvious from the beginning what statistical conditions are required from the inliers (see also the remark in the Questions section below). It is thus difficult to verify the soundness of the proofs (since there is an adaptive adversary involved, one is prone to to incorrectly claim that certain random variables are independent). I recommend reorganizing and rewriting the proofs in a coherent manner. 
         -  The proofs in Appendix are not described clearly. Majority of the text in the proofs do not give a high-level intuition of the proof strategy. For example, they are along the lines of "Observe that", "it holds that", and so on. See also the formatting on Page 15.

          
   - Furthermore, there are numerous typos in the paper.
     + Line 78: "proposed"
	  + Line 144: "terminates"
	 + Line 191: "mmoment"
	 + Line 201: missing period
	 + Line 206: "intro", Lemma 4.5 
	 + Lemma 4.5, Lemma 4.6: Given "as".
	 + Line 247: "extends"
	 + Definition 3.1:  "exists" -> exist. Where is scalar $\phi$?
	 + Display after Line 162: There should be a parenthesis enclosing the expression before \top.

### Update
I had forgotten to include the detailed bibliography for the references: 

[PJL20] A. Pensia, V. Jog, P. Loh. 2020. Robust regression with covariate filtering: Heavy tails and adversarial contamination

[CDGS20] Y. Cheng, I. Diakonikolas, R. Ge, M. Soltanolkotabi. 2020. High-Dimensional Robust Mean Estimation via Gradient Descent

[CDKGGS21] Y. Cheng, I. Diakonikolas, R. Ge, S. Gupta, D. Kane, M. Soltanolkotabi. 2021. Outlier-Robust Sparse Estimation via Non-Convex Optimization

[ZJS20] B. Zhu, J. Jiao, J. Steinhardt. 2020. Robust estimation via generalized quasi-gradients


questions: + See above.
+ The proofs in Appendix are not very clear. More critically, there are questions regarding soundness. For example, in Line 395, why is the expression upper bounded by O(1)? Should it not depend on R, which can be \infty in this setting?
limitations: The paper should add potential limitations of their results.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the theoretical properties of alternating minimization of trimmed log-likelihood loss for generalized linear models with corruption in the label space and joint space.
strengths_and_weaknesses: Strengths:

The studied setting, as a combination of the adopted estimator, the distributional assumption and the contamination models, is novel with respect to the cited literature in the manuscript. The asserted results and technical proofs seem solid. The paper is well-written and very easy to follow.

Weaknesses:

Although the setting is novel, the claims in this paper may be trivial extensions of existing results. No empirical results are given. There are a noteworthy number of typos and grammatical issues that render it not publication-ready.
questions: The authors have remarked several limitations including sub-Gaussian covariates and a very limited assumption on the covariance for sample corruption model. On top of that, I have a couple of concerns.

1. My major concern is whether the theoretical results are suspicious to be simple corollaries of existing results. First, the authors have appreciated the works [1][2] based on which a majority of their results are developed. The only difference seems to be the adopted loss, which is the negative log-likelihood, and the more general distribution, the generalized linear models. The formulation is reduced to [1] when Gaussian regression is assumed. A similar algorithm is used in [3] but not cited/discussed. I notice that Theorem 1.8 in [4] probably presents a stronger result with milder assumptions than that developed in this paper. Furthermore, Example 4 in [5] and Theorem 1.4 in [6] seem relevant but absent in references. It would be nice if a clear connection can be drawn between this work and [3][4][5][6]. 

2. The theoretical results may not be fundamental enough to exclude empirical results. The work could've taken advantage of the remaining 0.8 pages to demonstrate some experimental results even with a toy simulation dataset.

3. Line 1 in Algorithm 1 filters out data points with large labels in terms of $\ell_1$ norm. Does it still apply to nominal distributions? Some explanations or references will be appreciated.

4. Although the paper is well-written, there are many issues in terms of grammar, tense and punctuation if one takes a closer look at it. I list a few of them found as follows.
- Line 12, should use bold letters $\boldsymbol{\beta}$ for vectors for consistency.
- Line 35, 'achieve' -> 'achieves'.
- Line 52, 'a' -> 'an'.
- Line 53-55, duplicate 'achieve(s)'; tenses do not match for 'improved' and 'matches'.
- Line 70, 'Section B' -> 'Section 5'.
- Definition 3.1, scalar $\phi$ defined but unused.
- Definition 3.3, comma after the statement.
- A lot of equations and paragraphs end without punctuation.
- Line 129, 'though' -> 'through'.
- Line 144, 'maximize' -> 'maximizes'; 'terminate' -> 'terminates'; 'output' -> 'outputs'.
- Line 183, 'upper bound terms of' -> 'upper bound in terms of'.
- Line 201, period at the end.
- Line 241, duplicate 'be/been applied'.
- Line 247, 'extends' -> 'extended'.


References:

[1] Shen, Yanyao, and Sujay Sanghavi. "Learning with bad training data via iterative trimmed loss minimization." In International Conference on Machine Learning, pp. 5739-5748. PMLR, 2019.

[2] Chen, Sitan, Frederic Koehler, Ankur Moitra, and Morris Yau. "Online and distribution-free robustness: Regression and contextual bandits with huber contamination." In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 684-695. IEEE, 2022.

[3] Shen, Yanyao, and Sujay Sanghavi. "Iterative least trimmed squares for mixed linear regression." Advances in Neural Information Processing Systems 32 (2019).

[4] Diakonikolas, Ilias, Daniel M. Kane, Alistair Stewart, and Yuxin Sun. "Outlier-robust learning of ising models under dobrushin’s condition." In Conference on Learning Theory, pp. 1645-1682. PMLR, 2021.

[5] Foster, Dylan J., and Akshay Krishnamurthy. "Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination." Advances in Neural Information Processing Systems 34 (2021): 18907-18919.

[6] Chen, Sitan, Frederic Koehler, Ankur Moitra, and Morris Yau. "Classification under misspecification: Halfspaces, generalized linear models, and evolvability." Advances in Neural Information Processing Systems 33 (2020): 8391-8403.
limitations: The authors have partially addressed the limitations. Potential negative societal impact is not mentioned but unnecessary due to the theoretical nature of the work. The studied problem is interesting and results have rigorous technical proofs. If the authors can put this work  in a more clear position in the literature, I believe the paper can improve significantly.
review_title: null

Meta-review: metareview: This paper analyzes Trimmed Maximum Likelihood Estimation (TML) for generalized linear model when the data is corrupted adversarially.  Under a range of link functions, minimax near-optimal risk is shown achieved, tightening the state-of-the-art results.  In addition to label corruption, extensions were made to covariate corruption with semi-definite programming.  All the reviewers, including myself, find the paper a solid contribution to the methodology and analysis, hence a clear accept.  The rebuttal provides some useful results and insights, which can be included in the final version of the paper.

confidence: Certain
Decision: Accept