Computing Monetary Risk Measures in Linear Time
2026-07-06 • Machine Learning
Machine LearningMathematical Software
AI summaryⓘ
The authors present new fast methods to calculate popular risk measures called Value-at-Risk (VaR) and Conditional-Value-at-Risk (CVaR) for situations where outcomes have discrete probabilities. They introduce QuickVaR, an algorithm inspired by Quickselect, to efficiently find VaR, and then use it to develop QuickDivergence for CVaR and similar risk measures. Their approaches run much faster than traditional methods, especially for large datasets. They also provide code for these algorithms online.
Value-at-RiskConditional-Value-at-RiskQuickselect algorithmDiscrete random variableRisk measuresPolymatroid optimizationϕ-divergenceAlgorithm efficiencyNumerical algorithms
Authors
Palash Agrawal, Gersi Doko, Maeve Burwell, Marek Petrik
Abstract
Monetary risk measures have gained popularity for expressing decision-makers' risk aversion. Value-at-Risk (VaR) and Conditional-Value-at-Risk (CVaR), in particular, are used commonly for this purpose. This paper proposes new efficient algorithms to compute these risk measures for a discrete random variable in expected linear time with respect to the size of its domain. First, we propose a QuickVaR algorithm that computes the VaR of a discrete random variable. Then, we leverage QuickVaR to propose QuickDivergence, an algorithm for computing a class of $\varphi$-divergence risk measures, including the popular CVaR risk measure. The QuickVaR algorithm adapts the well-known Quickselect algorithm, while QuickDivergence builds on polymatroid optimization algorithms. Numerical results show that our new algorithms offer an order-of-magnitude speedup for large domains, and a library implementation of the algorithms is available at https://github.com/RiskAverseRL/RiskMeasures.jl.