--- abstract: | U-statistics constitute a large class of estimators, generalizing the empirical mean of a random variable $\X$ to sums over every $k$-tuple of distinct observations of $\X$. They may be used to estimate a regular functional $\theta(\PP_{\X})$ of the law of $\X$. When a vector of covariates $\Z$ is available, a conditional U-statistic may describe the effect of $\z$ on the conditional law of $\X$ given $\Z=\z$, by estimating a regular conditional functional $\theta(\PP_{\X|\Z=\cdot})$. We prove concentration inequalities for conditional U-statistics. Assuming a parametric model of the conditional functional of interest, we propose a regression-type estimator based on conditional U-statistics. Its theoretical properties are derived, first in a non-asymptotic framework and then in two different asymptotic regimes. Some examples are given to illustrate our methods.\ address: 'CREST-ENSAE, 5, avenue Henry Le Chatelier, 91764 Palaiseau Cedex, France.' author: - Alexis Derumigny bibliography: - 'biblio\_Cond\_UstatRegression.bib' title: | Estimation of a regular conditional functional by\ conditional U-statistics regression --- U-statistics ,regression-type models ,conditional distribution ,penalized regression 62F12 ,62G05 ,62J99 Introduction ============ Let $\X$ be a random element with values in a measurable space $(\Xc, \Ac)$, and denote by $\PP_{\X}$ its law. A natural framework is $\Xc = \Rb^{p_X}$, for a fixed dimension $p_{\X} > 0$. Often, we are interested in estimating a regular functional $\theta(\PP_{\X})$ of the law of $\X$, of the form $$\theta(\PP_{\X}) = \EE \big[ g(\X_1, \dots, \X_k) \big] = \int g(\x_1, \dots, \x_k) d\PP_{\X}(\x_1) \cdots d\PP_{\X}(\x_k),$$ for a fixed $k > 0$, a function $g : \Xc^k \to \Rb$ and $\X_1, \dots \X_k \simiid \PP_{\X}$. Following Hoeffding @hoeffding1948class, a natural estimator of $\theta(\PP_{\X})$ is the U-statistics $\hat \theta(\PP_{\X})$, defined by $$\begin{aligned} \hat \theta(\PP_{\X}) := |\Ikn|^{-1} \sum_{\sigma \in \Ikn} g\big(\X_{\sigma(1)}, \dots, \X_{\sigma(k)} \big),\end{aligned}$$ where $\Ikn$ is the set of injective functions from $\{1, \dots, k\}$ to $\{1, \dots, n\}$. For an introduction to the theory of U-statistics, we refer to Koroljuk and Borovskich @koroljuk1994theory and Serfling @serfling1980approximation [Chapter 5] In our framework, we assume that we actually observe $(\X, \Z)$ where $\Z$ is a $p$-dimensional covariate. We are now interested in regular functionals of the conditional law $\PP_{\X | \Z}$. For each $\z_1, \dots, \z_k \in \Zc$, where $\Zc$ is a compact subset of $\Rb^p$, we can define such a functional $\theta_{\z_1, \dots, \z_k}$ by $$\begin{aligned} \theta_{\z_1, \dots \z_k}( \PP_{\X | \Z = \cdot}) &:= \theta( \PP_{\X | \Z = \z_1}, \dots, \PP_{\X | \Z = \z_k} ) \\ &= \EE_{\bigotimes_{i=1}^k \PP_{\X | \Z = \z_i}} \big[ g(\X_1, \dots, \X_k) \big] = \EE \big[ g(\X_1, \dots, \X_k) \big| \Z_i=\z_i, \forall i=1, \dots, k \big] \\ &= \int g(\x_1, \dots, \x_k) d\PP_{\X | \Z = \z_1}(\x_1) \cdots d\PP_{\X | \Z = \z_k}(\x_k).\end{aligned}$$ This can be seen as a generalization of $\theta(\PP_\X)$ to the conditional case. Indeed, when $\X$ and $\Z$ are independent, the new functional $\theta_{\z_1, \dots, \z_k}( \PP_{\X | \Z = \cdot})$ is equal to the unconditional functional $\theta(\PP_\X)$. For convenience, we will use the notation $\theta(\z_1, \dots, \z_k) := \theta_{\z_1, \dots \z_k}( \PP_{\X | \Z = \cdot}),$ treating the law of $(\X, \Z)$ as fixed (but unknown). Stute @stute1991conditional defined a kernel-based estimator $\hat \theta(\z_1, \dots, \z_k)$ of the conditional functional $\theta(\z_1, \dots, \z_k)$ by $$\hat \theta(\z_1, \dots, \z_k) := \dfrac{\sum_{\sigma \in \Ikn} K_h \big(\Z_{\sigma(1)}-\z_1 \big) \cdots K_h \big(\Z_{\sigma(k)}-\z_k \big) \, g\big(\X_{\sigma(1)}, \dots, \X_{\sigma(k)} \big) } {\sum_{\sigma \in \Ikn} K_h \big(\Z_{\sigma(1)}-\z_1 \big) \cdots K_h \big(\Z_{\sigma(k)}-\z_k \big) }, \label{condUstat:def:estimator_hat_theta}$$ where $h > 0$ is the bandwidth, $K(\cdot)$ a kernel on $\Rb^p$, $K_h(\cdot) := h^{-p} K(\cdot / h)$, and $(\X_i, \Z_i) \simiid \PP_{\X, \Z}$. Stute @stute1991conditional proved the asymptotic normality of $\hat \theta(\z_1, \dots, \z_k)$ and its weak and strong consistency. Dony and Mason @dony2008uniform derived its uniform in bandwidth consistency under VC-type conditions over a class of possible functions $g$. Nevertheless, the estimator (\[condUstat:def:estimator\_hat\_theta\]) has several weaknesses. First, the interpretation of the whole hypersurface $(\z_1, \dots, \z_k) \mapsto \hat \theta(\z_1, \dots, \z_k)$ can be difficult. Indeed, the latter curve is of dimension $1+p \times k$, and it is rather challenging to visualize it even for small values of $p$ and $k$. Second, for each new $k$-uplet $(\z_1, \dots, \z_k)$, the computation of $\hat \theta(\z_1, \dots, \z_k)$ has a cost of $O(n^k)$. Then, if we want to estimate $\hat \theta(\z_1^{(i)}, \dots, \z_k^{(i)})$ for every $i=1, \dots, N$, where $\big(\z_1^{(1)}, \dots, \z_k^{(1)}, \dots, \z_1^{(N)}, \dots, \z_k^{(N)} \big) \in \Zc^{k \times N}$, then the total cost is $O(N n^k)$. Third, it is well-known that kernel estimators are not very smooth, in the sense that they usually present many spurious local minima and maxima, and this can be a problem in some applications. Therefore, we may want to build estimators which are more regular with respect to the conditioning variables $\z_1, \dots \z_k$, and have a simple functional form. Another idea is to decompose the function $(\z_1, \dots, \z_k) \mapsto \theta(\z_1, \dots, \z_k)$ on a basis $(\psi_i)_{i \geq 0}$, generalizing the work of Derumigny and Fermanian @derumigny2018kendall. This may not be always easy if the range of the function $\theta(\cdot, \cdots, \cdot)$ is a strict subset of $\Rb$. In that case, it is always possible to use a "link function" $\Lambda$, that would be strictly increasing and continuously differentiable and such that the range $\Lambda \circ \theta(\cdot, \cdots, \cdot)$ is exactly $\Rb$. Whatever the choice of $\Lambda$ (including the identity function), we can decompose the latter function on any basis $(\psi_i)_{i \geq 0}$. If only a finite number $r > 0$ of elements of this basis are necessary to represent the whole function $\Lambda \circ \theta(\cdot, \cdots, \cdot)$ over $\Zc^k$, then we have the following parametric model: $$\forall (\z_1, \dots, \z_k) \in \Zc^k, \, \Lambda \big( \theta(\z_1, \dots, \z_k) \big) = \psibm (\z_1, \dots, \z_k)^T \beta^*, \label{model:lambda_cond_theta_Z}$$ where $\beta^* \in \Rb^r$ is the true parameter and $\psibm(\cdot) := \big(\psi_1(\cdot), \dots, \psi_r(\cdot) \big)^T \in \Rb^r$. In most applications, finding an appropriate basis $\psibm$ is not easy. This will depend on the choice of the (conditional) functional $\theta$. Therefore, the most simple solution consists in choosing a concatenation of several well-known basis such as polynomials, exponentials, sinuses and cosinuses, indicator functions, etc... They allow to take into account potential non-linearities and even discontinuities of the function $\Lambda \circ \theta(\cdot, \cdots, \cdot)$. For the sake of inference, a necessary condition is the linear independence of such functions, as seen in the following proposition (whose straightforward proof is omitted). The parameter $\beta^*$ is identifiable in Model (\[model:lambda\_cond\_theta\_Z\]) if and only if the functions $(\psi_1(\cdot), \dots, \psi_r (\cdot))$ are linearly independent $\PP_\Z^{\otimes n}$-almost everywhere in the sense that, for all vectors $\t = (t_1, \dots, t_r) \in \Rb^r$, $\PP_\Z^{\otimes n} \big( \psibm(\Z_1, \dots, \Z_n)^T \t = 0 \big) = 1 \implies \t = 0.$ \[condUstat:prop:identifiability\_condition\] With such a choice of a wide and flexible class of functions, it is likely that not all these functions are relevant. This is know as sparsity, i.e. the number of non-zero coefficients of $\beta^*$, denoted by $|\Sc|$ = $|\beta^*|_0$ is less than $s$, for some $s \in \{1, \dots, r\}$. Here, $| \cdot |_0$ denotes the number of non-zero components of a vector of $\Rb^{r}$ and $\Sc$ is the set of non-zero components of $\beta^*$. Note that, in this framework, $r$ can be moderately large, for example $30$ or $50$, while the original dimension $p$ is small, for example $p=1$ or $2$. This corresponds to the decomposition of a function, defined on a small-dimension domain, in a mildly large basis. At first sight, in Model (\[model:lambda\_cond\_theta\_Z\]), there seems to be no noise perturbing the variable of interest. In fact, this can be seen as a simple consequence of our formulation of the model. In the same way, the classical linear model $Y=\X^T \beta^* + \varepsilon$ can be rewritten as $\EE[Y|\X=\x] = \x^T \beta^*$ without any explicit noise. By definition, $\EE[Y|\X=\x]$ is a deterministic function of a given $\x$. In our case, the corresponding fact is: $\Lambda \big( \theta(\z_1, \dots, \z_k) \big)$ is a deterministic function of the variables $(\z_1, \dots, \z_k)$. This means that we cannot write formally a model with noise, such as $\Lambda \big( \theta(\z_1, \dots, \z_k) \big) = \psibm (\z_1, \dots, \z_k)^T \beta^* + \varepsilon$ where $\varepsilon$ is independent of the choice of $(\z_1, \dots, \z_k)$ since the left-hand side of the latter equality is a $(\z_1, \dots, \z_k)$-mesurable quantity, unless $\varepsilon$ is constant almost surely. Contrary to more usual models, the explained variable $\Lambda \big( \theta(\z_1, \dots, \z_k) \big)$, is not observed in Model (\[model:lambda\_cond\_theta\_Z\]). Therefore, a direct estimation of the parameter $\beta^*$ (for example, by the ordinary least squares, or by the Lasso) is unfeasible. In other words, even if the function $(\z_1, \dots, \z_k) \mapsto \Lambda \big( \theta(\z_1, \dots, \z_k) \big)$ is deterministic (by definition of conditional probabilities), finding the best $\beta$ in Model (\[model:lambda\_cond\_theta\_Z\]) is far from being a numerical analysis problem since the function to be decomposed is unknown. Nevertheless, we will replace $\Lambda \big( \theta(\z_1, \dots, \z_k) \big)$ by the nonparametric estimate $\Lambda \big( \hat \theta(\z_1, \dots, \z_k) \big)$, and use it as an approximation of the explained variable. More precisely, we fix a finite collection of points $\z'_1, \dots, \z'_{n'} \in \Zc^{n'}$ and a collection $\Iknpr$ of injective functions $\sigma: \{1, \dots, k\} \to \{1, \dots, n'\}$. Note that we are not forced to include *all* the injective functions in $\Iknpr$, reducing its number of elements. This will allow us to decrease the computational cost of the procedure. For every $\sigma \in \Iknpr,$ we estimate $\hat \theta(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)})$. Finally, the estimator $\hat \beta$ is defined as the minimizer of the following $l_1$-penalized criteria $$\hat \beta := \arg \min_{\beta \in \Rb^{r}} \left[ \frac{(n'-k)!}{n'!} \sum_{\sigma \in \Iknpr} \bigg( \Lambda \Big(\hat \theta \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big) \Big) - \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big)^T \beta \bigg)^2 + \lambda |\beta|_1 \right], \label{condUstat:def:estimator_hat_beta}$$ where $\lambda$ is a positive tuning parameter (that may depend on $n$ and $n'$), and $|\cdot|_q$ denotes the $l_q$ norm, for $1\leq q \leq \infty$. This procedure is summed up in the following Algorithm \[condUstat:algo:estimation\_beta\]. Note that even if we study the general case with any $\lambda \geq 0$, the corresponding properties of the unpenalized estimator can be derived by choosing the particular case $\lambda = 0$. \[htb\] \[condUstat:algo:estimation\_beta\] Compute the minimizer $\hat \beta$ of (\[condUstat:def:estimator\_hat\_beta\]) using the $\hat \theta \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big),$ $j=1,\dots,n',$ estimated in the above step Once an estimator $\hat \beta$ of $\beta^*$ has been computed, the prediction of all the conditional functionals is reduced to the computation of $\Lambda^{(-1)} \big( \psibm (\z_1^{(i)}, \dots, \z_k^{(i)} )^T \hat \beta \big) := \tilde \theta(\z_1^{(i)}, \dots, \z_k^{(i)} )$, for every $i=1, \dots, N$. The total computational cost of this new method is therefore $O(|\Iknpr| n'{}^k + |\Iknpr| r + N s)$ operations. The first term corresponds to the cost of evaluating each non-parametric estimator (\[condUstat:def:estimator\_hat\_theta\]). The second term corresponds to the minimization of the convex optimization program (\[condUstat:def:estimator\_hat\_beta\]), and the last one is the prediction cost. Note that the procedure described in Algorithm \[condUstat:algo:estimation\_beta\] can provide a huge improvement compared to the previously available estimator with a cost in $O(N n^k)$ when $N \to \infty$, i.e. when we want to recover the full function $\theta(\cdot, \cdots, \cdot)$. Moreover, the speed-up given by Algorithm \[condUstat:algo:estimation\_beta\] compared to the original conditional U-statistics (\[condUstat:def:estimator\_hat\_theta\]) even increases with the sample size $n$, for moderate choices of $n'$. A similar model, called *functional response*, has already been studied: see, e.g. Kowalski and Tu @kowalski2008modern [Chapter 6.2]. They provide a method to estimate the parameter $\beta^*$, using generalized estimating equations. However, they only provide asymptotic results for their estimator, and their algorithm needs to solve a multi-dimensional equation which has no reason to be convex. In Section \[section:theoretical\_prop\_theta\], we provide non-asymptotic bounds for the non-parametric estimator $\hat \theta$. Then Section \[section:theoretical\_prop\_beta\] is devoted to the statement of corresponding bounds, as well as asymptotic properties for the parametric estimator $\hat \beta$. Finally, a few examples are presented in Section \[condUstats:sec:applications\]. All proofs have been postponed to the Appendix. Theoretical properties of the nonparametric estimator hat theta(.) {#section:theoretical_prop_theta} ================================================================== Non-asymptotic bounds for Nk ---------------------------- We remark that the estimator $\hat \theta$ is well-defined if and only if $N_k(\z_1, \dots, \z_k) > 0$, where $$N_k(\z_1, \dots, \z_k) := \frac{k!(n-k)!}{n!} \sum_{\sigma \in \Iknup} K_h \big(\Z_{\sigma(1)}-\z_1 \big) \cdots K_h \big(\Z_{\sigma(k)}-\z_k \big). \label{condUstat:def:normalization_factor_N_k}$$ To prove that our estimator $\hat \theta(\z_1, \dots, \z_k)$ exists with a probability that tends to 1, we will therefore study the behavior of $N_k$. We will need the following assumptions to control the kernel $K$ and the density of $\Z$. The kernel $K(\cdot)$ is bounded, i.e. there exists a finite constant $C_K$ such that $K(\cdot) \leq C_{K}$ and $\int K(\u) d\u = 1$. The kernel is of order $\alpha$ for some $\alpha > 0$, i.e. for all $j = 1, \dots, \alpha - 1$ and all $1 \leq i_1, \dots, i_{\alpha} \leq p$, $\int K(\u) \, u_{i_1} \dots u_{i_j} \; d\u = 0.$ \[condUstat:assumpt:kernel\_integral\] $f_\Z$ is $\alpha$-times continuously differentiable on $\Zc$ and there exists a finite constant $C_{K,\alpha}$ such that, for all $\z_1, \dots \z_k$, $$\begin{aligned} &\int \Big| K \big(\u_1 \big) \cdots K \big(\u_k \big) \Big| \sum_{m_1 + \, \cdots \, + m_k = \alpha} \binom{\alpha}{m_{1:k}} \\ &\hspace{1cm} \cdot \prod_{i=1}^k \sum_{j_1, \dots, j_{m_i} = 1}^{p} \big| u_{i,j_1} \dots u_{i,j_{m_i}} \big| \sup_{t \in [0,1]} \left| \frac{\partial^{m_i} f_{\Z}}{\partial z_{j_1} \, \cdots \, \partial z_{j_{m_i}}} \big(\z_i + t \u_i \big) \right| d\u_1 \cdots d\u_k \leq C_{K,\alpha} \end{aligned}$$ where $\binom{\alpha}{m_{1:k}} := \alpha! / \big( \prod_{i=1}^k (m_i!) \big)$ is the multinomial coefficient. \[condUstat:assumpt:bound\_int\_deriv\_fZ\] $f_\Z(\cdot) \leq f_{\Z, max} $ for some finite constant $f_{\Z, max}$. \[condUstat:assumpt:f\_Z\_max\] Under Assumptions \[condUstat:assumpt:kernel\_integral\], \[condUstat:assumpt:bound\_int\_deriv\_fZ\] and \[condUstat:assumpt:f\_Z\_max\], we have for any $t > 0$, $$\begin{aligned} \PP \bigg( \big| N_k(\z_1, \dots, \z_k) &- \prod_{i=1}^k f_{\Z}(\z_i) \big| \leq \frac{C_{K, \alpha}}{\alpha!} h^{\alpha} + t \bigg) \geq 1 - 2 \exp \bigg( - \frac{[ n / k] t^2}{h^{-k p} C_1 + h^{-k p} C_2 t} \bigg), \end{aligned}$$ where $C_1 := 2 f_{\Z, max}^k ||K||_2^{2k}$, and $C_2 := (4/3) C_K^k$ and $||K||_2^2 := \int K^2$. \[lemma:bound\_Nk\_fk\] This Lemma is proved in \[condUstat:proof:lemma:bound\_Nk\_fk\]. More can be said if the density $f_\Z$ is bounded below. Therefore, we will use the following assumption. There exists a constant $f_{\Z, min} > 0$ such that for every $\z \in \Zc$, $f_{\Z}(\z) > f_{\Z, min}$. \[condUstat:assumpt:f\_Z\_min\] If for some $\epsilon > 0$, we have $C_{K, \alpha} h^{\alpha} / \alpha ! + t \leq f_{\Z, min} - \epsilon$, then $\hat f(\z) \geq \epsilon > 0$ with probability larger than on the event whose probability is bound in Lemma \[lemma:bound\_Nk\_fk\]. We should therefore choose the largest $t$ possible, which yields the following corollary. Under Assumptions \[condUstat:assumpt:kernel\_integral\]-\[condUstat:assumpt:f\_Z\_min\], if $C_{K, \alpha} h^{\alpha} / \alpha ! \, < f_{\Z, min}$, then the random variable $N_k(\z_1, \dots, \z_k)$ is strictly positive with a probability larger than $1 - 2 \exp \bigg( - \frac{[ n / k] h^{k p} \big( f_{\Z, min} - C_{K, \alpha} h^{\alpha} / \alpha ! \big)^2} {C_1 + C_2 \big( f_{\Z, min} - C_{K, \alpha} h^{\alpha} / \alpha ! \big) } \bigg),$ guaranteeing the existence of the estimator $\hat \theta(\z_1, \dots, \z_k)$ on this event. \[cor:probaTheta\_Z\_valid\] Non-asymptotic bounds in probability for hat theta -------------------------------------------------- In this section, we generalize the bounds given in @derumigny2018kernel for the conditional Kendall's tau to any conditional U-statistics. To establish bounds on $\hat \theta$ for every fixed $n$, we will need some assumptions on the joint law of $(\X, \Z)$. There exists a measure $\mu$ on $(\Xc, \Ac)$ such that $\PP_{\X,\Z}$ is absolutely continuous with respect to $\mu \otimes Leb_p$, where $Leb_p$ is the Lebesgue measure on $\Rb^p$. \[condUstat:assumpt:dominating\_measure\_mu\] For every $\x \in \Xc$, $\z \mapsto f_{\X, \Z}(\x, \z)$ is differentiable almost everywhere up to the order $\alpha$. Moreover, there exists a finite constant $C_{g,f, \alpha} > 0$, such that, for every positive integers $m_1, \dots, m_k$ such that $\sum_{i=1}^k m_i = \alpha$, for every $0 \leq j_1, \dots, j_{m_i} \leq p$, $$\begin{aligned} &\int \prod_{i=1}^k \Bigg| \Big( g \big(\x_1, \dots, \x_k \big) - \EE \big[ g(\X_1, \dots, \X_k) \big| \Z_i=\z_i, \forall i=1, \dots, k \big] \Big) \\ &\hspace{0cm} \cdot \left( \frac{\partial^{m_i} f_{\X,\Z}}{\partial z_{j_1} \, \cdots \, \partial z_{j_{m_i}}} \big(\x_i,\z_i + \u_i \big) - \frac{\partial^{m_i} f_{\X,\Z}}{\partial z_{j_1} \, \cdots \, \partial z_{j_{m_i}}} \big(\x_i,\z_i \big) \right) \Bigg| d\mu(\x_1) \cdots d\mu(\x_k) \leq C_{g, f, \alpha} \prod_{i=1}^k \big|\u_i \big|_\infty, \end{aligned}$$ for every choices of $\x_1, \dots, \x_k \in \Xc$ and $\z_1, \dots, \z_k \in \Zc, \u_1, \dots, \u_k \in \Rb^p$ such that $\z_i + \u_i \in \Zc$. There exists a constant $C'_{K,\alpha}$ such that ${\sum_{m_1 + \, \cdots \, + m_k = \alpha} \binom{n}{m_{1:k}} \int \prod_{i=1}^k K(\u_i) \sum_{j_1, \dots, j_{m_i} = 1}^{p} u_{i,j_1} \dots u_{i,j_{m_i}} \prod_{i=1}^k \big|\u_i \big|_\infty d\u_1 \cdots d\u_k \leq C'_{K, \alpha}.}$ \[condUstat:assumpt:f\_XZ\_Holder\] An easy situation is the case when $g$ is bounded, i.e. when the following assumption hold. There exists a constant $C_{g}$ such that $||g||_\infty \leq C_{g} < + \infty$. \[condUstat:assumpt:g\_bounded\] When $g$ is not bounded, a weaker result can still be proved under a "conditional Bernstein" assumption. This assumption will help us to control the tail behavior of $g$ so that exponential concentration bounds are available. \[conditional Bernstein assumption\] There exists a positive function $B_{g}$ such that, for all $l \geq 1$ and $\z_1, \dots, \z_k \in \Rb^{k p}$, $\EE \Big[ \big| g(\X_1, \dots, \X_k) \big|^l \, \Big| \Z_1 = \z_1, \dots, \Z_k = \z_k \Big] \leq B_{g}(\z_1, \dots, \z_k)^l l!,$ such that $B_{g}(\Z_1, \dots, \Z_k) \leq \tilde B_{g}$ almost surely, for some finite positive constant $\tilde B_{g}$. \[condUstat:assumpt:conditional\_Bernstein\] As a shortcut notation, we will define also $B_{g, \z} := B_{g}(\z_1, \dots, \z_k)$. The following proposition is proved in \[condUstat:proof:prop:exponential\_bound\_hat\_theta\]. \[Exponential bound for the estimator $\hat \theta(\z_1, \dots, \z_k)$, with fixed $\z_1, \dots \z_k \in \Zc^k$\] Assume either Assumption \[condUstat:assumpt:g\_bounded\] or the weaker Assumption \[condUstat:assumpt:conditional\_Bernstein\]. Under Assumptions \[condUstat:assumpt:kernel\_integral\]-\[condUstat:assumpt:f\_XZ\_Holder\], for every $t,t'>0$ such that $C_{K, \alpha} h^{\alpha} / \alpha ! + t < f_{\Z, min}/2$, we have $$\begin{aligned} &\PP \Bigg( \big| \hat \theta(\z_1, \dots, \z_k) - \theta(\z_1, \dots, \z_k) \big| < \big(1 + C_3 h^{\alpha} + C_4 t \big) \times \big( C_5 h^{k + \alpha} + t' \big) \Bigg) \\ & \hspace{2cm} \geq 1 - 2 \exp \bigg( - \frac{[ n / k] t^2 h^{k p}}{ C_1 + C_2 t} \bigg) - 2 \exp \bigg( - \frac{[ n / k] t'{}^2 h^{kp}} {C_6 + C_7 t'} \bigg), \end{aligned}$$ where $C_3 := 4 f_{\Z, max}^k f_{\Z, min}^{-2k} C_{K, \alpha} / \alpha !$, $C_4 := 4 f_{\Z, max}^k f_{\Z, min}^{-2k} $ and $C_5 := C_{g, f, \alpha} C'_{K,\alpha} f_{\Z,min}^{-k} / \alpha !$. If Assumption \[condUstat:assumpt:g\_bounded\] is satisfied, the result holds with the following values: $C_6 := 2 C_{g}^2 f_{\Z,max}^k f_{\Z,min}^{-2k} ||K||_2^{2k}$, $C_7 := (8/3) C_K^k C_{g}^k f_{\Z,min}^{-k}$ ; in the case of Assumption \[condUstat:assumpt:conditional\_Bernstein\], the result holds with the following alternative values: $\tilde C_6 := 128 \big(B_{g, \z} + \tilde B_{g} \big)^2 C_K^{2k-1} f_{\Z,min}^{-2k}$, $\tilde C_7 := 2 \big(B_{g, \z} + \tilde B_{g} \big) C_K^{k} f_{\Z,min}^{-k}$. \[condUstat:prop:exponential\_bound\_hat\_theta\] Theoretical properties of the estimator hat beta {#section:theoretical_prop_beta} ================================================ Let us define the matrix $\Zb$ of dimension $|\Iknpr| \times r$ by $[\Zb']_{i,j} := \psi_j \big(\z'_{\sigma_i(1)}, \dots, \z'_{\sigma_i(k)} \big)$, where $1 \leq i \leq |\Iknpr|$, $1 \leq j \leq r$ and $\sigma_i$ is the $i$-th element of $\Iknpr$. The chosen order of $\Iknpr$ is arbitrary and has no impact in practice. In the same way, we define the vector $\Y$ of dimension $|\Iknpr|$ defined by $Y_i := \Lambda \Big(\hat \theta \big(\z'_{\sigma_i(1)}, \dots, \z'_{\sigma_i(k)} \big) \Big),$ such that the criterion (\[condUstat:def:estimator\_hat\_beta\]) is in the standard Lasso form $\hat \beta := \arg \min_{\beta \in \Rb^{r}} \Big[ ||\Y - \Zb' \beta||^2 + \lambda |\beta|_1 \Big],$ where for any vector $\v$ of size $|\Iknpr|$, its scaled norm is defined by $||\v|| := |\v|_2 / \sqrt{|\Iknpr|}$. Following @derumigny2018kendall, we define $\xi_{i,n}$, for $1 \leq i \leq |\Iknpr|$, by $\xi_{i,n} = \xi_{\sigma_i,n} := \Lambda \Big( \hat \theta \big(\z'_{\sigma_i(1)}, \dots, \z'_{\sigma_i(k)} \big) \Big) - \psibm \big(\z'_{\sigma_i(1)}, \dots, \z'_{\sigma_i(k)} \big)^T \beta^*.$ Non-asymptotic bounds on hat beta --------------------------------- We will also use the *Restricted Eigenvalue* (RE) condition, introduced by Bickel, Ritov and Tsybakov @bickel2009simultaneous. For $c_0 > 0$ and $s\in \{ 1, \dots, p \}$, it is defined as follows: $RE(s,c_0)$ **condition :** *The design matrix $\Zb'$ satisfies* $$\kappa(s, c_0) := \min \left\{ \frac{||\Zb' \delta||}{|\delta|_2} : \delta \neq 0, \, |\delta_{J_0^C}|_1 \leq c_0 |\delta_{J_0}|_1 , \, J_0 \subset \{1, \dots, r\}, \, |J_0| \leq s \right\} > 0.$$ Note that this condition is very mild, and is satisfied with a high probability for a large class of random matrices: see Bellec et al. @bellec2018slope [Section 8.1] for references and a discussion. We will also need the following regularity assumption on the function $\Lambda(\cdot)$. The function $\z\mapsto \psibm(\z)$ are bounded on $\Zc$ by a constant $C_\psibm$. Moreover, $\Lambda(\cdot)$ is continuously differentiable. Let $\Tc$ be the range of $\theta$, from $\Zc^k$ towards $\Rb$. On an open neighborhood of $\Tc$, the derivative of $\Lambda(\cdot)$ is bounded by a constant $C_{\Lambda'}$. \[condUstat:assumpt:compact\_case\] The following theorem is proved in \[condUstat:proof:thm:bound\_proba\_hat\_beta\]. Assume either Assumption \[condUstat:assumpt:g\_bounded\] or the weaker Assumption \[condUstat:assumpt:conditional\_Bernstein\]. Suppose that Assumptions \[condUstat:assumpt:kernel\_integral\]-\[condUstat:assumpt:f\_XZ\_Holder\] and \[condUstat:assumpt:compact\_case\] hold and that the design matrix $\Zb'$ satisfies the $RE(s,3)$ condition. Choose the tuning parameter as $\lambda = \gamma t$, with $\gamma \geq 4$ and $t>0$, and assume that we choose $h$ small enough such that $$\begin{aligned} h &\leq \min \bigg( \Big( \frac{f_{\Z, min} \alpha !} {4 \, C_{K, \alpha}} \Big)^{1/\alpha} \; , \; \Big( \frac{t}{2 C_5 C_8} \Big)^{1/(k+\alpha)} \bigg) \label{condUstat:cond:h_1_2}, \end{aligned}$$ where $C_8 := C_{\psibm} C_{\Lambda'} \big(1 + C_4 f_{\Z, min} / 2 \big)$. Then, we have $$\begin{aligned} &\PP \Big( ||\Zb'(\hat \beta - \beta^*)|| \leq \dfrac{4(\gamma+1) t \sqrt{s}}{\kappa(s,3)} \text{ and } |\hat \beta - \beta^*|_q \leq \dfrac{4^{2/q}(\gamma+1) t s^{1/q} }{\kappa^2(s,3)}, \text{ for every } 1 \leq q \leq 2 \Big) \nonumber \\ &\hspace{1cm} \geq 1 - 2 \sum_{\sigma \in \Iknpr} \Bigg[ \exp \bigg( - \frac{[ n / k] f_{\Z, min}^2 h^{k p}} { 16 C_1 + 4 C_2 f_{\Z, min} } \bigg) + \exp \bigg( - \frac{[ n / k] t^2 h^{kp}} {4 C_8^2 C_{6,\sigma} + 2 C_8 C_{7,\sigma} t} \bigg) \Bigg]. \label{condUstat:eq:bound_proba_hat_beta} \end{aligned}$$ If Assumption \[condUstat:assumpt:g\_bounded\] is satisfied, the result holds with $C_{6,\sigma}$ and $C_{7,\sigma}$ constant, respectively to $C_6$ and $C_7$ defined in Proposition \[condUstat:prop:exponential\_bound\_hat\_theta\]. In the case of Assumption \[condUstat:assumpt:conditional\_Bernstein\], the result holds with the following alternative values: $C_{6,\sigma} := 128 \big(B_{g}(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)}) + \tilde B_{g} \big)^2 C_K^{2k} f_{\Z,min}^{-2k}$ and $C_{7,\sigma} := 2 \big(B_{g}(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)}) + \tilde B_{g} \big) C_K^{k} f_{\Z,min}^{-k}$. \[condUstat:thm:bound\_proba\_hat\_beta\] The latter theorem gives some bounds that hold in probability for the prediction error $||\Zb'(\hat \beta - \beta^*)||_{n'}$ and for the estimation error $|\hat \beta - \beta^*|_q$ with $1 \leq q \leq 2$ under the specification (\[model:lambda\_cond\_theta\_Z\]). Note that the influence of $n'$ and $r$ is hidden through the Restricted Eigenvalue number $\kappa(s,3)$. Asymptotic properties of hat beta when n to infty and for fixed n prime {#sec:Asymp_n_fixed_nprime} ----------------------------------------------------------------------- In this part, $n'$ is still assumed to be fixed and we state the consistency and the asymptotic normality of $\hat\beta$ as $n \to \infty$. As above, we adopt a fixed design: the $\z'_i$ are arbitrarily fixed or, equivalently, our reasoning are made conditionally on the second sample. In this section, we follow Section 3 of Derumigny and Fermanian @derumigny2018kendall which gives similar results for the conditional Kendall's tau, a particular conditional U-statistic of order $2$. Proofs are identical and therefore omitted. Nevertheless, asymptotic properties of $\hat \beta$ require corresponding results on the first-step estimators $\hat \theta$. These results are state in Stute @stute1991conditional and recalled for convenience in \[section:asymptotic\_result\_theta\_stute\]. For $n, n' > 0$, denote by $\hat \beta_{n, n'}$ the estimator (\[condUstat:def:estimator\_hat\_beta\]) with $h = h_{n}$ and $\lambda = \lambda_{n, n'}$. We have $\hat \beta_{n, n'} = \arg \min_{\beta \in \Rb^{p'}} \GG_{n,n'}(\beta)$, where $$\begin{aligned} \GG_{n,n'}(\beta) &:= \frac{2 (n'-k)!}{n'!} \sum_{\sigma \in \Iknpr} \xi_{\sigma,n} \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big)^T (\beta^* - \beta) \nonumber \\ &+ \frac{(n'-k)!}{n'!} \sum_{\sigma \in \Iknpr} \big\{ \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big)^T (\beta^* - \beta) \big\}^2 + \lambda_{n, n'} |\beta|_1. \label{condUstat:def:process_GG} \end{aligned}$$ \[lemma:beta\_process\_GG\] \[Consistency of $\hat \beta$\] Under Assumption \[condUstat:assumpt:stute\_consistency\], if $n'$ is fixed and $\lambda = \lambda_{n, n'} \to \lambda_0 $, then, given $\z'_1, \ldots, \z'_{n'}$ and as $n$ tends to the infinity, $\hat \beta_{n, n'} \inprobto \beta^{**} := \inf_\beta \GG_{\infty,n'} (\beta),$ where $$\begin{aligned} \GG_{\infty,n'} (\beta) := \frac{1}{n'} \sum_{\sigma \in \Iknpr} \Big( \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big)^T (\beta^* - \beta) \Big)^2 + \lambda_0 |\beta |_1. \end{aligned}$$ In particular, if $\lambda_0=0$ and $< \{ \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big) : \sigma \in \Iknpr \} > \, = \Rb^{r}$, then $\hat \beta_{n, n'} \inprobto \beta^*$. \[Asymptotic law of the estimator\] \[condUstat:thm:WeakConvLasso\] Under Assumption \[condUstat:assumpt:stute\_asymptotic\_normality\], and if $\lambda_{n, n'} (n h_{n,n'}^{p})^{1/2}$ tends to $ \ell $ when $n\rightarrow \infty$, we have $(n h_{n,n'}^{p})^{1/2} (\hat \beta_{n, n'} - \beta^*) \indistrto \u^* := \arg \min_{\u \in \Rb^{r}} \FF_{\infty, n'}(\u),$ given $\z'_1,\ldots, \z'_{n'}$, where $$\begin{aligned} \FF_{\infty, n'}(\u) &:= \frac{2 (n'-k)!}{n'!} \sum_{\sigma \in \Iknpr} \sum_{j=1}^{r} W_{\sigma} \psi_j \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big) u_{j} + \frac{(n'-k)!}{n'!} \sum_{\sigma \in \Iknpr} \left( \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big)^T \u \right)^2 \\ &+ \ell \sum_{i=1}^{r} \big( |u_i| \1_{\{\beta_i^*=0\}} + u_i\sgn(\beta_i^*) \1_{\{\beta_i^* \neq 0\}} \big) , \end{aligned}$$ with $\W = (W_\sigma)_{\sigma \in \Iknpr} \sim \Nc \left(0, \tilde \HH \right)$ where $$\begin{aligned} [\tilde \HH]_{\sigma, \varsigma} & := \sum_{j,l = 1}^k \1_{\left\{\z'_{\sigma(j)} = \z'_{\varsigma(l)}\right\}} \frac{||K||_2^2}{f_\Z \left( \z'_{\sigma(j)} \right)} \Lambda' \bigg(\theta \left(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \right) \bigg) \Lambda' \bigg(\theta \left(\z'_{\varsigma(1)}, \dots, \z'_{\varsigma(k)} \right) \bigg) \\ & \cdot \bigg(\tilde \theta_{j,l} \left(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} , \z'_{\varsigma(1)}, \dots, \z'_{\varsigma(k)} \right) - \theta \left(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \right) \theta \left(\z'_{\varsigma(1)}, \dots, \z'_{\varsigma(k)} \right) \bigg), \end{aligned}$$ and $\tilde \theta_{j,l}$ is as defined in Equation (\[condUstat:eq:def:tilde\_theta\_jl\]). Moreover, $\lim\sup_{\protect n \to \infty} \PP\left( \Sc_n= \Sc \right) = c < 1, $ where $\Sc_n := \{j:\hat\beta_j \neq 0\}$ and $\Sc := \{j:\beta_j \neq 0\}$. A usual way of obtaining the oracle property is to modify our estimator in an "adaptive" way. Following Zou @zou2006, consider a preliminary "rough" estimator of $\beta^*$, denoted by $\tilde \beta_n$, or more simply $\tilde\beta$. Moreover $\nu_n (\tilde \beta_n - \beta^*)$ is assumed to be asymptotically normal, for some deterministic sequence $(\nu_n)$ that tends to the infinity. Now, let us consider the same optimization program as in (\[condUstat:def:estimator\_hat\_beta\]) but with a random tuning parameter given by $ \lambda_{n,n'} := \tilde\lambda_{n,n'}/ |\tilde{\beta}_n|^\delta$, for some constant $\delta >0$ and some positive deterministic sequence $(\tilde\lambda_{n,n'})$. The corresponding adaptive estimator (solution of the modified Equation (\[condUstat:def:estimator\_hat\_beta\])) will be denoted by $\check{\beta}_{n,n'}$, or simply $\check{\beta}$. Hereafter, we still set $\Sc_n=\{j : \check{\beta}_j \neq 0\}$. \[Asymptotic law of the adaptive estimator of $\beta$\] Under Assumption \[condUstat:assumpt:stute\_asymptotic\_normality\], if $\tilde\lambda_{n, n'} (n h_{n,n'}^{p})^{1/2} \rightarrow \ell\geq 0 $ and $\tilde\lambda_{n, n'} (n h_{n,n'}^p)^{1/2} \nu_n^\delta \rightarrow \infty $ when $n\rightarrow \infty$, we have $(n h_{n,n'}^{p})^{1/2} (\check \beta_{n, n'} - \beta^*)_{\Sc} \indistrto \u_{\Sc}^{**} := \underset{\u_{\Sc} \in \Rb^{s}}{\arg \min} \, \check\FF_{\infty, n'}(\u_{\Sc}),$ where $$\begin{aligned} &\check\FF_{\infty, n'}(\u_{\Sc}) := \frac{2 (n'-k)!}{n'!} \sum_{\sigma \in \Iknpr} \sum_{j\in \Sc} W_\sigma \psi_j (\z'_i) u_{j} + \frac{(n'-k)!}{n'!} \sum_{\sigma \in \Iknpr} \Big( \sum_{j\in \Sc} \psi_j (\z'_i) u_{j} \Big)^2 + \ell \sum_{i\in \Sc} \frac{u_i}{|\beta_i^*|^\delta} \sgn(\beta_i^*) , \end{aligned}$$ and $\W = (W_\sigma)_{\sigma \in \Iknpr} \sim \Nc \big(0, \tilde \HH \big).$ Moreover, when $\ell=0$, the oracle property is fulfilled: $ \PP\left( \Sc_n= \Sc \right) \rightarrow 1$ as $n \to \infty$. \[condUstat:thm:WeakConvLassoAdaptive\] Asymptotic properties of hat beta jointly in n,n prime ------------------------------------------------------ Now, we consider the framework in which both $n$ and $n'$ are going to infinity, while the dimensions $p$ and $r$ stay fixed. We now provide a consistency result for $\hat \beta_{n,n'}$. \[Consistency of $\hat \beta_{n,n'}$, jointly in $(n,n')$\] Assume that Assumptions \[condUstat:assumpt:kernel\_integral\]-\[condUstat:assumpt:f\_XZ\_Holder\], \[condUstat:assumpt:conditional\_Bernstein\] and \[condUstat:assumpt:compact\_case\] are satisfied. Assume that $\sum_{\sigma \in \Iknpr} \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big) \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big)^T/n'$ converges to a matrix $M_{\psi,\z'}$, as $n' \to \infty$. Assume that $\lambda_{n, n'} \to \lambda_{0}$ and $n' \exp ( - A n h^{2 k p}) \to 0$ for every $A>0$, when $(n,n') \to \infty$. Then $\hat \beta_{n,n'} \inprobto \arg \min_{\beta \in \Rb^{r}} \GG_{\infty,\infty}(\beta),$ as $(n,n') \to \infty,$ where $\GG_{\infty,\infty}(\beta):= (\beta^* - \beta) M_{\psi,\z'} (\beta^* - \beta)^T + \lambda_{0} |\beta|_1$. Moreover, if $\lambda_0 = 0$ and $M_{\psi,\z'}$ is invertible, then $\hat \beta_{n,n'}$ is consistent and tends to the true value $\beta^*$. \[condUstat:thm:consistency\_hatBeta\_n\_nprime\] Note that, since the sequence $(\z'_i)$ is deterministic, we only assume the convergence of the sequence of deterministic matrices $\sum_{\sigma \in \Iknpr} \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big) \psibm \big(\z'_{\sigma(1)}, \dots, \z'_{\sigma(k)} \big)^T/n'$ in $\Rb^{r^2}$. Moreover, if the "second subset" $(\z'_i)_{i=1,\ldots,n'}$ were a random sample (drawn along the law $\PP_{\Z}$), the latter convergence would be understood "in probability". And if $\PP_{\Z}$ satisfies the identifiability condition (Proposition \[condUstat:prop:identifiability\_condition\]), then $M_{\psi,\z'}$ would be invertible and $\hat \beta_{n,n'}\to \beta^*$ in probability. Now, we want to go one step further and derive the asymptotic law of the estimator $\hat \beta_{n,n'}$. \[Asymptotic law of $\hat \beta_{n,n'}$, jointly in $(n,n')$\] Under Assumptions \[condUstat:assumpt:kernel\_integral\]-\[condUstat:assumpt:dominating\_measure\_mu\] and under Assumption \[condUstat:assumpt:asymptNorm\_joint\], we have $$(n \times n' \times h_{n,n'}^{p})^{1/2} (\hat \beta_{n, n'} - \beta^*) \indistrto \Nc(0, \tilde V_{as}),$$ where $\tilde V_{as} := V_1^{-1} V_2 V_1^{-1}$, $V_1$ is the matrix defined in Assumption \[condUstat:assumpt:asymptNorm\_joint\](iv), and $V_2$ in Assumption \[condUstat:assumpt:asymptNorm\_joint\](v). \[condUstat:thm:weak\_conv\_doubleAsympt\] This theorem is proved in \[condUstat:proof:thm:weak\_conv\_doubleAsympt\] where we state Assumption \[condUstat:assumpt:asymptNorm\_joint\]. Applications and examples {#condUstats:sec:applications} ========================= Following Example 4.4 in Stute @stute1991conditional, we consider the function $g(x_1, x_2) := \1 \{ x_1 \leq x_2 \}$, with $k=2$. In this case $\theta(\z_1, \z_2) = \PP( X_1 \leq X_2 | \Z_1 = \z_1, \Z_2 = \z_2)$. The parameter $\theta(\z_1, \z_2)$ quantifies the probability that the quantity of interest $X$ be smaller if we knew that $\Z = \z_1$ than if we knew that $\Z = \z_2$. To illustrate our methods, we choose a simple example, with the Epanechnikov kernel, defined by $K(x) := (3/4)(1-u^2)\1{|u| \leq 1}$. It is a kernel of order $\alpha = 2$, with $\int K^2 = 3/5$. Assumption \[condUstat:assumpt:kernel\_integral\] is then satisfied with $C_K := 3/4$. Fix $p=1$, $\Zc = [-1,1]$, $\Xc = \Rb$, $f_Z(z) = \phi(z) \1 \{|z| \leq 1 \} / (1 - 2 \Phi(-1))$, where $\Phi$ and $\phi$ are respectively the cdf and the density of the standard Gaussian distribution and $X|Z=z \sim \Nc(z, 1)$, for every $z \in \Zc$. Assumption \[condUstat:assumpt:bound\_int\_deriv\_fZ\] is then satisfied with $C_{K,\alpha} = 0.2 $. Assumption \[condUstat:assumpt:f\_Z\_max\] is easily satisfied with $f_{Z,\max} = 1 / \big( \sqrt{2 \pi} (1-2\Phi(-1)) \big) \leq 0.59$. Therefore, we can apply Lemma \[lemma:bound\_Nk\_fk\]. We compute the constants $C_1 := 2 f_{\Z, max}^k ||K||_2^{2k} = 2 \times 0.59^2 \times (3/5)^2 \leq 0.26$ and $C_2 := (4/3) C_K^k = (4/3) \times (3/4)^2 = 3/4$. Therefore, for any $n \geq 0$, $h, t > 0$, $z_1, z_2 \in \Zc$, we have $$\begin{aligned} \PP \bigg( \big| N_2(z_1, z_2) &- f_{Z}(z_1) f_{Z}(z_2) \big| \leq 0.1 h^{\alpha} + t \bigg) \geq 1 - 2 \exp \bigg( - \frac{[ n / 2] t^2} {0.26 h^2 + 0.75 h^2 t} \bigg),\end{aligned}$$ Assumption \[condUstat:assumpt:f\_Z\_min\] is satisfied with $f_{Z, \min} = \phi(1) / (1 - 2 \Phi(-1)) > 0.35$, so that we can apply Corollary \[cor:probaTheta\_Z\_valid\]. Therefore, the estimator $\hat \theta(z_1, z_2)$ exists with probability greater than $1 - 2 \exp \bigg( - \frac{(n-1) h^2 \big( 0.35 - 0.1 h^2 \big)^2} {0.52 + 1.5 \times \big( 0.35 - 0.1 h^2 \big) } \bigg).$ Note that this probability is greater than $0.99$ as soon as $n \geq 3 \big( 0.52 + 1.5 \times ( 0.35 - 0.1 h^2 ) \big) / \big(h^2 ( 0.35 - 0.1 h^2 )^2 \big)$. For example, with $h=0.2$, it means that the estimator $\hat \theta(z_1, z_2)$ exists with a probability greater than $99\%$ as soon as $n$ is greater than $651$. We list below other possible examples of applications. Conditional moments constitute also a natural class of U-statistics. They include the conditional variance ($p_{\X} = 1$, $k=2$, $g(X_1, X_2)=X_1^2 - X_1 \cdot X_2$) and the conditional covariance ($p_{\X} = 2$, $k=2$, $g(\X_1, \X_2) := X_{1,1} \times X_{2,1} - X_{1,1} \times X_{2,2}$). The conditional variance gives information about the volatility of $X$ given the variable $\Z$. Conditional covariances can be used to describe how the dependence moves as a function of the conditioning variables $\Z$. Higher-order conditional moments (skewness, kurtosis, and so on) can also be estimated by higher-order conditional U-statistics, and they described respectively how the asymmetry and the behavior of the tails of $X$ change as function of $Z$. Gini's mean difference, an indicator of dispersion, can also be used in this framework. Formally, it is defined as the U-statistic with $p_{\X} = 1$, $k=2$ and $g(X_1, X_2) := |X_1 - X_2|$. Its conditional version describes how two variables are far away, on average, given their conditioning variables $\Z$. for example, $X$ could be the income of an individual, $\Z$ could be the position of its home, and $\theta(\z_1, \z_2)$ represent the average inequality between the income of two persons, one at point $\z_1$ and the other at point $\z_2$. Other conditional dependence measures can also be written as conditional U-statistics, see e.g. Example 1.1.7 of Koroljuk and Borovskisch @koroljuk1994theory. They show how a U-statistic of order $k=5$ can be used to estimated the dependence parameter $$\theta = \iint \big(F_{1,2}(x,y) - F_{1,2}(x,\infty) F_{1,2}(\infty,y)\big) dF_{1,2}(x,y).$$ In our framework, we could consider a conditional version, given by $$\theta(\z_1, \z_2) = \iint \big(F_{1,2|\Z=\z}(x,y) - F_{1,2|\Z=\z}(x,\infty) F_{1,2|\Z=\z}(\infty,y)\big) dF_{1,2|\Z=\z}(x,y),$$ where $\X$ is of dimension $p_{\X} = 2$. **Acknowledgements:** This work is supported by the GENES and by the Labex Ecodec under the grant ANR-11-LABEX-0047 from the French Agence Nationale de la Recherche. The author thanks Professor Jean-David Fermanian for helpful comments and discussions. Notations ========= In the proofs, we will use the following shortcut notation. First, $\x_{1:k}$ denotes the $k$-tuple ${(\x_1, \dots, \x_k) \in \Xc^k}$. Similarly, for a function $\sigma$, $\sigma(1:k)$ denotes the tuple $(\sigma(1), \dots, \sigma(k))$, and $\X_{\sigma(1:k)}$ is the $k$-tuple $(\X_{\sigma(1)}, \dots, \X_{\sigma(k)})$. For any variable $Y$ and any collection of given points $(\z_1, \dots \z_k)$, the conditional expectation $\EE[Y | \Z_{1:k} = \z_{1:k}]$ denotes $\EE[Y | \Z_1 = \z_1, \dots, \Z_k = \z_k]$. We denote by $\int \phi(\z_{1:k}) d\z_{1:k}$ the integral $\int \phi(\z_1, \dots, \z_k) d\z_1 \cdots d\z_k$ for any integrable function $\phi: \Rb^{k \times p} \to \Rb$, and by $\int g(\x_{1:k}) d\mu^{\otimes k}(\x_{1:k})$ the integral $\int g(\z_1, \dots, \z_k) d\mu(\x_1) \cdots d\mu(\x_k)$ for any $\mu$-integrable function $g: \Xc^k \to \Rb$. Asymptotic results for hat theta {#section:asymptotic_result_theta_stute} ================================ The estimator $\hat \theta(\z_1, \dots, \z_k)$ has been first studied by Stute (1991) @stute1991conditional. He proved the consistency and the asymptotic normality of $\hat \theta(\z_1, \dots, \z_k)$. We recall his results. (i) $h_n \to 0$ and $n h_n^{p} \to \infty$ ; (ii) $K(\z) \geq C_{K,1} \1_{\{ |\z|_\infty \leq \, C_{K,2}\}}$ for some $C_{K,1}, \, C_{K,2} > 0$ ; (iii) there exists a decreasing function $H:\Rb_+ \to \Rb_+$, and positive constants $c_1, c_2$ such that $H(t) {\underset{t \to \infty}{=}} o(t^{-1})$ and $c_1 H(|\z|_\infty) \leq K(\z) \leq c_2 H(|\z|_\infty)$. \[condUstat:assumpt:stute\_consistency\] \[Consistency of $\hat \theta$, Theorem 2 in Stute @stute1991conditional\] Under Assumption \[condUstat:assumpt:stute\_consistency\], for $\PP_\Z^{\otimes k}$-almost all $(\z_1, \dots, \z_k)$, $\hat \theta(\z_1, \dots, \z_k) \inprobto \theta(\z_1, \dots, \z_k)$ as $n \to \infty$. \[condUstat:prop:consistency\_hat\_Tau\] We introduce now a few more notations to state the asymptotic normality of $\hat \theta$. For $1 \leq j,l,m \leq k$ and $\z_1, \dots, \z_{3k} \in \Zc^{3k}$, define $$\begin{aligned} \theta_{j,l}&(\z_1, \dots, \z_k) := \EE \big[ g(\X_1, \dots, \X_{j-1}, \X, \X_{j+1}, \dots, \X_k) g(\X_{k+1}, \dots, \X_{k+l-1}, \X, \X_{k+l+1}, \dots, \X_{2k}) \nonumber \\ &\big| \Z = \z_j \; ; \; \Z_i=\z_i, \forall i=1, \dots, k, i \neq j \; ; \; \Z_{k+i}=\z_i, \forall i=1, \dots, k, i \neq l \big], \nonumber \\ \tilde \theta_{j,l}&(\z_1, \dots, \z_{2k}) := \EE \big[ g(\X_1, \dots, \X_{j-1}, \X, \X_{j+1}, \dots, \X_k) g(\X_{k+1}, \dots, \X_{k+l-1}, \X, \X_{k+l+1}, \dots, \X_{2k}) \nonumber \\ &\big| \Z = \z_j \; ; \; \Z_i=\z_i, \forall i=1, \dots, 2k, i \notin \{ j, k+l \} \big]. \label{condUstat:eq:def:tilde_theta_jl} \\ \theta_{j,l,m}&(\z_1, \dots, \z_{3k}) := \EE \big[ g(\X_1, \dots, \X_{j-1}, \X, \X_{j+1}, \dots, \X_k) \nonumber \\ &g(\X_{k+1}, \dots, \X_{k+l-1}, \X, \X_{k+l+1}, \dots, \X_{2k}) g(\X_{2k+1}, \dots, \X_{2k+m-1}, \X, \X_{2k+m+1}, \dots, \X_{3k}) \nonumber \\ &\big| \Z = \z_j \; ; \; \Z_i=\z_i, \forall i=1, \dots, 3k, i \notin \{ j, k+l, 2k+m \} \big]. \nonumber\end{aligned}$$ (i) $h_n \to 0$ and $n h_n^{p} \to \infty$ ; (ii) $K$ is symmetric at $0$, bounded and compactly supported ; (iii) $\theta_{j,l}$ is continuous at $(\z_1, \dots, \z_k)$ for all $1 \leq j,l \leq k$ ; (iv) $\theta$ is two times continuously differentiable in a neighborhood of $(\z_1, \dots, \z_k)$ ; (v) $\theta_{j,l,m}$ is bounded in a neighborhood of $(\z_1, \dots, \z_k, \z_1, \dots, \z_k, \z_1, \dots, \z_k) \in \Zc^{3k}$, for all $1 \leq j,l,m \leq k$ ; (vi) $f_\Z$ is twice differentiable in neighborhoods of $\z_i, 1 \leq i \leq k.$ \[condUstat:assumpt:stute\_asymptotic\_normality\] \[Asymptotic normality of $\hat \theta$, Corollary 2.4 in Stute @stute1991conditional\] Under Assumption \[condUstat:assumpt:stute\_asymptotic\_normality\], we have $\sqrt{n h_n^{p}} \big(\hat \theta(\z_1, \dots, \z_k) - \theta(\z_1, \dots, \z_k) \big) \indistrto \Nc(0,\rho^2),$\ where $\rho^2 := \sum_{j,l = 1}^k \1_{\{\z_j = \z_l\}} \big(\theta_{j,l}(\z_1, \dots, \z_k) - \theta^2(\z_1, \dots, \z_k) \big) ||K||_2^2 / f_\Z(\z_j)$. Moreover, let $N$ be a positive integer, and $\big(\z_1^{(1)}, \dots, \z_k^{(1)}, \dots, \z_1^{(N)}, \dots, \z_k^{(N)} \big) \in \Zc^{k \times N}$. Then under similar regularity conditions, $\sqrt{n h_n^{p}} \big( \hat \theta(\z_1^{(i)}, \dots, \z_k^{(i)}) - \theta(\z_1^{(i)}, \dots, \z_k^{(i)})\big)_{i=1, \dots, N} \indistrto \Nc(0,\HH)$, where, for $1 \leq \tilde j, \tilde l \leq N$, $$[\HH]_{\tilde j, \tilde l} := \sum_{j,l = 1}^k \1_{\left\{\z_j^{(\tilde j)} = \z_l^{(\tilde l)}\right\}} \bigg(\tilde \theta_{j,l} \left(\z_1^{(\tilde j)}, \dots, \z_k^{(\tilde j)} , \z_1^{(\tilde l)}, \dots, \z_k^{(\tilde l)} \right) - \theta \left(\z_1^{(\tilde j)}, \dots, \z_k^{(\tilde j)} \right) \theta \left(\z_1^{(\tilde l)}, \dots, \z_k^{(\tilde l)} \right) \bigg) \frac{||K||_2^2}{f_\Z \left(\z_j^{(\tilde j)} \right)}.$$ \[condUstat:prop:asympt\_norm:hat\_theta\] Note that the second part of Proposition \[condUstat:prop:asympt\_norm:hat\_theta\] above is a consequence of the first one. Indeed, for every $(c_1, \dots, c_{N}) \in \Rb^{N}$, we can define $\theta \big(\z_1^{(1)}, \dots, \z_k^{(1)}, \dots, \z_1^{(N)}, \dots, \z_k^{(N)} \big) := \sum_{\tilde i = 1}^{N} c_{\tilde i} \theta(\z_1^{(\tilde i)}, \dots, \z_k^{(\tilde i)})$ and corresponding versions of $g$, $\hat \theta$ and $\rho^2$. Finally, the conclusion follows from the Cramér-Wold device. Finite distance proofs for hat theta and hat beta ================================================= For convenience, we recall Berk's (1970) inequality (see Theorem A in Serfling @serfling1980approximation [p.201]). Note that, if $m=1$, this reduces to Bernstein's inequality. Let $k > 0$, $n \geq k$, $\X_1, \dots, \X_n$ i.i.d. random vectors with values in a measurable space $\Xc$ and $g: \Xc^k \to [a, b]$ be a real bounded function. Set $\theta := \EE[g(\X_{1:k})]$ and $\sigma^2 := Var[g(\X_{1:k})]$. Then, for any $t > 0$, $$\begin{aligned} \PP \left( \binom{n}{k}^{-1} \sum_{\sigma \in \Iknup} g \left(\X_{\sigma(1:k)} \right) - \theta \geq t \right) \leq \exp \bigg( - \frac{[ n / k] t^2}{2 \sigma^2 + (2/3) (b-\theta) t} \bigg), \end{aligned}$$ where $\Ikn$ is the set of bijective functions from $\{1, \dots, k\}$ to $\{1, \dots, n\}$ and $\Iknup$ is the subset of $\Ikn$ made of increasing functions. \[lemma:bernstein\_U\_stat\_sym\] Note that $g$ does not need to be symmetric for this bound to hold. Indeed, if $g$ is not symmetric, we can nonetheless apply this lemma to the symmetrized version $\tilde g$ defined as $\tilde g(\x_{1:k}) := (k!)^{-1} \sum_{\sigma \in {{\mathfrak{I}_{k,k}}}} g(\x_{\sigma(1:k)}),$ and we get the result. Proof of Lemma \[lemma:bound\_Nk\_fk\] {#condUstat:proof:lemma:bound_Nk_fk} -------------------------------------- We decompose the quantity to bound into a stochastic part and a bias as follows: $$\begin{aligned} N_k(\z_{1:k}) - \prod_{i=1}^k f_{\Z}(\z_i) = \big( N_k(\z_{1:k}) - \EE[N_k(\z_{1:k})] \big) + \big( \EE[N_k(\z_{1:k})] - \prod_{i=1}^k f_{\Z}(\z_i) \big).\end{aligned}$$ We first bound the bias. $$\begin{aligned} \bigg| \EE \big[N_k(\z_{1:k}) \big] - \prod_{i=1}^k f_{\Z}(\z_i) \bigg| &= \bigg| \EE \Big[ \binom{n}{k}^{-1} \sum_{\sigma \in \Ikn} \prod_{i=1}^k K_h \big(\Z_{\sigma(i)}-\z_i \big) \Big] - \prod_{i=1}^k f_{\Z}(\z_i) \bigg| \\ &= \bigg| \int \Big( \prod_{i=1}^k f_{\Z}(\z_i + h \u_i) - \prod_{i=1}^k f_{\Z}(\z_i) \Big) \prod_{i=1}^k K ( \u_i ) d\u_i \bigg| \\ &= \bigg| \int \Big(\phi_{\z, \u}(1) - \phi_{\z, \u}(0) \Big) \prod_{i=1}^k K ( \u_i ) d\u_i \bigg|,\end{aligned}$$ where $\phi_{\z, \u}(t) := \prod_{j=1}^k f_{\Z} \big( \z_i + t h \u_j \big)$ for $t \in [-1,1]$. Note that this function has at least the same regularity as $f_\Z$, so it is $\alpha$-differentiable, and by a Taylor-Lagrange expansion, we get $$\begin{aligned} \bigg| &\EE[N_k(\z_{1:k})] - \prod_{i=1}^k f_{\Z}(\z_i) \bigg| = \bigg| \int_{\Rb^{k p}} \bigg(\sum_{i=1}^{\alpha-1} \frac{1}{i!} \phi_{\z, \u}^{(i)}(0) + \frac{1}{\alpha !}\phi_{\z, \u}^{(\alpha)} (t_{\z, \u}) \bigg) \prod_{i=1}^k K ( \u_i ) d\u_i \bigg|.\end{aligned}$$ For $l>0$, we have $$\begin{aligned} \phi_{\z, \u}^{(l)}(0) &= \sum_{m_1 + \, \cdots \, + m_k = l} \binom{\alpha}{m_{1:k}} \prod_{i=1}^k \frac{\partial^{m_i} \Big( f_{\Z} \big(\z_i + ht \u_i \big) \Big)}{\partial t^{m_i}}(0) \\ &= \sum_{m_1 + \, \cdots \, + m_k = l} \binom{\alpha}{m_{1:k}} \prod_{i=1}^k \sum_{j_1, \dots, j_{m_i} = 1}^{p} h^{m_i} u_{i,j_1} \dots u_{i,j_{m_i}} \frac{\partial^{m_i} f_{\Z}}{\partial z_{j_1} \, \cdots \, \partial z_{j_{m_i}}} \big(\z_i + t_{\z, \u} h \u_i \big),\end{aligned}$$ where $\binom{\alpha}{m_{1:k}} := \alpha! / \big( \prod_{i=1}^k (m_i!) \big)$ is the multinomial coefficient. Using Assumption \[condUstat:assumpt:kernel\_integral\], for every $i=1, \dots, \alpha - 1$, we get $\int K(\u_1) \cdots K(\u_k) \phi_{\z, \u}^{(i)}(0) d\u_1 \cdots d\u_k = 0$. Therefore, only the last term remains and we have $$\begin{aligned} \bigg| &\EE[N_k(\z_{1:k})] - \prod_{i=1}^k f_{\Z}(\z_i) \bigg| = \bigg| \int \bigg( \frac{1}{\alpha !}\phi_{\z, \u}^{(\alpha)} (t_{\z, \u}) \bigg) \prod_{i=1}^k K ( \u_i ) d\u_i \bigg| \leq \frac{C_{K, \alpha}}{\alpha!} h^{\alpha},\end{aligned}$$ using Assumption \[condUstat:assumpt:bound\_int\_deriv\_fZ\]. Second, we bound the stochastic part. We have $$\begin{aligned} N_k(\z_{1:k}) - \EE[N_k(\z_{1:k})] &= \frac{k!(n-k)!}{n!} \sum_{\sigma \in \Iknup} \prod_{i=1}^k K_h \big(\Z_{\sigma(i)}-\z_i \big) - \prod_{i=1}^k \EE[K_h \big(\Z_{i}-\z_i \big)].\end{aligned}$$ Then, we can apply Lemma \[lemma:bernstein\_U\_stat\_sym\] to the function $g$ defined by $g(\tilde \z_1, \dots, \tilde \z_k) := \prod_{i=1}^k K_h \big(\tilde \z_i - \z_i \big)$. Here, we have $b = -a = h^{-k p} C_K^k$, and $$\begin{aligned} Var \big[ g(\Z_1, \dots, \Z_k)^2 \big] \leq \EE \big[ g(\Z_1, \dots, \Z_k)^2 \big] = \prod_{i=1}^k \EE \big[ K_h \big( \Z_i - \z_i \big)^2 \big] \leq h^{-k p} f_{\Z, max}^k ||K||_2^{2k}.\end{aligned}$$ Finally, we get $$\begin{aligned} \PP \left( \binom{n}{k}^{-1} N_k(\z_{1:k}) - \EE[N_k(\z_{1:k})] \geq t \right) \leq \exp \bigg( - \frac{[ n / k] t^2}{2 h^{-k p} f_{\Z, max}^k ||K||_2^{2k} + (4/3) h^{-k p} C_K^k t} \bigg),\end{aligned}$$ $\Box$ Proof of Proposition \[condUstat:prop:exponential\_bound\_hat\_theta\] {#condUstat:proof:prop:exponential_bound_hat_theta} ---------------------------------------------------------------------- We have the following decomposition $$\begin{aligned} | &\hat \theta(\z_{1:k}) - \theta(\z_{1:k}) | \\ &= \bigg| N_k(\z_{1:k})^{-1} \frac{(n-k)!}{n!} \sum_{\sigma \in \Ikn} \prod_{i=1}^k K_h \big(\Z_{\sigma(i)}-\z_i \big) \Big( g(\X_{\sigma(1:k)}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k}=\z_{1:k} \big] \Big) \bigg| \\ &= \frac{\prod_{i=1}^k f_{\Z}(\z_i)}{N_k(\z_1, \dots, \z_k)} \cdot \bigg| \frac{(n-k)!}{n!} \sum_{\sigma \in \Ikn} \prod_{i=1}^k \frac{K_h \big(\Z_{\sigma(i)}-\z_i \big)}{f_{\Z}(\z_i)} \Big( g(\X_{\sigma(1:k)}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k}=\z_{1:k} \big] \Big) \bigg| \\ &=: \frac{\prod_{i=1}^k f_{\Z}(\z_i)}{N_k(\z_1, \dots, \z_k)} \; \cdot \bigg| \sum_{\sigma \in \Ikn} S_{\sigma} \bigg|.\end{aligned}$$ The conclusion will follow from the next three lemmas, where we will bound separately $\prod_{i=1}^k f_{\Z} / N_k$, the bias term $\big| \sum_{\sigma \in \Ikn} \EE[S_{\sigma}] \big|$ and the stochastic component $\big| \sum_{\sigma \in \Ikn} \big(S_{\sigma} - \EE[S_{\sigma}] \big) \big|$. \[Bound for $\prod_{i=1}^k f_{\Z}(\z_i)/N_k$\] Under Assumptions \[condUstat:assumpt:kernel\_integral\], \[condUstat:assumpt:bound\_int\_deriv\_fZ\], \[condUstat:assumpt:f\_Z\_max\], and \[condUstat:assumpt:f\_Z\_min\] and if for some $t > 0$, $C_{K, \alpha} h^{\alpha} / \alpha ! + t < f_{\Z, min}^k/2$, we have $$\begin{aligned} &\PP \Bigg( \bigg| \frac{1}{N_k(\z_{1:k})} - \frac{1}{\prod_{i=1}^k f_{\Z}(\z_i)} \bigg| \leq \frac{4}{f_{\Z, min}^{2k}} \bigg( \frac{C_{K, \alpha} h^{\alpha}}{\alpha !} + t \bigg) \Bigg) \\ &\hspace{6cm} \geq 1 - 2 \exp \bigg( - \frac{[ n / k] t^2}{2 h^{-k p} f_{\Z, max}^k ||K||_2^{2k} + (4/3) h^{-k p} C_K^k t} \bigg), \end{aligned}$$ and on the same event, $N_k(\z_{1:k})$ is strictly positive and $$\begin{aligned} \frac{\prod_{i=1}^k f_{\Z}(\z_i)}{N_k(\z_{1:k})} \leq 1 + \frac{4 f_{\Z, max}^k}{f_{\Z, min}^{2k}} \bigg( \frac{C_{K, \alpha} h^{\alpha}}{\alpha !} + t \bigg). \end{aligned}$$ \[lemma:bound\_prodf\_Nk\] <span>*Proof :*</span> Using the mean value inequality for the function $x \mapsto 1/x$, we get $$\begin{aligned} \bigg| \frac{1}{N_k(\z_{1:k})}-\frac{1}{\prod_{i=1}^k f_{\Z}(\z_i)} \bigg| \leq \frac{1}{N_*^2} \big|N_k(\z_{1:k})-\prod_{i=1}^k f_{\Z}(\z_i) \big|,\end{aligned}$$ where $N_*$ lies between $N_k(\z_{1:k})$ and $\prod_{i=1}^k f_{\Z}(\z_i)$. By Lemma \[lemma:bound\_Nk\_fk\], we get $$\begin{aligned} \PP \bigg( \big| N_k(\z_{1:k}) &- \prod_{i=1}^k f_{\Z}(\z_i) \big| \leq \frac{C_{K, \alpha}}{\alpha !} h^{\alpha} + t \bigg) \geq 1 - 2 \exp \bigg( - \frac{[ n / k] t^2}{2 h^{-k p} f_{\Z, max}^k ||K||_2^{2k} + (4/3) h^{-k p} C_K^k t} \bigg). \end{aligned}$$ On this event, $\big| N_k(\z_{1:k}) - \prod_{i=1}^k f_{\Z}(\z_i) \big| \leq (1/2) \prod_{i=1}^k f_{\Z}(\z_i)$ by assumption, so that $f_{\Z, min}^k/2 \leq N_k(\z_{1:k})$. We have also $f_{\Z, min}^k/2 \leq \prod_{i=1}^k f_{\Z}(\z_i)$. Thus, we have $f_{\Z, min}^k/2 \leq N_*$. Combining the previous inequalities, we finally get $$\begin{aligned} \bigg| \frac{1}{N_k(\z_{1:k})} - \frac{1}{\prod_{i=1}^k f_{\Z}(\z_i)} \bigg| \leq \frac{1}{N_*^2} \big| N_k(\z_{1:k}) - \prod_{i=1}^k f_{\Z}(\z_i) \big| \leq \frac{4}{f_{\Z, min}^{2k}} \bigg( \frac{C_{K, \alpha} h^{\alpha}}{\alpha !} + t \bigg).\end{aligned}$$ $\Box$ Now, we provide a bound on the bias. Under Assumptions \[condUstat:assumpt:kernel\_integral\] and \[condUstat:assumpt:f\_XZ\_Holder\], we have $\big| \EE[S_{\sigma}] \big| \leq C_{g, f, \alpha} C_{K,\alpha} h^{k \alpha} / (f_{\Z,min}^k \alpha !).$ \[lemma:boundProba\_sum\_S\_sigma:bias\] <span>*Proof :*</span> We remark that $$\begin{aligned} 0 &= \int \Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) f_{\X | \Z=\z_1}(\x_1) \cdots f_{\X | \Z=\z_k}(\x_k) d\mu^{\otimes k}(\x_{1:k}) \nonumber \\ &= \int \Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \frac{f_{\X,\Z}(\x_1,\z_1) \cdots f_{\X, \Z}(\x_k,\z_k)}{\prod_{i=1}^k f_{\Z}(\z_i)} d\mu^{\otimes k}(\x_{1:k}).\end{aligned}$$ We have $$\begin{aligned} &\EE[S_{\sigma}] = \EE \bigg[\frac{K_h(\Z_{\sigma(1)}-\z_1) \cdots K_h(\Z_{\sigma(k)}-\z_k)}{\prod_{i=1}^k f_{\Z}(\z_i)} \Big( g\big(\X_{\sigma(1)}, \dots, \X_{\sigma(k)} \big) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \bigg] \displaybreak[0] \\ &= \int \Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \prod_{i=1}^k \frac{K(\u_i)}{f_{\Z}(\z_i)} f_{\X,\Z}(\x_i, \z_i + h\u_i) \, d\mu(\x_i) d\u_i \displaybreak[0] \\ &= \int\Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \bigg( \prod_{i=1}^k f_{\X,\Z} \Big(\x_i, \z_i + h \u_i \Big) - \prod_{i=1}^k f_{\X,\Z} \Big(\x_i, \z_i \Big) \bigg) \, \prod_{i=1}^k \frac{K(\u_i)}{f_{\Z}(\z_i)} \, d\mu(\x_i) d\u_i.\end{aligned}$$ We apply now the Taylor-Lagrange formula to the function $$\phi_{\x_{1:k}, \u_{1:k}}(t) := \prod_{i=1}^k f_{\X,\Z} \Big(\x_i, \z_i + h \u_i \Big),$$ and get $$\begin{aligned} &\EE[S_{\sigma}] = \int \Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \bigg( \phi_{\x_{1:k}, \u_{1:k}}(t)(1) - \phi_{\x_{1:k}, \u_{1:k}}(t)(0) \bigg) \prod_{i=1}^k \frac{K(\u_i)}{f_{\Z}(\z_i)} \, d\mu(\x_i) d\u_i \\ &= \int \Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \\ & \hspace{3cm} \cdot \bigg( \sum_{j=1}^{\alpha - 1} \frac{1}{j !} \phi_{\x_{1:k}, \u_{1:k}}(t)^{(j)}(0) + \frac{1}{\alpha !} \phi_{\x_{1:k}, \u_{1:k}}(t)^{(\alpha)} (t_{\x, \u}) \bigg) \, \prod_{i=1}^k \frac{K(\u_i)}{f_{\Z}(\z_i)} \, d\mu(\x_i) d\u_i \displaybreak[0] \\ &= \int \Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \\ & \hspace{3cm} \cdot \bigg( \frac{1}{\alpha !} \phi_{\x_{1:k}, \u_{1:k}}(t)^{(\alpha)} (t_{\x, \u}) \bigg) \, \prod_{i=1}^k \frac{K(\u_i)}{f_{\Z}(\z_i)} \, d\mu(\x_i) d\u_i \displaybreak[0] \\ &= \int \Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \\ & \hspace{3cm} \cdot \frac{1}{\alpha !} \bigg( \phi_{\x_{1:k}, \u_{1:k}}(t)^{(\alpha)} (t_{\x, \u}) - \phi_{\x_{1:k}, \u_{1:k}}(t)^{(\alpha)} (0) \bigg) \, \prod_{i=1}^k \frac{K(\u_i)}{f_{\Z}(\z_i)} \, d\mu(\x_i) d\u_i.\end{aligned}$$ For every real $t$, we have $$\begin{aligned} &\phi^{(\alpha)} (t) = \sum_{m_1 + \, \cdots \, + m_k = \alpha} \binom{n}{m_{1:k}} \prod_{i=1}^k \frac{\partial^{m_i} \Big( f_{\X,\Z} \big(\x_i,\z_i + ht \u_i \big) \Big)}{\partial t^{m_i}} \nonumber \\ &= \sum_{m_1 + \, \cdots \, + m_k = \alpha} \binom{n}{m_{1:k}} \prod_{i=1}^k \sum_{j_1, \dots, j_{m_i} = 1}^{p} h^{m_i} u_{i,j_1} \dots u_{i,j_{m_i}} \frac{\partial^{m_i} f_{\X,\Z}}{\partial z_{j_1} \, \cdots \, \partial z_{j_{m_i}}} \big(\x_i,\z_i + ht \u_i \big) \nonumber \\ &= h^{\alpha} \sum_{m_1 + \, \cdots \, + m_k = \alpha} \binom{n}{m_{1:k}} \prod_{i=1}^k \sum_{j_1, \dots, j_{m_i} = 1}^{p} u_{i,j_1} \dots u_{i,j_{m_i}} \frac{\partial^{m_i} f_{\X,\Z}}{\partial z_{j_1} \, \cdots \, \partial z_{j_{m_i}}} \big(\x_i,\z_i + ht \u_i \big). \label{condUstat:eq:computation_partial_deriv_phi}\end{aligned}$$ Therefore, we get $$\begin{aligned} &\EE[S_{\sigma}] = \sum_{m_1 + \, \cdots \, + m_k = \alpha} \binom{n}{m_{1:k}} \int \prod_{i=1}^k \frac{K(\u_i)}{\prod_{i=1}^k f_{\Z}(\z_i)} \sum_{j_1, \dots, j_{m_i} = 1}^{p} u_{i,j_1} \dots u_{i,j_{m_i}} \\ &\hspace{3cm} \cdot \Big( g(\x_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \\ &\hspace{3cm} \cdot \left( \frac{\partial^{m_i} f_{\X,\Z}}{\partial z_{j_1} \, \cdots \, \partial z_{j_{m_i}}} \big(\x_i,\z_i + ht \u_i \big) - \frac{\partial^{m_i} f_{\X,\Z}}{\partial z_{j_1} \, \cdots \, \partial z_{j_{m_i}}} \big(\x_i,\z_i \big) \right) d\mu(\x_1) d\u_1 \cdots d\mu(\x_k) d\u_k,\end{aligned}$$ and, using Assumption \[condUstat:assumpt:f\_XZ\_Holder\], this yields $$\begin{aligned} \big| \EE[S_{\sigma}] \big| & \leq \frac{C_{g, f, \alpha} C_{K,\alpha} h^{\alpha+k}} {f_{\Z,min}^k \alpha !}.\end{aligned}$$ $\Box$ Now we bound the stochastic component. We have the following equality $$\begin{aligned} \bigg| \sum_{\sigma \in \Ikn} \big( S_{\sigma} - \EE[S_{\sigma}] \big) \bigg| = \bigg| \frac{(n-k) !}{n !} \sum_{\sigma \in \Ikn} g\big( (\X_{\sigma(1)}, \Z_{\sigma(1)}) \, , \dots , \, (\X_{\sigma(k)}, \Z_{\sigma(k)}) \big) \bigg|\end{aligned}$$ with the function $\tilde g$ defined by $$\begin{aligned} &\tilde g\big( (\X_1, \Z_1) \, , \dots , \, (\X_k, \Z_k) \big) \\ &= \frac{K_h \big(\Z_1-\z_1 \big) \cdots K_h \big(\Z_k-\z_k \big)}{\prod_{i=1}^k f_{\Z}(\z_i)} \Big( g(\X_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \\ & - \EE \Bigg[ \frac{K_h \big(\Z_1-\z_1 \big) \cdots K_h \big(\Z_k-\z_k \big)}{\prod_{i=1}^k f_{\Z}(\z_i)} \Big( g(\X_{1:k}) - \EE \big[ g(\X_{1:k}) \big| \Z_{1:k} = \z_{1:k} \big] \Big) \Bigg]\end{aligned}$$ By construction, $\EE \Big[ \tilde g\big( (\X_1, \Z_1) \, , \dots , \, (\X_k, \Z_k) \big) \Big] = 0.$ If $\tilde g$ is bounded, we can derive an immediate bound for this stochastic component. Indeed, we would have $||\tilde g||_\infty \leq 4 C_K^k h^{-kp} C_{g}^k / f_{\Z,min}^k$. Moreover, we have $$\begin{aligned} Var \Big[ \tilde g \big( (\X_1, \Z_1) \, , \dots , \, (\X_k, \Z_k) \big) \Big] &\leq \EE \bigg[ \frac{K_h^2 \big(\Z_1-\z_1 \big) \cdots K_h^2 \big(\Z_k-\z_k \big)}{\prod_{i=1}^k f_{\Z}^2(\z_i)} g{}^2(\X_1, \dots, \X_k) \bigg] \\ &\leq C_{g}^2 f_{\Z,max}^k f_{\Z,min}^{-2k} h^{-k p} ||K||_2^{2k}.\end{aligned}$$ Therefore, we can apply Lemma \[lemma:bernstein\_U\_stat\_sym\], and we get $$\begin{aligned} \PP \bigg( \Big| \sum_{\sigma \in \Ikn} &\big( S_{\sigma} - \EE[S_{\sigma}] \big) \Big| > t \bigg) \leq 2 \exp \bigg( - \frac{[ n / k] t^2} {2 C_{g}^2 f_{\Z,max}^k f_{\Z,min}^{-2k} h^{-k p} ||K||_2^{2k} + (8/3) C_K^k h^{-kp} C_{g}^k f_{\Z,min}^{-k} t} \bigg).\end{aligned}$$ In the following Lemma \[lemma:boundProba\_sum\_S\_sigma\], our goal will be to bound the stochastic component using only Assumption \[condUstat:assumpt:conditional\_Bernstein\] on the conditional moments of $g$. Under Assumptions \[condUstat:assumpt:kernel\_integral\], \[condUstat:assumpt:f\_Z\_min\] and \[condUstat:assumpt:conditional\_Bernstein\], for every $t > 0$, we have $$\begin{aligned} \PP \left( \sum_{\sigma \in \Ikn} S_{\sigma} - \EE[S_{\sigma}] > t \right) &\leq \exp \left( - \frac{t^2 f_{\Z, min}^{2k} h^{k p} [ n / k]}{128 \big(B_{g, \z} + \tilde B_{g} \big)^2 C_K^{2k-1} + 2 t \big(B_{g, \z} + \tilde B_{g} \big) C_K^{k} f_{\Z, min}^{k}} \right). \end{aligned}$$ \[lemma:boundProba\_sum\_S\_sigma\] <span>*Proof:*</span> Using the same decomposition for U-statistics as in Hoeffding @hoeffding1963probability, we obtain $$\begin{aligned} \sum_{\sigma \in \Ikn} S_{\sigma} - \EE[S_{\sigma}] = \frac{1}{n!} \sum_{\sigma \in \Inn} \frac{1}{[ n / k]} \sum_{i = 1}^{[ n / k]} V_{n,i,\sigma},\end{aligned}$$ where $$\begin{aligned} V_{n,i,\sigma} &:= \tilde g \Big( \big(\X_{\sigma(1 + (i-1) k)}, \Z_{\sigma(2 + (i-1) k)} \big), \dots, \big(\X_{\sigma(i k)}, \Z_{\sigma(j k)} \big) \Big).\end{aligned}$$ For any $\lambda > 0$, we have $$\begin{aligned} \PP \left( \sum_{\sigma \in \Ikn} S_{\sigma} - \EE[S_{\sigma}] > t \right) &\leq e^{-\lambda t} \EE \left[ \exp \left(
{'source': 'arXiv_out/1903'}