Fast Learning Rate of lp-MKL and its Minimax Optimality
arXiv:1103.5202
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.
16 pages, submitted to COLT2011
References in corpus (8)
- High-dimensional additive modeling
- 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
- L2 Regularization for Learning Kernels
- Sparsity in multiple kernel learning
- A Unifying View of Multiple Kernel Learning
- Minimax-optimal rates for sparse additive models over kernel classes via convex programming
- Regularization Strategies and Empirical Bayesian Learning for MKL
- Non-Sparse Regularization for Multiple Kernel Learning