Kernel-based Online Pairwise Learning and Distributed Learning


Student thesis: Doctoral Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date1 Aug 2018


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- fp||p2 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 fp 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- fp||p2 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 ||ӯ- y||2, 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.

    Research areas

  • Reproducing Kernel Hilbert Space, Online Learning, Pairwise Learning, Iterative Hard Thresholding, Distributed Learning