Optimal Private and Communication Constraint Distributed Goodness-of-Fit Testing for Discrete Distributions in the Large Sample Regime

Federated learning faces challenges due to bandwidth limitations and privacy concerns when processing decentralized datasets. Existing research primarily focuses on continuous data distributions, leaving a gap in understanding how to perform hypothesis testing on discrete data, which is very common in real-world applications. This is particularly important in fields like population genetics, computer science, and natural language processing, where large discrete datasets are frequently encountered.

This research addresses the above issues by developing minimax upper and lower bounds for goodness-of-fit testing of discrete data in distributed settings. The analysis considers both bandwidth constraints and differential privacy constraints. The authors cleverly leverage Le Cam’s theory of statistical equivalence to connect the problem for discrete distributions to the well-understood counterpart for Gaussian data, allowing them to derive matching bounds. This novel approach overcomes the difficulties of directly analyzing the complex multinomial model. The paper’s findings provide valuable insights for designing communication-efficient and privacy-preserving statistical methods.