Corollary 13 shows that any algorithm learning n tasks using the hypothesis space family H
requires no more than

$$m\,=\,O\left(\frac{1}{\varepsilon^{2}}\,\left[d_{\,\mathbb{E}}(n\,)\log\frac{1}{\varepsilon}+\frac{1}{n}\log\frac{1}{\delta}\right]\right)\tag{50}$$

examples of each task to ensure that with high probability the average true error of any n hypotheses
it selects from H nis within " of their average empirical error on the sample z. We now give a
theorem showing that if the learning algorithm is required to produce n hypotheses whose average
true error is within " of the *best possible error* (achievable using H n) for an arbitrary sequence of distributions P1; : : : ; Pn, then within a log 1
"

factor the number of examples in equation (50) is also
necessary.
For any sequence P = (P1 ; : : : ; Pn) of n probability distributions on X - f1g, define
optP(H n) by
$$\operatorname{opt}_{\mathbf{P}}{\big(}\mathbb{H}^{n}{\big)}:=\operatorname*{inf}_{\mathbf{h}\in\mathbb{H}^{n}}\operatorname{er}_{\mathbf{P}}(\mathbf{h}).$$
Theorem 14. Let H be a Boolean hypothesis space family such that H 1contains at least two functions. For each n = 1; 2; : : : ; let An *be any learning algorithm taking as input* (n; m)*-samples* z 2 (X - f1g)

(n;m)
and producing as output n *hypotheses* h = (h1 ; : : : ; hn) 2 H n*. For all* 0 < " < 1=64 and 0 < Æ < 1=64*, if*

$$m\,<\frac{1}{\varepsilon^{2}}\left[\frac{d_{\,\mp}(n\,)}{616}+(1\,-\varepsilon^{2}\,)\frac{1}{n}\log\left(\frac{1}{8\delta(1\,-\,2\delta)}\right)\right]$$
$$\operatorname{III}^{*}\,\big)\,+\,\varepsilon$$

```
then there exist distributions P = (P1; : : : ; Pn) such that with probability at least Æ (over the
random choice of z),
                                   erP(An(z)) > optP(H
                                                           n
                                                            
                                                            ) + "
                                                                  

```

Proof. See Appendix C
3.4.2 LINEAR THRESHOLD NETWORKS
Theorems 13 and 14 show that within constants and a log(1=") factor, the sample complexity of learning n tasks using the Boolean hypothesis space family H is controlled by the complexity parameter dH (n). In this section we derive bounds on dH (n) for hypothesis space families constructed as thresholded linear combinations of Boolean feature maps. Specifically, we assume H is of the form given by (39), (38), (37) and (36), where now the squashing function  is replaced with a hard threshold:

$$\sigma(x):=\left\{\begin{array}{l l}{{1}}&{{\mathrm{if~}x\,\geq0,}}\\ {{-1}}&{{\mathrm{otherwise},}}\end{array}\right.$$
$\square$
and we don't restrict the range of the feature and output layer weights. Note that in this case the proof of Theorem 8 does not carry through because the constants ; 0in Theorem 7 depend on the Lipschitz bound on .

Theorem 15. Let H *be a hypothesis space family of the form given in* (39), (38), (37) and (36)*, with* a hard threshold sigmoid function . Recall that the parameters d, l and k *are the input dimension,*
number of hidden nodes in the feature map and number of features (output nodes in the feature map)