Differential privacy faces a core contradiction in learning: to protect privacy, you must add noise to gradients—more noise means better privacy but worse models. CVaR optimization learns tail risk: performance on the worst τ% of samples. Instead of learning well on average, the goal is to ensure the model performs well in the worst cases—a requirement in financial risk control, medical decision-making, and safety-critical autonomous driving.
This theoretical work by Mansouri reveals a simple but important fact: under differential privacy, the effective sample size for CVaR learning is not n, but nτ. If your dataset has 100,000 samples and the tail mass is τ = 5%, only 5,000 samples are genuinely informative for tail-risk learning. Privacy noise impacts estimation at the 5,000-sample level far more than at the 100,000-sample level.
More concretely, the privacy price is:
1/(εnτ)
—an intuitive three-variable product of privacy budget ε, sample size n, and tail mass τ. If any variable shrinks, the price rises. The thinner the tail (smaller τ), the more expensive tail-risk learning becomes—and the relationship is inverse, not linear.
The paper gives complete upper and lower bounds covering scalar estimation, finite hypothesis classes, and convex Lipschitz learning. The lower bound proves that in the approximate DP setting with small δ, the CVaR-specific privacy term must scale as 1/(εnτ), while the dimension penalty follows standard results from private convex optimization.
Open questions
- This is a purely theoretical analysis—are the convergence rates tight?
- Does the same scaling law dominate in non-convex, non-Lipschitz settings such as deep neural networks?
- In practice, when τ is very small (e.g., 0.1%), the privacy price becomes extremely high. Can structural assumptions on tail data distributions (e.g., specific parametric forms) break through this lower bound?
References
1. Mansouri, E. M. (2026). *The Privacy Price of Tail-Risk Learning: Effective Tail Sample Size in Differentially Private CVaR Optimization*. arXiv:2605.16219 [cs.LG]. 2. Dwork, C., & Roth, A. (2014). *The Algorithmic Foundations of Differential Privacy*. Foundations and Trends in Theoretical Computer Science. 3. Rockafellar, R. T., & Uryasev, S. (2000). *Optimization of Conditional Value-at-Risk*. Journal of Risk.