高效计算金融风险度量，速度提升十倍以上。
Computing Monetary Risk Measures in Linear Time
- 基于快速选择与多面体优化，实现线性时间风险计算。
- 在大规模数据集上，算法速度比传统方法快一个数量级。
- 适合金融风控、量化交易等需实时风险评估的场景。
货币风险度量在表达决策者风险偏好方面日益流行，其中价值风险（VaR）和条件价值风险（CVaR）应用广泛。本文提出新算法，在离散随机变量的定义域大小上以期望线性时间计算这些风险度量。首先提出QuickVaR算法，用于计算离散随机变量的VaR；随后利用QuickVaR，设计QuickDivergence算法，用于计算一类φ-分歧风险度量，包括常见的CVaR。QuickVaR借鉴经典快速选择算法，QuickDivergence则基于多面体优化。数值实验表明，新算法在大定义域下可实现数量级提速。算法库已开源：https://github.com/RiskAverseRL/RiskMeasures.jl。
原文摘要 · Abstract (English)
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 $φ$-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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。