On empirical eigenfunction-based ranking with ℓ1ℓ1 norm regularization

The problem of ranking, in which the goal is to learn a real-valued ranking function that induces a ranking over an instance space, has recently gained increasing attention in machine learning. We study a learning algorithm for ranking generated by a regularized scheme with an ℓ1ℓ1 regularizer. The algorithm is formulated in a data dependent hypothesis space. Such a space is spanned by empirical eigenfunctions which are constructed by a Mercer kernel and the learning data. We establish the computations of empirical eigenfunctions and the representer theorem for the algorithm. Particularly, we provide an analysis of the sparsity and convergence rates for the algorithm. The results show that our algorithm produces both satisfactory convergence rates and sparse representations under a mild condition, especially without assuming sparsity in terms of any basis.