Approximate DP

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

This paper characterizes how differential privacy affects the statistical complexity of CVaR (Conditional Value at Risk) optimization, showing that the effective sample size governing private tail-risk learning is εnτ rather than n, where τ is the tail mass. Complete minimax rates are derived for scalar estimation and finite classes under pure DP, with lower bounds extending to approximate DP. For convex Lipschitz learning, the CVaR-specific privacy cost necessarily scales as 1/(εnτ), with dimension dependence inherited from private stochastic convex optimization. The results reduce private CVaR learning to private learning on Θ(nτ) tail records as the canonical hard subproblem.