TL;DR: We prove that linear word analogies hold over a set of ordered pairs (e.g., {(Paris, France), (Ottawa, Canada), ...}) in an SGNS or GloVe embedding space with no reconstruction error when PMI(x,y) + log p(x,y) is the same for every word pair (x,y). We call this term the csPMI (co-occurrence shifted PMI). This has a number of interesting implications:
1. It implies that Pennington et al. (authors of GloVe) had the right intuition about why these analogies hold.
2. Adding two word vectors together to compose them makes sense, because you're implicitly downweighting the more frequent word -- like TF-IDF or SIF would do explicitly.
3. Using Euclidean distance to measure word dissimilarity make sense because the Euclidean distance is a linear function of the negative csPMI.