1. Competitive Analysis of Online Kernel Selection in Unified Framework
- Author
-
LIAO Yun, ZHANG Xiao, LIAO Shizhong
- Subjects
competitive analysis ,online kernel selection ,expert advice framework ,metrical task systems ,unified framework ,Electronic computers. Computer science ,QA75.5-76.95 - Abstract
Online kernel selection aims to find the optimal kernel for online kernel learning at each round. It is one of the fundamental and critical problems of online kernel learning. A problem of online kernel selection can be reduced to a problem of expert advice framework, where the set of experts corresponds to the set of candidate kernels. Predictions are given according to the weights and advices of the set of experts, and the weights are updated at each round. Based on the reduction, while improving the regret bound, this paper proposes the concept of expected online kernel selection. Within the unified framework of expert advice framework and metric task system, this paper presents the regret bounds and competitive ratios of expected online kernel selection, and proves that the competitive ratio is stable in expanded loss ranges. Finally, this paper derives a competitive ratio combined with online kernel learning. The work of investigating online kernel selection within the unified framework guarantees not only a sublinear regret bound, but also a strong competitive ratio, comprehensively generalizing the concept of online kernel selection and paving the way for new online kernel selection research.
- Published
- 2020
- Full Text
- View/download PDF