Lower bounds for risk in private interactive statistical decision making
Lower bounds for Bayesian CVaR in interactive problems with local differential privacy
Information Theory
Summary
This paper studies how to understand the minimum possible risk when making many interactive decisions with private data. The authors develop a new theoretical method using information theory that provides lower bounds on the worst expected loss under uncertainty. They apply this method to problems like estimating averages and bandit learning when individual data is protected by local differential privacy rules. This work helps explain how privacy constraints limit the best achievable accuracy in these interactive settings.
What this means in practice
- •For privacy engineers: Determine the theoretical accuracy limits when designing locally private data collection and learning systems, especially for mean estimation tasks.
- •For bandit algorithm designers: Establish baseline performance guarantees for multi-armed bandit algorithms under local differential privacy constraints.
A theory result. No direct application yet.
Authors
Raghav Bongole, Amirreza Zamani, Tobias J. Oechtering, Mikael Skoglund
Abstract
We develop an information-theoretic method for lower bounding the prior-predictive conditional value-at-risk (CVaR) of loss in interactive statistical decision making (ISDM). A generalized Fano inequality replaces a single error event by a randomized binary statistic constructed from a bounded transform of the loss, reducing the problem to a Bernoulli $f$-divergence inequality. A bounded hinge transform yields a direct lower bound on Bayesian CVaR under a prior fixed in advance. We derive reverse-KL specializations and obtain explicit bounds for Gaussian mean estimation and Gaussian stochastic bandits. We then impose local differential privacy (LDP) at the observation stage of the same ISDM model. LDP contraction inequalities combined with the adaptive KL chain rule give explicit Bayesian CVaR lower bounds for Gaussian mean estimation with heterogeneous privacy parameters and Gaussian $K$-armed bandits.