The exact contents of citations.db main_text.text for this paper — one flattened LaTeX string, title through conclusion, appendix excluded, unmodified except for removing email addresses. This is what our citation measures are computed over.
132,126 characters
Orthogonal Statistical Learning
\iftoggle{journal}{}{
\maketitle
\begin{abstract}
We provide non-asymptotic excess risk guarantees for statistical learning in a setting where the population risk with respect to which we evaluate the target parameter depends on an unknown \emph{nuisance parameter} that must be estimated from data. We analyze a two-stage sample splitting meta-algorithm that takes as input arbitrary estimation algorithms for the target parameter and nuisance parameter. We show that if the population risk satisfies a condition called \emph{Neyman orthogonality}, the impact of the nuisance estimation error on the excess risk bound achieved by the meta-algorithm is of second order. Our theorem is agnostic to the particular algorithms used for the target and nuisance and only makes an assumption on their individual performance. This enables the use of a plethora of existing results from machine learning to give new guarantees for learning with a nuisance component. Moreover, by focusing on excess risk rather than parameter estimation, we can provide rates under weaker assumptions than in previous works and accommodate settings in which the target parameter belongs to a complex nonparametric class. We provide conditions on the metric entropy of the nuisance and target classes such that \emph{oracle rates} of the same order as if we knew the nuisance parameter are achieved. \end{abstract}
}
\iftoggle{journal}{
\begin{frontmatter}
\title{Orthogonal Statistical Learning}
\runtitle{Orthogonal Statistical Learning}
\begin{aug}
\author[A]{\fnms{Dylan J.} \snm{Foster}\ead[label=e1]{[email removed]}}
\and
\author[B]{\fnms{Vasilis} \snm{Syrgkanis}\ead[label=e2]{[email removed]}}
\address[A]{Microsoft Research, New England,
\printead{e1}}
\address[B]{Microsoft Research, New England,
\printead{e2}}
\end{aug}
\begin{abstract}
We provide non-asymptotic excess risk guarantees for statistical learning in a setting where the population risk with respect to which we evaluate the target parameter depends on an unknown \emph{nuisance parameter} that must be estimated from data. We analyze a two-stage sample splitting meta-algorithm that takes as input arbitrary estimation algorithms for the target parameter and nuisance parameter. We show that if the population risk satisfies a condition called \emph{Neyman orthogonality}, the impact of the nuisance estimation error on the excess risk bound achieved by the meta-algorithm is of second order. Our theorem is agnostic to the particular algorithms used for the target and nuisance and only makes an assumption on their individual performance. This enables the use of a plethora of existing results from machine learning to give new guarantees for learning with a nuisance component. Moreover, by focusing on excess risk rather than parameter estimation, we can provide rates under weaker assumptions than in previous works and accommodate settings in which the target parameter belongs to a complex nonparametric class. We provide conditions on the metric entropy of the nuisance and target classes such that \emph{oracle rates} of the same order as if we knew the nuisance parameter are achieved. \end{abstract}
\begin{keyword}[class=MSC2020]
\kwd[Primary ]{62G08}
\kwd[; secondary ]{62C20, 62D20}
\end{keyword}
\begin{keyword}
\kwd{Statistical learning}
\kwd{double machine learning}
\kwd{Neyman orthogonality}
\kwd{policy learning}
\kwd{treatment effects}
\kwd{local Rademacher complexity}
\end{keyword}
\end{frontmatter}
}{}
\iftoggle{journal}{}{
{
\hypersetup{linkcolor=black}
\tableofcontents
}
\newpage
}
\iftoggle{draft}{
{
\hypersetup{linkcolor=black}
\tableofcontents
}
\newpage
}{}
\section{Introduction}
\label{sec:intro}
Predictive models based on modern machine learning methods are becoming increasingly widespread in policy making, with applications in healthcare, education, law enforcement, and business decision making. Most problems that arise in policy making, such as attempting to predict counterfactual outcomes for different interventions or optimizing policies over such interventions, are not pure prediction problems, but rather are causal in nature. It is important to address the causal aspect of these problems and build models that have a causal interpretation.
A common paradigm in the search of causality is that to estimate a model with a causal interpretation from observational data---that is, data not collected via randomized trial or via a known treatment policy---one typically needs to estimate many other quantities that are not of primary interest, but that can be used to de-bias a purely predictive machine learning model by formulating an appropriate loss. One example of such a \emph{nuisance parameter} is the propensity for taking an action under the current policy, which can be used to form unbiased estimates for the reward for new policies, but is typically unknown in datasets that do not come from controlled experiments.
To make matters more concrete, let us walk through an example for which certain variants have been well-studied in machine learning \citep{dudik2011doubly,swaminathan2015counterfactual,nie2017quasi,kallus2018policy}. Suppose a decision maker wants to estimate the causal effect of some treatment $T\in \{0,1\}$ on an outcome $Y$ as a function of a set of observable features $X$; the causal effect will be denoted as $\theta(X)$. Typically, the decision maker has access to data consisting of tuples $(X_i, T_i, Y_i)$, where $X_i$ is the observed feature for sample $i$, $T_i$ is the treatment taken, and $Y_i$ is the observed outcome.
Due to the partially observed nature of the problem, one needs to create unbiased estimates of the unobserved outcome. A standard approach is to make an \emph{unconfoundedness} assumption \citep{rosenbaum1983central} and use the so-called \emph{doubly-robust} formula, which is a combination of direct regression and inverse propensity scoring. Let $Y_i(t)$ denote the potential outcome for treatment $t$ in sample $i$, and let $f_0(t,x_i)\vcentcolon=\operatorname{\mathbb{E}}\brk[\big]{Y_i(t) \mid x_i}$ and $p_0(t,x_i) \vcentcolon= \operatorname{\mathbb{E}}\brk*{1\{T=t\} \mid x_i}$. If $(Y_i(0),Y_i(1))\perp{}T_i\mid{}X_i$, then the following is an unbiased estimator for the \revoneedit{conditional mean potential outcome (given covariates):}
\begin{equation}
\widehat{Y}_i{(t)} = f_0(t,x_i) + \frac{(Y_i - f_0(t,x_i))\, 1\{T_i=t\}}{p_0(t,x_i)}.
\end{equation}
Given such an estimator, we can estimate the treatment effect by running a regression between the unbiased estimates and the features, i.e. solve $\min_{\theta\in \Theta} \sum_i \prn{\widehat{Y}(1) - \widehat{Y}(0) - \theta(X_i)}^2$ over a target parameter class $\Theta$. In the population limit, with infinite samples, this corresponds to finding a parameter\xspace $\theta(x)$ that minimizes the population risk $\operatorname{\mathbb{E}}\brk[\big]{(\widehat{Y}_i(1) - \widehat{Y}_i(0) - \theta(X))^2}$. Similarly, if the decision maker is interested in policy optimization rather than estimating treatment effects, they can use these unbiased estimates to solve $\min_{\theta\in \Theta} \sum_{i} (\widehat{Y}_i(0) - \widehat{Y}_i(1))\cdot \theta(X_i)$ over a policy space $\Theta$ of functions mapping features to $\{0,1\}$. However, when dealing with observational data, the functions $f_0$ and $p_0$ are not known, and must be estimated if we wish to evaluate the proxy labels $\widehat{Y}(t)$. Since these functions are only used as a means to learn the target parameter $\theta$, we may regard them as nuisance parameters. The goal of the learner is to estimate a target parameter that achieves low population risk when evaluated at the \emph{true} nuisance parameters as opposed to the estimated nuisance parameters, since only then does the model have a causal interpretation.
This phenomenon is ubiquitous in causal inference and motivates us to formulate the abstract problem of \emph{statistical learning with a nuisance component}: Given $n$ i.i.d. examples from a distribution $\cD$, a learner is interested in finding a \emph{target parameter\xspace} $\widehat{\theta}\in \Theta$ so as to minimize a population risk function $L_{\cD}: \Theta \times \cG \rightarrow \bbR$. The population risk depends not just on the target parameter\xspace, but also on a \emph{nuisance parameter\xspace} whose true value $g_0\in \cG$ is unknown to the learner. The goal of the learner is to produce an estimate that has small \emph{excess risk} evaluated at the unknown true nuisance parameter\xspace:
\begin{equation}
\label{eq:excess_risk_intro}
L_{\cD}(\widehat{\theta},g_0) - \inf_{\theta\in\Theta}L_{\cD}(\theta,g_0)\to_n0.
\end{equation}
Depending on the application, such an excess risk bound can take different interpretations. For many settings, such as treatment effect estimation, it is closely related to mean squared error, while in policy optimization it typically corresponds to regret. Following the tradition of statistical learning theory \citep{vapnik1995nature,bousquet2004introduction}, we make excess risk the primary focus of our work, independent of the interpretation. We develop algorithms and analysis tools that generically address \cref{eq:excess_risk_intro}, then apply these tools to a number of applications of interest.
The problem of statistical learning with a nuisance component is strongly connected to the well-studied semiparametric inference problem \citep{levit1976efficiency,ibragimov1981statistical,pfanzagl1982contributions,bickel1982adaptive,klaassen1987consistent,robinson1988root,bickel1993efficient,newey1994asymptotic,robins1995semiparametric, ai2003efficient,van2003unified,van2003unifiedb,ai2007estimation,tsiatis2007semiparametric,kosorok2008introduction,van2011targeted,ai2012semiparametric,chernozhukov2016locally,belloni2017program,chernozhukov2016double}, which focuses on providing so-called ``$\sqrt{n}$-consistent and asymptotically normal'' estimates for a low-dimensional target parameter $\theta_0$ (which may be expressed as a population risk minimizer or a solution to estimating equations) in the presence of a typically nonparametric nuisance parameter. Unlike the semiparametric inference problem, statistical learning with a nuisance component does not require a well-specified model, nor a unique minimizer of the population risk. Moreover, we do not ask for parameter recovery or asymptotic inference (e.g., asymptotically valid confidence intervals). Rather, we are content with an excess risk bound, regardless of whether there is an underlying true parameter to be identified. As a consequence, we provide guarantees even in the presence of misspecification, and when the target parameter\xspace belongs to a large, potentially nonparametric class. For example, one line of previous work gives semiparametric inference guarantees when the nuisance parameter\xspace is a neural network \citep{chen1999improved,farrell2018deep}; by focusing on excess risk we can give guarantees for the case where the \emph{target} parameter\xspace is a neural network.
The case where the target parameter belongs to an arbitrary class has not been addressed at the level of generality we consider in the present work, but we mention some prior work that goes beyond the low-dimensional/parametric setup for special cases. \cite{athey2017efficient} and \cite{zhou2018offline} give guarantees based on metric entropy of the target class for the specific problem of treatment policy learning. For estimation of treatment effects, various nonparametric classes have been used for the target class on a case by case basis, including kernels \citep{nie2017quasi}, random forests \citep{athey2016generalized, oprescu2018orthogonal,friedberg2018}, and high-dimensional linear models \citep{chernozhukov2017orthogonal,chernozhukov2018plugin}. Other results allow for fairly general choices for the target parameter class in specific statistical models \citep{rubin2005general,rubin2007doubly,diaz2013targeted,van2014targeted,kennedy2017non,kennedy2019robust,kunzel2017meta}. Our work unifies these directions into a single framework, and our general tools lead to improved or refined results when specialized to many of these individual settings.
Our approach is to reduce the problem of statistical learning with a nuisance component to the standard formulation of statistical learning. We build on a recent thread of research on semiparametric inference known as ``double'' or ``debiased'' machine learning
\citep{chernozhukov2016locally,chernozhukov2017orthogonal,chernozhukov2016double,chernozhukov2018double,chernozhukov2018plugin}, which leverages sample splitting to provide inference guarantees under weak assumptions on the estimator for the nuisance parameter. Rather than directly analyzing particular algorithms and models for the target parameter (e.g., regularized regression, gradient boosting, or neural network estimation), we assume a black-box guarantee for the excess risk in the case where a nuisance value $g\in\cG$ is fixed. Our main theorem asks only for the existence of an algorithm $\mathrm{Alg}(\Theta, S ;\, g)$ that, for any given nuisance parameter\xspace $g$ and data set $S$, achieves low excess risk with respect to the population risk $L_{\cD}(\theta, g)$, i.e. with probability at least $1-\delta$,
\begin{equation}
L_{\cD}(\widehat{\theta},g) - \inf_{\theta\in\Theta}L_{\cD}(\theta,g) \leq \mathrm{Rate}_{\cD}(\Theta, S, \delta;\,{}g).
\end{equation}
Likewise, we assume the existence of a black-box algorithm $\mathrm{Alg}(\cG,S)$ to estimate the nuisance component $g_0$ from the data, with the required estimation guarantee varying from problem to problem.
\begin{figure}[tp]
\begin{framedmetaalgorithm}[Two-Stage Estimation with Sample Splitting]~\\
\textbf{Input}: Sample set $S=z_1,\ldots,z_n$.
\begin{itemize}
\item Split $S$ into subsets $S_1=z_1,\ldots,z_{\floor{n/2}}$ and $S_2=S\setminus{}S_1$.
\item Let $\widehat{g}$ be the output of $\mathrm{Alg}(\cG,S_1)$.
\item Return $\widehat{\theta}$, the output of $\mathrm{Alg}(\Theta,S_2;\,\widehat{g})$.
\end{itemize}
\label{alg:sample_splitting}
\end{framedmetaalgorithm}
\end{figure}
Given access to the two black-box algorithms, we analyze a simple sample splitting meta-algorithm for statistical learning with a nuisance component, presented as \texorpdfstring{\hyperref[alg:sample_splitting]{Meta-Algorithm \ref{alg:sample_splitting}}}{Meta-Algorithm \ref{alg:sample_splitting}}.
We can now state the main question addressed in this paper:
\emph{When is the excess risk achieved by sample splitting robust to nuisance component estimation error?}
In more technical terms, we seek to understand when the two-stage sample splitting meta-algorithm achieves an excess risk bound with respect to $g_0$, in spite of error in the estimator $\widehat{g}$ output by the first-stage algorithm. Robustness to nuisance estimation error allows the learner to use more complex models for nuisance estimation and---under certain conditions on the complexity of the target and nuisance parameter\xspace classes---to learn target parameters\xspace whose error is, up to lower order terms, as good as if the learner had known the true nuisance parameter\xspace in advance. Such a guarantee is referred to as achieving an \emph{oracle rate} in semiparametric inference.
\oldparagraph*{Overview of results} We use \emph{Neyman orthogonality} \citep{neyman1959optimal,neyman1979c}, a key tool in inference in semiparametric models \citep{newey1994asymptotic,van2000asymptotic,robins2008higher,zheng2010asymptotic,belloni2017program,chernozhukov2016double}, to provide oracle rates for statistical learning with a nuisance component. We show that if the population risk satisfies a functional analogue of Neyman orthogonality, the estimation error of $\widehat{g}$ has a second order impact on the overall excess risk (relative to $g_0$) achieved by $\widehat{\theta}$. To gain some intuition, Neyman orthogonality is weaker condition than double-robustness, albeit similar in flavor, (see, e.g., \cite{chernozhukov2016locally}) and is satisfied by both the treatment effect loss and the policy learning loss described in the introduction. In more detail, our variant of the Neyman orthogonality condition asserts that a functional cross-derivative of the loss vanishes when evaluated at the optimal target and nuisance parameters\xspace. Prior work provides a number of means through which to construct Neyman orthogonal losses whenever certain moment conditions are satisfied by the data generating process \citep{chernozhukov2016double,chernozhukov2016locally,chernozhukov2018plugin}. Indeed, orthogonal losses can be constructed in settings including treatment effect estimation, policy learning, missing and censored data problems, estimation of structural econometric models, and game-theoretic models.
We identify two regimes of excess risk behavior:
\begin{enumerate}
\item \emph{Fast rates.} When the population risk is strongly convex with respect to the prediction of the target parameter\xspace (e.g., the treatment effect estimation loss), then typically so-called \emph{fast rates} (e.g., rates of order of $O(1/n)$ for parametric classes) are optimal if the true nuisance parameter\xspace is known. Letting $R_{\cG}$ denote the estimation error of the nuisance component, in this setting we show that orthogonality implies that the first stage error has an impact on the excess risk of the order of $R_{\cG}^4$ (in particular, $n^{-1/4}$-RMSE rates for the nuisance suffice when the target is parametric).
\item \emph{Slow rates.} Absent any strong convexity of the population risk (e.g., for the treatment policy optimization loss), typically \emph{slow rates} (e.g. rates of order $O(1/\sqrt{n})$ for parametric classes) are optimal if the true nuisance parameter\xspace is known. For this setting, we show that the impact of nuisance estimation error is of the order $R_{\cG}^2$ so, once again, $n^{-1/4}$ RMSE rates for the nuisance suffice when the target is parametric.
\end{enumerate}
To make the conditions above concrete for arbitrary classes, we give conditions on the relative complexity of the target and nuisance classes---quantified via \emph{metric entropy}---under which the sample splitting meta-algorithm achieves oracle rates, assuming the two black-box estimation algorithms are instantiated appropriately. This allows us to extend several prior works beyond the parametric regime to complex nonparametric target classes. Our technical results extends the works of \cite{yang1999information,rakhlin2017empirical}, which provide minimax optimal rates without nuisance components and utilize the technique of \emph{aggregation} in designing optimal algorithms.
The flexibility of our approach allows us to instantiate our framework with any machine learning model and algorithm of interest for both nuisance and target parameter\xspace estimation, and to utilize the vast literature on generalization bounds in machine learning to establish refined (e.g., data-dependent or dimension-independent) rates for several classes of interests. For instance, our approach allows us to leverage recent work on size-independent generalization error of neural networks.
Moving beyond black-box results, we use our main theorems as a starting point to provide sharp analyses for certain general-purpose statistical learning algorithms for target estimation in the presence of nuisance parameters. First, we provide a new analysis for empirical risk minimization with plug-in estimation of nuisance parameters, wherein we extend the classical local Rademacher complexity analysis of empirical risk minimization \citep{koltchinskii2000rademacher,bartlett2005local} to account for the impact of the nuisance error (leveraging orthogonality). Second, in the slow rate regime we give a new analysis of \emph{variance-penalized} empirical risk minimization with plug-in nuisance estimation, which allows us to recover and extend several prior results in the literature on policy learning. Our result improves upon the variance-penalized risk minimization approach of \cite{maurer2009empirical} by replacing the dependence on the metric entropy at a fixed approximation level with the \emph{critical radius}, which is related to the entropy integral.
As a consequence of focusing on excess risk, we obtain oracle rates under weaker assumptions on the data generating process than in previous works. Notably, we obtain guarantees even when the target parameter\xspace is misspecified and the target parameters are not identifiable. For instance, for sparse high-dimensional linear classes, we obtain optimal prediction rates with no restricted eigenvalue assumptions. We highlight the applicability of our results to four settings of primary importance in the literature: 1) estimation of heterogeneous treatment effects from observational data, 2) offline policy optimization, 3) domain adaptation, 4) learning with missing data. For each of these applications, our general theorems allow for the use of arbitrary estimators for the nuisance and target parameter\xspace classes and provide robustness to the nuisance estimation error.
\subsection{Related work}
\oldparagraph*{General frameworks for learning/inference with nuisance parameters} The work of \cite{van2003unified} and subsequent refinements and extensions \citep{van2006cross,van2007super} develops cross-validation methodology for a similar risk minimization setting in which the target risk parameter depends on an unknown nuisance parameter. \cite{van2003unified} analyze a cross-validation meta-algorithm in which the learner simultaneously forms a nuisance parameter estimator and a set of candidate target parameter estimators using a set of training samples, then selects a final estimate for the target parameter by minimizing an empirical loss over a validation set. The train and validation splits may be chosen in a general fashion that encompasses $K$-fold and Monte Carlo validation.
They provide finite-sample oracle rates for the excess risk in the case where the target parameter belongs to a finite class (in particular, rates of the type $\log\abs*{\Theta}/n$ for a class of square losses and $\sqrt{\log\abs*{\Theta}/n}$ for general losses), and also extend these guarantees to linear combinations of basis functions via pointwise $\varepsilon$-nets (in our language, such classes are \emph{parametric}). Overall, our approach offers several new benefits:
\begin{itemize}
\item By completely splitting nuisance estimation and target estimation into separate stages and taking advantage of orthogonality, we can provide
meta-theorems on robustness that are invariant to the choice of learning algorithm both for the first and second stage, which obviates the need to assume the target class is finite or admits a linear representation (\cref{sec:orthogonal}).
\item When we do specialize to algorithms such as ERM and variants, we can provide finite-sample guarantees for rich classes of target parameters\xspace
in terms of sharp learning-theoretic complexity measures such as local Rademacher complexity and empirical metric entropy (\cref{sec:erm}). In particular, we can provide conditions under which oracle rates are attained under very general complexity assumptions on the target and nuisance parameters (\cref{sec:oracle}).
\end{itemize}
The methodology of \cite{van2003unified} can be used to directly estimate a target parameter or to select the best of many candidate nuisance estimators in a data-driven fashion. \cite{van2007super} refers to the use of this cross-validation methodology to perform data-adaptive estimation of nuisance parameters as the ``super learner'', and subsequent work has advocated for its use for nuisance estimation within a framework for semiparametric inference known as \emph{targeted maximum likelihood estimation} (TMLE). TMLE \citep{scharfstein1999theory,van2006targeted,zheng2010asymptotic,van2011targeted} and its more general variant, targeted minimum loss-based estimation, are general frameworks for semiparametric inference which---like our framework---employ empirical risk minimization in the presence of nuisance parameters. TMLE estimates the target parameter by repeatedly minimizing an empirical risk (typically the negative log-likelihood) in order to refine an initial estimate. This approach easily incorporates constraints, and can be used in tandem with the super learning technique. The analysis leverages orthogonality, and is also agnostic to how the nuisance estimates are obtained. However, the main focus of this framework is on the classical semiparametric inference objective; minimizing a population risk is not the end goal as it is here.
\oldparagraph*{Specific instances of risk minimization with nuisance parameters}
A number of prior works employ empirical risk minimization with nuisance parameters for specific statistical models \citep{rubin2005general,rubin2007doubly,diaz2013targeted,van2014targeted,kennedy2017non,kennedy2019robust,kunzel2017meta}. These results allow for general choices for the target class and nuisance class (typically subject to Donsker conditions, or with guarantees in the vein of \cite{van2003unified}), and the main focus is semiparametric inference rather than excess risk guarantees.
\oldparagraph*{Nonparametric target parameters}
Outside of the risk minimization-based approaches above and the examples in the prequel \citep{athey2016generalized,nie2017quasi,athey2017efficient,zhou2018offline,oprescu2018orthogonal,friedberg2018,chernozhukov2017orthogonal,chernozhukov2018plugin}, a number of other results also consider inference for nonparametric target parameters in the presence of nuisance parameters. In \cite{van2006estimating}, the target is a Lipschitz function over $[0,\infty)$ (the marginal survival function) and an estimation rate of $n^{-2/3}$ is given. \cite{wang2010nonparametric} consider estimation of smooth nonparametric target parameters in the presence of missing outcomes, and give algorithms based on kernel smoothing. \cite{robins2001comment,robins2008higher} consider settings where the target parameter is scalar, but the optimal rate is nonparametric due to the presence of complex nuisance parameters.
\oldparagraph*{Sample splitting}
While our use of sample splitting is directly inspired by recent use of the technique in double/debiased machine learning \citep{chernozhukov2016locally,chernozhukov2016double}, the basic technique dates back to the early days of semiparametric inference and it has found use in many other works to remove Donsker conditions for estimation in the presence of nuisance parameters \citep{bickel1982adaptive,klaassen1987consistent,van2000asymptotic,robins2008higher,zheng2010asymptotic}.
\oldparagraph*{Limitations}
Our results are quite general, but there are some applications that go beyond the scope of our framework. For example, while we consider only plug-in estimation for the nuisance parameters\xspace, several works attain refined results by using specialized estimators \cite{van2006targeted,hirshberg2017augmented,chernozhukov2018double,ning2018robust}. While our focus is on methods based on loss minimization, some problems such as nonparametric instrumental variables \citep{newey2003instrumental,hall2005nonparametric,blundell2007semi,chen2009efficient,chen2012estimation,chen2015sieve,chen2018optimal} are more naturally posed in terms of conditional moment restrictions.\iftoggle{journal}{}{\textcolor{red}{footnote}{In fact, nonparametric IV can be cast as a special case of the setup in \cref{eq:excess_risk}, but we do not know of any estimators for this problem that satisfy the conditions required to apply our main theorems.}}\iftoggle{journal}{ In fact, nonparametric IV can be cast as a special case of the setup in \cref{eq:excess_risk}, but we do not know of any estimators for this problem that satisfy the conditions required to apply our main theorems.}{}
\begin{revone}
Another direction where our results leave room for future improvement concerns the reliance on Neyman orthogonality. While Neyman orthogonality is a fairly general condition which allows one to handle many nuisance parameters simultaneously, many problems admit additional structure which can lead to more refined guarantees. For example, in the context of treatment effect estimation, subsequent work of \cite{kennedy2020optimal} uses the doubly robust structure of the problem to give guarantees that accommodate the case where different nuisance components (regression functions and propensity scores) are estimated at different rates.
\end{revone}
\subsection{Organization}
\begin{revone}
The first part of this paper presents our main results. \cref{sec:setup} contains technical preliminaries and definitions, and \cref{sec:orthogonal} presents our main theorems concerning the excess risk of \cref{alg:sample_splitting}. \cref{sec:orthogonal} also includes basic examples in which we apply these theorems to treatment effect estimation and policy learning.
Our main results are stated at a high level of generality, and consider generic estimation algorithms for the target and nuisance parameters. In the second part of the paper, we make matters more concrete and focus on specific algorithms. We leverage the main theorems to give explicit bounds based on the statistical capacity of the target and nuisance class. In particular:
\begin{itemize}
\item \cref{sec:erm} (\emph{Plug-in Empirical Risk Minimization}) provides explicit bounds for plug-in empirical risk minimization as the second stage of the meta-algorithm.
\item \cref{sec:oracle} (\emph{Sufficient Conditions for Oracle Rates}) considers aggregation based algorithms that go beyond empirical risk minimization, and gives sufficient conditions (as a function of the statistical capacity of the nuisance and target class) under which \cref{alg:sample_splitting} can be configured such that oracle excess risk bounds are achieved.
\end{itemize}
We conclude with discussion in \cref{sec:discussion}. Additional results are deferred to the appendix, which is split into three parts. \cref{part:experiments} contains experiments, and \cref{part:additional} contains supplementary theoretical results, including sufficient conditions for Neyman orthogonality, applications of our main results to specific settings, and further guarantees for specific algorithms and function classes. \cref{part:proofs} contains proofs for our main results.
\end{revone}
\section{Framework: Statistical Learning with a Nuisance Component}
\label{sec:setup}
We work in a learning setting in which observations belong to an abstract set $\cZ$. We receive a sample set $S\vcentcolon={}z_1,\ldots,z_n$ where each $z_t$ is drawn i.i.d. from an unknown distribution $\cD$ over $\cZ$. Define variable subsets $\cX\subseteq{}\cW\subset\cZ$; the restriction $\cX\subseteq{}\cW$ is not strictly necessary but simplifies notation. We focus on learning parameters\xspace that come from a \emph{target parameter\xspace class} $\Theta:\cX\to\cV_2$ and \emph{nuisance parameter\xspace class} $\cG:\cW\to{}\cV_1$, where $\cV_1$ and $\cV_2$ are finite dimensional vector spaces of dimension $K_1$ and $K_2$ respectively, equipped with norms $\nrm*{\cdot}_{\cV_1}$ and $\nrm*{\cdot}_{\cV_2}$. Note that since our results are fully non-asymptotic, the classes $\Theta$ and $\cG$ may be taken to grow with $n$.
Given an example $z_{t}\in{}\cZ$, we write $w_t\in\cW$ and $x_t\in\cX$ to denote the subsets of $z_t$ that act as arguments to the nuisance and target parameters respectively. For example, we may write $g(w_t)$ for $g\in\cG$ or $\theta(x_t)$ for $\theta\in\Theta$. We assume that the function spaces $\Theta$ and $\cG$ are equipped with \vsedit{pre-norms $\nrm*{\cdot}_{\Theta}$ and $\nrm*{\cdot}_{\cG}$ respectively, which need to satisfy non-negativity and $\|0\|=0$, but not necessarily the triangle inequality nor absolute homogeneity.} In our applications, both pre-norms take the form
$\nrm*{f}_{L_p(\cV,\cD)}=\prn*{\operatorname{\mathbb{E}}_{z\sim{}\cD}\nrm*{f(z)}_{\cV}^{p}}^{1/p}$
for functions $f:\cZ\to\cV$, where $\cV\in\crl*{\cV_1,\cV_2}$.
We measure performance of the target predictor through the real-valued \emph{population loss functional} $L_{\cD}(\theta,g)$, which maps a target predictor $\theta$ and nuisance predictor $g$ to a loss. The subscript $\cD$ in $L_{\cD}$ denotes that the functional depends on the underlying distribution $\cD$. For all of our applications, $L_{\cD}$ has the following structure, in line the classical statistical learning setting: First define a pointwise loss function $\ell(\theta,g;\,{}z)$, then define $L_{\cD}(\theta,g) \vcentcolon= \operatorname{\mathbb{E}}_{z\sim{}\cD}\brk{\ell(\theta,g;\,{}z)}$. Our general framework does not explicitly assume this structure, however.
Let $g_0\in\cG$ be the unknown true value for the nuisance parameter. Given the samples $S$, and without knowledge of $g_0$, we aim to produce a \emph{target predictor} $\widehat{\theta}$ that minimizes the \emph{excess risk} evaluated at $g_0$
\begin{equation}
\label{eq:excess_risk}
L_{\cD}(\widehat{\theta},g_0) - \inf_{\theta\in\Theta}L_{\cD}(\theta,g_0).
\end{equation}
As discussed in the introduction, we will always produce such a predictor via the sample splitting meta-algorithm (\cref{alg:sample_splitting}), which makes uses of a nuisance predictor $\widehat{g}$.
When the infimum in the excess risk is obtained, we use $\theta^{\star}$ to denote the corresponding minimizer, in which case the excess risk can be written as
\[
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta^{\star},g_0).
\]
We occasionally use the notation $\theta_0$ to refer to a particular target parameter with respect to which the second stage satisfies a \emph{first-order condition}, e.g. $D_{\theta}L_{\cD}(\theta_0,g_0)[\theta-\theta_0]=0\,\,\forall{}\theta\in\Theta$. If $\theta_0\in\Theta$ and the population risk is convex, then we can take $\theta^{\star}=\theta_0$ without loss of generality, but we do not assume this, and in general we do not assume existence of a such a parameter $\theta_0$.
\oldparagraph*{Notation}
We let $\tri*{\cdot,\cdot}$ denote the standard inner product. $\nrm*{\cdot}_{p}$ will denote the $\ell_{p}$ norm over $\bbR^{d}$ and $\nrm*{\cdot}_{\sigma}$ will denote the spectral norm over $\bbR^{d_1\times{}d_2}$.
Unless otherwise stated, the expectation $\operatorname{\mathbb{E}}\brk*{\cdot}$, probability $\bbP(\cdot)$, and variance $\mathrm{Var}(\cdot)$ operators will be taken with respect to the underlying distribution $\cD$. We define empirical analogues $\operatorname{\mathbb{E}}_{n}\brk{\cdot}$, $\bbP_n(\cdot)$, and $\mathrm{Var}_{n}(\cdot)$ with respect to a sample set $z_1,\ldots,z_n$, whose value will be clear from context. For a vector space $\cV$ with norm $\nrm*{\cdot}_{\cV}$ and function $f:\cZ\to\cV$, we define $\nrm*{f}_{L_p(\cV,\cD)}=\prn*{\operatorname{\mathbb{E}}_{z\sim{}\cD}\nrm*{f(z)}_{\cV}^{p}}^{1/p}$ for $p\in(0,\infty)$, with $L_p(\ell_q,\cD)$ referring to the special case where $\nrm*{\cdot}_{\cV}=\nrm*{\cdot}_{q}$. For a sample set $S=z_{1:n}$, we define the empirical variant $\nrm*{f}_{L_p(\cV,S)}=\prn*{\frac{1}{n}\sum_{i=1}^{n}\nrm*{f(z_i)}_{\cV}^{p}}^{1/p}$. When $\cV=\bbR$, we drop the first argument and write $L_p(\cD)$ and $L_p(S)$. We extend these definitions to $p=\infty$ in the natural way.
For a subset $\cX$ of a vector space, $\mathrm{conv}(\cX)$ will denote the convex hull. For an element $x\in\cX$, we define the star hull via
\begin{equation}
\mathrm{star}(\cX,x) = \crl*{t\cdot{}x+(1-t)\cdot{}x'\mid{}x'\in\cX,t\in\brk*{0,1}},
\end{equation}
and adopt the shorthand $\mathrm{star}(\cX) \vcentcolon= \mathrm{star}(\cX,0)$.
Given functions $f,g:\cX\to [0,\infty)$ where $\cX$ is any set,
we use non-asymptotic big-$O$ notation, writing $f=O(g)$ if there exists a numerical
constant $c < \infty$ such that $f(x)\leq{}c\cdot{}g(x)$ for all $x\in\cX$
and $f=\Omega(g)$ if there is a numerical constant $c>0$ such that
$f(x)\geq{}c\cdot{}g(x)$. We write $f = \widetilde{O}(g)$ as shorthand for $f=O(g
\max\{1,\mathrm{polylog}(g)\})$.
\section{Orthogonal Statistical Learning}
\label{sec:orthogonal}
In this section we present our main results on orthogonal statistical learning, which state that under certain conditions on the loss function, the error due to estimation of the nuisance component $g_0$ has higher-order impact on the prediction error of the target component. The results in this section, which form the basis for all subsequent results, are \emph{algorithm-independent}, and only involve assumptions on properties of the population risk $L_{\cD}$. To emphasize the high level of generality, the results in this section invoke the learning algorithms in \cref{alg:sample_splitting} only through ``rate'' functions $\mathrm{Rate}_{\cD}(\cG,\ldots)$ and $\mathrm{Rate}_{\cD}(\Theta,\ldots)$ which respectively bound the estimation error of the first stage and the excess risk of the second stage.
\begin{definition}[Algorithms and Rates]
\label{def:algorithms}
The first and second stage algorithms and corresponding rate functions are defined as follows:
\iftoggle{journal}{\begin{enumerate}}{}
\iftoggle{journal}{}{\begin{enumerate}[label=\textnormal{\textbf{\alph*)}}]}
\item \emph{Nuisance algorithm and rate.} The first stage learning algorithm $\mathrm{Alg}(\cG,S)$, when given a sample set $S$ from distribution $\cD$, outputs a predictor $\widehat{g}$ for which
\[
\nrm*{\widehat{g}-g_0}_{\cG} \leq{} \mathrm{Rate}_{\cD}(\cG, S, \delta)
\]
with probability at least $1-\delta$.
\item \emph{Target algorithm and rate.} The second stage learning algorithm $\mathrm{Alg}(\Theta,S;\,{}g)$, when given sample set $S$ from distribution $\cD$ and any $g\in\cG$ outputs a predictor $\widehat{\theta}$ for which
\[
L_{\cD}(\widehat{\theta},g) - L_{\cD}(\theta^{\star}, g) \leq{} \mathrm{Rate}_{\cD}(\Theta, S, \delta;\,{}\widehat{\theta},g)
\]
with probability at least $1-\delta$.
\end{enumerate}
\revoneedit{We let $\widehat{\Theta}$ denote any function class (fixed a-priori) for which $\widehat{\theta},\theta^{\star}\in\widehat{\Theta}$ almost surely.}
We denote worst-case variants of the rates by $\mathrm{Rate}_{\cD}(\cG, n, \delta) \vcentcolon= \sup_{S:\abs*{S}=n}\mathrm{Rate}_{\cD}(\cG, S, \delta)$ and $\mathrm{Rate}_{\cD}(\Theta, n, \delta;\,{}\widehat{\theta},g) \vcentcolon= \sup_{S:\abs*{S}=n}\mathrm{Rate}_{\cD}(\Theta, S, \delta;\,{}\widehat{\theta},g)$.
\end{definition}
Observe that if one naively applies the algorithm for the target class
using the nuisance predictor $\widehat{g}$ as a plug-in estimate for
$g_0$, the rate stated in \cref{def:algorithms} will only yield a ``pseudo''-excess risk bound of the form
\begin{equation}
\label{eq:excess_risk_wrong}
L_{\cD}(\widehat{\theta},\widehat{g}) - L_{\cD}(\theta^{\star},\widehat{g}) \leq{} \mathrm{Rate}_{\cD}(\Theta, S, \delta;\,{}\widehat{\theta},\widehat{g}).
\end{equation}
This clearly does not match the desired bound \cref{eq:excess_risk},
which concerns the excess risk evaluated at $g_0$ rather than the plug-in estimate $\widehat{g}$. The bulk of our work is to show that orthogonality can be used to correct this mismatch.
\cref{def:algorithms} and subsequent results are stated in terms of a class $\widehat{\Theta}$ containing $\widehat{\theta}$, which in general may have $\widehat{\Theta}\neq{}\Theta$. This extra level of generality serves two purposes. First, it allows for refined analysis in the case where $\widehat{\Theta}\subset\Theta$, which is encountered when using algorithms based on regularization that do not impose hard constraints on, e.g., the norm of the estimator. Second, it permits the use of \emph{improper prediction}, i.e. $\widehat{\Theta}\supset\Theta$, which in some cases is required to obtain optimal rates for misspecified models \citep{audibert2008progressive,foster2018logistic}.
Recall that for a sample set $S=z_1,\ldots,z_n$, the empirical loss is
defined via $L_{S}(\theta,g) =
\frac{1}{n}\sum_{t=1}^{n}\ell(\theta,g;\,{}z_t)$. Many classical
results from statistical learning can be applied to the double machine
learning setting by minimizing the empirical loss with plug-in
estimates for $g_0$, and we can simply cite these results to provide
examples of $\mathrm{Rate}_{\cD}$ for the target class $\Theta$. Note however that
this structure is not assumed by \cref{def:algorithms}, and we indeed
consider algorithms that do not have this form
\revoneedit{(cf. \cref{sec:oracle})}. \revoneedit{Let us highlight that we allow the function
$\mathrm{Rate}_{\cD}(\Theta,S,\delta;\widehat{\theta},\widehat{g})$ to depend on both the
target estimator $\widehat{\theta}$ and the nuisance estimator $\widehat{g}$;
this extra level of generality is useful for deriving
algorithm-specific guarantees (cf. \cref{sec:erm}).}
\oldparagraph*{Fast rates and slow rates}
The rates presented in this section fall into two distinct categories, which we distinguish by referring to them as either \emph{fast rates} or \emph{slow rates}. The meaning of the word ``fast'' or ``slow'' here is two-fold: First, for fast rates, our assumptions on the loss imply that when the target class $\Theta$ is not too large (e.g. a parametric or VC-subgraph class) prediction error rates of order $O(1/n)$ are possible in the absence of nuisance parameters. For our slow rate results, the best prediction error rate that can be achieved is $O(1/\sqrt{n})$, even for small classes. This distinction is consistent with the usage of the term fast rate in statistical learning \citep{bousquet2004introduction,bartlett2005local,srebro2010smoothness}, and we will see concrete examples of such rates for specific classes in later sections (\cref{sec:erm}, \cref{sec:algsandrates}).
The second meaning of ``fast'' versus ``slow'' refers to the first stage: When estimation error for the nuisance is of order $\varepsilon$, the impact on the second stage in our fast rate results is of order $\varepsilon^{4}$, while for our slow rate results the impact is of order $\varepsilon^{2}$. The fast rate regime---particularly, the $\varepsilon^{4}$-type dependence on the nuisance error---will be the more familiar of the two for readers accustomed to semiparametric inference. While fast rates might at first seem to strictly improve over slow rates, these results require stronger assumptions on the loss. Our results in \cref{sec:oracle} show that which setting is more favorable will in general depend on the precise relationship between the complexity of the target parameter\xspace class and the nuisance parameter class.
\subsection{Fast Rates Under Strong Convexity}
\label{ssec:orthogonal_strongly_convex}
We first present general conditions under which the sample splitting meta-algorithm obtains so-called fast rates for prediction. Our assumptions are stated in terms of \emph{directional derivatives} with respect to the target and nuisance parameters\xspace.
\begin{definition}[Directional Derivative]
Let $\cF$ be a vector space of functions. For a functional $F:\cF\to\bbR$, we define the derivative operator $D_{f}F(f)[h] = \frac{d}{dt}F(f+th)\Big|_{t=0}$
for a pair of functions $f,h\in\cF$. Likewise, we define
$D_{f}^{k}F(f)[h_1,\ldots,h_k] = \frac{\partial^{k}}{\partial{}t_1\ldots\partial{}t_k}
F(f + t_1{}h_1+\ldots+t_k{}h_k)\Big|_{t_1=\cdots=t_k=0}$. When considering a functional in two arguments, e.g. $L_{\cD}(\theta,g)$, we write $D_{\theta}L_{\cD}(\theta,g)$ and $D_{g}L_{\cD}(\theta,g)$ to make the argument with respect to which the derivative is taken explicit.
\end{definition}
\revoneedit{To present our results, we fix a representative $\theta^{\star}\in\operatorname*{arg\,min}_{\theta\in\Theta}L_{\cD}(\theta,g_0)$. In general, the minimizer may not be unique---indeed, by focusing on excess risk, we can provide guarantees even when parameter recovery is impossible. Thus, we assume that a single fixed representative $\theta^{\star}$ is used throughout all the assumptions stated in this subsection.}
Our first assumption is the starting point for this work, and asserts that the population loss is \emph{orthogonal} in the sense that the certain pathwise derivatives vanish.
\begin{assumption}[Orthogonal Loss]
\label{ass:orthogonal}
The population risk $L_{\cD}$ is \emph{Neyman orthogonal}:
\begin{equation}
\label{eq:orthogonal}
D_{g}D_{\theta}L_{\cD}(\theta^{\star},g_0)[\theta-\theta^{\star},g-g_0] = 0\quad\forall{}\theta\in\widehat{\Theta},\forall{}g\in\cG.
\end{equation}
\end{assumption}
\revoneedit{Note that while \cref{ass:orthogonal} is stated in terms of the risk
$L_{\cD}$, it is typically satisfied by choosing a particular
point-wise loss function whose expectation equals the risk; examples
are given in the sequel. The construction of such a point-wise loss is typically achieved by adding a de-biasing correction term to some ``initial'' loss, whose minimizer is the target quantity (see Appendix~\ref{sec:orthogonal_loss} for details on automated orthogonal loss construction). The de-biasing correction reduces the impact of errors in the nuisance function estimates on the gradient of the loss, and is related to the notion of an efficient influence function in semi-parametric inference (however, our estimand is not necessarily pathwise differentiable, and hence violates the basic premise of most semi-parametric inference theory).}
Beyond orthogonality, our main theorem requires three additional
assumptions, all of which are fairly standard in the context of fast
rates for statistical learning. We require a first-order optimality
condition for the target class, and require that the population risk
is both smooth and strongly convex with respect to the target parameter.
\begin{assumption}[First Order Optimality]
\label{ass:well_specified}
The minimizer for the population risk satisfies the first-order optimality condition:
\begin{equation}
\label{eq:well_specified}
D_{\theta}L_{\cD}(\theta^{\star},g_0)[\theta-\theta^{\star}]\geq 0 \quad{}\forall{}\theta\in\mathrm{star}(\widehat{\Theta},\theta^{\star}).
\end{equation}
\end{assumption}
\begin{remark}
The first-order condition is typically satisfied for models that are \emph{well-specified}, meaning that there is some variable in $z$ that identifies the target parameter\xspace $\theta_0$. More generally, it suffices to ``almost'' satisfy the first-order condition, i.e. to replace \cref{eq:well_specified} by the condition
\begin{equation}
D_{\theta}L_{\cD}(\theta^{\star},g_0)[\theta-\theta^{\star}]
\geq{} - o_n\prn*{\mathrm{Rate}_{\cD}(\Theta, n, \delta;\,{}\widehat{\theta},\widehat{g})}.
\end{equation}
The first-order condition is also satisfied whenever $\widehat{\Theta}$ is star-shaped around $\theta^{\star}$, i.e. $\mathrm{star}(\widehat{\Theta},\theta^{\star})\subseteq\widehat{\Theta}$.
\end{remark}
\begin{assumption}[Higher-Order Smoothness]
\label{ass:smooth_loss}
There exist constants $\beta_1$ and $\beta_2$ such that the following derivative bounds hold:
\iftoggle{journal}{\begin{enumerate}}{}
\iftoggle{journal}{}{\begin{enumerate}[label=\textnormal{\textbf{\alph*)}}]}
\item \emph{Second-order smoothness with respect to target.} For all $\theta\in\widehat{\Theta}$ and all $\bar{\theta}\in\mathrm{star}(\widehat{\Theta},\theta^{\star})$:
\begin{equation}
\label{eq:smooth1}
D^{2}_{\theta}L_{\cD}(\bar{\theta},g_0)[\theta-\theta^{\star},\theta-\theta^{\star}] \leq{}\beta_1\cdot \nrm*{\theta-\theta^{\star}}_{\Theta}^{2}.
\end{equation}
\item \emph{Higher-order smoothness.} \revoneedit{There exists $r\in[0,1)$ such
that for all $\theta\in\mathrm{star}(\widehat{\Theta},\theta^{\star}),\;g\in\cG$, and $\bar{g}\in\mathrm{star}(\cG,g_0)$:
\begin{align}
\label{eq:smooth2}
\abs*{D^{2}_{g}D_{\theta}L_{\cD}(\theta^{\star},\bar{g})[\theta-\theta^{\star},g-g_0,g-g_0]}
\leq{}~& \beta_2\cdot \nrm*{\theta-\theta^{\star}}^{1-r}_{\Theta} \cdot \nrm*{g-g_0}_{\cG}^2.
\end{align}
}
\end{enumerate}
\end{assumption}
\begin{assumption}[Strong Convexity]
\label{ass:strong_convex_loss}
The population risk is strongly convex with respect to the target parameter: \revoneedit{There exist constants $\lambda,\kappa>0$ such that for all $\theta\in\widehat{\Theta}$ and $g\in\cG$,
\begin{equation}
\label{eq:strongly_convex}
D^{2}_{\theta}L_{\cD}(\bar{\theta}, g)[\theta-\theta^{\star},\theta-\theta^{\star}]\geq{}\lambda\nrm*{\theta-\theta^{\star}}_{\Theta}^{2} - \kappa \nrm*{g - g_0}_{\cG}^{\frac{4}{1+r}} \quad{}\forall{}\bar{\theta}\in\mathrm{star}(\widehat{\Theta},\theta^{\star}),
\end{equation}
where $r\in[0,1)$ is as in \cref{ass:smooth_loss}.}
\end{assumption}
\cref{ass:smooth_loss} and \cref{ass:strong_convex_loss} are easily
satisfied whenever the loss is obtained by applying a square loss or
another smooth, strongly convex loss pointwise to the prediction of the
target class; concrete examples are given in
\cref{sec:sufficient}. \revoneedit{For most of our results, we apply
these assumptions with $r=0$, but the case $r>0$ will prove useful
for certain settings in which strong $L_{\infty}$-type estimation guarantees for the
target parameter are available (cf. \cref{ex:r_learner}). In general,
\cref{ass:orthogonal,ass:well_specified,ass:strong_convex_loss,ass:smooth_loss}
do not imply that $\theta^{\star}$ is uniquely identified unless
$\nrm{\cdot}_{\Theta}$ is a norm. However, if the assumptions are
satisfied by two parameters $\theta^{\star}\neq\tilde{\theta}^{\star}$, we
must have $\nrm{\theta^{\star}-\tilde{\theta}^{\star}}_{\Theta}=0$,
meaning convergence in the sense that $\nrm{\widehat{\theta}-\theta^{\star}}_{\Theta}\to{}0$ is equivalent for both representatives.}\iftoggle{journal}{\looseness=-1}{}
We now state our main theorem concerning fast rates.
\begin{theorem}
\label{thm:generic_strongly_convex}
Suppose there exists $\theta^{\star}\in\operatorname*{arg\,min}_{\theta\in\Theta}L_{\cD}(\theta,g_0)$ such that \cref{ass:orthogonal,ass:well_specified,ass:strong_convex_loss,ass:smooth_loss}, are satisfied. Then the sample splitting meta-algorithm (\cref{alg:sample_splitting}) produces a parameter\xspace $\widehat{\theta}$ such that with probability at least $1-\delta$,
\begin{equation}
\label{eq:generic_strongly_convex_l2}
\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2} \leq{} C_1\cdot\mathrm{Rate}_{\cD}(\Theta,S_2,\delta/2;\,{}\widehat{\theta},\widehat{g}) +
C_2
\cdot{}\prn*{
\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)
}^{\frac{4}{1+r}},
\end{equation}
where $C_1\leq\frac{4}{\lambda}$ and $C_2\leq2\prn[\Big]{\prn[\big]{\frac{\beta_2}{\lambda}}^{\frac{2}{1+r}} + \frac{\kappa}{\lambda}}$. In addition,
\begin{equation}
\label{eq:generic_strongly_convex_excess_risk}
\begin{aligned}
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta^{\star}, g_0)\leq{} \frac{\beta_1\, C_1}{2}\cdot\mathrm{Rate}_{\cD}(\Theta,S_2,\delta/2;\,{}\widehat{\theta},\widehat{g}) +
\frac{\beta_1\, C_2}{2}
\cdot\prn*{
\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)
}^{\frac{4}{1+r}}.
\end{aligned}
\end{equation}
\end{theorem}
\revoneedit{
The majority of the results in this paper concern the special case
in which $r=0$. In this case, since
$\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)\propto\nrm{\widehat{g}-g_0}_{\cG}$,
\cref{thm:generic_strongly_convex} shows that for
\cref{alg:sample_splitting}, the impact of the unknown nuisance
parameter on the prediction is of second-order,
i.e.
\[
\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2} \text{ and } L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta^{\star}, g_0) \lesssim{}
\mathrm{Rate}_{\cD}(\Theta,S_2,\delta/2;\,{}\widehat{\theta},\widehat{g})
+ \nrm[\big]{\widehat{g}-g_0}_{\cG}^{4}
\]
}This implies that if the optimal rate without nuisance
parameters is of order $O(n^{-1})$, it suffices to take
$\nrm{\widehat{g}-g_0}_{\cG}^{2}=o(n^{-1/2})$ to achieve
the oracle rate.
\begin{revone}
\begin{proof}[Proof of \cref{thm:generic_strongly_convex}]
We prove \cref{thm:generic_strongly_convex} by performing a Taylor
expansion to relate the excess risk at $\widehat{g}$ to the excess risk at
$g_0$, employing orthogonality and self-bounding arguments to control
cross terms. We abbreviate
$R_{\Theta}\vcentcolon=\mathrm{Rate}_{\cD}(\Theta,S_2,\delta/2;\,{}\widehat{\theta},\widehat{g})$ and
$R_{\cG}\vcentcolon=\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)$ to simplify notation.
By a second-order Taylor expansion on the risk at $\widehat{g}$, there exists $\bar{\theta}\in\mathrm{star}(\widehat{\Theta}, \theta^{\star})$ such that
\[
\frac{1}{2}\cdot{}D^{2}_{\theta}L_{\cD}(\bar{\theta},\widehat{g})[\widehat{\theta}-\theta^{\star},\widehat{\theta}-\theta^{\star}]
= L_{\cD}(\widehat{\theta},\widehat{g}) - L_{\cD}(\theta^{\star},\widehat{g}) - D_{\theta}L_{\cD}(\theta^{\star},\widehat{g})[\widehat{\theta}-\theta^{\star}].
\]
Next, using the strong convexity assumption (\cref{ass:strong_convex_loss}), we have
\begin{align*}
D^{2}_{\theta}L_{\cD}(\bar{\theta},\widehat{g})[\widehat{\theta}-\theta^{\star},\widehat{\theta}-\theta^{\star}]
\geq~& \lambda \cdot{}\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2} - \kappa \cdot \nrm[\big]{\widehat{g} - g_0}_{\cG}^\frac{4}{1+r} = \lambda \cdot{}\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2} - \kappa\cdot{}R_{\cG}^\frac{4}{1+r}.
\end{align*}
Combining these statements, we conclude that
\[
\frac{\lambda}{2}\cdot{}\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2} \leq L_{\cD}(\widehat{\theta},\widehat{g}) - L_{\cD}(\theta^{\star},\widehat{g}) + \frac{\kappa}{2}\cdot R_{\cG}^{\frac{4}{1+r}} - D_{\theta}L_{\cD}(\theta^{\star},\widehat{g})[\widehat{\theta}-\theta^{\star}].
\]
Using the assumed rate for $\widehat{\theta}$ (\cref{def:algorithms}), this implies the inequality
\begin{equation}
\label{eq:generic_strongly_convex_lower}
\frac{\lambda}{2}\cdot{}\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2}
\leq{} R_{\Theta} + \frac{\kappa}{2}\cdot R_{\cG}^{\frac{4}{1+r}} - D_{\theta}L_{\cD}(\theta^{\star},\widehat{g})[\widehat{\theta}-\theta^{\star}].
\end{equation}
We now apply a second-order Taylor expansion (using the assumed derivative continuity from \cref{ass:smooth_loss}), which implies that there exists $\bar{g}\in\mathrm{star}(\cG,g_0)$ such that
\begin{align*}
- D_{\theta}L_{\cD}(\theta^{\star},\widehat{g})[\widehat{\theta}-\theta^{\star}]
&=
- D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}] - D_{g}D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star},\widehat{g}-g_0]
\iftoggle{journal}{\\&~~~~}{}-
\frac{1}{2}\cdot{}D^{2}_{g}D_{\theta}L_{\cD}(\theta^{\star},\bar{g})[\widehat{\theta}-\theta^{\star},\widehat{g}-g_0,\widehat{g}-g_0].
\end{align*}
Using orthogonality of the loss (\cref{ass:orthogonal}), this is equal to
\begin{align*}
- D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]
- \frac{1}{2}\cdot{}D^{2}_{g}D_{\theta}L_{\cD}(\theta^{\star},\bar{g})[\widehat{\theta}-\theta^{\star},\widehat{g}-g_0,\widehat{g}-g_0].
\end{align*}
We use the second order smoothness assumed in \cref{ass:smooth_loss}
to upper bound by
\begin{align*}
\leq{}
- D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]
+ \frac{\beta_2}{2}\cdot{}\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}\cdot\nrm[\big]{\widehat{g}-g_0}_{\cG}^{2}.
\end{align*}
Invoking Young's inequality and using that $r\in[0,1)$, we have that
for any constant $\eta>0$, this is at most
\begin{align*}
&\leq{}
D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]
+ \frac{\beta_2 \eta}{4}\cdot{}\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2}
+ \frac{\beta_2}{2\eta^{\frac{1-r}{1+r}}}\cdot{}\nrm[\big]{\widehat{g}-g_0}_{\cG}^{\frac{4}{1+r}}.
\end{align*}
Lastly, we use the assumed rate for $\widehat{g}$
(\cref{def:algorithms}) to bound by
\begin{align*}
\leq{}
- D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]
+ \frac{\beta_2
\eta}{4}\cdot{}\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2} + \frac{\beta_2}{2\eta^{\frac{1-r}{1+r}}}\cdot{}
R_{\cG}^{\frac{4}{1+r}}.
\end{align*}
Choosing $\eta = \frac{\lambda}{\beta_2}$, combining this string of inequalities with \cref{eq:generic_strongly_convex_lower}, and rearranging, we have:
\begin{equation}
\label{eq:strongly_convex_quadratic}
\begin{aligned}
\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2}
&\leq \frac{4}{\lambda}\prn*{- D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]
+ R_{\Theta}} +
2\prn[\bigg]{\prn[\bigg]{\frac{\beta_2}{\lambda}}^{\frac{2}{1+r}} + \frac{\kappa}{\lambda}}\cdot R_{\cG}^{\frac{4}{1+r}}.
\end{aligned}
\end{equation}
\cref{ass:well_specified} implies that $D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]\geq{}0$, which establishes the inequality \cref{eq:generic_strongly_convex_l2}.
To derive the inequality \cref{eq:generic_strongly_convex_excess_risk}, we use another Taylor expansion, which implies that there exists $\bar{\theta}\in\mathrm{star}(\widehat{\Theta}, \theta^{\star})$ such that
\begin{align}
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta^{\star},g_0)
&= D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]
+ \frac{1}{2}\cdot{}D^{2}_{\theta}L_{\cD}(\bar{\theta},g_0)[\widehat{\theta}-\theta^{\star},\widehat{\theta}-\theta^{\star}].\notag
\intertext{Using the smoothness bound from \cref{ass:smooth_loss},
we upper bound
this by}
&\leq{} D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]
+ \frac{\beta_1}{2}\cdot\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^{2}.\label{eq:generic_strongly_convex_risk}
\end{align}
We combine \cref{eq:strongly_convex_quadratic} with \cref{eq:generic_strongly_convex_risk} to conclude that $L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta^{\star},g_0)$ is bounded by
\begin{align*}
\frac{2\beta_1}{\lambda} \cdot R_{\Theta} +
\beta_1\prn[\bigg]{\prn*{\frac{\beta_2}{\lambda}}^{\frac{2}{1+r}} + \frac{\kappa}{\lambda}}\cdot R_{\cG}^{\frac{4}{1+r}}
- \prn[\bigg]{\frac{2\beta_1}{\lambda}-1}\cdot{}D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}].
\end{align*}
The result follows by again using that $D_{\theta}L_{\cD}(\theta^{\star},g_0)[\widehat{\theta}-\theta^{\star}]\geq{}0$, along with the fact that $\beta_1/\lambda\geq{}1$ without loss of generality.
\end{proof}
\end{revone}
There is one issue not addressed by \cref{thm:generic_strongly_convex}: If the nuisance parameter $g_0$ were known, the rate for the target parameters would be $\mathrm{Rate}_{\cD}(\Theta,\ldots;\,{}\widehat{\theta},g_0)$, but the bound in \cref{eq:generic_strongly_convex_excess_risk} scales instead with $\mathrm{Rate}_{\cD}(\Theta,\ldots;\,{}\widehat{\theta},\widehat{g})$. This is addressed in \cref{sec:erm,sec:oracle}, where---building on \cref{thm:generic_strongly_convex}---we show that for many standard algorithms, the cost to relate these quantities grows as $\prn*{\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)}^{4}$, and can be absorbed into the second term in \cref{eq:generic_strongly_convex_l2} or \cref{eq:generic_strongly_convex_excess_risk}.\iftoggle{journal}{\looseness=-1}{}
\subsection{Beyond Strong Convexity: Slow Rates}
\label{ssec:orthogonal_slow_rate}
The strong convexity assumption used by
\cref{thm:generic_strongly_convex} requires curvature only in the
prediction space, not the parameter space. This is considerably weaker
than what is assumed in prior works on double machine learning (e.g.,
\cite{chernozhukov2018plugin}), and is a major advantage of analyzing
prediction error rather than parameter recovery. Nonetheless, in some
situations even assuming strong convexity on predictions may be
unrealistic. A second advantage of studying prediction is that, while
parameter recovery is not possible in this case, it is still possible
to achieve low prediction error, albeit with slower rates than in the
strongly convex case. We now give guarantees under which these
(slower) oracle rates for prediction error can be obtained in the
presence of nuisance parameters\xspace using
\cref{alg:sample_splitting}. \revoneedit{As in the prequel, we fix a
representative
$\theta^{\star}\in\operatorname*{arg\,min}_{\theta\in\Theta}L_{\cD}(\theta,g_0)$
throughout this subsection.}
The key technical assumption for next result is \emph{universal orthogonality}, which informally states that the loss is not simply orthogonal around $\theta^{\star}$, but rather is orthogonal for all $\theta\in\Theta$.
\begin{assumption}[Universal Orthogonality]
\label{ass:universal_orthogonality}
For all $\bar{\theta}\in\mathrm{star}(\widehat{\Theta},\theta^{\star}) + \mathrm{star}(\widehat{\Theta}-\theta^{\star},0)$,
\[
D_{g}D_{\theta}L_{\cD}(\bar{\theta},g_0)[\theta-\theta^{\star},g-g_0]=0\quad\forall{}g\in\cG,\;\;\revoneedit{\theta\in\widehat{\Theta}}.
\]
\end{assumption}
\revoneedit{Universal orthogonality is a strengthening of \cref{ass:orthogonal}, which requires that the cross derivative at $g_0$ vanishes for all $\bar{\theta}\in\mathrm{star}(\widehat{\Theta},\theta^{\star})$, rather than only at $\theta^{\star}$.} It is satisfied for examples including treatment effect estimation (\cref{sec:treatment_effect}) and policy learning (\cref{sec:policy_learning_body}), and is used implicitly in previous work in these settings \citep{nie2017quasi,athey2017efficient}. Beyond orthogonality, we require a mild smoothness assumption for the nuisance class.\iftoggle{journal}{\looseness=-1}{}
\begin{assumption}
\label{ass:smooth_loss_slow}
The derivatives $D^{2}_{g}L_{\cD}(\theta,g)$ and $D_{\theta}^{2}D_{g}L_{\cD}(\theta,g)$ are continuous.
Furthermore, there exists a constant $\beta$ such that for all $\theta\in\mathrm{star}(\widehat{\Theta},\theta^{\star})$ and $\bar{g}\in\mathrm{star}(\cG,g_0)$,
\begin{equation}
\abs*{D^{2}_{g}L_{\cD}(\theta,\bar{g})[g-g_0,g-g_0]}\leq{}\beta \cdot{}\nrm*{g-g_0}_{\cG}^{2}\quad\forall{}g\in\cG.
\end{equation}
\end{assumption}
Our main theorem for slow rates is as follows.
\begin{theorem}
\label{thm:orthogonal_slow}
Suppose that there is $\theta^{\star}\in\operatorname*{arg\,min}_{\theta\in\Theta}L_{\cD}(\theta,g_0)$ such that \cref{ass:universal_orthogonality} and \cref{ass:smooth_loss_slow} are satisfied. Then with probability at least $1-\delta$, the target parameter\xspace $\widehat{\theta}$ produced by \cref{alg:sample_splitting} enjoys the excess risk bound:
\[
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta^{\star}, g_0)
\leq{} \mathrm{Rate}_{\cD}(\Theta, S_2, \delta/2;\,{}\widehat{\theta},\widehat{g}) + \beta \cdot\prn*{\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)}^{2}.
\]
\end{theorem}
\begin{revone}
For generic Lipschitz losses, the optimal rate for parametric
classes---in the absence of nuisance parameters---scales with
$n^{-1/2}$. Without orthogonality, one expects the dependence
on nuisance estimation error to scale linearly with
$\nrm{\widehat{g}-g_0}_{\cG}$, which would require
$\nrm{\widehat{g}-g_0}_{\cG}^{2}=o(n^{-1})$ to achieve
the oracle rate. \cref{thm:orthogonal_slow} shows that under
orthogonality, the impact of nuisance parameter estimation is of
lower order, and it suffices that
$\nrm{\widehat{g}-g_0}_{\cG}^{2}=o(n^{-1/2})$.
The proof follows similar reasoning to that of
\cref{thm:generic_strongly_convex}; see \cref{app:orthogonal}.
\end{revone}
\subsection{Example: Treatment Effect Estimation}
\label{sec:treatment_effect}
To make matters concrete, we now walk through a detailed example in which we specialize our general framework to the well-studied problem of treatment effect estimation. We show how the setup falls in our framework, explain what statistical assumptions are required to apply our main theorems, and show how to interpret the resulting excess risk bounds.
Following, e.g., \cite{robinson1988root,nie2017quasi}, we receive examples $z=(X,W,Y,T)$ according to the following data generating process:
\begin{equation}
\label{eqn:treatment_control_dgp}
\begin{aligned}
&Y = T\cdot{}\theta_0(X) + f_0(W) + \varepsilon_1,&&\operatorname{\mathbb{E}}\brk*{\varepsilon_1\mid{}X,W,T}=0,\\
&T=e_0(W) + \varepsilon_2,&&\operatorname{\mathbb{E}}\brk*{\varepsilon_2\mid{}X,W}=0,
\end{aligned}
\end{equation}
where $X\in\cX$ and $W\in\cW$ are covariates, $T\in\crl*{0,1}$ is the treatment variable, and $Y\in\bbR$ is the target variable. The true target parameter\xspace is $\theta_0:\cX\to\bbR$, but we do not necessarily assume that $\theta_0\in\Theta$. The functions $e_0:\cW\to\brk*{0,1}$ and $f_{0}:\cW\to\bbR$ are unknown; we define $m_0(x,w)=\operatorname{\mathbb{E}}\brk*{Y\mid{}X=x,W=w}=\theta_0(x)e_0(w) + f_0(w)$ and take $g_0=\crl*{m_0,e_0}$ to be the true nuisance parameter. We set $w=(X,W,T)$ and $x=(X)$.
\begin{revone}
\subsubsection{Residualized Loss (R-Loss)}
Following \cite{robinson1988root,nie2017quasi}, we consider the residualized square loss
\begin{equation}
\label{eq:cate_control_loss}
\ell(\theta,\crl*{m,e};z) = \prn*{(Y-m(X,W) - (T-e(W))\theta(X)}^{2}.
\end{equation}
Let us take a moment to interpret the meaning of excess risk under this loss.
It is simple to verify that if the true nuisance parameters $g_0=\crl*{m_0,e_0}$ are plugged in, then
\[
L_{\cD}(\theta,g_0) - L_{\cD}(\theta_0,g_0) = \operatorname{\mathbb{E}}\prn*{(T-e_{0}(W))\cdot{}(\theta(X)-\theta_{0}(X))}^{2}.
\]
Thus, if a predictor $\theta$ has low risk it, must be good at predicting $\theta_{0}(X)$ whenever there is sufficient variation in the treatment $T$. In addition, If the model is not well-specified ($\theta_0\notin\Theta$) but $\Theta$ is convex, we can still deduce that
\[
L_{\cD}(\theta,g_0) - L_{\cD}(\theta^{\star},g_0) \geq{} \operatorname{\mathbb{E}}\prn*{(T-e_{0}(W))\cdot{}(\theta(X)-\theta^{\star}(X))}^{2},
\]
so in this case low excess risk implies that we predict nearly as well as the best predictor in class (again, assuming sufficient variation in $T$).
\oldparagraph*{Applying the main results: Fast rates}
We now apply \cref{thm:generic_strongly_convex} to derive oracle excess risk bounds for the residualized loss. Let us consider the seminorms $\nrm*{\theta}_{\Theta}^2\vcentcolon=\operatorname{\mathbb{E}}\brk*{(T-e_0(W))^{2}\theta^2(X)}$ and $\nrm*{\cdot}_{\cG}\vcentcolon=\nrm*{\cdot}_{L_4(\ell_2,\cD)}$ and $r=0$. Establishing the basic orthogonality and first-order conditions required to apply \cref{thm:generic_strongly_convex} is a simple exercise (see \cref{app:orthogonal} for a full derivation). To establish the smoothness and strong convexity properties \cref{ass:smooth_loss} and \cref{ass:strong_convex_loss}, we require mild boundedness assumptions, and a lower bound on the coverage parameter
\begin{equation}
\label{eq:rsc_treatment}
\lambda_{\mathsf{re}}\vcentcolon=\inf_{\theta\in\Theta}\crl*{\frac{\operatorname{\mathbb{E}}(T-e_0(W))^{2}\prn*{\theta(X)-\theta^{\star}(X)}^{2}}{\operatorname{\mathbb{E}}\prn*{\theta(X)-\theta^{\star}(X)}^{2}}} > 0.
\end{equation}
In particular, we have the following result.
\end{revone}
\begin{comment}
Establishing the basic orthogonality and first-order conditions required to apply \cref{thm:generic_strongly_convex} and \cref{thm:orthogonal_slow} is a simple exercise (see \cref{app:orthogonal} for a full derivation):
\begin{itemize}
\item
The conditional expectation assumptions in \cref{eqn:treatment_control_dgp} imply that the loss satisfies the first-order condition whenever $\theta_0\in\Theta$.
On the other hand, even if $\theta_0\notin\Theta$, the first-order condition is still satisfied as long as $\Theta$ is convex.
\item
The loss is universally orthogonal, meaning that its partial derivatives vanish not just around $\theta_0$ but around any $\theta:\cX\to\bbR$:
\[
D_{e}D_{\theta}L_{\cD}(\theta,\crl*{m_0,e_0})[\theta'-\theta,e-e_0]=0\quad\forall{}\theta,\theta',e
\]
and
\[
D_{m}D_{\theta}L_{\cD}(\theta,\crl*{m_0,e_0})[\theta'-\theta,m-m_0]=0\quad\forall{}\theta,\theta',m
\]
This means that the orthogonality condition \cref{eq:orthogonal} in \cref{ass:orthogonal} is satisfied for any $\theta^{\star}$, regardless of whether or not $\theta_0\in\Theta$.
\end{itemize}
As a consequence, our general results imply that for any class, it is possible to achieve oracle rates for prediction with this loss in the presence of nuisance parameters, even when the parameter\xspace $\Theta$ is completely misspecified. That is, if $\Theta$ is convex, then by the universal orthogonality property, oracle rates are achievable so long as $\mathrm{Rate}_{\cD}(\cG,n,\delta)=o\prn*{\mathrm{Rate}_{\cD}(\Theta,\cdots)^{1/4}}$, modulo regularity conditions which we verify now. \dfcomment{cut the paragraph above down.}
\end{comment}
\begin{revone}
\begin{proposition}
\label{prop:treatment_example}
Consider the treatment effect estimation setting with the residualized loss and norms $\nrm*{\theta}_{\Theta}^2\vcentcolon=\operatorname{\mathbb{E}}\brk*{(T-e_0(W))^{2}\theta^2(X)}$ and $\nrm*{\cdot}_{\cG}\vcentcolon=\nrm*{\cdot}_{L_4(\ell_2,\cD)}$. Suppose that $\theta_0\in\Theta$ and $\abs{\theta_0(x)}\leq{}1$. Then the assumptions of \cref{thm:generic_strongly_convex} are satisfied with constants $r=0$, $\lambda = \frac{1}{4}$, $\kappa=4\lambda_{\mathsf{re}}^{-1}$, $\beta_1=1$, and $\beta_2= 4\lambda_{\mathsf{re}}^{-1/2}$. As a result, the sample splitting meta-algorithm (\cref{alg:sample_splitting}) with the residualized loss produces a parameter\xspace $\widehat{\theta}$ such that with probability at least $1-\delta$,
\begin{align*}
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta_0, g_0)
\leq{} 8\cdot{}\mathrm{Rate}_{\cD}(\Theta,S_2,\delta/2;\,{}\widehat{\theta},\widehat{g}) +
144\lambda_{\mathsf{re}}^{-1}\cdot{}\prn*{
\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)
}^{4}.
\end{align*}
More generally, whenever $\Theta$ is convex, the same conclusion holds with $\theta_0$ replaced by $\theta^{\star}\in\operatorname*{arg\,min}_{\theta\in\Theta}L_{\cD}(\theta,g_0)$, regardless of whether $\theta_0\in\Theta$.
\end{proposition}
\cref{prop:treatment_example} implies that for any class, oracle rates for excess risk are achievable whenever $\mathrm{Rate}_{\cD}(\cG,n,\delta)=o\prn*{\mathrm{Rate}_{\cD}(\Theta,\cdots)^{1/4}}$. Interestingly, in the case where the target class $\Theta$ is convex, this holds even when the target parameter is arbitrarily misspecified. In addition, the excess risk bound in \cref{prop:treatment_example} has the desirable property that the coverage parameter $\lambda_{\mathsf{re}}$ enters only through the higher-order nuisance error term.
Let us interpret the coverage parameter $\lambda_{\mathsf{re}}$, which acts as a problem-dependent constant whose value reflects the interaction between the treatment policy and the treatment effect. In general, to lower bound $\lambda_{\mathsf{re}}$, it suffices to assume that $\mathrm{Var}(T-e_0(W) \mid X)\geq \eta$ for some $\eta> 0$, with no further assumptions required on the data distribution or target parameter class. This condition is typically referred to as \emph{overlap}, since it requires that the treatment is not deterministic for any realization of the covariates, and implies that $\lambda_{\mathsf{re}}\geq{}\eta$. On the other hand, even if overlap is not satisfied, one can still lower bound the coverage parameter. To do so, we focus on a special case investigated in \cite{chernozhukov2017orthogonal} and \cite{chernozhukov2018plugin}, where $\Theta$ is a class of high-dimensional predictors of the form $\theta(x) = \tri*{w,\phi(x)}$, where $w\in\bbR^{p}$ and $\phi:\cX\to\bbR^{p}$ is a fixed featurization; in general, the dimension $p$ may grow with $n$, with $p\gg{}n$. In this case, note that it suffices that the matrix $\operatorname{\mathbb{E}}\brk*{\mathrm{Var}(T-e_0(W)\mid X)\phi(X)\phi(X)^{\top}}$ satisfies a restricted minimum eigenvalue condition. Hence, a lower bound on $\lambda_{\mathsf{re}}$ generalizes assumptions used in \cite{chernozhukov2017orthogonal,chernozhukov2018plugin}.
\end{revone}
\oldparagraph*{Stronger guarantees for specific target classes}
The results in the prequel apply to arbitrary target classes, but require that the nuisance estimation algorithm is close in the $L_4$ norm (i.e., $\nrm*{\cdot}_{\cG}=\nrm*{\cdot}_{L_4(\ell_2,\cD)}$). For specific target classes (typically, classes with additional structure that facilitates estimation in parameter error), it is possible to provide improved guarantees that scale with weaker $L_2$ estimation error for the nuisance class. To illustrate the flexibility of \cref{thm:generic_strongly_convex} in accommodating such cases, we consider a constrained variant of the \emph{R-learner} of \citet{nie2017quasi} and recover the oracle rates from this work.
\begin{revone}
\begin{example}[Constrained R-Learner]
\label{ex:r_learner}
The R-learner of \cite{nie2017quasi} corresponds to a special case of the treatment effect estimation setup in \cref{eqn:treatment_control_dgp} in which the target parameter belongs to a kernel class, and is estimated by minimizing the orthogonal loss \cref{eq:cate_control_loss} with regularization. Specializing the sample splitting meta-algorithm (\cref{alg:sample_splitting}) to this setting, we obtain a constrained variant of their method. \preprint{\\}In more detail, consider the treatment effect estimation setting with $\nrm*{\theta}_{\Theta}^2\vcentcolon=\operatorname{\mathbb{E}}\brk*{(T-e_0(W))^{2}\theta^2(X)}$ and $\nrm*{\cdot}_{\cG}\vcentcolon=\nrm*{\cdot}_{L_2(\ell_2,\cD)}$. Let $\cH$ be a reproducing kernel Hilbert space (RKHS) with norm $\nrm{\cdot}_{\cH}$ and kernel $\cK$. Assume that $\abs{Y}\leq{}1$ almost surely and that treatments satisfy overlap, and consider the constrained target parameter class
\[
\Theta = \crl*{\theta\in\cH\mid{}\nrm{\theta}_{\cH}\leq{}c, \nrm{\theta}_{L_{\infty}(\cD)}\leq{}1},
\]
where $c\geq{}1$ is a parameter. For the target estimation algorithm, consider the plug-in empirical risk minimizer
\[
\widehat{\theta} = \arg\min_{\theta \in \Theta}\sum_{i=n/2}^n \ell(\theta(x_i), \widehat{g}(w_i); z_i),
\]
where $\widehat{g}$ is the nuisance estimator. Assume that the kernel $\cK$ has eigenvalue decay of the form $\sigma_j\sim j^{-1/p}$ for some parameter $p\in(0,1)$ and that a smoothed version of $\theta_0$ lies in the RKHS for smoothing parameter $\alpha\in (0,1/2)$ (refer to proof in \cref{app:example_proofs} for definitions), and choose $c\propto{}n^{\alpha/(p+(1-2\alpha))}$. If the nuisance estimation algorithm has $\nrm*{\widehat{g}-g_0}_{L_2(\ell_2,\cD)}\leq\mathrm{Rate}_{\cD}(\cG,S_1,\delta)=\widetilde{o}(n^{-1/4})$, then with probability at least $1-\delta$, \cref{alg:sample_splitting} has
\begin{equation}
\label{eq:r_learner}
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta^{\star},g_0)
\leq \widetilde{O}\prn*{n^{-\frac{1-2\alpha}{p+(1-2\alpha)}} + \frac{\log(\delta^{-1})}{n}},
\end{equation}
where $\widetilde{O}(\cdot)$ suppresses dependence on regularity parameters and $\log(n)$ factors. This matches the best known rate for the oracle learner \citep{nie2017quasi}.
\end{example}
This example shows that an $O(n^{-1/4})$ rate in $L_2$-error for the nuisances suffices to achieve the optimal rate in the absence of nuisance parameter. The proof leverages a lemma of \cite{mendelson2010regularization}, which states that for all $\theta\in\cH$,
$\nrm{\theta}_{L_{\infty}(\cD)}\lesssim\nrm{\theta}_{\cH}^{p} \nrm{\theta}_{L_{2}(\cD)}^{1-p}$, where $p$ is the eigenvalue decay parameter. This allows us to establish \cref{ass:smooth_loss} and \cref{ass:strong_convex_loss} with respect to $L_2$-error for the nuisance parameter, at the cost of incurring exponent $r=p$, rather than $r=0$ as in the generic result (\cref{prop:treatment_example}). Moreover, as a consequence of the norm comparison inequality of \cite{mendelson2010regularization}, the $L_2(\cD)$-error bound from our theorem also implies a bound on $L_{\infty}(\cD)$ error.
\end{revone}
\oldparagraph*{Slow rates}
We mention in passing that some distributions may simply not satisfy the coverage condition in \cref{eq:rsc_treatment}. In this case, we can appeal to \cref{thm:orthogonal_slow} (we show in \cref{app:example_proofs} that the residualized loss satisfies the universal orthogonality property), which does not require any lower bounds in the vein of \cref{eq:rsc_treatment}, but leads to slower rates. In general, whether the fast rate (\cref{thm:generic_strongly_convex}) or slow rate (\cref{thm:orthogonal_slow}) will give better results given finite samples will depend on the behavior of the data distribution and target class.
\begin{revone}
\subsubsection{Doubly-Robust Loss (DR-Loss)}
As an alternative to the residualized loss, for the special case of a binary treatment, we can use the doubly-robust approach described in \cref{sec:intro}. Consider the special case of \cref{eq:treatment_control_dgp} in which $X=W$. Recall that that $e_0(X)=\operatorname{\mathbb{E}}\brk*{T\mid{}X}$ is the treatment propensity, and define $f_0(t,x)=\operatorname{\mathbb{E}}\brk*{Y\mid{}T=t,X=x}$. Define
\[
\varphi(f,e;z) \vcentcolon= f(1,X) - f(0,X) - \frac{T-e(X)}{e(X)(1-e(X))}(Y-f(T,X)).\]
We take $g=\crl*{f(1,\cdot),f(0,\cdot), e}$ as the nuisance parameter. Then the doubly robust loss takes the form
\begin{equation}
\label{eq:doubly_robust_treatment_loss}
\ell(\theta,\crl{f(0,\cdot),f(1,\cdot),e};z) = \prn*{\varphi(f,e;z)- \theta(X)}^{2}.
\end{equation}
One can verify that $\operatorname{\mathbb{E}}\brk*{\varphi(f_0,e_0;z)\mid{}X}=\theta_0(X)$. As a result, whenever the true nuisance parameters $g_0=\crl{f_0(0,\cdot),f_0(1,\cdot),e_0}$ are plugged in, the oracle excess risk satisfies
\[
L_{\cD}(\theta,g_0) - L_{\cD}(\theta_0,g_0) = \operatorname{\mathbb{E}}\brk*{\prn*{\theta(X)-\theta_{0}(X)}^{2}},
\]
and hence is equivalent to $L_2$-error.
It is straightforward to verify that the doubly-robust loss satisfies the preconditions of \cref{thm:generic_strongly_convex}, which leads to the following result.
\begin{proposition}
\label{prop:doubly_robust}
Consider the treatment effect estimation setting with the doubly-robust loss and norms $\nrm*{\cdot}_{\Theta}\vcentcolon=\nrm{\cdot}_{L_2(\cD)}$ and $\nrm*{\cdot}_{\cG}\vcentcolon=\nrm*{\cdot}_{L_4(\ell_2,\cD)}$. Suppose that $\theta_0\in\Theta$ and that $\abs{\theta(x)},\nrm*{g(x)}_{\infty}\leq{}1$ for all $\theta\in\Theta,g\in\cG$. In addition, assume that $\abs{Y}\leq{}1$ almost surely, and that $\eta{}\leq{}e(X)\leq{}1-\eta$ for all $g=\crl{f(0,\cdot),f(1,\cdot),e}\in\cG$. Then the assumptions of \cref{thm:generic_strongly_convex} are satisfied with constants $r=0$, $\lambda = \frac{1}{4}$, $\kappa=0$, $\beta_1=1$, and $\beta_2= 24\eta^{-3}$. As a result, the sample splitting meta-algorithm (\cref{alg:sample_splitting}) with the doubly-robust loss produces a parameter\xspace $\widehat{\theta}$ such that with probability at least $1-\delta$,
\begin{align*}
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta_0, g_0)
\leq{} 8\cdot{}\mathrm{Rate}_{\cD}(\Theta,S_2,\delta/2;\,{}\widehat{\theta},\widehat{g}) +
O(\eta^{-6})\cdot{}\prn*{
\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)
}^{4}.
\end{align*}
\end{proposition}
This approach was further developed in the subsequent work of \citet{kennedy2020optimal}, who termed it the \emph{DR-Learner}, and provided improved oracle estimation rates which are doubly-robust with respect to the estimation errors for the propensities and conditional means. A variant of our two-stage algorithm for the doubly robust loss was also explored in the prior work of \cite{oprescu2018orthogonal} for the special case where the target estimation algorithm is a Generalized Random Forest.
\vsedit{We note that the explicit dependence on $\eta$ in the second order term in \cref{prop:doubly_robust} can be avoided if one instead re-defines the inverse propensity term $a_0(T,X)=\frac{T-e_0(X)}{e_0(X)\, (1-e_0(X))}$ as the nuisance function. In this case, the second part of \cref{ass:smooth_loss} is satisfied with respect to the product pre-norm: $\nrm*{g}_{\cG}=\nrm*{(f,a)}=\sqrt{\|f\|_{L_4(\ell_2,\cD)}\, \|a\|_{L_4(\ell_2,\cD)}}$, since we have that:
\begin{align*}
\abs*{D^{2}_{g}D_{\theta}L_{\cD}(\theta^{\star},\bar{g})[\nu_\theta, \nu_g, \nu_g]}
={}~& 4\operatorname{\mathbb{E}}\brk*{\nu_\theta(X)\, \nu_a(T,X)\, \nu_f(T,X) }
\leq{} 4 \nrm*{\nu_\theta}_{L_2(\cD)} \cdot \nrm*{\nu_g}_{\cG}^2
\end{align*}
Applying \cref{thm:generic_strongly_convex} with this definition of nuisance pre-norm yields a doubly robust version of \cref{prop:doubly_robust}, where only products of nuisance estimation rates arise.}
\end{revone}
\begin{comment}
Turning to slow rates, we observe that some distributions may simply not satisfy \cref{eq:rsc_treatment}. In this case, we can appeal to \cref{thm:orthogonal_slow}, as \cref{ass:smooth_loss_slow} is trivially satisfied as long as the classes are bounded, and does not require any lower bounds in the vein of \cref{eq:rsc_treatment}. This gives the following guarantee.
\dfcomment{Check if this gives anything non-trivial. If not get rid of the prop, and cut of the discussion above.}
\begin{revone}
\begin{proposition}
\dfcomment{Formal end-to-end slow rate guarantee.}
\end{proposition}
\end{revone}
While the dependence on first stage estimation error in \cref{thm:orthogonal_slow} is worse than in \cref{thm:generic_strongly_convex}, orthogonality still helps out here when the target class is sufficiently large, cf. \cref{fig:oracle_slow}.
\end{comment}
\begin{comment}
\oldparagraph*{Algorithms}
Per the discussion above, the general guarantees for ERM developed in \cref{sec:erm} can be applied to the treatment effect loss, both to obtain fast rates when sufficient conditions for strong convexity are met, and to obtain slow but variance-dependent rates otherwise. Suppose that the metric entropy of the target class $\Theta$ grows as $\cH_2(\Theta,\varepsilon,n)\propto{}\varepsilon^{-p_{2}}$. Then the machinery of \cref{sec:algsandrates} implies that for all of the possible combinations of conditions above (fast vs. slow rate, well-specified vs. misspecified) ERM suffices to obtain optimal rates, \emph{except} when the model is well-specified and $p_2>2$. In this case ERM is suboptimal \citep{rakhlin2017empirical}, but the Skeleton aggregation variant in \cref{app:rates} is sufficient.
\end{comment}
\begin{comment}
\oldparagraph*{Comparison to prior work on asymptotic normality in semi-parametric models}
Classical results on semiparametric inference for treatment effect estimation \citep{rosenbaum1983central,robins1995semiparametric,hahn1998role,hirano2003efficient,imbens2015causal} consider the case of a parametric class $\Theta$ and provide conditions for consistency and asymptotic normality of the estimated parameters. These results are mostly asymptotic in nature and require a well-specified model, i.e. $\theta_0$ belongs to the parametric class $\Theta$. Moreover, these results require strong convexity of the loss with respect to the parameters of the class, which is essentially an identifiability condition for the parameters. The rates typically depend on the degree of strong convexity in the leading term. Our results provide rates for excess risk and consistency with respect to a data dependent metric that drop both the well-specifiedness and the identifiability condition. Moreover, we do not constrain the algorithm used for fitting the second stage, while the classical results primarily consider least squares or GMM estimation for the second stage.
\oldparagraph*{Comparison to prior work on penalized kernel target classes} \cite{nie2017quasi} drops the well-specified model assumption and considers the case where $\Theta$ is a RKHS with bounded kernel norm and the second stage algorithm is penalized kernel regression. They provide results under conditions on the eigendecay of the kernel. Without making the eigendecay assumption, kernels with bounded RKHS norm are a convex class with metric entropy growth rate $p_2=2$ \citep{zhang2002covering}. Hence, our results from \cref{sec:erm} apply whenever ERM over the class is used. Our proof shows that one can achieve oracle rates for any such kernel class, with only second order influence from the nuisance error.
\oldparagraph*{Comparison to prior work on forest-based estimation} A recent line of work \citep{athey2016generalized, oprescu2018orthogonal,friedberg2018} considers a particular type of nonparametric target class, where $\Theta$ is only assumed to be Lipschitz in $x$. These works aim for sup-norm rates and apply a specific type of local GMM estimation within a random forest. Our results provide $L_2$ prediction error rates as opposed to sup-norm rates. Via \cref{sec:algsandrates}, this allows us to provide statistically optimal rates for \emph{any} nonparametric class satisfying the metric entropy growth condition, not just for Lipschitz functions.\textcolor{red}{footnote}{Lipschitz functions in $d$ dimensions satisfy \cref{ass:stagetwo_entropy} with $p_2=d$.}
\oldparagraph*{Comparison to prior work on neural network estimation} \cite{chen1999improved,farrell2018deep} analyze the estimation of heterogeneous treatment effects when the nuisance estimation is conducted via deep neural network training. They provide fast statistical rates for estimation of smooth non-parametric function classes with neural nets, thereby enabling the use of these modern ML methods as nuisance estimators. In our framework, their results can be used as a black box: One can simply use the rates and algorithms they provide to instantiate the $\mathrm{Rate}_{\cD}(\cG, S, \delta)$ quantity in our main theorems. Beyond nuisance estimation, we can also use their rates in our framework for the case when the \emph{target parameter} is a deep neural network. In this case, our main theorems imply that we can use a larger neural net class for the nuisance parameter than for the target parameter while preserving oracle convergence rates.
In fact, we can also leverage the recent surge of work on the generalization ability of deep networks from the machine learning community \citep{bartlett2017spectrally,golowich2017size}, which provide rates for the excess risk of deep neural networks that are almost independent of the neural network size. These results imply that one can obtain nearly size-independent rates for nuisance parameter estimation whenever the nuisance parameter can be expressed as a network with small (in appropriate norm) weights. Moreover, we can also use a deep neural network for target estimation. In this case, these results combined with our main theorems show that we can allow the norm bound for the nuisance neural net to be larger than that of the target network without affecting the leading term in the final rate.
\end{comment}
\subsection{Example: Policy Learning}
\label{sec:policy_learning_body}
As a second example, we show how to apply our framework to the classical problem of policy learning. Compared to our treatment effect estimation example, losses for this setting do not typically satisfy the strong convexity property, meaning that \cref{thm:orthogonal_slow} is the relevant meta-theorem, and slow rates are to be expected.
In policy learning, we receive examples of the form $Z=(X,T,Y)$, where $Y\in \bbR$ is an incurred loss, $T \in \cT$ is a treatment vector and $X\in \cX$ is a vector of covariates.
The treatment $T$ is chosen based on an unknown, potentially randomized policy which depends on $X$. Specifically, we assume the following data generating process:
\begin{equation}
\label{eq:treatment_control_dgp}
\begin{aligned}
&Y = f_0(T, X) + \varepsilon_1,&&\operatorname{\mathbb{E}}\brk*{\varepsilon_1\mid{}X,T}=0,\\
&T=e_0(X) + \varepsilon_2,&&\operatorname{\mathbb{E}}\brk*{\varepsilon_2\mid{}X}=0.
\end{aligned}
\end{equation}
The learner wishes to optimize over a set of treatment policies $\Theta\subseteq{}(\cX\to\cT)$ (i.e., policies take as input covariates $X$ and return a treatment). Their goal is to produce a policy $\widehat{\theta}$ that achieves small regret with respect to the population risk:
\begin{equation}
\label{eq:policy_risk}
\operatorname{\mathbb{E}}\brk[\big]{f_0(\widehat{\theta}(X), X)} - \min_{\theta \in \Theta} \operatorname{\mathbb{E}}\brk*{f_0(\theta(X), X)}.
\end{equation}
This formulation has been extensively studied in statistics \citep{qian2011performance,zhao2012estimating,zhou2017residual,athey2017efficient,zhou2018offline} and machine learning \citep{beygelzimer2009offset,dudik2011doubly,swaminathan2015counterfactual,kallus2018policy}\iftoggle{journal}{}{; in the latter, it is sometimes referred to as counterfactual risk minimization}.
The learner does not know the so-called counterfactual outcome function $f_0$, so it is treated as a nuisance parameter. Typically, orthogonalization of this nuisance parameter is possible by utilizing the secondary treatment equation in \cref{eq:treatment_control_dgp} and fitting a parameter\xspace for the observational policy $e_0$, which is also treated as a nuisance parameter. We can then write the expected counterfactual reward as
\begin{equation}
f_0(t, X) = \operatorname{\mathbb{E}}\brk*{\ell(t, f_0, e_0;Z) \mid X}
\end{equation}
for some known loss function $\ell$ that utilizes the treatment parameter\xspace $e_0$. Letting $g_0=\crl*{f_0,e_0}$, the learner's goal can be phrased as minimizing the population risk,
\begin{equation}
\label{eq:policy_generic}
\operatorname{\mathbb{E}}\brk*{f_0(\theta(X), X)} = \operatorname{\mathbb{E}}\brk*{\operatorname{\mathbb{E}}\brk*{\ell(\theta(X), f_0, e_0;Z) \mid X}} = \operatorname{\mathbb{E}}\brk*{\ell(\theta(X), f_0, e_0;Z)} =\vcentcolon L_{\cD}(\theta, g_0),
\end{equation}
over $\theta \in \Theta$. This formulation clearly falls into our orthogonal statistical learning framework, where the target parameter is the policy $\theta$ and the counterfactual outcome $f_0$ and observed treatment policy $e_0$ together form the nuisance parameter $g_0\vcentcolon=\crl*{f_0,e_0}$. To facilitate the use of estimation for the nuisance components, one typically assumes access to function classes $\cE$ and $\cF$ with $e_0\in\cE$ and $f_0\in\cF$ (so that $\cG=\cF\times\cE$), and fits the nuisance parameters via regression over these classes.
We make this discussion concrete for the special case of binary treatments $T\in \{0,1\}$, with additional examples in \cref{sec:policy}. To simplify notation, define $p_0(t, x) = \bbP\brk*{T=t \mid X=x}$, so that $p_0(t, x) = e_0(x)$ if $t=1$ and $1-e_0(x)$ if $t=0$. Consider the nuisance parameter $g=\crl*{f(0,\cdot),f(1,\cdot),e}$. Then the loss\iftoggle{journal}{}{ function}
\begin{equation}
\ell(t, g;Z) = f(t, X) + 1\{T=t\} \frac{(Y - f(t, X))}{p(t, X)},
\end{equation}
has the structure in \cref{eq:policy_generic}: it evaluates to the true risk \cref{eq:policy_risk} whenever the true nuisance parameter is plugged in. This formulation leads to the well-known doubly-robust estimator for the counterfactual outcome \citep{cassel1976some,robins1994estimation,robins1995semiparametric,dudik2011doubly}. It is straightforward to verify that the resulting population risk is orthogonal with respect to $g$. We can also obtain an equivalent loss function by subtracting the loss incurred by choosing treatment $0$. Define
\begin{equation}
\label{eq:binary_treatment}
\beta(g;Z)= \prn*{f(1, X) - f(0, X) + T\frac{Y - f(1, X)}{e(X)} - (1-T)\frac{Y - f(0, X)}{1-e(X)}},
\end{equation}
and set $\ell(t, g;Z) = \beta(g;Z)\cdot{}t$. This formulation leads to a linear population risk:
\begin{equation}
L_{\cD}(\theta, g) = \operatorname{\mathbb{E}}\brk*{\beta(g;Z)\cdot \theta(X)}.
\end{equation}
This population risk satisfies universal orthogonality, and \cref{thm:orthogonal_slow} can be applied with $\nrm{\cdot}_{\cG}=\nrm{\cdot}_{L_2(\ell_2,\cD)}$ whenever the nuisance parameters are bounded appropriately. In particular, we have the following corollary of \cref{thm:orthogonal_slow}.
\begin{revone}
\begin{proposition}
\label{prop:policy_learning}
Consider the policy learning setting with binary treatments and norm $\nrm*{\cdot}_{\cG}=\nrm*{\cdot}_{L_2(\ell_2,\cD)}$. Suppose that $\abs{Y}\leq{}1$ almost surely, and that all $g=\crl*{f(0,\cdot),f(1,\cdot),e}\in\cG$ have $\abs{f(t,X)}\leq{}1$ and $e(X)\in\brk{\eta,1-\eta}$ for some $\eta\in(0,1/2]$. Then with probability at least $1-\delta$, the target parameter\xspace $\widehat{\theta}$ produced by \cref{alg:sample_splitting} enjoys the excess risk bound:\iftoggle{journal}{\looseness=-1}{}
\[
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta^{\star}, g_0)
\leq{} \mathrm{Rate}_{\cD}(\Theta, S_2, \delta/2;\,{}\widehat{\theta},\widehat{g}) + O(\eta^{-3}) \cdot
\prn*{\mathrm{Rate}_{\cD}(\cG,S_1,\delta/2)}^{2}.
\]
\end{proposition}
Note that this bound depends on the overlap parameter $\eta$ only through the nuisance error term. We mention in passing that explicit dependence on this parameter can be avoided entirely by treating the inverse propensity term $a_0(T,X)=\frac{T-e_0(X)}{e_0(X)\, (1-e_0(X))}$ as nuisance parameter (see, e.g., \cite{chernozhukov2021automatic}). In this case, note that \cref{ass:smooth_loss_slow} is satisfied with respect to the product pre-norm: $\nrm*{g}_{\cG}=\nrm*{(f,a)}=\sqrt{\|f\|_{L_2(\ell_2,\cD)}\, \|a\|_{L_2(\ell_2,\cD)}}$, since we have that:
\begin{align*}
\abs*{D^{2}_{g}L_{\cD}(\theta,\bar{g})[\nu_g, \nu_g]}
={}~& 4\operatorname{\mathbb{E}}\brk*{\theta(X)\, \nu_a(T,X)\, \nu_f(T,X) }
\leq{} 4 \nrm*{\nu_g}_{\cG}^2
\end{align*}
Applying our \cref{thm:generic_strongly_convex} with this definition of nuisance pre-norm, yields a doubly robust version of \cref{prop:policy_learning}, where only products of nuisance estimation rates arise. Recent follow-up work of \cite{chernozhukov2021automatic} provides a statistical learning approach for estimating such nuisance functions with respect to mean-squared error, which is based on minimizing an empirical analogue of the risk function $\operatorname{\mathbb{E}}\brk*{a(T, X)^2 - 2 (a(1, X) - a(0,X))}$.
\end{revone}
\subsection{Discussion}
\label{sec:orthogonal_discussion}
\begin{revone}
We close by discussing extensions that build on the
results presented in this section, as well as additional connections between our
results and existing techniques in the literature on semiparametric
inference and double machine learning.
\oldparagraph*{Experiments, additional tools, and applications}
\cref{part:experiments} of the appendix contains an empirical evaluation of the
techniques presented in this section, with applications to treatment
effect estimation and policy learning. \cref{part:additional} of the
appendix contains supplementary theoretical results that build on the development of this section,
including user-friendly variants of the main theorems
(\cref{sec:user_friendly}), construction of orthogonal losses
(\cref{sec:orthogonal_loss}), sufficient conditions to apply the main theorems
(\cref{sec:sufficient}), and further applications
(\cref{sec:applications}).
\oldparagraph*{Construction of orthogonal losses}
While orthogonal losses are already known for many problem settings
and statistical models (treatment effect estimation, policy learning,
regression with missing or censored data, and so on), for new
problems one often begins with a loss that is not necessarily
orthogonal. In \cref{sec:orthogonal_loss}, we give a
generic approach to construct orthogonal losses, building on a
technique from \cite{chernozhukov2018plugin}.
\oldparagraph*{One the use of cross-fitting}
\cref{alg:sample_splitting} relies on sample splitting. While this
strategy is quite general and results in rate-optimal estimates, it
can be inefficient, since the target parameter is only estimated using
a subset of the data. A more practical alternative is to employ the
well-known \emph{cross-fitting} approach (e.g., \cite{chernozhukov2016double}), in which we split the data
into $K$ folds, obtain estimators using complementary folds,
and combine the results. Cross-fitting variants of
\cref{alg:sample_splitting} are given in
\cref{app:additional_algorithms} as \cref{alg:cross_fitting,alg:cross_fitting2}.\iftoggle{journal}{\looseness=-1}{}
One can show that under fairly genreal assumptions, the analysis in
this section remains valid when cross-fitting is employed, and we recommend this in
practice. However, compared to the setting considered in
\cite{chernozhukov2016double}, in which cross-fitting provably enjoys improved
efficiency over basic sample splitting, there is no hope of
establishing that cross-fitting improves efficiency at the level of
generality considered in the present work. This is because our framework
permits the use of arbitrary, potentially nonparametric or
high-dimensional estimators
which may be biased due to the use of regularization or
constraints and---for example---may not be asymptotically linear. As a result, even in the absence of nuisance parameters,
there is no guarantee that averaging multiple target estimators obtained
from independent sample splits will lead to improved efficiency.
\oldparagraph*{One the use of influence functions}
A special case of our framework can be phrased in the language of classical
semiparametric inference as follows: If the population risk functional is pathwise differentiable, and one estimates the
target by minimizing an estimator for the risk based on influence functions,
\vsedit{which will typically lead to a Neyman orthogonal loss and}
the resulting target estimator will have
favorable second-order errors dependence on the error of the nuisance
estimator; see \cite{curth2020estimating} for follow-up work which
takes this approach explicitly.
However, Neyman orthogonality goes beyond pathwise
differentiability (for instance, one can construct orthogonal losses assuming only existence of pathwise
derivatives locally at $(\theta^{\star},g_0)$; see \cref{sec:orthogonal_loss}), and
our results apply in settings where influence functions may not
exist. Moreover, one can obtain Neyman orthogonal losses without invoking influence functions, hence
orthogonal statistical learning is a more flexible framework. See \cite{van2003unifiedb,tsiatis2007semiparametric,kosorok2008introduction,kennedy2016semiparametric}
for a review of influence functions and semiparametric theory.
\end{revone}
\section{\iftoggle{revone}{{\color{black}Instantiating the Main Results: Plug-In Empirical Risk Minimization}}{}}
\label{sec:erm}
\revoneedit{The results in \cref{sec:orthogonal} are stated at a high level of generality, and concern generic estimation algorithms for the target and nuisance parameters. In this section we shift our focus to specific algorithms, and instantiate our general tools to provide explicit bounds based on intrinsic properties of the function classes under consideration.} In particular, we develop algorithms and analysis for orthogonal statistical learning with $M$-estimation losses of the form
\begin{equation}
L_{\cD}(\theta, g) = \operatorname{\mathbb{E}}\brk*{\ell(\theta(x), g(w); z)}.
\end{equation}
We analyze one of the most natural and widely used estimation algorithms for the target parameter: \emph{plug-in empirical risk minimization (plug-in ERM)}. Specifically, recalling that $S=S_1\cup{}S_2$, we define the empirical risk via
\begin{align}
L_{S_2}(\theta, g) =~& \frac{1}{n} \sum_{i=1}^n \ell(\theta(x_i), g(w_i); z_i),
\end{align}
where we adopt the convention that $\abs*{S}=2n$ with $S_2=\crl*{z_1,\ldots,z_n}$ to keep notation compact. The plug-in ERM algorithm returns the minimizer plug-in empirical loss obtained by plugging in the first-stage estimate of the nuisance component:
\begin{equation}
\widehat{\theta} = \arg\min_{\theta \in \Theta} L_{S_2}(\theta, \widehat{g}).
\end{equation}
\revoneedit{We provide oracle excess risk bounds for the plug-in ERM algorithm (and variants) in terms of statistical standard complexity measures for the target class $\Theta$. The main results in this section show that the impact of $\widehat{g}$ on the oracle excess risk achieved ERM is of second order, and that classical excess risk bounds carry over up to lower order terms and constant factors. These results are derived by bounding the second-stage $\mathrm{Rate}_{\cD}(\Theta,S_2,\delta;\,{}\widehat{\theta},\widehat{g})$ using (localized) empirical process tools, then appealing to the main theorems (\cref{thm:generic_strongly_convex} and \cref{thm:orthogonal_slow}).}
In the fast rate regime (i.e., for strongly convex losses) we offer a generalization of the local Rademacher complexity analysis of \cite{bartlett2005local} in the presence of an estimated nuisance component and show that the notion of the \emph{critical radius} of the class $\Theta$ still governs rate $\mathrm{Rate}_{\cD}(\Theta,S_2,\delta;\,{}\widehat{\theta},\widehat{g})$. This leads to \iftoggle{journal}{}{several }applications of our theory to specific target classes, including sparse linear models, neural networks and kernels (\cref{sec:specific_classes}).\iftoggle{journal}{\looseness=-1}{}
In the slow rate regime (i.e., for generic Lipschitz losses), we offer a novel moment-penalized variant of the plug-in ERM algorithm that achieves a rate whose leading term is equal to the critical radius, multiplied by the \emph{variance} of the population loss evaluated at the optimal target parameter. This offers an improvement over prior variance-penalized ERM approaches \citep{maurer2009empirical}, whose leading term depends on the metric entropy of the target function class at single scale, and which typically is larger than the critical radius.
\oldparagraph*{Technical preliminaries}
To present our main results, we need to introduce additional tools from empirical process theory and statistical learning. For any real-valued function class $\cG$, define the localized Rademacher complexity:
\begin{equation}
\mathcal{R}_n(\cG,\delta) \vcentcolon= \operatorname{\mathbb{E}}_{\epsilon, z_{1:n}}\brk*{\sup_{g\in \cG: \|g\|_{L_2(\cD)}\leq \delta} \left| \frac{1}{n}\sum_{i=1}^n \epsilon_i\, g(z_i) \right| },
\end{equation}
where $\epsilon_1,\ldots,\epsilon_n$ are independent Rademacher random variables. Let $\cR_n(\cG)$ denote the non-localized Rademacher complexity (that is, $\cR_n(\cG,\infty)$). We also make use of the \emph{metric entropy} of a function class (which is closely related to the Rademacher complexity). \dfedit{We make the mild assumption that $\Theta$ and $\cG$ are separable, so as to ensure that associated empirical processes are measurable (cf. \citet[pp 314-315]{boucheron2013concentration}).}
\begin{definition}[Metric Entropy]
\label{def:metric_entropy}
For any real-valued function class $\cG$ and sample $z_{1:n}$, the empirical metric entropy $\cH_p(\cG, \varepsilon, z_{1:n})$ is the logarithm of the size of the smallest function class $\cG'$, such that for any $g\in \cG$ there exists $g'\in \cG'$, with $\|g - g'\|_{L_p(z_{1:n})}\leq \varepsilon$. Moreover $\cH_p(\cG, \varepsilon, n)$ will denote the maximal empirical entropy over all possible sample sets $z_1,\ldots,z_n$.
\end{definition}
Finally, for a vector-valued function class $\cF$, let $\cF|_t = \{ f_t: (f_1, \ldots, f_t, \ldots, f_d) \in \cF\}$ denote the projection of the class onto the $t$-th coordinate.
\subsection{Fast Rates for Plug-In Empirical Risk Minimization}
Our first contribution is an extension of the foundational results of \cite{bartlett2005local,koltchinskii2000rademacher}---which bound the excess risk for empirical risk minimization in terms of local Rademacher complexities---to incorporate misspecification due to nuisance parameter estimation error. A crucial parameter in this approach is the \emph{critical radius} $\delta_n$ of a function class $\cG$, defined as the smallest solution to the inequality
\begin{equation}
\label{eq:fixed_point0}
\mathcal{R}_n(\cG,\delta_n) \leq \delta_n^2.
\end{equation}
Classical work shows that in the absence of a nuisance component, if a loss $\ell(\theta(z);z)$ is Lipschitz in its first argument and satisfies standard assumptions required for fast rates (strong convexity in the first argument), then empirical risk minimization achieves an excess risk bound of order $\delta_n^2$. For the case of parametric classes, $\delta_n=\widetilde{O}(n^{-1/2})$, leading to the fast $\widetilde{O}(n^{-1})$ rates for strongly convex losses. For more general classes (cf. \cite{wainwright2019}) the critical radius is---up to constant factors---equal to the solution to an inequality on the metric entropy of the function class (cf. \cref{app:specific}):
\begin{equation}
\int_{\frac{\delta_n^{2}}{8}}^{\delta_n} \sqrt{\frac{\cH_2(\cG(\delta_n,z_{1:n}),\varepsilon,z_{1:n})}{n}} d\varepsilon \leq{} \frac{\delta_n^{2}}{20},
\end{equation}
where $\cG(\delta,z_{1:n}) \vcentcolon= \crl{g\in\cG: \nrm*{g}_{L_2(z_{1:n})}\leq{}\delta}$; see \cref{sec:specific_classes} for concrete examples.
Our first theorem in this section extends this result in the presence of a nuisance component and bounds the excess risk of the plug-in ERM algorithm by the critical radius of the target function class $\Theta$ (more precisely, the worst-case critical radius for each coordinate of the target class, since we deal with vector-valued function classes).
\begin{theorem}[Fast Rates for Plug-In ERM]\label{thm:fast_erm}
Consider a function class $\Theta:\cX \rightarrow \bbR^{K_2}$ with $R\vcentcolon={}\sup_{\theta\in \Theta} \|\theta\|_{L_{\infty}(\ell_2,\cD)}\vee{}1$. Let $\delta_n^2 = \Omega\left(\frac{R^{2}K_2\log(\log(n))}{n}\right)$ be a solution to the equation:\iftoggle{journal}{\looseness=-1}{}
\begin{equation}\label{eqn:critical_radius}
\mathcal{R}_n(\ensuremath{\mathrm{star}}(\Theta|_{t} - \theta_t^\star),\delta) \leq \frac{\delta^2}{R},\quad \forall t\in \{1,\ldots, d\},
\end{equation}
where $\theta^{\star}_t$ is the projection of $\theta^{\star}$ onto coordinate $t$. Suppose that $\ell(\cdot, \widehat{g}(w);z)$ is $L$-Lipschitz with respect to the $\ell_2$ norm and that the population risk $L_{\cD}$ satisfies \cref{ass:orthogonal,ass:well_specified,ass:strong_convex_loss,ass:smooth_loss} with $\nrm*{\cdot}_{\Theta}=\|\cdot\|_{L_2(\ell_2,\cD)}$ and $\nrm*{\cdot}_{\cG}$ arbitrary. \begin{revone}Define $B_1\vcentcolon= \frac{L^{2}K_2^2}{\lambda^2}$ and $B_2\vcentcolon= \prn[\big]{\frac{\beta_2}{\lambda}}^{\frac{2}{1+r}}
+ \frac{\kappa}{\lambda}$, and let $\widehat{\theta}$ be the outcome of the plug-in ERM algorithm. Then, with probability at least $1-\delta$,
\begin{align}
\nrm[\big]{\widehat{\theta}-\theta^{\star}}_{\Theta}^2 \leq
O\prn*{
B_1\cdot{}\prn*{\frac{\delta_n^{2}}{R^2} + \frac{\log(\delta^{-1})}{n}} + B_2\cdot{}\nrm*{\widehat{g}-g_0}_{\cG}^{\frac{4}{1+r}}
},
\end{align}
and
\begin{align}
L_{\cD}(\widehat{\theta}, g_0) - L_{\cD}(\theta^{\star}, g_0)=
O\prn*{
\beta_1B_1\cdot{}\prn*{\frac{\delta_n^{2}}{R^2} + \frac{\log(\delta^{-1})}{n}} + \beta_1B_2\cdot{}\nrm*{\widehat{g}-g_0}_{\cG}^{\frac{4}{1+r}}
}.
\end{align}
\end{revone}
\end{theorem}
\iftoggle{journal}{\vspace{-15pt}}{}
\revoneedit{Critically, when $r=0$, the dependence on the nuisance estimation error scales as $\|\widehat{g} - g_0\|_{\cG}^4$ due to orthogonality, meaning that we can use a complex function class for nuisance estimation without spoiling the rate for the target class. This result is proven in two steps. First, we show that one can take $\mathrm{Rate}_{\cD}(\Theta,n,\delta;\widehat{\theta},\widehat{g})\lesssim{}\delta_n\cdot{}\nrm{\widehat{\theta}-\theta^{\star}}_{\Theta}+\delta_n^2$; this result uses standard empirical process theory tools, and does not leverage orthogonality. Then, we invoke orthogonality through \cref{thm:generic_strongly_convex} to derive the final guarantee. See \cref{app:constrained} for details.
}
\begin{comment}
In \cref{app:erm_smooth}, we show (\cref{lem:improved_fast_erm}) that when the loss $\ell$ is smooth with respect to the first argument, the lower bound on $\delta_n$ required by \cref{thm:fast_erm} can be dropped.
\end{comment}
\subsection{Slow Rates and Variance Penalization}
\label{sec:variance_penalized}
We now turn to the slow rate regime from \cref{ssec:orthogonal_slow_rate}, where the loss is not necessarily strongly convex in the prediction. We prove upper bounds on the generalization error of a variance penalized version of the plug-in ERM algorithm. Our main result gives a slow rate that scales with the variance of the loss rather than the range, and is robust to nuisance estimation error. The basic algorithm we analyze first estimates the nuisance parameter, then estimates the optimal loss value $\mu^{\star}\vcentcolon={}\inf_{\theta\in\Theta}L_{\cD}(\theta,g_0)$ using auxiliary samples, and finally performs plug-in empirical risk minimization with an empirical variance penalty which is centered using the estimate for $\mu^{\star}$. \revoneedit{See \cref{alg:variance_penalization} in \cref{app:additional_algorithms} for a full description.} To simplify notation, we assume that $\abs*{S}=3n$ and is partitioned equal splits $S=S_1\cup{}S_2\cup{}S_3$. Define the variance of the loss at $(\theta^{\star},g_0)$ via
\[
V^{\star} = \mathrm{Var}(\ell(\theta^{\star}(\cdot),g_0(\cdot);\cdot)).
\]
\begin{theorem}[Plug-In ERM with Centered Second Moment Penalization]
\label{thm:variance_penalized}
Consider the centered second moment-penalized plugin empirical risk minimizer in \cref{alg:variance_penalization}:
\begin{equation}
\widehat{\theta} = \arg\min_{\theta\in \Theta} \crl*{L_{S_2}(\theta, \widehat{g}) + 36\delta_nR^{-1}\|\ell(\theta(\cdot),\widehat{g}(\cdot);\cdot)-\widehat{\mu}\|_{L_2(S_2)}},
\end{equation}
where $\widehat{g}$ is the output of $\mathrm{Alg}(\cG,S_1)$ and $\widehat{\mu} = \inf_{\theta\in \Theta} L_{S_3}(\theta, \widehat{g})$. Consider the function class $\cF = \{\ell(\theta(\cdot), \widehat{g}(\cdot); \cdot): \theta \in \Theta\}$, and let $R\vcentcolon=\sup_{f\in \cF}\|f\|_{L_{\infty}(\cD)}\vee{}1$ and $f^{\star}\vcentcolon=\ell(\theta^{\star}(\cdot), \widehat{g}(\cdot); \cdot)$. Let $\delta_n^2 \geq 0$ be any solution to the inequality
\begin{equation}
\label{eq:variance_critical}
\mathcal{R}_n(\ensuremath{\mathrm{star}}(\cF - f^\star),\delta) \leq \frac{\delta^2}{R},
\end{equation}
\begin{revone}
Suppose that \cref{ass:universal_orthogonality} holds, $\ell(\theta(x),\cdot;z)$ is $L$-Lipschitz, and \cref{ass:smooth_loss_slow} holds with parameter $\beta$ and $\nrm*{\cdot}_{\cG}\vcentcolon=\nrm*{\cdot}_{L_2(\ell_2,\cD)}$. Let $C\vcentcolon= (L^2+\beta{}R)$. Then with probability at least $1-\delta$,\iftoggle{journal}{\looseness=-1}{}
\begin{align*}
&L_{\cD}(\widehat{\theta}, g_0) - L_{\cD}(\theta^{\star}, g_0) \\&= O\prn[\bigg]{ \sqrt{V^{\star}}\prn[\bi
gg]{\frac{\delta_n}{R} + \sqrt{\frac{\log(\delta^{-1})}{n}}} + \frac{1}{R}\prn*{\delta_n^{2} + \cR_n^{2}(\ell\circ\Theta) + C\cdot{}\nrm*{\widehat{g}-g_0}_{\cG}^{2}} + R\frac{\log(\delta^{-1})}{n}
}.
\end{align*}
\end{revone}
\end{theorem}
\iftoggle{journal}{\vspace{-15pt}}{}
\revoneedit{As with the previous result, \cref{thm:variance_penalized} is proven by first upper bounding $\mathrm{Rate}_{\cD}(\Theta,n,\delta;\widehat{\theta},\widehat{g})$ using empirical process tools, then invoking orthogonality through one of the main theorems (in this case, \cref{thm:orthogonal_slow}). The only complication is that the result requires the additional step of relating $\mathrm{Rate}_{\cD}(\Theta,\cdots,\widehat{g})$ to the function $\mathrm{Rate}_{\cD}(\Theta,\cdots,g_0)$, which entails bounding the variance of the loss at $\widehat{g}$ in terms of the variance of the loss at $g_0$ and nuisance estimation error.\looseness=-1
}
Our approach offers an improvement over the rates for empirical variance penalization in \cite{maurer2009empirical}, which provides a generalization error bound whose leading term is of the form: $
\sqrt{\frac{\mathrm{Var}_n(\ell(\theta^{\star}(\cdot), \widehat{g}(\cdot),\cdot)) \cH_{\infty}(\ell\circ\Theta, n^{-1}, z_{1:n})}{n}}$. The drawback of such a bound is that it evaluates the metric entropy at a fixed approximation level of $1/n$, which can be suboptimal compared to the critical radius.
\revoneedit{In \cref{app:vc}, we show that for classes $\Theta$ with bounded VC dimension, this guarantee can be further improved as a consequence of our general machinery\iftoggle{journal}{}{, and give a bound which scales with the so-called \emph{Alexander capacity function}}.}
\begin{revone}
\oldparagraph*{Discussion}
Due to space constraints, applications to specific target classes (sparse linear models, neural networks, kernel classes) are deferred to \cref{sec:specific_classes}.
\end{revone}
\section{\iftoggle{revone}{{\color{black}Instantiating the Main Results: Sufficient
Conditions for Oracle Rates}}{}}
\label{sec:oracle}
\begin{revone}
The previous section developed guarantees for orthogonal statistical
learning with a specific algorithm, plug-in empirical risk
minimization. While empirical risk minimization is a
workhorse of statistical learning, in general it does not attain
minimax excess risk for rich function classes, even in the absence of
nuisance parameters. In this section we build on the development so
far and, by appealing to \emph{aggregation} techniques, provide
algorithms that always attain minimax excess risk up to second-order
dependence on nuisance parameters.
Our main results provide \emph{sufficient
conditions} under which oracle rates are achieved which explicitly
depend on intrinsic properties of both the target and nuisance parameter classes. In
particular, we give sufficient conditions based on the relationship between the \emph{metric
entropy} for the nuisance and target classes.\iftoggle{journal}{\looseness=-1}{}
For any real-valued
function class $\cF$, we say that the \emph{complexity} of
$\cF$ is $p$ if for all $\varepsilon>0$,
\begin{equation}
\textstyle{\cH_{2}(\cF,\varepsilon,n) = O\left(\max\{ \varepsilon^{-p}, \log(1/\varepsilon)\}\right)},
\end{equation}
where we recall that $\cH_2$ is the metric entropy defined in
\cref{def:metric_entropy}. When $p=0$, this corresponds to the case of parametric
functions (e.g., linear models and VC-subgraph classes), while
for $p>0$, we recover nonparametric function classes, such as
Lipschitz/smooth functions or kernel spaces. We let $p_1$ and $p_2$
denote the maximum complexity of any output coordinate projection
for the nuisance and target class, respectively. We provide
sufficient conditions on the pair $(p_1,p_2)$ under which the sample splitting
meta-algorithm (\cref{alg:sample_splitting})---with an appropriate
choice for the target and nuisance estimator---can achieve oracle rates.
\end{revone}
\label{sec:algsandrates}
\label{sec:square_oracle}
We focus on\iftoggle{journal}{}{ the important special case of} square losses of the form
\begin{equation}
\ell(\theta(x),g(w); z) = \bigl(
\tri{\Lambda(g(w), v), \theta(x)}- \Gamma(g(w),z)\bigr)^{2}, \quad\quadL_{\cD}(\theta,g)=\operatorname{\mathbb{E}}\brk{\ell(\theta,g;z)},
\label{eq:square_oracle}
\end{equation}
where $\Lambda$ and $\Gamma$ are known functions, and where we recall from \cref{sec:setup} that $x$, $w$ are subsets of the data $z$, and $v\subseteq{}z$ is an arbitrary auxiliary subset of the data. We assume that the nuisance parameters\xspace are defined in terms of regression problems, i.e., that $g_0(w)=\operatorname{\mathbb{E}}\brk*{u\mid{}w}$ for some known random vector $u\subseteq{}z$. This assumption is standard in semiparametric literature \citep{bickel1993efficient,kosorok2008introduction,van2011targeted}, and implies that each coordinate $t$ of $g_0$ may be expressed as the minimizer of a squared loss: $g_{0,t}=\operatorname*{arg\,min}_{g_t\in\cG|_t}\operatorname{\mathbb{E}}\brk[\big]{\prn*{g_{t}(w)-u_t}^2}$. In this setting, a sufficient condition for orthogonality is that
\begin{equation}\label{eqn:oracle_orthogonality}
\operatorname{\mathbb{E}}\brk*{\nabla_{\gamma}\nabla_{\zeta} \ell(\theta^{\star}(x), g_0(w), z) \mid w} = 0,
\end{equation}
where $\nabla_{\zeta}$ and $\nabla_{\gamma}$ denote the gradient of $\ell$ with respect to the first and second argument\iftoggle{journal}{}{, respectively}.
In the absence of nuisance parameters, minimax optimal rates for excess risk in square loss regression have been characterized for the \emph{well-specified} setting in which
\begin{equation}
\label{eq:oracle_well_specified}
\operatorname{\mathbb{E}}\brk*{\Gamma(g_0(w),z)\mid{}w,v} = \tri{\Lambda(g_0(w),v), \theta_0(x)},
\end{equation}
for some $\theta_0\in\Theta$,
and for the misspecified setting where this assumption is removed. In the former setting, the minimax rates are of order $\Theta\prn{n^{-\frac{2}{2+p_2}}}$ \citep{yang1999information}, while in the latter setting the optimal rate is $\widetilde{\Theta}\prn{n^{-\frac{2}{2+p_2}\wedge{}\frac{1}{p_2}}}$ \citep{rakhlin2017empirical}. We show that under orthogonality, the optimal \iftoggle{journal}{}{well-specified and misspecified }rates can be achieved in the presence of nuisance parameters even when the nuisance class $\cG$ is larger than the target class $\Theta$, provided it is not \emph{too} much larger. This generalizes the large body of results on semiparametric inference\iftoggle{journal}{}{ \citep{levit1976efficiency,ibragimov1981statistical,pfanzagl1982contributions,bickel1982adaptive,klaassen1987consistent,robinson1988root,bickel1993efficient,newey1994asymptotic,robins1995semiparametric, ai2003efficient,van2003unified,van2003unifiedb,ai2007estimation,tsiatis2007semiparametric,kosorok2008introduction,van2011targeted,ai2012semiparametric,chernozhukov2016locally,belloni2017program,chernozhukov2016double}}, which show under various assumptions that if the target class is parametric, one can obtain a $\sqrt{n}$-consistent estimator for the target if the nuisance estimator converges at a $n^{-\frac{1}{4}}$ rate.
Our main workhorse for the results in this section is the ``Aggregation of $\varepsilon$-Nets'' or ``Skeleton Aggregation'' algorithm described in \cite{yang1999information} and extended to random design in \cite{rakhlin2017empirical}. \revoneedit{The Skeleton Aggregation method operates by splitting the samples in two, building an empirical cover for the function class under consideration using the first split, and then aggregating the elements of the cover using the second split. See \cref{sec:skeleton} for a full description. This approach is related to sieve-based methods (e.g., \citep{semenova2021debiased}), which employ parametric methods to learn a linear combination of basis elements that approximate the target, but \iftoggle{journal}{}{an important difference is that }Skeleton Aggregation builds the basis in a data-dependent fashion. We use Skeleton Aggregation as-is to provide rates for the first stage, and provide an extension in the presence of nuisance parameters for the second stage, which entails relating $\mathrm{Rate}_{\cD}(\Theta,n,\delta;\widehat{\theta},\widehat{g})$ to $\mathrm{Rate}_{\cD}(\Theta,n,\delta;\widehat{\theta},g_0)$.
}
\revoneedit{
We caution that the algorithms in this section are only designed to attain the minimax rates for \emph{generic} square losses of the type in \cref{eq:square_oracle} (e.g., vanilla square loss regression), and specific special cases may admit better rates. Deriving minimax lower bounds for specific losses of interest (as in \cite{kennedy2020optimal}) is an interesting direction for future research.
}
\oldparagraph*{Assumptions}
Since our aim is to provide sufficient conditions based on the metric entropy of the classes $\Theta$ and $\cG$, which is already quite technical, we assume that all other problem-dependent parameters are constant. This is only for expository purposes.
\begin{assumption}
\label{ass:square_oracle}
\iftoggle{journal}{}{The classes are bounded in the sense that for all}
\iftoggle{journal}{For all}{}
$\theta\in\Theta+\mathrm{star}(\Theta-\Theta)$ and \vsedit{$g\in\cG+\mathrm{star}(\cG-\cG,0)$}
the following bounds \vsedit{hold a.s.}: \textnormal{a)}
$\tri{\Lambda(g(w),v), \theta(x)}\in\brk*{-1,+1}$,
\textnormal{b)} $\Gamma(g(w),z)\in{}\brk*{-1,+1}$, \textnormal{c)}
$\Lambda(g(w), v) \Lambda(g(w), v)^{\top}\preceq{}I$,
\textnormal{d)} $\nrm*{g(w)}_{\infty}, \|\theta(x)\|_{\infty} \leq
1$, \vsedit{\textnormal{e)} $K_1,K_2=O(1)$, \textnormal{f)}
$\nrm*{u}_{\infty}\leq{}1$ almost surely, \textnormal{g)}
the functions $\crl*{\Lambda_t(\cdot, v)}_{t=1}^{K_2}$ and $\Gamma(\cdot, z)$ have $O(1)$-Lipschitz gradients with respect to $\ell_2$,
\textnormal{h)} the strong convexity condition
$\operatorname{\mathbb{E}}\brk[\big]{\tri*{\Lambda(g_0(w), v),
\theta(x)-\theta^{\star}(x)}^{2}}\geq \gamma
\operatorname{\mathbb{E}}\nrm*{\theta(x)-\theta^{\star}(x)}_{2}^{2}$ is satisfied for all $\theta\in\Theta+\mathrm{star}(\Theta-\Theta)$ for some $\gamma=\Omega(1)$.}
\end{assumption}
\cref{ass:square_oracle} implies that \cref{ass:smooth_loss} and \cref{ass:strong_convex_loss} are satisfied with respect to the seminorms $\nrm*{\theta}_{\Theta} \vcentcolon= \prn[\big]{\operatorname{\mathbb{E}}
\tri*{\Lambda(g_{0}(w),v), \theta(x)}^{2}}^{1/2}$ and $\nrm*{\cdot}_{\cG} = \nrm*{\cdot}_{L_4(\ell_2,\cD)}$, with $r=0$. Since typical results on minimax oracle rates provide rates for the nuisance $g$ with respect to $\|\cdot\|_{L_2(\ell_2,\cD)}$, we assume control on the ratio between these seminorms.
\begin{assumption}[Moment Comparison]
\label{ass:moment}
\iftoggle{journal}{$\nrm*{g-g_0}_{L_{4}(\ell_2,\cD)}\leq{}C_{2\to{}4}\cdot \nrm*{g-g_0}_{L_{2}(\ell_2,\cD)},$ for all $g\in\cG$ for a constant $C_{2\to{}4}$.
}{}
\iftoggle{journal}{}{
There is a constant $C_{2\to{}4}$ such that\[
\frac{\nrm*{g-g_0}_{L_{4}(\ell_2,\cD)}}{\nrm*{g-g_0}_{L_{2}(\ell_2,\cD)}}\leq{}C_{2\to{}4},\quad{}\forall{}g\in\cG.
\]}
\end{assumption}
The moment comparison condition has been used in statistics as a minimal assumption for learning without boundedness \citep{lecue2013learning,mendelson2014learning,liang2015learning}. For example, suppose that each $g\in\cG$ has the form $x\mapsto{}\tri*{w,x}$ for $w,x\in\bbR^{d}$. Then $C_{2\to{}4}\leq{}3^{1/4}$ if $x$ is mean-zero gaussian and $C_{2\to{}4}\leq{}\sqrt{8}$ if $x$ follows any distribution that is independent across all coordinates and symmetric (via the Khintchine inequality). Moment comparison is also implied by the ``subgaussian class'' assumption used in \cite{mendelson2011discrepancy,lecue2013learning}.\iftoggle{journal}{}{\textcolor{red}{footnote}{Suppose $\cG$ is scalar-valued and let $\nrm*{g}_{\psi_{2}}=\inf\crl*{c>0\mid{}\operatorname{\mathbb{E}}\exp\prn*{g^{2}(w)/c^{2}}\leq{}2}$. Then the subgaussian class assumption for our setting asserts that $\nrm*{g-g_0}_{\psi_{2}}\leq{}C\nrm*{g-g_0}_{L_2(\cD)}$ for all $g\in\cG$.}} We emphasize that the moment constant $C_{2\to{}4}$ does not enter the leading term in any of our bounds---only the $\mathrm{Rate}_{\cD}(\cG,\ldots,)$ term in \cref{thm:generic_strongly_convex}---and so it does not affect the asymptotic rates under conditions on metric entropy growth of $\cG$ that we prescribe in the sequel. We also note that this condition is not required for many classes of interest, where direct $L_{4}$ estimation rates are available (see discussion in \cref{sec:sufficient}). We adopt the condition here because it allows us to develop guarantees for arbitrary classes at the highest possible level of generality.
\begin{comment}
Moreover, if guarantees stronger than $L_4$ available (e.g., $L_{\infty}$ error or parameter recovery), then---in addition to removing the moment condition---we can obtain tighter dependence on problem parameters through an alternative version of the Cauchy-Schwarz argument used to establish \cref{ass:smooth_loss} and \cref{ass:strong_convex_loss} for the setup in this section (see \cref{sec:sufficient}). However, we adopt the condition here because it allows us to develop guarantees for arbitrary classes at the highest possible level of generality.
\end{comment}
\oldparagraph*{Main Result}
\revoneedit{The main theorem for this section provides sufficient conditions for oracle rates in the well-specified setting \cref{eq:oracle_well_specified}. For extensions of this result to misspecified models, as well as non-strongly convex losses, see \cref{sec:oracle_lipschitz}.
}
\begin{theorem}[Oracle Rates, Well-Specified Case]
\label{thm:oracle_well_specified}
Suppose that we are in the well-specified setting \cref{eq:oracle_well_specified}, and that \cref{ass:orthogonal,ass:well_specified} and \cref{ass:square_oracle,ass:moment} are satisfied for the class $\widehat{\Theta}$ defined below. Suppose that the following relationship holds:
\begin{equation}
p_1 < 2p_2+2.
\end{equation}
Then for appropriate choice of sub-algorithms, the sample splitting meta-algorithm \cref{alg:sample_splitting} produces a predictor $\widehat{\theta}$ that guarantees that with probability at least $1-\delta$,
\begin{equation}
\label{eq:oracle_well_specified2}
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta_0,g_0)
\leq{} \widetilde{O}\prn[\big]{n^{-\frac{2}{2+p_2}}},
\end{equation}
\revoneedit{where $\widetilde{O}(\cdot)$ hides problem-dependent parameters and $\log(\delta^{-1})$ terms. This result matches the minimax rate in the absence of nuisance parameters. In particular, when $p_2\leq{}2$ it suffices to take $\widehat{\Theta}=\Theta$ and use plug-in ERM for stage two, and when $p_2>2$ it suffices to take $\widehat{\Theta}=\Theta + \mathrm{star}(\Theta-\Theta,0)$ and use Skeleton Aggregation for stage two; in both cases, it suffices to use Skeleton Aggregation for stage one.
}
\end{theorem}
\begin{figure}[t]
\begin{center}
\includegraphics[width=.35\textwidth]{plotting/1}
\end{center}
\caption{Relationship between first and second stage for oracle rates; well-specified case.}
\label{fig:oracle_well_specified}
\end{figure}
\revoneedit{\cref{thm:oracle_well_specified} is proven by combining the main theorem (\cref{thm:generic_strongly_convex}) with algorithm-specific upper bounds on $\mathrm{Rate}_{\cD}(\Theta,\cdots)$ and $\mathrm{Rate}_{\cD}(\cG,\cdots)$. \cref{fig:oracle_well_specified} summarizes the sufficient conditions under which \cref{thm:oracle_well_specified} leads to the oracle rate $\Theta\prn{n^{-\frac{2}{2+p_2}}}$ \citep{yang1999information}}. In particular, whenever $\Theta$ is a parametric class (i.e. $\cH_{2}(\Theta,\varepsilon,n)\proptod_2\log(1/\varepsilon)$), it suffices to take $p_1<2$, which recovers the usual setup for semiparametric inference.
\begin{comment}
Next, we derive sufficient conditions for oracle rates in the case where the second stage is \emph{misspecified}. This setting has been relatively unexplored in recent results on double machine learning \citep{chernozhukov2016double,mackey2017orthogonal,chernozhukov2018plugin}; this is perhaps not surprising since for many settings, assuming a well-specified model is critical to establish orthogonality. However, for certain settings including treatment effect estimation (\cref{sec:treatment_effect}), orthogonality can indeed hold even without model correctness. The following theorem shows that we can obtain oracle rates in the presence of both misspecification and nuisance parameters as long as the nuisance class has moderate complexity.
\begin{theorem}[Oracle Rates, Misspecified Case]
\label{thm:oracle_misspecified}
Suppose that the target class $\Theta$ is convex. Suppose that \cref{ass:orthogonal,ass:well_specified} and \cref{ass:square_oracle,ass:moment} hold. If the relationship
\begin{equation}
p_1 < \max\crl*{2p_2+2,4p_2-2}
\end{equation}
holds, then for appropriate choice of sub-algorithms, the sample splitting meta-algorithm \cref{alg:sample_splitting} produces a predictor $\widehat{\theta}$ such that with probability at least $1-\delta$,
\begin{equation}
\label{eq:oracle_misspecified}
L_{\cD}(\widehat{\theta},g_0) - L_{\cD}(\theta_0,g_0)
\leq{} \widetilde{O}\prn[\big]{n^{-\frac{2}{2+p_2}\wedge{}\frac{1}{p_2}}},
\end{equation}
\revoneedit{thereby matching the minimax rate in the absence of nuisance parameters. In particular, it suffices to use Skeleton Aggregation for the first stage and plug-in ERM for the second stage.}
\end{theorem}
\revoneedit{Like the previous result, \cref{thm:oracle_misspecified} is proven by combining the main theorem (\cref{thm:generic_strongly_convex}) with algorithm-specific upper bounds on $\mathrm{Rate}_{\cD}(\Theta,\cdots)$ and $\mathrm{Rate}_{\cD}(\cG,\cdots)$. \cref{fig:oracle_misspecified} summarizes sufficient conditions under which \cref{thm:oracle_misspecified} matches the oracle rate
$\widetilde{\Theta}\prn{n^{-\frac{2}{2+p_2}\wedge{}\frac{1}{p_2}}}$ \citep{rakhlin2017empirical}.} Comparing to the well-specified case (\cref{thm:oracle_well_specified}/\cref{fig:oracle_well_specified}), we see that in the misspecified case, the condition on the metric entropy for the nuisance parameter is significantly more permissive when the target parameter class $\Theta$ is large (i.e. $p_2>2$). For example, if $p_2=5$ then we require $p_1<12$ for oracle rates in the well-specified case, but only require $p_1<18$ in the misspecified case. On the other hand, when $p_2\leq{}2$ the conditions on the nuisance metric entropy match the well-specified case. In particular, whenever $\Theta$ is a parametric class it again suffices to take $p_1<2$ so that the first stage has an $n^{-1/4}$-rate.
\begin{figure}[t]
\begin{center}
\includegraphics[width=.35\textwidth]{plotting/2}
\end{center}
\caption{Relationship between first and second stage for oracle rates; misspecified case.}
\label{fig:oracle_misspecified}
\end{figure}
\end{comment}
\section{Discussion}
\label{sec:discussion}
This paper initiates the systematic study of prediction error and
excess risk guarantees in the presence of nuisance parameters and
Neyman orthogonality. Our results highlight that orthogonality is
beneficial for learning with nuisance parameters even in the presence
of possible model misspecification, and even when the target
parameters belong to large nonparametric classes. We also show that
many of the typical assumptions used to analyze estimation in the
presence of nuisance parameters can be relaxed when excess risk
is the focus. There are many promising future directions,
including weakening assumptions, obtaining sharper guarantees for
specific settings and losses of interest (e.g., doubly-robust guarantees), and analyzing further
algorithms for general function classes (along the lines of
\cref{sec:erm,sec:oracle}). \revoneedit{We refer to the appendix for additional
results, as well as empirical results.}\iftoggle{journal}{\looseness=-1}{}
\iftoggle{journal}{}{\oldparagraph*{Acknowledgements}}
\iftoggle{journal}{\section*{Acknowledgements}}{}
We are grateful to \iftoggle{journal}{}{the anonymous COLT reviewers and to }Xiaohong Chen for
pointing out additional related work. Part of this work was completed
while DF was an intern at Microsoft Research\iftoggle{journal}{}{, New England}. DF
acknowledges support from the Facebook PhD fellowship and NSF Tripods
grant \#1740751.
\iftoggle{journal}{
\begin{supplement}
\stitle{Supplementary for ``Orthogonal Statistical Learning''}
\sdescription{The supplementary material contains proofs, experiments, and additional results deferred due to space constraints.}
\end{supplement}
}{}
\iftoggle{supp}{}{
\iftoggle{journal}{\bibliographystyle{imsart-nameyear}}{}
\bibliography{refs}
}