GloVe: Global Vectors for Word Representation

3.2 Complexity of the model

1. What is the computational complexity of training GloVe?
   Proportional to the number of nonzero entries of \(X\), at most \(O(|V|^2)\). Assuming co-occurrence counts follow a power law in pair frequency rank with \(\alpha = 1.25\) (as observed), the number of nonzeros is \(O(|C|^{0.8})\), better than window-based methods, which scale as \(O(|C|)\) in corpus size.
   • Pennington et al., 2014, GloVe (Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)), §3.2, pp. 1536–1537