{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T00:40:57Z","timestamp":1776300057322,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:00:00Z","timestamp":1642809600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,3]]},"DOI":"10.1007\/s10994-021-06082-8","type":"journal-article","created":{"date-parts":[[2022,1,22]],"date-time":"2022-01-22T00:04:11Z","timestamp":1642809851000},"page":"937-976","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Worst-case regret analysis of computationally budgeted online kernel selection"],"prefix":"10.1007","volume":"111","author":[{"given":"Junfan","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0594-7116","authenticated-orcid":false,"given":"Shizhong","family":"Liao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,22]]},"reference":[{"key":"6082_CR1","unstructured":"Agarwal, A., Duchi, J.C., Bartlett, P.L., & Levrard, C. (2011). Oracle inequalities for computationally budgeted model selection. In Proceedings of the 24th Annual Conference on Learning Theory (pp. 69\u201386)."},{"key":"6082_CR2","unstructured":"Agarwal, A., Luo, H., Neyshabur, B., & Schapire, R.E. (2017). Corralling a band of bandit algorithms. In Proceedings of the 30th Annual Conference on Learning Theory (pp. 12\u201338)."},{"issue":"1","key":"6082_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000024","volume":"5","author":"S Bubeck","year":"2012","unstructured":"Bubeck, S., & Cesa-Bianchi, N. (2012). Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends\u00aein Machine Learning, 5(1), 1\u2013122.","journal-title":"Foundations and Trends\u00aein Machine Learning"},{"issue":"62","key":"6082_CR4","first-page":"1","volume":"20","author":"S Bubeck","year":"2019","unstructured":"Bubeck, S., Devanur, N. R., Huang, Z., & Niazadeh, R. (2019). Multi-scale online learning: Theory and applications to online auctions and pricing. Journal of Machine Learning Research, 20(62), 1\u201337.","journal-title":"Journal of Machine Learning Research"},{"key":"6082_CR5","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge University Press.","DOI":"10.1017\/CBO9780511546921"},{"key":"6082_CR6","unstructured":"Cesa-Bianchi, N., Mansour, Y., & Shamir, O. (2015). On the complexity of learning with kernels. In Proceedings of the 28th Annual Conference on Learning Theory (pp. 297\u2013325)."},{"key":"6082_CR7","first-page":"225","volume":"16","author":"K Crammer","year":"2003","unstructured":"Crammer, K., Kandola, J. S., & Singer, Y. (2003). Online classification on a budget. Advances in Neural Information Processing Systems, 16, 225\u2013232.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6082_CR8","first-page":"748","volume":"29","author":"A Cutkosky","year":"2016","unstructured":"Cutkosky, A., & Boahen, K. (2016). Online convex optimization with unconstrained domains and losses. Advances in Neural Information Processing Systems, 29, 748\u2013756.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"5","key":"6082_CR9","doi-asserted-by":"publisher","first-page":"1342","DOI":"10.1137\/060666998","volume":"37","author":"O Dekel","year":"2008","unstructured":"Dekel, O., Shalev-Shwartz, S., & Singer, Y. (2008). The forgetron: A kernel-based perceptron on a budget. SIAM Journal on Computing, 37(5), 1342\u20131372.","journal-title":"SIAM Journal on Computing"},{"key":"6082_CR10","first-page":"6022","volume":"30","author":"DJ Foster","year":"2017","unstructured":"Foster, D. J., Kale, S., Mohri, M., & Sridharan, K. (2017). Parameter-free online learning via model selection. Advances in Neural Information Processing Systems, 30, 6022\u20136032.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6082_CR11","first-page":"14741","volume":"32","author":"DJ Foster","year":"2019","unstructured":"Foster, D. J., Krishnamurthy, A., & Luo, H. (2019). Model selection for contextual bandits. Advances in Neural Information Processing Systems, 32, 14741\u201314752.","journal-title":"Advances in Neural Information Processing Systems"},{"issue":"2","key":"6082_CR12","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s10994-012-5319-2","volume":"90","author":"SCH Hoi","year":"2013","unstructured":"Hoi, S. C. H., Jin, R., Zhao, P., & Yang, T. (2013). Online multiple kernel classification. Machine Learning, 90(2), 289\u2013316.","journal-title":"Machine Learning"},{"key":"6082_CR13","first-page":"9427","volume":"32","author":"R J\u00e9z\u00e9quel","year":"2019","unstructured":"J\u00e9z\u00e9quel, R., Gaillard, P., & Rudi, A. (2019). Efficient online learning with kernels for adversarial large scale problems. Advances in Neural Information Processing Systems, 32, 9427\u20139436.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6082_CR14","doi-asserted-by":"crossref","unstructured":"Jin, R., Hoi, S.C.H., & Yang, T. (2010). Online multiple kernel learning: Algorithms and mistake bounds. In Proceedings of the 21st International Conference on Algorithmic Learning Theory (pp. 390\u2013404)","DOI":"10.1007\/978-3-642-16108-7_31"},{"issue":"8","key":"6082_CR15","doi-asserted-by":"publisher","first-page":"2165","DOI":"10.1109\/TSP.2004.830991","volume":"52","author":"J Kivinen","year":"2004","unstructured":"Kivinen, J., Smola, A. J., & Williamson, R. C. (2004). Online learning with kernels. IEEE Transactions on Signal Processing, 52(8), 2165\u20132176.","journal-title":"IEEE Transactions on Signal Processing"},{"issue":"3","key":"6082_CR16","first-page":"1","volume":"20","author":"A Koppel","year":"2019","unstructured":"Koppel, A., Warnell, G., Stump, E., & Ribeiro, A. (2019). Parsimonious online learning with kernels via sparse projections in function space. Journal of Machine Learning Research, 20(3), 1\u201344.","journal-title":"Journal of Machine Learning Research"},{"key":"6082_CR17","unstructured":"Kothari, P.K., & Livni, R. (2020). On the expressive power of kernel methods and the efficiency of kernel learning by association schemes. In Proceedings of the31st International Conferences on Algorithmic Learning Theory (pp 422\u2013450)."},{"issue":"47","key":"6082_CR18","first-page":"1","volume":"17","author":"J Lu","year":"2016","unstructured":"Lu, J., Hoi, S. C. H., Wang, J., Zhao, P., & Liu, Z. (2016). Large scale online kernel learning. Journal of Machine Learning Research, 17(47), 1\u201343.","journal-title":"Journal of Machine Learning Research"},{"key":"6082_CR19","first-page":"2724","volume":"26","author":"B McMahan","year":"2013","unstructured":"McMahan, B., & Abernethy, J. (2013). Minimax optimal algorithms for unconstrained linear optimization. Advances in Neural Information Processing Systems, 26, 2724\u20132732.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6082_CR20","unstructured":"McMahan, H.B., & Orabona, F. (2014). Unconstrained online linear learning in hilbert spaces: Minimax algorithms and normal approximations. In Proceedings of The 27th Conference on Learning Theory (pp. 1020\u20131039)."},{"key":"6082_CR21","unstructured":"Muthukumar, V., Ray, M., Sahai, A., & Bartlett, P. (2019). Best of many worlds: Robust model selection for online supervised learning. In Proceedings of the 22nd International Conference on Artificial Intelligence and Statistics (pp. 3177\u20133186)."},{"key":"6082_CR22","doi-asserted-by":"crossref","unstructured":"Nguyen, T.D., Le, T., Bui, H., & Phung, D. (2017). Large-scale online kernel learning with random feature reparameterization. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (pp. 2543\u20132549).","DOI":"10.24963\/ijcai.2017\/354"},{"key":"6082_CR23","first-page":"1806","volume":"26","author":"F Orabona","year":"2013","unstructured":"Orabona, F. (2013). Dimension-free exponentiated gradient. Advances in Neural Information Processing Systems, 26, 1806\u20131814.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"6082_CR24","first-page":"2643","volume":"10","author":"F Orabona","year":"2009","unstructured":"Orabona, F., Keshet, J., & Caputo, B. (2009). Bounded kernel-based online learning. Journal of Machine Learning Research, 10, 2643\u20132666.","journal-title":"Journal of Machine Learning Research"},{"key":"6082_CR25","doi-asserted-by":"crossref","unstructured":"Sahoo, D., Hoi, S.C.H., & Li, B. (2014). Online multiple kernel regression. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD (pp. 293\u2013302).","DOI":"10.1145\/2623330.2623712"},{"key":"6082_CR26","unstructured":"Seldin, Y., Bartlett, P.L., Crammer, K., & Abbasi-Yadkori, Y. (2014). Prediction with limited advice and multiarmed bandits with paid observations. In Proceedings of the 31st International Conference on Machine Learning (pp. 280\u2013287)."},{"issue":"1","key":"6082_CR27","first-page":"3103","volume":"13","author":"Z Wang","year":"2012","unstructured":"Wang, Z., Crammer, K., & Vucetic, S. (2012). Breaking the curse of kernelization: Budgeted stochastic gradient descent for large-scale SVM training. Journal of Machine Learning Research, 13(1), 3103\u20133131.","journal-title":"Journal of Machine Learning Research"},{"key":"6082_CR28","doi-asserted-by":"crossref","unstructured":"Yang, T., Mahdavi, M., Jin, R., Yi, J., & Hoi, S.C.H. (2012). Online kernel selection: Algorithms and evaluations. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (pp 1197\u20131202).","DOI":"10.1609\/aaai.v26i1.8298"},{"key":"6082_CR29","unstructured":"Zhang, L., Yi, J., Jin, R., Lin, M., & He, X. (2013). Online kernel learning with a near optimal sparsity bound. In Proceedings of the 30th International Conference on Machine Learning (pp. 621\u2013629)."},{"key":"6082_CR30","doi-asserted-by":"crossref","unstructured":"Zhang, X., & Liao, S. (2018). Online kernel selection via incremental sketched kernel alignment. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (pp. 3118\u20133124).","DOI":"10.24963\/ijcai.2018\/433"},{"key":"6082_CR31","doi-asserted-by":"crossref","unstructured":"Zhang, X., & Liao, S. (2020). Hypothesis sketching for online kernel selection in continuous kernel space. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (pp. 2498\u20132504).","DOI":"10.24963\/ijcai.2020\/346"},{"key":"6082_CR32","unstructured":"Zhao, P., Wang, J., Wu, P., Jin, R., & Hoi, SCH. (2012). Fast bounded online gradient descent algorithms for scalable kernel-based online learning. In Proceedings of the 29th International Conference on Machine Learning (pp. 1075\u20131082)."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06082-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-021-06082-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-021-06082-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T01:04:52Z","timestamp":1674349492000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-021-06082-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,22]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,3]]}},"alternative-id":["6082"],"URL":"https:\/\/doi.org\/10.1007\/s10994-021-06082-8","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,22]]},"assertion":[{"value":"15 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"custom code.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}},{"value":"Not applicable.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}