On the Consistency of Ranking Algorithms

By John C. Duchi, Lester W. Mackey, Michael I. Jordan. 2010

106 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Evaluation & Benchmarks

Citations in the corpus

Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, methodology): “[11] established such a result for the value-regularized linear surrogate for ranking (which resembles the pairwise disagreement, PD, loss).”
On Structured Prediction Theory with Calibrated Convex Surrogate Losses (2017, methodology): “For example, for a bounded from below and continuous surrogate, Definition 3 with η = 0 is equivalent to infinite-sample consistency (Zhang, 2004a), classification calibration (Tewari & Bartlett, 2007), edge-consistency (Duchi et al., 2010), (L,R)calibration (Ramaswamy & Agarwal, 2016), prediction c”
Minimax-optimal Inference from Partial Rankings (2014, background): “While consistency of various rank aggregation algorithms has been studied when a growing number of sampled partial preferences is observed over a fixed number of items [5, 6], little is known in the high-dimensional setting where the number of items and number of observed partial rankings scale simu”
A Consistent Regularization Approach for Structured Prediction (2016, background): “Indeed, in the last few years, an effort has been made to analyze speciﬁc structured problems, such as multiclass classiﬁcation [5], multi-labeling [6], ranking [7] or quantile estimation [8].”
Learning Scoring Functions with Order-Preserving Losses and Standardized Supervision (2011, background): “Y is the following (Duchi et al., 2010, Def.”
A Survey of Preference-Based Reinforcement Learning Methods (2017, background): “To do so, we can define a scalar objective as the weighted pairwise disagreement loss L, as introduced by Duchi et al. (2010), L(π, ζ) = N∑ i=1 αiL(π, ζi), (3) where αi is the weight or importance assigned to ζi.”
Convex Calibrated Surrogates for Low-Rank Loss Matrices with Applications to Subset Ranking Losses (2013, methodology): “AT gratefully acknowledges the support of NSF under grant IIS-1319810.”
Quantum machine learning: a classical perspective (2017, methodology): “regularization methods for kernel-regularized least squares [22,29,76] (see §3) achieve the optimal learning rate of =O(N−1/2) while requiring only Õ(N2) operations.”
Convex Calibration Dimension for Multiclass Loss Matrices (2014, methodology): “As discussed recently by Duchi et al. [10] and Calauz`enes et al. [5], such an approach cannot be consistent for the PD and MAP losses, since these losses do not admit convex calibrated surrogates in r dimensions that can be used together with the sorting operation.”
On the Consistency of Multi-Label Learning (2011, unknown): “…on optimizing a surrogate loss function has been well-studied for binary classiﬁcation (Zhang, 2004b; Steinwart, 2005; Bartlett et al., 2006), multi-class classiﬁcation (Zhang, 2004a; Tewari and Bartlett, 2007), learning to rank (Cossock and Zhang, 2008; Xia et al., 2008; Duchi et al., 2010), etc.”
Iterative ranking from pair-wise comparisons (2012, background): “Furthermore, producing such scores are ubiquitous [17] as they may also be used to calculate the desired rankings.”
Consistent Multiclass Algorithms for Complex Performance Measures (2015, background): “, 2004; Tewari & Bartlett, 2007), losses for specific problems such as multilabel classification (Gao & Zhou, 2011) and ranking (Cossock & Zhang, 2008; Xia et al., 2008; Duchi et al., 2010; Ravikumar et al., 2011; Buffoni et al., 2011; Calauzènes et al., 2012), and some work on general multiclass lo”
A Theoretical Analysis of NDCG Type Ranking Measures (2013, background): “The research of consistency for ranking was initiated in [14, 17].”
Bipartite Ranking through Minimization of Univariate Loss (2011, background): “The basic idea is to reduce ranking to binary classification by treating each pair of instances (x, x′) as a single object, to be classified as positive if x should precede x′ and as negative if x should ranked below x′ (Herbrich et al., 1999; Freund et al., 2003; Agarwal et al., 2005; Duchi et al.,”
Cross-Entropy Loss Functions: Theoretical Analysis and Applications (2023, background): “…Dembczynski et al., 2012; Zhang et al., 2020b), learning with rejection (Cortes et al., 2016b;a; Ramaswamy et al., 2015; Cao et al., 2022), ranking (Duchi et al., 2010; Ravikumar et al., 2011; Ramaswamy et al., 2013; Gao & Zhou, 2015; Uematsu & Lee, 2017; Mao et al., 2023), cost-sensitive…”