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

在线核回归学习中,每当一个新的样本到来,训练器都需要计算核矩阵的逆矩阵,这个过程的计算复杂度至少为关于回合数的平方级别.提出将素描方法应用于假设的更新,给出一个基于素描方法的更高效的在线核回归算法.首先,将损失函数设定为平方损失,应用Nystr?m近似方法来近似核,并借鉴跟导方法(FTL)的思想,提出一个新的梯度下降算...

Online kernel regression based on random sketching method

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%.