2012/06/18 by Peilin Zhao, Jialei Wang, Zhao, Peilin +7
Decision Sciences · Engineering · Computer Science · #Advanced Bandit Algorithms Research #Sparse and Compressive Sensing Techniques #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1206.4633
Kernel-based online learning has often shown state-of-the-art performance for\nmany online learning tasks. It, however, suffers from a major shortcoming, that\nis, the unbounded number of support vectors, making it non-scalable and\nunsuitable for applications with large-scale datasets. In this work, we study\nthe problem of bounded kernel-based online learning that aims to constrain the\nnumber of support vectors by a predefined budget. Although several algorithms\nhave been proposed in literature, they are neither computationally efficient\ndue to their intensive budget maintenance strategy nor effective due to the use\nof simple Perceptron algorithm. To overcome these limitations, we propose a\nframework for bounded kernel-based online learning based on an online gradient\ndescent approach. We propose two efficient algorithms of bounded online\ngradient descent (BOGD) for scalable kernel-based online learning: (i) BOGD by\nmaintaining support vectors using uniform sampling, and (ii) BOGD++ by\nmaintaining support vectors using non-uniform sampling. We present theoretical\nanalysis of regret bound for both algorithms, and found promising empirical\nperformance in terms of both efficacy and efficiency by comparing them to\nseveral well-known algorithms for bounded kernel-based online learning on\nlarge-scale datasets.\n