Sublinear Algorithms For Large-scale Kernel Learning

Support vector machines(SVM)and penalty logistic regression(PLR)are two important learning methods in machine learning,which enjoy sound theoretical basis.For linearly inseparable problems,both SVM and PLR can classify the data in high-dimensional linearly separable space by mapping the data in the original space through kernel method.In this case,the performance of linear SVM and PLR are far less than that of nonlinear models.However,the computational time complexity of nonlinear kernel learning problems will not lower than On~2 theoretically,where n represents the training set size,which prevents nonlinear SVM and PLR from being applied to large-scale datasets.To this end,two sublinear time optimization algorithms for nonlin-ear SVM and a sublinear time optimization algorithm for nonlinear PLR are designed respectively in this paper.First,the sublinear algorithm of SVM is proposed based on the gradient descent optimization method.Each iteration of the algorithm consists of a gradient descent up-date step and a projection step,we use the random Fourier feature map to map the sam-pled example into an explicit random feature space to perform the above steps,which makes the time complexity of each iteration is constant.We derive the convergence rate of the algorithm and prove that the time complexity that returns the?approximate solu-tion to the corresponding problem is independent of the training set size.Furthermore,by replacing the loss function in SVM with the exponential loss function,we can design a sublinear algorithm for nonlinear PLR based on the same method.Then,Based on subset selection technique and improved primal-dual optimiza-tion algorithm,another sublinear time optimization algorithm for nonlinear SVM is proposed.Theoretically,it is proved that the time complexity of the corresponding algorithm for solving SVM is independent of the training set size.At last,Experimental results on several large-scale datasets demonstrate that the proposed algorithms are efficient and effective.