Ranking via Robust Binary Classification
We propose RoBiRank, a ranking algorithm that is motivated by observing a close connection between evaluation metrics for learning to rank and loss functions for robust classification. It shows competitive performance on standard benchmark datasets against a number of other representative algorithms in the literature. We also discuss extensions of RoBiRank to large scale problems where explicit feature vectors and scores are not given. We show that RoBiRank can be efficiently parallelized across a large number of machines; for a task that requires 386, 133 × 49, 824, 519 pairwise interactions between items to be ranked, RoBiRank finds solutions that are of dramatically higher quality than that can be found by a state-of-the-art competitor algorithm, given the same amount of wall-clock time for computation.
In this paper, the authors proposed a ranking algorithm named RoBiRank, which is motivated by their interesting observation of the connection between evaluation metrics for learning to rank and loss functions for robust classification. The proposed RoBiRank shows competitive performance comparing with recent advances, and further the authors extend the algorithm in order to be applied for large scale problems. Quality: this paper brings the connection between two seemly unrelated problems -- robust classification and learning to rank under a general framework, and proposes to address the problem of learning to rank from a robust binary classification perspective. The proposed loss function is not convex, and the authors propose to optimize the lower bound of the metrics, which is continuous and twice differentiable. The standard l2 regularizer is applied to the model, and the optimization is performed via the standard gradient-based optimization approach. The empirical results are extensive given the use of multiple real-world datasets and comparing with 8 existing algorithms. In addition, the authors further proposed the linearization trick leading to parallelization for the optimization, and demonstrated the performance on the Million Song Dataset; by comparing with Weston et al, the authors demonstrated that their algorithm outperforms the earlier work. Clarity: the paper is overall well written, and there are just a few very minor problems that I have mentioned below. Originality: the proposed new loss function for ranking can be seen as (1) applying logistic loss on the difference between the item-context utility between an observed pairs, and (2) further applying a transformation function with slower rate that can lead to robustness. Note that the transformation function used in the Step 2 has been proposed in Ding [9] as cited in the paper. Given these facts and the use of the standard l2 norm on the weight, I found that the model itself is incremental. But I feel that the parallelization for the optimization algorithm is non-trivial. Significance: the proposed model and algorithm enjoyed better performances evaluated with different metrics (e.g., precision, NDCG), based on which I think the paper is making significant contributions to the machine learning community. I have some questions/comments below: 1. The notation \Y_{x} does not seem to be define when first introduced in line no. 119. It seems that this notation is defined later in line no. 255. and I suggest that the authors correct this minor problem. 2. Could the authors provide some analyses concerning how tight is bound for the objective function in (10)?3. Concerning the evaluation metrics, I am wondering if the NDCG is the correct metric used to report the results. The reason is that the proposed model in this paper is optimization this metric, while for Rank-SVM the objective function is not NDCG.  4. could the author provide further analysis regarding the convergence rate for the proposed algorithm?