License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.55
URN: urn:nbn:de:0030-drops-154880
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15488/
Go to the corresponding LIPIcs Volume Portal

Canonne, Clément L. ; Wimmer, Karl

Identity Testing Under Label Mismatch

pdf-format:
LIPIcs-ISAAC-2021-55.pdf (0.8 MB)

Abstract

Testing whether the observed data conforms to a purported model (probability distribution) is a basic and fundamental statistical task, and one that is by now well understood. However, the standard formulation, identity testing, fails to capture many settings of interest; in this work, we focus on one such natural setting, identity testing under promise of permutation. In this setting, the unknown distribution is assumed to be equal to the purported one, up to a relabeling (permutation) of the model: however, due to a systematic error in the reporting of the data, this relabeling may not be the identity. The goal is then to test identity under this assumption: equivalently, whether this systematic labeling error led to a data distribution statistically far from the reference model.

BibTeX - Entry

@InProceedings{canonne_et_al:LIPIcs.ISAAC.2021.55,
  author =	{Canonne, Cl\'{e}ment L. and Wimmer, Karl},
  title =	{{Identity Testing Under Label Mismatch}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{55:1--55:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15488},
  URN =		{urn:nbn:de:0030-drops-154880},
  doi =		{10.4230/LIPIcs.ISAAC.2021.55},
  annote =	{Keywords: distribution testing, property testing, permutations, lower bounds}
}

Keywords: distribution testing, property testing, permutations, lower bounds
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI