{"id":"6da94004-c0e3-4b65-bb52-aca6152c6e47","arxiv_id":"2607.05078","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"QuickVaR and QuickDivergence compute VaR and EWS φ-divergence risk measures (CVaR, TVaR) in expected O(n) time by avoiding full sorts via Quickselect-style partitioning and polymatroid structure.","lead":"The paper gives expected-linear-time algorithms for VaR and for a class of φ-divergence risk measures (including CVaR and TVaR) on finite discrete random variables. The speedup matters for risk-averse RL and large-scale finance where these measures are evaluated repeatedly on big supports.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The Reader correctly identifies both the strongest claim and the precise scope limitation (EWS). After examining the recursive invariants, the Dutch-flag partition properties, the induction in Lemma 3.3, the four-case equivalence proof of Theorem 4.5, and the capacity constructions for CVaR/TVaR, I find no load-bearing gap that would alter the ACCEPT verdict. The algorithms are standard techniques applied carefully to a newly isolated structural subclass; the mathematics checks out and the empirical/code support is present. Therefore the Reader’s assessment stands unchanged.","tokens_in":19412,"tokens_out":442,"duration_ms":3676,"concrete_test":"Independently re-implement the non-recursive QuickVaR (Algorithm A.3) and QuickDivergence (Algorithm 4.2) and verify that, on a suite of random discrete distributions with known closed-form VaR/CVaR (e.g., two-point and uniform atoms), the returned values match the sorting-based baselines to machine precision while the measured asymptotic slope is consistent with O(n) rather than O(n log n).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims (Theorems 3.1, 3.4, 4.5) rest on standard selection analysis plus a clean structural restriction (EWS capacities, Definition 4.3) that is verified for CVaR and TVaR (Propositions 4.6–4.7). The proofs appear complete: Lemma 3.2–3.3 establish the recursive invariant for QuickVaR, the expected-time recurrence matches the classic quickselect argument, and the four-case matching argument in the proof of Theorem 4.5 shows that Algorithm 4.2 reproduces the greedy polymatroid solution without a full sort. The EWS restriction is explicitly scoped; the paper never claims linear time for EVaR or arbitrary φ-divergences. Empirical results and public code further corroborate the claims. No internal inconsistency or hidden assumption that would undermine the stated theorems was found.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":19682,"tokens_out":583,"duration_ms":4972,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"Table 1 lists EVaR but the linear-time claim does not apply to it; a parenthetical “not EWS” would prevent casual misreading.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a solid systems/algorithms contribution that sits comfortably at the intersection of combinatorial optimization and risk-averse ML. No novelty or citation concerns; the public code and clean proofs make it a low-risk accept."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing worth knowing is that they give expected O(n) algorithms for discrete VaR and for CVaR (and a related TVaR) that actually work, with public Julia code and timings that match the theory. That is immediately usable in risk-averse RL loops where you recompute these measures every iteration.\n\nWhat is new is not the selection idea itself—Quickselect is classical—but the clean recognition that VaR is exactly the upper quantile atom (Lemma 3.2) and that the CVaR and TVaR capacities are Element-Wise-Separable (EWS). That structural fact lets them replace the usual full sort in the greedy polymatroid algorithm with a single QuickVaR call plus a linear pass (Algorithm 4.2, Theorem 4.5). The inductive argument for QuickVaR (Lemma 3.3) and the four-case matching proof that QuickDivergence reproduces the sorted greedy solution are both careful and standard. They also ship a non-recursive version and a library, which is more than most theory papers do.\n\nSoft spots are minor and scoped. The linear-time claim stops at EWS capacities; they never claim EVaR or general φ-divergences, and the conclusion correctly flags those as open. TVaR is essentially an L1-ball risk measure they name for convenience; that is fine once you see the definition. Empirics are synthetic plus one small stock-return table, but the confidence bands are tight and the asymptotic gap appears where expected. No circularity, no free parameters, citations look appropriate.\n\nThis is for people who actually implement risk-averse MDPs or large-scale portfolio risk. A serious referee should see it; the central claims hold up and the contribution is concrete. I would accept for peer review and would cite the algorithms if I needed fast discrete CVaR.","headline":"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.","tokens_in":20217,"tokens_out":475,"would_cite":true,"duration_ms":4732,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["Value-at-Risk","Conditional-Value-at-Risk","φ-divergence risk measures","polymatroid optimization","linear-time algorithms","quickselect","EWS capacity"],"falsifier":"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.","tokens_in":20333,"feed_emoji":"⚡","tokens_out":671,"duration_ms":5373,"temperature":0.7,"pith_summary":"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.","feed_headline":"VaR and CVaR computed in linear time, no sort needed","feed_subtitle":"A quickselect-style partition replaces the usual n-log-n sort for discrete risk measures","key_machinery":"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.","core_discovery":"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.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["VaR found by Quickselect-style partition in expected linear time","QuickVaR locates the straddling atom without full sort","QuickDivergence yields CVaR in expected O(n) for discrete laws","Polymatroid EWS form makes CVaR greedy and linear-time","Discrete VaR and CVaR both computed in expected linear time"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["VaR found by Quickselect-style partition in expected linear time","QuickVaR locates the straddling atom without full sort","QuickDivergence yields CVaR in expected O(n) for discrete laws","Polymatroid EWS form makes CVaR greedy and linear-time","Discrete VaR and CVaR both computed in expected linear time"]},"model":"grok-4.5","effort":"low","cost_usd":0.001872,"raw_usage":{"total_tokens":840,"prompt_tokens":744,"num_sources_used":0,"completion_tokens":96,"cost_in_usd_ticks":18720000,"prompt_tokens_details":{"text_tokens":744,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":0,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":744,"tokens_out":96,"duration_ms":1421,"temperature":1.0,"reasoning_tokens":0,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-11T09:08:19.600601+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}