Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors claim to develop the first computationally efficient Generalized Method of Moments (GMM) estimator that is robust to a constant fraction of arbitrary outliers. The authors instantiate this estimator for two important special cases of GMM, namely instrumental variable (IV) linear regression and IV logistic regression, under distributional assumptions about the covariates, instruments, and responses. Some numerical results are provided to support the theory. 
strengths_and_weaknesses: Strengths:

1. A computationally efficient and robust GMM estimator should be of interest to the community. 
2. This paper is generally well-written and the theoretical results seem to be reasonable and reliable.

Weaknesses:

1. The algorithmic and theoretical contributions in this work seem to be incremental to me. In particular, the authors mention that "Estimators with the above properties have been developed for various fundamental high-dimensional problems, including mean and covariance estimation [6, 8], linear regression [9, 2], and stochastic optimization [25, 7]"  and that the algorithm proposed in this work is "a simple modification to the SEVER algorithm for robust stochastic optimization [7]". I appreciate the authors' effort to provide the $\textbf{Technical Overview}$. But I hope that the authors can demonstrate more clearly what are the major technical novelty in this submission (especially compared to [7]).

2. Personally, I do not like Assumption 3.1. It involves too many conditions. Even if the authors show in Theorems 6.2 and 6.3 that this assumption is satisfied by robust IV Linear/Logistic Regression, there are still too many involved conditions/parameters that make this assumption not easy to parse. I guess for Algorithms 2, 3, and 4, the situation is even worse. That is, there are too many input parameters for these algorithms, and for some of the parameters (e.g., the noise level $\sigma^2$ and well-conditionedness parameters $\lambda$ and $L$), I am not sure whether it is reasonable to use them as the inputs of the algorithms. In my opinion, practitioners typically prefer simple algorithms. But the algorithms provided in this submission seem to be too complicated (so many parameters!) for practitioners.  

3. The experimental results are not very convincing. In particular, Figures 1a and 1b are for synthetic data. Figure 1c is for real data, which is more desired, but it looks quite messy. For some cases, Huber regression outperforms the method provided in this work. In addition, the authors mention that "note that error is on log-scale, so the Huber regression is extremely noisy". It seems that the method proposed in this work is also quite noisy. 

4. Some references are missing. For example, the authors should add references for the sentence "Unfortunately, like most other classical estimators in statistics, the GMM estimator suffers from a lack of robustness: a single outlier in the observations can arbitrarily corrupt the estimate." and the sentence "However, practitioners in econometrics and applied statistics often employ more sophisticated inference methods such as GMM and IV regression." (Since compared to prior works, IV regression is emphasized in this submission and I am not familiar with IV regression. I am curious about how important IV regression is in practice). In the Experiments section, the authors should provide references to the baseline methods.
questions: Some minor suggestions are listed as follows:
1. The authors should provide the full name of the SEVER algorithm (at least when it first appears on Page 2).
2. The figures in Figure 1 look quite vague. Perhaps the authors can present them as separate figures (i.e., Figures 1, 2, 3 instead of Figures 1a, 1b, 1c).
limitations: Not applicable.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper studies the problem of robust inference when the loss is taken as the norm of generalized moments. The authors provide robust GMM algorithm based on the SEVER algorithm and the iterative filtering framework. The robust GMM algorithm filters both the moments as well as the directional derivatives of the moments. 
strengths_and_weaknesses: The authors provide a new algorithm, robust GMM, based on SEVER and iterative filtering. Theoretical guarantee is provided for the proposed algorithm. The authors also provide concrete applications for robust IV linear regression and logistic regression. I enjoy reading the paper and understanding the techniques. My main concern is about the optimality of the rates, as detailed in the question section.

questions: 1. I'd like the authors to provide more comment on the optimality of the results, in particular for Theorem 5.5, 6.2 and 6.3. It seems to me that in the special case of robust mean estimation with 
$g_i(w) = X_i - w$, Assumption 3.1 holds when X_i has bounded covariance and Theorem 5.5 gives a tight bound except for a worse breakdown point compared to [1] (and the algorithm basically coincides with the iterative filtering for mean estimation). If it is correct, perhaps it's worth mentioning after Theorem 5.5. 

2. However, I'm unsure about the optimality of Theorem 6.2 and 6.3, in particular, for a strongly convex function with bounded variance, the parameter estimation error is usually $O(\epsilon)$, see e.g. [2]. And the rate becomes better with higher moment assumption. However, the rate under bounded 8th moment is still $O(\sqrt{\epsilon})$. Can the authors comment on whether this rate is tight or not? Also, would strongly convexity or any other property helps improve the rate in Theorem 5.5?

[1] Zhu, Banghua, Jiantao Jiao, and Jacob Steinhardt. "Robust estimation via generalized quasi-gradients." Information and Inference: A Journal of the IMA 11.2 (2022): 581-636.

[2] Yin, Dong, et al. "Byzantine-robust distributed learning: Towards optimal statistical rates." International Conference on Machine Learning. PMLR, 2018.

limitations: N/A
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: * In this paper an algorithm and its theoretical guarantees are given for the problem of Generalized Method of Moments, in the setting 
where an $\epsilon$ fraction of data samples could be adversarially corrupted.  
* The guarantees are given under deterministic assumptions on the uncorrupted part of the data and on the moment function g. 
* It is then proved that samples from the instrumental variables linear and logistic regression models satisfy the above assumptions with high probability. 

* The arguments build upon series of recent work on robust estimation of means and local optima. However, the contributions presented here on top of these ideas are considerable. 

* It is stated that the methods presented in this paper are computationally tractable and, moreover, efficient, in contrast to existing work on Robust GMM.
strengths_and_weaknesses: As discussed above, I believe this is a well written paper with a solid contribution. 

The main weakness in my view is that eventual sample complexity $n$ of the instrumental variables algorithms in Section 6 is 
$(d+p)^5$, where $d$ is the dimension of the features and $p$ the dimension of the instrument variable. These clearly are infeasible for all 
but very small d and p. 

The synthetic data experiments are performed with $n$ $d$ and $p$ that do not satisfy these bounds, and results indicate that perhaps the bound may be strengthened. The experiment with NLSYM data is performed with d=2, instead of d=22 in the original data. 


1) Since the bounds in the paper are not computationally feasible, a deeper comparison to existing methods should be performed. 
   Why the present work is better than sources [20],[11], which are referred to as computationally intractable in the paper?
2) What would be the results of the NLSYM experiment if it was performed with full d=22 data?

questions: I will be glad to see the author's comments on points 1 and 2 above. 
limitations: The assumptions made in the paper were appropriately discussed.
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 SEVER algorithm was proposed in 2019 as a robust algorithm that aims to find an approximate critical point of a collection $f_1,\dots,f_n$ of real-valued functions, with the caveat that a fraction $\epsilon n$ of the sample is corrupted. Here, the authors propose a modification of this algorithm to compute generalized methods of moments estimators: these are estimators of the form $\hat \theta = argmin_{\theta\in \Theta} \|n^{-1}\sum_{i=1}^n g(X_i,\theta)\|^2$. Te output of their algorithm is computationally tractable even in high dimension and can be shown to be robust against a constant fraction of outliers.

The performance of this estimator is tested on both a synthetic on non-synthetic dataset.
strengths_and_weaknesses: The paper is well-written and provides a compelling motivation for considering the modified SEVER algorithm: GMM methods can be applied in a wide number of different contexts, so that designing a sound (and computationally tractable) robust method to compute them is a welcome contribution.

From a technical point of view, most results and proofs are modifications of corresponding results in the original SEVER paper. In such, there are no new techniques that are provided.

Although mostly clear, there are several parts throughout sections 4 and 5 where I had trouble following the proofs: there are either small typos with weird numerical constants appearing, or some parts I do not understand (see Questions below). The proofs in Section 6 were not carefully checked.
questions: - It is stated l.177 that the filtering algorithm is standard. Then, it is surprising that Lemmas 4.1 and 4.2 are not already found in the literature.
- Lemma 5.1: I think we also need an assumption of the type $\|w_0-w^*\|\leq R_0$ an $R\leq R_0$. (such assumptions are implicitly used in the proof)
- Theorem 5.4: what is $p$?
- In the proof of Lemma A.1: why do we have $\lambda\leq L$? The constants in the three last lines of l.461 seem off: we have $\|w-w^*\|\leq 3R_0$ and not $2R_0$.
- Proof of Lemma 4.1: once again the constants seem off.
- Proof of Lemma 5.2: once again, it looks like we are using that $\|w_0-w^*\|\leq R_0$ an $R\leq R_0$ in the proof of Lemma 5.2 (paragraph l.532)
- **!!!!!!** I do not understand the proof of Theorem 5.4. More specifically, it is stated that "In this event, $|S_t|\geq 2n/3$ for all $t$", and I do not know why this should hold. This is arguably the main theorem in the paper so more details on this proof are needed. (also, how is $X_1$ defined? an ''initialization'' is missing). 


Typos:
- l.182: had
- l.478 $\sqrt{L\epsilon}$
- l.511: Step 3 is not defined
- l.518: define $u$
- l.528 third line: $\mathbb{E}_{I_{good}}$
limitations: Yes.
review_title: null

Meta-review: metareview: The authors proposed new computationally efficient Generalized Method of Moments (GMM) estimators that are robust to a constant fraction of arbitrary outliers. It is based on modifications of existing algorithms such as SEVER and filtering. Although the analysis is not tight in all the cases, this paper presents an interesting first step towards solving this general family of problems. 

confidence: Less certain
Decision: Accept