| Paper ID | D1-S5-T3.3 |
| Paper Title |
Interactive Inference under Information Constraints |
| Authors |
Jayadev Acharya, Cornell University, United States; Clément L. Canonne, University of Sydney, Australia; Yuhan Liu, Ziteng Sun, Cornell University, United States; Himanshu Tyagi, Indian Institute of Science, India |
| Session |
D1-S5-T3: Distributed Learning |
| Chaired Session: |
Monday, 12 July, 23:20 - 23:40 |
| Engagement Session: |
Monday, 12 July, 23:40 - 00:00 |
| Abstract |
We consider the problem of distributed estimation and testing of discrete distributions under local information constraints that include communication and privacy as special cases. Our main result is a unified method that establishes tight bounds for interactive protocols under both the constraints and both the problems. Our main technical contribution is an average information bound that connects learning and testing and handles correlations due to interactivity. While we establish that for learning and testing under both the constraints above, interactivity does not help, we also illustrate a natural family of ``leaky query'' local constraints under which interactive protocols strictly outperform the noninteractive ones for identity testing.
|
