  Inference in log-linear models scales linearly in the size of output space in
the worst-case. This is often a bottleneck in natural language processing and
computer vision tasks when the output space is feasibly enumerable but very
large. We propose a method to perform inference in log-linear models with
sublinear amortized cost. Our idea hinges on using Gumbel random variable
perturbations and a pre-computed Maximum Inner Product Search data structure to
access the most-likely elements in sublinear amortized time. Our method yields
provable runtime and accuracy guarantees. Further, we present empirical
experiments on ImageNet and Word Embeddings showing significant speedups for
sampling, inference, and learning in log-linear models.
