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 $Θ(B min{1,(nτ)^{-1/2}+(εnτ)^{-1}})$, and finite classes of size $M$ have rate $Θ(B min{1,sqrt{log(2M)/(nτ)}+log(2M)/(εnτ)})$. These complete rates hold under pure […]