The convergence rate of a regularized ranking algorithm. (English) Zbl 1252.68225

Summary: We investigate the generalization performance of a regularized ranking algorithm in a reproducing kernel Hilbert space associated with least square ranking loss. An explicit expression for the solution via a sampling operator is derived and plays an important role in our analysis. Convergence analysis for learning a ranking function is provided, based on a novel capacity independent approach, which is stronger than for previous studies of the ranking problem.


68T05 Learning and adaptive systems in artificial intelligence
68Q32 Computational learning theory
62D05 Sampling theory, sample surveys
62F05 Asymptotic properties of parametric tests
46E22 Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces)
Full Text: DOI


[1] Agarwal, S.; Graepel, T.; Herbrich, R.; Har-Peled, S.; Roth, D., Generalization bounds for the area under the ROC curve, J. Mach. Learn. Res., 6, 393-425 (2005) · Zbl 1222.68129
[2] Agarwal, S.; Niyogi, P., Generalization bounds for ranking algorithms via algorithmic stability, J. Mach. Learn. Res., 10, 441-474 (2009) · Zbl 1235.68123
[3] Aronszajn, N., Theory of reproducing kernels, Trans. Amer. Math. Soc., 68, 337-404 (1950) · Zbl 0037.20701
[4] Clémencon, S.; Lugosi, G.; Vayatis, N., Ranking and empirical minimization of U-statistics, Ann. Statist., 36, 844-874 (2008) · Zbl 1181.68160
[5] Cossock, D.; Zhang, T., Statistical analysis of Bayes optimal subset ranking, IEEE Trans. Inf. Theory, 54, 11, 5140-5154 (2008) · Zbl 1319.62042
[6] Mukherjee, S.; Zhou, D. X., Learning coordinate covariances via gradients, J. Mach. Learn. Res., 7, 519-549 (2006) · Zbl 1222.68270
[7] Rudin, C.; Schapire, R. E., Margin-based ranking and an equivalence between adaBoost and rankBoost, J. Mach. Learn. Res., 10, 2193-2232 (2009) · Zbl 1235.68186
[8] Rudin, C., The P-norm push: a simple convex ranking algorithm that concentrates at the top of the list, J. Mach. Learn. Res., 10, 2233-2271 (2009) · Zbl 1235.68185
[9] Smale, S.; Zhou, D. X., Shannon sampling II. Connections to learning theory, Appl. Comput. Harmon. Anal., 19, 285-302 (2005) · Zbl 1107.94008
[10] Smale, S.; Zhou, D. X., Learning theory estimates via integral operators and their approximations, Constr. Approx., 26, 153-172 (2007) · Zbl 1127.68088
[11] Sun, H. W.; Wu, Q., Application of integral operator for regularized least square regression, Math. Comput. Modeling, 49, 276-285 (2009) · Zbl 1165.45310
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.