Papers for

bandit algorithm designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Lower bounds for risk in private interactive statistical decision making

Lower bounds for Bayesian CVaR in interactive problems with local differential privacy

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.

Tue 20 OctInformation Theory

The gist

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.

Open → 2610.28153v1