Robust Kullback-Leibler Divergence and Universal Hypothesis Testing for Continuous Distributions

Pengfei Yang, Biao Chen

Research output: Contribution to journalArticle

Abstract

Universal hypothesis testing (UHT) refers to the problem of deciding whether samples come from a nominal distribution or an unknown distribution that is different from the nominal distribution. Hoeffding’s test, whose test statistic is equivalent to the empirical Kullback-Leibler divergence (KL divergence), is known to be asymptotically optimal for distributions defined on finite alphabets. With continuous observations, however, the discontinuity of the KL divergence in the distribution functions results in significant complications for UHT. This paper introduces a robust version of the classical KL divergence, defined as the KL divergence from a distribution to the Lévy ball of a known distribution. This robust KL divergence is shown to be continuous in the underlying distribution function with respect to the weak convergence. The continuity property enables the development of an asymptotically optimal test for the university hypothesis testing problem with continuous observations. The optimality is in the same sense as that of the Hoeffding’s test and stronger than that of Zeitouni and Gutman. Perhaps more importantly, the developed test statistic can be computed through convex programs, making it much more meaningful in practice. Numerical experiments are also conducted to evaluate its performance as compared with some kernel based goodness of fit test that has been proposed recently.

Original languageEnglish (US)
JournalIEEE Transactions on Information Theory
DOIs
StateAccepted/In press - Jan 1 2018

Fingerprint

hypothesis testing
divergence
Distribution functions
Testing
Statistics
statistics
Experiments
continuity
university
experiment

Keywords

  • Convergence
  • Detectors
  • Distribution functions
  • Kernel
  • Kullback-Leibler divergence
  • Lévy metric
  • Measurement
  • Probability distribution
  • Testing
  • universal hypothesis testing

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

@article{365fb87da5114403be567a0ffe1ccaa8,
title = "Robust Kullback-Leibler Divergence and Universal Hypothesis Testing for Continuous Distributions",
abstract = "Universal hypothesis testing (UHT) refers to the problem of deciding whether samples come from a nominal distribution or an unknown distribution that is different from the nominal distribution. Hoeffding’s test, whose test statistic is equivalent to the empirical Kullback-Leibler divergence (KL divergence), is known to be asymptotically optimal for distributions defined on finite alphabets. With continuous observations, however, the discontinuity of the KL divergence in the distribution functions results in significant complications for UHT. This paper introduces a robust version of the classical KL divergence, defined as the KL divergence from a distribution to the L{\'e}vy ball of a known distribution. This robust KL divergence is shown to be continuous in the underlying distribution function with respect to the weak convergence. The continuity property enables the development of an asymptotically optimal test for the university hypothesis testing problem with continuous observations. The optimality is in the same sense as that of the Hoeffding’s test and stronger than that of Zeitouni and Gutman. Perhaps more importantly, the developed test statistic can be computed through convex programs, making it much more meaningful in practice. Numerical experiments are also conducted to evaluate its performance as compared with some kernel based goodness of fit test that has been proposed recently.",
keywords = "Convergence, Detectors, Distribution functions, Kernel, Kullback-Leibler divergence, Lévy metric, Measurement, Probability distribution, Testing, universal hypothesis testing",
author = "Pengfei Yang and Biao Chen",
year = "2018",
month = "1",
day = "1",
doi = "10.1109/TIT.2018.2879057",
language = "English (US)",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Robust Kullback-Leibler Divergence and Universal Hypothesis Testing for Continuous Distributions

AU - Yang, Pengfei

AU - Chen, Biao

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Universal hypothesis testing (UHT) refers to the problem of deciding whether samples come from a nominal distribution or an unknown distribution that is different from the nominal distribution. Hoeffding’s test, whose test statistic is equivalent to the empirical Kullback-Leibler divergence (KL divergence), is known to be asymptotically optimal for distributions defined on finite alphabets. With continuous observations, however, the discontinuity of the KL divergence in the distribution functions results in significant complications for UHT. This paper introduces a robust version of the classical KL divergence, defined as the KL divergence from a distribution to the Lévy ball of a known distribution. This robust KL divergence is shown to be continuous in the underlying distribution function with respect to the weak convergence. The continuity property enables the development of an asymptotically optimal test for the university hypothesis testing problem with continuous observations. The optimality is in the same sense as that of the Hoeffding’s test and stronger than that of Zeitouni and Gutman. Perhaps more importantly, the developed test statistic can be computed through convex programs, making it much more meaningful in practice. Numerical experiments are also conducted to evaluate its performance as compared with some kernel based goodness of fit test that has been proposed recently.

AB - Universal hypothesis testing (UHT) refers to the problem of deciding whether samples come from a nominal distribution or an unknown distribution that is different from the nominal distribution. Hoeffding’s test, whose test statistic is equivalent to the empirical Kullback-Leibler divergence (KL divergence), is known to be asymptotically optimal for distributions defined on finite alphabets. With continuous observations, however, the discontinuity of the KL divergence in the distribution functions results in significant complications for UHT. This paper introduces a robust version of the classical KL divergence, defined as the KL divergence from a distribution to the Lévy ball of a known distribution. This robust KL divergence is shown to be continuous in the underlying distribution function with respect to the weak convergence. The continuity property enables the development of an asymptotically optimal test for the university hypothesis testing problem with continuous observations. The optimality is in the same sense as that of the Hoeffding’s test and stronger than that of Zeitouni and Gutman. Perhaps more importantly, the developed test statistic can be computed through convex programs, making it much more meaningful in practice. Numerical experiments are also conducted to evaluate its performance as compared with some kernel based goodness of fit test that has been proposed recently.

KW - Convergence

KW - Detectors

KW - Distribution functions

KW - Kernel

KW - Kullback-Leibler divergence

KW - Lévy metric

KW - Measurement

KW - Probability distribution

KW - Testing

KW - universal hypothesis testing

UR - http://www.scopus.com/inward/record.url?scp=85056312568&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85056312568&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2879057

DO - 10.1109/TIT.2018.2879057

M3 - Article

AN - SCOPUS:85056312568

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

ER -