  This paper studies the complexity of estimating Renyi divergences of discrete
distributions: $p$ observed from samples and the baseline distribution $q$
known \emph{a priori}. Extending the results of Acharya et al. (SODA'15) on
estimating Renyi entropy, we present improved estimation techniques together
with upper and lower bounds on the sample complexity.
  We show that, contrarily to estimating Renyi entropy where a sublinear (in
the alphabet size) number of samples suffices, the sample complexity is heavily
dependent on \emph{events occurring unlikely} in $q$, and is unbounded in
general (no matter what an estimation technique is used). For any divergence of
order bigger than $1$, we provide upper and lower bounds on the number of
samples dependent on probabilities of $p$ and $q$. We conclude that the
worst-case sample complexity is polynomial in the alphabet size if and only if
the probabilities of $q$ are non-negligible.
  This gives theoretical insights into heuristics used in applied papers to
handle numerical instability, which occurs for small probabilities of $q$. Our
result explains that small probabilities should be handled with care not only
because of numerical issues, but also because of a blow up in sample
complexity.
