  Variational AutoEncoder (VAE) has been extended as a representative nonlinear
method for collaborative filtering. However, the bottleneck of VAE lies in the
softmax computation over all items, such that it takes linear costs in the
number of items to compute the loss and gradient for optimization. This hinders
the practical use due to millions of items in real-world scenarios. Importance
sampling is an effective approximation method, based on which the sampled
softmax has been derived. However, existing methods usually exploit the uniform
or popularity sampler as proposal distributions, leading to a large bias of
gradient estimation. To this end, we propose to decompose the
inner-product-based softmax probability based on the inverted multi-index,
leading to sublinear-time and highly accurate sampling. Based on the proposed
proposals, we develop a fast Variational AutoEncoder (FastVAE) for
collaborative filtering. FastVAE can outperform the state-of-the-art baselines
in terms of both sampling quality and efficiency according to the experiments
on three real-world datasets.
