Robust Generalized Method of Moments: A Finite Sample Viewpoint
Authors: Dhruv Rohatgi
Vasilis Syrgkanis
Venue: NeurIPS 2022 Accept (2022)
Keywords: robust statistics
generalized method of moments

Abstract: For many inference problems in statistics and econometrics, the unknown parameter is identified by a set of moment conditions. A generic method of solving moment conditions is the Generalized Method of Moments (GMM). However, classical GMM estimation is potentially very sensitive to outliers. Robustified GMM estimators have been developed in the past, but suffer from several drawbacks: computational intractability, poor dimension-dependence, and no quantitative recovery guarantees in the presence of a constant fraction of outliers. In this work, we develop the first computationally efficient GMM estimator (under intuitive assumptions) that can tolerate a constant $\epsilon$ fraction of adversarially corrupted samples, and that has an $\ell_2$ recovery guarantee of $O(\sqrt{\epsilon})$. To achieve this, we draw upon and extend a recent line of work on algorithmic robust statistics for related but simpler problems such as mean estimation, linear regression and stochastic optimization. As a special case, we apply our algorithm to instrumental variables linear regression with heterogeneous treatment effects, and experimentally demonstrate that it can tolerate as much as $10$ -- $15\%$ corruption, significantly improving upon baseline methods.

Robust Generalized Method of Moments: A Finite Sample Viewpoint
Dhruv Rohatgi* MIT
Vasilis Syrgkanis' Stanford University
Abstract
For many inference problems in statistics and econometrics, the unknown param- eter is identified by a of moment conditions. generic method of solving moment conditions is the Generalized Method of Moments (GMM). However, clas- sical GMM estimation is potentially very sensitive outliers. Robustified GMM estimators have been developed in the past, but suffer from several drawbacks: computational intractability, poor pnnension-dependemne covery guarantees in the presence of a constant fraction of outliers. In this work, we develop the first computationally efficient GMM estimator (under intuitive assump- tions) that can tolerate constant fraction of adversarially corrupted samples, and that has an & recovery guarantee of ((ve). To achieve this, we draw upon and extend a recent line of work on algorithmic robust statistics for related but simpler problems such as mean estimation, linear regression and stochastic optimization. As special case, apply algorithm to instrumental variables linear regression with heterogeneous treatment effects, and experimentally demonstrate that can tolerate as much as 10 15% corruption, significantly improving upon baseline methods.
and no quantitative re-
Introduction
Econometric and causal inference methodologies are increasingly being incorporated in automated large scale decision systems. Inevitably these systems need deal with the plethora of practical issues that arise from automation. One important aspect is being able to deal with corrupted or irregular data, either due to poor data collection, the presence of outliers, or adversarial attacks by malicious agents. Even traditional applications of econometric methods, in social science studies, can greatly benefit from robust inference so as not to draw conclusions solely driven by a handful of samples, recently highlighted in [4].
One broad statistical framework, that encompasses the most widely used estimation techniques in econometrics and causal inference, is the framework of estimating models defined via moment conditions. this paper we offer robust estimation algorithm that extends prior recent work in robust statistics to this more general estimation setting.
For family of distributions (Do 0 θ), identifying the parameter 0 is often equivalent solving
Ex-DA [g =)]= =, 0,
for an appropriate problem-specific vector-valued function ... This formalism encompasses such
problems linear regression (with covariates X, response Y, and moment g(XX)(())))))) Y), X(Y
'drohatgi @mit. This work partially done while the first author an intern Microsoft Research New England.
"vayrkköstanford edu. This work was partially done while the second author was Principal Researcher Microsoft Research New England.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

X))) and instrumental variables (IV) linear regression (with covariates X, response Y, instruments Z, and moment ,( 2). Z(Y 0)))).
Under simple identifiability assumptions, moment conditions are statistically tractable, and can be solved by the Generalized Method of Moments (GMM) [T6]. Given independent observations X1,..., Xn Da, the (unweighted) GMM estimator is
i = argmin BEB
Σ g(, 0)
Of course, for general functions g. finding 9 (the global minimizer of potentially non-convex function) may be compurationally intractable. Stronger assumptions imply that all approximate local minima of the above function are the true parameter, in which case the GMM estimator is efficiently approximable. For instrumental variables (IV) linear regression, these assumptions follow from standard non-degeneracy assumptions.
Due to its flexibility, the GMM estimator is widely used in practice (along with heuristic variants, in models where it is computationally intractable) [29]. Unfortunately, like most other classical estimators in statistics, the GMM estimator suffers from a lack robustness: a single outlier in the observations can arbitrarily corrupt the estimate.
Robust statistics Initiated by Tukey and Huber in the 1960s, robust statistics is a broad field studying estimators which have provable guarantees even in the presence of outliers [18]. Outliers can be modelled as samples from heavy-tailed distribution, or even as adversarially and arbitrarily corrupted data. Classically, robustness of an estimator against arbitrary outliers is measured by breakdown point (the fraction of outliers which can be tolerated without causing the estimator to become unbounded [14 and influence (the maximum change in the estimator under an infinitesimal fraction of outliers [15] These metrics have spurred development and study of numerous statistical
estimators which are often used in practice to mitigate the effect of outliers (e.g. Huber loss for mean estimation, linear regression, and other problems (7].. Problems such as robust univariate mean estimation are by now thoroughly understood 24 efficient estimators.
and have statistically and computationally
Unfortunately, in higher dimensions, there has long appeared to be a tradcoff between robustness and computational tractability; as a result, much of the literature on high-dimensional robust statisties has focused on statistical efficiency at the expense of computational feasibility [5] 23 [3] While there a rich literature on IV regression and GMM in the context of robust statisties, those works either present computationally intractable estimators [21 12 or are robust in the sense of bounded influence 227 (20) but not robust against arbitrary outliers. Until the last few years, most high -isheiinnsiinall statistical problems lacked robust estimators satisfying the following basic properties [7]:
Computational tractability (i.e. evading the curse of dimensionality)
2. Robustness constant fraction of arbitrary outliers
3. Quantitative error guarantees without dimension dependence.
Recently, a line of work on algorithmic robust statistics has blossomed within the theoretical computer science community, with the aim of filling this gap in the high- high-dimensional statistics literature. Estimators with the above properties have been developed for various fundamental high- nigh-dimensional
problems, including mean and covariance estimation 7 linear regression [TO 3 and stochastic optimization 26, g However, practitioners in econometrics and applied statistics often employ
more sophisticated inference methods such as GMM and IV regression (29 2) Such methods are
not traditionally under the purview of theoretical computer science and learning theory; perhaps as result, computationally and statistically efffccint robust estimators are still lacking.
Our contribution We address this lack. Methodologically speaking, our main contribution is to introduce GMM to the algorithmic robust statistics literature and vice versa (even aside from robustness, basic algorithmic questions about GMM remain open and surprisingly unstudied). Theo- retically speaking, we prove that simple modification to the SEVER algorithm for robust stochastic optimization [ (based on using bigher-derivative information) yields a computationally efficient and provably robust GMM estimator under intuitive deterministic assumptions about the uncorrupted

---

data. We instantiate this estimator for two important special cases of GMM inn--ummnttltllll variables linear regression and instrumental variables logistic regression- under distributional assumptions about the covariates, instruments, and responses (and in fact our algorithm also applies to the IV generalized linear model under certain conditions on the link function).
Experimentally, we apply our algorithm to robustly solve IV linear regression. We find that it performs well for wide range instrument strengths. the important setting of heterogeneous treatment effects, our algorithm tolerates as much as 10% corruption. Applied to a seminal dataset previously used estimate the effect of education on wages [6,, we provide evidence for the robustness of the inference, and demonstrate that our algorithm can recover the original inference from corruptions of the dataset, significantly better than baseline approaches.
Technical Overview Our robust GMM algorithm builds upon the SEVER algorithm and framework introduced in [ for robust stochastic optimization, which itself builds on seminal work on robust multivariate mean estimation via spectral filtering 7 In this section, we outline the increasing levels of complexity.
First, given samples " for an estimate of the mean of the uncorrupted samples. The spectral filtering approach due to [9] iteratively does the following, until the sample covariance matrix bounded: remove outliers in the direction of the largest variance. So long as the uncorrupted samples have bounded covariance, the filtering ensures that at termination, the empirical mean will approximate the uncorrupted mean.
Cny E Rd among which en corrupted, robust mean estimation asks
Second, given functions fi...., Rd + R among which en are corrupted, robust stochastic optimization asks for approximate critical point of the mean of the uncorrupted functions. The SEVER algorithm [ achieves this by alternating between (a) finding a critical point ú of the current sample set S, and (b) applying one iteration of spectral filtering the vectors {V (10) terminating when no samples are removed from s The termination guarantee of spectral filtering immediately implies that at termination, the average gradient of the uncorrupted samples at á is near the average gradient of the final sample set S at vù, which is 0 by part (a). So á at termination is an approximate critical point of the mean of the uncorrupted functions.
E S),
In our problem, we are given functions 91..... 9 Rd + Rº among which en are corrupted,
and wish to find an approximate minimizer of 1 Eiev (w) where U S [n]] is the set of [
uncorrupted functions. The obvious approach is to alternate between (a) finding a minimizer vi of Eies "xess (u 2 where S is the current sample set, and (b) applying spectral filtering the vectors (0)
S). terminating when samples are removed from S. The termination guarantee of spectral filtering implies that the final sample average [8] Eies (: is near the 1 ΣiEv (i)). Unfortunately, there is no guarantee that 1
[S] Eies 9s (w)) has small norm: part (a) only implies that a local minimizer (and hence critical point) of the norm, so
uncorrupted average TØ
1 S
1 Σ ( 0. [ SES
ÉES
In the above equality, the sample gradient matrix at v could be arbitrarily corrupted, so the sam- ple average t0 could have arbitrarily large norm. In principle, even the global minimizer could have large norm. However, this issue can be fixed by using higher-derivative information: specif- ically, we also apply spectral filtering to (projections of) the matrices V9,( Under appropriate boundedness and smoothness assumptions, it can then be shown that at termination (when neither filtering step removes samples), w is an approximate critical point of the norm of the uncorrupted
1 Eiev (w) | By a "strong identifiability" assumption, this implics that é is near the [oر
average
minimizer of b Eiev (x) as desired.
A related approach simply applies robust mean estimation to estimate the gradients at each step of gradient descent (26).
3

---

2
Preliminaries
For real scalars vectors HEs indexed by S, use the notation [s[[]] for the sam- ple expectation [S] Eiss Et. Similarly, if & are scalars, then we define the sample variance Vars(G)) (5 EsE,)² 2_ If & are vectors then we define the sample covariance matrix (C) = Es(S, - R,s (S+ - EBG,)²² A random vector X is 74 -ypeee-occocottaattivee if B((X, u))* S ((B((X, x)) for all vectors u.
Definition 2.1. For closed set H. function f IR, and ? > 0, 7-approximate critical point of f (in H. is some I E H such that for any vector v with I + du E H. for arbitrarily small ò > 0, it holds that ff 2 - ||=1|2-
Definition 2.2. For a closed set H. 7-approximate critical point oracle Cy, is an algorithm which, given a differentiable function f H. + I returns a "-approximate critical point of f.
Definition 2.3. The (unscaled) logistic functioo G R + defined by G(z) 1/(1+
Outline In Section B we describe the robust GMM problem, and we describe deterministic assump- tions on set of corrupted sample moments, under which we'll be able to efficiently estimate the parameter which makes the uncorrupted moments small. In Section we describe a key subroutine of our robust GMM algorithm, which is commonly known in the literature as filtering. In Section 5 we describe the robust GMM algorithm and prove a recovery guarantee under the assumptions from Section In Section 6 we apply this algorithm to instrumental variable linear and logistic regression, proving that under reasonable stochastic assumptions on the uncorrupted data, arbitrarily e-corrupted moments from these models satisfy the desired deterministic assumptions with high probability. Finally, in Section we evaluate the performance of our algorithm on two corrupted datasets.
Robust GMM Model
In this section, formalize the model in which we will provide robust GMM algorithm. Classically, the goal of GMM estimation is to identify 0 E θ given data XI...., Xn, ~ Do. using the moment condition (XX,,,,o(,X,))) 0)] = O. We consider the added challenge of the c-strong contamination model, in which an adversary allowed to inspect the data X1, X,,..., X,, and replace en samples with arbitrary data, before the algorithm is allowed most reasonable sources of outliers.
the data. This corruption model encompasses
For our main theorem, do not make stochastic assumptions about (Dg 0 θ). Instead, make deterministic assumptions about the empirical moments (0) == (X,, 8) the given data, which are robust to e-strong contamination. Concretely, we make the following assumption.
Assumption 3.1. Given differentiable moments 91, 91.....Hh Rd + R", a corruption parameter e > well-conditionedness parameters and Lipschitzness parameter Lg. and a noise level parameter 2 there is set good [n] with gooo 2 (1 <)n (the "uncorrupted samples"), vector w" Rdd (the "true parameter"), and a radius Ro ||w*|ls ll2 with the following properties:
Strong identifiability. mmin (Ei
and Vg(w=)) 2
Bounded-variance gradient. Es (w Vg( )u) < I for all unit- E RP, Rd
Bounded-variance noise. Eigns (v g(w"))² < 2 for all unit vectors v
Well-specification. ||Ersn..S All I Lv
Lipschitz gradient. ||E Vg(w)= Es Vg(w"))lo S Ly I|w w"1l2 for all w E (2
Stability gradient. Ro 2/(99g).
Intuitively, Assumption 3.1 can be thought of as condition on the uncorrupted samples, because they satisfy the assumption with parameter en, then after e-strong contamination, the corrupted samples will still satisfy the assumption with parameter en Strong identifiability is needed for parameter recovery (even without corruption). Bounded-variance gradient a technical condition which c.g. reduces to a 4th moment bound for IV regression. The third and fourth conditions ensure

---

that the data is approximately well-specified by the moment conditions. The fifth and sixth conditions hold trivially for IV linear regression; for non-linear moment problems. such as our logistic IV regression problem, this condition requires that the f2-norm of the parameters be sufficiently small, such that the logits do not approach the flat region of the logistic function, condition that natural to avoid loss of gradient information and extreme propensities.
4 The FILTER Algorithm
In many robust statistics algorithms, an important subroutine is a filtering algorithm for robust mean estimation. In this section we describe a filtering algorithm used in numerous prior works, including e.g. [ Given a set of vectors {é E S} and a threshold M, the algorithm returns a subset of S, by thresholding outliers in the direction of largest variance. Formally, see Algorithm
Algorithm 1 FILTER
1: procedure FILTER( S),
2: 5 [s].. Cov = Es((E: (5: - E)
3: +- largest eigenvector of Co))(E
4: Ti (u. (5: ) for E S
5: Lies Ti - 24M then
6: return S
7:
else
8:
Sample T f- Unif( (0 max return f 5: T, T)
9:
This algorithm has two important properties. First, if does not filter any samples, then the sample mean is provably stable, i.e. it cannot have been affected much by the corruptions, so long as the uncorrupted samples had bounded variance (proof in Appendix B.T.
Lemma 4.1 (see e.g. 8 19.. Suppose that FILTER does not filter out any samples. Then
[[st EsEll2 S 33 48 (M + ||Cov (e)
for any S [n] and > 0 such that |S 2 (1 - c)n.
Second, if the threshold is chosen appropriately (based on the variance of the uncorrupted samples), then the filtering step always in expectation removes at least as many corrupted samples as uncorrupted samples. Equivalently, the size of the symmetric difference between the current sample set and the uncorrupted samples (i.e. the number of corrupted samples in the current set plus the number of uncorrupted samples which have been filtered out of the current set) always decreases expectation (proof in Appendix 1.I.I.
Lemma 4.2 (see e.g. 8 9). Consider an execution of FILTER with sample set S of size |S] 2 2n/3. and vectors {& S}, and bound M. Let S' be the sample set after this iteration 's filtering. Let 1good C [n] satisfy goood 2 (5/6)n. Suppose that Cov (E:) - MI, then
EJSA A good
EISA good)
where the expectation is over the random threshold, and A denotes symmetric difference.
5 The ITERATED-GAM--SEVE Algorithm
In this section, we describe and analyze an algorithm moment conditions under Assumption 3.1 The key subroutine is the algorithm GMM-SEVER, which given an initial estimate Wy and radius R such that the true parameter is contained in BR(wa), returns a refined estimate w such that (with large probability) the radius bound can be decreased by constant factor. We assume access to an approximate constrained critical point oracle (Definition 2.2), which can be efficiently implemented (for arbitrary smooth bounded functions) by gradient descent.
MAAATTDDGGM-SSS
for robustly solving
5

---

Algorithm 2 GMM-SEVER
1: procedure GMM-SEVER(C, (9i....,9.. wa, R. o)
2: S [n]
3: repeat
4:
Compute 7-approximate critical point + Lyy, ((o + (w)
5:
6:
S' +- FILTER((Vg:(U)) u: S), L2 [|ul12)
7:
if + S then
8:
Set S < S' and return line 4 S" +- FILTER((9:(w)) : E 8), o² 4L RR²
9:
if S" + then
11:
Set < S" and return to line 4
until S" S
13:
return (w, S)
Algorithm 3 AMPLINEDD-GMM-SENEE
1: procedure AMPLIFIED-GMM--SEEEE 191....,9h)) Wo, R, 7, c, I, o,
2:
t 0
3:
repeat
4:
w, S. GMM-SEVER(C, ". (01, wo, 2,,,,,,,
5:
/+1+1
6:
until |S| 2 (1 11c)n or (1/10)* 88
7: return
Like the algorithm SEVER ( algorithm GMM-SEVER alternates (a) finding critical point of function associated to the current samples, and (b) filtering out "outlier" samples. Unlike SEVER, the function optimize is not simply empirical mean over the samples, but rather the squared-norm of the sample moments. Moreover, we need two filtering steps: the moments as well as directional derivatives of the moments, in carefully chosen direction. See Algorithm 2 for the complete description.
We will only prove constant failure probability for GMM-SEVER. However, we will show that can amplified to an arbitrarily small failure probability We call the resulting algorithm A MPP.IFFEDGGMM-SEE of iteratively calling AMPLIFIED-GE GAADDD-GM---LL parameter within successively smaller balls; see Algorithm
see Algorithm 3 The algorithm -MTTE--GM--EEEE then consists
to refine the parameter estimate and bound the true
We start by analyzing GMM-SEVER. In the next two lemmas, show that if the algorithm does filter out too many samples, then we can bound the distance from the output to w". First, we show first-order criticality condition (in the direction samples. If there was no corruption, then we would have an inequality of the form
w") for the norm of the moments of the "good"
w: )T E good V
E E (()) S.
L w 12
With e-corruption, the algorithm is designed so that we can still show the following inequality, matching the above guarantee up to O(ve) (proof in Appendix C.Ib:
Lemma 5.1. Suppose that the input parameters and wy satisfy BR(ws) S. B2Rs (0). Under Assumption 3.1 algorithm termination, if [S] 2 (1 10e)n, then the output i of GMM-SEVER satisfies
w') 16 w
EE 1 (g(w)" (ú)) S Y
2/2 3/2 3/2 6031 RVE
11
Moreover, we can show that any point satisfying the first-order criticality condition must be close to w", using the least singular value bound the gradient (proof in Appendix C.2)
Lemma 5.2. Suppose that the input parameters R and wo satisfy Br(wo) S (0). Under
Assumption 3./. suppose that w E Bu ww) satisfies
(w w²) T E, Vg( ()(w)) T E (w)) S m/w w

---

Algorithm 4 -TTRRATED-GMMMMEVER
1: procedure ITERATED SERRATED-GMM--- GMM- (ENM--SEEE((g)........ In), Ro. R,,,
2: t 1. 01 0, R1 Ro. 8' cB/ 7=
3: repeat
4: Wi AMPLITIED-OOM-SSEERRRII In WA, R,,,,,,,,,,,0000
5:
R4+1 + 2y/2² + +C((E/A)RRV((+o(()))/>
6:
tet+1
7:
until R > R2-1/2
8:
return di:-1
Then ||0 w0 4(K O 2/) VO/X?.
Putting the above lemmas together, immediately get the following bound on || == ==1l2
Lemma 5.3. Suppose that the input parameters R and wo satisfy (R(w)) BRR, (0). Under
Assumption 3.1 satisfies
at algorithm termination, SS| 2 (1 - 10e)n, then the output w of GMM-SEVER
4y X
v - w 10 S
2412 1
remains bound the size of termination. We follow the super-martingale argument from g which uses Lemma 4.2 (proof in Appendix C33
Theorem 5.4. Suppose that the input parameters R and wh satisfy Bn(wo) S B2no (0). Let i be the output of GMM-SEVER. Then with probability at least 9/10, holds that
47 X 22122(L 11020 /APVE.
|| w
The time complexity of GMM-SEVER is (poly(n, d, T-)) where T-, is the time complexity of the y p-apprxximate learner L. Moreover, for any 8 the success probability can be amplified 1 by repeating GMM-SEVER Ollog 1/8) times, or until |S] > (1 10e)n at termination. We call this AMPLIBED-GMM-SBEEE SEVER, and it has time complexity (pooly(n, d, p, TT)) log(1/6)).
With the above guarantee for GMM-SEVER and AMPLIFIDD-GMM-SEEVER we can now analyze TERAAEEDGGMM-SEVE (proof in Appendix C.4)
Theorem 5.5. Suppose that the input ITERATED- GEIEEEDD-MM--EEEEE consists of functions g1...., 9n Rd TR,, corruption parameter e > 0, well-conditionednees parameters À and L,, a Lipschitzness parameter T.g. noise level parameter o², radius bound Ro, and optimization error parameter
y, such that Assumption 3.1 is satisfied for some unknown parameter w" E IRd, and (L? />3)/ss
1/9648. P Suppose that the algorithm is also given failure probability parameter ó > 0.
Then the output w of ITERATED- BAATTED-GM--SEEEER satisfies
| "' S (00((00
with probability least 8. Moreover, the algorithm has time complexity Oppol((n, d. TT)) log(1/8) log( ( where Try is the time complexity of a a-ppproximate learner and 3/3/2 Ve.
Applications
In this section, we apply ITERATED-GMM-SEVER to solve linear and logistic instrumental variables regression in the strong contamination model.
'This constant may be improved; we focus in this paper on dependence the parameters of the problem and do not optimize constants.

---

Robust IV Linear Regression Let Z be the vector of p real-valued instruments, and let X be the vector of real-valued covariates. Suppose that Z and X are mean-zero. Suppose that the response can be described as Y = X "" + for some fixed w" E IRd. The distributional assumptions we will make about X, Y, and Z are described below.
Assumption 6.1. Given corruption parameter e well-conditioneddess parameters and L. hypercontractivity parameter т, noise level parameter o², and norm bound Ro. we assume
the following: (i) Valid instruments: E [ X, (iv) Boundedness: [|Cov([Z; (X]; X] S L, (v)
0, (ii) Bounded-variance noise: B [2] S
o², (iii) Strong instruments: min (EZX)
Hy Hypereontracttvvty; [Z: is (4, 2, T) h-pyercontraactiee (vi) Bounded 8th moments: max; X 1
(+r* and max; 2, S (== (vii) Bounded norm parameter: 1u"1l2 S Ro.
For intuition, conditions (i iii) are standard for IV regression even the absence of corruption; (iv- vi) are conditions on the moments of the distribution, and hold for variety of reasonable distributions including but not limited to any multivariate Gaussian distribution with bounded-spectral norm covariance. Condition (vii) essentially states that we need an initial estimate of w* (but the time complexity of our algorithm will depend only logarithmically on the initial estimate error Ro).
Define the random variable
g(w) = Z(Y XTww
for w E Rd, and let (X₃, Y, 2,) be n independent samples drawn according to (X, 2). Let > O. We prove that under the above assumption, if n is sufficiently large, then with high probability, for any e-contamination (X., Y,, Z of (X,, Y, Z:) the functions g((w) = OY, (X))
satisfy Assumption 3.1 Formally, we prove the following theorem (see Appendix(D]-
X / for sufficiently small constant e > O, and suppose that 2 C(d+p) + log((p + d) /E" for a sufficiently large constant C. Then with probability at least 0.95 over the samples (X,, Y,, 2:) the following holds: for any e-corruption of the samples and any upper bound Ro 2 || Il.. Assumption 3.1 is satisfied. In that event, if L,, X, a, and are known, then there is a poly d.p, log(1/0), log( log(Rn/ (oV))) time algorithm which produces an estimate w satisfying ||:0 - w=ll2 S (T, (2))///)///) with probability least 8.
Theorem 6.2. Let > O. Suppose that e < cmmi(A²/(FT2))
Robust IV Logistic Regression Let Z be a vector of rellevalued instruments, and let X be a vector of d real-valued covariates. Suppose that Z and X are mean-zert zero. Suppose that the response can be described as Y = G(X" "²) + for some fixed w" E Rd, where G is the (unscaled) logistic G(X""")++++ function. The proofs only 1-Lipsehitzeesss of G and G', and that G" (0) is bounded away from O.
As far as distributional assumptions, we assume in this section that Assumption 6.. holds, and additionally assume that the norm bound satisfies Ro S mmmnn(2 L, A/V3L3 for an appropriate constant e, where X, L, and are required for the Assumption. We obtain the following algorithmic result (proof in Appendix E}:
emin((2/(TI.)) (T X² X1/TA) for a sufficiently small constant <> O, and suppose that 2 C(d + p) Tloll (p + /e2 for sufficiently large Then with probability at least 0.95 over the samples (X,, Y,, ",)== the following holds: for any e-corruption of the sam- ples, Assumption 3.7 is satisfied. In that event, if Ro, L, X, o, and are known, then there is algorithm which produces an estimate w satisfying || w" w=1l2 S (I3/1/ (/3/2/2)))))) (x2)) with probability at least - 5.
Theorem 6.3. Let 6 > Suppose that < emin(>
constant C. Suppose that |/w" 1l < Ro I emin( /X//L,///TITI
poly(n, d, log( (1/),, log (e))
7 Experiments
In this section we corroborate our theory by applying our algorithm ITERATED-GMM-SENEE SEVER to several datasets for IV linear regression. See Appendix Gor omitted figures and experimental details (e.g. hyperparameter choices and descriptions of the baselines). Error bars are at 25th and 75th percentiles across independent trials.
Varied Instrument Strength. We construct a synthetic dataset with endogenous noise and 1% coruptionns, and evaluate our estimator the instrument strength is varied. Concretely, for dimension
8

---

Pater 2011
334
606
32%
5:40
120
(b) Synthetic HE dataset with added (c) NLSYM dataset with added cor- corruptions
Varied Instrument Sirength
ruptions
Figure 1
and strength a, we draw independent samples (x,, Y, Z,) where for unobserved noise Y ~ N La), we define instruments ~ (0, Ia) and covariates X; al; + Tii and response (X;, 0*) + (7) L). For & = 0.01n of the samples, we introduce corruption by setting Z; A/(kvdd and yi vd where A = Σ Zzyト. which zeroes out the IV estimate. We take = 10 and vary from 0.1 to 10. For each a, we do 10 independent with classical IV and two-stage Huber
20 and 0" (1, 0, .,,...)). 0);
trials, comparing median &2 error of regression. We also compare the "clean IV" error, i.e. the error IV on the uncorrupted samples. When is small, essentially estimator starts to outperform the baselines, and roughly tracks the clean error (Figure la). Similar results can be seen for d 100 (Figure 2 in Appendix G.5)
inference is possible (the clean error is large), but as increases,
Our next two examples consider IV linear regression with heterogeneous treatment effects, a natural setting in which the instruments and covariates are -igeedimessional, necessitating dimension- independent robust estimators. Consider study in which each sample has a vector X of charac- teristics, a scalar instrument Z, scalar treatment T, and response Y. Assuming that the control response and treatment effect are linear the characteristics, with unknown coefficients 9 and l" respectively, and that the response noise is mean-zero conditioned on Z and X (but may correlate with the treatment), we can write the moment conditions
E[XZ(Y - T(X, 0*) - (X, 8 = EX - T(X, 0*) - This can be interpreted an IV linear regression with covariates (T',X) X) and instruments (2X,X)
=0
Synthetic HE dataset. For parameters d. we generate unknown d-dimensional parameter vector 8t ~ (0, Ia). We then generate independent samples (X,, Y,, Z,) as follows. Draw X, (0, Ia) and Z; Ber(1/2). The binary treatment is drawn T3 ~ Ber(p.) with
P. + expp(-22 U.X.)' where U, 1), and X, 1/2// 1). Finally, the response is Y, (",,0")T + (X,, B*) U; with 3" :
Ordinary least squares would produce biased estimate of (0*,)"). since T is correlated with the response noise U. However, U is by construction independent of X and Z. Thus, in the absence of corruption, IV linear regression with covariates (TX, X), response Y, and instrument (ZX, X) should approximately recover the true parameters (0, (8).
For = 10 and d = 20. the IV estimate still has significant variance, and in this regime, even with no added corruptions, we find that ITERATED- SENTEDGGM-SS GMM-SEVER has lower recovery error than baselines (Table
1 in Appendix G.5). For n 10 and d = 20, the IV estimate is more accurate, Hence, we corrupt the first en samples, by setting X, == 1 and Y, == 3vd. Varying from 0.01 to 0.1, we compute the median & recovery error ITERATED: GMM-
TEMM-EEERR SEVER, classical IV, and two-stage Huber regression, across 50 independent trials (for each e). The results (Figure [b] demonstrate that our algorithm resilient to up to 10% corruptions, whereas both baselines rapidly degrade as e increases.
NLSYMM dataset. In this experiment, we use the data of 6 from the National Longitudinal Survey of Young Men for estimating the average treatment effect (ATE) of education wages. The data

---

consists of 3010 samples with years of education as the treatment, log wages as the response, and proximity to a 4-year college as the instrument, along with 22 covariates (e.g. geographic indicator variables). For simplicity, we restrict the model to only two covariates (years and squared years of labor force experience) and bias term. We find that the ATE estimated by BERRATTD-GMM-SFEE close to the positive ATE ( 0.277) estimated by classical IV, suggesting that Card's inference may be robust (Figure 3 in Appendix G.5). Next, we corrupt a random e- e-fraction of the responses, in way that negates the ATE inferred by classical IV regression (see Appendix G.2 for method).
Varying e from 0.01 to 0.2, we perform 10 independent trials (i.e. resampling the subset of corrupted samples each time). For each trial, we compute the ATE estimate of IV regression, the ATE estimate of two-stage Huber regression, and the median ATE estimate of 50 runs of ITERATED- -AADD-GGM--- SEMM-EEVER. For each e, we then plot the median absolute error of each algorithm across the 10 trials. We find that our algorithm outperforms both baselines, and has lower variance than two-stage Huber regression, up to as 0.15 (Figure Tc note that error is on log-scale, so the Huber regression is extremely noisy).
References
[1] Takeshi Amemiya. Two stage least absolute deviations estimators. Econometrica: Journal of the Econometric Sociery, pages 689-711, 1982.
[2] Joshua D Angrist and Alan B Krueger. Instrumental variables and the search for identification: From supply and demand to natural experiments. Journal of Economic perspectives, 15(4):69- 85, 2001.
[3] Ainesh Bakshi and Adarsh Prasad. Robust linear regression: Optimal rates in polynomial time. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 102-115, 2021.
[4] Tamara Broderick, Ryan Giordano, and Rachael Meager. An automatic finite-sample robustness metrie: Can dropping a little data change conclusions?, 2021.
[5] Christian Brownlees, Emilien Joly, and Gábor Lugosi. Empirical risk minimization for heavy- tailed losses. The Annals of Statistics, 236):25577 2015.
[6] David Card. Using geographic variation in college proximity to estimate the return to schooling, 1993.
[7] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators high-dimension without the computational intractability. SIAM Journal on Computing, 48(2):742 2744228644,4 2019.
[8] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Jacob Steinhardt, and Alistair Stew- art. Sever: A robust meta-algorithm for stochastic optimization. In International Conference on Machine Learning, pages 1596-1606. PMLR, 2019.
[9] Ilass Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference Machine Learning, pages 999-1008, PMLR, 2017.
[10] Ilias Diakonikolas, Weihao Kong, and Alistair Stewart. Efficient algorithms and lower bounds for robust linear regression. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithmss, pages 2745-2754. SIAM, 2019.
[11] Rick Durrett. Probability: theory and examples, volume 49, Cambridge university press, 2019.
[12] Gabriela V Cohen Freue, Heman Ortiz-Molina, and Ruben H Zamar. A natural robustification of the ordinary instrumental variables estimator. Biometrics, 69(3):641-655 2013.
[13] Chao Gao. Robust regression via mutivariate regression depth. Bernoulli, 1692):113911171 2020.
[14] Frank R Hampel. A general qualitative definition of robustness. The Annals of Mathematical Statistics, 12(6))1887-189) 1971.
10

---

[15] Frank R Hampel. The influence curve and its role in robust estimation. Journal of the american statistical association, 69(346):383-393 1974.
[16] Lars Peter Hansen. Large sample properties of generalized method of moments estimators. Econometrica: Journal of the economelric society, pages 1029-1054, 1982.
[17] Peter Huber. Robust estimation of a location parameter. In Breakthroughs in statistics, pages 492-518. Springer, 1992.
[18] Peter Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
[19] Arun Jambulapati, Jerry Li, Tselil Schramm, and Kevin Tian. Robust regression revisited: Acceleration and improved estimation rates. arXiv preprint 100::2200611998.. 2021.
[20] Tae-Hwan Kim and Christophe Muller. Two-stage huber estimation. Journal of statistical planning and inference, 137(2):405 4188 2007.
[21] William S Krasker. Two-stage Journal of Business & Economic Statistics, 4(4):437-444, 1986.
estimators for simultancous models.
[22] Jasper CH Lee and Paul Valiant. Optimal sub-gaussian mean estimation in r. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 672-683. IEEE, 2022.
[23] Gábor Lugosi and Shahar Mendelson. Sub-gaussian estimators of the mean of random vector. The annals of statistics, 47(2):8337744, 2019.
[24] Roberto I Oliveira and Paulo Orenstein. The sub-gaussian property of trimmed means estimators. Technical report, Technical report, IMPA, 2019.
[25] Pedregosa, G. Varoquaux, A. Gramfort, Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and Duchesnay. Scikit-learn: Machine learning Python, Journal of Machine Learning Research, 12:2825-2838 2011.
[26] Adarsh Prasad, Arun Sai Suggala, Sivaraman Balakrishnan, and Pradeep Ravikumar. Robust estimation via robust gradient estimation. arXiv preprint arXiv:1802.064885 2018
[27] Elvezio Ronchetti and Fabio Trojani. Robust inference with gmm estimators. Journal of econometrics, 101(1):37-69, 2001.
[28] Joel A Tropp. An introduction to matrix concentration inequalities. arXiv preprint arXiv:1501.01571, 2015.
[29] Jeffrey M Wooldridge.
Applications of generalized method moments estimation. Journal of Economic perspectives, 15(4):87-100, 2001.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes] See Theorems 5.3
6.2 6.3 and Section
(b) Did you describe the limitations of your work? [Yes] See Assumptions 3. and 6.1
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump-
tions B.1 and 6.1
(b) Did you include complete proofs of theoretical results? [Yes] See supplemental material

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] See supplemen- tal material
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and Appendix Giji supplemental material
(c) Did you report error bars (e.g.. with respect to the random seed after running ex- periments multiple times)? [Yes] See Section and Appendix G in supplemental material
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] National Longitudinal Survey of Young Men
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] Code included in supplemental material
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "xqMO1Qxzy8j", "reviewer": "Reviewer_JzqV", "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. ", "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 \n$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. \n\n2. 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?\n\n[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.\n\n[2] Yin, Dong, et al. \"Byzantine-robust distributed learning: Towards optimal statistical rates.\" International Conference on Machine Learning. PMLR, 2018.\n", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fmVaT-eBCIu", "reviewer": "Reviewer_rQ7k", "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. ", "questions": "Some minor suggestions are listed as follows:\n1. The authors should provide the full name of the SEVER algorithm (at least when it first appears on Page 2).\n2. 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.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. A computationally efficient and robust GMM estimator should be of interest to the community. \n2. This paper is generally well-written and the theoretical results seem to be reasonable and reliable.\n\nWeaknesses:\n\n1. 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]).\n\n2. 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.  \n\n3. 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. \n\n4. 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "esW_XRBp0CY", "reviewer": "Reviewer_g7Q3", "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.\n\nThe performance of this estimator is tested on both a synthetic on non-synthetic dataset.", "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.\n- 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)\n- Theorem 5.4: what is $p$?\n- 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$.\n- Proof of Lemma 4.1: once again the constants seem off.\n- 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)\n- **!!!!!!** 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). \n\n\nTypos:\n- l.182: had\n- l.478 $\\sqrt{L\\epsilon}$\n- l.511: Step 3 is not defined\n- l.518: define $u$\n- l.528 third line: $\\mathbb{E}_{I_{good}}$", "limitations": "Yes.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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.\n\nFrom 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.\n\nAlthough 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "_Mi_cggFUAz", "reviewer": "Reviewer_xqsD", "summary": "* In this paper an algorithm and its theoretical guarantees are given for the problem of Generalized Method of Moments, in the setting \nwhere an $\\epsilon$ fraction of data samples could be adversarially corrupted.  \n* The guarantees are given under deterministic assumptions on the uncorrupted part of the data and on the moment function g. \n* It is then proved that samples from the instrumental variables linear and logistic regression models satisfy the above assumptions with high probability. \n\n* 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. \n\n* It is stated that the methods presented in this paper are computationally tractable and, moreover, efficient, in contrast to existing work on Robust GMM.", "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. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "As discussed above, I believe this is a well written paper with a solid contribution. \n\nThe main weakness in my view is that eventual sample complexity $n$ of the instrumental variables algorithms in Section 6 is \n$(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 \nbut very small d and p. \n\nThe 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. \n\n\n1) Since the bounds in the paper are not computationally feasible, a deeper comparison to existing methods should be performed. \n   Why the present work is better than sources [20],[11], which are referred to as computationally intractable in the paper?\n2) What would be the results of the NLSYM experiment if it was performed with full d=22 data?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept