📊 statistics

Computing Monetary Risk Measures in Linear Time

本文介绍了 QuickVaR 和 QuickDivergence，这两种新算法能够以期望线性时间计算离散随机变量的风险价值（Value-at-Risk）和 $\phi$ -散度风险度量（包括 CVaR），并实现了较现有方法的显著加速。

原作者： Palash Agrawal, Gersi Doko, Maeve Burwell, Marek Petrik

发布于 2026-07-07

📖 1 分钟阅读☕ 轻松阅读

原作者： Palash Agrawal, Gersi Doko, Maeve Burwell, Marek Petrik

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位正在风暴中驾驶船只的船长。你面前有成千上万种可能的波浪高度（有些很小，有些则极其巨大）。为了做出安全的决策，你需要知道：“在 95% 的情况下，我可能面临的最坏波浪高度是多少？”或者说：“如果运气很差，那些最坏情况下的平均高度是多少？”

在数学和金融领域，这些问题是通过**风险度量（Risk Measures）**来回答的。其中最著名的两个概念是 VaR（风险价值）和 CVaR（条件风险价值）。

长期以来，为了计算这成千上万种可能性中的答案，就像是为了找一本特定的书，必须先将整个图书馆按字母顺序排列好。这种方法虽然可行，但非常缓慢且繁琐，尤其是当“图书馆”（数据）变得越来越大时。

本文介绍了两个名为 QuickVaR 和 QuickDivergence 的新工具，它们速度极快，解决了这个问题，且无需预先对整个“图书馆”进行排序。

旧方法：“全量排序”法

传统上，为了找到风险水平，计算机必须将所有可能的结果按从小到大的顺序进行排序。

比喻： 想象你有一堆乱七八糟的 100 万张扑克牌。为了找到第 950,000 张牌（即标记出前 5% 的那张牌），旧方法会强迫你先把每一张牌都按顺序整齐地摆放好。
问题： 排序非常耗时。如果扑克牌的数量增加一倍，所需的时间并不仅仅是增加一倍；由于“排序”这一步骤的存在，耗时会增长得更快。

新方法：“快速挑选”法

作者提出了一种受经典的“快速选择”（Quickselect）技巧启发的新方法。

比喻： 与其对整堆牌进行排序，不如随机抽取一张牌，然后问自己：“我要找的那张牌比这张大还是比这张小？”
- 如果你在寻找一张高数值的牌，而你随机抽到的牌很小，那么你立刻就能知道，你可以直接扔掉所有比这张牌小的牌。你不需要对它们进行排序，只需要忽略它们即可。
- 你重复这个过程，不断缩小范围，直到找到你需要的确切那张牌。
结果： 你是通过“观察”牌来找到答案，而不是通过“整理”牌。这种方式要快得多。

本文实际研究的内容

本文介绍了基于这种“快速挑选”思想的两种特定算法：

QuickVaR： 它负责找到那个特定的“切分点”（即 VaR）。这就像是在寻找那道精确的波浪高度界限，它将“常态”风暴与“灾难性”风暴区分开来。
QuickDivergence： 这是一个基于 QuickVaR 的更高级工具。它计算的是一类更广泛的风险度量（包括 CVaR，即观察最坏情况下的平均值）。它将问题视为一个谜题，通过使用一种特殊的数学捷径，让你完全跳过排序步骤。

结果：为航行加速

作者将这些新工具与旧的排序方法进行了对比测试。

发现： 对于较小的数据列表，新工具与旧方法一样快。但对于大型列表（这在现实世界的金融、机器人技术和灾难规划中非常常见），新工具的速度要快出几个数量级。
类比： 如果旧方法需要 10 分钟才能整理完 100 万本书的图书馆，那么新方法只需几秒钟就能找到那本书。随着“图书馆”规模的扩大，两种方法之间的差距会变得越来越大。

为什么这很重要（根据论文所述）

论文指出，这些算法对于机器人技术、金融和基础设施维护等领域至关重要。在这些领域，计算机通常需要基于海量数据做出决策，并且需要极其迅速地计算风险，有时甚至需要在学习过程的每一步中都进行计算。

通过消除对数据进行排序的需求，这些新算法消除了一个主要的“瓶颈”，使得决策系统能够在不损失准确性的情况下运行得更快。

简而言之： 本文为我们提供了一种方法，让我们无需先对庞大的可能性列表进行排序，就能找到其中的“最坏情况场景”，从而显著提升了处理大数据问题时的风险计算速度。

技术摘要：线性时间内计算货币风险度量

问题陈述

货币风险度量（如风险价值 VaR 和条件风险价值 CVaR）对于在机器人、金融、基础设施维护和灾难响应等领域进行风险厌恶建模至关重要。在诸如风险厌恶强化学习之类的应用中，这些度量必须被频繁计算，通常是在算法的每一次迭代中。

计算离散随机变量这些度量的标准方法涉及对输入概率分布和结果值进行排序。这一排序步骤引入了 $\Omega(n \log n)$ 的计算复杂度，其中 $n$ 是概率空间的大小。对于大规模问题，这种排序瓶颈成为了显著的计算障碍。本文旨在解决开发更高效算法的需求，即在不牺牲准确性的情况下，实现 $O(n)$ 的线性时间计算。

方法论

作者提出了两种新算法：QuickVaR 和 QuickDivergence，通过避免对输入数据进行全排序，实现了期望的线性时间复杂度。

1. QuickVaR：线性时间 VaR 计算

第一种算法用于计算离散随机变量的风险价值（VaR）。

核心机制： QuickVaR 改编了著名的 Quickselect 算法。它不是对随机变量的结果进行完全排序，而是使用随机化枢轴（pivot）选择策略对索引进行部分排序。
过程：
1. 从当前索引范围内均匀随机选择一个枢轴值。
2. 将输入数组划分为三部分：小于枢轴的值、等于枢轴的值以及大于枢轴的值（使用荷兰国旗算法）。
3. 计算“小于”组和“等于”组的累积概率质量。
4. 根据目标风险水平 $\alpha$ ，算法递归地缩小搜索范围，定位到包含 VaR 值的组。
复杂度： 其期望运行时间为 $O(n)$ ，相比现有技术在对数因子上实现了提升。

2. QuickDivergence：线性时间 $\phi$ -散度风险度量

第二种算法计算一类 $\phi$ -散度风险度量，特别针对 CVaR 以及一种提出的度量——总风险价值（Total-Value-at-Risk, TVaR）。

理论基础： 作者利用了以下事实：相干（coherent）共单调（comonotonic）货币风险度量可以被表述为在 拟阵（polymatroids） 上的线性优化问题。标准的拟阵优化需要对输入进行排序（ $\Omega(n \log n)$ ）。
EWS 性质： 文中确定了一个被称为**元素级可分（Element-Wise-Separable, EWS）**的结构性条件，该条件用于定义这些拟阵的容量函数。对于满足 EWS 性质的风险度量，可以在无需排序的情况下找到最优解。
过程：
1. 算法利用 QuickVaR 对输入向量进行部分排序，以识别关键阈值 $v$ 。
2. 它通过根据结果是否小于、等于或大于 $v$ 来分配权重，并处理一个特定的“最小值”元素（ $k_{min}$ ），从而构建最优概率分布 $q^*$ ，以确保满足拟阵的约束条件。
适用性： 作者证明了 CVaR 和 TVaR 均满足 EWS 性质，从而允许以期望 $O(n)$ 的时间进行计算。

核心贡献

QuickVaR 算法： 一种通过泛化 Quickselect 算法来计算 VaR 的新型线性时间算法。
QuickDivergence 框架： 一个用于计算 $\phi$ -散度风险度量（包括 CVaR 和 TVaR）的线性时间框架，通过将其归约为具有 EWS 容量函数的拟阵上的线性最小化问题。
理论保证： 本文为两种算法提供了正确性和期望 $O(n)$ 时间复杂度的形式化证明，并将其与基于排序方法的 $\Omega(n \log n)$ 下界进行了对比。
新风险度量定义： 本文正式定义并分析了作为 $\phi$ -散度风险度量的 TVaR（总风险价值），确立了其与熵风险价值（EVaR）的关系，并证明了它为 EVaR 提供了一个下界。
开源实现： 作者提供了一个实现这些算法的 Julia 库 (RiskMeasures.jl)。

实验结果

作者在合成数据集和现实数据集上评估了这些算法：

合成数据： 在规模从 $10^6$ 到 $10^7$ 的均匀分布和稀疏随机变量实验中，线性时间算法（QVaR, QCVaR, QTVaR）表现出比其基于排序的对应算法显著更快的速度。随着问题规模 $n$ 的增加，性能差距不断扩大，这与消除对数因子的理论预期一致。
现实场景：
- 股市场景： 在金融投资组合收益模拟中，线性时间算法显示出持续的加速效果（例如，QVaR 为 0.13ms，而 VaR 为 0.37ms）。
- 小规模问题： 在较小领域（ $n=1000$ 至 $10,000$）的测试确认，线性时间算法即使在小规模下也优于基于排序的方法，且未产生任何针对小输入的惩罚。
结论： 结果证实，理论上的加速转化为了实际的性能提升，为大规模领域提供了数量级的改进。

意义与主张

本文声称其主要贡献是将常见货币风险度量的计算复杂度从 $O(n \log n)$ 降低到了期望的 $O(n)$ 。这一改进之所以重要，是因为：

它消除了在风险厌恶强化学习等迭代算法中反复评估风险度量时的一个主要计算瓶颈。
它使得高效处理现实应用（机器人、金融、基础设施）中常见的超大规模离散随机变量成为可能。
所提算法实现简单，可以集成到现有工作流中，且不会对较小规模的问题造成性能损失。

作者指出，虽然此前已有关于结构化优化（如单纯形投影）的线性时间算法的研究，但本研究专门针对货币风险度量的计算，并确立了其在特定条件下的线性时间可解性。他们最后指出，未来的工作方向是将这些快速算法扩展到其他风险度量，如 EVaR 和分位数（Expectile）。