TY - JOUR
T1 - Online regularized learning with pairwise loss functions
AU - Guo, Zheng-Chu
AU - Ying, Yiming
AU - Zhou, Ding-Xuan
PY - 2017/2/1
Y1 - 2017/2/1
N2 - Recently, there has been considerable work on analyzing learning algorithms with pairwise loss functions in the batch setting. There is relatively little theoretical work on analyzing their online algorithms, despite of their popularity in practice due to the scalability to big data. In this paper, we consider online learning algorithms with pairwise loss functions based on regularization schemes in reproducing kernel Hilbert spaces. In particular, we establish the convergence of the last iterate of the online algorithm under a very weak assumption on the step sizes and derive satisfactory convergence rates for polynomially decaying step sizes. Our technique uses Rademacher complexities which handle function classes associated with pairwise loss functions. Since pairwise learning involves pairs of examples, which are no longer i.i.d., standard techniques do not directly apply to such pairwise learning algorithms. Hence, our results are a non-trivial extension of those in the setting of univariate loss functions to the pairwise setting.
AB - Recently, there has been considerable work on analyzing learning algorithms with pairwise loss functions in the batch setting. There is relatively little theoretical work on analyzing their online algorithms, despite of their popularity in practice due to the scalability to big data. In this paper, we consider online learning algorithms with pairwise loss functions based on regularization schemes in reproducing kernel Hilbert spaces. In particular, we establish the convergence of the last iterate of the online algorithm under a very weak assumption on the step sizes and derive satisfactory convergence rates for polynomially decaying step sizes. Our technique uses Rademacher complexities which handle function classes associated with pairwise loss functions. Since pairwise learning involves pairs of examples, which are no longer i.i.d., standard techniques do not directly apply to such pairwise learning algorithms. Hence, our results are a non-trivial extension of those in the setting of univariate loss functions to the pairwise setting.
KW - Online learning
KW - Pairwise learning
KW - Regularization
KW - RKHS
UR - http://www.scopus.com/inward/record.url?scp=84982111962&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84982111962&origin=recordpage
U2 - 10.1007/s10444-016-9479-7
DO - 10.1007/s10444-016-9479-7
M3 - RGC 21 - Publication in refereed journal
SN - 1019-7168
VL - 43
SP - 127
EP - 150
JO - Advances in Computational Mathematics
JF - Advances in Computational Mathematics
IS - 1
ER -