# New Generalization Bounds For Learning Kernels

| Corinna Cortes Google Research New York   |               |
|-------------------------------------------|---------------|
| corinna@google.com                        | Mehryar Mohri |
| Courant Institute and Google Research     |               |
| mohri@cims.nyu.edu                        |               |

| Afshin Rostamizadeh Courant Institute New York University rostami@cs.nyu.edu   |
|--------------------------------------------------------------------------------|

## Abstract

This paper presents several novel generalization bounds for the problem of learning kernels based on the analysis of the Rademacher complexity of the corresponding hypothesis sets. Our bound for learning kernels with a convex combination of p base kernels has only a log p dependency on the number of kernels, p, which is considerably more favorable than the previous best bound given for the same problem. We also give a novel bound for learning with a linear combination of p base kernels with an L2 regularization whose dependency on p is only in p 1/4.

## 1 Introduction

Kernel methods are widely used in statistical learning [17, 18]. Positive definite symmetric (PDS) kernels specify an inner product in an implicit Hilbert space where large-margin methods are used for learning and estimation. They can be combined with algorithms such as support vector machines (SVMs) [5, 10, 20] or other kernel-based algorithms to form powerful learning techniques.

But, the choice of the kernel, which is critical to the success of the algorithm, is typically left to the user. Rather than requesting the user to commit to a specific kernel, which may not be optimal for the task, especially if the user's prior knowledge about the task is poor, learning kernel methods require him only to specify a family of kernels. The learning algorithm then selects both the specific kernel out of that family, and the hypothesis defined with respect to that kernel.

There is a large body of literature dealing with various aspects of the problem of learning kernels, including theoretical questions, optimization problems related to this problem, and experimental results [13, 15, 2, 1, 19, 16, 14, 23, 11, 3, 8, 22, 9]. Some of this previous work considers families of Gaussian kernels [15] or hyperkernels [16]. Non-linear combinations of kernels have been recently considered by
[21, 3, 9]. But, the most common family of kernels examined is that of non-negative combinations of some fixed kernels constrained by a trace condition, which can be viewed as an L1 regularization [13], or by an L2 regularization [8].

This paper presents several novel generalization bounds for the problem of learning kernels for the family of convex combinations of base kernels or linear combinations with an L2 constraint. One of the first learning bounds given by Lanckriet et al. [13] for the family of convex combinations of p base kernels is similar to that of Bousquet and Herrmann [6] and has the following form: R(h) ≤ Rbρ(h) +
O
√
1 m pmax p k=1 Tr(Kk**) max**p i=1(kKkk/ Tr(Kk))/ρ2where R(h) is the generalization error of a hypothesis h, Rρ(h) is the fraction of training points with margin less than or equal to ρ and Kk is the kernel matrix associated to the kth base kernel. This bound was later shown by Srebro and Ben-David [19] to be always larger than one. Another bound by Lanckriet et al. [13] for the family of linear combinations of base kernels was also shown by the same authors to be always larger than one.

But Lanckriet et al. [13] also presented a multiplicative bound for convex combinations of base kernels that is of the form R(h) ≤ Rbρ(h) + O
qp/ρ2 m
. This bound converges and can perhaps be viewed as the first informative generalization bound for this family of kernels. However, the dependence of the bound on the number of kernels p is multiplicative which therefore does not encourage the use of too many base kernels. Srebro and Ben-David [19] presented a generalization bound based on the pseudo-dimension of the family of kernels that significantly improved on this bound. Their bound has the form R(h) ≤ Rbρ(h) +
Oe qp+R2/ρ2 m
, where the notation Oe(·) hides logarithmic terms and where R is an upper bound on Kk(x, x)