Testing randomness online. / Vovk, Vladimir.

In: Statistical Science, Vol. 36, No. 4, 11.2021, p. 595-611.

Research output: Contribution to journalArticlepeer-review

E-pub ahead of print

Standard

Testing randomness online. / Vovk, Vladimir.

In: Statistical Science, Vol. 36, No. 4, 11.2021, p. 595-611.

Research output: Contribution to journalArticlepeer-review

Harvard

Vovk, V 2021, 'Testing randomness online', Statistical Science, vol. 36, no. 4, pp. 595-611. https://doi.org/10.1214/20-STS817

APA

Vovk, V. (2021). Testing randomness online. Statistical Science, 36(4), 595-611. https://doi.org/10.1214/20-STS817

Vancouver

Vovk V. Testing randomness online. Statistical Science. 2021 Nov;36(4):595-611. https://doi.org/10.1214/20-STS817

Author

Vovk, Vladimir. / Testing randomness online. In: Statistical Science. 2021 ; Vol. 36, No. 4. pp. 595-611.

BibTeX

@article{a6e703ae932a433c8ceedb6ae3131ef7,
title = "Testing randomness online",
abstract = "The hypothesis of randomness is fundamental in statistical machine learning and in many areas of nonparametric statistics; it says that the observations are assumed to be independent and coming from the same unknown probability distribution. This hypothesis is close, in certain respects, to the hypothesis of exchangeability, which postulates that the distribution of the observations is invariant with respect to their permutations. This paper reviews known methods of testing the two hypotheses concentrating on the online mode of testing, when the observations arrive sequentially. All known online methods for testing these hypotheses are based on conformal martingales, which are defined and studied in detail. An important variety of online testing is change detection, where the use of conformal martingales leads to conformal versions of the CUSUM and Shiryaev--Roberts procedures; these versions work in the nonparametric setting where the data is assumed IID according to a completely unknown distribution before the change. The paper emphasizes conceptual and practical aspects and states two kinds of results. Validity results limit the probability of a false alarm or, in the case of change detection, the frequency of false alarms for various procedures based on conformal martingales. Efficiency results establish connections between randomness, exchangeability, and conformal martingales.",
keywords = "Change detection, Conformal prediction, Exchangeability, Martingale, Online setting, Testing randomness",
author = "Vladimir Vovk",
year = "2021",
month = oct,
day = "11",
doi = "10.1214/20-STS817",
language = "English",
volume = "36",
pages = "595--611",
journal = "Statistical Science",
issn = "0883-4237",
publisher = "Institute of Mathematical Statistics",
number = "4",

}

RIS

TY - JOUR

T1 - Testing randomness online

AU - Vovk, Vladimir

PY - 2021/10/11

Y1 - 2021/10/11

N2 - The hypothesis of randomness is fundamental in statistical machine learning and in many areas of nonparametric statistics; it says that the observations are assumed to be independent and coming from the same unknown probability distribution. This hypothesis is close, in certain respects, to the hypothesis of exchangeability, which postulates that the distribution of the observations is invariant with respect to their permutations. This paper reviews known methods of testing the two hypotheses concentrating on the online mode of testing, when the observations arrive sequentially. All known online methods for testing these hypotheses are based on conformal martingales, which are defined and studied in detail. An important variety of online testing is change detection, where the use of conformal martingales leads to conformal versions of the CUSUM and Shiryaev--Roberts procedures; these versions work in the nonparametric setting where the data is assumed IID according to a completely unknown distribution before the change. The paper emphasizes conceptual and practical aspects and states two kinds of results. Validity results limit the probability of a false alarm or, in the case of change detection, the frequency of false alarms for various procedures based on conformal martingales. Efficiency results establish connections between randomness, exchangeability, and conformal martingales.

AB - The hypothesis of randomness is fundamental in statistical machine learning and in many areas of nonparametric statistics; it says that the observations are assumed to be independent and coming from the same unknown probability distribution. This hypothesis is close, in certain respects, to the hypothesis of exchangeability, which postulates that the distribution of the observations is invariant with respect to their permutations. This paper reviews known methods of testing the two hypotheses concentrating on the online mode of testing, when the observations arrive sequentially. All known online methods for testing these hypotheses are based on conformal martingales, which are defined and studied in detail. An important variety of online testing is change detection, where the use of conformal martingales leads to conformal versions of the CUSUM and Shiryaev--Roberts procedures; these versions work in the nonparametric setting where the data is assumed IID according to a completely unknown distribution before the change. The paper emphasizes conceptual and practical aspects and states two kinds of results. Validity results limit the probability of a false alarm or, in the case of change detection, the frequency of false alarms for various procedures based on conformal martingales. Efficiency results establish connections between randomness, exchangeability, and conformal martingales.

KW - Change detection

KW - Conformal prediction

KW - Exchangeability

KW - Martingale

KW - Online setting

KW - Testing randomness

U2 - 10.1214/20-STS817

DO - 10.1214/20-STS817

M3 - Article

VL - 36

SP - 595

EP - 611

JO - Statistical Science

JF - Statistical Science

SN - 0883-4237

IS - 4

ER -