"On the (Non-)existence of Convex, Calibrated Surrogate Losses for Ranking"

By Clément Calauzènes, Nicolas Usunier, Patrick Gallinari. 2012

52 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 Optimization & Training

Citations in the corpus

Quantifying Learning Guarantees for Convex but Inconsistent Surrogates (2018, methodology): “There have indeed been several works to analyze inconsistent surrogates [12, 18, 5, 14], but they usually end the story with proving that some surrogate (or a family or surrogates) is not consistent.”
On Structured Prediction Theory with Calibrated Convex Surrogate Losses (2017, background): “A large body of work specifically focuses on the related tasks of ranking (Duchi et al., 2010; Calauzènes et al., 2012; Ramaswamy et al., 2013) and ordinal regression (Pedregosa et al.”
Surrogate regret bounds for bipartite ranking via strongly proper losses (2012, background): “…for the bipartite instance ranking problem, where instances are labeled positive or negative and the goal is to learn a scoring function that minimizes the probability of mis-ranking a pair of positive and negative instances, or equivalently, that maximizes the area under the ROC curve [14, 1].”
Convex Calibration Dimension for Multiclass Loss Matrices (2014, methodology): “…are not calibrated for the PD loss, and conjectured that such convex calibrated surrogates (in r dimensions) do not exist; Calauz`enes et al. [5] showed that indeed there do not exist any r -dimensional convex surrogates that use argsort as the predictor and are calibrated for the PD loss.”
A Theoretical Analysis of NDCG Type Ranking Measures (2013, background): “This result was further generalized in [7, 9], where non-existence of convex surrogate loss with Average Precision and Expected Reciprocal Rank were proved.”
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”
Large-Scale Multi-label Text Classification - Revisiting Neural Networks (2013, background): “k Loss Recently, it has been claimed that none of convex loss functions including BP-MLL’s loss function (Equation 3) is consistent with respect to rank loss which is non-convex and has discontinuity [2, 9]. Furthermore, univariate surrogate loss functions such as log loss are rather consistent with”
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.”
Of quantiles and expectiles: consistent scoring functions, Choquet representations and forecast rankings (2015, background): “…for quite some time (see for example Bartlett et al. (2006), Tewari and Bartlett (2005), Zhang (2004), Steinwart (2007), Reid and Williamson (2011), Calauzènes et al. (2012, 2013), Scott (2012), Duchi et al. (2013), Menon and Williamson (2014), Agarwal and Agarwal (2015), Frongillo and Kash…”