3.3.2 SAMPLE COMPLEXITY BOUNDS FOR NEURAL-NETWORK FEATURE LEARNING
The size of z ensuring that the resulting features will be good for learning novel tasks from the same environment is given by Theorem 2. All we have to do is compute the logarithm of the covering numbers C("; H n l

) and C("; H ).

```
Theorem 7. Let H =
                  
                   Hw : w 2 RW 	be a hypothesis space family where each Hw is of the form

```

$${\mathcal{H}}_{w}:=\left\{\sigma\left(\sum_{i=1}^{k}\alpha_{i}\,\phi_{w,i}(\cdot)\,+\,\alpha_{0}\right)\,:\,(\alpha_{1},\ldots,\alpha_{k})\in\mathbb{R}^{k}\,\right\},$$

where w = (w;1; : : : ; w;k) is a neural network with W weights mapping from Rdto Rk. If the feature weights w *and the output weights* 0; 1; : : : ; k *are bounded, the squashing function*  is Lipschitz, l *is squared loss, and the output space* Y = [0; 1℄ (any bounded subset of R will do), then there exist constants ; 0*(independent of* "; W and k*) such that for all* " > 0,

$$\log{\mathcal{C}}(\varepsilon,\,\mathbb{H}_{l}^{n}\,)\leq\,2\,((k+1\,)n\,+\,W)\log{\frac{\kappa}{\varepsilon}}$$

$$(41)$$
$$\log{\mathcal{C}}(\varepsilon,\mathbb{H}^{*})\leq\,2W\log{\frac{\kappa^{\prime}}{\varepsilon}}$$

$$(42)$$

(recall that we have specialized to squared loss here).

Proof. See Appendix B.

Noting that our neural network hypothesis space family H is permissible, plugging (41) and (42) into Theorem 2 gives the following theorem.

Theorem 8. Let H = fHwg be a hypothesis space family where each hypothesis space Hw *is a* set of squashed linear maps composed with a neural network feature map, as above. Suppose the number of features is k, and the total number of feature weights is W. Assume all feature weights and output weights are bounded, and the squashing function  is Lipschitz. Let z *be an* (n; m)*-sample* generated from the environment (P; Q)*. If*

$$n\,\geq\,O\left(\frac{1}{\varepsilon^{2}}\,\left[W\log\frac{1}{\varepsilon}+\log\frac{1}{\delta}\right]\right),$$

$$(43)$$

$$a m d$$
$$m\,\geq\,O\left({\frac{1}{\varepsilon^{2}}}\left[\left(k+1+{\frac{W}{n}}\right)\log{\frac{1}{\varepsilon}}+{\frac{1}{n}}\log{\frac{1}{\delta}}\right]\right)$$

then with probability at least 1  Æ any Hw 2 H *will satisfy*

$$\operatorname{er}_{Q}({\mathcal{H}}_{w})\leq\operatorname{\hat{e r}}_{\mathbf{z}}({\mathcal{H}}_{w})+\varepsilon\,.$$
erQ(Hw)  ^erz(Hw) + ": (45)
$$(44)$$
$$(45)$$

169