Maxime Haddouche
email: maxime.haddouche@inria.fr

Benjamin Guedj
email: benjamin.guedj@inria.fr

PAC-Bayes Generalisation Bounds for Heavy-Tailed Losses through Supermartingales

While PAC-Bayes is now an established learning framework for light-tailed losses (e.g., subgaussian or subexponential), its extension to the case of heavy-tailed losses remains largely uncharted and has attracted a growing interest in recent years. We contribute PAC-Bayes generalisation bounds for heavy-tailed losses under the sole assumption of bounded variance of the loss function. Under that assumption, we extend previous results from Kuzborskij and Szepesvári (2019). Our key technical contribution is exploiting an extention of Markov's inequality for supermartingales. Our proof technique unifies and extends different PAC-Bayesian frameworks by providing bounds for unbounded martingales as well as bounds for batch and online learning with heavy-tailed losses.

• Data-free priors. With an alternative set of techniques, Catoni (2007) obtained bounds with localised (i.e., data-dependent) priors. More recently, Lever et al. (

Introduction

PAC-Bayes learning is a branch of statistical learning theory aiming to produce (tight) generalisation guarantees for learning algorithms, and as a byproduct leads to designing new efficient learning procedures by minimising such guarantees. Generalisation bounds are helpful for understanding how a learning algorithm may perform on future similar batches of data. Since its emergence in the late 1990s, PAC-Bayes theory (see the seminal works of [START_REF] Shawe-Taylor | A PAC analysis of a Bayes estimator[END_REF][START_REF] Mcallester | Some PAC-Bayesian theorems[END_REF][START_REF] Mcallester | PAC-Bayesian model averaging[END_REF]2003;[START_REF] Catoni | A PAC-Bayesian approach to adaptive classification[END_REF][START_REF] Catoni | PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF] has revealed powerful enough to explain the generalisation abilities of learning algorithms which output distributions over the predictors space (a particular case being when the output is a Dirac mass on a single predictor) from which our predictors of interest are designed. We refer to the recent surveys from [START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF]; [START_REF] Alquier | User-friendly introduction to PAC-Bayes bounds[END_REF] for an overview on PAC-Bayes.

At first, PAC-Bayes theory was mainly focused on classification tasks (see [START_REF] Seeger | PAC-Bayesian Generalization Error Bounds for Gaussian Process Classification[END_REF][START_REF] Langford | Tutorial on practical prediction theory for classification[END_REF][START_REF] Catoni | PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF] but has quickly been generalised to any bounded loss function in regression (see e.g., [START_REF] Maurer | A note on the PAC Bayesian theorem[END_REF][START_REF] Germain | PAC-Bayesian Learning of Linear Classifiers[END_REF]2016). PAC-Bayes learning covers a broad scope of domains and tools, from information theory [START_REF] Kakade | On the complexity of linear prediction: Risk bounds, margin bounds, and regularization[END_REF]Wu and Seldin, 2022) to statistical learning [START_REF] Catoni | A PAC-Bayesian approach to adaptive classification[END_REF][START_REF] Catoni | PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF], convex optimisation [START_REF] Thiemann | A strongly quasiconvex PAC-Bayesian bound[END_REF], Bernstein-type concentration inequalities (Tolstikhin and Seldin, 2013;Mhammedi et al., 2019), margins (Biggs and Guedj, 2022a;Biggs et al., 2022) and martingales [START_REF] Seldin | PAC-Bayesian Analysis of Martingales and Multiarmed Bandits[END_REF]2012a;[START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF], to name but a few.

From a practical perspective, the above led to generalisations guarantees for PAC-Bayes-inspired neural networks (NN): a promising line of work initiated by [START_REF] Dziugaite | Computing Nonvacuous Generalization Bounds for Deep (stochastic) Neural Networks with many more parameters than training data[END_REF] and pursued further by [START_REF] Letarte | Dichotomize and generalize: PAC-Bayesian binary activated deep neural networks[END_REF]; [START_REF] Rivasplata | PAC-Bayes with Backprop[END_REF]; [START_REF] Pérez-Ortiz | Tighter Risk Certificates for Neural Networks[END_REF]; [START_REF] Biggs | Differentiable PAC-Bayes objectives with partially aggregated neural networks[END_REF]; Perez-Ortiz et al. (2021a;[START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF]; Biggs and Guedj (2022b), among others, established NN architectures enjoying tight generalisation guarantees, turning PAC-Bayes into a powerful tool to handle complex neural structures (e.g., [START_REF] Chérief-Abdellatif | On PAC-Bayesian reconstruction guarantees for VAEs[END_REF].

These encouraging breakthroughs gave rise to several initiatives to extend PAC-Bayes beyond the bounded losses assumption which is limiting in practice. Indeed, the goal is to make PAC-Bayes able to provide efficiency guarantees to any learning algorithm attached to a loss function. For instance, consider a NN 1 trained to solve regression problems without constraints on the training domain. Several works already proposed routes to overcome the boundedness constraint: Catoni (2004, Chapter 5) already proposed PAC-Bayes bounds for the classification tasks and regressions ones with quadratic loss under a subexponential assumption. This technique has later been exploited in [START_REF] Alquier | Sparse single-index model[END_REF] for the single-index model, and by [START_REF] Guedj | PAC-Bayesian estimation and prediction in sparse additive models[END_REF] for nonparametric sparse additive regression, both under the assumption that the noise is subexponential. However all these works are dealing with light-tailed losses. [START_REF] Alquier | Simpler PAC-Bayesian bounds for hostile data[END_REF]; Holland (2019); [START_REF] Kuzborskij | Efron-Stein PAC-Bayesian Inequalities[END_REF]; [START_REF] Haddouche | PAC-Bayes unleashed: generalisation bounds with unbounded losses[END_REF] proposed extensions beyond light-tailed losses. Our work stands in the continuation of this spirit while developing and exploiting a novel technical toolbox. To better highlight the novelty of our approach, we first present the two classical building blocks of PAC-Bayes.

1.1 Understanding PAC-Bayes: a celebrated route of proof

Two essential building blocks for a preliminary bound

In PAC-Bayes, we typically assume access to a non-negative loss function (h, z) taking as argument a predictor h ∈ H and data z ∈ Z (think of z as a pair input-output (x, y) for supervised learning problems, or as a single datum x in unsupervised learning). We also assume access to a m-sized sample S = (z 1 , ..., z m ) ∈ Z m of data on which we will learn a meaningful posterior distribution Q on H, from a prior P (or reference measure -see e.g., [START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF] for a discussion on the terminology of probability distributions in PAC-Bayes).

To do so, PAC-Bayesian proofs are built upon two cornerstones. The first one is the change of measure inequality [START_REF] Csiszár | I-divergence geometry of probability distributions and minimization problems[END_REF][START_REF] Donsker | Asymptotic evaluation of certain Markov process expectations for large time, I[END_REF][START_REF] Dupuis | A Weak Convergence Approach to the Theory of Large Deviations[END_REF] -see also [START_REF] Banerjee | On Bayesian Bounds[END_REF][START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF] for a proof). Lemma 1.1 (Change of measure inequality). For any measurable function ψ : H → R and any distributions Q, P on H:

E h∼Q [ψ(h)] ≤ KL(Q, P ) + log (E h∼P [exp(ψ(h))]) ,
with KL denoting the Kullback-Leibler divergence.

The change of measure inequality is then applied to a certain function f m : Z m × H → R of the data and a candidate predictor: for all posteriors Q,

E h∼Q [f m (S, h)] ≤ KL(Q, P ) + log (E h∼P [exp(f m (S, h))]) .
(1)

To deal with the random variable X(S)

:= E h∼P [exp(f m (S, h))], our second building block is Markov's inequality P(X > a) ≤ E[X]
a which we apply for a fixed δ ∈]0, 1[ on X(S) with a = E S [X(S)]/δ. Taking the complementary event gives that for any m, with probability at least 1 -δ over the sample S, X(S) ≤ E S [X(S)]/δ, thus:

E h∼Q [f m (S, h)] ≤ KL(Q, P ) + log(1/δ) + log (E h∼P E S [exp(f m (S, h))]) .
(2)

From preliminary to complete bounds

From the preliminary result of Eq. ( 2), there exists several ways to obtain PAC-Bayesian generalisation bounds, all being tied to specific choices of f and the assumptions on the dataset S. However they all rely on the control of an exponential moment implied by Markov's inequality: this is a strong constraint which has been at the heart of the classical assumption appearing in PAC-Bayes learning. For instance, the celebrated result of [START_REF] Mcallester | PAC-Bayesian model averaging[END_REF], tightened by [START_REF] Maurer | A note on the PAC Bayesian theorem[END_REF], exploits in particular, a data-free prior, an iid assumption on S and a light-tailed loss function. Most of the existing results stand with those assumptions (see e.g., [START_REF] Catoni | PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF][START_REF] Germain | PAC-Bayesian Learning of Linear Classifiers[END_REF][START_REF] Guedj | PAC-Bayesian estimation and prediction in sparse additive models[END_REF]Tolstikhin and Seldin, 2013;[START_REF] Guedj | PAC-Bayesian high dimensional bipartite ranking[END_REF]Mhammedi et al., 2019;Wu and Seldin, 2022). Indeed, in many of these works, a boundedness assumption on the loss is used but in many cases, it can be relaxed to subgaussiannity without loss of generality. [START_REF] Catoni | Statistical learning theory and stochastic optimization: Ecole d'Eté de Probabilités de Saint-Flour[END_REF] extended PAC-Bayes learning to the subexponential case. Many works tried to mitigate at least one of the following three assumptions.

Proof. We apply the optional stopping theorem (Durrett, 2019, Thm 4.8.4) with Markov's inequality defining the stopping time i = inf{t > 1 : Z t > δ -1 so that

P ∃t ≥ 1 : Z t > δ -1 = P Z i > δ -1 ≤ E [Z i ] δ ≤ E [Z 0 ] δ ≤ δ.
A major interest of Ville's result is that it holds for a countable sequence of random variables simultaneously. This point is new in PAC-Bayes as it will allow us to obtain bounds holding for a countable (not necessarily finite) dataset S = (z i ) i≥1 .

On which supermartingale do we apply Ville's bound ? To fully exploit Lemma 1.2, we now take a countable dataset S = (z i ) i≥1 ∈ Z m . Recall that, because we use the change of measure inequality, we have to deal with the following exponential random variable appearing in Eq. ( 1) for any m ≥ 1:

Z m := E h∼P [exp(f m (S, h))].
Our goal is to choose a sequence of functions f m such that (Z m ) m is a supermartingale. A way to do so comes from [START_REF] Bercu | Exponential inequalities for self-normalized martingales with applications[END_REF].

Lemma 1.3. Let (M m ) be a locally square-integrable martingale with respect to the filtration (F m ). For all η ∈ R and m ≥ 0, one has:

E exp η∆M m - η 2 2 (∆[M ] m + ∆ M m ) | F m-1 ≤ 1,
where

∆M m = M m -M m-1 , ∆[M ] m = ∆M 2 m and ∆ M m = E ∆M 2 m | F m-1 . We define V m (η) = exp ηM m -η 2 2 ([M ] m + M m ) . Then, for all η ∈ R, (V m (η)) is a positive super- martingale with E [V m (η)] ≤ 1 where [M ] m (h) := m i=1 ∆[M ] m , M m (h) := m i=1 ∆ M m .
In the sequel, this lemma will be helpful to design a supermartingale (i.e., to choose a relevant f m for any m) without further assumption.

Contributions and outline

By avoiding Markov, a key message of [START_REF] Kuzborskij | Efron-Stein PAC-Bayesian Inequalities[END_REF] is that, for learning problems with independent data, PAC-Bayes learning only requires the control of order 2 moment on losses to be used with convergence guarantees. This is strictly less restrictive than the classical subgaussian/subgamma assumptions appearing in the major part of the literature.

We successfully prove this fact remains even for non-independent data: we only need to control order 2 (conditional) moments to perform PAC-Bayes learning. Furthermore, our proof technique is general enough to encompass two different PAC-Bayesian framework: PAC-Bayes for martingales [START_REF] Seldin | PAC-Bayesian Analysis of Martingales and Multiarmed Bandits[END_REF]2012a;[START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF] and Online PAC-Bayes learning (Haddouche and Guedj, 2022). Thus, our main contributions are twofold.

• We provide a novel PAC-Bayesian bound holding for data-free priors and unbounded martingales.

From this, we recover in PAC-Bayes bounds for unbounded losses and iid data as a significant particular case.

• We extend the Online PAC-Bayes framework of Haddouche and Guedj (2022) to the case of unbounded losses.

More precisely, Sec. 2.1 contains our novel PAC-Bayes bound for unbounded martingales and Sec. 2.3 contains an immediate corollary for learning theory with iid data. Our second contribution lies in Sec. 3 and extend Online PAC-Bayes theory to the case of unbounded losses. We eventually apply our main result for martingales in Sec. 4 to the setting of multi-armed bandit. Doing so, we provably extend a result of Seldin et al. (2012a) to the case of unbounded rewards.

Appendix A gathers more details on PAC-Bayes, we draw in Appendix B a detailed comparison between our new results and a few classical ones. We show that adapting our bounds to the assumptions made in those papers allows to recover similar or improved bounds. We defer to Appendix C the proofs of Secs. 2.3 and 4.

2 A PAC-Bayesian bound for unbounded martingales

Main result

A line of work led by [START_REF] Seldin | PAC-Bayesian Analysis of Martingales and Multiarmed Bandits[END_REF]2012a;[START_REF] Guedj | A Primer on PAC-Bayesian Learning[END_REF] provided PAC-Bayes bounds for almost surely bounded martingales. We provably extend the remits of their result to the case of unbounded martingales.

Framework Our framework is close to the one of Seldin et al. (2012a): we assume having access to a countable dataset S = (z i ) i≥1 ∈ with no restriction on the distribution of S (in particular the z i can depend on each others). We denote for any m, S m := (z i ) i=1..m the restriction of S to its m first points. (F i ) i≥0 is a filtration adapted to S. We denote for any i

∈ N E i-1 [.] := E[. | F i-1 ].
We also precise the space H to be an index (or a hypothesis) space, possibly uncountably infinite.

Let {X 1 (S 1 , h), X 2 (S 2 , h), • • • : h ∈ H} be martingale difference sequences, meaning that for any m ≥ 1, h ∈ H, E m-1 [X m (S m , h)] = 0. For any h ∈ H, let M m (h) = m i=1 X i (S i , h
) be martingales corresponding to the martingale difference sequences and we define, as in [START_REF] Bercu | Exponential inequalities for self-normalized martingales with applications[END_REF], the following

[M ] m (h) := m i=1 X i (S i , h) 2 , M m (h) = m i=1 E i-1 X i (S i , h) 2 .
For a distribution Q over H define weighted averages of the martingales with respect to

Q as M m (Q) = E h∼Q [M m (h)] (similar definitions hold for [M ] m (Q), M m (Q)).
Main result. We now present the main result of this section where we succesfully avoid the boundedness assumption on martingales. This relaxation comes at the cost of additional variance terms [M ] m , M m . Theorem 2.1. For any data-free prior P ∈ M + 1 (H), any λ > 0, any collection of martingales (M m (h)) m≥1 indexed by h ∈ H, the following holds with probability 1 -δ over the sample S = (z i ) i∈N , for all m ∈ N/{0},

Q ∈ M + 1 (H): |M m (Q)| ≤ KL(Q, P ) + log(2/δ) λ + λ 2 ([M ] m (Q) + M m (Q)) .
Proof lies in Sec. 2.2.

Analysis of the bound. This theorem involves several terms. The change of measure inequality introduces the KL divergence term, the approximation term log(2/δ) comes from Ville's inequality (instead of Markov in classical PAC-Bayes). Finally, the terms [M ] m (Q), M m (Q) come from our choice of supermartingale as suggested by [START_REF] Bercu | Exponential inequalities for self-normalized martingales with applications[END_REF]. The term [M ] m (Q) can be interpreted as an empirical variance term while M m (Q) is its theoretical counterpart. Note that M m (Q) also appears in Seldin et al. (2012a, Theorem 1).

We recall that this general result stands with no assumption on the martingale difference sequence (X i ) i≥1 and holds uniformly on all m ≥ 1. Those two points are, to the best of our knowledge, new within the PAC-Bayes literature. We discuss in Sec. 2.3 and Appendix B more concrete instantiations.

Comparison with literature. The closest result from Thm. 2.1 is the PAC-Bayes Bernstein inequality of Seldin et al. (2012a). Our bound is a natural extension of theirs as their result only involves the variance term (not the empirical one), but requires two additional assumptions:

1. Bounded variations of the martingale difference sequence: Seldin et al. (2012a) need those assumptions to ensure the Bernstein assumption which states that for any h,

∀m, ∃C m ∈ R 2 such that a.s. for all h |X m (S m , h)| ≤ C m .

Restriction on the range of the

λ: ∀m, λ m ≤ 1/C m .
E[exp(λM m (h) -λ 2 2 M m (h))] ≤ 1.
Our proof technique do not require the Bernstein assumption (and so none of the two conditions described above, which allow us to deal with unbounded martingales) as we exploit the supermartingale structure to obtain our results. More precisely, the price to pay to avoid the Bernstein assumption is to consider the empirical variance term [M ] m (h) and to prove that

exp λM m -λ 2 2 ([M ] m + M m ) m≥1
is a supermartingale using Lemma 1.2 and Lemma 1.3 (see Sec. 2.2 for the complete proof). A broader discussion is detailed in Appendix B.

Proof of Thm. 2.1

Proof. We fix η ∈ R and we consider the function f m to be for all (S, h):

f m (S, h) := ηM m (h) - η 2 2 ([M ] m (h) + M m (h)) = m i=1 η∆M i (h) - η 2 2 (∆[M ] i (h) + ∆ M i (h)),
where

∆M i (h) = X i (S i , h), ∆[M ] i (h) = X i (S i , h) 2 , ∆ M i (h) = E i-1 X i (S i , h) 2 .
For the sake of clarity, we dropped the dependency in S of M m . Note that, given the definition of M m , M m (h) is F m measurable for any fixed h.

Let P a fixed data-free prior, we first apply the change of measure inequality to obtain ∀m ∈ N, ∀Q ∈ M + 1 (H):

E h∼Q [f m (S, h)] ≤ KL(Q, P ) + log   Eh∼P [exp(f m (S, h))] :=Zm    ,
with the convention f 0 = 0. We now have to show that (Z m ) m is a supermartingale with Z 0 = 1. To do so remark that for any m, because P is data free one has the following result.

Lemma 2.2. For any data-free prior P , any σ-algebra F belonging to the filtration (F i ) i≥0 , any nonnegative function f taking as argument the sample S and a predictor h, one has almost surely:

E [E h∼P [f (S, h)] | F] = E h∼P [E[f (S, h) | F]] .
Proof. Let A be a F-measurable event. We want to show that

E [E h∼P [f (S, h)]1 A ] = E [E h∼P [E[f (S, h) | F]] 1 A ] ,
where the first expectation in each term is taken over S. Note that it is possible to take this expectation thanks to the Kolomogorov's extension theorem (see e.g. Tao, 2011, Thm 2.4.4) which ensure the existence of a probability space for the discrete-time stochastic process S = (z i ) i≥1 .

Thus, this is enough to conclude that

E [E h∼P [f (S, h)] | F] = E h∼P [E[f (S, h) | F]] ,
by definition of the conditional expectation. To do so, notice that because f (S, h)1 A is a nonnegative function, and that P is data-free, we can apply the classical Fubini-Tonelli theorem.

E [E h∼P [f (S, h)]1 A ] = E h∼P [E [f (S, h)1 A ]] .
One now conditions by F and use the fact that 1 A is F-measurable:

= E h∼P [E [E [f (S, h) | F] 1 A ]] .
We finally re-apply Fubini-Tonelli to re-intervert the expectations:

= E [E h∼P [E [f (S, h) | F] 1 A ]] .
This concludes the proof of Lemma 2.2.

We then use Lemma 2.2 with f = exp(f m ) and F = F m-1 to obtain:

E m-1 [Z m ] = E h∼P [E m-1 [(exp(f m (S, h))]] = E h∼P exp(f m-1 (S, h))E m-1 exp(η∆M m (h) - η 2 2 (∆[M ] m (h) + ∆ M m (h)) , with f m-1 (S, h) = m-1 i=1 η(∆M i (h)) -η 2 2 (∆[M ] i (h) + ∆ M i (h)). Using Lemma 1.3 ensures that for any h, E m-1 [exp(η∆M m (h) - η 2 2 (∆[M ] m (h) + ∆ M m (h))] ≤ 1, thus we have E m-1 [Z m ] ≤ E h∼P [exp(f m-1 (S, h))] = Z m-1 .
Thus (Z m ) m is a nonnegative supermartingale with Z 0 = 1. We can use Ville's inequality (Lemma 1.2) which states that

P S ∃m ≥ 1 : Z m > δ -1 ≤ δ.
Thus, with probability 1 -δ over S, for all m ∈ N, Z m ≤ 1/δ. We then have the following intermediary result. For all P a data-free prior, η ∈ R, with probability 1 -δ over S, for all m > 0,

Q ∈ M + 1 (H) ηM m (Q) ≤ KL(Q, P ) + log(1/δ) + η 2 2 ([M ] m (Q) + M m (Q))], (3)
recalling that M m (Q) = E h∼Q [M m (h)],
and that similar definitons hold for [M ] m (Q), M m (Q). Thus, applying the bound with η = ±λ (λ > 0) and taking an union bound gives, with probability 1 -δ over S,

for any m ∈ N, Q ∈ M + 1 (H) λ |M m (Q)| ≤ KL(Q, P ) + log(2/δ) + λ 2 2 ([M ] m (Q) + M m (Q))].
Dividing by λ concludes the proof.

A corollary: Batch learning with iid data and unbounded losses

In this section, we instantiate Thm. 2.1 onto a learning theory framework with iid data. We show that our bound encompasses several results of literature as particular cases.

Framework We consider a learning problem specified by a tuple (H, Z, ) consisting of a set H of predictors, the data space Z, and a loss function : H × Z → R + . We consider a countable dataset S = (z i ) i≥1 ∈ Z N and assume that sequence is iid following the distribution µ. We also denote by M + 1 (H) is the set of probabilities on H.

Definitions The generalisation error R of a predictor

h ∈ H is ∀h, R(h) = E z∼µ [ (h, z)], the empir- ical error of h is ∀h, R m (h) = 1 m m i=1 (h, z i )] and finally the quadratic generalisation error V of h is ∀h, Quad(h) = E z∼µ [ (h, z) 2 ].
We also denote by generalisation gap for any h the quantity |R(h) -R m (h)|.

Main result. We now state the main result of this section. This bound is a corollary of Thm. 2.1 and fills the gap with learning theory.

Theorem 2.3. For any data-free prior P ∈ M + 1 (H), any λ > 0 the following holds with probability 1 -δ over the sample

S = (z i ) i∈N , for all m ∈ N/{0}, Q ∈ M + 1 (H) E h∼Q [R(h)] ≤ E h∼Q R m (h) + λ 2m m i=1 (h, z i ) 2 + KL(Q, P ) + log(2/δ) λm + λ 2 E h∼Q [Quad(h)].
Proof is furnished in Appendix C.

About the choice of λ. A novelty in this theorem is that the bound holds simultaneously on all m > 0 -this is due to the use of Ville's inequality. This sheds a new light on the choice of λ. Indeed, taking a localised λ depending on a given sample size (e.g. λ m = 1/ √ m) ensures convergence guarantees for the expected generalisation gap. Doing so, our bound matches the usual PAC-Bayes literature (i.e. a bound holding with high probability for a single m). However the novelty brought by Thm. 2.3 is that our bound holds for unbounded losses for all times simultaneously. This suggests that taking a sample size-dependent λ may not be the best answer. We detail an instance of this fact below when one thinks of λ as a parameter of an optimisation objective. Indeed, our bound suggests a new optimisation objective for unbounded losses which is for any m > 0:

argmin Q E h∼Q 1 m m i=1 (h, z i ) + λ 2 (h, z i ) 2 + KL(Q, P ) λm . ( 4
)
Eq. ( 4) differs from the classical objective of Catoni (2007, Thm 1.2.6) on the additional quadratic term λ 2 (h, z i ) 2 . Note that this objective implies a bound on the theoretical order 2 moment to be meaningful as we do not include it in our objective. Note that this constraint is less restrictive than Catoni's objective which requires a bounded loss. This objective stresses the role of the parameter λ as being involved in a new explicit tradeoff between the KL term and the efficiency on training data.

Also, this optimisation objective is valid for any sample size m, this means that our λ should not depend on certain dataset size but should be fixed in order to ensure a learning algorithm with generalisation guarantees at all time. This draws a parallel with Stochastic Gradient Descent with fixed learning step.

About the underlying assumptions in this bound. Our result is empirical (all terms can be computer or approximated) at the exception of the term E h∼Q [Quad(h)]. This invites to choose carefully the class of posteriors, in order to bound this second-order moment with minimal assumptions. For instance, if we consider the particular case of the quadratic loss (h, z) = (h-z) 2 , then we only need to assume that our data have a finite variance if we restrict our posteriors to have both bounded means and variance. This assumption is striclty less restrictive than the classical subgaussian/subgamma assumption classically appearing in the literature.

Comparison with literature. Back to the bounded case, we note that instantiating the boundedness assumption in Thm. 2.3 make us recover the result of Alquier et al. (2016, Theorem 4.1) for the subgaussian case. We also remark that instantiating the HYPE condition conditioning Haddouche et al. (2021, Theorem 3) allow us to improve their result as we transformed the control of an exponential moment into one on a second-order moment. More details are gathered in Appendix B. We also compare Thm. 2.3 to Kuzborskij and Szepesvári (2019, Theorem 3) which is a PAC-Bayes bound for unbounded losses obtained through a concentration inequality from De la Peña et al. (2009). They arrived to what they denote as semiempirical inequalities which also involve empirical and theoretical variance terms (and not an exponential moment).Their bound holds for independent data and a single posterior. First of all, note that Thm. 2.3 holds for any posterior, which is strictly more general. Note also that our bound is a straightforward corollary of Thm. 2.1 which holds for any martingale (thus for any data distribution in a learning theory framework) and so, exploits a different toolbox than [START_REF] Kuzborskij | Efron-Stein PAC-Bayesian Inequalities[END_REF] (control of a supermartingale vs. concentration bounds for independent data). We insist that a fundamental novelty in our work is to extend the conclusion of [START_REF] Kuzborskij | Efron-Stein PAC-Bayesian Inequalities[END_REF] to the case of non-independent data: it is possible to perform PAC-Bayes learning for unbounded losses at the expense of the control of second-order moments. Note also that their bound is slightly tighter than ours as their result is Thm. 2.3 being optimised in λ (which is something we cannot do as the resulting λ would be data-dependent).

Online PAC-Bayes learning with unbounded losses

Recently, an online learning framework has been designed in Haddouche and Guedj (2022). This allowed the design of Online PAC-Bayes (OPB) algorithms which involved the use of history-dependent priors evolving at each time step of the learning procedure. The main contribution of this section is an OPB bound valid for unbounded losses.

Framework We consider the same framework as in Sec. 2.3 except we do not make any assumption on the data distribution. Our goal is now to define a posterior sequence (Q i ) i≥1 from a prior sequence (P i ) i≥1 .

We also define a filtration (F i ) i≥1 adapted to (z i ) i≥1 . We reuse the following definitions extracted from Haddouche and Guedj (2022).

Definitions For all i, we denote by

E i [.] the conditional expectation E[. | F i ]. A stochastic kernel from ∪ ∞ m=1 Z m to H is defined as a mapping Q : ∪ ∞ m=1 Z m × Σ H → [0, 1] where (i) For any B ∈ Σ H , the function S → Q(S, B) is measurable, (ii) For any S, the function B → Q(S, B) is a probability measure over H.
We also say that a sequence of stochastic kernels (P i ) i≥1 is an online predictive sequence if (i) for all i ≥ 1, S ∈ ∪ ∞ m=1 Z m , P i (S, .) is F i-1 measurable and (ii) for all i ≥ 2, P i (S, .) P 1 (S, .).

Main result.

We now state the main theorem of this section, which extends the remits of the Online PAC-Bayes framework to the case of unbounded losses.

Theorem 3.1. For any distribution over the (countable) dataset S, any λ > 0 and any online predictive sequence (used as priors) (P i ) i≥1 , we have with probability at least 1-δ over the sample S ∼ µ, the following, holding for the data-dependent measures P i,S := P i (S, .) any posterior sequence (Q i ) i≥1 and any m ≥ 1:

m i=1 E hi∼Qi [E[ (h i , z i ) | F i-1 ]] ≤ m i=1 E hi∼Qi [ (h i , z i )] + λ 2 m i=1 E hi∼Qi Vi (h i , z i ) + V i (h i ) + m i=1 KL(Q i P i,S ) λ + log(1/δ) λ .
With for all i, Vi (

h i , z i ) = ( (h i , z i ) -E i-1 [ (h i , z i )]) 2 is the empirical variance at time i and V i (h i ) = E i-1 [ V (h i , z i )] is the true conditional variance.
Proof lies in Sec. 3.1.

Analysis of the bound. This bound is, to our knowledge, the first Online PAC-Bayes bound in literature holding for unbounded losses. It is semi-empirical as the variance and empirical variance terms have theoretical components. However, these terms can be controlled with assumptions on conditional second-order moments and not on exponential ones (as made in Haddouche and Guedj, 2022 where the bounded loss assumption was used to obtain conditional subgaussianity). To emphasise our point, we consider as in Sec. 2.3 the case of the quadratic loss (h, z) = (h -z) 2 . Here, we only need to assume that our data have a finite variance if we restrict our posteriors to have both bounded means and variance. Also the meaning of the online predictive sequence P i is that we must be able to design properly a sequence of priors before drawing our data, this can be for instance an online algorithm whihc generate a prior distribution from past data at each time step.

Finally, we note that if we assume being able to bound simultaneaously all condtional means and variance (which is strictly less restrictive than bounding the loss),then Thm. 3.1 suggests a new online learning objective which is an online counterpart to Eq. ( 4).

∀i ≥ 1 Qi+1 = argmin

Q∈M + 1 (H) E hi∼Q (h i , z i ) + λ 2 (h i , z i ) 2 + KL(Q P i,S ) λ (5)
Comparison with literature. Our most natural comparison point is Theorem 2.3 of Haddouche and Guedj (2022) (re-stated in Appendix A). We claim that Thm. 3.1 is a strict improvement of their result on various sides described below.

• If we assume our loss to be bounded, then we can upper bound our empirical/theoretical variance terms to recover exactly Haddouche and Guedj (2022, Theorem 2.3). Our bound can then be seen as a strict extension of theirs and shows that bounding order two moments is a sufficient condition to perform online PAC-Bayes: subgaussianity induced by boundedness is not necessary even when our data are non iid.

• Another crucial point lies on the range of our result which holds with high probability for any countable posterior sequence (Q i ) i≥1 , any time m and the priors (P i,S ) i≥1 . This is far much general than Haddouche and Guedj (2022, Theorem 2.3) which holds only for a single m and a single posterior sequence (Q i,S ) i=1..m . This happens because in Haddouche and Guedj (2022), the change of measure inequality has not been exploited: they used a preliminary theorem from [START_REF] Rivasplata | PAC-Bayes analysis beyond the usual bounds[END_REF] which holds for a single (data-dependent) prior/posterior couple. This preliminary theorem already involved Markov's inequality which forced the authors to assume conditionnal subgaussianity to deal with an exponential moment. On the contrary, we exploited the fact that our online predictive sequence was history-dependent to use the change of measure inequality at any time step and control an exponential supermartingale through Ville's inequality.

• In Haddouche and Guedj (2022, Eq. 1), an OPB algorithm is given by their upper bound. This works because their associated learning objective admits a close form (Gibbs posterior) which matches the fact their bound hold for a single posterior sequence. Because our bound holds uniformly on all posteriors, it is now legitimate to restrict their algorithms to any parametric class of distributions and perform any optimisation algorithm to obtain a surrogate of the best candidate.

Online PAC-Bayes as presented in Haddouche and Guedj (2022) relies on a conditional subgaussiannity assumption to control an exponential moment. They did not exploit a martingale-type structure to do so.

Our supermartingale approach has proven to be well suited to Online PAC-Bayes as we provided atheorem valid for unbounded losses holding simultaneously on all posteriors: two points which have not been reached in Haddouche and Guedj (2022).

Proof of Thm. 3.1

Proof. We fix m ≥ 1, S a countable dataset and (P i ) i≥1 an online predictive sequence. We aim to design a m-tuple of probabilities. Thus, our predictor set of interest is H m := H ⊗m and then, our predictor h is a tuple (h 1 , .., h m ) ∈ H.

Our goal is to apply the change of measure inequality on H m to a specific function f m inspired from Lemma 1.3. We define this function below, for any sample S and any predictor h m = (h 1 , ..., h m )

f m (S, h m ) := m i=1 λX i (h i , z i ) - λ 2 2 m i=1 ( Vi (h i , z i ) + V i (h i )), where X i (h i , z i ) = E i-1 [ (h i , z i )] -(h i , z i ).
Notice that for fixed h, the sequence (f m (S, h)) m≥1 is a supermartingale according to Lemma 1.3. Now for a given posterior tuple Q 1 , ...Q m we define Q = Q 1 ⊗ ... ⊗ Q m and also P m S = P 1,S ⊗ ... ⊗ P m,S . We can now properly apply the change of measure inequality for any m:

m i=1 E hi∼Qi [λX i (h i , z i ) - λ 2 2 ( Vi (h i , z i ) + V i (h i ))] = E h m ∼Q [f m (S, h m )] ≤ KL(Q, P m S ) + log E h m ∼P m S exp(f m (S, h m )) .
Noticing that KL(Q,

P m S ) = m i=1 KL(Q i , P i,S
), the only remaining term to deal with is the exponential rv. To do so we prove the following lemma:

Lemma 3.2. The sequence (M m := E h m ∼P m S exp(f m (S, h m )) m≥1 is a non-negative supermartingale.
Proof. We fix m ≥ 1 and we recall that for any i, P i,S is

F i-1 -measurable. We show that E m-1 [M m ] ≤ M m-1 . We first recover M m-1 from E m-1 [M m ]. E m-1 [M m ] = E m-1 E h m ∼P m S exp(f m (S, h m ) = E m-1 E h1,..,hm∼P 1,S ⊗...⊗P m,S exp(f m (S, h m ) = E m-1 E h1,..,hm∼P 1,S ⊗...⊗P m,S Π m i=1 exp λX i (h i , z i ) - λ 2 2 ( Vi (h i , z i ) + V i (h i )) = M m-1 E m-1 E hm∼P m,S exp λX m (h m , z m ) - λ 2 2 ( Vm (h m , z m ) + V m (h m )) .
The last line holding because P m-1

S = P 1,S ⊗ ... ⊗ P m-1,S is F m-1 measurable.
Now we exploit the fact that P m,S is F m-1 measurable to apply a conditional Fubini lemma stated in Haddouche and Guedj (2022, Lemma D.3). We have:

E m-1 E hm∼P m,S exp λX m (h m , z m ) - λ 2 2 ( Vm (h m , z m ) + V m (h m )) = E hm∼P m,S E m-1 exp λX m (h m , z m ) - λ 2 2 ( Vm (h m , z m ) + V m (h m )
) .

Now we can apply Lemma 1.3 for any h

m ∈ H with ∆M m = X m (h m , z m ), ∆[M ] m = V (h m , z m ) and ∆ M m = V m (h m ).
We then have for all h m ∈ H:

E m-1 exp λX m (h m , z m ) - λ 2 2 ( Vm (h m , z m ) + V m (h m )) ≤ 1. Thus E m-1 [M m ] ≤ M m-1
, this concludes the lemma's proof.

Now we can apply Ville's inequality which implies that with probability at least 1 -δ, for any m ≥ 1:

E h m ∼P m S exp(f m (S, h m )) ≤ 1 δ .
Thus we have with probability at least 1-δ, for any posterior sequence (Q i ) i≥1 , the data-dependent measures P 1,S , ..., P m,S and any m ≥ 1:

m i=1 E hi∼Qi λX i (h i , z i ) - λ 2 2 ( Vi (h i , z i ) + V i (h i )) ≤ m i=1 KL(Q i , P i,S ) + log 1 δ .
Re-organising the terms in this bound and dividing by λ concludes the proof.

Application to the multi-armed bandit problem

We exploit our main result in the context of the multi-armed bandit problem -we adopt the framework of Seldin et al. (2012a).

Framework. Let A be a set of actions of size |A| = K < +∞ and a ∈ A be an action. At each round i, the environment furnishes a reward function R i : A → R which associate a reward R i (a) to the arm a.

Assuming the R i s are iid, we denote for any a, the expected reward for action a to be R(a

) = E R1 [R 1 (a)].
At each round i, the player executes an action A i according to a policy π i . We then set the filtration (F i ) i≥1 to be

F i = σ ({π j , A j , R j | 1 ≤ j ≤ m}).
Assumptions. We suppose here that (R i ) i≥1 is an iid sequence and that at each time i, A i and R i are independent and that π i is F i-1 measurable. This means that the player is not aware of the rewards each round and performs its current move with regards to the past.

We also add two technical assumptions. First, the order two moment of the expected reward is uniformly bounded:

sup a∈A E R1 [R 1 (a) 2 ] ≤ C.
This assumption is strictly less restrictive than the boundedness assumption made in Seldin et al. (2012a). Similarly to this work, we also assume that there exists a sequence (ε i ) i≥1 such that inf a∈A π i (a) ≥ ε i . We say that (π i ) i≥1 is bounded from below by (ε i ) i≥1 .

Definitions. For i ≥ 1 and a ∈ {1, . . . , K}, define a set of random variables (R a i ) i≥1 (the importance weighted samples, [START_REF] Sutton | Reinforcement Learning: An introduction[END_REF])

R a i := 1 πi(a) R i , if A i = a, 0, otherwise.
We define for any time m: (a). Let a * be the "best" action (the action with the highest expected reward, if there are multiple "best" actions pick any of them). Define the expected and empirical per-round regrets as

Rm (a) = 1 m t i=1 R a i . Observe that for all i, E [R a i | F i-1 ] = R(a) and E[ Rm (a)] = R
∆(a) = R (a * ) -R(a), ∆m (a) = Rm (a * ) -Rm (a).
Observe that m ∆m (a) -∆(a) forms a martingale. Let

V m (a) = m i=1 E R a * i -R a i -[R (a * ) -R(a)] 2 | F i-1
be the cumulative variance of this martingale and

Vm (a) = m i=1 R a * i -R a i -[R (a * ) -R(a)]
2 its empirical counterpart. We denote for any distribution

Q over A, ∆(Q) = E a∼Q [∆(a)], V m (Q) = E a∼Q [V m (a)
], similar definitions hold for ∆m (Q), Vm (Q). We can now state the main result of this section -its proof is deferred to Appendix C.

Theorem 4.1. For any m ≥ 1, any history-dependent policy sequence (π i ) i≥1 bounded from below by (ε i ) i≥1 , we have with probability 1 -δ, for all posterior Q

∆(Q) -∆m (Q) ≤ 2 1 + 2K δ (log(K) + log(4/δ)) mε m .
To the best of our knowledge, this result is the first PAC-Bayesian guarantees for multi-armed bandits with unbounded rewards. The proposed bound is as tight as Theorem 2.3 of Seldin et al. (2012a), up to a factor (e -2) transformed into 1 + 2K δ (which is a huge dependency in K) within the square root. Note that our result comes at the price of the localisation: Theorem 2.3 of Seldin et al. (2012a) proposes a bound holding uniformly for all time m while our approach only holds for a single time m.

We believe there is room for improvement in Thm. 4.1. Indeed, the current approach is naive as it consists in bounding crudely with high probability the empirical variance. Such a naive trick impeach us to consider all times simultaneously. Indeed, in its current form, taking an union bound on Thm. 4.1 is costful as we have a dependency in 1/δ in our result (instead of log(1/δ) in Seldin et al., 2012a): this would destroy the convergence rate. The question of dealing more subtly with the empirical variance term is left as an open question.

Conclusion

We showed that it is possible to generalise the PAC-Bayes toolbox to unbounded martingales and heavytailed losses (resp. learning problem with unbounded losses for batch/online learning), the solely implicit assumption being the existence of second order moments on the martingale difference sequence (resp. on the loss function) which is reasonable as many PAC-Bayes bound lies on assumptions on exponential moments (e.g. the subgaussian assumption) to work. We also proved that our main theorem can be seen as a general basis allowing to recover several PAC-Bayesian bounds. This shows that the supermartingale framework is a fruitful approach to unify several branches of PAC-Bayes and could lead to new promising developement such as the work of [START_REF] Jang | Tighter PAC-Bayes Bounds Through Coin-Betting[END_REF].

A Some PAC-Bayesian background

We present below an immediate corollary of Seldin et al. (2012a, Thm 2.1) where we upper bounded the cumulative by an empirical quantity (the sum of squared upper bound of the martingale difference sequence).

Theorem A.1 (Seldin et al., 2012a, Theorem 2.1). Let {C 1 , C 2 , . . .} be an increasing sequence set in advance, such that |X i (S i , h)| ≤ C i for all S i , h with probability 1. Let {P 1 , P 2 , . . .} be a sequence of data-free prior distributions over H. Let (λ i ) i≥1 be a sequence of positive numbers such that

λ m ≤ 1 C m .
Then with probability 1 -δ over S = (z i ) i≥1 , for all m ≥ 1, any posterior Q over H,

|M m (Q)| ≤ KL (Q P m ) + 2 log(m + 1) + log 2 δ λ m + (e -2)λ m V m (Q), where V m (Q) is defined in Appendix B.1.
Furthermore, if we bound the variance term, we would have:

|M m (Q)| ≤ KL (Q P m ) + 2 log(m + 1) + log 2 δ λ m + (e -2)λ m m i=1 C 2 i .
Below, we use the definitions introduced in Sec. 2.3. We study here a particular case of [START_REF] Alquier | On the properties of variational approximations of gibbs posteriors[END_REF] for bounded losses which are especially subgaussian thanks to Hoeffding's lemma.

Theorem A.2 (Adapted from Alquier et al., 2016, Theorem 4.1). Let m > 0,S = (z 1 , ..., z m ) be an iid sample from the same law µ. For any data-free prior P , for any loss function bounded by K, any λ > 0, δ ∈]0; 1[, one has with probability 1 -δ for any posterior

Q ∈ M 1 (H) E h∼Q [R(h)] ≤ E h∼Q [R m (h)] + KL(Q P ) + log(1/δ) λ + λK 2 2m .
Theorem A.3 (Haddouche et al., 2021, Theorem 3). Let the loss be HYPE(K) compliant. For any P ∈ M + 1 (H) with no data dependency, for any α ∈ R and for any δ ∈ [0, 1], we have with probability at least 1 -δ over size-m samples S, for any Q

E h∼Q [R(h)] ≤ E h∼Q [R m (h)] + KL(Q||P ) + log 1 δ m α + 1 m α log E h∼P exp K(h) 2 2m 1-2α .
Theorem A.4 (Theorem 2.3 of Haddouche and Guedj, 2022). For any distribution µ over Z m , any λ > 0 and any online predictive sequence (used as priors) (P i ), for any sequence of stochastic kernels (Q i ) we have with probability 1 -δ over the sample S ∼ µ, the following, holding for the data-dependent measures Q i,S := Q i (S, .), P i,S := P i (S, .) :

m i=1 E hi∼Q i,S [E[ (h i , z i ) | F i-1 ]] ≤ m i=1 E hi∼Q i,S [ (h i , z i )] + KL(Q i,S P i,S ) λ + λmK 2 2 + log(1/δ) λ .

B Extensions of previous results

Here we gather several corollaries of our main result in order to show how our Thm. 2.1 extends the validity of some classical results in the literature. More precisely we show that our result extends (up to numerical factors) the PAC-Bayes Bernstein inequality of Seldin et al. (2012a). Then, going back to the bounded case, we generalise a result from [START_REF] Catoni | PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF] reformulated in [START_REF] Alquier | On the properties of variational approximations of gibbs posteriors[END_REF] and we also show how our work strictly improves on the bound of [START_REF] Haddouche | PAC-Bayes unleashed: generalisation bounds with unbounded losses[END_REF].

B.1 Extension of the PAC-Bayes Bernstein inequality

Here we rename two terms for consistency with Theorem 2.1 of Seldin et al. (2012a)

(h) = [M ] m (h) = m i=1 X i (S i , h) 2 and the cumulative variance as V m (h) = M m (h) = m i=1 E i-1 [X i (S i , h) 2 ].
We provide below a corollary containing two bounds: the first one being a straightforward corollary of Thm. 2.1, the second being valid for bounded martingales and formally close to Theorem 2.1 of Seldin et al. (2012a).

Corollary B.1. Let {P 1 , P 2 , . . .} be a sequence of data-free prior distributions over H. Let (λ i ) i≥1 be a sequence of positive numbers. Then the following holds with probability 1 -δ over S = (z i ) i≥1 : for any tuple

(m, λ k , k ) with m, k ≥ 1, any posterior Q over H, |M m (Q)| ≤ KL (Q, P k ) + 2 log(k + 1) + log(2/δ) λ k + λ k 2 Vm (Q) + V m (Q) , ( 6
)
with

Vm (Q) = E h∼Q [ Vm (h)], V m (Q) = E h∼Q [V m (h)]
. Furthermore, if we assume that for any i, there exists

C i > 0 such that |X i (S i , h)| ≤ C i for all S i
, h then we have the following corollary: with probability 1 -δ over S, for any tuple (m, λ m , P m ) m ≥ 1, any posterior Q,

|M m (Q)| ≤ KL (Q, P m ) + 2 log(m + 1) + log(2/δ) λ m + λ m m i=1 C 2 i . ( 7
)
The proof is deferred to Appendix C. Note that Eq. ( 6) holds uniformly on all tuples {(λ k , P k , m) | k ≥ 1, m ≥ 1} while Eq. ( 7), as well as Theorem 2.1 of Seldin et al. (2012a) holds uniformly on the tuples {(λ m , P m , m) | m ≥ 1} which is a strictly smaller collection. Hence our approach gives guarantees for a larger event with the same confidence level.

Furthermore, Theorem 2.1 of Seldin et al. (2012a) involves the cumulative variance V m (Q) (and not its empirical counterpart). Because this term is theoretical, we bound it in Thm. A.1 by m i=1 C 2 i which is supposedly empirical. In this context, Eq. ( 7), recovers nearly exactly the bound of Seldin et al. (2012a) with the transformation of a factor (e -2) into 1. Notice also that Eq. ( 7) stands with no assumption on the range of the λ i , which is not the case in Thm. A.1.

Finally, we stress two fundamental differences between our work and the one of Seldin et al. (2012a). First, we replace Markov's inequality by Ville's inequality; second, we exploited the exponential inequality of Lemma 1.3 instead of the Bernstein inequality. These allow for results for unbounded martingales for all m simultaneously.

B.2 Extensions of learning theory results

B.2.1 A general result for bounded losses

We use definitions from Sec. 2.3 and provide a corollary of our main result when the loss is bounded by a positive constant K > 0. We assume our data are iid.

Corollary B.2. For any data-free prior P ∈ M + 1 (H), any λ > 0 the following holds with probability 1 -δ over the sample S = (z i ) i∈N , for all m ∈ N/{0},

Q ∈ M + 1 (H) |E h∼Q [R(h)] -E h∼Q [R m (h)]| ≤ KL(Q, P ) + log(2/δ) λm + λK 2 .
We also have the local bound: for any m ≥ 1, with probability 1 -δ over S, for all The first bound is, to our knowledge, the first PAC-Bayesian bound for bounded losses holding uniformly (for a given parameter λ) on the choice of Q, m and thus extends the scope of Catoni's bound which holds for a single m with high probability. Indeed, if we want for instance Thm. A.2 to hold for any i ∈ {1..m}, we then have to take an union bound on m events which turns the term log(1/δ) into log(m/δ) (but with the benefit of holding for m parameters λ 1 , ..., λ m ). This point is common to the most classical PAC-Bayesian bounds (as those of [START_REF] Mcallester | Some PAC-Bayesian theorems[END_REF][START_REF] Mcallester | PAC-Bayesian model averaging[END_REF][START_REF] Maurer | A note on the PAC Bayesian theorem[END_REF][START_REF] Catoni | PAC-Bayesian Supervised Classification: The Thermodynamics of Statistical Learning[END_REF]Tolstikhin and Seldin, 2013) and impeach us to have a bound uniformly on all m ∈ N/{0} as log(m) goes to infinity asymptotically.

Q ∈ M + 1 (H) E h∼Q [R(h)] ≤ E h∼Q [R m (h)] + KL(Q, P ) + log(2/δ) λ + λK 2 m .

B.2.2 An extension of Haddouche et al. (2021)

We now focus on the work of

= (z i ) i∈N , for all Q ∈ M + 1 (H) E h∼Q [R(h)] ≤ E h∼Q 1 m m i=1 (h, z i ) + 1 2m 1-α (h, z i ) 2 + KL(Q, P ) + log(1/δ) m α + 1 2m 1-α E h∼Q [K 2 (h)].
Proof. The proof is a straightforward application of Thm. 2.3 by fixing m ≥ 1 choosing λ = m α-1 (thus we localise Thm. 2.3 to a single m), and bounding Quad(h) by K 2 (h).

The main improvement of our bound over Thm. A.3 is that we do not have to assume the convergence of an exponential moment to obtain a non-trivial bound. Indeed, we transformed the (implicit) assumption

E h∼P exp K(h) 2 2m 1-2α < +∞ onto E h∼Q [K(h) 2 ]
< +∞, which is significantly less restrictive. Furthermore, Thm. A.3 holds for a single choice of m while ours still holds uniformly over all integers m > 0.

Cor. B.3 also sheds new light on the HYPE condition. Indeed, in [START_REF] Haddouche | PAC-Bayes unleashed: generalisation bounds with unbounded losses[END_REF], K only intervenes in an exponential moment involving the prior P , while ours considers a second-order moment on K implying the posterior Q. The difference is major as E h∼Q [K(h) 2 ] can be controlled by a wise choice of posterior. Thus it can be incorporated in our optimisation route, acting now as an optimisation constraint instead of an environment constraint.

C Proofs

C.1 Proof of Thm. 2.3

Proof. Let P a fixed data-free prior, set (F i ) i≥0 such that for all i, z i is F i measurable. We also set for any fixed h ∈ H, M m (h) := m i=1 (h, z i ) -R(h). Note that because data are iid, for any fixed h, the sequence (M m (h)) m is indeed a martingale. We set for any m

≥ 1, h ∈ H [M ] m (h) = m i=1 ( (h, z i ) -R(h)) 2 and M m (h) = m i=1 E i-1 [( (h, z i ) -R(h)) 2 ] = m i=1 E z∼µ [( (h, z) -R(h)) 2 ].
The last equality holds because data is assumed iid. Thus, we can apply Thm. 2.1 to obtain with probability 1 -δ

|M m (Q)| ≤ KL(Q, P ) + log(2/δ) λ + λ 2 [M ] m (Q) 2 + M m (Q) 2 . Now, we notice that |M m (Q)| = m|E h∼Q [R(h) -R m (h)]| and that for any m, h, because is nonnegative [M ] m (h) + M m (h) = m i=1 ( (h, z i ) -R(h)) 2 + E z∼µ [( (h, z) -R(h)) 2 ] ≤ m i=1 (h, z i ) 2 + R(h) 2 + E z∼µ [ (h, z) 2 ] -R(h) 2 .
Thus integrating over h gives:

[M ] m (Q) + M m (Q) ≤ m i=1 E h∼Q [ (h, z i ) 2 ] + mE h∼Q [Quad(h)].
Then dividing by m and applying the last inequality gives

E h∼Q [R(h)] ≤ E h∼Q 1 m m i=1 (h, z i ) + λ 2 (h, z i ) 2 + KL(Q, P ) + log(2/δ) λm + λ 2 E h∼Q [Quad(h)].
This concludes the proof. Notice that for any Q, KL(Q, P ) ≤ log(K) by concavity of the log. We now fix an horizon M > 0, we then have in particular, with probability 1 -δ/2: for any posterior Q,

|M m (Q)| ≤ log(K) + 2 log(k + 1) + log(4/δ) λ k + λ m 2 Vm (Q) + V m (Q) .
We now have to deal with V k (Q), Vk (Q) for all k ≤ m. To do so, we propose the two following lemmas.

Lemma C.1. For all m ≥ 1, a ∈ A, V m (a) ≤ 2Cm εm . Then, we have for any m, Q, V m (Q) ≤ 2Cm εm .

Proof. We have

V t (a) = m i=1 E R a * i -R a i -∆(a) 2 | F i-1 = m i=1 E R a * i -R a i 2 | F i-1 -m∆(a) 2 ≤ m i=1 E R a * i -R a i 2 | F i-1 = m i=1 E E Ai∼πi E Ri 1 π i (a * ) 2 R i (a * ) 2 1(A i = a * ) + 1 π i (a) 2 R i (a) 2 1(A i = a) | F i-1 .

20

The last line holding because R i is independent of F i-1 , A i is independent of R i and π is F i-1 measurable. We now use that for all i, a,

E Ri [R i (a) 2 ] ≤ C = m i=1 E E Ai∼πi 1 π i (a * ) 2 C1(A i = a * ) + 1 π i (a) 2 C1(A i = a) | F i-1 = m i=1 C π i (a) π i (a) 2 + π i (a * ) π i (a * ) 2 = m i=1 C 1 π i (a) + 1 π i (a * ) ≤ 2Cm ε m .
Lemma C.2. Let m ≥ 1, with probability 1 -δ/2, for any posterior Q, we have This concludes the proof.

Vm (Q) ≤ 4CKm ε m δ . Proof. Let Q a distribution over A. Recall that Vm (Q) = m i=1 R a * i -R a i -[R (a * ) -R(a)]
To conclude, we apply Lemmas C. Proof. Fix δ > 0. For any pair (λ k , P k ), k ≥ 1, we apply Thm. 2.1 with

δ k := δ k(k + 1) ≥ δ (k + 1) 2 .
Notice that we have +∞ k=1 δ k = δ. We then have with probability 1 -δ k over S, for any m ≥ 1, any posterior Q,

|M m (Q)| ≤ KL (Q, P k ) + 2 log(k + 1) + log(2/δ) λ k + λ k 2 Vm (Q) + V m (Q) .
Taking an union bound on all those event, gives the final result, valid with probability 1 -δ over the sample S, for any any tuple (m, λ k , P k ) with m, k ≥ 1, any posterior Q over H. This gives Eq. ( 6).

To obtain Eq. ( 7), we restrict the range of Eq. ( 6) to the tuples (m, λ m , P m ), m ≥ 1 (the restricted set of tuples where k = m) and we bound both Vm (Q), V m (Q) by For the second bound, we start from Eq. ( 8) again and for a fixed m, we now apply our result with λ = λ/m. We then have for any m, with probability 1 -δ, for any

Q λ |E h∼Q [R(h) -R m (h)]| ≤ KL(Q, P ) + log(1/δ) + λ 2 2m 2 m i=1 E h∼Q [∆[M ] i (h) + ∆ M i (h)].
Finally, dividing by λ, bounding ∆[M ] i (h) + ∆ M i (h) by 2K 2 and rearranging the terms concludes the proof.

C. 2

 2 Proof of Thm. 4.1 Proof. Let (λ m ) i≥1 be a countable sequence of positive scalars. As precised earlier M m (a) := m ∆m (a) -∆(a) is a martingale. We then apply Thm. 2.1 with the uniform prior (∀a, P (a) = 1 K ) and λ = λ m (depending possibly on m): with probability 1 -δ/2, for any tuple (m, λ m ) with m ≥ 1, any posterior Q,|M m (Q)| ≤ KL (Q, P ) + 2 + log(4/δ) λ m + λ m 2 Vm (Q) + V m (Q) .

  any a, ( Ŝ M a m ) m is a nonnegative random variable. We then apply Markov's inequality for any a, with probability 1 -δ/2KVm (a) ≤ 2KE[ Vm (a)] δ .Noticing that E[ Vm (a)] = E[V m (a)], we can apply Lemma C.1 to conclude thatE[ Vm (a)] ≤ 2Cm ε m .Finally, taking an union bound on thoser events for all a ∈ A gives us, with probability 1 -δ/2,

  1 and C.2 to get that with probability 1 -δ, for any posterior Q |M m (Q)| ≤ KL (Q, P ) + log(4/δ)

EE

  For the first bound we start from the intermediary result Eq. (3) of Thm. 2.1. Using the same marrtingale as in Thm. 2.3 gives, for any η ∈ R, holding with probability 1 -δ for any m > 0,Q ∈ M + 1 h∼Q [ (h, z i )] -mE h∼Q [R(h)] ≤ KL(Q, P ) + log(1h∼Q [∆[M ] i (h) + ∆ M i (h)].Taking η = ±λ with λ > 0 givesλm |E h∼Q [R(h) -R m (h)]| ≤ KL(Q, P ) + log(1/δ) + λ 2 2 m i=1 E h∼Q [∆[M ] i (h) + ∆ M i (h)].(8)Finally, divide by λm and bound ∆[M ] i (h) + ∆ M i (h) by 2K 2 to conclude.

  (see Thm. A.1). For a martingale M m (h) = m i=1 X i (S i , h), we define, at time m, empirical cumulative variance to be Vm

  The proof is deferred to Appendix C. Remark that the second bound of Corollary B.2 is exactly the Catoni bound stated in[START_REF] Alquier | On the properties of variational approximations of gibbs posteriors[END_REF] (see Thm. A.2 in Appendix A) up to a numerical factor of 2.

  [START_REF] Haddouche | PAC-Bayes unleashed: generalisation bounds with unbounded losses[END_REF] which provides general PAC-Bayesian bounds for unbounded losses. Their theorems hold for iid data and under the so-called HYPE (for HYPothesisdependent rangE) condition. It states that a loss function is HYPE(K) compliant if there exists a function K : H → R + (supposedly accessible) such that ∀z ∈ Z, (h, z) ≤ K(h). We provide Cor. B.3 to compare ourselves with their main result (stated in Thm. A.3 for convenience). For any data-free prior P ∈ M + 1 (H), any loss function being HYPE(K) compliant, any α ∈ [0, 1], m ≥ 1, the following holds with probability 1 -δ over the sample S

	Corollary B.3.


Lotfi Baidar
email: l.baidar@esi-sba.dz

Abdellatif Rahmoun
email: a.rahmoun@esi-sba.dz

Pascal Lorenz
email: lorenz@ieee.org

Miloud Mihoubi
email: miloud.mihoubi@univ-sba.dz

Whale Optimization Approach for Optimization Problem In Distributed Wireless Sensor Network

Keywords: Wireless Sensor Network, node localization, optimization problem, metaheuristic, Whale Optimization Algorithm ACM Reference format:

Recently, Node localization has played a vital role in wireless sensor networks (WSN), where the node's coordinates have mostly required before sensing operation. Sensor devices are randomly deployed in the network for monitoring task. The crucial objective of localization is to determine the position of the sensor nodes based on a few landmark nodes. Node localization problem is formulated as an optimization problem and metaheuristic techniques are called to deal with the issue in multidimensional space, in this paper, the Whale Optimization Algorithm (WOA) is proposed to deal with the challenge, furthermore, the capability of auto localization is highly requested. WOA computes iteratively the node's positions based on a multistage approach to browse the whole region of the network. Deploying this algorithm on a large WSN with hundreds of sensors shows good performance in terms of node localization. the simulation result proved the good performance of WOA in term of localization error and computing time .

CCS CONCEPTS

CCS → Networks → Network types → Wireless access networks.

INTRODUCTION

WSN (Wireless Sensor Network) consists of a large number of densely deployed nodes which are tiny, low power, inexpensive, multi-functional connected by a wireless medium. Its main task is to provide information of environment at each moment, the sensors are installed for tracking and monitoring the environmental requirements and physical phenomenon such as climate prediction, analysis of sane, atmospheric pressure, etc.

WSN is employed in several application domains such as security and surveillance, data aggregation, environment sensing, industrial process control, structural health monitoring [START_REF] Adnan | Bio-Mimic optimization strategies in wireless sensor networks: a survey[END_REF]. The gathered information needs to be associated with rental sensor nodes to provide an accurate view of the sensor field. Each sensor can monitor its region and proceed to send the collected data to sink node, the effectiveness of WSN is bound to its ability to collect data and transmit them in a minimum time and with greater precision [START_REF] Akyildiz | A survey on sensor networks[END_REF].Numerous challenges are addressed in WSN and have been largely browsed: energy minimization (optimization), energy harvesting, compression schemes, selforganizing network algorithms, routing protocols, security, quality of service management, etc… The three most essential problems are energy efficiency, quality of service and security management [START_REF] Sohraby | Wireless sensor networks: Technology, protocols, and applications[END_REF], moreover, one of the most issues in WSN is node localization, the information location plays a vital role in coverage, deployment purpose, routing information, location service, target tracking, and rescue operations. The intuitive solution is to equip every node with a Global Positioning System (GPS) receiver that can accurately provide the sensors with their exact location, localization by equipping each node with GPS is not suitable, because it is less energy efficient and expensive , it needs large size of hardware and has a line of sight problem. On the other hand, If GPS is installed on every node, then it increases the node size and deployment cost. Furthermore, GPS is not energy efficient as it consumes a lot of energy and not suitable for a network like WSN, where for instance, it does not work at all in indoor environments. Numerous localization methods have been proposed for solving the problem, in place of equipping each node by a GPS, the majority of methods allowed to use a certain number of nodes in the network equipped with GPS. These nodes are generally known by anchor nodes, beacons or landmark which their position is known, the remain sensors communicate with the anchor nodes for determinate its positions by using some localization algorithm. This paper is divided into eight sections, section two gives an survey about localization technique founded, the section three describes the mechanism of Whale Optimization Algorithm, the node localization problem is formulated in section four, In the fifth section a simulation result is presented and analyzed to evaluate the performance of the proposed algorithm, Our conclusion is drawn in the final section.

LITERATURE SURVEY

A detailed survey on localization is available in [START_REF] Alrajeh | Localization Techniques in Wireless Sensor Networks[END_REF][START_REF] Chowdhurya | Advances on Localization Techniques for Wireless Sensor Networks: A Survey[END_REF][START_REF]Localization Algorithms in Wireless Sensor Networks: Current Approaches and Future Challenges[END_REF][START_REF] Han | Localization algorithms of Wireless Sensor Networks: a survey[END_REF][START_REF] Hoang | An RSS comparison based Localization in Wireless Sensor Networks[END_REF] , furthermore , node localization challenge can be divided via much consideration and according to several criteria: the mobility of the nodes (static vs. mobile, mixed), the execution environment (centralized vs. distributed, mixed), distance estimation (rangefree and range-based).

Localization scheme can be divided into three components combined show Fig. 1, where several methods are proposed the first phase (distance estimation). The main task of the first phase is evaluating the distance between beacons nodes and target nodes, where many techniques are used , we found Radio Signal Strength Indicator ( RSSI ) [START_REF] Cheon | IEEE 802.15.4 ZigBee-Based Timeof-Arrival Estimation for Wireless Sensor Networks[END_REF], Time of Arrival ( TOA ) and Time Difference of Arrival ( TDOA ) [START_REF] Zhu | A distributed continuous-time algorithm for network localization using angle-of-arrival information[END_REF], Angle of Arrival (AOA) [START_REF] Pk | node localization in wirless sensor network[END_REF] are applied to calculate the angle or distance [START_REF] Singh | A Hybrid Localization Algorithm for Wireless Sensor Networks[END_REF].

The second phase named position computation, exploiting the data from distance estimation phase it is possible to calculate the coordinates of the target nodes, wherein the several approaches are proposed in this phase: such methods include trilateration multi-lateration, triangulation, probabilistic approaches, bounding box, the central position, fingerprinting [START_REF] Boukerche | Localization systems for wireless sensor networks[END_REF], there is other work concentrates all information about distances computing that uses mathematical optimization techniques to compute the positions of the nodes.

The third phase of localization scheme is localization algorithm , the combining operation schematized in Fig. 1, localization algorithm determines how the information concerning distances and positions is manipulated in order to allow nodes of a WSN to estimate their positions.

Localization algorithm has received much attention in the last two years, recently, metaheuristic methods have been seen as important tools to solve the problem of optimization, and node localization is treated as a multidimensional optimization problem, where a substantial number of methods are addressed through population-based stochastic techniques. PSO (particle swarm optimization) is proposed [START_REF] Gopakumar | Localization in wireless sensor networks using particle swarm optimization[END_REF] for node localization problem. After getting the estimated distances and calculated coordinates in the network by the estimation and calculation phases. The basic idea of this approach that all unknown nodes send the coordinates and distance to a base station, the base station runs PSO to minimize the tracking error defined. The approach does not take into account the flip ambiguity problems (Fig. 1), and location of nodes that do not have at least three tags in their neighborhood, The system only works well if either beacon have sufficient range or there is a large number of beacons. In addition, the base station requires estimates the range of all target nodes located in the surrounding of beacons nodes. This requires a lot of communication that can lead to congestion, delays and the depletion of energy. More than, the proposed scheme has limited scalability because the dimensionality PSO is twice the number of target nodes.

Fig. 1. Flip ambiguity phenomenon

PSO approach BFA are proposed [START_REF] Kulkarni | Bio-inspired node localization in wireless sensor networks[END_REF] to deal with the localization issue, the distributed architecture is utilized for both approaches, iterative fashion to locate the nodes, this means that each target node that has three or more beacons in its hearing range runs localization Algorithm to minimize the localization error, and each node localized in the iteration i is considered as an anchor nodes at iteration i+1.

The process continues iteratively until either all the nodes get localized or no more nodes can be localized, the proposed method does not require that each node transmit it range measurement to a central node. Besides, it can localize all nodes that have three beacons nodes in their range. As the localization iterations pass by, a node may get the number of references for localization, which mitigates the flip ambiguity problem, the situation that results in large localization error when the references are near collinear. However, the proposed method is prone to error accumulation.

A comparison of the performance of PSO and BFA in the number of nodes localized, localization accuracy and computation time is presented according to the results, it has concluded that the two approaches have a trade problem where simulations obtained showed that PSO is convergent quickly by contribution to BFA, on other hand BFA gives many error accuracies than PSO .

Binary PSO is proposed to minimize localization time and energy computing and Improving the original approach, where the same strategy of localization phase utilized in [START_REF] Zain | Distributed Localization for Wireless Sensor Networks using Binary Particle Swarm Optimization (BPSO)[END_REF], this approach has proven effective in comparison with the original approach, although it is efficient in terms of convergent but localization error remains low than the original PSO. h-best PSO is proposed for enhancement of PSO for node localization problem [START_REF] Kumar | Meta-Heuristic Range Based Node Localization Algorithm for Wireless Sensor Networks[END_REF], the objective of the proposed approach is to have a fast converging for localization and have a significant localization rate in terms of nodes and minimizing the location error, the results obtained demonstrated that the proposed approach is efficient when compared with PSO original and BBO, Although The HPSO-based localization algorithm determined the accurate coordinates Quickly, whereas BBO-based localization algorithm find the coordinate of the nodes more accurately. The proposed algorithms also reduce the number of transmissions to the base station, that helps the node to retain more energy, and so, the node can perform for a long period. in [START_REF] Chandirasekaran | A Case Study of Bio-Optimization Techniques for Wireless Sensor Network in NodeLocation Awareness[END_REF], a comparative study is presented in this paper, and three famous meta-heuristics: PSO, SFLA, FFA are proposed for node localization in distributed scheme range based, several parameters are combined in comparison as execution time, localization error, number of the non-localized node. For understanding the performance of the proposed algorithms, Lab VIEW platform is used. The obtained results show that the PSO converge rapidly then FFA and SFLA algorithms but it gives more average error then the two other. The point common is that there is not the grand difference in the errors offered by both, the selection of the algorithms to use for localization depends entirely on the hardware available to the user and the time constraints involved. The using of short transmission radius is not suitable for these algorithms.

In 2017, a comparative study is introduced between the three most popular metaheuristic (Bat Algorithm, PSO and DE) in [START_REF] Mihoubi | Metaheuristic RSSI based for node localization in distributed wireless sensor network[END_REF], whereas two criteria parameter are evaluated: localization error and localization time), the obtained result shown that Bat algorithm gives more efficiency and accuracy rate is better than the two other.

In 2018, an Effective Bat algorithm is proposed for node localization issues [START_REF] Miloud | An effective Bat algorithm for node localization in distributed wireless sensor network[END_REF], the drawback of original Bat algorithm is improved by introducing the Doppler effect phenomena, The updating frequency makes the algorithm converge rapidly during the moving of the bats and localization error is minimized, on the other hand, two parameters are added to balancing the algorithm and regularize the performance. The simulation results demonstrate that the proposed algorithm has a high convergence rate and greater precision than the original Bat algorithm and particle swarm optimization (PSO) algorithms.

In 2017 , Grey Wolf Optimization (GWO) is another metaheuristic proposed for node localization challenge [START_REF] Rajakumar | Grey Wolf Optimization Algorithm for Node Localization Problem in Wireless Sensor Networks[END_REF], the simulations results are compared with MBA (modified Bat algorithm and PSO ) , we can conclude that GWO is more efficient than the two other proposed algorithm , GWO proved that has faster convergence rate and estimating the location of the node .

Moth Flame Optimization Algorithm (MFOA) is the latest approach proposed to deal with node localization in distributed paradigm of WSN [START_REF] Miloud | Moth Flame Optimization Algorithm Range-Based for Node Localization Challenge in Decentralized Wireless Sensor Network[END_REF], MFOA it is show are combination between PSO and genetic algorithm (GA) , furthermore, the moth fly smartly through several trajectory as spiral trajectory, the simulations result prove that MFOA is very efficient and improve the performance of the network .

WHALE OPTIMIZATION ALGORITHM

The Whale Optimization Algorithm (WOA) was proposed by the authors of Mirjalili and Lewis [START_REF] Mirjalili | The whale optimization algorithm[END_REF] inspired from the behavior of the humpback whales, the fundamental steps of WOA are summarized as follow :

Encircling prey

Humpback whales can recognize the location of prey and encircle them. Since the position of the optimum design in the search space is not known a priori, the WOA algorithm assumes that the current best candidate solution is the target prey or is close to the optimum. After the best search agent is defined, the other search agents will hence try to update their positions towards the best search agent. This behavior is represented by the folling equations :

) ( ) ( . * t X t X C D   (1) D A t X t X . ) ( ) 1 ( *    (2)
Where t indicates the current iteration, A and C are coefficient vectors, * X is the position vector of the best solution obtained so far, X is the position vector .

Is the absolute value, and • is an element-by-element multiplication. It is worth mentioning here that * X should be updated in each iteration if there is a better solution.

The vectors A and C are calculates as follows :

a r a A   . 2 (3) r C . 2  (4)
Where a are linearly decreased from 2 to 0 over the course of iterations (in both exploration and exploitation phases) and r is a random vector in [0,1] .

Bubble-net attacking method (exploitation phase)

In order to mathematically model the bubble-net behaviour of humpback whales, two approaches are designed as follows :

1. Shrinking encircling mechanism: This behaviour is achieved by decreasing the value of a in the equation [START_REF] Sohraby | Wireless sensor networks: Technology, protocols, and applications[END_REF]. Note that the fluctuation range of A is also decreased by a .

In other words A is a random value in the interval [-a, a] where a is decreased from 2 to 0 over the course of iterations.

Setting random values for A in [-1, 1], the new position of a search agent can be defined anywhere in between the original position of the agent and the position of the current best agent.

Spiral updating position:

The spiral equation between the position of the prey and the whale to imitate the helix-shaped movement of the humpback whales is as follows:

) ( ) 2 cos( . . ) 1 ( * ' t X l e D t X bl     (5)
It is worth noticing that humpback whales swim around the prey within a shrinking circle and along a spiral-shaped path simultaneously. So in order to model this behavior, we assume the probability of 50% to choose between either the shrinking encircling method or the spiral model, to update the position of whales. The mathematical model is described as follows:

Where ) ( ) ( * ' t X t X D  
and indicates the distance of the ith whale from the prey (best solution obtained so far), b is a constant for defining the shape of the logarithmic spiral, and t is a random number in [-1,1].

Search for prey (exploration phase)

The variation of vector can be utilized to search for prey, i.e., exploration phase. Therefore, can be used with the random values greater than 1 or less than -1 to force search agents to move away from a reference whale. The mathematical model for this phase is as follows:

X rand X C D   . (7) D A rand X t X . ) 1 (    (8) ,
Where rand X is a random position vector (a random whale) chosen from the current population .

Pseudo code of the WOA algorithm

NODE LOCALIZATION BASED ON WOA

The main objective of localization is to find out the coordinate of target nodes by using anchor nodes with single hop range-based distributed technique. The main steps of node localization scheme are:

1. M target nodes and N anchor nodes are randomly deployed in the sensor field. Each target node and anchor node has transmission range R. Anchor nodes compute their location awareness and transmit their coordinates. The nodes which get settled at the end of iteration serve as reference nodes during the next iteration and behave like anchors.

2. The node that falls within transmission range of three or more anchors is considered as localized node.

3. Each localized node measures its distance from each of its neighboring anchors. The distance measurements are corrupted with Gaussian noise , due to environment consideration. A node estimates its distance from ith anchor as = [ + ], where d is actual distance given by: (9)

Whereas (x, y) is the location of the target node and ( , ) is the location of the ith anchor node in the neighborhood 4. Each localizable node WOA independently to localize itself by finding its coordinates (x, y). The objective function (mean of square of error between actual and estimated distances of computed node coordinates and the actual node coordinates), is minimized by: [START_REF] Zhu | A distributed continuous-time algorithm for network localization using angle-of-arrival information[END_REF] Where N ≥ 3 ( 2 D location of a node needs minimum 3 anchors) is the number of anchors with in transmission range, R, of the target node .

5. Evolves the optimal location of target nodes, i.e. (x, y) by minimizing the error function 6. After coordinate so fall localizable nodes (say, ML) are determined, the mean localization error is computed as the mean of square of distance so of computed nodes coordinates ( ) and the actual node coordinates ( , for i = 1, 2, ML determined for WOA , as shown below: [START_REF] Pk | node localization in wirless sensor network[END_REF] Where "L=M-N " As the iterations progress, the number of localized nodes increases. This increases the number of references available for already localized nodes. A node that localizes using just three references in an iteration k may have more references in iteration k +1. This decreases the probability of the flip ambiguity.

SIMULATION EXPERIMENTS AND PERFORMANCE EVALUATION

Simulation Setup

In this subsection, all the simulations are performed using MATLAB 8.4 environment on a laptop of 4 GB memory and i5-2.4 GHz CPU to evaluate the performance of WOA. In our simulation experiments, the sensor nodes are randomly deployed over a 100. 100 square area (see Fig. 2). The number of sensors nodes is 200 and 20 anchor nodes are taken. The transmission range of sensor node is 30. The initial deployment of sensor node is random, so, for each iteration, the number of localizable nodes is not expected to be the same. The unknown nodes coordinates is calculated using WOA.

Fig. 2. Nodes deployment in network

The neighbor relationship diagram according to the node deployment is displayed in Fig. 3, The neighbor relationship diagram explains the audience and the relation between the sensors nodes.

Fig. 3. Communication connectivity of Sensor nodes

The localized and target sensor locations obtained by WOA algorithm are shown in the Fig. 4.

Performance Evaluation

In this part, we study the performance of the proposed approach, the convergence time is evaluated with increasing number of iterations. The result of convergence is shown in Fig. One hundred sensors nodes are deployed randomly in 100 x 100 m area, the anchors nodes are 4 placed in the corner of the rectangle network to avoid the collinear problem like the literature [START_REF] Abdi | a hybrid RSSI based localization algorithm for WSN using a mobile anchor node[END_REF]. Their coordinates are (0, 0), (0, 100), (100, 0) and (100, 100). In addition, it is assumed that the communication range of the anchors nodes and the sensors nodes in the sensor area and each sensor node can communicate with every other sensor node in the sensor field. The simulation result are presented in the Fig. 6 and the Fig. 7 ,

  Input data, Number of maxiter and Population etc Initialize the whales population Xi (i = 1, 2, ..., n) Initialize a, A, C, l and p Calculate the fitness of each search agent X*= the best search agent while (it < Maxiter) for each search agent if (p < 0.5) if (|A| < 1) Update the position of the current search agent by the equation (1) else if (|A| ≥ 1) Select a random search agent (X_rand) Update the position of the current search agent by the equation (8) end else if (p ≥ 0.5) Update the position of the current search by the by the equation (5) end end Calculate the fitness of each search agent Update X* if there is a better solution it=it+1 Update a, A, C, l and p end while return X*

7 .

 7 Steps 2 to 6 are repeated by number of iteration defined or until all target nodes get localized or no more nodes can be localized. The performance of the localization algorithm is based on EL and MML, where MML = [M -ML] is the number of nodes that could not be localized. Lesser the value of ML and L, better the performance is.

Algorithm 1 : 1 : 2 : 3 : 4 : 5 :

 112345 Multi-stage localization using WOA Initialize network topology Find unknown nodes with three or more anchor nodes in their neighborhood Run WOA algorithm to find location of unknown nodes identified in step 2 Add localized sensor nodes In current stage to the anchor node list and remove them from unknown node list Repeat steps 2-4 until all sensor nodes are localized

Fig. 4 .

 4 Fig. 4. Node localization By WOA

5

 5

Fig. 5 . 5 . 3

 553 Fig. 5. Convergence of WOA 5.3 Comparative study In this part, to evaluate the performance of the WOA applied to node localization challenge, a comparative study localization error/localization time versus iteration number is carried out with the most recent metaheuristics: PSO, DE, GWO and MFOA. One hundred sensors nodes are deployed randomly in 100 x 100 m area, the anchors nodes are 4 placed in the corner of the rectangle network to avoid the collinear problem like the literature

Fig. 6 .Fig. 7 . 6 CONCLUSION

 676 Fig. 6. Localization error versus Iteration number