Since E[σi**] = 0** for all i and since the Rademacher variables are independent, we can write E[σi1**. . . σ**il
] =

E[σi1] **· · ·**E[σil
] = 0 for any l distinct variables σi1**, . . . , σ**il
. Thus, Eσ
hσ
s1
1**· · ·** σ
sm
1 even, in which case Eσ hσ s1 1· · · σ smm i= 1. Therefore, the following inequality holds:1 E σ h Xm i=1 Φk(xi)  ri≤X 2t1+...+2tm=2r ′ 2r ′ 2t1,...,2tm Kk(x1, x1) t1· · · Kk(xm, xm) tm ≤ (2r ′) r ′ X t1+...+tm=r ′ r ′ t1,...,tm Kk(x1, x1) t1· · · Kk(xm, xm) tm = (2r ′ Tr[Kk])r ′ = (r Tr[Kk])r/2. Thus, the Rademacher complexity is bounded by
i= 0 unless all sis are

$$\widehat{\mathfrak{R}}_{S}(H_{p})\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 r.

Assume that Kk(**x, x**) ≤ R2for all x ∈ X and k ∈ [1, p]. Then, Tr[Kk] ≤ mR2for any k ∈ [1, p], thus the Rademacher complexity can be bounded as follows

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

For p > 1, the function r 7→ p 1/rr 1/2reaches its minimum at r0 **= 2 log** p. This gives

$$(6)$$
$$\widehat{\Re}_{S}(H_{p})\leq\sqrt{\frac{2e\,[\log p\,]R^{2}/\rho^{2}}{m}}.$$

It is likely that the constants in the bound of theorem can be further improved. We used a very rough upper bound for the multinomial coefficients. A finer bound using Sterling's approximation should provide a better result. Remarkably, the bound of the theorem has a very mild dependency with respect to p.

The theorem can be used to derive generalization bounds for learning kernels in classification, regression, and other tasks. We briefly illustrate its application to binary classification where the labels y are in {−1, +1}.

Let R(h) denote the generalization error of h ∈ Hp, that is R(h**) = Pr[**yh(x) < 0]. For a training sample S = ((x1, y1), . . . ,(xm, ym)) and any ρ > 0, let Rbρ(h) denote the fraction of the training points with margin less than or equal to ρ, that is Rbρ(h) = 1m Pm i=1 1yih(xi)≤ρ. Then, the following result holds.

Corollary 2 *For any* δ > 0, with probability at least 1 − δ*, the following bound holds for any* h ∈ Hp:

  **Corollary 2**: _10 for any $\sigma>0$, with probability at least $\tau$, for any limiting condition from any $n\in\mathbf{H}_{p}$,_  $$R(h)\leq\widehat{R}_{p}(h)+\frac{2\|\tau\|_{\mathbf{r}}}{m\rho}+2\sqrt{\frac{\log\frac{2}{\pi}}{2m}}.\tag{7}$$  _with $\mathbf{\tau}=(\sqrt{\tau\,\mathrm{Tr}[\mathbf{K}_{1}]},\ldots,\sqrt{\tau\,\mathrm{Tr}[\mathbf{K}_{p}]})^{\top}$, for any even integer $r>0$. If additionally, $K_{h}(x,x)\leq R^{2}$ for all $\tau\in\mathbf{H}_{p}$, then $\tau\in\mathbf{H}_{p}$._
$$\left(7\right)$$
x ∈ X and k ∈ [1, p]*, then, for* p > 1,
$$R(h)\leq\widehat{R}_{\rho}(h)+2\sqrt{\frac{2e\lceil\log p\rceil R^{2}/\rho^{2}}{m}}+2\sqrt{\frac{\log\frac{2}{\delta}}{2m}}.$$
Proof: With our definition of the Rademacher complexity, for any δ > 0, with probability at least 1 − δ, the following bound holds for any h ∈ Hp [12, 4]:

$$R(h)\leq\widehat{R}_{\rho}(h)+2\widehat{\Re}_{S}(H_{p})+2\sqrt{\frac{\log\frac{2}{\delta}}{2m}}.$$
$$(8)$$

1We use the following rather rough inequality:

$$\left(x_{1},\ldots,x_{m}\right)={\frac{(2r^{\prime})!}{(2t_{1})!\cdots(2t_{m})!}}\leq{\frac{(2r^{\prime})!}{(t_{1})!\cdots(t_{m})!}}\leq{\frac{(2r^{\prime})\cdots(r^{\prime}+1)\cdot r^{\prime}!}{(t_{1})!\cdots(t_{m})!}}\leq{\frac{(2r^{\prime})^{r^{\prime}}\cdot r^{\prime}!}{(t_{1})!\cdots(t_{m})!}}=(2r^{\prime})^{r^{\prime}}\left(t_{1},\ldots,t_{m}\right).$$
