Competitive Analysis of Online Kernel Selection in Unified Framework

doi:10.3778/j.issn.1673-9418.1905092

Abstract

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.

Key words: competitive analysis, online kernel selection, expert advice framework, metrical task systems, unified framework

摘要：

在线核选择旨在给出在线核学习每回合的最优核，是在线核学习的基础性和关键性问题。在线核选择问题可归约为专家建议框架问题，其中专家集对应候选核集；每回合，根据专家的权重及专家的建议给出预测结果，并更新专家的权重。基于这一归约，在改进已有后悔界的同时，提出期望在线核选择的概念，并应用专家建议框架与度量任务系统的统一框架，给出期望在线核选择问题的后悔界和竞争比，并证明该竞争比在损失拓展情况下是稳定的。最后，给出结合在线核学习方法的竞争比。该项工作全面推广了在线核选择的概念，在统一框架下，不仅可以得到亚线性后悔界，同时也能得到较强的竞争比，为在线核选择研究开辟了新的途径。

关键词: 竞争性分析, 在线核选择, 专家建议框架, 度量任务系统, 统一框架

LIAO Yun, ZHANG Xiao, LIAO Shizhong. Competitive Analysis of Online Kernel Selection in Unified Framework[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(7): 1126-1132.

廖芸，张骁，廖士中. 统一框架下在线核选择的竞争性分析[J]. 计算机科学与探索, 2020, 14(7): 1126-1132.

References

[1] Chapelle O, Vapnik V, Bousquet O, et al. Choosing multiple parameters for support vector machines[J]. Machine Learning, 2002, 46(1): 131-159.
[2] Feng C, Liao S Z. Model selection for Gaussian kernel sup-port vector machines in random Fourier feature space[J]. Journal of Computer Research and Development, 2016, 53(9): 1971-1978.冯昌, 廖士中. 随机傅里叶特征空间中高斯核支持向量机模型选择[J]. 计算机研究与发展, 2016, 53(9): 1971-1978.
[3] Bartlett P L, Mendelson S. Rademacher and Gaussian com-plexities: risk bounds and structural results[J]. Journal of Machine Learning Research, 2002, 3: 463-482.
[4] Liu Y, Liao S Z. Frame kernel selection via explicit descrip-tion of integral operator space[J]. Scientia Sinica Informa-tionis, 2016, 46(2): 165-178.刘勇, 廖士中. 基于积分算子空间显式描述的框架核选择方法[J]. 中国科学: 信息科学, 2016, 46(2): 165-178.
[5] Zhang X, Liao Y, Liao S Z. A survey on online kernel selec-tion for online kernel learning[J]. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 2019, 9(2): e1295.
[6] Yang T B, Mahdavi M, Jin R, et al. Online kernel selection: algorithms and evaluations[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence, Toronto, Jul 22-26, 2012. Menlo Park: AAAI, 2012: 1197-1203.
[7] Chen B D, Liang J L, Zheng N N, et al. Kernel least mean square with adaptive kernel size[J]. Neurocomputing, 2016, 191: 95-106.
[8] Nguyen T D, Le T, Bui H, et al. Large-scale online kernel learning with random feature reparameterization[C]//Procee-dings of the 26th International Joint Conference on Artifi-cial Intelligence, Melbourne, Aug 19-25, 2017. San Mateo: Morgan Kaufmann, 2017: 2543-2549.
[9] Zhang X, Liao S Z. Online kernel selection via incremental sketched kernel alignment[C]//Proceedings of the 27th Inter-national Joint Conference on Artificial Intelligence, Stock-holm, Jul 13-19,?2018. San Mateo: Morgan Kaufmann, 2018: 3118-3124.
[10] Zhang X, Liao S Z. Online kernel selection with local regret[J]. Chinese Journal of Computers, 2019, 42(1): 61-72.张骁, 廖士中. 基于局部后悔的在线核选择[J]. 计算机学报, 2019, 42(1): 61-72.
[11] Shalev-Shwartz S. Online learning and online convex optimi-zation[J]. Foundations and Trends in Machine Learning, 2011, 4(2): 107-194.
[12] Borodin A, El-Yaniv R. Online computation and competitive analysis[M]. New York: Cambridge University Press, 1998.
[13] Andrew L L H, Barman S, Ligett K, et al. A tale of two me-trics: simultaneous bounds on competitiveness and regret [C]//Proceedings of the 26th Annual Conference on Learning Theory, Princeton University, Jun 12-14, 2013: 741-763.
[14] Buchbinder N, Naor J. The design of competitive online alg-orithms via a primal-dual approach[J]. Foundations and Trends in Theoretical Computer Science, 2009, 3(2/3): 93-263.
[15] Huang Z. Online primal dual: beyond linear programs[J]. SIGACT News, 2014, 45(4): 105-119.
[16] Borodin A, Linial N, Saks M E. An optimal on-line algorithm for metrical task system[J]. Journal of the ACM, 1992, 39(4): 745-763.
[17] Cesa-Bianchi N, Lugosi G. Prediction, learning, and games[M]. New York: Cambridge University Press, 2006.
[18] Buchbinder N, Chen S, Naor J S, et al. Unified algorithms for online learning and competitive analysis[C]//Proceed-ings of the 25th Annual Conference on Learning Theory, Edinburgh, Jun 25-27, 2012.