mlsanityData to 14 Oct 2026

Computing Monetary Risk Measures in Linear Time

arXiv 2607.05078 ↗First posted 6 Jul 2026cs.LG cs.MS stat.APcited by 0

Not on the map. Why?

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.

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

39 of 47 references.

References · 39

  1. 2021Learning Transferable Visual Models From Natural Language Supervisioncited by 33,744
  2. 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,375
  3. 2024Qwen2-VL: Enhancing Vision-Language Model's Perception of the World at Any Resolutioncited by 4,234
  4. 2017ScanNet: Richly-annotated 3D Reconstructions of Indoor Scenescited by 3,117
  5. 2019SuperGlue: Learning Feature Matching with Graph Neural Networkscited by 1,443
  6. 2017SuperPoint: Self-Supervised Interest Point Detection and Descriptioncited by 1,320
  7. 2017Vision-and-Language Navigation: Interpreting visually-grounded navigation instructions in real environmentscited by 1,027
  8. 2015NetVLAD: CNN architecture for weakly supervised place recognitioncited by 941
  9. 2018From Coarse to Fine: Robust Hierarchical Localization at Large Scalecited by 559
  10. 2022OpenScene: 3D Scene Understanding with Open Vocabulariescited by 559
  11. 2023LERF: Language Embedded Radiance Fieldscited by 543
  12. 2019ScanRefer: 3D Object Localization in RGB-D Scans using Natural Languagecited by 452
27 more
  1. 2023ConceptGraphs: Open-Vocabulary 3D Scene Graphs for Perception and Planningcited by 365
  2. 2021ScanQA: 3D Question Answering for Spatial Scene Understandingcited by 346
  3. 2019REVERIE: Remote Embodied Visual Referring Expression in Real Indoor Environmentscited by 333
  4. 2022SQA3D: Situated Question Answering in 3D Scenescited by 314
  5. 2020A Recurrent Vision-and-Language BERT for Navigationcited by 302
  6. 20193D Scene Graph: A Structure for Unified Semantics, 3D Space, and Cameracited by 281
  7. 2023NavGPT: Explicit Reasoning in Vision-and-Language Navigation with Large Language Modelscited by 280
  8. 2016DSAC - Differentiable RANSAC for Camera Localizationcited by 266
  9. 2019Vision-and-Dialog Navigationcited by 250
  10. 2021Patch-NetVLAD: Multi-Scale Fusion of Locally-Global Descriptors for Place Recognitioncited by 238
  11. 2020Learning 3D Semantic Scene Graphs from 3D Indoor Reconstructionscited by 208
  12. 20233D-VisTA: Pre-trained Transformer for 3D Vision and Text Alignmentcited by 204
  13. 2021Back to the Feature: Learning Robust Camera Localization from Pixels to Posecited by 199
  14. 2019RIO: 3D Object Instance Re-Localization in Changing Indoor Environmentscited by 188
  15. 2021SceneGraphFusion: Incremental 3D Scene Graph Prediction from RGB-D Sequencescited by 163
  16. 2022Rethinking Visual Geo-localization for Large-Scale Applicationscited by 163
  17. 2017Geometry-Aware Learning of Maps for Camera Localizationcited by 161
  18. 2023MixVPR: Feature Mixing for Visual Place Recognitioncited by 161
  19. 2017Learning Less is More - 6D Camera Localization via 3D Surface Regressioncited by 146
  20. 2023Accelerated Coordinate Encoding: Learning to Relocalize in Minutes using RGB and Posescited by 107
  21. 2023OrienterNet: Visual Localization in 2D Public Maps with Neural Matchingcited by 84
  22. 2022Text2Pos: Text-to-Point-Cloud Cross-Modal Localizationcited by 40
  23. 2024Quality-Aware Image-Text Alignment for Opinion-Unaware Image Quality Assessmentcited by 32
  24. 2023SGAligner : 3D Scene Alignment with Scene Graphscited by 30
  25. 2024SceneGraphLoc: Cross-Modal Coarse Visual Localization on 3D Scene Graphscited by 29
  26. 2024"Where am I?" Scene Retrieval with Languagecited by 15
  27. 2024DiaLoc: An Iterative Approach to Embodied Dialog Localizationcited by 4

Built on by

Not cited yet.