Pith. sign in

REVIEW 4 minor 43 references

Computing Monetary Risk Measures in Linear Time

T0 review · 0 major / 4 minor · reviewed 2026-07-11 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read VaR, CVaR and TVaR of a discrete random variable can be computed in expected linear time by adapting quickselect and exploiting a piecewise-linear capacity.

desk verdict Clean expected-linear-time algorithms for discrete VaR and for CVaR/TVaR via an EWS polymatroid reduction; proofs and code look solid, impact is practical rather than conceptual. read the letter →

arxiv 2607.05078 v1 pith:N75EWQW2 submitted 2026-07-06 cs.LG cs.MSstat.AP

Palash Agrawal , Gersi Doko , Maeve Burwell , Marek Petrik This is my paper
classification cs.LGcs.MSstat.AP
keywords Value-at-RiskConditional-Value-at-Riskφ-divergenceriskmeasurespolymatroidoptimizationlinear-timealgorithmsquickselectEWScapacity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Standard ways of evaluating Value-at-Risk and Conditional-Value-at-Risk on a finite sample sort the outcomes, costing a logarithmic factor that becomes expensive when the same risk measure is evaluated repeatedly inside a learning or planning loop. This paper shows that the sort can be avoided. QuickVaR finds the VaR quantile by a randomized three-way partition that mirrors quickselect and finishes in expected linear time. QuickDivergence then uses that quantile to solve the linear program that defines any coherent risk measure whose capacity is element-wise separable (a simple two-piece linear function of probability mass). Both CVaR and the related Total-Value-at-Risk belong to this class, so they inherit the same linear bound. Numerical checks on uniform, sparse and portfolio-return data confirm order-of-magnitude speed-ups once the support grows past a few million atoms, with no penalty on small instances.

What carries the argument

The EWS (element-wise-separable) capacity g(x) = min{c + m·x, 1}. Because it is piecewise linear, the greedy assignment on a sorted support collapses to a single threshold that QuickVaR already computes, removing the need for a full sort.

What would settle it

Implement both the classical sort-based CVaR and QuickDivergence on identical large discrete samples (n ≥ 10^7) drawn from a non-degenerate distribution; if the observed wall-clock ratio fails to grow like log n, or if the two algorithms ever return different numeric values, the claim is false.

Watch

Extended reading notes

Core claim

For any discrete random variable the VaR value is the unique probability atom that straddles the risk level α; that atom can be located by a quickselect-style partition in expected O(n) time. When the risk measure is the linear optimization over a polymatroid whose capacity is of the special EWS form min{c + m·mass, 1}, the same partial order already supplies the greedy solution, so CVaR and TVaR are likewise linear-time.

Load-bearing premise

The linear-time claim for risk measures beyond VaR holds only when the capacity function is exactly the two-piece linear EWS form; measures whose capacity is not of that shape still require a sort.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper develops expected-linear-time algorithms for evaluating discrete monetary risk measures. QuickVaR (Algorithm 3.1) adapts randomized Quickselect with a three-way Dutch-flag partition to return VaR_α of a discrete random variable; Theorems 3.1 and 3.4 establish correctness via an inductive invariant (Lemma 3.3) and an O(n) expected-time recurrence identical to classic selection analysis. QuickDivergence (Algorithm 4.2) then solves linear minimization over normalized polymatroids whose capacity is Element-Wise-Separable (EWS, Definition 4.3), again in expected O(n) time (Theorem 4.5). Propositions 4.6–4.7 verify that both CVaR and the authors’ TVaR admit EWS capacities, so both inherit the linear-time bound. Empirical timings on synthetic and portfolio data, together with a public Julia library, confirm order-of-magnitude speed-ups for large domains.

Significance. If the claims hold, the work removes a logarithmic bottleneck that appears in every iteration of risk-averse RL, robust MDP, and large-scale portfolio optimization. The contribution is concrete: a clean reduction of a practically important subclass of φ-divergence risk measures to selection plus a structural polymatroid property, accompanied by complete proofs, reproducible code, and timings that match the asymptotic prediction. The EWS restriction is stated explicitly, so the result is not oversold; it still covers the two most widely used coherent risk measures (VaR and CVaR) and a useful lower bound on EVaR.

minor comments (4)
  1. Remark 3.5 correctly notes that weighted-median algorithms return the lower quantile; a one-sentence pointer to the precise difference between q^{+}_α and q^{-}_α would help readers who know only the median literature.
  2. Figure 2 uses log-log axes; adding a short note that the observed slope is consistent with O(n) versus O(n log n) would make the visual claim self-contained.
  3. The non-recursive listing (Algorithm A.3) is useful for implementers; a brief remark that it is the version used in the public library would clarify the experimental setup.
  4. Table 1 lists EVaR but the linear-time claim does not apply to it; a parenthetical “not EWS” would prevent casual misreading.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: linear-time claims rest on self-contained selection and polymatroid arguments, not on fitted parameters or load-bearing self-definitions.

full rationale

The paper's central results (Theorems 3.1, 3.4, 4.5) are algorithmic correctness and complexity statements. QuickVaR is obtained by adapting the classic quickselect recurrence (explicitly compared to Horowitz et al.) together with a discrete-VaR characterization (Lemma 3.2) that is proved from the definition (1); the recursive invariant (Lemma 3.3) and the expected-time bound follow by induction and the standard average-case analysis of random pivots. QuickDivergence likewise reduces linear optimization over an EWS polymatroid to a single call to QuickVaR plus an O(n) assignment that is shown, case by case, to reproduce the classical greedy solution (Algorithm 4.1 / Korte-Vygen). The EWS structural restriction (Definition 4.3) is verified algebraically for CVaR and TVaR (Propositions 4.6-4.7) from their known dual formulations; the paper never claims the same for EVaR or arbitrary φ-divergences. Self-citations supply only background definitions of risk measures and earlier application contexts; none of them is used to justify the linear-time claims or uniqueness of the algorithms. There are no fitted constants, no self-referential definitions of the target quantities, and no renaming of known empirical patterns. The derivation is therefore self-contained against external benchmarks and exhibits no circular reduction.

Assumptions & free parameters 0 free parameters · 3 assumptions · 2 invented entities

The work rests on standard algorithmic and convex-analysis facts plus one structural restriction (EWS capacities) that the authors introduce to obtain linearity. No free parameters are fitted; the only invented notion is the EWS class itself, which is definitional rather than ontological.

assumptions (3)
  • standard math Quickselect-style random pivot yields expected linear time for selection (Horowitz et al. 1998, Thm 3.3)
    Used verbatim for the runtime proof of QuickVaR (Thm 3.4).
  • domain assumption Coherent comonotonic risk measures equal linear optimization over a normalized polymatroid (Föllmer & Schied, Cor. 4.88 / Thm 4.94)
    Proposition 4.2; the entire QuickDivergence reduction rests on this classical representation.
  • ad hoc to paper A capacity of the form g(1^ opμ_A) with g(x)=min{c+m x,1} is submodular and defines a valid polymatroid (Def. 4.3, Prop. 4.4)
    The EWS restriction is introduced by the authors; without it the linear-time claim fails.
invented entities (2)
  • EWS (Element-Wise-Separable) capacity functions
    purpose: Identify the precise structural subclass of polymatroids for which sorting can be replaced by a single QuickVaR call.
    Definition 4.3; purely definitional, no physical or statistical entity is postulated.
  • TVaR (Total-Value-at-Risk) capacity independent evidence
    purpose: Give a second concrete EWS example beyond CVaR and illustrate the lower bound on EVaR.
    Eq. (5) and Prop. 4.7; the measure itself appears in earlier robust-optimization literature, but the capacity form is new here.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computing Monetary Risk Measures in Linear Time." pith.science (2026). https://pith.science/paper/N75EWQW2

@misc{pith2026260705078,
  author       = {Pith},
  title        = {Pith review of: Computing Monetary Risk Measures in Linear Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N75EWQW2}},
  note         = {Machine review of arXiv:2607.05078}
}
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.

Figures

Figures reproduced from arXiv: 2607.05078 by the authors.

Figure 1
Figure 1. Comparison of risk measure values for a normal distribution with mean [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Comparison of runtime of the algorithms for samples from a [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

43 extracted references · 5 linked inside Pith

  1. [1]

    2021 , booktitle =

    Andersen Ang and Jianzhu Ma and Nianjun Liu and Kun Huang , title =. 2021 , booktitle =

    2021

  2. [2]

    and Hopcroft, John E

    Aho, Alfred V. and Hopcroft, John E. and Ullman, Jeffrey D. , biburl =

  3. [3]

    Computer Algorithms , year =

    Horowitz, Ellis and Sahni, Sartaj and Rajasekaran, Sanguthevar , publisher =. Computer Algorithms , year =

  4. [4]

    2004 , publisher=

    Convex Optimization , author=. 2004 , publisher=

    2004

  5. [5]

    2009 , publisher=

    Introduction to Algorithms , author=. 2009 , publisher=

    2009

  6. [6]

    and Barto, Andrew G

    Sutton, Richard S. and Barto, Andrew G. , biburl =. Reinforcement Learning: An Introduction , url =

  7. [7]

    2012 , number =

    Journal of Optimization Theory and Applications , title =. 2012 , number =

    2012

  8. [8]

    2011 , publisher=

    Combinatorial optimization: Theory and Algorithms , author=. 2011 , publisher=

    2011

Show all 43 references
  1. [9]

    and Schweizer, Nikolaus , journal =

    Kruse, Thomas and Schneider, Judith C. and Schweizer, Nikolaus , journal =. A Toolkit for Robust Risk Assessment Using F-Divergences , year =

  2. [10]

    Data-Driven Stochastic Programming Using Phi-Divergences , year =

    Bayraksan, G. Data-Driven Stochastic Programming Using Phi-Divergences , year =. The

  3. [11]

    Stochastic Finance: Introduction in Discrete Time , year =

    Follmer, Hans and Schied, Alexander , publisher =. Stochastic Finance: Introduction in Discrete Time , year =

  4. [12]

    Adam and V

    L. Adam and V. Mácha , title =. 2019 , archiveprefix =. 1905.03488 , eprinttype =

    2019 arXiv

  5. [13]

    2014 , publisher =

    Lectures on Stochastic Programming: Modeling and Theory , author =. 2014 , publisher =

    2014

  6. [14]

    Tyrrell and Wets, Roger J-B , publisher =

    Rockafellar, R. Tyrrell and Wets, Roger J-B , publisher =. Variational Analysis , year =

  7. [15]

    and Thomas, Joy A

    Cover, Thomas M. and Thomas, Joy A. , title =. 1991 , address =

    1991

  8. [16]

    An Information-Theoretic Approach to Constructing Coherent Risk Measures , year =. 2011

    2011

  9. [17]

    Bayesian Regret Minimization in Offline Bandits , year =

    Petrik, Marek and Tennenholtz, Guy and Ghavamzadeh, Mohammad , booktitle =. Bayesian Regret Minimization in Offline Bandits , year =

  10. [18]

    Fast Projection onto the Simplex and the

    Condat, Laurent , journal =. Fast Projection onto the Simplex and the. 2016 , number =

    2016

  11. [19]

    Efficient Projections onto the L1-Ball for Learning in High Dimensions , year =

    Duchi, John and. Efficient Projections onto the L1-Ball for Learning in High Dimensions , year =. International

  12. [20]

    , booktitle =

    Lim, Cong Han and Wright, Stephen J. , booktitle =. Efficient. 2016 , pages =

    2016

  13. [21]

    Projection onto the Probability Simplex:

    Wang, Weiran and. Projection onto the Probability Simplex:. 2013 , archiveprefix =. 1309.1541 , eprinttype =

    2013 arXiv

  14. [22]

    Fast Algorithms for

    Behzadian, Bahram and Petrik, Marek and Ho, Chin Pang , booktitle =. Fast Algorithms for

  15. [23]

    Ho, Chin Pang and Petrik, Marek and Wiesemann, Wolfram , booktitle =. Fast. 2018 , pages =

    2018

  16. [24]

    Partial Policy Iteration for

    Ho, Chin Pang and Petrik, Marek and Wiesemann, Wolfram , journal =. Partial Policy Iteration for. 2021 , pages =

    2021

  17. [25]

    Robust Phi-Divergence

    Ho, Chin Pang and Petrik, Marek and Wiesemann, Wolfram , booktitle =. Robust Phi-Divergence. 2022 , archiveprefix =

    2022

  18. [26]

    , journal =

    Iyengar, Garud N. , journal =. Robust Dynamic Programming , year =

  19. [27]

    Robust Control of

    Nilim, Arnab and El Ghaoui, Laurent , journal =. Robust Control of. 2005 , number =

    2005

  20. [28]

    A Discipline of Programming , year =

    Dijkstra, Edsger Wybe , publisher =. A Discipline of Programming , year =

  21. [29]

    2012 , edition =

    Korte, Bernhard and Vygen, Jens , title =. 2012 , edition =

    2012

  22. [30]

    arXiv preprint arXiv:2403.18972 , year=

    Risk-aware robotics: Tail risk measures in planning, control, and verification , author=. arXiv preprint arXiv:2403.18972 , year=

    arXiv

  23. [31]

    Robotics Research: The 18th International Symposium ISRR , pages=

    How should a robot assess risk? towards an axiomatic theory of risk in robotics , author=. Robotics Research: The 18th International Symposium ISRR , pages=. 2020 , organization=

    2020

  24. [32]

    Sensors , volume=

    A review on traversability risk assessments for autonomous ground vehicles: Methods and metrics , author=. Sensors , volume=. 2024 , publisher=

    2024

  25. [33]

    2018 , publisher =

    Jeffrey Bilmes , title =. 2018 , publisher =

    2018

  26. [34]

    Energy Economics , title =

    Inzunza, Andr. Energy Economics , title =. 2016 , pages =

    2016

  27. [35]

    , booktitle =

    Barahona, Francisco and Ettl, Markus and Petrik, Marek and Rimshnick, Peter M. , booktitle =. Agile Logistics Simulation and Optimization for Managing Disaster Responses. , year =

  28. [36]

    Entropic Risk Optimization in Discounted

    Hau, Jia Lin and Petrik, Marek and Ghavamzadeh, Mohammad , booktitle =. Entropic Risk Optimization in Discounted

  29. [37]

    On Dynamic Programming Decompositions of Static Risk Measures in

    Hau, Jia Lin and Delage, Erick and Ghavamzadeh, Mohammad and Petrik, Marek , booktitle =. On Dynamic Programming Decompositions of Static Risk Measures in. 2023 , archiveprefix =. 2304.12477 , primaryclass =

    2023 arXiv

  30. [38]

    Notes on Financial Risk and Analytics with

    Privault, Nicolas , institution =. Notes on Financial Risk and Analytics with

  31. [39]

    Risk-Averse Total-Reward

    Su, Xihong and. Risk-Averse Total-Reward. 2025 , copyright =

    2025

  32. [40]

    Q-Learning for Quantile

    Hau, Jia Lin and Delage, Erick and Derman, Esther and Ghavamzadeh, Mohammad and Petrik, Marek , booktitle =. Q-Learning for Quantile. 2025 , archiveprefix =. 2410.24128 , shorttitle =

    2025 arXiv

  33. [41]

    Spectral Measures of Risk:

    Acerbi, Carlo , journal =. Spectral Measures of Risk:. 2002 , number =

    2002

  34. [42]

    Distributionally Robust Stochastic Programming , year =

    Shapiro, Alexander , journal =. Distributionally Robust Stochastic Programming , year =

  35. [43]

    Concentration Inequalities: A Nonasymptotic Theory of Independence , shorttitle =

    Boucheron, St. Concentration Inequalities: A Nonasymptotic Theory of Independence , shorttitle =

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.