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.
51,878 characters · 14 sections · 74 citation commands
Minimax Instrumental Variable Regression and $L_2$ Convergence Guarantees without Identification or Closedness
\affil[1]{Cornell University} \affil[2]{Tsinghua University} \affil[3]{Massachusetts Institute of Technology} \affil[4]{Stanford University}
Instrumental variable (IV) estimation is an important problem in many applications. Examples include causal inference angrist1995identification,newey2003instrumental,deaner2018proxy,cui2020semiparametric, missing data problems wang2014instrumental,miao2015identification, asset pricing models chen2014local,christensen2017nonparametric,escanciano2015nonparametric, dynamic discrete choice models kalouptsidi2021linear, and reinforcement learning liao2021instrumental,uehara2021finite.
In this paper, we focus on the estimation of nonparametric IV (NPIV) regression newey2003instrumental. This problem involves three sets of variables $X$, $Y$, and $Z$ that take values in compact Euclidean sets $D_X$, $D_Y$, and $D_Z$, respectively. In the original IV estimation problem, $X$ stands for endogenous variables, $Y$ stands for an outcome variable, and $Z$ stands for exogenous IVs. We define $L_2(X),L_2(Z)$ as the $L_2$ spaces of functions of $X, Z$ respectively, defined in terms of their distributions. We are interested in solving the following equation with respect to $h \in L_2(Z)$:
This equation can be alternatively written as $\Tcal h = r_0$, where $r_0(Z) = \EE[Y \mid Z]$, and $\Tcal: L_2(X) \to L_2(Z)$ is a bounded linear operator that maps every $h \in L_2(X)$ to $\EE\bracks{h(X) \mid Z} \in L_2(Z)$. Here both the function $r_0$ and the operator $\Tcal$ are unknown. Instead, we only have access to a set of independent and identically distributed observations $\Dcal \coloneqq \{X_i,Y_i,Z_i\}_{i=1}^n$.
There has been a surge in interest in NPIV regressions. A number of classical works have proposed sieve or kernel-based estimators carrasco2007linear,horowitz2011applied,newey2013nonparametric,newey2003instrumental,chen2007large. However, NPIV estimation is notoriously difficult because it is an ill-posed inverse problem. In particular, the solution to the NPIV equation $\Tcal h = r_0$ may not be unique, and even if it is unique, the solution may depend on the underlying data distribution discontinuously carrasco2007linear. Therefore, existing works typically assume that the NPIV solution is unique andrews2017examples,newey2003instrumental. Even if it is not the case, they restrict the linear operator $\Tcal$ and the NPIV solution florens2011identification,chen2021robust. A widely used restriction is the source condition, which assumes that the IV solution belongs to a subspace defined by the operator $\Tcal$ carrasco2007linear,cavalier2011inverse,chen2011rate. Under these conditions, the estimators proposed in these classic literature can have strong theoretical guarantees. However, these traditional nonparametric estimators do not allow for the integration of modern, flexible general function approximation methods such as neural networks or tree-based methods.
To overcome this limitation, recent works have proposed various algorithms that can accommodate general function approximation. These algorithms typically employ two function classes, $\Hcal$ and $\Gcal$. In particular, the function class $\Hcal$ is the hypothesis class for the solution to the NPIV equation $\Tcal h=r_0$. The function class $\Gcal$, often referred to as a witness function class or discriminator class, is introduced to witness how much each given function $h$ violates the NPIV equation. Then, NPIV estimators are defined as solutions to a minimax optimization problem lewis2018adversarial,bennett2019deep,dikkala2020minimax,LiaoLuofeng2020PENE,muandet2020dual:
where $L(h,g)$ is an objective function mapping from $\Hcal \times \Gcal$ to $\mathbb{R}$.
Although highly flexible, these minimax approaches have several limitations. First, they typically assume that the solution to the NPIV equation $\Tcal h=r_0$ is unique. However, this assumption can be easily violated if the instrumental variables are not very strong andrews2005inference,Andrews2019weak, and they usually do not hold in proximal causal inference kallus2021causal. Secondly, the minimax estimators may not give strong $L_2$ error rate guarantees, and instead only have error rate guarantees in terms of a weaker projected mean squared error (MSE) dikkala2020minimax. However, even when the projected MSE vanishes to zero, the minimax estimator may not converge to any fixed IV solution since the projected MSE is a pseudometric unlike the $L_2$ metric. Thirdly, current minimax estimators typically need some form of closedness condition, such as $\Tcal h \in \Gcal$ for any $h \in \Hcal$ dikkala2020minimax,LiaoLuofeng2020PENE or other close variant bennett2022inference. However, this assumption may impose stringent restrictions on the operator $\Tcal$, noting that $\Gcal$ must be a restricted class to ensure bounded statistical complexity. In particular, the closedness assumption is at odds with the widely used source condition, since we will show that the closedness assumption is more plausible when the spectrum of $\Tcal$ decays more slowly while the source condition is more plausible when the spectrum decays more rapidly.
To the best of our knowledge, all current approaches incorporating general function approximation for IV problems suffer from at least one of the three limitations listed above. In this paper, we propose the first method that avoids all three of these limitations. Specifically, we do not assume that the NPIV solution is unique, and instead we target the least norm solution $h_0$. This is a standard approach for inverse problems with non-unique solutions florens2011identification,babii2017completeness,chen2021robust,bennett2022inference. We show that our proposed estimator can converge to the least norm IV solution and derive its $L_2$ error rate guarantee. These theoretical guarantees only need the fairly standard source condition and realizability assumptions (i.e., well-specification of $\Hcal$ and $\Qcal$). (ref) summarizes the assumptions and guarantees in our paper and related ones.
Our proposed estimator and its theory are grounded in the novel insight that finding the least norm solution $h_0$ to $\Tcal h=r_0$ can be viewed as a constrained optimization problem. In particular, we show that the least norm solution can be uniquely identified as a saddle point of the minimax optimization of the Lagrangian. Although previous minimax estimators also leverage minimax optimization, their inner maximization is used to approximate the projected MSE $\EE[{\prns{[\Tcal h](Z) - r_0(Z)}^2}]$, which necessitates the closedness assumption. In contrast, the inner maximization in our methods results from the method of Lagrange multipliers, and it does not need the closedness assumption. Interestingly, we prove that the source condition is the sufficient and necessary condition for the existence of stationary Lagrange multipliers and thus the saddle point to our minimax optimization problem. This also reveals a new role of the source condition widely used in inverse problems.
Our paper is organized as follows. In \pref{sec:setup}, we present our setup of IV estimation and the limitations of current works in this setting. In \pref{sec:algorithm}, we introduce our minimax estimator by framing the problem as a constrained optimization problem. In \pref{sec:primary_identification}, we demonstrate that the minimax optimization identifies the least norm solution given infinite data. In \pref{sec:finite}, we present the finite-sample error guarantee, i.e., $L_2$ convergence rate. In \pref{sec:discussion}, we compare our estimator and theory to those in closely related works. Finally, we conclude our paper in \pref{sec:conclusion}.
Instrumental variable estimation has received considerable attention as a subclass of inverse problems, as detailed in the works of carrasco2007linear,cavalier2011inverse, newey2013nonparametric,ito2014inverse.
Even when the operator $\Tcal$ and response $r_0$ are known, nonparametric instrumental variable estimation poses significant difficulties due to its ill-posed nature. The ill-posedness often refers to the presence of one or more of the following characteristics: (1) the absence of solutions, (2) the existence of multiple solutions, and (3) the discontinuity of the inverse of $\Tcal$. To address these challenges, various regularization techniques have been proposed, such as compactness of the solution space newey2003instrumental, Tikhonov regularization, and Landweber–Fridman regularization carrasco2007linear,cavalier2011inverse. In practical settings where $\Tcal$ and $r_0$ are unknown, a range of estimators have been proposed in the literature, including series-based estimators ai2003efficient,hall2005nonparametric,blundell2007semi,chen2011rate,darolles2011nonparametric,chen2012estimation,florens2011identification,chen2021robust, kernel-based estimators hall2005nonparametric,horowitz2007asymptotic, and RKHS-based estimators singh2019kernel,muandet2020dual.
Recently, there has been growing interest in the application of general function approximation techniques, such as deep neural networks and random forests, to instrumental variable problems in a unified manner dikkala2020minimax,lewis2018adversarial,bennett2019deep,zhang2020maximum. Among these approaches, dikkala2020minimax,LiaoLuofeng2020PENE,bennett2022inference provide finite-sample convergence rate guarantees. Specifically, LiaoLuofeng2020PENE establishes $L_2$ convergence by linking minimax optimization with Tikhonov regularization under the assumption of the source condition. bennett2022inference establishes an $L_2$ convergence guarantee under the source condition from a distinct perspective. Notably, the assumptions we need are strictly weaker than those of bennett2022inference. dikkala2020minimax guarantees convergence in terms of projected mean squared error without the source condition; however, this guarantee is insufficient to identify a specific element when the solution is not unique. These works dikkala2020minimax,LiaoLuofeng2020PENE,bennett2022inference rely on the so-called closedness assumption, which imposes restrictions on the smoothness of the operator $\Tcal$ via the witness class. This assumption has been the subject of considerable discussion in the context of offline reinforcement learning, with researchers exploring ways to relax it chen2019information,uehara2020minimax,foster2021offline,huang2022beyond. In this paper, we examine the relaxation of this assumption in a more general IV setting. { This is of importance since the source condition and closedness are inherently conflicting. }
We note that there are a number of alternative approaches for integrating machine learning into instrumental variable estimation hartford2017deep,yu2018deep,xu2020learning,liu2020deep,kato2021learning,lu2021machine. However, to the best of our knowledge, these approaches do not offer an $L_2$ convergence rate guarantee in the absence of the assumption of uniqueness.
We aim to solve the following equation with respect to $h$:
where $r_0(Z) = \EE[Y\mid Z]\in L_2(Z)$ is an unknown function and $\Tcal: L_2(X) \to L_2(Z)$ is an unknown conditional expectation operator that maps any $h \in L_2(X)$ to $\EE[h(X)\mid Z]$. Note that $\Tcal$ is a bounded operator since its norm is upper-bounded by 1 via Jensen's inequality. Moreover, we use $\Tcal^{\star}: L_2(Z) \to L_2(X)$ to denote the adjoint operator of $\Tcal$, i.e., $\langle g,\Tcal h\rangle_{L_2(Z)}=\langle \Tcal^{\star}g,h\rangle_{L_2(X)}$ for any $h \in L_2(X), g \in L_2(Z)$ where $\langle \cdot,\cdot \rangle_{L_2(X)}$ and $\langle \cdot,\cdot \rangle_{L_2(Z)}$ are inner products over $L_2(X)$ and $L_2(Z)$, respectively. It is known that $\Tcal^{*}$ is given by $[\Tcal^* g](X) = \EE[g(Z)\mid X]$ for any $g \in L_2(Z)$ carrasco2007linear. Importantly, here we do not assume compactness of $\Tcal$, because compactness is violated whenever $X, Z$ include common variables, as is the case in many applications deaner2018proxy,cui2020semiparametric. Moreover, we denote the range space of $\Tcal$ by $\Rcal(\Tcal)$, i.e., $\Rcal(\Tcal)=\{\Tcal h: h \in L_2(X)\}$.
Throughout this work, we assume that there exists a solution to (ref).
Most of the existing literature further assumes that $\Tcal$ is injective and the solution to (ref) is unique. However, even in this case, (ref) still corresponds to an ill-posed inverse problem, since the inverse operator $\Tcal^{-1}$ is generally unbounded, so the NIPV solution can be very sensitive to even slight perturbations to the data distributions. Without further restrictions, we can only obtain an estimator $\hat h$ with convergence guarantee in terms of the projected MSE $\EE[\{\Tcal \hat h-r_0\}^2(Z)] = \EE[\{\Tcal (\hat h-h)\}^2(Z)]$ for $h\in \Ncal_{r_0}(\Tcal)$. However, the projected MSE is only a pseudometric. Hence, even if $\EE[\{\Tcal(\hat h-h)\}^2(Z)]$ vanishes to zero, the estimator $\hat h$ may not converge to a fixed point. Furthermore, the projected MSE is weaker than the valid metric such as the $L_2$ metric. Indeed, according to Jensen's inequality, we have $\EE[\{\hat h-h)\}^2(X)]\geq \EE[\{\Tcal(\hat h-h)\}^2(Z)]. $ However, the other direction generally does not hold. Thus $\EE[\{\hat h-h)\}^2(X)]$ may not vanish even when $\EE[\{\Tcal(\hat h-h)\}^2(Z)]$ does.
In many problems, $L_2$ rate guarantees are preferable or even necessary hall2005nonparametric,chen2011rate,kallus2021causal,uehara2021finite. In order to achieve $L_2$ convergence, we need to further restrict the ill-posedness of the NPIV problem. One common way is to restrict the magnitude of the ill-posedness measure $\sup_{h \in \Hcal}\frac{ \EE[\{h-h')\}^2(X)] }{\EE[\{\Tcal(h-h')\}^2(Z)]}$ for any solution $h' \in \Ncal_{r_0}(\Tcal)$, where $\Hcal$ is the function class used to obtain the estimator dikkala2020minimax,chen2012estimation. This allows us to translate projected MSE guarantees to corresponding $L_2$ error rates under the uniqueness of (ref).
However, in this paper, we do not assume a unique solution to (ref), because it may not hold in many practical settings. In particular, uniqueness is violated when instrumental variables are weak andrews2005inference,Andrews2019weak. For instance, when the spaces $D_X$ and $D_Z$ are discrete and the cardinality of $D_Z$ exceeds that of $D_X$, uniqueness generally does not hold. Moreover, uniqueness is usually violated in proximal causal inference, as kallus2021causal demonstrates in various examples. When solutions are non-unique, (ref) becomes even more ill-posed. In this case, existing estimators may still have projected MSE guarantees, but obtaining $L_2$ rate guarantees becomes much more difficult. In particular, the ill-posedness measure is generally infinity and thus uninformative. Most of the existing estimators do not necessarily converge to any particular solution in $\Ncal_{r_0}(\Tcal)$ in terms of the $L_2$ metric.
Given that there may be (infinitely) many solutions in $\Ncal_{r_0}(\Tcal)$, we propose to target a particular solution that achieves the least norm, that is,
This least norm solution is well-defined as it is the projection of the origin in $L_2(X)$ onto a closed affine space $\Ncal_{r_0}(\Tcal) \subseteq L_2(X)$. We formalize this in the following lemma.
We note that some of the existing literature also targets the least norm solution when the IV equation admits non-unique solutions florens2011identification,santos2011instrumental,chen2021robust, but they all focus on classic sieve or kernel-based estimators. The only exception is bennett2022inference as they employ general function approximation while allowing for non-unique solutions. But as we discuss in (ref), their method requires a closedness assumption that puts strong restrictions on the operator $\Tcal$. In this paper, we propose a new estimator for the least norm solution $h_0$ with a strong $L_2$ convergence guarantee. Importantly, our estimator accommodates general function approximation but does not need the closedness assumption, thereby improving upon the existing literature.
In this section, we propose our estimator for the least norm solution $h_0$ in (ref). To this end, we first provide a reformulation of the solution $h_0$. Note that
This is a constrained optimization problem over the Hilbert space $L_2(X)$. Following the method of Lagrange multipliers, we can consider an alternative minimax optimization:
where $g$ corresponds to a Lagrange multiplier.
In (ref), the objective function $L(h, q)$ is unknown since the two inner products involve the unknown function $r_0$, the unknown operator $\Tcal$, and the unknown distribution of $X$ and $Z$. To construct an estimator based on (ref), we first rewrite the inner products into expectations with respect to the distribution of $X$ and $Z$:
Then we can replace the unknown expectations with empirical averages, and restrict the functions $h$ and $g$ to some classes $\Hcal\subset [D_X \to \RR]$ and $\Gcal \subset [D_Z\to \RR]$. This leads to the following estimator:
where $\EE_n\bracks{\cdot}$ stands for the empirical average operator based on sample data $\Dcal=\{X_i,Y_i,Z_i\}$. For example, we have $\EE_n[h^2(X)] = \frac{1}{n}\sum_{i=1}^n h^2(X_i)$. Notably, the term $\EE_n[h^2(X)]$ in (ref) can be viewed as a penalization term, so we call our estimator a penalized minimax estimator. The role of this penalization term is later discussed in \pref{thm:idenfication}.
The estimator $\hat h_{\mathrm{mn}}$ in (ref) has a minimax optimization formulation. The computational perspective will be discussed in \pref{sec:comptuational}. This is in line with many recent machine learning IV estimators with general function approximation (see a review in (ref)). However, our minimax optimization in (ref) is motivated by the method of Lagrange multipliers, while existing minimax estimators are based on fundamentally different principles. As a result, our objective function $L_n(h, g)$ differs from those used in existing minimax estimators. In particular, our minimax estimator requires quite different conditions, as we will discuss in (ref).
To justify the objective function in \pref{eq:motivatioin3}, we need to further guarantee that
In Section (ref), we establish (ref) under fairly mild conditions. Based on this, we then further derive the $L_2$ convergence rate of our proposed estimator $\hat h_{\mathrm{mn}}$.
In this section, we establish that our proposed minimax formulation can indeed identify the least norm solution $h_0$ as shown in (ref). We start with introducing a key assumption for our result, and then present our identification result under this assumption.
Our identification crucially depends on the following source condition.
Assumption (ref) further strengthens Assumption (ref) in that it restricts $r_0$ to a smaller subspace $\Rcal(\Tcal\Tcal^{\star}) \subseteq \Rcal(\Tcal)$. In particular, we have $\Rcal(\Tcal) = \Tcal(\overline{\Rcal({\Tcal^{\star}})})$\footnote{To see this note that $L_2(X) = \overline{\Rcal(\Tcal^\star)} \oplus \Rcal(\Tcal^\star)^\perp$, and $\Rcal(\Tcal^\star)^\perp = \Ncal(\Tcal)$, so $\Tcal(L_2(X)) = \Tcal(\overline{\Rcal(T^\star)})$.} and $\Rcal(\Tcal \Tcal^\star) = \Tcal(\Rcal({\Tcal^{\star}}))$, so $\Rcal(\Tcal \Tcal^\star)$ is generally a strict subset of $\Rcal(\Tcal)$, unless $\Rcal(\Tcal^\star)$ is a closed set. It is well known that for ill-posed inverse problems, the operator $\Tcal^\star$ generally does not have a closed range space carrasco2007linear, thus in general Assumption (ref) imposes non-trivial restrictions on the ill-posedness of the inverse problem. In (ref), we provide a more concrete example to illustrate these restrictions.
Source conditions are common assumptions used to derive strong convergence rate guarantees in the inverse problem literature. They have been widely used for both inverse problems with known operators engl1996regularization,ito2014inverse and IV problems with unknown operators florens2011identification,carrasco2007linear,liao2021instrumental. A standard source condition in the literature is that the solution $h_0$ satisfies $h_0 \in \Rcal((\Tcal\Tcal^{\star})^{\beta/2})$ for a positive exponent $\beta > 0$. Our source condition in Assumption (ref) can be shown to be equivalent to $h_0 \in \Rcal((\Tcal\Tcal^{\star})^{1/2})$ via the spectral theory of linear operators cavalier2011inverse. Thus, our Assumption (ref) is a source condition of this kind with source exponent $\beta = 1$.
Assumption (ref) implies that there exists $\bar{g}_0 \in L_2(Z)$ such that
In fact, any $\bar g_0$ satisfying (ref) is closely related to the least norm solution $h_0$.
In particular, given (ref), the functions $\bar g_0$ that satisfy (ref) are given by:
In the next subsection, we will show the importance of the source condition given by Assumption (ref). In particular, this condition ensures that we can obtain $h_0$ from the saddle points of $L(h,g)$.
Here, we characterize the saddle points of $L(h,g)$ under Assumption (ref), as follows:
It is well-known that $(h',g')$ is a saddle point if and only if we have the “strong duality” condition\\ $ \inf_{h \in L_2(X)} \sup_{g \in L_2(Z)}L(h,g) = \sup_{g \in L_2(Z)} \inf_{h \in L_2(X)} L(h,g)$ and
We provide formal proof for this in \pref{sec:auxiliary}. Given this equivalent characterization of the saddle point, we can obtain the following corollary from \pref{lem:saddle_point}.
It is worth noting that the equality for $h_0$ in (ref) holds even without the source condition. Moreover, the strong duality $ \inf_{h \in L_2(X)} \sup_{g \in L_2(Z)}L(h,g) = \sup_{g \in L_2(Z)} \inf_{h \in L_2(X)} L(h,g)$ also holds in the absence of this source condition. However, the source condition is important to establish the existence of $\argmax_{g \in L_2(Z)} \inf_{h \in L_2(X)} L(h,g)$ and the second statement in (ref). Equivalently, this shows that the source condition guarantees the existence of stationary Lagrangian multipliers for the problem in (ref), and the set of stationary Lagrangian multipliers is given by $\Ncal_{h_0}(\Tcal^{\star})$.
So far we have demonstrated that Assumption (ref) is a sufficient condition for the existence of saddle points. Interestingly, it is also a necessary condition for their existence.
The above lemma is proved by first showing that the saddle point exists if and only if there exists a solution to $ \argmin_{g \in L_2(Z)}\|\Tcal^{*}g-h_0\|^2_2$. We then demonstrate that the existence of this optimization problem is equivalent to the source condition ((ref)). Our \pref{lem:saddle_point} and \pref{lem:saddle_point2} show that the source condition is closely related to the existence of stationary Lagrangian multipliers for the constrained optimization formulation of $h_0$. To our knowledge, this relation is novel in the literature.
\pref{lem:saddle_point} characterizes the saddle points over the unrestricted $L_2(X)$ and $L_2(Z)$ spaces. However, in practical estimation, we can only use some function classes $\Hcal \subset L_2(X),\Gcal \subset L_2(Z)$ with limited statistical complexity. For these two restricted classes to capture some saddle points, we need them to satisfy the following realizability assumptions.
The realizability assumptions above require that the function classes $\Hcal$ and $\Gcal$ are well-specified, in that they contain at least some true saddle points. In particular, Assumption (ref) is equivalent to $h_0 \in \Tcal^{*}\Gcal$. In the following theorem, we further extend the saddle point characterization of $h_0$ in (ref) to these restricted classes under these realizability conditions.
(ref) shows that under the source condition and the realizability assumptions, the min-max optimization of our proposed objective over the function classes $\Hcal, \Gcal$ can recover the saddle points in the classes. At a high level, the proof of this theorem works by showing: (1) saddle points over the original class remain saddle points over the restricted classes; (2) any additional saddle points over the restricted classes are best-responses to saddle points over the original class; and (3) $h_0$ is a unique best response to any $\bar g \in \Ncal_{h_0}(\Tcal^{\star})$ as a result of strong convexity of $L(h,g)$ in $h$ induced by $\langle h,h\rangle_{L_2(X)}$. See \pref{sec:general} for details.
As discussed in \pref{sec:primary_identification}, our proposed minimax optimization formulation can identify the target least norm solution $h_0$ when the population distribution is known. In this section, we further show that our finite-sample estimator $\hat h_{\mathrm{mn}}$ in (ref) converges to $h_0$, and we derive its $L_2$ error rate.
Notably, the assumptions required in \pref{thm:main} are identical to those in (ref). In particular, both theorems only require that the function classes $\Hcal$ and $\Qcal$ satisfy the realizability conditions Assumption (ref),(ref). Realizability is a fundamental assumption in statistical learning theory. For instance, realizability is a standard assumption in least squares regression problems wainwright2019high. To the best of our knowledge, existing minimax IV regression estimators additionally require much stronger conditions such as $\Tcal \Hcal \subset \Gcal$ or $\Tcal^{*}\Gcal \subset \Hcal$. These conditions are often referred to as the closedness condition, and they impose additional restrictions on the operator $\Tcal$. See (ref) for a detailed discussion.
It then remains to bound the right-hand side term in \pref{thm:main}. This is an empirical process term, which can be easily upper-bounded by invoking standard statistical learning theory for any reasonable function classes $\Hcal,\Gcal$ with bounded statistical complexities. In particular, we can use standard symmetrization arguments to bound the right-hand side of \pref{thm:main} with the Rademacher complexities of $\Hcal, \Gcal$. The Rademacher complexity $\mathfrak{R}_n(\Hcal)$ of class $\Hcal$ is defined as $\mathfrak{R}_n(\Hcal) = n^{-1} \EE[\sup_{h\in \Hcal}\sum_{i=1}^n \sigma_i h(X_i)]$ where $\{\sigma_1, \dots, \sigma_n\}$ are independent random variables drawn from the Rademacher distribution. The Rademacher complexity $\mathfrak{R}_n(\Gcal)$ of class $\Gcal$ can be defined analogously.
Furthermore, for given function classes $\Hcal, \Qcal$, we can obtain final $L_2$ convergence rates by plugging in off-the-shelf results of Rademacher complexities. For example, the following corollary is obtained by instantiating \pref{thm:main} to finite classes.
As another example, we instantiate (ref) for more general nonparametric classes whose complexity are characterized by their covering numbers.
If we specialize (ref) to Sobolev balls $\Hcal,\Gcal$ with smoothness parameter $\alpha$ and input dimension $d$, we have $\beta = d/\alpha$, so the rates become $O(n^{-1/4})$ when $\alpha/d > 2$ and $O(n^{-\alpha/(2d)})$ when $\alpha/d \leq 2$. It is an interesting question whether this rate is optimal. Although chen2011rate derives a minimax rate for NPIV regression estimation, their result requires the NIPV equation to have a unique solution and they impose stronger conditions on the function classes, so it is not directly comparable to our rate. A thorough investigation of the rate optimality is left for future work.
Finally, we also consider the case where the function classes $\Hcal, \Gcal$ are misspecified so they may not satisfy the realizability assumptions. This result is useful when we use sieve estimators based on sample-dependent function classes $\Hcal$ and $\Gcal$, that approximate certain function spaces. For example, $\Hcal, \Gcal$ can be linear models with polynomial basis functions or neural networks with growing dimensions, which can gradually approach H\"older or Sobolev balls chen2007large.
Compared to (ref), the upper bound in (ref) involves additional misspecification errors $\epsilon_h, \epsilon_g$ due to misspecified $\Hcal, \Gcal$. The empirical process term in (ref) can be again bounded by Rademacher complexities.
In this section, we compare our method with existing minimax NPIV estimators in dikkala2020minimax,LiaoLuofeng2020PENE,bennett2022inference as they are most relevant. Other existing minimax estimators are similar so we only briefly review them in Section (ref).
dikkala2020minimax considers the following minimax estimator:
Here for simplicity, we omit possible additional regularizers for $h$ and $g$.
dikkala2020minimax assumes the closedness condition that $\Tcal(\Hcal-h^{\diamond}_0)\subset \Gcal$ where $h^{\diamond}_0$ can be an arbitrary solution to $\Tcal h = r_0$ (note this condition is invariant to the choice of $h^{\diamond}_0$). Under this condition, letting $L(h,g)$ be the population analog of $\tilde L_n(h,g)$, it can be shown that $\max_{g \in \Gcal}\EE[{\tilde L(h,g)}] = 0.5 \EE[(\Tcal(h^{\diamond}_0-h)[Z])^2] = 0.5 \EE[{\prns{[\Tcal h](Z) - r_0(Z)}^2}]$. In other words, the minimax objective in dikkala2020minimax is used to approximate the projected MSE objective under the closedness condition. In contrast, our proposed minimax objective is motivated by the method of Lagrange multipliers, and it does not need the closedness condition.
To compare the theory in dikkala2020minimax with our theory, we consider finite classes $\Hcal,\Gcal$ for simplicity. Then the theory in dikkala2020minimax implies that if $\Ncal_{r_0}(\Tcal) \cap \Hcal \neq 0$ and $\Tcal (\Hcal-h^{\diamond}_0)\subset \Gcal$ for $h^{\diamond}_0 \in \Ncal_{r_0}(\Tcal)$, then we have $ \EE[\{\Tcal(\hat h_{\mathrm{pro}}-h^{\diamond}_0)\}^2(Z)] = O\prns{\prns{\frac{\ln\prns{|\Hcal||\Gcal|/\delta}}{n}}^{1/2}}$ with probability $1-\delta$.
Note that the rate $O((\ln(|\Hcal||\Gcal|)/n)^{1/2})$ above is faster than our rate $O((\ln(|\Hcal||\Gcal|)/n)^{1/4})$ in Corollary \pref{cor:iv2}. However, the rate above is for the weak projected MSE, while our rate in Corollary \pref{cor:iv2} is for the stronger $L_2$ error, so they are not comparable. In particular, the projected MSE rate cannot translate into an $L_2$ rate without further restrictions. dikkala2020minimax consider restrictiting the ill-posedness measure $\sup_{h \in \Hcal}\frac{ \EE[\{\hat h-h)\}^2(X)] }{\EE[\{\Tcal(\hat h-h)\}^2(Z)]}$. However, this ill-posedness measure may generally be infinite, and in fact is guaranteed to be infinite when the solutions to the NPIV problem are nonunique, so using it to get $L_2$ convergence rates is often problematic.
LiaoLuofeng2020PENE builds on dikkala2020minimax and incorporates additional Tikhonov regularization into the minimax optimization:
LiaoLuofeng2020PENE also needs the closedness assumption in dikkala2020minimax and a realizability assumption that the Tikhonov regularized solution $h_{0, \alpha}$ is contained in $\Hcal$ for small $\alpha$. In addition, they assume that the NPIV solution is unique and satisfies a source condition with exponent $\beta \in (0,1]$, and the regularization strength $\alpha$ vanishes to $0$ at an appropriate rate as $n \to \infty$. Under these conditions, they can derive an $L_2$ convergence rate. In particular, their $L_2$ rate has the order $O(n^{-1/6})$ when the function classes are e.g. finite or VC, and $\beta = 1$.
Our proposed estimator and theory significantly differ from LiaoLuofeng2020PENE. Specifically, our estimator does not involve the $\EE_n[g^2(Z)]$ term and our regularized term $\EE_n[h^2(X)]$ has a constant coefficient $0.5$ but (ref) needs a vanishing $\alpha$. Moreover, our theory accommodates non-unique solutions, and uses different realizability assumptions. Notably, under our source condition $\beta = 1$, our convergence rate $O(n^{-1/4})$ is faster than the rate $O(n^{-1/6})$ in LiaoLuofeng2020PENE.
Under the same source condition, bennett2022inference \footnote{{ Note the main focus of bennett2022inference is to estimate the Riesz representator (in their notation, $q^{\dagger}$) with $L_2$ error rates. However, their argument is easily adapted to our scenario. } } formulate the $L_2$ error of $h_0$ as projected MSEs: $ \EE[\{h_0-h\}^2(X) ] = \EE[(\Tcal^{*}\{\bar g_0-g\})^2(X)]$ where $\Tcal^{*} g=h$ and $\Tcal^{*} \bar g_0=h_0$. First, note that for any fixed $\bar g_0$ such that $T^\star \bar g_0 = h_0$, we have
Then, under the closedness assumption $\Tcal^{*}\Gcal \subset \Hcal$, we have
Then, noting that the inner minimizer $h$ satisfies $\Tcal^{*}g=h$ for any given $g$, and recalling the original goal is to find $h_0$ such that $\Tcal^{*}\bar g_0=h_0$, we can deduce that \footnote{Here, letting a loss function to be $L^{\star}(h,g)$, the equation $(\bar g_0,h_0)=\argmin_{g}\argmax_{h}L(h,g)$ means $\bar g_0=\argmin_{g}\max_{h}L(h,g)$ and $h_0=\argmax_{h}L(h,\bar g_0)$. }
Finally, their proposed estimator $\hat h_{\text{fli}}$ is given by replacing expectations with empirical averages.
In comparison to our proposed estimator $\hat h_{\mathrm{mn}}$, the difference lies in the flip of $\argmax$ and $\argmin$. Since $\Gcal,\Hcal$ could be non-convex, the two estimators are generally different. Indeed, this results in a significant difference in terms of the required assumptions. In $\hat h_{\text{fli}}$, the primary assumptions are the source condition, $\bar g_0 \in \Gcal$, and $\Tcal^{*}\Gcal \subset \Hcal$ (note that $h_0 \in \Hcal$ is implicit from the latter two conditions). Conversely, in our proposed estimator $\hat h_{\mathrm{mn}}$, the primary assumptions are the source condition and $\bar g_0 \in \Gcal,h_0 \in \Hcal$. This condition is strictly weaker as we dispense with the requirement of closedness. This improvement is significant due to the inherent conflict between the source condition and closedness, as elucidated next.
In (ref), the existing estimators all require certain closedness assumption, either $\Tcal(\Hcal-h^{\diamond}_0)\subset \Gcal$ for an arbitrary solution $h^{\diamond}_0$ to $\Tcal h = r_0$, or $\Tcal^{*}\Gcal \subset \Hcal$. In contrast, our proposed estimator does not need any closedness assumption. In this subsection, we show that the closedness conditions are inherently in tension with the source condition. This illustrates the benefit of getting rid of the source condition. For simplicity, we consider a compact linear operator $\Tcal$ that admits a singular value decomposition (SVD) $\{\sigma_i,u_i,v_i\}_{i=1}^{\infty}$, where $\{u_i\}_{i=1}^{\infty},\{v_i\}_{i=1}^{\infty}$ are orthonormal bases in the Hilbert spaces $L_2(Z),L_2(X)$, respectively, and $\sigma_1\geq \sigma_2\geq \cdots$ are the singular values. It follows that $\Tcal v_i =\sigma_i u_i,\Tcal^* u_i =\sigma_i v_i $, and $\Tcal\Tcal^{\star}$ has the SVD $\{\sigma^2_i,u_i,u_i\}_{i=1}^{\infty}$. Here we assume a compact operator merely for a simple countable SVD. Non-compact operators can be handled similarly, but involve more cumbersome notations cavalier2011inverse.
To understand the source condition in Assumption (ref), we write the function $r_0$ as $r_0 = \sum_{i=1}^{\infty} \gamma_i u_i$ with $\sum_{i = 1}^{\infty} \gamma^2_i<\infty$. The source condition $r_0 \in \Rcal(\Tcal\Tcal^{\star})$ means that there exists $\bar g_0=\sum_{i=1}^{\infty}\beta_i u_i $ with $\sum_{i=1}^{\infty}\beta^2_i<\infty$ such that $h_0= \Tcal^{*}\Tcal\bar g_0$. It follows from the SVD of $\Tcal\Tcal^{\star}$ that $\gamma_i=\sigma^2_i\beta_i$. Therefore, the source condition requires $\sum_{i=1}^{\infty} \gamma_i^2/\sigma^4_i<\infty$. This means that the function $r_0$ needs to be sufficiently smooth relative to the spectrum of $\mathcal{T}$. Obviously, the source condition is more readily satisfied when the decaying rate of $\{\sigma_i\}_{i=1}^{\infty}$ is slower, i.e., when the operators $\Tcal$ and $\Tcal^\star$ are less smooth. In contrast, the closedness conditions are generally more easily satisfied when $\{\sigma_i\}_{i=1}^{\infty}$ decays faster and the operators $\Tcal$ and $\Tcal^\star$ are more smooth.
Hence, we observe that the source condition and closedness imply opposing restrictions on the smoothness of the operators $\Tcal$ and $\Tcal^\star$.
In this paper, we study NPIV regression with general function approximation. We propose a penalized minimax estimator based on a novel constrained optimization formulation of the least norm IV solution. We prove that our estimator converges to this least norm solution, and derive its $L_2$ convergence rate under a source condition and realizability assumptions on both function classes for the minimax estimator. Notably, our estimator does not require uniqueness of the NPIV solution, and it avoids a closedness condition commonly assumed for existing minimax estimators. There are many interesting future directions of research. One direction is extending our work to more general inverse problems, including nonlinear inverse problems ito2014inverse. Another direction is extending our work to IV quantile regression chernozhukov2017instrumental.