text:
\section{Applications}

\label{sec:applications}
\label{SEC:APPLICATIONS}
We apply the proposed $M$-estimation framework
to three classes of problems: General Moment Problems with Missing Data, Games of Incomplete Information, and Treatment Effects in presence of a  Nonlinear Link Function. We present simulation evidence of the performance of our estimators in each application in the Supplementary Material.

\subsection{Nonlinear Treatment Effects }
\label{sec:nonlinearTE}
\label{SEC:NONLINEARTE}

Consider the following model of Nonlinear Treatment Effects:
\begin{align}
\label{eq:nonlinearTE}
    \mathbb{E} \left[  G(x '\theta_0 + f_0(u))-y | x,u \right] &= 0,
\end{align}
where
$x\in \mathbb{R}^p$ is a high-dimensional treatment vector, $u \in \mathcal{U}$ is a control vector that
affects the outcome $y$ through a composition of a partially linear index $x'\theta_0 + f_0(u)$ and a  nonlinear known monotonically increasing link function $G:\mathbb{R} \rightarrow \mathbb{R}$.

We represent $\theta_0$ as a solution to an orthogonal CMR. Let $h(u) = \mathbb{E}[x|u]$ be the $p$-vector Conditional Expectation Function of $x$. Let $q(u):=h(u)'\theta_0+f_0(u)=\mathbb{E} \big[ G^{-1} (\mathbb{E} [y|x,u])| u\big]$ be the Conditional Expectation Function of $G^{-1} (\mathbb{E} [y|x,u])$. Let $V_0(z)=G'(x'\theta_0 + f_0(u))$ be the derivative of the link function. The orthogonal CMR takes the form
\begin{align}
    m(w,\Lambda(z,g(z))'\theta, g(z)):= \frac{1}{V(z)}(G(\Lambda(z,g(z))'\theta + q(u)) - y),
\end{align}
where $z=(x; u)$, $g(z)=\{h(u), q(u), V(z)\}$ and $\Lambda(z, g(z)) = x-h(u)$. The orthogonal loss function $\ell(w,t,g)$ is taken to be an arbitrary solution to the following ODE:
\begin{align}
\label{eq:nonlinearTEODE}
\frac{\partial}{\partial t}\ell(w,t,g(z)) = \frac{G(t) - y}{V(z)}
,\;t \in \mathbb{R}.
\end{align}

Now we can apply Theorem~\ref{cor:non-ortho-rate} to get a convergence rate result.

\begin{corollary}[Orthogonal Estimation of Non-linear Treatment Effects]
\label{cor:non-linear-te}

Suppose the following conditions hold.
\begin{enumerate}
    \item \label{itm:nonlinear:rate} W.p. $1-\delta$, the estimator $\widehat{g}=(\widehat{h},\widehat{q},\widehat{V}) \in {\mathcal G}_{n,\delta}={\mathcal H}_{n,\delta} \bigtimes {\mathcal Q}_{n,\delta} \bigtimes V_{n,\delta} $ satisfies Assumption \ref{ass:nuisance} with $g_{n,\delta}$ rate in $\ell_{\infty}$ norm.

    \item \label{itm:nonlinear:smooth} The functions $t \rightarrow G(t), G'(t), G^{(2)}(t), G^{3}(t)$ are $U$-bounded on the index space ${\mathcal I}:=\{(x-h(z))'\theta + q(u): \theta \in \Theta, \{h, q, V\}\in {\mathcal G}_n, w\in \mathcal W\}$. In addition,  $\inf_{t\in {\mathcal I}} G'(t) \geq \nu>0$ on the index space ${\mathcal I}$.
    \item  \label{itm:nonlinear:ide} There exists $\gamma_{\text{TE}}>0$ and $\nu>0$ such that covariance matrix \begin{equation}
    \Sigma_{\text{TE}} := \mathbb{E}[(x-h_0(z))\, (x-h_0(z))'] \geq \gamma_{\text{TE}} I, ~~~~~~~ \gamma_{\text{TE}} >0.
\end{equation}

\end{enumerate}
In addition, suppose $\sup_{\theta \in \Theta}\|\theta\|_0 \leq k=o\left(\left(\frac{n}{\log(p/\delta)}\right)^{1/4}\right)$, $k g_{n,\delta}=o(1)$ and  $\| \theta_0\|_{\infty} \leq U$. Then the estimate of Algorithm~\ref{def:lasso:intro} with $M$-estimator loss defined in Equation \eqref{eq:nonlinearTEODE}, regularization parameter $\lambda/2 \geq  U_{\text{TE}}^2 \sqrt{\frac{\log(2p/\delta)}{2n}} + 4U_{\text{TE}}^3 g_{n,\delta}^2$ and the search set $\mathcal{T} = \mathbb{R}^p$ obeys, w.p. $1-4\delta$:
\begin{equation}
\|\widehat{\theta} - \theta_0\|_2 = \frac{3\sqrt{k}}{\gamma_{\text{TE}}}  O\left(\max\left\{  U_{\text{TE}}^2\sqrt{\frac{\log(2p/\delta)}{2n}},  4U_{\text{TE}}^3 g_{n,\delta}^2\right\}\right),
\end{equation}
where $U_{\text{TE}}=\frac{U}{\nu} + \frac{U}{\nu^2}+\frac{2U}{\nu^3}$.
\end{corollary}

In the worst-case, computing an estimate $\widehat{h}$ of $h$ with respect to an $\ell_{\infty,1}$ norm would scale linearly with $p$ if there is no relation across the coordinates of $h$. Remark \ref{rm:fsh} gives primitive sufficient conditions on $h(u)$ for convergence.

\begin{remark}[First-Stage Estimator of $h(u)$]
\label{rm:fsh}
Suppose there exists a low-dimensional "base" treatment $\tau \in \mathcal{R}^{d_{\tau}}$ such that the technical treatment $x$ is generated according to
$$x = B(u)' \tau $$
for some known matrix of controls $B(u)$. In addition, suppose the following conditions hold.
\begin{enumerate}
    \item  $\pi(u)=\mathbb{E}[\tau|u]$ satisfies  Assumption \ref{ass:nuisance} with rate $\pi_{n,\delta}$ in $\ell_{\infty}(\ell_2)$ norm.
    \item (1) For some $\bar{B}_{\infty}< \infty$, $\sup_{u \in \mathcal{R}^{d_u}} \|B_j(u)\|_1 \leq \bar{B}_{\infty}$.
\end{enumerate}
Then $\widehat{h}(u) = B(u) \widehat{\pi}(u)$ satisfies Assumption \ref{ass:nuisance} with $h_{n,\delta} = \bar{B}_{\infty} \pi_{n,\delta}$ in $\ell_{\infty}$-norm.
\end{remark}

\begin{remark}[First-Stage Estimator of $V(z)$]
\label{rm:fsvee}
Suppose there exist estimators $\widehat{h}(u)$ of $h_0(u)$ and $\widehat{q}(u)$ of $q_0(u)$ that satisfy Assumption \ref{ass:nuisance} with $h_{n,\delta}, q_{n,\delta}$ rates in $\ell_{\infty}$ norm. Suppose the conditions of Corollary \ref{cor:non-linear-te} hold except \ref{itm:nonlinear:rate}. Let $K(w,t,\{h,q\})$ be a solution to a one-dimensional ODE
\begin{align}
\label{eq:nonlinearTEODEprelim}
\frac{\partial}{\partial t}K(w,t,\{h,q\}) = G(t) - y
,\;t \in \mathbb{R}.
\end{align}
Let $\tilde{\theta}$ be an output of Algorithm \ref{def:lasso:intro} with the loss function
$K(w,t,\{h,q\})$, the search set $\mathcal{T}=\mathcal{R}^p$ and the regularization penalty $\lambda_{\text{fs}}/2 \geq U g_{n,\delta}+U g_{n,\delta}^2 +U^2\sqrt{\frac{\log (2p/\delta)}{2n}}$. Then, w.p. $1-5\delta$ $\widehat{V}(z)=G'((x-\widehat{h}(u))'\tilde{\theta} + \widehat{q}(u))$ belongs to the realization set $V_{n,\delta} = \{ G'((x-h(u))'\theta + q(u)), \quad \|\tilde{\theta} - \theta_0\|_1 \leq \theta_{n,\delta}, \| h (u)- h_0(u)\|_{\infty} \leq h_{n,\delta}, \|q (u)- q_0(u)\|_{\infty} \leq q_{n,\delta} \}$, where $\theta_{n,\delta} = \frac{6k}{\gamma_{\text{TE}}} \lambda$. Moreover, the set  $V_{n,\delta}$ shrinks at rate $U^2 \theta_{n,\delta} + U (q_{n,\delta}+h_{n,\delta})$.

\end{remark}

Recognize that $V(z)=G'(\Lambda(z,g(u))'\theta_0+q(u))$ is a known function of $z,\theta, \{h(u),q(u)\}$. Moreover, the loss function $K(w,t,\{h,q\})$ in \eqref{eq:nonlinearTEODEprelim} is a convex function of $t$. Then, the statement of Remark \ref{rm:fsvee} follows from Lemma \ref{lem:ver:nuisance}.

\begin{comment}

Define $f_0^{\theta}(u)$ as follows:
\begin{align}
    f^{\theta}_0(u):= \arg \min_{f \in \mathcal{M}}
    \mathbb{E} (G^{-1} (\mathbb{E} [y|x,u]) - x'\theta-f(u))^2,
\end{align}
where the set $\mathcal{M}= \{f(u):\mathcal{U} \rightarrow \mathbb{R}\}$ consists of square integrable functions of $u$. Then:
\begin{align}
    f^{\theta}_0(u):=q_0(u) - h_0(u)'\theta,
\end{align}
where $q_0(u):=\mathbb{E} \big[ G^{-1} (\mathbb{E} [y|x,u])| u\big]$ is the Conditional Expectation Function of $G^{-1} (\mathbb{E} [y|x,u])$ and $h_0(u):= \mathbb{E} [x|u]$ is the Conditional Expectation Function of the  treatment. Observe that we can also re-write $q_0$ as: $q_0(u)= \mathbb{E}\left[ x'\theta_0 + f_0(u)\right] = h_0(u)'\theta +f_0(u)$. This leads to the modified moment:
\begin{align}
    \mathbb{E} \left[ G((x-h_0(u)) '\theta_0 + q_0(u)) - y| x,u \right] &= 0,
\end{align}

Unlike the linear case (i.e. $G(t)=t$), the latter moment is still not orthogonal with respect to $h$ and $q$. The non-linearity requires us to make one extra modification to the moment: at a high level, optimally weight the moment by dividing by the conditional variance, to take away heteroskedasticity. This modification turns out to lead to an orthogonal moment.

\paragraph{Casting problem as estimation with nuisance component} More formally, we will consider the following instance of the single index model presented in Section \ref{sec:moment}: let
Consider the conditional moment restriction:
\begin{align}
    m(w,\Lambda(z,g(z))'\theta, g(z)):= \frac{1}{V(z)}(G(\Lambda(z,g(z))'\theta + q(u)) - y)
\end{align}
Define the target loss function as:
\begin{equation}\label{eqn:ortholoss-te}
    \ell(w,\theta,g(z)) := K(w,(x-h(u)) '\theta+q(u),g(z)).
\end{equation}
Let where $K(w,t,g(z))$ be a solution to the ODE

\end{comment}
\begin{example}[Discrete Choice with Logistic Errors]\label{ex:logistic}
When the link function $G$ is the
logistic function ${\mathcal L}$, then the resulting orthogonal loss in Equation~\eqref{eq:nonlinearTEODE} corresponds
to the weighted logistic maximum likelihood estimator:
\begin{align*}
    \ell(w, \Lambda(z,g(z))'\theta, g(z)) &=
    \frac{1}{V(z)} \big( y\cdot \log\left({\mathcal L}\left((x-h(u)) '\theta+q(u)\right)\right)\\
    &+ (1-y)\cdot \log\left(1-{\mathcal L}((x-h(u)) '\theta+q(u))\right) \big),
\end{align*}
where $\Lambda(z,g(z))=x-h(u)$ and $g(z)=\{ h(u),q(u),V(z)\}$.
\end{example}
The logistic link function arises in a binary discrete choice problem, where the agents's utility from outside alternative is normalized to zero and the other alternative is $x'\theta_0 + f_0(u)+\epsilon$, where unobserved shock $\epsilon$ follows a Gumbel distribution.  In this setting, $\theta_0$ corresponds to the effect of co-variate vector $x$ on the agent's utility. Our approach also extends to more than two choices, albeit with some extra technical arguments, which we omit for simplicity of exposition.

\begin{comment}

\paragraph{Estimating $q$, $h$ and $V$} First, observe that $h$ has a high dimensional output of size $d=p$. Hence, in the worst-case computing an estimate $\widehat{h}$ of $h$ with respect to an $\ell_{\infty,1}$ norm would scale linearly with $p$ if there is no relation across the coordinates of $h$. Hence, we will need to make an assumption that $h$ is really determined by a lower dimensional nuisance function $\pi(u)$, which is then projected back to a high dimensional space via a known linear transform: $B(u) \pi(u)$. If we further assume that $\|B(u)\|_{\infty, 1} = \max_{i} \|B_i(u)\|_1 \leq H$, then it suffices to estimate the lower dimensional nuisance $\pi$ in $\ell_{\infty,\infty}$ norm. For instance, if the high-dimensional treatment $x$ is really determined by lower dimensional treatment $\tau \in \mathbb{R}^d_{\tau}$, with $d_{\tau}$ being a constant, via a known linear transform: $B(u)'\tau$, then observe that $\mathbb{E}[x|u] = B(u) \mathbb{E}[\tau|u] = B(u)\pi_0(u)$, with $\pi_0(u)=\mathbb{E}[\tau | u]$. If further the base treatments have a sparse linear relation with $u$, i.e. $\pi_{0,j}(u)=u'\gamma_{0.j}$ with $\|\gamma_{0,j}\|_0\leq k_\gamma$, then we can compute an estimate $\widehat{\pi}_j$ of each $\pi_{0,j}$ via a lasso, regressing $\tau_j$ on $u$. Further, if we assume that $f_0(u)=u'\alpha_0$ for some sparse coefficient, $\|\alpha_0\|_0\leq k_{\alpha}$, then we can compute a preliminary estimate of $\tilde{\theta}$ and $\widehat{\alpha}$ by running a non-orthogonal non-linear lasso based on the loss $\int_0^{x'\theta + u'\alpha} (G(t) - y) dt$. With this estimates at hand, we can estimate $q_0$ and $V_0$ in a plugin manner:
\begin{align*}
    \widehat{q}(u) ~=~& \widehat{h}(u)'\tilde{\theta} + u'\widehat{\alpha}=\widehat{\pi}(u)' B(u)' \tilde{\theta} + u'\widehat{\alpha}\\
    \widehat{V}(z) ~=~& G'(x'\tilde{\theta} + u'\widehat{\alpha})
\end{align*}
Assuming that $k_\gamma$ and $k_\alpha$ grow at a sufficiently some slow rate of $n/\log(p)$, then the estimation error of the nuisance component can asymptotically be ignored.

\end{comment}

\begin{remark}[Plausibility of Assumption \ref{ass:nuisance} for Corollary \ref{cor:non-linear-te}]
Suppose the conditions of Remarks \ref{rm:fsh} and \ref{rm:fsvee} hold. Suppose $\pi(u)=\mathbb{E}[\tau|u]$ and $q(u)$ are linear sparse functions of $u$ that obey the conditions of Remark \ref{rm:lin} with $k_{\beta} \gg k$ and $k_{\alpha} \gg k$. Then, a preliminary estimator $\tilde{\theta}$ defined in Remark \ref{rm:fsvee} converges at rate $\theta_{n,\delta}=\frac{12k}{\gamma_{\text{TE}}} \lambda_{\text{fs}}$, and $\hat{V}(z)$ converges at rate $v_{n,\delta}=U^2 \theta_{n,\delta} + U (\bar{B} \pi_{n,\delta}+q_{n,\delta})$. Therefore, Assumption \ref{ass:nuisance} is satisfied for $\hat{g} = (\hat{h}, \hat{q}, \hat{V})$ with $g_{n,\delta} = (\bar{B} \pi_{n,\delta}+q_{n,\delta}) (1+U)+ U^2\theta_{n,\delta}$.
\end{remark}

\subsection{General Moment Problem with Missing Data}
\label{sec:selection}
\label{SEC:SELECTION}

We consider a setting with missing data where we want to estimate a parameter $\theta$, based on a conditional moment restriction:
\begin{equation}\label{eq:moment}
\mathbb{E}[u(y, x'\theta_0) | x]=0
\end{equation}
where $y\in \mathbb{R}^q$ and $x \in \mathbb{R}^p$. However, only some of the labels $y$ are observed. In particular, if we denote with $d\in\{0,1\}$ the indicator random variable that determines whether $y$ is observed, then we assume that we only observe the quantities $(x, dy)$. Hence, evaluating the conditional moment \eqref{eq:moment} directly is infeasible, since the variable $y$ is not always observed.

\begin{comment}
Such models commonly occur in biostatistic and econometric applications, where the indicator $d$ determines whether the data are corrupted due to some measurement error.
\end{comment}
A standard way to make progress in this problem is to assume that all variables $z\supseteq x$ that could have a direct effect on both the missing indicator $d$ and the outcome $y$ are also observable. Such variables are typically referred to as confounders or controls. This is formalized in the following assumption.
\begin{assumption}[Observed Confounders (OC)]
\label{ass:MAR} The presence indicator $d$
is independent from $y$ conditional on an observed set of variables
$z\supseteq x$, with $z\in \mathbb{R}^{d_z}$, i.e.:
$d \perp y
\,| \,z$.
\end{assumption}

We invoke Assumption \ref{ass:MAR} to represent this problem as a single index conditional moment restriction (\eqref{eq:main},\eqref{eq:cond_exog}).
Let $p_0(z) = \mathbb{E}[d|z]$ denote the conditional probability of observing $y$ given $z$. Then the single index moment function $$m(w, x'\theta, p(z)) = \dfrac{d\,u(y, x'\theta)}{p(z)}$$ is a special case of \eqref{eq:main} with $\Lambda(z,g(z))=x$ and $g(z)=p(z)$. By Assumption \ref{ass:MAR}, $m(w, x'\theta, p(z)) $ is a valid conditional moment restriction
\begin{align*}
\mathbb{E} [m(w, x'\theta, p(z))|z]=~& \mathbb{E}\left[\mathbb{E}\left[ \frac{d\, u(y, x'\theta_0)}{p_0(z)} \bigg| z\right]\,\bigg|\,x\right] \\
=~& \mathbb{E}\left[\frac{\mathbb{E}[d\,|\,z]}{p_0(z)} \mathbb{E}[u(y, x'\theta_0)\,|\,z]\,\bigg|\,x\right]= 0.
\end{align*}

Define the nuisance function $h_0(z)$ as
\begin{equation*}
 -\mathbb{E}\left[\frac{d\, u(y, x'\theta_0)}{p_0(z)^2}\,|\,z\right] = -\frac{1}{p_0(z)}\underbrace{\mathbb{E}\left[u(y, x'\theta_0)\,|\,z\right]}_{h_0(z)}
\end{equation*}
and observe that $h_0(z)\neq 0$. According to Theorem \ref{lem:general}, an orthogonal CMR for $\theta_0$ takes the form
\begin{align*}
    \phi(w,x'\theta,\tilde{g}(z)) = \dfrac{d\,u(y, x'\theta)}{p(z)} -\frac{ h(z)}{p(z)} ( v - p(z)),
\end{align*}
where the nuisance component $\tilde{g}(z)=\{p(z), h(z)\}$.

We construct the orthogonal loss using characterization \eqref{eq:characterization}.
Let the function $K(w,t,p(z))$ be a solution to ODE: $\frac{\partial}{\partial t} K(w, t, p(z)) = m(w, t, p(z))$.
Then, the orthogonal loss function is \begin{equation}\label{eqn:m-loss-md}
\ell(w, x'\theta, \{p(z), h(z)\}) := \underbrace{K(w, x'\theta, p(z))}_{\text{original loss}} + \underbrace{h(z)\,(d-p(z))\, x'\theta}_{\text{orthogonal correction}}.
\end{equation}

\begin{corollary}[Orthogonal Estimation of General Moment Problem with Missing Data]
\label{cor:selection}
Define the correlation matrix as \begin{equation}
\Sigma_{\text{MD}}=\mathbb{E}\left[\nabla_{\theta \theta} \ell(w,x'\theta_0, p(z)) \right] = \mathbb{E}\left[\nabla_t u(y, x'\theta_0) x\,x'\right]
\end{equation}
Suppose the following conditions hold.
\begin{enumerate}
    \item \label{index-sel:nuisance} There exists estimator $\hat{g} = (\hat{p}, \hat{h})$ that satisfies Assumption \ref{ass:nuisance} with rate $g_{n,\delta}$ in $\ell_2$-norm.
     \item Bounded data $\sup_{w \in \mathcal W} \|w\|_{\infty} \leq U$
    \item \label{index-sel:convexity} The function $u(y,t)$ is increasing in $t$ for any $y \in \mathcal{R}$.
    \item \label{index-sel:smooth} Limited overlap: for some $\bar{p}>0$, $\inf_{z \in {\mathcal Z} } p_0(z)\geq \underline{p}>0$.
    \item \label{index-sel:identification} There exists $\gamma_{\text{MD}}>0:$ $\Sigma_{MD}\geq \gamma_{\text{MD}} I$. The functions $u(y,t)$,$\nabla_t u(y,t)$, $\nabla_{tt} u(y,t)$ are $U$-bounded.

\end{enumerate}
Finally, let  $\sup_{\theta \in \Theta} \| \theta \|_0 \leq U$ and $k=o\left(\left(\frac{n}{\log(p/\delta)}\right)^{1/4}\right)$.  Then, the Plug-in Regularized Extremum Estimator of Algorithm \ref{def:lasso:intro} with $M$-estimator loss defined in Equation \eqref{eqn:m-loss-md}, regularization parameter $\frac{\lambda}{2} \geq U_{MD}^2\sqrt{\frac{\log(2p/\delta)}{2n}} + 4U_{MD}^3 g_{n,\delta}^2$  and the search set $\mathcal{T} = \mathbb{R}^p$ obeys, w.p. $1-4\delta$:
\begin{equation}
 \|\widehat{\theta}-\theta_0\|_2 \leq \frac{\sqrt{k}}{\nu \gamma_{\text{MD}}} O\left(\max\left\{\sqrt{\frac{\log(2p/\delta)}{2n}}, 4U^3 g_{n,\delta}^2, \xi_{n,\delta}^2 \right\}\right)
\end{equation}
for some $U_{\text{MD}}$.
\end{corollary}

\begin{remark}[Plausibility of Assumption \ref{ass:nuisance} for Corollary \ref{cor:selection}]
Suppose all conditions of Corollary \ref{cor:selection} hold except \ref{index-sel:nuisance}.
Suppose $p_0(z)$ obeys the conditions of Remark \ref{rm:log}. Suppose $u(x'\theta,y) = x'\theta - y$ where $y = x'\theta_0 + z_{-x}'\alpha_0 + \zeta,  \mathbb{E}[z_{-x}'\alpha | x]=0$ is a linear sparse function of $x,z_{-x}$. Then, $h(z)=\mathbb{E}[ x'\theta_0 - y|z] =  z_{-x}'\alpha_0$. Define the estimator $\hat{h}(z)=z_{-x}'\hat{\alpha}$, where $(\hat{\theta},\hat{\alpha})$ is the estimate of $(\theta,\alpha)$ in $\ell_1$-regularized regression of $y$ on $x,z_{-x}$. According to Remark \ref{rm:lin}, $\| \hat{\alpha} - \alpha_0\|_2 = O_{P} (\sqrt{\frac{(k_{\alpha}+k) \log p}{n}})$ and $\| \hat{\alpha} - \alpha_0\|_1 = O_{P} (\sqrt{\frac{(k_{\alpha}+k)^2 \log p}{n}})$.  Therefore, Assumption \ref{ass:nuisance} is satisfied.

\end{remark}

\subsection{Games of Incomplete Information}
\label{sec:strategic}
\label{SEC:STRATEGIC}

Consider a two-player discrete static game of incomplete information, where each player $i \in \{1,2\}$ can choose between two actions: $1$ or $0$. The payoffs for each player from action $1$ are given by:
\begin{align}
\label{eq:games}
    U_1 &= x_1'\alpha_0^1 +  y_2 \Delta_0^1 + \epsilon_1, \quad \mathbb{E} [\epsilon_1 | z] = 0 \\
\label{eq:games-2}
    U_2 &= x_2'\alpha_0^2 +  y_1 \Delta_0^2 + \epsilon_1, \quad \mathbb{E} [\epsilon_2 | z] = 0,
\end{align}
where $y_i \in \{1,0\}$ stands for an action of player $i$, $x_i,\alpha_0^i \in \mathcal{R}^{p-1}$ is a covariate vector that directly determines the utility of player $i$, and $\Delta_0^i$ is  a strategic interaction parameter, showing the impact on the utility of player $i$ of the action of his opponent for each player $i \in \{1,2\}$. In addition, each player privately observes a shock $\epsilon_i$ that is mean independent from the features $z= \{x_1,x_2\}$ that are commonly observed by both players and the researcher. In particular, we will focus on the case when $\epsilon_i$ are drawn from the Gumbel distribution, conditional on $z$.

Each player $i$ makes a simultaneous choice $y_i$ without observing her opponent's private shock $\epsilon_{-i}$. We
assume that players' choices correspond to {\it Bayes-Nash equilibrium} strategies in the game and, therefore,
can be determines as
$$y_i = \arg \max_{y_i \in \{1,0\}} \{  x_i'\alpha_0^i +  \mathbb{E}[y_{-i} | z] \Delta_0^i + \epsilon_i , 0\},  $$
where $y_{-i}$ is the action of the opponent and the utility of an action $0$ (outside option) is normalized to $0$ for each player. Therefore, if a researcher observes samples from repeated plays of this game (where at each round each player gets a new draw of the additive logistic random variable), the estimated probabilities of choices by each player will also consistently estimate her opponent's beliefs regarding her choices.

\paragraph{Casting problem as estimation with nuisance component} Focusing on player $i\in \{1,2\}$,  the estimation of the model defined in \eqref{eq:games}-\eqref{eq:games-2} can be cast as the following special case of the single index conditional moment restriction of Section \ref{sec:moment}:
\begin{align*}
    \mathbb{E}[m(w,\Lambda(z, g(z))'\theta, g(z))\,|\,z] := \mathbb{E}[{\mathcal L} (\Lambda(z, g(z))'\theta) - y\,|\,z] ~=~& 0\\
   \mathbb{E}[v - g(z)\,|\,z] ~=~&0 ,
\end{align*}
where ${\mathcal L}(t)=1/(1+e^{-t} )$ is the logistic function, $\Lambda(z, g(z)) = (x_i; g(z))$, $\theta=(\alpha^i; \Delta^i)$ is the combined vector of co-variate effects $\alpha^i$ and strategic effect $\Delta^i$, the nuisance component $g:\mathbb{R}^{2p-2}\rightarrow \mathbb{R}$ is the conditional probability of opponent entry and $v\in \{0, 1\}$ is an action of the opponent.

Define the function $h_0(z)$ as $h_0(z) = \Delta_{0}^i\, {\mathcal L}'(\Lambda(z,g_0(z))'\theta_0)$
and observe that $h_0(z) \neq 0$. Then, the orthogonal CMR takes the form
\begin{align*}
    \phi(w,\Lambda(z,g(z))'\theta_0,g(z)) = {\mathcal L} (\Lambda(z, g(z))'\theta) - y + h_0(z) (v - g(z)).
\end{align*}

Let $K(w, t, g(z))$ be the logistic loss:
\begin{align}
    K(w, t, g(z)) := - y \log {\mathcal L} (t) - (1-y) \log (1-{\mathcal L} (t)).
\end{align}
The orthogonal loss  function takes the form
\begin{align}
\label{eq:losshardgames}
    \ell(w, \Lambda(z, g(z))'\theta, \{g(z), h(z)\}) :&=
    \underbrace{K(w, \Lambda(z, g(z))'\theta, g(z))}_{\text{non-orthogonal logistic loss}} \\
    &+ \underbrace{h(z)\, (v - g(z))\, \Lambda(z, g(z))'\theta}_{\text{orthogonal correction}}. \nonumber
\end{align}
Invoking Theorem~\ref{cor:non-ortho-rate}, we obtain the following result.

\begin{corollary}[Orthogonal Estimation of Games of Incomplete Information]
\label{cor:games}
Define the correlation matrix as \begin{equation}
    \Sigma_{\text{games}} := \mathbb{E}[\Lambda(z,g_0(z))\Lambda(z,g_0(z))']
\end{equation}
Suppose the following conditions hold
\begin{enumerate}
    \item \label{index-games:nuisance} Assumption \ref{ass:nuisance} is satisfied for $\tilde{g}(z)=\{g(z),h(z)\}$ with rate $\tilde{g}_{n,\delta}$ in $\ell_2$-norm.

    \item The elements of $w$ and the functions $g,h$ are $U$-bounded. For some $\nu>0$,  ${\mathcal L}(t)\, (1-{\mathcal L}(t)) \geq \nu$ for any $t\in \{\Lambda(z, g_0(z))'\theta: \theta\in \Theta, z\in {\mathcal Z}\}$.
    \item There exists $\gamma_{\text{games}}>0$ such that $\Sigma_{\text{games}}\geq \gamma_{\text{games}} I$

\end{enumerate}

In addition, let $\sup_{\theta \in \Theta} \|\theta \|_0\leq U k=o\left(\left(\frac{n}{\log(p/\delta)}\right)^{1/4}\right)$,  $k \tilde{g}_{n,\delta}=o(1)$. Then the estimate of Algorithm~\ref{def:lasso:intro} with $M$-estimator loss defined in Equation \eqref{eq:losshardgames}, regularization parameter $\frac{\lambda}{2} \geq U_{\text{games}}^2\sqrt{\frac{\log(2p/\delta)}{2n}} + 4U_{\text{games}}^3 \tilde{g}_{n,\delta}^2$  and the search set $\mathcal{T} = \mathbb{R}^p$ obeys, w.p. $1-4\delta$:
\begin{equation}
 \|\widehat{\theta}-\theta_0\|_2 \leq \frac{\sqrt{k}}{\nu \gamma_{\text{games}}} O\left(\max\left\{\sqrt{\frac{\log(2p/\delta)}{2n}}, 4U^3 \tilde{g}_{n,\delta}^2, \xi_{n,\delta}^2 \right\}\right)
\end{equation}
for some $U_{\text{games}}$.
\end{corollary}

\begin{remark}[Plausibility of Assumption \ref{ass:nuisance} for Corollary \ref{cor:games}]
Suppose  $g(z)=\mathbb{E}[v|z]$ obeys the conditions of Remark \ref{rm:log}.  Then, the nuisance parameter $h(z)=\Delta_0^i {\mathcal L}'(\Lambda(z,g_0(z))'\theta_0)$ satisfies the conditions of Lemma \ref{lem:ver:nuisance} since $\Delta_0^i \subset \theta$ is a coordinate of $\theta$. Therefore, $\hat{h}(z)$ converges with rate  $h_{n,\delta}$ defined in Lemma \ref{lem:ver:nuisance} and Assumption \ref{ass:nuisance} is satisfied for $\tilde{g}(z)=\{g(z),h(z)\}$.
\end{remark}

\begin{comment}
\paragraph{Estimating $g$ and $h$} If we assume that $g$ follows a high-dimensional logistic parametric form: $g(z) = {\mathcal L}(\tau(z)'\psi)$ for some sparse parameter $\psi$ with $\|\psi\|_0\leq k_z$, then we can compute an estimate $\widehat{g}$ of $g_0$ via a logistic lasso at a rate of $g_{n,\delta} =O\left(\frac{k_z}{\gamma_\tau}\sqrt{\frac{\log(p/\delta)}{n}}\right)$, where $\gamma_\tau$ is the minimum eigenvalue of $\mathbb{E}[\tau(z)\tau(z)']$. Moreover, an estimate $\widehat{h}$ of $h_0$ can be estimated in a plugin manner using the estimate $\widehat{g}$ of $g_0$ as well as a preliminary estimate $\tilde{\theta}$ of $\theta_0$ and evaluating $\widehat{h}(z)=\tilde{\Delta}^i {\mathcal L}'(\Lambda(z, \widehat{g}(z))'\tilde{\theta})$. The preliminary estimate $\tilde{\theta}$ can be obtained via a non-orthogonal logistic lasso regressing $y_i$ on $x_i, \widehat{g}(z)$. The latter will lead to an $\ell_1$ rate for $\tilde{\theta}$ of the order of $O\left(\frac{k}{\gamma}\left(\sqrt{\frac{\log(p/\delta)}{n}} + g_{n,\delta} \right)\right)$, where $\gamma$ is the minimum eigenvalue of $\Sigma_{\text{games}}$. If $k$ and $k_z$ grow sufficiently slow, i.e. $k\, k_z = o\left(\left(\frac{n}{\log(p/\delta)}\right)^{-1/4}\right)$, then the estimation error of both $\widehat{h}$ and $\widehat{g}$ can asymptotically be ignored.

\end{comment}

\section*{Supplementary Material}
\setcounter{section}{0}

\input{Proofs_2019.tex}
\input{monte_carlo.tex}

\end{document}

\section{Constructing an $M$-estimator for Single Index Conditional Moment Restrictions}
 \label{sec:moment}
 \label{SEC:MOMENT}

\paragraph{Notation} We assume that an i.i.d. auxiliary sample $S'$ and main sample $S=(w_i)_{i=1}^n$, of size $n$ each, are available for estimation in the first and the second stage. For a  function $f:\mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^d\rightarrow \mathbb{R} $, $\nabla_t f(w,t,\gamma)$ and $\nabla_{\gamma} f(w,t,\gamma)$ stand for the partial derivatives of $f$ w.r.t to the second and the third argument. The notation $f(w, \Lambda(z,g(z))'\theta,g)$ and $\nabla_t f(w, \Lambda(z,g(z))'\theta,g)$ stand for the functions $f(w,t,\gamma)$ and $\nabla_t f(w, t,g)$ whose second argument is taken to be $t=\Lambda(z,g(z))'\theta$ and $\gamma=g$.  For a $p$-valued random vector $\xi$, $\|\xi\|_{P,2}:= \sqrt{\mathbb{E} \| \xi\|_2^2 }$. The sparsity index $k=k_n$ and the dimension $p=p_n$ grow with $n$. The constants $U,\gamma,\nu,\bar{B},\bar{\sigma},\bar{H}$ are understood to be independent   from $n$.

 \subsection{Set-Up}
 \label{sec:setup}
 We are interested in the target parameter $\theta$  identified by a system of conditional moment restrictions (CMRs)
 \begin{align}
    \mathbb{E}[m(w , \Lambda(z,g_0(z))'\theta_0, g_0(z)) | z]~&=0 \label{eq:main}   \\
    \mathbb{E}[R(w,g_0(z))|z] ~&= 0 \label{eq:cond_exog},
\end{align}
where $w \in \mathcal W$ is a vector of data, $z \subset w, z \in {\mathcal Z}$ is a vector of variables in the conditioning set, and $\Lambda(z,g_0(z))$ is a $p$-vector-function of $z$. The moment function $m:\mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^d\rightarrow \mathbb{R}$ and the random vector $\Lambda(z,g_0(z))$ can depend on an unknown nuisance function $g_0(z)$. For example, $g_0(z)$ could be a conditional expectation function, conditional quantile function, or conditional density. The function $g_0(z)$ is defined by the conditional exogeneity restriction ~\eqref{eq:cond_exog} and  can depend only on a subvector of $z$. The parameter $\theta$ is assumed to be high-dimensional sparse. The goal is to provide an $M$-estimator for $\theta_0$ that converges at the oracle $\ell_2$-rate $\sqrt{\frac{k \log p}{n}}$ , where the oracle knows  the nuisance function $g_0(z)$ and solves a parametric problem defined by \eqref{eq:main}.
\begin{comment}
, meaning that
the total dimension can  exceed the sample size (i.e, $p \gg n$), but the sparsity index $k$ must be small:
$$ k = \|\theta_0\|_0 := |\{j: \theta_{0,j} \neq 0\}| \ll n.$$
\end{comment}

We construct the $M$-estimator loss function assuming the unconditional moment for $\theta_0$, defined as
\begin{align}
\label{eq:mortho}
    \rho(w,\theta,g) = m(w, \Lambda(z,g(z))'\theta, g(z)) \cdot \Lambda(z,g(z)),
\end{align}
is orthogonal  to $g$.
A moment condition
$\rho(w,\theta,g): \mathcal{W} \bigtimes \Theta \bigtimes \mathcal{G}  \rightarrow \mathbb{R}^p$ is
orthogonal with respect to $g$ if its pathwise derivative w.r.t $g$ at $g_0$ is zero:
$$
\nabla_r \mathbb{E}\left[\rho_j (w,\theta_0, r(g-g_0) + g_0) \big|_{r=0} \right] = 0, \quad \forall j \in
\{1,2,...,p\}.$$

\begin{assumption}[Orthogonality]
\label{ass:orthogonal}
The moment equation $\rho(w,\theta,g)$ in \eqref{eq:mortho} is orthogonal with respect to $g$.
\end{assumption}

Assumption \ref{ass:orthogonal} streamlines our exposition. We describe the Plug-In Regularized $M$-estimator and state our results under Assumption \ref{ass:orthogonal} in Sections \ref{sec:setup}-\ref{sec:nonconvex}. In Section \ref{sec:orthogonalization}, we
transform an arbitrary system of CMRs  \eqref{eq:main}-\eqref{eq:cond_exog} into a system of CMRs that obeys Assumption  \ref{ass:orthogonal}.

We define the orthogonal loss function   $\ell:\mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^{d} \rightarrow \mathbb{R}$  as any solution to the one-dimensional ordinary differential equation (ODE):
\begin{equation}
\label{eq:ode}
 \nabla_{t} \ell(w,t,g(z)) = m(w,t,g(z)),
\end{equation}
where $\nabla_{t} \ell(w,t,g(z))$ is the  partial derivative of the loss function with respect to its second argument.
By construction, the gradient of the loss function $\ell(w,\Lambda(z,g(z))'\theta,g(z))$ is equal to
\begin{align*}
    \nabla_{\theta} \ell(w,\Lambda(z,g(z))'\theta,g(z)) =
    m(w,\Lambda(z,g(z))'\theta,g(z))\cdot \Lambda(z,g(z)),
\end{align*}
which is a valid and orthogonal moment equation for $\theta_0$.

We estimate the target parameter $\theta_0$ in two stages, with each stage computed on a separate sample. First, we estimate the nuisance parameter $g$ on an auxiliary sample.  Second, we plug the estimated nuisance parameter into the $\ell_1$-regularized orthogonal loss. If the loss function $\ell(w,\Lambda(z,\widehat{g}(z))'\theta,\widehat{g}(z))$ is convex in $\theta$, we define the estimator as the global minimum on the search set $\mathcal{T}=\mathcal{R}^p$
and the penalty parameter $\lambda$ of the order \eqref{eq:lambda}. If the loss function is not convex, we  define the estimator  as a local minimum in a shrinking neighborhood of $\theta_0$. We provide the construction of the preliminary estimator and the neighborhood around it in Section \ref{sec:nonconvex}. In both cases, the general scheme of our estimator follows Algorithm \ref{def:lasso:intro}.

\begin{algorithm}[H]
\begin{flushleft}
Input:  $\lambda \geq 0$, search set $\mathcal{T}\subset \mathbb{R}^p$
\end{flushleft}
\begin{algorithmic}[1]
\STATE Partition sample into  an auxiliary sample $S'$ and an estimation sample $S$
\STATE  Estimate the nuisance parameter $\widehat{g} \in \mathcal{G}$ on the auxiliary sample $S'$.
\STATE Estimate $\theta_0$ via plug-in $\ell_1$-regularized local extremum estimation, i.e.:
    \begin{equation}
    \label{eq:mainalg}
    \widehat{\theta} = \argmin_{\theta\in \mathcal{T}}~
    \frac{1}{n} \sum_{i=1}^n \ell(w_i, \Lambda(z_i,\widehat{g}(z_i))'\theta,\widehat{g}(z_i))+ \lambda \|\theta\|_1.
\end{equation}
\end{algorithmic}
\caption{Plug-in Regularized Extremum Estimator}
\label{def:lasso:intro}
\end{algorithm}

\subsection{Example}

\begin{example}[Partially Linear Model with High-Dimensional Heterogeneous Treatment Effect]\label{ex:linear-intro}

Consider the following partially linear model
\begin{align}
\label{eq:plr}
 y =& d'\theta_0 + f_0(u) + \epsilon, \quad  \mathbb{E}[\epsilon | u, \tau] = 0
\end{align}
where $y$ is an outcome variable, $d \in \mathbb{R}^p $ is a  technical treatment vector, and $u \in {\mathcal Z}
\subset \mathbb{R}^d$ is a vector of control variables acting on the outcome $y$ via a non-linear function $f_0(u)$. The vector of treatment $d$ is generated according to
$$ d=\tau x,$$
where $\tau$ is a scalar base treatment variable and $x=(1, \bar{x}), \quad x \subseteq u$ is a $p$-vector of observed characteristics/factors along which the treatment effect varies.

\end{example}
The  treatment effect
$$ \theta_0 = (\theta_{0,1},  {\theta_{0,-1}}')$$
consists of the Average Treatment Effect (ATE) $\theta_{0,1}$ and the Treatment Modification Effect (TME) $\theta_{0,-1}$.  The  causal effect of the unit change in the base treatment $\Delta \tau$ on the outcome $y$ is equal to the sum of the ATE and the TME:
$$
\Delta d'\theta_0 = \Delta \tau x'\theta_0 = \underbrace{\theta_{0,1}}_{\mathrm{ATE}} +  \underbrace{x '\theta_{0,-1}}_{\mathrm{TME}}.
$$

We present  Example \ref{ex:linear-intro} as a special case of the model \eqref{eq:main}-\eqref{eq:cond_exog}.  Let $h_0(u)=\mathbb{E}[\tau|u]$ and $q_0(u) = \mathbb{E}[y|u]$ be  conditional expectations of the base treatment $\tau$ and the outcome $y$, and let $g_0(u) = (h_0(u), q_0(u))'$.  Rewriting \eqref{eq:plr}, we obtain a  conditional moment restriction for $\theta_0$:
\begin{align}
\label{eq:plr2}
	\mathbb{E} \bigg[  y - q_0(u)-(\tau - h_0(u)) \cdot x'\theta_0 \bigg| \tau,u \bigg] ~&= 0 \\
	\mathbb{E} \bigg[ (\tau, y)' - g_0(u)\bigg|u \bigg] ~&=0, \nonumber
\end{align}
which is a special case of \eqref{eq:main} with the control vector $z=(\tau,u)$,  data vector $w=(u,\tau,y)$,  $\Lambda(z,g(z)) = (\tau - h(u)) x$, and $R(w,g(z))=R(w,g(u))=(\tau, y)' - g(u)$.
The moment function $\rho(w,\theta,g)$ defined in \eqref{eq:mortho} takes the form
\begin{align*}
    \rho(w,\theta,g) &= \left ( y - q(u)-(\tau - h(u)) \cdot x'\theta \right)\cdot (\tau - h(u)) x
\end{align*}
and is orthogonal with respect to $g$ (see Appendix \ref{sec:ortho} for a proof).

The orthogonal loss $\ell:\mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^d\rightarrow \mathbb{R}$ is taken to be any solution of the ODE
\begin{align*}
\nabla_{t} \ell(w,t,g(u)) = (y - q(u) -  t).
\end{align*}
We set the loss function $\ell(w,t,g_0(u))$ to be a squared loss:
\begin{equation}
\label{eq:linearloss}
    \ell(w,t, g(u)) = \frac{1}{2}(y-q(u)-t)^2,
\end{equation}
where the sign of the function was chosen to ensure convexity of $\ell(w,t, g(u))$ in $t$. The proposed $M$-estimator is the global minimum described in  Algorithm \ref{def:lasso:intro} with the input parameters $\mathcal{T}=\mathbb{R}^p$ and $\lambda$ as in \eqref{eq:lambda}.

We compare the proposed estimator to a direct alternative  where the target  $\theta_0$ and the nuisance parameter $g_0(z)$ are estimated in one step. We argue that the orthogonal estimator achieves better performance when the the nuisance parameter $g_0(z)$ is more complex and harder to learn (in a sense we will make precise) than the target. Suppose  the nuisance functions  $f_0(u) = u'\alpha_0$ and $h_0(u) = u'\beta_0$  are linear sparse functions of $u$, with  sparsity indices $k_{\alpha}$ and $k_{\beta}$. Typically, the number  of covariates  that have a non-zero impact on the outcome $k_{\alpha}$ is larger than the number of factors that affect the treatment assignment $k_{\beta}$ or  contribute to the heterogeneity of the treatment effect, which is the sparsity index $k$ (i.e., $k_{\alpha} \gg k, k_{\alpha} \gg k_{\beta})$. Therefore, the first-stage nuisance function $q_0(u)=\tau x'\theta_0 + u'\alpha_0$ has a larger sparity index than  the function $h_0(u)=u'\beta_0$ and the target parameter $\theta_0$ and is harder to learn in that sense.

We consider the direct estimator as the joint estimate of $(\theta,\alpha)$ in the following minimization problem:
\begin{align*}
\ell_{\text{direct}}(\theta, \alpha ):&= \frac{1}{2n} \sum_{i=1}^n\left(y_i - d_i'\theta - u_i'\alpha \right)^2 \\
\widehat{\theta}_{\text{direct}} &=  \arg \min_{\theta \in \mathcal{R}^p, \alpha \in \mathcal{R}^p}\ell_{\text{direct}}( \theta, \alpha ) + \lambda_{\text{direct}}(\|\alpha\|_1 +\|\theta\|_1).
\end{align*}

The convergence rate of the direct estimator is bounded
$$    \| \widehat{\theta}_{\text{direct}}-\theta_0\|_2  \leq  \| (\widehat{\theta}_{\text{direct}}, \widehat{\alpha})-(\theta_0,\alpha_0)\|_2 \lesssim_{P}   \sqrt{k_{\alpha}+k}\sqrt{\frac{\log (p)}{n}}. $$
In contrast, the convergence rate of  the Plug-In Regularized Estimator attains the
$$\| \widehat{\theta} - \theta_0\|_2 \lesssim_{P} \sqrt{k} \left( \sqrt{\frac{\log p}{n}} + g_n^2 \right),$$
where $g_n  \lesssim_{P} \sqrt{(k + k_{\alpha}+k_{
\beta})\frac{\log p}{n}} $ is the rate of the first-stage linear Lasso estimator from \cite{belloni2013} with the first-stage regularization penalty $\lambda_{\text{fs}}  \sim \sqrt{\frac{\log p}{n}}$. Since $k_{\alpha} \gg k$ and $k_{\alpha} \gg k_{\beta}$, the Plug-In Regularized estimator converges faster than the direct estimator.

\begin{figure}[tpb]
    \centering
    \begin{subfigure}[]{0.45\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{ell2_error_dgp_dgp1_growing_kappa.png}
    \end{subfigure}
    ~
    \begin{subfigure}[]{0.45\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{ell1_error_dgp_dgp1_growing_kappa.png}
    \end{subfigure}
    \caption{\footnotesize{\emph{Comparison of
    direct and orthogonal estimation for the
    Heterogeneous Treatment Effects with a Linear Link Function}  We simulated $100$ experiments, with data generating parameters $u\sim N(0, I_p)$, $\epsilon, \eta\sim N(0, 1)$, $n=5000$, $p=200$, $k=2$, $k_{\alpha}=\|\alpha_0\|_0=\|\beta_0\|_0=k_{\beta}\in\{1, 4, \ldots, 37\}$. The supports of $\alpha_0$ and $\beta_0$ are identical and all non-zero coefficients of $\alpha_0, \beta_0, \theta_0$ are equal to one. The left figure shows the median, min and max $\ell_2$ estimation error for $\theta$ across $100$ experiments as a function of the support size $k_f,k_h$ and for each of the estimation methods: direct regression, orthogonal plug-in estimation, orthogonal estimation with cross-fitting. The right figure shows the corresponding quantities for the case of the $\ell_1$ error.}}
    \label{fig:experiments-linear}
\end{figure}

\paragraph{Cross-fitting} We can use machine learning methods  in the first stage because of sample splitting. In the absence of sample splitting, the estimation error of the first-stage machine learning estimator may be correlated with the true values of the second-stage moment, leading to  overfitting bias.  While  sample splitting helps  overcome  overfitting bias, it cuts the estimation sample in half.  This problem can lead to a less efficient estimator in small samples. To overcome this problem, we use the cross-fitting technique from \cite{doubleml2016}. Specifically, we partition the sample into two halves. To estimate the residuals for each half, we use the other half to estimate the first-stage nuisance parameter.  Then, we compute the resulting loss function  on the whole sample. As a result, each observation is used in both the first and  second stages, improving the efficiency in small samples.

\subsection{Main Result}
\label{sec:mainresult}

In this section, we give the sufficient conditions on the model, described by conditional moment restrictions \eqref{eq:main}-\eqref{eq:cond_exog} under Assumption \ref{ass:orthogonal}. We relax this assumption in Section \ref{sec:orthogonalization}.

 Our first assumption requires that the first stage estimator achieves some non-trivial rate of convergence to the truth. In particular, Assumption \ref{ass:nuisance} introduces a sequence of nuisance realization sets ${\mathcal G}_{n,\delta} \subset \mathcal{G}$ that contain the first-stage estimator $\widehat{g}$ with probability $1-\delta$. As sample size $n$ increases, set ${\mathcal G}_{n,\delta}$ shrinks around the true value $g_0$. The shrinkage speed is measured by the rate $g_{n,\delta}$ and is referred  to as the first-stage rate.

\begin{assumption}[First-Stage Rate]
\label{ass:nuisance}
For any $\delta>0$, w.p. at least $1-\delta$, the first-stage estimate $\widehat{g}$ belongs to a neighborhood ${\mathcal G}_{n,\delta}\subset {\mathcal G}$ of $g_0$, such that:
\begin{align*}
\sup_{g \in {\mathcal G}_{n,\delta}} \| g - g_0 \| \leq g_{n,\delta}.
\end{align*}
\end{assumption}

Assumption \ref{ass:nuisance} is satisfied by many machine learning estimators under structured assumptions on the model in $\ell_2$ and/or $\ell_{\infty}$ norm. For example, it holds for Lasso (\cite{belloni:11}, \cite{belloni2013}) in linear and generalized linear models, for $L_2$-boosting in sparse models \cite{luospindler}, for neural network \cite{ChenWhite1991}, and for random forest \cite{wagerwalther}. In Section  \ref{sec:fsrate}, we give specific construction of nuisance realization sets for linear and generalized linear sparse models derived from primitive conditions on the problem.

\begin{assumption}[Smoothness of moment condition]\label{ass:smooth}
The conditional moment model defined by $\{\mathcal W, {\mathcal Z}, \Theta, {\mathcal G}, m,\Lambda\}$ is $U$-smooth if $m$ and $\Lambda$ are twice differentiable, with derivatives bounded by some constant $U$. For any $\forall w\in\,W,\,\theta\in \Theta,\,g\in {\mathcal G}_n$ the following conditions hold:
    \begin{align*}
         |m(w, \Lambda(z, g(z))'\theta, g(z))|, \|\nabla_{\gamma} m(w, \theta_0, g(z))\|_{\infty},\, \|\nabla_{\gamma\gamma}m(w, \theta_0, g(z))\|_{\infty} \leq~& U\\
         \|\Lambda(z, g(z))\|_{\infty}, \|\nabla_{\gamma} \Lambda(z, g(z))\|_{\infty}, \|\nabla_{\gamma\gamma} \Lambda(z, g(z))\|_{\infty}, \|\nabla_{\gamma}\Lambda(z, g(z))'\theta\|_{\infty}\leq~& U\\
         |\nabla_{t} m(w, \Lambda(z, g(z))'\theta, g(z))|,\, |\nabla_{tt} m(w, \Lambda(z, g(z))'\theta, g(z))|\leq~& U\\
         \|\nabla_{\gamma t} m(w, \Lambda(z, g(z))'\theta, g(z))\|  \leq~& U,
    \end{align*}
\end{assumption}
where $\nabla_{\gamma}m(w, \theta_0, g(z))$ stands for the derivative of the moment function with respect to the output of $g(z)$. Assumption \ref{ass:smooth} ensures that the moment function is sufficiently smooth in its second argument (single index, denoted by $t$) and third argument (output of the nuisance function, denoted by $\gamma$).

\begin{assumption}[Identification]
\label{ass:identification}
The covariance matrix $$\Sigma=\mathbb{E}[\Lambda(z,g_0(z)) \Lambda(z, g_0(z))']$$ has minimum eigenvalue at least $\gamma_\Sigma>0$.  The $\mathbb{E}[m(w, t, g_0(z))\,|\,z]$ is strictly increasing in $t$. There exists $\nu>0$ such that the partial derivative $$\nabla_{t}\mathbb{E}[m(w, \Lambda(z,g_0(z))'\theta , g_0(z))\,|\,z] \geq \nu>0$$ is bounded from below.
\end{assumption}

\begin{assumption}[Monotonicity in single index]
\label{ass:convexity_moment}
The moment function $m(w, t, \gamma)$ is increasing in the single index $t$ for any $w \in \mathcal{R}$ and $\gamma \in \mathcal{R}$.
\end{assumption}

Assumption  \ref{ass:convexity_moment} ensures that the loss function $\ell(w,t,g(z))$ is a convex function of $t$ for any $w$ and $g(z)$. We invoke Assumption  \ref{ass:convexity_moment} to prove the global convergence of Algorithm \ref{def:lasso:intro} (Theorem \ref{cor:non-ortho-rate}). We drop Assumption  \ref{ass:convexity_moment} and establish local convergence of Algorithm \ref{def:lasso:prelim} in Section \ref{sec:nonconvex}.

\begin{comment}
Assumption \ref{ass:orthogonal} is made for the purpose of exposition. We show how to obtain an orthogonal CMR starting from a non-orthogonal one in Section \ref{sec:orthogonalization}.
\end{comment}

\begin{theorem}[$M$-Estimation of Conditional Moment Restriction with Convexity]\label{cor:non-ortho-rate}

(a) Suppose that the nuisance space $\mathcal G$
is equipped with the norm $\|g\|_{\infty,1}= \sup_{w\in W} \|g(w)\|_1$. Suppose Assumptions
\ref{ass:orthogonal}, \ref{ass:nuisance}, \ref{ass:smooth}, \ref{ass:identification}, \ref{ass:convexity_moment}
and  $k= o\left(\left(\frac{n}{\log(p/\delta)}\right)^{1/4}\right)$, $kg_{n,\delta}=o(1)$.  In addition, suppose $\sup_{\theta \in \Theta} \|\theta\|_{\infty} \leq U$.  Then, the estimator of Algorithm~\ref{def:lasso:intro} with $\lambda$ satisfying $\frac{\lambda}{2} \geq U^2\sqrt{\frac{\log(2p/\delta)}{2n}} + 4U^3 g_{n,\delta}^2  $
and $\mathcal{T}=\mathcal{R}^p$  achieves w.p. $1-4\delta$  for  $n$ large enough:
\begin{equation}
  \|\widehat{\theta}-\theta_0\|_2 \leq \frac{\sqrt{k}}{\nu \gamma_\Sigma} O\left(\max\left\{U^2\sqrt{\frac{\log(2p/\delta)}{2n}}, 4U^3 g_{n,\delta}^2\right\}\right).
\end{equation}
(b) Suppose the nuisance space is equipped with the $\ell_2$-norm $\|g\|_{2,1}=\sqrt{\mathbb{E}\left[\|g(w)\|_1^2\right]}$ and, furthermore, $\sup_{w, g\in {\mathcal G}_n} \|g(w)\|_{\infty}\leq H$ and $g(z) \in \mathbb{R}^d$. Define $\xi_{n,\delta}=d\, H \, \sqrt{\frac{\log(2/\delta)}{2n}}$. Then,
the estimator of Algorithm~\ref{def:lasso:intro} with $\lambda$ satisfying $\frac{\lambda}{2} \geq U^2 \sqrt{\frac{\log(2p/\delta)}{2n}} + 4U^3 g_{n,\delta}^2 $
and $\mathcal{T}=\mathcal{R}^p$ achieves w.p. $1-4\delta$  for  $n$ large enough:
\begin{equation}
  \|\widehat{\theta}-\theta_0\|_2 \leq \frac{\sqrt{k}}{\nu \gamma_\Sigma} O\left(\max\left\{\sqrt{\frac{\log(2p/\delta)}{2n}}, 4U^3 g_{n,\delta}^2, \xi_{n,\delta}^2 \right\}\right).
\end{equation}
In both (a) and (b),
\begin{equation}
  \|\widehat{\theta}-\theta_0\|_1 \leq 4 \sqrt{k} \|\widehat{\theta}-\theta_0\|_2.
\end{equation}

\end{theorem}

Theorem \ref{cor:non-ortho-rate} is our first main result. It gives a finite-sample bound on the Plug-In Regularized Estimator in terms of the squared first-stage rate $g_{n,\delta}^2$, where the rate can be either in $\ell_{\infty}$ (a) or $\ell_{2}$ (b) space, and the oracle rate in a parametric problem $\sqrt{\frac{\log(2p/\delta)}{2n}}$. By orthogonality, the first-stage bias has a second-order effect on the gradient of the loss function. As a result, the  level of $\ell_1$-regularization penalty $\lambda$, sufficient to dominate the noise of the problem, exhibits a second-order dependence on the first-stage rate  $g_{n,\delta}$. Thus, the finite-sample bound follows.

Remarkably, the first-stage bias has no effect on the curvature parameter $\nu \gamma_\Sigma$  of the loss function. This is a unique feature of the convexity of the loss function, the $\ell_1$  penalty and the sparsity of $\theta_0$.  By convexity, the minimizer of $\ell_1$-regularized loss belongs to a restricted subset of $p$-dimensional space. On this subset, the first-stage bias scales with the sparsity index $k$, rather than the total dimension $p$, and therefore is negligible. This result has been shown for Example \ref{ex:linear-intro} (\cite{semenova:17}), however, establishing this result for a general class of nonlinear semiparametric models is the novelty of this work.

\subsubsection{Verification of Assumption \ref{ass:nuisance}}
\label{sec:fsrate}
In this section, we give specific constructions of nuisance realization sets for linear and logistic sparse models, thereby demonstrating that Assumption \ref{ass:nuisance} is plausible.

\begin{remark}[Linear Sparse Model]
\label{rm:lin}
Suppose $g(z)=\mathbb{E}[v|z]$ is a conditional expectation function of an observed random variable $v$. Let $p(z)$ be a $d_p$-vector of basis functions. Suppose $g(z) = p(z)'\alpha_0$, where $\alpha \in \mathcal{R}^{d_p}, d_p \gg n$ is a sparse vector with the sparsity index $k_{\alpha} = \| \alpha_0\|_0$.  Suppose the following regularity conditions hold: (a) Bounded basis: $\max_{1 \leq j \leq d_p} |p_j(z)| \leq \bar{B}$ a.s. and $\|p(z) \|_{P,2} \leq \bar{B}$. (b) Identification: there exists $\kappa_{\text{min}}>0$ such that $\text{min} \text{eig} \quad \mathbb{E} p(z_i) p(z_i)^\top \geq \kappa_{\text{min}}>0$. (c) SubGaussian entries of gradient. There exists $\bar{\sigma}< \infty$ s.t. $\{ (v - g_0(z))\cdot p_j(z), j=1,2,\dots, p_d \}$ are $\bar{\sigma}$-subGaussian r.v. Let $\lambda_{\alpha}$ obey $\lambda_{\alpha} \geq 2(\bar{B}^2 + \bar{\sigma})\sqrt{\frac{\log (2p_d/\delta)}{n}}$.  Define the Lasso estimator of $\alpha_0$ on auxiliary sample $S'$ as $$\widehat{\alpha}:= \arg \min_{\alpha \in \mathcal{R}^{d_p}} \frac{1}{n} \sum_{i \in S'} (v_i - p(z_i)'\alpha)^2 + \lambda_{\alpha} \| \alpha \|_1$$ and the first-stage estimate as $\widehat{g}(z) = p(z)'\widehat{\alpha}$.

For the case of $\ell_{\infty}$-norm, define the nuisance realization set ${\mathcal G}_{n,\delta}$ as
\begin{align*}
    {\mathcal G}_{n,\delta} = \bigg \{ p(z)' \alpha, \quad  \| \alpha - \alpha_0 \|_1 \leq  \frac{12 k_{\alpha} }{\kappa_{\text{min}}} \lambda
    \bigg\}
\end{align*}
Then, by Theorem \ref{thm:main-convex} in Appendix \ref{sec:app_proof}, w.p. $1-4 \delta$, $\widehat{g}(z) \in {\mathcal G}_{n,\delta}$ and Assumption \ref{ass:nuisance} is satisfied with $g_{n,\delta}=\bar{B}\frac{12 k_{\alpha} }{\kappa_{\text{min}}} \lambda$.

For the case $\ell_2$-norm, define the nuisance realization set ${\mathcal G}_{n,\delta}$ as
\begin{align*}
    {\mathcal G}_{n,\delta} = \bigg \{ p(z)' \alpha, \quad  \| \alpha - \alpha_0 \|_2 \leq  \frac{3 \sqrt{k_{\alpha}} }{\kappa_{\text{min}}} \lambda
    \bigg\}
\end{align*}
Then, by Theorem \ref{thm:main-convex} in Appendix \ref{sec:app_proof}, w.p. $1-4 \delta$, $\widehat{g}(z) \in {\mathcal G}_{n,\delta}$ and Assumption \ref{ass:nuisance} is satisfied with $g_{n,\delta}=\bar{B}\frac{3 \sqrt{k_{\alpha}} }{\kappa_{\text{min}}} \lambda $.

\end{remark}

\begin{remark}[Logistic Sparse Model]
\label{rm:log}
Suppose $g(z)=\mathbb{E}[v|z]$ is a conditional expectation function of an observed random variable $v \in \{0,1\}$. Further, suppose $g(z) = {\mathcal L}(p(z)'\alpha_0)$, where ${\mathcal L}(t) = \frac{1}{1+ \exp(-t)}$ is the logistic function and $\alpha, k_{\alpha},p(x)$ are as in Remark \ref{rm:lin}. Suppose regularity conditions (a,b) from Remark \ref{rm:lin} hold. In addition, suppose $\| \alpha \|_1 \leq R_0$ and  there exists $\nu >0$ such that $\inf_{t \in [- \bar{B} R_0, \bar{B} R_0] }{\mathcal L}(t) (1-{\mathcal L}(t)) \geq \nu$.  Let $\lambda_{\alpha}$ be such that $\lambda_{\alpha} \geq 2(\bar{B}^2/4 +\frac{\bar{B}}{4}) \sqrt{\frac{\log (2p_d/\delta)}{n}}$.  Define the logistic Lasso estimator of $\alpha_0$ on auxiliary sample $S'$ as $$\widehat{\alpha}:= \arg \min_{\alpha \in \mathcal{R}^{d_p}} \frac{1}{n} \sum_{i \in S'}- v_i \log ({\mathcal L}(p(z_i)'\alpha)) - (1-v_i) \log(1- {\mathcal L}(p(z_i)'\alpha)) + \lambda_{\alpha} \| \alpha \|_1$$ and the first-stage estimate as $\widehat{g}(z) = {\mathcal L}(p(z)'\widehat{\alpha})$. For the case of $\ell_{\infty}$-norm, define the nuisance realization set ${\mathcal G}_{n,\delta}$ as
\begin{align*}
    {\mathcal G}_{n,\delta} = \bigg \{ {\mathcal L}(p(z)' \alpha), \quad  \| \alpha - \alpha_0 \|_1 \leq  \frac{12 k_{\alpha} }{\nu \kappa_{\text{min}}} \lambda
    \bigg\}
\end{align*}
Then, by Theorem \ref{thm:main-convex} in Appendix \ref{sec:app_proof}, w.p. $1-4 \delta$, $\widehat{g}(z) \in {\mathcal G}_{n,\delta}$ and Assumption \ref{ass:nuisance} is satisfied with $g_{n,\delta}=\frac{\bar{B}}{4}\frac{12 k_{\alpha} }{\nu\kappa_{\text{min}}} \lambda$.
For the case $\ell_2$-norm, define the nuisance realization set ${\mathcal G}_{n,\delta}$ as
\begin{align*}
    {\mathcal G}_{n,\delta} = \bigg \{ {\mathcal L}(p(z)' \alpha), \quad  \| \alpha - \alpha_0 \|_2 \leq  \frac{3 \sqrt{k_{\alpha}} }{\nu\kappa_{\text{min}}} \lambda
    \bigg\}
\end{align*}
Then, by Theorem \ref{thm:main-convex} in Appendix \ref{sec:app_proof}, w.p. $1-4 \delta$, $\widehat{g}(z) \in {\mathcal G}_{n,\delta}$ and Assumption \ref{ass:nuisance} is satisfied with $g_{n,\delta}=\frac{\bar{B}}{4}\frac{3 \sqrt{k_{\alpha}} }{\kappa_{\text{min}}} \lambda $.

\end{remark}

Remarks \ref{rm:lin} and \ref{rm:log} are similar to the existing results in the  literature (see, e.g., \cite{belloni:11}, \cite{orthogStructural}, and \cite{Negahban2012}). To reflect the specific dependence on the constants $U,\bar{B},\bar{\sigma}$, we prove Remarks \ref{rm:lin} and \ref{rm:log} as special cases of Theorem \ref{cor:non-ortho-rate} with squared/logistic loss and absent nuisance parameter.

\subsection{Non-convex $M$-estimator loss}
\label{sec:nonconvex}
In this section, we drop the Assumption \ref{ass:convexity_moment} resulting in a non-convex orthogonal loss.  We prove in Appendix \ref{sec:app_proof} that without convexity, the first-stage error's influence on the loss curvature is proportional to $g_{n,\delta} R$, where  $g_{n,\delta}$ is the first-stage rate and $R$ is $\ell_1$-radius of the search set. Because the regularization penalty must dominate the first-stage error to ensure convergence,
$\lambda$ must satisfy $\lambda \gtrsim_P g_{n,\delta} R$.
In order to make the oracle choice of regularization penalty admissible,
 we set the search set $\mathcal{T}$ in Algorithm \ref{def:lasso:intro}  to be
a shrinking $\ell_1$-ball around $\theta_0$ with the $\ell_1$-radius $R(n,\delta)=O(g_{n,\delta})$.  Then, the admissible penalty level $\lambda  \gtrsim_P g_{n,\delta}^2$ leads to oracle convergence rate.  We construct this neighborhood around a preliminary estimator, which we obtain from  Algorithm \ref{def:lasso:intro} with the search set being equal to a bounded $\ell_1$-ball and aggressive choice of regularization parameter. We describe these multi-step procedure in Algorithm \ref{def:lasso:prelim}.

\begin{algorithm}[H]
\begin{flushleft}{\bf Input:}
{\bf Input:} Radii $R_0,R_1$.\\
{\bf Input:} Preliminary and final regularization weights $\lambda_{\text{pre}}$, $\lambda_{\text{fin}}$.
\end{flushleft}
\begin{algorithmic}[1]
\STATE Partition sample into three samples $S_1,S_2,S_3$ each of size $n$
\STATE  Estimate  nuisance $\widehat{g} \in {\mathcal G}$  on the sample $S_1$.
\STATE Estimate $\theta_0$ via the plug-in $\ell_1$-regularized extremum estimation, i.e.:
    \begin{equation}
    \tilde{\theta} = \arg\min_{\theta\in \mathcal{T}_{\text{pre}}} \frac{1}{n} \sum_{i=1}^n \ell(w_i, \Lambda(z_i, \widehat{g}(z_i))'\theta, \widehat{g}(z_i))  + \lambda_{\text{pre}} \|\theta\|_1,
\end{equation}
where the search set $\mathcal{T}_{\text{pre}} = \{ \theta: \|\theta \|_1 \leq R_0\}$ is an $\ell_1$-ball of radius $R_0$ around $0$.
\STATE Estimate $\theta_0$ via the plug-in $\ell_1$-regularized extremum estimation, i.e.:
    \begin{equation}
    \widehat{\theta} = \arg\min_{\theta  \in \mathcal{T}_{\text{fin}}} \frac{1}{n} \sum_{i=1}^n \ell(w_i, \Lambda(z_i, \widehat{g}(z_i))'\theta, \widehat{g}(z_i))  + \lambda_{\text{fin}} \|\theta\|_1,
\end{equation}
where the search set $\mathcal{T}_{\text{fin}} = \{ \theta: \|\theta - \tilde{\theta} \|_1 \leq R_1\}$ is an $\ell_1$-ball of radius $R_1$ around $\tilde{\theta}$.
\end{algorithmic}
\caption{Plug-in Regularized Estimator with Preliminary Step}
\label{def:lasso:prelim}
\end{algorithm}

\begin{theorem}[Convergence Rate of the Plug-in Regularized Estimator with Preliminary Step]\label{thm:main-non-convex} Suppose that the nuisance space $\mathcal G$
is equipped with the norm $\|g\|_{\infty,1}= \sup_{w\in W} \|g(w)\|_1$. Suppose  Assumptions
\ref{ass:orthogonal}, \ref{ass:nuisance},   \ref{ass:smooth}, \ref{ass:identification} hold and  $\|\theta_0\|_{\infty} \leq U$.
Let $R_0 \leq k U$,$B = 4U^3$, $L=3U^3$, $\epsilon_{n,\delta}=U^2\sqrt{\frac{\log (2p/\delta)}{2n}}$
  $\tau_{n,\delta}=4U^5k \sqrt{\frac{2 \log p}{n}}+U^3 \sqrt{\frac{4\log(2\,p/\delta)}{n}}$. Let radius of search be
\begin{equation}\label{eqn:second-radius}
     R_1(n, 4\delta) = \frac{8k}{\gamma} \left(\epsilon_{n,\delta} + B g_{n,\delta}^2 + (\tau_{n,\delta} + Lg_{n,\delta} ) R_0\right)
 \end{equation}
Then, the Plug-in Regularized Estimator of Algorithm \ref{def:lasso:prelim} with regularization parameters $\lambda_{pre}:  \frac{\lambda_{pre}}{2} \geq  \epsilon_{n,\delta} + B g_{n,\delta}^2   + (\tau_{n,\delta} + L (g_{n,\delta} )) R_0$ and  $\lambda_{fin}$ satisfying $\frac{\lambda_{fin}}{2} \geq  \epsilon_{n,\delta} + B g_{n,\delta}^2  + (\tau_{n,\delta} + L (g_{n,\delta} )) R_1(n, \delta)$
achieves w.p. $1-8\delta$ a rate of:
\begin{equation}
  \|\widehat{\theta}-\theta_0\|_2 \leq  \frac{\sqrt{k}}{\nu \gamma_\Sigma} O\left(\max\left\{\epsilon_{n,\delta}, Bg_{n,\delta}^2, \tau_{n,\delta}^2\frac{k R_0}{\gamma}, (g_{n,\delta}^2 + \xi_{n,\delta}^2) \frac{L^2\,k\,R_0}{\gamma}\right\}\right)
\end{equation}
In addition, the $\ell_1$ bound holds
\begin{equation}
    \|\widehat{\theta}-\theta_0\|_1 \leq \frac{6k}{\nu \gamma_\Sigma} O\left(\max\left\{\epsilon_{n,\delta}, Bg_{n,\delta}^2, \tau_{n,\delta}^2\frac{k R_0}{\gamma}, (g_{n,\delta}^2 + \xi_{n,\delta}^2) \frac{L^2\,k\,R_0}{\gamma}\right\}\right)
\end{equation}
\end{theorem}

Theorem \ref{thm:main-non-convex} is our second main result. It gives a finite-sample bound on the Plug-In Regularized Estimator with Preliminary Step in terms of the squared first-stage rate $g_{n,\delta}^2$ in $\ell_{\infty}$ norm and the model primitives. It shows that the absence of convexity of the loss function can be substituted by local search in a shrinking neighborhood of the true parameter, where this neighborhood is constructed around a slowly converging preliminary estimator. This estimator is constructed as a local minimum of $\ell_1$-regularized orthogonal loss in $R_0$ $
\ell_1$-ball and aggressive choice of regularization penalty.

\subsection{Construction of an orthogonal conditional moment restriction}
\label{sec:orthogonalization}

In this section, we drop  Assumption \ref{ass:orthogonal}. Starting from any system of CMRs
 \eqref{eq:main}-\eqref{eq:cond_exog}, we obtain an orthogonal CMR that obeys Assumption \ref{ass:orthogonal}. We also provide primitive sufficient conditions on  \eqref{eq:main}-\eqref{eq:cond_exog} to ensure that the orthogonal CMR obeys Assumptions \ref{ass:nuisance}-\ref{ass:identification}.

\begin{theorem}[Bias Correction Term for a Nuisance Function Determined by a Conditional Exogeneity Restriction]

\label{lem:general}
Let $g_0(z)$ be a nuisance parameter defined by \eqref{eq:cond_exog}.  Define the bias correction term $\alpha(w,\tilde{g})$ for the moment $m(w,t,g)$ as
\begin{align}
\label{eq:alpha:gen}
\alpha(w,\tilde{g}):= -h(z) I(z)^{-1} R(w,g),
\end{align}
where the nuisance parameter $\tilde{g}$ is  vector-valued function of $z$ that consists of $h(z), I(z),g(z)$ (i.e,  $\tilde{g}(z) = \{h(z), I(z),g(z)\}$). The true values of each function are
 $$h_0(z)=\mathbb{E}[ \nabla_{\gamma} m(z,\Lambda(z, g_0(z))'\theta_0,g_0(z))|z], $$ $I_0(z):= \mathbb{E} [ \nabla_{\gamma} R(w,g_0)|z]$ is the Gateaux derivative of the expected generalized residual $\mathbb{E} [R(w,g)|z]$ with respect to $g$ conditionally on $z$. Let the conditional moment restriction  be
 \begin{equation}
     \label{eq:rho:phi}
     \phi(w,t,\tilde{g}) = m(w,t,g) + \alpha(w,\tilde{g}).
 \end{equation}
Then, the unconditional moment $\rho(w,\theta,\tilde{g})$
 \begin{align*}
     \rho(w,\theta,\tilde{g})=  \phi(w,\Lambda(z,g(z))'\theta,\tilde{g}) \cdot \Lambda(z,g(z))
 \end{align*}
satisfies Assumption \ref{ass:orthogonal} with the nuisance parameter $\tilde{g}(z)$.
\end{theorem}

Theorem  \ref{lem:general} presents the construction of a conditionally orthogonal CMR starting from a non-orthogonal one. The special cases of this theorem have been known before. For example, when $g(z)=\mathbb{E}[v|z]$ is a conditional expectation of an observed variable $v$, the bias correction term takes the form
$$ \alpha(w,\tilde{g}) = h(z) (v - g(z)),$$
and $\tilde{g}(z) = \{g(z),h(z) \}$ (\cite{Newey:94}). For another example, let $u \in (0,1)$ be a  quantile level and $$R(w,g) = u - 1_{\{ v \leq g(z)\}}$$ defines a conditional $u$-quantile of $v$. Then, the bias correction term
$$ \alpha(w,\tilde{g}) = h(z) \frac{u - 1_{\{ v \leq g(z)\}}}{f_v(z)},$$
$f_v(z)$ is the conditional density of $v$ given $z$, and $\tilde{g}(z) = \{g(z),h(z),f_v(z) \}$  (\cite{IchimuraNewey:17}). Theorem \ref{lem:general} considers the nuisance parameter $g_0(z)$ identified by a conditional exogeneity restriction \eqref{eq:cond_exog}.

The additive structure of the bias correction term in  Theorem \ref{lem:general} implies the additive characterization of the orthogonal loss.
Let $K(w,t,g(z)): \mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^d\rightarrow \mathbb{R}$ be any solution to the following Ordinary Differential Equation
\begin{align}
   \nabla_t K(w,t,g(z)) = m(w,t,g(z)).
\end{align}
We refer to $K(w,t,g(z))$ as original $M$-estimator loss.
Then, the orthogonal loss function $\ell(w,t,\tilde{g}(z))$ as
\begin{align}
\label{eq:characterization}
    \ell(w,\Lambda(z,g(z))'\theta,\tilde{g}(z)) :&=K(w,\Lambda(z,g(z))'\theta,g(z)) \\
    &+ \alpha(w,\tilde{g}) \Lambda(z,g(z))'\theta \nonumber
\end{align}
is an admissible solution to \eqref{eq:ode} and a valid orthogonal loss.

In Lemmas \ref{lem:ver:nuisance} and \ref{lem:ver:ass}, we give simple conditions on the original CMRs \eqref{eq:main}-\eqref{eq:cond_exog} so that
the orthogonal CMR \eqref{eq:rho:phi} obeys the conditions of Theorem \ref{cor:non-ortho-rate} and \ref{thm:main-non-convex}.

\begin{lemma}[Plausibility of Assumption \ref{ass:nuisance} for orthogonal CMR $\phi(w,t,\tilde{g}$]
\label{lem:ver:nuisance}
(1) Suppose $h(z) = \mathbb{E}[\nabla_{\gamma} m(w,\Lambda(z,g_0(z))'\theta_0,g_0(z))|z] = R_h(z,\theta,g)$ is a  known function of $z,\theta,g$. Let $\tilde{\theta}$ be a preliminary estimator of $\theta$ defined as an output of Algorithm \ref{def:lasso:intro} with
a convex loss function $K(w,\Lambda(z,g(z))'\theta,g(z))$, search set $\mathcal{T}=\mathcal{R}^p$, and regularization penalty $\lambda_{\text{fs}}$: $\lambda_{\text{fs}}/2 \geq U g_{n,\delta}+U g_{n,\delta}^3 +U^2\sqrt{\frac{\log (2p/\delta)}{2n}}$.
Then,
$\widehat{h}(z)=R_h(z,\tilde{\theta},\widehat{g})$ belongs to the following realization set ${\mathcal H}_{n,\delta}$ w.p. $1-5\delta$
\begin{align*}
    {\mathcal H}_{n,\delta}= \bigg \{ R_h(w,\theta,g): \| g -g_0\|_{\infty} \leq g_{n,\delta}, \| \theta - \theta_0\|_1 \leq \theta_{n,\delta} \bigg \}.
\end{align*}
The set ${\mathcal H}_{n,\delta}$ shrinks at rate $h_{n,\delta} = U^2 \theta_{n,\delta} + U g_{n,\delta}$ where $\theta_{n,\delta} = \frac{6k}{\nu \gamma_{\Sigma}} \lambda_{\text{fs}}$.
(2) Suppose  $I(z) = \mathbb{E} \nabla_{\gamma} [R(w,g)|z] = R_I(z,g)$ is a  known function of $z,g$. Then, $\widehat{I}(z)=R_I(z,\widehat{g}) \in I_{n,\delta}$  w.p. $1-\delta$
\begin{align*}
    I_{n,\delta}=\bigg\{ R_I(w,g): \| g -g_0\|_{\infty} \leq g_{n,\delta} \bigg \}
\end{align*}
and this set shrinks at rate $i_{n,\delta} = U g_{n,\delta}$

\end{lemma}

\begin{lemma}[Verification of Assumptions \ref{ass:smooth}-\ref{ass:convexity_moment} for orthogonal CMR $\phi(w,t,\tilde{g}$]
\label{lem:ver:ass}
(a) Assumptions \ref{ass:identification} and \ref{ass:convexity_moment} holds for the function $m:\mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^d\rightarrow \mathbb{R}$ in \eqref{eq:main} if and only if it holds for $\phi:\mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^d\rightarrow \mathbb{R}$ in \eqref{eq:rho:phi}.
(b) Suppose the following conditions hold. (1) $\{ \mathcal W, {\mathcal Z}, \Theta, {\mathcal G}, m, \Lambda)$ is  $U$-smooth. (2) $|R(w,\gamma)|, \|\nabla_{ \gamma}  R(w,\gamma)\|$, $\|\nabla_{\gamma \gamma}  R(w,\gamma)\| \leq U$. (3) Let $I(z)$ be the realization set for $I_0(z)= \mathbb{E}[ \nabla_{ \gamma}  R(w,g_0(z))|z]$. For any $i(z) \in I(z), \inf_{z \in {\mathcal Z}} |i(z)| \geq E>0$. Then, the conditional moment model $\{ \mathcal W, {\mathcal Z}, \Theta, \tilde{{\mathcal G}}, \phi, \Lambda)$ is $U_{\phi}$-smooth with $U_{\phi}=\frac{U}{E}+\frac{U^2}{E} + U + \frac{2U^2}{E^2}+\frac{2U^2}{E^3}+\frac{U}{E^2}$.
\end{lemma}

\begin{comment}
We argue that orthogonalization does not introduce any extra conditions on the model $\{\mathcal W, {\mathcal Z}, \Theta,\tilde{G},m,\Lambda)$ except that Assumption \ref{ass:nuisance} must hold for the new nuisance parameter $\tilde{g}(z)$ with realization set $\tilde{G}$ instead of the old one. Indeed, the correction term $\alpha(w,\tilde{g})$ does not depend on the single index. Therefore, Assumption \ref{ass:convexity_moment} holds for the function $m:\mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^d\rightarrow \mathbb{R}$ if and only if it holds for $\phi:m:\mathcal W\,\times\,\mathbb{R}\,\times\,\mathbb{R}^d\rightarrow \mathbb{R}$ in \eqref{eq:rho:phi}. Moreover, the partial derivative in Assumption \ref{ass:identification} is the same for  $m$ if  and only if it holds for $\phi$:
$$\nabla_{t} E [m(w,\Lambda(z,g_0(z))'\theta_0,g_0(z))|z] = \nabla_{t} E [\phi(w,\Lambda(z,g_0(z))'\theta_0,g_0(z))|z].$$ Finally, Assumption \ref{ass:smooth} holds for $m$ if and only if it holds for $\phi$.

\paragraph{Estimating $h(z)$}  One might wonder how hard it is to estimate $h_0(z)$. Generically, $h_0(z)$ can be estimated in a two-step manner as follows. Suppose that we have an estimator $\widehat{g}$ of the original nuisance parameter $g_0$, as well as a preliminary estimator $\tilde{\theta}$ of our target parameter $\theta_0$ (converging at a rate slower than $n^{-1/2}$). Then we can estimate $\widehat{h}(z)$ in a plug-in manner from moment equation:
\begin{equation}
    \widehat{h}(z) = \mathbb{E}[\nabla_\gamma m(w, \tilde{\theta}, \widehat{g}(z)) | z]
\end{equation}
i.e. $\widehat{h}(z)$ is a regression of the random variable $\nabla_\gamma m(w, \tilde{\theta}, \widehat{g}(z))$ on a vector of covariates $z$.
\end{comment}
\section{Monte-Carlo Simulations}
\label{sec:montecarlo}
\subsection{Monte-Carlo Simulations for Section \ref{sec:selection}}
We performed a monte-carlo analysis of the performance our approach. We considered a special case of the model given in the previous paragraph, with data-generating process:
\begin{align*}
y ~=~& x' h(u) + \epsilon,\\
h(u) ~=~& \theta + A_1 u + A_2 \left(u^2 - \mathbb{E}\left[u^2\right]\right)\\
\Pr(d=1 | x, u) ~=~& {\mathcal L}(\sigma_\eta (x'\beta + u'\gamma))\\
x \sim U(-\sigma_x,\sigma_x)^p,~& u\sim U(-\sigma_u, \sigma_u)^d,~ \epsilon \sim N(0, \sigma_\epsilon)
\end{align*}
Such a setting captures the case where $z=(x,u)$, $x$ is a treatment vector and the component $u$ creates treatment effect heterogeneity in a polynomial form. Our goal is to estimate the average treatment effect $\theta$ of $x$, averaging out the effect of $u$. The fact that $d$ is correlated with $u$, does not allow us to simply run a regression between $y$ and $x$ on the non-missing data. We considered the case where $k_\theta$ entries of $\theta$ are non-zero wlog we assumed that these are the first $k_\theta$ coefficients of $\theta$. Moreover, the matrices $A_1$ and $A_2$ are also sparse, in the sense that only the rows that correspond to the support of $\theta$ are non-zero and among the columns only $k_u$ of the entries are non-zero (i.e. only $k_u$ of the variables $u$ have an effect). The non-zero coefficients of $A_1$ and $A_2$ where drawn independently from $U(1, 2)$. The coefficients $\beta$ where drawn independently from $U(0, 1)$ and the coefficients $\gamma$ independently from $U(2,3)$. The non-zero coefficients of $\theta_0$ where equal to $2$.

\begin{figure}[tpb]
\centering
    \includegraphics[scale=.7]{l2_errors_missing.png}
    \caption{\footnotesize{\emph{Missing Data.} Distribution of $\ell_2$ errors of estimate $\hat{\theta}$ from each method, i.e. $\|\hat{\theta}_{\text{method}} - \theta_0\|_2$, across $1000$ experiments. Parameters: $n=5000$, $p=20$, $d=20$, $k_\theta=1$, $k_u=1$, $\theta_0=(2, 0, \ldots, 0)$, $\sigma_\eta=0.1$, $\sigma_x=\sigma_u=3$, $\sigma_\epsilon=1$, $\lambda=\sqrt{\log(p)/n}$.}}
    \label{fig:missing-1}
\end{figure}

The results of $1000$ experiments are depicted in Figures \ref{fig:missing-1} and \ref{fig:missing-2}. We compared three main approaches: i) the direct approach (Direct), where we simply run a lasso regression of $y$ on $x, x*u$ (where $x*u$ denotes all pairwise product terms) using only the non-missing data, ii) the non-orthogonal inverse propensity approach (IPS) where we use the non-orthogonal moment $M$ and we estimate the propensity in a cross-fitting manner, iii) the orthogonal approach (Ortho) based on moment $\Phi$, where we estimate the propensity and function $q_0(z)$ in a cross-fitting manner. The propensity was estimated with a logistic lasso, where the regularization weight was chosen with cross-validation. The function $q_0$ was estimated by running a Random Forest regression between $y$ and $x, u$ and then subtracting a term $x'\tilde{\theta}$, where $\tilde{\theta}$ is a preliminary estimate of $\theta$ computed via the non-orthogonal IPS algorithm. For the second stage estimation in both IPS and Ortho we performed $\ell_1$ penalized estimation with $\lambda=\sqrt{\log(p)/n}$. For the direct method we selected the regularization weight $\lambda$ of the Lasso via cross validation. Apart from these three main methods, we also evaluated the performance of \emph{oracle} versions of both the IPS and the Ortho method, where the nuisance functions $p_0$ and $q_0$ are not estimated but rather the true ones are given by an oracle. These are infeasible methods, evaluated primarily so as to examine the effect of using plugin estimates of these functions as opposed to oracle versions of them. Interestingly, we observe that the orthogonal approach achieves very similar performance to its oracle version, unlike the IPS approach.

\begin{figure}[htpb]
    \centering
    \includegraphics[scale=0.7]{l2_decrease_missing.png}
    \caption{\footnotesize{\emph{Missing Data.} Distribution of decrease in $\ell_2$ errors of estimate $\hat{\theta}$ between each method and the proposed Ortho method, i.e. $\|\hat{\theta}_{\text{method}}-\theta_0\|_2 - \|\hat{\theta}_{\text{Ortho}} - \theta_0\|_2$, across $1000$ experiments. We observe that the proposed method leads to a statistically significant positive decrease in error, as compared to each other method (except its oracle version) and even outperforms the oracle version of the IPS approach. Moreover, its performance compared to its oracle version is statistically identical. Parameters: $n=5000$, $p=20$, $d=20$, $k_\theta=1$, $k_u=1$, $\theta_0=(2, 0, \ldots, 0)$, $\sigma_\eta=0.1$, $\sigma_x=\sigma_u=3$, $\sigma_\epsilon=1$, $\lambda=\sqrt{\log(p)/n}$.}}
    \label{fig:missing-2}
\end{figure}

\begin{figure}[htpb]
    \centering
    \begin{subfigure}[t]{.9\textwidth}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{dmr_kz_1_se_1_dx_sx.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{ipmr_kz_1_se_1_dx_sx.png}
    \end{subfigure}
    \subcaption{Varying $(p, \sigma_x)$}
    \end{subfigure}
    \begin{subfigure}[t]{0.9\textwidth}
    \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{dmr_kz_1_sx_3_dx_se.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.49\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{ipmr_kz_1_sx_3_dx_se.png}
    \end{subfigure}
    \subcaption{Varying $(p, \sigma_\epsilon)$}
    \end{subfigure}
    \caption{\footnotesize{\emph{Missing Data.} Median percentage decrease in $\ell_2$ error between (Direct, IPS) and Ortho, i.e. $100\times \frac{\text{error}_{\text{Method}} - \text{error}_{\text{Ortho}}}{\text{error}_{\text{Method}}}$ across $100$ experiments as two parameters of the DGP vary. When a parameter is not shown then the following default values are assumed: $n=5000$, $p=20$, $d=20$, $k_\theta=1$, $k_u=1$, $\theta_0=(2, 0, \ldots, 0)$, $\sigma_\eta=0.1$, $\sigma_x=\sigma_u=3$, $\sigma_\epsilon=1$, $\lambda=\sqrt{\log(p)/n}$.}}
    \label{fig:missing-3}
\end{figure}

\subsection{Monte-Carlo Simulations for Section~\ref{sec:strategic}}
We performed a monte-carlo analysis of the performance our orthogonal estimation approach. We considered a special case of the model, where the errors follow a gambit distribution and hence the probability of entry takes a logistic linear form:
\begin{align*}
\Pr[y_i=1 | x] ~=~& {\mathcal L}\left(x' \alpha_0^i + g_0^{-i}(x)\Delta_0^i\right),\\
x \sim U(-\sigma_x,\sigma_x)^p
\end{align*}
where $g_0^i:[-\sigma_x, \sigma_x]^p \rightarrow [0,1]$ is the equilibrium mapping of the game of incomplete information. We considered two data generating processes (DGPs): i) a stylized dgp (DGP1) where $\Delta_0^2=0$ and therefore the estimation of $g_0^2$ boils down to a logistic lasso, while the estimation of $\alpha_0^1, \Delta_0^1$ depends on the estimate $g_0^2$, ii) an equilibrium based dgp (DGP2) where we computed the fixed point $g_0$ of the equilibrium equations and then generated entry decisions from the logistic function. In this setting estimating $g_0^2$ is non-trivial as the dependence on $x$ might not follow a logistic-linear form. We denote with $k_i = \|\alpha_0^i\|$, the sparsity of the coefficient associated with each player.

\begin{figure}[tpb]
    \centering
    \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_error_one_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_decrease_one_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_error_one_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_decrease_one_player.png}
    \end{subfigure}
    \caption{\footnotesize{\emph{Games.} Distribution of $\ell_1$ and $\ell_2$ errors and error decreases of estimate $\hat{\theta}$ from each method, i.e. $\|\hat{\theta}_{\text{method}} - \theta_0\|_2$, across $100$ experiments based on the games setting DGP1. Parameters: $n=10000$, $p=1000$, $k_1=1$, $k_2=3$, $\alpha_0^1=(1, 0, \ldots, 0)$, $\alpha_0^2=(u_1, u_2, u_3, 0, \ldots, 0)$, with $u_i\sim U(-2, 2)$, $\Delta_0^1=-2$, $\Delta_0^2=0$, $\sigma_x=1$, $\lambda=\sqrt{\log(p)/4n}$.}}
    \label{fig:games-1}
\end{figure}

We evaluated the performance of several approaches for estimating the parameters of player $1$, i.e. $\theta_0=(\alpha_0^1, \Delta_0^1)$. The results of $100$ experiments are depicted in Figures \ref{fig:games-1}, \ref{fig:games-2} and \ref{fig:games-3}. We compared three main approaches: i) an \emph{infeasible} oracle logistic (OracleLG) approach, where we used the true entry probability of player $2$, $g_0^2$ and then run a logistic lasso for estimating $\theta_0$, ii) a non-orthogonal two-stage logistic lasso (2SLG), where we estimated $g_0^2$ in the first stage using a logistic lasso (potentially mis-specified model in DGP2) in a cross-fitting manner and then run a second stage logistic lasso for estimating $\theta_0$, iii) an orthogonal two stage approach (2SOrthoLG), where in the first stage we estimated $g_0^2$ and a preliminary $\tilde{\theta}_0$, via a logistic lasso, in a cross-fitting manner, so as to compute the orthogonal correction term and in the second stage we run an orthogonal loss minimization. We observe that 2SOrthoLG consistently outperforms 2SLG and is at par with the infeasible OracleLG.

\begin{figure}[tpb]
    \centering
    \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_error_two_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_decrease_two_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_error_two_player.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_decrease_two_player.png}
    \end{subfigure}
    \caption{\footnotesize{\emph{Games.} Distribution of $\ell_1$ and $\ell_2$ errors and error decreases of estimate $\hat{\theta}$ from each method, i.e. $\|\hat{\theta}_{\text{method}} - \theta_0\|_2$, across $100$ experiments based on the games setting DGP2. Parameters: $n=10000$, $p=1000$, $k_1=1$, $k_2=3$, $\alpha_0^1=(1, 0, \ldots, 0)$, $\alpha_0^2=(u_1, u_2, u_3, 0, \ldots, 0)$, with $u_i\sim U(-2, 2)$, $\Delta_0^1=-2$, $\Delta_0^2=-3$, $\sigma_x=1$, $\lambda=\sqrt{\log(p)/4n}$.}}
    \label{fig:games-2}
\end{figure}

\begin{figure}[tpb]
    \centering
    \begin{subfigure}[t]{0.46\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_games_varying_p_sigma_n_5000.png}
        \caption{$n=5000$}
    \end{subfigure}
    ~
     \begin{subfigure}[t]{0.46\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_games_varying_p_sigma_n_10000.png}
        \caption{$n=10000$}
    \end{subfigure}
    \caption{\footnotesize{\emph{Games.} Median percentage decrease in $\ell_2$ error between 2SLG and 2SOrthoLG, i.e. $100\times \frac{\text{error}_{\text{2SLG}} - \text{error}_{\text{2SOrthoLG}}}{\text{error}_{\text{2SLG}}}$ across $100$ experiments based on the games  DGP1 and as $p$ varies in $\{1000, 2000, 5000\}$ and $\sigma_x$ varies in $\{1, 2, 3\}$. Parameters: $k_1=1$, $k_2=3$, $\alpha_0^1=(1, 0, \ldots, 0)$, $\alpha_0^2=(u_1, u_2, u_3, 0, \ldots, 0)$, with $u_i\sim U(-2, 2)$, $\Delta_0^1=-2$, $\Delta_0^2=-3$, $\lambda=\sqrt{\log(p)/4n}$.}}
    \label{fig:games-3}
\end{figure}

\subsection{Monte Carlo Simulations for Section~\ref{sec:nonlinearTE}}

We performed an experimental evaluation of our orthogonal estimation method for the case of the logistic link function presented in Example \ref{ex:logistic}. We considered the following concrete data generating process, which is a non-linear generalization of the Partially-Linear Regression model:
\begin{align*}
    \Pr[y=1|u, \tau] =& {\mathcal L}(\tau \cdot u'\theta_0 + u'\alpha_0), & y\in \{0, 1\}\\
    \tau =& u'\beta_0 + \eta,\\
    \eta \sim N(0, \sigma_\eta),~~& u \sim U(-\sigma_u, \sigma_u)
\end{align*}
where $\tau\in \mathbb{R}$ is a base treatment variable, $u\in \mathbb{R}^p$ is a high-dimensional vector of features/control variables and $y\in \mathbb{R}$ is an outcome of interest. The target parameter $\theta_0$ corresponds to a linear parametrization of the heterogeneous treatment effect of $\tau$ on the utility of an agent in a binary discrete choice model. The features $u$ also have a confounding effect, in the sense that they have a direct impact on the utility apart from determining the heterogeneity in the effect of $\tau$.

In this setting our orthogonal approach with cross-fitting described in this section boils down to the following steps:
\begin{enumerate}
    \item Split the data-set $S$ in half and on the first sample:
    \begin{enumerate}
        \item Compute estimate $\hat{\beta}$ of $\beta_0$ via a Lasso regression of $\tau$ on $u$.
        \item Compute a preliminary estimate $\tilde{\theta}$ of $\theta_0$ and an estimate $\hat{\alpha}$ of $\alpha_0$, by running a logistic $\ell_1$ penalized regression of $y$ on $\tau \cdot u$ and $u$.
        \item Let the estimates of the nuisance functions be: $\hat{\pi}(u) = u'\hat{\beta}$, $\hat{q}(u) = u'\hat{\beta}\cdot u'\tilde{\theta} + u'\hat{\alpha}$, $\hat{V}(z) = {\mathcal L}'(\tau u'\tilde{\theta} + u'\hat{\alpha})$ and evaluate them on the other half of the data to obtain nuisance quantities, $\hat{\pi}_i = \hat{\pi}(u_i), \hat{q}_i=\hat{q}(u_i), \hat{V}_i=\hat{V}(z_i)$ for each sample $i$.
    \end{enumerate}
    \item Repeat the above process to compute the nuisance estimates for the first half of the data, by exchanging the role of the two data splits.
    \item  Using the nuisance estimates for all data points, run an orthogonal $\ell_1$ penalized regression based on the loss:
\begin{equation*}
    L_S(w_i, \theta, \hat{g}(z_i)) = \frac{1}{n}\sum_i \frac{y_i\cdot \log\left({\mathcal L}\left((\tau_i - \hat{\pi}_i) u_i'\theta+\hat{q}_i\right)\right) + (1-y_i)\cdot \log\left(1-{\mathcal L}((\tau_i - \hat{\pi}_i) u_i'\theta+\hat{q}_i)\right)}{\hat{V}_i}
\end{equation*}
\end{enumerate}
We compared our approach to a direct approach where we estimate $\theta_0$ by running a logistic $\ell_1$ penalized regression, regressing $y$ on $\tau\cdot u$ and $u$ and then reading the target parameter from the coefficients associated with variables $\tau \cdot u$. Figure~\ref{fig:experiments-logistic} provides a sample of the experimental performance of the two approaches, showing a smaller $\ell_1$ and $\ell_2$ error of the orthogonal approach across $100$ experiments.

\begin{figure}[tpb]
     \centering
    \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_error_logistic.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l2_decrease_logistic.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_error_logistic.png}
    \end{subfigure}
     \begin{subfigure}[t]{0.244\textwidth}
        \centering
        \includegraphics[width=1\textwidth]{l1_decrease_logistic.png}
    \end{subfigure}
    \caption{\footnotesize{\emph{Heterogeneous Treatment Effects with Logistic Link Function.} Direct vs orthogonal estimation for heterogeneous treatment effect model with a logistic link function. We simulated $100$ experiments, with data generating parameters: $n=5000$, $p=2000$, $k=2$, $k_g=\|\alpha_0\|_0=\|\beta_0\|_0=5$, $\sigma_\eta=3$, $\sigma_u=0.5$. Supports of $\alpha_0$ and $\beta_0$ are identical and all non-zero coefficients of $\alpha_0, \beta_0, \theta_0$ are equal to one. The left figure shows the distribution of the $\ell_2$ errors of the two methods as well as the distribution of the decrease in $\ell_2$ error when going from from the direct regression to the orthogonal plug-in estimation across the $100$ experiments. The right figure shows the corresponding quantities for the $\ell_1$ norm}}
    \label{fig:experiments-logistic}
\end{figure}
\section{General case: Finite Sample Theory for Extremum Estimators}
\label{sec:app_proof}

We assume that both the estimation sample $S=\{w_1,\ldots, w_n\}\in {\cal W}^n$ and the auxiliary sample $S'=\{w_1',\ldots, w_n'\}\in {\cal W}^n$ consist of $n$ i.i.d. data points, each drawn from a data generating distribution $D$. We
consider empirical loss function $L_S(\theta, g)$ and population loss
$L_D(\theta, g)$, that depend on a target parameter $\Theta \in \mathbb{R}^p$ and a nuisance component $g$ that can either be a finite-dimensional parameter or a function.

\begin{definition}[Orthogonal Loss]
    \label{def:ortholoss}
    Loss function $L: \Theta \times {\mathcal G}\rightarrow \mathbb{R}$ is orthogonal with respect to the nuisance function if the pathwise derivative  map of its
    gradient at $\theta_0$,
    \begin{equation}
    D_r [g-g_0, \nabla_{\theta} L(\theta_0, g_0)]:= \frac{\partial}{\partial r} \nabla_{\theta} L(\theta_0, r (g-g_0) + g_0)
    \end{equation}
    exists $\forall r \in [0,1)$ and $g \in {\mathcal G}$, and vanishes at $r=0$:
    \begin{equation}
        \forall g\in {\mathcal G}: D_0 [g-g_0, \nabla_{\theta} L(\theta_0, g_0)] = 0
    \end{equation}
\end{definition}

\begin{assumption}[Orthogonality of Population Loss]\label{ass:ortholoss}
The population loss function $L_D$ is orthogonal.
\end{assumption}

\begin{assumption}[Convexity of Empirical Loss]\label{ass:convloss}
The empirical loss $L_S(\theta,g)$ is a convex function of $\theta \in \Theta$ for any $g$ in some neighborhood of ${\mathcal G}_n$ of the true $g_0$.
\end{assumption}

\paragraph{Curvature of the loss} The mere fact that the estimator $\widehat{\theta}$ is a local minimum of the empirical loss $L_S(\cdot, \widehat{g})$ is not sufficient to guarantee that $\widehat{\theta}$ is close to $\theta_0$. Even if we knew that $\widehat{\theta}$ was an approximate minimizer of the population oracle loss $L_D(\cdot, g_0)$, this would not imply that $\widehat{\theta}$ is close to $\theta_0$, unless the loss function $L_D(\cdot, g_0)$ has a large curvature within the search set ${\cal T}$. For a given direction $\nu \in \mathbb{R}^p$, we measure this curvature of loss function $L: \Theta \rightarrow \mathbb{R}$ by the symmetric Bregman distance, considered in \cite{Acharyya:2013,loh2012,loh2017} among others.\footnote{The latter quantity is referred to as the symmetric Bregman distance since it corresponds to a symmetrized version of the Bregman distance, defined as: $D(\theta'~|~\theta) = L(\theta') - L(\theta) - \langle \nabla_{\theta} L(\theta), \theta'-\theta\rangle$, which measures how far the value of $L$ at $\theta'$ is from the value of a linear approximation of $L$ when it is linearized around the point $\theta$. Observe that $H(\theta, \theta') = D(\theta'~|~\theta) + D(\theta~|~\theta')$.}

\begin{definition}[Symmetric Bregman distance]
\label{def:genhessian}
For a differentiable function $L: \Theta \rightarrow \mathbb{R}$, define its symmetric Bregman distance as:
\begin{equation}
    \label{eq:genhess}
    H(\theta_0+\nu, \theta_0):= \langle \nabla_{\theta} L(\theta_0+\nu) - \nabla_{\theta} L(\theta_0) , \nu \rangle
\end{equation}
\end{definition}

\begin{definition}[$(\gamma,\,\kappa_{n,\delta},\tau_{n,\delta})$-Generalized Restricted  Strong Convexity on a set $\mathcal{B}$]

\label{def:GRC}

A differentiable function $L: \Theta \rightarrow \mathbb{R}$ satisfies the GRC property with curvature $\gamma$ and tolerance parameters $(\kappa_{n,\delta},\tau_{n,\delta})$
on a set $\mathcal{B}$ if its symmetric Bregman distance satisfies:
$$\forall \nu \in {\cal B}: H(\theta_0+\nu, \theta_0) \geq \gamma \| \nu \|_2^2 - \kappa_{n,\delta} \| \nu \|_1 - \tau_{n,\delta} \| \nu \|^2_1. $$
\end{definition}

\begin{assumption}[ $(\gamma,\, \kappa_{n,\delta}, \tau_{n,\delta})$-GRC Empirical Oracle Loss on set $\mathcal{B}$]
\label{ass:grc}
There exist curvature $\gamma >0$ and tolerance parameter sequences $(\kappa_{n,\delta}, \tau_{n,\delta})$ such that the empirical oracle loss $L_S(\cdot, g_0)$ satisfies the $(\gamma,\, \kappa_{n,\delta}, \tau_{n,\delta})$-GRC condition on the set $\mathcal{B}$.  w.p. $1-\delta$.
\end{assumption}

\begin{comment}
Assumption \ref{ass:grc} states that the empirical oracle  loss $L_S(\theta,g_0)$  has a positive curvature $\gamma$ in all directions $\nu \in \mathcal{B}$, allowing for the violation described by the tolerance parameters $\tau_{n,\delta},\kappa_{n,\delta}$.
In our further discussion we use notation $H_S(\theta',\theta,g)$ and $H_D(\theta',\theta,g)$
to denote, respectively, symmetric Bregman distances
of the empirical and population losses evaluated at
parameter values $\theta'$ and $\theta$ and nuisance $g$.
In many biostatistic and econometric applications, it is plausible to assume that the population loss $L_D(\cdot, g_0)$ is strongly convex with no violations (satisfies $(\gamma,0,0)$-GRC). In this case, if the difference $H_S(\theta_0+\nu,\theta_0,g_0)-H_D(\theta_0+\nu,\theta_0,g_0)$ between the symmetric Bregman distances of the empirical and population loss converges to zero at rate $\kappa_{n,\delta}$ uniformly over $\nu\in {\cal B}$, then $(\gamma,0,0)$-GRC of $L_D(\theta,g_0)$ implies $(\gamma,\kappa_{n,\delta},0)$-GRC of $L_S(\cdot,g_0)$. Also, if the empirical oracle loss $L_S(\cdot,g_0)$ is twice differentiable, and its Hessian converges at rate $\tau_{n,\delta}$ uniformly over the set
$\{\theta_0 +r \nu: \nu \in \mathcal{B}, r\in [0,1]\}$
to its population counterpart, then
$(\gamma,0,0)$-GRC of $L_D(\cdot, g_0)$ implies $(\gamma,0,\tau_{n,\delta})$-GRC of
$L_S(\cdot, g_0)$.
\end{comment}
\begin{assumption}[Bounded Hessian of the Gradient of Population Loss w.r.t. Nuisance]\label{ass:orthohessian}
The second order path-wise derivative of the gradient
$\nabla_{\theta} L_D(\theta_0, \cdot)$ w.r.t the nuisance parameter:
\begin{equation}
    D_{r}^2[g'-g, \nabla_{\theta}L_D(\theta_0, g )]:=\frac{\partial^2}{\partial r^2}\nabla_{\theta}L_D(\theta_0, r(g'-g)+g )
\end{equation}
exists $\forall r \in [0,1)$ and is bounded as:
$$ \exists B, \forall g \in {\mathcal G}_n, \forall r\in [0,1):  \left\| D_{r}^2[g-g_0, \nabla_{\theta}L_D(\theta_0, g_0 )]
\right\|_{\infty} \leq B \|g - g_0\|^2.  $$
\end{assumption}

When Assumptions~\ref{ass:ortholoss} and ~\ref{ass:orthohessian}
are satisfied, the estimation error in $\widehat{g}$ has a second-order impact on the gradient of the population loss, since by the second-order Taylor expansion:
$$\| \nabla_{\theta} L_D(\theta_0, \widehat{g}) \|_{\infty} \leq  \| \nabla_{\theta} L_D(\theta_0, g_0) \|_{\infty} + B \|\widehat{g}-g_0\|^2 = B \|\widehat{g}-g_0\|^2,$$
where the last equality follows from the first order condition (FOC) for $L_D(\theta, g_0)$
being satisfied at $\theta_0$.

To prove the Algorithm \ref{def:lasso:intro} with a convex non-orthogonal loss, we will make use of the following assumption.
\begin{assumption}[Bounded  Gradient of Population Loss w.r.t. Nuisance]\label{ass:nonortholoss}
The path-wise derivative of the gradient
$\nabla_{\theta} L_D(\theta_0, \cdot)$ w.r.t the nuisance parameter:
\begin{equation}
    D_{r}^2[g'-g, \nabla_{\theta}L_D(\theta_0, g )]:=\frac{\partial^2}{\partial r^2}\nabla_{\theta}L_D(\theta_0, r(g'-g)+g )
\end{equation}
exists $\forall r \in [0,1)$ and is bounded as:
$$ \exists B, \forall g \in {\mathcal G}_n, \forall r\in [0,1):  \left\| D_{r}^2[g-g_0, \nabla_{\theta}L_D(\theta_0, g_0 )]
\right\|_{\infty} \leq B_0 \| g-g_0\| + B \|g - g_0\|^2.  $$
\end{assumption}

\begin{comment}
\paragraph{Convergence of the gradient of the empirical loss $L_S(\theta_0,g)$}  To ensure that the empirical oracle gradient $\nabla_{\theta} L_S(\theta_0, g) $ goes to zero in $\ell_{\infty}$ norm, we assume that the gradient of the empirical loss $\nabla_{\theta} L_S(\theta_0, g)$  concentrates well around its population analogue for each fixed instance of $g \in {\mathcal G}_n$. Crucially, by using different samples in the first and the second stages of Algorithm~\ref{def:lasso:intro}, we do not require the uniform convergence of $\nabla_{\theta} L_S(\theta_0, g)$ over the realization set ${\mathcal G}_n$ of the nuisance $g$, and therefore, we do not restrict the complexity of the function class $\mathcal{G}_n$.
As a result, one can employ high-dimensional, highly complex methods to estimate $g_0$.
\end{comment}

\begin{assumption}[Convergence Rate of Empirical Gradient]\label{ass:lossconv}
We assume that for any fixed $g\in {\mathcal G}_n$, there exists a sequence $\epsilon_{n,\delta}$ such that $ \|\nabla_{\theta} L_S(\theta_0, g) - \nabla_{\theta} L_D(\theta_0, g)\|_{\infty}$ converges at rate $\epsilon_{n,\delta}$ to zero w.p. $1-\delta$. Formally, for any $\delta >0$:
\begin{align*}
\forall g \in {\mathcal G}_n: \Pr\left( \|\nabla_{\theta} L_S(\theta_0, g) - \nabla_{\theta} L_D(\theta_0, g)\|_{\infty} \leq \epsilon_{n,\delta}\right) \geq 1- \delta.
\end{align*}
\end{assumption}

This regularity assumption is a mild requirement. For example, in the case of the $M$-estimation problem with a bounded loss gradient $\|\nabla_{\theta}\ell(w, \theta_0, g)\|_{\infty}\leq B$, Assumption \ref{ass:lossconv} follows from McDiarmid's inequality with $\epsilon_{n,\delta} = O\left(\sqrt{\frac{\log(p/\delta)}{n}}\right)$.

\begin{assumption}[Lipschitz symmetric Bregman distance on $\mathcal{B}$]
\label{ass:liphessian-non-conv}
The empirical symmetric Bregman distance
\begin{equation*}
    H_S(\theta_0+\nu, \theta_0, g) = \ldot{\nabla_{\theta} L_S(\theta_0+\nu, g) - \nabla_{\theta} L_S(\theta_0, g)}{\nu},
\end{equation*}
satisfies the following Lipschitz condition in $g$ uniformly over a set $\mathcal{B}$: $\forall g,g'\in {\mathcal G}_n$, w.p. $1-\delta$:
\begin{equation}
    \forall \nu \in {\cal B}: \left| H_S(\theta_0+\nu, \theta_0, g) - H_S(\theta_0+\nu,\theta_0, g')\right| \leq L (\|g-g'\| + \xi_{n,\delta}) \|\nu\|_1^2.
\end{equation}
\end{assumption}

\begin{theorem}[Convergence Rate of Plug-in Regularized Estimator]\label{thm:main-convex} Let Assumptions
\ref{ass:nuisance},  \ref{ass:ortholoss},  \ref{ass:convloss}, \ref{ass:orthohessian},
\ref{ass:lossconv}, \ref{ass:grc}, \ref{ass:liphessian-non-conv}  are satisfied for $\mathcal{B} = {\mathcal C}(T;3)$. Moreover, assume that $k(\tau_{n,\delta} + L (g_{n,\delta} + \xi_{n,\delta}))=o(1)$ and $n$ is large enough such that $16\,k\,(\tau_{n,\delta} + L (g_{n,\delta} + \xi_{n,\delta}))\leq \gamma/2$. Then, the Plug-in Regularized Estimator of Algorithm \ref{def:lasso:intro} with regularization weight $\lambda$ satisfying $\frac{\lambda}{2}\geq \epsilon_{n,\delta} + \kappa_{n,\delta} + B\,g_{n,\delta}^2$ and a search set $\mathcal{T}=\mathbb{R}^p$ satisfies w.p. $1-4\delta$:
\begin{align}
    \| \widehat{\theta} - \theta_0 \|_2 \leq~& \frac{3\sqrt{k}}{\gamma} \lambda &
     \| \widehat{\theta} - \theta_0 \|_1 \leq~& \frac{12k}{\gamma} \lambda
\label{eq:resultconvex}
\end{align}
Moreover, if Assumption \ref{ass:ortholoss} fails, the Plug-in Regularized Estimator of Algorithm \ref{def:lasso:intro} with aggressive regularization weight $\lambda_{\text{agg}}$ satisfying $\frac{\lambda}{2}\geq \epsilon_{n,\delta} + \kappa_{n,\delta} + B_0 g_{n,\delta} B\,g_{n,\delta}^2$ and a search set $\mathcal{T}=\mathbb{R}^p$ satisfies \eqref{eq:resultconvex} w.p. $1-4\delta$.
\end{theorem}

\subsection{Proof of Main Theorem for Convex Losses}

Throughout the proof we assume that the probabilistic Assumptions \ref{ass:nuisance}, \ref{ass:lossconv}, \ref{ass:grc} and \ref{ass:liphessian-non-conv} hold deteriministically. By a union bound, the probability of that event is at least $1-4\delta$. Hence, the proof below holds with probability $1-3\delta$. Moreover, given that we fix the confidence level $\delta$ we will drop it from the subscripts throughout the proof.

Before moving into the technical details we begin by providing an outline of the proof. We first show (Lemma \ref{lem:fsrsc}) that if the empirical oracle loss $L_S(\cdot, g_0)$ satisfies the $(\gamma, \kappa_{n,\delta}, \tau_{n,\delta})$-GRC condition, then the empirical plug-in loss $L_S(\cdot, \widehat{g})$ also satisfies a $(\gamma/2, \kappa_{n,\delta}, 0)$-GRC condition for sufficiently large sample size $n$, assuming that the first stage estimation is consistent at a reasonable rate. Subsequently (Lemma \ref{lem:subspace}), we show that if the regularization weight is at least $2\|\nabla_{\theta} L_S(\theta_0, \widehat{g})\|_{\infty}$, then the estimation error $\nu=\widehat{\theta}-\theta_0$ must lie in a small cone of the high dimensional space, were most of the mass is placed on the coordinates of the true support. Restricted strong convexity of the plug-in empirical loss and the fact that the estimation error lies in the restricted cone, together with a slightly stronger condition on the weight $\lambda \geq 2\left(\|\nabla_{\theta} L_S(\theta_0, \widehat{g})\|_{\infty}+\kappa_{n,\delta}\right)$, then imply (Lemma \ref{thm:gen-conv}) that the estimation error must be of the order $\frac{\lambda \sqrt{k}}{\gamma}$. We then conclude the proof of the main theorem by invoking orthogonality of the loss function to show that the $\ell_{\infty}$ norm of the gradient of the empirical plug-in loss evaluated at the true parameter, decays at least as fast as $\epsilon_{n,\delta} + B g_{n,\delta}^2$ (Lemma \ref{lem:influence}). Hence, it suffices to set a regularization weight that decays at a rate $\epsilon_{n,\delta} + B g_{n,\delta}^2+\kappa_{n,\delta}$, which leads to the final convergence rate claimed in Theorem \ref{thm:main-convex}.
\begin{lemma}[From Population to Empirical GRC.]\label{lem:pop-to-emp-non-conv}
Suppose the difference between the sample and the population symmetric Bregman distances normalized by $\|\nu\|_1$ converges uniformly over $\nu \in \mathcal{B}$ to zero at rate $\kappa_{n,\delta}$, i.e., w.p. $1-\delta$:
\begin{align*}
    \sup_{\nu \in \mathcal{B} }  \frac{ |H_S(\theta_0+\nu,\theta_0,g_0) - H_D(\theta_0+\nu,\theta_0,g_0)|} { \| \nu \|_1} \leq \kappa_{n,\delta}
\end{align*}

Then, $(\gamma,0,0)$-GRC of $L_D(\cdot, g_0)$ implies
    $(\gamma, \kappa_{n,\delta}, 0)$-GRC of $L_S(\cdot,g_0)$ on $\mathcal{B}$ w.p. $1-\delta$.
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem:pop-to-emp-non-conv}]
With probability $1-\delta$:
\begin{align*}
    H_S(\theta_0+\nu,\theta_0,g_0) &\geq H_D(\theta_0+\nu,\theta_0,g_0)  - \sup_{\nu \in \mathcal{B}} \frac{|H_D(\theta_0+\nu,\theta_0,g_0) -  H_S(\theta_0+\nu,\theta_0,g_0) |}{  \| \nu\|_1}\| \nu\|_1 \\
    &\geq \gamma \| \nu \|_2^2 - \kappa_{n,\delta} \|\nu\|_1
\end{align*}
\end{proof}

\begin{lemma}[From Population to Empirical GRC with Twice Differentiability]\label{lem:pop-to-emp-non-conv-twice}
Suppose that $L_S(\theta,g_0)$ is twice differentiable and its empirical Hessian concentrates uniformly over $\theta\in \{\theta_0 +r \nu: \nu \in \mathcal{B}, r\in [0,1]\}$ to its population counterpart at rate $\tau_{n,\delta}/2$, i.e., w.p. $1-\delta$:
    \begin{equation}
    \sup_{\theta \in \{\theta_0 +r \nu: \nu \in \mathcal{B}, r\in [0,1]\}}  \|\nabla_{\theta \theta }L_S(\theta, g_0) - \nabla_{\theta \theta}L_D(\theta, g_0)\|_{\infty} \leq \tau_{n,\delta},
\end{equation}
Then, $(\gamma,0,0)$-GRC of $L_D(\cdot, g_0)$ implies
    $(\gamma, 0, \tau_{n,\delta})$-GRC of $L_S(\cdot,g_0)$ on ${\cal B}$ w.p. $1-\delta$.
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem:pop-to-emp-non-conv-twice}]
On the event $\mathcal{E}_2:=\{ \sup_{\theta \in \Theta}  \|\nabla_{\theta \theta}L_S(\theta, g_0) - \nabla_{\theta \theta}L_D(\theta, g_0)\|_{\infty} < \tau_{n,\delta} \}$, which occurs with probability $1-\delta$:
\begin{align*}
   H_S(\theta_0+\nu,\theta_0,g_0) =~& \int_{0}^{1} \frac{\partial}{\partial r} \nu^T \nabla_{\theta}L_S(\theta_0 + r\nu) dr \\
    =~& \int_{0}^{1} \nu^T \nabla_{\theta\theta}L_S(\theta_0 + r\nu) \nu dr \\
    \geq~& \int_{0}^{1} \nu^T \nabla_{\theta\theta}L_D(\theta_0 + r\nu) \nu dr - \tau_{n,\delta} \|\nu\|_1^2 \\
    =~& H_D(\theta_0+\nu,\theta_0) - \tau_{n,\delta} \|\nu\|_1^2 \\
    \geq~& \gamma \|\nu\|_2^2 - \tau_{n,\delta} \|\nu \|_1^2
\end{align*}
\end{proof}
\begin{lemma}[Influence on Oracle Gradient ]\label{lem:influence}
Assumptions \ref{ass:nuisance}, \ref{ass:orthohessian}, \ref{ass:lossconv}, and \ref{ass:nonortholoss} imply that w.p. $1-2\delta$:
\label{lem:oraclegrad}
\begin{align}
    \label{eq:grad}
     \|\nabla_\theta L_S(\theta_0, \widehat{g})\|_{\infty} &\leq  \epsilon_{n,\delta} + B_0 g_{n,\delta} + B g_{n,\delta}^2
\end{align}
\end{lemma}
\begin{proof}[Proof of Lemma \ref{lem:influence}]
We consider the event that the probabilistic statements in Assumptions \ref{ass:nuisance} and \ref{ass:lossconv} occur. The latter happens with probability at least $1-2\delta$, by the union bound. We further condition on the value of the first stage estimate to be $\widehat{g}\in {\mathcal G}_n$.

By the first-order optimality condition, $\nabla_{\theta} L_D(\theta_0, g_0)=0$ and by the triangle inequality:
    \begin{align}
        \|\nabla L_S(\theta_0, \widehat{g})\|_{\infty} &\leq  \|  \nabla_{\theta} [L_D(\theta_0, \widehat{g}) -L_D(\theta_0, g_0) ] \|_{\infty} + \|  \nabla_{\theta} [L_S(\theta_0, \widehat{g}) -L_D(\theta_0, \widehat{g})] \|_{\infty} \label{eqn:gradient-eqn-1}
    \end{align}
    Observe that because we estimated $\widehat{g}$ on a separate sample $S'$, the fact that we have conditioned on $G=\widehat{g}$ does not affect the distribution of the samples in $S$. Hence, if we let $G$ denote the random variable corresponding to the first stage estimate, then:
    \begin{equation*}
        \Pr\left(\|  \nabla_{\theta} [L_S(\theta_0, \widehat{g}) -L_D(\theta_0, \widehat{g})] \|_{\infty} \geq \epsilon_ {n,\delta} | G = \widehat{g}\right) = \Pr\left(\|  \nabla_{\theta} [L_S(\theta_0, \widehat{g}) -L_D(\theta_0, \widehat{g})] \|_{\infty}\geq \epsilon_{n,\delta}\right)
    \end{equation*}
    By Assumption \ref{ass:lossconv} the term on the right hand side is at most $\delta$. Hence, it suffices to bound the first term on the right hand side of Equation \eqref{eqn:gradient-eqn-1} by $B g_{n,\delta}^2$ w.p. $1-\delta$.

    Consider the vector valued function $f(r) = \nabla_{\theta} L_D(\theta_0, g_0 + r (\widehat{g}-g_0))$. By a first order Taylor expansion of $f^i(1)$ around $f^i(0)$ for each $i\in [d]$ and the definition of the pathwise derivative, we have:
    \begin{equation}
            \nabla_{\theta_i} L_D(\theta_0, \widehat{g}) = \nabla_{\theta_i} L_D(\theta_0, g_0) + \underbrace{D_0[\widehat{g}-g_0, \nabla_{\theta_i} L_D(\theta_0, g_0)]}_{\Gamma} + \underbrace{D_{\bar{r}_i}^2[\widehat{g}-g_0, \nabla_{\theta_i} L_D(\theta_0, g_0)]}_\Delta
    \end{equation}
    for some $\bar{r}_i\in [0,1]$. By Assumption \ref{ass:nonortholoss}, we have that
    \begin{equation*}
        \|  \nabla_{\theta} [L_D(\theta_0, \widehat{g}) - L_D(\theta_0, g_0) ] \|_{\infty}  \leq B_0 g_{n,\delta}+ B g_{n,\delta}^2
    \end{equation*}
    which completes the proof of the Lemma. Furthermore, if Assumption \ref{ass:ortholoss} holds, we have that $\Gamma=0=B_0$ and by  Assumption \ref{ass:orthohessian}, we have that $|\Delta| \leq B\|\widehat{g}-g_0\|^2$.
\end{proof}

\begin{lemma} [No First Stage Influence on Restricted Strong Convexity]
\label{lem:fsrsc}
Let Assumptions \ref{ass:nuisance}, \ref{ass:grc}, \ref{ass:liphessian-non-conv} with $\mathcal{B} = {\mathcal C}(T;3)$ hold deterministically and $k(\tau_{n,\delta} + L\,g_{n})=o(1)$. Then, the empirical plug-in loss $L_S(\cdot, \widehat{g})$ satisfies the $(\gamma/2,\kappa_{n,\delta}, 0)$-GRC condition with ${\cal B}={\cal C}(T;3)$, for $n$ sufficiently large, such that $16 k(\tau_{n,\delta} + L\,(g_{n}+\xi_{n,\delta}))\leq \frac{\gamma}{2}$.
\end{lemma}
\begin{proof}
 Assumption \ref{ass:liphessian-non-conv} implies:
$$\sup_{\nu   \in {\mathcal C}(T;3)}\frac{| H_S(\theta_0+\nu, \theta_0, \widehat{g}) -  H_S(\theta_0+\nu, \theta_0, g_0)  |}{\| \nu \|_1^2} \leq L g_{n,\delta}.$$
Subsequently, invoking the Cauchy-Schwarz inequality and the fact that $\nu = \theta - \theta_0 \in C(T,3)$:
\begin{align*}
 \max_{\nu \in {\mathcal C}(T;3)}\frac{|H_S(\theta_0+\nu, \theta_0, \widehat{g}) - H_S(\theta_0+\nu, \theta_0, g_0) |}{\|\nu\|^2_2} &\leq
 \max_{\nu \in {\mathcal C}(T;3)}\frac{\|\nu \|_1^2 L g_{n,\delta}}{\|\nu\|^2_2}
 \leq \frac{((1+3) \| \nu_T \|_1)^2 L (g_{n,\delta} + \xi_{n,\delta}) }{\|\nu\|^2_2} \\
 & \leq 16 \frac{ \| \nu_T \|_1^2 L (g_{n,\delta} + \xi_{n,\delta})}{\|\nu_T\|^2_2}\\
 & \leq 16 k  L (g_{n,\delta}+\xi_{n,\delta}) \leq 16k  L (g_{n,\delta} + \xi_{n,\delta})
\end{align*}
By Assumption \ref{ass:grc}, the empirical oracle loss $L_S(\cdot, g_0)$ satisfies the $(\gamma,\kappa_{n,\delta}, \tau_{n,\delta})$-GRC condition: $\forall \nu\in C(T; 3)$
\begin{align*}
    H_S(\theta_0+\nu, \theta_0, \widehat{g}) &\geq H_S(\theta_0+\nu, \theta_0,g_0)- 16k   L (g_{n,\delta}+\xi_{n,\delta})\|\nu\|^2_2   \\
    &\geq \gamma\|\nu\|^2_2-\kappa_{n,\delta} \| \nu \|_1 - \tau_{n,\delta} \|\nu\|_1^2 - 16k   L (g_{n,\delta}+\xi_{n,\delta})\|\nu\|_2^2\\
    &\geq \gamma \|\nu\|^2_2 - \kappa_{n,\delta} \| \nu \|_1 - 16k(\tau_{n,\delta} + L\,(g_{n,\delta}+\xi_{n,\delta}))\|\nu\|_2^2 \geq \frac{\gamma}{2} \|\nu\|^2_2 - \kappa_{n,\delta} \| \nu \|_1
\end{align*}
\end{proof}

\begin{lemma}\label{lem:subspace} If $\frac{\lambda}{2} \geq \|\nabla_\theta L_S(\theta_0, \widehat{g})\|_{\infty}$ and Assumption \ref{ass:convloss} holds, then $\nu \in {\cal C}(T; 3)$, where $\nu=\widehat{\theta}-\theta_0$.
\end{lemma}
\begin{proof}

Since $\widehat{\theta}$ minimizes the penalized loss, we have:
\begin{equation}\label{eqn:minimizer}
L_S(\widehat{\theta},\widehat{g}) - L_S(\theta_0,\widehat{g}) \leq \lambda \left(\|\theta_0\|_1 - \|\widehat{\theta}\|_1\right) \leq \lambda \left(\|\nu_T\|_1 - \|\nu_{T^c}\|_1\right),
\end{equation}
where the second inequality follows from the observation that $\|\widehat{\theta}\|_1 = \|\theta_0 + \nu_T\|_1 + \|\nu_{T^c}\|_1 \geq \|\theta_0\|_1 - \|\nu_T\|_1 + \|\nu_{T^c}\|_1$. By convexity of $L_S(\theta, \widehat{g})$, Cauchy-Schwarz inequality and the lower bound assumption on $\lambda$:
\begin{equation}\label{eqn:convexity}
L_S(\widehat{\theta}, \widehat{g}) - L_S(\theta_0, \widehat{g}) \geq \nabla_\theta L_S(\theta_0, \widehat{g}) \cdot (\widehat{\theta}-\theta_0) \geq -\|\nabla_\theta L_S(\theta_0, \widehat{g})\|_\infty \|\nu\|_1 \geq - \frac{\lambda}{2} \|\nu\|_1
\end{equation}
Combining Equations \eqref{eqn:minimizer} and \ref{eqn:convexity}:
\begin{equation*}
\lambda \left(\|\nu_T\|_1 - \|\nu_{T^c}\|_1\right) \geq L_S(\widehat{\theta},\widehat{g}) - L_S(\theta_0,\widehat{g}) \geq -\frac{\lambda}{2} \|\nu\|_1
\end{equation*}
Dividing by $\lambda$ and re-arranging we get $3\|\nu_T\|_1 \geq \|\nu_{T^c}\|_1$.
\end{proof}

\begin{lemma}[Oracle Inequality for $\theta$]\label{thm:gen-conv}
If Assumptions \ref{ass:nuisance},  \ref{ass:orthohessian}, \ref{ass:lossconv}, \ref{ass:grc}, \ref{ass:liphessian-non-conv}, \ref{ass:convloss}, \ref{ass:nonortholoss} with $\mathcal{B} = {\mathcal C}(T;3)$ hold deterministically and $\frac{\lambda}{2} \geq \epsilon_{n,\delta} + B\,g_{n,\delta}^2 + \kappa_{n,\delta}$ then the second stage estimate $\widehat{\theta}$, for $n$ sufficiently large, such that $16 k(\tau_{n,\delta} + L\,(g_{n}+\xi_{n,\delta}))\leq \frac{\gamma}{2}$,
satisfies:
\begin{align}
\|\widehat{\theta} - \theta_0\|_2 \leq& \frac{3\sqrt{k}}{\gamma} \lambda  & \|\widehat{\theta} - \theta_0\|_1 \leq& \frac{12 k}{\gamma} \lambda
\end{align}
\end{lemma}
\begin{proof}
 Let $\nu = \widehat{\theta} - \theta_0$. Similar to Equation \eqref{eqn:minimizer}, since $\widehat{\theta}$ minimizes the penalized objective:
\begin{equation}\label{eqn:minimizer-2}
L_S(\widehat{\theta},\widehat{g}) - L_S(\theta_0,\widehat{g}) \leq \lambda \left(\|\theta_0\|_1 - \|\widehat{\theta}\|_1\right) \leq \lambda \left(\|\nu_T\|_1 - \|\nu_{T^c}\|_1\right),
\end{equation}
By Lemma \ref{lem:influence}, \ref{lem:fsrsc} and \ref{lem:subspace} we have:
\begin{align*}
 \lambda \left(\| \theta_0 \|_1 - \|\widehat{\theta}\|_1 \right)   \geq~& \nabla_\theta L_S(\widehat{\theta}, \widehat{g}) \cdot (\widehat{\theta}-\theta_0) \tag{Optimality of $\widehat{\theta}$} \\
 \geq~&  \nabla_\theta L_S(\theta_0, \widehat{g}) \cdot (\widehat{\theta}-\theta_0) + H_S(\widehat{\theta},\theta_0,\widehat{g}) \tag{Symmetric Bregman distance}\\
\geq~& \nabla_\theta L_S(\theta_0, \widehat{g}) \cdot (\widehat{\theta}-\theta_0)  + \frac{\gamma}{2} \|\nu\|_2^2 - \kappa_{n,\delta} \| \nu \|_1 \tag{Lemmas \ref{lem:fsrsc}, \ref{lem:subspace}}\\
\geq~& -\|\nabla_{\theta} L_S(\theta_0,\widehat{g})\|_{\infty} \cdot \|\nu\|_1  + \frac{\gamma}{2} \|\nu\|_2^2 - \kappa_{n,\delta} \| \nu \|_1 \tag{Cauchy-Schwarz}\\
\geq~& - (\epsilon_{n,\delta} + B_0 g_{n,\delta}+ B\,g_{n,\delta}^2) \cdot \|\nu\|_1  + \frac{\gamma}{2} \|\nu\|_2^2 - \kappa_{n,\delta} \| \nu \|_1 \tag{Lemma \ref{lem:influence}}\\
\geq~& -\frac{\lambda}{2} \cdot \|\nu\|_1  + \frac{\gamma}{2} \|\nu\|_2^2 \tag{Assumption on $\lambda$}
\end{align*}
Furthermore, when Assumption \ref{ass:ortholoss} holds, $B_0=0$.
Combining Equation \eqref{eqn:minimizer-2} with the latter inequality we get:
\begin{align*}
\frac{\gamma}{2} \|\nu\|_2^2 \leq \frac{3\lambda}{2} \|\nu_T\|_1 - \frac{\lambda}{2} \|\nu_{T^c}\|_1 \leq \frac{3\lambda}{2} \|\nu_T\|_1 \leq \frac{3\lambda \sqrt{k}}{2} \|\nu\|_2
\end{align*}
Dividing over by $\|\nu\|_2$, yields the theorem. The $\ell_1$ rate is derived by the fact that in the cone ${\cal C}(T;3)$: $\|\nu\|_1\leq 4 \sqrt{k} \|\nu\|_2$.
\end{proof}

\subsection{Proof of Main Theorem for Non-Convex Losses}

First, let us prove that orthogonality of the loss (Assumptions \ref{ass:ortholoss} and \ref{ass:orthohessian}) implies that the noise of the problem,
summarized by $\| \nabla_{\theta} L_S(\theta_0, \widehat{g}) \|_{\infty}$, decays at least as fast as $O_p\left( g_{n,\delta}^2+ \epsilon_{n,\delta}\right)$.

\begin{lemma}[Second Order Influence on Oracle Gradient ]\label{lem:influence}
Assumptions \ref{ass:nuisance}, \ref{ass:ortholoss}, \ref{ass:orthohessian} and \ref{ass:lossconv} imply that w.p. $1-2\delta$:
\label{lem:oraclegrad}
\begin{align}
    \label{eq:grad}
     \|\nabla_\theta L_S(\theta_0, \widehat{g})\|_{\infty} &\leq  \epsilon_{n,\delta} + B g_{n,\delta}^2
\end{align}
\end{lemma}
\begin{proof}[Proof of Lemma \ref{lem:influence}]
We consider the event that the probabilistic statements in Assumptions \ref{ass:nuisance} and \ref{ass:lossconv} occur. The latter happens with probability at least $1-2\delta$, by the union bound. We further condition on the value of the first stage estimate to be $\widehat{g}\in {\mathcal G}_{n,\delta}$.

By the first-order optimality condition, $\nabla_{\theta} L_D(\theta_0, g_0)=0$ and by the triangle inequality:
    \begin{align}
        \|\nabla L_S(\theta_0, \widehat{g})\|_{\infty} &\leq  \|  \nabla_{\theta} [L_D(\theta_0, \widehat{g}) -L_D(\theta_0, g_0) ] \|_{\infty} + \|  \nabla_{\theta} [L_S(\theta_0, \widehat{g}) -L_D(\theta_0, \widehat{g})] \|_{\infty} \label{eqn:gradient-eqn-1}
    \end{align}
    Observe that because we estimated $\widehat{g}$ on a separate sample $S'$, the fact that we have conditioned on $G=\widehat{g}$ does not affect the distribution of the samples in $S$. Hence, if we let $G$ denote the random variable corresponding to the first stage estimate, then:
    \begin{equation*}
        \Pr\left(\|  \nabla_{\theta} [L_S(\theta_0, \widehat{g}) -L_D(\theta_0, \widehat{g})] \|_{\infty} \geq \epsilon_ {n,\delta} | G = \widehat{g}\right) = \Pr\left(\|  \nabla_{\theta} [L_S(\theta_0, \widehat{g}) -L_D(\theta_0, \widehat{g})] \|_{\infty}\geq \epsilon_{n,\delta}\right)
    \end{equation*}
    By Assumption \ref{ass:lossconv} the term on the right hand side is at most $\delta$. Hence, it suffices to bound the first term on the right hand side of Equation \eqref{eqn:gradient-eqn-1} by $B g_{n,\delta}^2$ w.p. $1-\delta$.

    Consider the vector valued function $f(r) = \nabla_{\theta} L_D(\theta_0, g_0 + r (\widehat{g}-g_0))$. By a first order Taylor expansion of $f^i(1)$ around $f^i(0)$ for each $i\in [d]$ and the definition of the pathwise derivative, we have:
    \begin{equation}
            \nabla_{\theta_i} L_D(\theta_0, \widehat{g}) = \nabla_{\theta_i} L_D(\theta_0, g_0) + \underbrace{D_0[\widehat{g}-g_0, \nabla_{\theta_i} L_D(\theta_0, g_0)]}_{\Gamma} + \underbrace{D_{\bar{r}_i}^2[\widehat{g}-g_0, \nabla_{\theta_i} L_D(\theta_0, g_0)]}_\Delta
    \end{equation}
    for some $\bar{r}_i\in [0,1]$. By Assumption \ref{ass:ortholoss}, we have that $\Gamma=0$ and by Regularity Assumption \ref{ass:orthohessian}, we have that $|\Delta| \leq B\|\widehat{g}-g_0\|^2$. By Assumption \ref{ass:nuisance}, we also have $\|\widehat{g}-g_0\|\leq g_{n,\delta}$. Combining all the above we have:
    \begin{equation*}
        \|  \nabla_{\theta} [L_D(\theta_0, \widehat{g}) - L_D(\theta_0, g_0) ] \|_{\infty}  \leq B g_{n,\delta}^2
    \end{equation*}
    which completes the proof of the Lemma.
\end{proof}

\begin{assumption}[Preliminary Estimator]\label{ass:prelim-estimate} We assume that there exists a preliminary estimator $\tilde{\theta}$ such that with probability $1-\delta$:
$$\|\tilde{\theta}-\theta_0\|_1 \leq R(n,\delta)$$
\end{assumption}

\begin{theorem}[Convergence Rate of the Plug-in Regularized Estimator]\label{thm:main-non-convex:app} Let Assumptions
\ref{ass:nuisance}, \ref{ass:ortholoss}, \ref{ass:orthohessian},
\ref{ass:lossconv}, \ref{ass:prelim-estimate}  hold, and $\tilde{\theta}$ be  a preliminary estimator. Let Assumptions
\ref{ass:grc}, \ref{ass:liphessian-non-conv} hold on a set $\mathcal{B} = \{ \theta: \|\theta - \tilde{\theta} \|_1 \leq R(n, \delta)\}$. Then, the Plug-in Regularized Estimator of Algorithm \ref{def:lasso:intro} with regularization parameter $\lambda$ satisfying $\frac{\lambda}{2} \geq  \epsilon_{n,\delta} + B g_{n,\delta}^2 + \kappa_{n,\delta} + (\tau_{n,\delta} + L (g_{n,\delta} + \xi_{n,\delta})) R(n, \delta)$
and search set $\mathcal{T}=\mathcal{B}$ satisfies w.p. $1-5\delta$:
\begin{align}
    \| \widehat{\theta} - \theta_0 \|_2 \leq~& \frac{3\sqrt{k}}{2\gamma} \lambda &
     \| \widehat{\theta} - \theta_0 \|_1 \leq~& \frac{6k}{\gamma} \lambda \label{eq:oracle:1}
\end{align}
\end{theorem}

\begin{proof} [Proof of Theorem \ref{thm:main-non-convex:app}]
Consider the event $\mathcal{E}_n$ that all probabilistic statements in Assumptions \ref{ass:nuisance}, \ref{ass:lossconv}, \ref{ass:grc}, \ref{ass:liphessian-non-conv} and \ref{ass:prelim-estimate} occur for some confidence parameter $\delta$. If each individual occurs with probability $1-\delta$, then by a union bound their intersection occurs w.p. $1-5\delta$. On this event $\mathcal{E}_n$ the following proof holds. For simplicity of notation we drop the confidence parameter $\delta$ from all subscripts as it is fixed.

Since $\widehat{\theta}\in \mathcal{T}$ is a local minimum of the empirical plug-in loss function $L_S(\cdot, \widehat{g})$, we can write from the first-order condition that for any $\theta\in \mathcal{T}$:
\begin{equation}
\ldot{\nabla_{\theta} L_S(\widehat{\theta}, \widehat{g}) + \lambda\, \sign{\widehat{\theta}}}{\widehat{\theta} - \theta} \leq 0.
\end{equation}
By Assumption \ref{ass:prelim-estimate}, we have that with probability approach $1$, that $\theta_0\in \mathcal{T}$. Hence, we can apply the latter inequality for $\theta=\theta_0$. Letting $\nu=\widehat{\theta}-\theta_0$ we can write:
\begin{equation}
\ldot{\nabla_{\theta} L_S(\widehat{\theta}, \widehat{g}) + \lambda \,\sign{\widehat{\theta}}}{\nu} \leq 0.
\end{equation}
By Cauchy-Schwarz and the definition of norms:
$$\ldot{\sign{\widehat{\theta}}}{\theta_0 - \widehat{\theta}}\leq \|\sign{\widehat{\theta}}\|_{\infty} \|\theta_0\|_1 - \ldot{\sign{\widehat{\theta}}}{\widehat{\theta}} =  \|\theta_0\|_1 - \|\widehat{\theta}\|_1.$$ Combining the two inequalities we get:
\begin{equation}\label{eqn:nonconv-proof-1}
\ldot{\nabla_{\theta} L_S(\widehat{\theta}, \widehat{g})}{\nu}\leq \lambda \left( \|\theta_0\|_1 - \|\widehat{\theta}\|_1\right).
\end{equation}
By the $(\gamma, \kappa_{n,\delta}, \tau_{n,\delta})$-GRC condition on the empirical oracle loss
\begin{equation}
    H_S(\widehat{\theta}, \theta_0, g_0)  \geq \gamma \|\nu\|_2^2 - \kappa_{n,\delta} \|\nu\|_1 - \tau_{n,\delta} \|\nu\|_1^2
\end{equation}
Combining the inequality above with Assumption \ref{ass:liphessian-non-conv}, we derive a GRC condition for the empirical plugin loss:
\begin{align}
    H_S(\widehat{\theta}, \theta_0, \widehat{g}) \geq~& H_S(\widehat{\theta}, \theta_0, g_0) - L (g_{n,\delta} + \xi_{n}) \|\nu\|_1^2
    \geq~ \gamma \|\nu\|_2^2 - \kappa_{n,\delta} \|\nu\|_1 - \underbrace{(\tau_{n,\delta} + L (g_{n,\delta} + \xi_{n,\delta}))}_{\zeta_n} \cdot \|\nu\|_1^2 \label{eqn:nonconv-proof-2}
\end{align}
Combining Equation \eqref{eqn:nonconv-proof-1} and \eqref{eqn:nonconv-proof-2}:
\begin{align}
    \ldot{\nabla_{\theta} L_S(\theta_0, \widehat{g})}{\nu} =~& \ldot{\nabla_{\theta} L_S(\widehat{\theta}, \widehat{g})}{\nu} -  H_S(\widehat{\theta}, \theta_0, \widehat{g}) \nonumber\\
    \leq~& \lambda \left( \|\theta_0\|_1 - \|\widehat{\theta}\|_1\right) - \gamma \|\nu\|_2^2 + \kappa_{n,\delta} \|\nu\|_1 + \zeta_n \|\nu\|_1^2\label{eqn:nonconvproof_star}
\end{align}
By Cauchy-Schwarz, we also have:
\begin{align}\label{eqn:nonconvproof_star_star}
    \ldot{\nabla_{\theta} L_S(\theta_0, \widehat{g})}{\nu} \geq - \|\nabla_{\theta} L_S(\theta_0, \widehat{g})\|_{\infty} \|\nu\|_1
\end{align}
Combining Equations \eqref{eqn:nonconvproof_star} and \eqref{eqn:nonconvproof_star_star}:
\begin{align*}
    \gamma \|\nu\|_2^2 \leq \lambda \left( \|\theta_0\|_1 - \|\widehat{\theta}\|_1\right) + \kappa_{n,\delta} \|\nu\|_1 + \zeta_n \|\nu\|_1^2 + \|\nabla_{\theta} L_S(\theta_0, \widehat{g})\|_{\infty} \|\nu\|
\end{align*}
By Lemma \ref{lem:influence}, $\frac{\lambda}{2} \geq \zeta_n \| \nu \|_1 + \kappa_{n,\delta} + \epsilon_{n,\delta} + B g_{n}^2$ (which is assumed by the Theorem) implies that $\frac{\lambda}{2} \geq \zeta_n \| \nu \|_1 + \kappa_{n,\delta} + \|\nabla_{\theta} L_S(\theta_0, \widehat{g})\|_{\infty}$.
Hence, we have:
\begin{equation}
    \gamma \|\nu\|_2^2 \leq \lambda \left( \|\theta_0\|_1 - \|\widehat{\theta}\|_1 \right) + \frac{\lambda}{2}\|\nu\|_1 \label{eqn:nonconvproof_delta}
\end{equation}
By $\nu_T$ we denote $p$-dimensional vector
such that $\nu_{i,T}=\nu_i$ on set of indices $i \in T \subset \{1,\ldots,p\}$ and $\nu_{i,T}=0$ if $i \not\in T$. Also, let $T^c$ be the complement of $T$ Observe that:
\begin{equation}
    \|\theta_0\|_1 - \|\widehat{\theta}\|_1\leq \|\nu_T\|_1 - \|\nu_{T^c}\|_1 \label{eqn:nonconvproof_delta_delta}
\end{equation}
Combining Equations \eqref{eqn:nonconvproof_delta} and \eqref{eqn:nonconvproof_delta_delta}, we get:
\begin{equation}\label{eqn:non-convex-cone}
    \gamma \|\nu\|_2^2 \leq \frac{3\lambda}{2} \|\nu_T\|_1 - \frac{\lambda}{2} \|\nu_{T^c}\|_1 \leq \frac{3\lambda}{2} \|\nu_T\|_1  \leq \frac{3\lambda \sqrt{k}}{2} \|\nu_T\|_2 \leq  \frac{3\lambda \sqrt{k}}{2} \|\nu\|_2
\end{equation}
Dividing both sides by $\|\nu\|_2$ yields the rate:
\begin{equation}
    \|\nu\|_2 \leq \frac{3 \sqrt{k}}{2\gamma} \cdot \lambda
\end{equation}

For the $\ell_1$ convergence rate, observe that from Equation \eqref{eqn:non-convex-cone}, we can also derive that:
\begin{equation}
    0 \leq \gamma \|\nu\|_2^2 \leq \frac{3\lambda}{2} \|\nu_T\|_1 - \frac{\lambda}{2} \|\nu_{T^c}\|_1
\end{equation}
Thus we get that: $\|\nu_{T^c}\|_1 \leq 3 \|\nu_T\|_1$, which implies the $\ell_1$ convergence theorem, since:
\begin{equation*}
    \|\nu\|_1 \leq 4\|\nu_T\|_1 \leq 4\sqrt{k}\|\nu_T\|_2\leq 4\sqrt{k}\|\nu\|_2
\end{equation*}
\end{proof}

\begin{corollary}[Convergence Rate of Plug-in Regularized Estimator with Preliminary Step] Let $R=\max_{\theta \in \Theta} \|\theta\|_1$ and suppose that Assumptions
\ref{ass:nuisance}, \ref{ass:ortholoss}, \ref{ass:orthohessian},
\ref{ass:lossconv}, \ref{ass:grc}, \ref{ass:liphessian-non-conv} hold on set $\mathcal{B} = \Theta$ with $k(\tau_{n,\delta} + L (g_{n,\delta}+\xi_{n,\delta}))=o(1)$. Then the estimator returned by Algorithm~\ref{def:lasso:prelim} with the orthogonal loss $L_S$ as preliminary and final loss, search radii $R_0=R$, and $R_1=R_1(n, 4\delta)$ defined in Equation \eqref{eqn:second-radius} and regularization weights:
\begin{align}
\lambda_{\text{pre}} =~& 2\left(\epsilon_{n,\delta} + B g_{n,\delta}^2 + \kappa_{n,\delta} + (\tau_{n,\delta} + L (g_{n,\delta} + \xi_{n,\delta})) R_0\right)\\
\lambda_{\text{fin}} =~& 2\left(\epsilon_{n,\delta} + B g_{n,\delta}^2 + \kappa_{n,\delta} + (\tau_{n,\delta} + L (g_{n,\delta} + \xi_{n,\delta})) R_1(n, 4\delta)\right)
\end{align}
satisfies w.p. $1-8\delta$:
\begin{align}
\label{eq:resultnonconvex}
    \|\widehat{\theta}-\theta_0\|_2 \leq~& \frac{\sqrt{k}}{\gamma} O\left(\max\left\{\epsilon_{n,\delta}, \kappa_{n, \delta}, Bg_{n,\delta}^2, \tau_{n,\delta}^2  \frac{k\,R_0}{\gamma}, (g_{n,\delta}^2+ \xi_{n,\delta}^2) \frac{L^2\,k\,R_0}{\gamma}\right\}\right)

\end{align}
If $k\,R_0\,(g_{n,\delta}^2 + \xi_{n,\delta}^2) = o(\max\{\epsilon_{n,\delta}, \kappa_{n,\delta}\})$, then the estimation error of the nuisance component can asymptotically be ignored.
\label{cor:result-non-convex}
\end{corollary}

\begin{proof}[Proof of Corollary \ref{cor:result-non-convex}]

We apply Theorem \ref{thm:main-non-convex:app} with the preliminary estimator $\tilde{\theta}=0$ and $R(n,\delta)=R_0$, for some upper bound $R_0$ on $\|\theta_0\|_1$.  Then the Theorem states that the resulting estimator $\tilde{\theta}$ achieves a rate in terms of the $\ell_1$ norm:
 \begin{equation}\label{eqn:second-radius}
     R_1(n, 4\delta) = \frac{8k}{\gamma} \left(\epsilon_{n,\delta} + B g_{n,\delta}^2 + \kappa_{n,\delta} + (\tau_{n,\delta} + L (g_{n,\delta} + \xi_{n,\delta})) R_0\right)
 \end{equation}
Subsequently, we can use $\tilde{\theta}$ as our preliminary estimator and invoke the theorem with the latter rate $R(n, \delta)=R_1(n,\delta)$, which will yield a new estimator $\widehat{\theta}$ that achieves w.p. $1-8\delta$:
 \begin{align*}
     \|\widehat{\theta}-\theta_0\|_2 \leq~& \frac{3\sqrt{k}}{\gamma} \left(\epsilon_{n,\delta} + B g_{n,\delta}^2 + \kappa_{n,\delta} + (\tau_{n,\delta} + L (g_{n,\delta} + \xi_{n,\delta})) R_1(n, 4\delta)\right)\\
     =~& \frac{\sqrt{k}}{\gamma} O\left(\max\left\{\epsilon_{n,\delta}, \kappa_{n, \delta}, Bg_{n,\delta}^2, \tau_{n,\delta}^2\frac{k R_0}{\gamma}, (g_{n,\delta}^2 + \xi_{n,\delta}^2) \frac{L^2\,k\,R_0}{\gamma}\right\}\right)
 \end{align*} Thus we have recovered a rate that has only the second order dependence on the first stage error.
\end{proof}

\section{Proofs from Section \ref{sec:moment}}
\label{sec:proofs_moment}

In the following Lemmas, we establish Assumptions
\ref{ass:orthohessian}, \ref{ass:lossconv}, \ref{ass:grc}, \ref{ass:liphessian-non-conv} from the Assumptions \ref{ass:smooth} and \ref{ass:identification}.

\begin{lemma}[Bounded Hessian of the Gradient of Population Loss w.r.t. Nuisance for $M$-estimator loss]
\label{lem:orthohessian}
Assumption \ref{ass:orthohessian} follows from Assumption \ref{ass:smooth} for $\|g\|_k,$ where $k \in \{2, \infty\}$.

\end{lemma}
\begin{proof}[Proof of Lemma \ref{lem:orthohessian} ]

Let $\bar{g}_r = r(g-g_0) + g$ and $B=4U^3$. Then, $\nabla_{\theta_i}\ell(w, \Lambda(z,g_0(z))' \theta_0, \bar{g}_r(z))=m(w, \Lambda(z,g_0(z))' \theta_0, \bar{g}_r(z))\Lambda_i(z,g_0(z))$ and $\| \nabla_{\gamma\gamma\theta_i}\ell(w, \Lambda(z,g_0(z))' \theta_0, \bar{g}_r(z))\| \leq 4U^3$.  By Cauchy-Schwarz inequality and Assumption \ref{ass:smooth}, the $i$-th coordinate of the second-order pathwise derivative is bounded as:
\begin{align*}
    \left(D_r^2[g-g_0, \nabla_{\theta} L_D(\theta_0, g_0)]\right)_i =~& \mathbb{E}[(g(z)-g_0(z))' \nabla_{\gamma\gamma\theta_i}\ell(w, \theta_0, \bar{g}_r(z))\,(g(z)-g_0(z))]\\
    \leq~& \mathbb{E}[\|\nabla_{\gamma\gamma\theta_i}\ell(w, \Lambda(z,g_0(z))' \theta_0, \bar{g}_r(z))\|_{\infty}\,\|g(z)-g_0(z)\|_1^2]\\
    \leq~& B\, \underbrace{\mathbb{E}[\|g(z)-g_0(z)\|_1^2}_{\|g-g_0\|_{2, 1}^2}]\\
    \leq~& B\, \sup_{z\in {\mathcal Z}} \|g(z)-g_0(z)\|_{1}^2\\
    \leq~& B\, \|g-g_0\|_{\infty, 1}^2
\end{align*}

\end{proof}

\begin{lemma}[Convergence Rate of Empirical Gradient of $M$-estimator loss]
\label{lem:lossconv}
Assumption \ref{ass:lossconv} follows from Assumption \ref{ass:smooth}.
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem:lossconv}]
As shown in Lemma \ref{lem:orthohessian}, $\|\nabla_{\theta} \ell(w,\Lambda(z,g_0(z))' \theta_0,g)\|_{\infty} \leq H$, we have that each coordinate of the empirical gradient is a sum of $n$ independent random variables with mean equal to the population gradient and bounded a.s. in absolute value by $U^2$. Hence, by McDiarmid's inequality, each term is within $\epsilon_{n,\delta}=U^2\sqrt{\frac{\log(2p/\delta)}{2n}}$ of each mean with probability at least $1-\frac{\delta}{p}$. By a union bound over the $p$ coordinates we get that all coordinates are within $\epsilon_{n,\delta}$ from their mean with probability at least $1-\delta$.
\end{proof}

\begin{lemma}[Generalized Restricted Strong Convexity
for $M$-estimator loss]
\label{lem:grc}
Suppose Assumption \ref{ass:smooth} and \ref{ass:identification} hold. Then, the empirical loss function $L_S(\theta,g_0)$ satisfies the $(\nu \gamma_\Sigma,\, 0, \tau_{n,\delta})$-GRC condition on the set $\mathcal{B}=\Theta$ with $\tau_{n,\delta}=4U^5k \sqrt{\frac{2 \log p}{n}}+U^3 \sqrt{\frac{4\log(2\,p/\delta)}{n}}$
w.p. $1-\delta$. (That is, Assumption \ref{ass:grc} holds on $\mathcal{B}=\Theta$)

\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem:grc}]
By Assumption \ref{ass:identification}, the population loss $L_D$ satisfies the $(\gamma_D, 0, 0)$-GRC condition.

Step 1. We first assume that the empirical oracle Hessian converges uniformly to its population counterpart in the sense described below. We prove this Assumption in Step 2.

W.p. $1-\delta$,
    \begin{align}
    \label{eq:uniform}
        \sup_{\theta \in\Theta} \|\mathbb{E}_S[\nabla_{\theta\theta}\ell(w, \Lambda(z,g(z))'\theta, g_0(w))] - \mathbb{E}[\nabla_{\theta\theta}\ell(w, \Lambda(z,g(z))'\theta, g_0(w))]\|_{\infty} = \widehat{\tau}_{n,\delta}
    \end{align}
    with $k \widehat{\tau}_{n,\delta}=o(1)$.

Applying Lemma \ref{lem:pop-to-emp-non-conv-twice} with $L_S(\theta,g_0)=\frac{1}{n} \sum_{i=1}^n \ell(w_i,\Lambda(z,g_0(z_i))'\theta,g_0(z_i)) $
obeys the $(\gamma, 0, \tau_{n,\delta})$-GRC property.

Step 2. We establish the uniform convergence of each entry of the Hessian. The result would then follow via a union bound over the $p^2$ entries of the Hessian. For $i, j\in \{1,\ldots, p\}$, the $(i,j)$ entry takes the form:
\begin{align*}
    \nabla_{\theta_i \theta_j} \ell(w, \theta, g_0(z)) = \nabla_t m(w, \Lambda(z, g_0(z))'\theta, g_0(z)) \Lambda_i(z, g_0(z)) \Lambda_j(z, g_0(z))
\end{align*}
By Assumption \ref{ass:smooth},  we have that $|\nabla_{t}  m(w, \Lambda(z, g_0(z))'\theta, g_0(z))|\leq U$ and $\|\Lambda(z, g_0(z))\|_{\infty}\leq U$, we have that the latter function depends on the parameter $\theta$ only through a $U^3$-Lipschitz function of a linear index of $\theta$. By invoking Lemma 26.9 of \cite{Shalev2014}, we know that the Rademacher complexity of any such class is upper bounded by $U^3$ times the Rademacher complexity of the function class ${\mathcal F}=\{\Lambda(\cdot, g_0(\cdot))'\theta: \theta\in \Theta\}$. Since $\|\theta\|_1\leq k U$ for any $\theta \in \Theta$ and $\|\Lambda(z, g_0(z))\|_{\infty}\leq U$, we can invoke
Lemma 26.11 of \cite{Shalev2014} to bound the Rademacher complexity of ${\mathcal F}$ by $U^2 k \sqrt{\frac{2\log(p)}{n}}$. Thus the overall Rademacher complexity of the function class defined by the entry of the Hessian is at most ${\mathcal R} = U^5  k \sqrt{\frac{2\log(p)}{n}}$. Subsequently, since these functions are also absolutely bounded by $U^3$, via standard results in statistical learning theory (see e.g. Lemma 26.2 and 26.5 of \cite{Shalev2014}, we have that with probability at least $1-\delta/p^2$:
\begin{align*}
    \sup_{\theta\in \Theta} |\mathbb{E}_S[\nabla_{\theta_i \theta_j} \ell(w, \theta, g_0(z))] - \mathbb{E}[\nabla_{\theta_i \theta_j} \ell(w, \theta, g_0(z))]| \leq 4 {\mathcal R} + U^3 \sqrt{\frac{4\log(2\,p/\delta)}{n}}
\end{align*}
Taking a union bound over the $p^2$ entries yields the condition for the stated $\widehat{\tau}_{n,\delta}$.
\end{proof}

\begin{lemma}[Lipshitz curvature of $M$-estimator]
\label{lem:liphessian-non-conv}

Assumption \ref{ass:smooth} implies that Assumption \ref{ass:liphessian-non-conv} holds on $\mathcal{B}=\Theta$.
\end{lemma}

\begin{proof}
Within this proof, we will abuse the notation and write $\ell(w, \theta, g)=\ell(w, \Lambda(z,g(z))'\theta, g)$. Note that $\nabla_{\gamma\theta_i\theta_j} \ell(w, \theta, \bar{g})=\nabla_{\gamma t} \left(m(w, \Lambda(z, g_0(z))'\theta, g_0(z)) \cdot \Lambda_i(z, g_0(z)) \cdot \Lambda_j(z, g_0(z)) \right)$. Since each function in $ \left(m(w, \Lambda(z, g_0(z))'\theta, g_0(z)) \cdot \Lambda_i(z, g_0(z)) \cdot \Lambda_j(z, g_0(z)) \right)$ has $U$-bounded derivative, its derivative is bounded by $L=3U^3$.

Case 1. Proof for $\|g-g'\|_{\infty}$ norm.

By Assumption \ref{ass:smooth}, we have:
\begin{align*}
   |\nabla_{\theta_i\theta_j} L_S(\theta, g) - \nabla_{\theta_i\theta_j} L_S(\theta, g')|=~& |\mathbb{E}_S[\nabla_{\theta_i\theta_j} \ell(w, \theta, g) - \nabla_{\theta_i\theta_j} \ell(w, \theta, g')]|\\
   \leq~& \mathbb{E}_S[|\nabla_{\theta_i\theta_j} \ell(w, \theta, g) - \nabla_{\theta_i\theta_j} \ell(w, \theta, g')|]\\
   \leq~& \sup_{w\in \mathcal W}|\nabla_{\theta_i\theta_j} \ell(w, \theta, g) - \nabla_{\theta_i\theta_j} \ell(w, \theta, g')|\\
   =~& \sup_{w\in\mathcal W} |\nabla_{\gamma\theta_i\theta_j} \ell(w, \theta, \bar{g})'(g(w)-g'(w))|\\
   \leq~& \sup_{w\in \mathcal W} H \|g(w)-g'(w)\|_1\\
   =~&  L\,\|g-g'\|_{\infty, 1}
\end{align*}

Case 2. Proof for $\|g-g'\|_{2}$ norm.
Now observe that since $\|g(z)-g'(z)\|_{\infty}\leq H$, we have that $\|g(z)-g'(z)\|_1\leq d\,H$. By McDiarmid's inequality we then have that for any fixed $g, g'\in {\mathcal G}_n$, with probability $1-\delta$:
\begin{align*}
    \left|\mathbb{E}_S[\|g(z)-g'(z)\|_1] - \mathbb{E}[\|g(z)-g'(z)\|_1]\right| \leq d\, H \, \sqrt{\frac{\log(2/\delta)}{2n}} := \xi_{n,\delta}
\end{align*}
Combining with the previous inequality we have:
\begin{align*}
   |\nabla_{\theta_i\theta_j} L_S(\theta, g) - \nabla_{\theta_i\theta_j} L_S(\theta, g')|
   \leq~&  L \left(\mathbb{E}[\|g(z)-g'(z)\|_1] + \xi_{n,\delta}\right)
\end{align*}
By Jensens' inequality:
\begin{equation*}
    \mathbb{E}[\|g(z)-g'(z)\|_1] \leq \sqrt{\mathbb{E}[\|g(z)-g'(z)\|_1^2]} = \|g-g'\|_{2,1}
\end{equation*}
Combining completes the proof.
\end{proof}

\subsection{Proof of Theorem \ref{cor:non-ortho-rate}}

We show that Theorem \ref{cor:non-ortho-rate} follows from Theorem \ref{thm:main-convex} and verify its assumptions.

Assumption \ref{ass:nuisance} is directly assumed in Theorem \ref{cor:non-ortho-rate}. Assumptions
\ref{ass:ortholoss} and \ref{ass:convloss} are restated in Assumption \ref{ass:orthogonal} and Assumption \ref{ass:convexity_moment}. Assumption
 \ref{ass:orthohessian}  is verified in Lemma \ref{lem:orthohessian} under Assumption \ref{ass:smooth} with $B=4U^3$. Assumption
\ref{ass:lossconv} is verified in Lemma \ref{lem:lossconv} under Assumption \ref{ass:smooth} with $\epsilon_{n,\delta}=U^2\sqrt{\frac{\log(2p/\delta)}{2n}}$.
Assumption \ref{ass:grc} is verified in Lemma \ref{lem:grc} under Assumptions \ref{ass:smooth} and \ref{ass:identification} with $\gamma_D=\nu \gamma$ and $\tau_{n,\delta}=4U^5k \sqrt{\frac{2 \log p}{n}}+U^3 \sqrt{\frac{4\log(2\,p/\delta)}{n}}$. Assumption \ref{ass:liphessian-non-conv} is verified  in Lemma \ref{lem:liphessian-non-conv} under Assumption \ref{ass:smooth} with $L=3U^3$.

\subsection{Proofs from Section \ref{sec:fsrate}}
Proof of Remark \ref{rm:lin}. The estimator $\widehat{\alpha}$  is a special case of Theorem \ref{thm:main-convex} with population loss $L_D(\alpha) = \mathbb{E} (v_i - p_{g}(z_i)'\alpha)^2$, sample loss $L_S( \alpha) =\mathbb{E}_n (v_i - p(z_i)'\alpha)^2$ and absent nuisance parameter. Here we verify all the conditions of Theorem \ref{thm:main-convex}. Assumptions \ref{ass:nuisance},  \ref{ass:ortholoss}, \ref{ass:orthohessian}, \ref{ass:liphessian-non-conv} are redundant because there is no nuisance parameter in the first stage. Assumption \ref{ass:convloss} holds since $L_S( \alpha)$ is convex in $\alpha$. By condition (c), the gradient $\nabla_{\alpha} L_S( \alpha) = 2\mathbb{E}_n(v_i - p(z_i)'\alpha_0) p(z_i)$ is a sample average of i.i.d. subGaussian random variables with variance proxy $\bar{\sigma}$. Therefore,  w.p. $1-\delta$, $\| \nabla_{\alpha} L_S( \alpha)\|_{\infty} \leq \bar{\sigma} \sqrt{\frac{\log (2p_d/\delta)}{n}}$ and Assumption \ref{ass:lossconv} holds with $\epsilon_{n,\delta}=\bar{\sigma} \sqrt{\frac{\log (2p_d/\delta)}{n}}$. By Assumption (a) of Remark \ref{rm:lin}, w.p. 1-$\delta$, $ \| \mathbb{E}_n p(z_i)p(z_i)^\top - \mathbb{E} p(z_i) p(z_i)^\top \|_{\infty} \leq \tau_{n,\delta}=\bar{B}^2 \sqrt{\frac{2\log p_d}{n}}$. By Lemma \ref{lem:pop-to-emp-non-conv} and condition (a), $L_S( \alpha)$ obeys $(\gamma,0,\tau_{n,\delta})$-condition with $\tau_{n,\delta}=\bar{B}^2 \sqrt{\frac{2\log p_d}{n}}$ w.p. $1-\delta$. Therefore, w.p. $1-4 \delta$, the linear Lasso estimator with $\lambda_{\alpha}/2 \geq (\bar{B}^2+\bar{\sigma}) \sqrt{\frac{2\log p_d}{n}}$ obeys
$\|\widehat{\alpha} - \alpha_0 \|_2 \leq \lambda \frac{3 \sqrt{k_{\alpha}}}{\kappa_{\text{min}}}$ and $\|\widehat{\alpha} - \alpha_0 \|_1 \leq \lambda \frac{12 k_{\alpha}}{\kappa_{\text{min}}}$.

(a) Case of $\ell_{\infty}$ norm. As shown above, $\widehat{g}(x) \in {\mathcal G}_{n,\delta}$ w.p. $1-4\delta$. Furthermore, $\forall g \in {\mathcal G}_{n,\delta}$, $\|g - g_0\|_{\infty} \leq \|p(x)\|_{\infty} \| \alpha - \alpha_0\|_1 \leq \bar{B} \lambda \frac{12 k_{\alpha}}{\kappa_{\text{min}}}=:g_{n,\delta}$.

(b) Case of $\ell_{2}$ norm. As shown above, $\widehat{g}(x) \in {\mathcal G}_{n,\delta}$ w.p. $1-4\delta$. Furthermore, $\forall g \in {\mathcal G}_{n,\delta}$, $\|g - g_0\|_{2} \leq \|p(x)\|_{P,2} \| \alpha - \alpha_0\|_2 \leq \bar{B} \lambda \frac{3 \sqrt{k_{\alpha}}}{\kappa_{\text{min}}}=:g_{n,\delta}$.

Proof of Remark \ref{rm:log}. The estimator $\widehat{\alpha}$  is a special case of Theorem \ref{thm:main-convex} with a logistic link function and absent nuisance parameter.  Assumptions \ref{ass:nuisance},  \ref{ass:ortholoss}, \ref{ass:orthohessian}, \ref{ass:liphessian-non-conv} are redundant because there is no nuisance parameter in the first stage. Assumption \ref{ass:convloss} holds since $L_S( \alpha)$ is convex in $\alpha$. The gradient $\nabla_{\alpha} L_S( \alpha) = 2\mathbb{E}_n(v_i - {\mathcal L}(p(z_i)'\alpha_0))  {\mathcal L}'(p(z_i)'\alpha_0) p(z_i)$ is a sample average of $\frac{\bar{B}}{4}$-bounded random variables. By Assumption (a) of Remark \ref{rm:lin}, w.p. 1-$\delta$, $ \| \mathbb{E}_n p(z_i)p(z_i)^\top - \mathbb{E} p(z_i) p(z_i)^\top \|_{\infty} \leq \bar{B}^2 \sqrt{\frac{2\log p_d}{n}}$. Therefore, $\|\nabla_{\alpha \alpha} L_S(\alpha) - \nabla_{\alpha \alpha} L_D(\alpha)\|_{\infty} = \| \mathbb{E}_n {\mathcal L}'(p(z_i)'\alpha_0) p(x_i) p(x_i)^\top -  \mathbb{E} {\mathcal L}'(p(z_i)'\alpha_0) p(x_i) p(x_i)^\top \|_{\infty} \leq  \frac{\bar{B}^2}{4}\sqrt{\frac{2\log p_d}{n}}:=\tau_{n,\delta} $ w.p. $1-\delta$. Therefore, w.p. $1-4 \delta$, the logistic Lasso algorithm with $\lambda_{\alpha}/2 \geq (\frac{\bar{B}^2+\bar{B}}{4})\sqrt{\frac{2\log p_d}{n}}$
$\|\widehat{\alpha} - \alpha_0 \|_2 \leq \lambda \frac{3 \sqrt{k_{\alpha}}}{\kappa_{\text{min}}}$ and $\|\widehat{\alpha} - \alpha_0 \|_1 \leq \lambda \frac{12 k_{\alpha}}{\kappa_{\text{min}}}$.

(a) Case of $\ell_{\infty}$ norm. As shown above, $\widehat{g}(x) \in {\mathcal G}_{n,\delta}$ w.p. $1-4\delta$. Furthermore, $\forall g \in {\mathcal G}_{n,\delta}$, $\|g - g_0\|_{\infty} \leq \sup_{t \in \mathbb{R}} {\mathcal L}'(t) \|p(x)\|_{\infty} \| \alpha - \alpha_0\|_1 \leq \frac{\bar{B}}{4} \lambda \frac{12 k_{\alpha}}{\kappa_{\text{min}}}=:g_{n,\delta}$.

(b) Case of $\ell_{2}$ norm. As shown above, $\widehat{g}(x) \in {\mathcal G}_{n,\delta}$ w.p. $1-4\delta$. Furthermore, $\forall g \in {\mathcal G}_{n,\delta}$, $\|g - g_0\|_{2} \leq  \sup_{t \in \mathbb{R}} {\mathcal L}'(t) \|p(x)\|_{P,2} \| \alpha - \alpha_0\|_2 \leq \bar{B} \lambda \frac{3 \sqrt{k_{\alpha}}}{\kappa_{\text{min}}}=:g_{n,\delta}$.

\subsection{Proof of Theorem \ref{thm:main-non-convex}}
Theorem \ref{thm:main-non-convex} follows from Corollary \ref{cor:result-non-convex}.  Assumptions \ref{ass:orthohessian}, \ref{ass:lossconv}, \ref{ass:grc}, and \ref{ass:liphessian-non-conv}  have been verified in
the proof of Theorem \ref{cor:non-ortho-rate} with the set $\mathcal{B} =\Theta$.

\begin{proof}[Proof of Theorem \ref{lem:general}]
Observe that $\mathbb{E} [\alpha(w,\tilde{g})|z] =0$ follows from $\mathbb{E}[R(w,g_0)|z]=0$ \eqref{eq:cond_exog} and $\alpha(w,\tilde{g})$ being the product of $R(w,g)$ and the functions of $z$.  Now we show that the moment function \eqref{eq:rho:phi} an orthogonal CMR. Let $\nabla_{\gamma} \phi,\nabla_{\gamma} m $ stand for the derivative w.r.t. the output of $g$.
\begin{align*}
 \nabla_{\gamma} \mathbb{E}[  \phi(w,\Lambda(z,g(z))'\theta, \tilde{g}) |z]] &= \nabla_{\gamma} \mathbb{E}[  m(w,\Lambda(z,g(z))'\theta, g) |z]] \\
    &- h_0(z)\mathbb{E}[ I(z)^{-1} \nabla_{\gamma} R(w,g)|z] \\
    &=^{iii} h_0(z) - h_0(z) =0,
\end{align*}
where $iii$ follows from the definition of $I(z)=\mathbb{E}[\nabla_{\gamma} R(w,g)|z]$. The derivative with respect to unknown parts in the correction term follows from \eqref{eq:cond_exog}. Indeed,
\begin{align*}
 \nabla_{h} \mathbb{E}[  \phi(w,\Lambda(z,g(z))'\theta, \tilde{g}) |z]] &= -\mathbb{E}[ I(z)^{-1} R(w,g_0(z))|z]=0
 \end{align*}
and
 \begin{align*}
 \nabla_{I} \mathbb{E}[  \phi(w,\Lambda(z,g(z))'\theta, \tilde{g}) |z]] &= \mathbb{E}[ I_0(z)^{-2} h_0(z) R(w,g_0(z))|z]=0.
 \end{align*}

\end{proof}

\begin{proof}[Proof of Lemma \ref{lem:ver:nuisance}]
By intermediate value theorem,
\begin{align*}
   &|R_h(w,\tilde{\theta},\widehat{g}) - R_h(w,\theta_0,g_0)| \leq | \nabla_{t} m(w,\Lambda(z,g(z))'\theta_0,\bar{g}) \Lambda(z,g(z))'(\tilde{\theta}-\theta_0)| \\
   &+ |\nabla_{\gamma}m(w,\Lambda(z,g(z))'\theta_0,g_0) (\widehat{g}(z)- g_0)| \\
   &\leq U^2 \| \tilde{\theta}-\theta_0\|_1 + U g_{n,\delta}.
\end{align*}
Invoking the Theorem \ref{thm:main-convex} under Assumption \ref{ass:nonortholoss} with aggressive regularization penalty $\lambda_{\text{fs}}$: $\lambda_{\text{fs}}/2 \geq U g_{n,\delta}+4U^3 g_{n,\delta}^3 +U^2\sqrt{\frac{\log (2p/\delta)}{2n}}$ gives w.p. $1-4\delta$, $\| \tilde{\theta}-\theta_0\|_1 \leq \frac{12k}{\gamma} \lambda  $
By Assumption \ref{ass:nuisance}, w.p. $1-\delta$, $\widehat{g} \in {\mathcal G}_{n,\delta}$. By union bound, w.p. $1-5\delta$, $R_h(w,\tilde{\theta},\widehat{g}) \in {\mathcal H}_{n,\delta}$.
\end{proof}

\begin{proof}[Proof of Lemma \ref{lem:ver:ass}]
(a) Observe that  the correction term $\alpha(w,\tilde{g})$ does not depend on the single index $\Lambda(z,g(z))'\theta$. Therefore, $\nabla_{t} m(w,t,g) = \nabla_{t} \phi(w,t,\tilde{g})$ and we need to verify only the first line of Assumption \ref{ass:smooth}.  $|\nabla_{h}\phi(w,t,\tilde{g})| =| \frac{1}{I(z)} R(w,g)|\leq \frac{U}{E} $, $|\nabla_{g} \phi(w,t,\tilde{g}) \leq |\nabla_{\gamma}(m, \Lambda(z,g(z))'\theta,g(z))| + |\frac{h(z)}{I(z)}\nabla_{\gamma} R(w,g)| \leq U + \frac{U^2}{E}  $,
$|\nabla_{I}\phi(w,t,\tilde{g})| =| \frac{h(z)}{I^2(z)} R(w,g)|\leq \frac{U^2}{E^2}$,
$|\nabla_{gg} \phi(w,t,\tilde{g}) \leq |\nabla_{\gamma\gamma}(m, \Lambda(z,g(z))'\theta,g(z))| + |\frac{h(z)}{I(z)}\nabla_{\gamma\gamma} R(w,g)| \leq U + \frac{U^2}{E}  $,
$|\nabla_{II}\phi(w,t,\tilde{g})| =| \frac{2h(z)}{I^3(z)} R(w,g)|\leq \frac{2U^2}{E^3}$,
$|\nabla_{Ih}\phi(w,t,\tilde{g})| = |\frac{1}{I^2(z)} R(w,g)|\leq \frac{U}{E^2}$,
$|\nabla_{Ig} \phi(w,t,\tilde{g}) = |\frac{h(z)}{I^2(z)}\nabla_{\gamma} R(w,g)| \leq  \frac{U^2}{E^2}  $.

(b). First, $m(w,t,g)$ is monotone in $t$ if and only if $\phi(w,t,\tilde{g})$ is monotone in $t$. Second, the partial derivative in Assumption \ref{ass:identification} is the same for  $m$ if  and only if it holds for $\phi$:
$$\nabla_{t} E [m(w,\Lambda(z,g_0(z))'\theta_0,g_0(z))|z] = \nabla_{t} E [\phi(w,\Lambda(z,g_0(z))'\theta_0,g_0(z))|z].$$
Therefore, (b) holds.

\end{proof}

\section{Proofs from Section~\ref{sec:applications}}\label{sec:proof-apps}
\label{sec:ortho}

\begin{lemma}
The loss function $\ell(w,\Lambda(z,g(z))'\theta,g)$ defined in (\eqref{eq:nonlinearTEODE}) is an orthogonal
loss with respect to $g=\{h, q, V\}$.
\end{lemma}
\begin{proof}

Define the gradient of the loss function
\begin{align*}
    \rho(w, \theta_0, g_0(z)) = \nabla_{t} \ell(w,\Lambda(z,g(z))'\theta,g) \Lambda(z,g(z)).
\end{align*}
We verify orthogonality with respect to each component in $g$:
\begin{align*}
    \mathbb{E}[\nabla_h \rho(w, \theta_0, g_0(z))\,|\,u] = & -\mathbb{E}\left[\frac{G'(x'\theta_0 + f_0(u))}{V_0(z)} \, (x - h_0(u)) \theta_0' + \frac{G(x'\theta_0+f_0(u))-y}{V_0(z)} I_p \,\bigg|\,u\right]\\
    = & -\mathbb{E}\left[(x-h_0(u))\theta_0' + \frac{G(x'\theta_0+f_0(u))-y}{V_0(z)} I_p \,\bigg|\,u\right]\\
    = & -\mathbb{E}\left[x-h_0(u)\,|\,u\right]\theta_0' - \mathbb{E}\left[\frac{\mathbb{E}\left[G(x'\theta_0+f_0(u))-y|x,u\right]}{V_0(z)} I_p \,\bigg|\,u\right] = 0\\
\mathbb{E}[\nabla_q \rho(w, \theta_0, g_0(z))\,|\,u] = & \mathbb{E}\left[\frac{G'(x'\theta_0 + f_0(u))}{V_0(z)} \, (x - h_0(u)) \,\bigg|\,u\right]
    =  \mathbb{E}\left[x-h_0(u)\,\bigg|\,u\right] = 0\\
\mathbb{E}[\nabla_V \rho(w, \theta_0, g_0(z))\,|\,z] = & -\mathbb{E}\left[\frac{G(x'\theta_0+f_0(u))-y}{V_0(z)^2} \,\bigg|\,z\right] = 0
\end{align*}
where $I_p$ denotes the $p$-dimensional identity matrix.
\end{proof}
\begin{proof}[Proof of Corollary \ref{cor:non-linear-te}]
We verify Assumptions \ref{ass:smooth}-\ref{ass:convexity_moment} of Theorem \ref{cor:non-ortho-rate}.
(a) Assumption \ref{ass:smooth} follows from condition 2 with $U_{\text{TE}}=\frac{U}{\nu} + \frac{U}{\nu^2}+\frac{2U}{\nu^3}$. (b) Assumption \ref{ass:identification} (a) follows from condition 3. Assumption \ref{ass:identification} (b) holds since
\begin{align*}
    \partial_t \mathbb{E}[m(w,\Lambda(z,g_0(z))'\theta_0, g_0(z))|z] = \frac{G'(x'\theta_0+f_0(u))}{V_0(z)}=1.
\end{align*}
Assumption \ref{ass:convexity_moment} follows from condition 3. Since $\frac{1}{V(z)}G'((x-h(u))'\theta + q(u))\geq \nu$, it is monotonically increasing and $\ell(w,\Lambda(z,g(z))'\theta,g)$ is a convex function of $\theta$.

\end{proof}

redpajama_set_name: RedPajamaArXiv