Adaptive Stopping Rule for Kernel-based Gradient Descent Algorithms

In this paper, we propose an adaptive stopping rule for kernel-based gradient descent (KGD) algorithms. We introduce the empirical effective dimension to quantify the increments of iterations in KGD and derive an implementable early stopping strategy. We analyze the performance of the adaptive stopping rule in the framework of learning theory. Using the recently developed integral operator approach, we rigorously prove the opti-mality of the adaptive stopping rule in terms of showing the optimal learning rates for KGD equipped with this rule. Furthermore, a sharp bound on the number of iterations in KGD equipped with the proposed early stopping rule is also given to demonstrate its computational advantage. Introduction In financial studies, clinical medicine, gene analysis and engineering applications, data of input-output pairs are collected to pursue the relation between input and output. Kernel methods [14], which map input points from the input space to some feature space and then synthesize the estimator in the feature space, have been widely used for this purpose. The research was supported by the National Natural Science Foundation of China [Grant Nos. To overcome their computational and storage bottlenecks, numerous techniques (e,g, the distributed learning [41, 22], localized learning [27] and random sketching [17, 39]) have been further developed to equip kernel methods in the recent era of big data. KGD, as a popular realization of kernel methods, succeeds in avoiding the saturation of KRR in theory [16], reducing the computational burden of KPCA in computation [13], and benefiting in scalability when compared with KPLS and KCG [23]. Therefore, it has been widely used in regression [40], classification [37] and minimum error entropy principle analysis [21].