small. On the other hand, when is in reased, the number of nodes under onsideration grows together with the upper limit on the number of examples rea hing ea h single one of them. Thus, both small and large values of yield loose bounds. In the stri test bounds the value of is somewhere in the middle, in our example around values 1.01.5. In the bound of Equation 5 the argument of the umulative distribution fun tion  tends towards zero when the value of is very small, but at the same time the exponent de reases. The value of  approa hes 1/2, when its argument goes to zero. On the other hand, when has a large value,  approa hes value 1 and the exponent P also in reases.

## 6.2 On The Exa Tness Of The Approximation

Above we used the expe ted value of P in the analysis; EP = EQER. We now probe into the deviation of P from its expe ted value. The deviation of R is dire tly available from Theorem 7:

$$\mathbf{Pr}\,\{\,|R-\mathbf{E}R|\geq\lambda\,\}\leq2\exp\left(-{\frac{\lambda^{2}(k-1/2)}{k^{2}-\mathbf{E}^{2}R}}\right)\,.$$

For Q we do not have a similar result yet. In this se
tion we provide one.

Let us rst re apitulate the denition of the Lips hitz ondition.

Denition Let f : D1 -    - Dm ! IR be a real-valued fun
tion with m arguments from possibly distin t domains. The fun tion f is said to satisfy the Lip
hitz 
ondition if for any x1 2 D1; : : : ; xm 2 Dm, any i 2 f1; : : : ; mg, and any yi 2 Di, jf (x1; : : : ; xi1; xi ; xi+1; : : : ; xm)  f (x1; : : : ; xi1; yi; xi+1; : : : ; xm)j  1:
Hen e, a fun tion satises the Lips hitz ondition if an arbitrary hange in the value of any one argument does not hange the value of the fun tion more than 1.

The following result (M
Diarmid, 1989) holds for fun tions satisfying the Lips hitz ondition. More general results of the same kind an be obtained using martingales (see e.g.,

(Motwani & Raghavan, 1995)).

Theorem 8 (M
Diarmid) Let X1; : : : ; Xm be independent random variables taking values in a set V . Let f : V m ! IR be su
h that, for i = 1; : : : ; m:
x1;:::;xm;yi2V
jf (x1; : : : ; xi1; xi ; xi+1; : : : ; xm)  f (x1; : : : ; xi1; yi; xi+1; : : : ; xm)j  
i :
sup Then for  > 0,

$\Pr\{\left|f(X_{1},\ldots,X_{m})-\mathds{E}\,f(X_{1},\ldots,X_{m})\right|\geq\lambda\,\}\leq2\exp\left(-\frac{2\lambda^{2}}{\sum_{i=1}^{m}c_{i}^{2}}\right).$  $i=1,\ldots,n$ be a random variable such that $W=i$ if the $i$ th 

Let Wi, i = 1; : : : ; n, be a random variable su
h that Wi = j if the i-th example is dire ted to the safe node zj . By the uniform distribution assumption Wi-s are independent.

They have their values within the set f1; : : : ; kg. Let us dene the fun
tion f so that f (w1; : : : ; wn) is the number of those safe nodes that re
eive at most r = 
n=k examples, when the i-th example is dire ted to the safe node zwi

. That is,

$f(w_{1},\ldots,w_{n})=|\{i\in\{1,\ldots,k\}|\,|S_{i}|\leq r\}|$,