Kernel-based Online Pairwise Learning and Distributed Learning

Abstract

In learning theory, statistical efficiency and learning rates of various algorithms form important research topics. In this thesis we study these topics and evaluate specific algorithms theoretically, by using techniques such as kernel methods, covering numbers and probability inequalities.

Firstly, we will review the general framework of learning theory, including Reproducing Kernel Hilbert Spaces, covering numbers and the principle of bias-variance trade off.

Secondly, we will present our research work on online pairwise learning algorithms. Online pairwise learning is a learning task in which new data enter to form pairs with old data in every iteration. In the existing literature, ||f_t - f_p||_p² of the learning error for the t-th iteration of the online learning algorithm is estimated of order O(t^-1/3). We make a significant improvement by showing that the K-norm of the target function f_p is bounded by a constant up to a logarithmic factor with high probability. We prove this new observation by using an iterative process. After this bound is verified, a refined bound O(t^-1/2+e) of the learning error ||f_t - f_p||_p² will be derived. We will also discuss the distributed online pairwise learning and demonstrate how the analysis is difficult.

Thirdly, we will consider learning rate estimation of a distributed iterative hard thresholding algorithm. The iterative hard thresholding is an algorithm which sets a hard threshold so that entries smaller than the threshold is forced to be zero in the next iteration. Due to the moving support of the resulting vector in every iteration, the distributed version is hard to estimate. By assuming the target function has a lower bound in every entry, the support can be proved to be fixed. We prove that a good bound of learning error, which is the difference of the average function and the target function ||ӯ_t - y||₂, can be reached, with the assumption of Restricted Isometry Property along with a lower bound of the target function y.

Finally, we discuss some research issues which will be considered in our future work.

Date of Award	1 Aug 2018
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Dingxuan ZHOU (Supervisor)