Online Multikernel Learning Method via Online Biconvex Optimization

Random feature-based online multikernel learning (RF-OMKL) is a promising low-complexity framework for machine learning optimization from continuous streaming data. Nonetheless, it is still an open problem to find an efficient algorithm with an analytical performance guarantee due to the challenge of an underlying online biconvex optimization (OBO). The state-of-the-art method [named expert-based online multikernel learning (EoKle)] tackled this problem approximately with the lens of expert-based online learning, in which multiple kernels (or experts) optimize their own kernel functions separately and the best sole one is determined via Hedge algorithm. It is asymptotically optimal as to the best sole kernel function in hindsight. We propose collaborative expert-based online multikernel learning (CoKle) by devising a collaborative Hedge (CoHedge) algorithm, in which kernel functions separately optimized as in EoKle are combined in an asymptotically optimal way. It is proved that CoKle is asymptotically optimal as to the best combination of each optimal kernel function in hindsight. Remarkably, this is the first method with a theoretical performance guarantee for expert-based RF-OMKL. Despite its effectiveness, CoKle is inherently suboptimal due to the individual optimization of kernel functions. We address this by presenting an OBO-based method (named BoKle) and partially prove its asymptotic optimality for RF-OMKL. Thus, BoKle can outperform the suboptimal expert-based methods such as CoKle and EoKle. Finally, we demonstrate the superiority of BoKle via experiments with real datasets.