Plugging in the bound on the empirical Rademacher complexity given by Theorem 1 yields the statement of the corollary.

The corollary gives a generalization bound for learning kernels with Hp that is in

$$O\left({\sqrt{\frac{(\log p)\,R^{2}/\rho^{2}}{m}}}\right).$$
. (9)
In comparison, the bound for this problem given by Srebro and Ben-David [19] using the pseudo-dimension has a stronger dependency with respect to p and is more complex:

$$O\left(\sqrt{8\frac{2+p\log\frac{128e m^{3}R^{2}}{\rho^{2}p}+256\frac{R^{2}}{\rho^{2}}\log\frac{\rho e m}{8R}\log\frac{128m R^{2}}{\rho^{2}}}{m}}\right).$$
$$(10)$$

This bound is also not informative for **p > m**.

4 Rademacher complexity bound for H′p
Theorem 3 For any sample S of size m*, the Rademacher complexity of the hypothesis set* H′p
can be bounded
as follows:
$$\widehat{\mathfrak{R}}_{S}(H_{p}^{\prime})\leq\frac{\|\mathbf{\tau}\|_{r}}{m\rho}\quad\text{with}\mathbf{\tau}=(\sqrt{r\operatorname{Tr}[\mathbf{K}_{1}]},\ldots,\sqrt{r\operatorname{Tr}[\mathbf{K}_{p}]})^{\top},$$
for any even integer 0 < r ≤ 4*. If additionally,* Kk(**x, x**) ≤ R2for all x ∈ X and k ∈ [1, p]*, then, for any*
p ≥ 1,
$$\hat{\Re}_{S}(H_{p}^{\prime})\leq2p^{1/4}\sqrt{\frac{R^{2}/\rho^{2}}{m}}.$$
This bound also hold without the condition µk ≥ 0, k ∈ [1, p], on the hypothesis set H′p
.

Proof: We can proceed as in the proof for bounding the Rademacher complexity of Hp, except for bounding the following term:

If: $$\left(\sum_{k=1}^p\|\mathbf{w}_k\|^q\right)^{1/q}=\left[\sum_{k=1}^p\mu_k^q(\boldsymbol{\alpha}^\top\mathbf{K}_k\boldsymbol{\alpha})^{q/2}\right]^{1/q}$$ $$=\left[\sum_{k=1}^p\mu_k^2(\mu_k^{\frac{2(q-2)}{q}}\boldsymbol{\alpha}^\top\mathbf{K}_k\boldsymbol{\alpha})^{q/2}\right]^{1/q}$$ $$\leq\left[(\sum_{k=1}^p\mu_k^2\,\mu_k^{\frac{2(q-2)}{q}}\boldsymbol{\alpha}^\top\mathbf{K}_k\boldsymbol{\alpha})^{q/2}\right]^{1/q}\quad\text{(convexity)}$$ $$=\sqrt{\sum_{k=1}^p\mu_k^{\frac{4(q-1)}{q}}\boldsymbol{\alpha}^\top\mathbf{K}_k\boldsymbol{\alpha}}.$$

Assume now that q > 4/3, which implies 4(q−1)
q < 1. Then, since µk ∈ [0, 1], this implies µ 4(q−1)
q k ≤ µk.

Thus, for any q > 4/3, we can write:

$$\left(\sum_{k=1}^{p}\|\mathbf{w}_{k}\|^{q}\right)^{1/q}\leq{\sqrt{\sum_{k=1}^{p}\mu_{k}\alpha^{\top}\mathbf{K}_{k}\alpha}}={\sqrt{\alpha^{\top}\mathbf{K}\alpha}}\leq1/\rho^{2}.$$

Taking the limit q → 4/3 shows that the inequality is also verified for q = 4/3. Thus, as in the proof for Hp, the Rademacher complexity can be bounded as follows

$$\widehat{\mathfrak{R}}_{S}(H_{p}^{\prime})\leq\frac{\|\mathbf{\tau}\|_{r}}{m\rho}\quad\text{with}\mathbf{\tau}=(\sqrt{r\operatorname{Tr}[\mathbf{K}_{1}]},\ldots,\sqrt{r\operatorname{Tr}[\mathbf{K}_{p}]})^{\top},$$

but here r is an even integer such that 1/r = 1 − 1/q ≥ 1 − 3/**4 = 1**/4, that is r ≤ 4. Assume that Kk(**x, x**) ≤ R2for all x ∈ X and k ∈ [1, p]. Then, Tr[Kk] ≤ mR2for any k ∈ [1, p], thus, for r = 4, the Rademacher complexity can be bounded as follows

$$\widehat{\Re}_{S}(H_{p}^{\prime})\leq\frac{1}{m\rho}(p(\sqrt{4m R^{2}})^{4})^{1/4}=2p^{1/4}\sqrt{\frac{R^{2}/\rho^{2}}{m}}.$$
