On the accuracy of self-normalized log-linear models
  Calculation of the log-normalizer is a major computational obstacle in
applications of log-linear models with large output spaces. The problem of fast
normalizer computation has therefore attracted significant attention in the
theoretical and applied machine learning literature. In this paper, we analyze
a recently proposed technique known as "self-normalization", which introduces a
regularization term in training to penalize log normalizers for deviating from
zero. This makes it possible to use unnormalized model scores as approximate
probabilities. Empirical evidence suggests that self-normalization is extremely
effective, but a theoretical understanding of why it should work, and how
generally it can be applied, is largely lacking. We prove generalization bounds
on the estimated variance of normalizers and upper bounds on the loss in
accuracy due to self-normalization, describe classes of input distributions
that self-normalize easily, and construct explicit examples of high-variance
input distributions. Our theoretical results make predictions about the
difficulty of fitting self-normalized models to several classes of
distributions, and we conclude with empirical validation of these predictions.
