Zakaria Mhammedi
email: zak.mhammedi@anu.edu.au

Benjamin Guedj
email: benjamin.guedj@inria.fr

Robert C Williamson
email: bobwilliamsonoz@icloud.com

PAC-Bayesian Bound for the Conditional Value at Risk

Conditional Value at Risk (CVAR) is a family of "coherent risk measures" which generalize the traditional mathematical expectation. Widely used in mathematical finance, it is garnering increasing interest in machine learning, e.g., as an alternate approach to regularization, and as a means for ensuring fairness. This paper presents a generalization bound for learning algorithms that minimize the CVAR of the empirical loss. The bound is of PAC-Bayesian type and is guaranteed to be small when the empirical CVAR is small. We achieve this by reducing the problem of estimating CVAR to that of merely estimating an expectation. This then enables us, as a by-product, to obtain concentration inequalities for CVAR even when the random variable in question is unbounded.

Introduction

The goal in statistical learning is to learn hypotheses that generalize well, which is typically formalized by seeking to minimize the expected risk associated with a given loss function. In general, a loss function is a map ℓ∶ H × X → R ≥0 , where X is a feature space and H is an hypotheses space. In this case, the expected risk associated with a given hypothesis h ∈ H is given by R[ℓ(h, X)] ∶= E[ℓ(h, X)]. Since the data-generating distribution is typically unknown, the expected risk is approximated using observed i.i.d. samples X 1 , . . . , X n of X, and an hypothesis is then chosen to minimize the empirical risk R[ℓ(h, X)] ∶= ∑ n i=1 ℓ(h, X i ) n. When choosing an hypothesis ĥ based on the empirical risk R, one would like to know how close R[ℓ( ĥ, X)] is to the actual risk R[ℓ( ĥ, X)]; only then can one infer something about the generalization property of the learned hypothesis ĥ.

Generalization bounds-in which the expected risk is bounded in terms of its empirical version up to some error-are at the heart of many machine learning problems. The main techniques leading to such bounds comprise uniform converges arguments (often involving the Rademacher complexity of the set H), algorithmic stability arguments (see e.g. [START_REF] Bousquet | Stability and generalization[END_REF] and more recently the work from [START_REF] Karim | An exponential tail bound for lq stable learning rules[END_REF][START_REF] Bousquet | Sharper bounds for uniformly stable algorithms[END_REF][START_REF] Celisse | Stability revisited: new generalisation bounds for the leave-oneout[END_REF]), and the PAC-Bayesian analysis for non-degenerate randomized estimators [START_REF] Mcallester | PAC-Bayesian Stochastic Model Selection[END_REF]. Behind these techniques lies concentration inequalities, such as Chernoff's inequality (for the PAC-Bayesian analysis) and McDiarmid's inequality (for algorithmic stability and the uniform convergence analysis), which control the deviation between population and empirical averages [see [START_REF] Boucheron | Concentration inequalities[END_REF], 2013, McDiarmid, 1998, among others].

Standard concentration inequalities are well suited for learning problems where the goal is to minimize the expected risk E[ℓ(h, X)]. However, the expected risk-the mean performance of an algorithm-might fail to capture the underlying phenomenon of interest. For example, when dealing with medical (responsitivity to a specific drug with grave side effects, etc.), environmental (such as pollution, exposure to toxic compounds, etc.), or sensitive engineering tasks (trajectory evaluation for autonomous vehicles, etc.), the mean performance is not necessarily the best objective to optimize as it will cover potentially disastrous mistakes (e.g., a few extra centimeters when crossing another vehicle, a slightly too large dose of a lethal compound, etc.) while possibly improving on average. There is thus a growing interest to work with alternative measures of risk (other than the expectation) for which standard concentration inequalities do not apply directly. Of special interest are coherent risk measures [START_REF] Artzner | Coherent measures of risk[END_REF] which possess properties that make them desirable in mathematical finance and portfolio optimization [START_REF] Allais | Le comportement de l'homme rationnel devant le risque: critique des postulats et axiomes de l'école américaine[END_REF][START_REF] Ellsberg | Risk, ambiguity, and the savage axioms[END_REF][START_REF] Tyrrell Rockafellar | Optimization of conditional value-at-risk[END_REF], with a focus on optimizing for the worst outcomes rather than on average. Coherent risk measures have also been recently connected to fairness, and appear as a promising framework to control the fairness of an algorithm's solution [START_REF] Williamson | Fairness risk measures[END_REF].

A popular coherent risk measure is the Conditional Value at Risk (CVAR; see [START_REF] Ch | Some Remarks on the Value-at-Risk and the Conditional Value-at-Risk[END_REF]; for α ∈ (0, 1) and random variable Z, CVAR α [Z] measures the expectation of Z conditioned on the event that Z is greater than its (1α)-th quantile. CVAR has been shown to underlie the classical SVM [START_REF] Takeda | ν-support vector machine as conditional value-at-risk minimization[END_REF], and has in general attracted a large interest in machine learning over the past two decades [Bhat and Prashanth, 2019[START_REF] Youhua | A Risk-Averse Newsvendor Model Under the CVaR Criterion[END_REF], Chow and Ghavamzadeh, 2014[START_REF] Huo | Risk-aware multi-armed bandit problem with application to portfolio selection[END_REF][START_REF] Morimura | Nonparametric return distribution approximation for reinforcement learning[END_REF][START_REF] Pinto | Robust adversarial reinforcement learning[END_REF][START_REF] Prashanth | Actor-critic algorithms for risk-sensitive MDPs[END_REF][START_REF] Takeda | A robust approach based on conditional value-at-risk measure to statistical learning problems[END_REF][START_REF] Tamar | Optimizing the CVaR via sampling[END_REF][START_REF] Williamson | Fairness risk measures[END_REF].

Various concentration inequalities have been derived for CVAR α [Z], under different assumptions on Z, which bound the difference between CVAR α [Z] and its standard estimator CVAR α [Z] with high probability [Bhat and Prashanth, 2019[START_REF] David | Large deviations bounds for estimating conditional value-at-risk[END_REF][START_REF] Kumar Kolla | Concentration bounds for empirical conditional value-at-risk: The unbounded case[END_REF][START_REF] Prashanth | Actor-critic algorithms for risk-sensitive MDPs[END_REF][START_REF] Wang | Deviation inequalities for an estimator of the conditional value-at-risk[END_REF]. However, none of these works extend their results to the statistical learning setting where the goal is to learn an hypothesis from data to minimize the conditional value at risk. In this paper, we fill this gap by presenting a sharp PAC-Bayesian generalization bound when the objective is to minimize the conditional value at risk. Related Works. Deviation bounds for CVAR were first presented by [START_REF] David | Large deviations bounds for estimating conditional value-at-risk[END_REF]. However, their approach only applies to bounded continuous random variables, and their lower deviation bound has a sub-optimal dependence on the level α. [START_REF] Wang | Deviation inequalities for an estimator of the conditional value-at-risk[END_REF] later refined their analysis to recover the "correct" dependence in α, albeit their technique still requires a two-sided bound on the random variable Z. [START_REF] Thomas | Concentration inequalities for conditional value at risk[END_REF] derived new concentration inequalities for CVAR with a very sharp empirical performance, even though the dependence on α in their bound is sub-optimal. Further, they only require a one-sided bound on Z, without a continuity assumption. [START_REF] Kumar Kolla | Concentration bounds for empirical conditional value-at-risk: The unbounded case[END_REF] were the first to provide concentration bounds for CVAR when the random variable Z is unbounded, but is either sub-Gaussian or sub-exponential. Bhat and Prashanth [2019] used a bound on the Wasserstein distance between true and empirical cumulative distribution functions to substantially tighten the bounds of [START_REF] Kumar Kolla | Concentration bounds for empirical conditional value-at-risk: The unbounded case[END_REF] when Z has finite exponential or kth-order moments; they also apply their results to other coherent risk measures. However, when instantiated with bounded random variables, their concentration inequalities have sub-optimal dependence in α.

On the statistical learning side, [START_REF] Duchi | Learning models with uniform performance via distributionally robust optimization[END_REF] present generalization bounds for a class of coherent risk measures that technically includes CVAR. However, their bounds are based on uniform convergence arguments which lead to looser bounds compared with ours.

Contributions. Our main contribution is a PAC-Bayesian generalization bound for the conditional value at risk, where we bound the difference CVAR α [Z] -CVAR α [Z], for α ∈ (0, 1), by a term of order CVAR α [Z] ⋅ K n (nα), with K n representing a complexity term which depends on H. Due to the presence of CVAR α [Z] inside the square-root, our generalization bound has the desirable property that it becomes small whenever the empirical conditional value at risk is small. For the standard expected risk, only state-of-the-art PAC-Bayesian bounds share this property (see e.g. [START_REF] Catoni | PAC-Bayesian supervised classification: the thermodynamics of statistical learning[END_REF], [START_REF] Langford | PAC-Bayes & margins[END_REF], [START_REF] Maurer | A note on the PAC-Bayesian theorem[END_REF] or more recently in [START_REF] Mhammedi | PAC-Bayes Un-Expected Bernstein Inequality[END_REF], Tolstikhin and Seldin [2013]). We refer to [START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF] for a recent survey on PAC-Bayes.

As a by-product of our analysis, we derive a new way of obtaining concentration bounds for the conditional value at risk by reducing the problem to estimating expectations using empirical means. This reduction then makes it easy to obtain concentration bounds for CVAR α [Z] even when the random variable Z is unbounded (Z may be sub-Gaussian or sub-exponential). Our bounds have explicit constants and are sharper than existing ones due to Bhat and Prashanth [2019], [START_REF] Kumar Kolla | Concentration bounds for empirical conditional value-at-risk: The unbounded case[END_REF] which deal with the unbounded case.

Outline. In Section 2, we define the conditional value at risk along with its standard estimator. In Section 3, we recall the statistical learning setting and present our PAC-Bayesian bound for CVAR. The proof of our main bound is in Section 4. In Section 5, we present a new way of deriving concentration bounds for CVAR which stems from our analysis in Section 4. Section 6 concludes and suggests future directions.

Preliminaries

Let (Ω, F , P ) be a probability space. For p ∈ N, we denote by L p (Ω) ∶= L p (Ω, F , P ) the space of p-integrable functions, and we let M P (Ω) be the set of probability measures on Ω which are absolutely continuous with respect to P . We reserve the notation E for the expectation under the reference measure P , although we sometimes write E P for clarity. For random variables Z 1 , . . . , Z n , we denote Pn ∶= ∑ n i=1 δ Zi n the empirical distribution, and we let Z 1∶n ∶= (Z 1 , . . . , Z n ). Furthermore, we let π ∶= (1, . . . , 1) ⊺ n ∈ R n be the uniform distribution on the simplex. Finally, we use the notation Õ to hide log-factors in the sample size n.

Coherent Risk Measures (CRM).

A CRM [START_REF] Artzner | Coherent measures of risk[END_REF] is a functional R∶ L1 (Ω) → R ∪ {+∞} that is simultaneously, positive homogeneous, monotonic, translation equivariant, and sub-additive 1 (see Appendix B for a formal definition). For α ∈ (0, 1) and a real random variable Z ∈ L 1 (Ω), the conditional value at risk CVAR α [Z] is a CRM and is defined as the mean of the random variable Z conditioned on the event that Z is greater than its (1α)-th quantile 2 . This is equivalent to the following expression, which is more convenient for our analysis:

CVAR α [Z] = C α [Z] ∶= inf µ∈R µ + E[Z -µ] + α .
Key to our analysis is the dual representation of CRMs. It is known that any CRM R∶ L 1 (Ω) → R ∪ {+∞} can be expressed as the support function of some closed convex set Q ⊆ L 1 (Ω) [START_REF] Tyrrell | The fundamental risk quadrangle in risk management, optimization and statistical estimation[END_REF]; that is, for any real random variable Z ∈ L 1 (Ω), we have

R[Z] = sup q∈Q E P [Zq] = sup q∈Q Ω Z(ω)q(ω)dP (ω). (dual representation) (1)
In this case, the set Q is called the risk envelope associated with the risk measure R. The risk envelope Q α of CVAR α [Z] is given by

Q α ∶= q ∈ L 1 (Ω) ∃Q ∈ M P (Ω), q = dQ dP ≤ 1 α , (2)
and so substituting

Q α for Q in (1) yields CVAR α [Z].
Though the overall approach we take in this paper may be generalizable to other popular CRMs, (see Appendix B) we focus our attention on CVAR for which we derive new PAC-Bayesian and concentration bounds in terms of its natural estimator CVAR α [Z]; given i.i.d. copies of Z 1 , . . . , Z n of Z, we define

CVAR α [Z] ∶= Ĉα [Z] ∶= inf µ∈R µ + n i=1 [Z i -µ] + nα . (3)
From now on, we write C α [Z] and Ĉα [Z] for CVAR α [Z] and CVAR α [Z], respectively.

PAC-Bayesian Bound for the Conditional Value at Risk

In this section, we briefly describe the statistical learning setting, formulate our goal, and present our main results.

In the statistical learning setting, Z is a loss random variable which can be written as Z = ℓ(h, X), where ℓ∶ H × X → R ≥0 is a loss function and X [resp. H] is a feature [resp. hypotheses] space. The aim is to learn an hypothesis ĥ = ĥ(X 1∶n ) ∈ H, or more generally a distribution ρ = ρ(X 1∶n ) over H (also referred to as randomized estimator), based on i.i.d. samples X 1 , . . . , X n of X which minimizes some measure of risk-typically, the expected risk

E P [ℓ(ρ, X)], where ℓ(ρ, X) ∶= E h∼ρ [ℓ(h, X)].
Our work is motivated by the idea of replacing this expected risk by any coherent risk measure R.

In particular, if Q is the risk envelope associated with R, then our quantity of interest is

R[ℓ(ρ, X)] ∶= sup q∈Q Ω ℓ(ρ, X(ω))q(ω)dP (ω).
Thus, given a consistent estimator R[ℓ(ρ, X)] of R[ℓ(ρ, X)] and some prior distribution ρ 0 on H, our grand goal (which goes beyond the scope of this paper) is to bound the

risk R[ℓ(ρ, X)] as R[ℓ(ρ, X)] ≤ R[ℓ(ρ, X)] + Õ ⎛ ⎝ KL(ρ ρ 0 ) n ⎞ ⎠ , (4)
with high probability. Based on (3), the consistent estimator we use for C

α [ℓ(ρ, X)] is Ĉα [ℓ(ρ, X)] ∶= inf µ∈R µ + n i=1 [ℓ(ρ, X i ) -µ] + nα , α ∈ (0, 1). (5)
This is in fact a consistent estimator (see e.g. [Duchi and Namkoong, 2018, Proposition 9]). As a first step towards the goal in (4), we derive a sharp PAC-Bayesian bound for the conditional value at risk, which we state now as our main theorem: Theorem 1. Let α ∈ (0, 1), δ ∈ (0, 1 2), n ≥ 2, and N ∶= ⌈log 2 (n α)⌉. Further, let ρ 0 be any distribution on a hypothesis set H, ℓ∶ H × X → [0, 1] be a loss, and X 1 , . . . , X n be i.i.d. copies of X. Then, for any "posterior" distribution ρ = ρ(X 1∶n ) over H, ε n ∶= ln(N δ) 2αn

+ ln(N δ) 3αn , and K n ∶= KL(ρ ρ 0 ) + ln(N δ), we have, with probability at least 1 -2δ.

E h∼ρ [C α [ℓ(h, X)]] ≤ Ĉα [ℓ(ρ, X)] + 27 Ĉα [ℓ(ρ, X)]K n 5αn + 2ε n Ĉα [ℓ(ρ, X)] + 27K n 5nα . (6)
Discussion of the bound. Although we present the bound for the bounded loss case, our result easily generalizes to the case where ℓ(h, X) is sub-Gaussian or sub-exponential, for all h ∈ H. We discuss this in Section 5. Our second observation is that since [START_REF] Tyrrell | The fundamental risk quadrangle in risk management, optimization and statistical estimation[END_REF], and so we can further bound the term

C α [Z] is a coherent risk mea- sure, it is convex in Z [Rockafellar
E h∼ρ [C α [ℓ(h, X)]] on the LHS of (6) from below by C α [ℓ(ρ, X)] = C α [E h∼ρ [ℓ(h, X)]]
. This shows that the type of guarantee we have in ( 6) is in general tighter than the one in (4).

Even though not explicitly done before, a PAC-Bayesian bound of the form (4) can be derived for a risk measure R using an existing technique due to [START_REF] Mcallester | PAC-Bayesian Stochastic Model Selection[END_REF] as soon as, for any fixed hypothesis h,

the difference R[ℓ(h, X)] -R[ℓ(h, X)
] is sub-exponential with a sufficiently fast tail decay as a function of n (see the proof of Theorem 1 in [START_REF] Mcallester | PAC-Bayesian Stochastic Model Selection[END_REF]

[C α [ℓ(h, X)]] (i.e. the LHS of (6)) of the form E h∼ρ [ Ĉα [ℓ(h, X)]] + KL(ρ ρ 0 ) + ln n δ αn . ( 7
)
Such a bound is weaker than ours in two ways; (I) by Jensen's inequality the term Ĉα [ℓ(ρ, X)] in our bound (defined in ( 5)) is always smaller than the term E h∼ρ [ Ĉα [ℓ(h, X)]] in (7); and (II) unlike in our bound in (6), the complexity term inside the square-root in (7) does not multiply the empirical conditional value at risk Ĉα [ℓ(ρ, X)]. This means that our bound can be much smaller whenever Ĉα [ℓ(ρ, X)] is small-this is to be expected in the statistical learning setting since ρ will typically be picked by an algorithm to minimize the empirical value Ĉα [ℓ(ρ, X)]. This type of improved PAC-Bayesian bound, where the empirical error appears multiplying the complexity term inside the square-root, has been derived for the expected risk in works such as [START_REF] Catoni | PAC-Bayesian supervised classification: the thermodynamics of statistical learning[END_REF][START_REF] Langford | PAC-Bayes & margins[END_REF][START_REF] Maurer | A note on the PAC-Bayesian theorem[END_REF][START_REF] Seeger | PAC-Bayesian generalization error bounds for Gaussian process classification[END_REF]; these are arguably the state-of-theart generalization bounds.

A reduction to the expected risk. A key step in the proof of Theorem 1 is to show that for a real random variable Z (not necessarily bounded) and α ∈ (0, 1), one can construct a function g∶ R → R such that the auxiliary variable Y = g(Z) satisfies (I)

E[Y ] = E[g(Z)] = C α [Z]; (8) and (II) for i.i.d. copies Z 1∶n of Z, the i.i.d. random variables Y 1 ∶= g(Z 1 ), . . . , Y n ∶= g(Z n ) satisfy 1 n n i=1 Y i ≤ Ĉα [Z](1 + ǫ n ), where ǫ n = Õ(α -1 2 n -1 2 ), (9)
with high probability. Thus, due to ( 8) and ( 9), bounding the difference

E[Y ] - 1 n n i=1 Y i , (10)
is sufficient to obtain a concentration bound for CVAR. Since Y 1 , . . . , Y n are i.i.d., one can apply standard concentration inequalities, which are available whenever Y is sub-Gaussian or subexponential, to bound the difference in (10). Further, we show that whenever Z is sub-Gaussian or sub-exponential, then essentially so is Y . Thus, our method allows us to obtain concentration inequalities for Ĉα [Z], even when Z is unbounded. We discuss this in Section 5.

Proof Sketch for Theorem 1

In this section, we present the key steps taken to prove the bound in Theorem 1. We organize the proof in three subsections. In Subsection 4.1, we introduce an auxiliary estimator Cα [Z] for C α [Z], α ∈ (0, 1), which will be useful in our analysis; in particular, we bound this estimator in terms of Ĉα [Z] (as in (9) above, but with the LHS replaced by Cα [Z]). In Subsection 4.2, we introduce an auxiliary random variable Y whose expectation equals C α [Z] (as in ( 8)) and whose empirical mean is bounded from above by the estimator Cα [Z] introduced in Subsection 4.1-this enables the reduction described at the end of Section 3. In Subsection 4.3, we conclude the argument by applying the classical Donsker-Varadhan variational formula [Csiszár, 1975, Donsker and[START_REF] Donsker | Asymptotic evaluation of certain Markov process expectations for large time -III[END_REF].

An Auxiliary Estimator for CVAR

In this subsection, we introduce an auxiliary estimator Cα [Z] of C α [Z] and show that it is not much larger than Ĉα [Z]. For α, δ ∈ (0, 1), n ∈ N, and π ∶= (1, . . . , 1) ⊺ n ∈ R n , define:

Qα ∶= {q ∈ [0, 1 α] n ∶ E i∼π [q i ] -1 ≤ ǫ n } , where ǫ n ∶= ln 1 δ 2αn + ln 1 δ 3αn . ( 11
)
Using the set Qα , and given i.

i.d. copies Z 1 , . . . , Z n of Z, let Cα [Z] ∶= sup q∈ Qα 1 n n i=1 Z i q i . (12)
In the next lemma, we give a "variational formulation" of Cα [Z], which will be key in our results:

Lemma 2. Let α, δ ∈ (0, 1), n ∈ N, and Cα [Z] be as in (12). Then, for any Z 1 , . . . , Z n ∈ R,

Cα [Z] = inf µ∈R µ + µ ǫ n + E i∼π [Z i -µ] + α
, where ǫ n as in (11). ( 13)

The proof of Lemma 2 (which is in Appendix A.1) is similar to that of the generalized Donsker-Varadhan variational formula considered in [START_REF] Beck | Mirror descent and nonlinear projected subgradient methods for convex optimization[END_REF]. The "variational formulation" on the RHS of ( 13) reveals some similarity between Cα [Z] and the standard estimator Ĉα [Z] defined in (3). In fact, thanks to Lemma 2, we have the following relationship between the two:

Lemma 3. Let α, δ ∈ (0, 1), n ∈ N, and Z 1 , . . . , Z n ∈ R ≥0 . Further, let Z (1) , . . . , Z (n) be the decreasing order statistics of Z 1 , . . . , Z n . Then, for ǫ n as in (11), we have

Cα [Z] ≤ Ĉα [Z] ⋅ (1 + ǫ n ); (14
)

and if Z 1 , . . . , Z n ∈ R (not necessarily positive), then Cα [Z] ≤ Ĉα [Z] + Z (⌈nα⌉) ⋅ ǫ n . (15)
The inequality in (15) will only be relevant to us in the case where Z maybe negative, which we deal with in Section 5 when we derive new concentration bounds for CVAR.

An Auxiliary Random Variable

In this subsection, we introduce a random variable Y which satisfies the properties in ( 8) and ( 9), where Y 1 , . . . , Y n are i.i.d. copies of Y (this is where we leverage the dual representation in ( 1)). This allows us to the reduce the problem of estimating CVAR to that of estimating an expectation.

Let X be an arbitrary set, and f ∶ X → R be some fixed measurable function (we will later set f to a specific function depending on whether we want a new concentration inequality or a PAC-Bayesian bound for CVAR). Given a random variable X in X (arbitrary for now), we define

Z ∶= f (X) (16)
and the auxiliary random variable:

Y ∶= Z ⋅ E[q ⋆ X] = f (X) ⋅ E[q ⋆ X], where q ⋆ ∈ argmax q∈Qα E[Zq], (17)
and Q α as in (2). In the next lemma, we show two crucial properties of the random variable Ythese will enable the reduction mentioned at the end of Section 3:

Lemma 4. Let α, δ ∈ (0, 1) and X 1 , . . . , X n be i.i.d. random variables in X . Then, (I) the random variable Y in (17) and

Y i ∶= Z i ⋅ E[q ⋆ X i ], i ∈ [n]
, where Z i ∶= f (X i ), are i.i.d. and satisfy

E[Y ] = E[Y i ] = C α [Z], for all i ∈ [n]; and (II) with probability at least 1 -δ, (E[q ⋆ X 1 ], . . . , E[q ⋆ X n ]) ⊺ ∈ Qα , where Qα is as in (11). ( 18
)
The random variable Y introduced in (17) will now be useful since due to (18) in Lemma 4, we have, for α, δ ∈ (0, 1); Z as in (16); and i.i.d. random variables X, X 1 , . . . , X n ∈ X ,

P 1 n n i=1 Y i ≤ Cα [Z] ≥ 1 -δ, where Y i = Z i ⋅ E[q ⋆ X i ] (19)
and Cα [Z] as in (12). We now present a concentration inequality for the random variable Y in (17); the proof, which can be found in Appendix A, is based on a version of the standard Bernstein's moment inequality [Cesa-Bianchi and Lugosi, 2006, Lemma A.5]:

Lemma 5. Let X, (X i ) i∈[n] be i.i.d. random variables in X . Further, let Y be as in (17), and

Y i = f (X i ) ⋅ E[q ⋆ X i ], i ∈ [n], with q ⋆ as in (17). If {f (x) x ∈ X } ⊆ [0, 1], then for all η ∈ [0, α], E exp nη ⋅ E P [Y ] - 1 n n i=1 Y i - ηκ(η α) α C α [Z] ≤ 1, where Z = f (X),
and κ(x) ∶= (e x -1x) x 2 , for x ∈ R.

Lemma 5 will be our starting point for deriving the PAC-Bayesian bound in Theorem 1.

Exploiting the Donsker-Varadhan Formula

In this subsection, we instantiate the results of the previous subsections with f (⋅) ∶= ℓ(⋅, h), h ∈ H, for some loss function ℓ∶ H × X → [0, 1]; in this case, the results of Lemmas 3 and 5 hold for

Z = Z h ∶= ℓ(h, X), (20)
for any hypothesis h ∈ H. Next, we will need the following result which follows from the classical Donsker-Varadhan variational formula [Csiszár, 1975, Donsker and[START_REF] Donsker | Asymptotic evaluation of certain Markov process expectations for large time -III[END_REF]]:

Lemma 6. Let δ ∈ (0, 1), γ > 0 and ρ 0 be any fixed (prior) distribution over H. Further, let {R h ∶ h ∈ H} be any family of random variables such that E[exp(γR h )] ≤ 1, for all h ∈ H. Then, for any (posterior) distribution ρ over H, we have

P E h∼ρ [R h ] ≤ KL(ρ ρ 0 ) + ln 1 δ γ ≥ 1 -δ. In addition to Z h in (20), define Y h ∶= ℓ(h, X) ⋅ E[q ⋆ X] and Y h,i ∶= ℓ(h, X i ) ⋅ E[q ⋆ X i ], for i ∈ [n]. Then, if we set γ = ηn and R h = E P [Y h ] -∑ n i=1 Y h,i n -ηκ(η α)C α [Z h ] α, Lemma 5 guarantees that E[exp(γR h )]
≤ 1, and so by Lemma 6 we get the following result: Theorem 7. Let α, δ ∈ (0, 1), and η ∈ [0, α]. Further, let X 1 , . . . , X n be i.i.d. random variables in X . Then, for any randomized estimator ρ = ρ(X 1∶n ) over H, we have, with

Ẑ ∶= E h∼ρ [ℓ(h, X)], E h∼ρ [C α [ℓ(h, X)]] ≤ Ĉα [ Ẑ](1 + ǫ n ) + ηκ(η α) E h∼ρ [C α [ℓ(h, X)]] α + KL(ρ ρ 0 ) + ln 1 δ ηn , (21)
with probability at least 1 -2δ on the samples X 1 , . . . , X n , where ǫ n is defined in (11).

If we could optimize the RHS of ( 21) over η ∈ [0, α], this would lead to our desired bound in Theorem 1 (after some rearranging). However, this is not directly possible since the optimal η depends on the sample X 1∶n through the term KL(ρ ρ 0 ). The solution is to apply the result of Theorem 7 with a union bound, so that (21) holds for any estimator η = η(X 1∶n ) taking values in a carefully chosen grid G; to derive our bound, we will use the grid G ∶= α2 -1 , . . . , α2 -N N ∶= ⌈1 2 log 2 (n α)⌉ .

From this point, the proof of Theorem 1 is merely a mechanical exercise of rearranging (21) and optimizing η over G, and so we postpone the details to Appendix A.

New Concentration Bounds for CVAR

In this section, we show how some of the results of the previous section can be used to reduce the problem of estimating C α [Z] to that of estimating a standard expectation. This will then enable us to easily obtain concentration inequalities for Ĉα [Z] even when Z is unbounded. We note that previous works [Bhat and Prashanth, 2019[START_REF] Kumar Kolla | Concentration bounds for empirical conditional value-at-risk: The unbounded case[END_REF] used sophisticated techniques to deal with the unbounded case (sometimes achieving only sub-optimal rates), whereas we simply invoke existing concentration inequalities for empirical means thanks to our reduction.

The key results we will use are Lemmas 3 and 4, where we instantiate the latter with X = R and f ≡ id, in which case:

Y = Z ⋅ E[q ⋆ Z], and q ⋆ ∈ argmax q∈Qα E[Zq]. (22)
Together, these two lemmas imply that, for any α, δ ∈ (0, 1), i.i.d. random variables Z 1 , . . . , Z n ,

C α [Z] -Ĉα [Z] -Z (⌈nα⌉) ǫ n ≤ E[Y ] - 1 n n i=1 Y i , (23)
with probability at least 1δ, where ǫ n is as in (11) and Z (1) , . . . , Z (n) are the decreasing order statistics of Z 1 , . . . , Z n ∈ R. Thus, getting a concentration inequality for Ĉα [Z] can be reduced to getting one for the empirical mean ∑ n i=1 Y i n of the i.i.d. random variables Y 1 , . . . , Y n . Next, we show that whenever Z is a sub-exponential [resp. sub-Gaussian] random variable, essentially so is Y . But first we define what this means: Definition 8. Let I ⊆ R, b > 0, and Z be a random variable such that, for some σ > 0,

E[η ⋅ (Z -E[Z])] ≤ exp η 2 σ 2 2 , ∀η ∈ I, Then, Z is (σ, b)-sub-exponential [resp. σ-sub-Gaussian] if I = (-1 b, 1 b) [resp. I = R].
Lemma 9. Let σ, b > 0 and α ∈ (0, 1). Let Z be a zero-mean real random variable and let Y be as in (22).

If Z is (σ, b)-sub-exponential [resp. σ-sub-Gaussian], then E[exp(ηY )] ≤ 2 exp(η 2 σ 2 (2α 2 )), ∀η ∈ (-α b, α b) [resp. η ∈ R]. (24)
Note that in Lemma 9 we have assumed that Z is a zero-mean random variable, and so we still need to do some work to derive a concentration inequality for Ĉα [Z]. In particular, we will use the fact that

C α [Z -E[Z]] = C α [Z] -E[Z] and Ĉα [Z -E[Z]] = Ĉα [Z] -E[Z]
, which holds since C α and Ĉα are coherent risk measures, and thus translation invariant (see Definition 14). We use this in the proof of the next theorem (which is in Appendix A): Theorem 10. Let σ, b > 0, α, δ ∈ (0, 1), and ǫ n be as in (11).

If Z is a σ-sub-Gaussian random variable, then with G[Z] ∶= C α [Z] -Ĉα [Z] and t n ∶= Z (⌈nα⌉) -E[Z] ⋅ ǫ n , we have P [G[Z] ≥ t + t n ] ≤ δ + 2 exp(-nα 2 t 2 (2σ 2 )), ∀t ≥ 0; (25) otherwise, if Z is (σ, b)-sub-exponential random variable, then P [G[Z] ≥ t + t n ] ≤ δ + 2 exp -nα 2 t 2 (2σ 2 ) , if 0 ≤ t ≤ σ 2 (bα); 2 exp (-nαt (2b)) , if t > σ 2 (bα).
We note that unlike the recent results due to Bhat and Prashanth [2019] which also deal with the unbounded case, the constants in our concentration inequalities in Theorem 10 are explicit.

When Z is a σ-sub-Gaussian random variable with σ > 0, an immediate consequence of Theorem 10 is that by setting t = 2σ 2 ln(2 δ) (nα 2 ) in ( 25), we get that, with probability at least 1 -2δ,

C α [Z] -Ĉα [Z] ≤ σ α 2 ln 1 δ n + Z (⌈nα⌉) -E[Z] ⋅ ⎛ ⎜ ⎝ ln 1 δ 2αn + ln 1 δ 3αn ⎞ ⎟ ⎠ . ( 26
)
A similar inequality holds for the sub-exponential case. We note that the term Z (⌈nα⌉) -E[Z] in (26) can be further bounded from above by

nα ⌊nα⌋ Ĉα [Z] -E Pn [Z] + E[Z] -E Pn [Z] . ( 27
)
This follows from the triangular inequality and facts that Ĉα 27) which depends on the unknown P can be bounded from above using another concentration inequality.

[Z] ≥ 1 nα ∑ ⌊nα⌋ i=1 Z (i) ≥ ⌊nα⌋ nα Z (⌈nα⌉) (see e.g. Lemma 4.1 in Brown [2007]), and Ĉα [Z] ≥ E Pn [Z] [Ahmadi-Javid, 2012]. The remaining term E P [Z]-E Pn [Z] in (
Generalization bounds of the form (4) for unbounded but sub-Gaussian or sub-exponential ℓ(h, X), h ∈ H, can be obtained using the PAC-Bayesian analysis of [START_REF] Mcallester | PAC-Bayesian Stochastic Model Selection[END_REF] Theorem 1] and our concentration inequalities in Theorem 10. However, due to the fact that α is squared in the argument of the exponentials in these inequalities (which is also the case in the bounds of Bhat and Prashanth [2019], [START_REF] Kumar Kolla | Concentration bounds for empirical conditional value-at-risk: The unbounded case[END_REF]) the generalization bounds obtained this way will have the α outside the square-root "complexity term"-unlike our bound in Theorem 1.

We conjecture that the dependence on α in the concentration bounds of Theorem 10 can be improved by swapping α 2 for α in the argument of the exponentials; in the sub-Gaussian case, this would move α inside the square-root on the RHS of (26). We know that this is at least possible for bounded random variables as shown in [START_REF] David | Large deviations bounds for estimating conditional value-at-risk[END_REF], [START_REF] Wang | Deviation inequalities for an estimator of the conditional value-at-risk[END_REF]. We now recover this fact by presenting a new concentration inequality for Ĉα [Z] when Z is bounded using the reduction described at the beginning of this section. Theorem 11. Let α, δ ∈ (0, 1), and Z 1∶n be i.i.d. rvs in [0, 1]. Then, with probability at least 1 -2δ,

C α [Z] -Ĉα [Z] ≤ 12C α [Z] ln 1 δ 5αn ∨ 3 ln 1 δ αn + C α [Z] ⎛ ⎜ ⎝ ln 1 δ 2αn + ln 1 δ 3αn ⎞ ⎟ ⎠ . ( 28
)
The proof is in Appendix A. The inequality in (28) essentially replaces the range of the random variable Z typically present under the square-root in other concentration bounds [Brown, 2007, Wang and[START_REF] Wang | Deviation inequalities for an estimator of the conditional value-at-risk[END_REF] by the smaller quantity C α [Z]. The concentration bound ( 28) is not immediately useful for computational purposes since its RHS depends on C α [Z]. However, it is possible to rearrange this bound so that only the empirical quantity Ĉα [Z] appears on the RHS of ( 28) instead of C α [Z]; we provide the means to do this in Lemma 13 in the appendix.

Conclusion and Future Work

In this paper, we derived a first PAC-Bayesian bound for CVAR by reducing the task of estimating CVAR to that of merely estimating an expectation (see Section 4). This reduction then made it easy to obtain concentration inequalities for CVAR (with explicit constants) even when the random variable in question is unbounded (see Section 5).

We note that the only steps in the proof of our main bound in Theorem 1 that are specific to CVAR are Lemmas 2 and 3, and so the question is whether our overall approach can be extended to other coherent risk measures to achieve (4).

In Appendix B, we discuss how our results may be extended to a rich class of coherent risk measures known as ϕ-entropic risk measures. These CRMs are often used in the context of robust optimization [START_REF] Namkoong | Variance-based regularization with convex objectives[END_REF], and are perfect candidates to consider next in the context of this paper.

A Proofs

A.1 Proof of Lemma 2

Proof Let ϕ(⋅) ∶= ι [0,1 α] (⋅), where for a set C ⊆ R, ι C (x) = 0 if x ∈ C; and +∞ otherwise. From (12), we have that Cα [Z] is equal to

P ∶= sup q∶ Ei∼π[qi]-1 ≤ǫn E i∼π [Z i q i -ϕ(q i )], (29)
where we recall that π = (1, . . . , 1) ⊺ n ∈ R n . The Lagrangian dual D of ( 29) is given by

D ∶= inf η,γ≥0 ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ η -γ + (η + γ)ǫ n + sup q∶0≤qi ≤1 α,i∈[n] {E i∼π [(Z i -η + γ)q i -ϕ(q i )]} ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ , = inf η,γ≥0 ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ η -γ + (η + γ)ǫ n + E i∼π ⎡ ⎢ ⎢ ⎢ ⎣ sup 0≤x≤1 α {(Z i -η + γ)x -ϕ(x)} ⎤ ⎥ ⎥ ⎥ ⎦ ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭ , = inf η,γ≥0 {η -γ + (η + γ)ǫ n + E i∼π [ϕ ⋆ (Z i -η + γ)]} , (30)
= inf µ∈R {µ + µ ǫ n + E i∼π [ϕ ⋆ (Z i -µ)]} , (31)
where ( 30) is due to {x ∈ R ϕ(x) < +∞} = [0, 1 α], and (31) follows by setting µ ∶= ηγ and noting that the inf in ( 30) is always attained at a point (η, γ) ∈ R 2 ≥0 satisfying η ⋅ γ = 0, in which case η + γ = µ ; this is true because by the positivity of ǫ n , if η, γ > 0, then (η + γ)ǫ n can always be made smaller while keeping the difference η -γ fixed. Finally, since the primal problem is feasible-q = π is a feasible solution-there is no duality gap (see the proof of [Beck and Teboulle, 2003, Theorem 4.2]), and thus the RHS of ( 31) is equal to P in (29). The proof is concluded by noting that the Fenchel dual of ϕ satisfies ϕ ⋆ (z) = 0 ∨ (z α), for all z ∈ R. ∎

A.2 Proof of Lemma 3

Proof Let μ be the argmin in µ ∈ R of the RHS of (3). By Lemma 2, we have

Cα [Z] = inf µ∈R µ + µ ǫ n + E i∼π [Z i -µ] + α , ≤ μ + μ ǫ n + E i∼π [Z i -μ)] + α , = Ĉα [Z] + μ ǫ n . (by definition of μ) (32)
The inequality in (15) follows from (32) and the fact that μ = Z (⌈nα⌉) (see proof of [Brown, 2007, Proposition 4.1]).

Now we show (14) under the assumption that

Z i ≥ 0, for all i ∈ [n]. Note that by definition Ĉα [Z] = μ + 1 α E i∼π [Z i -μ] + , and so μ ≤ Ĉα [Z]. Furthermore, since α ∈ (0, 1) and Z i ≥ 0, for i ∈ [n]
, the RHS of (3) is a decreasing function of µ on ] -∞, 0], and thus μ ≥ 0 (since μ is the minimizer of (3)). Combining the fact that 0 ≤ μ ≤ Ĉα [Z] with (32) completes the proof. ∎

A.3 Proof of Lemma 4

Proof The first claim follows by the fact that X i , i ∈ [n], are i.i.d., and an application of the total expectation theorem. Now for the second claim, let ∆ ∶= E Pn [q ⋆ X] -1 . Since q ⋆ is a density, the total expectation theorem implies

∆ = E Pn [q ⋆ X] -E[E[q ⋆ X]] ,
and so by Bennett's inequality (see e.g. Theorem 3 in [START_REF] Maurer | Empirical Bernstein bounds and sample variance penalization[END_REF]) applied to the random variable E[q ⋆ X], we get that, with probability at least 1δ,

∆ ≤ VAR[E[q ⋆ X]] ln 1 δ 2n + E[q ⋆ X] ∞ ln 1 δ 3n , ≤ E[E[q ⋆ X] 2 ] ln 1 δ 2n + E[q ⋆ X] ∞ ln 1 δ 3n , ≤ E[q ⋆ X] ∞ ln 1 δ 2n + E[q ⋆ X] ∞ ln 1 δ 3n ,
where the last inequality follows by the fact that E

[E[q ⋆ X] 2 ] ≤ E[E[q ⋆ X]] ⋅ E[q ⋆ X] ∞ = E[q ⋆ X] ∞ , which holds since E[q ⋆ X] ≥ 0 and E[E[q ⋆ X]] = E[q ⋆ ] = 1.
The proof is concluded by the facts that E[q ⋆ X] ∞ ≤ q ⋆ ∞ (by Jensen's inequality); q ∞ ≤ 1 α, for all q ∈ Q α by definition; and q ⋆ ∈ Q α . ∎

A.4 Proof of Lemma 5

We need the following lemma in the proof of Lemma 5:

Lemma 12. Let S, S 1 , . . . , S n be i.i.d. random variable such that S ∈ [0, B], B > 0. We have,

E P exp nη E P [S] -η n i=1 S i -nη 2 κ(ηB) ⋅ E P [S 2 ] ≤ 1, ( 33
)
for all η ∈ [0, 1 B], where κ(η) ∶= (e ηη -1) η 2 .

Proof The desired bound follows by the version of Bernstein's moment inequality in [Cesa-Bianchi and Lugosi, 2006, Lemma A.5] and [START_REF] Mhammedi | PAC-Bayes Un-Expected Bernstein Inequality[END_REF]

E[Y 2 ] = E[Z 2 ⋅ E[q ⋆ X] 2 ], ≤ E[Z ⋅ E[q ⋆ X]] ⋅ Z ⋅ E[q ⋆ X] ∞ , (Hölder) ≤ C α [Z] ⋅ Z ⋅ E[q ⋆ X] ∞ , (Lemma 4) ≤ C α [Z] α, (Z ≤ 1, q ⋆ ≤ 1 α)
where the fact that q ⋆ ≤ 1 α follows simply from q ⋆ ∈ Q α and the definition of Q α . We also have

Y ∞ = Z ⋅ E[q ⋆ X] ∞ ≤ Z ∞ ⋅ E[q ⋆ X] ∞ , ≤ q ⋆ ∞ , (Z ≤ 1 & Jensen) ≤ 1 α,
again the last inequality follows from q ⋆ ∈ Q α and the definition of Q α . ∎

A.5 Proof of Theorem 7

Proof Let h ∈ H and α, δ ∈ (0, 1), and define

R h ∶= C α [Z h ] - 1 n n i=1 Y i - ηκ(η α) α C α [Z h ], (34)
where

Y i ∶= ℓ(h, X i ) ⋅ E[q ⋆ X i ], i ∈ [n]
, where q ⋆ is as in ( 17) with Z as in (20). By Lemma 4,

C α [Z h ] = E P [Y ],
where Y ∶= ℓ(h, X) ⋅ E[q ⋆ X]. Thus, by Lemma 5 with Z = Z h , we have E P [exp(nηR h )] ≤ 1. Applying Lemma 6 with R h as in ( 34) and γ = nη, yields,

E h∼ρ [C α [ℓ(h, X)]] ≤ 1 n n i=1 ℓ(ρ, X i ) ⋅ E[q ⋆ X i ] + ηκ(η α) E h∼ρ [C α [ℓ(h, X)]] α + KL(ρ ρ 0 ) + ln 1 δ ηn , (35)
with probability at least 1δ. Now invoking Lemmas 3 and 4 (in particular ( 18)), yields

1 n n i=1 ℓ(ρ, X i ) ⋅ E[q ⋆ X i ] ≥ Ĉα [ Ẑ] ⋅ (1 + ǫ n ).
with probability at least 1δ, where Ẑ ∶= E h∼ρ [ℓ(h, X)]. Combining this with (35) via a union bound yields the desired bound. ∎

A.6 Proof of Theorem 1

To prove Theorem 1, we will need the following lemma:

Lemma 13. Let R, R, A, B > 0. If R ≤ R + √ RA + B, then R ≤ R + RA + 2B + A. Proof If R ≤ R + √ RA + B, then for all η > 0, R ≤ R + η 2 R + A 2η + B,
which after rearranging, becomes,

R ≤ R 1 -η 2 + A 2η ⋅ (1 -η 2) + B 1 -η 2 , for η ∉ {0, 2}. (36)
The minimizer of the RHS of ( 36) is given by

η = η ⋆ ∶= -A + A 2 + 4AB + 4A R 2(B + R) .
Plugging this η into (36), yields,

R ≤ R + A 2 + B + 1 2 4A R + A 2 + 4AB, ≤ R + A + 2B + A R, (37)
where (37) follows by the facts that A 2 + 4AB ≤ (A + 2B) 2 and 4 RA

+ (A + 2B) 2 ≤ 4 RA + A + 2B. ∎ Proof of Theorem 1 Define the grid G by G ∶= 2 -1 α, . . . , 2 -N α N ∶= ⌈1 2 ⋅ log 2 n α ⌉
, and let η = η(Z 1∶n ) ∈ G be any estimator. Then, using the fact that κ(x) ≤ 3 5, for all x ≤ 1 2, and invoking Theorem 7 with a union bound over η ∈ G, and ε n ∶=

ln N δ 2αn + ln N δ 3αn , we get that E h∼ρ [C α [ℓ(h, X)]] -Ĉα [ Ẑ] ⋅ (1 + ε n ) ≤ KL(ρ ρ 0 ) + ln N δ ηn + 3η 5α E h∼ρ [C α [ℓ(h, X)]], (38)
with probability at least 1 -2δ, where we recall that Ẑ = E h∼ρ [ℓ(h, X)]. Let η be an estimator which satisfies

η ∈ [η ⋆ ∧ (α 2), 2η ⋆ ] ∩ G, where η ⋆ ∶= 5α ⋅ (KL(ρ ρ 0 ) + ln N δ ) 3n E h∼ρ [C α [ℓ(h, X)]] (39)
is the unconstrained minimizer η of the RHS of (38). Since the loss ℓ has range in [0, 1], KL(ρ ρ 0 ) ≥ 0, and (δ, n) ∈]0, 1 2[×[2, +∞[, we have η ⋆ ≥ α n ≥ min G. This, with the fact that G is in the form of a geometric progression with common ratio 2 and max G = α 2, ensures the existence (and in fact the uniqueness) of η satisfying (39).

Case 1. Suppose that η ⋆ ≤ α 2. In this case, the estimator η in (39) satisfies η

⋆ ≤ η ≤ 2η ⋆ . Plugging η into (38) yields E h∼ρ [C α [ℓ(h, X)]] -Ĉα [ Ẑ] ≤ 3 3 E h∼ρ [C α [ℓ(h, X)]] ⋅ (KL(ρ ρ 0 ) + ln N δ ) 5αn + Ĉα [ Ẑ] ⋅ ε n . By applying Lemma 13 with R = E h∼ρ [C α [ℓ(h, X)]], R = Ĉα [ Ẑ], A = 27(KL(ρ ρ0)+ln N δ ) 5αn
, and

B = Ĉα [ Ẑ] ⋅ ε n , we get E h∼ρ [C α [ℓ(h, X)]] -Ĉα [ Ẑ] ≤ 27 Ĉα [ Ẑ] ⋅ (KL(ρ ρ 0 ) + ln N δ ) 5αn + 2 Ĉα [ Ẑ] ⋅ ε n + 27(KL(ρ ρ 0 ) + ln N δ ) 5nα . ( 40
)
Case 2. Suppose now that η ⋆ > α 2. In this case, η = α 2. Plugging this into (38) and using the fact that η ⋆ > α 2, yields

E h∼ρ [C α [ℓ(h, X)]] -Ĉα [ Ẑ] ≤ 4(KL(ρ ρ 0 ) + ln N δ ) αn + Ĉα [ Ẑ] ⋅ ε n . (41)
Since Ĉα [ Ẑ] ≥ 0 and 4 ≤ 27 5, the RHS of ( 41) is less than the RHS of ( 40), which completes the proof.

∎ A.7 Proof of Lemma 9 Proof Suppose that Z is (σ, b)-sub-exponential. Then, E[e ηZ ] ≤ e η 2 σ 2 2 , ∀ η ≤ 1 b. (42)
Using that E[q ⋆ Z] ≤ 1 α, and Cauchy-Schwartz, we get

ηY ≤ ηZ α, ∀η ∈ R, (43)
and so, for all η ≤ α b, we have

E[e ηY ] ≤ E[e ηY ] (43) ≤ E[e ηZ α ] + E[e -ηZ α ] (42) ≤ 2e η 2 σ 2 2α 2 .
When Z is σ-sub-Gaussian case, the proof is the same, except that we replace b by 0. ∎

A.8 Proof of Theorem 11

Proof Let X = [0, 1] and f ≡ id be the identity map. By invoking Lemmas 3 and 5 with Z = f (X) = X; and using (19) (which is a consequence of Lemma 4), we get, for all η ∈ [0, α],

E P exp nη ⋅ C α [Z] -Ĉα [Z](1 + ǫ n ) - ηκ(η α)C α [Z] α ≤ 1, (44)
with probability at least 1δ, where ǫ n is as in (11). By adding C α [Z] ⋅ ǫ n to both sides of (44) and using the fact that κ(x) ≤ 3 5, for all x ≤ 1 2, we get, for all η ∈ [0, α 2],

E P exp nη ⋅ C α [Z] -Ĉα [Z] - 3η 5α + ǫ n C α [Z] ≤ 1, (45)
with probability at least 1

-δ. Let W ∶= C α [Z] -Ĉα [Z] -3η 5α + ǫ n C α [Z],
and note that by (45), we have

P [E P [exp(nηW )] ≤ 1] ≥ 1 -δ.
Let E be the event that E P [exp(nηW )] ≤ 1. With this, we have, for any δ ∈ (0, 1) and all η ∈ [0, α 2],

P C α [Z] -Ĉα [Z] ≥ 3η 5α + ǫ n C α [Z] + ln 1 δ ηn = P e nηW ≥ 1 δ = P e nηW ≥ 1 δ E ⋅ P [E] + P e nηW ≥ 1 δ E c ⋅ (1 -P [E]), ≤ δ E[e nηW E] + δ, (46) ≤ 2δ, (by definition of E) (47)
where ( 46) follows by Markov's inequality and ( 45). Now, we can re-express (47) as

C α [Z] -Ĉα [Z] ≤ 3η 5α + ǫ n C α [Z] + ln 1 δ ηn ,
with probability at least 1 -2δ. By setting η = 5α ln 1 δ 3nCα[Z] ∧ α 2 (which does not depend on the samples), we get

C α [Z] -Ĉα [Z] ≤ ǫ n C α [Z] + 12C α [Z] ln 1 δ 5αn ∨ 3 ln 1 δ αn ,
with probability at least 1 -2δ. ∎

A.9 Proof of Theorem 10

Proof Let Z = Z -E[Z]. Suppose that Z is (σ, b)-sub-exponential. In this case, by Lemma 9 the random variable Y ∶= Z ⋅ E[q ⋆ Z] satisfies (24), and so by [Wainwright, 2019, Theorem 2.19], we have

P E[Y ] - 1 n n i=1 Y i ≥ t ≤ ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 2e -nα 2 t 2 2σ 2 , if 0 ≤ t ≤ σ 2 bα ; 2e -nαt 2b , if t > σ 2 bα . (48
P C α [ Z] -Ĉα [ Z] -Z(⌈nα⌉) ⋅ ǫ n ≥ t ≤ P C α [ Z] -Ĉα [ Z] -Z(⌈nα⌉) ⋅ ǫ n ≥ E[Y ] - 1 n n i=1 Y i + P E[Y ] - 1 n n i=1 Y i ≥ t , ≤ δ + ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 2e -nα 2 t 2 2σ 2 , if 0 ≤ t ≤ σ 2 bα ; 2e -nαt 2b , if t > σ 2 bα , (49)
where the last inequality follows by (48) and the fact that (23) (with Z replaced by Z) holds with probability at least 1δ. Since C α [Z] [resp. Ĉα [Z]] is a coherent risk measure, we have C α

[ Z] = C α [Z] -E[Z] [resp. Ĉα [ Z] = Ĉα [Z] -E[Z]],
and so the LHS of ( 49) is equal to

P C α [Z] -Ĉα [Z] ≥ t + Z(⌈nα⌉) ⋅ ǫ n .
This with the fact that Z(⌈nα⌉) = Z (⌈nα⌉) -E[Z] completes the proof for the sub-exponential case.

When Z is σ-sub-Gaussian case, the proof is the same, except that we replace b by 0 and use the convention that 0 0 = +∞. ∎

B Beyond CVAR

Q c ϕ ∶= q ∈ L 1 (Ω)
∃Q ∈ M P (Ω), q = dQ dP , D ϕ (Q P ) ≤ c , and D ϕ (Q P ) ∶= E P [ϕ(q)] is the ϕ-divergence between two distributions Q and P , where Q ≪ P and q = dQ dP .

As mentioned above, CVAR α [Z] is a ϕ-entropic risk measure; in fact, it is the ϕ-entropic risk measure at level c = 0 with ϕ(⋅) ∶= ι [0,1 α] (⋅), where for a set C ⊆ R, ι C (x) = 0 if x ∈ C; and +∞ otherwise Ahmadi-Javid [2012].

The natural estimator ER

Z i ⋅ E[q ⋆ Z i ] ≤ ER c ϕ [Z],
with high probability, where q ⋆ ∈ argmin q∈Q c ϕ E [Zq]. The similarities between the expressions of ER c ϕ [Z] and Ĉα [Z] hint that it might be possible to find such an estimator by carefully constructing a set Qc ϕ to play the role of the Qα in Section 4. We leave such investigations for future work.

  By Lemma 4, the random variables Y, Y 1 , . . . , Y n are i.i.d., and so the result of Lemma 12 applies; this means that (33) holds for (S, S 1 , . . . , S n ) = (Y, Y 1 , . . . , Y n ) and B = b ≥ Y ∞ . Thus, to complete the proof it suffices to bound Y ∞ and Y 2 2 = E[Y 2 ] from above. Starting with E[Y 2 ], and recalling that Z = f (X) ∈ [0, 1] by assumption, we have:

)

  For any real random variables A, B, and C, we have[A ≥ C] ⇒ [A ≥ B or B ≥ C], and so P [A ≥ C] ≤ P [A ≥ B] + P [B ≥ C]. Applying this with A = C α [ Z] -Ĉα [ Z] -Z(⌈nα⌉) ǫ n , B = E[Y ] -∑ n i=1 Y i n, and C = t ∈ R. we get:

First, we

  give a formal definition of a coherent risk measure (CRM): Definition 14. We say that R∶ L 1 (Ω) → R ∪ {+∞} is a coherent risk measure if, for any Z, Z ′ ∈ L 1 (Ω) and c ∈ R, it satisfies the following axioms: (Positive Homogeneity) R[λZ] = λR[Z], for all λ ∈ (0, 1); (Monotonicity) R[Z] ≤ R[Z ′ ] if Z ≤ Z ′ a.s.; (Translation Equivariance) R[Z + c] = R[Z] + c; (Sub-additivity) R[Z + Z ′ ] ≤ R[Z] + R[Z ′ ].It is known that the conditional value at risk is a member of a class of CRMs called ϕ-entropic risk measures Ahmadi-Javid[2012]. These CRMs are often used in the context of robust optimization[START_REF] Namkoong | Variance-based regularization with convex objectives[END_REF], and are perfect candidates to consider next in the context of this paper: Definition 15. Let ϕ∶ [0, +∞[→ R ∪ {+∞} be a closed convex function such that ϕ(1) = 0. The ϕ-entropic risk measure with divergence level c is defined asER c ϕ [Z] ∶= sup q∈Q c ϕ E P [Zq], where

  µ + ν E Pn ϕ ⋆ Zµ ν c .Extending the results of Lemmas 2 and 3 comes down to finding an auxiliary estimator ER c ϕ [Z] of ER c ϕ [Z] which satisfies (as in Lemma 3) ER c ϕ [Z] ≤ ER c ϕ [Z] ⋅ (1 + ǫ n ), for some "small" ǫ n , and 1 n n i=1

These are precisely the properties which make coherent risk measures excellent candidates in some machine learning applications (see e.g.[Williamson and Menon

, 2019] for an application to fairness)2 We use the convention in Brown[2007],[START_REF] Prashanth | Actor-critic algorithms for risk-sensitive MDPs[END_REF],[START_REF] Wang | Deviation inequalities for an estimator of the conditional value-at-risk[END_REF].


Jingjing Pan
email: jingjingpan@nuaa.edu.cn

Meng Sun

Yide Wang

Cédric Le Bastard

Vincent Baltazart

A time-delay estimation approach for coherent GPR signals by taking into account the noise pattern and radar pulse

Keywords: Time-delay estimation (TDE), ground penetrating radar (GPR), coherent signals

In this paper, we propose to perform time-delay estimation (TDE) of coherent GPR signals by taking into accout the radar pulse and noise pattern. The proposed method can process raw GPR data without whitening procedure and decorrelate coherent signals properly with a Hankel matrix which contains the signal eigenvector, the radar pulse and the noise characteristics. Simulations and a field experiment show the effectiveness of the proposed method.

Introduction

In civil engineering, ground penetrating radar (GPR) is a widely used non-destructive device in subsurface sensing in many aspects, such as building structure and quality assessment, buried targets localization and so on [START_REF] Daniels | Ground penetrating radar[END_REF][START_REF] Benedetto | Civil engineering applications of ground penetrating radar[END_REF]. In the survey of horizontally stratified media, for example, pavement, time-delay estimation (TDE) is important that provides structural information by using GPR [START_REF] Bastard | Thin-pavement thickness estimation using GPR with high-resolution and superresolution methods[END_REF][START_REF] Sun | Advanced signal processing methods for ground-penetrating radar: Applications to civil engineering[END_REF]. High resolution methods, including multiple signal classification (MUSIC) [START_REF] Schmidt | Multiple emitter location and signal parameter estimation[END_REF] and estimation of signal parameters via rational invariance technique (ESPRIT) [START_REF] Roy | ESPRIT-estimation of signal parameters via rotational invariance techniques[END_REF], are popular in parameter estimation, especially for thin layer pavements.

Nevertheless, most of the TDE algorithms assume ideal Dirac radar pulse, making the temporal whitening of the GPR data indispensable. The whitening procedure, dividing the raw data by the radar pulse, modifies implicitly the properities of the noise and might therefore affect the backscattered echoes through the signal also a family of sparse deconvolution methods in TDE, for example, orthogonal matching pursuit (OMP) method [START_REF] Davenport | Analysis of orthogonal matching pursuit using the restricted isometry property[END_REF], l 1 -norm deconvolution method [START_REF] Li | Enhanced GPR signal for layered media time-delay estimation in low-SNR scenario[END_REF][START_REF] Malioutov | A sparse signal reconstruction perspective for source localization with sensor arrays[END_REF], without restrictions on the radar pulse or the noise.

However, OMP shows poor performance in terms of resolution power while l 1 -norm deconvolution method has high computational burden and suffers performance degradation in low SNR scenarios, especially with weak signals [START_REF] Malioutov | A sparse signal reconstruction perspective for source localization with sensor arrays[END_REF].

The radar pulse leads to a nonlinear frequency behavior in the exponent of the measured GPR echoes.

Therefore, the conventional spatial smoothing preprocessing (SSP) and its variants [START_REF] Shan | On spatial smoothing for direction-of-arrival estimation of coherent signals[END_REF][START_REF] Pillai | Forward/backward spatial smoothing techniques for coherent signal identification[END_REF] can't be applied directly for the decorrelation, since they are based on the linear frequency behavior in the exponent of the received signals. Besides, there are several methods constructing new matrices to decorrelate coherent signals. In [START_REF] Han | An ESPRIT-like algorithm for coherent DOA estimation[END_REF], the authors build a Toeplitz matrix with the elements in the data covariance matrix, whose rank is independent of the coherency among signals. The structure of Hankel matrix is also exploited to decorrelate signals with enhanced performance [START_REF] Gao | Data-based matrix decomposition technique for high-resolution array processing of coherent signals[END_REF][START_REF] Ye | DOA estimation by exploiting the symmetric configuration of uniform linear array[END_REF]. The construction of the Hankel matrix in [START_REF] Gao | Data-based matrix decomposition technique for high-resolution array processing of coherent signals[END_REF] is based on the received data while that in [START_REF] Ye | DOA estimation by exploiting the symmetric configuration of uniform linear array[END_REF] is based on the data covariance matrix. In this correspondence, we would like to modify [START_REF] Bastard | Modified ESPRIT (M-ESPRIT) algorithm for time delay estimation in both any noise and any radar pulse context by a GPR radar[END_REF] for coherent scenarios by using the matrix reconstruction approach and considering both the noise pattern and radar pulse. The proposed method has the following merits: 1) it can directly deal with raw GPR data without whitening procedure; 2) the decorrelation is achieved through a constructed Hankel matrix which contains the signal eigenvector, the radar pulse and the noise characteristics; 3) it has enhanced performance especially for weak signals.

The rest of this paper is organized as follows. Section 2 gives the signal model. Section 3 describes the proposed method. Section 4 presents the simulation results along with a field experiment. Conclusions are drawn in Section 5.

Signal Model

The stratified non-dispersive media model in [START_REF] Bastard | Modified ESPRIT (M-ESPRIT) algorithm for time delay estimation in both any noise and any radar pulse context by a GPR radar[END_REF] is adopted in this paper. Assume the media is composed of K interfaces and the GPR observations are conducted with M equispaced frequencies. Therefore, the backscattered echoes are time-shifted and attenuated replicas of the transmitted signal. Within frequency bandwidth B, the backscattered echoes in vector form can be written as

r = ΛAs + n (1)
with the following notations:

• r = [r(f 1 ), . . . , r(f M )]
T is the M × 1 received GPR signal vector in frequency domain; f m = f 1 + (m -1)∆f , with f 1 the beginning of bandwidth and ∆f the frequency shift, m = 1, . . . , M ; superscript T denotes transpose operation;

• s = [s 1 , . . . , s K ] T is the K × 1 source vector composed of echoes' amplitudes;

• n = [n 1 , . . . , n M ]
T is the M × 1 noise vector with zero mean;

• Λ = diag{ẽ 1 , . . . , ẽM } is a M ×M diagonal matrix with diagonal elements corresponding to the Fourier transform of the radar pulse;

• A = [a(τ 1 ), . . . , a(τ K )] is the mode matrix whose columns are defined as a(τ k ) = e -j2πf1τk , . . . , e -j2πfM τk T , k = 1, . . . , K; τ k is the time of arrival of the kth echo.

Assuming the noise to be independent of the backscattered echoes, the data covariance matrix of r can be expressed as

R = E(rr H ) = ΛAR s A H Λ H + σ 2 Σ (2)
where E(.) denotes the ensemble average; R s = E(ss H ) and σ 2 Σ are the signal sources and noise covariance matrix, respectively; superscript H denotes transpose conjugate operation. In this paper, the signal model is under the following assumptions:

1. The backscattered echoes are coherent; the signal covariance matrix R s is rank one;

2. The noise is statistically independent, zero mean complex Gaussian random process, and can be spatially white or colored;

3. The radar pulse Λ and noise covariance matrix Σ are known beforehand;

4. The noise is independent of all the backscattered echoes.

Methodology

Generalized eigenvalue decomposition

The generalized eigenvalue decomposition (GEVD) of the matrix pair (R, Σ) is defined as in [START_REF] Cadzow | A high resolution direction-of-arrival algorithm for narrow-band coherent and incoherent sources[END_REF][START_REF] Saarnisaari | TLS-ESPRIT in a time delay estimation[END_REF] Re

m = λ m Σe m , m = 1, . . . , M (3)
with λ m the mth eigenvalue in descending order and e m the corresponding eigenvector with dimension M × 1.

65

In contrast to [START_REF] Bastard | Modified ESPRIT (M-ESPRIT) algorithm for time delay estimation in both any noise and any radar pulse context by a GPR radar[END_REF], the backscattered GPR echoes in this paper are coherent. In this case, the eigenvalues after the generalized eigenanalysis are distributed as

λ 1 > λ 2 = • • • = λ M = σ 2 .
Referring to the largest eigenvalue λ 1 , (3) can be expressed as

Re 1 = λ 1 Σe 1 . (4)
Substituting ( 2) into ( 4) and after some mathematical manipulations, we deduce 5) can be reformulated as follows:

AR s A H Λ H e 1 = (λ 1 -σ 2 )Λ -1 Σe 1 . ( 5
) Let t = R s A H Λ H e 1 , (
g = At = (λ 1 -σ 2 )Λ -1 Σe 1 ( 6
)
where t is a K × 1 vector whose elements are non-zero; g is a M × 1 vector.

Proposed method for TDE 70

In [START_REF] Wang | Spatial spectrum estimation theory and algorithm[END_REF][START_REF] Cadzow | General direction-of-arrival estimation: a signal subspace approach[END_REF], the authors only make use of the signal eigenvector e 1 in the decorrelation with enhanced performance. It implies that in coherent scenarios, the signal eigenvector corresponding to the largest eigenvalue contains all the information of signals and can be used for decorrelation. Unlike [START_REF] Wang | Spatial spectrum estimation theory and algorithm[END_REF][START_REF] Cadzow | General direction-of-arrival estimation: a signal subspace approach[END_REF], we propose to exploit not only the information of e 1 but also the radar pulse and noise characteristics to decorrelate the coherent backscattered echoes, which is achieved by transforming g into a Hankel matrix X as in [START_REF] Gao | Data-based matrix decomposition technique for high-resolution array processing of coherent signals[END_REF][START_REF] Ye | DOA estimation by exploiting the symmetric configuration of uniform linear array[END_REF], [START_REF] Le Cadre | Approximated stochastic realization and model reduction methods applied to array processing by means of state space models[END_REF]:

X =          g 1 g 2 . . . g L g 2 g 3 . . . g L+1 . . . . . . . . . g M -L+1 g M -L+2 . . . g M          (M -L+1)×L (7)
where g m is the mth element of vector g, m = 1, . . . , M and

K ≤ L ≤ M -K + 1.
Matrix X in (7) can be reformulated as

X = A 1 TA T 2 (8)
where

A 1 =          1 1 . . . 1 z 1 z 2 . . . z K . . . . . . . . . z M -L 1 z M -L 2 . . . z M -L K          (M -L+1)×K , (9)
A 2 =          1 1 . . . 1 z 1 z 2 . . . z K . . . . . . . . . z L-1 1 z L-1 2 . . . z L-1 K          L×K , (10)
and T = diag{e -j2πf1τ1 t 1 , e -j2πf1τ2 t 2 , . . . , e -j2πf1τK t K } with z k = e -j2π∆f τk and t k the kth element of t.

Matrices A 1 and A 2 have Vandermonde structure and they are therefore non-singular. We can also prove that T is of full rank, since t k and e -j2πf1τk are non-zero. The rank of matrix X is K, which is not affected by the coherency. In this case, the truncated singular value decomposition (SVD) of matrix X is

X = U s Φ s V H s (11)
where Φ s is a diagonal matrix whose elements are the K largest non-zero singular values of X; U s and V s are respectively the left and right singular vector matrices of X, corresponding to the K dominant singular values. Define the singular vector matrices associated with the remaining smaller singular values as U n and

V n , respectively. We can multiply (11) by V n under the concept of orthogonality:

XV n = U s Φ s V H s V n = 0. (12)
Substituting ( 8) into (12) yields:

XV n = A 1 TA T 2 V n = 0. ( 13
)
Since A 1 is a Vandermonde matrix and T is non-singular, the above formula implies:

A H 2 V * n = 0 ( 14
)
where * denotes conjugate operation.

According to [START_REF] Han | An ESPRIT-like algorithm for coherent DOA estimation[END_REF], the time-delays can be estimated by finding the zeros of ā(τ )V * n , with ā(τ ) =

[1, e -j2π∆f τ , . . . , e -j2π∆f (L-1)τ ] H . In theory, it is identical to evaluate the polynomial D(z) on the unit circle, like in Root-MUSIC [START_REF] Barabell | Improving the resolution performance of eigenstructure-based direction-finding algorithms[END_REF]. The expression of D(z) is

D(z) = L-1 l=-L+1 α l z -l (15)
where α l is the sum of entries of P along the lth diagonal and P = V * n V T n . The time-delays can be derived by the K roots that are inside and closest to the unit circle.

Matrix U n can also be applied in TDE but with similar performance, which is not included here. In addition, X can be extended into a forward-backward version as in [START_REF] Pillai | Forward/backward spatial smoothing techniques for coherent signal identification[END_REF]:

Y =    X J 1 X * J 2    (16)
where J 1 and J 2 are anti-identity matrices with dimensions (M -L+1)×(M -L+1) and L×L, respectively.

The other estimation steps with matrix Y are the same as those with X. In the following, the estimation with matrices X and Y are referred as the 'Proposed method-F' and 'Proposed method-FB', respectively.

To sum up, the proposed procedures are as follows:

1. Estimate the data covariance matrix R;

2. Perform GEVD on the matrix pair (R, Σ);

3. Calculate g according to (6);

4. Construct matrices X and Y and apply SVD on them;

5. Build polynomial D(z) and estimate the time-delays with the roots inside and closest to the unit circle.

Numerical and experimental results

In order to evaluate the performance of the proposed method, several simulations and an experiment are carried out in this section.

In the simulations, the stratified medium is assumed to have three layers, as shown in Figure 1 The relative-root-mean-square-error (RRMSE) is used to evaluate the statistical performance of the proposed method:

RRMSE = 1 Q Q q=1 ( ∆τ kq -∆τ k ) 2 ∆τ k ( 17
)
where ∆τ kq denotes the estimate of the time-delay within the kth layer for the qth run; ∆τ k is the true value; Q is the number of Monte Carlo trials.

The radar pulse is modeled as a Ricker pulse in this paper, which is a common pattern in GPR [START_REF] Bastard | Modified ESPRIT (M-ESPRIT) algorithm for time delay estimation in both any noise and any radar pulse context by a GPR radar[END_REF].

During the Monte Carlo process, the colored noise is generated as in [START_REF] Werner | DOA estimation and detection in colored noise using additional noise-only data[END_REF]:

σ 2 Σ = 10 -SNR 20 GG H GG H (18)
where the elements of matrix G with dimension M × M are generated with a sequence of independent and identically distributed zero mean gaussian random variables with unit standard deviation.

Figures 2 and3 show the TDE results for ∆τ 1 and ∆τ 2 with respect to SNR through 200 Monte Carlo trials, respectively. The data covariance matrix is estimated with 500 snapshots. The estimates of Root-MUSIC with MSSP and a second-order cone programming (SOCP) based l 1 -norm deconvolution method are recorded for comparison, called Root-MUSIC-MSSP and l 1 -norm, respectively. In order to apply MSSP, the echoes are whitened by the radar pulse. The size of elements in the sub-band of MSSP is 11, equal to L. In the comparison, Root-MUSIC-MSSP doesn't take into account the colored noise. Given the noise distribution and SNR, the optimal regularization parameter of the l 1 -norm method is set according to [START_REF] Malioutov | A sparse signal reconstruction perspective for source localization with sensor arrays[END_REF].

As shown in Figures 2 and3, the RRMSEs of all the methods are descreasing with the increasing of SNR. The statistical curves are closer to each other in the estimation of the first time-delay, than those of the second time-delay. It's specially true for the curves of l 1 -norm. The reason may lie in the presence of weak signal, since the amplitude of the third echo is only 0.026 while the other two are 0.267 and 0.223, respectively. The proposed method with forward only operation and Root-MUSIC-MSSP are less effective in TDE, compared with the proposed method with both forward and backward operation, no matter B∆τ is greater than 1 or not. The proposed method shows enhanced performance by considering the radar pulse and the noise, especially for weak signals.

In the second simulation, we evaluate the accuracy of the proposed method in terms of the number of snapshots. SNR is 15 dB. The other settings are the same with the first simulation. In Figures 4 and5, the RRMSEs are getting smaller when the number of snapshots gets larger. The proposed method with forward and backward operation outperforms the others for each number of snapshots. In Figure 4, the curves of the proposed method with forward operation, the l 1 -norm method and Root-MUSIC-MSSP are similar when the number of snapshots is small; when the number of snapshots increases, larger than 600 in this case, the proposed method with forward operation achieves better result than Root-MUSIC-MSSP and l 1 -norm. Similar to Figures 2 and3, l 1 -norm has smaller RRMSEs in the estimation of ∆τ 1 than that of ∆τ 2 , for each number of snapshots.

Apart from the simulations, the proposed method is tested with a field experiment on IFSTTAR fatigue carousel [START_REF] Simonin | Progress in monitoring the debonding within pavement structures during accelerated pavement testing on the fatigue carousel[END_REF]. The IFSTTAR's pavement fatigue carrousel is a circular outdoor test track which allows various loading capabilities and speeds (refer to Fig. 1 in [START_REF] Simonin | Progress in monitoring the debonding within pavement structures during accelerated pavement testing on the fatigue carousel[END_REF] for more details). There are three different types of artificial debondings: sand, geotextile and uncoated interface. In this experiment, only the measurements on the sand zone are used. The probed pavement is composed of two layers of asphalt, whose structure is shown in Figure 6. The observation radar system is composed of a vector network analyzer (VNA) and a quasi-monostatic step frequency radar with closely located transmitter (Tx) and receiver (Rx). The distance between Tx and Rx is fixed at 20 cm during the B-scan (obtained from 21 A-scans). Antennas are 70 cm above the pavement in order to collect the backscattered echoes in the far-field. The radar pulse is measured with a metal plane [START_REF] Bastard | Thin-pavement thickness estimation using GPR with high-resolution and superresolution methods[END_REF]. Since there are two layers, Rx receives two backscattered echoes from the interfaces of pavement. Figure 7 shows the A-scan at the 6th sample point without air wave and Figure 8 shows the B-scan along the 21 A-scans, within a large frequency band f ∈ [0.8, 10.8] GHz. In order to validate the high resolution power of our proposed method, the used frequency bandwidth for the tested algorithms is In order to evaluate the performance of the Proposed method-FB and Root-MUSIC-MSSP, several preprocessing techniques are needed: 1) temporal filtering: filter out the air wave; 2) data whitening: divide the raw GPR data by the radar pulse; 3) spatial smoothing: apply MSSP to decorrelate coherent backscattered echoes. Root-MUSIC-MSSP requires all the preprocessing techniques while the Proposed method-FB only needs temporal filtering.

The noise in the experiment is considered as Gaussian white noise. Both the Proposed method-FB and Root-MUSIC-MSSP apply root operation in TDE and the statistical estimation results over 21 A-scans are listed in Table 1. Parameter L is set as 14. As shown in Table 1, both methods allow estimating the time-delay within the first layer. Nevertheless, the proposed method with forward and backward operation provides a more accurate and robust result with smaller relative error and standard deviation.

Conclusion

This paper proposes a TDE method for coherent GPR signals by taking into account of the noise pattern and radar pulse. A Hankel matrix containing the signal eigenvector, the noise and the radar pulse is generated to decorrelate the coherent backscattered echoes. Then, the SVD technique together with the root of a polynomial are applied in the estimation of time-delays. The performance of the proposed method is validated by numerical simulations and a field experiment in coherent scenarios with colored or white noise and different time resolutions. The proposed method with forward and backward operation shows good performance in the simulations and the field experiment, compared with the proposed forward only operation, the Root-MUSIC-MSSP and l 1 -norm. The consideration of radar pulse and noise in the decorrelation step improves the estimation results with coherent GPR signals, especially for weak signals.

Future work includes the evaluation of the proposed method on measurements of real roads.

SNR(dB) RRMSE(%)

Proposed method-forward backward Proposed method-forward MUSIC-MSSP l 1 -norm

SNR(dB) RRMSE(%)

Proposed method-forward backward Proposed method-forward MUSIC-MSSP l 1 -norm

  . The dielectric constants of these layers are 1 = 3, 2 = 8 and 3 = 9, respectively. The thickness of Layers 1 and 2 are H 1 = 25 mm and H 2 = 50 mm, respectively. The frequency range of the step frequency GPR is B = 2 GHz, with f ∈ [1, 3] GHz and M = 21 frequency samples. The amplitudes of backscattered echoes are respectively S 1 =0.267, S 2 =0.223 and S 3 =0.026, with the corresponding time of arrivals [τ 1 , τ 2 , τ 3 ] = [6.67, 6.96, 7.90] ns.For a given bandwidth B, the time resolution of a technique is defined as the minimal time interval ∆τ between two distinguishable echoes[START_REF] Bastard | Thin-pavement thickness estimation using GPR with high-resolution and superresolution methods[END_REF]. Conventional FFT-based methods are restricted to distinguish non-overlapping echoes, and its time resolution is about B∆τ = 1. The time-delays within Layers 1 and 2 are ∆τ 1 = τ 2τ 1 = 0.29 ns, ∆τ 2 = τ 3τ 2 = 0.94 ns. In consequence, the corresponding products are B∆τ 1 = 0.58 and B∆τ 2 = 1.88, which means S 0 and S 1 are overlapped while S 1 and S 2 are not. L is set as 11.

f ∈ [ 3 . 4 , 4 . 1 ]

 3441 GHz with M = 29 samples. The product B∆τ is about 0.75, which indicates the overlapping echoes. According to Figures7 and 8, the time-delay between the first and second echoes within Layer 1 is about 1.07 ns.

Figure 1 :

 1 Figure 1: Stratified layers for a simulated setup.

Figure 2 :

 2 Figure 2: RRMSEs of ∆τ 1 versus SNR. B∆τ 1 = 0.58, number of snapshots = 500.

Figure 3 :

 3 Figure 3: RRMSEs of ∆τ 2 versus SNR. B∆τ 2 = 1.88, number of snapshots = 500.

Figure 4 :

 4 Figure 4: RRMSEs of ∆τ 1 versus the number of snapshots. B∆τ = 0.58, SNR = 15 dB.

Figure 5 :Figure 6 :

 56 Figure 5: RRMSEs of ∆τ 2 versus the number of snapshots. B∆τ = 1.88, SNR = 15 dB.

13

 13

Figure 7 :Figure 8 :

 78 Figure 7: GPR data, A-scan at the 6th sample point within frequency band (f ∈ [0.8, 10.8] GHz).

Table 1 :

 1 Statistical estimation results of the Proposed method-FB and Root-MUSIC-MSSP over 21 A-scans.

		Mean (ns) Std * (ns) Relative error (%)
	Proposed method-FB	1.04	0.031	3.02
	Root-MUSIC-MSSP	1.13	0.055	5.80

* Standard deviation.

to noise ratio (SNR) [START_REF] Bastard | Modified ESPRIT (M-ESPRIT) algorithm for time delay estimation in both any noise and any radar pulse context by a GPR radar[END_REF].

The authors in [START_REF] Bastard | Modified ESPRIT (M-ESPRIT) algorithm for time delay estimation in both any noise and any radar pulse context by a GPR radar[END_REF][START_REF] Swindlehurst | Time delay and spatial signature estimation using known asynchronous signals[END_REF] propose to take the radar pulse into account in the estimation. The work in [START_REF] Swindlehurst | Time delay and spatial signature estimation using known asynchronous signals[END_REF] supposes to deal with Gaussian white noise. While [START_REF] Bastard | Modified ESPRIT (M-ESPRIT) algorithm for time delay estimation in both any noise and any radar pulse context by a GPR radar[END_REF] considers any noise pattern but assumes null correlation among the backscattered echoes, which is not valid in practical GPR applications. There are

Conflict of interest statement

We declare that we have no financial and personal relationships with other people or organizations that can inappropriately influence our work, there is no professional or other personal interest of any nature or kind in any product, service and/or company that could be construed as influencing the position presented in, or the review of, the manuscript entitled.