{"ID":5937073,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-09T13:28:50.14143324Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.05078","arxiv_id":"2607.05078","title":"Computing Monetary Risk Measures in Linear Time","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.","short_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...","url_abs":"https://arxiv.org/abs/2607.05078","url_pdf":"https://arxiv.org/pdf/2607.05078v1","authors":"[\"Palash Agrawal\",\"Gersi Doko\",\"Maeve Burwell\",\"Marek Petrik\"]","published":"2026-07-06T13:39:45Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.MS\",\"stat.AP\"]","methods":"[]","has_code":false,"code_links":[{"ID":613955,"CreatedAt":"2026-07-07T03:14:33.014478982Z","UpdatedAt":"2026-07-07T03:14:33.014478982Z","DeletedAt":null,"paper_id":5937073,"paper_url":"https://arxiv.org/abs/2607.05078","paper_title":"Computing Monetary Risk Measures in Linear Time","repo_url":"https://github.com/RiskAverseRL/RiskMeasures.jl","is_official":false,"mentioned_in_paper":false,"mentioned_in_github":true,"github_stars":0}]}