Paper: arXiv 2408.06531

Authors: Stéphane Crépey, Noufel Frikha, Azar Louzi, Jonathan Spence

Abstract

Crépey, Frikha, and Louzi (2023) introduced a multilevel stochastic approximation scheme to compute the value-at-risk of a financial loss that is only simulatable by Monte Carlo. The optimal complexity of the scheme is in \(O({"\varepsilon"}^{"-5/2"})\), \({"\varepsilon"} > 0\) being a prescribed accuracy, which is suboptimal when compared to the canonical multilevel Monte Carlo performance. This suboptimality stems from the discontinuity of the Heaviside function involved in the biased stochastic gradient that is recursively evaluated to derive the value-at-risk. To mitigate this issue, this paper proposes and analyzes a multilevel stochastic approximation algorithm that adaptively selects the number of inner samples at each level, and proves that its optimal complexity is in \(O({"\varepsilon"}^{"-2"}|\ln {"\varepsilon"}|^{“5/2”})\). Our theoretical analysis is exemplified through numerical experiments.

Complexity vs Empirical Score

  • Math Complexity: 9.5/10
  • Empirical Rigor: 3.0/10
  • Quadrant: Lab Rats — high math complexity, limited empirical testing

Why this score: The paper is heavily theoretical, featuring advanced stochastic calculus, multilevel methods, and complexity analysis, but relies on generic toy models for validation without backtest-ready datasets or code. It targets theoretical improvements over existing Monte Carlo methods rather than direct trading application.

Research Flowchart

  flowchart TD
  A["Research Goal<br>Design optimal multilevel stochastic approximation<br>for Value-at-Risk computation"] --> B["Key Methodology<br>Adaptive multilevel stochastic approximation<br>with dynamic inner sample selection"]
  B --> C["Data/Inputs<br>Monte Carlo simulatable<br>financial loss process"]
  C --> D["Computational Process<br>Recursive biased gradient evaluation<br>mitigating Heaviside discontinuity"]
  D --> E["Key Findings<br>Optimal complexity: O(ε⁻²|ln ε|⁵ᐟ²)<br>(Improved from O(ε⁻⁵ᐟ²))<br>Validated through numerical experiments"]

Evidence Card

What the authors claim, on what data, and who has checked it. Read from the paper's own text by a language model: every quote is verbatim, nothing was re-run. How to read this card

Proposes

The paper proposes and analyzes a multilevel stochastic approximation algorithm that adaptively selects the number of inner samples at each level, achieving a best complexity of O(ε^{-2}|\ln{\varepsilon}|^{5/2}).

Source sentence
To mitigate this issue, this paper proposes and analyzes a multilevel stochastic approximation algorithm that adaptively selects the number of inner samples at each level, and proves that its best complexity is in O($\varepsilon^{-2}|\ln{\varepsilon}|^\frac52$).

Assumes 5

  • For all h in H, the distribution function FXh admits a first order Taylor expansion FXh(ξ) - FX0(ξ) = v(ξ)h + w(ξ,h)h with bounded integrals of v and vanishing w as h→0. statistical
    Source sentence
    (i) For all h ∈H, FXh admits the first order Taylor expansion FXh(ξ) −FX0(ξ) = v(ξ)h + w(ξ, h)h, ξ ∈R, for some functions v, w(·, h) : R →R satisfying, for all ξ0 ⋆∈Argmin V0, Z ∞ ξ0⋆ v(ξ)dξ < ∞, lim H∋h↓0 w(ξ0 ⋆, h) = lim H∋h↓0 Z ∞ ξ0⋆ w(ξ, h)dξ = 0.
  • For all h in H, the law of Xh admits a continuous probability density function fXh. model
    Source sentence
    (2.12) (ii) For all h ∈H, the law of Xh admits a continuous pdf fXh with respect to the Lebesgue measure.
  • The densities fXh converge locally uniformly to fX0 as h→0. model
    Source sentence
    Moreover, the pdf (fXh)h∈H converge locally uniformly to fX0.
  • For any radius R>0, the density fXh is bounded away from zero on the ball B(ξ0*,R) uniformly over h. statistical
    Source sentence
    (iii) For all R > 0, inf h∈H,ξ∈B(ξ0⋆,R) fXh(ξ) > 0.
Show 1 more
  • The densities fXh are uniformly bounded and uniformly Lipschitz. statistical
    Source sentence
    (iv) The pdf (fXh)h∈H are uniformly bounded and uniformly Lipschitz, namely, sup h∈H (∥fXh∥∞+ [fXh]Lip) < ∞, where [fXh]Lip denotes the Lipschitz constant of fXh, h ∈H. 5 Remark 2.4 ([15, Remark 1.2]).

Data

  • Synthetic nested Monte Carlo loss model synthetic unknown
    Source sentence
    The nested Monte Carlo averaging (2.7) is thus available to ap-proximate (7.2), hence the applicability of NSA, adNSA, σ-adNSA, u-adNSA, MLSA, adMLSA, σ-adMLSA and u-adMLSA to approximate the VaR.

Costs

Not applicable The paper reports no trading or execution result.

Finds 3

  • The adaptive multilevel stochastic approximation scheme attains the canonical ε^{-2} multilevel complexity up to a logarithmic factor, closing the performance gap with unbiased Robbins-Monro schemes. theoretical
    Source sentence
    8 Conclusion For a prescribed accuracy ε > 0, the canonical ε−2 multilevel complexity order is retrieved, up to a logarithmic factor, for an MLSA scheme with a Heaviside-type update function. This is made possible by adopting an adaptive refinement strategy on the samples driving the multilevel algorithm’s inner nested schemes.
  • Adaptive MLSA achieves a two‑fold speed‑up over its non‑adaptive counterpart in numerical experiments. performance
    Source sentence
    The overperformance over u-adNSA can be explained by the desaturated refinement strategy used by the latter algorithm. adMLSA, σ-adMLSA and u-adMLSA show to be outperforming MLSA: for a target RMSE of order 10−2, adMLSA, σ-adMLSA and u-adMLSA run on average in 1s while MLSA runs in 2s, achieving a 2-fold speed-up over their non-adaptive counterpart. σ-adMLSA seems to be slightly outperforming adMLSA, The performance
  • The proposed algorithm reduces the complexity from O(ε^{-5/2}) to O(ε^{-2}|\ln{\varepsilon}|^{5/2}). theoretical
    Source sentence
    The best complexity of the scheme is in O($\varepsilon^{-\frac52}$), $\varepsilon>0$ being a prescribed accuracy, which is suboptimal compared to the canonical multilevel Monte Carlo performance. To mitigate this issue, this paper proposes and analyzes a multilevel stochastic approximation algorithm that adaptively selects the number of inner samples at each level, and proves that its best complexity is in

Checked by others

No other paper in the archive has been found to support or contradict these findings (compared with 14 related papers). Coverage is partial, so this is neither replication nor refutation.

Cited by 4 papers in the archive (4 by independent authors)

Code

https://github.com/azarlouzi/ada_mlsa — the authors' own repository

Extracted 2026-11-14 · same card as JSON · A language model chose these items: check the source sentence before relying on one.