We consider neural network training, in applications in which there are many possible classes, but at test-time, the task is to identify only whether the given example belongs to a specific class, which can be different in different applications of the classifier. For instance, this is the case in an image search engine. We consider the Single Logit Classification (SLC) task: training the network so that at test-time, it would be possible to accurately identify if the example belongs to a given class, based only on the output logit for this class. We propose a natural principle, the Principle of Logit Separation, as a guideline for choosing and designing losses suitable for the SLC. We show that the cross-entropy loss function is not aligned with the Principle of Logit Separation. In contrast, there are known loss functions, as well as novel batch loss functions that we propose, which are aligned with this principle. In total, we study seven loss functions. Our experiments show that indeed in almost all cases, losses that are aligned with Principle of Logit Separation obtain a 20%-35% relative performance improvement in the SLC task, compared to losses that are not aligned with it. We therefore conclude that the Principle of Logit Separation sheds light on an important property of the most common loss functions used by neural network classifiers. Tensorflow code for optimizing the new batch losses will be made publicly available upon publication; A URL will be provided in the publication version of this manuscript.
The paper addresses the problem of a mismatch between training classification loss and a loss at test time. This is motivated by use cases in which multiclass classification problems are learned during training, but where binary or reduced multi-class classifications is performed at test time. The question for me is the following: if at test time, we have to solve "some" binary classification task, possibly drawn at random from a set of binary problems (this is not made precise in the paper), then why not optimize the same classification error or a surrogate loss at training time? Instead, the authors start with a multiclass problem, which may introduce a computational burden. when the number of classes is large as one needs to compute a properly normalized softmax. The authors now seem to ask, what if one were to use a multi-classification loss at training time, but then decides at test time that a binary classification of one-vs-all is asked for. 
If one buys into the relevance of the setting, then of course, one is faced with the problem that the multiclass logits (aka raw scores) may not be calibrated to be used for binary classification by applying a fixed threshold. The authors call this sententiously "Principle of logit separation". Not too surprisingly, the standard multiclass losses do not have the desired property, however approaches that reduce multi-class to binary classification at training time do, namely unnormalized models with penalized log Z (self-normalization), the NCE approach, as well as (the natural in the proposed setting) binary classification loss. I find this almost a bit circular in the line of argumentation, but ok. It remains odd that while usually one has tried to reduce multiclass to binary, the authors go the opposite direction.
The main technical contribution of the paper is the batch-nornalization that makes sure that multiclass logits across mini-batches of data are better calibrated. One can almost think of that as an additional regularization. This seems interesting and does not create much overhead, if one applies mini-batched SGD optimization anyway. However, I feel this technique would need to be investigated with regard to general improvements in a multiclass setting and as such also benchmarked relative to other methods that could be applied.