  We present an approximate inference method, based on a synergistic
combination of R\'enyi $\alpha$-divergence variational inference (RDVI) and
rejection sampling (RS). RDVI is based on minimization of R\'enyi
$\alpha$-divergence $D_\alpha(p||q)$ between the true distribution $p(x)$ and a
variational approximation $q(x)$; RS draws samples from a distribution $p(x) =
\tilde{p}(x)/Z_{p}$ using a proposal $q(x)$, s.t. $Mq(x) \geq \tilde{p}(x),
\forall x$. Our inference method is based on a crucial observation that
$D_\infty(p||q)$ equals $\log M(\theta)$ where $M(\theta)$ is the optimal value
of the RS constant for a given proposal $q_\theta(x)$. This enables us to
develop a \emph{two-stage} hybrid inference algorithm. Stage-1 performs RDVI to
learn $q_\theta$ by minimizing an estimator of $D_\alpha(p||q)$, and uses the
learned $q_\theta$ to find an (approximately) optimal $\tilde{M}(\theta)$.
Stage-2 performs RS using the constant $\tilde{M}(\theta)$ to improve the
approximate distribution $q_\theta$ and obtain a sample-based approximation. We
prove that this two-stage method allows us to learn considerably more accurate
approximations of the target distribution as compared to RDVI. We demonstrate
our method's efficacy via several experiments on synthetic and real datasets.
