Robust Generalized Method of Moments: A Finite Sample Viewpoint

Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.

42,117 characters · 7 sections · 20 citation commands

Rendered from LaTeX for readability, not typeset faithfully. Citation keys are highlighted; maths is left as source; figures, tables and equation environments are summarised rather than reproduced; unrecognised commands are greyed out so nothing is silently dropped. Email addresses are removed.

abstractFor 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 two examples of the generality of our algorithm, we show how our estimation algorithm and assumptions apply to instrumental variables linear and logistic regression. Moreover, we experimentally validate that our estimator outperforms classical IV regression and two-stage Huber regression on synthetic and semi-synthetic datasets with corruption.

Introduction

Econometric and causal inference methodologies are increasingly being incorporated in automated large scale decision systems. Inevitably these systems need to 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 more classical 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, as was recently highlighted in broderick2021automatic.

Recent work in statistical machine learning has enabled robust estimation for regression problems and more generally estimation problems that reduce to the minimization of a stochastic loss. However, many estimation methods in causal inference and econometrics do not fall under this umbrella. A more general 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. In this paper we offer a robust estimation algorithm that extends prior recent work in robust statistics to this more general estimation setting.

For a family of distributions $\{\mathcal{D}_\theta: \theta \in \Theta\}$, identifying the parameter $\theta$ is often equivalent to solving

equation[equation omitted — 102 chars of source]

for an appropriate problem-specific vector-valued function $g$. This formalism encompasses such problems as linear regression (with covariates $X$, response $Y$, and moment $g((X, Y), \theta) = X(Y - X^T\theta)$) and instrumental variables linear regression (with covariates $X$, response $Y$, instruments $Z$, and moment $g((X,Y,Z), \theta) = Z(Y - X^T\theta)$).

Under simple identifiability assumptions, moment conditions are statistically tractable, and can be solved by the Generalized Method of Moments (GMM) hansen1982large. Given independent observations $X_1,\dots,X_n \sim \mathcal{D}_\theta$, the GMM estimator is \[\hat{\theta} = \operatorname*{argmin}_{\theta \in \Theta} \left(\frac{1}{n} \sum_{i=1}^n g(X_i, \theta)\right)^T W \left(\frac{1}{n} \sum_{i=1}^n g(X_i, \theta)\right)\] for a positive-definite weight matrix $W$. Of course, for general functions $g$, finding $\hat{\theta}$ (the global minimizer of a potentially non-convex function) may be computationally intractable. Under stronger assumptions, all approximate local minima of the above function are near 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 (or heuristic variants, in models where it is computationally intractable). 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.

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {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 huber2004robust. Outliers can be modelled as samples from a 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 hampel1971general) and influence (the maximum change in the estimator under an infinitesimal fraction of outliers hampel1974influence). 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 huber1992robust).

Unfortunately, classical robust statistics suffers from a number of limitations due to emphasis on statistical efficiency and low-dimensional statistical problems. In particular, until the last few years, most high-dimensional statistical problems lacked robust estimators satisfying the following basic properties (see e.g. diakonikolas2019robust for discussion in the setting of learning Gaussians and mixtures of Gaussians):

enumerate• Computational tractability (i.e. evading the curse of dimensionality) • Robustness to a constant fraction of arbitrary outliers • Quantitative error guarantees without dimension dependence.

In a revival of robust statistics within the field of theoretical computer science, estimators with the above properties have been developed for various fundamental problems in high-dimensional statistics, including mean and covariance estimation diakonikolas2019robust, diakonikolas2017being, linear regression diakonikolas2019efficient, bakshi2021robust, and stochastic optimization diakonikolas2019sever. However, practitioners in econometrics and applied statistics often employ more sophisticated inference methods such as GMM and IV regression, for which computationally and statistically efficient robust estimators are still lacking.

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {Our contribution} In this work, we address the aforementioned lack. Extending the Sever algorithm for robust stochastic optimization diakonikolas2019sever, we develop a computationally efficient and provably robust GMM estimator under intuitive deterministic assumptions about the uncorrupted data. We instantiate this estimator for two special cases of GMM---instrumental 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).

We corroborate the theory with experiments solving IV linear regression on corrupted synthetic and semi-synthetic data, which demonstrate that our algorithm outperforms non-robust IV as well as Huberized IV.

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {Techniques and Relation to [DKKLSS19]} Our robust GMM algorithm builds upon the Sever algorithm and framework introduced in diakonikolas2019sever for stochastic optimization. In this section, we briefly outline the relation. The Sever algorithm robustly finds an approximate critical point for the empirical mean of input functions $f_1,\dots,f_n: \mathbb{R}^d \to \mathbb{R}$, i.e. for convex functions, approximately and robustly solves \[\frac{1}{n} \sum_{i=1}^n \nabla f_i(w^*) = 0.\] The approach is to alternate between (a) finding an approximate critical point $\hat{w}$ of the current sample set, and (b) filtering the sample set by $\nabla f_i(\hat{w})$, until convergence (i.e. when no samples are filtered out). Filtering ensures that at convergence, the mean of $\nabla f_i(\hat{w})$ over the current sample set (which is small by criticality) is near the mean over the uncorrupted samples, so $\hat{w}$ is an approximate critical point for the uncorrupted samples, as desired.

Any moment condition which is the gradient of some function can be interpreted as a critical-point finding problem, and solved in the above way. An example is linear regression, where the moment $g(w) = X(Y - X^T W)$ is the gradient of the squared-loss $f(w) = \left \lVert Y - X^T w \right \rVert_2^2$. However, $g(w) = Z(Y - X^T w)$ is not a gradient, so IV linear regression cannot directly be solved by Sever. In general, we need a way to robustly find an approximate solution to \[\frac{1}{n}\sum_{i=1}^n g(w^*) = 0.\] Our approach is to alternate approximately minimizing \[\left \lVert \frac{1}{|S|} \sum_{i \in S} g(w) \right \rVert_2^2,\] where $S$ is the current sample set, with a filtering step. However, it is not sufficient to filter by $g(\hat{w})$, because the minimization step does not necessarily output $\hat{w}$ for which $\frac{1}{|S|} \sum_{i \in S} g(w)$ is small (unlike for Sever, where $g = \nabla f$, and so an approximate zero of $\frac{1}{|S|} \sum_{i \in S} \nabla f_i(w)$ can always be found, for an arbitrary set of functions $\{f_i\}_{i \in S}$).

To fix this, we introduce a second filtering step based on $\nabla g$. Under an identifiability condition for the uncorrupted samples (which is needed even in the absence of corruption), we show that the above situation, where $\frac{1}{|S|} \sum_{i \in S} g(w)$ is large, can be detected by the gradient filtering step, so that at convergence the empirical moment is in fact small.

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {Further related work} The generalized method of moments and instrumental variables regression have indeed been studied in the context of robust statistics amemiya1982two, freue2013natural, krasker1986two, ronchetti2001robust. However, the resulting estimators face the same nearly ubiquitous issues described above. For instance, amemiya1982two presents a variant of two-stage least squares which uses least absolute deviations. The resulting estimator performs well under the metric of bounded influence, but an arbitrary outlier can still cause arbitrary changes in the estimator. The estimator proposed by freue2013natural modifies the closed-form solution to IV linear regression using robust mean and covariance estimators. These have attractive theoretical properties but are computationally intractable, and the heuristics by which they are implemented in practice have no associated theoretical guarantees. The robust GMM estimator presented in ronchetti2001robust has bounded influence but is not robust to a constant fraction of outliers.

Preliminaries

For random variables $\{\xi_i\}_{i \in S}$ indexed by a set $S$, we use the notation $\mathbb{E}_S[\xi_i]$ for the sample expectation $\frac{1}{|S|} \sum_{i \in S} \xi_i$. Similarly, if $\xi_i$ are scalars, then we define the sample variance $\operatorname{Var}_S(\xi_i) = \mathbb{E}_S(\xi_i - \mathbb{E}_S \xi_i)^2$. If $\xi_i$ are vectors then we define the sample covariance matrix $\operatorname{Cov}_S(\xi_i) = \mathbb{E}_S (\xi_i - \mathbb{E}_S \xi_i)(\xi_i - \mathbb{E}_S \xi_i)^T$. A random vector $X$ is $(4,2,\tau)$-hypercontractive if $\mathbb{E}(\langle X,u\rangle)^4 \leq \tau (\mathbb{E}(\langle X,u\rangle)^2)^2$ for all vectors $u$.

definitionFor a closed set $\mathcal{H}$, a function $f: \mathcal{H} \to \mathbb{R}$, and $\gamma > 0$, a $\gamma$-approximate critical point of $f$ (in $\mathcal{H}$) is some $x \in \mathcal{H}$ such that for any vector $v$ with $x+\delta v \in \mathcal{H}$ for arbitrarily small $\delta>0$, it holds that $v \cdot \nabla f(x) \geq -\gamma \left \lVert v \right \rVert_2$.

definitionFor a closed set $\mathcal{H}$, a $\gamma$-approximate learner $\mathcal{L}_\mathcal{H}$ is an algorithm which, given a differentiable function $f: \mathcal{H} \to \mathbb{R}$ returns a $\gamma$-approximate critical point of $f$.

definitionThe (unscaled) logistic function $G: \mathbb{R} \to \mathbb{R}$ is defined by $G(x) = 1/(1 + e^{-x})$.

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {Outline} In Section (ref), we describe the robust GMM problem, and we describe deterministic assumptions on a set of corrupted sample moments, under which we'll be able to efficiently estimate the parameter which makes the uncorrupted moments small. In Section (ref), we describe a key subroutine of our robust GMM algorithm, which is commonly known in the literature as filtering. In Section (ref), we describe the robust GMM algorithm and prove a recovery guarantee under the assumptions from Section (ref). In Section (ref), we apply this algorithm to instrumental variable linear and logistic regression, proving that under reasonable stochastic assumptions on the uncorrupted data, arbitrarily $\epsilon$-corrupted moments from these models satisfy the desired deterministic assumptions with high probability. Finally, in Section (ref), we evaluate the performance of our algorithm on two corrupted datasets.

Robust GMM Model

In this section, we formalize the model in which we will provide a robust GMM algorithm. Classically, the goal of GMM estimation is to identify $\theta \in \Theta$ given data $X_1,\dots,X_n \sim \mathcal{D}_\theta$, using the moment condition $\mathbb{E}_{X \sim \mathcal{D}_\theta}[g(X,\theta)] = 0$. We consider the added challenge of the $\epsilon$-strong contamination model, in which an adversary is allowed to inspect the data $X_1,\dots,X_n$ and replace $\epsilon n$ samples with arbitrary data, before the algorithm is allowed to see the data. This corruption model encompasses most reasonable sources of outliers.

For our main theorem, we do not make stochastic assumptions about $\{\mathcal{D}_\theta: \theta \in \Theta\}$. Instead, we make deterministic assumptions (strong identifiability, boundedness, and so forth) about the moments of the corrupted data $\{g_i(\theta) := g(X_i, \theta)\}_{i=1}^n$ (for IV linear and logistic regression, we will prove that the assumptions hold with high probability under reasonable distributional assumptions).

Concretely, since only $\epsilon n$ samples were corrupted, there is a set of $(1-\epsilon)n$ uncorrupted samples. This set is unknown, but all we need is that it exists. More specifically, we assume that there exists a large subset of the data, of size at least $(1-\epsilon)n$, which satisfies finite-sample analogues of various distributional identifiability and boundedness conditions.

assumptionGiven differentiable moments $g_1,\dots,g_n: \mathbb{R}^d \to \mathbb{R}$, a corruption parameter $\epsilon>0$, well-conditionedness parameters $\lambda$ and $L$, a Lipschitzness parameter $L_g$, and a noise level parameter $\sigma^2$, there is a set $I_\text{good} \subseteq [n]$ with $|I_\text{good}| \geq (1-\epsilon)n$ (the “uncorrupted samples”), a vector $w^* \in \mathbb{R}^d$ (the “true parameter”), and a radius $R_0 \geq \left \lVert w^* \right \rVert_2$ with the following properties: \begin{itemize}[leftmargin=1em] • Strong identifiability. $\sigma_\text{min}(\mathbb{E}_{I_\text{good}} \nabla g(w^*)) \geq \lambda$ • Bounded-variance gradient. $\mathbb{E}_{I_\text{good}} (u^T\nabla g(w^*)v)^2 \leq L^2$ for all unit-vectors $u \in \mathbb{R}^p$, $v \in \mathbb{R}^d$ • Bounded-variance noise. $\mathbb{E}_{I_\text{good}} (v\cdot g(w^*))^2 \leq \sigma^2 L$ for all unit vectors $v$ • Well-specification. $\left \lVert \mathbb{E}_{I_\text{good}} g(w^*) \right \rVert_2 \leq \sigma\sqrt{L\epsilon}$ • Lipschitz gradient. $\left \lVert \mathbb{E}_{I_\text{good}}\nabla g(w) - \mathbb{E}_{I_\text{good}}\nabla g(w^*) \right \rVert_\text{op} \leq L_g\left \lVert w-w^* \right \rVert_2$ for all $w \in B_{2R_0}(0)$ • Stability of gradient. $R_0 < \lambda/(8L_g)$. \end{itemize}

The stability of the gradient condition essentially states that the radius of the ball containing $w^*$ is sufficiently small that $\mathbb{E} \nabla g(w)$ cannot change much in this ball. Note that if the gradient is constant in $w$, as for IV linear regression, then the Lipschitz gradient assumption is satisfied with $L_g = 0$, and the stability assumption is vacuous. For non-linear moment problems, such as our logistic IV regression problem, this condition requires that the $\ell_2$-norm of the parameters be sufficiently small, such that the logits do not approach the flat region of the logistic function, a condition that is natural to avoid loss of gradient information and extreme propensities.

We state several consequences of Assumption (ref) which will be used later (proof in Appendix (ref)).

lemmaUnder Assumption (ref), the following bounds hold for all $w \in B_{2R_0}(0)$: \begin{itemize} \setlength\itemsep{-.2em} • $\mathbb{E}_{I_\text{good}}(u^T \nabla g(w)v)^2 \leq 2L^2$ for all unit vectors $u \in \mathbb{R}^p$ and $v \in \mathbb{R}^d$ • $\operatorname{Cov}_{I_\text{good}}(g(w)) \preceq 2\sigma^2 L + 4L^2 \left \lVert w-w^* \right \rVert_2^2I$ • $\sigma_\text{min}(\mathbb{E}_{I_\text{good}} \nabla g(w)) \geq \lambda/2$ • $\left \lVert \mathbb{E}_{I_\text{good}} g(w) \right \rVert_2 \leq \sigma\sqrt{L\epsilon} + 2L\left \lVert w-w^* \right \rVert_2$ • $\left \lVert \mathbb{E}_{I_\text{good}} \nabla g(w) \right \rVert_\text{op} \leq L\sqrt{2}$ \end{itemize}

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. diakonikolas2019sever. Given a set of vectors $\{\xi_i: i \in S\}$ and a threshold $M$, the algorithm returns a subset, by thresholding outliers in the direction of largest variance. Formally, see Algorithm (ref).

algorithm[algorithm omitted — 790 chars of source]

This algorithm has two important properties. First, if it 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 (ref)).

lemmaSuppose that Filter does not filter out any samples. Then \[\left \lVert \mathbb{E}_S \xi - \mathbb{E}_I \xi \right \rVert_2 \leq 3\sqrt{48}\sqrt{(M+\left \lVert \operatorname{Cov}_I(\xi) \right \rVert_\text{op})\epsilon}\] for any $I \subseteq [n]$ and $\epsilon>0$ such that $|S|,|I| \geq (1-\epsilon)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 in expectation (proof in Appendix (ref)).

lemmaConsider an execution of Filter with sample set $S$ of size $|S| \geq 2n/3$, and vectors $\{\xi_i: i \in S\}$, and bound $M$. Let $S'$ be the sample set after this iteration's filtering. Let $I_\text{good} \subseteq [n]$ satisfy $|I_\text{good}| \geq (5/6)n$. Suppose that $\operatorname{Cov}_{I_\text{good}}(\xi_i) \preceq MI$, then \[\mathbb{E}|S' \triangle I_\text{good}| \leq \mathbb{E}|S \triangle I_\text{good}|,\] where the expectation is over the random threshold.

The Iterated-Gmm-Sever Algorithm

In this section, we describe and analyze an algorithm Iterated-Gmm-Sever for robustly solving moment conditions under Assumption (ref). The key subroutine is the algorithm Gmm-Sever, which given an initial estimate $w_0$ and a radius $R$ such that the true parameter is contained in $B_R(w_0)$, returns a refined estimate $w$ such that (with large probability) the radius bound can be decreased by a constant factor.

Like the algorithm Sever diakonikolas2019sever, our algorithm Gmm-Sever alternates (a) finding a critical point of a function associated to the current samples, and (b) filtering out “outlier” samples. Unlike Sever, the function we optimize is not simply an 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 a carefully chosen direction. See Algorithm (ref) for the complete description.

algorithm[algorithm omitted — 1,096 chars of source]

We will only prove a constant failure probability for Gmm-Sever. However, we will show that it can be amplified to an arbitrarily small failure probability $\delta$. We call the resulting algorithm Amplified-Gmm-Sever; see Algorithm (ref). The algorithm Iterated-Gmm-Sever then consists of iteratively calling Amplified-Gmm-Sever to refine the parameter estimate and bound the true parameter within successively smaller balls; see Algorithm (ref).

algorithm[algorithm omitted — 599 chars of source]

algorithm[algorithm omitted — 877 chars of source]

We start by analyzing Gmm-Sever. In the next two lemmas, we show that if the algorithm does not filter out too many samples, then we can bound the distance from the output to $w^*$. First, we show a first-order criticality condition (in the direction $\hat{w} - w^*$) for the norm of the moments of the “good" samples. If there was no corruption, then we would have an inequality of the form \[\frac{(\hat{w} - w^*)^T}{\left \lVert \hat{w} - w^* \right \rVert_2} \mathbb{E}_{I_\text{good}} \nabla g(\hat{w})^T \mathbb{E}_{I_\text{good}} g(\hat{w}) \leq \gamma.\] With $\epsilon$-corruption, the algorithm is designed so that we can still show the following inequality, matching the above guarantee up to $O(\sqrt{\epsilon})$ (proof in Appendix (ref)):

lemmaUnder Assumption (ref), at algorithm termination, if $|S| \geq (1-10\epsilon)n$, then the output $\hat{w}$ of $\textsc{Gmm-Sever}$ satisfies \[\frac{(\hat{w}-w^*)^T}{\left \lVert \hat{w}-w^* \right \rVert_2} \mathbb{E}_{I_\text{good}} \nabla g(\hat{w})^T \mathbb{E}_{I_\text{good}} g(\hat{w}) \leq \gamma + 275\sigma L^{3/2}\sqrt{\epsilon} + 603L^2 R\sqrt{\epsilon}\]

Moreover, we can show that any point satisfying the first-order criticality condition must be close to $w^*$, using the least singular value bound on the gradient (proof in Appendix (ref)).

lemmaUnder Assumption (ref), suppose that $w \in B_R(w_0)$ satisfies \[(w-w^*)^T \mathbb{E}_{I_\text{good}} \nabla g(w)^T \mathbb{E}_{I_\text{good}} g(w) \leq \kappa \left \lVert w-w^* \right \rVert_2.\] Then $\left \lVert w-w^* \right \rVert_2 \leq 4(\kappa + \sigma L^{3/2}\sqrt{\epsilon})/\lambda^2$.

Putting the above lemmas together, we immediately get the following bound on $\left \lVert \hat{w} - w^* \right \rVert_2$.

lemmaUnder Assumption (ref), at algorithm termination, if $|S| \geq (1-10\epsilon)n$, then the output $\hat{w}$ of Gmm-Sever satisfies \[\left \lVert \hat{w} - w^* \right \rVert_2 \leq \frac{4\gamma}{\lambda^2} + 2412(L^2/\lambda^2)R\sqrt{\epsilon} + 1102\sigma (L^{3/2}/\lambda^2)\sqrt{\epsilon}.\]

It remains to bound the size of $S$ at termination. We follow the super-martingale argument from diakonikolas2019sever, which uses Lemma (ref) (proof in Appendix (ref)).

theoremSuppose that the initial conditions $R$ and $w_0$ satisfy $B_R(w_0) \subseteq B_{2R_0}(0)$. Let $\hat{w}$ be the output of Gmm-Sever. Then with probability at least $9/10$, it holds that \[\left \lVert \hat{w} - w^* \right \rVert_2 \leq \frac{4\gamma}{\lambda^2} + 2412(L^2/\lambda^2)R\sqrt{\epsilon} + 1102\sigma (L^{3/2}/\lambda^2)\sqrt{\epsilon}.\] The time complexity of Gmm-Sever is $O(\operatorname{poly}(n,d,p, T_\gamma))$ where $T_\gamma$ is the time complexity of the $\gamma$-approximate learner $\mathcal{L}$. Moreover, for any $\delta>0$ the success probability can be amplified to $1-\delta$ by repeating Gmm-Sever $O(\log 1/\delta)$ times, or until $|S| \geq (1-10\epsilon)n$ at termination. We call this Amplified-Gmm-Sever, and it has time complexity $O(\operatorname{poly}(n,d,p, T_\gamma) \cdot \log(1/\delta))$.

With the above guarantee for Gmm-Sever and Amplified-Gmm-Sever, we can now analyze Iterated-Gmm-Sever (proof in Appendix (ref)).

theoremSuppose that the input to Iterated-Gmm-Sever consists of functions $g_1,\dots,g_n: \mathbb{R}^d \to \mathbb{R}$, a corruption parameter $\epsilon>0$, well-conditionedness parameters $\lambda$ and $L$, a Lipschitzness parameter $L_g$, a noise level parameter $\sigma^2$, a radius bound $R_0$, and an optimization error parameter $\gamma$, such that Assumption (ref) is satisfied for some unknown parameter $w^* \in \mathbb{R}^d$, and $(L^2/\lambda^2)\sqrt{\epsilon} \leq 1/9648$. \footnote{This constant may be improved; we focus in this paper on dependence on the parameters of the problem and do not optimize constants.} Suppose that the algorithm is also given a failure probability parameter $\delta>0$. Then the output $\hat{w}$ of Iterated-Gmm-Sever satisfies \[\left \lVert \hat{w} - w^* \right \rVert_2 \leq O(\sigma(L^{3/2}/\lambda^2)\sqrt{\epsilon})\] with probability at least $1-\delta$. Moreover, the algorithm has time complexity $O(\operatorname{poly}(n,d,p, T_\gamma) \cdot \log(1/\delta) \cdot \log(R\sqrt{L}/(\sigma\sqrt{\epsilon})))$, where $T_\gamma$ is the time complexity of a $\gamma$-approximate learner and $\gamma = \sigma L^{3/2}\sqrt{\epsilon}$.

Applications

In this section, we apply Iterated-Gmm-Sever to solve linear and logistic instrumental variables regression in the strong contamination model.

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {Robust IV Linear Regression} Let $Z$ be the vector of $p$ real-valued instruments, and let $X$ be the vector of $d$ real-valued covariates. Suppose that $Z$ and $X$ are mean-zero. Suppose that the response can be described as $Y = X^T w^* + \xi$ for some fixed $w^* \in \mathbb{R}^d$. The distributional assumptions we will make about $X$, $Y$, and $Z$ are described below.

assumptionGiven a corruption parameter $\epsilon > 0$, well-conditionedness parameters $\lambda$ and $L$, hypercontractivity parameter $\tau$, noise level parameter $\sigma^2$, and norm bound $R_0$, we assume the following: (i) Valid instruments: $\mathbb{E}[\xi|Z] = 0$, (ii) Bounded-variance noise: $\mathbb{E}[\xi^2|Z] \leq \sigma^2$, (iii) Strong instruments: $\sigma_\text{min}(\mathbb{E} ZX^T) \geq \lambda$, (iv) Boundedness: $\left \lVert \operatorname{Cov}([Z; X] \right \rVert_\text{op} \leq L$, (v) Hypercontractivity: $[Z; X]$ is $(4,2,\tau)$-hypercontractive, (vi) Bounded 8th moments: $\max_i X_i^8 \leq O(\tau^2 L^4)$ and $\max_i Z_i^8 \leq O(\tau^2 L^4)$ (vii) \textbf{Bounded norm parameter:} $\left \lVert w^* \right \rVert_2 \leq R_0$.

Define \[g(w)= Z(Y - X^T w)\] for $w \in \mathbb{R}^d$, and let $(X_i,Y_i,Z_i)$ be $n$ independent samples drawn according to $(X,Y,Z)$. Let $\epsilon > 0$. We prove that under the above assumption, if $n$ is sufficiently large, then with high probability, for any $\epsilon$-contamination $(X'_i, Y'_i, Z'_i)_{i=1}^n$ of $(X_i,Y_i, Z_i)_{i=1}^n$, the functions $g_i(w) = Z'_i(Y'_i - (X'_i)^T w)$ satisfy Assumption (ref). Formally, we prove the following theorem (see Appendix (ref)):

theoremLet $\epsilon > 0$. Suppose that $\epsilon < c\min(\lambda^2/(\tau L^2), \lambda^4/L^4)$ for a sufficiently small constant $c>0$, and suppose that $n \geq C(d+p)^5 \tau \log((p+d)/\tau\epsilon)/\epsilon^2$ for a sufficiently large constant $C$. Then with probability at least $0.95$ over the samples $(X_i, Y_i, Z_i)_{i=1}^n$, the following holds: for any $\epsilon$-corruption of the samples and any upper bound $R_0 \geq \left \lVert w^* \right \rVert_2$, Assumption (ref) is satisfied. In that event, if $L$, $\lambda$, $\sigma$, and $\epsilon$ are known, then there is a $\operatorname{poly}(n,d,p,\log(1/\delta),\log(R_0/(\sigma\sqrt{\epsilon})))$-time algorithm which produces an estimate $\hat{w}$ satisfying, with probability at least $1-\delta$: \[\left \lVert \hat{w} - w^* \right \rVert_2 \leq O(\sigma (L^{3/2}/\lambda^2)\sqrt{\epsilon})\]

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {Robust IV Logistic Regression} Let $Z$ be a vector of $p$ real-valued instruments, and let $X$ be a vector of $d$ real-valued covariates. Suppose that $Z$ and $X$ are mean-zero. Suppose that the response can be described as $Y = G(X^T w^*) + \xi$ for some fixed $w^* \in \mathbb{R}^d$, where $G$ is the (unscaled) logistic function. The proofs only use $1$-Lipschitzness of $G$ and $G'$, and that $G'(0)$ is bounded away from $0$.

As far as distributional assumptions, we assume in this section that Assumption (ref) holds, and additionally assume that the norm bound satisfies $R_0 \leq c\min(\lambda^2/L, \lambda/\sqrt{\tau L^3})$ for an appropriate constant $c$, where $\lambda$, $L$, and $\tau$ are as required for the Assumption. We obtain the following algorithmic result (proof in Appendix (ref)):

theoremLet $\epsilon > 0$. Suppose that $\epsilon < c\min(\lambda^2/(\tau L^2), \lambda^4/L^4)$ for a sufficiently small constant $c>0$, and suppose that $n \geq C(d+p)^5 \tau \log((p+d)/\tau\epsilon)/\epsilon^2$ for a sufficiently large constant $C$. Suppose that $\left \lVert w^* \right \rVert_2 \leq R_0 \leq c\min(\lambda^2/L,\lambda/\sqrt{\tau L^3})$. Then with probability at least $0.95$ over the samples $(X_i, Y_i, Z_i)_{i=1}^n$, the following holds: for any $\epsilon$-corruption of the samples, Assumption (ref) is satisfied. In that event, if $R_0$, $L$, $\lambda$, $\sigma$, and $\epsilon$ are known, then there is a $\operatorname{poly}(n,d,p,\log(1/\delta),\log(R_0/(\sigma\sqrt{\epsilon})))$-time algorithm which produces an estimate $\hat{w}$ satisfying, with probability at least $1-\delta$: \[\left \lVert \hat{w} - w^* \right \rVert_2 \leq O(\sigma (L^{3/2}/\lambda^2)\sqrt{\epsilon})\]

Experiments

In this section we corroborate our theory by applying our algorithm Iterated-Gmm-Sever to several datasets for IV linear regression with heterogeneous treatment effects. This is a natural setting in which the instruments and covariates are high-dimensional, necessitating dimension-independent robust estimators.

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {IV Linear Regression with Heterogeneous Treatment Effects.} Consider a study in which each sample has a vector $X$ of characteristics, a scalar instrument $Z$, a scalar treatment $T$, and a response $Y$. Assuming that the average treatment effect is linear in the characteristics with unknown coefficients, and that the response noise is independent of the instrument, we can write a moment condition \[\mathbb{E}[XZ(Y - T\langle X, w^* \rangle - \langle X, \beta \rangle)] = 0.\] This can be interpreted as an IV linear regression, and therefore our algorithm applies to it.

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {Synthetic experiment.} For our first experiment, we generate a unknown $20$-dimensional parameter vector $\theta \sim N(0,I)$. We then generate $10000$ independent samples each with a $20$-dimensional characteristic vector $X$ drawn from $N(0, I)$. The instrument $Z$ is drawn from an unbiased Bernoulli distribution, and the binary treatment is drawn from a Bernoulli-$p$ distribution with \[p = \frac{1}{1 + \exp(-Z-\sqrt{20}U\bar{X})},\] where $U$ is a standard normal random variable and $\bar{X} = \frac{1}{20}\sum_{j=1}^{20} X_j$. Finally, the response is \[Y = \langle X, \theta\rangle T + U.\] The treated samples ($T = 1$) with positive $\bar{X}$ tend to have larger $U$ (and hence larger response), and the treated samples with negative $\bar{X}$ tend to have smaller $U$ (and hence smaller response), so ordinary least-squares would tend to overestimate the treatment effect in the direction of the all-ones vector. However, $U$ is by construction independent of $XZ$, so $Z$ is a valid instrument. Indeed, in the absence of corruption, IV linear regression approximately recovers the true parameter $\theta$.

We then corrupt an $\epsilon$-fraction of the samples, by setting the characteristic vector equal to the all-ones vector (and leaving the instrument and response unchanged). We compute the $\ell_2$ recovery error of Iterated-Gmm-Sever, classical IV, and two-stage Huber regression for $\epsilon$ varying between $0.01$ and $0.5$. For each choice of $\epsilon$, we repeat the experiment $10$ times and average the recovery errors for each algorithm. See Figure (ref) for the results.

figure[figure omitted — 741 chars of source]

\@startsection{paragraph}{4} {\z@}{1.25ex \@plus 1ex \@minus .2ex}{-1em} {\normalfont} {Semi-synthetic experiment.} In this experiment, we use the data of Card card1993using from the National Longitudinal Survey of Young Men for estimating the average treatment effect (ATE) of education on 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 and demographic indicator variables). For simplicity, we restrict the model to only two covariates (years and squared years of labor force experience). We find that the ATE estimated by Iterated-Gmm-Sever is close to the positive ATE estimated by classical IV, suggesting that Card's inference may be robust. Next, we corrupt an $\epsilon$-fraction of the data. Specifically, we solve the IV regression on the uncorrupted data, and we alter the responses of a random $\epsilon$-fraction of the data in a way such that the parameter which satisfies the moment conditions is exactly negated (for $\epsilon n$ not too small, this can be done by solving an underdetermined linear system). This in particular negates the ATE inferred by classical IV regression.

In Figure (ref), we plot the ATE inferred by IV and the ATE inferred by Iterated-Gmm-Sever as $\epsilon$ is varied from $0.01$ to $0.4$ (the Iterated-Gmm-Sever breaks down on this data for larger levels of corruption). We see that Iterated-Gmm-Sever approximately recovers the correct (positive) ATE of the uncorrupted data, for $\epsilon$ up to around $0.15$. For larger $\epsilon$, the estimate becomes unstable. This is due to the algorithm removing some but not all of the outliers, which are very large norm. We expect that an additional norm thresholding procedure could help remedy this instability, but further investigation may be required.