Robust Testing and Estimation under Manipulation Attacks

Jayadev Acharya, Ziteng Sun, Huanyu Zhang
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:43-53, 2021.

Abstract

We study robust testing and estimation of discrete distributions in the strong contamination model. Our results cover both centralized setting and distributed setting with general local information constraints including communication and LDP constraints. Our technique relates the strength of manipulation attacks to the earth-mover distance using Hamming distance as the metric between messages (samples) from the users. In the centralized setting, we provide optimal error bounds for both learning and testing. Our lower bounds under local information constraints build on the recent lower bound methods in distributed inference. In the communication constrained setting, we develop novel algorithms based on random hashing and an L1-L1 isometry.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-acharya21a, title = {Robust Testing and Estimation under Manipulation Attacks}, author = {Acharya, Jayadev and Sun, Ziteng and Zhang, Huanyu}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {43--53}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/acharya21a/acharya21a.pdf}, url = {https://proceedings.mlr.press/v139/acharya21a.html}, abstract = {We study robust testing and estimation of discrete distributions in the strong contamination model. Our results cover both centralized setting and distributed setting with general local information constraints including communication and LDP constraints. Our technique relates the strength of manipulation attacks to the earth-mover distance using Hamming distance as the metric between messages (samples) from the users. In the centralized setting, we provide optimal error bounds for both learning and testing. Our lower bounds under local information constraints build on the recent lower bound methods in distributed inference. In the communication constrained setting, we develop novel algorithms based on random hashing and an L1-L1 isometry.} }
Endnote
%0 Conference Paper %T Robust Testing and Estimation under Manipulation Attacks %A Jayadev Acharya %A Ziteng Sun %A Huanyu Zhang %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-acharya21a %I PMLR %P 43--53 %U https://proceedings.mlr.press/v139/acharya21a.html %V 139 %X We study robust testing and estimation of discrete distributions in the strong contamination model. Our results cover both centralized setting and distributed setting with general local information constraints including communication and LDP constraints. Our technique relates the strength of manipulation attacks to the earth-mover distance using Hamming distance as the metric between messages (samples) from the users. In the centralized setting, we provide optimal error bounds for both learning and testing. Our lower bounds under local information constraints build on the recent lower bound methods in distributed inference. In the communication constrained setting, we develop novel algorithms based on random hashing and an L1-L1 isometry.
APA
Acharya, J., Sun, Z. & Zhang, H.. (2021). Robust Testing and Estimation under Manipulation Attacks. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:43-53 Available from https://proceedings.mlr.press/v139/acharya21a.html.

Related Material