## Abstract

The problem of estimating the KL divergence between two unknown distributions is studied. The alphabet size k of the distributions can scale to infinity. The estimation is based on m and n independent samples respectively drawn from the two distributions. It is first shown that there does not exist any consistent estimator to guarantee asymptotic small worst-case quadratic risk over the set of all pairs of distributions. A restricted set that contains pairs of distributions with bounded ratio F(k) is further considered. An augmented plug-in estimator is proposed, and is shown to be consistent if and only if m = ω(k V log^{2}(F(k)) and n = ω(kF(k)). Furthermore, if F(k) ≥ log^{2}k and log^{2}(F(k)) = o(k), it is shown that any consistent estimator must satisfy the necessary conditions: m = ω( k/log k V log^{2}(F(k)) and n = ω( kF(k)/log k).

Original language | English (US) |
---|---|

Title of host publication | Proceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 1118-1122 |

Number of pages | 5 |

Volume | 2016-August |

ISBN (Electronic) | 9781509018062 |

DOIs | |

State | Published - Aug 10 2016 |

Event | 2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain Duration: Jul 10 2016 → Jul 15 2016 |

### Other

Other | 2016 IEEE International Symposium on Information Theory, ISIT 2016 |
---|---|

Country | Spain |

City | Barcelona |

Period | 7/10/16 → 7/15/16 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Information Systems
- Modeling and Simulation
- Applied Mathematics