1
$\begingroup$

Consider the Kernel regression estimator:

$$\hat{y}(x)=\frac{\sum_{i=1}^n{K(x-x_i)y_i}}{\sum_{i=1}^n{K(x-x_i)}},$$

where $x,x_1,\dots,x_n\in\mathbb{R}^d$, $y_1,\dots,y_n\in\mathbb{R}$, where $K:\mathbb{R}^d\rightarrow(0,\infty)$ is a strictly positive valued, differentiable kernel function, with a unique maximum at $0$.

Suppose further that for all $i,j\in\{1,\dots,n\}$, if $x_i\le x_j$ then $y_i \le y_j$.

Is it the case that for all $x\in\mathbb{R}^d$:

$$\frac{\partial\hat{y}(x)}{\partial x} \ge 0?$$

It seems obvious in the $d=1$ case, but even there I haven't been able to prove it. It's unclear to me if it holds for $d>1$. If it only holds under additional assumptions on $K$ I'd be interested in them.


Note, this was originally posted on math.stackexchange here: https://math.stackexchange.com/questions/3612590/does-kernel-regression-preserve-monotonicity but it attracted no answers even after a bounty was posted.


Notation:

$\frac{\partial \hat{y}(x)}{\partial x}$ is the column vector of partial derivatives of $\hat{y}(x)$, i.e. the (transposed) Jacobian.

For vectors $a=[a_1,\dots,a_d]^\top$ and $b=[b_1,\dots,b_d]^\top$, $a\le b$ if and only if $a_i \le b_i$ for all $i\in\{1,\dots,d\}$.

$\endgroup$

1 Answer 1

1
$\begingroup$

The result is false in general even for $d=1$. E.g., let $$K=f_r+f_s,$$ where $f_t$ is the density of $N(0,t^2)$. Then for $x_i=y_i=i$ ($\forall i=1,\dots,n$) and $$(n,r,s,x_*)=\Big(3,\frac{427}{215},\frac{1}{1547},\frac{472}{473}\Big)$$ we have $$\hat y'(x_*)=-527.1\ldots<0.$$

Here is the graph $\{(x,\hat y(x))\colon\frac{471}{473}\le x\le\frac{475}{473}\}$:

enter image description here

We see a very narrow dip.


However, $\hat y'\ge0$ if $K$ is log concave. Indeed, letting $$k_i:=K(x-x_i)\quad\text{and}\quad k'_i:=K'(x-x_i),$$ we have $$ \begin{aligned} 2\Big(\sum_{i=1}^n k_i\Big)^2\hat y'(x) &=\sum_{i,j=1}^n(k'_i y_i k_j-k_i y_i k'_j+k'_j y_j k_i-k_j y_j k'_i) \\ &=\sum_{i,j=1}^n(y_i-y_j)\Big(\frac{k'_i}{k_i}-\frac{k'_j}{k_j}\Big)k_ik_j\ge0, \end{aligned}\tag{1} $$ because $y_i$ is increasing in $i$ and $$\frac{k'_i}{k_i}=(\ln K(x-x_i))' \tag{2}$$ is increasing in $i$; the latter holds because $x_i$ is increasing in $i$ and $(\ln K)'$ is decreasing (since $K$ is log concave). (In particular, any normal density is log concave.)



In the case $d>1$, the desired monotonicity fails to hold in general even when $K$ is log concave. E.g., let $$K(u_1,\dots,u_d):=\exp\{u_1u_2-u_1^2-\cdots-u_d^2\},$$ $n=2$, $x_1=(0,\dots,0)$, $x_2=(0,1,0,\dots,0)$, $y_1=0$, and $y_2=1$. Then $(\partial_1\ln K)(u_1,\dots,u_d)=u_2-2u_1$, where $\partial_1$ denotes the partial derivative with respect to the first coordinate. On the other hand (cf. (1) and (2)), $(\partial_1\hat y)(0,\dots,0)$ equals $l'_2-l'_1$ in sign, where $$l'_1:=(\partial_1\ln K)(0,\dots,0)=0$$ and $$l'_2:=(\partial_1\ln K)(0,-1,0,\dots,0)=-1<0=l'_1.$$ So, $(\partial_1\hat y)(0,\dots,0)<0$, as claimed.



Looking back at (1), it is clear that the necessary and sufficient condition for the desired monotonicity is that the appropriate analogs of $\frac{k'_i}{k_i}-\frac{k'_j}{k_j}$ be $\ge0$ whenever for the corresponding $x_i$ and $x_j$ we have $x_i\ge x_j$. In particular, this will happen if $K$ is the product of log-concave functions of one coordinate each.

Here we of course need to assume that that $x_i$'s are linearly ordered, so that, without loss of generality, $x_i\le x_j$ if $i<j$. Indeed, suppose e.g. that $x_1=(1,0,\dots,0)$, $y_1=1$, $x_i=(0,1,0,\dots,0)$ and $y_i=0$ for $i=2,\dots,n$. Then the implication $x_i\le x_j\implies y_i\le y_j$ holds for all $i,j$. This implication will also hold if we replace here $y_1$ by $-1$. But then $\hat y$ will change in sign, and hence its monotonicity pattern will change to the opposite one.

$\endgroup$
17
  • $\begingroup$ In the multivariate log-concave case, your expression for $\hat{y}'(x)$ goes through exactly as here, but the final $\ge 0$ might not, if I'm understanding correctly. There will be some $i,j$ for which $x_i \ngeq x_j$ and $x_j \ngeq x_i$, thus for those pairs you can't guarantee anything about the sign of the product. Do you have a counter-example for the claim with a log-concave $K$ and $d>1$? $\endgroup$
    – cfp
    Apr 22, 2020 at 9:24
  • $\begingroup$ @cfp : In the multivariate case, you left the meaning of $\frac{\partial\hat{y}(x)}{\partial x}$ and the meaning of the inequalities $x_i\le x_j$ undefined. Until you have done that, it is of course impossible to say anything about the multivariate case. $\endgroup$ Apr 22, 2020 at 13:25
  • 1
    $\begingroup$ @cfp : I have now given a counter-example with a log-concave $K$ for $d>1$. $\endgroup$ Apr 22, 2020 at 16:14
  • 1
    $\begingroup$ @cfp : Looking at (1), it is clear that the necessary and sufficient condition is that the appropriate analogs of $\frac{k'_i}{k_i}-\frac{k'_j}{k_j}$ be of the same sign as $y_i-y_j$. In particular, this will happen if $K$ is the product of log-concave functions of one coordinate each. To me, this coordinate-wise approach seems quite unnatural, though, since it depends on the choice of the basis. $\endgroup$ Apr 22, 2020 at 17:33
  • 1
    $\begingroup$ @cfp : I see now that the coordinate-wise approach may actually make sense in practice. I have also added my latter comment to the answer. $\endgroup$ Apr 22, 2020 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.