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

arXiv: https://arxiv.org/abs/2605.16219 · HTML: https://mlsanity.com/paper/2605.16219/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 27 references that are in the map.
- First posted on arXiv 15 May 2026.

## Builds on (most cited first, 8 of 8)

- [Fairness Without Demographics in Repeated Loss Minimization](https://mlsanity.com/paper/1806.08010/) (2018)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Distributionally Robust Losses for Latent Covariate Mixtures](https://mlsanity.com/paper/2007.13982/) (2020)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [PAC-Bayesian Bound for the Conditional Value at Risk](https://mlsanity.com/paper/2006.14763/) (2020)
- [Differentially Private Worst-group Risk Minimization](https://mlsanity.com/paper/2402.19437/) (2024)
- [Differentially Private Non-convex Distributionally Robust Optimization](https://mlsanity.com/paper/2602.16155/) (2026)
- [On the Generalization and Robustness in Conditional Value-at-Risk](https://mlsanity.com/paper/2602.18053/) (2026)

## Abstract (arXiv)

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.