Fast Learning Rate of lp-MKL and its Minimax Optimality

Taiji SuzukiarXiv 2011 · DOI · arXiv

Abstract

In this paper, we present a new, sharp generalization bound for $\ell_p$-norm Multiple Kernel Learning ($\ell_p$-MKL). By employing localization techniques, we derive a learning rate that is characterized by the spectral decay rate of the associated kernels. We demonstrate that this derived rate achieves minimax optimality on the $\ell_p$-mixed-norm ball, providing a theoretical justification for the empirical success of $\ell_p$-MKL over traditional sparse methods.

Introduction

Supervised learning with kernel methods relies heavily on the choice of the kernel function. Multiple Kernel Learning (MKL) automates this by learning a combination of candidate kernels. While early research focused on sparse $\ell_1$-regularization, empirical evidence suggests that non-sparse $\ell_p$-regularization ($p > 1$) often yields higher accuracy. However, existing theoretical bounds for $\ell_p$-MKL were often "global" and pessimistic, suggesting a slow convergence rate of $O(1/\sqrt{n})$. This paper bridges the gap between theory and practice by deriving "fast" learning rates that account for kernel complexity.

Theoretical Framework and Notation

The analysis is grounded in the spectral properties of the Reproducing Kernel Hilbert Spaces (RKHS) involved. We assume the eigenvalues of the kernels decay at a rate of $k^{-1/s}$, where $s$ represents the complexity of the space. The key notations used throughout the analysis are defined in the table below.

Table of key notation and parameters used in the $\ell_p$-MKL analysis.

Methodology: Localization and Spectral Assumptions

To obtain sharper bounds, we utilize localization techniques, specifically local Rademacher complexity and peeling devices. Unlike global bounds that consider the entire function space, localization focuses on a neighborhood around the optimal solution.

The learning rate is determined by two main factors:

  1. Spectral Decay ($s$): A faster decay (smaller $s$) indicates simpler kernels and leads to faster convergence.
  2. $\ell_p$-Mixed-Norm Regularization: The analysis covers the general case $p \geq 1$, allowing for both sparse and dense kernel combinations.

Key Results

The primary result is a new convergence rate for the $\ell_2$-error: $$\text{Rate} \approx n^{-\frac{1}{1+s}} M^{1 - \frac{2s}{p(1+s)}}$$

Minimax Optimality

We prove that this bound is "sharp" by deriving a theoretical lower bound—the absolute best any algorithm could achieve—and showing that the $\ell_p$-MKL upper bound matches it. This confirms that $\ell_p$-MKL is minimax optimal on an $\ell_p$-mixed-norm ball.

Sparse vs. Dense Truths

  • Sparse Truth: If only a few kernels are relevant, $p=1$ provides the fastest rate.
  • Dense Truth: If many kernels contribute, the learning rate becomes largely independent of $p$, suggesting that solving MKL is as complex as solving $M$ individual kernel problems.

Conclusion and Future Work

This work provides the first sharp generalization bounds for $\ell_p$-MKL, showing it is theoretically optimal. While the results are robust for $p \geq 1$, future work could investigate the linear dependency on the number of kernels $M$ and explore the discrepancy between theoretical sparse optimality ($p=1$) and empirical dense performance ($p>1$) in certain contexts.

Summary updated

Abstract

In this paper, we give a new sharp generalization bound of lp-MKL which is a generalized framework of multiple kernel learning (MKL) and imposes lp-mixed-norm regularization instead of l1-mixed-norm regularization. We utilize localization techniques to obtain the sharp learning rate. The bound is characterized by the decay rate of the eigenvalues of the associated kernels. A larger decay rate gives a faster convergence rate. Furthermore, we give the minimax learning rate on the ball characterized by lp-mixed-norm in the product space. Then we show that our derived learning rate of lp-MKL achieves the minimax optimal rate on the lp-mixed-norm ball.
BibTeX
@misc{suzuki2011fast,
  author = {Taiji Suzuki},
  title = {{Fast Learning Rate of lp-MKL and its Minimax Optimality}},
  year = {2011},
  eprint = {1103.5202},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1103.5202},
}
Figure