Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces efficient algorithms for computing Value-at-Risk (VaR) and Conditional-Value-at-Risk (CVaR) for discrete random variables, achieving expected linear time complexity relative to the size of the variable's domain. The QuickVaR algorithm adapts the Quickselect method, while QuickDivergence extends this approach to a broader class of $\varphi$-divergence risk measures. Numerical evaluations demonstrate that these algorithms provide significant speedups for large domains, making them practical for real-world applications in risk assessment.
Achieving linear time complexity for computing VaR and CVaR could revolutionize risk assessment in finance and decision-making.
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.