The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimization

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 Theta(B min1,(nτ)-1/2+(ε nτ)-1), and finite classes of size M have rate Theta(B min1,√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 Theta(nτ) informative tail records as the canonical hard subproblem inside private CVaR learning.