betaFeedback

WorksComputer Science

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 ff-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 KK-armed bandits.

Introduction

Interactive statistical decision making (ISDM) provides a common framework for problems in which a learner’s actions influence the information it subsequently observes. A model specifies the environment, an algorithm selects actions using the available history, and their interaction induces a distribution over the resulting transcript. Passive estimation is recovered when the

Preliminary versions of parts of this work appeared in [1], [2]. learner has no control over the observation process, whereas multi-armed bandits, contextual bandits, and reinforcement learning are prominent adaptive examples [3], [4], [5].

Information-theoretic lower bounds characterize the performance that no admissible procedure can surpass. Classical methods based on Le Cam’s, Assouad’s, and Fano’s inequalities relate statistical difficulty to the distinguishability of candidate models. In interactive problems, this distinguishability depends on the algorithm, because its actions determine which observations are collected. Interactive extensions of classical lower-bound methods account for this dependence [5], while the Decision–Estimation Coefficient provides a complementary characterization of the complexity of broad classes of interactive decision problems [3], [4].

Most information-theoretic lower bounds focus on expected loss or on the probability that a loss exceeds a prescribed threshold. Interactive Fano arguments, for example, typically reduce the loss to a binary success or failure event and then control the corresponding Bernoulli divergence [5], [6]. This reduction is well suited to expected-risk and quantile criteria, but it does not directly describe more general bounded functionals of the loss.

The distinction is particularly relevant for conditional value-at-risk (CVaR), which measures the severity of losses in the upper tail rather than only their expectation or a single quantile. Information-theoretic lower bounds for Bayesian expected risk are well developed [7], and recent work has established high-probability and minimax-quantile lower bounds in both passive and interactive settings [8], [5], [6], [9]. These results concern risk criteria that differ from the prior-predictive Bayesian CVaR studied here. In our formulation, a model is first drawn from a prescribed prior, the transcript is then generated by its interaction with the algorithm, and CVaR is evaluated under the resulting joint prior-predictive law. The prior is fixed before optimizing over admissible algorithms and therefore forms part of the decision problem.

This paper develops a general route to lower bounds for this criterion. The key step replaces the usual indicator of a threshold event by a randomized binary statistic representing an arbitrary bounded transform of the loss. Data processing then relates the expected transformed loss under the model-dependent experiment to its counterpart under a reference experiment through a Bernoulli ff-divergence constraint. Indicator functions recover the usual threshold-event reduction, while other transforms permit different loss functionals to be treated within the same argument.

For bounded losses, we apply this reduction to a hinge transform and combine it with the Rockafellar–Uryasev representation of CVaR [10]. The resulting converse reduces a problemspecific CVaR lower bound to two tasks: controlling the excess loss under a suitable reference distribution and bounding the average divergence between the model-dependent and reference transcript laws. A reverse-KL specialization produces an exponential Bernoulli inverse. Balancing this inverse against the CVaR tail level leads to the logarithmic dependence on the reciprocal tail probability that appears in our explicit lower bounds.

We first apply the method without privacy constraints. For Gaussian mean estimation, we use a symmetric two-point prior and a clipped squared-error proxy to lower bound the prior-predictive CVaR of squared estimation error. For Gaussian KK-armed stochastic bandits, we use a uniform prior over environments with different optimal arms and lower bound the CVaR of cumulative pseudo-regret. In each case, the fixed-prior inequality is established for every value of the model separation. A separation is selected afterward to identify a hard prior from the corresponding family. Thus, for each selected prior, the optimization over algorithms is a fixed-prior Bayesian decision problem.

We then incorporate local differential privacy (LDP). Statistical estimation under LDP has an extensive information-theoretic literature [11, 12, 13], and interactive decision making under LDP has also been studied through private variants of the Decision–Estimation Coefficient and related high-probability criteria [14]. Heterogeneous privacy levels have recently been considered for high-probability estimation [15]. Our objective is different: we seek fixed-prior, prior-predictive CVaR lower bounds when the learner acts using locally privatized observations.

The general CVaR argument remains unchanged in the private setting and is applied directly to the released transcript. Privacy affects the analysis through the available divergence budget. We conditionally apply an LDP contraction inequality at each round and combine the result with the adaptive KL chain rule. This yields transcript-level divergence bounds for sequentially private procedures, which can then be inserted into the same Bayesian CVaR converse used in the nonprivate setting.

We instantiate this argument for Gaussian mean estimation with heterogeneous privacy parameters and for Gaussian KK-armed bandits under sequential LDP. We also provide a bounded mean-estimation example under heterogeneous LDP to compare the parameter dependence of our Bayesian CVaR lower bound with known high-probability minimax results for the same bounded observation model [15]. The comparison concerns the dependence on the tail and privacy parameters and the Bayesian CVaR and minimax-quantile criteria remain distinct.

Contributions

The main contributions are as follows.

  1. A bounded-transform extension of interactive Fano arguments. We extend the interactive Fano method of [5] from threshold indicators to arbitrary bounded measurable transforms of the loss. A randomized binary representation and data processing yield a two-sided Bernoulli ff-divergence constraint on the expected transform. This allows a broader class of loss functionals to be controlled directly, without first reducing the loss to a single threshold event. The threshold-event reduction of [5] is recovered as a special case, while other choices, such as the hinge transform, provide direct access to tail-sensitive criteria including CVaR.

  1. A fixed-prior Bayesian CVaR converse. For bounded losses, a hinge transform and the Rockafellar–Uryasev representation convert the general ff-divergence constraint into a lower bound on prior-predictive Bayesian CVaR. We develop an explicit reverse-KL specialization that retains the dependence on the CVaR level.

  1. Explicit Gaussian estimation and bandit lower bounds. We apply the converse to Gaussian mean estimation under squared error and to Gaussian KK-armed bandits under cumulative pseudo-regret. The results first hold for every fixed prior in a parameterized hard family. Selecting a separation afterward gives hard-prior lower bounds with logarithmic dependence on the CVaR tail probability.

  1. Extension to locally private observations. We formulate the released-transcript version of ISDM under sequential LDP and combine one-round LDP contraction with the adaptive KL chain rule. This gives Bayesian CVaR lower bounds for Gaussian mean estimation with heterogeneous privacy levels, Gaussian stochastic bandits under LDP, and a bounded mean-estimation model used for comparison with existing heterogeneous-LDP results.

Section III presents the bounded-transform divergence inequality, and § 4 derives its Bayesian CVaR consequence. § 6 treats the Gaussian applications. Sections VII and VIII develop the LDP formulation and its applications. Related work and limitations are discussed in § 9 and § 10, respectively, and detailed proofs are deferred to the appendices.

Preliminary versions of parts of this work appeared in [1], [2]. The present article combines the bounded-transform and Bayesian CVaR framework with reverse-KL Gaussian applications and an extension to sequential local differential privacy.

Interactive Statistical Decision Making and Bayesian Risk

This section introduces the statistical framework and the Bayesian risk criterion used throughout the paper. We first fix the notation, then describe the interactive experiment and its induced transcript distribution, and finally define the Bayesian CVaR criterion under a prior fixed in advance.

Notation

We use capital letters for random variables and lower-case letters for their realizations. For probability measures PP and QQ on a common measurable space, total variation is denoted by dTV(P,Q)d_{\mathrm{TV}}(P,Q) and Kullback–Leibler divergence by DKL(P∥Q)D_{\mathrm{KL}}(P\mathbin{\|}Q). For probability measures PP and QQ on a common measurable space and a convex function f:R+→R∪{+∞}f:\mathbb{R}_{+}\to\mathbb{R}\cup\{+\infty\} satisfying f(1)=0f(1)=0, the ff-divergence is

Df(P∥Q):=∫qf(pq) dλ,(1)D_f(P\mathbin{\|}Q):=\int q f\left(\frac{p}{q}\right)\,\mathrm{d}\lambda, \tag*{(1)}

where λ\lambda is any measure dominating PP and QQ, with p=dP/dλp=\mathrm{d}P/\mathrm{d}\lambda and q=dQ/dλq=\mathrm{d}Q/\mathrm{d}\lambda [16]. This definition is independent of the choice of λ\lambda.

We write

[x]+:=max⁡{x,0}.(2)[x]_{+}:=\max\{x,0\}. \tag*{(2)}

The Bernoulli distribution with mean aa is denoted by Bern⁡(a)\operatorname{Bern}(a).

For a nonnegative random variable LL and α∈(0,1)\alpha\in(0,1), the CVaR is written as

CVaR⁡α(L):=inf⁡s∈R{s+11−αE[(L−s)+]}.(3)\operatorname{CVaR}_{\alpha}(L):=\inf_{s\in\mathbb{R}}\left\{s+\frac{1}{1-\alpha}\mathbb{E}[(L-s)_{+}]\right\}. \tag*{(3)}

Interactive statistical decision making

Let M\mathcal{M} be a model class, A\mathcal{A} an action space, and Y\mathcal{Y} an observation space. An interactive procedure ALG⁡∈D\operatorname{ALG}\in\mathcal{D} operates for TT rounds. Given the history

Ht−1=(A1,Y1,…,At−1,Yt−1),(4)H_{t-1}=(A_{1},Y_{1},\ldots,A_{t-1},Y_{t-1}), \tag*{(4)}

it selects

At∼πt(⋅∣Ht−1).(5)A_{t}\sim\pi_{t}(\mathord{\cdot}\mid H_{t-1}). \tag*{(5)}

Under a model M∈MM\in\mathcal{M}, the environment then generates

Yt∼PtM(⋅∣At,Ht−1).(6)Y_{t}\sim P_{t}^{M}(\mathord{\cdot}\mid A_{t},H_{t-1}). \tag*{(6)}

The transcript is

HT=(A1,Y1,…,AT,YT),(7)H_T = (A_1, Y_1, \ldots, A_T, Y_T), \tag*{(7)}

and its induced distribution is denoted by

PM,ALG.(8)\mathbb{P}^{M,\mathrm{ALG}}. \tag*{(8)}

The defining feature of ISDM is that the transcript distribution depends on the procedure. In bandit problems, the action determines which observation distribution is sampled. The same formulation subsumes both passive and adaptive statistical problems.

Fixed-prior Bayesian decision problems

Fix a prior

μ∈P(M).(9)\mu\in\mathcal{P}(\mathcal{M}). \tag*{(9)}

For a fixed procedure ALG, the Bayesian experiment is

M∼μ,HT∣M∼PM,ALG.(10)M \sim\mu, \qquad H_T \mid M \sim\mathbb{P}^{M,\mathrm{ALG}}. \tag*{(10)}

Equivalently, the joint law of the model and transcript is

Pμ,ALG(dM,dh):=μ(dM)PM,ALG(dh).(11)\mathbb{P}_{\mu,\mathrm{ALG}}(dM,dh) := \mu(dM)\mathbb{P}^{M,\mathrm{ALG}}(dh). \tag*{(11)}

Let

L:M×HT→[0,∞)(12)L : \mathcal{M} \times\mathcal{H}_T \to[0,\infty) \tag*{(12)}

be a measurable loss. The fixed-prior Bayesian CVaR value is

CVaR⁡αμ,ALG(L):=inf⁡s∈R{s+11−αEPμ,ALG[(L−s)+]}.(13)\operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L) := \inf_{s \in\mathbb{R}} \left\{s + \frac{1}{1-\alpha}\mathbb{E}_{\mathbb{P}_{\mu,\mathrm{ALG}}}[(L-s)_{+}]\right\}. \tag*{(13)}

For the fixed prior μ\mu, the optimal Bayesian CVaR is

Eα(μ):=inf⁡ALG∈DCVaR⁡αμ,ALG(L),(14)\mathcal{E}_{\alpha}(\mu) := \inf_{\mathrm{ALG}\in\mathcal{D}} \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L), \tag*{(14)}

where the expectation in (3) is taken with respect to (11).

Remark II.1 (Fixed prior). In (14), μ\mu is specified before the procedure is optimized. A lower bound for a particular prior is therefore a lower bound for a particular Bayesian decision problem. If a parameterized family of priors is optimized afterward, the resulting statement is that at least one prior in that family is hard.

Generalized Interactive Fano Inequality

This section develops the main information-theoretic inequality of the paper. We associate a bounded function of the loss with a binary random variable and use data processing for ff-divergences to compare its law under the model-dependent experiment with its law under a reference experiment. The resulting inequality gives both lower and upper bounds on the expected transformed loss through Bernoulli ff-divergence inverses.

Fix a prior μ\mu, a procedure ALG, and a probability distribution QQ on the transcript space. Let ϕ:R+→[0,1]\phi:\mathbb{R}_{+}\to[0,1] be measurable and define

aϕ:=EM∼μEHT∼PM,ALG[ϕ(L(M,HT))],(15)a_{\phi}:=\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim P^{M,\mathrm{ALG}}}\left[\phi(L(M,H_T))\right], \tag*{(15)}
bϕ,Q:=EM∼μEHT∼Q[ϕ(L(M,HT))].(16)b_{\phi,Q}:=\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim Q}\left[\phi(L(M,H_T))\right]. \tag*{(16)}

For an ff-divergence, define the average divergence

Bf(ALG,Q):=EM∼μDf(PM,ALG∥Q).(17)B_f(\mathrm{ALG},Q):=\mathbb{E}_{M\sim\mu}D_f\left(P^{M,\mathrm{ALG}}\middle\|Q\right). \tag*{(17)}

For b∈[0,1]b\in[0,1] and B≥0B\geq0, define the lower and upper Bernoulli ff-divergence inverses by

af−(B;b):=inf⁡{a∈[0,1]:Df(Bern⁡(a)∥Bern⁡(b))≤B},(18)a_f^{-}(B;b):=\inf\left\{a\in[0,1]:D_f(\operatorname{Bern}(a)\middle\|\operatorname{Bern}(b))\leq B\right\}, \tag*{(18)}
af+(B;b):=sup⁡{a∈[0,1]:Df(Bern⁡(a)∥Bern⁡(b))≤B}.(19)a_f^{+}(B;b):=\sup\left\{a\in[0,1]:D_f(\operatorname{Bern}(a)\middle\|\operatorname{Bern}(b))\leq B\right\}. \tag*{(19)}

The following theorem is the main result of this section. It shows that the expected transformed loss under the model-dependent experiment and under the reference experiment must satisfy a Bernoulli ff-divergence constraint. Inverting this constraint gives a two-sided bound on the expected transformed loss.

Theorem III.1 (Generalized interactive Fano inequality). Fix a prior μ\mu, a procedure ALG, a reference distribution QQ, a measurable function ϕ:R+→[0,1]\phi:\mathbb{R}_{+}\to[0,1], and an ff-divergence. Let

aϕ:=EM∼μEHT∼PM,ALG[ϕ(L(M,HT))],(20)a_{\phi}:=\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim P^{M,\mathrm{ALG}}}\left[\phi(L(M,H_T))\right], \tag*{(20)}
bϕ,Q:=EM∼μEHT∼Q[ϕ(L(M,HT))],(21)b_{\phi,Q}:=\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim Q}\left[\phi(L(M,H_T))\right], \tag*{(21)}

and

Bf(ALG,Q):=EM∼μDf(PM,ALG∥Q).(22)B_f(\mathrm{ALG},Q):=\mathbb{E}_{M\sim\mu}D_f\left(P^{M,\mathrm{ALG}}\middle\|Q\right). \tag*{(22)}

Then

Df(Bern⁡(aϕ)∥Bern⁡(bϕ,Q))≤Bf(ALG,Q).(23)D_f\left(\operatorname{Bern}(a_{\phi})\middle\|\operatorname{Bern}(b_{\phi,Q})\right)\leq B_f(\mathrm{ALG},Q). \tag*{(23)}

Consequently,

af−(Bf(ALG,Q);bϕ,Q)≤aϕ≤af+(Bf(ALG,Q);bϕ,Q).(24)a_f^{-}(B_f(\mathrm{ALG},Q);b_{\phi,Q}) \le a_\phi\le a_f^{+}(B_f(\mathrm{ALG},Q);b_{\phi,Q}). \tag*{(24)}

Remark III.2 (Choice of inversion direction). Theorem III.1 gives a two-sided constraint on the expected transform aϕa_\phi. The endpoint used in a particular application depends on the direction of the desired converse.

For the CVaR lower bound developed below, we use the nondecreasing hinge transform

ϕs(ℓ)=(ℓ−s)+Lmax⁡,(25)\phi_s(\ell)=\frac{(\ell-s)_+}{L_{\max}}, \tag*{(25)}

and therefore require a lower bound on E[ϕs(L)]\mathbb{E}[\phi_s(L)]. Hence only the lower endpoint af−a_f^{-} enters the CVaR converse.

The upper endpoint af+a_f^{+} is retained in the general theorem because it is useful for transforms for which an upper bound on the expected transform yields the desired lower bound, such as success-probability or complementary tails.

Remark III.3 (Binary reduction). The proof introduces an independent U∼Unif⁡[0,1]U\sim\operatorname{Unif}[0,1] and sets

References

  1. [1]R. Bongole, T. J. Oechtering, and M. Skoglund, “Generalizing the fano inequality further,” arXiv preprint arXiv:2601.12027, 2026.arxiv.org/abs/2601.12027
  2. [2]——, “Instantiating bayesian cvar lower bounds in interactive decision making problems,” arXiv preprint arXiv:2604.12519, 2026.
  3. [3]D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin, “The statistical complexity of interactive decision making,” 2023. [Online]. Available: https://arxiv.org/abs/2112.13487
  4. [4]D. J. Foster, N. Golowich, and Y. Han, “Tight guarantees for interactive decision making with the decision-estimation coefficient,” in The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023, pp. 3969–4043.arxiv.org/abs/2301.08215
  5. [5]F. Chen, D. J. Foster, Y. Han, J. Qian, A. Rakhlin, and Y. Xu, “Assouad, fano, and le cam with interaction: A unifying lower bound framework and characterization for bandit learnability,” Advances in Neural Information Processing Systems, vol. 37, pp. 75 585–75 641, 2024.arxiv.org/abs/2410.05117
  6. [6]R. Bongole, A. Zamani, T. J. Oechtering, and M. Skoglund, “Minimax quantile lower bounds for interactive statistical decision making with privacy,” arXiv preprint arXiv:2606.23096, 2026.arxiv.org/abs/2606.23096
  7. [7]A. R. Esposito, A. Vandenbroucque, and M. Gastpar, “Lower bounds on the bayesian risk via information measures,” Journal of Machine Learning Research, vol. 25, no. 340, pp. 1–45, 2024.arxiv.org/abs/2303.12497
  8. [8]T. Ma, K. A. Verchand, and R. J. Samworth, “High-probability minimax lower bounds,” Statistical Science, vol. 41, no. 3, pp. 637–658, 2026.arxiv.org/abs/2406.13447
  9. [9]A. R. Esposito, “Minimax quantile bounds via information measures,” arXiv preprint arXiv:2608.20857, 2026.arxiv.org/abs/2608.20857
  10. [10]R. T. Rockafellar and S. Uryasev, “Conditional value-at-risk for general loss distributions,” Journal of banking & finance, vol. 26, no. 7, pp. 1443–1471, 2002.DOI
  11. [11]J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 429–438.
  12. [12]——, “Minimax optimal procedures for locally private estimation,” Journal of the American Statistical Association, vol. 113, no. 521, pp. 182–201, 2018.arxiv.org/abs/1604.02390
  13. [13]J. Duchi and R. Rogers, “Lower bounds for locally private estimation via communication complexity,” in Conference on Learning Theory. PMLR, 2019, pp. 1161–1191.arxiv.org/abs/1902.00582
  14. [14]F. Chen and A. Rakhlin, “Decision making in changing environments: Robustness, query-based learning, and differential privacy,” arXiv preprint arXiv:2501.14928, 2025.arxiv.org/abs/2501.14928
  15. [15]M. Aliakbarpour, A. Fallah, S. Roy, and R. Stevens, “High-probability bounds for heterogeneous local differential privacy,” arXiv preprint arXiv:2510.11895, 2025.arxiv.org/abs/2510.11895
  16. [16]Y. Polyanskiy and Y. Wu, Information theory: From coding to learning. Cambridge university press, 2025.
  17. [17]D. Basu, C. Dimitrakakis, and A. Tossou, “Privacy in multi-armed bandits: Fundamental definitions and lower bounds,” arXiv preprint arXiv:1905.12298, 2019.
  18. [18]W. Ren, X. Zhou, J. Liu, and N. B. Shroff, “Multi-armed bandits with local differential privacy,” arXiv preprint arXiv:2007.03121, 2020.arxiv.org/abs/2007.03121
  19. [19]C. Tan and P. Weng, “Cvar-regret bounds for multi-armed bandits,” in Asian Conference on Machine Learning. PMLR, 2023, pp. 974–989.
  20. [20]M. Joseph, J. Kulkarni, J. Mao, and S. Z. Wu, “Locally private gaussian estimation,” Advances in Neural Information Processing Systems, vol. 32, 2019.arxiv.org/abs/1811.08382
  21. [21]Y. Tao, Y. Wu, P. Zhao, and D. Wang, “Optimal rates of (locally) differentially private heavy-tailed multi-armed bandits,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2022, pp. 1546–1574.arxiv.org/abs/2106.02575
  22. [22]D. Baudry, R. Gautron, E. Kaufmann, and O. Maillard, “Optimal thompson sampling strategies for support-aware cvar bandits,” in International Conference on Machine Learning. PMLR, 2021, pp. 716–726.

Paper details

vlnc:W_rwdb99g9
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents