  Adaptive importance sampling for stochastic optimization is a promising
approach that offers improved convergence through variance reduction. In this
work, we propose a new framework for variance reduction that enables the use of
mixtures over predefined sampling distributions, which can naturally encode
prior knowledge about the data. While these sampling distributions are fixed,
the mixture weights are adapted during the optimization process. We propose
VRM, a novel and efficient adaptive scheme that asymptotically recovers the
best mixture weights in hindsight and can also accommodate sampling
distributions over sets of points. We empirically demonstrate the versatility
of VRM in a range of applications.
