Timezone: »

Robust Testing and Estimation under Manipulation Attacks
Jayadev Acharya · Ziteng Sun · Huanyu Zhang

Thu Jul 22 09:00 AM -- 11:00 AM (PDT) @

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.

Author Information

Jayadev Acharya (Cornell University)
Ziteng Sun (Cornell University)
Huanyu Zhang (Facebook)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors