5
$\begingroup$

Optimal rate of convergence for a nonparametric estimator is well-known. This rate is derived for when we don't anything about functional form (expect perhaps degree of smoothness). Suppose we know that the true functional form is say linear and despite knowing that we apply a nonparametric estimator, is the optimal rate of convergence still the same or different? Basically, does the performance of a nonparametric estimator depend on what the true function looks like or not?

$\endgroup$

1 Answer 1

11
$\begingroup$

Yes, in some cases the rate can be much faster for specific functions than in the general case.

Consider the model $y_i = \theta^*_i + \epsilon_i$ where $\epsilon_i \sim N(0, \sigma^2)$ and $\theta^*_i$ are unknown. You can think of $\theta^*_i$ as $f^*(i/n)$, i.e. the values of some true function that you are trying to estimate on a grid $1/n, 2/n, \ldots, n/n$.

You can define a least squares estimator over a class of functions $\mathcal{C}$ as $$\hat{\theta} = \text{argmin}_{\theta \in \mathcal{C}} \|\theta - y\|^2.$$

  • With $\mathcal{C}_{iso} := \{\theta \in \mathbb{R}^n : \theta_1 \le \cdots \le \theta_n\}$, we get isotonic regression.
  • With $\mathcal{C}_{TV}(V) := \{\theta \in \mathbb{R}^n : |\theta_1-\theta_2| + |\theta_2 - \theta_3| + \cdots+ | \theta_{n-1} - \theta_n| \le V\}$ for some $V \ge 0$, we get total variation denoising.

We can define the risk of an estimator $\hat{\theta}$ as $R(\hat{\theta}, \theta^*) = \frac{1}{n} \mathbb{E}\|\hat{\theta} - \theta^*\|^2$.

For each of isotonic regression and total variation denoising, when $\theta^* \in \mathcal{C}$, the risk can be bounded by $\lesssim n^{-2/3}$ (up to log factors), and this rate is minimax (up to log factors) over $\mathcal{C}$ (i.e. no estimator can have a better worst-case risk over $\mathcal{C}$).

However, if $\theta^*$ lies on a face of the polyhedron $\mathcal{C}$, the least squares estimator adapts and has a faster rate. Specifically,

  • For isotonic regression, if the true function is piecewise constant and nondecreasing, the estimator achieves a faster rate of $n^{-1}$ (up to log factors). The intuition is that the estimator is able to adapt and find the segments where the true function is constant, even though it does not have this information.
  • For total variation denoising, if the true function is piecewise constant and if the tuning parameter $V$ is chosen appropriately, the estimator also achieves the faster rate of $n^{-1}$ (up to log factors). The intuition is similar: the estimator is able to adapt and find the constant segments, despite not knowing where the knots are in advance.

Note that if you knew in advance the knots of the piecewise constant true function, simply averaging the observations $y_i$ on each segment would achieve risk on the order of $n^{-1}$. So the above estimators are able to get within log factors of these "oracle" rates without knowing this information about the true function.

References for the above claims (which also contain pointers to other relevant literature):

$\endgroup$
2
  • $\begingroup$ Thanks, this might partially answer my question. However, I would like to know if there are some results on standard kernel regression. The reason I ask this is that one of criticism of nonparametric regression is the curse of dimensionality but that may not be the case if true function is well-behaved enough. $\endgroup$
    – user41838
    Feb 22 at 14:15
  • $\begingroup$ @user41838 I am less familiar with the literature for kernel regression. The paper [2] mentions that standard kernel regression doesn't exhibit adaptation, but variable-width bandwidth kernel regression does. These lecture notes seem to discuss this topic. $\endgroup$
    – angryavian
    Feb 22 at 16:25

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.