2018/05/31 by Lei Yu, Vincent Y. F. Tan, Yu, Lei +1
Computer Science · Engineering · Mathematics · Physics and Astronomy · #Adversarial Robustness in Machine Learning #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR) #Statistical Mechanics and Entropy #Wireless Communication Security Techniques #cs.CR #cs.IT #math.IT #math.PR
paper · pdf · doi:10.48550/arxiv.1805.12451
36 pages, double column. To appear in IEEE Transactions on Information Theory
openalex publication_date 2018/05/31 · openalex created_date 2018/06/13 · arxiv created 2018/12/21 · arxiv updated 2018/12/24 · openalex updated_date 2026/07/28
The random variable simulation problem consists in using a k-dimensional i.i.d. random vector Xk with distribution PXk to simulate an n-dimensional i.i.d. random vector Yn so that its distribution is approximately QYn. In contrast to previous works, in this paper we consider the standard Rényi divergence and two variants of all orders to measure the level of approximation. These two variants are the max-Rényi divergence Dαmax(P,Q) and the sum-Rényi divergence Dα+(P,Q). When α=∞, these two measures are strong because for any ε>0, D∞max(P,Q)≤ε or D∞+(P,Q)≤ε implies e-ε≤(P(x))/(Q(x))≤ eε for all x. Under these Rényi divergence measures, we characterize the asymptotics of normalized divergences as well as the Rényi conversion rates. The latter is defined as the supremum of (n)/(k) such that the Rényi divergences vanish asymptotically. In addition, when the Rényi parameter is in the interval (0,1), the Rényi conversion rates equal the ratio of the Shannon entropies \fracH(PX)H(QY), which is consistent with traditional results in which the total variation measure was adopted. When the Rényi parameter is in the interval (1,∞], the Rényi conversion rates are, in general, smaller than \fracH(PX)H(QY). When specialized to the case in which either PX or QY is uniform, the simulation problem reduces to the source resolvability and intrinsic randomness problems. The preceding results are used to characterize the asymptotics of Rényi divergences and the Rényi conversion rates for these two cases.