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

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

Source: arXiv cs.LG | 2026-05-18