# Inference under Information Constraints I: Lower Bounds from Chi-Square Contraction

arXiv: https://arxiv.org/abs/1812.11476 · HTML: https://mlsanity.com/paper/1812.11476/

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Dec 2018.

## Built on by (most cited first, 30 of 31)

- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergence](https://mlsanity.com/paper/2102.01258/) (2021)
- [Communication-Efficient Federated Learning with Binary Neural Networks](https://mlsanity.com/paper/2110.02226/) (2021)
- [BAFFLE: A Baseline of Backpropagation-Free Federated Learning](https://mlsanity.com/paper/2301.12195/) (2023)
- [Communication-constrained hypothesis testing: Optimality, robustness, and reverse data processing inequalities](https://mlsanity.com/paper/2206.02765/) (2022)
- [Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints](https://mlsanity.com/paper/2301.03566/) (2023)
- [Contraction of Locally Differentially Private Mechanisms](https://mlsanity.com/paper/2210.13386/) (2022)
- [Differentially Private Sampling from Distributions](https://mlsanity.com/paper/2211.08193/) (2022)
- [The Sample Complexity of Simple Binary Hypothesis Testing](https://mlsanity.com/paper/2403.16981/) (2024)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests](https://mlsanity.com/paper/2406.06749/) (2024)
- [Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes](https://mlsanity.com/paper/2604.07796/) (2026)
- [Robust Testing and Estimation under Manipulation Attacks](https://mlsanity.com/paper/2104.10740/) (2021)
- [Independence Testing for Bounded Degree Bayesian Network](https://mlsanity.com/paper/2204.08690/) (2022)
- [Continual Mean Estimation Under User-Level Privacy](https://mlsanity.com/paper/2212.09980/) (2022)
- [An invitation to the sample complexity of quantum hypothesis testing](https://mlsanity.com/paper/2403.17868/) (2024)
- [Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2509.21940/) (2025)
- [Breaking The Dimension Dependence in Sparse Distribution Estimation under Communication Constraints](https://mlsanity.com/paper/2106.08597/) (2021)
- [Algorithms for bounding contribution for histogram estimation under user-level privacy](https://mlsanity.com/paper/2206.03008/) (2022)
- [Over-the-Air Statistical Estimation](https://mlsanity.com/paper/2103.04014/) (2021)
- [Fundamental limits of over-the-air optimization: Are analog schemes optimal?](https://mlsanity.com/paper/2109.05222/) (2021)
- [Optimal high-dimensional and nonparametric distributed testing under communication constraints](https://mlsanity.com/paper/2202.00968/) (2022)
- [Distributed Nonparametric Estimation under Communication Constraints](https://mlsanity.com/paper/2204.10373/) (2022)
- [Private and Communication-Efficient Algorithms for Entropy Estimation](https://mlsanity.com/paper/2305.07751/) (2023)
- [Statistical Inference with Limited Memory: A Survey](https://mlsanity.com/paper/2312.15225/) (2023)
- [Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions](https://mlsanity.com/paper/2504.14696/) (2025)
- [Uniformity Testing in the Shuffle Model: Simpler, Better, Faster](https://mlsanity.com/paper/2108.08987/) (2021)
- [Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph](https://mlsanity.com/paper/2509.16180/) (2025)
- [Matching Rates and Optimal Allocation for Federated Probe-Logit Distillation under Heterogeneous Bandwidth Budgets](https://mlsanity.com/paper/2605.29642/) (2026)

## Abstract (arXiv)

Multiple players are each given one independent sample, about which they can only provide limited information to a central referee. Each player is allowed to describe its observed sample to the referee using a channel from a family of channels W, which can be instantiated to capture both the communication- and privacy-constrained settings and beyond. The referee uses the messages from players to solve an inference problem for the unknown distribution that generated the samples. We derive lower bounds for sample complexity of learning and testing discrete distributions in this information-constrained setting. Underlying our bounds is a characterization of the contraction in chi-square distances between the observed distributions of the samples when information constraints are placed. This contraction is captured in a local neighborhood in terms of chi-square and decoupled chi-square fluctuations of a given channel, two quantities we introduce. The former captures the average distance between distributions of channel output for two product distributions on the input, and the latter for a product distribution and a mixture of product distribution on the input. Our bounds are tight for both public- and private-coin protocols. Interestingly, the sample complexity of testing is order-wise higher when restricted to private-coin protocols.