Evaluating the risk associated to a portfolio is important to
regulators, market exchanges and investors. The value-at-risk (VaR)
and expected shortfall (ES) remain the most widely used risk measures
in finance. Given a portfolio of future random loss X and a confidence
level c in (0,1), the VaR represents the quantile of X at level c (P(X
VaR) = 1-c) and the ES the average loss given that X exceeds the
VaR, i.e. the superquantile of X at level c (ES = E[X|X > VaR]).

Computing efficiently the VaR and ES of a given portfolio constitutes
an active field of research. Rockafeller and Uryasev (2000) show that,
under suitable assumptions, the VaR and ES can be jointly retrieved as
solutions to a stochastic convex program, thus allowing to resort to
stochastic approximation methods. In a realistic scenario, the loss of
the portfolio is expressed in a nested way, i.e. X = E[f(Y, Z)|Y],
where Y describes the risk factors influencing the portfolio up to
some time horizon T > 0, Z the risk factors influencing it beyond T,
and f(Y, Z) the subsequent cash flows. The conditioning is done with
respect to the information available at time T. When X cannot be
simulated exactly, a natural solution consists in swapping X with a
nested Monte Carlo estimate thereof within the stochastic
approximation scheme for the VaR and ES. This solution nevertheless
increases the estimation complexity.

We endeavor to accelerate the stochastic approximation of the VaR and
ES in the nested loss case. The goalpost is to attain a quadratic
complexity as is achieved by unbiased stochastic approximation in the
case where X can be simulated exactly.
We first present a nested stochastic approximation scheme, which
simulates X with a bias, and attains a complexity in O(n^3) to achieve
an error in O(1/n). We then leverage the multilevel paradigm to bring
the estimation cost down to O(n^2.5) for the VaR and to O(n^2 ln(n)^2)
for the ES. Since these complexities can only be reached under
additional inaccessible conditions, we develop an ergodic
Polyak-Ruppert version of the multilevel algorithm and demonstrate its
increased numerical stability through appropriate central limit
theorems. Eventually, to bridge the performance gap between the
multilevel and unbiased VaR schemes (in O(n^2.5) and O(n^2)), we
adaptively refine the Monte Carlo innovations digested by the
multilevel algorithm, resulting in a complexity of O(n^2 ln(n)^2.5).
All the above results are exemplified through suitable numerical
studies that include realistic financial scenarios.