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 $\tau$, the privacy-relevant sample size is not $n$, but $n\tau$; equivalently, the effective private tail sample size is $\epsilon n\tau$. 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 $\mathrm{\Theta }(B\min \{1,(n\tau {)}^{-1\mathrm{/}2}+(\epsilon n\tau {)}^{-1}\})$, and finite classes of size $M$ have rate $\mathrm{\Theta }(B\min \{1,\sqrt{\log (2M)\mathrm{/}(n\tau )}+\log (2M)\mathrm{/}(\epsilon n\tau )\})$. These complete rates hold under pure DP, and their lower bounds extend to approximate DP in the stated small-$\delta$ regimes. For convex Lipschitz learning, modular upper and lower reductions show that the CVaR-specific privacy term necessarily scales as $1\mathrm{/}(\epsilon n\tau )$, with dimension dependence inherited from private stochastic convex optimization. Together, these results identify ordinary private learning on $\mathrm{\Theta }(n\tau )$ informative tail records as the canonical hard subproblem inside private CVaR learning.