2019/05/20 by Jayadev Acharya, Clément L. Canonne, Acharya, Jayadev +3 · 4 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning and Algorithms #Statistics Theory (math.ST) #Stochastic Gradient Optimization Techniques #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1905.08302
openalex publication_date 2019/05/20 · openalex created_date 2022/07/29 · openalex updated_date 2026/07/28
A central server needs to perform statistical inference based on samples that\nare distributed over multiple users who can each send a message of limited\nlength to the center. We study problems of distribution learning and identity\ntesting in this distributed inference setting and examine the role of shared\nrandomness as a resource. We propose a general-purpose simulate-and-infer\nstrategy that uses only private-coin communication protocols and is\nsample-optimal for distribution learning. This general strategy turns out to be\nsample-optimal even for distribution testing among private-coin protocols.\nInterestingly, we propose a public-coin protocol that outperforms\nsimulate-and-infer for distribution testing and is, in fact, sample-optimal.\nUnderlying our public-coin protocol is a random hash that when applied to the\nsamples minimally contracts the chi-squared distance of their distribution to\nthe uniform distribution.\n