# Computing Monetary Risk Measures in Linear Time

arXiv: https://arxiv.org/abs/2607.05078 · HTML: https://mlsanity.com/paper/2607.05078/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 39 of its 47 references that are in the map.
- First posted on arXiv 6 Jul 2026.

## Builds on (most cited first, 30 of 39)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Qwen2-VL: Enhancing Vision-Language Model's Perception of the World at Any Resolution](https://mlsanity.com/paper/2409.12191/) (2024)
- [ScanNet: Richly-annotated 3D Reconstructions of Indoor Scenes](https://mlsanity.com/paper/1702.04405/) (2017)
- [SuperGlue: Learning Feature Matching with Graph Neural Networks](https://mlsanity.com/paper/1911.11763/) (2019)
- [SuperPoint: Self-Supervised Interest Point Detection and Description](https://mlsanity.com/paper/1712.07629/) (2017)
- [Vision-and-Language Navigation: Interpreting visually-grounded navigation instructions in real environments](https://mlsanity.com/paper/1711.07280/) (2017)
- [NetVLAD: CNN architecture for weakly supervised place recognition](https://mlsanity.com/paper/1511.07247/) (2015)
- [From Coarse to Fine: Robust Hierarchical Localization at Large Scale](https://mlsanity.com/paper/1812.03506/) (2018)
- [OpenScene: 3D Scene Understanding with Open Vocabularies](https://mlsanity.com/paper/2211.15654/) (2022)
- [LERF: Language Embedded Radiance Fields](https://mlsanity.com/paper/2303.09553/) (2023)
- [ScanRefer: 3D Object Localization in RGB-D Scans using Natural Language](https://mlsanity.com/paper/1912.08830/) (2019)
- [ConceptGraphs: Open-Vocabulary 3D Scene Graphs for Perception and Planning](https://mlsanity.com/paper/2309.16650/) (2023)
- [ScanQA: 3D Question Answering for Spatial Scene Understanding](https://mlsanity.com/paper/2112.10482/) (2021)
- [REVERIE: Remote Embodied Visual Referring Expression in Real Indoor Environments](https://mlsanity.com/paper/1904.10151/) (2019)
- [SQA3D: Situated Question Answering in 3D Scenes](https://mlsanity.com/paper/2210.07474/) (2022)
- [A Recurrent Vision-and-Language BERT for Navigation](https://mlsanity.com/paper/2011.13922/) (2020)
- [3D Scene Graph: A Structure for Unified Semantics, 3D Space, and Camera](https://mlsanity.com/paper/1910.02527/) (2019)
- [NavGPT: Explicit Reasoning in Vision-and-Language Navigation with Large Language Models](https://mlsanity.com/paper/2305.16986/) (2023)
- [DSAC - Differentiable RANSAC for Camera Localization](https://mlsanity.com/paper/1611.05705/) (2016)
- [Vision-and-Dialog Navigation](https://mlsanity.com/paper/1907.04957/) (2019)
- [Patch-NetVLAD: Multi-Scale Fusion of Locally-Global Descriptors for Place Recognition](https://mlsanity.com/paper/2103.01486/) (2021)
- [Learning 3D Semantic Scene Graphs from 3D Indoor Reconstructions](https://mlsanity.com/paper/2004.03967/) (2020)
- [3D-VisTA: Pre-trained Transformer for 3D Vision and Text Alignment](https://mlsanity.com/paper/2308.04352/) (2023)
- [Back to the Feature: Learning Robust Camera Localization from Pixels to Pose](https://mlsanity.com/paper/2103.09213/) (2021)
- [RIO: 3D Object Instance Re-Localization in Changing Indoor Environments](https://mlsanity.com/paper/1908.06109/) (2019)
- [SceneGraphFusion: Incremental 3D Scene Graph Prediction from RGB-D Sequences](https://mlsanity.com/paper/2103.14898/) (2021)
- [Rethinking Visual Geo-localization for Large-Scale Applications](https://mlsanity.com/paper/2204.02287/) (2022)
- [Geometry-Aware Learning of Maps for Camera Localization](https://mlsanity.com/paper/1712.03342/) (2017)
- [MixVPR: Feature Mixing for Visual Place Recognition](https://mlsanity.com/paper/2303.02190/) (2023)

## Abstract (arXiv)

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.