Many classification tasks in machine learning lie beyond the classical binary and multi-class classification settings. In those tasks, the output elements are structured objects made of interdependent parts, such as sequences in natural language processing, images in computer vision, permutations in ranking or matching problems, etc. The structured prediction setting has two key properties that makes it radically different from multi-class classification, namely, the exponential growth of the size of the output space with the number of its parts, and the cost-sensitive nature of the learning task, as prediction mistakes are not equally costly. In this talk, I will present recent work on the design on loss functions that combine numerical efficiency and statistical consistency (joint work with Alessandro Rudi, Alex Nowak-Vila, Vivien Cabannes).