基于随机素描方法的在线核回归

Online kernel regression based on random sketching method

在线核回归学习中,每当一个新的样本到来,训练器都需要计算核矩阵的逆矩阵,这个过程的计算复杂度至少为关于回合数的平方级别。提出将素描方法应用于假设的更新,给出一个基于素描方法的更高效的在线核回归算法。首先,将损失函数设定为平方损失,应用Nystr?m近似方法来近似核,并借鉴跟导方法(FTL)的思想,提出一个新的梯度下降算法,称之为FTL-在线核回归(F-OKR);然后,应用素描方法对其加速,使得F-OKR的计算复杂度降低到关于回合数和素描规模线性、关于数据维度平方的级别;最后,设计了一个高效的素描在线核回归算法(SOKR)。与F-OKR相比,SOKR的精度几乎没有影响,而同时在适当的数据集上,运行时间减少16.7%左右。在理论上证得了两种算法的亚线性后悔界。实验结果也验证了所提算法与Nystr?m在线梯度下降算法(NOGD)相比有更好的表现,平均损失降低约64%。

In online kernel regression learning,the inverse matrix of the kernel matrix needs to be calculated when a new sample arrives,and the computational complexity is at least the square of the number of rounds.The idea of applying sketching method to hypothesis updating was introduced,and a more efficient online kernel regression algorithm via sketching method was proposed.Firstly,The loss function was set as the square loss,a new gradient descent algorithm,called FTL-Online Kernel Regression(F-OKR)was proposed,using the Nystr?m approximation method to approximate the Kernel,and applying the idea of Follow-The-Leader(FTL).Then,sketching method was used to accelerate F-OKR so that the computational complexity of F-OKR was reduced to the level of linearity with the number of rounds and sketch scale,and square with the data dimension.Finally,an efficient online kernel regression algorithm called Sketched Online Kernel Regression(SOKR)was designed.Compared to F-OKR,SOKR had no change in accuracy and reduced the runtime by about 16.7% on some datasets.The sub-linear regret bounds of these two algorithms were proved,and experimental results on standard regression datasets also verify that the algorithms have better performance than NOGD(Nystr?m Online Gradient Descent)algorithm,the average loss of all the datasets was reduced by about 64%.