Introduction
Instrumental variable (IV) analyses generally start by posing a structural equation :
Y = h s t r u c t u r a l ( X ) + ϵ , (1) Y = h_{\mathrm{structural}}(X) + \epsilon, \tag*{(1)} Y = h structural ( X ) + ϵ , (1) where h s t r u c t u r a l h_{\mathrm{structural}} h structural causal effect of X X X Y Y Y X X X ϵ \epsilon ϵ E [ ϵ ∣ X ] ≠ 0 \mathbb{E}[\epsilon\mid X] \ne0 E [ ϵ ∣ X ] = 0 Z Z Z statistical solution given joint observations of W = ( X , Y , Z ) ∼ P W = (X, Y, Z) \sim P W = ( X , Y , Z ) ∼ P h ↦ E P [ m ( W ; h ) ] h \mapsto\mathbb{E}_{P}[m(W; h)] h ↦ E P [ m ( W ; h )] h ∈ H h \in\mathcal{H} h ∈ H
T P h = r P , (2) T_{P}h = r_{P}, \tag*{(2)} T P h = r P , (2) where T P : H → G T_{P} : \mathcal{H} \to\mathcal{G} T P : H → G h ↦ arg min g ∈ G E P ( h ( X ) − g ( Z ) ) 2 h \mapsto\operatorname*{arg\,min}_{g \in\mathcal{G}} \mathbb{E}_{P}(h(X) - g(Z))^{2} h ↦ arg min g ∈ G E P ( h ( X ) − g ( Z ) ) 2 r P = arg min r ∈ G E P ( Y − r ( Z ) ) 2 r_{P} = \operatorname*{arg\,min}_{r \in\mathcal{G}} \mathbb{E}_{P}(Y - r(Z))^{2} r P = arg min r ∈ G E P ( Y − r ( Z ) ) 2 H , G \mathcal{H}, \mathcal{G} H , G X X X Z Z Z all square-integrable functions, then ( T P h ) ( Z ) = E P [ h ( X ) ∣ Z ] (T_{P}h)(Z) = \mathbb{E}_{P}[h(X) \mid Z] ( T P h ) ( Z ) = E P [ h ( X ) ∣ Z ]
There are two possible challenges with this:
The existence of solutions to Eq. (2). When we start with Eq. (1) with h s t r u c t u r a l ∈ H h_{\mathrm{structural}} \in\mathcal{H} h structural ∈ H H \mathcal{H} H linear structural equation [3 , 7 , 31 , 34 ] . Nonparametric IV (NPIV) analysis aims to relax this by allowing h s t r u c t u r a l h_{\mathrm{structural}} h structural [1 , 2 , 8 , 9 , 11 , 12 , 17 , 27 , 32 ] who achieve efficiency in this statistical model, then the estimator may well deteriorate very ungracefully when no perfect solution to Eq. (2) actually exists. This can be understood as exclusion and/or homogeneity (additive ϵ \epsilon ϵ exact same causal effect [4 , 5 , 24 ] ?
The uniqueness of E P [ m ( W ; h ) ] \mathbb{E}_{P}[m(W;h)] E P [ m ( W ; h )] Even if we have solutions to Eq. (2), there may be many, and they may not all lead to the same value of E P [ m ( W ; h ) ] \mathbb{E}_{P}[m(W;h)] E P [ m ( W ; h )] Z Z Z X X X h s t r u c t u r a l h_{\mathrm{structural}} h structural T P h = T P h ′ T_{P}h = T_{P}h' T P h = T P h ′ E P [ m ( W ; h ) ] = E P [ m ( W ; h ′ ) ] \mathbb{E}_{P}[m(W;h)] = \mathbb{E}_{P}[m(W;h')] E P [ m ( W ; h )] = E P [ m ( W ; h ′ )] h , h ′ ∈ H h,h' \in\mathcal{H} h , h ′ ∈ H G \mathcal{G} G T P ∗ g = a P T_{P}^{*}g = a_{P} T P ∗ g = a P a P ∈ H a_{P} \in\mathcal{H} a P ∈ H h ↦ E P [ m ( W ; h ) ] h \mapsto\mathbb{E}_{P}[m(W;h)] h ↦ E P [ m ( W ; h )] a P ∈ range ( T P ∗ ) ⊆ kernel ( T P ) ⊥ a_{P} \in\operatorname{range}(T_{P}^{*}) \subseteq\operatorname{kernel}(T_{P})^{\perp} a P ∈ range ( T P ∗ ) ⊆ kernel ( T P ) ⊥ 8 , 9 , 19 , 26 , 32 , ? ]. However, the same conundrum arises: a solution to that linear equation may well only approximately exist in practice.
In both cases, it would behoove us to not impose the assumptions of the existence of solutions (to T P h = r P T_{P}h = r_{P} T P h = r P T P ∗ g = a P T_{P}^{*}g = a_{P} T P ∗ g = a P perfect solutions may not really exist in practice and this can derail inference procedures that assume they do. Instead, we would rather target a statistical quantity that is well-defined regardless of existence of such solutions, coincides with the structural quantities when they do make sense, and degrades reasonably in mild violations of existence of solutions.
Toward that end, in this paper we consider debiased inference on the following estimand:
Ψ ( P ) : = E P [ g ( Z ) h ( X ) ] , h ∈ H P , g ∈ G P , \Psi(P) := \mathbb{E}_{P}[g(Z)h(X)], \qquad h \in\mathcal{H}_{P}, \quad g \in\mathcal{G}_{P}, Ψ ( P ) := E P [ g ( Z ) h ( X )] , h ∈ H P , g ∈ G P , where H P : = arg min h ∈ H ∥ T P h − r P ∥ L 2 ( P Z ) 2 \mathcal{H}_{P} := \arg\min_{h \in\mathcal{H}} \lVert T_{P}h - r_{P} \rVert_{L^{2}(P_{Z})}^{2} H P := arg min h ∈ H ∥ T P h − r P ∥ L 2 ( P Z ) 2 G P : = arg min g ∈ G ∥ T P ∗ g − a P ∥ L 2 ( P X ) 2 \mathcal{G}_{P} := \arg\min_{g \in\mathcal{G}} \lVert T_{P}^{*}g - a_{P} \rVert_{L^{2}(P_{X})}^{2} G P := arg min g ∈ G ∥ T P ∗ g − a P ∥ L 2 ( P X ) 2 T P h = r P T_{P}h = r_{P} T P h = r P T P ∗ g = a P T_{P}^{*}g = a_{P} T P ∗ g = a P T P h = r P T_{P}h = r_{P} T P h = r P T P ∗ g = a P T_{P}^{*}g = a_{P} T P ∗ g = a P
To allow sufficient generality so as to also cover such related problems as proximal causal inference [17 , 19 , 27 , 29 ] , we generalize r P r_{P} r P
G → R : g ↦ E P [ m ~ ( W ; g ) ] , (3) \mathcal{G} \to\mathbb{R}: g \mapsto\mathbb{E}_{P}[\widetilde{m}(W;g)], \tag*{(3)} G → R : g ↦ E P [ m ( W ; g )] , (3) where m ~ \widetilde{m} m m ~ ( W ; g ) = Y g ( Z ) \widetilde{m}(W;g) = Yg(Z) m ( W ; g ) = Y g ( Z ) a P a_{P} a P H → R : h ↦ E P [ m ( W ; h ) ] \mathcal{H} \to\mathbb{R}: h \mapsto\mathbb{E}_{P}[m(W;h)] H → R : h ↦ E P [ m ( W ; h )] m m m [9 ] for instantiation in proximal causal inference and missing-not-at-random data.
Setup and Identification
Notation. Throughout this paper we consider three random variables X , Y , Z X,Y,Z X , Y , Z E X , E Y , E Z E_X,E_Y,E_Z E X , E Y , E Z σ \sigma σ F E X , F E Y , F E Z \mathcal{F}_{E_X},\mathcal{F}_{E_Y},\mathcal{F}_{E_Z} F E X , F E Y , F E Z W W W ( X , Y , Z ) (X,Y,Z) ( X , Y , Z ) E W = E X × E Y × E Z E_W = E_X \times E_Y \times E_Z E W = E X × E Y × E Z ( Ω , F , P ) (\Omega,\mathcal{F},P) ( Ω , F , P ) E P \mathbb{E}_P E P E \mathbb{E} E P X , P Y , P Z P_X,P_Y,P_Z P X , P Y , P Z P P P X , Y , Z X,Y,Z X , Y , Z X ∼ P X , Y ∼ P Y , Z ∼ P Z X \sim P_X,Y \sim P_Y,Z \sim P_Z X ∼ P X , Y ∼ P Y , Z ∼ P Z ( E X , F E X ) (E_X,\mathcal{F}_{E_X}) ( E X , F E X ) P X P_X P X L 2 ( E X , F E X , P X ) L^2(E_X,\mathcal{F}_{E_X},P_X) L 2 ( E X , F E X , P X ) L 2 ( P X ) L^2(P_X) L 2 ( P X ) L 2 ( P Y ) L^2(P_Y) L 2 ( P Y ) L 2 ( P Z ) L^2(P_Z) L 2 ( P Z ) H , G \mathcal{H},\mathcal{G} H , G L 2 ( P X ) L^2(P_X) L 2 ( P X ) L 2 ( P Z ) L^2(P_Z) L 2 ( P Z ) ∥ ⋅ ∥ H = ∥ ⋅ ∥ L 2 ( P X ) \lVert\cdot\rVert_{\mathcal{H}} = \lVert\cdot\rVert_{L^2(P_X)} ∥ ⋅ ∥ H = ∥ ⋅ ∥ L 2 ( P X ) ∥ ⋅ ∥ G = ∥ ⋅ ∥ L 2 ( P Z ) \lVert\cdot\rVert_{\mathcal{G}} = \lVert\cdot\rVert_{L^2(P_Z)} ∥ ⋅ ∥ G = ∥ ⋅ ∥ L 2 ( P Z ) H 1 \mathcal{H}_1 H 1 H 2 \mathcal{H}_2 H 2 L ( H 1 , H 2 ) \mathcal{L}(\mathcal{H}_1,\mathcal{H}_2) L ( H 1 , H 2 ) H 1 \mathcal{H}_1 H 1 H 2 \mathcal{H}_2 H 2 ∥ ⋅ ∥ o p \lVert\cdot\rVert_{\mathrm{op}} ∥ ⋅ ∥ op A ∈ L ( H 1 , H 2 ) A \in\mathcal{L}(\mathcal{H}_1,\mathcal{H}_2) A ∈ L ( H 1 , H 2 ) A ∗ ∈ L ( H 2 , H 1 ) A^* \in\mathcal{L}(\mathcal{H}_2,\mathcal{H}_1) A ∗ ∈ L ( H 2 , H 1 ) A ⊆ H 1 A \subseteq\mathcal{H}_1 A ⊆ H 1 A ‾ \overline{A} A H 1 \mathcal{H}_1 H 1 A ⊥ ⊆ H 1 A^\perp\subseteq\mathcal{H}_1 A ⊥ ⊆ H 1 H 1 \mathcal{H}_1 H 1
We let T P : H → G T_P:\mathcal{H} \to\mathcal{G} T P : H → G h ↦ arg min g ∈ G E P [ ( h ( X ) − g ( Z ) ) 2 ] h \mapsto\arg\min_{g\in\mathcal{G}} \mathbb{E}_P[(h(X)-g(Z))^2] h ↦ arg min g ∈ G E P [( h ( X ) − g ( Z ) ) 2 ] T P T_P T P T P T_P T P ∥ T P ∥ o p ≤ 1 \lVert T_P\rVert_{\mathrm{op}} \le1 ∥ T P ∥ op ≤ 1 h ∈ H h \in\mathcal{H} h ∈ H g ∈ G g \in\mathcal{G} g ∈ G E P [ h ( X ) g ( Z ) ] = ⟨ T P h , g ⟩ L 2 ( P Z ) = ⟨ h , T P ∗ g ⟩ L 2 ( P X ) \mathbb{E}_P[h(X)g(Z)] = \langle T_P h,g\rangle_{L^2(P_Z)} = \langle h,T_P^*g\rangle_{L^2(P_X)} E P [ h ( X ) g ( Z )] = ⟨ T P h , g ⟩ L 2 ( P Z ) = ⟨ h , T P ∗ g ⟩ L 2 ( P X )
Let X n , X X_n,X X n , X n ∈ N n \in\mathbb{N} n ∈ N X n → p X X_n \xrightarrow{p} X X n p X X n X_n X n X X X X n ⇝ X X_n \rightsquigarrow X X n ⇝ X X n X_n X n X X X ( a n ) , ( b n ) (a_n),(b_n) ( a n ) , ( b n ) a n = O ( b n ) a_n = O(b_n) a n = O ( b n ) ∣ a n ∣ / ∣ b n ∣ |a_n|/|b_n| ∣ a n ∣/∣ b n ∣ a n = o ( b n ) a_n = o(b_n) a n = o ( b n ) ∣ a n ∣ / ∣ b n ∣ → 0 |a_n|/|b_n| \to0 ∣ a n ∣/∣ b n ∣ → 0 a n = ω ( b n ) a_n = \omega(b_n) a n = ω ( b n ) ∣ a n ∣ / ∣ b n ∣ → ∞ |a_n|/|b_n| \to\infty ∣ a n ∣/∣ b n ∣ → ∞ X n = O p ( b n ) X_n = O_p(b_n) X n = O p ( b n ) X n / b n X_n/b_n X n / b n X n = o p ( b n ) X_n = o_p(b_n) X n = o p ( b n ) X n / b n → p 0 X_n/b_n \xrightarrow{p} 0 X n / b n p 0
Definition and well-definedness of target functional. We let m : E W × H → R m:E_W \times\mathcal{H} \to\mathbb{R} m : E W × H → R m ~ : E W × G → R \widetilde{m}:E_W \times\mathcal{G} \to\mathbb{R} m : E W × G → R H \mathcal{H} H G \mathcal{G} G R \mathbb{R} R H \mathcal{H} H G \mathcal{G} G h ↦ E P [ m ( W ; h ) ] h \mapsto\mathbb{E}_P[m(W;h)] h ↦ E P [ m ( W ; h )] g ↦ E P [ m ~ ( W ; g ) ] g \mapsto\mathbb{E}_P[\widetilde{m}(W;g)] g ↦ E P [ m ( W ; g )] a P ∈ H a_P \in\mathcal{H} a P ∈ H r P ∈ G r_P \in\mathcal{G} r P ∈ G
H P : = arg min h ∈ H ∥ T P h − r P ∥ L 2 ( P Z ) 2 , (4) \mathcal{H}_P := \arg\min_{h\in\mathcal{H}} \lVert T_P h-r_P\rVert_{L^2(P_Z)}^2, \tag*{(4)} H P := arg h ∈ H min ∥ T P h − r P ∥ L 2 ( P Z ) 2 , (4) G P : = arg min g ∈ G ∥ T P ∗ g − a P ∥ L 2 ( P X ) 2 . (5) \mathcal{G}_P := \arg\min_{g\in\mathcal{G}} \lVert T_P^*g-a_P\rVert_{L^2(P_X)}^2. \tag*{(5)} G P := arg g ∈ G min ∥ T P ∗ g − a P ∥ L 2 ( P X ) 2 . (5) In this paper, we refer to the linear equation T P h = r P T_P h=r_P T P h = r P primary linear equation and T P ∗ g = a P T_P^*g=a_P T P ∗ g = a P secondary linear equation. We refer to an element of H P \mathcal{H}_P H P primary nuisance and an element of G P \mathcal{G}_P G P secondary nuisance .1 H P \mathcal{H}_P H P G P \mathcal{G}_P G P T P T_P T P T P ∗ T_P^* T P ∗ kernel ( T P ) ⊥ = range ( T P ∗ ) ‾ \operatorname{kernel}(T_P)^\perp= \overline{\operatorname{range}(T_P^*)} kernel ( T P ) ⊥ = range ( T P ∗ )
H = kernel ( T P ) ⊕ kernel ( T P ) ⊥ = kernel ( T P ) ⊕ range ( T P ∗ ) ‾ , \mathcal{H} = \operatorname{kernel}(T_P) \oplus\operatorname{kernel}(T_P)^\perp= \operatorname{kernel}(T_P) \oplus\overline{\operatorname{range}(T_P^*)}, H = kernel ( T P ) ⊕ kernel ( T P ) ⊥ = kernel ( T P ) ⊕ range ( T P ∗ ) , G = kernel ( T P ∗ ) ⊕ kernel ( T P ∗ ) ⊥ = kernel ( T P ∗ ) ⊕ range ( T P ) ‾ . \mathcal{G} = \operatorname{kernel}(T_P^*) \oplus\operatorname{kernel}(T_P^*)^\perp= \operatorname{kernel}(T_P^*) \oplus\overline{\operatorname{range}(T_P)}. G = kernel ( T P ∗ ) ⊕ kernel ( T P ∗ ) ⊥ = kernel ( T P ∗ ) ⊕ range ( T P ) . Accordingly, write
a P = a P , ∥ + a P , ⊥ , a P , ∥ ∈ kernel ( T P ) ⊥ = range ( T P ∗ ) ‾ , a P , ⊥ ∈ kernel ( T P ) , a_P = a_{P,\parallel} + a_{P,\perp}, \qquad a_{P,\parallel} \in\operatorname{kernel}(T_P)^\perp= \overline{\operatorname{range}(T_P^*)}, \qquad a_{P,\perp} \in\operatorname{kernel}(T_P), a P = a P , ∥ + a P , ⊥ , a P , ∥ ∈ kernel ( T P ) ⊥ = range ( T P ∗ ) , a P , ⊥ ∈ kernel ( T P ) , r P = r P , ∥ + r P , ⊥ , r P , ∥ ∈ kernel ( T P ∗ ) ⊥ = range ( T P ) ‾ , r P , ⊥ ∈ kernel ( T P ∗ ) . r_P = r_{P,\parallel} + r_{P,\perp}, \qquad r_{P,\parallel} \in\operatorname{kernel}(T_P^*)^\perp= \overline{\operatorname{range}(T_P)}, \qquad r_{P,\perp} \in\operatorname{kernel}(T_P^*). r P = r P , ∥ + r P , ⊥ , r P , ∥ ∈ kernel ( T P ∗ ) ⊥ = range ( T P ) , r P , ⊥ ∈ kernel ( T P ∗ ) . The orthogonal residuals r P , ⊥ r_{P,\perp} r P , ⊥ a P , ⊥ a_{P,\perp} a P , ⊥
Assumption 1. r P , ∥ ∈ range ( T P ) r_{P,\parallel} \in\operatorname{range}(T_P) r P , ∥ ∈ range ( T P ) a P , ∥ ∈ range ( T P ∗ ) a_{P,\parallel} \in\operatorname{range}(T_P^*) a P , ∥ ∈ range ( T P ∗ )
Lemma 1 (Nonemptiness of H P \mathcal{H}_P H P G P \mathcal{G}_P G P We have H P ≠ ∅ \mathcal{H}_P \ne\varnothing H P = ∅ r P , ∥ ∈ range ( T P ) r_{P,\parallel} \in\operatorname{range}(T_P) r P , ∥ ∈ range ( T P ) G P ≠ ∅ \mathcal{G}_P \ne\varnothing G P = ∅ a P , ∥ ∈ range ( T P ∗ ) a_{P,\parallel} \in\operatorname{range}(T_P^*) a P , ∥ ∈ range ( T P ∗ ) H P \mathcal{H}_P H P G P \mathcal{G}_P G P
Proof. Since T P h ∈ range ( T P ) ⊆ kernel ( T P ∗ ) ⊥ T_P h \in\operatorname{range}(T_P) \subseteq\operatorname{kernel}(T_P^*)^\perp T P h ∈ range ( T P ) ⊆ kernel ( T P ∗ ) ⊥ r P , ⊥ ∈ kernel ( T P ∗ ) r_{P,\perp} \in\operatorname{kernel}(T_P^*) r P , ⊥ ∈ kernel ( T P ∗ )
∥ T P h − r P ∥ L 2 ( P Z ) 2 = ∥ T P h − r P , ∥ ∥ L 2 ( P Z ) 2 + ∥ r P , ⊥ ∥ L 2 ( P Z ) 2 . \lVert T_P h-r_P\rVert_{L^2(P_Z)}^2 = \lVert T_P h-r_{P,\parallel}\rVert_{L^2(P_Z)}^2 + \lVert r_{P,\perp}\rVert_{L^2(P_Z)}^2. ∥ T P h − r P ∥ L 2 ( P Z ) 2 = ∥ T P h − r P , ∥ ∥ L 2 ( P Z ) 2 + ∥ r P , ⊥ ∥ L 2 ( P Z ) 2 . Therefore H P ≠ ∅ \mathcal{H}_P \ne\varnothing H P = ∅ r P , ∥ ∈ range ( T P ) r_{P,\parallel} \in\operatorname{range}(T_P) r P , ∥ ∈ range ( T P ) G P \mathcal{G}_P G P
Remark 1 (Existence of solutions vs. least squares minimizers). Assumption 1 asserts that the component of r P r_P r P kernel ( T P ∗ ) ⊥ \operatorname{kernel}(T_P^*)^\perp kernel ( T P ∗ ) ⊥ T P T_P T P a P a_P a P
r P ∈ kernel ( T P ∗ ) + range ( T P ) , a P ∈ range ( T P ∗ ) + kernel ( T P ) . r_P \in\operatorname{kernel}(T_P^*) + \operatorname{range}(T_P), \qquad a_P \in\operatorname{range}(T_P^*) + \operatorname{kernel}(T_P). r P ∈ kernel ( T P ∗ ) + range ( T P ) , a P ∈ range ( T P ∗ ) + kernel ( T P ) . This condition guarantees that the least squares solution sets H P \mathcal{H}_P H P G P \mathcal{G}_P G P H \mathcal{H} H G \mathcal{G} G T P h = r P T_P h = r_P T P h = r P
r P , ∥ ∈ range ( T P ) and r P , ⊥ = 0. r_{P,\parallel} \in\operatorname{range}(T_P) \qquad\text{and} \qquad r_{P,\perp} = 0. r P , ∥ ∈ range ( T P ) and r P , ⊥ = 0. Similarly, solvability of T P ∗ g = a P T_P^*g = a_P T P ∗ g = a P
a P , ∥ ∈ range ( T P ∗ ) and a P , ⊥ = 0. a_{P,\parallel} \in\operatorname{range}(T_P^*) \qquad\text{and} \qquad a_{P,\perp} = 0. a P , ∥ ∈ range ( T P ∗ ) and a P , ⊥ = 0. Thus, compared with the usual identification condition in [8 , 9 ] , [32 ] , which restricts a P a_P a P range ( T P ∗ ) \operatorname{range}(T_P^*) range ( T P ∗ ) a P a_P a P kernel ( T P ) \operatorname{kernel}(T_P) kernel ( T P ) r P r_P r P kernel ( T P ∗ ) \operatorname{kernel}(T_P^*) kernel ( T P ∗ ) T P h = r P T_P h = r_P T P h = r P T P ∗ g = a P T_P^*g = a_P T P ∗ g = a P [8 ] when we assume both r P , ⊥ = 0 r_{P,\perp} = 0 r P , ⊥ = 0 a P , ⊥ = 0 a_{P,\perp} = 0 a P , ⊥ = 0
We now show that E P [ h ( X ) g ( Z ) ] \mathbb{E}_P[h(X)g(Z)] E P [ h ( X ) g ( Z )] h ∈ H P h \in\mathcal{H}_P h ∈ H P g ∈ G P g \in\mathcal{G}_P g ∈ G P
Lemma 2 (Well-definedness of the target functional). Under Assumption 1 , let h , g h,g h , g H P \mathcal{H}_P H P G P \mathcal{G}_P G P H P = h + kernel ( T P ) \mathcal{H}_P=h+\operatorname{kernel}(T_P) H P = h + kernel ( T P ) G P = g + kernel ( T P ∗ ) \mathcal{G}_P=g+\operatorname{kernel}(T_P^*) G P = g + kernel ( T P ∗ ) h , h ′ ∈ H P h,h' \in\mathcal{H}_P h , h ′ ∈ H P g , g ′ ∈ G P g,g' \in\mathcal{G}_P g , g ′ ∈ G P
E P [ h ( X ) g ( Z ) ] = E P [ h ′ ( X ) g ′ ( Z ) ] . \mathbb{E}_P[h(X)g(Z)]=\mathbb{E}_P[h'(X)g'(Z)]. E P [ h ( X ) g ( Z )] = E P [ h ′ ( X ) g ′ ( Z )] . Proof. Note that h ∈ H P h \in\mathcal{H}_P h ∈ H P
T P ∗ T P h − T P ∗ r P = 0. T_P^*T_Ph-T_P^*r_P=0. T P ∗ T P h − T P ∗ r P = 0. We therefore have H P = h + kernel ( T P ∗ T P ) = h + kernel ( T P ) \mathcal{H}_P=h+\operatorname{kernel}(T_P^*T_P)=h+\operatorname{kernel}(T_P) H P = h + kernel ( T P ∗ T P ) = h + kernel ( T P ) G P \mathcal{G}_P G P h , h ′ ∈ H P h,h' \in\mathcal{H}_P h , h ′ ∈ H P g , g ′ ∈ G P g,g' \in\mathcal{G}_P g , g ′ ∈ G P
E P [ h ( X ) g ( Z ) ] = E P [ h ( X ) ( T P ∗ g ) ( X ) ] = E P [ h ( X ) ( T P ∗ g ′ ) ( X ) ] = E P [ h ( X ) g ′ ( Z ) ] = E P [ ( T P h ) ( Z ) g ′ ( Z ) ] = E P [ h ′ ( X ) g ′ ( Z ) ] . \begin{aligned}
\mathbb{E}_P[h(X)g(Z)] &= \mathbb{E}_P[h(X)(T_P^*g)(X)] = \mathbb{E}_P[h(X)(T_P^*g')(X)] \\
&= \mathbb{E}_P[h(X)g'(Z)] = \mathbb{E}_P[(T_Ph)(Z)g'(Z)] = \mathbb{E}_P[h'(X)g'(Z)].
\end{aligned} E P [ h ( X ) g ( Z )] = E P [ h ( X ) ( T P ∗ g ) ( X )] = E P [ h ( X ) ( T P ∗ g ′ ) ( X )] = E P [ h ( X ) g ′ ( Z )] = E P [( T P h ) ( Z ) g ′ ( Z )] = E P [ h ′ ( X ) g ′ ( Z )] . Under Assumption 1 and by Lemma 2, the following object is well-defined:
Ψ ( P ) : = E P [ g ( Z ) h ( X ) ] , h ∈ H P , g ∈ G P , (6) \Psi(P):=\mathbb{E}_P[g(Z)h(X)],\qquad h\in\mathcal{H}_P,\quad g\in\mathcal{G}_P, \tag*{(6)} Ψ ( P ) := E P [ g ( Z ) h ( X )] , h ∈ H P , g ∈ G P , (6) We refer to Ψ \Psi Ψ Ψ \Psi Ψ bilinear functional in the nuisances g g g h h h
Functional bias expansion
Minimum norm elements of H P , G P \mathcal{H}_P,\mathcal{G}_P H P , G P Under Assumption 1, the least-squares solution sets H P \mathcal{H}_P H P G P \mathcal{G}_P G P H P , G P \mathcal{H}_P,\mathcal{G}_P H P , G P
h P † = arg min h ∈ H P ∥ h ∥ L 2 ( P X ) , g P † = arg min g ∈ G P ∥ g ∥ L 2 ( P Z ) . h_P^\dagger=\underset{h\in\mathcal{H}_P}{\arg\min}\ \lVert h\rVert_{L^2(P_X)},\qquad
g_P^\dagger=\underset{g\in\mathcal{G}_P}{\arg\min}\ \lVert g\rVert_{L^2(P_Z)}. h P † = h ∈ H P arg min ∥ h ∥ L 2 ( P X ) , g P † = g ∈ G P arg min ∥ g ∥ L 2 ( P Z ) . where H P \mathcal{H}_P H P G P \mathcal{G}_P G P (4) and (5) . Minimum norm elements provide canonical choices in H P \mathcal{H}_P H P G P \mathcal{G}_P G P T P † T_P^\dagger T P † T P T_P T P dom ( T P † ) = range ( T P ) ⊕ kernel ( T P ∗ ) \operatorname{dom}(T_P^\dagger)=\operatorname{range}(T_P)\oplus\operatorname{kernel}(T_P^*) dom ( T P † ) = range ( T P ) ⊕ kernel ( T P ∗ ) [21 ] . By definition of H P \mathcal{H}_P H P r P ∈ dom ( T P † ) r_P\in\operatorname{dom}(T_P^\dagger) r P ∈ dom ( T P † ) h P † = T P † r P h_P^\dagger=T_P^\dagger r_P h P † = T P † r P T P ∣ kernel ( T P ) ⊥ : kernel ( T P ) ⊥ → range ( T P ) T_P|_{\operatorname{kernel}(T_P)^\perp}:\operatorname{kernel}(T_P)^\perp\to\operatorname{range}(T_P) T P ∣ kernel ( T P ) ⊥ : kernel ( T P ) ⊥ → range ( T P ) range ( T P ) \operatorname{range}(T_P) range ( T P ) T P † T_P^\dagger T P † kernel ( T P ∗ ) \operatorname{kernel}(T_P^*) kernel ( T P ∗ ) r P r_P r P
h P † = T P † r P = T P † r P , ∥ = ( T P ∣ kernel ( T P ) ⊥ ) − 1 r P , ∥ . h_P^\dagger=T_P^\dagger r_P=T_P^\dagger r_{P,\parallel}=\left(T_P|_{\operatorname{kernel}(T_P)^\perp}\right)^{-1}r_{P,\parallel}. h P † = T P † r P = T P † r P , ∥ = ( T P ∣ kernel ( T P ) ⊥ ) − 1 r P , ∥ . In addition, the pseudoinverse can also be interpreted as the Tikhonov regularized solution in the limit of vanishing regularization,
h P † = lim λ ↓ 0 h P λ , h P λ = arg min h ∈ H λ ∥ h ∥ L 2 ( P X ) 2 + ∥ T P h − r P ∥ L 2 ( P Z ) 2 . (7) h_P^\dagger=\lim_{\lambda\downarrow0}h_P^\lambda,\qquad
h_P^\lambda=\underset{h\in\mathcal{H}}{\arg\min}\ \lambda\lVert h\rVert_{L^2(P_X)}^2+\lVert T_Ph-r_P\rVert_{L^2(P_Z)}^2. \tag*{(7)} h P † = λ ↓ 0 lim h P λ , h P λ = h ∈ H arg min λ ∥ h ∥ L 2 ( P X ) 2 + ∥ T P h − r P ∥ L 2 ( P Z ) 2 . (7) Symmetrically, we have
g P † = arg min g ∈ G P ∥ g ∥ L 2 ( P Z ) = ( T P ∗ ) † a P = ( T P ∗ ) † a P , ∥ = ( T P ∗ ∣ kernel ( T P ∗ ) ⊥ ) − 1 a P , ∥ , g_P^\dagger=\underset{g\in\mathcal{G}_P}{\arg\min}\ \lVert g\rVert_{L^2(P_Z)}=(T_P^*)^\dagger a_P=(T_P^*)^\dagger a_{P,\parallel}=\left(T_P^*|_{\operatorname{kernel}(T_P^*)^\perp}\right)^{-1}a_{P,\parallel}, g P † = g ∈ G P arg min ∥ g ∥ L 2 ( P Z ) = ( T P ∗ ) † a P = ( T P ∗ ) † a P , ∥ = ( T P ∗ ∣ kernel ( T P ∗ ) ⊥ ) − 1 a P , ∥ , where the last equality holds because ( T P ∗ ) † (T_P^*)^\dagger ( T P ∗ ) † kernel ( T P ) \operatorname{kernel}(T_P) kernel ( T P ) a P a_P a P
T P h P † = r P , ∥ , T P ∗ g P † = a P , ∥ , Ψ ( P ) = E P [ h P † ( X ) g P † ( Z ) ] . T_P h_P^\dagger= r_{P,\parallel}, \qquad T_P^* g_P^\dagger= a_{P,\parallel}, \qquad\Psi(P) = \mathbb{E}_P[h_P^\dagger(X)g_P^\dagger(Z)]. T P h P † = r P , ∥ , T P ∗ g P † = a P , ∥ , Ψ ( P ) = E P [ h P † ( X ) g P † ( Z )] . For these fixed targets, define respectively
Ψ h P † ( g ) = E P [ h P † ( X ) g ( Z ) ] , Ψ h P † : L 2 ( P Z ) → R , \Psi_{h_P^\dagger}(g) = \mathbb{E}_P[h_P^\dagger(X)g(Z)], \qquad\Psi_{h_P^\dagger}: L^2(P_Z) \to\mathbb{R}, Ψ h P † ( g ) = E P [ h P † ( X ) g ( Z )] , Ψ h P † : L 2 ( P Z ) → R , Ψ g P † ( h ) = E P [ h ( X ) g P † ( Z ) ] , Ψ g P † : L 2 ( P X ) → R . \Psi_{g_P^\dagger}(h) = \mathbb{E}_P[h(X)g_P^\dagger(Z)], \qquad\Psi_{g_P^\dagger}: L^2(P_X) \to\mathbb{R}. Ψ g P † ( h ) = E P [ h ( X ) g P † ( Z )] , Ψ g P † : L 2 ( P X ) → R . Source condition. We will next impose an analogous assumption to the source condition in Bennett et al. [8 , 9 ] that controls the smoothness of our functionals and enables a functional bias expansion we can use for debiased estimation. However, unlike Bennett et al. [8 , 9 ] , consistent with not assuming that solutions to either the primary or secondary linear equations exist, we will impose source conditions only on the projected components and only as needed for the nonzero orthogonal residuals r P , ⊥ r_{P,\perp} r P , ⊥ a P , ⊥ a_{P,\perp} a P , ⊥ T P T_P T P T P ∗ T_P^* T P ∗ weak metrics , and L 2 L^2 L 2 strong metrics . This terminology is classical in NPIV and ill-posed inverse problem, as weak metrics are prediction norms, and unlike strong metrics, weak metric nuisance errors can be controlled without restrictive assumptions on measure of ill-posedness [13 , 18 ] .
Assumption 2 (Existence of weak metric Riesz representers for nuisance where solution does not exist). We assume both of the following statements hold
r P , ⊥ = 0 or a P , ∥ ∈ range ( T P ∗ T P ) r_{P,\perp} = 0 \quad\text{or} \quad a_{P,\parallel} \in\operatorname{range}(T_P^*T_P) r P , ⊥ = 0 or a P , ∥ ∈ range ( T P ∗ T P ) a P , ⊥ = 0 or r P , ∥ ∈ range ( T P T P ∗ ) . a_{P,\perp} = 0 \quad\text{or} \quad r_{P,\parallel} \in\operatorname{range}(T_PT_P^*). a P , ⊥ = 0 or r P , ∥ ∈ range ( T P T P ∗ ) . Remark 2 (Assumption 1 and Assumption 2 in the finite dimensional setting). If H P \mathcal{H}_P H P G P \mathcal{G}_P G P range ( T P ) = range ( T P ) \operatorname{range}(T_P) = \operatorname{range}(T_P) range ( T P ) = range ( T P ) range ( T P ∗ ) = range ( T P ∗ ) \operatorname{range}(T_P^*) = \operatorname{range}(T_P^*) range ( T P ∗ ) = range ( T P ∗ ) range ( T P T P ∗ ) = range ( T P ) \operatorname{range}(T_PT_P^*) = \operatorname{range}(T_P) range ( T P T P ∗ ) = range ( T P ) range ( T P ∗ T P ) = range ( T P ∗ ) \operatorname{range}(T_P^*T_P) = \operatorname{range}(T_P^*) range ( T P ∗ T P ) = range ( T P ∗ ) P P P
Remark 3 (Interpretation of Assumption 2). As explained in Remark 1, assuming r P , ⊥ = 0 r_{P,\perp} = 0 r P , ⊥ = 0 r P , ∥ ∈ range ( T P ) r_{P,\parallel} \in\operatorname{range}(T_P) r P , ∥ ∈ range ( T P ) T P h = r P T_Ph = r_P T P h = r P a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel} \in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P ) a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel} \in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P ) g P † g_P^\dagger g P † T P T_P T P r P , ⊥ r_{P,\perp} r P , ⊥ T P ∗ g = a P T_P^*g = a_P T P ∗ g = a P a P , ⊥ a_{P,\perp} a P , ⊥ T P ∗ T_P^* T P ∗ a P , ⊥ a_{P,\perp} a P , ⊥ h P † h_P^\dagger h P †
Note that Assumption 2 is stronger than Assumption 1 only on sides where the corresponding orthogonal residual is nonzero. Assumption 1 should be understood as the minimal assumption to ensure the existence of least-squares solutions. Assumption 2 additionally requires existence of solutions to Riesz regression [16 ] defined via the weak metric , on sides where the residual r P , ⊥ r_{P,\perp} r P , ⊥ a P , ⊥ a_{P,\perp} a P , ⊥
A P h = arg min α h ∈ H { 1 2 ∥ T P α h ∥ L 2 ( P Z ) 2 − ⟨ a P , ∥ , α h ⟩ L 2 ( P X ) } , (8) A_{P}^{h} = \underset{\alpha^{h} \in\mathcal{H}}{\operatorname{arg\,min}} \left\{ \frac{1}{2}\lVert T_{P}\alpha^{h}\rVert_{L^{2}(P_{Z})}^{2} - \langle a_{P,\parallel},\alpha^{h}\rangle_{L^{2}(P_{X})} \right\}, \tag*{(8)} A P h = α h ∈ H arg min { 2 1 ∥ T P α h ∥ L 2 ( P Z ) 2 − ⟨ a P , ∥ , α h ⟩ L 2 ( P X ) } , (8) A P g = arg min α g ∈ G { 1 2 ∥ T P ∗ α g ∥ L 2 ( P X ) 2 − ⟨ r P , ∥ , α g ⟩ L 2 ( P Z ) } . (9) A_{P}^{g} = \underset{\alpha^{g} \in\mathcal{G}}{\operatorname{arg\,min}} \left\{ \frac{1}{2}\lVert T_{P}^{*}\alpha^{g}\rVert_{L^{2}(P_{X})}^{2} - \langle r_{P,\parallel},\alpha^{g}\rangle_{L^{2}(P_{Z})} \right\}. \tag*{(9)} A P g = α g ∈ G arg min { 2 1 ∥ T P ∗ α g ∥ L 2 ( P X ) 2 − ⟨ r P , ∥ , α g ⟩ L 2 ( P Z ) } . (9) When these sets are nonempty, we define the minimum-norm elements
α P h , † = arg min α h ∈ A P h ∥ α h ∥ L 2 ( P X ) , α P g , † = arg min α g ∈ A P g ∥ α g ∥ L 2 ( P Z ) . \alpha_{P}^{h,\dagger} = \underset{\alpha^{h} \in A_{P}^{h}}{\operatorname{arg\,min}} \lVert\alpha^{h}\rVert_{L^{2}(P_{X})}, \qquad\alpha_{P}^{g,\dagger} = \underset{\alpha^{g} \in A_{P}^{g}}{\operatorname{arg\,min}} \lVert\alpha^{g}\rVert_{L^{2}(P_{Z})}. α P h , † = α h ∈ A P h arg min ∥ α h ∥ L 2 ( P X ) , α P g , † = α g ∈ A P g arg min ∥ α g ∥ L 2 ( P Z ) . Furthermore, the first-order conditions of these optimization problems yield
⟨ h , T P ∗ T P α P h ⟩ L 2 ( P X ) = ⟨ a P , ∥ , h ⟩ L 2 ( P X ) = E P [ h ( X ) g P † ( Z ) ] , ∀ h ∈ H , \langle h,T_{P}^{*}T_{P}\alpha_{P}^{h}\rangle_{L^{2}(P_{X})} = \langle a_{P,\parallel},h\rangle_{L^{2}(P_{X})} = \mathbb{E}_{P}[h(X)g_{P}^{\dagger}(Z)], \qquad\forall h \in\mathcal{H}, ⟨ h , T P ∗ T P α P h ⟩ L 2 ( P X ) = ⟨ a P , ∥ , h ⟩ L 2 ( P X ) = E P [ h ( X ) g P † ( Z )] , ∀ h ∈ H , ⟨ g , T P T P ∗ α P g ⟩ L 2 ( P Z ) = ⟨ r P , ∥ , g ⟩ L 2 ( P Z ) = E P [ g ( Z ) h P † ( X ) ] , ∀ g ∈ G . \langle g,T_{P}T_{P}^{*}\alpha_{P}^{g}\rangle_{L^{2}(P_{Z})} = \langle r_{P,\parallel},g\rangle_{L^{2}(P_{Z})} = \mathbb{E}_{P}[g(Z)h_{P}^{\dagger}(X)], \qquad\forall g \in\mathcal{G}. ⟨ g , T P T P ∗ α P g ⟩ L 2 ( P Z ) = ⟨ r P , ∥ , g ⟩ L 2 ( P Z ) = E P [ g ( Z ) h P † ( X )] , ∀ g ∈ G . We next establish the equivalence between the projected source conditions and the existence of solutions to the Riesz regression problems and how these solutions give rise to the minimum-norm least-squares solutions. Our argument adapts Theorem 2 and Lemma 3 of [9 ] .
Lemma 3. The following statements are equivalent:
a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel} \in\operatorname{range}(T_{P}^{*}T_{P}) a P , ∥ ∈ range ( T P ∗ T P )
A P h A_{P}^{h} A P h
g P † ∈ range ( T P ) g_{P}^{\dagger} \in\operatorname{range}(T_{P}) g P † ∈ range ( T P )
When these conditions hold, every α P h ∈ A P h \alpha_{P}^{h} \in A_{P}^{h} α P h ∈ A P h
T P ∗ T P α P h = a P , ∥ , T P α P h = g P † . (10) T_{P}^{*}T_{P}\alpha_{P}^{h} = a_{P,\parallel}, \qquad T_{P}\alpha_{P}^{h} = g_{P}^{\dagger}. \tag*{(10)} T P ∗ T P α P h = a P , ∥ , T P α P h = g P † . (10) Similarly, the following statements are equivalent:
r P , ∥ ∈ range ( T P T P ∗ ) r_{P,\parallel} \in\operatorname{range}(T_{P}T_{P}^{*}) r P , ∥ ∈ range ( T P T P ∗ )
A P g A_{P}^{g} A P g
h P † ∈ range ( T P ∗ ) h_{P}^{\dagger} \in\operatorname{range}(T_{P}^{*}) h P † ∈ range ( T P ∗ )
When these conditions hold, every α P g ∈ A P g \alpha_{P}^{g} \in A_{P}^{g} α P g ∈ A P g
T P T P ∗ α P g = r P , ∥ , T P ∗ α P g = h P † . T_{P}T_{P}^{*}\alpha_{P}^{g} = r_{P,\parallel}, \qquad T_{P}^{*}\alpha_{P}^{g} = h_{P}^{\dagger}. T P T P ∗ α P g = r P , ∥ , T P ∗ α P g = h P † . Remark 4 (Source condition). Let H 0 = kernel ( T P ) ⊥ \mathcal{H}_{0} = \operatorname{kernel}(T_{P})^{\perp} H 0 = kernel ( T P ) ⊥ H 0 \mathcal{H}_{0} H 0 T P T_{P} T P
⟨ u , v ⟩ T P : = ⟨ T P u , T P v ⟩ L 2 ( P Z ) . \langle u,v\rangle_{T_{P}} := \langle T_{P}u,T_{P}v\rangle_{L^{2}(P_{Z})}. ⟨ u , v ⟩ T P := ⟨ T P u , T P v ⟩ L 2 ( P Z ) . This defines an inner product on H 0 \mathcal{H}_0 H 0 H 0 \mathcal{H}_0 H 0 ∥ T P ( ⋅ ) ∥ L 2 ( P Z ) \|T_P(\cdot)\|_{L^2(P_Z)} ∥ T P ( ⋅ ) ∥ L 2 ( P Z ) range ( T P ) \operatorname{range}(T_P) range ( T P ) range ( T P ) \operatorname{range}(T_P) range ( T P )
To remedy this, we use the fact that the pair ( H 0 , ∥ T P ( ⋅ ) ∥ L 2 ( P Z ) ) (\mathcal{H}_0, \|T_P(\cdot)\|_{L^2(P_Z)}) ( H 0 , ∥ T P ( ⋅ ) ∥ L 2 ( P Z ) ) H ‾ 0 T P \overline{\mathcal{H}}_0^{T_P} H 0 T P ⟨ ⋅ , ⋅ ⟩ T P \langle\cdot,\cdot\rangle_{T_P} ⟨ ⋅ , ⋅ ⟩ T P H ‾ 0 T P \overline{\mathcal{H}}_0^{T_P} H 0 T P u ↦ T P u u \mapsto T_Pu u ↦ T P u H 0 \mathcal{H}_0 H 0 range ( T P ) \operatorname{range}(T_P) range ( T P )
H ‾ 0 T P ≅ range ( T P ) ‾ . \overline{\mathcal{H}}_0^{T_P} \cong\overline{\operatorname{range}(T_P)}. H 0 T P ≅ range ( T P ) . Consider the linear functional ℓ a : H 0 → R \ell_a:\mathcal{H}_0 \to\mathbb{R} ℓ a : H 0 → R
ℓ a ( u ) = ⟨ a P , ∥ , u ⟩ L 2 ( P X ) , u ∈ H 0 . \ell_a(u)=\langle a_{P,\parallel},u\rangle_{L^2(P_X)}, \qquad u\in\mathcal{H}_0. ℓ a ( u ) = ⟨ a P , ∥ , u ⟩ L 2 ( P X ) , u ∈ H 0 . Under Assumption 1, a P , ∥ ∈ range ( T P ∗ ) a_{P,\parallel}\in\operatorname{range}(T_P^*) a P , ∥ ∈ range ( T P ∗ ) g P † ∈ kernel ( T P ∗ ) ⊥ = range ( T P ) ‾ g_P^\dagger\in\operatorname{kernel}(T_P^*)^\perp=\overline{\operatorname{range}(T_P)} g P † ∈ kernel ( T P ∗ ) ⊥ = range ( T P ) T P ∗ g = a P , ∥ T_P^*g=a_{P,\parallel} T P ∗ g = a P , ∥
ℓ a ( u ) = ⟨ g P † , T P u ⟩ L 2 ( P Z ) . \ell_a(u)=\langle g_P^\dagger,T_Pu\rangle_{L^2(P_Z)}. ℓ a ( u ) = ⟨ g P † , T P u ⟩ L 2 ( P Z ) . so ℓ a \ell_a ℓ a ℓ a \ell_a ℓ a H ‾ 0 T P \overline{\mathcal{H}}_0^{T_P} H 0 T P ℓ a \ell_a ℓ a H ‾ 0 T P \overline{\mathcal{H}}_0^{T_P} H 0 T P ℓ a \ell_a ℓ a g P † g_P^\dagger g P † H ‾ 0 T P ≅ range ( T P ) ‾ \overline{\mathcal{H}}_0^{T_P}\cong\overline{\operatorname{range}(T_P)} H 0 T P ≅ range ( T P )
The condition a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel}\in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P ) ℓ a \ell_a ℓ a ( H ‾ 0 T P , ∥ T P ( ⋅ ) ∥ L 2 ( P Z ) ) (\overline{\mathcal{H}}_0^{T_P},\|\!T_P(\cdot)\!\|_{L^2(P_Z)}) ( H 0 T P , ∥ T P ( ⋅ ) ∥ L 2 ( P Z ) ) ( H 0 , ∥ ⋅ ∥ H ) (\mathcal{H}_0,\|\cdot\|_{\mathcal{H}}) ( H 0 , ∥ ⋅ ∥ H ) g P † ∈ range ( T P ) g_P^\dagger\in\operatorname{range}(T_P) g P † ∈ range ( T P ) α P h ∈ H 0 \alpha_P^h\in\mathcal{H}_0 α P h ∈ H 0
T P α P h = g P † . T_P\alpha_P^h=g_P^\dagger. T P α P h = g P † . Applying T P ∗ T_P^* T P ∗
T P ∗ T P α P h = a P , ∥ , T_P^*T_P\alpha_P^h=a_{P,\parallel}, T P ∗ T P α P h = a P , ∥ , that is, a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel}\in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P ) kernel ( T P ) ⊥ \operatorname{kernel}(T_P)^\perp kernel ( T P ) ⊥ A P h \mathcal{A}_P^h A P h r P , ∥ ∈ range ( T P T P ∗ ) r_{P,\parallel}\in\operatorname{range}(T_PT_P^*) r P , ∥ ∈ range ( T P T P ∗ ) T P T_P T P T P ∗ T_P^* T P ∗
Remark 4 shows that the minimum-norm element of A P h \mathcal{A}_P^h A P h ∥ T P ( ⋅ ) ∥ L 2 ( P Z ) \|T_P(\cdot)\|_{L^2(P_Z)} ∥ T P ( ⋅ ) ∥ L 2 ( P Z ) (8) and (9) as Riesz regressions.
Remark 5 (Comparison with [9 ] ). We compare Assumption 2 with the functional strong identification condition of [9 ] . That condition can also be understood as the existence of a solution to a Riesz regression problem. However, unlike that work, we require existence of solutions to Riesz regressions only for linear functionals defined by a P , ∥ , r P , ∥ a_{P,\parallel},r_{P,\parallel} a P , ∥ , r P , ∥ r P , ⊥ , a P , ⊥ r_{P,\perp},a_{P,\perp} r P , ⊥ , a P , ⊥ [9 ] requires existence of solutions to Riesz regression for linear functional defined by a P a_P a P
For a generic nuisance tuple
η = ( h , g , α h , α g , r ⊥ , a ⊥ ) , h , α h ∈ H , g , α g ∈ G , r ⊥ ∈ G , a ⊥ ∈ H , \eta= (h,g,\alpha^{h},\alpha^{g},r_{\perp},a_{\perp}), \qquad h,\alpha^{h} \in\mathcal{H}, \quad g,\alpha^{g} \in\mathcal{G}, \quad r_{\perp} \in\mathcal{G},a_{\perp} \in\mathcal{H}, η = ( h , g , α h , α g , r ⊥ , a ⊥ ) , h , α h ∈ H , g , α g ∈ G , r ⊥ ∈ G , a ⊥ ∈ H , define
χ ( W ; η ) : = m ( W ; h ) + m ~ ( W ; g ) − h ( X ) g ( Z ) + r ⊥ ( Z ) { α h ( X ) − g ( Z ) } + a ⊥ ( X ) { α g ( Z ) − h ( X ) } . (11) \chi(W;\eta) := m(W;h) + \widetilde{m}(W;g) - h(X)g(Z)
+ r_{\perp}(Z)\{\alpha^{h}(X)-g(Z)\} + a_{\perp}(X)\{\alpha^{g}(Z)-h(X)\}. \tag*{(11)} χ ( W ; η ) := m ( W ; h ) + m ( W ; g ) − h ( X ) g ( Z ) + r ⊥ ( Z ) { α h ( X ) − g ( Z )} + a ⊥ ( X ) { α g ( Z ) − h ( X )} . (11) Remark 6 (Special case where solutions to linear inverse problem(s) exist). The setting of [8 ] and [9 ] , where both linear inverse problems admit solutions, imposes both r P , ⊥ = 0 r_{P,\perp}=0 r P , ⊥ = 0 a P , ⊥ = 0 a_{P,\perp}=0 a P , ⊥ = 0 (11) trivially zero when η = η P \eta=\eta_{P} η = η P (11) the last two terms, plugging in just h ^ , g ^ \widehat{h},\widehat{g} h , g r P , ⊥ ≠ 0 r_{P,\perp}\ne0 r P , ⊥ = 0 a P , ⊥ ≠ 0 a_{P,\perp}\ne0 a P , ⊥ = 0 r P , ⊥ = 0 r_{P,\perp}=0 r P , ⊥ = 0 r ⊥ ≡ 0 r_{\perp}\equiv0 r ⊥ ≡ 0 α h \alpha^{h} α h a P , ⊥ = 0 a_{P,\perp}=0 a P , ⊥ = 0 a ⊥ ≡ 0 a_{\perp}\equiv0 a ⊥ ≡ 0 α g \alpha^{g} α g r P , ⊥ , a P , ⊥ , α h , α g r_{P,\perp},a_{P,\perp},\alpha^{h},\alpha^{g} r P , ⊥ , a P , ⊥ , α h , α g
When r P , ⊥ = 0 r_{P,\perp}=0 r P , ⊥ = 0 α h \alpha^{h} α h r P , ⊥ α h r_{P,\perp}\alpha^{h} r P , ⊥ α h a P , ⊥ = 0 a_{P,\perp}=0 a P , ⊥ = 0 α g \alpha^{g} α g η P \eta_{P} η P
η P : = ( h P † , g P † , α P h , † , α P g , † , r P , ⊥ , a P , ⊥ ) . (12) \eta_{P}:=(h_{P}^{\dagger},g_{P}^{\dagger},\alpha_{P}^{h,\dagger},\alpha_{P}^{g,\dagger},r_{P,\perp},a_{P,\perp}). \tag*{(12)} η P := ( h P † , g P † , α P h , † , α P g , † , r P , ⊥ , a P , ⊥ ) . (12) Our estimator will take the form of plugging in some η ^ \widehat{\eta} η χ \chi χ
Theorem 1 (Bias characterization). For any fixed η = ( h , g , α h , α g , r ⊥ , a ⊥ ) \eta=(h,g,\alpha^{h},\alpha^{g},r_{\perp},a_{\perp}) η = ( h , g , α h , α g , r ⊥ , a ⊥ )
E P [ χ ( W ; η ) ] − Ψ ( P ) = − ⟨ T P ( h − h P † ) , g − g P † ⟩ L 2 ( P Z ) + ⟨ T P α h − g , r ⊥ − r P , ⊥ ⟩ L 2 ( P Z ) + ⟨ T P ∗ α g − h , a ⊥ − a P , ⊥ ⟩ L 2 ( P X ) , (13) \mathbb{E}_{P}[\chi(W;\eta)]-\Psi(P)
= -\left\langle T_{P}(h-h_{P}^{\dagger}),g-g_{P}^{\dagger}\right\rangle_{L^{2}(P_{Z})}
+\left\langle T_{P}\alpha^{h}-g,r_{\perp}-r_{P,\perp}\right\rangle_{L^{2}(P_{Z})}
+\left\langle T_{P}^{*}\alpha^{g}-h,a_{\perp}-a_{P,\perp}\right\rangle_{L^{2}(P_{X})}, \tag*{(13)} E P [ χ ( W ; η )] − Ψ ( P ) = − ⟨ T P ( h − h P † ) , g − g P † ⟩ L 2 ( P Z ) + ⟨ T P α h − g , r ⊥ − r P , ⊥ ⟩ L 2 ( P Z ) + ⟨ T P ∗ α g − h , a ⊥ − a P , ⊥ ⟩ L 2 ( P X ) , (13) where the expectation on the left hand side is taken with respect to W W W
Proof of Theorem 1. By definition of the Riesz representers a P ∈ L 2 ( P X ) a_{P}\in L^{2}(P_{X}) a P ∈ L 2 ( P X ) r P ∈ L 2 ( P Z ) r_{P}\in L^{2}(P_{Z}) r P ∈ L 2 ( P Z )
E P [ m ( W ; h ) ] = ⟨ a P , h ⟩ L 2 ( P X ) \mathbb{E}_{P}[m(W;h)] = \langle a_{P},h\rangle_{L^{2}(P_{X})} E P [ m ( W ; h )] = ⟨ a P , h ⟩ L 2 ( P X ) E P [ m ~ ( W ; g ) ] = ⟨ r P , g ⟩ L 2 ( P Z ) . \mathbb{E}_{P}[\widetilde{m}(W;g)] = \langle r_{P},g\rangle_{L^{2}(P_{Z})}. E P [ m ( W ; g )] = ⟨ r P , g ⟩ L 2 ( P Z ) . We have
E P [ χ ( W ; η ) ] = ⟨ a P , h ⟩ L 2 ( P X ) + ⟨ r P , g ⟩ L 2 ( P Z ) − ⟨ T P h , g ⟩ L 2 ( P Z ) + ⟨ r ⊥ , T P α h − g ⟩ L 2 ( P Z ) + ⟨ a ⊥ , T P ∗ α g − h ⟩ L 2 ( P X ) . \mathbb{E}_{P}[\chi(W;\eta)]
= \langle a_{P},h\rangle_{L^{2}(P_{X})}+\langle r_{P},g\rangle_{L^{2}(P_{Z})}-\langle T_{P}h,g\rangle_{L^{2}(P_{Z})}+\langle r_{\perp},T_{P}\alpha^{h}-g\rangle_{L^{2}(P_{Z})}+\langle a_{\perp},T_{P}^{*}\alpha^{g}-h\rangle_{L^{2}(P_{X})}. E P [ χ ( W ; η )] = ⟨ a P , h ⟩ L 2 ( P X ) + ⟨ r P , g ⟩ L 2 ( P Z ) − ⟨ T P h , g ⟩ L 2 ( P Z ) + ⟨ r ⊥ , T P α h − g ⟩ L 2 ( P Z ) + ⟨ a ⊥ , T P ∗ α g − h ⟩ L 2 ( P X ) . We substitute in the above equation
a P = T P ∗ g P † + a P , ⊥ , r P = T P h P † + r P , ⊥ , a_{P}=T_{P}^{*}g_{P}^{\dagger}+a_{P,\perp}, \qquad r_{P}=T_{P}h_{P}^{\dagger}+r_{P,\perp}, a P = T P ∗ g P † + a P , ⊥ , r P = T P h P † + r P , ⊥ , and subtract Ψ ( P ) = ⟨ T P h P † , g P † ⟩ L 2 ( P Z ) \Psi(P) = \langle T_P h_P^\dagger, g_P^\dagger\rangle_{L^2(P_Z)} Ψ ( P ) = ⟨ T P h P † , g P † ⟩ L 2 ( P Z )
E P [ χ ( W ; η ) ] − Ψ ( P ) = ⟨ T P ∗ g P † + a P , ⊥ , h ⟩ L 2 ( P X ) + ⟨ T P h P † + r P , ⊥ , g ⟩ L 2 ( P Z ) − ⟨ T P h P † , g P † ⟩ L 2 ( P Z ) − ⟨ T P h , g ⟩ L 2 ( P Z ) + ⟨ r ⊥ , T P α h − g ⟩ L 2 ( P Z ) + ⟨ a ⊥ , T P ∗ α g − h ⟩ L 2 ( P X ) = − ⟨ T P ( h − h P † ) , g − g P † ⟩ L 2 ( P Z ) + ⟨ r ⊥ , T P α h − g ⟩ L 2 ( P Z ) + ⟨ r P , ⊥ , g ⟩ L 2 ( P Z ) + ⟨ a ⊥ , T P ∗ α g − h ⟩ L 2 ( P X ) + ⟨ a P , ⊥ , h ⟩ L 2 ( P X ) . \begin{aligned}
\mathbb{E}_P[\chi(W;\eta)]-\Psi(P)
={}&\langle T_P^*g_P^\dagger+a_{P,\perp},h\rangle_{L^2(P_X)}
+\langle T_P h_P^\dagger+r_{P,\perp},g\rangle_{L^2(P_Z)}
-\langle T_P h_P^\dagger,g_P^\dagger\rangle_{L^2(P_Z)}
-\langle T_P h,g\rangle_{L^2(P_Z)}\\
&+\langle r_\perp,T_P\alpha^h-g\rangle_{L^2(P_Z)}
+\langle a_\perp,T_P^*\alpha^g-h\rangle_{L^2(P_X)}\\
={}&-\langle T_P(h-h_P^\dagger),g-g_P^\dagger\rangle_{L^2(P_Z)}
+\langle r_\perp,T_P\alpha^h-g\rangle_{L^2(P_Z)}
+\langle r_{P,\perp},g\rangle_{L^2(P_Z)}
+\langle a_\perp,T_P^*\alpha^g-h\rangle_{L^2(P_X)}
+\langle a_{P,\perp},h\rangle_{L^2(P_X)}.
\end{aligned} E P [ χ ( W ; η )] − Ψ ( P ) = = ⟨ T P ∗ g P † + a P , ⊥ , h ⟩ L 2 ( P X ) + ⟨ T P h P † + r P , ⊥ , g ⟩ L 2 ( P Z ) − ⟨ T P h P † , g P † ⟩ L 2 ( P Z ) − ⟨ T P h , g ⟩ L 2 ( P Z ) + ⟨ r ⊥ , T P α h − g ⟩ L 2 ( P Z ) + ⟨ a ⊥ , T P ∗ α g − h ⟩ L 2 ( P X ) − ⟨ T P ( h − h P † ) , g − g P † ⟩ L 2 ( P Z ) + ⟨ r ⊥ , T P α h − g ⟩ L 2 ( P Z ) + ⟨ r P , ⊥ , g ⟩ L 2 ( P Z ) + ⟨ a ⊥ , T P ∗ α g − h ⟩ L 2 ( P X ) + ⟨ a P , ⊥ , h ⟩ L 2 ( P X ) . Since r P , ⊥ ∈ kernel ( T P ∗ ) r_{P,\perp}\in\operatorname{kernel}(T_P^*) r P , ⊥ ∈ kernel ( T P ∗ ) a P , ⊥ ∈ kernel ( T P ) a_{P,\perp}\in\operatorname{kernel}(T_P) a P , ⊥ ∈ kernel ( T P )
⟨ T P α h , r P , ⊥ ⟩ = 0 , ⟨ T P ∗ α g , a P , ⊥ ⟩ = 0. \langle T_P\alpha^h,r_{P,\perp}\rangle=0,\qquad\langle T_P^*\alpha^g,a_{P,\perp}\rangle=0. ⟨ T P α h , r P , ⊥ ⟩ = 0 , ⟨ T P ∗ α g , a P , ⊥ ⟩ = 0. Therefore
( † ) = ⟨ T P α h − g , r ⊥ − r P , ⊥ ⟩ + ⟨ T P ∗ α g − h , a ⊥ − a P , ⊥ ⟩ . (\dagger)=\langle T_P\alpha^h-g,r_\perp-r_{P,\perp}\rangle+\langle T_P^*\alpha^g-h,a_\perp-a_{P,\perp}\rangle. ( † ) = ⟨ T P α h − g , r ⊥ − r P , ⊥ ⟩ + ⟨ T P ∗ α g − h , a ⊥ − a P , ⊥ ⟩ . which concludes the proof.
Remark 7. We see from the right hand side of (13) , the α \alpha α α h \alpha^h α h α g \alpha^g α g T P α h T_P\alpha^h T P α h T P ∗ α g T_P^*\alpha^g T P ∗ α g α h \alpha^h α h α g \alpha^g α g α P h \alpha_P^h α P h α P g \alpha_P^g α P g α h \alpha^h α h g g g T P T_P T P (13) is that r P , ⊥ ∈ kernel ( T P ∗ ) r_{P,\perp}\in\operatorname{kernel}(T_P^*) r P , ⊥ ∈ kernel ( T P ∗ ) ⟨ T P α h , r P , ⊥ ⟩ L 2 ( P Z ) = 0 \langle T_P\alpha^h,r_{P,\perp}\rangle_{L^2(P_Z)}=0 ⟨ T P α h , r P , ⊥ ⟩ L 2 ( P Z ) = 0 g P † ∈ range ( T P ) g_P^\dagger\in\operatorname{range}(T_P) g P † ∈ range ( T P ) a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel}\in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P )
Remark 8 (Comparison to the setting where solutions to linear inverse problem(s) exist). Following [8 , 9 ] , where only the first term in the bias expansion appears, we can bound the first term by the product of strong and weak metrics, where we can weaken either the H \mathcal{H} H G \mathcal{G} G
∣ ⟨ T P ( h − h P † ) , g − g P † ⟩ L 2 ( P Z ) ∣ ≤ min { ∥ T P ( h − h P † ) ∥ L 2 ( P Z ) ∥ g − g P † ∥ L 2 ( P Z ) , ∥ h − h P † ∥ L 2 ( P X ) ∥ T P ∗ ( g − g P † ) ∥ L 2 ( P X ) } . \left|\langle T_P(h-h_P^\dagger),g-g_P^\dagger\rangle_{L^2(P_Z)}\right|
\le\min\left\{\|T_P(h-h_P^\dagger)\|_{L^2(P_Z)}\|g-g_P^\dagger\|_{L^2(P_Z)},\|h-h_P^\dagger\|_{L^2(P_X)}\|T_P^*(g-g_P^\dagger)\|_{L^2(P_X)}\right\}. ⟨ T P ( h − h P † ) , g − g P † ⟩ L 2 ( P Z ) ≤ min { ∥ T P ( h − h P † ) ∥ L 2 ( P Z ) ∥ g − g P † ∥ L 2 ( P Z ) , ∥ h − h P † ∥ L 2 ( P X ) ∥ T P ∗ ( g − g P † ) ∥ L 2 ( P X ) } . In addition to this term, unlike [8 , 9 ] , we also need to control two additional terms in (13) , due to the fact that we do not necessarily assume the orthogonal residuals r P , ⊥ r_{P,\perp} r P , ⊥ a P , ⊥ a_{P,\perp} a P , ⊥
Nuisance learners
In this section we develop learners for all of our nuisance functions. For simplicity we will assume we have separate independent datasets I 1 , I 2 , I 3 , I 4 \mathcal{I}_1,\mathcal{I}_2,\mathcal{I}_3,\mathcal{I}_4 I 1 , I 2 , I 3 , I 4 n n n I 1 \mathcal{I}_1 I 1 h P † h_P^\dagger h P † g P † g_P^\dagger g P † I 1 \mathcal{I}_1 I 1 α P h , † \alpha_P^{h,\dagger} α P h , † α P g , † \alpha_P^{g,\dagger} α P g , † I 2 \mathcal{I}_2 I 2 I 1 \mathcal{I}_1 I 1 r P , ⊥ r_{P,\perp} r P , ⊥ a P , ⊥ a_{P,\perp} a P , ⊥ I 3 \mathcal{I}_3 I 3 I 4 \mathcal{I}_4 I 4 n n n n n n
Background on empirical process minimization
Let F \mathcal{F} F f : W → R f:\mathcal{W}\to\mathbb{R} f : W → R F \mathcal{F} F
star ( F ) : = { t f : f ∈ F , t ∈ [ 0 , 1 ] } . \operatorname{star}(\mathcal{F}):=\{tf:f\in\mathcal{F},t\in[0,1]\}. star ( F ) := { t f : f ∈ F , t ∈ [ 0 , 1 ]} . We define the population localized Rademacher complexity [6 ] of the star hull of F \mathcal{F} F
R ( F , δ ) : = 1 2 n ∑ ϵ ∈ { − 1 , 1 } n E P [ sup γ ∈ [ 0 , 1 ] , f ∈ F : γ ∥ f ∥ ≤ δ ∣ 1 n ∑ i = 1 n ϵ i γ f ( W i ) ∣ ] , \mathcal{R}(\mathcal{F},\delta):=\frac{1}{2^n}\sum_{\epsilon\in\{-1,1\}^n}\mathbb{E}_{P}\left[\sup_{\gamma\in[0,1],f\in\mathcal{F}:\gamma\|f\|\leq\delta}\left|\frac{1}{n}\sum_{i=1}^{n}\epsilon_i\gamma f(W_i)\right|\right], R ( F , δ ) := 2 n 1 ϵ ∈ { − 1 , 1 } n ∑ E P [ γ ∈ [ 0 , 1 ] , f ∈ F : γ ∥ f ∥ ≤ δ sup n 1 i = 1 ∑ n ϵ i γ f ( W i ) ] , and define the critical radius of F \mathcal{F} F
R ( F , δ ) ≤ δ 2 . \mathcal{R}(\mathcal{F},\delta)\leq\delta^2. R ( F , δ ) ≤ δ 2 . We refer the reader to [36 ] , Chapter 14 for a detailed introduction to localized uniform concentration inequalities, and to [36 ] , Example 14.6, 14.7 for examples of critical radii of kernel classes. In our work, we use a variant for vector-valued function classes and Lipschitz loss functions derived in [22 ] . It is stated in Lemma 8 in the Appendix.
Minimax h h h g g g
We construct learners of the minimum-norm least-squares solutions h P † = arg min h ∈ H P ∥ h ∥ L 2 ( P X ) h_P^\dagger=\arg\min_{h\in\mathcal{H}_P}\|h\|_{L_2(P_X)} h P † = arg min h ∈ H P ∥ h ∥ L 2 ( P X ) g P † = arg min g ∈ G P ∥ g ∥ L 2 ( P Z ) g_P^\dagger=\arg\min_{g\in\mathcal{G}_P}\|g\|_{L_2(P_Z)} g P † = arg min g ∈ G P ∥ g ∥ L 2 ( P Z ) H P \mathcal{H}_P H P G P \mathcal{G}_P G P (4) and (5) . To do so, we show that the Tikhonov-regularized minimax learner of [8 ] remains a good learner of h P † h_P^\dagger h P † T P h = r P T_P h=r_P T P h = r P T P h P † ≠ r P T_P h_P^\dagger\ne r_P T P h P † = r P H P \mathcal{H}_P H P G P \mathcal{G}_P G P g P † g_P^\dagger g P † G P \mathcal{G}_P G P
Following [8 ] , given a hypothesis class H n ⊆ H \mathcal{H}_n\subseteq\mathcal{H} H n ⊆ H G n ⊆ G \mathcal{G}_n\subseteq\mathcal{G} G n ⊆ G
h ^ ( λ ) : = arg min h ∈ H n max g ∈ G n E n [ 2 { m ~ ( W ; g ) − h ( X ) g ( Z ) } − g ( Z ) 2 + λ h ( X ) 2 ] . (14) \widehat{h}(\lambda):=\arg\min_{h\in\mathcal{H}_n}\max_{g\in\mathcal{G}_n}\mathbb{E}_n\left[2\{\widetilde{m}(W;g)-h(X)g(Z)\}-g(Z)^2+\lambda h(X)^2\right]. \tag*{(14)} h ( λ ) := arg h ∈ H n min g ∈ G n max E n [ 2 { m ( W ; g ) − h ( X ) g ( Z )} − g ( Z ) 2 + λh ( X ) 2 ] . (14) The learner for g P † g_P^\dagger g P † ( H , X , T P , m ~ , r P ) (\mathcal{H},X,T_P,\widetilde{m},r_P) ( H , X , T P , m , r P ) ( G , Z , T P ∗ , m , a P ) (\mathcal{G},Z,T_P^*,m,a_P) ( G , Z , T P ∗ , m , a P )
For generality, in this section we impose a generic source condition. Note that, unlike [8 ] , we impose it on the projection of r P r_P r P range ( T P ) \operatorname{range}(T_P) range ( T P ) r P r_P r P range ( T P ) \operatorname{range}(T_P) range ( T P )
Assumption 3 (β h \beta_h β h β h ≥ 0 \beta_h\geq0 β h ≥ 0
r P , ∥ ∈ range ( ( T P T P ∗ ) ( β h + 1 ) / 2 ) . r_{P,\parallel}\in\operatorname{range}\left((T_PT_P^*)^{(\beta_h+1)/2}\right). r P , ∥ ∈ range ( ( T P T P ∗ ) ( β h + 1 ) /2 ) . For completeness, we also state the analogue of Assumption 3 for a P , ∥ a_{P,\parallel} a P , ∥
Assumption 4 (β g \beta_g β g β g ≥ 0 \beta_g \ge0 β g ≥ 0
a P , ∥ ∈ range ( ( T P ∗ T P ) ( β g + 1 ) / 2 ) . a_{P,\parallel} \in\operatorname{range}\left((T_P^*T_P)^{(\beta_g+1)/2}\right). a P , ∥ ∈ range ( ( T P ∗ T P ) ( β g + 1 ) /2 ) . Remark 9 (Relation of Assumption 3 and Assumption 2). An alert reader will notice that Assumption 3 with β h = 1 \beta_h = 1 β h = 1 need to estimate an element of A P g \mathcal{A}_P^g A P g A P g \mathcal{A}_P^g A P g a P , ⊥ a_{P,\perp} a P , ⊥ r P , ∥ ∈ range ( T P T P ∗ ) r_{P,\parallel} \in\operatorname{range}(T_PT_P^*) r P , ∥ ∈ range ( T P T P ∗ ) equivalent condition for A P g \mathcal{A}_P^g A P g not require an element of A P g \mathcal{A}_P^g A P g r P , ∥ r_{P,\parallel} r P , ∥ h P † h_P^\dagger h P †
h P † ∈ range ( ( T P ∗ T P ) β h / 2 ) , h_P^\dagger\in\operatorname{range}\left((T_P^*T_P)^{\beta_h/2}\right), h P † ∈ range ( ( T P ∗ T P ) β h /2 ) , as we show in Corollary 2. Such a source condition leads to faster convergence rates for the minimax h h h h P λ h_P^\lambda h P λ (7) . We will discuss further the role of the source condition in controlling bias in Remark 10.
The above bias argument is shown in Lemma 4 as follows.
Lemma 4 (Tikhonov regularization bias). Let h P λ h_P^\lambda h P λ (7) . Suppose Assumption 3 holds. Then, for a finite constant C P , β h C_{P,\beta_h} C P , β h
∥ h P λ − h P † ∥ L 2 ( P X ) 2 ≤ C P , β h λ min { β h , 2 } , \left\lVert h_P^\lambda- h_P^\dagger\right\rVert_{L^2(P_X)}^2 \le C_{P,\beta_h}\lambda^{\min\{\beta_h,2\}}, h P λ − h P † L 2 ( P X ) 2 ≤ C P , β h λ m i n { β h , 2 } , ∥ T P ( h P λ − h P † ) ∥ L 2 ( P Z ) 2 ≤ C P , β h λ min { β h + 1 , 2 } . \left\lVert T_P(h_P^\lambda- h_P^\dagger) \right\rVert_{L^2(P_Z)}^2 \le C_{P,\beta_h}\lambda^{\min\{\beta_h+1,2\}}. T P ( h P λ − h P † ) L 2 ( P Z ) 2 ≤ C P , β h λ m i n { β h + 1 , 2 } . Our proof of Lemma 4 adapts the proof [8 ] to the case where T P h P † ≠ r P T_Ph_P^\dagger\ne r_P T P h P † = r P T P T_P T P
Remark 10 (Saturation effect). A larger source condition exponent indicates that h P † h_P^\dagger h P † T P ∗ T P T_P^*T_P T P ∗ T P β h = 1 \beta_h = 1 β h = 1 β h = 2 \beta_h = 2 β h = 2 [10 , 21 ] . In general, Tikhonov regularization falls within a broader family of regularization strategies known as spectral algorithms [23 ] , and the saturation threshold is proportional to the qualification of a spectral algorithm. As an example of spectral algorithm, we can instead use iterated Tikhonov regularization as is done in [8 ] , whose qualification is proportional to the number of iteration steps. In the context of Remark 9, under Assumption 2 we already require β h ≥ 1 \beta_h \ge1 β h ≥ 1 a P , ⊥ a_{P,\perp} a P , ⊥ not obtain further convergence rates speed up in weak metric by taking β h > 1 \beta_h > 1 β h > 1
We next assume our hypothesis and critic classes are compatible in that the latter captures the directions of interest induced by the former. We also assume mean-squared-continuity.
Assumption 5 (Closedness). T P ( h P † − H n ) ⊆ G n T_P(h_P^\dagger-\mathcal{H}_n)\subseteq\mathcal{G}_n T P ( h P † − H n ) ⊆ G n
Assumption 6 (Mean-squared continuity). There exists a universal constant C > 0 C>0 C > 0 g ∈ G g\in\mathcal{G} g ∈ G h ∈ H h\in\mathcal{H} h ∈ H
E P [ m ~ ( W ; g ) 2 ] ≤ C ∥ g ∥ L 2 ( P Z ) 2 , E P [ m ( W ; h ) 2 ] ≤ C ∥ h ∥ L 2 ( P X ) 2 . \mathbb{E}_P[\widetilde{m}(W;g)^2]\leq C\lVert g\rVert_{L^2(P_Z)}^2,\qquad\mathbb{E}_P[m(W;h)^2]\leq C\lVert h\rVert_{L^2(P_X)}^2. E P [ m ( W ; g ) 2 ] ≤ C ∥ g ∥ L 2 ( P Z ) 2 , E P [ m ( W ; h ) 2 ] ≤ C ∥ h ∥ L 2 ( P X ) 2 . We are now prepared to state the equivalent of [8 ] but extended to the case where a solution to the linear equation of interest need not exist:
Theorem 2 (Convergence rates for h h h Fix λ ≤ 1 \lambda\leq1 λ ≤ 1 C > 0 C>0 C > 0 n n n m ~ ( W ; g ) \widetilde{m}(W;g) m ( W ; g ) g ( Z ) g(Z) g ( Z ) h ( X ) h(X) h ( X ) C C C g ∈ G n g\in\mathcal{G}_n g ∈ G n h ∈ H n h\in\mathcal{H}_n h ∈ H n h P † , h P λ ∈ H n h_P^\dagger,h_P^\lambda\in\mathcal{H}_n h P † , h P λ ∈ H n ζ ∈ ( 0 , 0.5 ) \zeta\in(0,0.5) ζ ∈ ( 0 , 0.5 )
δ h , n = Ω ( log log n − log ζ n ) \delta_{h,n}=\Omega\left(\sqrt{\frac{\log\log n-\log\zeta}{n}}\right) δ h , n = Ω ( n log log n − log ζ ) be an upper bound on the critical radii of H n ⋅ G n \mathcal{H}_n\cdot\mathcal{G}_n H n ⋅ G n { m ~ ( ⋅ ; g ) : g ∈ G n } \{\widetilde{m}(\cdot;g):g\in\mathcal{G}_n\} { m ( ⋅ ; g ) : g ∈ G n } H n \mathcal{H}_n H n G n \mathcal{G}_n G n 1 − ζ 1-\zeta 1 − ζ
∥ h ^ ( λ ) − h P † ∥ L 2 ( P X ) 2 = O ( δ h , n 2 λ + λ min { β h , 1 } ) , \lVert\widehat{h}(\lambda)-h_P^\dagger\rVert_{L^2(P_X)}^2=O\left(\frac{\delta_{h,n}^2}{\lambda}+\lambda^{\min\{\beta_h,1\}}\right), ∥ h ( λ ) − h P † ∥ L 2 ( P X ) 2 = O ( λ δ h , n 2 + λ m i n { β h , 1 } ) , and
∥ T P ( h ^ ( λ ) − h P † ) ∥ L 2 ( P Z ) 2 = O ( δ h , n 2 + λ min { β h + 1 , 2 } ) . \lVert T_P(\widehat{h}(\lambda)-h_P^\dagger)\rVert_{L^2(P_Z)}^2=O\left(\delta_{h,n}^2+\lambda^{\min\{\beta_h+1,2\}}\right). ∥ T P ( h ( λ ) − h P † ) ∥ L 2 ( P Z ) 2 = O ( δ h , n 2 + λ m i n { β h + 1 , 2 } ) . In particular, with λ h = δ h , n 2 / min { β h + 1 , 2 } \lambda_h=\delta_{h,n}^{2/\min\{\beta_h+1,2\}} λ h = δ h , n 2/ m i n { β h + 1 , 2 }
∥ h ^ ( λ h ) − h P † ∥ L 2 ( P X ) 2 = O ( δ h , n 2 min { β h , 1 } / min { β h + 1 , 2 } ) , \lVert\widehat{h}(\lambda_h)-h_P^\dagger\rVert_{L^2(P_X)}^2=O\left(\delta_{h,n}^{2\min\{\beta_h,1\}/\min\{\beta_h+1,2\}}\right), ∥ h ( λ h ) − h P † ∥ L 2 ( P X ) 2 = O ( δ h , n 2 m i n { β h , 1 } / m i n { β h + 1 , 2 } ) , ∥ T P ( h ^ ( λ h ) − h P † ) ∥ L 2 ( P Z ) 2 = O ( δ h , n 2 ) . \lVert T_P(\widehat{h}(\lambda_h)-h_P^\dagger)\rVert_{L^2(P_Z)}^2=O(\delta_{h,n}^2). ∥ T P ( h ( λ h ) − h P † ) ∥ L 2 ( P Z ) 2 = O ( δ h , n 2 ) . Minimax α \alpha α
From Remark 6, we know that if r P , ⊥ ≠ 0 r_{P,\perp}\ne0 r P , ⊥ = 0 A P h \mathcal{A}_P^h A P h a P , ⊥ ≠ 0 a_{P,\perp}\ne0 a P , ⊥ = 0 A P g \mathcal{A}_P^g A P g A P h \mathcal{A}_P^h A P h A P g \mathcal{A}_P^g A P g (8) and (9) . We only consider the former learning problem, all of our results apply symmetrically to the latter. We assume a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel}\in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P ) A P h ≠ ∅ \mathcal{A}_P^h\ne\varnothing A P h = ∅ r P , ⊥ ≠ 0 r_{P,\perp}\ne0 r P , ⊥ = 0 A P h \mathcal{A}_P^h A P h
α P h , † : = arg min α h ∈ A P h ∥ α h ∥ L 2 ( P X ) . \alpha_P^{h,\dagger}:=\underset{\alpha^h\in\mathcal{A}_P^h}{\operatorname{arg\,min}}\lVert\alpha^h\rVert_{L^2(P_X)}. α P h , † := α h ∈ A P h arg min ∥ α h ∥ L 2 ( P X ) . We define the following minimax learner for α P h , † \alpha_P^{h,\dagger} α P h , † H n ⊆ H \mathcal{H}_n\subseteq\mathcal{H} H n ⊆ H G n ⊆ G \mathcal{G}_n\subseteq\mathcal{G} G n ⊆ G λ α h > 0 \lambda_{\alpha^h}>0 λ α h > 0
α ^ h ( λ α h ) : = arg min α h ∈ H n max g ∈ G n E n [ 2 { g ^ ( λ g ) ( Z ) g ( Z ) − α h ( X ) g ( Z ) } − g ( Z ) 2 + λ α h α h ( X ) 2 ] . (15) \widehat{\alpha}^{h}(\lambda_{\alpha^h}):=\underset{\alpha^h\in\mathcal{H}_n}{\operatorname{arg\,min}}\ \underset{g\in\mathcal{G}_n}{\operatorname{max}}\ \mathbb{E}_n\left[2\{\widehat{g}(\lambda_g)(Z)g(Z)-\alpha^h(X)g(Z)\}-g(Z)^2+\lambda_{\alpha^h}\alpha^h(X)^2\right]. \tag*{(15)} α h ( λ α h ) := α h ∈ H n arg min g ∈ G n max E n [ 2 { g ( λ g ) ( Z ) g ( Z ) − α h ( X ) g ( Z )} − g ( Z ) 2 + λ α h α h ( X ) 2 ] . (15) where g ^ ( λ g ) \widehat{g}(\lambda_g) g ( λ g ) g P † g_P^\dagger g P †
Lemma 5 (Bias bounds). We assume a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel} \in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P ) λ > 0 \lambda> 0 λ > 0
α P , λ h : = arg min α ∈ H { ∥ T P α − g P † ∥ L 2 ( P Z ) 2 + λ ∥ α ∥ L 2 ( P X ) 2 } . \alpha^h_{P,\lambda} := \underset{\alpha\in\mathcal{H}}{\arg\min}\left\{\left\|T_P\alpha-g_P^{\dagger}\right\|_{L^2(P_Z)}^2+\lambda\|\alpha\|_{L^2(P_X)}^2\right\}. α P , λ h := α ∈ H arg min { T P α − g P † L 2 ( P Z ) 2 + λ ∥ α ∥ L 2 ( P X ) 2 } . We now take λ = λ n ↓ 0 \lambda=\lambda_n\downarrow0 λ = λ n ↓ 0 n → ∞ n\to\infty n → ∞
∥ T P ( α P , λ n h − α P h , † ) ∥ L 2 ( P Z ) 2 = o ( λ n ) \left\|T_P\left(\alpha^h_{P,\lambda_n}-\alpha_P^{h,\dagger}\right)\right\|_{L^2(P_Z)}^2=o(\lambda_n) T P ( α P , λ n h − α P h , † ) L 2 ( P Z ) 2 = o ( λ n ) ∥ α P , λ n h − α P h , † ∥ L 2 ( P X ) 2 = o ( 1 ) . \left\|\alpha^h_{P,\lambda_n}-\alpha_P^{h,\dagger}\right\|_{L^2(P_X)}^2=o(1). α P , λ n h − α P h , † L 2 ( P X ) 2 = o ( 1 ) . The proof of Lemma 5 leverages the spectral theorem for bounded self-adjoint operators [30 ] , which allows us to avoid assuming T P T_P T P o ( λ ) o(\lambda) o ( λ ) o ( 1 ) o(1) o ( 1 ) O ( λ ) O(\lambda) O ( λ ) O ( 1 ) O(1) O ( 1 ) α P h , † \alpha_P^{h,\dagger} α P h , †
Assumption 7 (Closedness). T P ( α P h , † − H n ) ⊆ G n T_P(\alpha_P^{h,\dagger}-\mathcal{H}_n)\subseteq\mathcal{G}_n T P ( α P h , † − H n ) ⊆ G n
Theorem 3 (Convergence rates for α \alpha α Let λ α h , n ≤ 1 \lambda_{\alpha^h,n}\leq1 λ α h , n ≤ 1 a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel}\in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P ) 0 ∈ G n 0\in\mathcal{G}_n 0 ∈ G n
α P h , † , α P , λ α h , n h ∈ H n . \alpha_P^{h,\dagger},\alpha^h_{P,\lambda_{\alpha^h,n}}\in\mathcal{H}_n. α P h , † , α P , λ α h , n h ∈ H n . Assume that there exists a constant C > 0 C>0 C > 0 n n n g ( Z ) g(Z) g ( Z ) α ( X ) \alpha(X) α ( X ) C C C g ∈ G n g\in\mathcal{G}_n g ∈ G n α ∈ H n \alpha\in\mathcal{H}_n α ∈ H n g ^ ( λ g ) \widehat{g}(\lambda_g) g ( λ g ) (15) , and conditionally on the first-stage sample suppose g ^ ( λ g ) ( Z ) \widehat{g}(\lambda_g)(Z) g ( λ g ) ( Z ) O ( 1 ) O(1) O ( 1 ) ζ ∈ ( 0 , 0.5 ) \zeta\in(0,0.5) ζ ∈ ( 0 , 0.5 )
δ α h , n = Ω ( log log n + log ( 1 / ζ ) n ) \delta_{\alpha^h,n}=\Omega\left(\sqrt{\frac{\log\log n+\log(1/\zeta)}{n}}\right) δ α h , n = Ω ( n log log n + log ( 1/ ζ ) ) be a common upper bound on the critical radii of
G n , H n ⋅ G n , H n − α P , λ α h , n h . \mathcal{G}_n,\qquad\mathcal{H}_n\cdot\mathcal{G}_n,\qquad\mathcal{H}_n-\alpha^h_{P,\lambda_{\alpha^h,n}}. G n , H n ⋅ G n , H n − α P , λ α h , n h . Then, conditionally on the first-stage sample, with probability at least 1 − ζ 1-\zeta 1 − ζ
∥ T P ( α ^ h − α P h , † ) ∥ L 2 ( P Z ) 2 ≤ C ( δ α h , n 2 + λ α h , n + ∥ g ^ ( λ g ) − g P † ∥ L 2 ( P Z ) 2 ) , \left\|T_P(\widehat{\alpha}^h-\alpha_P^{h,\dagger})\right\|_{L^2(P_Z)}^2\leq C\left(\delta_{\alpha^h,n}^2+\lambda_{\alpha^h,n}+\left\|\widehat{g}(\lambda_g)-g_P^{\dagger}\right\|_{L^2(P_Z)}^2\right), T P ( α h − α P h , † ) L 2 ( P Z ) 2 ≤ C ( δ α h , n 2 + λ α h , n + g ( λ g ) − g P † L 2 ( P Z ) 2 ) , for a constant C < ∞ C<\infty C < ∞ n n n ζ \zeta ζ λ α h , n ↓ 0 \lambda_{\alpha^h,n}\downarrow0 λ α h , n ↓ 0
δ α h , n 2 + ∥ g ^ ( λ g ) − g P † ∥ L 2 ( P Z ) 2 λ α h , n → p 0 , \frac{\delta_{\alpha^h,n}^2+\left\|\widehat{g}(\lambda_g)-g_P^{\dagger}\right\|_{L^2(P_Z)}^2}{\lambda_{\alpha^h,n}}\xrightarrow{p}0, λ α h , n δ α h , n 2 + g ( λ g ) − g P † L 2 ( P Z ) 2 p 0 , then
∥ α ^ h − α P h , † ∥ L 2 ( P X ) 2 → p 0. \left\|\widehat{\alpha}^h-\alpha_P^{h,\dagger}\right\|_{L^2(P_X)}^2\xrightarrow{p}0. α h − α P h , † L 2 ( P X ) 2 p 0. Our proof relies on showing that
λ α h , n ∥ α ^ h − α P h , † ∥ L 2 ( P X ) 2 + ∥ T P ( α ^ h − α P h , † ) ∥ L 2 ( P Z ) 2 \lambda_{\alpha^h,n}\left\|\widehat{\alpha}^h-\alpha_P^{h,\dagger}\right\|_{L^2(P_X)}^2+\left\|T_P(\widehat{\alpha}^h-\alpha_P^{h,\dagger})\right\|_{L^2(P_Z)}^2 λ α h , n α h − α P h , † L 2 ( P X ) 2 + T P ( α h − α P h , † ) L 2 ( P Z ) 2 can be bounded using δ α h , n \delta_{\alpha^h,n} δ α h , n α P h , † \alpha_P^{h,\dagger} α P h , †
r-learners
Finally, we learn the orthogonal residual
r P , ⊥ = r P − T P h P † = r P − r P , ∥ . r_{P,\perp}=r_P-T_P h_P^\dagger=r_P-r_{P,\parallel}. r P , ⊥ = r P − T P h P † = r P − r P , ∥ . We focus on r P , ⊥ r_{P,\perp} r P , ⊥ a P , ⊥ a_{P,\perp} a P , ⊥
( T P , G , Z , m ~ , r P , h P † ) ↔ ( T P ∗ , H , X , m , a P , g P † ) . \left(T_P,\mathcal{G},\mathcal{Z},\widetilde{m},r_P,h_P^\dagger\right)\leftrightarrow\left(T_P^*,\mathcal{H},\mathcal{X},m,a_P,g_P^\dagger\right). ( T P , G , Z , m , r P , h P † ) ↔ ( T P ∗ , H , X , m , a P , g P † ) . For a given first-stage learner h 1 h_1 h 1 r P − T P h 1 r_P-T_P h_1 r P − T P h 1 h 1 ∈ H h_1\in\mathcal{H} h 1 ∈ H G n r ⊆ G \mathcal{G}_n^r\subseteq\mathcal{G} G n r ⊆ G m ~ \widetilde{m} m (3) , we define
r ^ ⊥ ( h 1 ) ∈ arg max q ∈ G n r E n [ 2 { m ~ ( W ; q ) − h 1 ( X ) q ( Z ) } − q ( Z ) 2 ] . (16) \widehat{r}_{\perp}(h_1)\in\underset{q\in\mathcal{G}_n^r}{\operatorname{arg\,max}}\ \mathbb{E}_n\left[2\{\widetilde{m}(W;q)-h_1(X)q(Z)\}-q(Z)^2\right]. \tag*{(16)} r ⊥ ( h 1 ) ∈ q ∈ G n r arg max E n [ 2 { m ( W ; q ) − h 1 ( X ) q ( Z )} − q ( Z ) 2 ] . (16) To see why Equation (16) is the correct objective, we observe that
E [ 2 m ~ ( W ; q ) − 2 h 1 ( X ) q ( Z ) − q ( Z ) 2 ] = E [ 2 ( r P ( Z ) − ( T P h 1 ) ( Z ) ) q ( Z ) − q ( Z ) 2 ] . (17) \mathbb{E}\left[2\widetilde{m}(W;q)-2h_1(X)q(Z)-q(Z)^2\right]=\mathbb{E}\left[2(r_P(Z)-(T_P h_1)(Z))q(Z)-q(Z)^2\right]. \tag*{(17)} E [ 2 m ( W ; q ) − 2 h 1 ( X ) q ( Z ) − q ( Z ) 2 ] = E [ 2 ( r P ( Z ) − ( T P h 1 ) ( Z )) q ( Z ) − q ( Z ) 2 ] . (17) Differentiating the right hand side with respect to q q q q = r P − T P h 1 q=r_P-T_P h_1 q = r P − T P h 1
Theorem 4 (L 2 L^2 L 2 r ^ ⊥ ( h 1 ) \widehat{r}_{\perp}(h_1) r ⊥ ( h 1 ) h 1 h_1 h 1 h 1 ∈ H h_1\in\mathcal{H} h 1 ∈ H
r P − T P h 1 ∈ G n r , r_P-T_P h_1\in\mathcal{G}_n^r, r P − T P h 1 ∈ G n r , suppose that Assumption 6 holds, and that there exists a constant C > 0 C>0 C > 0 n n n m ~ ( W ; q ) \widetilde{m}(W;q) m ( W ; q ) q ( Z ) q(Z) q ( Z ) h 1 ( X ) h_1(X) h 1 ( X ) ( r P − T P h 1 ) ( Z ) (r_P-T_P h_1)(Z) ( r P − T P h 1 ) ( Z ) C C C q ∈ G n r q\in\mathcal{G}_n^r q ∈ G n r ζ ∈ ( 0 , 0.5 ) \zeta\in(0,0.5) ζ ∈ ( 0 , 0.5 )
δ r ⊥ , n = Ω ( log log n − log ζ n ) \delta_{r_\perp,n}=\Omega\left(\sqrt{\frac{\log\log n-\log\zeta}{n}}\right) δ r ⊥ , n = Ω ( n log log n − log ζ ) be an upper bound on the critical radii of G n r \mathcal{G}_n^r G n r { m ~ ( ⋅ ; q ) : q ∈ G n r } \{\widetilde{m}(\cdot;q):q\in\mathcal{G}_n^r\} { m ( ⋅ ; q ) : q ∈ G n r } 1 − ζ 1-\zeta 1 − ζ
∥ r ^ ⊥ ( h 1 ) − ( r P − T P h 1 ) ∥ L 2 ( P Z ) 2 = O ( δ r ⊥ , n 2 ) . \left\|\widehat{r}_{\perp}(h_1)-(r_P-T_P h_1)\right\|_{L^2(P_Z)}^2=O\left(\delta_{r_\perp,n}^2\right). ∥ r ⊥ ( h 1 ) − ( r P − T P h 1 ) ∥ L 2 ( P Z ) 2 = O ( δ r ⊥ , n 2 ) . The motivation for the realizability assumption is clear from Equation (17) .
Corollary 1 (Convergence rates for r r r h ^ ( λ h ) \widehat{h}(\lambda_h) h ( λ h ) (16) . We also suppose that the assumptions of Theorem 2 hold for h ^ ( λ h ) \widehat{h}(\lambda_h) h ( λ h ) h 1 = h ^ ( λ h ) h_1=\widehat{h}(\lambda_h) h 1 = h ( λ h )
∥ r ^ ⊥ ( h ^ ( λ h ) ) − r P , ⊥ ∥ L 2 ( P Z ) 2 = O p ( δ r ⊥ , n 2 + δ h , n 2 + λ h min { β h + 1 , 2 } ) . \left\|\widehat{r}_{\perp}(\widehat{h}(\lambda_h))-r_{P,\perp}\right\|_{L^2(P_Z)}^2=O_p\left(\delta_{r_\perp,n}^2+\delta_{h,n}^2+\lambda_h^{\min\{\beta_h+1,2\}}\right). r ⊥ ( h ( λ h )) − r P , ⊥ L 2 ( P Z ) 2 = O p ( δ r ⊥ , n 2 + δ h , n 2 + λ h m i n { β h + 1 , 2 } ) . In particular, if λ h = δ h , n 2 / min { β h + 1 , 2 } \lambda_h=\delta_{h,n}^{2/\min\{\beta_h+1,2\}} λ h = δ h , n 2/ m i n { β h + 1 , 2 } 1 − ζ 1-\zeta 1 − ζ
∥ r ^ ⊥ ( h ^ ( λ h ) ) − r P , ⊥ ∥ L 2 ( P Z ) 2 = O ( δ r ⊥ , n 2 + δ h , n 2 ) . \left\|\widehat{r}_{\perp}(\widehat{h}(\lambda_h))-r_{P,\perp}\right\|_{L^2(P_Z)}^2=O\left(\delta_{r_\perp,n}^2+\delta_{h,n}^2\right). r ⊥ ( h ( λ h )) − r P , ⊥ L 2 ( P Z ) 2 = O ( δ r ⊥ , n 2 + δ h , n 2 ) . Remark 11 (Saddle point vs second max step). Equation (16) is exactly the inner max of the minimax learner Equation (14) for h ^ ( λ ) \hat{h}(\lambda) h ^ ( λ ) h P † h^{\dagger}_{P} h P † r P , ⊥ r_{P,\perp} r P , ⊥ h 1 h_{1} h 1 h ^ ( λ h ) \hat{h}(\lambda_{h}) h ^ ( λ h ) range ( T P ) \operatorname{range}(T_{P}) range ( T P ) G n \mathcal{G}_{n} G n G n r \mathcal{G}^{r}_{n} G n r kernel ( T P ) \operatorname{kernel}(T_{P}) kernel ( T P )
Debiased inference on the target functional
We now present our main results on the inference for Ψ ( P ) \Psi(P) Ψ ( P )
We view the set of nuisance functions as a tuple and refer to a particular nuisance function as a coordinate of the tuple. As explained at the start of Section 4, we use three independent datasets I 1 , I 2 , I 3 \mathcal{I}_{1},\mathcal{I}_{2},\mathcal{I}_{3} I 1 , I 2 , I 3 I 4 \mathcal{I}_{4} I 4
Ψ ^ : = 1 n ∑ i ∈ I 4 χ ( W i ; η ^ ) . (18) \widehat{\Psi}:=\frac{1}{n}\sum_{i\in\mathcal{I}_{4}}\chi(W_{i};\widehat{\eta}). \tag*{(18)} Ψ := n 1 i ∈ I 4 ∑ χ ( W i ; η ) . (18) where the function χ \chi χ (11) , η ^ = ( h ^ , g ^ , α ^ h , α ^ g , r ^ ⊥ , a ^ ⊥ ) \widehat{\eta}=(\widehat{h},\widehat{g},\widehat{\alpha}^{h},\widehat{\alpha}^{g},\widehat{r}_{\perp},\widehat{a}_{\perp}) η = ( h , g , α h , α g , r ⊥ , a ⊥ ) I 1 , I 2 , I 3 \mathcal{I}_{1},\mathcal{I}_{2},\mathcal{I}_{3} I 1 , I 2 , I 3 Ψ ^ \widehat{\Psi} Ψ
σ ^ 2 : = 1 n ∑ i ∈ I 4 ( χ ( W i ; η ^ ) − Ψ ^ ) 2 . (19) \widehat{\sigma}^{2}:=\frac{1}{n}\sum_{i\in\mathcal{I}_{4}}\left(\chi(W_{i};\widehat{\eta})-\widehat{\Psi}\right)^{2}. \tag*{(19)} σ 2 := n 1 i ∈ I 4 ∑ ( χ ( W i ; η ) − Ψ ) 2 . (19) The extension to cross-fitting [14 , 15 ] is immediate: we split the data and permute the roles, averaging the estimator Ψ ^ \widehat{\Psi} Ψ η ^ \widehat{\eta} η n \sqrt{n} n
As in Section 3, we use the following tuple as the fixed target of our nuisance learners,
η P † : = ( h P † , g P † , α P h , † , α P g , † , r P , ⊥ , a P , ⊥ ) . \eta_{P}^{\dagger}:=(h_{P}^{\dagger},g_{P}^{\dagger},\alpha_{P}^{h,\dagger},\alpha_{P}^{g,\dagger},r_{P,\perp},a_{P,\perp}). η P † := ( h P † , g P † , α P h , † , α P g , † , r P , ⊥ , a P , ⊥ ) . where the first four coordinates are minimum-norm elements of their respective sets. We use the convention that the α h \alpha^{h} α h r P , ⊥ = 0 r_{P,\perp}=0 r P , ⊥ = 0 α g \alpha^{g} α g a P , ⊥ = 0 a_{P,\perp}=0 a P , ⊥ = 0 inactive " coordinate. Otherwise, we refer to it as an "active " coordinate. The function w ↦ χ ( w ; η P † ) w\mapsto\chi(w;\eta_{P}^{\dagger}) w ↦ χ ( w ; η P † ) influence function candidate . By Theorem 1, E P [ χ ( W ; η P † ) ] = Ψ ( P ) \mathbb{E}_{P}[\chi(W;\eta_{P}^{\dagger})]=\Psi(P) E P [ χ ( W ; η P † )] = Ψ ( P )
χ P ( w ) : = χ ( w ; η P † ) , φ P ( w ) : = χ P ( w ) − Ψ ( P ) , σ P 2 : = E P [ φ P ( W ) 2 ] . (20) \chi_{P}(w):=\chi(w;\eta_{P}^{\dagger}),\qquad\varphi_{P}(w):=\chi_{P}(w)-\Psi(P),\qquad\sigma_{P}^{2}:=\mathbb{E}_{P}[\varphi_{P}(W)^{2}]. \tag*{(20)} χ P ( w ) := χ ( w ; η P † ) , φ P ( w ) := χ P ( w ) − Ψ ( P ) , σ P 2 := E P [ φ P ( W ) 2 ] . (20) We emphasize that despite parametrization invariance shown in Lemma 2, the candidate σ P 2 \sigma_{P}^{2} σ P 2 minimum-norm elements of the least squares solution sets. In general, choosing arbitrary elements of the least squares solution sets may lead to a larger asymptotic variance candidate.
We define the strong and weak metric errors for the nuisance functions
e h s = ∥ h ^ − h P † ∥ L 2 ( P X ) , e h w = ∥ T P ( h ^ − h P † ) ∥ L 2 ( P Z ) , e g s = ∥ g ^ − g P † ∥ L 2 ( P Z ) , e g w = ∥ T P ∗ ( g ^ − g P † ) ∥ L 2 ( P X ) , e α h s = ∥ α ^ h − α P h , † ∥ L 2 ( P X ) , e α h w = ∥ T P ( α ^ h − α P h , † ) ∥ L 2 ( P Z ) , e α g s = ∥ α ^ g − α P g , † ∥ L 2 ( P Z ) , e α g w = ∥ T P ∗ ( α ^ g − α P g , † ) ∥ L 2 ( P X ) , e r ⊥ s = ∥ r ^ ⊥ − r P , ⊥ ∥ L 2 ( P Z ) , e a ⊥ s = ∥ a ^ ⊥ − a P , ⊥ ∥ L 2 ( P X ) . \begin{aligned}
e_h^s &= \lVert\widehat{h} - h_P^\dagger\rVert_{L^2(P_X)}, & e_h^w &= \lVert T_P(\widehat{h} - h_P^\dagger) \rVert_{L^2(P_Z)},\\
e_g^s &= \lVert\widehat{g} - g_P^\dagger\rVert_{L^2(P_Z)}, & e_g^w &= \lVert T_P^*(\widehat{g} - g_P^\dagger) \rVert_{L^2(P_X)},\\
e_{\alpha_h}^s &= \lVert\widehat{\alpha}^h - \alpha_P^{h,\dagger} \rVert_{L^2(P_X)}, & e_{\alpha_h}^w &= \lVert T_P(\widehat{\alpha}^h - \alpha_P^{h,\dagger}) \rVert_{L^2(P_Z)},\\
e_{\alpha_g}^s &= \lVert\widehat{\alpha}^g - \alpha_P^{g,\dagger} \rVert_{L^2(P_Z)}, & e_{\alpha_g}^w &= \lVert T_P^*(\widehat{\alpha}^g - \alpha_P^{g,\dagger}) \rVert_{L^2(P_X)},\\
e_{r_\perp}^s &= \lVert\widehat{r}_\perp- r_{P,\perp} \rVert_{L^2(P_Z)},\\
e_{a_\perp}^s &= \lVert\widehat{a}_\perp- a_{P,\perp} \rVert_{L^2(P_X)}.
\end{aligned} e h s e g s e α h s e α g s e r ⊥ s e a ⊥ s = ∥ h − h P † ∥ L 2 ( P X ) , = ∥ g − g P † ∥ L 2 ( P Z ) , = ∥ α h − α P h , † ∥ L 2 ( P X ) , = ∥ α g − α P g , † ∥ L 2 ( P Z ) , = ∥ r ⊥ − r P , ⊥ ∥ L 2 ( P Z ) , = ∥ a ⊥ − a P , ⊥ ∥ L 2 ( P X ) . e h w e g w e α h w e α g w = ∥ T P ( h − h P † ) ∥ L 2 ( P Z ) , = ∥ T P ∗ ( g − g P † ) ∥ L 2 ( P X ) , = ∥ T P ( α h − α P h , † ) ∥ L 2 ( P Z ) , = ∥ T P ∗ ( α g − α P g , † ) ∥ L 2 ( P X ) , We only require consistency for e α h s e_{\alpha_h}^s e α h s e α g s e_{\alpha_g}^s e α g s r P , ⊥ = 0 r_{P,\perp}=0 r P , ⊥ = 0 r ^ ⊥ ≡ 0 \widehat{r}_\perp\equiv0 r ⊥ ≡ 0 e α h s = e α h w = e r ⊥ s = 0 e_{\alpha_h}^s=e_{\alpha_h}^w=e_{r_\perp}^s=0 e α h s = e α h w = e r ⊥ s = 0 a P , ⊥ = 0 a_{P,\perp}=0 a P , ⊥ = 0 a ^ ⊥ ≡ 0 \widehat{a}_\perp\equiv0 a ⊥ ≡ 0 e α g s = e α g w = e a ⊥ s = 0 e_{\alpha_g}^s=e_{\alpha_g}^w=e_{a_\perp}^s=0 e α g s = e α g w = e a ⊥ s = 0
Condition 1 (Requirements on convergence rates for nuisance functions). The nuisance errors are consistent with respect to the strong metric,
e h s + e g s + e α h s + e α g s + e r ⊥ s + e a ⊥ s = o p ( 1 ) (21) e_h^s + e_g^s + e_{\alpha_h}^s + e_{\alpha_g}^s + e_{r_\perp}^s + e_{a_\perp}^s = o_p(1) \tag*{(21)} e h s + e g s + e α h s + e α g s + e r ⊥ s + e a ⊥ s = o p ( 1 ) (21) Since T P T_P T P T P ∗ T_P^* T P ∗
n min { e g w e h s , e g s e h w } = o p ( 1 ) , (22) \sqrt{n}\min\left\{e_g^w e_h^s, e_g^s e_h^w\right\}=o_p(1), \tag*{(22)} n min { e g w e h s , e g s e h w } = o p ( 1 ) , (22) n [ ( e α h w + e g s ) e r ⊥ s + ( e α g w + e h s ) e a ⊥ s ] = o p ( 1 ) . (23) \sqrt{n}\left[\left(e_{\alpha_h}^w+e_g^s\right)e_{r_\perp}^s+\left(e_{\alpha_g}^w+e_h^s\right)e_{a_\perp}^s\right]=o_p(1). \tag*{(23)} n [ ( e α h w + e g s ) e r ⊥ s + ( e α g w + e h s ) e a ⊥ s ] = o p ( 1 ) . (23) We refer to (22) and (23) as product rate conditions . Note (22) is derived from Remark 8. We also observe that (23) contains plug-in L 2 L^2 L 2 e h s e_h^s e h s e g s e_g^s e g s e α h w e_{\alpha_h}^w e α h w e α g w e_{\alpha_g}^w e α g w α \alpha α
Theorem 5 (Asymptotic linearity). Suppose Assumptions 1, 2 and 6 and Condition 1 hold, and 0 < σ P 2 < ∞ 0<\sigma_P^2<\infty 0 < σ P 2 < ∞ C > 0 C>0 C > 0
max { ∥ h ^ ∥ ∞ 2 , ∥ h P † ∥ ∞ 2 , ∥ g P † ∥ ∞ 2 , ∥ α P h , † ∥ ∞ 2 , ∥ α P g , † ∥ ∞ 2 , ∥ a ^ ⊥ ∥ ∞ 2 , ∥ r ^ ⊥ ∥ ∞ 2 } ≤ C , \max\left\{\lVert\widehat{h}\rVert_\infty^2,\lVert h_P^\dagger\rVert_\infty^2,\lVert g_P^\dagger\rVert_\infty^2,\lVert\alpha_P^{h,\dagger}\rVert_\infty^2,\lVert\alpha_P^{g,\dagger}\rVert_\infty^2,\lVert\widehat{a}_\perp\rVert_\infty^2,\lVert\widehat{r}_\perp\rVert_\infty^2\right\}\le C, max { ∥ h ∥ ∞ 2 , ∥ h P † ∥ ∞ 2 , ∥ g P † ∥ ∞ 2 , ∥ α P h , † ∥ ∞ 2 , ∥ α P g , † ∥ ∞ 2 , ∥ a ⊥ ∥ ∞ 2 , ∥ r ⊥ ∥ ∞ 2 } ≤ C , with probability tending to 1. We drop the assumptions on α P h , † \alpha_P^{h,\dagger} α P h , † α P g , † \alpha_P^{g,\dagger} α P g , †
n ( Ψ ^ − Ψ ( P ) ) = 1 n ∑ i = 1 n φ P ( W i ) + o p ( 1 ) ⇝ N ( 0 , σ P 2 ) . (24) \sqrt{n}\left(\widehat{\Psi}-\Psi(P)\right)=\frac{1}{\sqrt{n}}\sum_{i=1}^{n}\varphi_P(W_i)+o_p(1)\leadsto N(0,\sigma_P^2). \tag*{(24)} n ( Ψ − Ψ ( P ) ) = n 1 i = 1 ∑ n φ P ( W i ) + o p ( 1 ) ⇝ N ( 0 , σ P 2 ) . (24) Moreover, σ ^ \widehat{\sigma} σ σ P \sigma_P σ P σ ^ → p σ P \widehat{\sigma}\to_p\sigma_P σ → p σ P σ ^ \widehat{\sigma} σ (19) .
Sufficient conditions for nuisance learners
We next record sufficient conditions under which the nuisance learners from Section 4 satisfy Condition 1. Let β h \beta_h β h β g \beta_g β g
κ h : = min { β h , 1 } min { β h + 1 , 2 } , κ g : = min { β g , 1 } min { β g + 1 , 2 } . \kappa_h := \frac{\min\{\beta_h,1\}}{\min\{\beta_h+1,2\}}, \qquad\kappa_g := \frac{\min\{\beta_g,1\}}{\min\{\beta_g+1,2\}}. κ h := min { β h + 1 , 2 } min { β h , 1 } , κ g := min { β g + 1 , 2 } min { β g , 1 } . Recall that under Assumption 2, β h ≥ 1 \beta_h \ge1 β h ≥ 1 a P , ⊥ ≠ 0 a_{P,\perp} \ne0 a P , ⊥ = 0 β g ≥ 1 \beta_g \ge1 β g ≥ 1 r P , ⊥ ≠ 0 r_{P,\perp} \ne0 r P , ⊥ = 0 δ h , n \delta_{h,n} δ h , n δ g , n \delta_{g,n} δ g , n δ α h , n \delta_{\alpha_h,n} δ α h , n δ α g , n \delta_{\alpha_g,n} δ α g , n δ r ⊥ , n \delta_{r_\perp,n} δ r ⊥ , n δ a ⊥ , n \delta_{a_\perp,n} δ a ⊥ , n h ^ \hat{h} h ^ g ^ \hat{g} g ^ α ^ h \hat{\alpha}^h α ^ h α ^ g \hat{\alpha}^g α ^ g r ^ ⊥ \hat{r}_\perp r ^ ⊥ a ^ ⊥ \hat{a}_\perp a ^ ⊥
Theorem 2 and its symmetric analogue give
e h w = O p ( δ h , n ) , e h s = O p ( δ h , n κ h ) , e g w = O p ( δ g , n ) , e g s = O p ( δ g , n κ g ) . e_h^w = O_p(\delta_{h,n}), \qquad e_h^s = O_p(\delta_{h,n}^{\kappa_h}), \qquad e_g^w = O_p(\delta_{g,n}), \qquad e_g^s = O_p(\delta_{g,n}^{\kappa_g}). e h w = O p ( δ h , n ) , e h s = O p ( δ h , n κ h ) , e g w = O p ( δ g , n ) , e g s = O p ( δ g , n κ g ) . For "active" coordinates of the α \alpha α α h \alpha^h α h r P , ⊥ ≠ 0 r_{P,\perp} \ne0 r P , ⊥ = 0 α g \alpha^g α g a P , ⊥ ≠ 0 a_{P,\perp} \ne0 a P , ⊥ = 0
e α h w = O p ( { δ α h , n 2 + λ α h , n + δ g , n 2 κ g } 1 / 2 ) , e_{\alpha_h}^w = O_p\left(\left\{\delta_{\alpha_h,n}^2+\lambda_{\alpha_h,n}+\delta_{g,n}^{2\kappa_g}\right\}^{1/2}\right), e α h w = O p ( { δ α h , n 2 + λ α h , n + δ g , n 2 κ g } 1/2 ) , e α g w = O p ( { δ α g , n 2 + λ α g , n + δ h , n 2 κ h } 1 / 2 ) . e_{\alpha_g}^w = O_p\left(\left\{\delta_{\alpha_g,n}^2+\lambda_{\alpha_g,n}+\delta_{h,n}^{2\kappa_h}\right\}^{1/2}\right). e α g w = O p ( { δ α g , n 2 + λ α g , n + δ h , n 2 κ h } 1/2 ) . Moreover, e α h s = o p ( 1 ) e_{\alpha_h}^s=o_p(1) e α h s = o p ( 1 )
λ α h , n ↓ 0 , δ α h , n 2 + δ g , n 2 κ g λ α h , n → 0 , (25) \lambda_{\alpha_h,n}\downarrow0,\qquad\frac{\delta_{\alpha_h,n}^2+\delta_{g,n}^{2\kappa_g}}{\lambda_{\alpha_h,n}}\to0, \tag*{(25)} λ α h , n ↓ 0 , λ α h , n δ α h , n 2 + δ g , n 2 κ g → 0 , (25) and, symmetrically, e α g s = o p ( 1 ) e_{\alpha_g}^s=o_p(1) e α g s = o p ( 1 )
λ α g , n ↓ 0 , δ α g , n 2 + δ h , n 2 κ h λ α g , n → 0. (26) \lambda_{\alpha_g,n}\downarrow0,\qquad\frac{\delta_{\alpha_g,n}^2+\delta_{h,n}^{2\kappa_h}}{\lambda_{\alpha_g,n}}\to0. \tag*{(26)} λ α g , n ↓ 0 , λ α g , n δ α g , n 2 + δ h , n 2 κ h → 0. (26) Note that (25) and (26) are exactly bias-variance trade-off conditions. The λ \lambda λ
e r ⊥ s = O p ( δ r ⊥ , n + δ h , n ) , e a ⊥ s = O p ( δ a ⊥ , n + δ g , n ) . e_{r_\perp}^s = O_p(\delta_{r_\perp,n}+\delta_{h,n}), \qquad e_{a_\perp}^s = O_p(\delta_{a_\perp,n}+\delta_{g,n}). e r ⊥ s = O p ( δ r ⊥ , n + δ h , n ) , e a ⊥ s = O p ( δ a ⊥ , n + δ g , n ) . Thus (21) follows if (25) and (26) hold, and δ h , n \delta_{h,n} δ h , n δ g , n \delta_{g,n} δ g , n δ r ⊥ , n \delta_{r_\perp,n} δ r ⊥ , n δ a ⊥ , n \delta_{a_\perp,n} δ a ⊥ , n o ( 1 ) o(1) o ( 1 ) (22) is implied by
n min { δ g , n δ h , n κ h , δ g , n κ g δ h , n } → 0. \sqrt{n}\min\left\{\delta_{g,n}\delta_{h,n}^{\kappa_h},\delta_{g,n}^{\kappa_g}\delta_{h,n}\right\}\to0. n min { δ g , n δ h , n κ h , δ g , n κ g δ h , n } → 0. For the second product condition (23) , define
q α h , n 2 : = { δ α h , n 2 + λ α h , n + δ g , n 2 κ g , r P , ⊥ ≠ 0 , 0 , r P , ⊥ = 0 , q_{\alpha_h,n}^2 :=
\begin{cases}
\delta_{\alpha_h,n}^2+\lambda_{\alpha_h,n}+\delta_{g,n}^{2\kappa_g}, & r_{P,\perp}\ne0,\\
0, & r_{P,\perp}=0,
\end{cases} q α h , n 2 := { δ α h , n 2 + λ α h , n + δ g , n 2 κ g , 0 , r P , ⊥ = 0 , r P , ⊥ = 0 , q α g , n 2 : = { δ α g , n 2 + λ α g , n + δ h , n 2 κ h , a P , ⊥ ≠ 0 , 0 , a P , ⊥ = 0. q_{\alpha_g,n}^2 :=
\begin{cases}
\delta_{\alpha_g,n}^2+\lambda_{\alpha_g,n}+\delta_{h,n}^{2\kappa_h}, & a_{P,\perp}\ne0,\\
0, & a_{P,\perp}=0.
\end{cases} q α g , n 2 := { δ α g , n 2 + λ α g , n + δ h , n 2 κ h , 0 , a P , ⊥ = 0 , a P , ⊥ = 0. Then (23) is implied by
n [ q α h , n ( δ r ⊥ , n + δ h , n ) + q α g , n ( δ a ⊥ , n + δ g , n ) ] → 0. \sqrt{n}\left[q_{\alpha_h,n}(\delta_{r_\perp,n}+\delta_{h,n})+q_{\alpha_g,n}(\delta_{a_\perp,n}+\delta_{g,n})\right]\to0. n [ q α h , n ( δ r ⊥ , n + δ h , n ) + q α g , n ( δ a ⊥ , n + δ g , n ) ] → 0. Simple sufficient condition. Consider the case where we do not a priori assume either residual r P , ⊥ , a P , ⊥ r_{P,\perp},a_{P,\perp} r P , ⊥ , a P , ⊥ δ n \delta_n δ n δ h , n , δ g , n , δ α h , n , δ α g , n , δ r ⊥ , n \delta_{h,n},\delta_{g,n},\delta_{\alpha h,n},\delta_{\alpha g,n},\delta_{r_\perp,n} δ h , n , δ g , n , δ α h , n , δ α g , n , δ r ⊥ , n δ a ⊥ , n \delta_{a_\perp,n} δ a ⊥ , n κ : = min { κ h , κ g } \kappa:= \min\{\kappa_h,\kappa_g\} κ := min { κ h , κ g }
n δ n 1 + κ → 0 , \sqrt{n}\,\delta_n^{1+\kappa} \to0, n δ n 1 + κ → 0 , then we have that Condition 1 holds by choosing λ α h , n = λ α g , n = λ n = o ( 1 ) \lambda_{\alpha h,n}=\lambda_{\alpha g,n}=\lambda_n=o(1) λ α h , n = λ α g , n = λ n = o ( 1 ) λ n = ω ( δ n 2 κ ) \lambda_n=\omega(\delta_n^{2\kappa}) λ n = ω ( δ n 2 κ ) λ n = o ( n − 1 δ n − 2 ) \lambda_n=o(n^{-1}\delta_n^{-2}) λ n = o ( n − 1 δ n − 2 ) β h , β g ≥ 1 \beta_h,\beta_g \ge1 β h , β g ≥ 1 κ h = κ g = 1 / 2 \kappa_h=\kappa_g=1/2 κ h = κ g = 1/2 δ n = o ( n − 1 / 3 ) \delta_n=o(n^{-1/3}) δ n = o ( n − 1/3 )
Conclusions
In low-dimensional linear IV analysis, two-stage least squares (2SLS) does not require there to be an exact solution β \beta β E [ Z X ⊤ ] β = E [ Z Y ] \mathbb{E}[ZX^\top]\beta=\mathbb{E}[ZY] E [ Z X ⊤ ] β = E [ Z Y ] [3 , 7 , 31 , 34 ] . When there is no exact solution, it just targets the least-squares solution E [ Z X ⊤ ] † E [ Z Y ] \mathbb{E}[ZX^\top]^\dagger\mathbb{E}[ZY] E [ Z X ⊤ ] † E [ Z Y ] [4 , 5 ] , while inference requires adjustment to covariance estimates [24 , 28 ] . When moving to NPIV, we have to estimate nonparametric functions to solve infinite-dimensional linear equations and to debias functionals to ensure valid inference on finite-dimensional parameters [1 , 8 , 9 , 32 ] . Along the way, much of the NPIV-functionals literature has imposed existence of solutions, whether to T P h = r P T_P h=r_P T P h = r P T P ∗ g = a P T_P^*g=a_P T P ∗ g = a P [24 , 28 ] , except here this also changes the debiased estimator itself.
Acknowledgements
The authors would like to thank Ben Deaner for helpful discussions.
Proofs for functional bias
Proof of Lemma 3. We prove the statement for α h \alpha^{h} α h α g \alpha^{g} α g T P T_{P} T P T P ∗ T_{P}^{*} T P ∗ a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel} \in\operatorname{range}(T_{P}^{*}T_{P}) a P , ∥ ∈ range ( T P ∗ T P ) A P h ≠ ∅ \mathcal{A}_{P}^{h} \ne\varnothing A P h = ∅ (8) is convex and Fréchet differentiable, so α ∈ H \alpha\in\mathcal{H} α ∈ H
⟨ T P ∗ T P α − a P , ∥ , v ⟩ L 2 ( P X ) = 0 , ∀ v ∈ H . \left\langle T_{P}^{*}T_{P}\alpha-a_{P,\parallel},v\right\rangle_{L^{2}(P_{X})}=0,\qquad\forall v\in\mathcal{H}. ⟨ T P ∗ T P α − a P , ∥ , v ⟩ L 2 ( P X ) = 0 , ∀ v ∈ H . Thus A P h \mathcal{A}_{P}^{h} A P h a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel} \in\operatorname{range}(T_{P}^{*}T_{P}) a P , ∥ ∈ range ( T P ∗ T P )
T P ∗ T P α P h = a P , ∥ . T_{P}^{*}T_{P}\alpha_{P}^{h}=a_{P,\parallel}. T P ∗ T P α P h = a P , ∥ . Since T P ∗ g P † = a P , ∥ T_{P}^{*}g_{P}^{\dagger}=a_{P,\parallel} T P ∗ g P † = a P , ∥
T P ∗ ( T P α P h − g P † ) = 0. T_{P}^{*}\left(T_{P}\alpha_{P}^{h}-g_{P}^{\dagger}\right)=0. T P ∗ ( T P α P h − g P † ) = 0. Also T P α P h ∈ range ( T P ) T_{P}\alpha_{P}^{h}\in\operatorname{range}(T_{P}) T P α P h ∈ range ( T P ) g P † ∈ kernel ( T P ∗ ) ⊥ = range ( T P ) ‾ g_{P}^{\dagger}\in\operatorname{kernel}(T_{P}^{*})^{\perp}=\overline{\operatorname{range}(T_{P})} g P † ∈ kernel ( T P ∗ ) ⊥ = range ( T P )
T P α P h − g P † ∈ kernel ( T P ∗ ) ∩ kernel ( T P ∗ ) ⊥ = { 0 } . T_{P}\alpha_{P}^{h}-g_{P}^{\dagger}\in\operatorname{kernel}(T_{P}^{*})\cap\operatorname{kernel}(T_{P}^{*})^{\perp}=\{0\}. T P α P h − g P † ∈ kernel ( T P ∗ ) ∩ kernel ( T P ∗ ) ⊥ = { 0 } . This proves that either of the first two statements implies g P † ∈ range ( T P ) g_{P}^{\dagger}\in\operatorname{range}(T_{P}) g P † ∈ range ( T P ) g P † = T P α g_{P}^{\dagger}=T_{P}\alpha g P † = T P α α ∈ H \alpha\in\mathcal{H} α ∈ H
a P , ∥ = T P ∗ g P † = T P ∗ T P α , a_{P,\parallel}=T_{P}^{*}g_{P}^{\dagger}=T_{P}^{*}T_{P}\alpha, a P , ∥ = T P ∗ g P † = T P ∗ T P α , so a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel}\in\operatorname{range}(T_{P}^{*}T_{P}) a P , ∥ ∈ range ( T P ∗ T P ) α h \alpha^{h} α h α P h ∈ A P h \alpha_{P}^{h}\in\mathcal{A}_{P}^{h} α P h ∈ A P h
Proofs for nuisance learners
Mathematical background
We follow [30 ] to present the following generalization of spectral theorem for self-adjoint compact bounded operators. It will enable us to analyse the setting with non-compact T : H → G T:\mathcal{H}\to\mathcal{G} T : H → G [18 ] and NPIV with observed covariates [25 , 33 ] .
Definition 1 (Projection-valued measure). Let H H H P ( H ) P(H) P ( H ) L ( H ) \mathcal{L}(H) L ( H ) Π \Pi Π H H H
B ( R ) → P ( H ) \mathcal{B}(\mathbb{R})\to P(H) B ( R ) → P ( H ) from the σ \sigma σ B ( R ) \mathcal{B}(\mathbb{R}) B ( R ) R \mathbb{R} R
Π ∅ = 0 \Pi_{\varnothing}=0 Π ∅ = 0 Π R = Id \Pi_{\mathbb{R}}=\operatorname{Id} Π R = Id
For some constant R > 0 R>0 R > 0 Π [ − R , R ] = Id \Pi_{[-R,R]}=\operatorname{Id} Π [ − R , R ] = Id
If A n A_n A n n ≥ 1 n \ge1 n ≥ 1 R \mathbb{R} R
A = ⋃ n ≥ 1 A n ∈ B ( R ) , A = \bigcup_{n \ge1} A_n \in\mathcal{B}(\mathbb{R}), A = n ≥ 1 ⋃ A n ∈ B ( R ) , and then we have Π A = ∑ n ≥ 1 Π A n \Pi_A = \sum_{n \ge1} \Pi_{A_n} Π A = ∑ n ≥ 1 Π A n H H H
We state the following theorem in terms of projection-valued measures:
Theorem 6 (Spectral theorem for bounded self-adjoint operators). Let H H H T = T ∗ T = T^* T = T ∗ H H H σ ( T ) \sigma(T) σ ( T )
σ ( T ) : = { λ ∈ R ∣ λ Id − T is not invertible. } \sigma(T) := \{\lambda\in\mathbb{R} \mid\lambda\operatorname{Id} - T \text{ is not invertible.}\} σ ( T ) := { λ ∈ R ∣ λ Id − T is not invertible. } There exists a unique projection-valued measure Π T \Pi_T Π T
T = ∫ σ ( T ) λ d Π T ( λ ) . T = \int_{\sigma(T)} \lambda\, \mathrm{d}\Pi_T(\lambda). T = ∫ σ ( T ) λ d Π T ( λ ) . If f f f σ ( T ) \sigma(T) σ ( T )
f ( T ) = ∫ σ ( T ) f ( λ ) d Π T ( λ ) . f(T) = \int_{\sigma(T)} f(\lambda) \mathrm{d}\Pi_T(\lambda). f ( T ) = ∫ σ ( T ) f ( λ ) d Π T ( λ ) . Lemma 6 (Positive square root). Let H H H A = A ∗ ∈ L ( H ) A = A^* \in\mathcal{L}(H) A = A ∗ ∈ L ( H ) A 1 / 2 ∈ L ( H ) A^{1/2} \in\mathcal{L}(H) A 1/2 ∈ L ( H ) ( A 1 / 2 ) 2 = A (A^{1/2})^2 = A ( A 1/2 ) 2 = A
Proof. Since A A A σ ( A ) ⊂ [ 0 , ∞ ) \sigma(A) \subset[0,\infty) σ ( A ) ⊂ [ 0 , ∞ )
A 1 / 2 : = ∫ σ ( A ) λ d Π A ( λ ) . A^{1/2} := \int_{\sigma(A)} \sqrt{\lambda} \, \mathrm{d}\Pi_A(\lambda). A 1/2 := ∫ σ ( A ) λ d Π A ( λ ) . Then A 1 / 2 A^{1/2} A 1/2
( A 1 / 2 ) 2 = ∫ σ ( A ) λ d Π A ( λ ) = A . (A^{1/2})^2 = \int_{\sigma(A)} \lambda\, \mathrm{d}\Pi_A(\lambda) = A. ( A 1/2 ) 2 = ∫ σ ( A ) λ d Π A ( λ ) = A . If B B B A A A B = B ∗ B = B^* B = B ∗ σ ( B ) ⊂ [ 0 , ∞ ) \sigma(B) \subset[0,\infty) σ ( B ) ⊂ [ 0 , ∞ )
A 1 / 2 = ( B 2 ) 1 / 2 = ( λ ↦ λ 2 ) ( B ) = B A^{1/2} = (B^2)^{1/2} = \left(\lambda\mapsto\sqrt{\lambda^2}\right)(B) = B A 1/2 = ( B 2 ) 1/2 = ( λ ↦ λ 2 ) ( B ) = B by the continuous functional calculus. Hence the positive square root is unique. □ \square □
Theorem 7 (Polar decomposition). Let H 1 , H 2 H_1, H_2 H 1 , H 2 T : H 1 → H 2 T : H_1 \to H_2 T : H 1 → H 2 U ∈ L ( H 1 , H 2 ) U \in\mathcal{L}(H_1,H_2) U ∈ L ( H 1 , H 2 )
T = U ∣ T ∣ , ∣ T ∣ : = ( T ∗ T ) 1 / 2 , kernel ( U ) = kernel ( T ) . T = U|T|, \qquad|T| := (T^*T)^{1/2}, \qquad\operatorname{kernel}(U) = \operatorname{kernel}(T). T = U ∣ T ∣ , ∣ T ∣ := ( T ∗ T ) 1/2 , kernel ( U ) = kernel ( T ) . The initial space of U U U range ( ∣ T ∣ ) = kernel ( T ) ⊥ \operatorname{range}(|T|) = \operatorname{kernel}(T)^\perp range ( ∣ T ∣ ) = kernel ( T ) ⊥ range ( T ) \operatorname{range}(T) range ( T ) Proof. By Lemma 6, ∣ T ∣ = ( T ∗ T ) 1 / 2 |T|=(T^{*}T)^{1/2} ∣ T ∣ = ( T ∗ T ) 1/2 x ∈ H 1 x\in H_1 x ∈ H 1
∥ ∣ T ∣ x ∥ 2 = ⟨ ∣ T ∣ 2 x , x ⟩ = ⟨ T ∗ T x , x ⟩ = ∥ T x ∥ 2 \lVert|T|x\rVert^2=\langle|T|^2x,x\rangle=\langle T^{*}Tx,x\rangle=\lVert Tx\rVert^2 ∥ ∣ T ∣ x ∥ 2 = ⟨ ∣ T ∣ 2 x , x ⟩ = ⟨ T ∗ T x , x ⟩ = ∥ T x ∥ 2 Hence kernel ( ∣ T ∣ ) = kernel ( T ) \operatorname{kernel}(|T|)=\operatorname{kernel}(T) kernel ( ∣ T ∣ ) = kernel ( T )
U 0 : range ( ∣ T ∣ ) → range ( T ) , ∣ T ∣ x ↦ T x . U_0:\operatorname{range}(|T|)\to\operatorname{range}(T),\qquad|T|x\mapsto Tx. U 0 : range ( ∣ T ∣ ) → range ( T ) , ∣ T ∣ x ↦ T x . This is well-defined by kernel ( ∣ T ∣ ) = kernel ( T ) \operatorname{kernel}(|T|)=\operatorname{kernel}(T) kernel ( ∣ T ∣ ) = kernel ( T ) U 0 U_0 U 0
V : range ( ∣ T ∣ ) ‾ → range ( T ) ‾ . V:\overline{\operatorname{range}(|T|)}\to\overline{\operatorname{range}(T)}. V : range ( ∣ T ∣ ) → range ( T ) . Since ∣ T ∣ = ∣ T ∣ ∗ |T|=|T|^{*} ∣ T ∣ = ∣ T ∣ ∗
H = range ( ∣ T ∣ ) ‾ ⊕ kernel ( ∣ T ∣ ) . H=\overline{\operatorname{range}(|T|)}\oplus\operatorname{kernel}(|T|). H = range ( ∣ T ∣ ) ⊕ kernel ( ∣ T ∣ ) . Define U U U
U ( x + y ) : = V x , x ∈ range ( ∣ T ∣ ) ‾ , y ∈ kernel ( ∣ T ∣ ) . U(x+y):=Vx,\qquad x\in\overline{\operatorname{range}(|T|)},\quad y\in\operatorname{kernel}(|T|). U ( x + y ) := V x , x ∈ range ( ∣ T ∣ ) , y ∈ kernel ( ∣ T ∣ ) . Then U U U range ( ∣ T ∣ ) ‾ \overline{\operatorname{range}(|T|)} range ( ∣ T ∣ ) range ( T ) ‾ \overline{\operatorname{range}(T)} range ( T )
for every x ∈ H x\in H x ∈ H T = U ∣ T ∣ T=U|T| T = U ∣ T ∣ kernel ( U ) = kernel ( ∣ T ∣ ) = kernel ( T ) \operatorname{kernel}(U)=\operatorname{kernel}(|T|)=\operatorname{kernel}(T) kernel ( U ) = kernel ( ∣ T ∣ ) = kernel ( T ) W W W W ∣ T ∣ = T = U ∣ T ∣ W|T|=T=U|T| W ∣ T ∣ = T = U ∣ T ∣ W = U W=U W = U range ( ∣ T ∣ ) \operatorname{range}(|T|) range ( ∣ T ∣ )
W ‾ = U ‾ \overline{W}= \overline{U} W = U on range ( ∣ T ∣ ) ‾ \overline{\operatorname{range}(|T|)} range ( ∣ T ∣ ) kernel ( ∣ T ∣ ) \operatorname{kernel}(|T|) kernel ( ∣ T ∣ ) W = U W=U W = U H 1 H_1 H 1
Corollary 2. Under Assumption 3, there exists w P ∈ H w_P\in\mathcal{H} w P ∈ H
h P † = ( T P ∗ T P ) β h 2 w P . h_P^{\dagger}=(T_P^{*}T_P)^{\frac{\beta_h}{2}}w_P. h P † = ( T P ∗ T P ) 2 β h w P . Proof. By Assumption 3, there exists v P ∈ G v_P\in\mathcal{G} v P ∈ G
r P , ∥ = ( T P T P ∗ ) β h + 1 2 v P . r_{P,\parallel}=(T_PT_P^{*})^{\frac{\beta_h+1}{2}}v_P. r P , ∥ = ( T P T P ∗ ) 2 β h + 1 v P . We write the polar decomposition of T P = U ∣ T P ∣ T_P=U|T_P| T P = U ∣ T P ∣
( T P T P ∗ ) s = ( U ∣ T P ∣ ∣ T P ∣ U ∗ ) s = U ( T P ∗ T P ) s U ∗ (T_PT_P^{*})^s=(U|T_P||T_P|U^{*})^s=U(T_P^{*}T_P)^sU^{*} ( T P T P ∗ ) s = ( U ∣ T P ∣∣ T P ∣ U ∗ ) s = U ( T P ∗ T P ) s U ∗ for any s > 0 s>0 s > 0 h P † h_P^{\dagger} h P †
T P h = r P , ∥ = ( T P T P ∗ ) β h + 1 2 v P = U ∣ T P ∣ ( T P ∗ T P ) β h 2 U ∗ v P T_Ph=r_{P,\parallel}=(T_PT_P^{*})^{\frac{\beta_h+1}{2}}v_P
=U|T_P|(T_P^{*}T_P)^{\frac{\beta_h}{2}}U^{*}v_P T P h = r P , ∥ = ( T P T P ∗ ) 2 β h + 1 v P = U ∣ T P ∣ ( T P ∗ T P ) 2 β h U ∗ v P where w P : = U ∗ v P w_P:=U^{*}v_P w P := U ∗ v P h P † ∈ kernel ( T P ) ⊥ h_P^{\dagger}\in\operatorname{kernel}(T_P)^{\perp} h P † ∈ kernel ( T P ) ⊥ ( T P ∗ T P ) β h 2 w P ∈ kernel ( T P ) ⊥ (T_P^{*}T_P)^{\frac{\beta_h}{2}}w_P\in\operatorname{kernel}(T_P)^{\perp} ( T P ∗ T P ) 2 β h w P ∈ kernel ( T P ) ⊥
h P † − ( T P ∗ T P ) β h 2 w P ∈ kernel ( T P ) ∩ kernel ( T P ) ⊥ . h_P^{\dagger}-(T_P^{*}T_P)^{\frac{\beta_h}{2}}w_P\in\operatorname{kernel}(T_P)\cap\operatorname{kernel}(T_P)^{\perp}. h P † − ( T P ∗ T P ) 2 β h w P ∈ kernel ( T P ) ∩ kernel ( T P ) ⊥ . Proofs for sub:minimaxlearnersofhpdag
Proof of Lemma 4. We adapt the proof of [8 ] (Lemma 3) and generalize to general bounded operator T T T h ∈ H P h \in\mathcal{H}_{P} h ∈ H P
T P ∗ ( T P h − r P ) = 0. (27) T_{P}^{*}(T_{P}h-r_{P})=0. \tag*{(27)} T P ∗ ( T P h − r P ) = 0. (27) Therefore T P h − r P ∈ kernel ( T P ∗ ) = range ( T P ) ‾ ⊥ T_{P}h-r_{P} \in\operatorname{kernel}(T_{P}^{*})=\overline{\operatorname{range}(T_{P})}^{\perp} T P h − r P ∈ kernel ( T P ∗ ) = range ( T P ) ⊥
( ∀ h ∈ H P ) ( ∀ g ∈ range ( T P ) ‾ ) , ⟨ T P h − r P , g ⟩ = 0. (28) (\forall h \in\mathcal{H}_{P})(\forall g \in\overline{\operatorname{range}(T_{P})}),\quad\langle T_{P}h-r_{P},g\rangle=0. \tag*{(28)} ( ∀ h ∈ H P ) ( ∀ g ∈ range ( T P ) ) , ⟨ T P h − r P , g ⟩ = 0. (28) By adding the constant − ∥ T P h P † − r P ∥ 2 -\lVert T_{P}h_{P}^{\dagger}-r_{P}\rVert^{2} − ∥ T P h P † − r P ∥ 2 h P λ h_{P}^{\lambda} h P λ
h P λ = arg min h ∈ H λ ∥ h ∥ H 2 + ⟨ T P ( h − h P † ) , T P ( h + h P † ) − 2 r P ⟩ L 2 ( P Z ) = arg min h ∈ H λ ∥ h ∥ H 2 + ∥ T P ( h − h P † ) ∥ L 2 ( P Z ) 2 + 2 ⟨ T P ( h − h P † ) , T P h P † − r P ⟩ L 2 ( P Z ) ⏟ = 0 , \begin{aligned}
h_{P}^{\lambda}
&=\underset{h\in\mathcal{H}}{\operatorname{arg\,min}}\ \lambda\lVert h\rVert_{\mathcal{H}}^{2}+\left\langle T_{P}(h-h_{P}^{\dagger}),T_{P}(h+h_{P}^{\dagger})-2r_{P}\right\rangle_{L^{2}(P_{Z})}\\
&=\underset{h\in\mathcal{H}}{\operatorname{arg\,min}}\ \lambda\lVert h\rVert_{\mathcal{H}}^{2}+\left\lVert T_{P}(h-h_{P}^{\dagger})\right\rVert_{L^{2}(P_{Z})}^{2}+2\underbrace{\left\langle T_{P}(h-h_{P}^{\dagger}),T_{P}h_{P}^{\dagger}-r_{P}\right\rangle_{L^{2}(P_{Z})}}_{=0},
\end{aligned} h P λ = h ∈ H arg min λ ∥ h ∥ H 2 + ⟨ T P ( h − h P † ) , T P ( h + h P † ) − 2 r P ⟩ L 2 ( P Z ) = h ∈ H arg min λ ∥ h ∥ H 2 + T P ( h − h P † ) L 2 ( P Z ) 2 + 2 = 0 ⟨ T P ( h − h P † ) , T P h P † − r P ⟩ L 2 ( P Z ) , where we use Eq. ([]) (#eq:28). Taking the Fréchet derivative of the above objective with respect to h h h
h P λ = ( T P ∗ T P + λ Id H ) − 1 T P ∗ T P h P † . h_{P}^{\lambda}=(T_{P}^{*}T_{P}+\lambda\operatorname{Id}_{\mathcal{H}})^{-1}T_{P}^{*}T_{P}h_{P}^{\dagger}. h P λ = ( T P ∗ T P + λ Id H ) − 1 T P ∗ T P h P † . By Corollary 2 and Theorem 6, we have
h P λ − h P † = − λ ( T P ∗ T P + λ Id H ) − 1 h P † = ( ∫ σ ( T P ∗ T P ) − λ μ β h / 2 μ + λ d Π T P ∗ T P ( μ ) ) w P , h_{P}^{\lambda}-h_{P}^{\dagger}=-\lambda(T_{P}^{*}T_{P}+\lambda\operatorname{Id}_{\mathcal{H}})^{-1}h_{P}^{\dagger}=\left(\int_{\sigma(T_{P}^{*}T_{P})}\frac{-\lambda\mu^{\beta_{h}/2}}{\mu+\lambda}\,\mathrm{d}\Pi_{T_{P}^{*}T_{P}}(\mu)\right)w_{P}, h P λ − h P † = − λ ( T P ∗ T P + λ Id H ) − 1 h P † = ( ∫ σ ( T P ∗ T P ) μ + λ − λ μ β h /2 d Π T P ∗ T P ( μ ) ) w P , for some w P ∈ H w_{P}\in\mathcal{H} w P ∈ H
∥ h P λ − h P † ∥ L 2 ( P X ) 2 ≤ sup μ ∈ σ ( T P ∗ T P ) ( λ μ β h / 2 μ + λ ) 2 ∥ w P ∥ L 2 ( P X ) 2 . \left\lVert h_{P}^{\lambda}-h_{P}^{\dagger}\right\rVert_{L^{2}(P_{X})}^{2}\leq\sup_{\mu\in\sigma(T_{P}^{*}T_{P})}\left(\frac{\lambda\mu^{\beta_{h}/2}}{\mu+\lambda}\right)^{2}\lVert w_{P}\rVert_{L^{2}(P_{X})}^{2}. h P λ − h P † L 2 ( P X ) 2 ≤ μ ∈ σ ( T P ∗ T P ) sup ( μ + λ λ μ β h /2 ) 2 ∥ w P ∥ L 2 ( P X ) 2 . Since T P ∗ T P T_{P}^{*}T_{P} T P ∗ T P σ ( T P ∗ T P ) ⊂ [ 0 , ∞ ) \sigma(T_{P}^{*}T_{P})\subset[0,\infty) σ ( T P ∗ T P ) ⊂ [ 0 , ∞ ) [8 ] (Lemma 3).
Proof of Theorem 2. Let any h ∈ H h\in\mathcal{H} h ∈ H g ∈ range ( T P ) ‾ g\in\overline{\operatorname{range}(T_{P})} g ∈ range ( T P )
E P [ m ~ ( W ; g ) − h ( X ) g ( Z ) ] = ⟨ r P − T P h , g ⟩ = ⟨ r P − T P h P † , g ⟩ + ⟨ T P ( h P † − h ) , g ⟩ = ⟨ T P ( h P † − h ) , g ⟩ , \begin{aligned}
\mathbb{E}_{P}[\widetilde{m}(W;g)-h(X)g(Z)]
&=\langle r_{P}-T_{P}h,g\rangle\\
&=\langle r_{P}-T_{P}h_{P}^{\dagger},g\rangle+\langle T_{P}(h_{P}^{\dagger}-h),g\rangle\\
&=\langle T_{P}(h_{P}^{\dagger}-h),g\rangle,
\end{aligned} E P [ m ( W ; g ) − h ( X ) g ( Z )] = ⟨ r P − T P h , g ⟩ = ⟨ r P − T P h P † , g ⟩ + ⟨ T P ( h P † − h ) , g ⟩ = ⟨ T P ( h P † − h ) , g ⟩ , where the last equality is by Eq. ([]) (#eq:27). This gives the equivalent of Eq.(10) in [8 ] . The proof then follows the proof of [8 ] (Theorem 4), using Lemma 4 instead of [8 ] (Lemma 3).
Proofs for sub:minimaxlearnersoftheweaknormrieszrepresenter
We first prove two preparatory results and an algebraic identity, and then provide the proof for Theorem 3.
Proof of Lemma 5. The proof follows an analogous calculation to Lemma 4. We introduce the shorthand
b α h , w ( λ ) : = ∥ T P ( α P , λ h − α P h , † ) ∥ L 2 ( P Z ) 2 b_{\alpha^h,w}(\lambda) := \left\|T_P(\alpha^h_{P,\lambda}-\alpha^{h,\dagger}_P)\right\|_{L^2(P_Z)}^2 b α h , w ( λ ) := T P ( α P , λ h − α P h , † ) L 2 ( P Z ) 2 b α h , s ( λ ) : = ∥ α P , λ h − α P h , † ∥ L 2 ( P X ) 2 . b_{\alpha^h,s}(\lambda) := \left\|\alpha^h_{P,\lambda}-\alpha^{h,\dagger}_P\right\|_{L^2(P_X)}^2. b α h , s ( λ ) := α P , λ h − α P h , † L 2 ( P X ) 2 . Since a P , ∥ ∈ range ( T P ∗ T P ) a_{P,\parallel} \in\operatorname{range}(T_P^*T_P) a P , ∥ ∈ range ( T P ∗ T P ) α P h , † \alpha^{h,\dagger}_P α P h , †
T P α P h , † = g P † T_P\alpha^{h,\dagger}_P=g^\dagger_P T P α P h , † = g P † exists, and it satisfies α P h , † ∈ kernel ( T P ) ⊥ \alpha^{h,\dagger}_P \in\operatorname{kernel}(T_P)^\perp α P h , † ∈ kernel ( T P ) ⊥
α P , λ h = ( T P ∗ T P + λ Id H ) − 1 T P ∗ T P α P h , † \alpha^h_{P,\lambda}=(T_P^*T_P+\lambda\operatorname{Id}_{\mathcal{H}})^{-1}T_P^*T_P\alpha^{h,\dagger}_P α P , λ h = ( T P ∗ T P + λ Id H ) − 1 T P ∗ T P α P h , † α P , λ h − α P h , † = − λ ( T P ∗ T P + λ Id H ) − 1 α P h , † . \alpha^h_{P,\lambda}-\alpha^{h,\dagger}_P=-\lambda(T_P^*T_P+\lambda\operatorname{Id}_{\mathcal{H}})^{-1}\alpha^{h,\dagger}_P. α P , λ h − α P h , † = − λ ( T P ∗ T P + λ Id H ) − 1 α P h , † . By Theorem 6, applied to the positive self-adjoint operator T P ∗ T P T_P^*T_P T P ∗ T P
α P , λ h − α P h , † = ( ∫ σ ( T P ∗ T P ) − λ μ + λ d Π T P ∗ T P ( μ ) ) α P h , † . \alpha^h_{P,\lambda}-\alpha^{h,\dagger}_P=\left(\int_{\sigma(T_P^*T_P)}\frac{-\lambda}{\mu+\lambda}\,\mathrm{d}\Pi_{T_P^*T_P}(\mu)\right)\alpha^{h,\dagger}_P. α P , λ h − α P h , † = ( ∫ σ ( T P ∗ T P ) μ + λ − λ d Π T P ∗ T P ( μ ) ) α P h , † . Thus
b α h , s ( λ ) = ∥ α P , λ h − α P h , † ∥ L 2 ( P X ) 2 = ∫ σ ( T P ∗ T P ) λ 2 ( μ + λ ) 2 d ⟨ Π T P ∗ T P ( μ ) α P h , † , α P h , † ⟩ L 2 ( P X ) , b_{\alpha^h,s}(\lambda)=\left\|\alpha^h_{P,\lambda}-\alpha^{h,\dagger}_P\right\|_{L^2(P_X)}^2=\int_{\sigma(T_P^*T_P)}\frac{\lambda^2}{(\mu+\lambda)^2}\,\mathrm{d}\left\langle\Pi_{T_P^*T_P}(\mu)\alpha^{h,\dagger}_P,\alpha^{h,\dagger}_P\right\rangle_{L^2(P_X)}, b α h , s ( λ ) = α P , λ h − α P h , † L 2 ( P X ) 2 = ∫ σ ( T P ∗ T P ) ( μ + λ ) 2 λ 2 d ⟨ Π T P ∗ T P ( μ ) α P h , † , α P h , † ⟩ L 2 ( P X ) , b α h , w ( λ ) = ∥ T P ( α P , λ h − α P h , † ) ∥ L 2 ( P Z ) 2 = ∫ σ ( T P ∗ T P ) μ λ 2 ( μ + λ ) 2 d ⟨ Π T P ∗ T P ( μ ) α P h , † , α P h , † ⟩ L 2 ( P X ) , b_{\alpha^h,w}(\lambda)=\left\|T_P(\alpha^h_{P,\lambda}-\alpha^{h,\dagger}_P)\right\|_{L^2(P_Z)}^2=\int_{\sigma(T_P^*T_P)}\frac{\mu\lambda^2}{(\mu+\lambda)^2}\,\mathrm{d}\left\langle\Pi_{T_P^*T_P}(\mu)\alpha^{h,\dagger}_P,\alpha^{h,\dagger}_P\right\rangle_{L^2(P_X)}, b α h , w ( λ ) = T P ( α P , λ h − α P h , † ) L 2 ( P Z ) 2 = ∫ σ ( T P ∗ T P ) ( μ + λ ) 2 μ λ 2 d ⟨ Π T P ∗ T P ( μ ) α P h , † , α P h , † ⟩ L 2 ( P X ) , where the second equality follows from applying Theorem 6 to the continuous functions μ ↦ λ 2 ( μ + λ ) 2 \mu\mapsto\frac{\lambda^2}{(\mu+\lambda)^2} μ ↦ ( μ + λ ) 2 λ 2 μ ↦ μ λ 2 ( μ + λ ) 2 \mu\mapsto\frac{\mu\lambda^2}{(\mu+\lambda)^2} μ ↦ ( μ + λ ) 2 μ λ 2
We now take λ = λ n ↓ 0 \lambda=\lambda_n\downarrow0 λ = λ n ↓ 0 σ ( T P ∗ T P ) \sigma(T_P^*T_P) σ ( T P ∗ T P )
B ↦ ⟨ Π T P ∗ T P ( B ) α P h , † , α P h , † ⟩ L 2 ( P X ) , B\mapsto\left\langle\Pi_{T_P^*T_P}(B)\alpha^{h,\dagger}_P,\alpha^{h,\dagger}_P\right\rangle_{L^2(P_X)}, B ↦ ⟨ Π T P ∗ T P ( B ) α P h , † , α P h , † ⟩ L 2 ( P X ) , and the sequence of functions σ ( T P ∗ T P ) → R \sigma(T_P^*T_P)\to\mathbb{R} σ ( T P ∗ T P ) → R
μ ↦ λ n 2 ( μ + λ n ) 2 . \mu\mapsto\frac{\lambda_n^2}{(\mu+\lambda_n)^2}. μ ↦ ( μ + λ n ) 2 λ n 2 . We denote the scalar-valued measure by ν \nu ν α P h , † ∈ kernel ( T P ) ⊥ \alpha^{h,\dagger}_P\in\operatorname{kernel}(T_P)^\perp α P h , † ∈ kernel ( T P ) ⊥ ν \nu ν μ = 0 \mu=0 μ = 0 μ ∈ σ ( T P ∗ T P ) \mu\in\sigma(T_P^*T_P) μ ∈ σ ( T P ∗ T P ) μ ≠ 0 \mu\ne0 μ = 0 λ 2 ( μ + λ ) 2 → 0 \frac{\lambda^2}{(\mu+\lambda)^2}\to0 ( μ + λ ) 2 λ 2 → 0
∣ λ n 2 ( μ + λ n ) 2 ∣ ≤ 1. \left|\frac{\lambda_n^2}{(\mu+\lambda_n)^2}\right|\le1. ( μ + λ n ) 2 λ n 2 ≤ 1. Hence, by dominated convergence theorem, we have b α h , s ( λ n ) → 0 b_{\alpha^h,s}(\lambda_n) \to0 b α h , s ( λ n ) → 0 n → ∞ n \to\infty n → ∞
On the other hand, by another application of dominated convergence theorem, we have
b α h , w ( λ n ) λ n = ∫ σ ( T P ∗ T P ) μ λ n ( μ + λ n ) 2 d ⟨ Π T P ∗ T P ( μ ) α P h , † , α P h , † ⟩ L 2 ( P X ) → 0 , (29) \frac{b_{\alpha^h,w}(\lambda_n)}{\lambda_n} = \int_{\sigma(T_P^*T_P)} \frac{\mu\lambda_n}{(\mu+\lambda_n)^2} \, \mathrm{d}\left\langle\Pi_{T_P^*T_P}(\mu)\alpha_P^{h,\dagger},\alpha_P^{h,\dagger}\right\rangle_{L^2(P_X)} \to0, \tag*{(29)} λ n b α h , w ( λ n ) = ∫ σ ( T P ∗ T P ) ( μ + λ n ) 2 μ λ n d ⟨ Π T P ∗ T P ( μ ) α P h , † , α P h , † ⟩ L 2 ( P X ) → 0 , (29) as n → ∞ n \to\infty n → ∞ μ λ / ( μ + λ ) 2 → 0 \mu\lambda/(\mu+\lambda)^2 \to0 μ λ / ( μ + λ ) 2 → 0 μ ≥ 0 \mu\ge0 μ ≥ 0 0 ≤ μ λ / ( μ + λ ) 2 ≤ 1 / 4 0 \le\mu\lambda/(\mu+\lambda)^2 \le1/4 0 ≤ μ λ / ( μ + λ ) 2 ≤ 1/4
b α h , w ( λ n ) λ n = o ( 1 ) . \frac{b_{\alpha^h,w}(\lambda_n)}{\lambda_n} = o(1). λ n b α h , w ( λ n ) = o ( 1 ) . We now present a concentration of measure result, which will be used in the proof of Theorem 3.
Lemma 7 (Localized concentration for the α h \alpha^h α h λ = λ α h , n \lambda= \lambda_{\alpha^h,n} λ = λ α h , n
α λ : = α P , λ h , α 0 : = α P h , † . \alpha_\lambda:= \alpha_{P,\lambda}^h,\qquad\alpha_0 := \alpha_P^{h,\dagger}. α λ := α P , λ h , α 0 := α P h , † . Condition on the first-stage sample used to construct g ^ \widehat{g} g g ^ ( Z ) \widehat{g}(Z) g ( Z ) M < ∞ M < \infty M < ∞
sup α ∈ H n ∥ α ∥ ∞ ≤ M , sup g ∈ G n ∥ g ∥ ∞ ≤ M , ∥ α λ ∥ ∞ ≤ M . \sup_{\alpha\in\mathcal{H}_n} \|\alpha\|_\infty\le M,\qquad\sup_{g \in\mathcal{G}_n} \|g\|_\infty\le M,\qquad\|\alpha_\lambda\|_\infty\le M. α ∈ H n sup ∥ α ∥ ∞ ≤ M , g ∈ G n sup ∥ g ∥ ∞ ≤ M , ∥ α λ ∥ ∞ ≤ M . Assume also that
α 0 , α λ ∈ H n , 0 ∈ G n , T P ( α 0 − α ) ∈ G n , ∀ α ∈ H n . \alpha_0,\alpha_\lambda\in\mathcal{H}_n,\qquad0 \in\mathcal{G}_n,\qquad T_P(\alpha_0-\alpha) \in\mathcal{G}_n,\qquad\forall\alpha\in\mathcal{H}_n. α 0 , α λ ∈ H n , 0 ∈ G n , T P ( α 0 − α ) ∈ G n , ∀ α ∈ H n . For α ∈ H n \alpha\in\mathcal{H}_n α ∈ H n
q α : = T P ( α 0 − α ) . q_\alpha:= T_P(\alpha_0-\alpha). q α := T P ( α 0 − α ) . Let δ n \delta_n δ n
δ n = Ω ( log log n + log ( 1 / ζ ) n ) , \delta_n = \Omega\left(\sqrt{\frac{\log\log n+\log(1/\zeta)}{n}}\right), δ n = Ω ( n log log n + log ( 1/ ζ ) ) , and suppose that, conditionally on the first-stage sample, δ n \delta_n δ n
G n , H n ⋅ G n , H n − α λ . \mathcal{G}_n,\qquad\mathcal{H}_n\cdot\mathcal{G}_n,\qquad\mathcal{H}_n-\alpha_\lambda. G n , H n ⋅ G n , H n − α λ . Then, after enlarging δ n \delta_n δ n M M M E \mathcal{E} E 1 − ζ 1-\zeta 1 − ζ E \mathcal{E} E
∣ ( E n − E ) [ 2 g ^ ( Z ) q α ( Z ) − 2 α ( X ) q α ( Z ) − q α ( Z ) 2 ] ∣ ≤ δ n ∥ q α ∥ L 2 ( P Z ) + δ n 2 , ∀ α ∈ H n , (30) \left|(\mathbb{E}_n-\mathbb{E})\left[2\widehat{g}(Z)q_\alpha(Z)-2\alpha(X)q_\alpha(Z)-q_\alpha(Z)^2\right]\right| \le\delta_n\|q_\alpha\|_{L^2(P_Z)}+\delta_n^2,\qquad\forall\alpha\in\mathcal{H}_n, \tag*{(30)} ( E n − E ) [ 2 g ( Z ) q α ( Z ) − 2 α ( X ) q α ( Z ) − q α ( Z ) 2 ] ≤ δ n ∥ q α ∥ L 2 ( P Z ) + δ n 2 , ∀ α ∈ H n , (30) ∣ ( E n − E ) [ 2 g ^ ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − g ( Z ) 2 ] ∣ ≤ δ n ∥ g ∥ L 2 ( P Z ) + δ n 2 , ∀ g ∈ G n , (31) \left|(\mathbb{E}_n-\mathbb{E})\left[2\widehat{g}(Z)g(Z)-2\alpha_\lambda(X)g(Z)-g(Z)^2\right]\right| \le\delta_n\|g\|_{L^2(P_Z)}+\delta_n^2,\qquad\forall g \in\mathcal{G}_n, \tag*{(31)} ( E n − E ) [ 2 g ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − g ( Z ) 2 ] ≤ δ n ∥ g ∥ L 2 ( P Z ) + δ n 2 , ∀ g ∈ G n , (31) ∣ ( E n − E ) [ α ( X ) 2 − α λ ( X ) 2 ] ∣ ≤ δ n ∥ α − α λ ∥ L 2 ( P X ) + δ n 2 , ∀ α ∈ H n . (32) \left|(\mathbb{E}_n-\mathbb{E})\left[\alpha(X)^2-\alpha_\lambda(X)^2\right]\right| \le\delta_n\|\alpha-\alpha_\lambda\|_{L^2(P_X)}+\delta_n^2,\qquad\forall\alpha\in\mathcal{H}_n. \tag*{(32)} ( E n − E ) [ α ( X ) 2 − α λ ( X ) 2 ] ≤ δ n ∥ α − α λ ∥ L 2 ( P X ) + δ n 2 , ∀ α ∈ H n . (32) Proof. Throughout the proof we condition on the first-stage sample, so that g ^ \widehat{g} g
For (30) , define the vector-valued class
V 1 : = { W ↦ ( α ( X ) q α ( Z ) , q α ( Z ) ) : α ∈ H n } , q α = T P ( α 0 − α ) . \mathcal{V}_1 := \left\{W \mapsto\left(\alpha(X)q_\alpha(Z),q_\alpha(Z)\right): \alpha\in\mathcal{H}_n\right\},\qquad q_\alpha=T_P(\alpha_0-\alpha). V 1 := { W ↦ ( α ( X ) q α ( Z ) , q α ( Z ) ) : α ∈ H n } , q α = T P ( α 0 − α ) . Its first coordinate projection satisfies
V 1 ∣ 1 = { α q α : α ∈ H n } ⊆ H n ⋅ G n , \mathcal{V}_{1|1} = \{\alpha q_{\alpha} : \alpha\in\mathcal{H}_n\} \subseteq\mathcal{H}_n \cdot\mathcal{G}_n, V 1∣1 = { α q α : α ∈ H n } ⊆ H n ⋅ G n , because q α ∈ G n q_{\alpha} \in\mathcal{G}_n q α ∈ G n
V 1 ∣ 2 = { q α : α ∈ H n } ⊆ G n . \mathcal{V}_{1|2} = \{q_{\alpha} : \alpha\in\mathcal{H}_n\} \subseteq\mathcal{G}_n. V 1∣2 = { q α : α ∈ H n } ⊆ G n . Moreover, since α 0 ∈ H n \alpha_0 \in\mathcal{H}_n α 0 ∈ H n q α 0 = T P ( α 0 − α 0 ) = 0 q_{\alpha_0} = T_P(\alpha_0 - \alpha_0) = 0 q α 0 = T P ( α 0 − α 0 ) = 0 ( 0 , 0 ) (0,0) ( 0 , 0 ) V 1 \mathcal{V}_1 V 1 ( 0 , 0 ) (0,0) ( 0 , 0 )
ℓ 1 ( u 1 , u 2 ; W ) : = 2 g ^ ( Z ) u 2 − 2 u 1 − u 2 2 . \ell_1(u_1,u_2; W) := 2\widehat{g}(Z)u_2 - 2u_1 - u_2^2. ℓ 1 ( u 1 , u 2 ; W ) := 2 g ( Z ) u 2 − 2 u 1 − u 2 2 . The loss ℓ 1 \ell_1 ℓ 1 ( u 1 , u 2 ) (u_1,u_2) ( u 1 , u 2 ) 1 − ζ / 3 1-\zeta/3 1 − ζ /3
∣ ( E n − E ) [ 2 g ^ ( Z ) q α ( Z ) − 2 α ( X ) q α ( Z ) − q α ( Z ) 2 ] ∣ ≲ δ n ∥ ( α q α , q α ) ∥ L 2 ( P ) , 2 + δ n 2 . \left|(\mathbb{E}_n-\mathbb{E})\left[2\widehat{g}(Z)q_{\alpha}(Z)-2\alpha(X)q_{\alpha}(Z)-q_{\alpha}(Z)^2\right]\right| \lesssim\delta_n\|(\alpha q_{\alpha},q_{\alpha})\|_{L^2(P),2}+\delta_n^2. ( E n − E ) [ 2 g ( Z ) q α ( Z ) − 2 α ( X ) q α ( Z ) − q α ( Z ) 2 ] ≲ δ n ∥ ( α q α , q α ) ∥ L 2 ( P ) , 2 + δ n 2 . Since α \alpha α
∥ ( α q α , q α ) ∥ L 2 ( P ) , 2 ≲ ∥ q α ∥ L 2 ( P Z ) . \|(\alpha q_{\alpha},q_{\alpha})\|_{L^2(P),2} \lesssim\|q_{\alpha}\|_{L^2(P_Z)}. ∥ ( α q α , q α ) ∥ L 2 ( P ) , 2 ≲ ∥ q α ∥ L 2 ( P Z ) . Absorbing the constant into δ n \delta_n δ n (30) .
For (31) , define
V 2 : = { W ↦ ( α λ ( X ) g ( Z ) , g ( Z ) ) : g ∈ G n } . \mathcal{V}_2 := \{W \mapsto(\alpha_{\lambda}(X)g(Z),g(Z)) : g \in\mathcal{G}_n\}. V 2 := { W ↦ ( α λ ( X ) g ( Z ) , g ( Z )) : g ∈ G n } . Its first coordinate projection satisfies
V 2 ∣ 1 = { α λ g : g ∈ G n } ⊆ H n ⋅ G n , \mathcal{V}_{2|1} = \{\alpha_{\lambda}g : g \in\mathcal{G}_n\} \subseteq\mathcal{H}_n \cdot\mathcal{G}_n, V 2∣1 = { α λ g : g ∈ G n } ⊆ H n ⋅ G n , because α λ ∈ H n \alpha_{\lambda} \in\mathcal{H}_n α λ ∈ H n V 2 ∣ 2 = G n \mathcal{V}_{2|2}=\mathcal{G}_n V 2∣2 = G n 0 ∈ G n 0\in\mathcal{G}_n 0 ∈ G n ( 0 , 0 ) (0,0) ( 0 , 0 ) V 2 \mathcal{V}_2 V 2 V 2 \mathcal{V}_2 V 2 ( 0 , 0 ) (0,0) ( 0 , 0 ) ℓ 1 \ell_1 ℓ 1 1 − ζ / 3 1-\zeta/3 1 − ζ /3
∣ ( E n − E ) [ 2 g ^ ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − g ( Z ) 2 ] ∣ ≲ δ n ∥ ( α λ g , g ) ∥ L 2 ( P ) , 2 + δ n 2 . \left|(\mathbb{E}_n-\mathbb{E})\left[2\widehat{g}(Z)g(Z)-2\alpha_{\lambda}(X)g(Z)-g(Z)^2\right]\right| \lesssim\delta_n\|(\alpha_{\lambda}g,g)\|_{L^2(P),2}+\delta_n^2. ( E n − E ) [ 2 g ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − g ( Z ) 2 ] ≲ δ n ∥ ( α λ g , g ) ∥ L 2 ( P ) , 2 + δ n 2 . Since α λ \alpha_{\lambda} α λ ∥ ( α λ g , g ) ∥ L 2 ( P ) , 2 ≲ ∥ g ∥ L 2 ( P Z ) \|(\alpha_{\lambda}g,g)\|_{L^2(P),2}\lesssim\|g\|_{L^2(P_Z)} ∥ ( α λ g , g ) ∥ L 2 ( P ) , 2 ≲ ∥ g ∥ L 2 ( P Z ) δ n \delta_n δ n (31) .
For (32) , apply Lemma 8 to the scalar class H n \mathcal{H}_n H n α λ \alpha_{\lambda} α λ ℓ 2 ( u ) = u 2 \ell_2(u)=u^2 ℓ 2 ( u ) = u 2 H n − α λ \mathcal{H}_n-\alpha_{\lambda} H n − α λ δ n \delta_n δ n u ↦ u 2 u\mapsto u^2 u ↦ u 2 H n \mathcal{H}_n H n 1 − ζ / 3 1-\zeta/3 1 − ζ /3
∣ ( E n − E ) [ α ( X ) 2 − α λ ( X ) 2 ] ∣ ≲ δ n ∥ α − α λ ∥ L 2 ( P X ) + δ n 2 . \left|(\mathbb{E}_n-\mathbb{E})\left[\alpha(X)^2-\alpha_{\lambda}(X)^2\right]\right| \lesssim\delta_n\|\alpha-\alpha_{\lambda}\|_{L^2(P_X)}+\delta_n^2. ( E n − E ) [ α ( X ) 2 − α λ ( X ) 2 ] ≲ δ n ∥ α − α λ ∥ L 2 ( P X ) + δ n 2 . Absorbing the constant into δ n \delta_n δ n (32) . The desired conclusion follows by taking a union bound over the failure probabilities of the three events.
Algebraic identity. We have the identity, for all α ∈ H n \alpha\in\mathcal{H}_n α ∈ H n
∥ T P α − g P † ∥ 2 2 + λ ∥ α ∥ 2 2 − ∥ T P α λ − g P † ∥ 2 2 − λ ∥ α λ ∥ 2 2 = ∥ T P ( α − α λ ) ∥ 2 2 + λ ∥ α − α λ ∥ 2 2 . (33) \left\|T_P\alpha-g_P^\dagger\right\|_2^2+\lambda\|\alpha\|_2^2-\left\|T_P\alpha_\lambda-g_P^\dagger\right\|_2^2-\lambda\|\alpha_\lambda\|_2^2
=\left\|T_P(\alpha-\alpha_\lambda)\right\|_2^2+\lambda\|\alpha-\alpha_\lambda\|_2^2. \tag*{(33)} T P α − g P † 2 2 + λ ∥ α ∥ 2 2 − T P α λ − g P † 2 2 − λ ∥ α λ ∥ 2 2 = ∥ T P ( α − α λ ) ∥ 2 2 + λ ∥ α − α λ ∥ 2 2 . (33) To show this identity, recall
α P , λ h = arg min α ∈ H λ ∥ α ∥ L 2 ( P X ) 2 + ∥ T P α − g P † ∥ L 2 ( P Z ) 2 . \alpha_{P,\lambda}^h=\underset{\alpha\in\mathcal{H}}{\operatorname{arg\,min}}\lambda\|\alpha\|_{L^2(P_X)}^2+\|T_P\alpha-g_P^\dagger\|_{L^2(P_Z)}^2. α P , λ h = α ∈ H arg min λ ∥ α ∥ L 2 ( P X ) 2 + ∥ T P α − g P † ∥ L 2 ( P Z ) 2 . By computing the first order Fréchet derivative, we find
λ α P , λ h + T P † T P α P , λ h − T P † g P † = 0. (34) \lambda\alpha_{P,\lambda}^h+T_P^\dagger T_P\alpha_{P,\lambda}^h-T_P^\dagger g_P^\dagger=0. \tag*{(34)} λ α P , λ h + T P † T P α P , λ h − T P † g P † = 0. (34) Therefore, for any α ∈ H \alpha\in\mathcal{H} α ∈ H
∥ T P α − g P † ∥ L 2 ( P Z ) 2 + λ ∥ α ∥ L 2 ( P X ) 2 − ∥ T P α P , λ h − g P † ∥ L 2 ( P Z ) 2 − λ ∥ α P , λ h ∥ L 2 ( P X ) 2 = ∥ T P ( α − α P , λ h ) ∥ L 2 ( P Z ) 2 + λ ∥ α − α P , λ h ∥ L 2 ( P X ) 2 + 2 ⟨ α − α P , λ h , T P † T P α P , λ h − T P † g P † ⟩ L 2 ( P X ) + 2 λ ⟨ α − α P , λ h , α P , λ h ⟩ L 2 ( P X ) 2 ⟨ α − α P , λ h , T P † T P α P , λ h − T P † g P † ⟩ L 2 ( P X ) + 2 λ ⟨ α − α P , λ h , α P , λ h ⟩ L 2 ( P X ) ⏟ = 0 \begin{aligned}
&\left\|T_P\alpha-g_P^\dagger\right\|_{L^2(P_Z)}^2+\lambda\|\alpha\|_{L^2(P_X)}^2-\left\|T_P\alpha_{P,\lambda}^h-g_P^\dagger\right\|_{L^2(P_Z)}^2-\lambda\|\alpha_{P,\lambda}^h\|_{L^2(P_X)}^2\\
&=\left\|T_P(\alpha-\alpha_{P,\lambda}^h)\right\|_{L^2(P_Z)}^2+\lambda\|\alpha-\alpha_{P,\lambda}^h\|_{L^2(P_X)}^2\\
&\quad+2\left\langle\alpha-\alpha_{P,\lambda}^h,T_P^\dagger T_P\alpha_{P,\lambda}^h-T_P^\dagger g_P^\dagger\right\rangle_{L^2(P_X)}
+2\lambda\left\langle\alpha-\alpha_{P,\lambda}^h,\alpha_{P,\lambda}^h\right\rangle_{L^2(P_X)}\\
&\quad\underset{=0}{\underbrace{\phantom{2\left\langle\alpha-\alpha_{P,\lambda}^h,T_P^\dagger T_P\alpha_{P,\lambda}^h-T_P^\dagger g_P^\dagger\right\rangle_{L^2(P_X)}
+2\lambda\left\langle\alpha-\alpha_{P,\lambda}^h,\alpha_{P,\lambda}^h\right\rangle_{L^2(P_X)}}}}
\end{aligned} T P α − g P † L 2 ( P Z ) 2 + λ ∥ α ∥ L 2 ( P X ) 2 − T P α P , λ h − g P † L 2 ( P Z ) 2 − λ ∥ α P , λ h ∥ L 2 ( P X ) 2 = T P ( α − α P , λ h ) L 2 ( P Z ) 2 + λ ∥ α − α P , λ h ∥ L 2 ( P X ) 2 + 2 ⟨ α − α P , λ h , T P † T P α P , λ h − T P † g P † ⟩ L 2 ( P X ) + 2 λ ⟨ α − α P , λ h , α P , λ h ⟩ L 2 ( P X ) = 0 2 ⟨ α − α P , λ h , T P † T P α P , λ h − T P † g P † ⟩ L 2 ( P X ) + 2 λ ⟨ α − α P , λ h , α P , λ h ⟩ L 2 ( P X ) where we use Eq. (34) .
Proof of Theorem 3. Throughout the proof, we condition on the independent samples used to construct g ^ ( λ g ) \widehat{g}(\lambda_g) g ( λ g )
g ^ : = g ^ ( λ g ) , λ : = λ α h , n , α ^ : = α ^ h ( g ^ , λ ) , \widehat{g}:=\widehat{g}(\lambda_g),\qquad
\lambda:=\lambda_{\alpha^h,n},\qquad
\widehat{\alpha}:=\widehat{\alpha}^h(\widehat{g},\lambda), g := g ( λ g ) , λ := λ α h , n , α := α h ( g , λ ) , α P : = α P h , † , α λ : = α P , λ h , δ n : = δ α h , n . \alpha_P:=\alpha_P^{h,\dagger},\qquad
\alpha_\lambda:=\alpha_{P,\lambda}^h,\qquad
\delta_n:=\delta_{\alpha^h,n}. α P := α P h , † , α λ := α P , λ h , δ n := δ α h , n . We use ∥ ⋅ ∥ 2 \|\cdot\|_2 ∥ ⋅ ∥ 2 L 2 L^2 L 2 ∥ ⋅ ∥ 2 , n \|\cdot\|_{2,n} ∥ ⋅ ∥ 2 , n L 2 ( P n ) L^2(P_n) L 2 ( P n ) α ^ \widehat{\alpha} α
α ^ = arg min α ∈ H n max g ∈ G n E n [ 2 g ^ ( Z ) g ( Z ) − 2 α ( X ) g ( Z ) − g ( Z ) 2 + λ α ( X ) 2 ] . (35) \widehat{\alpha}=\underset{\alpha\in\mathcal{H}_n}{\operatorname{arg\,min}}\ \underset{g\in\mathcal{G}_n}{\operatorname{max}}\ \mathbb{E}_n\left[2\widehat{g}(Z)g(Z)-2\alpha(X)g(Z)-g(Z)^2+\lambda\alpha(X)^2\right]. \tag*{(35)} α = α ∈ H n arg min g ∈ G n max E n [ 2 g ( Z ) g ( Z ) − 2 α ( X ) g ( Z ) − g ( Z ) 2 + λ α ( X ) 2 ] . (35) We introduce another useful shorthand
g ~ : = T P ( α P − α ^ ) . \widetilde{g}:=T_P(\alpha_P-\widehat{\alpha}). g := T P ( α P − α ) . We have
∥ T P ( α P − α ^ ) ∥ 2 2 = 2 ⟨ g P † , g ~ ⟩ 2 − 2 ⟨ T P α ^ , g ~ ⟩ 2 − ⟨ g ~ , g ~ ⟩ 2 = 2 ⟨ g ^ , g ~ ⟩ 2 + 2 ⟨ g P † − g ^ , g ~ ⟩ 2 − 2 ⟨ T P α ^ , g ~ ⟩ 2 − ⟨ g ~ , g ~ ⟩ 2 = 2 ⟨ g P † − g ~ , g ~ ⟩ 2 + E [ 2 g ^ ( Z ) g ~ ( Z ) − 2 α ^ ( X ) g ~ ( Z ) − g ~ ( Z ) 2 ] , \begin{aligned}
\left\|T_P(\alpha_P-\widehat{\alpha})\right\|_2^2
&=2\left\langle g_P^\dagger,\widetilde{g}\right\rangle_2-2\left\langle T_P\widehat{\alpha},\widetilde{g}\right\rangle_2-\left\langle\widetilde{g},\widetilde{g}\right\rangle_2\\
&=2\left\langle\widehat{g},\widetilde{g}\right\rangle_2+2\left\langle g_P^\dagger-\widehat{g},\widetilde{g}\right\rangle_2-2\left\langle T_P\widehat{\alpha},\widetilde{g}\right\rangle_2-\left\langle\widetilde{g},\widetilde{g}\right\rangle_2\\
&=2\left\langle g_P^\dagger-\widetilde{g},\widetilde{g}\right\rangle_2+\mathbb{E}\left[2\widehat{g}(Z)\widetilde{g}(Z)-2\widehat{\alpha}(X)\widetilde{g}(Z)-\widetilde{g}(Z)^2\right],
\end{aligned} ∥ T P ( α P − α ) ∥ 2 2 = 2 ⟨ g P † , g ⟩ 2 − 2 ⟨ T P α , g ⟩ 2 − ⟨ g , g ⟩ 2 = 2 ⟨ g , g ⟩ 2 + 2 ⟨ g P † − g , g ⟩ 2 − 2 ⟨ T P α , g ⟩ 2 − ⟨ g , g ⟩ 2 = 2 ⟨ g P † − g , g ⟩ 2 + E [ 2 g ( Z ) g ( Z ) − 2 α ( X ) g ( Z ) − g ( Z ) 2 ] , where in the last step we use the property of orthogonal projection T P T_P T P g ~ = q α ^ \tilde{g}=q_{\widehat{\alpha}} g ~ = q α (30) gives, on E \mathcal{E} E
∥ T P ( α P − α ^ ) ∥ 2 2 ≤ δ n ∥ g ~ ∥ 2 + δ n 2 + 2 ⟨ g P † − g ^ , g ~ ⟩ 2 (36) \left\|T_P(\alpha_P-\widehat{\alpha})\right\|_2^2 \le\delta_n\left\|\widetilde{g}\right\|_2+\delta_n^2+2\left\langle g_P^\dagger-\widehat{g},\widetilde{g}\right\rangle_2 \tag*{(36)} ∥ T P ( α P − α ) ∥ 2 2 ≤ δ n ∥ g ∥ 2 + δ n 2 + 2 ⟨ g P † − g , g ⟩ 2 (36) + E n [ 2 g ~ ( Z ) g ~ ( Z ) − 2 α ^ ( X ) g ~ ( Z ) − g ~ ( Z ) 2 ] . (37) +\mathbb{E}_n\left[2\widetilde{g}(Z)\widetilde{g}(Z)-2\widehat{\alpha}(X)\widetilde{g}(Z)-\widetilde{g}(Z)^2\right]. \tag*{(37)} + E n [ 2 g ( Z ) g ( Z ) − 2 α ( X ) g ( Z ) − g ( Z ) 2 ] . (37) First, by the closedness Assumption 7, we have g ~ ∈ G n \widetilde{g}\in\mathcal{G}_n g ∈ G n E \mathcal{E} E
Eq. ( B ) ≤ sup g ∈ G n E n [ 2 g ^ ( Z ) g ( Z ) − 2 α ^ ( X ) g ( Z ) − g ( Z ) 2 ] \operatorname{Eq.}(B)\le\sup_{g\in\mathcal{G}_n}\mathbb{E}_n\left[2\widehat{g}(Z)g(Z)-2\widehat{\alpha}(X)g(Z)-g(Z)^2\right] Eq. ( B ) ≤ g ∈ G n sup E n [ 2 g ( Z ) g ( Z ) − 2 α ( X ) g ( Z ) − g ( Z ) 2 ] ≤ ( a ) sup g ∈ G n E n [ 2 g ^ ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − g ( Z ) 2 + λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] \overset{(a)}{\le}\sup_{g\in\mathcal{G}_n}\mathbb{E}_n\left[2\widehat{g}(Z)g(Z)-2\alpha_\lambda(X)g(Z)-g(Z)^2+\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right] ≤ ( a ) g ∈ G n sup E n [ 2 g ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − g ( Z ) 2 + λ α λ ( X ) 2 − λ α ( X ) 2 ] ≤ ( b ) sup g ∈ G n { E [ 2 g ^ ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − g ( Z ) 2 ] + δ n ∥ g ∥ 2 + δ n 2 } + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] ≤ sup g ∈ G n E [ 2 g ^ ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − 1 2 g ( Z ) 2 ] + 3 δ n 2 2 + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] ≤ sup g ∈ L 2 ( P Z ) E [ 2 g ^ ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − 1 2 g ( Z ) 2 ] + 3 δ n 2 2 + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] \begin{aligned}
\overset{(b)}{\le}\sup_{g\in\mathcal{G}_n}\left\{\mathbb{E}\left[2\widehat{g}(Z)g(Z)-2\alpha_\lambda(X)g(Z)-g(Z)^2\right]+\delta_n\left\|g\right\|_2+\delta_n^2\right\}+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right] \\
&\le\sup_{g\in\mathcal{G}_n}\mathbb{E}\left[2\widehat{g}(Z)g(Z)-2\alpha_\lambda(X)g(Z)-\frac{1}{2}g(Z)^2\right]+\frac{3\delta_n^2}{2}+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right] \\
&\le\sup_{g\in L^2(P_Z)}\mathbb{E}\left[2\widehat{g}(Z)g(Z)-2\alpha_\lambda(X)g(Z)-\frac{1}{2}g(Z)^2\right]+\frac{3\delta_n^2}{2}+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right]
\end{aligned} ≤ ( b ) g ∈ G n sup { E [ 2 g ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − g ( Z ) 2 ] + δ n ∥ g ∥ 2 + δ n 2 } + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] ≤ g ∈ G n sup E [ 2 g ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − 2 1 g ( Z ) 2 ] + 2 3 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] ≤ g ∈ L 2 ( P Z ) sup E [ 2 g ( Z ) g ( Z ) − 2 α λ ( X ) g ( Z ) − 2 1 g ( Z ) 2 ] + 2 3 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] = ( c ) 2 ∥ g ^ − T P α λ ∥ 2 2 + 3 δ n 2 2 + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] . \overset{(c)}{=}2\left\|\widehat{g}-T_P\alpha_\lambda\right\|_2^2+\frac{3\delta_n^2}{2}+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right]. = ( c ) 2 ∥ g − T P α λ ∥ 2 2 + 2 3 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] . In the above derivations, we use (35) in (a), we use (31) in (b), in (c), after enlarging the supremum to L 2 ( P Z ) L^2(P_Z) L 2 ( P Z ) g = 2 ( g ^ − T P α λ ) g=2(\widehat{g}-T_P\alpha_\lambda) g = 2 ( g − T P α λ )
∥ g ^ − T P α λ ∥ 2 2 − ∥ g P † − T P α λ ∥ 2 2 = ⟨ g ^ + g P † − 2 T P α λ , g ^ − g P † ⟩ 2 . (38) \left\|\widehat{g}-T_P\alpha_\lambda\right\|_2^2-\left\|g_P^\dagger-T_P\alpha_\lambda\right\|_2^2=\left\langle\widehat{g}+g_P^\dagger-2T_P\alpha_\lambda,\widehat{g}-g_P^\dagger\right\rangle_2. \tag*{(38)} ∥ g − T P α λ ∥ 2 2 − g P † − T P α λ 2 2 = ⟨ g + g P † − 2 T P α λ , g − g P † ⟩ 2 . (38) Therefore,
⟨ g P † − g ~ , g ~ ⟩ 2 + ∥ g ^ − T P α λ ∥ 2 2 = ⟨ g P † − g ^ , g ~ ⟩ 2 + ∥ g P † − T P α λ ∥ 2 2 + ⟨ g ^ + g P † − 2 T P α λ , g ^ − g P † ⟩ 2 = ⟨ g P † − g ^ , g ~ + 2 T P α λ − g ^ − g P † ⟩ 2 + ∥ g P † − T P α λ ∥ 2 2 = ⟨ g P † − g ^ , T P α P − T P α ^ + 2 T P α λ − g ^ − g P † ⟩ 2 + ∥ g P † − T P α λ ∥ 2 2 = ⟨ g P † − g ^ , − T P α ^ + 2 T P α λ − g ^ ⟩ 2 + ∥ g P † − T P α λ ∥ 2 2 . (39) \begin{aligned}
\left\langle g_P^\dagger-\widetilde{g},\widetilde{g}\right\rangle_2+\left\|\widehat{g}-T_P\alpha_\lambda\right\|_2^2 \\
&=\left\langle g_P^\dagger-\widehat{g},\widetilde{g}\right\rangle_2+\left\|g_P^\dagger-T_P\alpha_\lambda\right\|_2^2+\left\langle\widehat{g}+g_P^\dagger-2T_P\alpha_\lambda,\widehat{g}-g_P^\dagger\right\rangle_2 \\
&=\left\langle g_P^\dagger-\widehat{g},\widetilde{g}+2T_P\alpha_\lambda-\widehat{g}-g_P^\dagger\right\rangle_2+\left\|g_P^\dagger-T_P\alpha_\lambda\right\|_2^2 \\
&=\left\langle g_P^\dagger-\widehat{g},T_P\alpha_P-T_P\widehat{\alpha}+2T_P\alpha_\lambda-\widehat{g}-g_P^\dagger\right\rangle_2+\left\|g_P^\dagger-T_P\alpha_\lambda\right\|_2^2 \\
&=\left\langle g_P^\dagger-\widehat{g},-T_P\widehat{\alpha}+2T_P\alpha_\lambda-\widehat{g}\right\rangle_2+\left\|g_P^\dagger-T_P\alpha_\lambda\right\|_2^2. \tag*{(39)}
\end{aligned} ⟨ g P † − g , g ⟩ 2 + ∥ g − T P α λ ∥ 2 2 = ⟨ g P † − g , g ⟩ 2 + g P † − T P α λ 2 2 + ⟨ g + g P † − 2 T P α λ , g − g P † ⟩ 2 = ⟨ g P † − g , g + 2 T P α λ − g − g P † ⟩ 2 + g P † − T P α λ 2 2 = ⟨ g P † − g , T P α P − T P α + 2 T P α λ − g − g P † ⟩ 2 + g P † − T P α λ 2 2 = ⟨ g P † − g , − T P α + 2 T P α λ − g ⟩ 2 + g P † − T P α λ 2 2 . (39) Hence, on E \mathcal{E} E
∥ T P ( α P − α ^ ) ∥ 2 2 ≤ δ n ∥ g ~ ∥ 2 2 + 5 2 δ n 2 + 2 ∥ g P † − g ^ , g ^ ∥ 2 2 + 2 ∥ g ^ − T P α λ ∥ 2 2 + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] = ( a ) δ n ∥ g ~ ∥ 2 2 + 5 2 δ n 2 + 2 ⟨ g P † − g ^ , − T P α ^ + 2 T P α λ − g ^ ⟩ 2 + 2 ∥ T P ( α P − α λ ) ∥ 2 2 + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] = ( b ) 2 ∥ T P ( α P − α λ ) ∥ 2 2 + 5 2 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] + δ n ∥ g ~ ∥ 2 2 + 2 ⟨ g P † − g ^ , T P ( α λ − α ^ ) ⟩ 2 + 2 ⟨ g P † − g ^ , T P ( α λ − α P ) ⟩ 2 + 2 ⟨ g P † − g ^ , g P † − g ^ ⟩ 2 ≤ ( c ) 3 ∥ T P ( α P − α λ ) ∥ 2 2 + 3 ∥ g P † − g ^ ∥ 2 2 + 5 2 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] + δ n ∥ g ~ ∥ 2 2 + 2 ⟨ 2 ( g P † − g ^ ) , 1 2 ( T P ( α λ − α ^ ) ) ⟩ 2 ≤ ( d ) 3 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ^ ∥ 2 2 + 5 2 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ^ ( X ) 2 ] + δ n ∥ g ~ ∥ 2 2 + 1 4 ∥ T P ( α λ − α ^ ) ∥ 2 2 , (40) \begin{aligned}
\lVert T_P(\alpha_P-\widehat{\alpha})\rVert_2^2
&\le\delta_n\lVert\widetilde{g}\rVert_2^2+\frac{5}{2}\delta_n^2+2\lVert g_P^\dagger-\widehat{g},\widehat{g}\rVert_2^2+2\lVert\widehat{g}-T_P\alpha_\lambda\rVert_2^2+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right]\\
&\overset{(a)}{=}\delta_n\lVert\widetilde{g}\rVert_2^2+\frac{5}{2}\delta_n^2+2\left\langle g_P^\dagger-\widehat{g},-T_P\widehat{\alpha}+2T_P\alpha_\lambda-\widehat{g}\right\rangle_2+2\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2\\
&\qquad+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right]\\
&\overset{(b)}{=}2\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+\frac{5}{2}\delta_n^2+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right]+\delta_n\lVert\widetilde{g}\rVert_2^2\\
&\qquad+2\left\langle g_P^\dagger-\widehat{g},T_P(\alpha_\lambda-\widehat{\alpha})\right\rangle_2+2\left\langle g_P^\dagger-\widehat{g},T_P(\alpha_\lambda-\alpha_P)\right\rangle_2+2\left\langle g_P^\dagger-\widehat{g},g_P^\dagger-\widehat{g}\right\rangle_2\\
&\overset{(c)}{\le}3\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+3\lVert g_P^\dagger-\widehat{g}\rVert_2^2+\frac{5}{2}\delta_n^2+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right]+\delta_n\lVert\widetilde{g}\rVert_2^2\\
&\qquad+2\left\langle2(g_P^\dagger-\widehat{g}),\frac{1}{2}\left(T_P(\alpha_\lambda-\widehat{\alpha})\right)\right\rangle_2\\
&\overset{(d)}{\le}3\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+7\lVert g_P^\dagger-\widehat{g}\rVert_2^2+\frac{5}{2}\delta_n^2\\
&\qquad+\mathbb{E}_n\left[\lambda\alpha_\lambda(X)^2-\lambda\widehat{\alpha}(X)^2\right]+\delta_n\lVert\widetilde{g}\rVert_2^2+\frac{1}{4}\lVert T_P(\alpha_\lambda-\widehat{\alpha})\rVert_2^2, \tag*{(40)}
\end{aligned} ∥ T P ( α P − α ) ∥ 2 2 ≤ δ n ∥ g ∥ 2 2 + 2 5 δ n 2 + 2 ∥ g P † − g , g ∥ 2 2 + 2 ∥ g − T P α λ ∥ 2 2 + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] = ( a ) δ n ∥ g ∥ 2 2 + 2 5 δ n 2 + 2 ⟨ g P † − g , − T P α + 2 T P α λ − g ⟩ 2 + 2 ∥ T P ( α P − α λ ) ∥ 2 2 + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] = ( b ) 2 ∥ T P ( α P − α λ ) ∥ 2 2 + 2 5 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] + δ n ∥ g ∥ 2 2 + 2 ⟨ g P † − g , T P ( α λ − α ) ⟩ 2 + 2 ⟨ g P † − g , T P ( α λ − α P ) ⟩ 2 + 2 ⟨ g P † − g , g P † − g ⟩ 2 ≤ ( c ) 3 ∥ T P ( α P − α λ ) ∥ 2 2 + 3 ∥ g P † − g ∥ 2 2 + 2 5 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] + δ n ∥ g ∥ 2 2 + 2 ⟨ 2 ( g P † − g ) , 2 1 ( T P ( α λ − α ) ) ⟩ 2 ≤ ( d ) 3 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ∥ 2 2 + 2 5 δ n 2 + E n [ λ α λ ( X ) 2 − λ α ( X ) 2 ] + δ n ∥ g ∥ 2 2 + 4 1 ∥ T P ( α λ − α ) ∥ 2 2 , (40) In the above derivations, we use Eq. (39) in ( a ) (a) ( a ) ( b ) (b) ( b ) ⟨ g P † − g ^ , 2 T P α λ − T P α ^ − g ^ ⟩ 2 \left\langle g_P^\dagger-\widehat{g},2T_P\alpha_\lambda-T_P\widehat{\alpha}-\widehat{g}\right\rangle_2 ⟨ g P † − g , 2 T P α λ − T P α − g ⟩ 2 2 ∥ g P † − g ^ ∥ 2 2 2\lVert g_P^\dagger-\widehat{g}\rVert_2^2 2 ∥ g P † − g ∥ 2 2 ( c ) (c) ( c )
∥ T P ( α P − α λ ) ∥ 2 2 + ∥ g P † − g ^ ∥ 2 2 + 2 ⟨ g P † − g ^ , T P ( α λ − α P ) ⟩ 2 ≥ 0 , \lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+\lVert g_P^\dagger-\widehat{g}\rVert_2^2+2\left\langle g_P^\dagger-\widehat{g},T_P(\alpha_\lambda-\alpha_P)\right\rangle_2\ge0, ∥ T P ( α P − α λ ) ∥ 2 2 + ∥ g P † − g ∥ 2 2 + 2 ⟨ g P † − g , T P ( α λ − α P ) ⟩ 2 ≥ 0 , and in ( d ) (d) ( d )
2 ⟨ 2 ( g P † − g ^ ) , 1 2 ( T P ( α λ − α ^ ) ) ⟩ 2 ≤ 4 ∥ g P † − g ^ ∥ 2 2 + 1 4 ∥ T P ( α λ − α ^ ) ∥ 2 2 . 2\left\langle2(g_P^\dagger-\widehat{g}),\frac{1}{2}\left(T_P(\alpha_\lambda-\widehat{\alpha})\right)\right\rangle_2\le4\lVert g_P^\dagger-\widehat{g}\rVert_2^2+\frac{1}{4}\lVert T_P(\alpha_\lambda-\widehat{\alpha})\rVert_2^2. 2 ⟨ 2 ( g P † − g ) , 2 1 ( T P ( α λ − α ) ) ⟩ 2 ≤ 4 ∥ g P † − g ∥ 2 2 + 4 1 ∥ T P ( α λ − α ) ∥ 2 2 . We find, on E \mathcal{E} E
∥ T P ( α ^ − α λ ) ∥ 2 2 + λ ∥ α ^ − α λ ∥ 2 2 = ∥ T P ( α ^ − α P ) ∥ 2 2 + λ ∥ α ^ ∥ 2 2 − ∥ T P ( α λ − α P ) ∥ 2 2 − λ ∥ α λ ∥ 2 2 = ( a ) ∥ T P ( α ^ − α P ) ∥ 2 2 + λ ∥ α ^ ∥ 2 2 − ∥ T P ( α λ − α P ) ∥ 2 2 − λ ∥ α λ ∥ 2 2 ≤ ( b ) 2 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ^ ∥ 2 2 + 5 2 δ n 2 + λ ( E − E n ) [ α ^ ( X ) 2 − α λ ( X ) 2 ] + δ n ∥ g ~ ∥ 2 2 + 1 4 ∥ T P ( α λ − α ^ ) ∥ 2 2 ≤ ( c ) 2 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ^ ∥ 2 2 + 9 2 δ n 2 + λ ( E − E n ) [ α ^ ( X ) 2 − α λ ( X ) 2 ] + 1 8 ∥ T P ( α P − α ^ ) ∥ 2 2 + 1 4 ∥ T P ( α λ − α ^ ) ∥ 2 2 ≤ ( d ) 9 4 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ^ ∥ 2 2 + 9 2 δ n 2 + λ ( E − E n ) [ α ^ ( X ) 2 − α λ ( X ) 2 ] + 1 2 ∥ T P ( α λ − α ^ ) ∥ 2 2 , \begin{aligned}
\lVert T_P(\widehat{\alpha}-\alpha_\lambda)\rVert_2^2+\lambda\lVert\widehat{\alpha}-\alpha_\lambda\rVert_2^2
&=\lVert T_P(\widehat{\alpha}-\alpha_P)\rVert_2^2+\lambda\lVert\widehat{\alpha}\rVert_2^2-\lVert T_P(\alpha_\lambda-\alpha_P)\rVert_2^2-\lambda\lVert\alpha_\lambda\rVert_2^2\\
&\overset{(a)}{=} \lVert T_P(\widehat{\alpha}-\alpha_P)\rVert_2^2+\lambda\lVert\widehat{\alpha}\rVert_2^2-\lVert T_P(\alpha_\lambda-\alpha_P)\rVert_2^2-\lambda\lVert\alpha_\lambda\rVert_2^2\\
&\overset{(b)}{\le}2\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+7\lVert g_P^\dagger-\widehat{g}\rVert_2^2+\frac{5}{2}\delta_n^2\\
&\qquad+\lambda(\mathbb{E}-\mathbb{E}_n)\left[\widehat{\alpha}(X)^2-\alpha_\lambda(X)^2\right]+\delta_n\lVert\widetilde{g}\rVert_2^2+\frac{1}{4}\lVert T_P(\alpha_\lambda-\widehat{\alpha})\rVert_2^2\\
&\overset{(c)}{\le}2\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+7\lVert g_P^\dagger-\widehat{g}\rVert_2^2+\frac{9}{2}\delta_n^2\\
&\qquad+\lambda(\mathbb{E}-\mathbb{E}_n)\left[\widehat{\alpha}(X)^2-\alpha_\lambda(X)^2\right]+\frac{1}{8}\lVert T_P(\alpha_P-\widehat{\alpha})\rVert_2^2+\frac{1}{4}\lVert T_P(\alpha_\lambda-\widehat{\alpha})\rVert_2^2\\
&\overset{(d)}{\le}\frac{9}{4}\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+7\lVert g_P^\dagger-\widehat{g}\rVert_2^2+\frac{9}{2}\delta_n^2\\
&\qquad+\lambda(\mathbb{E}-\mathbb{E}_n)\left[\widehat{\alpha}(X)^2-\alpha_\lambda(X)^2\right]+\frac{1}{2}\lVert T_P(\alpha_\lambda-\widehat{\alpha})\rVert_2^2,
\end{aligned} ∥ T P ( α − α λ ) ∥ 2 2 + λ ∥ α − α λ ∥ 2 2 = ∥ T P ( α − α P ) ∥ 2 2 + λ ∥ α ∥ 2 2 − ∥ T P ( α λ − α P ) ∥ 2 2 − λ ∥ α λ ∥ 2 2 = ( a ) ∥ T P ( α − α P ) ∥ 2 2 + λ ∥ α ∥ 2 2 − ∥ T P ( α λ − α P ) ∥ 2 2 − λ ∥ α λ ∥ 2 2 ≤ ( b ) 2 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ∥ 2 2 + 2 5 δ n 2 + λ ( E − E n ) [ α ( X ) 2 − α λ ( X ) 2 ] + δ n ∥ g ∥ 2 2 + 4 1 ∥ T P ( α λ − α ) ∥ 2 2 ≤ ( c ) 2 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ∥ 2 2 + 2 9 δ n 2 + λ ( E − E n ) [ α ( X ) 2 − α λ ( X ) 2 ] + 8 1 ∥ T P ( α P − α ) ∥ 2 2 + 4 1 ∥ T P ( α λ − α ) ∥ 2 2 ≤ ( d ) 4 9 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ∥ 2 2 + 2 9 δ n 2 + λ ( E − E n ) [ α ( X ) 2 − α λ ( X ) 2 ] + 2 1 ∥ T P ( α λ − α ) ∥ 2 2 , where in the above derivations, we apply the identity (33) for α ^ \hat{\alpha} α ^ (40) in (b), we complete the square in (c) to write
δ n ∥ g ~ ∥ 2 ≤ 1 8 ∥ T P ( α P − α ^ ) ∥ 2 2 + 2 δ n 2 , \delta_n \lVert\tilde{g}\rVert_2 \le\frac{1}{8}\lVert T_P(\alpha_P-\hat{\alpha})\rVert_2^2+2\delta_n^2, δ n ∥ g ~ ∥ 2 ≤ 8 1 ∥ T P ( α P − α ^ ) ∥ 2 2 + 2 δ n 2 , and we apply the triangular inequality to ∥ T P ( α P − α ^ ) ∥ 2 2 \lVert T_P(\alpha_P-\hat{\alpha})\rVert_2^2 ∥ T P ( α P − α ^ ) ∥ 2 2 (32) with α ^ \hat{\alpha} α ^ E \mathcal{E} E
( E n − E ) [ α λ ( X ) 2 − α ^ ( X ) 2 ] ≤ δ n ∥ α λ − α ^ ∥ 2 + δ n 2 ≤ δ n 2 2 + 1 2 ∥ α λ − α ^ ∥ 2 2 + δ n 2 . (\mathbb{E}_n-\mathbb{E})\left[\alpha_\lambda(X)^2-\hat{\alpha}(X)^2\right]\le\delta_n\lVert\alpha_\lambda-\hat{\alpha}\rVert_2+\delta_n^2\le\frac{\delta_n^2}{2}+\frac{1}{2}\lVert\alpha_\lambda-\hat{\alpha}\rVert_2^2+\delta_n^2. ( E n − E ) [ α λ ( X ) 2 − α ^ ( X ) 2 ] ≤ δ n ∥ α λ − α ^ ∥ 2 + δ n 2 ≤ 2 δ n 2 + 2 1 ∥ α λ − α ^ ∥ 2 2 + δ n 2 . Hence on E \mathcal{E} E
∥ T P ( α ^ − α λ ) ∥ 2 2 + λ ∥ α ^ − α λ ∥ 2 2 ≤ 9 4 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ^ ∥ 2 2 + 9 2 δ n 2 + λ 2 δ n 2 + λ 2 ∥ α λ − α ^ ∥ 2 2 + λ δ n 2 + 1 2 ∥ T P ( α λ − α ^ ) ∥ 2 2 . \begin{aligned}
\lVert T_P(\hat{\alpha}-\alpha_\lambda)\rVert_2^2+\lambda\lVert\hat{\alpha}-\alpha_\lambda\rVert_2^2 \\
&\le\frac{9}{4}\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+7\lVert g_P^\dagger-\hat{g}\rVert_2^2+\frac{9}{2}\delta_n^2 \\
&+\frac{\lambda}{2}\delta_n^2+\frac{\lambda}{2}\lVert\alpha_\lambda-\hat{\alpha}\rVert_2^2+\lambda\delta_n^2+\frac{1}{2}\lVert T_P(\alpha_\lambda-\hat{\alpha})\rVert_2^2.
\end{aligned} ∥ T P ( α ^ − α λ ) ∥ 2 2 + λ ∥ α ^ − α λ ∥ 2 2 ≤ 4 9 ∥ T P ( α P − α λ ) ∥ 2 2 + 7 ∥ g P † − g ^ ∥ 2 2 + 2 9 δ n 2 + 2 λ δ n 2 + 2 λ ∥ α λ − α ^ ∥ 2 2 + λ δ n 2 + 2 1 ∥ T P ( α λ − α ^ ) ∥ 2 2 . Rearranging and using λ ≤ 1 \lambda\le1 λ ≤ 1
∥ T P ( α ^ − α λ ) ∥ 2 2 + λ ∥ α ^ − α λ ∥ 2 2 ≤ 9 2 ∥ T P ( α P − α λ ) ∥ 2 2 + 14 ∥ g P † − g ^ ∥ 2 2 + 12 δ n 2 . \lVert T_P(\hat{\alpha}-\alpha_\lambda)\rVert_2^2+\lambda\lVert\hat{\alpha}-\alpha_\lambda\rVert_2^2\le\frac{9}{2}\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+14\lVert g_P^\dagger-\hat{g}\rVert_2^2+12\delta_n^2. ∥ T P ( α ^ − α λ ) ∥ 2 2 + λ ∥ α ^ − α λ ∥ 2 2 ≤ 2 9 ∥ T P ( α P − α λ ) ∥ 2 2 + 14 ∥ g P † − g ^ ∥ 2 2 + 12 δ n 2 . By Lemma 5, we have on E \mathcal{E} E
∥ T P ( α ^ − α P ) ∥ 2 2 ≤ 20 ∥ T P ( α P − α λ ) ∥ 2 2 + 28 ∥ g P † − g ^ ∥ 2 2 + 24 δ n 2 = O ( λ + δ n 2 + ∥ g P † − g ^ ∥ 2 2 ) . \begin{aligned}
\lVert T_P(\hat{\alpha}-\alpha_P)\rVert_2^2\le20\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+28\lVert g_P^\dagger-\hat{g}\rVert_2^2+24\delta_n^2 \\
&=O\left(\lambda+\delta_n^2+\lVert g_P^\dagger-\hat{g}\rVert_2^2\right).
\end{aligned} ∥ T P ( α ^ − α P ) ∥ 2 2 ≤ 20 ∥ T P ( α P − α λ ) ∥ 2 2 + 28 ∥ g P † − g ^ ∥ 2 2 + 24 δ n 2 = O ( λ + δ n 2 + ∥ g P † − g ^ ∥ 2 2 ) . We also have
∥ α ^ − α P ∥ 2 2 ≤ 2 ∥ α λ − α P ∥ 2 2 + 2 λ { 9 ∥ T P ( α P − α λ ) ∥ 2 2 + 14 ∥ g P † − g ^ ∥ 2 2 + 12 δ n 2 } . \lVert\hat{\alpha}-\alpha_P\rVert_2^2\le2\lVert\alpha_\lambda-\alpha_P\rVert_2^2+\frac{2}{\lambda}\left\{9\lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2+14\lVert g_P^\dagger-\hat{g}\rVert_2^2+12\delta_n^2\right\}. ∥ α ^ − α P ∥ 2 2 ≤ 2 ∥ α λ − α P ∥ 2 2 + λ 2 { 9 ∥ T P ( α P − α λ ) ∥ 2 2 + 14 ∥ g P † − g ^ ∥ 2 2 + 12 δ n 2 } . Since ∥ T P ( α P − α λ ) ∥ 2 2 = o ( λ ) \lVert T_P(\alpha_P-\alpha_\lambda)\rVert_2^2=o(\lambda) ∥ T P ( α P − α λ ) ∥ 2 2 = o ( λ ) ∥ α λ − α P ∥ 2 2 = o ( 1 ) \lVert\alpha_\lambda-\alpha_P\rVert_2^2=o(1) ∥ α λ − α P ∥ 2 2 = o ( 1 ) o ( 1 ) o(1) o ( 1 )
2 λ { 14 ∥ g P † − g ^ ∥ 2 2 + 12 δ n 2 } = o ( 1 ) , \frac{2}{\lambda}\left\{14\lVert g_P^\dagger-\hat{g}\rVert_2^2+12\delta_n^2\right\}=o(1), λ 2 { 14 ∥ g P † − g ^ ∥ 2 2 + 12 δ n 2 } = o ( 1 ) , as n → ∞ n\to\infty n → ∞
Proofs for sub:learnersoforthogonalresiduals
Proof of Theorem 4. We define the shorthand
q 0 : = r P − T P h 1 q_0:=r_P-T_P h_1 q 0 := r P − T P h 1 q ^ : = r ^ ⊥ ( h 1 ) \hat{q}:=\hat{r}_{\perp}(h_1) q ^ := r ^ ⊥ ( h 1 ) ℓ q ( W ) : = q ( Z ) 2 − 2 { m ~ ( W ; q ) − h 1 ( X ) q ( Z ) } . \ell_q(W):=q(Z)^2-2\{\tilde{m}(W;q)-h_1(X)q(Z)\}. ℓ q ( W ) := q ( Z ) 2 − 2 { m ~ ( W ; q ) − h 1 ( X ) q ( Z )} . We have,
E P [ ℓ q ( W ) − ℓ q 0 ( W ) ] = E P [ q ( Z ) 2 − q 0 ( Z ) 2 − 2 { m ~ ( W ; q ) − h 1 ( X ) q ( Z ) } + 2 { m ~ ( W ; q 0 ) − h 1 ( X ) q 0 ( Z ) } ] = E P [ q ( Z ) 2 − q 0 ( Z ) 2 − 2 r P ( Z ) q ( Z ) + 2 r P ( Z ) q 0 ( Z ) + 2 h 1 ( X ) ( q ( Z ) − q 0 ( Z ) ) ] = E P [ q ( Z ) 2 − q 0 ( Z ) 2 − 2 q 0 ( Z ) q ( Z ) + 2 { r P ( Z ) − T P h 1 ( Z ) } q 0 ( Z ) ] = ∥ q − q 0 ∥ L 2 ( P Z ) 2 . \begin{aligned}
\mathbb{E}_{P}[\ell_q(W)-\ell_{q_0}(W)]
= \mathbb{E}_{P}\left[q(Z)^2-q_0(Z)^2-2\{\widetilde{m}(W;q)-h_1(X)q(Z)\}+2\{\widetilde{m}(W;q_0)-h_1(X)q_0(Z)\}\right] \\
&= \mathbb{E}_{P}\left[q(Z)^2-q_0(Z)^2-2r_P(Z)q(Z)+2r_P(Z)q_0(Z)+2h_1(X)(q(Z)-q_0(Z))\right] \\
&= \mathbb{E}_{P}\left[q(Z)^2-q_0(Z)^2-2q_0(Z)q(Z)+2\{r_P(Z)-T_P h_1(Z)\}q_0(Z)\right] \\
&= \lVert q-q_0\rVert_{L^2(P_Z)}^2.
\end{aligned} E P [ ℓ q ( W ) − ℓ q 0 ( W )] = E P [ q ( Z ) 2 − q 0 ( Z ) 2 − 2 { m ( W ; q ) − h 1 ( X ) q ( Z )} + 2 { m ( W ; q 0 ) − h 1 ( X ) q 0 ( Z )} ] = E P [ q ( Z ) 2 − q 0 ( Z ) 2 − 2 r P ( Z ) q ( Z ) + 2 r P ( Z ) q 0 ( Z ) + 2 h 1 ( X ) ( q ( Z ) − q 0 ( Z )) ] = E P [ q ( Z ) 2 − q 0 ( Z ) 2 − 2 q 0 ( Z ) q ( Z ) + 2 { r P ( Z ) − T P h 1 ( Z )} q 0 ( Z ) ] = ∥ q − q 0 ∥ L 2 ( P Z ) 2 . By (16) , r ^ ⊥ ( h 1 ) \widehat{r}_{\perp}(h_1) r ⊥ ( h 1 ) E n ℓ q ( W ) \mathbb{E}_n\ell_q(W) E n ℓ q ( W ) G r , n \mathcal{G}_{r,n} G r , n
q ^ = arg min q ∈ G r , n E n [ ℓ q ( W ) ] . \widehat{q}=\underset{q\in\mathcal{G}_{r,n}}{\operatorname{arg\,min}}\mathbb{E}_n[\ell_q(W)]. q = q ∈ G r , n arg min E n [ ℓ q ( W )] . Hence we have
∥ q ^ − q 0 ∥ L 2 ( P Z ) 2 = E P [ ℓ q ^ ( W ) − ℓ q 0 ( W ) ] = E n [ ℓ q ^ ( W ) − ℓ q 0 ( W ) ] + ( E P − E n ) [ ℓ q ^ ( W ) − ℓ q 0 ( W ) ] ≤ ∣ ( E P − E n ) [ ℓ q ^ ( W ) − ℓ q 0 ( W ) ] ∣ . \begin{aligned}
\lVert\widehat{q}-q_0\rVert_{L^2(P_Z)}^2
&=\mathbb{E}_{P}[\ell_{\widehat{q}}(W)-\ell_{q_0}(W)]\\
&=\mathbb{E}_n[\ell_{\widehat{q}}(W)-\ell_{q_0}(W)]+(\mathbb{E}_{P}-\mathbb{E}_n)[\ell_{\widehat{q}}(W)-\ell_{q_0}(W)]\\
&\leq\left|(\mathbb{E}_{P}-\mathbb{E}_n)[\ell_{\widehat{q}}(W)-\ell_{q_0}(W)]\right|.
\end{aligned} ∥ q − q 0 ∥ L 2 ( P Z ) 2 = E P [ ℓ q ( W ) − ℓ q 0 ( W )] = E n [ ℓ q ( W ) − ℓ q 0 ( W )] + ( E P − E n ) [ ℓ q ( W ) − ℓ q 0 ( W )] ≤ ∣ ( E P − E n ) [ ℓ q ( W ) − ℓ q 0 ( W )] ∣ . Thus it suffices to bound ∣ ( E P − E n ) [ ℓ q ^ ( W ) − ℓ q 0 ( W ) ] ∣ \left|(\mathbb{E}_{P}-\mathbb{E}_n)[\ell_{\widehat{q}}(W)-\ell_{q_0}(W)]\right| ∣ ( E P − E n ) [ ℓ q ( W ) − ℓ q 0 ( W )] ∣ q ( Z ) q(Z) q ( Z ) O ( 1 ) O(1) O ( 1 ) G r , n \mathcal{G}_{r,n} G r , n h 1 ( X ) h_1(X) h 1 ( X ) q ( Z ) 2 + 2 h 1 ( X ) q ( Z ) q(Z)^2+2h_1(X)q(Z) q ( Z ) 2 + 2 h 1 ( X ) q ( Z ) O ( 1 ) O(1) O ( 1 ) q ( Z ) q(Z) q ( Z )
∥ m ~ ( W ; q ) − m ~ ( W ; q 0 ) ∥ L 2 ( P ) ≲ ∥ q − q 0 ∥ L 2 ( P Z ) . \lVert\widetilde{m}(W;q)-\widetilde{m}(W;q_0)\rVert_{L^2(P)}\lesssim\lVert q-q_0\rVert_{L^2(P_Z)}. ∥ m ( W ; q ) − m ( W ; q 0 ) ∥ L 2 ( P ) ≲ ∥ q − q 0 ∥ L 2 ( P Z ) . Thus Lemma 8 gives, uniformly over q ∈ G r , n q\in\mathcal{G}_{r,n} q ∈ G r , n 1 − ζ 1-\zeta 1 − ζ
∣ ( E n − E P ) [ ℓ q ( W ) − ℓ q 0 ( W ) ] ∣ = O ( δ r ⊥ , n ∥ q − q 0 ∥ L 2 ( P Z ) + δ r ⊥ , n 2 ) . \left|(\mathbb{E}_n-\mathbb{E}_{P})[\ell_q(W)-\ell_{q_0}(W)]\right|=O\left(\delta_{r_\perp,n}\lVert q-q_0\rVert_{L^2(P_Z)}+\delta_{r_\perp,n}^2\right). ∣ ( E n − E P ) [ ℓ q ( W ) − ℓ q 0 ( W )] ∣ = O ( δ r ⊥ , n ∥ q − q 0 ∥ L 2 ( P Z ) + δ r ⊥ , n 2 ) . Setting q = q ^ q=\widehat{q} q = q ∥ q ^ − q 0 ∥ L 2 ( P Z ) \lVert\widehat{q}-q_0\rVert_{L^2(P_Z)} ∥ q − q 0 ∥ L 2 ( P Z )
∥ q ^ − q 0 ∥ L 2 ( P Z ) 2 ≤ ∣ ( E n − E P ) [ ℓ q ^ ( W ) − ℓ q 0 ( W ) ] ∣ = O ( δ r ⊥ , n ∥ q ^ − q 0 ∥ L 2 ( P Z ) + δ r ⊥ , n 2 ) . \lVert\widehat{q}-q_0\rVert_{L^2(P_Z)}^2\leq\left|(\mathbb{E}_n-\mathbb{E}_{P})[\ell_{\widehat{q}}(W)-\ell_{q_0}(W)]\right|=O\left(\delta_{r_\perp,n}\lVert\widehat{q}-q_0\rVert_{L^2(P_Z)}+\delta_{r_\perp,n}^2\right). ∥ q − q 0 ∥ L 2 ( P Z ) 2 ≤ ∣ ( E n − E P ) [ ℓ q ( W ) − ℓ q 0 ( W )] ∣ = O ( δ r ⊥ , n ∥ q − q 0 ∥ L 2 ( P Z ) + δ r ⊥ , n 2 ) . Solving this inequality yields
∥ r ^ ⊥ ( h 1 ) − ( r P − T P h 1 ) ∥ L 2 ( P Z ) 2 = O ( δ r ⊥ , n 2 ) . \lVert\widehat{r}_{\perp}(h_1)-(r_P-T_P h_1)\rVert_{L^2(P_Z)}^2=O(\delta_{r_\perp,n}^2). ∥ r ⊥ ( h 1 ) − ( r P − T P h 1 ) ∥ L 2 ( P Z ) 2 = O ( δ r ⊥ , n 2 ) . Proof of Corollary 1. We condition on the first-stage sample used to build h ^ ( λ h ) \widehat{h}(\lambda_h) h ( λ h )
∥ r ^ ⊥ ( h ^ ( λ h ) ) − { r P − T P h ^ ( λ h ) } ∥ L 2 ( P Z ) 2 = O p ( δ r ⊥ , n 2 ) . \lVert\widehat{r}_{\perp}(\widehat{h}(\lambda_h))-\{r_P-T_P\widehat{h}(\lambda_h)\}\rVert_{L^2(P_Z)}^2=O_p(\delta_{r_\perp,n}^2). ∥ r ⊥ ( h ( λ h )) − { r P − T P h ( λ h )} ∥ L 2 ( P Z ) 2 = O p ( δ r ⊥ , n 2 ) . Since r P , ⊥ = r P − T P h P † r_{P,\perp}=r_P-T_P h_P^\dagger r P , ⊥ = r P − T P h P †
∥ T P ( h ^ ( λ h ) − h P † ) ∥ L 2 ( P Z ) 2 = O p ( δ h , n 2 + λ h min { β h + 1 , 2 } ) . \lVert T_P(\widehat{h}(\lambda_h)-h_P^\dagger)\rVert_{L^2(P_Z)}^2=O_p\left(\delta_{h,n}^2+\lambda_h^{\min\{\beta_h+1,2\}}\right). ∥ T P ( h ( λ h ) − h P † ) ∥ L 2 ( P Z ) 2 = O p ( δ h , n 2 + λ h m i n { β h + 1 , 2 } ) . The result follows from applying the triangle inequality and then marginalizing over the first-stage sample.
Notation. For a vector-valued class F ⊆ { f : X → R d } \mathcal{F} \subseteq\{f : \mathcal{X} \to\mathbb{R}^{d}\} F ⊆ { f : X → R d }
F ∣ t : = { f t : f ∈ F } , t = 1 , … , d , \mathcal{F}_{\mid t} := \{f_t : f \in\mathcal{F}\}, \qquad t = 1,\ldots,d, F ∣ t := { f t : f ∈ F } , t = 1 , … , d , where f t f_t f t t t t f f f f : X → R d f : \mathcal{X} \to\mathbb{R}^{d} f : X → R d
∥ f ∥ 2 , 2 : = ( E ∥ f ( X ) ∥ 2 2 ) 1 / 2 . \|f\|_{2,2} := \left(\mathbb{E}\|f(X)\|_{2}^{2}\right)^{1/2}. ∥ f ∥ 2 , 2 := ( E ∥ f ( X ) ∥ 2 2 ) 1/2 . For a scalar class A \mathcal{A} A
star ( A ) : = { t a : a ∈ A , 0 ≤ t ≤ 1 } , A − a ⋆ : = { a − a ⋆ : a ∈ A } . \operatorname{star}(\mathcal{A}) := \{ta : a \in\mathcal{A},\ 0 \leq t \leq1\}, \qquad\mathcal{A} - a^{\star} := \{a-a^{\star} : a \in\mathcal{A}\}. star ( A ) := { t a : a ∈ A , 0 ≤ t ≤ 1 } , A − a ⋆ := { a − a ⋆ : a ∈ A } . We write R ( A , r ) \mathcal{R}(\mathcal{A},r) R ( A , r ) n n n [22 ] .
Lemma 8 (Localized concentration). Consider a function class F \mathcal{F} F sup f ∈ F ∥ f ∥ ∞ ≤ 1 \sup_{f\in\mathcal{F}}\|f\|_{\infty} \leq1 sup f ∈ F ∥ f ∥ ∞ ≤ 1 f ⋆ ∈ F f^{\star} \in\mathcal{F} f ⋆ ∈ F δ n 2 ≥ 4 d log ( 41 log ( 2 c 2 n ) ) c 2 n \delta_n^2 \geq\frac{4d\log(41\log(2c_2n))}{c_2n} δ n 2 ≥ c 2 n 4 d l o g ( 41 l o g ( 2 c 2 n ))
∀ t ∈ { 1 , … , d } : R ( star ( F ∣ t − f t ⋆ ) , δ ) ≤ δ 2 . (41) \forall t \in\{1,\ldots,d\} : \mathcal{R}(\operatorname{star}(\mathcal{F}_{\mid t}-f_t^{\star}),\delta) \leq\delta^2. \tag*{(41)} ∀ t ∈ { 1 , … , d } : R ( star ( F ∣ t − f t ⋆ ) , δ ) ≤ δ 2 . (41) Moreover, assume that the loss ℓ \ell ℓ L L L ℓ 2 \ell_2 ℓ 2 c 5 , c 6 c_5,c_6 c 5 , c 6 1 − c 5 exp ( − c 6 n δ n 2 ) 1-c_5\exp(-c_6n\delta_n^2) 1 − c 5 exp ( − c 6 n δ n 2 )
∣ P n ( L f − L f ⋆ ) − P ( L f − L f ⋆ ) ∣ ≤ 18 L d δ n { ∥ f − f ⋆ ∥ 2 , 2 + δ n } , ∀ f ∈ F . (42) \left|\mathbb{P}_n(\mathcal{L}_f-\mathcal{L}_{f^{\star}})-\mathbb{P}(\mathcal{L}_f-\mathcal{L}_{f^{\star}})\right| \leq18Ld\delta_n\{\|f-f^{\star}\|_{2,2}+\delta_n\}, \qquad\forall f \in\mathcal{F}. \tag*{(42)} ∣ P n ( L f − L f ⋆ ) − P ( L f − L f ⋆ ) ∣ ≤ 18 L d δ n { ∥ f − f ⋆ ∥ 2 , 2 + δ n } , ∀ f ∈ F . (42) Proofs for debiased inference
Empirical process notations. Let P n P_n P n I 4 \mathcal{I}_4 I 4 Ψ ^ \widehat{\Psi} Ψ f : E W → R f : \mathcal{E}_W \to\mathbb{R} f : E W → R
P n f : = 1 n ∑ w i ∈ I 4 f ( w i ) P_n f := \frac{1}{n}\sum_{w_i\in\mathcal{I}_4} f(w_i) P n f := n 1 w i ∈ I 4 ∑ f ( w i ) P f : = ∫ f ( w ) P ( d w ) . P f := \int f(w)\,P(dw). P f := ∫ f ( w ) P ( d w ) . Proof of Theorem 5. Recall Ψ ^ \widehat{\Psi} Ψ (18)
Ψ ^ = 1 n ∑ i ∈ I 4 χ ( W i ; η ^ ) = P n { χ ( ⋅ ; η ^ ) } = ( P n − P ) { χ ( ⋅ ; η ^ ) } + P { χ ( ⋅ ; η ^ ) } = ( P n − P ) { χ ( ⋅ ; η ^ ) − χ P } + ( P n − P ) { χ P } + P { χ ( ⋅ ; η ^ ) } , \begin{aligned}
\widehat{\Psi} = \frac{1}{n}\sum_{i\in\mathcal{I}_4}\chi(W_i;\widehat{\eta}) \\
&= P_n\{\chi(\cdot;\widehat{\eta})\} \\
&= (P_n-P)\{\chi(\cdot;\widehat{\eta})\}+P\{\chi(\cdot;\widehat{\eta})\} \\
&= (P_n-P)\{\chi(\cdot;\widehat{\eta})-\chi_P\}+(P_n-P)\{\chi_P\}+P\{\chi(\cdot;\widehat{\eta})\},
\end{aligned} Ψ = n 1 i ∈ I 4 ∑ χ ( W i ; η ) = P n { χ ( ⋅ ; η )} = ( P n − P ) { χ ( ⋅ ; η )} + P { χ ( ⋅ ; η )} = ( P n − P ) { χ ( ⋅ ; η ) − χ P } + ( P n − P ) { χ P } + P { χ ( ⋅ ; η )} , where χ P \chi_P χ P (20) . We therefore have the algebraic expansion
n ( Ψ ^ − Ψ ( P ) ) = n ( P n − P ) { χ P } \sqrt{n}(\widehat{\Psi}-\Psi(P))=\sqrt{n}(P_n-P)\{\chi_P\} n ( Ψ − Ψ ( P )) = n ( P n − P ) { χ P } + n ( P n − P ) { χ ( ⋅ ; η ^ ) − χ P } \qquad+\sqrt{n}(P_n-P)\{\chi(\cdot;\widehat{\eta})-\chi_P\} + n ( P n − P ) { χ ( ⋅ ; η ) − χ P } + n ( P { χ ( ⋅ ; η ^ ) } − Ψ ( P ) ) . \qquad+\sqrt{n}\left(P\{\chi(\cdot;\widehat{\eta})\}-\Psi(P)\right). + n ( P { χ ( ⋅ ; η )} − Ψ ( P ) ) . Since χ P ( w ) = φ P ( w ) + Ψ ( P ) \chi_P(w)=\varphi_P(w)+\Psi(P) χ P ( w ) = φ P ( w ) + Ψ ( P ) E P [ χ P ( W ) ] = Ψ ( P ) \mathbb{E}_P[\chi_P(W)]=\Psi(P) E P [ χ P ( W )] = Ψ ( P )
( I F ) = n ( 1 n ∑ i ∈ I 4 φ P ( W i ) ) . (\mathrm{IF})=\sqrt{n}\left(\frac{1}{n}\sum_{i\in\mathcal{I}_4}\varphi_P(W_i)\right). ( IF ) = n ( n 1 i ∈ I 4 ∑ φ P ( W i ) ) . We will leave ( I F ) (\mathrm{IF}) ( IF ) ( E Q ) (\mathrm{EQ}) ( EQ ) I 4 \mathcal{I}_4 I 4 I 1 , I 2 , I 3 \mathcal{I}_1,\mathcal{I}_2,\mathcal{I}_3 I 1 , I 2 , I 3 [20 ] . By independence, the expectation over the samples in I 4 \mathcal{I}_4 I 4 I 4 \mathcal{I}_4 I 4 I 1 , I 2 , I 3 \mathcal{I}_1,\mathcal{I}_2,\mathcal{I}_3 I 1 , I 2 , I 3 E I 4 \mathbb{E}_{\mathcal{I}_4} E I 4
E I 4 [ ( ( P n − P ) { χ ( ⋅ ; η ^ ) − χ P } ) 2 ] = 1 n Var P { χ ( W ; η ^ ) − χ P ( W ) } ≤ 1 n E W [ ( χ ( W ; η ^ ) − χ P ( W ) ) 2 ] . \mathbb{E}_{\mathcal{I}_4}\left[\left((P_n-P)\{\chi(\cdot;\widehat{\eta})-\chi_P\}\right)^2\right]=\frac{1}{n}\operatorname{Var}_P\{\chi(W;\widehat{\eta})-\chi_P(W)\}\leq\frac{1}{n}\mathbb{E}_W\left[\left(\chi(W;\widehat{\eta})-\chi_P(W)\right)^2\right]. E I 4 [ ( ( P n − P ) { χ ( ⋅ ; η ) − χ P } ) 2 ] = n 1 Var P { χ ( W ; η ) − χ P ( W )} ≤ n 1 E W [ ( χ ( W ; η ) − χ P ( W ) ) 2 ] . Thus conditional Chebyshev inequality gives, for every ϵ > 0 \epsilon>0 ϵ > 0
P ( ∣ n ( P n − P ) { χ ( ⋅ ; η ^ ) − χ P } ∣ > ϵ ∣ η ^ ) ≤ E W [ ( χ ( W ; η ^ ) − χ P ( W ) ) 2 ] ϵ 2 . (43) \mathbb{P}\left(\left|\sqrt{n}(P_n-P)\{\chi(\cdot;\widehat{\eta})-\chi_P\}\right|>\epsilon\mid\widehat{\eta}\right)\leq\frac{\mathbb{E}_W\left[\left(\chi(W;\widehat{\eta})-\chi_P(W)\right)^2\right]}{\epsilon^2}. \tag*{(43)} P ( n ( P n − P ) { χ ( ⋅ ; η ) − χ P } > ϵ ∣ η ) ≤ ϵ 2 E W [ ( χ ( W ; η ) − χ P ( W ) ) 2 ] . (43) We have
χ ( w ; η ^ ) − χ P = m ( w ; h ^ ) + m ~ ( w ; g ^ ) − h ^ ( x ) g ^ ( z ) + r ^ ⊥ ( z ) { α ^ h ( x ) − g ^ ( z ) } + a ^ ⊥ ( x ) { α ^ g ( z ) − h ^ ( x ) } − m ( w ; h P † ) − m ~ ( w ; g P † ) + h P † ( x ) g P † ( z ) − r P , ⊥ ( z ) { α P h , † ( x ) − g P † ( z ) } − a P , ⊥ ( x ) { α P g , † ( z ) − h P † ( x ) } . \begin{aligned}
\chi(w;\widehat{\eta})-\chi_P
={}&m(w;\widehat{h})+\widetilde{m}(w;\widehat{g})-\widehat{h}(x)\widehat{g}(z)+\widehat{r}_{\perp}(z)\{\widehat{\alpha}^{h}(x)-\widehat{g}(z)\}+\widehat{a}_{\perp}(x)\{\widehat{\alpha}^{g}(z)-\widehat{h}(x)\}\\
&-m(w;h_P^\dagger)-\widetilde{m}(w;g_P^\dagger)+h_P^\dagger(x)g_P^\dagger(z)-r_{P,\perp}(z)\{\alpha_P^{h,\dagger}(x)-g_P^\dagger(z)\}-a_{P,\perp}(x)\{\alpha_P^{g,\dagger}(z)-h_P^\dagger(x)\}.
\end{aligned} χ ( w ; η ) − χ P = m ( w ; h ) + m ( w ; g ) − h ( x ) g ( z ) + r ⊥ ( z ) { α h ( x ) − g ( z )} + a ⊥ ( x ) { α g ( z ) − h ( x )} − m ( w ; h P † ) − m ( w ; g P † ) + h P † ( x ) g P † ( z ) − r P , ⊥ ( z ) { α P h , † ( x ) − g P † ( z )} − a P , ⊥ ( x ) { α P g , † ( z ) − h P † ( x )} . We have, by the above identity and triangle inequality,
E W [ ( χ ( W ; η ^ ) − χ P ( W ) ) 2 ] ≤ 5 E W [ ( m ( W ; h ^ ) − m ( W ; h P † ) ) 2 ] + 5 E W [ ( m ~ ( W ; g ^ ) − m ~ ( W ; g P † ) ) 2 ] . (44) \mathbb{E}_W\left[\left(\chi(W;\widehat{\eta})-\chi_P(W)\right)^2\right]
\leq5\mathbb{E}_W\left[\left(m(W;\widehat{h})-m(W;h_P^\dagger)\right)^2\right]+5\mathbb{E}_W\left[\left(\widetilde{m}(W;\widehat{g})-\widetilde{m}(W;g_P^\dagger)\right)^2\right]. \tag*{(44)} E W [ ( χ ( W ; η ) − χ P ( W ) ) 2 ] ≤ 5 E W [ ( m ( W ; h ) − m ( W ; h P † ) ) 2 ] + 5 E W [ ( m ( W ; g ) − m ( W ; g P † ) ) 2 ] . (44) + 5 E W [ ( h ^ ( X ) g ^ ( Z ) − h P † ( X ) g P † ( Z ) ) 2 ] (45) +5\mathbb{E}_W\left[\left(\widehat{h}(X)\widehat{g}(Z)-h_P^\dagger(X)g_P^\dagger(Z)\right)^2\right] \tag*{(45)} + 5 E W [ ( h ( X ) g ( Z ) − h P † ( X ) g P † ( Z ) ) 2 ] (45) + 5 E W [ ( r ^ ⊥ ( Z ) { α ^ h ( X ) − g ^ ( Z ) } − r P , ⊥ ( Z ) { α P h , † ( X ) − g P † ( Z ) } ) 2 ] (46) +5\mathbb{E}_W\left[\left(\widehat{r}_{\perp}(Z)\{\widehat{\alpha}^{h}(X)-\widehat{g}(Z)\}-r_{P,\perp}(Z)\{\alpha_P^{h,\dagger}(X)-g_P^\dagger(Z)\}\right)^2\right] \tag*{(46)} + 5 E W [ ( r ⊥ ( Z ) { α h ( X ) − g ( Z )} − r P , ⊥ ( Z ) { α P h , † ( X ) − g P † ( Z )} ) 2 ] (46) + 5 E W [ ( a ^ ⊥ ( X ) { α ^ g ( Z ) − h ^ ( X ) } − a P , ⊥ ( X ) { α P g , † ( Z ) − h P † ( X ) } ) 2 ] . (47) +5\mathbb{E}_W\left[\left(\widehat{a}_{\perp}(X)\{\widehat{\alpha}^{g}(Z)-\widehat{h}(X)\}-a_{P,\perp}(X)\{\alpha_P^{g,\dagger}(Z)-h_P^\dagger(X)\}\right)^2\right]. \tag*{(47)} + 5 E W [ ( a ⊥ ( X ) { α g ( Z ) − h ( X )} − a P , ⊥ ( X ) { α P g , † ( Z ) − h P † ( X )} ) 2 ] . (47) By linearity of m m m m ~ \widetilde{m} m
( A ) ≤ 5 C ∥ h ^ − h P † ∥ L 2 ( P X ) 2 + 5 C ∥ g ^ − g P † ∥ L 2 ( P Z ) 2 = 5 C ( e h s ) 2 + 5 C ( e g s ) 2 . \begin{aligned}
(\mathrm{A})\leq5C\left\|\widehat{h}-h_P^\dagger\right\|_{L_2(P_X)}^2+5C\left\|\widehat{g}-g_P^\dagger\right\|_{L_2(P_Z)}^2 \\
&=5C(e_h^s)^2+5C(e_g^s)^2.
\end{aligned} ( A ) ≤ 5 C h − h P † L 2 ( P X ) 2 + 5 C g − g P † L 2 ( P Z ) 2 = 5 C ( e h s ) 2 + 5 C ( e g s ) 2 . We next use the identity a 1 b 1 − a 2 b 2 = a 2 ( b 1 − b 2 ) + b 1 ( a 1 − a 2 ) a_1b_1-a_2b_2=a_2(b_1-b_2)+b_1(a_1-a_2) a 1 b 1 − a 2 b 2 = a 2 ( b 1 − b 2 ) + b 1 ( a 1 − a 2 )
( a 1 b 1 − a 2 b 2 ) 2 ≤ 2 a 2 2 ( b 1 − b 2 ) 2 + 2 b 1 2 ( a 1 − a 2 ) 2 . (a_1b_1-a_2b_2)^2\leq2a_2^2(b_1-b_2)^2+2b_1^2(a_1-a_2)^2. ( a 1 b 1 − a 2 b 2 ) 2 ≤ 2 a 2 2 ( b 1 − b 2 ) 2 + 2 b 1 2 ( a 1 − a 2 ) 2 . We have
( B ) ≤ 10 ∥ h ^ ∥ L ∞ ( P X ) 2 ∥ g ^ − g P † ∥ L 2 ( P Z ) 2 + 10 ∥ g P † ∥ L ∞ ( P Z ) 2 ∥ h ^ − h P † ∥ L 2 ( P X ) 2 (\mathrm{B}) \le10\|\hat{h}\|_{L^\infty(P_X)}^2\|\hat{g}-g_P^\dagger\|_{L^2(P_Z)}^2+10\|g_P^\dagger\|_{L^\infty(P_Z)}^2\|\hat{h}-h_P^\dagger\|_{L^2(P_X)}^2 ( B ) ≤ 10∥ h ^ ∥ L ∞ ( P X ) 2 ∥ g ^ − g P † ∥ L 2 ( P Z ) 2 + 10∥ g P † ∥ L ∞ ( P Z ) 2 ∥ h ^ − h P † ∥ L 2 ( P X ) 2 ( C ) ≤ 20 ∥ r ^ ⊥ ∥ L ∞ ( P Z ) 2 ( ∥ α ^ h − α P h , † ∥ L 2 ( P X ) 2 + ∥ g ^ − g P † ∥ L 2 ( P Z ) 2 ) + 20 ( ∥ α P h , † ∥ L ∞ ( P X ) 2 + ∥ g P † ∥ L ∞ ( P Z ) 2 ) ∥ r ^ ⊥ − r P , ⊥ ∥ L 2 ( P Z ) 2 \begin{aligned}
(\mathrm{C}) \le{}&20\|\hat{r}_\perp\|_{L^\infty(P_Z)}^2\left(\|\hat{\alpha}^h-\alpha_P^{h,\dagger}\|_{L^2(P_X)}^2+\|\hat{g}-g_P^\dagger\|_{L^2(P_Z)}^2\right)\\
&+20\left(\|\alpha_P^{h,\dagger}\|_{L^\infty(P_X)}^2+\|g_P^\dagger\|_{L^\infty(P_Z)}^2\right)\|\hat{r}_\perp-r_{P,\perp}\|_{L^2(P_Z)}^2
\end{aligned} ( C ) ≤ 20∥ r ^ ⊥ ∥ L ∞ ( P Z ) 2 ( ∥ α ^ h − α P h , † ∥ L 2 ( P X ) 2 + ∥ g ^ − g P † ∥ L 2 ( P Z ) 2 ) + 20 ( ∥ α P h , † ∥ L ∞ ( P X ) 2 + ∥ g P † ∥ L ∞ ( P Z ) 2 ) ∥ r ^ ⊥ − r P , ⊥ ∥ L 2 ( P Z ) 2 ( D ) ≤ 20 ∥ a ^ ⊥ ∥ L ∞ ( P X ) 2 ( ∥ α ^ g − α P g , † ∥ L 2 ( P Z ) 2 + ∥ h ^ − h P † ∥ L 2 ( P X ) 2 ) + 20 ( ∥ α P g , † ∥ L ∞ ( P Z ) 2 + ∥ h P † ∥ L ∞ ( P X ) 2 ) ∥ a ^ ⊥ − a P , ⊥ ∥ L 2 ( P X ) 2 . \begin{aligned}
(\mathrm{D}) \le{}&20\|\hat{a}_\perp\|_{L^\infty(P_X)}^2\left(\|\hat{\alpha}^g-\alpha_P^{g,\dagger}\|_{L^2(P_Z)}^2+\|\hat{h}-h_P^\dagger\|_{L^2(P_X)}^2\right)\\
&+20\left(\|\alpha_P^{g,\dagger}\|_{L^\infty(P_Z)}^2+\|h_P^\dagger\|_{L^\infty(P_X)}^2\right)\|\hat{a}_\perp-a_{P,\perp}\|_{L^2(P_X)}^2.
\end{aligned} ( D ) ≤ 20∥ a ^ ⊥ ∥ L ∞ ( P X ) 2 ( ∥ α ^ g − α P g , † ∥ L 2 ( P Z ) 2 + ∥ h ^ − h P † ∥ L 2 ( P X ) 2 ) + 20 ( ∥ α P g , † ∥ L ∞ ( P Z ) 2 + ∥ h P † ∥ L ∞ ( P X ) 2 ) ∥ a ^ ⊥ − a P , ⊥ ∥ L 2 ( P X ) 2 . Under the assumption that there exists a large constant C > 0 C>0 C > 0
max { ∥ h ^ ∥ ∞ 2 , ∥ h P † ∥ ∞ 2 , ∥ g P † ∥ ∞ 2 , ∥ α P h , † ∥ ∞ 2 , ∥ α P g , † ∥ ∞ 2 , ∥ a ^ ⊥ ∥ ∞ 2 , ∥ r ^ ⊥ ∥ ∞ 2 } ≤ C , \max\left\{\|\hat{h}\|_\infty^2,\|h_P^\dagger\|_\infty^2,\|g_P^\dagger\|_\infty^2,\|\alpha_P^{h,\dagger}\|_\infty^2,\|\alpha_P^{g,\dagger}\|_\infty^2,\|\hat{a}_\perp\|_\infty^2,\|\hat{r}_\perp\|_\infty^2\right\}\le C, max { ∥ h ^ ∥ ∞ 2 , ∥ h P † ∥ ∞ 2 , ∥ g P † ∥ ∞ 2 , ∥ α P h , † ∥ ∞ 2 , ∥ α P g , † ∥ ∞ 2 , ∥ a ^ ⊥ ∥ ∞ 2 , ∥ r ^ ⊥ ∥ ∞ 2 } ≤ C , we have, upon redefining C C C
E W [ ( χ ( W ; η ^ ) − χ P ) 2 ] ≤ C { ( e h s ) 2 + ( e g s ) 2 + ( e α h s ) 2 + ( e α g s ) 2 + ( e r ⊥ s ) 2 + ( e a ⊥ s ) 2 } . \mathbb{E}_W\left[(\chi(W;\hat{\eta})-\chi_P)^2\right]\le C\left\{(e_h^s)^2+(e_g^s)^2+(e_{\alpha^h}^s)^2+(e_{\alpha^g}^s)^2+(e_{r_\perp}^s)^2+(e_{a_\perp}^s)^2\right\}. E W [ ( χ ( W ; η ^ ) − χ P ) 2 ] ≤ C { ( e h s ) 2 + ( e g s ) 2 + ( e α h s ) 2 + ( e α g s ) 2 + ( e r ⊥ s ) 2 + ( e a ⊥ s ) 2 } . As n → ∞ n\to\infty n → ∞ I 1 , I 2 , I 3 \mathcal{I}_1,\mathcal{I}_2,\mathcal{I}_3 I 1 , I 2 , I 3 δ > 0 \delta>0 δ > 0
B δ : = { E W [ ( χ ( W ; η ^ ) − χ P ( W ) ) 2 ] > δ } . B_\delta:=\left\{\mathbb{E}_W\left[(\chi(W;\hat{\eta})-\chi_P(W))^2\right]>\delta\right\}. B δ := { E W [ ( χ ( W ; η ^ ) − χ P ( W ) ) 2 ] > δ } . with respect to probability measure on samples I i \mathcal{I}_i I i i = 1 , 2 , 3 i=1,2,3 i = 1 , 2 , 3 1 B δ 1_{B_\delta} 1 B δ B δ B_\delta B δ ϵ > 0 \epsilon>0 ϵ > 0
P ( ∣ ( E Q ) ∣ ≥ ϵ ) = E [ P ( ∣ ( E Q ) ∣ > ϵ ∣ η ^ ) 1 B δ ] + E [ P ( ∣ ( E Q ) ∣ > ϵ ∣ η ^ ) ( 1 − 1 B δ ) ] ≤ P ( B δ ) + δ ϵ 2 , \begin{aligned}
P\left(\left|(\mathrm{EQ})\right|\ge\epsilon\right)=\mathbb{E}\left[P\left(\left|(\mathrm{EQ})\right|>\epsilon\mid\hat{\eta}\right)1_{B_\delta}\right]+\mathbb{E}\left[P\left(\left|(\mathrm{EQ})\right|>\epsilon\mid\hat{\eta}\right)(1-1_{B_\delta})\right] \\
&\le P(B_\delta)+\frac{\delta}{\epsilon^2},
\end{aligned} P ( ∣ ( EQ ) ∣ ≥ ϵ ) = E [ P ( ∣ ( EQ ) ∣ > ϵ ∣ η ^ ) 1 B δ ] + E [ P ( ∣ ( EQ ) ∣ > ϵ ∣ η ^ ) ( 1 − 1 B δ ) ] ≤ P ( B δ ) + ϵ 2 δ , where we apply (43) . We have shown that lim n → ∞ P ( B δ ) = 0 \lim_{n\to\infty}P(B_\delta)=0 lim n → ∞ P ( B δ ) = 0 δ \delta δ δ > 0 \delta>0 δ > 0
lim sup n → ∞ P ( ∣ ( E Q ) ∣ ≥ ϵ ) ≤ δ ϵ 2 . \limsup_{n\to\infty}P\left(\left|(\mathrm{EQ})\right|\ge\epsilon\right)\le\frac{\delta}{\epsilon^2}. n → ∞ lim sup P ( ∣ ( EQ ) ∣ ≥ ϵ ) ≤ ϵ 2 δ . Hence ∣ ( E Q ) ∣ = o p ( 1 ) |(\mathrm{EQ})|=o_p(1) ∣ ( EQ ) ∣ = o p ( 1 )
We bound ( R ) (R) ( R ) (13) , we have
n − 1 / 2 ∣ ( R ) ∣ ≤ ∣ ⟨ T P ( h ^ − h P † ) , g ^ − g P † ⟩ L 2 ( P Z ) ∣ + ∣ ⟨ T P α ^ h − g ^ , r ^ ⊥ − r P , ⊥ ⟩ L 2 ( P Z ) ∣ + ∣ ⟨ T P ∗ α ^ g − h ^ , a ^ ⊥ − a P , ⊥ ⟩ L 2 ( P X ) ∣ . \begin{aligned}
n^{-1/2}|(R)|\le{}&
\left|\left\langle T_P(\hat{h}-h_P^\dagger),\hat{g}-g_P^\dagger\right\rangle_{L^2(P_Z)}\right|\\
&+\left|\left\langle T_P\hat{\alpha}^h-\hat{g},\hat{r}_\perp-r_{P,\perp}\right\rangle_{L^2(P_Z)}\right|\\
&+\left|\left\langle T_P^*\hat{\alpha}^g-\hat{h},\hat{a}_\perp-a_{P,\perp}\right\rangle_{L^2(P_X)}\right|.
\end{aligned} n − 1/2 ∣ ( R ) ∣ ≤ ⟨ T P ( h ^ − h P † ) , g ^ − g P † ⟩ L 2 ( P Z ) + ⟨ T P α ^ h − g ^ , r ^ ⊥ − r P , ⊥ ⟩ L 2 ( P Z ) + ⟨ T P ∗ α ^ g − h ^ , a ^ ⊥ − a P , ⊥ ⟩ L 2 ( P X ) . The first term above is bounded by min { e g w e h s , e g s e h w } \min\{e_g^w e_h^s, e_g^s e_h^w\} min { e g w e h s , e g s e h w } T P α P h , t = g P t T_P\alpha_P^{h,t}=g_P^t T P α P h , t = g P t T P ∗ α P g , t = h P t T_P^*\alpha_P^{g,t}=h_P^t T P ∗ α P g , t = h P t
∥ T P α ^ h − g ^ ∥ L 2 ( P Z ) ≤ ∥ T P ( α ^ h − α P h , t ) ∥ L 2 ( P Z ) + ∥ g P t − g ^ ∥ L 2 ( P Z ) = e α h w + e g s , ∥ T P ∗ α ^ g − h ^ ∥ L 2 ( P X ) ≤ ∥ T P ∗ ( α ^ g − α P g , t ) ∥ L 2 ( P X ) + ∥ h P t − h ^ ∥ L 2 ( P X ) = e α g w + e h s . \begin{aligned}
\left\|T_P\widehat{\alpha}^h-\widehat{g}\right\|_{L^2(P_Z)} &\leq\left\|T_P(\widehat{\alpha}^h-\alpha_P^{h,t})\right\|_{L^2(P_Z)}+\left\|g_P^t-\widehat{g}\right\|_{L^2(P_Z)}=e_{\alpha h}^w+e_g^s,\\
\left\|T_P^*\widehat{\alpha}^g-\widehat{h}\right\|_{L^2(P_X)} &\leq\left\|T_P^*(\widehat{\alpha}^g-\alpha_P^{g,t})\right\|_{L^2(P_X)}+\left\|h_P^t-\widehat{h}\right\|_{L^2(P_X)}=e_{\alpha g}^w+e_h^s.
\end{aligned} T P α h − g L 2 ( P Z ) T P ∗ α g − h L 2 ( P X ) ≤ T P ( α h − α P h , t ) L 2 ( P Z ) + g P t − g L 2 ( P Z ) = e α h w + e g s , ≤ T P ∗ ( α g − α P g , t ) L 2 ( P X ) + h P t − h L 2 ( P X ) = e α g w + e h s . Recalling
e r ⊥ s = ∥ r ^ ⊥ − r P , ⊥ ∥ L 2 ( P Z ) , e a ⊥ s = ∥ a ^ ⊥ − a P , ⊥ ∥ L 2 ( P X ) , e_{r_\perp}^s=\left\|\widehat{r}_\perp-r_{P,\perp}\right\|_{L^2(P_Z)},\qquad e_{a_\perp}^s=\left\|\widehat{a}_\perp-a_{P,\perp}\right\|_{L^2(P_X)}, e r ⊥ s = ∥ r ⊥ − r P , ⊥ ∥ L 2 ( P Z ) , e a ⊥ s = ∥ a ⊥ − a P , ⊥ ∥ L 2 ( P X ) , we obtain by applying Cauchy-Schwarz inequality that
n − 1 2 ∣ ( R ) ∣ ≤ min { e g w e h s , e g s e h w } + ( e α h w + e g s ) e r ⊥ s + ( e α g w + e h s ) e a ⊥ s . n^{-\frac{1}{2}} |(R)|\leq\min\{e_g^w e_h^s,e_g^s e_h^w\}+(e_{\alpha h}^w+e_g^s)e_{r_\perp}^s+(e_{\alpha g}^w+e_h^s)e_{a_\perp}^s. n − 2 1 ∣ ( R ) ∣ ≤ min { e g w e h s , e g s e h w } + ( e α h w + e g s ) e r ⊥ s + ( e α g w + e h s ) e a ⊥ s . We further use (22) and (23) to conclude that
∣ ( R ) ∣ = o p ( 1 ) . |(R)|=o_p(1). ∣ ( R ) ∣ = o p ( 1 ) . Therefore we have shown that
∣ ( E Q ) + ( R ) ∣ = o p ( 1 ) (48) |(EQ)+(R)|=o_p(1) \tag*{(48)} ∣ ( E Q ) + ( R ) ∣ = o p ( 1 ) (48) under the Theorem’s assumptions. This yields the asymptotic linearity of our estimator Ψ ^ \widehat{\Psi} Ψ (24) . By assumption, σ P 2 = E P [ φ P ( W ) 2 ] < ∞ \sigma_P^2=\mathbb{E}_P[\varphi_P(W)^2]<\infty σ P 2 = E P [ φ P ( W ) 2 ] < ∞
( I F ) ⇝ N ( 0 , σ P 2 ) . (IF)\rightsquigarrow\mathcal{N}(0,\sigma_P^2). ( I F ) ⇝ N ( 0 , σ P 2 ) . We further have,
n ( Ψ ^ − Ψ ( P ) ) ⇝ N ( 0 , σ P 2 ) , \sqrt{n}\left(\widehat{\Psi}-\Psi(P)\right)\rightsquigarrow\mathcal{N}(0,\sigma_P^2), n ( Ψ − Ψ ( P ) ) ⇝ N ( 0 , σ P 2 ) , due to (48) and an application of Slutsky’s theorem.
It remains to show variance consistency. We have already shown that P { χ ( ⋅ ; η ^ ) − χ P } 2 = o p ( 1 ) P\{\chi(\cdot;\widehat{\eta})-\chi_P\}^2=o_p(1) P { χ ( ⋅ ; η ) − χ P } 2 = o p ( 1 ) η ^ \widehat{\eta} η
E I 4 [ 1 n ∑ i ∈ I 4 ( χ ( W i ; η ^ ) − χ P ( W i ) ) 2 ∣ η ^ ] = E W [ ( χ ( W ; η ^ ) − χ P ( W ) ) 2 ] = o p ( 1 ) . \mathbb{E}_{\mathcal{I}_4}\left[\left.\frac{1}{n}\sum_{i\in\mathcal{I}_4}\left(\chi(W_i;\widehat{\eta})-\chi_P(W_i)\right)^2\right|\widehat{\eta}\right]=\mathbb{E}_W\left[\left(\chi(W;\widehat{\eta})-\chi_P(W)\right)^2\right]=o_p(1). E I 4 [ n 1 i ∈ I 4 ∑ ( χ ( W i ; η ) − χ P ( W i ) ) 2 η ] = E W [ ( χ ( W ; η ) − χ P ( W ) ) 2 ] = o p ( 1 ) . Hence by Markov’s inequality,
P n { χ ( ⋅ ; η ^ ) − χ P } 2 = 1 n ∑ i ∈ I 4 ( χ ( W i ; η ^ ) − χ P ( W i ) ) 2 = o p ( 1 ) . P_n\{\chi(\cdot;\widehat{\eta})-\chi_P\}^2=\frac{1}{n}\sum_{i\in\mathcal{I}_4}\left(\chi(W_i;\widehat{\eta})-\chi_P(W_i)\right)^2=o_p(1). P n { χ ( ⋅ ; η ) − χ P } 2 = n 1 i ∈ I 4 ∑ ( χ ( W i ; η ) − χ P ( W i ) ) 2 = o p ( 1 ) . We apply the reverse triangle inequality with respect to the empirical L 2 ( P n ) L^2(P_n) L 2 ( P n )
∣ [ P n { χ ( ⋅ ; η ^ ) − P n χ ( ⋅ ; η ^ ) } 2 ] 1 / 2 − [ P n { χ P − P n χ P } 2 ] 1 / 2 ∣ = ∣ ∥ χ ( ⋅ ; η ^ ) − P n χ ( ⋅ ; η ^ ) ∥ L 2 ( P n ) − ∥ χ P − P n χ P ∥ L 2 ( P n ) ∣ ≤ ∥ χ ( ⋅ ; η ^ ) − χ P − P n { χ ( ⋅ ; η ^ ) − χ P } ∥ L 2 ( P n ) ≤ ∥ χ ( ⋅ ; η ^ ) − χ P ∥ L 2 ( P n ) = o p ( 1 ) , \begin{aligned}
\left|\left[P_n\{\chi(\cdot;\widehat{\eta})-P_n\chi(\cdot;\widehat{\eta})\}^2\right]^{1/2}-\left[P_n\{\chi_P-P_n\chi_P\}^2\right]^{1/2}\right|
&=\left|\|\chi(\cdot;\widehat{\eta})-P_n\chi(\cdot;\widehat{\eta})\|_{L^2(P_n)}-\|\chi_P-P_n\chi_P\|_{L^2(P_n)}\right|\\
&\leq\|\chi(\cdot;\widehat{\eta})-\chi_P-P_n\{\chi(\cdot;\widehat{\eta})-\chi_P\}\|_{L^2(P_n)}\\
&\leq\|\chi(\cdot;\widehat{\eta})-\chi_P\|_{L^2(P_n)}=o_p(1),
\end{aligned} [ P n { χ ( ⋅ ; η ) − P n χ ( ⋅ ; η ) } 2 ] 1/2 − [ P n { χ P − P n χ P } 2 ] 1/2 = ∥ χ ( ⋅ ; η ) − P n χ ( ⋅ ; η ) ∥ L 2 ( P n ) − ∥ χ P − P n χ P ∥ L 2 ( P n ) ≤ ∥ χ ( ⋅ ; η ) − χ P − P n { χ ( ⋅ ; η ) − χ P } ∥ L 2 ( P n ) ≤ ∥ χ ( ⋅ ; η ) − χ P ∥ L 2 ( P n ) = o p ( 1 ) , where the last inequality uses
P n { f − P n f } 2 = P n f 2 − ( P n f ) 2 ≤ P n f 2 . P_n\{f-P_nf\}^2 = P_nf^2-(P_nf)^2 \le P_nf^2. P n { f − P n f } 2 = P n f 2 − ( P n f ) 2 ≤ P n f 2 . Finally, since χ P ∈ L 2 ( P ) \chi_P \in L^2(P) χ P ∈ L 2 ( P ) P n χ P → p P χ P P_n\chi_P \to_p P\chi_P P n χ P → p P χ P P n χ P 2 → p P χ P 2 P_n\chi_P^2 \to_p P\chi_P^2 P n χ P 2 → p P χ P 2
P n { χ P − P n χ P } 2 = P n χ P 2 − ( P n χ P ) 2 → p P χ P 2 − ( P χ P ) 2 = σ P 2 . P_n\{\chi_P-P_n\chi_P\}^2 = P_n\chi_P^2-(P_n\chi_P)^2 \to_p P\chi_P^2-(P\chi_P)^2=\sigma_P^2. P n { χ P − P n χ P } 2 = P n χ P 2 − ( P n χ P ) 2 → p P χ P 2 − ( P χ P ) 2 = σ P 2 . Hence we have proved σ ^ → p σ P \widehat{\sigma} \to_p \sigma_P σ → p σ P
