OPTIMAL HIGH-DIMENSIONAL AND NONPARAMETRIC DISTRIBUTED TESTING UNDER COMMUNICATION CONSTRAINTS

Botond Szabó; Lasse Vuursteen; Harry Van Zanten

doi:10.1214/23-AOS2269

OPTIMAL HIGH-DIMENSIONAL AND NONPARAMETRIC DISTRIBUTED TESTING UNDER COMMUNICATION CONSTRAINTS

Botond Szabó, Lasse Vuursteen, Harry Van Zanten

Mathematics

Research output: Contribution to Journal › Article › Academic › peer-review

16 Downloads (Pure)

Abstract

We derive minimax testing errors in a distributed framework where the data is split over multiple machines and their communication to a central machine is limited to b bits. We investigate both the d- and infinite-dimensional signal detection problem under Gaussian white noise. We also derive distributed testing algorithms reaching the theoretical lower bounds. Our results show that distributed testing is subject to fundamentally different phenomena that are not observed in distributed estimation. Among our findings we show that testing protocols that have access to shared randomness can perform strictly better in some regimes than those that do not. We also observe that consistent nonparametric distributed testing is always possible, even with as little as one bit of communication, and the corresponding test outperforms the best local test using only the information available at a single local machine. Furthermore, we also derive adaptive nonparametric distributed testing strategies and the corresponding theoretical lower bounds.

Original language	English
Pages (from-to)	909-934
Number of pages	26
Journal	Annals of Statistics
Volume	51
Issue number	3
DOIs	https://doi.org/10.1214/23-AOS2269
Publication status	Published - Jun 2023

Bibliographical note

Funding Information:
Funding. Cofunded by the European Union (ERC, BigBayesUQ, project number: 101041064). Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Publisher Copyright:
© Institute of Mathematical Statistics, 2023.

Funding

Funding. Cofunded by the European Union (ERC, BigBayesUQ, project number: 101041064). Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Funders	Funder number
European Commission
European Research Council	101041064
European Research Council

Keywords

Distributed methods
hypothesis testing
minimax optimal
nonparametric

Access to Document

10.1214/23-AOS2269

23-AOS2269_OPTIMAL HIGH-DIMENSIONAL AND NONPARAMETRIC DISTRIBUTED TESTING UNDER COMMUNICATION CONSTRAINTSFinal published version, 319 KBLicence: Article 25fa Dutch Copyright Act

Persistent URL (handle)

Persistent link

Cite this

@article{7cb48649655f463e8a36943bddd85088,

title = "OPTIMAL HIGH-DIMENSIONAL AND NONPARAMETRIC DISTRIBUTED TESTING UNDER COMMUNICATION CONSTRAINTS",

abstract = "We derive minimax testing errors in a distributed framework where the data is split over multiple machines and their communication to a central machine is limited to b bits. We investigate both the d- and infinite-dimensional signal detection problem under Gaussian white noise. We also derive distributed testing algorithms reaching the theoretical lower bounds. Our results show that distributed testing is subject to fundamentally different phenomena that are not observed in distributed estimation. Among our findings we show that testing protocols that have access to shared randomness can perform strictly better in some regimes than those that do not. We also observe that consistent nonparametric distributed testing is always possible, even with as little as one bit of communication, and the corresponding test outperforms the best local test using only the information available at a single local machine. Furthermore, we also derive adaptive nonparametric distributed testing strategies and the corresponding theoretical lower bounds.",

keywords = "Distributed methods, hypothesis testing, minimax optimal, nonparametric",

author = "Botond Szab{\'o} and Lasse Vuursteen and Zanten, {Harry Van}",

note = "Funding Information: Funding. Cofunded by the European Union (ERC, BigBayesUQ, project number: 101041064). Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Publisher Copyright: {\textcopyright} Institute of Mathematical Statistics, 2023.",

year = "2023",

month = jun,

doi = "10.1214/23-AOS2269",

language = "English",

volume = "51",

pages = "909--934",

journal = "Annals of Statistics",

issn = "0090-5364",

publisher = "Institute of Mathematical Statistics",

number = "3",

}

TY - JOUR

T1 - OPTIMAL HIGH-DIMENSIONAL AND NONPARAMETRIC DISTRIBUTED TESTING UNDER COMMUNICATION CONSTRAINTS

AU - Szabó, Botond

AU - Vuursteen, Lasse

AU - Zanten, Harry Van

N1 - Funding Information: Funding. Cofunded by the European Union (ERC, BigBayesUQ, project number: 101041064). Views and opinions expressed are, however, those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Publisher Copyright: © Institute of Mathematical Statistics, 2023.

PY - 2023/6

Y1 - 2023/6

N2 - We derive minimax testing errors in a distributed framework where the data is split over multiple machines and their communication to a central machine is limited to b bits. We investigate both the d- and infinite-dimensional signal detection problem under Gaussian white noise. We also derive distributed testing algorithms reaching the theoretical lower bounds. Our results show that distributed testing is subject to fundamentally different phenomena that are not observed in distributed estimation. Among our findings we show that testing protocols that have access to shared randomness can perform strictly better in some regimes than those that do not. We also observe that consistent nonparametric distributed testing is always possible, even with as little as one bit of communication, and the corresponding test outperforms the best local test using only the information available at a single local machine. Furthermore, we also derive adaptive nonparametric distributed testing strategies and the corresponding theoretical lower bounds.

AB - We derive minimax testing errors in a distributed framework where the data is split over multiple machines and their communication to a central machine is limited to b bits. We investigate both the d- and infinite-dimensional signal detection problem under Gaussian white noise. We also derive distributed testing algorithms reaching the theoretical lower bounds. Our results show that distributed testing is subject to fundamentally different phenomena that are not observed in distributed estimation. Among our findings we show that testing protocols that have access to shared randomness can perform strictly better in some regimes than those that do not. We also observe that consistent nonparametric distributed testing is always possible, even with as little as one bit of communication, and the corresponding test outperforms the best local test using only the information available at a single local machine. Furthermore, we also derive adaptive nonparametric distributed testing strategies and the corresponding theoretical lower bounds.

KW - Distributed methods

KW - hypothesis testing

KW - minimax optimal

KW - nonparametric

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

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

U2 - 10.1214/23-AOS2269

DO - 10.1214/23-AOS2269

M3 - Article

AN - SCOPUS:85172090461

SN - 0090-5364

VL - 51

SP - 909

EP - 934

JO - Annals of Statistics

JF - Annals of Statistics

IS - 3

ER -

OPTIMAL HIGH-DIMENSIONAL AND NONPARAMETRIC DISTRIBUTED TESTING UNDER COMMUNICATION CONSTRAINTS

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this