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 f f f -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 K K K -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 K K K -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.
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 f f f -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.
A fixed-prior Bayesian CVaR converse. For bounded losses, a hinge transform and the Rockafellar–Uryasev representation convert the general f f f -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.
Explicit Gaussian estimation and bandit lower bounds. We apply the converse to Gaussian mean estimation under squared error and to Gaussian K K K -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.
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 P P P and Q Q Q on a common measurable space, total variation is denoted by d T V ( P , Q ) d_{\mathrm{TV}}(P,Q) d TV ( P , Q ) and Kullback–Leibler divergence by D K L ( P ∥ Q ) D_{\mathrm{KL}}(P\mathbin{\|}Q) D KL ( P ∥ Q ) . For probability measures P P P and Q Q Q on a common measurable space and a convex function f : R + → R ∪ { + ∞ } f:\mathbb{R}_{+}\to\mathbb{R}\cup\{+\infty\} f : R + → R ∪ { + ∞ } satisfying f ( 1 ) = 0 f(1)=0 f ( 1 ) = 0 , the f f f -divergence is
D f ( P ∥ Q ) : = ∫ q f ( p q ) d λ , (1) D_f(P\mathbin{\|}Q):=\int q f\left(\frac{p}{q}\right)\,\mathrm{d}\lambda, \tag*{(1)} D f ( P ∥ Q ) := ∫ q f ( q p ) d λ , (1)
where λ \lambda λ is any measure dominating P P P and Q Q Q , with p = d P / d λ p=\mathrm{d}P/\mathrm{d}\lambda p = d P / d λ and q = d Q / d λ q=\mathrm{d}Q/\mathrm{d}\lambda q = d Q / d λ [16 ] . This definition is independent of the choice of λ \lambda λ .
We write
[ x ] + : = max { x , 0 } . (2) [x]_{+}:=\max\{x,0\}. \tag*{(2)} [ x ] + := max { x , 0 } . (2)
The Bernoulli distribution with mean a a a is denoted by Bern ( a ) \operatorname{Bern}(a) Bern ( a ) .
For a nonnegative random variable L L L and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , the CVaR is written as
CVaR α ( L ) : = inf s ∈ R { s + 1 1 − α 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)} CVaR α ( L ) := s ∈ R inf { s + 1 − α 1 E [( L − s ) + ] } . (3)
Interactive statistical decision making
Let M \mathcal{M} M be a model class, A \mathcal{A} A an action space, and Y \mathcal{Y} Y an observation space. An interactive procedure ALG ∈ D \operatorname{ALG}\in\mathcal{D} ALG ∈ D operates for T T T rounds. Given the history
H t − 1 = ( A 1 , Y 1 , … , A t − 1 , Y t − 1 ) , (4) H_{t-1}=(A_{1},Y_{1},\ldots,A_{t-1},Y_{t-1}), \tag*{(4)} H t − 1 = ( A 1 , Y 1 , … , A t − 1 , Y t − 1 ) , (4)
it selects
A t ∼ π t ( ⋅ ∣ H t − 1 ) . (5) A_{t}\sim\pi_{t}(\mathord{\cdot}\mid H_{t-1}). \tag*{(5)} A t ∼ π t ( ⋅ ∣ H t − 1 ) . (5)
Under a model M ∈ M M\in\mathcal{M} M ∈ M , the environment then generates
Y t ∼ P t M ( ⋅ ∣ A t , H t − 1 ) . (6) Y_{t}\sim P_{t}^{M}(\mathord{\cdot}\mid A_{t},H_{t-1}). \tag*{(6)} Y t ∼ P t M ( ⋅ ∣ A t , H t − 1 ) . (6)
The transcript is
H T = ( A 1 , Y 1 , … , A T , Y T ) , (7) H_T = (A_1, Y_1, \ldots, A_T, Y_T), \tag*{(7)} H T = ( A 1 , Y 1 , … , A T , Y T ) , (7)
and its induced distribution is denoted by
P M , A L G . (8) \mathbb{P}^{M,\mathrm{ALG}}. \tag*{(8)} P M , ALG . (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)} μ ∈ P ( M ) . (9)
For a fixed procedure ALG, the Bayesian experiment is
M ∼ μ , H T ∣ M ∼ P M , A L G . (10) M \sim\mu, \qquad H_T \mid M \sim\mathbb{P}^{M,\mathrm{ALG}}. \tag*{(10)} M ∼ μ , H T ∣ M ∼ P M , ALG . (10)
Equivalently, the joint law of the model and transcript is
P μ , A L G ( d M , d h ) : = μ ( d M ) P M , A L G ( d h ) . (11) \mathbb{P}_{\mu,\mathrm{ALG}}(dM,dh) := \mu(dM)\mathbb{P}^{M,\mathrm{ALG}}(dh). \tag*{(11)} P μ , ALG ( d M , d h ) := μ ( d M ) P M , ALG ( d h ) . (11)
Let
L : M × H T → [ 0 , ∞ ) (12) L : \mathcal{M} \times\mathcal{H}_T \to[0,\infty) \tag*{(12)} L : M × H T → [ 0 , ∞ ) (12)
be a measurable loss. The fixed-prior Bayesian CVaR value is
CVaR α μ , A L G ( L ) : = inf s ∈ R { s + 1 1 − α E P μ , A L G [ ( 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)} CVaR α μ , ALG ( L ) := s ∈ R inf { s + 1 − α 1 E P μ , ALG [( L − s ) + ] } . (13)
For the fixed prior μ \mu μ , the optimal Bayesian CVaR is
E α ( μ ) : = inf A L G ∈ D CVaR α μ , A L G ( L ) , (14) \mathcal{E}_{\alpha}(\mu) := \inf_{\mathrm{ALG}\in\mathcal{D}} \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L), \tag*{(14)} E α ( μ ) := ALG ∈ D inf CVaR α μ , ALG ( L ) , (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 f f f -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 f f f -divergence inverses.
Fix a prior μ \mu μ , a procedure ALG, and a probability distribution Q Q Q on the transcript space. Let ϕ : R + → [ 0 , 1 ] \phi:\mathbb{R}_{+}\to[0,1] ϕ : R + → [ 0 , 1 ] be measurable and define
a ϕ : = E M ∼ μ E H T ∼ P M , A L G [ ϕ ( L ( M , H T ) ) ] , (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)} a ϕ := E M ∼ μ E H T ∼ P M , ALG [ ϕ ( L ( M , H T )) ] , (15)
b ϕ , Q : = E M ∼ μ E H T ∼ Q [ ϕ ( L ( M , H T ) ) ] . (16) b_{\phi,Q}:=\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim Q}\left[\phi(L(M,H_T))\right]. \tag*{(16)} b ϕ , Q := E M ∼ μ E H T ∼ Q [ ϕ ( L ( M , H T )) ] . (16)
For an f f f -divergence, define the average divergence
B f ( A L G , Q ) : = E M ∼ μ D f ( P M , A L G ∥ Q ) . (17) B_f(\mathrm{ALG},Q):=\mathbb{E}_{M\sim\mu}D_f\left(P^{M,\mathrm{ALG}}\middle\|Q\right). \tag*{(17)} B f ( ALG , Q ) := E M ∼ μ D f ( P M , ALG Q ) . (17)
For b ∈ [ 0 , 1 ] b\in[0,1] b ∈ [ 0 , 1 ] and B ≥ 0 B\geq0 B ≥ 0 , define the lower and upper Bernoulli f f f -divergence inverses by
a f − ( B ; b ) : = inf { a ∈ [ 0 , 1 ] : D f ( 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)} a f − ( B ; b ) := inf { a ∈ [ 0 , 1 ] : D f ( Bern ( a ) ∥ Bern ( b )) ≤ B } , (18)
a f + ( B ; b ) : = sup { a ∈ [ 0 , 1 ] : D f ( 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)} a f + ( B ; b ) := sup { a ∈ [ 0 , 1 ] : D f ( Bern ( a ) ∥ Bern ( b )) ≤ B } . (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 f f f -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 Q Q Q , a measurable function ϕ : R + → [ 0 , 1 ] \phi:\mathbb{R}_{+}\to[0,1] ϕ : R + → [ 0 , 1 ] , and an f f f -divergence. Let
a ϕ : = E M ∼ μ E H T ∼ P M , A L G [ ϕ ( L ( M , H T ) ) ] , (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)} a ϕ := E M ∼ μ E H T ∼ P M , ALG [ ϕ ( L ( M , H T )) ] , (20) b ϕ , Q : = E M ∼ μ E H T ∼ Q [ ϕ ( L ( M , H T ) ) ] , (21) b_{\phi,Q}:=\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim Q}\left[\phi(L(M,H_T))\right], \tag*{(21)} b ϕ , Q := E M ∼ μ E H T ∼ Q [ ϕ ( L ( M , H T )) ] , (21) and
B f ( A L G , Q ) : = E M ∼ μ D f ( P M , A L G ∥ Q ) . (22) B_f(\mathrm{ALG},Q):=\mathbb{E}_{M\sim\mu}D_f\left(P^{M,\mathrm{ALG}}\middle\|Q\right). \tag*{(22)} B f ( ALG , Q ) := E M ∼ μ D f ( P M , ALG Q ) . (22) Then
D f ( Bern ( a ϕ ) ∥ Bern ( b ϕ , Q ) ) ≤ B f ( A L G , Q ) . (23) D_f\left(\operatorname{Bern}(a_{\phi})\middle\|\operatorname{Bern}(b_{\phi,Q})\right)\leq B_f(\mathrm{ALG},Q). \tag*{(23)} D f ( Bern ( a ϕ ) ∥ Bern ( b ϕ , Q ) ) ≤ B f ( ALG , Q ) . (23)
Consequently,
a f − ( B f ( A L G , Q ) ; b ϕ , Q ) ≤ a ϕ ≤ a f + ( B f ( A L G , 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)} a f − ( B f ( ALG , Q ) ; b ϕ , Q ) ≤ a ϕ ≤ a f + ( B f ( ALG , Q ) ; b ϕ , Q ) . (24)
Remark III.2 (Choice of inversion direction). Theorem III.1 gives a two-sided constraint on the expected transform a ϕ a_\phi a ϕ . 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 ) + L max , (25) \phi_s(\ell)=\frac{(\ell-s)_+}{L_{\max}}, \tag*{(25)} ϕ s ( ℓ ) = L m a x ( ℓ − s ) + , (25)
and therefore require a lower bound on E [ ϕ s ( L ) ] \mathbb{E}[\phi_s(L)] E [ ϕ s ( L )] . Hence only the lower endpoint a f − a_f^{-} a f − enters the CVaR converse.
The upper endpoint a f + a_f^{+} 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] U ∼ Unif [ 0 , 1 ] and sets
V = 1 { U ≤ ϕ ( L ( M , H T ) ) } . (26) V=\mathbb{1}\{U\le\phi(L(M,H_T))\}. \tag*{(26)} V = 1 { U ≤ ϕ ( L ( M , H T ))} . (26)
Under the model-dependent joint law, V ∼ Bern ( a ϕ ) V\sim\operatorname{Bern}(a_\phi) V ∼ Bern ( a ϕ ) ; under the reference joint law, V ∼ Bern ( b ϕ , Q ) V\sim\operatorname{Bern}(b_{\phi,Q}) V ∼ Bern ( b ϕ , Q ) . Data processing gives (23) .
Remark III.4 (Relation to quantile reductions). Choosing ϕ \phi ϕ as the indicator of a loss event recovers the single-threshold reduction used in quantile lower bounds [5 ] . More generally, Theorem III.1 allows any measurable function ϕ : R + → [ 0 , 1 ] \phi:\mathbb{R}_+\to[0,1] ϕ : R + → [ 0 , 1 ] . This additional flexibility permits bounded transforms of the loss, including the hinge transform used below to obtain the CVaR lower bound.
Bayesian CVaR Lower Bounds
This section specializes the generalized Fano inequality to fixed-prior Bayesian CVaR. For a prior μ \mu μ and a procedure A L G \mathrm{ALG} ALG , let
M ∼ μ , H T ∣ M ∼ P M , A L G . M\sim\mu,\qquad H_T\mid M\sim P^{M,\mathrm{ALG}}. M ∼ μ , H T ∣ M ∼ P M , ALG .
The prior-predictive Bayesian CVaR of the loss L ( M , H T ) L(M,H_T) L ( M , H T ) is
CVaR α μ , A L G ( L ) : = inf s ∈ R { s + 1 1 − α E M ∼ μ E H T ∼ P M , A L G [ ( L ( M , H T ) − s ) + ] } . (27) \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L)
:=\inf_{s\in\mathbb{R}}\left\{s+\frac{1}{1-\alpha}\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim P^{M,\mathrm{ALG}}}\left[(L(M,H_T)-s)_+\right]\right\}. \tag*{(27)} CVaR α μ , ALG ( L ) := s ∈ R inf { s + 1 − α 1 E M ∼ μ E H T ∼ P M , ALG [ ( L ( M , H T ) − s ) + ] } . (27)
Assume that 0 ≤ L ≤ L max 0 \le L \le L_{\max} 0 ≤ L ≤ L m a x . The infimum in (27) may then be restricted to s ∈ [ 0 , L max ] s \in[0,L_{\max}] s ∈ [ 0 , L m a x ] . For such s s s , define the normalized hinge transform
ϕ s ( ℓ ) : = ( ℓ − s ) + L max , (28) \phi_s(\ell) := \frac{(\ell-s)_+}{L_{\max}}, \tag*{(28)} ϕ s ( ℓ ) := L m a x ( ℓ − s ) + , (28)
so that ϕ s ( ℓ ) ∈ [ 0 , 1 ] \phi_s(\ell) \in[0,1] ϕ s ( ℓ ) ∈ [ 0 , 1 ] . For a reference distribution Q Q Q on the transcript space, independent of M ∼ μ M \sim\mu M ∼ μ , define
b s ( Q ) : = 1 L max E M ∼ μ E H T ∼ Q [ ( L ( M , H T ) − s ) + ] . (29) b_s(Q) := \frac{1}{L_{\max}}\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim Q}[(L(M,H_T)-s)_+]. \tag*{(29)} b s ( Q ) := L m a x 1 E M ∼ μ E H T ∼ Q [( L ( M , H T ) − s ) + ] . (29)
Applying Theorem III.1 to ϕ s \phi_s ϕ s yields a general lower bound on Bayesian CVaR in terms of the reference excess loss b s ( Q ) b_s(Q) b s ( Q ) and the prior-averaged divergence B f ( A L G , Q ) B_f(\mathrm{ALG},Q) B f ( ALG , Q ) .
Corollary IV.1 (Fixed-prior Bayesian CVaR lower bound). For every reference distribution Q Q Q and every A L G ∈ D \mathrm{ALG} \in\mathcal{D} ALG ∈ D ,
CVaR α μ , A L G ( L ) ≥ inf 0 ≤ s ≤ L max { s + L max 1 − α a f − ( B f ( A L G , Q ) ; b s ( Q ) ) } . (30) \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L) \ge\inf_{0\le s\le L_{\max}}\left\{s+\frac{L_{\max}}{1-\alpha}a_f^{-}(B_f(\mathrm{ALG},Q);b_s(Q))\right\}. \tag*{(30)} CVaR α μ , ALG ( L ) ≥ 0 ≤ s ≤ L m a x inf { s + 1 − α L m a x a f − ( B f ( ALG , Q ) ; b s ( Q )) } . (30) The same bound therefore holds after taking the infimum over any subclass of admissible procedures, including procedures satisfying local differential privacy.
Remark IV.2. To apply (30) , it is enough to lower bound b s ( Q ) b_s(Q) b s ( Q ) and upper bound B f ( A L G , Q ) B_f(\mathrm{ALG},Q) B f ( ALG , Q ) . These two quantities are then inserted into the lower Bernoulli inverse a f − a_f^{-} a f − . The reference distribution Q Q Q is chosen to make both calculations tractable.
Reverse-KL Specialization
Take f ( u ) = − log u f(u)=-\log u f ( u ) = − log u . Then D f ( P ∥ Q ) = D K L ( Q ∥ P ) D_f(P\mathbin{\|}Q)=D_{\mathrm{KL}}(Q\mathbin{\|}P) D f ( P ∥ Q ) = D KL ( Q ∥ P ) . Let h ( b ) = − b log b − ( 1 − b ) log ( 1 − b ) h(b)=-b\log b-(1-b)\log(1-b) h ( b ) = − b log b − ( 1 − b ) log ( 1 − b ) denote the binary entropy.
To obtain explicit bounds from Corollary IV.1, we next lower bound the Bernoulli inverse for reverse KL. The following lemma shows that an upper bound on D K L ( Bern ( b ) ∥ Bern ( a ) ) D_{\mathrm{KL}}(\operatorname{Bern}(b)\mathbin{\|}\operatorname{Bern}(a)) D KL ( Bern ( b ) ∥ Bern ( a )) yields an exponential lower bound on a a a .
Lemma IV.3 (Reverse-KL Bernoulli inverse). Suppose b ∈ ( 0 , 1 ] b \in(0,1] b ∈ ( 0 , 1 ] and D K L ( Bern ( b ) ∥ Bern ( a ) ) ≤ B D_{\mathrm{KL}}(\operatorname{Bern}(b)\mathbin{\|}\operatorname{Bern}(a)) \le B D KL ( Bern ( b ) ∥ Bern ( a )) ≤ B . Then
a ≥ exp ( − B + h ( b ) b ) . (31) a \ge\exp\left(-\frac{B+h(b)}{b}\right). \tag*{(31)} a ≥ exp ( − b B + h ( b ) ) . (31) Consequently, if b ≥ β > 0 b \ge\beta> 0 b ≥ β > 0 , then
a f − ( B ; b ) ≥ 1 2 1 / β e − B / β . (32) a_f^{-}(B;b) \ge\frac{1}{2^{1/\beta}}e^{-B/\beta}. \tag*{(32)} a f − ( B ; b ) ≥ 2 1/ β 1 e − B / β . (32)
In particular, for β = 1 / 4 \beta= 1/4 β = 1/4 ,
a f − ( B ; b ) ≥ 1 16 e − 4 B . (33) a_f^{-}(B;b) \ge\frac{1}{16}e^{-4B}. \tag*{(33)} a f − ( B ; b ) ≥ 16 1 e − 4 B . (33)
Remark IV.4 (Dependence on the CVaR level). The bound (33) is exponential in the divergence budget B B B . In (30), this term is multiplied by ( 1 − α ) − 1 (1-\alpha)^{-1} ( 1 − α ) − 1 . Balancing these two terms when choosing the separation between the hard models yields the factor log ( 1 / ( 1 − α ) ) \log(1/(1-\alpha)) log ( 1/ ( 1 − α )) appearing in the applications below.
Applying the Bayesian CVaR Bound
This section summarizes the steps used to apply the Bayesian CVaR bound to a concrete statistical problem. We first fix the prior and, when necessary, replace the original loss by a bounded lower proxy. We then choose a reference distribution, lower bound the corresponding reference excess loss, and upper bound the prior-averaged divergence. These quantities are inserted into the Bernoulli inverse and then into the CVaR bound. If the prior belongs to a parameterized family, the separation parameter is chosen only after the fixed-prior inequality has been established.
Fixed prior and bounded loss
Choose a prior μ \mu μ and a loss or bounded proxy ℓ \ell ℓ satisfying
0 ≤ ℓ ≤ L max and ℓ ≤ L . (34) 0 \le\ell\le L_{\max} \qquad\text{and} \qquad\ell\le L. \tag*{(34)} 0 ≤ ℓ ≤ L m a x and ℓ ≤ L . (34)
Then
CVaR α ( L ) ≥ CVaR α ( ℓ ) . (35) \operatorname{CVaR}_{\alpha}(L) \ge\operatorname{CVaR}_{\alpha}(\ell). \tag*{(35)} CVaR α ( L ) ≥ CVaR α ( ℓ ) . (35)
Reference distribution
Choose a probability distribution Q Q Q on the transcript space. For thresholds s ∈ [ 0 , L max ] s \in[0,L_{\max}] s ∈ [ 0 , L m a x ] , compute
b s ( Q ) = 1 L max E μ , Q [ ( ℓ − s ) + ] . (36) b_s(Q) = \frac{1}{L_{\max}}\mathbb{E}_{\mu,Q}[(\ell-s)_{+}]. \tag*{(36)} b s ( Q ) = L m a x 1 E μ , Q [( ℓ − s ) + ] . (36)
Choose Q Q Q so that both the excess-loss expectation and the divergence bound can be evaluated explicitly.
Divergence bound
For the same Q Q Q , bound
B f ( A L G , Q ) = E M ∼ μ D f ( P M , A L G ∥ Q ) . (37) B_f(\mathrm{ALG},Q)=\mathbb{E}_{M\sim\mu}D_f(P^{M,\mathrm{ALG}}\|Q). \tag*{(37)} B f ( ALG , Q ) = E M ∼ μ D f ( P M , ALG ∥ Q ) . (37)
The bound must hold for every algorithm in the class being considered.
Bernoulli inversion and CVaR
A lower bound
b s ( Q ) ≥ β (38) b_s(Q)\ge\beta \tag*{(38)} b s ( Q ) ≥ β (38)
combined with an upper bound B f ( A L G , Q ) ≤ B ‾ B_f(\mathrm{ALG},Q)\le\overline{B} B f ( ALG , Q ) ≤ B gives a lower bound on a f − ( B f ; b s ) a_f^{-}(B_f;b_s) a f − ( B f ; b s ) through the chosen divergence specialization. This is substituted into (30) .
For reverse KL, if b s ≥ 1 / 4 b_s\ge1/4 b s ≥ 1/4 , then
a f − ( B f ; b s ) ≥ 1 16 e − 4 B f . (39) a_f^{-}(B_f;b_s)\ge\frac{1}{16}e^{-4B_f}. \tag*{(39)} a f − ( B f ; b s ) ≥ 16 1 e − 4 B f . (39)
Remark V.1 (Fixed prior and hard-family choice). For a fixed separation parameter, the prior is fixed and the lower bound is a statement about that specified prior. Afterward, choosing the separation parameter as a function of α \alpha α , T T T , n n n , or the privacy parameters gives an existence result: at least one prior in the chosen family satisfies the resulting optimized lower bound.
Bayesian CVaR Bounds for Gaussian Models
This section applies the general Bayesian CVaR bound to two Gaussian statistical problems without privacy constraints. We first consider Gaussian mean estimation and then Gaussian K K K -armed stochastic bandits. In each case, we first derive a lower bound for every fixed prior in a parameterized family and then choose the separation parameter to obtain an explicit hard-prior rate. The same Gaussian model families will be used again under LDP in Section VIII.
Gaussian mean estimation
Let
X 1 , … , X n ∼ i . i . d . N ( θ , σ 2 ) , θ ∈ [ − R , R ] , (40) X_1,\ldots,X_n\mathrel{\overset{\mathrm{i.i.d.}}{\sim}}\mathcal{N}(\theta,\sigma^2),\qquad\theta\in[-R,R], \tag*{(40)} X 1 , … , X n ∼ i.i.d. N ( θ , σ 2 ) , θ ∈ [ − R , R ] , (40)
where σ > 0 \sigma>0 σ > 0 . For Δ ∈ ( 0 , R ] \Delta\in(0,R] Δ ∈ ( 0 , R ] , fix the prior
μ Δ : = 1 2 δ − Δ + 1 2 δ + Δ . (41) \mu_{\Delta}:=\frac{1}{2}\delta_{-\Delta}+\frac{1}{2}\delta_{+\Delta}. \tag*{(41)} μ Δ := 2 1 δ − Δ + 2 1 δ + Δ . (41)
For an estimator θ ^ \hat{\theta} θ ^ , use the bounded loss
ℓ Δ : = min { ( θ ^ − θ ) 2 , Δ 2 } . (42) \ell_{\Delta} := \min\left\{(\hat{\theta}-\theta)^2,\Delta^2\right\}. \tag*{(42)} ℓ Δ := min { ( θ ^ − θ ) 2 , Δ 2 } . (42)
Then 0 ≤ ℓ Δ ≤ Δ 2 0 \le\ell_{\Delta} \le\Delta^2 0 ≤ ℓ Δ ≤ Δ 2 and, for every z ∈ R z \in\mathbb{R} z ∈ R ,
ℓ Δ ( + Δ , z ) + ℓ Δ ( − Δ , z ) ≥ Δ 2 . (43) \ell_{\Delta}(+\Delta,z)+\ell_{\Delta}(-\Delta,z)\ge\Delta^2. \tag*{(43)} ℓ Δ ( + Δ , z ) + ℓ Δ ( − Δ , z ) ≥ Δ 2 . (43)
The following theorem gives the fixed-prior Bayesian CVaR lower bound for squared-error estimation under the two-point prior μ Δ \mu_{\Delta} μ Δ . It first holds for every fixed Δ ∈ ( 0 , R ] \Delta\in(0,R] Δ ∈ ( 0 , R ] ; choosing Δ \Delta Δ afterward gives the stated dependence on n n n , σ 2 \sigma^2 σ 2 , R R R , and the CVaR level α \alpha α .
Theorem VI.1 (Gaussian mean estimation). For every Δ ∈ ( 0 , R ] \Delta\in(0,R] Δ ∈ ( 0 , R ] and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
inf θ ^ CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ Δ 2 min { 1 2 , 1 16 ( 1 − α ) exp ( − 4 n Δ 2 σ 2 ) } . (44) \inf_{\hat{\theta}}\operatorname{CVaR}_{\alpha}^{\mu_{\Delta}}\left((\hat{\theta}-\theta)^2\right)\ge\Delta^2\min\left\{\frac{1}{2},\frac{1}{16(1-\alpha)}\exp\left(-\frac{4n\Delta^2}{\sigma^2}\right)\right\}. \tag*{(44)} θ ^ inf CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ Δ 2 min { 2 1 , 16 ( 1 − α ) 1 exp ( − σ 2 4 n Δ 2 ) } . (44) If δ = 1 − α < 1 / 8 \delta=1-\alpha<1/8 δ = 1 − α < 1/8 , choosing
Δ 2 : = min { R 2 , σ 2 4 n log 1 8 δ } (45) \Delta^2:=\min\left\{R^2,\frac{\sigma^2}{4n}\log\frac{1}{8\delta}\right\} \tag*{(45)} Δ 2 := min { R 2 , 4 n σ 2 log 8 δ 1 } (45) gives
inf θ ^ CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ 1 2 min { R 2 , σ 2 4 n log 1 8 ( 1 − α ) } . (46) \inf_{\hat{\theta}}\operatorname{CVaR}_{\alpha}^{\mu_{\Delta}}\left((\hat{\theta}-\theta)^2\right)\ge\frac{1}{2}\min\left\{R^2,\frac{\sigma^2}{4n}\log\frac{1}{8(1-\alpha)}\right\}. \tag*{(46)} θ ^ inf CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ 2 1 min { R 2 , 4 n σ 2 log 8 ( 1 − α ) 1 } . (46) In particular,
inf θ ^ CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≳ min { R 2 , σ 2 n log 1 1 − α } , (47) \inf_{\hat{\theta}}\operatorname{CVaR}_{\alpha}^{\mu_{\Delta}}\left((\hat{\theta}-\theta)^2\right)\gtrsim\min\left\{R^2,\frac{\sigma^2}{n}\log\frac{1}{1-\alpha}\right\}, \tag*{(47)} θ ^ inf CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≳ min { R 2 , n σ 2 log 1 − α 1 } , (47) up to universal constants in the stated range of α \alpha α .
Remark VI.2 (Relation to the mean-estimation minimax rate). The optimized lower bound has the familiar 1 / n 1/n 1/ n squared-error dependence, with an additional logarithmic factor in the CVaR tail level. The theorem is a fixed-prior statement before the choice in (45).
K-armed Gaussian bandits
Let K ≥ 2 K \ge2 K ≥ 2 . For g ∈ ( 0 , 1 ] g \in(0,1] g ∈ ( 0 , 1 ] and j ∈ [ K ] j \in[K] j ∈ [ K ] , define the Gaussian bandit model M j g M_j^g M j g by
Y t ∣ A t = a , M j g ∼ { N ( g , σ 2 ) , a = j , N ( 0 , σ 2 ) , a ≠ j . (48) Y_t\mid A_t=a,M_j^g\sim
\begin{cases}
\mathcal{N}(g,\sigma^2), & a=j,\\
\mathcal{N}(0,\sigma^2), & a\ne j.
\end{cases} \tag*{(48)} Y t ∣ A t = a , M j g ∼ { N ( g , σ 2 ) , N ( 0 , σ 2 ) , a = j , a = j . (48)
Thus arm j j j is uniquely optimal with gap g g g . Fix the uniform prior
μ g K = 1 K ∑ j = 1 K δ M j g . (49) \mu_g^K = \frac{1}{K}\sum_{j=1}^{K}\delta_{M_j^g}. \tag*{(49)} μ g K = K 1 j = 1 ∑ K δ M j g . (49)
Let N j ( T ) N_j(T) N j ( T ) be the number of pulls of arm j j j . The pseudo-regret under M j g M_j^g M j g is
R T ( M j g ) = g ( T − N j ( T ) ) . (50) R_T(M_j^g) = g\bigl(T-N_j(T)\bigr). \tag*{(50)} R T ( M j g ) = g ( T − N j ( T ) ) . (50)
The following theorem lower bounds the Bayesian CVaR of cumulative pseudo-regret under the fixed prior μ g K \mu_g^K μ g K . The first bound holds for every fixed gap g ∈ ( 0 , 1 ] g \in(0,1] g ∈ ( 0 , 1 ] . Choosing the gap afterward gives an explicit lower bound in terms of T T T , K K K , σ 2 \sigma^2 σ 2 , and α \alpha α .
Theorem VI.3 (K K K -armed Gaussian bandit). For every g ∈ ( 0 , 1 ] g \in(0,1] g ∈ ( 0 , 1 ] and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
inf A L G ∈ D T CVaR α μ g K ( R T ) ≥ T g min { K − 1 2 K , 1 16 ( 1 − α ) exp ( − 2 g 2 T K σ 2 ) } . (51) \inf_{\mathrm{ALG}\in\mathcal{D}_T}\operatorname{CVaR}_{\alpha}^{\mu_g^K}(R_T) \geq Tg\min\left\{\frac{K-1}{2K},\frac{1}{16(1-\alpha)}\exp\left(-\frac{2g^2T}{K\sigma^2}\right)\right\}. \tag*{(51)} ALG ∈ D T inf CVaR α μ g K ( R T ) ≥ T g min { 2 K K − 1 , 16 ( 1 − α ) 1 exp ( − K σ 2 2 g 2 T ) } . (51) For 1 − α < K / [ 8 ( K − 1 ) ] 1-\alpha< K/[8(K-1)] 1 − α < K / [ 8 ( K − 1 )] , choosing
g 2 ≔ min { 1 , K σ 2 2 T log K 8 ( K − 1 ) ( 1 − α ) } (52) g^2 \coloneqq\min\left\{1,\frac{K\sigma^2}{2T}\log\frac{K}{8(K-1)(1-\alpha)}\right\} \tag*{(52)} g 2 : = min { 1 , 2 T K σ 2 log 8 ( K − 1 ) ( 1 − α ) K } (52) gives, for a suitable uniform hard prior,
inf A L G ∈ D T CVaR α μ g K ( R T ) ≥ K − 1 2 K T min { 1 , σ K 2 T log K 8 ( K − 1 ) ( 1 − α ) } . (53) \inf_{\mathrm{ALG}\in\mathcal{D}_T}\operatorname{CVaR}_{\alpha}^{\mu_g^K}(R_T) \geq\frac{K-1}{2K}T\min\left\{1,\sigma\sqrt{\frac{K}{2T}}\sqrt{\log\frac{K}{8(K-1)(1-\alpha)}}\right\}. \tag*{(53)} ALG ∈ D T inf CVaR α μ g K ( R T ) ≥ 2 K K − 1 T min { 1 , σ 2 T K log 8 ( K − 1 ) ( 1 − α ) K } . (53) Consequently, for fixed K K K ,
inf A L G ∈ D T CVaR α μ g K ( R T ) ≳ min { T , σ K T log 1 1 − α } (54) \inf_{\mathrm{ALG}\in\mathcal{D}_T}\operatorname{CVaR}_{\alpha}^{\mu_g^K}(R_T) \gtrsim\min\left\{T,\sigma\sqrt{KT\log\frac{1}{1-\alpha}}\right\} \tag*{(54)} ALG ∈ D T inf CVaR α μ g K ( R T ) ≳ min { T , σ K T log 1 − α 1 } (54) up to constants depending only on K K K and for the stated range of α \alpha α .
Remark VI.4 (Origin of the 1 / K 1/K 1/ K factor). The uniform prior contains K K K possible optimal arms. Under the one-good-arm construction (48), the null reference with all arms distributed as N ( 0 , σ 2 ) \mathcal{N}(0,\sigma^2) N ( 0 , σ 2 ) differs from M j g M_j^g M j g only when arm j j j is selected. Averaging the resulting transcript divergence over j j j and using ∑ j = 1 K N j ( T ) = T \sum_{j=1}^{K}N_j(T)=T ∑ j = 1 K N j ( T ) = T produces the factor 1 / K 1/K 1/ K .
Interactive Statistical Decision Making under LDP
This section incorporates local differential privacy into the ISDM model. We first define the released observation and transcript laws when each raw observation is passed through an LDP channel. We then recall the contraction of distinguishability induced by an LDP channel and use it together with the KL chain rule to obtain a divergence bound for the complete adaptive released transcript. This transcript-level bound will provide the information term in the Bayesian CVaR results of Section VIII.
Observation model under LDP
At round t t t , given the released history
H t − 1 L D P = ( A 1 , Z 1 , … , A t − 1 , Z t − 1 ) , (55) H_{t-1}^{\mathrm{LDP}} = (A_1, Z_1, \ldots, A_{t-1}, Z_{t-1}), \tag*{(55)} H t − 1 LDP = ( A 1 , Z 1 , … , A t − 1 , Z t − 1 ) , (55)
the learner chooses
A t ∼ π t ( ⋅ ∣ H t − 1 L D P ) . (56) A_t \sim\pi_t(\cdot\mid H_{t-1}^{\mathrm{LDP}}). \tag*{(56)} A t ∼ π t ( ⋅ ∣ H t − 1 LDP ) . (56)
The model then generates
Y t ∼ P t M ( ⋅ ∣ A t , H t − 1 L D P ) , (57) Y_t \sim P_t^M(\cdot\mid A_t, H_{t-1}^{\mathrm{LDP}}), \tag*{(57)} Y t ∼ P t M ( ⋅ ∣ A t , H t − 1 LDP ) , (57)
and the learner observes
Z t ∼ W t ( ⋅ ∣ Y t , A t , H t − 1 L D P ) . (58) Z_t \sim W_t(\cdot\mid Y_t, A_t, H_{t-1}^{\mathrm{LDP}}). \tag*{(58)} Z t ∼ W t ( ⋅ ∣ Y t , A t , H t − 1 LDP ) . (58)
We first specify the privacy requirement imposed on each released observation.
Definition VII.1 (Sequential local differential privacy). The channel W t W_t W t is ε t \varepsilon_t ε t -LDP if, for every history h h h , action a a a , pair of raw observations y , y ′ y,y' y , y ′ , and measurable set C ⊆ Z C \subseteq\mathcal{Z} C ⊆ Z ,
W t ( C ∣ y , a , h ) ≤ e ε t W t ( C ∣ y ′ , a , h ) . (59) W_t(C \mid y,a,h) \le e^{\varepsilon_t}W_t(C \mid y',a,h). \tag*{(59)} W t ( C ∣ y , a , h ) ≤ e ε t W t ( C ∣ y ′ , a , h ) . (59) A procedure is ε \varepsilon ε -LDP if this condition holds at every round, where
ε = ( ε 1 , … , ε T ) . (60) \varepsilon= (\varepsilon_1,\ldots,\varepsilon_T). \tag*{(60)} ε = ( ε 1 , … , ε T ) . (60) The condition is meaningful for every finite ε t ≥ 0 \varepsilon_t \ge0 ε t ≥ 0 . The case ε t = 0 \varepsilon_t = 0 ε t = 0 forces the released distribution to be the same for every raw observation, while larger values impose weaker privacy constraints. In the lower bounds below, the additional restriction ε t ≤ 1 \varepsilon_t \le1 ε t ≤ 1 is used only to simplify the contraction coefficient to a constant multiple of ε t 2 \varepsilon_t^2 ε t 2 .
Integrating out the raw observation gives the released observation kernel
P ~ t M , A L G ( d z ∣ a , h ) : = ∫ W t ( d z ∣ y , a , h ) P t M ( d y ∣ a , h ) . (61) \widetilde{P}_{t}^{M,\mathrm{ALG}}(dz \mid a,h) := \int W_t(dz \mid y,a,h)P_t^M(dy \mid a,h). \tag*{(61)} P t M , ALG ( d z ∣ a , h ) := ∫ W t ( d z ∣ y , a , h ) P t M ( d y ∣ a , h ) . (61)
The released transcript is
H T L D P = ( A 1 , Z 1 , … , A T , Z T ) , (62) H_T^{\mathrm{LDP}} = (A_1,Z_1,\ldots,A_T,Z_T), \tag*{(62)} H T LDP = ( A 1 , Z 1 , … , A T , Z T ) , (62)
and its distribution under ( M , A L G ) (M,\mathrm{ALG}) ( M , ALG ) is denoted by
P L D P M , A L G . (63) \mathbb{P}_{\mathrm{LDP}}^{M,\mathrm{ALG}}. \tag*{(63)} P LDP M , ALG . (63)
Remark VII.2 (ISDM representation under LDP). Equation (61) shows directly how the LDP problem fits the ISDM model. The model still specifies an observation law, the procedure still selects actions from the available history, and the interaction still induces a transcript distribution. The only change is that the learner observes Z t Z_t Z t rather than Y t Y_t Y t .
For a fixed prior μ \mu μ , define the Bayesian CVaR value under LDP by
C α L D P ( μ ) : = inf A L G ∈ D ε L D P CVaR α μ , A L G ( L ) . (64) \mathcal{C}_{\alpha}^{\mathrm{LDP}}(\mu) := \inf_{\mathrm{ALG}\in\mathcal{D}_{\varepsilon}^{\mathrm{LDP}}} \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L). \tag*{(64)} C α LDP ( μ ) := ALG ∈ D ε LDP inf CVaR α μ , ALG ( L ) . (64)
Divergence contraction
The effect of an LDP channel is most naturally stated in terms of the marginal distribution that it induces on the released observation. Let P P P be a distribution on the raw observation space Y \mathcal{Y} Y , and let W W W be a Markov kernel from Y \mathcal{Y} Y to the released observation space Z \mathcal{Z} Z . Define the induced released marginal by
M P W ( C ) : = ∫ Y W ( C ∣ y ) P ( d y ) , C ⊆ Z . (65) M_P^W(C) := \int_{\mathcal{Y}} W(C \mid y)P(dy), \qquad C \subseteq\mathcal{Z}. \tag*{(65)} M P W ( C ) := ∫ Y W ( C ∣ y ) P ( d y ) , C ⊆ Z . (65)
Thus, if
Y ∼ P , Z ∣ Y = y ∼ W ( ⋅ ∣ y ) , (66) Y \sim P, \qquad Z \mid Y=y \sim W(\cdot\mid y), \tag*{(66)} Y ∼ P , Z ∣ Y = y ∼ W ( ⋅ ∣ y ) , (66)
then
Z ∼ M P W . (67) Z \sim M_P^W. \tag*{(67)} Z ∼ M P W . (67)
Similarly, a second raw observation distribution P ′ P' P ′ induces the released marginal
M P ′ W ( C ) : = ∫ Y W ( C ∣ y ) P ′ ( d y ) . (68) M_{P'}^W(C) := \int_{\mathcal{Y}} W(C \mid y)P'(dy). \tag*{(68)} M P ′ W ( C ) := ∫ Y W ( C ∣ y ) P ′ ( d y ) . (68)
For ε ≥ 0 \varepsilon\ge0 ε ≥ 0 , define
κ ( ε ) : = min { 4 , e 2 ε } ( e ε − 1 ) 2 . (69) \kappa(\varepsilon) := \min\{4,e^{2\varepsilon}\}(e^\varepsilon-1)^2. \tag*{(69)} κ ( ε ) := min { 4 , e 2 ε } ( e ε − 1 ) 2 . (69)
A contraction inequality of Duchi, Jordan, and Wainwright [12 ] states that if W W W is ε \varepsilon ε -LDP, then for any two raw observation distributions P P P and P ′ P' P ′ , the corresponding released marginals satisfy
D K L ( M P W ∥ M P ′ W ) + D K L ( M P ′ W ∥ M P W ) ≤ κ ( ε ) d T V ( P , P ′ ) 2 . (70) D_{\mathrm{KL}}\left(M_P^W \mathbin\Vert M_{P'}^W\right)+D_{\mathrm{KL}}\left(M_{P'}^W \mathbin\Vert M_P^W\right)
\le\kappa(\varepsilon)d_{\mathrm{TV}}(P,P')^2. \tag*{(70)} D KL ( M P W ∥ M P ′ W ) + D KL ( M P ′ W ∥ M P W ) ≤ κ ( ε ) d TV ( P , P ′ ) 2 . (70)
The left-hand side is therefore a symmetrized KL divergence between released marginals, while the total variation distance on the right-hand side is computed from the raw observation distributions.
In the sequential setting, for a fixed history h h h and action a a a , define
P ~ t M ( C ∣ a , h ) : = ∫ y W t ( C ∣ y , a , h ) P t M ( d y ∣ a , h ) . (71) \widetilde{P}_t^M(C\mid a,h):=\int_y W_t(C\mid y,a,h)P_t^M(\mathrm{d}y\mid a,h). \tag*{(71)} P t M ( C ∣ a , h ) := ∫ y W t ( C ∣ y , a , h ) P t M ( d y ∣ a , h ) . (71)
This is the conditional marginal distribution of the released observation Z t Z_t Z t under model M M M , given ( A t , H t − 1 ) = ( a , h ) (A_t,H_{t-1})=(a,h) ( A t , H t − 1 ) = ( a , h ) . If W t W_t W t is ε t \varepsilon_t ε t -LDP, then for any two models M M M and M ′ M' M ′ , (70) gives
D K L ( P ~ t M ( ⋅ ∣ a , h ) ∥ P ~ t M ′ ( ⋅ ∣ a , h ) ) + D K L ( P ~ t M ′ ( ⋅ ∣ a , h ) ∥ P ~ t M ( ⋅ ∣ a , h ) ) ≤ κ ( ε t ) d T V ( P t M ( ⋅ ∣ a , h ) , P t M ′ ( ⋅ ∣ a , h ) ) 2 . (72) D_{\mathrm{KL}}\left(\widetilde{P}_t^M(\cdot\mid a,h)\mathbin\Vert\widetilde{P}_t^{M'}(\cdot\mid a,h)\right)
+D_{\mathrm{KL}}\left(\widetilde{P}_t^{M'}(\cdot\mid a,h)\mathbin\Vert\widetilde{P}_t^M(\cdot\mid a,h)\right)
\le\kappa(\varepsilon_t)d_{\mathrm{TV}}\left(P_t^M(\cdot\mid a,h),P_t^{M'}(\cdot\mid a,h)\right)^2. \tag*{(72)} D KL ( P t M ( ⋅ ∣ a , h ) ∥ P t M ′ ( ⋅ ∣ a , h ) ) + D KL ( P t M ′ ( ⋅ ∣ a , h ) ∥ P t M ( ⋅ ∣ a , h ) ) ≤ κ ( ε t ) d TV ( P t M ( ⋅ ∣ a , h ) , P t M ′ ( ⋅ ∣ a , h ) ) 2 . (72)
The one-round contraction inequality controls the divergence between two released observation laws for a fixed history and action. The next proposition extends this control to the full adaptive transcript by summing the conditional divergences over time.
Proposition VII.3 (Adaptive transcript KL under LDP). Fix two models M M M and M ′ M' M ′ and an ε \varepsilon ε -LDP procedure. Let
d t ( h , a ) : = d T V ( P t M ( ⋅ ∣ a , h ) , P t M ′ ( ⋅ ∣ a , h ) ) . (73) d_t(h,a):=d_{\mathrm{TV}}\left(P_t^M(\cdot\mid a,h),P_t^{M'}(\cdot\mid a,h)\right). \tag*{(73)} d t ( h , a ) := d TV ( P t M ( ⋅ ∣ a , h ) , P t M ′ ( ⋅ ∣ a , h ) ) . (73) Then
D K L ( P L D P M , A L G ∥ P L D P M ′ , A L G ) ≤ E P L D P M , A L G [ ∑ t = 1 T κ ( ε t ) d t ( H t − 1 , A t ) 2 ] . (74) D_{\mathrm{KL}}\left(\mathbb{P}_{\mathrm{LDP}}^{M,\mathrm{ALG}}\mathbin\Vert\mathbb{P}_{\mathrm{LDP}}^{M',\mathrm{ALG}}\right)
\le\mathbb{E}_{\mathbb{P}_{\mathrm{LDP}}^{M,\mathrm{ALG}}}\left[\sum_{t=1}^{T}\kappa(\varepsilon_t)d_t(H_{t-1},A_t)^2\right]. \tag*{(74)} D KL ( P LDP M , ALG ∥ P LDP M ′ , ALG ) ≤ E P LDP M , ALG [ t = 1 ∑ T κ ( ε t ) d t ( H t − 1 , A t ) 2 ] . (74)
Remark VII.4 (Role of the contraction coefficient). The function κ ( ε ) \kappa(\varepsilon) κ ( ε ) is the one-round contraction coefficient in (70) . Thus, in the applications, the quantity
∑ t κ ( ε t ) (75) \sum_t \kappa(\varepsilon_t) \tag*{(75)} t ∑ κ ( ε t ) (75)
records the cumulative effect of the privacy channels. When ε t ≤ 1 \varepsilon_t \le1 ε t ≤ 1 , it is at most 16 ∑ t ε t 2 16\sum_t \varepsilon_t^2 16 ∑ t ε t 2 .
Bayesian CVaR Bounds under LDP
This section combines the generalized Fano-CVaR bound with the released transcript divergence control developed in Section VII. The prior, loss, and model separation used in the Gaussian problems remain unchanged; the main difference is that the divergence between transcript laws is now controlled through the LDP channels. We first treat Gaussian mean estimation with heterogeneous privacy parameters, then Gaussian K K K -armed bandits under sequential LDP, and finally give a bounded mean-estimation result for comparison with existing heterogeneous-LDP high-probability bounds.
Gaussian mean estimation under heterogeneous LDP
Consider
X i ∼ i . i . d . N ( θ , σ 2 ) , θ ∈ [ − R , R ] , (76) X_i \mathrel{\overset{\mathrm{i.i.d.}}{\sim}} \mathcal{N}(\theta,\sigma^2), \qquad\theta\in[-R,R], \tag*{(76)} X i ∼ i.i.d. N ( θ , σ 2 ) , θ ∈ [ − R , R ] , (76)
with the prior μ Δ \mu_\Delta μ Δ from (41) . User i i i applies an ε i \varepsilon_i ε i -LDP channel to X i X_i X i . Define
Λ n : = ∑ i = 1 n κ ( ε i ) , κ ( ε ) : = min { 4 , e 2 ε } ( e ε − 1 ) 2 . (77) \Lambda_n := \sum_{i=1}^{n}\kappa(\varepsilon_i), \qquad\kappa(\varepsilon) := \min\{4,e^{2\varepsilon}\}(e^\varepsilon-1)^2. \tag*{(77)} Λ n := i = 1 ∑ n κ ( ε i ) , κ ( ε ) := min { 4 , e 2 ε } ( e ε − 1 ) 2 . (77)
The following theorem gives the fixed-prior Bayesian CVaR lower bound when the i i i th observation is released through an ε i \varepsilon_i ε i -LDP channel. The privacy parameters enter through the cumulative contraction quantity Λ n \Lambda_n Λ n . For ε i ≤ 1 \varepsilon_i \le1 ε i ≤ 1 , the resulting bound depends on the privacy levels through ∑ i = 1 n ε i 2 \sum_{i=1}^n\varepsilon_i^2 ∑ i = 1 n ε i 2 .
Theorem VIII.1 (Gaussian mean estimation under heterogeneous LDP). For every Δ ∈ ( 0 , R ] \Delta\in(0,R] Δ ∈ ( 0 , R ] and every α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
inf θ ^ , W 1 , … , W n W i is ε i -LDP for all i CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ Δ 2 min { 1 2 , 1 16 ( 1 − α ) exp ( − 2 Δ 2 Λ n σ 2 ) } . (78) \inf_{\substack{\hat{\theta},W_1,\ldots,W_n\\ W_i\ \text{is}\ \varepsilon_i\text{-LDP for all }i}} \operatorname{CVaR}^{\mu_\Delta}_{\alpha}\left((\hat{\theta}-\theta)^2\right)
\ge\Delta^2\min\left\{\frac{1}{2},\frac{1}{16(1-\alpha)}\exp\left(-\frac{2\Delta^2\Lambda_n}{\sigma^2}\right)\right\}. \tag*{(78)} θ ^ , W 1 , … , W n W i is ε i -LDP for all i inf CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ Δ 2 min { 2 1 , 16 ( 1 − α ) 1 exp ( − σ 2 2 Δ 2 Λ n ) } . (78)
If ε i ≤ 1 \varepsilon_i \le1 ε i ≤ 1 for all i i i , then
inf θ ^ , W 1 , … , W n W i is ε i -LDP for all i CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ Δ 2 min { 1 2 , 1 16 ( 1 − α ) exp ( − 32 Δ 2 σ 2 ∑ i = 1 n ε i 2 ) } . (79) \inf_{\widehat{\theta},W_1,\ldots,W_n\atop W_i\text{ is }\varepsilon_i\text{-LDP for all }i}
\operatorname{CVaR}_{\alpha}^{\mu_\Delta}\left((\widehat{\theta}-\theta)^2\right)
\ge\Delta^2\min\left\{\frac{1}{2},\frac{1}{16(1-\alpha)}\exp\left(-\frac{32\Delta^2}{\sigma^2}\sum_{i=1}^{n}\varepsilon_i^2\right)\right\}. \tag*{(79)} W i is ε i -LDP for all i θ , W 1 , … , W n inf CVaR α μ Δ ( ( θ − θ ) 2 ) ≥ Δ 2 min { 2 1 , 16 ( 1 − α ) 1 exp ( − σ 2 32 Δ 2 i = 1 ∑ n ε i 2 ) } . (79)
Assume Λ n > 0 \Lambda_n>0 Λ n > 0 . Fix δ : = 1 − α < 1 / 8 \delta:=1-\alpha<1/8 δ := 1 − α < 1/8 . Choosing
Δ 2 : = min { R 2 , σ 2 2 Λ n log 1 8 δ } (80) \Delta^2:=\min\left\{R^2,\frac{\sigma^2}{2\Lambda_n}\log\frac{1}{8\delta}\right\} \tag*{(80)} Δ 2 := min { R 2 , 2 Λ n σ 2 log 8 δ 1 } (80)
gives, for a suitable fixed prior in the family,
inf ALG ∈ D ε L D P CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ 1 2 min { R 2 , σ 2 2 Λ n log 1 8 ( 1 − α ) } . (81) \inf_{\operatorname{ALG}\in\mathcal{D}_{\varepsilon}^{\mathrm{LDP}}}
\operatorname{CVaR}_{\alpha}^{\mu_\Delta}\left((\widehat{\theta}-\theta)^2\right)
\ge\frac{1}{2}\min\left\{R^2,\frac{\sigma^2}{2\Lambda_n}\log\frac{1}{8(1-\alpha)}\right\}. \tag*{(81)} ALG ∈ D ε LDP inf CVaR α μ Δ ( ( θ − θ ) 2 ) ≥ 2 1 min { R 2 , 2 Λ n σ 2 log 8 ( 1 − α ) 1 } . (81)
In particular, when ε i ≤ 1 \varepsilon_i\le1 ε i ≤ 1 ,
\inf_{\operatorname{ALG}\in\mathcal{D}_{\varepsilon}^{\mathrm{LDP}}}
\operatorname{CVaR}_{\alpha}^{\mu_\Delta}\left((\wide{\theta}-\theta)^2\right)
\gtrsim\min\left\{R^2,\frac{\sigma^2\log(1/(1-\alpha))}{\sum_{i=1}^{n}\varepsilon_i^2}\right\}. \tag*{(82)}
If Λ n = 0 \Lambda_n=0 Λ n = 0 , then ε i = 0 \varepsilon_i=0 ε i = 0 for every i i i . In this case, the fixed-prior bound (78) , with Δ = R \Delta=R Δ = R , gives
inf ALG ∈ D ε L D P CVaR α μ R ( ( θ ^ − θ ) 2 ) ≥ R 2 min { 1 2 , 1 16 ( 1 − α ) } . \inf_{\operatorname{ALG}\in\mathcal{D}_{\varepsilon}^{\mathrm{LDP}}}
\operatorname{CVaR}_{\alpha}^{\mu_R}\left((\widehat{\theta}-\theta)^2\right)
\ge R^2\min\left\{\frac{1}{2},\frac{1}{16(1-\alpha)}\right\}. ALG ∈ D ε LDP inf CVaR α μ R ( ( θ − θ ) 2 ) ≥ R 2 min { 2 1 , 16 ( 1 − α ) 1 } .
Remark VIII.2 (Effect of the LDP constraint). Theorem VI.1 uses the same two-point Gaussian family and loss. The only change in the LDP proof is the bound on the transcript divergence. Without an LDP constraint the relevant reverse-KL divergence is of order n Δ 2 / σ 2 n\Delta^2/\sigma^2 n Δ 2 / σ 2 , whereas under heterogeneous LDP it is controlled by Δ 2 Λ n / σ 2 \Delta^2\Lambda_n/\sigma^2 Δ 2 Λ n / σ 2 . For small privacy parameters, Λ n ≤ 16 ∑ i ε i 2 \Lambda_n\le16\sum_i\varepsilon_i^2 Λ n ≤ 16 ∑ i ε i 2 .
Remark VIII.3 (Unbounded Gaussian observations). The Gaussian observations are not assumed to be bounded. The LDP contraction in (70) applies to arbitrary input distributions through their total variation distance. The loss is bounded by the truncation in (42) ; no bounded-support assumption on the Gaussian observation is used. The mean-estimation mechanism is noninteractive across users, as in the heterogeneous-LDP formulation considered for comparison below.
Remark VIII.4 (Comparison with bounded mean estimation). The bounded mean-estimation result at the end of this section uses a different observation model. We include it because it matches the boundedness and heterogeneous-LDP assumptions used by Aliakbarpour et al. [15 ] , allowing a comparison of the dependence on 1 − α 1-\alpha 1 − α and the privacy parameters.
Gaussian K K K -armed bandits under LDP
Consider the Gaussian bandit family { M j g : j ∈ [ K ] } \{M_j^g : j \in[K]\} { M j g : j ∈ [ K ]} from § 6 , with prior μ g K \mu_g^K μ g K . The raw reward distribution of the selected arm is passed through an ε t \varepsilon_t ε t -LDP channel before it is revealed to the learner. Define
Λ T : = ∑ t = 1 T κ ( ε t ) , κ ( ε ) : = min { 4 , e 2 ε } ( e ε − 1 ) 2 . (83) \Lambda_T := \sum_{t=1}^{T} \kappa(\varepsilon_t), \qquad\kappa(\varepsilon) := \min\{4,e^{2\varepsilon}\}(e^\varepsilon-1)^2. \tag*{(83)} Λ T := t = 1 ∑ T κ ( ε t ) , κ ( ε ) := min { 4 , e 2 ε } ( e ε − 1 ) 2 . (83)
We next apply the same argument to the Gaussian bandit family from § 6 . The following theorem lower bounds the Bayesian CVaR of cumulative pseudo-regret when the reward observed at round t t t is released through an ε t \varepsilon_t ε t -LDP channel. The privacy dependence enters through the cumulative contraction quantity Λ T \Lambda_T Λ T .
Theorem VIII.5 (Gaussian K K K -armed bandit under LDP). For every g ∈ ( 0 , 1 ] g \in(0,1] g ∈ ( 0 , 1 ] and every α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) ,
inf A L G ∈ D T , ε L D P CVaR α μ g K ( R T ) ≥ T g min { K − 1 2 K , 1 16 ( 1 − α ) exp ( − g 2 Λ T K σ 2 ) } . (84) \inf_{\mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{T,\varepsilon}} \operatorname{CVaR}^{\mu_g^K}_{\alpha}(R_T) \ge T g \min\left\{\frac{K-1}{2K},\frac{1}{16(1-\alpha)}\exp\left(-\frac{g^2\Lambda_T}{K\sigma^2}\right)\right\}. \tag*{(84)} ALG ∈ D T , ε LDP inf CVaR α μ g K ( R T ) ≥ T g min { 2 K K − 1 , 16 ( 1 − α ) 1 exp ( − K σ 2 g 2 Λ T ) } . (84) If ε t ≤ 1 \varepsilon_t \le1 ε t ≤ 1 for every t t t , then
inf A L G ∈ D T , ε L D P CVaR α μ g K ( R T ) ≥ T g min { K − 1 2 K , 1 16 ( 1 − α ) exp ( − 16 g 2 K σ 2 ∑ t = 1 T ε t 2 ) } . (85) \inf_{\mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{T,\varepsilon}} \operatorname{CVaR}^{\mu_g^K}_{\alpha}(R_T) \ge T g \min\left\{\frac{K-1}{2K},\frac{1}{16(1-\alpha)}\exp\left(-\frac{16g^2}{K\sigma^2}\sum_{t=1}^{T}\varepsilon_t^2\right)\right\}. \tag*{(85)} ALG ∈ D T , ε LDP inf CVaR α μ g K ( R T ) ≥ T g min { 2 K K − 1 , 16 ( 1 − α ) 1 exp ( − K σ 2 16 g 2 t = 1 ∑ T ε t 2 ) } . (85) Assume Λ T > 0 \Lambda_T>0 Λ T > 0 . For δ : = 1 − α < K / [ 8 ( K − 1 ) ] \delta:=1-\alpha<K/[8(K-1)] δ := 1 − α < K / [ 8 ( K − 1 )] , choose
g 2 : = min { 1 , K σ 2 Λ T log K 8 ( K − 1 ) δ } . (86) g^2:=\min\left\{1,\frac{K\sigma^2}{\Lambda_T}\log\frac{K}{8(K-1)\delta}\right\}. \tag*{(86)} g 2 := min { 1 , Λ T K σ 2 log 8 ( K − 1 ) δ K } . (86) Then, for the corresponding fixed prior,
inf A L G ∈ D T , ε L D P CVaR α μ g K ( R T ) ≥ K − 1 2 K T min { 1 , σ K Λ T log K 8 ( K − 1 ) ( 1 − α ) } . (87) \inf_{\mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{T,\varepsilon}} \operatorname{CVaR}^{\mu_g^K}_{\alpha}(R_T)
\ge\frac{K-1}{2K}T\min\left\{1,\frac{\sigma\sqrt{K}}{\sqrt{\Lambda_T}}\sqrt{\log\frac{K}{8(K-1)(1-\alpha)}}\right\}. \tag*{(87)} ALG ∈ D T , ε LDP inf CVaR α μ g K ( R T ) ≥ 2 K K − 1 T min { 1 , Λ T σ K log 8 ( K − 1 ) ( 1 − α ) K } . (87)
For K = 2 K=2 K = 2 and homogeneous 0 < ε t = ε ≤ 1 0<\varepsilon_t=\varepsilon\le1 0 < ε t = ε ≤ 1 ,
inf A L G ∈ D T , ε L D P CVaR α μ g 2 ( R T ) ≳ min { T , σ ε T log 1 1 − α } . (88) \inf_{\mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{T,\varepsilon}} \operatorname{CVaR}^{\mu_g^2}_{\alpha}(R_T)\gtrsim\min\left\{T,\frac{\sigma}{\varepsilon}\sqrt{T\log\frac{1}{1-\alpha}}\right\}. \tag*{(88)} ALG ∈ D T , ε LDP inf CVaR α μ g 2 ( R T ) ≳ min { T , ε σ T log 1 − α 1 } . (88)
More generally, for homogeneous 0 < ε ≤ 1 0<\varepsilon\le1 0 < ε ≤ 1 and fixed K K K ,
inf A L G ∈ D T , ε L D P CVaR α μ g K ( R T ) ≳ min { T , σ ε K T log 1 1 − α } . (89) \inf_{\mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{T,\varepsilon}} \operatorname{CVaR}^{\mu_g^K}_{\alpha}(R_T)\gtrsim\min\left\{T,\frac{\sigma}{\varepsilon}\sqrt{KT\log\frac{1}{1-\alpha}}\right\}. \tag*{(89)} ALG ∈ D T , ε LDP inf CVaR α μ g K ( R T ) ≳ min { T , ε σ K T log 1 − α 1 } . (89)
If Λ T = 0 \Lambda_T=0 Λ T = 0 , then ϵ t = 0 \epsilon_t=0 ϵ t = 0 for every t t t . In this case, the fixed-prior bound (84), with g = 1 g=1 g = 1 , gives
inf A L G ∈ D T , ϵ L D P CVaR α μ K ( R T ) ≥ T min { K − 1 2 K , 1 16 ( 1 − α ) } . \inf_{\mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{T,\epsilon}} \operatorname{CVaR}^{\mu_K}_{\alpha}(R_T) \ge T \min\left\{ \frac{K-1}{2K}, \frac{1}{16(1-\alpha)} \right\}. ALG ∈ D T , ϵ LDP inf CVaR α μ K ( R T ) ≥ T min { 2 K K − 1 , 16 ( 1 − α ) 1 } .
Remark VIII.6 (Effect of the LDP constraint on the bandit bound). Theorem VI.3 and Theorem VIII.5 use the same Gaussian environments, prior, and pseudo-regret. Under LDP, the transcript divergence is bounded after the reward distributions are passed through the LDP channels. This replaces the usual dependence on T T T in the information term by the cumulative privacy quantity Λ T \Lambda_T Λ T . For homogeneous small ϵ \epsilon ϵ , this gives the factor 1 / ϵ 1/\epsilon 1/ ϵ in the resulting lower bound. The rates involving ∑ i ϵ t 2 \sum_i \epsilon_t^2 ∑ i ϵ t 2 or 1 / ϵ 1/\epsilon 1/ ϵ apply only in the small-privacy regime and as ϵ → ∞ \epsilon\to\infty ϵ → ∞ , the LDP contraction bound becomes vacuous, and the results of Section VI apply.
Remark VIII.7 (Adaptive action selection). The factor 1 / K 1/K 1/ K in the divergence budget comes from averaging over the K K K possible optimal arms. At each round the algorithm selects one arm, so only one model in the hard family differs from the null reference on the observed reward distribution. The calculation uses the conditional LDP contraction followed by the adaptive KL chain rule.
Remark VIII.8 (Comparison with LDP expected-regret bounds). The factor σ K T / ϵ \sigma\sqrt{KT}/\epsilon σ K T / ϵ without the CVaR term is consistent with the usual statistical cost of LDP in stochastic bandits. The new feature of the present CVaR statement is the explicit factor log ( 1 / ( 1 − α ) ) \sqrt{\log(1/(1-\alpha))} log ( 1/ ( 1 − α )) .
Bounded mean estimation for comparison with heterogeneous LDP
The next theorem uses a bounded observation model in order to compare directly with the heterogeneous-LDP mean-estimation problem studied by Aliakbarpour et al. [15 ] .
Let X i ∈ [ − 1 , 1 ] X_i \in[-1,1] X i ∈ [ − 1 , 1 ] and consider the two distributions
P + , Δ ( X = 1 ) = 1 + Δ 2 , P + , Δ ( X = − 1 ) = 1 − Δ 2 , (90) P_{+,\Delta}(X=1)=\frac{1+\Delta}{2}, \qquad P_{+,\Delta}(X=-1)=\frac{1-\Delta}{2}, \tag*{(90)} P + , Δ ( X = 1 ) = 2 1 + Δ , P + , Δ ( X = − 1 ) = 2 1 − Δ , (90)
P − , Δ ( X = 1 ) = 1 − Δ 2 , P − , Δ ( X = − 1 ) = 1 + Δ 2 , (91) P_{-,\Delta}(X=1)=\frac{1-\Delta}{2}, \qquad P_{-,\Delta}(X=-1)=\frac{1+\Delta}{2}, \tag*{(91)} P − , Δ ( X = 1 ) = 2 1 − Δ , P − , Δ ( X = − 1 ) = 2 1 + Δ , (91)
whose means are ± Δ \pm\Delta ± Δ . Let
μ Δ b d = 1 2 δ P + , Δ + 1 2 δ P − , Δ . (92) \mu_{\Delta}^{\mathrm{bd}}=\frac{1}{2}\delta_{P_{+,\Delta}}+\frac{1}{2}\delta_{P_{-,\Delta}}. \tag*{(92)} μ Δ bd = 2 1 δ P + , Δ + 2 1 δ P − , Δ . (92)
The following theorem applies the same Bayesian CVaR argument to this bounded two-point model. Its purpose is to make the dependence on α \alpha α and the heterogeneous privacy parameters directly comparable with existing high-probability results for the same observation model.
Theorem VIII.9 (Bounded mean estimation under heterogeneous LDP). Let 0 < ε i ≤ 1 0 < \varepsilon_i \le1 0 < ε i ≤ 1 . For every Δ ∈ ( 0 , 1 ] \Delta\in(0,1] Δ ∈ ( 0 , 1 ] ,
inf θ ^ , W 1 , … , W n W i is ε i -LDP for all i CVaR α μ , b d ( ( θ ^ − θ ) 2 ) ≥ Δ 2 min { 1 2 , 1 16 ( 1 − α ) exp ( − 32 Δ 2 ∑ i = 1 n ε i 2 ) } . (93) \inf_{\substack{\widehat{\theta},W_1,\ldots,W_n\\ W_i\ \text{is}\ \varepsilon_i\text{-LDP for all }i}} \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{bd}}\left((\widehat{\theta}-\theta)^2\right)
\ge\Delta^2 \min\left\{\frac{1}{2},\frac{1}{16(1-\alpha)}\exp\left(-32\Delta^2\sum_{i=1}^{n}\varepsilon_i^2\right)\right\}. \tag*{(93)} θ , W 1 , … , W n W i is ε i -LDP for all i inf CVaR α μ , bd ( ( θ − θ ) 2 ) ≥ Δ 2 min { 2 1 , 16 ( 1 − α ) 1 exp ( − 32 Δ 2 i = 1 ∑ n ε i 2 ) } . (93) For 1 − α < 1 / 8 1-\alpha< 1/8 1 − α < 1/8 , there is a prior in this two-point family for which
inf ALG ∈ D ε L D P CVaR α μ , b d ( ( θ ^ − θ ) 2 ) ≥ 1 2 min { 1 , log 1 8 ( 1 − α ) 32 ∑ i = 1 n ε i 2 } . (94) \inf_{\operatorname{ALG}\in\mathcal{D}_{\varepsilon}^{\mathrm{LDP}}}\operatorname{CVaR}_{\alpha}^{\mu,\mathrm{bd}}\left((\widehat{\theta}-\theta)^2\right)
\ge\frac{1}{2}\min\left\{1,\frac{\log\frac{1}{8(1-\alpha)}}{32\sum_{i=1}^{n}\varepsilon_i^2}\right\}. \tag*{(94)} ALG ∈ D ε LDP inf CVaR α μ , bd ( ( θ − θ ) 2 ) ≥ 2 1 min { 1 , 32 ∑ i = 1 n ε i 2 log 8 ( 1 − α ) 1 } . (94)
Summary of the explicit bounds
Table I summarizes the bounds derived and the bounded mean-estimation comparison. In the table, δ = 1 − α \delta=1-\alpha δ = 1 − α , R R R is the bound on the Gaussian mean parameter in the estimation problems, and σ 2 \sigma^2 σ 2 is the common observation variance. For the LDP rows, ε i \varepsilon_i ε i or ε t \varepsilon_t ε t denotes the corresponding privacy parameter.
Table I. Explicit Bayesian CVaR lower bounds derived in this paper. Each bound is first stated for a fixed prior; the displayed rate is obtained by choosing the separation parameter afterward. Universal numerical constants are suppressed in the rate column.
Relation to Prior Work
This section places the results of the paper relative to the main information-theoretic lower-bound frameworks that are closest to our setting. We distinguish the present fixed-prior Bayesian CVaR criterion from interactive minimax lower bounds, Bayesian expected-risk bounds, minimax quantile bounds, and lower bounds under local differential privacy. We then discuss the literature on private estimation and bandits and clarify how CVaR is used in the bandit setting.
Table II compares the present results with the closest information-theoretic lower-bound frameworks. The two preliminary conference versions of parts of this article are not treated as external prior work; their relationship to this journal article is stated in the Introduction.
Table II. Comparison with related lower-bound results. Fixed-prior Bayesian CVaR refers to a criterion of the form inf A L G CVaR α μ , A L G ( L ) \inf_{\mathrm{ALG}} \operatorname{CVaR}^{\mu,\mathrm{ALG}}_{\alpha}(L) inf ALG CVaR α μ , ALG ( L ) for a specified prior μ \mu μ .
Interactive Fano and DEC
Foster et al. [3 , 4 ] develop the Decision-Estimation Coefficient (DEC) as a general complexity measure for interactive decision making. Chen et al. [5 ] develop interactive versions of Fano, Le Cam, and Assouad methods and connect them to DEC-based lower bounds. Their framework also gives quantile versions of DEC, providing high-probability lower bounds for interactive decision problems.
The generalized Fano inequality used here addresses a different question. For a specified prior and bounded transform of the loss, it gives a Bernoulli f f f -divergence inequality directly for the prior-predictive experiment. The hinge transform gives a fixed-prior Bayesian CVaR lower bound. Thus the distinction is between a broad characterization of interactive minimax complexity and a direct lower bound for a specified Bayesian risk functional.
Esposito, Vandenbroucque, and Gastpar [7 ] develop Bayesian risk lower bounds using a broad class of information measures, including φ \varphi φ -divergences, Rényi information, and Sibson mutual information. They use data processing and variational arguments to obtain estimator-independent lower bounds and discuss the effect of privatization through strong data-processing inequalities.
The present work also uses an information measure to lower bound Bayesian risk, but the setting and risk criterion are different. We allow the transcript distribution to depend on an adaptive decision rule and apply a randomized binary reduction to a bounded transform of the loss. The main risk functional is CVaR, and its level α \alpha α remains explicit in the final bound.
Minimax quantile lower bounds
Ma, Verchand, and Samworth [8 ] develop high-probability variants of Le Cam and Fano lower bounds and introduce minimax quantiles. Chen et al. [5 ] develop quantile DEC within the interactive Fano framework. Bongole et al. [6 ] develop explicit minimax quantile lower bounds for ISDM and study mutual-information privacy.
For a fixed random variable X X X ,
CVaR α ( X ) ≥ VaR α ( X ) . (96) \operatorname{CVaR}_{\alpha}(X) \ge\operatorname{VaR}_{\alpha}(X). \tag*{(96)} CVaR α ( X ) ≥ VaR α ( X ) . (96)
Therefore, if the same probability law and model are being considered, a quantile lower bound can give a CVaR lower bound. The minimax and fixed-prior Bayesian criteria are nevertheless different because
inf A L G sup M ∈ M VaR α M , A L G ( L ) (97) \inf_{\mathrm{ALG}}\sup_{M\in\mathcal{M}} \operatorname{VaR}_{\alpha}^{M,\mathrm{ALG}}(L) \tag*{(97)} ALG inf M ∈ M sup VaR α M , ALG ( L ) (97)
uses the worst model, whereas
inf A L G CVaR α μ , A L G ( L ) (98) \inf_{\mathrm{ALG}} \operatorname{CVaR}^{\mu,\mathrm{ALG}}_{\alpha}(L) \tag*{(98)} ALG inf CVaR α μ , ALG ( L ) (98)
uses the specified prior to form the loss distribution before CVaR is evaluated.
Decision making under LDP
Duchi, Jordan, and Wainwright [12 ] establish the LDP contraction inequality used in the present work. Chen and Rakhlin [14 ] study interactive decision making under LDP using variants of the DEC and include quantile-based private DEC quantities. Thus the compatibility of adaptive decision making with LDP and the corresponding information contractions are already established.
Our use of these results is to control the divergence term in the generalized Bayesian CVaR inequality. This gives explicit lower bounds in the problem parameters and in α \alpha α , rather than a bound left in terms of a DEC quantity.
LDP lower bounds for estimation and bandits
For mean estimation, Aliakbarpour et al. [15 ] study bounded observations under heterogeneous LDP and derive matching high-probability minimax bounds. Joseph et al. [20 ] study Gaussian mean estimation under LDP, where the unbounded data domain creates additional difficulties. The Gaussian LDP mean-estimation theorem in this paper uses a two-point argument and the LDP contraction inequality; it is stated without claiming that the resulting bound is a complete characterization of the unbounded Gaussian problem.
For stochastic bandits, Basu, Dimitrakakis, and Tossou [17 ] , Ren et al. [18 ] , and Tao et al. [21 ] establish regret lower and upper bounds under privacy constraints, including LDP. These results are primarily expectation-based. The present bandit theorem applies CVaR directly to the cumulative pseudo-regret under a fixed prior and displays the additional dependence on the CVaR level.
CVaR in bandit problems
CVaR has been studied as a risk-sensitive objective in bandits and reinforcement learning. Baudry et al. [22 ] study bandit policies based on risk measures of individual arm distributions. Tan and Weng [19 ] study the CVaR of the regret random variable itself and derive algorithm-specific CVaR-regret upper bounds.
The present result concerns the information-theoretic lower bound for the latter type of random variable, with an additional Bayesian prior on the bandit environment. In particular, the CVaR is taken after the model has been drawn from the fixed prior and the adaptive transcript has been generated.
Discussion
This section discusses the interpretation and scope of the preceding results. We first clarify the role of the fixed prior and the choice of f f f -divergence, then explain how LDP changes the information term in the lower bound, and finally discuss the relation between the Gaussian and bounded examples, the connection with DEC-based results, and the main limitations of the present analysis.
Fixed-prior Bayesian CVaR
The basic quantity in this paper is
inf ALG ∈ D CVaR α μ , ALG ( L ) (99) \inf_{\operatorname{ALG}\in\mathcal{D}} \operatorname{CVaR}_{\alpha}^{\mu,\operatorname{ALG}}(L) \tag*{(99)} ALG ∈ D inf CVaR α μ , ALG ( L ) (99)
for a specified prior μ \mu μ . The lower bounds in § 6 and VIII are first stated for fixed priors such as μ Δ \mu_{\Delta} μ Δ or μ g K \mu_{g}^{K} μ g K . Only after these statements are proved do we choose a separation parameter to obtain a rate in n n n , T T T , or α \alpha α .
This distinction is useful when comparing with minimax quantiles. A minimax quantile is unaffected by how much prior probability is assigned to a difficult model. A Bayesian CVaR need not be. For example, if a difficult model has prior mass ρ \rho ρ , its contribution to the upper 1 − α 1-\alpha 1 − α tail can be small when ρ ≪ 1 − α \rho\ll1-\alpha ρ ≪ 1 − α . The prior therefore remains part of the statistical problem throughout the Bayesian calculation.
Choice of divergence
The generalized Fano inequality permits different f f f -divergences. The choice affects the Bernoulli inverse and therefore the dependence on α \alpha α . Hellinger distance gives a convenient explicit inverse. Reverse KL gives an exponential inverse as in (33) , which leads to log ( 1 / ( 1 − α ) ) \log(1/(1-\alpha)) log ( 1/ ( 1 − α )) after the hard-instance separation is chosen.
The divergence choice does not automatically improve the statistical rate of a problem. Its role is to determine whether the lower-bound calculation retains the desired dependence on the tail probability.
Effect of local differential privacy
Under LDP, the model, prior, and loss need not be changed. The raw observation is passed through an LDP channel and the learner acts on the resulting observation. The LDP contraction changes the bound on the transcript divergence.
For Gaussian mean estimation, the reverse-KL budget without privacy constraints is of order
n Δ 2 σ 2 , (100) \frac{n\Delta^{2}}{\sigma^{2}}, \tag*{(100)} σ 2 n Δ 2 , (100)
whereas the heterogeneous-LDP calculation gives a budget of order
Δ 2 σ 2 ∑ i κ ( ε i ) . (101) \frac{\Delta^{2}}{\sigma^{2}}\sum_{i}\kappa(\varepsilon_i). \tag*{(101)} σ 2 Δ 2 i ∑ κ ( ε i ) . (101)
For Gaussian bandits, the same replacement occurs in the adaptive transcript calculation. Thus the statistical model and loss calculation stay the same while the information bound changes.
Gaussian and bounded mean estimation under LDP
The main mean-estimation theorem uses Gaussian observations in order to remain consistent with the Gaussian model used elsewhere in the paper. The observation is unbounded, but the LDP contraction depends on total variation and does not require bounded support.
The bounded mean-estimation theorem is included separately because it gives a direct comparison with the heterogeneous-LDP minimax quantile result of Aliakbarpour et al. [15 ] . In that comparison the statistical model, boundedness assumption, and heterogeneous privacy parameters agree, so the two rates can be compared directly.
Relation between explicit bounds and DEC
DEC-based results and the bounds developed here serve different purposes. DEC provides a broad complexity measure for interactive learning and can be used to characterize large families of problems. The present generalized Fano inequality instead gives a direct expression for a specified Bayesian CVaR. Once the reference excess loss and divergence are evaluated for a concrete problem, the dependence on α \alpha α and the model parameters is explicit.
The LDP bandit result is an example of this distinction. Existing LDP bandit lower bounds establish the cost of privacy for expected regret, while the private DEC framework provides a general high-probability lower-bound formulation. The theorem here evaluates the corresponding information constraint directly in a standard Gaussian bandit and obtains an explicit CVaR lower bound.
Limitations and extensions
The privacy results use pure LDP and the KL contraction in (70). Extending the analysis to approximate LDP or other privacy definitions requires the corresponding divergence inequalities. The present work gives lower bounds and does not establish matching Bayesian CVaR upper bounds.
The fixed priors used for the explicit calculations are finite. The generalized Fano and CVaR inequalities themselves allow arbitrary priors. For nonuniform or continuous priors, useful bounds will require direct control of the prior-weighted excess loss and divergence terms. This may lead to bounds that depend explicitly on prior mass near difficult subsets of the model class.
Conclusion
We developed an information-theoretic lower-bound method for the Bayesian CVaR of losses in interactive statistical decision making. The generalized Fano inequality reduces a bounded function of the loss to a Bernoulli f f f -divergence. A bounded hinge function then gives a direct lower bound on the CVaR under a specified prior.
We used this result to obtain explicit bounds for Gaussian mean estimation and Gaussian stochastic bandits.
We also incorporated local differential privacy at the observation stage of the ISDM model. Established LDP contraction inequalities, combined with the KL chain rule in adaptive problems, give the divergence bounds required by the same generalized Fano inequality. This yields explicit Bayesian CVaR bounds for Gaussian mean estimation under heterogeneous LDP and Gaussian stochastic bandits under LDP.
Several questions remain open. It is natural to study nonuniform and continuous priors, where the lower bound may depend explicitly on how the prior places mass on difficult models. Extensions to other privacy definitions and to other reinforcement learning settings are also possible. A further question is to identify statistical problems for which a direct Bayesian CVaR converse yields a substantially sharper statement than a corresponding quantile lower bound.
Appendix A: Proof of the Generalized Fano Inequality and CVaR Corollary
This appendix proves the two main general results used throughout the paper. We first prove the generalized Fano inequality by reducing the transformed loss to a Bernoulli random variable and applying f f f -divergence data processing. We then specialize the lower side of the resulting inversion to the hinge transform used in the Bayesian CVaR corollary.
Proof of Theorem III.1. Fix a prior μ \mu μ , a procedure ALG, a reference distribution Q Q Q , and a measurable function ϕ : R + → [ 0 , 1 ] \phi: \mathbb{R}_{+} \to[0,1] ϕ : R + → [ 0 , 1 ] . We prove first the Bernoulli divergence inequality and then its two-sided inversion.
Define the model-dependent and reference experiments: Define probability measures P 0 P_0 P 0 and P 1 P_1 P 1 on M × H T \mathcal{M} \times\mathcal{H}_T M × H T by
P 0 ( d M , d h ) : = μ ( d M ) P M , A L G ( d h ) , (102) P_0(dM,dh) := \mu(dM)\mathbb{P}^{M,\mathrm{ALG}}(dh), \tag*{(102)} P 0 ( d M , d h ) := μ ( d M ) P M , ALG ( d h ) , (102)
P 1 ( d M , d h ) : = μ ( d M ) Q ( d h ) . (103) P_1(dM,dh) := \mu(dM)Q(dh). \tag*{(103)} P 1 ( d M , d h ) := μ ( d M ) Q ( d h ) . (103)
Under P 0 P_0 P 0 , the model is drawn from the prior and the transcript is generated according to the model-dependent experiment P M , A L G \mathbb{P}^{M,\mathrm{ALG}} P M , ALG . Under P 1 P_1 P 1 , the model has the same prior μ \mu μ , but the transcript is generated from the reference distribution Q Q Q , independently of M M M .
Introduce the randomized binary statistic: Let
U ∼ Unif [ 0 , 1 ] (104) U \sim\operatorname{Unif}[0,1] \tag*{(104)} U ∼ Unif [ 0 , 1 ] (104)
be independent of ( M , H T ) (M,\mathcal{H}_T) ( M , H T ) under both experiments. To include this auxiliary random variable explicitly, define the product measures
P ‾ 0 : = P 0 ⊗ Unif [ 0 , 1 ] , P ‾ 1 : = P 1 ⊗ Unif [ 0 , 1 ] . (105) \overline{P}_0 := P_0 \otimes\operatorname{Unif}[0,1], \qquad\overline{P}_1 := P_1 \otimes\operatorname{Unif}[0,1]. \tag*{(105)} P 0 := P 0 ⊗ Unif [ 0 , 1 ] , P 1 := P 1 ⊗ Unif [ 0 , 1 ] . (105)
Now define
V : = 1 { U ≤ ϕ ( L ( M , H T ) ) } . (106) V := \mathbf{1}\left\{U \le\phi\left(L(M,\mathcal{H}_T)\right)\right\}. \tag*{(106)} V := 1 { U ≤ ϕ ( L ( M , H T ) ) } . (106)
Since ϕ \phi ϕ takes values in [ 0 , 1 ] [0,1] [ 0 , 1 ] , this construction is well defined.
3) Identify the Bernoulli parameters: Conditioning on ( M , H T ) (M, H_T) ( M , H T ) under P ‾ 0 \overline{P}_0 P 0 gives
P ‾ 0 ( V = 1 ) = E P ‾ 0 [ Pr ( U ≤ ϕ ( L ( M , H T ) ) ∣ M , H T ) ] = E P ‾ 0 [ ϕ ( L ( M , H T ) ) ] = E M ∼ μ E H T ∼ P M , A L G [ ϕ ( L ( M , H T ) ) ] = a ϕ . (107) \begin{aligned}
\overline{P}_0(V = 1) = \mathbb{E}_{\overline{P}_0}\left[\Pr\left(U \le\phi(L(M, H_T)) \mid M, H_T\right)\right] \\
&= \mathbb{E}_{\overline{P}_0}\left[\phi(L(M, H_T))\right] \\
&= \mathbb{E}_{M \sim\mu}\mathbb{E}_{H_T \sim P^{M,\mathrm{ALG}}}\left[\phi(L(M, H_T))\right] \\
&= a_\phi. \tag*{(107)}
\end{aligned} P 0 ( V = 1 ) = E P 0 [ Pr ( U ≤ ϕ ( L ( M , H T )) ∣ M , H T ) ] = E P 0 [ ϕ ( L ( M , H T )) ] = E M ∼ μ E H T ∼ P M , ALG [ ϕ ( L ( M , H T )) ] = a ϕ . (107)
Similarly,
P ‾ 1 ( V = 1 ) = E M ∼ μ E H T ∼ Q [ ϕ ( L ( M , H T ) ) ] = b ϕ , Q . (108) \begin{aligned}
\overline{P}_1(V = 1) = \mathbb{E}_{M \sim\mu}\mathbb{E}_{H_T \sim Q}\left[\phi(L(M, H_T))\right] \\
&= b_{\phi,Q}. \tag*{(108)}
\end{aligned} P 1 ( V = 1 ) = E M ∼ μ E H T ∼ Q [ ϕ ( L ( M , H T )) ] = b ϕ , Q . (108)
Therefore,
Law P ‾ 0 ( V ) = Bern ( a ϕ ) , Law P ‾ 1 ( V ) = Bern ( b ϕ , Q ) . (109) \operatorname{Law}_{\overline{P}_0}(V) = \operatorname{Bern}(a_\phi), \qquad\operatorname{Law}_{\overline{P}_1}(V) = \operatorname{Bern}(b_{\phi,Q}). \tag*{(109)} Law P 0 ( V ) = Bern ( a ϕ ) , Law P 1 ( V ) = Bern ( b ϕ , Q ) . (109)
4) Apply data processing: The mapping
( M , H T , U ) ⟼ V (110) (M, H_T, U) \longmapsto V \tag*{(110)} ( M , H T , U ) ⟼ V (110)
is a measurable Markov kernel from M × H T × [ 0 , 1 ] \mathcal{M} \times\mathcal{H}_T \times[0,1] M × H T × [ 0 , 1 ] to { 0 , 1 } \{0,1\} { 0 , 1 } . Hence the data-processing inequality for f f f -divergences gives
D f ( Bern ( a ϕ ) ∥ Bern ( b ϕ , Q ) ) ≤ D f ( P ‾ 0 ∥ P ‾ 1 ) . (111) D_f\left(\operatorname{Bern}(a_\phi)\mathbin\Vert\operatorname{Bern}(b_{\phi,Q})\right) \le D_f\left(\overline{P}_0\mathbin\Vert\overline{P}_1\right). \tag*{(111)} D f ( Bern ( a ϕ ) ∥ Bern ( b ϕ , Q ) ) ≤ D f ( P 0 ∥ P 1 ) . (111)
Since the same independent uniform distribution is appended to both P 0 P_0 P 0 and P 1 P_1 P 1 , tensoring with this common factor does not change the f f f -divergence. Thus,
D f ( P ‾ 0 ∥ P ‾ 1 ) = D f ( P 0 ∥ P 1 ) . (112) D_f\left(\overline{P}_0\mathbin\Vert\overline{P}_1\right) = D_f\left(P_0\mathbin\Vert P_1\right). \tag*{(112)} D f ( P 0 ∥ P 1 ) = D f ( P 0 ∥ P 1 ) . (112)
5) Evaluate the divergence between the two joint experiments: The model marginal is μ \mu μ under both P 0 P_0 P 0 and P 1 P_1 P 1 . Conditional on M M M , the transcript distributions are P M , A L G P^{M,\mathrm{ALG}} P M , ALG and Q Q Q , respectively. Therefore the f f f -divergence decomposes as
D f ( P 0 ∥ P 1 ) = E M ∼ μ D f ( P M , A L G ∥ Q ) = B f ( A L G , Q ) . (113) \begin{aligned}
D_f(P_0\mathbin\Vert P_1) = \mathbb{E}_{M \sim\mu}D_f\left(P^{M,\mathrm{ALG}}\mathbin\Vert Q\right) \\
&= B_f(\mathrm{ALG}, Q). \tag*{(113)}
\end{aligned} D f ( P 0 ∥ P 1 ) = E M ∼ μ D f ( P M , ALG ∥ Q ) = B f ( ALG , Q ) . (113)
Combining (111), (112), and (113) yields
D f ( Bern ( a ϕ ) ∥ Bern ( b ϕ , Q ) ) ≤ B f ( A L G , Q ) , (114) D_f\left(\operatorname{Bern}(a_\phi)\mathbin\Vert\operatorname{Bern}(b_{\phi,Q})\right) \le B_f(\mathrm{ALG}, Q), \tag*{(114)} D f ( Bern ( a ϕ ) ∥ Bern ( b ϕ , Q ) ) ≤ B f ( ALG , Q ) , (114)
which proves (23).
6) Invert the Bernoulli divergence constraint: Fix
B = B f ( A L G , Q ) , b = b ϕ , Q . (115) B = B_f(\mathrm{ALG}, Q), \qquad b = b_{\phi,Q}. \tag*{(115)} B = B f ( ALG , Q ) , b = b ϕ , Q . (115)
The inequality just proved implies that
a ϕ ∈ { a ∈ [ 0 , 1 ] : D f ( Bern ( a ) ∥ Bern ( b ) ) ≤ B } . (116) a_{\phi} \in\left\{a \in[0,1] : D_f\left(\operatorname{Bern}(a)\mathbin\Vert\operatorname{Bern}(b)\right) \le B\right\}. \tag*{(116)} a ϕ ∈ { a ∈ [ 0 , 1 ] : D f ( Bern ( a ) ∥ Bern ( b ) ) ≤ B } . (116)
By definition,
a f − ( B ; b ) = inf { a ∈ [ 0 , 1 ] : D f ( Bern ( a ) ∥ Bern ( b ) ) ≤ B } , (117) a_f^{-}(B;b) = \inf\left\{a \in[0,1] : D_f\left(\operatorname{Bern}(a)\mathbin\Vert\operatorname{Bern}(b)\right) \le B\right\}, \tag*{(117)} a f − ( B ; b ) = inf { a ∈ [ 0 , 1 ] : D f ( Bern ( a ) ∥ Bern ( b ) ) ≤ B } , (117)
a f + ( B ; b ) = sup { a ∈ [ 0 , 1 ] : D f ( Bern ( a ) ∥ Bern ( b ) ) ≤ B } . (118) a_f^{+}(B;b) = \sup\left\{a \in[0,1] : D_f\left(\operatorname{Bern}(a)\mathbin\Vert\operatorname{Bern}(b)\right) \le B\right\}. \tag*{(118)} a f + ( B ; b ) = sup { a ∈ [ 0 , 1 ] : D f ( Bern ( a ) ∥ Bern ( b ) ) ≤ B } . (118)
Since a ϕ a_{\phi} a ϕ belongs to the feasible set in (116) , it follows immediately that
a f − ( B f ( A L G , Q ) ; b ϕ , Q ) ≤ a ϕ ≤ a f + ( B f ( A L G , Q ) ; b ϕ , Q ) . (119) a_f^{-}\left(B_f(\mathrm{ALG},Q);b_{\phi,Q}\right) \le a_{\phi} \le a_f^{+}\left(B_f(\mathrm{ALG},Q);b_{\phi,Q}\right). \tag*{(119)} a f − ( B f ( ALG , Q ) ; b ϕ , Q ) ≤ a ϕ ≤ a f + ( B f ( ALG , Q ) ; b ϕ , Q ) . (119)
This proves (24).
Proof of Corollary IV.1. Fix a procedure A L G \mathrm{ALG} ALG and a reference distribution Q Q Q . Assume
0 ≤ L ≤ L max . (120) 0 \le L \le L_{\max}. \tag*{(120)} 0 ≤ L ≤ L m a x . (120)
For s ∈ [ 0 , L max ] s \in[0,L_{\max}] s ∈ [ 0 , L m a x ] , apply Theorem III.1 with the hinge transform
ϕ s ( ℓ ) = ( ℓ − s ) + L max . (121) \phi_s(\ell) = \frac{(\ell-s)_{+}}{L_{\max}}. \tag*{(121)} ϕ s ( ℓ ) = L m a x ( ℓ − s ) + . (121)
1) Identify the two Bernoulli parameters: Under the model-dependent Bayesian experiment,
a ϕ s = E M ∼ μ E H T ∼ P M , A L G [ ( L ( M , H T ) − s ) + L max ] = 1 L max E μ , A L G [ ( L − s ) + ] . (122) \begin{aligned}
a_{\phi_s}
&= \mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim\mathbb{P}^{M,\mathrm{ALG}}}\left[\frac{(L(M,H_T)-s)_{+}}{L_{\max}}\right] \\
&= \frac{1}{L_{\max}}\mathbb{E}_{\mu,\mathrm{ALG}}\left[(L-s)_{+}\right]. \tag*{(122)}
\end{aligned} a ϕ s = E M ∼ μ E H T ∼ P M , ALG [ L m a x ( L ( M , H T ) − s ) + ] = L m a x 1 E μ , ALG [ ( L − s ) + ] . (122)
Under the reference experiment,
b ϕ s , Q = 1 L max E M ∼ μ E H T ∼ Q [ ( L ( M , H T ) − s ) + ] = b s ( Q ) . (123) \begin{aligned}
b_{\phi_s,Q}
&= \frac{1}{L_{\max}}\mathbb{E}_{M\sim\mu}\mathbb{E}_{H_T\sim Q}\left[(L(M,H_T)-s)_{+}\right] \\
&= b_s(Q). \tag*{(123)}
\end{aligned} b ϕ s , Q = L m a x 1 E M ∼ μ E H T ∼ Q [ ( L ( M , H T ) − s ) + ] = b s ( Q ) . (123)
2) Use the lower Bernoulli inverse: The two-sided conclusion of Theorem III.1 gives, in particular,
a ϕ s ≥ a f − ( B f ( A L G , Q ) ; b s ( Q ) ) . (124) a_{\phi_s} \ge a_f^{-}\left(B_f(\mathrm{ALG},Q);b_s(Q)\right). \tag*{(124)} a ϕ s ≥ a f − ( B f ( ALG , Q ) ; b s ( Q ) ) . (124)
Substituting (122) yields
E μ , A L G [ ( L − s ) + ] ≥ L max a f − ( B f ( A L G , Q ) ; b s ( Q ) ) . (125) \mathbb{E}_{\mu,\mathrm{ALG}}\left[(L-s)_{+}\right] \ge L_{\max}a_f^{-}\left(B_f(\mathrm{ALG},Q);b_s(Q)\right). \tag*{(125)} E μ , ALG [ ( L − s ) + ] ≥ L m a x a f − ( B f ( ALG , Q ) ; b s ( Q ) ) . (125)
3) Substitute into the CVaR representation: By the Rockafellar–Uryasev representation,
CVaR α μ , A L G ( L ) = inf s ∈ R { s + 1 1 − α E μ , A L G [ ( L − s ) + ] } . (126) \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L)=\inf_{s\in\mathbb{R}}\left\{s+\frac{1}{1-\alpha}\mathbb{E}_{\mu,\mathrm{ALG}}\left[(L-s)_{+}\right]\right\}. \tag*{(126)} CVaR α μ , ALG ( L ) = s ∈ R inf { s + 1 − α 1 E μ , ALG [ ( L − s ) + ] } . (126)
Because 0 ≤ L ≤ L max 0\le L\le L_{\max} 0 ≤ L ≤ L m a x , the infimum in (126) may be restricted to s ∈ [ 0 , L max ] s\in[0,L_{\max}] s ∈ [ 0 , L m a x ] .
Indeed, if s < 0 s<0 s < 0 , then L − s ≥ 0 L-s\ge0 L − s ≥ 0 almost surely, and hence
s + 1 1 − α E μ , A L G [ ( L − s ) + ] = s + E μ , A L G [ L ] − s 1 − α = E μ , A L G [ L ] − α s 1 − α ≥ E μ , A L G [ L ] 1 − α , (127) s+\frac{1}{1-\alpha}\mathbb{E}_{\mu,\mathrm{ALG}}\left[(L-s)_{+}\right]
=s+\frac{\mathbb{E}_{\mu,\mathrm{ALG}}[L]-s}{1-\alpha}
=\frac{\mathbb{E}_{\mu,\mathrm{ALG}}[L]-\alpha s}{1-\alpha}
\ge\frac{\mathbb{E}_{\mu,\mathrm{ALG}}[L]}{1-\alpha}, \tag*{(127)} s + 1 − α 1 E μ , ALG [ ( L − s ) + ] = s + 1 − α E μ , ALG [ L ] − s = 1 − α E μ , ALG [ L ] − α s ≥ 1 − α E μ , ALG [ L ] , (127)
which is the value of the same objective at s = 0 s=0 s = 0 .
If s > L max s>L_{\max} s > L m a x , then ( L − s ) + = 0 (L-s)_{+}=0 ( L − s ) + = 0 almost surely, so the objective is equal to s > L max s>L_{\max} s > L m a x , whereas at s = L max s=L_{\max} s = L m a x it is equal to L max L_{\max} L m a x . Hence no minimizer lies outside [ 0 , L max ] [0,L_{\max}] [ 0 , L m a x ] .
Therefore,
CVaR α μ , A L G ( L ) = inf 0 ≤ s ≤ L max { s + 1 1 − α E μ , A L G [ ( L − s ) + ] } . (128) \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L)
=\inf_{0\le s\le L_{\max}}\left\{s+\frac{1}{1-\alpha}\mathbb{E}_{\mu,\mathrm{ALG}}\left[(L-s)_{+}\right]\right\}. \tag*{(128)} CVaR α μ , ALG ( L ) = 0 ≤ s ≤ L m a x inf { s + 1 − α 1 E μ , ALG [ ( L − s ) + ] } . (128)
Applying (125) for every s ∈ [ 0 , L max ] s\in[0,L_{\max}] s ∈ [ 0 , L m a x ] gives
CVaR α μ , A L G ( L ) ≥ inf 0 ≤ s ≤ L max { s + L max 1 − α a f ( B f ( A L G , Q ) ; b s ( Q ) ) } . (129) \operatorname{CVaR}_{\alpha}^{\mu,\mathrm{ALG}}(L)
\ge\inf_{0\le s\le L_{\max}}\left\{s+\frac{L_{\max}}{1-\alpha}a_f\left(B_f(\mathrm{ALG},Q);b_s(Q)\right)\right\}. \tag*{(129)} CVaR α μ , ALG ( L ) ≥ 0 ≤ s ≤ L m a x inf { s + 1 − α L m a x a f ( B f ( ALG , Q ) ; b s ( Q ) ) } . (129)
This proves the corollary.
Appendix B: Divergence Calculations
This appendix proves the reverse-KL Bernoulli inversion used in the Gaussian and LDP applications.
Proof of Lemma IV.3. For f ( u ) = − log u f(u)=-\log u f ( u ) = − log u ,
D f ( Bern ( a ) ∥ Bern ( b ) ) = D K L ( Bern ( b ) ∥ Bern ( a ) ) . (130) D_f(\operatorname{Bern}(a)\Vert\operatorname{Bern}(b))
=D_{\mathrm{KL}}(\operatorname{Bern}(b)\Vert\operatorname{Bern}(a)). \tag*{(130)} D f ( Bern ( a ) ∥ Bern ( b )) = D KL ( Bern ( b ) ∥ Bern ( a )) . (130)
If the latter is at most B B B , then
B ≥ b log b a + ( 1 − b ) log 1 − b 1 − a (131) B\ge b\log\frac{b}{a}+(1-b)\log\frac{1-b}{1-a} \tag*{(131)} B ≥ b log a b + ( 1 − b ) log 1 − a 1 − b (131)
= − h ( b ) − b log a − ( 1 − b ) log ( 1 − a ) (132) =-h(b)-b\log a-(1-b)\log(1-a) \tag*{(132)} = − h ( b ) − b log a − ( 1 − b ) log ( 1 − a ) (132)
≥ − h ( b ) − b log a . (133) \ge-h(b)-b\log a. \tag*{(133)} ≥ − h ( b ) − b log a . (133)
Thus
− b log a ≤ B + h ( b ) , (134) -b\log a \le B+h(b), \tag*{(134)} − b log a ≤ B + h ( b ) , (134)
which gives (31). If b ≥ β b\ge\beta b ≥ β , then h ( b ) ≤ log 2 h(b)\le\log2 h ( b ) ≤ log 2 and 1 / b ≤ 1 / β 1/b\le1/\beta 1/ b ≤ 1/ β , so
a ≥ exp ( − B + log 2 β ) . (135) a\ge\exp\left(-\frac{B+\log2}{\beta}\right). \tag*{(135)} a ≥ exp ( − β B + log 2 ) . (135)
For β = 1 / 4 \beta=1/4 β = 1/4 , this is (33).
Appendix C: Proofs for the Gaussian Applications
This appendix proves the lower bounds of Section VI. We treat Gaussian mean estimation first and then the Gaussian K K K -armed bandit. In both proofs, the fixed-prior bound is established before the separation parameter is chosen.
Gaussian mean estimation
Proof of Theorem VI.1. Fix n ≥ 1 n\ge1 n ≥ 1 , σ > 0 \sigma>0 σ > 0 , and α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) . We first fix an arbitrary separation
Δ ∈ ( 0 , R ] (136) \Delta\in(0,R] \tag*{(136)} Δ ∈ ( 0 , R ] (136)
and the corresponding prior
μ Δ = 1 2 δ − Δ + 1 2 δ + Δ . (137) \mu_{\Delta}=\frac{1}{2}\delta_{-\Delta}+\frac{1}{2}\delta_{+\Delta}. \tag*{(137)} μ Δ = 2 1 δ − Δ + 2 1 δ + Δ . (137)
We also fix an arbitrary estimator θ ^ = θ ^ ( X n ) \widehat{\theta}=\widehat{\theta}(X^n) θ = θ ( X n ) . The argument below will hold for every estimator.
Define a bounded loss: Define
ℓ Δ ( θ , θ ^ ) : = min { ( θ ^ − θ ) 2 , Δ 2 } . (138) \ell_{\Delta}(\theta,\widehat{\theta}):=\min\left\{(\widehat{\theta}-\theta)^2,\Delta^2\right\}. \tag*{(138)} ℓ Δ ( θ , θ ) := min { ( θ − θ ) 2 , Δ 2 } . (138)
Then
0 ≤ ℓ Δ ≤ Δ 2 . (139) 0\le\ell_{\Delta}\le\Delta^2. \tag*{(139)} 0 ≤ ℓ Δ ≤ Δ 2 . (139)
Thus L max = Δ 2 L_{\max}=\Delta^2 L m a x = Δ 2 . Since ℓ Δ ≤ ( θ ^ − θ ) 2 \ell_{\Delta}\le(\widehat{\theta}-\theta)^2 ℓ Δ ≤ ( θ − θ ) 2 pointwise, monotonicity of CVaR \operatorname{CVaR} CVaR gives
CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ CVaR α μ Δ ( ℓ Δ ) . (140) \operatorname{CVaR}_{\alpha}^{\mu_{\Delta}}\left((\widehat{\theta}-\theta)^2\right)\ge\operatorname{CVaR}_{\alpha}^{\mu_{\Delta}}(\ell_{\Delta}). \tag*{(140)} CVaR α μ Δ ( ( θ − θ ) 2 ) ≥ CVaR α μ Δ ( ℓ Δ ) . (140)
2) Lower bound the reference excess loss: For z ∈ R z \in\mathbb{R} z ∈ R , let
ℓ + ( z ) : = min { ( z − Δ ) 2 , Δ 2 } , ℓ − ( z ) : = min { ( z + Δ ) 2 , Δ 2 } . (141) \ell_{+}(z) := \min\{(z-\Delta)^2,\Delta^2\}, \qquad\ell_{-}(z) := \min\{(z+\Delta)^2,\Delta^2\}. \tag*{(141)} ℓ + ( z ) := min {( z − Δ ) 2 , Δ 2 } , ℓ − ( z ) := min {( z + Δ ) 2 , Δ 2 } . (141)
Since the two parameter values are separated by 2 Δ 2\Delta 2Δ ,
max { ∣ z − Δ ∣ , ∣ z + Δ ∣ } ≥ Δ (142) \max\{|z-\Delta|,|z+\Delta|\} \ge\Delta \tag*{(142)} max { ∣ z − Δ∣ , ∣ z + Δ∣ } ≥ Δ (142)
for every z z z . Hence
max { ℓ + ( z ) , ℓ − ( z ) } = Δ 2 . (143) \max\{\ell_{+}(z),\ell_{-}(z)\} = \Delta^2. \tag*{(143)} max { ℓ + ( z ) , ℓ − ( z )} = Δ 2 . (143)
It follows that, for every s ∈ [ 0 , Δ 2 ] s \in[0,\Delta^2] s ∈ [ 0 , Δ 2 ] ,
( ℓ + ( z ) − s ) + + ( ℓ − ( z ) − s ) + ≥ Δ 2 − s . (144) (\ell_{+}(z)-s)_{+}+(\ell_{-}(z)-s)_{+} \ge\Delta^2-s. \tag*{(144)} ( ℓ + ( z ) − s ) + + ( ℓ − ( z ) − s ) + ≥ Δ 2 − s . (144)
Take the reference distribution to be
Q : = N ( − Δ , σ 2 ) ⊗ n . (145) Q := \mathcal{N}(-\Delta,\sigma^2)^{\otimes n}. \tag*{(145)} Q := N ( − Δ , σ 2 ) ⊗ n . (145)
Then
b s ( Q ) = 1 2 Δ 2 E Q [ ( ℓ + ( θ ^ ) − s ) + + ( ℓ − ( θ ^ ) − s ) + ] ≥ Δ 2 − s 2 Δ 2 = 1 2 ( 1 − s Δ 2 ) . (146) \begin{aligned}
b_s(Q) &= \frac{1}{2\Delta^2}\mathbb{E}_{Q}\left[(\ell_{+}(\hat{\theta})-s)_{+}+(\ell_{-}(\hat{\theta})-s)_{+}\right] \\
&\ge\frac{\Delta^2-s}{2\Delta^2}=\frac{1}{2}\left(1-\frac{s}{\Delta^2}\right). \tag*{(146)}
\end{aligned} b s ( Q ) = 2 Δ 2 1 E Q [ ( ℓ + ( θ ^ ) − s ) + + ( ℓ − ( θ ^ ) − s ) + ] ≥ 2 Δ 2 Δ 2 − s = 2 1 ( 1 − Δ 2 s ) . (146)
Therefore,
0 ≤ s ≤ Δ 2 2 ⟹ b s ( Q ) ≥ 1 4 . (147) 0 \le s \le\frac{\Delta^2}{2}\quad\Longrightarrow\quad b_s(Q) \ge\frac{1}{4}. \tag*{(147)} 0 ≤ s ≤ 2 Δ 2 ⟹ b s ( Q ) ≥ 4 1 . (147)
3) Compute the reverse-KL information budget: Choose
f ( u ) = − log u , (148) f(u)=-\log u, \tag*{(148)} f ( u ) = − log u , (148)
so that
D f ( P ∥ Q ) = D K L ( Q ∥ P ) . (149) D_f(P\|Q)=D_{\mathrm{KL}}(Q\|P). \tag*{(149)} D f ( P ∥ Q ) = D KL ( Q ∥ P ) . (149)
Because Q Q Q is the distribution under − Δ -\Delta − Δ ,
B f = 1 2 D K L ( Q ∥ Q ) + 1 2 D K L ( Q ∥ P + ) = 1 2 D K L ( P − ∥ P + ) , (150) \begin{aligned}
B_f &= \frac{1}{2}D_{\mathrm{KL}}(Q\|Q)+\frac{1}{2}D_{\mathrm{KL}}(Q\|P_{+}) \\
&= \frac{1}{2}D_{\mathrm{KL}}(P_{-}\|P_{+}), \tag*{(150)}
\end{aligned} B f = 2 1 D KL ( Q ∥ Q ) + 2 1 D KL ( Q ∥ P + ) = 2 1 D KL ( P − ∥ P + ) , (150)
where
P − = N ( − Δ , σ 2 ) ⊗ n , P + = N ( + Δ , σ 2 ) ⊗ n . (151) P_{-}=\mathcal{N}(-\Delta,\sigma^2)^{\otimes n}, \qquad P_{+}=\mathcal{N}(+\Delta,\sigma^2)^{\otimes n}. \tag*{(151)} P − = N ( − Δ , σ 2 ) ⊗ n , P + = N ( + Δ , σ 2 ) ⊗ n . (151)
For equal-variance Gaussians,
D K L ( N ( m 0 , σ 2 ) ∥ N ( m 1 , σ 2 ) ) = ( m 0 − m 1 ) 2 2 σ 2 . (152) D_{\mathrm{KL}}\left(\mathcal{N}(m_0,\sigma^2)\Vert\mathcal{N}(m_1,\sigma^2)\right)=\frac{(m_0-m_1)^2}{2\sigma^2}. \tag*{(152)} D KL ( N ( m 0 , σ 2 ) ∥ N ( m 1 , σ 2 ) ) = 2 σ 2 ( m 0 − m 1 ) 2 . (152)
Thus
D K L ( N ( − Δ , σ 2 ) ∥ N ( + Δ , σ 2 ) ) = 2 Δ 2 σ 2 . (153) D_{\mathrm{KL}}\left(\mathcal{N}(-\Delta,\sigma^2)\Vert\mathcal{N}(+\Delta,\sigma^2)\right)=\frac{2\Delta^2}{\sigma^2}. \tag*{(153)} D KL ( N ( − Δ , σ 2 ) ∥ N ( + Δ , σ 2 ) ) = σ 2 2 Δ 2 . (153)
By additivity over the independent observations,
D K L ( P − ∥ P + ) = 2 n Δ 2 σ 2 . (154) D_{\mathrm{KL}}(P_-\Vert P_+)=\frac{2n\Delta^2}{\sigma^2}. \tag*{(154)} D KL ( P − ∥ P + ) = σ 2 2 n Δ 2 . (154)
Hence
B f = n Δ 2 σ 2 . (155) B_f=\frac{n\Delta^2}{\sigma^2}. \tag*{(155)} B f = σ 2 n Δ 2 . (155)
4) Apply the Bernoulli inverse: For s ≤ Δ 2 / 2 s\leq\Delta^2/2 s ≤ Δ 2 /2 , Step 2 gives b s ( Q ) ≥ 1 / 4 b_s(Q)\geq1/4 b s ( Q ) ≥ 1/4 . Lemma IV.3 therefore gives
a f − ( B f ; b s ( Q ) ) ≥ 1 16 e − 4 B f = 1 16 exp ( − 4 n Δ 2 σ 2 ) . (156) a_f^-(B_f;b_s(Q))\geq\frac{1}{16}e^{-4B_f}=\frac{1}{16}\exp\left(-\frac{4n\Delta^2}{\sigma^2}\right). \tag*{(156)} a f − ( B f ; b s ( Q )) ≥ 16 1 e − 4 B f = 16 1 exp ( − σ 2 4 n Δ 2 ) . (156)
5) Apply the CVaR bound: Let δ : = 1 − α \delta:=1-\alpha δ := 1 − α . Corollary IV.1 gives
CVaR α μ Δ ( ℓ Δ ) ≥ inf 0 ≤ s ≤ Δ 2 { s + Δ 2 δ a f − ( B f ; b s ( Q ) ) } . (157) \operatorname{CVaR}_{\alpha}^{\mu_\Delta}(\ell_\Delta)\geq\inf_{0\leq s\leq\Delta^2}\left\{s+\frac{\Delta^2}{\delta}a_f^-(B_f;b_s(Q))\right\}. \tag*{(157)} CVaR α μ Δ ( ℓ Δ ) ≥ 0 ≤ s ≤ Δ 2 inf { s + δ Δ 2 a f − ( B f ; b s ( Q )) } . (157)
If s ≥ Δ 2 / 2 s\geq\Delta^2/2 s ≥ Δ 2 /2 , the expression is at least Δ 2 / 2 \Delta^2/2 Δ 2 /2 . If 0 ≤ s < Δ 2 / 2 0\leq s<\Delta^2/2 0 ≤ s < Δ 2 /2 , Step 4 gives
s + Δ 2 δ a f − ( B f ; b s ( Q ) ) ≥ Δ 2 16 δ exp ( − 4 n Δ 2 σ 2 ) . (158) s+\frac{\Delta^2}{\delta}a_f^-(B_f;b_s(Q))\geq\frac{\Delta^2}{16\delta}\exp\left(-\frac{4n\Delta^2}{\sigma^2}\right). \tag*{(158)} s + δ Δ 2 a f − ( B f ; b s ( Q )) ≥ 16 δ Δ 2 exp ( − σ 2 4 n Δ 2 ) . (158)
Thus every s ∈ [ 0 , Δ 2 ] s\in[0,\Delta^2] s ∈ [ 0 , Δ 2 ] satisfies the same lower bound, and therefore
CVaR α μ Δ ( ℓ Δ ) ≥ Δ 2 min { 1 2 , 1 16 ( 1 − α ) exp ( − 4 n Δ 2 σ 2 ) } . (159) \operatorname{CVaR}_{\alpha}^{\mu_\Delta}(\ell_\Delta)\geq\Delta^2\min\left\{\frac{1}{2},\frac{1}{16(1-\alpha)}\exp\left(-\frac{4n\Delta^2}{\sigma^2}\right)\right\}. \tag*{(159)} CVaR α μ Δ ( ℓ Δ ) ≥ Δ 2 min { 2 1 , 16 ( 1 − α ) 1 exp ( − σ 2 4 n Δ 2 ) } . (159)
Combining this with (140) and then taking the infimum over all estimators proves the fixed-prior bound (44) for the arbitrary Δ ∈ ( 0 , R ] \Delta\in(0,R] Δ ∈ ( 0 , R ] .
6) Choose a hard prior from the family: Assume δ = 1 − α < 1 / 8 \delta=1-\alpha<1/8 δ = 1 − α < 1/8 and set x : = Δ 2 x:=\Delta^2 x := Δ 2 . The fixed-prior bound is
x min { 1 2 , 1 16 δ e − 4 n x / σ 2 } , 0 < x ≤ R 2 . (160) x\min\left\{\frac{1}{2},\frac{1}{16\delta}e^{-4nx/\sigma^2}\right\},\qquad0<x\leq R^2. \tag*{(160)} x min { 2 1 , 16 δ 1 e − 4 n x / σ 2 } , 0 < x ≤ R 2 . (160)
Define
g ( x ) : = 1 16 δ e − 4 n x / σ 2 . (161) g(x):=\frac{1}{16\delta}e^{-4nx/\sigma^2}. \tag*{(161)} g ( x ) := 16 δ 1 e − 4 n x / σ 2 . (161)
Since g g g is decreasing, there is a unique x 0 > 0 x_0 > 0 x 0 > 0 satisfying
g ( x 0 ) = 1 2 . (162) g(x_0) = \frac{1}{2}. \tag*{(162)} g ( x 0 ) = 2 1 . (162)
Solving gives
x 0 = σ 2 4 n log 1 8 δ . (163) x_0 = \frac{\sigma^2}{4n}\log\frac{1}{8\delta}. \tag*{(163)} x 0 = 4 n σ 2 log 8 δ 1 . (163)
Choose
x n , α : = min { R 2 , x 0 } , Δ n , α : = x n , α . (164) x_{n,\alpha} := \min\{R^2,x_0\}, \qquad\Delta_{n,\alpha} := \sqrt{x_{n,\alpha}}. \tag*{(164)} x n , α := min { R 2 , x 0 } , Δ n , α := x n , α . (164)
This is an admissible separation, so the fixed-prior inequality applies to μ Δ n , α \mu_{\Delta_{n,\alpha}} μ Δ n , α .
If R 2 ≤ x 0 R^2 \leq x_0 R 2 ≤ x 0 , then g ( R 2 ) ≥ 1 / 2 g(R^2) \geq1/2 g ( R 2 ) ≥ 1/2 , and the fixed-prior bound at x = R 2 x=R^2 x = R 2 is R 2 / 2 R^2/2 R 2 /2 . If R 2 > x 0 R^2 > x_0 R 2 > x 0 , then x = x 0 x=x_0 x = x 0 and both terms inside the minimum equal 1 / 2 1/2 1/2 , so the bound is x 0 / 2 x_0/2 x 0 /2 . Hence
inf θ ^ CVaR α μ Δ n , α ( ( θ ^ − θ ) 2 ) ≥ 1 2 min { R 2 , σ 2 4 n log 1 8 ( 1 − α ) } . (165) \inf_{\widehat{\theta}}\operatorname{CVaR}^{\mu_{\Delta_{n,\alpha}}}_{\alpha}\left((\widehat{\theta}-\theta)^2\right)
\geq\frac{1}{2}\min\left\{R^2,\frac{\sigma^2}{4n}\log\frac{1}{8(1-\alpha)}\right\}. \tag*{(165)} θ inf CVaR α μ Δ n , α ( ( θ − θ ) 2 ) ≥ 2 1 min { R 2 , 4 n σ 2 log 8 ( 1 − α ) 1 } . (165)
Equivalently,
sup 0 < Δ ≤ R inf θ ^ CVaR α μ Δ ( ( θ ^ − θ ) 2 ) ≥ 1 2 min { R 2 , σ 2 4 n log 1 8 ( 1 − α ) } . (166) \sup_{0<\Delta\leq R}\inf_{\widehat{\theta}}\operatorname{CVaR}^{\mu_{\Delta}}_{\alpha}\left((\widehat{\theta}-\theta)^2\right)
\geq\frac{1}{2}\min\left\{R^2,\frac{\sigma^2}{4n}\log\frac{1}{8(1-\alpha)}\right\}. \tag*{(166)} 0 < Δ ≤ R sup θ inf CVaR α μ Δ ( ( θ − θ ) 2 ) ≥ 2 1 min { R 2 , 4 n σ 2 log 8 ( 1 − α ) 1 } . (166)
This is the stated hard-prior consequence.
K-armed Gaussian bandits
Proof of Theorem VI.3. Fix K ≥ 2 K \geq2 K ≥ 2 , T ≥ 1 T \geq1 T ≥ 1 , σ > 0 \sigma> 0 σ > 0 , α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , and an arbitrary g ∈ ( 0 , 1 ] g \in(0,1] g ∈ ( 0 , 1 ] . Fix the uniform prior
μ g K = 1 K ∑ j = 1 K δ M j g . (167) \mu_g^K = \frac{1}{K}\sum_{j=1}^{K}\delta_{M_j^g}. \tag*{(167)} μ g K = K 1 j = 1 ∑ K δ M j g . (167)
and an arbitrary algorithm A L G ∈ D T \mathrm{ALG} \in\mathcal{D}_T ALG ∈ D T . Let M 0 M_0 M 0 be the null model in which every arm has reward distribution N ( 0 , σ 2 ) \mathcal{N}(0,\sigma^2) N ( 0 , σ 2 ) . Let Q Q Q be the transcript distribution under M 0 M_0 M 0 , and let P j \mathbb{P}_j P j be the transcript distribution under M j g M_j^g M j g .
1 ) 1) 1 ) Define the loss: Under M j g M_j^g M j g ,
R T ( M j g ) = g ( T − N j ( T ) ) , (168) R_T(M_j^g) = g(T-N_j(T)), \tag*{(168)} R T ( M j g ) = g ( T − N j ( T )) , (168)
so
0 ≤ R T ( M j g ) ≤ T g . (169) 0 \leq R_T(M_j^g) \leq Tg. \tag*{(169)} 0 ≤ R T ( M j g ) ≤ T g . (169)
Thus L max = T g L_{\max}=Tg L m a x = T g . 2) Bound the reference excess loss: For every realized action sequence,
∑ j = 1 K N j ( T ) = T . (170) \sum_{j=1}^{K} N_j(T) = T. \tag*{(170)} j = 1 ∑ K N j ( T ) = T . (170)
Hence
1 K ∑ j = 1 K R T ( M j g ) = g K ∑ j = 1 K ( T − N j ( T ) ) = K − 1 K g T . (171) \frac{1}{K}\sum_{j=1}^{K} R_T(M_j^g) = \frac{g}{K}\sum_{j=1}^{K}(T-N_j(T))
= \frac{K-1}{K}gT. \tag*{(171)} K 1 j = 1 ∑ K R T ( M j g ) = K g j = 1 ∑ K ( T − N j ( T )) = K K − 1 g T . (171)
This is a pointwise identity and does not depend on Q Q Q .
For s ∈ [ 0 , T g ] s \in[0,Tg] s ∈ [ 0 , T g ] , convexity of x ↦ ( x − s ) + x \mapsto(x-s)_+ x ↦ ( x − s ) + gives
b s ( Q ) ≥ 1 T g ( K − 1 K g T − s ) + = ( K − 1 K − s T g ) + . (172) b_s(Q) \ge\frac{1}{Tg}\left(\frac{K-1}{K}gT-s\right)_+
= \left(\frac{K-1}{K}-\frac{s}{Tg}\right)_+. \tag*{(172)} b s ( Q ) ≥ T g 1 ( K K − 1 g T − s ) + = ( K K − 1 − T g s ) + . (172)
Therefore,
0 ≤ s ≤ K − 1 2 K T g ⟹ b s ( Q ) ≥ K − 1 2 K ≥ 1 4 . (173) 0 \le s \le\frac{K-1}{2K}Tg \quad\Longrightarrow\quad b_s(Q) \ge\frac{K-1}{2K} \ge\frac{1}{4}. \tag*{(173)} 0 ≤ s ≤ 2 K K − 1 T g ⟹ b s ( Q ) ≥ 2 K K − 1 ≥ 4 1 . (173)
3) Decompose the adaptive transcript KL: Let
H t − 1 : = ( A 1 , Y 1 , … , A t − 1 , Y t − 1 ) . (174) H_{t-1} := (A_1,Y_1,\ldots,A_{t-1},Y_{t-1}). \tag*{(174)} H t − 1 := ( A 1 , Y 1 , … , A t − 1 , Y t − 1 ) . (174)
Conditional on H t − 1 = h H_{t-1}=h H t − 1 = h , the algorithm selects A t A_t A t according to the same kernel under M 0 M_0 M 0 and M j g M_j^g M j g . Thus the action component cancels in the conditional KL. Given the selected arm, the reward distribution is independent of the past. Under M 0 M_0 M 0 ,
P 0 ( ⋅ ∣ a ) = N ( 0 , σ 2 ) , a ∈ [ K ] , (175) P_0(\cdot\mid a) = \mathcal{N}(0,\sigma^2), \qquad a \in[K], \tag*{(175)} P 0 ( ⋅ ∣ a ) = N ( 0 , σ 2 ) , a ∈ [ K ] , (175)
while under M j g M_j^g M j g ,
P j ( ⋅ ∣ a ) = { N ( g , σ 2 ) , a = j , N ( 0 , σ 2 ) , a ≠ j . (176) P_j(\cdot\mid a) =
\begin{cases}
\mathcal{N}(g,\sigma^2), & a=j,\\
\mathcal{N}(0,\sigma^2), & a\ne j.
\end{cases} \tag*{(176)} P j ( ⋅ ∣ a ) = { N ( g , σ 2 ) , N ( 0 , σ 2 ) , a = j , a = j . (176)
The chain rule for KL therefore gives
D K L ( Q ∥ P j ) = ∑ t = 1 T E Q [ D K L ( P 0 ( ⋅ ∣ A t ) ∥ P j ( ⋅ ∣ A t ) ) ] . (177) D_{\mathrm{KL}}(Q\Vert P_j)
= \sum_{t=1}^{T}\mathbb{E}_Q\left[D_{\mathrm{KL}}\left(P_0(\cdot\mid A_t)\Vert P_j(\cdot\mid A_t)\right)\right]. \tag*{(177)} D KL ( Q ∥ P j ) = t = 1 ∑ T E Q [ D KL ( P 0 ( ⋅ ∣ A t ) ∥ P j ( ⋅ ∣ A t ) ) ] . (177)
The conditional KL is zero when A t ≠ j A_t \ne j A t = j . When A t = j A_t=j A t = j ,
D K L ( N ( 0 , σ 2 ) ∥ N ( g , σ 2 ) ) = g 2 2 σ 2 . (178) D_{\mathrm{KL}}\left(\mathcal{N}(0,\sigma^2)\Vert\mathcal{N}(g,\sigma^2)\right)
= \frac{g^2}{2\sigma^2}. \tag*{(178)} D KL ( N ( 0 , σ 2 ) ∥ N ( g , σ 2 ) ) = 2 σ 2 g 2 . (178)
Thus
D K L ( Q ∥ P j ) = g 2 2 σ 2 ∑ t = 1 T E Q [ 1 { A t = j } ] (179) D_{\mathrm{KL}}(Q\Vert\mathbb{P}_j)=\frac{g^2}{2\sigma^2}\sum_{t=1}^{T}\mathbb{E}_Q[\mathbb{1}\{A_t=j\}] \tag*{(179)} D KL ( Q ∥ P j ) = 2 σ 2 g 2 t = 1 ∑ T E Q [ 1 { A t = j }] (179)
= g 2 2 σ 2 E Q [ N j ( T ) ] . (180) =\frac{g^2}{2\sigma^2}\mathbb{E}_Q[N_j(T)]. \tag*{(180)} = 2 σ 2 g 2 E Q [ N j ( T )] . (180)
Averaging over the uniform prior gives
B f : = 1 K ∑ j = 1 K D K L ( Q ∥ P j ) = g 2 2 K σ 2 ∑ j = 1 K E Q [ N j ( T ) ] = g 2 T 2 K σ 2 , (181) \begin{aligned}
B_f:=\frac{1}{K}\sum_{j=1}^{K}D_{\mathrm{KL}}(Q\Vert\mathbb{P}_j) \\
&=\frac{g^2}{2K\sigma^2}\sum_{j=1}^{K}\mathbb{E}_Q[N_j(T)] \\
&=\frac{g^2T}{2K\sigma^2}, \tag*{(181)}
\end{aligned} B f := K 1 j = 1 ∑ K D KL ( Q ∥ P j ) = 2 K σ 2 g 2 j = 1 ∑ K E Q [ N j ( T )] = 2 K σ 2 g 2 T , (181)
where the last equality uses ∑ j N j ( T ) = T \sum_j N_j(T)=T ∑ j N j ( T ) = T pathwise.
4) Bernoulli inverse: For s ≤ ( K − 1 ) T g / ( 2 K ) s\le(K-1)Tg/(2K) s ≤ ( K − 1 ) T g / ( 2 K ) , Lemma IV.3 and b s ( Q ) ≥ 1 / 4 b_s(Q)\ge1/4 b s ( Q ) ≥ 1/4 give
a f − ( B f ; b s ( Q ) ) ≥ 1 16 exp ( − 2 g 2 T K σ 2 ) . (182) a_f^{-}(B_f;b_s(Q))\ge\frac{1}{16}\exp\left(-\frac{2g^2T}{K\sigma^2}\right). \tag*{(182)} a f − ( B f ; b s ( Q )) ≥ 16 1 exp ( − K σ 2 2 g 2 T ) . (182)
5) CVaR bound: Let δ : = 1 − α \delta:=1-\alpha δ := 1 − α . If s ≥ ( K − 1 ) T g / ( 2 K ) s\ge(K-1)Tg/(2K) s ≥ ( K − 1 ) T g / ( 2 K ) , the CVaR objective is at least that threshold. If s < ( K − 1 ) T g / ( 2 K ) s<(K-1)Tg/(2K) s < ( K − 1 ) T g / ( 2 K ) , then
s + T g δ a f − ( B f ; b s ( Q ) ) ≥ T g 16 δ exp ( − 2 g 2 T K σ 2 ) . (183) s+\frac{Tg}{\delta}a_f^{-}(B_f;b_s(Q))\ge\frac{Tg}{16\delta}\exp\left(-\frac{2g^2T}{K\sigma^2}\right). \tag*{(183)} s + δ T g a f − ( B f ; b s ( Q )) ≥ 16 δ T g exp ( − K σ 2 2 g 2 T ) . (183)
Thus
CVaR α μ K g ( R T ) ≥ T g min { K − 1 2 K , 1 16 ( 1 − α ) exp ( − 2 g 2 T K σ 2 ) } . (184) \operatorname{CVaR}_{\alpha}^{\mu_K^g}(R_T)\ge Tg\min\left\{\frac{K-1}{2K},\frac{1}{16(1-\alpha)}\exp\left(-\frac{2g^2T}{K\sigma^2}\right)\right\}. \tag*{(184)} CVaR α μ K g ( R T ) ≥ T g min { 2 K K − 1 , 16 ( 1 − α ) 1 exp ( − K σ 2 2 g 2 T ) } . (184)
Since the algorithm was arbitrary, the fixed-prior inequality follows.
6) Choose a hard prior from the gap family: Set δ : = 1 − α \delta:=1-\alpha δ := 1 − α and
c K : = K − 1 2 K . (185) c_K:=\frac{K-1}{2K}. \tag*{(185)} c K := 2 K K − 1 . (185)
The two terms inside the minimum are equal when
c K = 1 16 δ exp ( − 2 g 2 T K σ 2 ) . (186) c_K=\frac{1}{16\delta}\exp\left(-\frac{2g^2T}{K\sigma^2}\right). \tag*{(186)} c K = 16 δ 1 exp ( − K σ 2 2 g 2 T ) . (186)
Thus
g 0 2 = K σ 2 2 T log K 8 ( K − 1 ) δ . (187) g_0^2=\frac{K\sigma^2}{2T}\log\frac{K}{8(K-1)\delta}. \tag*{(187)} g 0 2 = 2 T K σ 2 log 8 ( K − 1 ) δ K . (187)
When δ < K / [ 8 ( K − 1 ) ] \delta< K/[8(K-1)] δ < K / [ 8 ( K − 1 )] , the logarithm is positive. Choose
g T , α : = min { 1 , g 0 } . (188) g_{T,\alpha} := \min\{1,g_0\}. \tag*{(188)} g T , α := min { 1 , g 0 } . (188)
If g 0 ≤ 1 g_0 \le1 g 0 ≤ 1 , both branches equal c K c_K c K . If g 0 > 1 g_0 > 1 g 0 > 1 , monotonicity of the exponential branch implies that at g = 1 g=1 g = 1 the second branch is at least c K c_K c K . Hence, in either case,
inf A L G ∈ D T CVaR α μ K T , g T , α ( R T ) ≥ c K T min { 1 , σ K 2 T log K 8 ( K − 1 ) ( 1 − α ) } . (189) \inf_{\mathrm{ALG}\in\mathcal{D}_T} \operatorname{CVaR}_{\alpha}^{\mu_K^{T,g_{T,\alpha}}}(R_T) \ge c_K T \min\left\{1,\sigma\sqrt{\frac{K}{2T}}\sqrt{\log\frac{K}{8(K-1)(1-\alpha)}}\right\}. \tag*{(189)} ALG ∈ D T inf CVaR α μ K T , g T , α ( R T ) ≥ c K T min { 1 , σ 2 T K log 8 ( K − 1 ) ( 1 − α ) K } . (189)
For fixed K K K , this is of order
min { T , σ K T log 1 1 − α } . (190) \min\left\{T,\sigma\sqrt{KT\log\frac{1}{1-\alpha}}\right\}. \tag*{(190)} min { T , σ K T log 1 − α 1 } . (190)
Appendix D: Proofs for the LDP Applications
This appendix proves the transcript-divergence result and the LDP applications. We first derive the adaptive KL bound for released transcripts and then apply it to Gaussian mean estimation, Gaussian K K K -armed bandits, and the bounded mean-estimation comparison.
Proof of Proposition VII.3. Fix a horizon T T T , two models M M M and M ′ M' M ′ , and an arbitrary ε \varepsilon ε -LDP procedure ALG. We prove the transcript divergence bound by conditioning on the released history at each round.
Let
H t − 1 L D P : = ( A 1 , Z 1 , … , A t − 1 , Z t − 1 ) (191) H_{t-1}^{\mathrm{LDP}} := (A_1,Z_1,\ldots,A_{t-1},Z_{t-1}) \tag*{(191)} H t − 1 LDP := ( A 1 , Z 1 , … , A t − 1 , Z t − 1 ) (191)
be the released history before round t t t . Conditional on H t − 1 L D P = h H_{t-1}^{\mathrm{LDP}}=h H t − 1 LDP = h , the algorithm selects A t A_t A t according to an action kernel
π t ( d a ∣ h ) . (192) \pi_t(da\mid h). \tag*{(192)} π t ( d a ∣ h ) . (192)
The same kernel is used under M M M and M ′ M' M ′ , because the algorithm is the same in the two experiments.
Given ( A t , H t − 1 L D P ) = ( a , h ) (A_t,H_{t-1}^{\mathrm{LDP}})=(a,h) ( A t , H t − 1 LDP ) = ( a , h ) , model M M M generates the raw observation according to
P t M ( d y ∣ a , h ) , (193) P_t^M(dy\mid a,h), \tag*{(193)} P t M ( d y ∣ a , h ) , (193)
and the LDP channel produces the released observation according to
W t ( d z ∣ y , a , h ) . (194) W_t(dz \mid y,a,h). \tag*{(194)} W t ( d z ∣ y , a , h ) . (194)
Therefore the conditional released marginal is
P ~ t M ( d z ∣ a , h ) = ∫ W t ( d z ∣ y , a , h ) P t M ( d y ∣ a , h ) . (195) \widetilde{P}^{M}_t(dz \mid a,h)=\int W_t(dz \mid y,a,h)P^{M}_t(dy \mid a,h). \tag*{(195)} P t M ( d z ∣ a , h ) = ∫ W t ( d z ∣ y , a , h ) P t M ( d y ∣ a , h ) . (195)
Define P ~ t M ′ \widetilde{P}^{M'}_t P t M ′ analogously.
Conditional on H t − 1 L D P = h H^{\mathrm{LDP}}_{t-1}=h H t − 1 LDP = h , the joint distributions of ( A t , Z t ) (A_t,Z_t) ( A t , Z t ) factor as
P L D P M , A L G ( d a , d z ∣ h ) = π t ( d a ∣ h ) P ~ t M ( d z ∣ a , h ) , (196) \mathbb{P}^{M,\mathrm{ALG}}_{\mathrm{LDP}}(da,dz \mid h)=\pi_t(da \mid h)\widetilde{P}^{M}_t(dz \mid a,h), \tag*{(196)} P LDP M , ALG ( d a , d z ∣ h ) = π t ( d a ∣ h ) P t M ( d z ∣ a , h ) , (196)
P L D P M ′ , A L G ( d a , d z ∣ h ) = π t ( d a ∣ h ) P ~ t M ′ ( d z ∣ a , h ) . (197) \mathbb{P}^{M',\mathrm{ALG}}_{\mathrm{LDP}}(da,dz \mid h)=\pi_t(da \mid h)\widetilde{P}^{M'}_t(dz \mid a,h). \tag*{(197)} P LDP M ′ , ALG ( d a , d z ∣ h ) = π t ( d a ∣ h ) P t M ′ ( d z ∣ a , h ) . (197)
Since the action kernel is identical, it contributes zero to the conditional KL divergence. The KL chain rule therefore gives
D K L ( P L D P M , A L G ∥ P L D P M ′ , A L G ) (198) D_{\mathrm{KL}}\left(\mathbb{P}^{M,\mathrm{ALG}}_{\mathrm{LDP}}\middle\|\mathbb{P}^{M',\mathrm{ALG}}_{\mathrm{LDP}}\right) \tag*{(198)} D KL ( P LDP M , ALG P LDP M ′ , ALG ) (198)
= ∑ t = 1 T E P L D P M , A L G [ D K L ( P ~ t M ( ⋅ ∣ A t , H t − 1 L D P ) ∥ P ~ t M ′ ( ⋅ ∣ A t , H t − 1 L D P ) ) ] . (199) =\sum_{t=1}^{T}\mathbb{E}_{\mathbb{P}^{M,\mathrm{ALG}}_{\mathrm{LDP}}}\left[D_{\mathrm{KL}}\left(\widetilde{P}^{M}_t(\cdot\mid A_t,H^{\mathrm{LDP}}_{t-1})\middle\|\widetilde{P}^{M'}_t(\cdot\mid A_t,H^{\mathrm{LDP}}_{t-1})\right)\right]. \tag*{(199)} = t = 1 ∑ T E P LDP M , ALG [ D KL ( P t M ( ⋅ ∣ A t , H t − 1 LDP ) P t M ′ ( ⋅ ∣ A t , H t − 1 LDP ) ) ] . (199)
For fixed t t t , h h h , and a a a , the one-direction KL is bounded by the symmetrized KL. Hence, by (72) ,
D K L ( P ~ t M ( ⋅ ∣ a , h ) ∥ P ~ t M ′ ( ⋅ ∣ a , h ) ) ≤ κ ( ε t ) d T V 2 ( P t M ( ⋅ ∣ a , h ) , P t M ′ ( ⋅ ∣ a , h ) ) . (200) D_{\mathrm{KL}}\left(\widetilde{P}^{M}_t(\cdot\mid a,h)\middle\|\widetilde{P}^{M'}_t(\cdot\mid a,h)\right)\leq\kappa(\varepsilon_t)d_{\mathrm{TV}}^2\left(P^{M}_t(\cdot\mid a,h),P^{M'}_t(\cdot\mid a,h)\right). \tag*{(200)} D KL ( P t M ( ⋅ ∣ a , h ) P t M ′ ( ⋅ ∣ a , h ) ) ≤ κ ( ε t ) d TV 2 ( P t M ( ⋅ ∣ a , h ) , P t M ′ ( ⋅ ∣ a , h ) ) . (200)
Substituting (200) into (199) proves
D K L ( P L D P M , A L G ∥ P L D P M ′ , A L G ) ≤ E P L D P M , A L G [ ∑ t = 1 T κ ( ε t ) d t ( H t − 1 L D P , A t ) 2 ] . (201) D_{\mathrm{KL}}\left(\mathbb{P}^{M,\mathrm{ALG}}_{\mathrm{LDP}}\middle\|\mathbb{P}^{M',\mathrm{ALG}}_{\mathrm{LDP}}\right)\leq\mathbb{E}_{\mathbb{P}^{M,\mathrm{ALG}}_{\mathrm{LDP}}}\left[\sum_{t=1}^{T}\kappa(\varepsilon_t)d_t\left(H^{\mathrm{LDP}}_{t-1},A_t\right)^2\right]. \tag*{(201)} D KL ( P LDP M , ALG P LDP M ′ , ALG ) ≤ E P LDP M , ALG [ t = 1 ∑ T κ ( ε t ) d t ( H t − 1 LDP , A t ) 2 ] . (201)
which is (74) .
Gaussian mean estimation under heterogeneous LDP
Proof of Theorem VIII.1. Fix n ≥ 1 n\geq1 n ≥ 1 , σ > 0 \sigma>0 σ > 0 , α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , and an arbitrary Δ ∈ ( 0 , R ] \Delta\in(0,R] Δ ∈ ( 0 , R ] . We first prove the fixed-prior statement for
μ Δ = 1 2 δ − Δ + 1 2 δ + Δ . (202) \mu_{\Delta}=\frac{1}{2}\delta_{-\Delta}+\frac{1}{2}\delta_{+\Delta}. \tag*{(202)} μ Δ = 2 1 δ − Δ + 2 1 δ + Δ . (202)
Fix an arbitrary procedure A L G ∈ D ε L D P \mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{\varepsilon} ALG ∈ D ε LDP . The choice of Δ \Delta Δ will be made only after the fixed-prior bound has been established.
Define a bounded loss: Define
ℓ Δ ( θ , θ ^ ) : = min { ( θ ^ − θ ) 2 , Δ 2 } . (203) \ell_{\Delta}(\theta,\widehat{\theta}) := \min\left\{(\widehat{\theta}-\theta)^2,\Delta^2\right\}. \tag*{(203)} ℓ Δ ( θ , θ ) := min { ( θ − θ ) 2 , Δ 2 } . (203)
Then 0 ≤ ℓ Δ ≤ Δ 2 0 \le\ell_{\Delta} \le\Delta^2 0 ≤ ℓ Δ ≤ Δ 2 , so L max = Δ 2 L_{\max} = \Delta^2 L m a x = Δ 2 . Moreover,
ℓ Δ ( θ , θ ^ ) ≤ ( θ ^ − θ ) 2 . (204) \ell_{\Delta}(\theta,\widehat{\theta}) \le(\widehat{\theta}-\theta)^2. \tag*{(204)} ℓ Δ ( θ , θ ) ≤ ( θ − θ ) 2 . (204)
Thus CVaR monotonicity gives
CVaR α μ Δ , A L G ( ( θ ^ − θ ) 2 ) ≥ CVaR α μ Δ , A L G ( ℓ Δ ) . (205) \operatorname{CVaR}_{\alpha}^{\mu_{\Delta,\mathrm{ALG}}}\left((\widehat{\theta}-\theta)^2\right) \ge\operatorname{CVaR}_{\alpha}^{\mu_{\Delta,\mathrm{ALG}}}(\ell_{\Delta}). \tag*{(205)} CVaR α μ Δ , ALG ( ( θ − θ ) 2 ) ≥ CVaR α μ Δ , ALG ( ℓ Δ ) . (205)
Lower bound the reference excess loss: Let Q Q Q be the released transcript distribution when the true parameter is − Δ -\Delta − Δ . For z ∈ R z \in\mathbb{R} z ∈ R , define
ℓ + ( z ) : = min { ( z − Δ ) 2 , Δ 2 } , ℓ − ( z ) : = min { ( z + Δ ) 2 , Δ 2 } . (206) \ell_{+}(z) := \min\left\{(z-\Delta)^2,\Delta^2\right\}, \qquad\ell_{-}(z) := \min\left\{(z+\Delta)^2,\Delta^2\right\}. \tag*{(206)} ℓ + ( z ) := min { ( z − Δ ) 2 , Δ 2 } , ℓ − ( z ) := min { ( z + Δ ) 2 , Δ 2 } . (206)
Because the two parameter values are separated by 2 Δ 2\Delta 2Δ ,
max { ℓ + ( z ) , ℓ − ( z ) } = Δ 2 (207) \max\{\ell_{+}(z),\ell_{-}(z)\} = \Delta^2 \tag*{(207)} max { ℓ + ( z ) , ℓ − ( z )} = Δ 2 (207)
for every z z z . Consequently, for every s ∈ [ 0 , Δ 2 ] s \in[0,\Delta^2] s ∈ [ 0 , Δ 2 ] ,
( ℓ + ( z ) − s ) + + ( ℓ − ( z ) − s ) + ≥ Δ 2 − s . (208) (\ell_{+}(z)-s)_{+}+(\ell_{-}(z)-s)_{+} \ge\Delta^2-s. \tag*{(208)} ( ℓ + ( z ) − s ) + + ( ℓ − ( z ) − s ) + ≥ Δ 2 − s . (208)
The fixed prior is uniform, so
b s ( Q ) = 1 2 Δ 2 E Q [ ( ℓ + ( θ ^ ) − s ) + + ( ℓ − ( θ ^ ) − s ) + ] ≥ Δ 2 − s 2 Δ 2 = 1 2 ( 1 − s Δ 2 ) . (209) b_s(Q) = \frac{1}{2\Delta^2}\mathbb{E}_{Q}\left[(\ell_{+}(\widehat{\theta})-s)_{+}+(\ell_{-}(\widehat{\theta})-s)_{+}\right]
\ge\frac{\Delta^2-s}{2\Delta^2} = \frac{1}{2}\left(1-\frac{s}{\Delta^2}\right). \tag*{(209)} b s ( Q ) = 2 Δ 2 1 E Q [ ( ℓ + ( θ ) − s ) + + ( ℓ − ( θ ) − s ) + ] ≥ 2 Δ 2 Δ 2 − s = 2 1 ( 1 − Δ 2 s ) . (209)
Hence
0 ≤ s ≤ Δ 2 2 ⟹ b s ( Q ) ≥ 1 4 . (210) 0 \le s \le\frac{\Delta^2}{2} \quad\Longrightarrow\quad b_s(Q) \ge\frac{1}{4}. \tag*{(210)} 0 ≤ s ≤ 2 Δ 2 ⟹ b s ( Q ) ≥ 4 1 . (210)
Compute the total variation distance of the raw laws: For every user i i i , the two raw distributions are
P + , Δ = N ( + Δ , σ 2 ) , P − , Δ = N ( − Δ , σ 2 ) . (211) P_{+,\Delta} = \mathcal{N}(+\Delta,\sigma^2), \qquad P_{-,\Delta} = \mathcal{N}(-\Delta,\sigma^2). \tag*{(211)} P + , Δ = N ( + Δ , σ 2 ) , P − , Δ = N ( − Δ , σ 2 ) . (211)
Their KL divergence in either direction is
D K L ( P + , Δ ∥ P − , Δ ) = D K L ( P − , Δ ∥ P + , Δ ) = 2 Δ 2 σ 2 . (212) D_{\mathrm{KL}}(P_{+,\Delta}\|P_{-,\Delta}) = D_{\mathrm{KL}}(P_{-,\Delta}\|P_{+,\Delta}) = \frac{2\Delta^2}{\sigma^2}. \tag*{(212)} D KL ( P + , Δ ∥ P − , Δ ) = D KL ( P − , Δ ∥ P + , Δ ) = σ 2 2 Δ 2 . (212)
Pinsker’s inequality therefore gives
d T V ( P + , Δ , P − , Δ ) 2 ≤ Δ 2 σ 2 . (213) d_{\mathrm{TV}}(P_{+,\Delta},P_{-,\Delta})^2 \le\frac{\Delta^2}{\sigma^2}. \tag*{(213)} d TV ( P + , Δ , P − , Δ ) 2 ≤ σ 2 Δ 2 . (213)
4) Bound the released transcript divergence: Let P ~ + \widetilde{P}_{+} P + and P ~ − \widetilde{P}_{-} P − denote the released transcript laws under + Δ +\Delta + Δ and − Δ -\Delta − Δ , respectively. Since the problem is passive, Proposition VII.3 reduces to the sum of the one-user conditional divergences. By (213) ,
D K L ( P ~ − ∥ P ~ + ) ≤ Δ 2 σ 2 ∑ i = 1 n κ ( ε i ) . (214) D_{\mathrm{KL}}\left(\widetilde{P}_{-}\mathbin\Vert\widetilde{P}_{+}\right) \le\frac{\Delta^{2}}{\sigma^{2}}\sum_{i=1}^{n}\kappa(\varepsilon_i). \tag*{(214)} D KL ( P − ∥ P + ) ≤ σ 2 Δ 2 i = 1 ∑ n κ ( ε i ) . (214)
Define
Λ n : = ∑ i = 1 n κ ( ε i ) . (215) \Lambda_n := \sum_{i=1}^{n}\kappa(\varepsilon_i). \tag*{(215)} Λ n := i = 1 ∑ n κ ( ε i ) . (215)
For reverse KL,
B f = 1 2 D K L ( P ~ − ∥ P ~ − ) + 1 2 D K L ( P ~ − ∥ P ~ + ) = 1 2 D K L ( P ~ − ∥ P ~ + ) . (216) B_f = \frac{1}{2}D_{\mathrm{KL}}\left(\widetilde{P}_{-}\mathbin\Vert\widetilde{P}_{-}\right) + \frac{1}{2}D_{\mathrm{KL}}\left(\widetilde{P}_{-}\mathbin\Vert\widetilde{P}_{+}\right) = \frac{1}{2}D_{\mathrm{KL}}\left(\widetilde{P}_{-}\mathbin\Vert\widetilde{P}_{+}\right). \tag*{(216)} B f = 2 1 D KL ( P − ∥ P − ) + 2 1 D KL ( P − ∥ P + ) = 2 1 D KL ( P − ∥ P + ) . (216)
Thus
B f ≤ Δ 2 Λ n 2 σ 2 . (217) B_f \le\frac{\Delta^{2}\Lambda_n}{2\sigma^{2}}. \tag*{(217)} B f ≤ 2 σ 2 Δ 2 Λ n . (217)
If ε i ≤ 1 \varepsilon_i \le1 ε i ≤ 1 for all i i i , then
Λ n ≤ 16 ∑ i = 1 n ε i 2 , (218) \Lambda_n \le16\sum_{i=1}^{n}\varepsilon_i^{2}, \tag*{(218)} Λ n ≤ 16 i = 1 ∑ n ε i 2 , (218)
so
B f ≤ 8 Δ 2 σ 2 ∑ i = 1 n ε i 2 . (219) B_f \le\frac{8\Delta^{2}}{\sigma^{2}}\sum_{i=1}^{n}\varepsilon_i^{2}. \tag*{(219)} B f ≤ σ 2 8 Δ 2 i = 1 ∑ n ε i 2 . (219)
5) Bound the Bernoulli inverse: For s ≤ Δ 2 / 2 s \le\Delta^{2}/2 s ≤ Δ 2 /2 , (210) gives b s ( Q ) ≥ 1 / 4 b_s(Q) \ge1/4 b s ( Q ) ≥ 1/4 . Hence Lemma IV.3 gives
a f − ( B f ; b s ( Q ) ) ≥ 1 16 e − 4 B f ≥ 1 16 exp ( − 2 Δ 2 Λ n σ 2 ) . (220) \begin{aligned}
a_f^{-}(B_f;b_s(Q)) \ge\frac{1}{16}e^{-4B_f} \\
&\ge\frac{1}{16}\exp\left(-\frac{2\Delta^{2}\Lambda_n}{\sigma^{2}}\right). \tag*{(220)}
\end{aligned} a f − ( B f ; b s ( Q )) ≥ 16 1 e − 4 B f ≥ 16 1 exp ( − σ 2 2 Δ 2 Λ n ) . (220)
6) Obtain the fixed-prior CVaR bound: Let δ : = 1 − α \delta:= 1-\alpha δ := 1 − α . Corollary IV.1 gives
CVaR α μ Δ , A L G ( ℓ Δ ) ≥ inf 0 ≤ s ≤ Δ 2 { s + Δ 2 δ a f − ( B f ; b s ( Q ) ) } . (221) \operatorname{CVaR}_{\alpha}^{\mu_{\Delta},\mathrm{ALG}}(\ell_{\Delta}) \ge\inf_{0\le s\le\Delta^{2}}\left\{s+\frac{\Delta^{2}}{\delta}a_f^{-}(B_f;b_s(Q))\right\}. \tag*{(221)} CVaR α μ Δ , ALG ( ℓ Δ ) ≥ 0 ≤ s ≤ Δ 2 inf { s + δ Δ 2 a f − ( B f ; b s ( Q )) } . (221)
If s ≥ Δ 2 / 2 s \ge\Delta^{2}/2 s ≥ Δ 2 /2 , the expression is at least Δ 2 / 2 \Delta^{2}/2 Δ 2 /2 . If 0 ≤ s < Δ 2 / 2 0 \le s < \Delta^{2}/2 0 ≤ s < Δ 2 /2 , then (220) and s ≥ 0 s \ge0 s ≥ 0 give
s + Δ 2 δ a f − ( B f ; b s ( Q ) ) ≥ Δ 2 16 δ exp ( − 2 Δ 2 Λ n σ 2 ) . (222) s+\frac{\Delta^{2}}{\delta}a_f^{-}(B_f;b_s(Q)) \ge\frac{\Delta^{2}}{16\delta}\exp\left(-\frac{2\Delta^{2}\Lambda_n}{\sigma^{2}}\right). \tag*{(222)} s + δ Δ 2 a f − ( B f ; b s ( Q )) ≥ 16 δ Δ 2 exp ( − σ 2 2 Δ 2 Λ n ) . (222)
Therefore, for every s ∈ [ 0 , Δ 2 ] s \in[0,\Delta^{2}] s ∈ [ 0 , Δ 2 ] ,
s + Δ 2 δ a f − ( B f ; b s ( Q ) ) ≥ Δ 2 min { 1 2 , 1 16 ( 1 − α ) exp ( − 2 Δ 2 Λ n σ 2 ) } . (223) s+\frac{\Delta^{2}}{\delta}a_f^{-}(B_f;b_s(Q)) \ge\Delta^{2}\min\left\{\frac{1}{2},\frac{1}{16(1-\alpha)}\exp\left(-\frac{2\Delta^{2}\Lambda_n}{\sigma^{2}}\right)\right\}. \tag*{(223)} s + δ Δ 2 a f − ( B f ; b s ( Q )) ≥ Δ 2 min { 2 1 , 16 ( 1 − α ) 1 exp ( − σ 2 2 Δ 2 Λ n ) } . (223)
Taking the infimum over s s s , using (205) , and then using the arbitrariness of ALG gives the fixed-prior bound (78) for every Δ ∈ ( 0 , R ] \Delta\in(0,R] Δ ∈ ( 0 , R ] .
7) Choose a hard prior from the family: Assume δ < 1 / 8 \delta< 1/8 δ < 1/8 . The two terms in the minimum are equal when
1 2 = 1 16 δ exp ( − 2 Δ 2 Λ n σ 2 ) . (224) \frac{1}{2} = \frac{1}{16\delta}\exp\left(-\frac{2\Delta^{2}\Lambda_{n}}{\sigma^{2}}\right). \tag*{(224)} 2 1 = 16 δ 1 exp ( − σ 2 2 Δ 2 Λ n ) . (224)
Hence
Δ 0 2 = σ 2 2 Λ n log 1 8 δ . (225) \Delta_{0}^{2} = \frac{\sigma^{2}}{2\Lambda_{n}}\log\frac{1}{8\delta}. \tag*{(225)} Δ 0 2 = 2 Λ n σ 2 log 8 δ 1 . (225)
Choose
Δ n , α 2 : = min { R 2 , Δ 0 2 } . (226) \Delta_{n,\alpha}^{2} := \min\{R^{2},\Delta_{0}^{2}\}. \tag*{(226)} Δ n , α 2 := min { R 2 , Δ 0 2 } . (226)
Because the fixed-prior inequality holds for every admissible Δ \Delta Δ , it applies to this choice. If R 2 ≤ Δ 0 2 R^{2} \le\Delta_{0}^{2} R 2 ≤ Δ 0 2 , the exponential term is at least 1 / 2 1/2 1/2 and the lower bound is R 2 / 2 R^{2}/2 R 2 /2 . If R 2 > Δ 0 2 R^{2} > \Delta_{0}^{2} R 2 > Δ 0 2 , the two terms are equal to 1 / 2 1/2 1/2 and the lower bound is Δ 0 2 / 2 \Delta_{0}^{2}/2 Δ 0 2 /2 . Therefore
inf A L G ∈ D ε L D P CVaR α μ Δ n , α ( ( θ ^ − θ ) 2 ) ≥ 1 2 min { R 2 , σ 2 2 Λ n log 1 8 ( 1 − α ) } . (227) \inf_{\mathrm{ALG}\in\mathcal{D}_{\varepsilon}^{\mathrm{LDP}}}\operatorname{CVaR}_{\alpha}^{\mu_{\Delta_{n,\alpha}}}\left((\widehat{\theta}-\theta)^{2}\right) \ge\frac{1}{2}\min\left\{R^{2},\frac{\sigma^{2}}{2\Lambda_{n}}\log\frac{1}{8(1-\alpha)}\right\}. \tag*{(227)} ALG ∈ D ε LDP inf CVaR α μ Δ n , α ( ( θ − θ ) 2 ) ≥ 2 1 min { R 2 , 2 Λ n σ 2 log 8 ( 1 − α ) 1 } . (227)
Gaussian K K K -armed bandits under LDP
Proof of Theorem VIII.5. Fix K ≥ 2 K \ge2 K ≥ 2 , T ≥ 1 T \ge1 T ≥ 1 , σ > 0 \sigma> 0 σ > 0 , α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , and an arbitrary gap g ∈ ( 0 , 1 ] g \in(0,1] g ∈ ( 0 , 1 ] . Fix the prior
μ g K = 1 K ∑ j = 1 K δ M j g . (228) \mu_{g}^{K} = \frac{1}{K}\sum_{j=1}^{K}\delta_{M_{j}^{g}}. \tag*{(228)} μ g K = K 1 j = 1 ∑ K δ M j g . (228)
and an arbitrary procedure
A L G ∈ D T , ε L D P . (229) \mathrm{ALG} \in\mathcal{D}_{T,\varepsilon}^{\mathrm{LDP}}. \tag*{(229)} ALG ∈ D T , ε LDP . (229)
Let M 0 M_{0} M 0 be the null model in which every arm has reward law N ( 0 , σ 2 ) \mathcal{N}(0,\sigma^{2}) N ( 0 , σ 2 ) . Let Q Q Q denote its released transcript law, and let P j P_{j} P j denote the released transcript law under M j g M_{j}^{g} M j g .
1) Define the loss: Under M j g M_{j}^{g} M j g ,
R T ( M j g ) = g ( T − N j ( T ) ) , (230) R_{T}(M_{j}^{g}) = g(T-N_{j}(T)), \tag*{(230)} R T ( M j g ) = g ( T − N j ( T )) , (230)
so
0 ≤ R T ( M j g ) ≤ T g . (231) 0 \le R_{T}(M_{j}^{g}) \le Tg. \tag*{(231)} 0 ≤ R T ( M j g ) ≤ T g . (231)
Thus L max = T g L_{\max} = Tg L m a x = T g . 2) Lower bound the reference excess loss: For every realized action sequence,
∑ j = 1 K N j ( T ) = T . (232) \sum_{j=1}^{K} N_j(T) = T. \tag*{(232)} j = 1 ∑ K N j ( T ) = T . (232)
Hence
1 K ∑ j = 1 K R T ( M j g ) = K − 1 K g T . (233) \frac{1}{K}\sum_{j=1}^{K} R_T(M_j^g) = \frac{K-1}{K}gT. \tag*{(233)} K 1 j = 1 ∑ K R T ( M j g ) = K K − 1 g T . (233)
This identity is pointwise and therefore does not depend on the reference transcript law Q Q Q .
For s ∈ [ 0 , T g ] s \in[0,Tg] s ∈ [ 0 , T g ] , Jensen’s inequality gives
b s ( Q ) ≥ 1 T g ( K − 1 K g T − s ) + = ( K − 1 K − s T g ) + . (234) b_s(Q) \ge\frac{1}{Tg}\left(\frac{K-1}{K}gT-s\right)_+
= \left(\frac{K-1}{K}-\frac{s}{Tg}\right)_+. \tag*{(234)} b s ( Q ) ≥ T g 1 ( K K − 1 g T − s ) + = ( K K − 1 − T g s ) + . (234)
Therefore
0 ≤ s ≤ K − 1 2 K T g ⟹ b s ( Q ) ≥ K − 1 2 K ≥ 1 4 . (235) 0 \le s \le\frac{K-1}{2K}Tg
\quad\Longrightarrow\quad
b_s(Q) \ge\frac{K-1}{2K} \ge\frac{1}{4}. \tag*{(235)} 0 ≤ s ≤ 2 K K − 1 T g ⟹ b s ( Q ) ≥ 2 K K − 1 ≥ 4 1 . (235)
3) Bound the raw Gaussian total variation distance: Fix an arm j j j . Under M 0 M_0 M 0 and M j g M_j^g M j g , the reward distributions coincide for every arm a ≠ j a \ne j a = j . When a = j a=j a = j , they are
N ( 0 , σ 2 ) and N ( g , σ 2 ) . (236) \mathcal{N}(0,\sigma^2) \qquad\text{and} \qquad\mathcal{N}(g,\sigma^2). \tag*{(236)} N ( 0 , σ 2 ) and N ( g , σ 2 ) . (236)
Pinsker’s inequality and the equal-variance Gaussian KL formula give
d T V 2 ( N ( 0 , σ 2 ) , N ( g , σ 2 ) ) ≤ 1 2 D K L ( N ( 0 , σ 2 ) ∥ N ( g , σ 2 ) ) = g 2 4 σ 2 . (237) d_{\mathrm{TV}}^2\left(\mathcal{N}(0,\sigma^2),\mathcal{N}(g,\sigma^2)\right)
\le\frac{1}{2}D_{\mathrm{KL}}\left(\mathcal{N}(0,\sigma^2)\mathbin{\|}\mathcal{N}(g,\sigma^2)\right)
= \frac{g^2}{4\sigma^2}. \tag*{(237)} d TV 2 ( N ( 0 , σ 2 ) , N ( g , σ 2 ) ) ≤ 2 1 D KL ( N ( 0 , σ 2 ) ∥ N ( g , σ 2 ) ) = 4 σ 2 g 2 . (237)
4) Bound the released transcript divergence: Fix an arm j ∈ [ K ] j \in[K] j ∈ [ K ] and let
H t − 1 L D P : = ( A 1 , Z 1 , … , A t − 1 , Z t − 1 ) . (238) H_{t-1}^{\mathrm{LDP}} := (A_1,Z_1,\ldots,A_{t-1},Z_{t-1}). \tag*{(238)} H t − 1 LDP := ( A 1 , Z 1 , … , A t − 1 , Z t − 1 ) . (238)
The conditional raw reward laws under M 0 M_0 M 0 and M j g M_j^g M j g differ only when A t = j A_t=j A t = j . Therefore Proposition VII.3 and (237) give
D K L ( Q ∥ P j ) ≤ g 2 4 σ 2 E Q [ ∑ t = 1 T κ ( ε t ) 1 { A t = j } ] . (239) D_{\mathrm{KL}}(Q\mathbin{\|}P_j) \le\frac{g^2}{4\sigma^2}\mathbb{E}_Q\left[\sum_{t=1}^{T}\kappa(\varepsilon_t)\mathbb{1}\{A_t=j\}\right]. \tag*{(239)} D KL ( Q ∥ P j ) ≤ 4 σ 2 g 2 E Q [ t = 1 ∑ T κ ( ε t ) 1 { A t = j } ] . (239)
For reverse KL,
B f : = 1 K ∑ j = 1 K D K L ( Q ∥ P j ) ≤ g 2 4 K σ 2 E Q [ ∑ t = 1 T κ ( ε t ) ∑ j = 1 K 1 { A t = j } ] = g 2 4 K σ 2 ∑ t = 1 T κ ( ε t ) . (240) \begin{aligned}
B_f := \frac{1}{K}\sum_{j=1}^{K}D_{\mathrm{KL}}(Q\mathbin\Vert P_j) \\
&\le\frac{g^2}{4K\sigma^2}\mathbb{E}_Q\left[\sum_{t=1}^{T}\kappa(\varepsilon_t)\sum_{j=1}^{K}\mathbb{1}\{A_t=j\}\right] \\
&= \frac{g^2}{4K\sigma^2}\sum_{t=1}^{T}\kappa(\varepsilon_t). \tag*{(240)}
\end{aligned} B f := K 1 j = 1 ∑ K D KL ( Q ∥ P j ) ≤ 4 K σ 2 g 2 E Q [ t = 1 ∑ T κ ( ε t ) j = 1 ∑ K 1 { A t = j } ] = 4 K σ 2 g 2 t = 1 ∑ T κ ( ε t ) . (240)
Define
Λ T : = ∑ t = 1 T κ ( ε t ) . (241) \Lambda_T := \sum_{t=1}^{T}\kappa(\varepsilon_t). \tag*{(241)} Λ T := t = 1 ∑ T κ ( ε t ) . (241)
Then
B f ≤ g 2 Λ T 4 K σ 2 . (242) B_f \le\frac{g^2\Lambda_T}{4K\sigma^2}. \tag*{(242)} B f ≤ 4 K σ 2 g 2 Λ T . (242)
If ε t ≤ 1 \varepsilon_t \le1 ε t ≤ 1 for every t t t , then
Λ T ≤ 16 ∑ t = 1 T ε t 2 , (243) \Lambda_T \le16\sum_{t=1}^{T}\varepsilon_t^2, \tag*{(243)} Λ T ≤ 16 t = 1 ∑ T ε t 2 , (243)
so
B f ≤ 4 g 2 K σ 2 ∑ t = 1 T ε t 2 . (244) B_f \le\frac{4g^2}{K\sigma^2}\sum_{t=1}^{T}\varepsilon_t^2. \tag*{(244)} B f ≤ K σ 2 4 g 2 t = 1 ∑ T ε t 2 . (244)
5) Bound the Bernoulli inverse: For
0 ≤ s ≤ K − 1 2 K T g , (245) 0 \le s \le\frac{K-1}{2K}Tg, \tag*{(245)} 0 ≤ s ≤ 2 K K − 1 T g , (245)
we have b s ( Q ) ≥ 1 / 4 b_s(Q) \ge1/4 b s ( Q ) ≥ 1/4 . Hence Lemma IV.3 gives
a ˉ f ( B f ; b s ( Q ) ) ≥ 1 16 e − 4 B f ≥ 1 16 exp ( − g 2 Λ T K σ 2 ) . (246) \begin{aligned}
\bar{a}_f(B_f;b_s(Q)) \ge\frac{1}{16}e^{-4B_f} \\
&\ge\frac{1}{16}\exp\left(-\frac{g^2\Lambda_T}{K\sigma^2}\right). \tag*{(246)}
\end{aligned} a ˉ f ( B f ; b s ( Q )) ≥ 16 1 e − 4 B f ≥ 16 1 exp ( − K σ 2 g 2 Λ T ) . (246)
6) Obtain the fixed-prior CVaR bound: Set δ : = 1 − α \delta:= 1-\alpha δ := 1 − α . Corollary IV.1 gives
CVaR α μ K g , A L G ( R T ) ≥ inf 0 ≤ s ≤ T g { s + T g δ a ˉ f ( B f ; b s ( Q ) ) } . (247) \operatorname{CVaR}_{\alpha}^{\mu_K^g,\mathrm{ALG}}(R_T) \ge\inf_{0\le s\le Tg}\left\{s+\frac{Tg}{\delta}\bar{a}_f(B_f;b_s(Q))\right\}. \tag*{(247)} CVaR α μ K g , ALG ( R T ) ≥ 0 ≤ s ≤ T g inf { s + δ T g a ˉ f ( B f ; b s ( Q )) } . (247)
If
s ≥ K − 1 2 K T g , (248) s \ge\frac{K-1}{2K}Tg, \tag*{(248)} s ≥ 2 K K − 1 T g , (248)
then the expression is at least ( K − 1 ) T g / ( 2 K ) (K-1)Tg/(2K) ( K − 1 ) T g / ( 2 K ) . If 0 ≤ s < ( K − 1 ) T g / ( 2 K ) 0 \le s < (K-1)Tg/(2K) 0 ≤ s < ( K − 1 ) T g / ( 2 K ) , then (246) gives
s + T g δ a ˉ f ( B f ; b s ( Q ) ) ≥ T g 16 δ exp ( − g 2 Λ T K σ 2 ) . (249) s+\frac{Tg}{\delta}\bar{a}_f(B_f;b_s(Q)) \ge\frac{Tg}{16\delta}\exp\left(-\frac{g^2\Lambda_T}{K\sigma^2}\right). \tag*{(249)} s + δ T g a ˉ f ( B f ; b s ( Q )) ≥ 16 δ T g exp ( − K σ 2 g 2 Λ T ) . (249)
Therefore
CVaR α μ K , g , A L G ( R T ) ≥ T g min { K − 1 2 K , 1 16 ( 1 − α ) exp ( − g 2 Λ T K σ 2 ) } . (250) \operatorname{CVaR}_{\alpha}^{\mu_K,g,\mathrm{ALG}}(R_T) \ge Tg \min\left\{ \frac{K-1}{2K}, \frac{1}{16(1-\alpha)} \exp\left(-\frac{g^2\Lambda_T}{K\sigma^2}\right) \right\}. \tag*{(250)} CVaR α μ K , g , ALG ( R T ) ≥ T g min { 2 K K − 1 , 16 ( 1 − α ) 1 exp ( − K σ 2 g 2 Λ T ) } . (250)
Since A L G \mathrm{ALG} ALG was arbitrary, this proves the fixed-prior bound (84) .
7) Choose a hard prior from the gap family: Let
c K : = K − 1 2 K , δ : = 1 − α . (251) c_K := \frac{K-1}{2K}, \qquad\delta:= 1-\alpha. \tag*{(251)} c K := 2 K K − 1 , δ := 1 − α . (251)
Assume
δ < K 8 ( K − 1 ) . (252) \delta< \frac{K}{8(K-1)}. \tag*{(252)} δ < 8 ( K − 1 ) K . (252)
The two terms in the minimum in (84) are equal when
c K = 1 16 δ exp ( − g 2 Λ T K σ 2 ) . (253) c_K = \frac{1}{16\delta} \exp\left(-\frac{g^2\Lambda_T}{K\sigma^2}\right). \tag*{(253)} c K = 16 δ 1 exp ( − K σ 2 g 2 Λ T ) . (253)
Solving for g 2 g^2 g 2 gives
g 0 2 = K σ 2 Λ T log K 8 ( K − 1 ) δ . (254) g_0^2 = \frac{K\sigma^2}{\Lambda_T} \log\frac{K}{8(K-1)\delta}. \tag*{(254)} g 0 2 = Λ T K σ 2 log 8 ( K − 1 ) δ K . (254)
Choose
g T , α : = min { 1 , g 0 } . (255) g_{T,\alpha} := \min\{1,g_0\}. \tag*{(255)} g T , α := min { 1 , g 0 } . (255)
If g 0 ≤ 1 g_0 \le1 g 0 ≤ 1 , the two branches are equal at g = g 0 g=g_0 g = g 0 . If g 0 > 1 g_0>1 g 0 > 1 , then monotonicity of the exponential branch implies that at g = 1 g=1 g = 1 the second branch is at least c K c_K c K . Hence, in both cases,
inf A L G ∈ D T , ε L D P CVaR α μ g T , α K , A L G ( R T ) ≥ K − 1 2 K T min { 1 , σ K Λ T log K 8 ( K − 1 ) ( 1 − α ) } . (256) \inf_{\mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{T,\varepsilon}} \operatorname{CVaR}_{\alpha}^{\mu_{g_{T,\alpha}}^{K,\mathrm{ALG}}}(R_T)
\ge\frac{K-1}{2K}T \min\left\{1,\frac{\sigma\sqrt{K}}{\sqrt{\Lambda_T}}\sqrt{\log\frac{K}{8(K-1)(1-\alpha)}}\right\}. \tag*{(256)} ALG ∈ D T , ε LDP inf CVaR α μ g T , α K , ALG ( R T ) ≥ 2 K K − 1 T min { 1 , Λ T σ K log 8 ( K − 1 ) ( 1 − α ) K } . (256)
If 0 < ε t = ε ≤ 1 0<\varepsilon_t=\varepsilon\le1 0 < ε t = ε ≤ 1 for every t t t , then Λ T ≤ 16 T ε 2 \Lambda_T\le16T\varepsilon^2 Λ T ≤ 16 T ε 2 and therefore, for fixed K K K ,
inf A L G ∈ D T , ε L D P CVaR α μ g T , α K , A L G ( R T ) ≳ min { T , σ ε K T log 1 1 − α } , (257) \inf_{\mathrm{ALG}\in\mathcal{D}^{\mathrm{LDP}}_{T,\varepsilon}} \operatorname{CVaR}_{\alpha}^{\mu_{g_{T,\alpha}}^{K,\mathrm{ALG}}}(R_T)
\gtrsim\min\left\{T,\frac{\sigma}{\varepsilon}\sqrt{KT\log\frac{1}{1-\alpha}}\right\}, \tag*{(257)} ALG ∈ D T , ε LDP inf CVaR α μ g T , α K , ALG ( R T ) ≳ min { T , ε σ K T log 1 − α 1 } , (257)
up to constants depending only on K K K .
Bounded mean estimation for comparison with heterogeneous LDP
Proof of Theorem VIII.9. Fix n ≥ 1 n \ge1 n ≥ 1 , α ∈ ( 0 , 1 ) \alpha\in(0,1) α ∈ ( 0 , 1 ) , and an arbitrary
Δ ∈ ( 0 , 1 ] . (258) \Delta\in(0,1]. \tag*{(258)} Δ ∈ ( 0 , 1 ] . (258)
Consider the two bounded distributions
P + , Δ ( X = 1 ) = 1 + Δ 2 , P + , Δ ( X = − 1 ) = 1 − Δ 2 , (259) P_{+,\Delta}(X=1)=\frac{1+\Delta}{2}, \qquad P_{+,\Delta}(X=-1)=\frac{1-\Delta}{2}, \tag*{(259)} P + , Δ ( X = 1 ) = 2 1 + Δ , P + , Δ ( X = − 1 ) = 2 1 − Δ , (259)
P − , Δ ( X = 1 ) = 1 − Δ 2 , P − , Δ ( X = − 1 ) = 1 + Δ 2 . (260) P_{-,\Delta}(X=1)=\frac{1-\Delta}{2}, \qquad P_{-,\Delta}(X=-1)=\frac{1+\Delta}{2}. \tag*{(260)} P − , Δ ( X = 1 ) = 2 1 − Δ , P − , Δ ( X = − 1 ) = 2 1 + Δ . (260)
Their means are + Δ +\Delta + Δ and − Δ -\Delta − Δ . Fix the prior
μ Δ b d = 1 2 δ P + , Δ + 1 2 δ P − , Δ . (261) \mu_{\Delta}^{\mathrm{bd}}=\frac{1}{2}\delta_{P_{+,\Delta}}+\frac{1}{2}\delta_{P_{-,\Delta}}. \tag*{(261)} μ Δ bd = 2 1 δ P + , Δ + 2 1 δ P − , Δ . (261)
Fix an arbitrary heterogeneous LDP procedure.
1) Bounded loss and reference excess loss: Use
ℓ Δ = min { ( θ ^ − θ ) 2 , Δ 2 } . (262) \ell_{\Delta}=\min\left\{(\widehat{\theta}-\theta)^2,\Delta^2\right\}. \tag*{(262)} ℓ Δ = min { ( θ − θ ) 2 , Δ 2 } . (262)
Let Q Q Q denote the released transcript distribution under P − , Δ P_{-,\Delta} P − , Δ . The same pointwise separation as in the Gaussian mean-estimation proof gives
b s ( Q ) ≥ 1 2 ( 1 − s Δ 2 ) , (263) b_s(Q)\ge\frac{1}{2}\left(1-\frac{s}{\Delta^2}\right), \tag*{(263)} b s ( Q ) ≥ 2 1 ( 1 − Δ 2 s ) , (263)
so b s ( Q ) ≥ 1 / 4 b_s(Q)\ge1/4 b s ( Q ) ≥ 1/4 for $0\le s\le\Delta^2/2.
2) Compute the raw total variation distance: Since the distributions are supported on { − 1 , + 1 } \{-1,+1\} { − 1 , + 1 } ,
d T V ( P + , Δ , P − , Δ ) = 1 2 ∑ x ∈ { − 1 , + 1 } ∣ P + , Δ ( x ) − P − , Δ ( x ) ∣ = 1 2 ( Δ + Δ ) = Δ . (264) \begin{aligned}
d_{\mathrm{TV}}(P_{+,\Delta},P_{-,\Delta})=\frac{1}{2}\sum_{x\in\{-1,+1\}}\left|P_{+,\Delta}(x)-P_{-,\Delta}(x)\right| \\
&=\frac{1}{2}(\Delta+\Delta)=\Delta. \tag*{(264)}
\end{aligned} d TV ( P + , Δ , P − , Δ ) = 2 1 x ∈ { − 1 , + 1 } ∑ ∣ P + , Δ ( x ) − P − , Δ ( x ) ∣ = 2 1 ( Δ + Δ ) = Δ. (264)
3) Bound the released divergence: For each user i i i , the LDP contraction inequality gives
D K L ( P ~ − , i ∥ P ~ + , i ) ≤ κ ( ε i ) Δ 2 . (265) D_{\mathrm{KL}}(\widetilde{P}_{-,i}\Vert\widetilde{P}_{+,i})\le\kappa(\varepsilon_i)\Delta^2. \tag*{(265)} D KL ( P − , i ∥ P + , i ) ≤ κ ( ε i ) Δ 2 . (265)
Applying the chain rule across the independent users and then using the reverse-KL definition of B f B_f B f gives
B f ≤ Δ 2 2 ∑ i = 1 n κ ( ε i ) . (266) B_f\le\frac{\Delta^2}{2}\sum_{i=1}^{n}\kappa(\varepsilon_i). \tag*{(266)} B f ≤ 2 Δ 2 i = 1 ∑ n κ ( ε i ) . (266)
When ε i ≤ 1 \varepsilon_i\le1 ε i ≤ 1 ,
B f ≤ 8 Δ 2 ∑ i = 1 n ε i 2 . (267) B_f\le8\Delta^2\sum_{i=1}^{n}\varepsilon_i^2. \tag*{(267)} B f ≤ 8 Δ 2 i = 1 ∑ n ε i 2 . (267)
4) Apply the Bernoulli inverse and the CVaR bound: For s ≤ Δ 2 / 2 s \le\Delta^{2}/2 s ≤ Δ 2 /2 , Lemma IV.3 gives
a f − ( B f ; b s ( Q ) ) ≥ 1 16 exp ( − 32 Δ 2 ∑ i = 1 n ε i 2 ) . (268) a_f^{-}(B_f;b_s(Q)) \ge\frac{1}{16}\exp\left(-32\Delta^{2}\sum_{i=1}^{n}\varepsilon_i^{2}\right). \tag*{(268)} a f − ( B f ; b s ( Q )) ≥ 16 1 exp ( − 32 Δ 2 i = 1 ∑ n ε i 2 ) . (268)
The same two-range argument as above therefore gives
inf ALG ∈ D ε L D P CVaR Δ μ b d , A L G ( ( θ ^ − θ ) 2 ) ≥ Δ 2 min { 1 2 , 1 16 ( 1 − α ) exp ( − 32 Δ 2 ∑ i = 1 n ε i 2 ) } . (269) \inf_{\operatorname{ALG}\in\mathcal{D}_{\varepsilon}^{\mathrm{LDP}}} \operatorname{CVaR}_{\Delta}^{\mu^{\mathrm{bd}},\mathrm{ALG}}\left((\widehat{\theta}-\theta)^2\right) \ge\Delta^{2}\min\left\{\frac{1}{2},\frac{1}{16(1-\alpha)}\exp\left(-32\Delta^{2}\sum_{i=1}^{n}\varepsilon_i^{2}\right)\right\}. \tag*{(269)} ALG ∈ D ε LDP inf CVaR Δ μ bd , ALG ( ( θ − θ ) 2 ) ≥ Δ 2 min { 2 1 , 16 ( 1 − α ) 1 exp ( − 32 Δ 2 i = 1 ∑ n ε i 2 ) } . (269)
Finally, choosing
Δ 2 = min { 1 , 1 32 ∑ i = 1 n ε i 2 log 1 8 ( 1 − α ) } (270) \Delta^{2}=\min\left\{1,\frac{1}{32\sum_{i=1}^{n}\varepsilon_i^{2}}\log\frac{1}{8(1-\alpha)}\right\} \tag*{(270)} Δ 2 = min { 1 , 32 ∑ i = 1 n ε i 2 1 log 8 ( 1 − α ) 1 } (270)
for 1 − α < 1 / 8 1-\alpha<1/8 1 − α < 1/8 gives the stated comparison result.