关键词: 在线学习, 素描方法, 后悔分析, 回归, 核方法

Abstract:

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

Key words: online learning, sketching method, regret analysis, regression, kernel method