0.20 Lower performance bounds for estimators  (Page 8/4)

Lower performance bounds

In other modules, estimators/predictors are analyzed, in order to obtain upper bounds on their performance. These bounds are of the form:

where $\gamma >0$ . We would like to know if these bounds are tight, in the sense that there is no otherestimator that is significantly better. To answer this, we need lower bounds like

We assume we have the following ingredients:

• * Class of models, $\mathcal{F}\subseteq \mathcal{S}$ . $\mathcal{F}$ is a class of models containing the “true" model and is a subset of some bigger class $\mathcal{S}$ . E.g. $\mathcal{F}$ could be the class of Lipschitz density functions or distributions $P_{XY}$ satisfying the box-counting condition.
• * An observation model, ${\mathcal{P}}_f$ , indexed by $f\in \mathcal{F}$ . ${\mathcal{P}}_f$ denotes the distribution of the data under model $f$ . E.g. in regression and classification, this is the distribution of $Z=(X_1,Y_1,\cdots ,X_n,Y_n)\subseteq \mathcal{Z}$ . We will assume that ${\mathcal{P}}_f$ is a probability measure on the measurable space $(\mathcal{Z},\mathcal{B})$ .
• * A performance metric $d(.,.).\ge 0$ . If you have a model estimate ${\widehat{f}}_n$ , then the performance of that model estimate relative to the true model $f$ is $d({\widehat{f}}_n,f)$ . E.g.
  $$\text{Regression:}d({\widehat{f}}_n,f)=\left|\right|{\widehat{f}}_n-f{\left|\right|}_2={\left(\int ,{({\widehat{f}}_n\left(x\right)-f\left(x\right))}^2,d,x\right)}^{1/2}$$
  $$\text{Classification:}d({\widehat{f}}_n,f)=R\left({\widehat{G}}_n\right)-R^{*}={\int }_{{\widehat{G}}_n\Delta G^{*}}|2\eta \left(x\right)-1|d{P}_X\left(x\right)$$

As before, we are interested in the risk of a learning rule, in particular the maximal risk given as:

where ${\widehat{f}}_n$ is a function of the observations $Z$ and ${\mathbb{E}}_f$ denotes the expectation with respect to ${\mathcal{P}}_f$ .

The main goal is to get results of the form

where $c>0$ and $s_n\to 0$ as $n\to \infty$ . The $inf$ is taken over all estimators, i.e. all measurable functions ${\widehat{f}}_n:\mathcal{Z}\to \mathcal{S}$ .

Suppose we have shown that

and also that for a particular estimator ${\overline{f}}_n$

We say that $s_n$ is the optimal rate of convergence for this problem and that ${\overline{f}}_n$ attains that rate.

General reduction scheme

Instead of directly bounding the expected performance, we are going to prove stronger probability bounds of the form

These bounds can be readily converted to expected performance bounds using Markov's inequality:

Therefore it follows:

First reduction step

Reduce the original problem to an easier one by replacing the larger class $\mathcal{F}$ with a smaller finite class $\{f_0,\cdots ,f_M\}\subseteq \mathcal{F}$ . Observe that

The key idea is to choose a finite collection of models such that the resulting problem is as hard as the original, otherwise the lower bound will not be tight.

Second reduction step

Next, we reduce the problem to a hypotheses test. Ideally, we would like to have something like

The $inf$ is over all measurable test functions

and ${\mathcal{P}}_{f_j}({\widehat{h}}_n\left(Z\right)\ne j)$ denotes the probability that after observing the data, the test infers the wrong hypothesis.

This might not always be true or easy to show, but in certain scenarios it can be done. Suppose $d(.,.)$ is a semi-distance, i.e. it satisfies