Fenchel-Young losses are a family of convex loss functions,encompassing the squared, logistic and sparsemax losses, among others.Each Fenchel-Young loss is implicitly associated with a link function, formapping model outputs to predictions. For instance, the logistic loss isassociated with the soft argmax link function. Can we build new loss functionsassociated with the same link function as Fenchel-Young losses?In this paper, we introduce Fitzpatrick losses, a new family of convex lossfunctions based on the Fitzpatrick function. A well-known theoretical tool inmaximal monotone operator theory, the Fitzpatrick function naturally leads to arefined Fenchel-Young inequality, making Fitzpatrick losses tighter thanFenchel-Young losses, while maintaining the same linkfunction for prediction. As an example, we introduce the Fitzpatrick logistic loss and theFitzpatrick sparsemax loss, counterparts of the logistic and the sparsemaxlosses. This yields twonew tighter losses associated with the soft argmax and the sparse argmax,two of the most ubiquitous output layers used in machine learning. We study indetails the properties of Fitzpatrick losses and in particular, we show thatthey can be seen as Fenchel-Young losses using a modified, target-dependentgenerating function. We demonstrate the effectiveness of Fitzpatrick losses forlabel proportion estimation.