The Privacy Price of Tail-Risk Learning
The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimization El Mustapha Mansouri School of Engineering, Institute of Science Tokyo, Yokohama, Kanagawa 226-8501, Japan
arXiv:2605.16219v1 [cs.LG] 15 May 2026
Abstract Differential privacy changes the effective sample size governing CVaR learning. For tail mass τ , the privacy-relevant sample size is not n, but nτ ; equivalently, the effective private tail sample size is εnτ . Private CVaR excess risk decomposes into ordinary tail-risk statistical error and a privacy price. This decomposition is complete for scalar estimation and finite classes: scalar estimation has rate Θ B min{1, (nτ )−1/2 + (εnτ )−1 } , and finite classes of p size M have rate Θ B min{1, log(2M )/(nτ ) + log(2M )/(εnτ )} . These complete rates hold under pure DP, and their lower bounds extend to approximate DP in the stated small-δ regimes. For convex Lipschitz learning, modular upper and lower reductions show that the CVaR-specific privacy term necessarily scales as 1/(εnτ ), with dimension dependence inherited from private stochastic convex optimization. Together, these results identify ordinary private learning on Θ(nτ ) informative tail records as the canonical hard subproblem inside private CVaR learning. Keywords: differential privacy, conditional value-at-risk, CVaR, tail-risk learning, private machine learning, private CVaR optimization, minimax rates, sample complexity, effective sample size, private stochastic convex optimization, distributionally robust optimization, robust learning, finite classes, convex Lipschitz learning
Asymptotic notation. For nonnegative quantities U and V depending on the problem parameters, U = O(V ) means that U ≤ CV for a universal numerical constant C < ∞ over the stated parameter regime, and U = Ω(V ) means that U ≥ cV for a universal numerical constant c > 0. The notation U = Θ(V ) is used when both bounds hold; U ≍ V has the same meaning. The symbols ≲ and ≳ denote the corresponding one-sided inequalities up e and Ω(·), e to universal constants. Tilde notation, such as O(·) hides only polylogarithmic factors in the dimensionless parameters in force, such as n, d, M, 1/τ, 1/ε, and 1/δ; it never hides additional polynomial dependence on these parameters or any dependence on scale parameters such as B, G, and D.
1 Introduction Empirical risk minimization optimizes average performance. In heterogeneous populations, however, a small average loss can coexist with large loss on rare or poorly represented subpopulations; this phenomenon motivates robust and distributionally robust learning objectives for minority-group performance (Hashimoto et al., 2018). A standard mathematical response is to replace expectation by a tail-risk functional. For a nonnegative loss L and tail mass τ ∈ (0, 1], define ρτ (L) := CVaR1−τ (L) = inf
η∈R
1
1 η + E[(L − η)+ ] . τ
Mansouri
1 √ nτ nτ
1 εnτ
Private Excess CVaR 1 1 √ + εnτ nτ
Figure 1: Error decomposition in private CVaR learning. CVaR concentrates learning on the worst τ -fraction of the sample, leaving only nτ informative tail observa√ tions. Ordinary tail-risk estimation contributes the statistical term 1/ nτ , while differential privacy adds a separate price of order 1/(εnτ ). Thus privacy acts on the effective private tail sample size εnτ , not on the full sample size n.
This is the average loss in the worst τ fraction of the distribution, with the variational formulation due to Rockafellar and Uryasev (2000). The same functional is known as expected shortfall or average value-at-risk, and it is one of the canonical law-invariant coherent risk measures (Artzner et al., 1999; Acerbi and Tasche, 2002; Shapiro, 2013). The central question is what happens when the learner must also satisfy differential privacy. The question is not merely algorithmic. The samples that determine CVaR are precisely the high-loss tail samples. In applications, those records often correspond to rare, atypical, high-impact, or minority cases. Thus the privacy and robustness requirements collide at the same observations. The privacy model is record-level central differential privacy (Dwork et al., 2006; Dwork and Roth, 2014). Given iid data S = (Z1 , . . . , Zn ) from P , a hypothesis class F, and bounded losses ℓ(f ; Z) ∈ [0, B], the population objective is 1 ρτ,P (f ) = inf η + EP [(ℓ(f ; Z) − η)+ ] . τ η∈[0,B] The central quantity is the private minimax excess CVaR risk ε,δ Rn,τ (F) := inf sup E ρτ,P (A(S)) − inf ρτ,P (f ) . f ∈F
A∈(ε,δ)-DP P
The expectation is over both the sample and the learner’s internal randomness. Main message. Private CVaR learning decomposes into ordinary tail-risk statistics and a privacy price. This decomposition is closed completely for scalar estimation and finite classes. In convex Lipschitz learning, the same CVaR-specific privacy price persists through modular reductions to and from private stochastic convex optimization. Thus the results identify the inverse-tail-mass factor 1/τ as the intrinsic privacy price of tail-risk learning: private CVaR excess
=
ordinary CVaR statistical error
+
privacy price.
The new privacy phenomenon is entirely in the second term. The correct private sample size is not n. It is nτ . Equivalently, the privacy price scales as complexity , εnτ 2
The Privacy Price of Tail-Risk Learning
DP protection
n records
private signal scale ∼ εnτ
εnτ ≳ complexity privacydominated
learnable
worst τ tail ≈ nτ informative records
∆CVaR ∼ B/(nτ )
εnτ
Figure 2: The Privacy–Tail-Risk Frontier in Private CVaR Learning. CVaR concentrates the objective on the worst τ -fraction of the loss distribution, so only about nτ records carry tail information. Record-level differential privacy must protect each high-loss tail record, producing sensitivity of order B/(nτ ). Consequently, the privacy-relevant sample size is εnτ , not εn. Nontrivial private tail-risk learning requires this effective private tail sample size to dominate the relevant model complexity.
not as complexity/(εn). This is the privacy price of tail-risk learning. In the CVaR dual representation, the relevant record leverage is exactly 1/τ , which is why the private sample size becomes nτ . Figure 1 summarizes this decomposition. Why the factor 1/τ is unavoidable. The empirical CVaR objective is ( ) n 1 X ρbτ,S (f ) = inf η+ (ℓ(f ; Zi ) − η)+ . nτ η∈[0,B] i=1
Changing one record changes the lifted empirical objective by at most B/(nτ ), and the minimized empirical CVaR by B min{1, 1/(nτ )}. This is exactly the sensitivity to which differential privacy calibrates noise. The lower bounds show that this sensitivity calculation is not merely a proof artifact: for scalar estimation, for finite-class learning, and for convex learning via tail embedding, an inverse-tail-mass privacy penalty is unavoidable. Figure 2 traces how the tail focus, one-record sensitivity, and private tail-sample scale fit together. 1.1 Contributions The main theoretical contributions are as follows. 1. A sharp sensitivity lemma is proved for empirical CVaR and its Rockafellar-Uryasev lifted objective: for bounded losses, minimized empirical CVaR has exact one-record sensitivity B min{1, 1/(nτ )}, while the lifted objective at fixed (f, η) has sensitivity B/(nτ ). 2. The complete scalar minimax rate is established. Estimating ρτ (Z) privately for Z ∈ [0, B] has rate 1 1 Θ B min 1, √ + , εnτ nτ 3
Mansouri
under pure differential privacy, with the lower bound extending to approximate differential privacy whenever δ is small enough for group privacy to be informative. 3. The complete finite-class minimax rate is established under pure DP and under approximate DP in the stated p small-δ regime. For |F| = M , ordinary CVaR uniform convergence contributes B log(2M )/(nτ ), while privacy contributes B log(2M )/(εnτ ). Together they yield ( r Θ B min 1,
log(2M ) log(2M ) + nτ εnτ
)! ,
exhibiting the effective sample size nτ and the effective private sample size εnτ side by side. 4. A modular approximate-DP convex upper bound is proved using a rescaled lifted convex problem and the standard Euclidean private-SCO population-risk interface. For G-Lipschitz convex losses over a Euclidean set of diameter D, the private term is e O
! p (GD + B) d log(1/δ) . εnτ
5. A tail-sample transfer theorem identifies the canonical hard subproblem inside CVaR learning: ordinary expected-risk learning with m samples is embedded exactly inside CVaR learning with n samples and m ≍ nτ informative tail observations. Combining this embedding with the Euclidean approximate-DP SCO lower interface yields dimensiondependent CVaR lower bounds, up to imported SCO logarithmic factors, of order √ )! 1 e min{B, GD} min 1, √ + d Ω εnτ nτ (
for a natural bounded convex Lipschitz CVaR subclass. The resulting phase transition is simple: nontrivial private tail-risk learning requires εnτ ≫ model complexity. In Euclidean convex learning this complexity is of order
√
d, up to logarithmic factors.
Pure and approximate DP. The minimax equalities are stated for pure DP. For approximate DP, the same lower-bound mechanisms extend in the small-δ regimes where group privacy remains informative; these regimes are stated explicitly rather than hidden in asymptotic notation. The convex Lipschitz results are modular transfer results in the standard approximate-DP Euclidean SCO regime; the scalar and finite-class minimax equalities are the complete pure-DP characterizations. 4
The Privacy Price of Tail-Risk Learning
Table 1: Summary of the main guarantees. The scalar, finite-class, and convex rows give theorem-level minimax evidence for the 1/τ privacy frontier. The finite-class row is the closed model where the ordinary statistical term and the privacy price are both characterized. The coherent-envelope row records only the general sensitivity mechanism; the minimax theory is proved for CVaR. Setting
Main guarantee
Takeaway
Scalar CVaR estimation
Complete rate under pure DP; approximate-DP lower √ bound under small δ: Θ(B min{1, 1/ nτ + 1/(εnτ )}).
Closed scalar decomposition.
Finite class, |F | = M
Complete rate underp pure DP; approximate DP under small δ: Θ(B min{1, log(2M )/(nτ ) + log(2M )/(εnτ )}).
Ordinary tail sample size nτ plus private tail sample size εnτ .
Convex Lipschitz learning
√ e Upper privacy term: O((GD + B) d/(εnτ √ )). Tail √ e 0 min{1, 1/ nτ + d/(εnτ )}). embedding gives Ω(R
Envelope-bounded coherent risks
Privacy dependence sharp in (ε, n, τ, d); scale-sharp under B ≍ GD.
One-record empirical sensitivity is at most B min{1, κ/n}. Sensitivity extension No general coherent-risk minimax theorem is claimed. only; CVaR is the resolved case κ = 1/τ .
1.2 Related work CVaR and coherent risk. Coherent risk measures were axiomatized by Artzner et al. (1999). The variational representation used throughout the analysis is due to Rockafellar and Uryasev (2000), who also developed CVaR for general loss distributions (Rockafellar and Uryasev, 2002). Expected shortfall/CVaR is coherent under the standard definitions studied by Acerbi and Tasche (2002). Kusuoka-type representations show that law-invariant coherent risk measures can be represented using average value-at-risk functionals (Shapiro, 2013). Ruszczyński and Shapiro (2006) developed optimization theory for convex risk functions. CVaR and robust learning. CVaR-style and DRO-style losses have been used to improve worst-tail or worst-subpopulation performance. CVaR-based statistical learning formulations go back at least to Takeda and Kanamori (2009). Hashimoto et al. (2018) use distributionally robust objectives to mitigate minority-group underperformance without explicit demographic labels. Duchi et al. (2023) propose robust losses for latent covariate mixtures and explicitly motivate the method by failures of average-loss minimization on heterogeneous subpopulations. PAC-Bayesian and statistical learning analyses of CVaR have also appeared (Mhammedi et al., 2020). A recent preprint develops sharp nonprivate generalization and robustness results for CVaR-ERM under heavy-tailed and contaminated data (Mulumudi et al., 2026). These works do not characterize the differential privacy price of CVaR learning. Differential privacy and private learning. Differential privacy was introduced through sensitivity-calibrated randomized mechanisms by Dwork et al. (2006); for general background on differential privacy, group privacy, and post-processing, see Dwork and Roth (2014). The 5
Mansouri
finite-class upper bound uses the exponential mechanism of McSherry and Talwar (2007). Private convex ERM was studied by Chaudhuri et al. (2011) and later by Bassily et al. (2014). Bassily et al. (2019) established near-optimal population-risk rates for private stochastic convex optimization. This theory is used as a primitive after reducing CVaR learning to a lifted convex problem. Nearby privacy-robustness work. Recent work studies differentially private worstgroup risk minimization for known finite groups (Zhou and Bassily, 2024). CVaR is different: the high-loss tail is unknown, endogenous, and predictor-dependent. Differentially private quantile estimation and quantile-loss optimization are also close but distinct (Gillenwater et al., 2021; Chen and Chua, 2023). The lower bounds include cases where the VaR threshold is known; the difficulty is private tail averaging, not merely private quantile estimation. Finally, a recent preprint on DP-DRO studies private algorithms for DRO formulations, including divergence-based models, but it does not settle the minimax population excess-risk frontier for standard unregularized CVaR-ERM (Xu et al., 2026). Table 2: Relationship to nearby lines of work. The distinguishing feature here is private learning of an endogenous CVaR tail average at the effective tail sample size nτ . Line of work
Objective
Privacy
Endogenous tail Minimax nτ frontier
Private SCO
Expectation
Yes
No
Private quantiles Worst-group risk
VaR/quantile Known groups
Yes Yes
Partly No
DP-DRO
Robust objective
Yes
Varies
Private CVaR learning
CVaR tail average
Yes
Yes
No tail-risk sample-size effect No private tail-average term Group sizes are fixed externally Not unregularized CVaR minimax Yes: scalar and finite-class complete, convex modular
2 Preliminaries 2.1 Differential privacy Datasets S, S ′ ∈ Z n are neighboring, denoted S ∼ S ′ , if they differ in at most one coordinate. Definition 2.1 (Differential privacy) A randomized algorithm A : Z n → O is (ε, δ)differentially private if for all neighboring S, S ′ and all measurable E ⊆ O, P(A(S) ∈ E) ≤ eε P(A(S ′ ) ∈ E) + δ. If δ = 0, the algorithm is ε-differentially private. The following standard group-privacy consequence is used (Dwork and Roth, 2014). Lemma 2.2 (Group privacy) If A is (ε, δ)-DP and S, S ′ differ in at most k entries, then for all events E, k−1 X ′ kε P(A(S ) ∈ E) ≤ e P(A(S) ∈ E) + δ ejε . j=0
6
The Privacy Price of Tail-Risk Learning
Equivalently, P(A(S) ∈ E) ≥ e−kε P(A(S ′ ) ∈ E) − kδ. Proof Iterate the one-step DP inequality along a path of k neighboring datasets. The second inequality follows by rearranging and using e(j−k)ε ≤ 1.
2.2 CVaR For an integrable real random variable X and τ ∈ (0, 1], define ρτ (X) = inf
η∈R
1 η + E[(X − η)+ ] . τ
When X is a loss, this is CVaR1−τ (X), the average loss over the upper τ tail (Rockafellar and Uryasev, 2000, 2002). If X ∈ [0, B], the infimum may be restricted to η ∈ [0, B]. A useful dual representation is
1 ρτ (X) = sup E[qX] : 0 ≤ q ≤ , Eq = 1 . τ This representation makes clear that CVaR is an adversarially reweighted expectation whose density envelope is 1/τ (Rockafellar and Uryasev, 2002; Ruszczyński and Shapiro, 2006). 2.3 Learning objective Let F be a class of predictors and let ℓ : F × Z → [0, B] be a loss. For f ∈ F, ρτ,P (f ) := ρτ (ℓ(f ; Z)),
Z ∼ P.
The empirical counterpart is n
( ρbτ,S (f ) = inf
η∈[0,B]
1 X η+ (ℓ(f ; Zi ) − η)+ nτ
) .
i=1
For convex learning, write f = w ∈ W ⊂ Rd and define the lifted population and empirical objectives 1 ϕP (w, η) = η + EP [(ℓ(w; Z) − η)+ ], τ n 1 X ϕbS (w, η) = η + (ℓ(w; Zi ) − η)+ . nτ i=1
Then ρτ,P (w) = inf ϕP (w, η),
inf ρτ,P (w) = inf ϕP (w, η). w
η∈[0,B]
7
w,η
Mansouri
3 Sensitivity and scalar CVaR estimation 3.1 Sensitivity of empirical CVaR Lemma 3.1 (Exact one-record sensitivity) Assume ℓ(f ; z) ∈ [0, B] for all f, z. If S ∼ S ′ , then 1 . sup ρbτ,S (f ) − ρbτ,S ′ (f ) ≤ B min 1, nτ f This bound is tight for the minimized empirical CVaR functional. Moreover, the lifted objective at fixed (f, η) has sensitivity B sup ϕbS (f, η) − ϕbS ′ (f, η) ≤ . nτ f,η Proof For a vector x = (x1 , . . . , xn ) ∈ [0, B]n , empirical CVaR has the dual form ( n ) n 1X 1 1X qi x i : 0 ≤ q i ≤ , qi = 1 . ρbτ (x) = sup n τ n i=1
i=1
If x, x′ differ only in coordinate j, then every feasible q satisfies qj B 1X 1X ′ . qi xi − qi xi = |xj − x′j | ≤ n n n nτ i
i
Taking suprema over the same feasible set gives |b ρτ (x) − ρbτ (x′ )| ≤
B . nτ
Since both empirical CVaR values lie in [0, B], also |b ρτ (x) − ρbτ (x′ )| ≤ B. The exact upper bound follows. It is attained by x = (0, . . . , 0) and x′ = (B, 0, . . . , 0), for which 1 1 B ′ ρbτ (x) = 0, ρbτ (x ) = min n, = B min 1, . n τ nτ For fixed (f, η) and neighboring samples S, S ′ differing only in the last coordinate, 1 B ϕbS (f, η) − ϕbS ′ (f, η) ≤ (ℓ(f ; Zn ) − η)+ − (ℓ(f ; Zn′ ) − η)+ ≤ , nτ nτ because η ∈ [0, B] and both positive parts lie in [0, B]. This lemma identifies both scales. Minimized empirical CVaR has the exact capped sensitivity above, while algorithms acting on the lifted objective still face the B/(nτ ) scale pointwise in (f, η). 8
The Privacy Price of Tail-Risk Learning
3.2 Scalar lower bound The scalar problem is a private statistical estimation problem in the sense of optimal-rate private estimation (Smith, 2011). The next result proves that this scale is informationtheoretically unavoidable even when there is no learning problem and the VaR threshold is known. Theorem 3.2 (Private scalar CVaR estimation lower bound) There are universal constants c, c1 , c2 > 0 such that the following holds. Let τ ∈ (0, 1], B > 0, and ε ∈ (0, 1]. For any ε-DP estimator rb : Z n → R, 1 sup ES∼P n |b r(S) − ρτ,P (Z)| ≥ cB min 1, . εnτ P :Z∈[0,B] The same lower bound holds for (ε, δ)-DP estimators whenever δ ≤ c2 /k, where k = ⌈4np⌉ and p = c1 min{τ, 1/(εn)}. Proof Let P0 put all mass at 0. Let P1 put mass p at B and mass 1 − p at 0, where 1 p = c1 min τ, εn for a small numerical constant c1 > 0. Since p ≤ τ , the Rockafellar-Uryasev formula gives ρτ,P0 (Z) = 0,
ρτ,P1 (Z) =
pB =: ∆. τ
Indeed, for X = B1{U = 1} with U ∼ Bernoulli(p) and p ≤ τ , n o p pB p pB ρτ (X) = inf η + (B − η) = inf +η 1− = . τ τ τ τ η∈[0,B] η∈[0,B] Suppose for contradiction that an ε-DP estimator satisfies expected error at most ∆/16 under both P0n and P1n . Define the event E = {b r(S) ≤ ∆/2}. By Markov’s inequality, P0n (E) ≥ 7/8,
P1n (E) ≤ 1/8.
Under P1n , let K be the number of nonzero observations. Then K ∼ Binomial(n, p) and EK = np. Let k = ⌈4np⌉. Markov’s inequality gives P1n (K ≤ k) ≥ 3/4. On the event {K ≤ k}, the realized dataset differs from the all-zero dataset in at most k entries. By group privacy, P(b r(S) ≤ ∆/2 | S) ≥ e−kε P(b r(0n ) ≤ ∆/2) ≥ e−kε P0n (E). This is the pure-DP comparison. Since kε ≤ 4c1 + ε and c1 is chosen small, the right-hand side is bounded below by a numerical constant larger than 1/4. Consequently P1n (E) > 1/8, contradicting the previous display. 9
Mansouri
For approximate DP, the same argument uses the group-privacy bound P(b r(S) ∈ E) ≥ e−kε P(b r(0n ) ∈ E) − kδ. Taking δ ≤ c2 /k for a sufficiently small universal constant c2 preserves the contradiction after reducing constants. Therefore some distribution among P0 , P1 has expected error at least ∆/16, and 1 pB = c1 B min 1, . ∆= τ εnτ
Theorem 3.3 (Scalar private plug-in upper bound) Let Z ∈ [0, B] and let ρbτ,S = ρτ,Pbn (Z) be empirical CVaR. Define ρeτ (S) = Π[0,B] (b ρτ,S + ξ) ,
ξ ∼ Lap
∆τ ε
,
1 ∆τ = B min 1, nτ
.
Then ρeτ is ε-DP and, for ε ∈ (0, 1],
1 sup E |e ρτ (S) − ρτ,P (Z)| ≤ sup E |b ρτ,S − ρτ,P (Z)| + B min 1, εnτ P :Z∈[0,B] P :Z∈[0,B]
.
Proof By Lemma 3.1, ρbτ,S has one-record sensitivity at most ∆τ . The Laplace mechanism therefore gives ε-DP. Since ρτ,P (Z) ∈ [0, B], projection onto [0, B] cannot increase absolute error, so Π[0,B] (b ρτ,S + ξ) − ρτ,P (Z) ≤ |b ρτ,S − ρτ,P (Z)| + |ξ|. Taking expectations gives the nonprivate empirical error plus E|ξ| = ∆τ /ε. The projected estimator also has error at most B. Since ε ≤ 1, 1 ∆τ ≤ B min 1, , min B, ε εnτ which proves the display.
Theorem 3.4 (Complete scalar private CVaR minimax rate) Let Rε,0,scal := inf n,τ
sup
rb∈ε-DP P :Z∈[0,B]
ES∼P n |b r(S) − ρτ,P (Z)| .
For ε ∈ (0, 1], under pure DP, Rε,0,scal =Θ n,τ
1 1 B min 1, √ + εnτ nτ
.
The same complete rate holds for approximate DP under the small-δ condition in Theorem 3.2. 10
The Privacy Price of Tail-Risk Learning
Proof For the upper bound, Lemma 4.1 implies 1 . E |b ρτ,S − ρτ,P (Z)| ≤ CB min 1, √ nτ P :Z∈[0,B] sup
Combining this with the plug-in private estimator in Theorem 3.3 gives Rε,0,scal ≤ CB min n,τ
1 1 1, √ + εnτ nτ
.
For the nonprivate lower bound, use Bernoulli losses. When nτ ≲ 1, compare Bernoulli masses p0 = τ /2 and p1 = τ ; the n-sample KL divergence is bounded by a universal constant and p the CVaR gap is B/2. When nτ ≳ 1, compare Bernoulli masses p0 = τ /2 and p1 = τ /2 + c τ /n, with c > 0 small enough that p1 ≤ τ . For X = B Bernoulli(p) with √ p ≤ τ , ρτ (X) = pB/τ , so the CVaR gap is cB/ nτ in the second regime. In both regimes, Le Cam’s method gives 1 ε,0,scal Rn,τ ≥ cB min 1, √ . nτ Theorem 3.2 gives the privacy lower bound Rε,0,scal ≥ cB min n,τ
1 1, εnτ
.
Taking the maximum of the two lower bounds and using max{a, b} ≥ (a + b)/2, with the trivial cap by B, proves the displayed lower bound. The approximate-DP statement follows from the small-δ extension in Theorem 3.2.
Approximate-DP regime.
In Theorem 3.2, p = c1 min{τ, 1/(εn)} and k = ⌈4np⌉, so 1 . k = O min nτ, ε
The approximate-DP lower bound requires δ ≤ c/k. Thus standard choices such as δ = n−2 satisfy the condition in the p = τ regime once constants are fixed, since k ≲ nτ ≤ n. In the privacy-dominated regime, where k ≲ 1/ε, the same choice satisfies the condition for constant ε, or more generally whenever n−2 ≲ ε. Remark 3.5 (Private quantiles are not enough) In the proof above the minimizing threshold is known: η = 0. Thus the lower bound is not caused by privately estimating a quantile. It is caused by privately estimating the tail average. This separates private CVaR learning from private quantile estimation and from general private estimation phenomena (Smith, 2011). 11
Mansouri
4 Finite-class private CVaR learning For finite classes, the decomposition can be closed completely. The ordinary CVaR statistical term has effective sample size nτ , while the exponential mechanism contributes the privacy price at effective private sample size εnτ . For a distribution P , write the ordinary nonprivate CVaR uniform-convergence term as Gn,τ (F, P ) := 2ES sup |ρτ,P (f ) − ρbτ,S (f )| . f ∈F
Lemma 4.1 (Scalar empirical CVaR concentration) Let X1 , . . . , Xn be iid copies of a random variable X ∈ [0, B], and let ρbτ,n be the empirical CVaR at tail mass τ . There is a universal constant C > 0 such that, for every u ≥ 1, r u u P |b ρτ,n − ρτ (X)| > CB min 1, + ≤ 4e−u . nτ nτ In particular, after increasing C, r u ≤ 4e−u P |b ρτ,n − ρτ (X)| > CB min 1, nτ for all u ≥ 1. Proof Write 1 ϕ(η) = η + P (X − η)+ , τ
1 b ϕ(η) = η + Pn (X − η)+ , τ
where Pn denotes the empirical measure, and let hη (x) = (x − η)+ . The following relative Bernstein inequality is used for the one-dimensional excess-threshold class H = {hη : η ∈ [0, B]}: with probability at least 1 − 2e−u , simultaneously for all η ∈ [0, B], ! r B P hη u Bu (Pn − P )hη ≤ C0 + , (4.1) n n and r (P − Pn )hη ≤ C0
B Pn hη u Bu + n n
! .
(4.2)
For completeness, Appendix A proves this relative Bernstein specialization; scalar empirical CVaR concentration inequalities of this type also go back to Brown (2007) and were sharpened by Thomas and Learned-Miller (2019). Let η ⋆ ∈ argminη∈[0,B] ϕ(η). Since ρτ (X) ≤ B and η ⋆ ≥ 0, P hη⋆ = τ (ρτ (X) − η ⋆ ) ≤ τ B. On the event (4.1), b ⋆ ) − ϕ(η ⋆ ) = 1 (Pn − P )hη⋆ ≤ C0 B ρbτ,n − ρτ (X) ≤ ϕ(η τ 12
r
u u + nτ nτ
.
The Privacy Price of Tail-Risk Learning
b b η ) ≤ ϕ(B) b For the reverse direction, let ηb ∈ argminη∈[0,B] ϕ(η). Since ϕ(b = B and ηb ≥ 0, Pn hηb = τ (b ρτ,n − ηb) ≤ τ B. On the event (4.2), b η ) = 1 (P − Pn )hηb ≤ C0 B ρτ (X) − ρbτ,n ≤ ϕ(b η ) − ϕ(b τ
r
u u + nτ nτ
.
Combining the two one-sided bounds gives the first display. The second follows because both CVaR values lie in [0, B]: if u ≤ nτ , the linear term is dominated by the square-root term, while if u > nτ , the trivial bound |b ρτ,n − ρτ (X)| ≤ B applies.
Theorem 4.2 (Finite-class nonprivate CVaR uniform convergence) There is a universal constant C > 0 such that for every finite class F with |F| = M and losses in [0, B], ( r ) log(2M ) . sup Gn,τ (F, P ) ≤ CB min 1, nτ P Moreover, this rate is minimax optimal up to constants for ordinary nonprivate CVaR learning over finite classes. Proof Apply Lemma 4.1 to the scalar loss ℓ(f ; Z) for each fixed f ∈ F and take a union bound. For s ≥ 0, with probability at least 1 − 4e−s , ( r ) log(4M ) + s sup |ρτ,P (f ) − ρbτ,S (f )| ≤ CB min 1, . nτ f ∈F Integrating this tail bound gives ( r ES sup |ρτ,P (f ) − ρbτ,S (f )| ≤ CB min 1, f ∈F
log(2M ) nτ
) ,
after adjusting the universal constant. Multiplying by the factor 2 in the definition of Gn,τ gives the upper bound. For the lower bound, use the canonical tail embedding with no privacy constraint. Ordinary finite-class learning with m iid informative observations has minimax excess risk at least ( r ) log M cB min 1, m by the standard Fano–Assouad finite-class lower bound. Let m = ⌈4nτ ⌉ and suppose, toward contradiction, that an ordinary nonprivate CVaR learner on n samples achieved excess risk αn on every embedded finite-class instance. Given m ordinaryPiid samples, draw independent activation indicators T1 , . . . , Tn ∼ Bernoulli(τ ) and set K = i Ti . If K ≤ m, place the first K ordinary samples into the active slots and fill inactive slots with the dummy zero-loss 13
Mansouri
point; if K > m, fill the remaining active slots with the dummy point as well. No privacy parameters are involved here; this is only a coupling argument. The constructed sample has total variation distance at most P(K > m) ≤ exp(−cnτ ) from the ideal embedded CVaR sample, and under the embedding the CVaR excess equals ordinary excess exactly. Thus the CVaR learner would give an ordinary finite-class learner with m ≍ nτ samples and excess at most αn + B exp(−cnτ ). Comparing with the ordinary finite-class lower bound and absorbing the exponentially small residual gives ) ( r log M , cB min 1, nτ with constants adjusted for the binomial coupling. This is the nonprivate version of the tail-sample transfer theorem proved formally in Theorem 6.3.
Theorem 4.3 (Finite-class private upper bound) There is a universal constant C > 0 such that the following holds. Let F be finite with |F| = M , and suppose ℓ(f ; z) ∈ [0, B]. The exponential mechanism of McSherry and Talwar (2007), with score q(S, f ) = −b ρτ,S (f ) and sensitivity B/(nτ ) is ε-DP and returns fb satisfying log(2M ) b E ρτ,P (f ) − inf ρτ,P (f ) ≤ Gn,τ (F, P ) + CB min 1, . f ∈F εnτ Consequently, ( r ) log(2M ) log(2M ) sup E ρτ,P (fb) − inf ρτ,P (f ) ≤ CB min 1, + . f ∈F nτ εnτ P
Proof The sensitivity lemma implies that q(S, f ) has sensitivity at most B/(nτ ). Therefore the exponential mechanism sampling εnτ P(fb = f ) ∝ exp − ρbτ,S (f ) 2B is ε-DP. The standard expected utility guarantee for the exponential mechanism (McSherry and Talwar, 2007) yields 2B(log M + 1) b E ρbτ,S (f ) − min ρbτ,S (f ) | S ≤ . f ∈F εnτ Let f ⋆ ∈ argminf ρτ,P (f ). Then h i h i ρτ,P (fb) − ρτ,P (f ⋆ ) ≤ ρτ,P (fb) − ρbτ,S (fb) + ρbτ,S (fb) − ρbτ,S (f ⋆ ) + [b ρτ,S (f ⋆ ) − ρτ,P (f ⋆ )] ≤ 2 sup |ρτ,P (f ) − ρbτ,S (f )| + ρbτ,S (fb) − min ρbτ,S (f ). f
f
14
The Privacy Price of Tail-Risk Learning
Taking expectations gives the same display with privacy term Vpriv :=
2B(log M + 1) . εnτ
The expected excess risk is also at most B, because all losses lie in [0, B]. Hence it is bounded by both Gn,τ (F, P ) + Vpriv and B, and therefore by Gn,τ (F, P ) + min{B, Vpriv }. Writing a = (log M + 1)/(εnτ ), the displayed bound follows from min{B, 2Ba} ≤ 2B min{1, a}.
The precedingptheorem says that finite-class private CVaR learning decomposes into the ordinary term B log(2M )/(nτ ) and the privacy price B log(2M )/(εnτ ), up to universal constants. The next theorem shows that the privacy dependence is minimax optimal up to constants and the trivial range cap. Theorem 4.4 (Finite-class minimax lower bound for the privacy price) There are universal constants c, c′ , c0 > 0 such that for every M ≥ 2, n ≥ 1, τ ∈ (0, 1], B > 0, and ε ∈ (0, 1], there is a class F with |F| = M and losses in [0, B] such that every ε-DP learner A returning an element of F satisfies log M sup E ρτ,P (A(S)) − inf ρτ,P (f ) ≥ cB min 1, . f ∈F εnτ P √ The same extension holds for (ε, δ)-DP under the small-δ condition δ ≤ c′ /(k M ), where k = ⌈4np⌉ and p = c0 min{τ, log M/(εn)}. Proof First suppose M is larger than a sufficiently large universal constant M0 . Let Z = {0, 1, . . . , M } and F = {f1 , . . . , fM }. Define ℓ(fr ; z) = B1{z ∈ [M ], z ̸= r}. The point z = 0 is a null observation with zero loss for every predictor. For each j ∈ [M ], let Pj be the distribution with Pj (Z = j) = p, where
Pj (Z = 0) = 1 − p,
log M p = c0 min τ, εn
for a sufficiently small universal constant c0 > 0. Since p ≤ τ , under Pj the predictor fj has zero loss always, while every fr with r = ̸ j has loss B with probability p and loss 0 otherwise. Therefore ρτ,Pj (fj ) = 0,
ρτ,Pj (fr ) = 15
pB τ
(r ̸= j).
Mansouri
Indeed, for X = B1{U = 1} with U ∼ Bernoulli(p) and p ≤ τ , o pB n p ρτ (X) = inf . η + (B − η) = τ τ η∈[0,B] Thus the excess-risk gap for every wrong predictor under Pj is ∆=
Bp . τ
Suppose, toward contradiction, that the expected excess risk is at most ∆/4 under every Pj . Then 3 PS∼Pjn (A(S) = fj ) ≥ for every j. 4 P n Let S0 = (0, . . . , 0) and write qj = P(A(S0 ) = fj ). Then j qj = 1. Under Pj , let Kj = |{i : Zi = j}|. Then Kj ∼ Binomial(n, p), and with k = ⌈4np⌉, Markov’s inequality gives P(Kj > k) ≤ 1/4. On {Kj ≤ k}, the sample differs from S0 in at most k entries, so pure group privacy gives P(A(S) = fj ) ≤ ekε qj . Consequently, PS∼Pjn (A(S) = fj ) ≤
1 + ekε qj . 4
Averaging over j yields M
1 X 1 ekε PS∼Pjn (A(S) = fj ) ≤ + . M 4 M j=1
Because kε ≤ 4c0 log M + 1 and M ≥ M0 , choosing c0 small and M0 large ensures ekε /M ≤ 1/4. The average success probability is therefore at most 1/2, contradicting the lower bound 3/4 for every term. For (ε, δ)-DP, group privacy gives P(A(S) = fj ) ≤ ekε qj + kekε δ. √ Averaging adds the term ke√kε δ. Since the previous choice of constants gives ekε ≤ M , it suffices to require δ ≤ c′ /(k M ) for a small universal constant c′ . For 2 ≤ M < M0 , the same conclusion follows, after changing constants, from the two-hypothesis construction on {0, 1}, augmented with M − 2 dummy predictors g whose loss is identically B. Since every dummy predictor has excess at least the hard gap under both hard distributions, any learner with expected excess below a fixed fraction of the gap must solve the original two-hypothesis problem with constant success probability. Since log M ≍ 1 in this range, the displayed rate reduces to the two-point rate. Finally, pB log M ∆= = c0 B min 1, , τ εnτ which proves the theorem.
16
The Privacy Price of Tail-Risk Learning
Approximate-DP regime. k = ⌈4np⌉, so
In the finite-class packing, p = c0 min{τ, log M/(εn)} and
log M . k = O min nτ, ε √ The approximate-DP lower bound assumes δ ≤ c/(k M ). This is the regime in which approximate-DP group privacy still distinguishes the M -way packing. For polynomial-size classes and the common choice δ = n−ω(1) , this condition is satisfied after constants are fixed. For exponentially large M , the approximate-DP lower bound is intentionally weaker; the pure-DP lower bound remains unconditional. Theorem 4.5 (Complete finite-class private CVaR minimax rate) Let Rε,0 n,τ (M ) denote the distribution-free minimax excess CVaR risk over all finite classes of size M with losses in [0, B]. Under pure ε-DP, ( r )! log(2M ) log(2M ) + , Rε,0 n,τ (M ) = Θ B min 1, nτ εnτ with universal implicit constants. The same complete rate holds for approximate DP under the small-δ condition in Theorem 4.4. Proof The upper bound is Theorem 4.3 combined with Theorem 4.2. For the lower bound, Theorem 4.2 gives an ordinary statistical lower bound ( r ) log(2M ) a := cB min 1, , nτ while Theorem 4.4 gives a privacy lower bound log(2M ) log M ≍ cB min 1, , b := cB min 1, εnτ εnτ where the last comparison uses M ≥ 2. Since both lower bounds apply to the same distribution-free minimax problem over size-M classes, Rε,0 n,τ (M ) ≥ max{a, b}. For nonnegative x, y, max{x, y} ≥ (x + y)/2, and after applying the trivial cap B this yields ( r ) log(2M ) log(2M ) max{a, b} ≥ c′ B min 1, + nτ εnτ for another universal constant c′ > 0. This proves the lower bound. Thus finite classes give the anchor theorem: the ordinary tail sample size nτ and the effective private tail sample size εnτ appear in the same decomposition. In particular, the privacy component of this complete rate is log(2|F|) B min 1, , εnτ up to universal constants. 17
Mansouri
5 Convex private CVaR learning as modular transfer Now consider a convex parameter set W ⊂ Rd . The purpose of this section is modular: isolate the CVaR-induced privacy degradation from the ambient private-SCO geometry. The upper bound reduces private CVaR optimization to private SCO on a lifted objective; the lower bound in Section 6 transfers private-SCO hardness back through the tail embedding. Assumption 5.1 (Bounded convex Lipschitz losses) The set W is closed, convex, and has Euclidean diameter at most D. The loss ℓ(w; z) is convex in w, G-Lipschitz in w, and takes values in [0, B]. For a scale parameter λ > 0, set u = η/λ, define Θλ = W × [0, B/λ] ⊂ Rd+1 , and write the scaled lifted loss as 1 gλ (w, u; z) = λu + (ℓ(w; z) − λu)+ . τ Then minimizing Egλ (w, u; Z) over (w, u) ∈ Θλ is exactly the Rockafellar–Uryasev CVaR problem with the threshold variable η = λu. Lemma 5.2 (Scaled lifted convexity and Lipschitzness) Under Assumption 5.1, gλ (·; z) is convex on Θλ and is Lτ,λ -Lipschitz with √ Lτ,λ ≤
G2 + λ2 . τ
The diameter of Θλ is at most r DΘ,λ ≤
D2 +
B2 . λ2
Proof The map (v, u) 7→ (v − λu)+ is convex and nondecreasing in v, while w 7→ ℓ(w; z) is convex. Hence gλ is convex. For a subgradient, let s ∈ [0, 1] be a subgradient of r 7→ r+ at r = ℓ(w; z) − λu. Then ∂w gλ = sτ −1 ∂w ℓ(w; z),
∂u gλ = λ(1 − sτ −1 ).
Therefore ∥∂w gλ ∥2 ≤ G/τ,
|∂u gλ | ≤ λ/τ,
where the latter uses τ ≤ 1. The Lipschitz bound follows. The diameter bound is immediate from the product geometry.
18
The Privacy Price of Tail-Risk Learning
5.1 Private SCO as an imported interface The convex results are intentionally modular. Rather than reproving Euclidean private-SCO theory, the relevant result is stated as a precise interface, and the Rockafellar–Uryasev CVaR lift is then verified to satisfy that interface. This separation isolates the CVaR-specific phenomenon: the replacement of the full sample size n by the effective tail sample size nτ , and of the private sample size εn by the effective private tail sample size εnτ . e e All logarithmic factors hidden in O(·) and Ω(·) in this subsection are exactly those inherited from the cited Euclidean approximate-DP SCO interface. The CVaR lifting and tail-embedding reductions introduce no additional polynomial dependence on n, τ, ε, δ, or d. Theorem 5.3 (Euclidean approximate-DP SCO interfaces) Let Θ ⊂ RdΘ be closed and convex with Euclidean diameter at most DΘ . For a distribution Q over losses g(·; Z), write LQ (θ) = EZ∼Q g(θ; Z), L⋆Q = inf LQ (θ). θ∈Θ
The cited Euclidean SCO results are usually stated in terms of a radius MΘ = supθ∈Θ ∥θ∥2 . Since excess risk and differential privacy are invariant under translations of the parameter domain, Θ can be translated before the interface is applied, so that MΘ ≤ DΘ . Thus the radius-based statements imply the diameter-based form used below, up to universal constants. The excess-risk criterion is expected population excess, ES,A LQ (A(S)) − L⋆Q , S ∼ Qn , where the expectation is over both the sample and the learner’s internal randomness. Privacy is record-level central privacy with respect to the n sampled losses. Upper interface. Suppose that, for every z, g(·; z) is convex and LΘ -Lipschitz on Θ. For every ε ∈ (0, 1] and 0 < δ ≤ n−2 , the non-smooth Euclidean private-SCO theorem of Bassily et al. (2019, Theorem 4.4) gives a central (ε, δ)-DP algorithm ASCO satisfying " #! p d log(1/δ) 1 Θ e LΘ D Θ √ + ES,A LQ (ASCO (S)) − L⋆Q ≤ O . εn n The non-smooth implementation uses Moreau–Yosida smoothing, equivalently proximal access to the individual losses. Because the theorem is used only as a statistical rate primitive, no running-time claim is made. Lower interface. For the privacy-dependent term, the standard reduction from private ERM lower bounds to private SCO lower bounds is used, as recorded by Bassily et al. (2019, Appendix C), together with the Euclidean private-ERM lower bounds of Bassily et al. (2014). √ The nonprivate 1/ m term is the standard stochastic convex optimization lower bound. e lower-bound interface, with the tilde hiding only the These ingredients are combined as a Ω logarithmic losses from this imported SCO lower-bound reduction. For every m ≥ 1, dΘ ≥ 1, DΘ > 0, LΘ > 0, ε ∈ (0, 1], and 0 < δ ≤ m−2 , this interface gives a distribution over shifted linear losses on a Euclidean domain of diameter DΘ such that the losses are convex, LΘ -Lipschitz, and have range contained in an interval of length at most LΘ DΘ , while every central (ε, δ)-DP learner satisfies √ 1 dΘ ⋆ e √ sup ES,A LQ (A(S)) − LQ ≥ Ω LΘ DΘ min 1, + . εm m Q 19
Mansouri
The lower-bound class is convex and bounded without clipping: it is obtained by shifting linear losses by a parameter-independent constant. Such shifts preserve excess risk. Verification for the lifted CVaR problem.
For the lifted CVaR loss
1 gλ (w, u; z) = λu + (ℓ(w; z) − λu)+ , τ
(w, u) ∈ Θλ := W × [0, B/λ],
Lemma 5.2 gives √ dΘ = d + 1,
LΘ = Lτ,λ ≤
G2 + λ2 , τ
r DΘ = DΘ,λ ≤
D2 +
B2 . λ2
Moreover 0 ≤ gλ (w, u; z) ≤ B/τ , because ℓ(w; z) ∈ [0, B] and λu ∈ [0, B]. Thus the lifted CVaR problem satisfies the Euclidean SCO upper interface with dimension d + 1. Applying the upper-interface algorithm to the lifted losses preserves record-level privacy, because each original record zi produces exactly one lifted loss gλ (·; zi ). Theorem 5.4 (Private convex CVaR upper bound) Under Assumption 5.1, for ε ∈ (0, 1] and 0 < δ ≤ n−2 , there exists a central (ε, δ)-DP learner returning w b ∈ W such that " #! p (d + 1) log(1/δ) GD + B 1 e √ + E ρτ,P (w) b − inf ρτ,P (w) ≤ O . w∈W τ εn n In particular, the private part is e O
! p (GD + B) d log(1/δ) εnτ
e . Under the natural normalization B ≍ GD, this scale is O(B
p d log(1/δ)/(εnτ )).
Proof Apply the upper interface in Theorem 5.3 to the lifted loss gλ over Θλ . Let θb = (w, b u b) be the output. Since ρτ,P (w) b ≤ Egλ (w, b u b; Z) and inf ρτ,P (w) =
w∈W
inf (w,u)∈Θλ
Egλ (w, u; Z),
the CVaR excess risk is bounded by the lifted SCO population excess risk. By Lemma 5.2, s 1 B2 2 2 2 (G + λ ) D + 2 . Lτ,λ DΘ,λ ≤ τ λ The expression inside the square root equals G2 D 2 + B 2 +
G2 B 2 + λ2 D 2 . λ2
20
The Privacy Price of Tail-Risk Learning
Choosing λ2 = GB/D when G, B, D > 0, and using a limiting argument in degenerate cases, gives GD + B Lτ,λ DΘ,λ ≤ . τ Substituting this into Theorem 5.3, with dΘ = d + 1, yields " #! p (d + 1) log(1/δ) 1 GD + B e √ + . E ρτ,P (w) b − inf ρτ,P (w) ≤ O w∈W τ εn n The private part is therefore ! p (GD + B) d log(1/δ) e O . εnτ
Remark 5.5 (Modular convex transfer) The convex upper bound is deliberately modular. The rescaled Rockafellar–Uryasev lifting supplies the CVaR-specific reduction, while the Euclidean approximate-DP SCO interface supplies the ambient high-dimensional optimization guarantee. This factorization is useful: any improvement in the private-SCO interface can be substituted into the same CVaR lift, and the lift itself introduces no additional polynomial dependence on n, τ, ε, δ, or d. The CVaR-specific privacy dependence is the factor 1/(εnτ ), and the lower bounds below show that this factor is unavoidable.
6 Tail embedding and minimax lower bounds The next result is the conceptual core. It identifies the canonical hard subproblem inside CVaR learning: ordinary expected-risk learning with only the tail fraction of samples carrying information. 6.1 Exact embedding of expectation into CVaR Let Q be a distribution on X , let a(w; x) ∈ [0, B] be an ordinary loss, and add a dummy point x⊥ ∈ / X with a(w; x⊥ ) = 0 for all w. Draw T ∼ Bernoulli(τ ). If T = 1, draw Y = X ∼ Q; if T = 0, set Y = x⊥ . Define Z = (T, Y ) and the CVaR loss ℓ(w; Z) = T a(w; Y ). Let Pτ (Q) denote the induced distribution on Z. Theorem 6.1 (Canonical tail embedding) For every w, ρτ,Pτ (Q) (ℓ(w; Z)) = EX∼Q [a(w; X)]. Consequently, minimizing CVaR over the embedded distribution is exactly equivalent to minimizing ordinary expected risk under Q. 21
Mansouri
Proof For η = 0, 1 1 η + E[(T a(w; Y ) − η)+ ] = E[T a(w; Y )] = EQ a(w; X). τ τ Now take η ≥ 0. Then 1 η + E[(T a(w; Y ) − η)+ ] = η + EQ [(a(w; X) − η)+ ] τ = EQ [max{a(w; X), η}] ≥ EQ a(w; X). For η < 0, 1 1−τ η + E[(T a(w; Y ) − η)+ ] = η + EQ [a(w; X) − η] + (−η) τ τ 1−τ (−η) ≥ EQ a(w; X). = EQ a(w; X) + τ Thus the infimum over η equals EQ a(w; X).
Remark 6.2 The nonnegativity of a is used in the embedding. If an imported ordinaryrisk lower bound is stated for losses in [−B, B], one first shifts every loss by the same w-independent constant to obtain losses in [0, 2B]. This preserves excess risk and changes only constants. Figure 3 illustrates the reduction: ordinary informative examples become the active records in an embedded CVaR sample, while inactive records carry zero loss. 6.2 Tail-sample transfer from CVaR learners to ordinary private SCO learners The embedding gives a formal way to transfer private SCO lower bounds to CVaR learning. On this embedded subclass, the effective-sample-size heuristic is exact: n CVaR records contain only Θ(nτ ) ordinary informative records. For an ordinary loss class A with losses a(w; x) ∈ [0, B], let Embτ (A) denote the CVaR class obtained by the dummy-inactive embedding above. For fixed privacy parameters (ε, δ), let Rε,δ,SCO (A) denote the ordinary m private SCO minimax excess risk with m samples, and let Rε,δ,CVaR (Embτ (A)) denote the n,τ private CVaR minimax excess risk over the embedded class with n samples. These are class-restricted transfer risks. Theorem 6.3 (Tail-sample transfer) Fix n and τ , and let m = ⌈4nτ ⌉. Then Rε,δ,CVaR (Embτ (A)) ≥ Rε,δ,SCO (A) − B exp(−cnτ ), n,τ m for a universal constant c > 0. Proof It suffices to prove the following algorithmic reduction. Suppose there is an (ε, δ)-DP CVaR learner An that, for every embedded distribution Pτ (Q), achieves expected excess 22
The Privacy Price of Tail-Risk Learning
Ordinary SCO instance Xi ∼ Q m ≍ nτ
Tail embedding Eτ n CVaR slots, Ti ∼ Bernoulli(τ )
Lower-bound transfer ρτ (ℓ) = EQ a
active (Ti = 1) inactive (Ti = 0) : Yi = x⊥ , ℓ = 0
ordinary SCO inside CVaR learning m ≍ nτ
CVaR instance Zi = (Ti , Yi ),
ℓ(w; Zi ) = Ti a(w; Yi )
≈ nτ active tail records
√ e R0 d Ω εnτ
Figure 3: Tail-sample embedding reduction. Ordinary expected-risk learning with m samples is embedded into CVaR learning by activating each record with probability τ and assigning inactive records zero loss. The embedded loss ℓ(w; (T, Y )) = T a(w; Y ) places the informative observations in the upper τ -tail, so CVaR recovers the ordinary expected loss on the active distribution. Thus the effective-sample-size heuristic is exact on the canonical tail-embedded subproblem: any private CVaR learner on n samples would imply a private SCO learner on m ≃ nτ samples.
CVaR risk at most αn . For every m ≥ 4nτ , an (ε, δ)-DP ordinary learner is constructed using m iid samples from Q whose expected excess ordinary risk is at most αn + B exp(−cm). Given ordinary samples X1 , . . . , Xm ∼ Q, construct a synthetic CVaR P dataset of size n as follows. Draw independent T1 , . . . , Tn ∼ Bernoulli(τ ) and let K = i Ti . If K ≤ m, assign the first K ordinary samples to the active records {i : Ti = 1}, and assign the dummy point x⊥ to inactive records. If K > m, use the available m ordinary samples for the first m active records and fill the remaining active records with x⊥ . Changing one input sample Xj changes at most one synthetic record. Therefore the composed algorithm that constructs the synthetic dataset, runs An , and outputs its predictor is (ε, δ)-DP by post-processing (Dwork and Roth, 2014) and the one-record sensitivity of the construction. Couple this actual synthetic dataset Se to an ideal dataset S ⋆ ∼ Pτ (Q)n by using the same Bernoulli indicators and the same active covariates whenever K ≤ m. Under this coupling, Se = S ⋆ except on {K > m}, and therefore e Pτ (Q)n ≤ P(K > m). dTV L(S), The algorithmic output distribution after applying An is also within this total variation distance by post-processing. By Theorem 6.1, the ordinary excess risk of any output w is exactly its embedded CVaR excess risk. Since this excess risk is bounded by B, the expected ordinary excess risk of the composed learner is at most αn + BP(K > m). 23
Mansouri
Finally, EK = nτ and m ≥ 4nτ , so a Chernoff bound (Boucheron et al., 2013, Chapter 2) gives P(K > m) ≤ exp(−cm) for a universal constant c > 0. This proves the claimed ordinary-risk bound. Taking the contrapositive and then m = ⌈4nτ ⌉ gives the displayed minimax inequality, after adjusting the constant in the exponential residual.
Remark 6.4 The reduction uses more ordinary samples than the expected number of active CVaR samples by only a constant factor. Thus any lower bound for private SCO with m samples becomes a lower bound for CVaR learning with nτ ≍ m effective tail samples. 6.3 Convex lower bound and phase transition The convex lower bound uses only the lower interface in Theorem 5.3. The case D = 0 is trivial, so assume D > 0. To enforce the global loss cap B without clipping, apply the Euclidean lower-bound primitive with Lipschitz parameter G0 := min{G, B/D}. The resulting shifted linear-loss class is convex, G0 -Lipschitz, hence G-Lipschitz, and has range contained in an interval of length at most R0 := G0 D = min{B, GD}. After shifting by a w-independent constant, the losses lie in [0, R0 ] ⊆ [0, B], so the CVaR tail embedding applies without changing excess risk. The logarithmic factors hidden below are exactly those inherited from the imported approximate-DP SCO lower interface, not from the CVaR embedding. Corollary 6.5 (Dimension-dependent private CVaR lower bound) There exists a convex Lipschitz CVaR learning subclass over W ⊂ Rd with losses bounded by B such that every central (ε, δ)-DP learner with ε ∈ (0, 1] and 0 < δ ≤ ⌈4nτ ⌉−2 satisfies, with R0 = min{B, GD}, ( √ ) 1 d − B exp(−c′ nτ ) sup E ρτ,P (w) b − inf ρτ,P (w) ≥ cR0 min 1, √ + w∈W εnτ nτ P up to the logarithmic factors inherited from the lower interface in Theorem 5.3, for universal constants c, c′ > 0. Proof Let G0 = min{G, B/D} and R0 = G0 D = min{B, GD}. Use the shifted linear-loss class from the lower interface in Theorem 5.3 with Lipschitz parameter G0 , diameter D, dimension d, and sample size m = ⌈4nτ ⌉. The losses are convex, G-Lipschitz, and bounded in [0, R0 ] ⊆ [0, B]. Suppose a central (ε, δ)-DP CVaR learner on n samples achieved expected excess smaller than the displayed lower bound. Applying the tail-sample transfer theorem, Theorem 6.3, would produce a central (ε, δ)-DP ordinary SCO learner with m = ⌈4nτ ⌉ samples and 24
The Privacy Price of Tail-Risk Learning
expected excess below the Euclidean approximate-DP SCO lower interface, after accounting for the binomial-overflow residual. This contradicts the lower interface in Theorem 5.3. The privacy guarantee is preserved by Theorem 6.3 because changing one ordinary sample changes at most one synthetic active CVaR record. The embedding in Theorem 6.1 preserves convexity and Lipschitzness because ℓ(w; (T, Y )) = T a(w; Y ),
T ∈ {0, 1}.
It also preserves boundedness, since 0 ≤ a(w; Y ) ≤ R0 ≤ B. Therefore the embedded class is a valid bounded convex Lipschitz CVaR subclass. Substituting m = ⌈4nτ ⌉ into the lower interface gives ( √ )! 1 e R0 min 1, √ + d , Ω εnτ nτ up to the residual B exp(−c′ nτ ) from Theorem 6.3.
Residual term. The subtraction term is the binomial-overflow error in the coupling used by the tail-sample transfer theorem. The lower bound is therefore informative once nτ ≳ 1, and asymptotically once nτ → ∞. In the small-tail-sample regime nτ = O(1), the scalar and finite-class lower bounds already show the constant-scale privacy obstruction. The reduction also preserves record-level privacy exactly: changing one ordinary sample changes at most one synthetic active record before the CVaR learner is applied. Convex comparison. The convex theory is modular: it separates CVaR-specific structure from the Euclidean approximate-DP SCO interface. The upper bound uses the rescaled Rockafellar–Uryasev lifting to reduce private CVaR optimization to a standard private SCO problem over (w, u). The upper interface then gives the private term ! p (GD + B) d log(1/δ) e . O εnτ The lower bound runs in the opposite direction: the tail-embedding theorem shows that ordinary private SCO with m samples is contained inside CVaR learning with m ≍ nτ informative tail samples. Combining this embedding with the lower interface gives √ )! 1 e R0 min 1, √ + d , Ω εnτ nτ (
R0 = min{B, GD}.
Thus the privacy-dependent dependence on ε, n, τ , and d is matched up to the logarithmic factors inherited from Euclidean private SCO. The CVaR-specific reductions introduce the effective private tail sample size εnτ . Figure 4 summarizes the two transfer directions and the matched private component. 25
Mansouri
The corollary yields a clean impossibility threshold. Corollary 6.6 (Private tail-sample phase transition) For Euclidean convex CVaR learning, nontrivial dimension-dependent private learning requires √ εnτ ≫ d up to logarithmic factors. More generally, the private effective tail sample size must dominate the relevant complexity of the hypothesis class. Proof Ignoring the exponentially small binomial-overflow residual from Theorem 6.3, √ as carried √ into the preceding corollary, the private lower-bound term is R0 d/(εnτ ). If εnτ ≲ d, this term is of order R0 , the capped trivial scale of the bounded convex problem.
upper transfer CVaR lift + private-SCO upper primitive
√ e O((GD + B) d/(εnτ ))
matched private component √ d εnτ
√ e 0 d/(εnτ )) Ω(R
lower transfer tail embedding + private-SCO lower primitive
Figure 4: Matched convex upper and lower transfers. The upper route applies the rescaled Rockafellar–Uryasev lift and imports the Euclidean approximate-DP SCO upper primitive, producing the displayed private term. The lower route uses the tail-sample embedding to transfer Euclidean private-SCO hardness into CVaR learning. The tilde-Omega notation suppresses the logarithmic factors inherited from the imported Euclidean private-SCO lower interface.
Table 3: Modular anatomy of the convex result. Component
Source
Role
Rockafellar–Uryasev lift
Standard CVaR representation
Converts CVaR minimization into a convex problem over (w, u) with η = λu. Lifted Lipschitz scale Elementary calculation Gives scale (GD + B)/τ , hence the private upper term after the SCO interface. Private SCO upper interface Bassily–Feldman–Talwar– Supplies the approximate-DP expectedThakurta population SCO upper bound. Tail-sample embedding New reduction Embeds ordinary learning with m ≍ nτ informative samples into CVaR learning. Private SCO lower interface Euclidean private-SCO lower Transfers ordinary private-SCO hardness to theory CVaR through the tail embedding.
26
The Privacy Price of Tail-Risk Learning
7 A sensitivity extension to envelope-bounded coherent risks The exact minimax lower bounds are proved for CVaR. A simple sensitivity calculation, however, extends to coherent risks with bounded dual density envelopes in the standard coherent-risk framework (Artzner et al., 1999; Ruszczyński and Shapiro, 2006). Let ρQ (X) = sup E[qX], 0 ≤ q ≤ κ, Eq = 1. q∈Q
The empirical P analogue over a sample S = (Z1 , . . . , Zn ) assigns weights qi /n with 0 ≤ qi ≤ κ −1 and n i qi = 1. Proposition 7.1 (Sensitivity for envelope-bounded coherent risks) If the realized loss values xi ∈ [0, B] and the dual envelope satisfies q ≤ κ for every q ∈ Q, then the empirical risk has one-record sensitivity at most n κo B min 1, . n For CVaR at tail mass τ , κ = 1/τ . Proof Changing one sample changes any weighted empirical average by at most (κ/n)B. Taking a supremum over admissible weights cannot increase the sensitivity beyond the supremum of pointwise changes. Since the risk of [0, B]-valued losses also lies in [0, B], the one-record change is at most B. Combining the two bounds gives the display. Proposition 7.1 should be read as a sensitivity extension, not as a complete minimax theorem for arbitrary coherent risk envelopes. It shows that any envelope-bounded coherent risk with dual density radius κ has empirical one-record sensitivity at most B min{1, κ/n}. For CVaR, κ = 1/τ , and the preceding scalar, finite-class, and convex lower bounds show that this sensitivity scale is minimax sharp. Thus CVaR provides the canonical case in which the dual-envelope sensitivity mechanism is fully resolved.
8 Discussion The results identify a privacy-tail-risk frontier by decomposing private CVaR excess into ordinary tail-risk statistics and a privacy price. The mechanism is visible in the empirical objective: CVaR gives each tail observation weight of order 1/(nτ ), and differential privacy must protect the contribution of any single such observation. The lower bounds show that this is not merely a defect of sensitivity-based algorithms. Scalar CVaR estimation closes the decomposition with rate 1 1 . Θ B min 1, √ + εnτ nτ Finite-class CVaR learning gives the anchor theorem, closing the same decomposition with rate ( r )! log(2M ) log(2M ) Θ B min 1, + . nτ εnτ 27
Mansouri
The tail-sample transfer theorem further shows that ordinary private convex learning on m examples is contained in CVaR learning with m ≍ nτ informative tail examples. The results also clarify the relationship between CVaR learning and private quantile estimation. CVaR optimization contains a VaR threshold, but the lower bounds remain when the threshold is known. Therefore private quantile machinery can help with one component of the problem, but it cannot remove the private tail-average cost. Several extensions are natural. First, the modular convex upper bound can be paired with sharper CVaR-specific empirical-process arguments, replacing the generic nonprivate term by distribution-dependent or tail-sample-size rates under additional regularity while preserving the same privacy price. Second, strongly convex losses should yield improved geometry-dependent private terms. Third, unbounded or heavy-tailed losses require private truncation or robust private tail estimation; without boundedness or moment/tail regularity, the scalar lower bounds suggest that uniform guarantees are impossible. Fourth, Proposition 7.1 suggests that envelope-bounded coherent risks may admit analogous privacy theories, with the dual density radius playing the role occupied by 1/τ for CVaR.
9 Conclusion Differential privacy imposes an unavoidable inverse-tail-mass penalty on CVaR learning. For tail mass τ , the observations that determine the objective have effective sample size nτ , and privacy further reduces the useful scale to εnτ . The results decompose private CVaR learning into an ordinary CVaR statistical term and a minimax-sharp privacy price. The latter is governed by the effective private tail sample size εnτ and has the form privacy term at scale
model complexity , εnτ
with the preceding lower bounds showing that the 1/τ privacy price itself is intrinsic. Thus CVaR is the canonical case in which the dual-envelope sensitivity 1/τ is shown to be the minimax-sharp source of the privacy penalty.
Competing interests The author declares no competing interests.
Appendix A. A relative Bernstein bound for threshold-excess functions This appendix proves the empirical-process step used in Lemma 4.1. The threshold-excess class is one-dimensional and nested, and its localized entropy is measured relative to its own L1 (P ) mass. This is the reason the concentration bound has no residual log(1/τ ) factor. Let H = {hη (x) = (x − η)+ : η ∈ [0, B]}. All suprema below may be read as suprema over rational η’s. This causes no loss because η 7→ hη is Lipschitz in the uniform norm. Thus the class is separable and standard measurability issues are avoided. 28
The Privacy Price of Tail-Risk Learning
Lemma A.1 (Relative Bernstein for threshold excesses) There is a universal constant C > 0 such that, for every u ≥ 1, with probability at least 1 − 2e−u , ! r B P hη u Bu (Pn − P )hη ≤ C simultaneously for all η ∈ [0, B]. + n n With probability at least 1 − 2e−u , r (P − Pn )hη ≤ C
B Pn hη u Bu + n n
! simultaneously for all η ∈ [0, B].
Proof It is enough to prove the result for B = 1. The general case follows by applying the normalized argument to X/B and multiplying the resulting inequality by B. Hence assume X ∈ [0, 1]. Write A(η) = P hη = P (X − η)+ . The map A is continuous and nonincreasing on [0, 1], because |hη (x) − hη′ (x)| ≤ |η − η ′ |
for all x ∈ [0, 1].
This continuity is the only fact needed to handle atoms and ties. No no-atom assumption is used. For r ∈ (0, 1], define the localized class H(r) = {hη ∈ H : P hη ≤ r}. Since h1 ≡ 0, the class H(r) is nonempty. Let ηr = inf{η ∈ [0, 1] : A(η) ≤ r}. By continuity of A, A(ηr ) ≤ r. Moreover, since A is nonincreasing, H(r) = {hη : η ≥ ηr } up to P -null distinctions. Thus hηr is the largest element of H(r) in the pointwise order. If A is flat over an interval, any threshold in the flat part gives the same L1 (P ) bracket width, so ties cause no ambiguity. Fix α ∈ (0, 1), and put ar = A(ηr ) ≤ r. If ar = 0, then all functions in H(r) are P -a.s. zero and one bracket of L1 (P ) width zero suffices. Otherwise, let la m 1 r N= ≤ αr α and define levels tj = (ar − jαr)+ ,
j = 0, . . . , N.
Using continuity and monotonicity of A, choose nondecreasing thresholds ηr = η0 ≤ η1 ≤ · · · ≤ ηN = 1 29
Mansouri
so that A(ηj ) = tj whenever tj > 0, and ηN = 1 when tN = 0. For every j ≥ 1, monotonicity gives hηj ≤ hη ≤ hηj−1 whenever η ∈ [ηj−1 , ηj ]. The corresponding bracket width is P (hηj−1 − hηj ) = A(ηj−1 ) − A(ηj ) ≤ αr. Therefore
1 + 1, N[] (αr, H(r), L1 (P )) ≤ α
and hence log N[] (αr, H(r), L1 (P )) ≤ C0 log(C0 /α).
(A.1)
Crucially, this bound depends on the relative resolution α, but not on the radius r. L1 (P ) bracket of width δ is an L2 (P ) bracket of width at most √ Since 0 ≤ h ≤ 1, every √ δ. Thus, for 0 < ε ≤ r, C1 r log N[] (ε, H(r), L2 (P )) ≤ C1 log . ε2 Consequently,
Z √r q √ log N[] (ε, H(r), L2 (P )) dε ≤ C2 r.
(A.2)
0
√ Indeed, after the change of variables ε = r s, the left side is bounded by Z 1p √ r log(C1 /s2 ) ds, 0
√ which is O( r). The bracketing maximal inequality (van der Vaart and Wellner, 1996, Theorem 2.14.2) now gives, uniformly in r ∈ (0, 1], r r E sup |(Pn − P )h| ≤ C3 . (A.3) n h∈H(r) The following standard localized relative-deviation theorem is used in the exact form needed. It is the bounded, nonnegative, variance-controlled form of Bartlett, Bousquet and Mendelson’s local Rademacher theorem; equivalently it follows from their Theorem 3.3 and Corollary 3.5 (Bartlett et al., 2005). Localized relative-deviation theorem. Let G be a countably separable class of functions satisfying 0 ≤ g ≤ 1 and Var(g) ≤ P g. Suppose that for every r ∈ (0, 1], E
sup
|(Pn − P )g| ≤ ψ(r),
g∈G:P g≤r
where ψ is a sub-root function with fixed point r∗ . Then there is a universal constant C such that, for every u ≥ 1, with probability at least 1 − 2e−u , simultaneously for all g ∈ G and all K > 1, K u P g + CK r∗ + , (A.4) Pn g ≤ K −1 n 30
The Privacy Price of Tail-Risk Learning
and
K u Pn g + CK r∗ + . (A.5) K −1 n Both inequalities are applied to the same nonnegative class G; nothing is applied to −G. For the present class H, the variance condition holds because Pg ≤
Var(hη (X)) ≤ P h2η ≤ P hη , as 0 ≤ hη ≤ 1. By (A.3), the theorem applies with r r . ψ(r) = C3 n Its fixed point satisfies r∗ ≤ C4 /n. Since u ≥ 1, put u u ≤ C5 . n n
t = r∗ + From (A.4), (Pn − P )h ≤
1 P h + CKt K −1
for all K > 1.
If P h ≤ t, choose K = 2 and get (Pn − P )h ≤ Ct. If P h > t, choose K = 1 + gives √ (Pn − P )h ≤ C P h t + Ct.
p P h/t, which
Therefore, simultaneously for all h ∈ H, r (Pn − P )h ≤ C
Phu u + n n
! .
(A.6)
Similarly, (A.5) gives (P − Pn )h ≤
1 Pn h + CKt K −1
for all K > 1.
Optimizing in the same way, now using Pn h, yields ! r Pn h u u (P − Pn )h ≤ C + n n
(A.7)
simultaneously for all h ∈ H. This is the desired empirical-radius lower-tail bound. Notice that it was obtained from the two-sided relative deviation theorem for the nonnegative class H, not by applying an upper-tail theorem to −H. Finally, rescale from B = 1 to general B. If Y = X/B and h̃η/B (Y ) = (Y − η/B)+ , then hη (X) = B h̃η/B (Y ),
P hη = BP h̃η/B .
Multiplying (A.6) and (A.7) by B gives r (Pn − P )hη ≤ C
31
B P hη u Bu + n n
! ,
Mansouri
and r (P − Pn )hη ≤ C
B Pn hη u Bu + n n
! .
This proves both claims.
Appendix B. Additional details on the exponential mechanism For completeness, recall the standard expected utility guarantee of the exponential mechanism (McSherry and Talwar, 2007) used in the finite-class upper bound. If a finite-range score q(S, r) has sensitivity ∆q and the exponential mechanism samples r with probability proportional to exp(εq(S, r)/(2∆q )), then h i 2∆ q (log M + 1). E max q(S, r) − q(S, rb) | S ≤ r ε Using q = −b ρ gives the displayed empirical excess bound.
Appendix C. Constants in the scalar lower bound The proof of Theorem 3.2 is intentionally stated with universal constants. One admissible calibration is as follows. Let p = c1 min{τ, 1/(εn)} and k = ⌈4np⌉. Since ε ≤ 1, kε ≤ (4np + 1)ε ≤ 4c1 + 1. Thus, for c1 a small fixed numerical constant, e−kε ≥ e−(4c1 +1) . Since P0n (E) ≥ 7/8 and P (K ≤ k) ≥ 3/4, pure DP gives 7 1 3 P1n (E) ≥ e−(4c1 +1) > , 4 8 8 contradicting P1n (E) ≤ 1/8. In the approximate case, it suffices to require kδ ≤ 1/8 after adjusting constants.
Appendix D. Why the tail-embedding distribution is a legitimate CVaR instance The embedded loss ℓ(w; (T, Y )) = T a(w; Y ) has a large atom at zero because inactive records use the fixed dummy covariate x⊥ . This is not a pathology; it is exactly the mathematical structure of rare-event learning. The top τ tail of ℓ contains all active examples T = 1 and possibly zero-loss inactive examples to fill the tail. Because inactive examples contribute zero loss and active losses are nonnegative, the CVaR equals the active conditional mean. This is why the embedding is exact and why the lower bound does not depend on approximation or asymptotics. 32
The Privacy Price of Tail-Risk Learning
References C. Acerbi and D. Tasche. On the coherence of expected shortfall. Journal of Banking and Finance, 26(7):1487–1503, 2002. P. Artzner, F. Delbaen, J.-M. Eber, and D. Heath. Coherent measures of risk. Mathematical Finance, 9(3):203–228, 1999. P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. Annals of Statistics, 33(4):1497–1537, 2005. R. Bassily, V. Feldman, K. Talwar, and A. G. Thakurta. Private stochastic convex optimization with optimal rates. Advances in Neural Information Processing Systems, 2019. R. Bassily, A. Smith, and A. G. Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pages 464–473, 2014. S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. D. B. Brown. Large deviations bounds for estimating conditional value-at-risk. Operations Research Letters, 35(6):722–730, 2007. K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12:1069–1109, 2011. D. Chen and G. A. Chua. Differentially private stochastic convex optimization under a quantile loss function. Proceedings of the 40th International Conference on Machine Learning, PMLR 202:4435–4461, 2023. J. Duchi, T. Hashimoto, and H. Namkoong. Distributionally robust losses for latent covariate mixtures. Operations Research, 71(2):649–664, 2023. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. Theory of Cryptography Conference, LNCS 3876:265–284, Springer, 2006. C. Dwork and A. Roth. The Algorithmic Foundations of Differential Privacy. Foundations and Trends in Theoretical Computer Science, 9(3–4):211–407, 2014. J. Gillenwater, M. Joseph, and A. Kulesza. Differentially private quantiles. Proceedings of the 38th International Conference on Machine Learning, PMLR 139:3713–3722, 2021. T. Hashimoto, M. Srivastava, H. Namkoong, and P. Liang. Fairness without demographics in repeated loss minimization. Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1929–1938, 2018. F. McSherry and K. Talwar. Mechanism design via differential privacy. Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pages 94–103, 2007. 33
Mansouri
Z. Mhammedi, B. Guedj, and R. C. Williamson. PAC-Bayesian bound for the conditional value at risk. Advances in Neural Information Processing Systems, 2020. D. K. Mulumudi, P. Manupriya, G. Aminian, and A. Raj. On the generalization and robustness in conditional value-at-risk. arXiv preprint arXiv:2602.18053, 2026. R. T. Rockafellar and S. Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2(3):21–41, 2000. R. T. Rockafellar and S. Uryasev. Conditional value-at-risk for general loss distributions. Journal of Banking and Finance, 26(7):1443–1471, 2002. A. Ruszczyński and A. Shapiro. Optimization of convex risk functions. Mathematics of Operations Research, 31(3):433–452, 2006. A. Shapiro. On Kusuoka representation of law invariant risk measures. Mathematics of Operations Research, 38(1):142–152, 2013. A. Smith. Privacy-preserving statistical estimation with optimal convergence rates. Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 813–821, 2011. A. Takeda and T. Kanamori. A robust approach based on conditional value-at-risk measure to statistical learning problems. European Journal of Operational Research, 198(1):287–296, 2009. P. S. Thomas and E. Learned-Miller. Concentration inequalities for conditional value at risk. Proceedings of the 36th International Conference on Machine Learning, PMLR 97:6225–6233, 2019. A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes: With Applications to Statistics. Springer, 1996. D. Xu, M. Ding, Z. Ma, H. Xie, Y. Tao, A. Slaitane, and D. Wang. Differentially private non-convex distributionally robust optimization. arXiv preprint arXiv:2602.16155, 2026. X. Zhou and R. Bassily. Differentially private worst-group risk minimization. Proceedings of the 41st International Conference on Machine Learning, PMLR 235:61783–61803, 2024.
34