{'fraction_non_alphanumeric': 0.05014911047886745, 'fraction_numerical': 0.017139135502005277, 'mean_word_length': 4.109281961471103, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Optimizing tail risks using an importance sampling based extrapolation for heavy-tailed objectives

Motivated by the prominence of Conditional Value-at-Risk (CVaR) as a measure for tail risk in settings affected by uncertainty, we develop a new formula for approximating CVaR based optimization objectives and their gradients from limited samples. A key difficulty that limits the widespread practical use of these optimization formulations is the large amount of data required by the state-of-the-art sample average approximation schemes to approximate the CVaR objective with high fidelity. Unlike the state-of-the-art sample average approximations which require impractically large amounts of data in tail probability regions, the proposed approximation scheme exploits the self-similarity of heavy-tailed distributions to extrapolate data from suitable lower quantiles. The resulting approximations are shown to be statistically consistent and are amenable for optimization by means of conventional gradient descent. The approximation is guided by means of a systematic importance-sampling scheme whose asymptotic variance reduction properties are rigorously examined. Numerical experiments demonstrate the superiority of the proposed approximations and the ease of implementation points to the versatility of settings to which the approximation scheme can be applied.


Introduction
Conditional Value at Risk (CVaR) is a tail-risk measure which has found widespread use in decision making in reliability/safety-critical uncertain environments such as those arising in finance, operations research, power flow distribution, motion planning, etc. (see, for example, [1,12,18,21,22]). For a random objective L(θ) denoting the the risk (or loss) associated with a controllable parameter choice θ, the CVaR at level 1 − β is the risk averaged over the β fraction of the outcomes with the highest risk, as in, where v β (θ) is the (1−β)-quantile of L(θ). As is often in practice, suppose that the loss structure L(θ) is given by L(θ) = (θ, X), for a deterministic function (·) which is convex in θ and a random vector X modeling uncertainty. Then the CVaR, denoted by C β (θ) above, is a convex risk measure with desirable coherence properties [18]; indeed, the convexity renders CVaR as a suitable vehicle for introducing risk-aversion in optimization formulations.
The widespread use of CVaR in the above contexts has recently sparked interest in its applicability towards tackling broader challenges pertaining to fairness and reliability/safety in modern machine learning applications: see, for e.g, [6,23]. However, despite the conceptual advantages, a key difficulty which restricts the use of CVaR in the modern data-driven applications is the inherent statistical difficulty associated with tail risks: With limited fraction of historical data representing extreme risk outcomes, sample-averages possess high variance unless large amounts of data are utilized. For example, if we wish to approximate CVaR of a random variable within a fixed relative error at level 1 − β = 0.99, we would need at least 1/β = 100 times more samples than we would require to estimate its mean. The impact of insufficient data on the noisiness of mean -CVaR frontiers in the context of portfolio optimization has been chronicled in [5,13]. Due to the statistical nature of rare events, this difficulty is present in all data-driven settings where 1 − β is taken close to 1 in order to incorporate high reliability or safety requirements.
To overcome this limitation, we consider the specific setting where the random vector X is suitably heavy-tailed and exploit the self-similar structure of heavy-tailed distributions to arrive at statistically consistent approximations of CVaR-based objectives and their gradients which can be constructed with limited samples. Our interest in the heavy-tailed case is motivated by the fact that tail risks are more pronounced and risk-aversion is of paramount importance particularly in the presence of heavy-tailed stochastic factors. Our contributions are two-fold: 1) Assuming oracle access to the probability density of X, we first develop an entirely novel Importance Sampling (IS) scheme for approximating the CVaR objective C β (θ). The IS estimator has zero bias and is shown to possess substantially lower variance (when compared to the naive sample average) in the considered setting where the use of IS, until now, has been well-developed only for instances where X is one-dimensional (or) its components are independent. 2) More importantly, when the probability density of X is not known, we show that the likelihood representation in the importance sampling estimator can be suitably approximated to result in data-driven estimators for the CVaR term C β (θ) and its gradient ∇C β (θ). Interestingly, the variance of the resulting approximations are only a fraction of those constructed from the usual sample averages and their bias vanish as the estimation task is made more challenging by letting β 0.
A key ingredient in verifying the statistical consistency is Theorem 3.1 which establishes that the approximation, for an estimable parameter ξ, has vanishing relative error for suitably small β 0 , β even if β 0 β. This is due to the self-similarity of heavy-tailed distributions and allows approximating CVaR at higher quantile 1 − β by means of CVaR observed in data at lower quantile 1 − β 0 , where β 0 is chosen suitably larger than β. This self-similarity phenomenon, though well-known in extreme value theory in statistics and quantitative risk management, has not been utilized in optimization contexts. Our goal is to suitably facilitate the use of extreme value theory based extrapolation in data-driven optimization by tackling the estimation of gradient (sensitivity) of objectives with tail risks. Moreover, among methods which specifically consider optimization in the presence of heavy-tails, see for eg. [14], the proposed approach based on self-similarity has the added advantage that it does not require explicit estimation of the joint dependence of X, which is a statistically challenging exercise even in small dimensions. Numerical experiments in the context of portfolio optimization reveal superior performance compared to using naive sample averages even in dimensions as large as 100 (thus demonstrating scalability) and offers reliable performance even if there is a severe paucity of samples in the desired tail region The paper is organized as follows: After introducing the importance sampling scheme for CVaR estimation in Section 2, we use it to derive the extrapolation based estimator in Section 3. We demonstrate the strength of the proposed data-driven scheme in Section 4 by reporting results of experiments with simulated and real datasets. We provide a sketch of the proof of a main result in Section 5. The entire proofs of all the new results in the paper are presented in the appendix.
Notation. We use bold symbols to denote vectors, for e.g., x = (x 1 , . . . , x d ). For any two vectors a, b, we use ab and a/b, respectively, to denote component-wise multiplication and division. For any a ∈ R, a + = max{0, a} denotes the positive part of a. The symbols P − → and L − → denote convergence in probability and distribution, respectively. For a sequence of random variables {X n } n≥1 , we say that X n is o P (1) if X n P − → 0. We say that a sequence a n = o(b n ), if as n → ∞, a n /b n → 0, and that a n =Õ(b n ) if there exist a constant k such that a n /(b n log k b n ) is asymptotically bounded. A function L(·) is slowly varying if for any constant c, L(ct)/L(t) → 1 as t → ∞. We use N (0, I d ) to denote the d-dimensional standard Gaussian vector.

CVaR estimation via importance sampling
Suppose that L(θ) := (θ X) represents the random loss (or risk) associated with the parameter θ ∈ Θ, where Θ is a bounded subset of R d ++ , and X is an R d + −valued random vector whose distribution satisfies Assumption 2 below. The loss : R → R + is such that the derivate (u) exists for all u exceeding a positive constant u 0 and is taken to grow at most polynomially.
Commonly used losses in portfolio optimization, newsvendor models and quadratic optimization models, square loss, logistic loss, etc. satisfy the above assumptions.To state the assumption on the distribution of X, let M n denote the component-wise maxima of n independent and identically distributed (i.i.d.) copies of X.
There exists a normalizing sequence {a n } n≥1 ⊆ R + d such that, as n → ∞, the sequence a n −1 ∞ a n is convergent and the distribution of M n /a n converges to a nondegenerate probability distribution.
Just like how the central limit theorem quantifies the limiting behaviour of the i.i.d. sum n −1/2 (X 1 + . . . + X n ), the extreme value theorem (see, eg. [17]) specifies all possible limiting distributions of suitably scaled and centred maxima (M n − b n ) /a n . For heavy-tailed random vectors, the centering sequence {b n } can be taken to be zero without loss of generality, whereas {b n } is necessarily divergent for light-tailed distrubtions. Thus, Assumption 2 is indeed one of the general descriptions of multivariate heavy-tailed distributions, and it includes the wellstudied multivariate regularly varying models [17]. In Assumption 2, the scaling constants a n,1 , . . . , a n,d capture the relative tail heaviness of each component and the limiting distribution describes diverse dependence distributions.
Since this sample requirement is impractically large when β is small, importance sampling is employed, when feasible, to reduce variance to a lower order than O(β −2 ).
2.2. Importance sampling. Importance sampling (IS) is a popular variance reduction technique that has found applications in various engineering disciplines, most notably in settings where rare events need to be tackled [4]. The objective of this section is to develop an IS scheme for estimating C β (θ) such that the resulting IS estimator i) has substantially lower variance and ii) is applicable across nontrivial joint dependence among the components of X. As we shall see in Section 3, the importance sampling estimator also serves as a natural starting point towards estimating CVaR and its gradient from data when the distribution of X is not known.
The first step in the IS estimation of CVaR is to develop an IS estimator for the c.d.f. F θ (u) := 1 − P ( (θ X) > u). Suppose that the probability density of X is given by f (·). To circumvent the issue of limited observations in the tail region E 1 := {x : (θ x) > u} when 1 − F θ (u) is small, we instead obtain samples for X from a carefully chosen IS probability density f IS (·) under which the set E 1 has much higher probability than 1 − F θ (u). Let denote the likelihood ratio associated with the change of distribution. It is necessary that IS density is such that f IS (x) > 0 for any x ∈ E 1 such that f (x) > 0. Then, whereX is distributed according to f IS (·). This suggests the use of the estimator, whereX 1 , . . . ,X n are i.i.d. samples from the IS density f IS (·). To obtain estimators with low variance, it is desirable that the IS density is such that the likelihood ratio L R (X i ) is small. This is achieved by choosing an IS density which somewhat mirrors the conditional distribution of X over the target rare set E 1 (see [4], Section 4.2). While there is a rich literature on the choice of IS density when the components of X are independent (see [3] and references therein), the dependent case is underdeveloped due to the need to carefully account for the dependence structure present in the rare event of interest.
2.3. The proposed IS density and the IS algorithm. A central idea in extreme value theory is that when a distribution satisfies Assumption 2, lim n→∞ nP (X/a n ∈ A) exists for a large class of sets A, see [16]; as a result, for suitably large m, n such that m < n, P (X/a n ∈ A) can be approximated, in principle, by (m/n) × P (X/a m ∈ A), thus indicating the use of selfsimilarity which is present at different scales in the distribution of X.
Exploiting this phenomenon towards the IS estimation of the c.d.f. F θ (u) results in the following radically new approach towards selecing IS density: We first identify a lower level l < u and suitably replicate the samples observed in the less rarer set E 0 := {x : (θ x) > l} by appropriately scaling them onto the target rare set E 1 . To be specific, if we takeX = sX for suitable scaling vector s = (s 1 , . . . , s d ) such that s i ≥ 1 for all i, then the resulting IS density is given by, f IS (x) = density of sX = f (x/s) Π d k=1 s −1 k . Consquently, the likelihood ratio is given by, The self-similarilty of the distribution ensures that the IS density mirrors the distribution of X over the set E 1 , thus obviating the major impediment in searching for an IS density in multivariate setting. In other words, the proposed IS scheme 'automatically learns' the conditional distribution of X over the set E 1 by exploiting the more frequent samples observed in a similar, but less rare, set E 0 .
Since our interest in the c.d.f F θ (·) stems from the goal of CVaR estimation, we present our IS scheme for jointly estimating c.d.f., VaR and CVaR below. Variance reduction guarantees are presented immediately after Algorithm 1. Under Assumption 2, it is necessary that the marginal densities f k (·) of X k , k = 1, . . . , d and the joint pdf f (·) of X = (X 1 , . . . , X d ) are polynomially decaying, as in, for any positive constant c and x ∈ R + d \ {0}, as t → ∞ (see [16], Sections 5.2-5.5). Here, α = (α 1 , . . . , α d ) is the vector of tail indices quantifying the rate of decay (or heaviness) of the respective marginal tails of distributions. We have used t 1/α := (t 1/α 1 , . . . , t 1/α d ) to denote the component-wise exponentiation. Common examples of densities which satisfy (5) include the multivariate-t and Pareto densities (see [8]).

Remark 1.
To estimate CVaR C β (θ) within a prescribed relative error, by taking β 0 = β κ for κ < 1, we get variance reduction by a factorÕ(β −(1−κ) ). Then, as a consequence of central limit theorem, it is sufficient to choose the number of samples for the IS scheme to be smaller by a factorÕ(β −(1−κ) ) than naive sample averaging.

Extrapolation based data-driven estimators
In this section, we consider the data-driven setting where the probability density of X is not known and the CVaR C β (θ) and its gradient ∇C β (θ) have to be estimated from historical data X 1 , . . . , X n . The starting point for the data-driven estimator is the IS CVaR estimatorĈ IS β,n (θ) in Step 3 of Algorithm 1. Given i.i.d. data X 1 , . . . , X n , observe that all the terms in the expression forĈ IS β,n (θ) are computable except the likelihood ratio L R (sX). Due to the assumed heavy-tailed nature of X, we can however approximate the likelihood ratio as demonstrated in Example 1 below.
Example 1. Suppose that L(θ) = θ X and the marginal components of X = (X 1 , . . . , X d ) have the same distribution. Then α k = α for k = 1, . . . , d. Given a tail probability level β, take β 0 = cβ for a suitable constant c > 1, t = 1/β 0 and reparameterize x ∈ R d ++ as z = t −1/α x. To approximate the likelihood ratio L R (sX), recall that we have taken s = c 1/α in Algorithm 1. Therefore, sx = (ct) 1/α z and x = t 1/α z. Since t is large when the tail probability level β is small, we can use (5) to approximate the likelihood ratio L R (·) as, for all x suitably large. In particular, since the target rare set {x : ). Then, from (3), we have the approximation, is the empirical c.d.f. constructed from the samples. Recalling that (θ X) = θ X, we obtain the following the expressions forv IS β,n (θ),Ĉ IS β,n (θ) in Algorithm 1 andv β 0 ,n ,Ĉ β 0 ,n in Section 2.1: Theorem 3.1 below establishes that the above heuristic approximations motivated by approximating the IS estimator are indeed valid for the large class of losses (·) and diverse dependence structures for X introduced in the beginning of Section 2.  (1)) and (7) The significance of the theorem is that the CVaR C β (θ) and its gradient ∇C β (θ) at a high probability level 1−β (say, 1−β = 0.99) can be computed from their respective estimates, C β (θ) and ∇C β (θ), obtained from a lower probability level 1 − β 0 (say, 1 − β 0 = 0.9). In principle, this should reduce the number of samples required to estimate the respective quantities by a factor of β 0 /β. We observe this is indeed the case in most numerical experiments in Section 4. While this type of extrapolation performed from the risk observed at a lower level is the central plank of tail risk measurement in extreme value theory in statistics [7] and quantitative risk management [14,15], to the best of our knowledge, such extrapolation has not been utilized in gradient estimation and subsequent optimization. The approximation for gradients ∇C β (θ), as in Theorem 3.1, is new even from an extreme value theory point of view, and becomes an useful addition to the arsenal of existing extrapolation techniques. The approximations in Theorem 3.1 facilitates the following low variance estimation scheme for the CVaR C β (θ) and its gradient ∇C β (θ).
ReturnC β,n (θ),∇ n C β (θ). Corollary 3.1 below establishes consistency of the estimators (in a relative error sense) in Algorithm 2 as the target rare set {L(θ) > v β(n) (θ)} is made increasingly rare; this is accomplished by letting β(n) 0 as the number of samples n → ∞.
Remark 2. The conditions of the Corollary 3.1 are satisfied, for example, when nβ 0 (n) → ∞. Similar consistency can be established for the CVaR gradient (by replacing the CVaR by its gradient everywhere in Corollary 3.1).
We now argue that the estimators in Algorithm 2 enjoy a variance reduction of β 0 /β over their naive counterparts. To faciliatate this argument, recall that the error in the IS estimator (see Section 2) for CVaR estimation is approximately N (0, n −1/2 σ 2 IS (β)). Further, observe that for the naive estimator of CVaR,Ĉ β (θ), from Corollary 2 of [10], the error is roughly N (0, n −1/2 σ 2 SA (β)). Recall that Theorem 2.1 shows that for small β, σ 2 SA (β)/σ 2 IS (β) ∼ β 0 /β. From Example 1, the estimators in Algorithm 2 were essentially arrived at by replacing the likelihood in the importance sampling estimator from Algorithm 1 by its limit. Since the error of making this approximation is negligible for small values of β, the proposed estimatorC β (θ) (and thus∇C β (θ)) is likely to have variance smaller by a factor β 0 /β than the naive sample average counterparts. In this case, the sample complexity becomes smaller by a factor β 0 /β with the extrapolation scheme in Algorithm 2. This is verified through the numerical experiments in Section 4. Indeed, the above reasoning may be made precise by deriving a central limit theorem for the estimator from Algorithm 2, under the set-up of Corollary 3.1, with some mild additional regularity assumptions on the distribution of X (for e.g., the second order conditions from [7]). However, this is beyond the scope of the current paper, and will be pursued as a follow-up research.

Numerical Experiments
In this section, we report the results of numerical experiments performed with simulated and real data in order to compare the performance of estimators proposed in Algorithm 2 with that of the naive sample average estimators.

Scalability of gradient estimation with dimension d.
In this experiment, we compare Root Mean Square Errors (RMSE) of the relative errors of the gradients ∇C β (θ) computed from i) the proposed estimator in Algorithm 2 and ii) the naive sample average (SA) estimator. Taking β = 0.1 and candidate losses to be L 1 (θ) = θ X and L 2 (θ) = (θ X) 2 , we report RMSE relative errors observed in dimensions d = 50 and d = 100. Since the true value of ∇C β (θ) are not known in closed form, we approximate them using sample average with N 1 = 10 6 samples to serve as a benchmark for computing relative error of our estimates. For the linear loss L 1 (θ), the lower level β 0 is chosen as 20β, whereas for the square loss L 2 (θ), β 0 is set at 8β; these levels are identified by cross-validating over an interval of candidate β 0 . The RMSE relative errors are reported in Figures 1 and 2. It is evident from the figures that Algorithm 2 outperforms the naive method, robustly across dimensions d = 50, 100, by resulting in significantly smaller error than the naive method in gradient estimation. Moreover, in a manner consistent with our hypothesis, the number of samples required by the naive method to get the same level of accuracy as the proposed estimator scales like β 0 /β : For example, in Figure 2, where d = 50 and β = 0.01, fixing the RMSE observed for the proposed estimator with n = 250 samples,  Figure 1 is used, but components of X are chosen to be independent Pareto(6).
we observe that the naive sample estimator requires as much as n = 2000 samples to offer the identified RMSE.

Application to Risk Constrained Portfolio Optimisation.
We demonstrate the utility of the proposed gradient estimator by applying it to solving a single period risk constrained portfolio optimization problem. The historical losses from d assets are given by observations {X 1 , . . . , X n }. Taking the loss L(θ) to be the portfolio loss θ X for a given portfolio weight vector θ, we aim to solve, This formulation has been considered extensively in the literature on tail risk sensitive portfolio optimization (see [1,12,13]). In order to evaluate the effectiveness of the estimators, we first compute the true optimum value V * of (12) using a large number (N = 10 5 ) of samples to serve as a benchmark. We then solve (12) using gradient descent, where the gradients are estimated from limited data for both the proposed and naive SA estimators. Suppose that θ 1 and θ 2 are the optimal portfolio weights output by the gradient descent methods in which the gradients are estimated, respectively, using the proposed and the naive SA gradient estimators. We then evaluate the true objective values V 1 , V 2 at θ 1 and θ 2 by using N = 10 5 samples. We then report the relative mean square errors, |V 1 − V * |/V * indicating the efficacy of the proposed gradient estimation scheme, and |V 1 − V * |/V * which indicates the efficacy of the naive SA estimation scheme. Specific implementation and Results: We assume that the dependence between asset returns is captured using a t-copula and allow the tails of losses from individual assets to be different. Such an assumption is used widely in modelling asset returns (see [9]). In order to stay close to a realistic data set, the marginal tails and dependence between asset returns are modelled using the correlation matrix of daily returns from twelve S&P-500 stocks, over a 5 year period (1200 days). We consider the cases where β = 0.01, 0.005 in (12). The number of times periods of data n is varied from 400 days to 1600 days (about 2-6 years). Increasing the amount of data beyond this is practically infeasible, since typically only about 5-6 years of financial data is used in portfolio optimisation problems (see [13]). As before, the lower level β 0 = 0.1 is selected through cross validation. We observe that in Figure 3, errors in the optimal solution are significantly lower using when Algorithm 2 is used to compute CVaR gradients, over using the naive estimator for CVaR gradient. For example, we observe that the error in optimal solution using Algorithm 2 is roughly 17%, when β = 0.005 and n = 400. The number of samples of data required to achieve the same level of accuracy using the naive estimator is over 1600. This indicates a large reduction in amount of data required to solve the risk constrained optimisation problem (12) by means of the proposed method.

4.3.
Experiments with S&P-500 data. For demonstrating the efficacy of the proposed experiment with real data, we use 5 years (1200 days) of daily returns for 12 S&P-500 stocks. We divide the data into intervals, call them S i , of the form [N i , N i + 300] 100 i=1 . Here, the starting indices N i are chosen uniformly at random, without replacement from {1, . . . , 1200}. For each sample window S i , we compute the CVaR and its gradient using the naive approach and the proposed Algorithm 2 for the choices β 0 = 0.1 and β = 0.01. We then calculate the mean and the variance of both the estimators. We find that for the CVaR, the variance of naive computation is 303.15, while that for the extrapolation based estimator is 161.77 (the means in computation of CVaR are 41.05 and 41.64, respectively). Similarly, for the gradient, the variance for the naive SA estimator is 403.74, while that for the proposed extrapolation based estimator is 163.88. This suggests that even on a representative sample of real asset data, the proposed estimator significantly out-performs the naive sample average.

Proofs of Theorem 2.1 and 3.1
We present the proofs for the case where (u) = u. We begin by establishing an asymptotic approximation for v β (θ). Notice that under Assumption 2, from Theorem 3 of [19] and Theorem 5.3 of [16], as t ↑ ∞. (13) tP (X/a t ∈ ·) → ν(z ∈ ·), where the convergence is over all sets not containing the origin, and ν(·) is a Radon measure (see [19] for a detailed explanation). Thus, the tail behaviour of X can be inferred by looking at the dependence measure ν(·). Specifically, for a suitably large t, for any b ∈ R d Further define X t = X/a t . Then, under Assumption 2, the limitsθ andâ are well defined. Observe that with θ t =ā −1 t a t θ, one can writeā −1 t θ X = θ t X t . Proposition 5.1 extends the discussed convergence slightly: For any s ≤ 1, define Proposition 5.1 shows that for a large t, the probability that θ X ≥ā t u is approximately t −1 ν(θ z ≥ u). By setting ν(θ z ≥ u) to 1, v β (θ) ∼ā t κ 1 (θ), as t → ∞ (see Proposition 5.2). The proof of Proposition 5.1, which outlines how the limiting measure ν(·) plays a vital role in all our analysis, is given in Section 5.2.
Step 1: The first step is to approximate the VaR of θ X using Proposition 5.1. Proposition 5.2, below gives the necessary approximation: Under the assumptions of Theorem 3.1, v β (θ) ∼ā t κ 1 (θ), as t → ∞.
Step 2: In order to establish convergence of expectations from the above weak convergence, the following uniform integrebility condition is needed: For any sequenceθ t →θ, X/ā t conditioned onθ t X t ≥ κ 1 (θ) is uniformly integreble.

Now, repeating
Step 3, with ∇C t replaced by C t establishes (7). As mentioned earlier, to demonstrate the role of the limiting measure ν(·) in the analysis, we present the proof of Proposition 5.1.

5.3.
Proof of Theorem 2.1. For simplicity, we only demonstrate the proof for the case l(u) = u. As before, let β = 1/t and β 0 = 1/t 0 . Let L(y) be the likelihood ratio. The central limit theorem follows directly as a consequence of Corollary 2 of [10]. Further, σ 2 where Var denotes the variance with respect to the alternate measure. This equals In order to prove the second part of the theorem, notice that following a change of measurẽ A few definitions are needed to proceed. Let θ i,t = u Notice that for all large enough t, inf θ t p≥1 p ≥ δ, for some δ > 0. Fix > 0. From the hypothesis of the theorem (see [16], Section 6, p.g. 199 onward), for all large enough t, uniformly over p ∈ B c δ , and f p ut·t 0 t 1/α is at least where L(·) is a slowly varying function. Thus, (21) is upper bounded by (1 + ) 3 times t/t 0 times (θ t p − 1) 2 ϕ(p)dp.

Conclusions
In this paper, we develop extrapolation based estimators for the computation of CVaR and its derivative. Such extreme value based estimators for CVaR and its gradient are entirely new, and have not been studied in literature. We apply this estimator to a risk constrained portfolio optimisation problem, and find that the extrapolation based methods achieve a substantial improvement in performance over the naive approach. Broadly, extreme value based extrapolations should have a wide range of applications in finance and operations research, where problems involving risk constraint optimisation with limited data are common.

Proof of Lemma A.1
Integration with respect to the measure ν can be done conveniently in terms of the representation Z = R/T γ , where R is a d-dimensional random vector, and T is an improper uniform random variable taking values in [0, ∞) (see [19] for a more detailed explanation for rewriting ν(·) in terms of R and T ). In particular, Recall thatθ =âθ, and notice thatâ i > 0 only if ξ i = ξ, where ξ = max d i=1 ξ i is the index of the fattest tail. Therefore for any fixed u, (33) can be re-written as (34) Using Fubini's Theorem, (34) equals 1 u 1/ξ r (θ r) 1/ξ dF (r).
Since above was arbitrary, the proof is complete.
Since the above quantity goes to 0 as n → ∞, the proof is complete. Proposition A.1 extends Theorem 3.1 to a general loss.
A matching lower bound may be established, which completes the proof .

Tata Institute of Fundamental Research
Singapore University of Technology and Design