Convex Calibrated Surrogates for Low-Rank Loss Matrices with Applications to Subset Ranking Losses
The design of convex, calibrated surrogate losses, whose minimization entails consistency with respect to a desired target loss, is an important concept to have emerged in the theory of machine learning in recent years. We give an explicit construction of a convex least-squares type surrogate loss that can be designed to be calibrated for any multiclass learning problem for which the target loss matrix has a low-rank structure; the surrogate loss operates on a surrogate target space of dimension at most the rank of the target loss. We use this result to design convex calibrated surrogates for a variety of subset ranking problems, with target losses including the precision@q, expected rank utility, mean average precision, and pairwise disagreement.
The paper demonstrates calibrated convex surrogate 
      losses for multiclass classification. If the n by k loss matrix (where the 
      label set has size n and the prediction set has size k) has rank d, 
      minimizing this surrogate loss corresponds to a d-dimensional least 
      squares problem, and converting the solution to a prediction corresponds 
      to a d-dimensional linear maximization over a set of size k. The paper 
      describes two examples (precision at q and expected rank utility) for 
      which n and k are exponentially large, but predictions can be calculated 
      efficiently. It describes two more examples (mean average precision and 
      pairwise disagreement) with exponential n and k for which the calibrated 
      predictions apparently cannot be calculated efficiently, but efficiently 
      computable predictions are calibrated for restricted sets of probability 
      distributions. This is an exciting contribution that seems to be 
      important for a wide variety of multiclass losses of great practical 
      significance. Technically, it is a combination of two results from ref 
      [16] - the important low rank observation appeared already in [16]. The 
      paper is clearly written. The main criticism is of the results on 
      calibration with respect to restricted sets of probability distributions. 
      For instance, Theorem 4 gives a result that the efficiently computable 
      prediction rule is calibrated for a certain family P_reinforce. Why is 
      this family interesting? What is the intuition behind it? Are there 
      interesting examples of distributions that satisfy these conditions? 
      Similar questions apply to the set of distributions considered in Theorem 
      7. Minor comments: line 227: 1(\sigma^{-1}(i)\leq q) should be 
      1(\sigma(i)\le q). (Similarly at line 236) 242: 1 and 0 interchanged. 
      254: Having max(y_i-v,0) in place of simply y_i seems silly. Why not 
      just redefine the set of labels as {0,1,...,s-v}^r? 320: u^p_{ij} is 
      only defined for i\geq j. The appendix mentions that it is made symmetric, 
      but not the paper.