Trading off Consistency and Dimensionality of Convex Surrogates for Multiclass Classification

Consistent losses are well-motivated theoretically, yet for large n, such as in information retrieval and structured prediction tasks, their optimization may be computationally infeasible.