Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
132,139 characters · 16 sections · 88 citation commands
Orthogonal Statistical Learning
\iftoggle{journal}{
}
\iftoggle{journal}{
}
\iftoggle{journal}{ { \hypersetup{linkcolor=black} } }
\iftoggle{draft}{ { \hypersetup{linkcolor=black} } }
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 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 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 unconfoundedness assumption rosenbaum1983central and use the so-called 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):}
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 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 statistical learning with a nuisance component: Given $n$ i.i.d. examples from a distribution $\cD$, a learner is interested in finding a 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 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 excess risk evaluated at the unknown true nuisance parameter\xspace:
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 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 (ref), 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 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 chen1999improved,farrell2018deep; by focusing on excess risk we can give guarantees for the case where the 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. athey2017efficient and 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 nie2017quasi, random forests athey2016generalized, oprescu2018orthogonal,friedberg2018, and high-dimensional linear models chernozhukov2017orthogonal,chernozhukov2018plugin. Other results allow for fairly general choices for the target parameter class in specific statistical models 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 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$,
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.
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)}}{Meta-Algorithm (ref)}. We can now state the main question addressed in this paper: 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 oracle rate in semiparametric inference.
\oldparagraph*{Overview of results} We use Neyman orthogonality neyman1959optimal,neyman1979c, a key tool in inference in semiparametric models 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., 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 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:
To make the conditions above concrete for arbitrary classes, we give conditions on the relative complexity of the target and nuisance classes---quantified via 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 yang1999information,rakhlin2017empirical, which provide minimax optimal rates without nuisance components and utilize the technique of 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 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 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 maurer2009empirical by replacing the dependence on the metric entropy at a fixed approximation level with the 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.
\oldparagraph*{General frameworks for learning/inference with nuisance parameters} The work of van2003unified and subsequent refinements and extensions van2006cross,van2007super develops cross-validation methodology for a similar risk minimization setting in which the target risk parameter depends on an unknown nuisance parameter. 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 parametric). Overall, our approach offers several new benefits:
The methodology of 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. 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 targeted maximum likelihood estimation (TMLE). TMLE 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 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 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 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 van2006estimating, the target is a Lipschitz function over $[0,\infty)$ (the marginal survival function) and an estimation rate of $n^{-2/3}$ is given. wang2010nonparametric consider estimation of smooth nonparametric target parameters in the presence of missing outcomes, and give algorithms based on kernel smoothing. 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 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 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 van2006targeted,hirshberg2017augmented,chernozhukov2018double,ning2018robust. While our focus is on methods based on loss minimization, some problems such as nonparametric instrumental variables 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 (ref), 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 (ref), but we do not know of any estimators for this problem that satisfy the conditions required to apply our main theorems.}
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 target parameter\xspace class $\Theta:\cX\to\cV_2$ and 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 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 target predictor $\widehat{\theta}$ that minimizes the excess risk evaluated at $g_0$
As discussed in the introduction, we will always produce such a predictor via the sample splitting meta-algorithm ((ref)), 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 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
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)\})$.
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 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 (ref) 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.
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 (ref) will only yield a “pseudo”-excess risk bound of the form
This clearly does not match the desired bound (ref), 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.
(ref) 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 improper prediction, i.e. $\widehat{\Theta}\supset\Theta$, which in some cases is required to obtain optimal rates for misspecified models 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 (ref), and we indeed consider algorithms that do not have this form \revoneedit{(cf. (ref))}. \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. (ref)).}
\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 fast rates or 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 bousquet2004introduction,bartlett2005local,srebro2010smoothness, and we will see concrete examples of such rates for specific classes in later sections ((ref), (ref)).
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 (ref) 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.
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 directional derivatives with respect to the target and nuisance parameters\xspace.
\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 orthogonal in the sense that the certain pathwise derivatives vanish.
\revoneedit{Note that while (ref) 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) 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.
(ref) and (ref) 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 (ref). \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. (ref)). In general, (ref) 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.
\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}$, (ref) shows that for (ref), 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.
There is one issue not addressed by (ref): 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 (ref) scales instead with $\mathrm{Rate}_{\cD}(\Theta,\ldots;\,{}\widehat{\theta},\widehat{g})$. This is addressed in (ref), where---building on (ref)---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 (ref) or (ref).\iftoggle{journal}{\looseness=-1}
The strong convexity assumption used by (ref) 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., 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 (ref). \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 universal orthogonality, which informally states that the loss is not simply orthogonal around $\theta^{\star}$, but rather is orthogonal for all $\theta\in\Theta$.
\revoneedit{Universal orthogonality is a strengthening of (ref), 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 ((ref)) and policy learning ((ref)), and is used implicitly in previous work in these settings nie2017quasi,athey2017efficient. Beyond orthogonality, we require a mild smoothness assumption for the nuisance class.\iftoggle{journal}{\looseness=-1}
Our main theorem for slow rates is as follows.
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., robinson1988root,nie2017quasi, we receive examples $z=(X,W,Y,T)$ according to the following data generating process:
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)$.
\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 (ref) in accommodating such cases, we consider a constrained variant of the R-learner of nie2017quasi and recover the oracle rates from this work.
\oldparagraph*{Slow rates} We mention in passing that some distributions may simply not satisfy the coverage condition in (ref). In this case, we can appeal to (ref) (we show in (ref) that the residualized loss satisfies the universal orthogonality property), which does not require any lower bounds in the vein of (ref), but leads to slower rates. In general, whether the fast rate ((ref)) or slow rate ((ref)) will give better results given finite samples will depend on the behavior of the data distribution and target class.
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 (ref) 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:
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:
This formulation has been extensively studied in statistics qian2011performance,zhao2012estimating,zhou2017residual,athey2017efficient,zhou2018offline and machine learning 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 (ref) 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
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,
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 (ref). 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}
has the structure in (ref): it evaluates to the true risk (ref) whenever the true nuisance parameter is plugged in. This formulation leads to the well-known doubly-robust estimator for the counterfactual outcome 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
and set $\ell(t, g;Z) = \beta(g;Z)\cdot{}t$. This formulation leads to a linear population risk:
This population risk satisfies universal orthogonality, and (ref) 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 (ref).
\revoneedit{The results in (ref) 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
We analyze one of the most natural and widely used estimation algorithms for the target parameter: plug-in empirical risk minimization (plug-in ERM). Specifically, recalling that $S=S_1\cup{}S_2$, we define the empirical risk via
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:
\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 ((ref) and (ref)).}
In the fast rate regime (i.e., for strongly convex losses) we offer a generalization of the local Rademacher complexity analysis of bartlett2005local in the presence of an estimated nuisance component and show that the notion of the 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 ((ref)).\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 variance of the population loss evaluated at the optimal target parameter. This offers an improvement over prior variance-penalized ERM approaches 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:
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 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. boucheron2013concentration).}
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.
Our first contribution is an extension of the foundational results of 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 critical radius $\delta_n$ of a function class $\cG$, defined as the smallest solution to the inequality
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. 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. (ref)):
where $\cG(\delta,z_{1:n}) \vcentcolon= \crl{g\in\cG: \nrm*{g}_{L_2(z_{1:n})}\leq{}\delta}$; see (ref) 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).
\iftoggle{journal} \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 (ref) to derive the final guarantee. See (ref) for details. }
We now turn to the slow rate regime from (ref), 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 (ref) in (ref) 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)). \]
\iftoggle{journal} \revoneedit{As with the previous result, (ref) 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, (ref)). 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 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 (ref), 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 Alexander capacity function}.}
We focus on\iftoggle{journal}{ the important special case of} square losses of the form
where $\Lambda$ and $\Gamma$ are known functions, and where we recall from (ref) 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 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
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 well-specified setting in which
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}}}$ yang1999information, while in the latter setting the optimal rate is $\widetilde{\Theta}\prn{n^{-\frac{2}{2+p_2}\wedge{}\frac{1}{p_2}}}$ 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 too much larger. This generalizes the large body of results on semiparametric inference\iftoggle{journal}{ 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 yang1999information and extended to random design in 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 (ref) for a full description. This approach is related to sieve-based methods (e.g., 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 generic square losses of the type in (ref) (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 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.
(ref) implies that (ref) and (ref) 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.
The moment comparison condition has been used in statistics as a minimal assumption for learning without boundedness 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 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 (ref)---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 (ref)). We adopt the condition here because it allows us to develop guarantees for arbitrary classes at the highest possible level of generality.
\oldparagraph*{Main Result} \revoneedit{The main theorem for this section provides sufficient conditions for oracle rates in the well-specified setting (ref). For extensions of this result to misspecified models, as well as non-strongly convex losses, see (ref). }
\revoneedit{(ref) is proven by combining the main theorem ((ref)) with algorithm-specific upper bounds on $\mathrm{Rate}_{\cD}(\Theta,\cdots)$ and $\mathrm{Rate}_{\cD}(\cG,\cdots)$. (ref) summarizes the sufficient conditions under which (ref) leads to the oracle rate $\Theta\prn{n^{-\frac{2}{2+p_2}}}$ 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.
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 (ref)). \revoneedit{We refer to the appendix for additional results, as well as empirical results.}\iftoggle{journal}{\looseness=-1}
\iftoggle{journal}{\oldparagraph*{Acknowledgements}} \iftoggle{journal}{
} 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}{
}
\iftoggle{supp}{ \iftoggle{journal} }