Antoine Godichon
email: antoine.godichon_baggioni@sorbonne-universite.fr

gradient algorithms without strong convexity nor bounded gradient

Convergence in quadratic mean of averaged stochastic gradient algorithms without strong convexity nor bounded gradient

Antoine Godichon-Baggioni

Introduction

A usual problem in stochastic optimization and machine learning is, considering a random variable X, to estimate the minimizer of a convex function G of the form

G(h) = E [g(X, h)]
where h lies in a separable Hilbert space H. This problem is encountered when we estimate, for instance, the parameters of logistic regressions [START_REF] Bach | Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression[END_REF][START_REF] Cohen | On projected stochastic gradient descent algorithm with weighted averaging for least squares regression[END_REF], the geometric median and quantiles [START_REF] Cardot | Efficient and fast estimation of the geometric median in Hilbert spaces with an averaged stochastic gradient algorithm[END_REF][START_REF] Godichon-Baggioni | Estimating the geometric median in hilbert spaces with stochastic gradient algorithms: Lp and almost sure rates of convergence[END_REF][START_REF] Cardot | Online estimation of the geometric median in hilbert spaces: Nonasymptotic confidence balls[END_REF], or superquantiles [START_REF] Bercu | Stochastic approximation algorithms for superquantiles estimation[END_REF][START_REF] Costa | Non asymptotic controls on a recursive superquantile approximation[END_REF]. Since the gradient or the Hessian of G cannot be explicitly calculated, one cannot apply usual optimization methods such that gradient or Newton algorithms to approximate the minimizer. A solution to overcome this problem, considering n i.i.d copies X 1 , . . . , X n of X, is to approximate the solution of the empirical function

G n (h) = 1 n n ∑ k=1 g(X k , h).
Nevertheless, this often necessitates high computational costs when the dimension of H and the sample size are both large. In order to partially overcome this cost problem, one way is to focus on mini-batch gradient algorithms, i.e to consider iterative estimates of the form

m t+1 = m t -γ t ∑ i∈S t ∇ h g (X i , m t )
where S t ⊂ {1, . . . , n} is the mini-batch considered at time t (Konečn ỳ et al., 2015; Alfarra et al., 2020). Nevertheless, these kinds of methods necessitate to store all the data into memory and do not enable to easily update the estimates if the data arrive sequentially. In order to address these problems, the online stochastic gradient algorithm introduced by [START_REF] Robbins | A stochastic approximation method[END_REF] should be preferred. Nevertheless, as mentioned in [START_REF] Pelletier | On the almost sure asymptotic behaviour of stochastic algorithms[END_REF], the estimates obtained with this algorithm hardly ever attain the asymptotic efficiency. Fortunately, one can consider its averaged version introduced by [START_REF] Ruppert | Efficient estimations from a slowly convergent robbins-monro process[END_REF] and [START_REF] Polyak | Acceleration of stochastic approximation[END_REF] which is known to be asymptotically efficient [START_REF] Pelletier | Asymptotic almost sure efficiency of averaged stochastic algorithms[END_REF]. In this paper, we focus on non asymptotic analysis of such estimates.

Related works

The rate of convergence in quadratic mean of averaged stochastic gradient algorithms in the case where G is strongly convex was given in [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)[END_REF]. Nevertheless, the loss of strong convexity generates several technical problems and makes the obtaining of non asymptotic results much more difficult. In recent works, [START_REF] Bach | Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression[END_REF] and [START_REF] Gadat | Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity[END_REF] succeeded in obtaining the L 2 rates of convergence of the estimates but supposed for this that the gradient of g is bounded, which can be considered as restrictive. For instance, this is not verified in most of regressions if the eplicative variable is not bounded, or in the case of the recursive estimation of p means with p ∈ (1, 2) (Godichon-Baggioni, 2019b). In Godichon-Baggioni (2019a), the gradient of g was not supposed to be bounded anymore, but it was assumed that it admits moments of any order.

Furthermore, the upper bounds of the quadratic mean errors of the estimates at time n were not explicitly given. In addition, in [START_REF] Cardot | Online estimation of the geometric median in hilbert spaces: Nonasymptotic confidence balls[END_REF], non asymptotic confidence balls were given in the case of the recursive estimation of the geometric median, but these balls where only available from a non calculated rank. Recently, [START_REF] Costa | Non asymptotic controls on a recursive superquantile approximation[END_REF] focus on the use of stochastic gradient algorithms for superquantiles estimation and give uniform bounds of the quadratic mean error of the estimates. Nevertheless, here again, the bound depends on non calculated constants. Finally, in a recent work, [START_REF] Défossez | A simple convergence proof of adam and adagrad[END_REF] give simple proof for obtaining convergence results for some adaptive stochastic gradient methods.

Contribution

In this work, the aim is to give a very weak framework for each we are able to obtain explicit L 2 rates of convergence of stochastic gradient estimates and their averaged version. First, we replace usual strong convexity assumption by strict (or locally strong) convexity. Second we do not assume that the gradient of g is bounded or admits moments of any order, but we only suppose that it admits a fourth order moment. Finally, under weak assumptions, we give explicit bounds of the quadratic mean errors of the estimates and prove that, up to a calculated rest term, the averaged estimates achieve the Cramer-Rao bound.

Notations

In this paper, we denote by . the euclidean norm on H, ., . the associated inner product, and . op the spectral norm of operators on H. Remark that given h, h ′ ∈ H, we will also write h, h ′ = h T h ′ . Furthermore, for all h ∈ H and r > 0, B(h, r)

:= {h ′ ∈ H, h -h ′ ≤ r}.
Finally, for any x ∈ R, ⌈x⌉ gives the superior integer part of x.

Paper organization

The paper is organized as follows: first the framework and assumptions are given and discussed in Section 2. The rate of convergence in quadratic mean of the stochastic gradient estimates are introduced in Section 3 while the ones for their averaged version are given in Section 4. Finally, the proofs of the convergence results for gradient estimates and their averaged version are respectively postponed in Sections 5 and 6.

Framework

In what follows, we consider a random variable X taking values in a measurable space X and let H be a separable Hilbert space (not necessarily of finite dimension). We focus on the estimation of the minimizer θ of the convex function G : H -→ R defined for all h ∈ H by

G(h) := E [g (X, h)]
with g : X × H -→ R. Throughout the suite, we will suppose that the following assumptions are fulfilled:

(A1) For almost every x ∈ X , the functional g(x, .) is differentiable on H and there are non-negative constants

C 1 , C ′ 1 , C 2 , C ′ 2 such that for all h ∈ H, E ∇ h g (X, h) 2 ≤ C 1 + C 2 (G(h) -G(θ)) , E ∇ h g (X, h) 4 ≤ C ′ 1 + C ′ 2 (G(h) -G(θ)) 2 (A2)
The functional G is twice continuously differentiable and λ min := λ min ∇ 2 G(θ) > 0.

(A3)

The Hessian of G is uniformly bounded on H, i.e there is a positive constant L ∇G such that for all h ∈ H, ∇ 2 G(h) op ≤ L ∇G .

(A4) There are positive constants λ 0 , r λ 0 and a non-negative constant C λ 0 such that ∀h ∈ B (θ, r λ 0 ),

λ min ∇ 2 G (h) ≥ λ 0 and ∇G(h) -∇ 2 G(θ) (h -θ) ≤ C λ 0 h -θ 2
Remark that Assumption (A1) ensures that the functional G is differentiable. One of the main difference with [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)[END_REF] and [START_REF] Gadat | Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity[END_REF] is that they suppose that the gradient of g is uniformly bounded. Moreover, an important difference with Godichon-Baggioni (2019a) is that we only suppose that the moment of order four of the gradient exists instead of each moments. In addition, Assumption (A2) leads the functional G to be strictly convex, so that θ is its unique minimizer. Furthermore, Assumption (A3) ensures that the gradient of G is L ∇G -lipschitz. Finally, Assumption (A4) just means that there is a neighborhood of θ on each we have both locally strong convexity of G and a locally quadratic increasing of the rest term in the Taylor's expansion of the gradient (which is verified as soon as the Hessian of G is lipschitz on a neighborhood of θ). Remark that if H is a finite dimensional space, the local strong convexity was already given by (A2). As a conclusion, these assumptions can be considered as weak compare to the existing ones in the literature on non-asymptotic results.

The stochastic gradient algorithm

In what follows, let us consider X 1 , . . . , X n , X n+1 , . . . be i.i.d copies of X. The stochastic gradient algorithm is defined recursively for all n ≥ 0 by [START_REF] Robbins | A stochastic approximation method[END_REF])

θ n+1 = θ n -γ n+1 ∇ h g (X n+1 , θ) , (1)
with θ 0 bounded. We consider from now a stepsequence (γ n ) of the form γ n = c γ n -α , where c γ > 0 and α ∈ (1/2, 1).

Case with unbounded gradient

In this section, we focus on the case where C 2 = 0 or C ′ 2 = 0. We first give the rate of convergence in quadratic mean of G (θ n ).

Lemma 3.1. Suppose Assumptions (A1) to (A4) hold. Then,

E (G (θ n ) -G(θ)) 2 ≤ e -1 4 c γ a 0 n 1-α e 2a 1 c 2 γ 2α 2α-1 +2a 2 c 3 γ 3α 3α-1 u 0 + σ 2 c 3 γ 3α 3α -1 + 2 1+4α σ 2 c 2 γ a 0 n -2α with u 0 = E (G (θ 0 ) -G(θ)) 2 , a 0 = λ 2 0 min 1,r 2 λ 0 L ∇G , a 1 = max λ 4 0 4L 2 ∇G , C 2 (4L ∇G + 1) , a 2 = 1 2 L 2 ∇G C ′ 2 , and σ 2 = C 2 1 (4L ∇G +1) 2 L ∇G 12λ 2 0 min 1,r 2 λ 0 + c γ L 2 ∇G C ′ 1 2 .
In a simple way, this lemma ensures that we have the usual rate of convergence

E [G (θ n )] - G(θ) = O (n -α
). This result is crucial to give the following rate of convergence in quadratic mean of the estimates θ n . Theorem 3.1. Suppose assumptions (A1) to (A4) hold. Then,

E θ n -θ 2 ≤ Ae -1 4 λ min c γ n 1-α + c 1 2L 2 δ λ 2 min e -1 8 a 0 c γ n 1-α + 2 2+8α σ 2 c 2 γ a 0 L 2 δ λ 2 min n -2α + 2 1+α C 1 λ min c γ n -α with a 0 , a 1 , a 2 , σ 2 defined in Lemma 3.1, v 0 = E θ 0 -θ 2 ] , L δ = max 2C λ 0 λ 0 , 2L ∇G λ 0 r λ 0 , b 1 = L ∇G 2 max C 2 , λ 2 min 2L ∇G , c 1 = exp 2a 1 c 2 γ 2α 2α-1 + 2a 2 c 3 γ 3α 3α-1 v 0 + σ 2 c 3 γ 3α 3α-1 and A = e 2b 1 c 2 γ 2α 2α-1 v 0 + 2αc 2 γ C 1 2α -1 + 2 L 2 δ λ min u 0 c γ + c 1 + 4c 1 a 0 (1 -α) e -1 4 a 0 c γ + 2 1+4α σ 2 c 3 γ a 0 3α 3α -1 .
In other words, we get the usual rate of convergence E θ nθ 2 = O (n -α ) (Bach and Moulines, 2013; Gadat and Panloup, 2017; Godichon-Baggioni, 2019a) and so, with weak assumptions. Moreover, contrary to [START_REF] Gadat | Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity[END_REF] and Godichon-Baggioni (2019a), we give an explicit boud of the quadratic mean error. Finally, note that for the main term, i.e 2 1+α C 1 λ min c γ n -α , we succeed in obtaining a term analogous to the one in the strongly convex case given by [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)[END_REF]. Let us now discuss about the rest terms.

The term Ae -1 4 λ min c γ n 1-α can be seen as a quantification of the error due to the initialization while the term c 1

2L 2 δ λ 2 min e -1 8 a 0 c γ n 1-α + 2 2+8α σ 2 c 2 γ a 0 L 2 δ λ 2 min n -2α comes from the error approximation of ∇ 2 G(θ) (θ n -θ) by ∇G (θ n ).
Remark that in the particular case of the linear regression, C λ 0 = 0 for any r λ 0 . Moreover, one can take r λ 0 = +∞ and λ 0 = λ min , which leads to L δ = 0 and to a bound analogous to the one in [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)[END_REF].

Case with ∇G(.) bounded

Since in several cases such as logistic regression, softmax regression or the estimation of the geometric median one has C 2 = C ′ 2 = 0, we now focus on this case to have more precise bounds. We first give the rate of convergence in quadratic mean of G (θ n ).

Lemma 3.2. Suppose assumptions (A1) to (A4) hold. Then, for all n ≥ 1,

E (G (θ n ) -G(θ)) 2 ≤ c n ′ 0 exp - 1 2 a 0 c γ n 1-α + σ 2 M 0 c 2 γ n -2α with n ′ 0 = inf {n, a 0 γ n+1 ≤ 1}, c n ′ 0 := σ 2 exp 1 2 a 0 c γ (n ′ 0 + 1) 1-α γ 3 n ′ 0 + c 3 γ 3α 3α-1 , M 0 := max 2 4α
a 0 , c γ and a 0 , σ 2 defined in Lemma 3.1.

We can now give the rate of convergence in quadratic mean of θ n in the particular case

where

C 2 = C ′ 2 = 0.
Theorem 3.2. Suppose Assumptions (A1) to (A4) hold. Then

E θ n -θ 2 ≤ A ′ e -λ min c γ n 1-α + c n ′ 0 L 2 δ λ 2 min e -1 4 a 0 c γ n 1-α + L 2 δ c 2 γ σ 2 λ 2 min M 0 n -2α + 2 α C 1 c γ λ min n -α
with n ′ 1 = min {n, λ min γ n+1 ≤ 1}, a 0 , σ 2 defined in Lemma 3.1, c n ′ 0 , M 0 defined in Lemma 3.2, and

A ′ = e λ min c γ (n ′ 1 +1) 1-α C 1 c 2 γ 2α 2α -1 + c n ′ 0 + c γ u 0 + 2c n ′ 0 a 0 (1 -α) e -1 2 a 0 c γ + σ 2 c 3 γ M 0 3α 3α -1 .
Remark that here again, without surprise, the main term

2 α C 1 c γ λ min n -α
is analogous to the one for the strongly convex case given by [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)[END_REF].

The averaged algorithm

Let us recall that the averaged algorithm introduced by [START_REF] Ruppert | Efficient estimations from a slowly convergent robbins-monro process[END_REF] and [START_REF] Polyak | Acceleration of stochastic approximation[END_REF] is defined for all n ≥ 0 by

θ n = 1 n + 1 n ∑ k=0 θ k ,
which can be written recursively as

θ n+1 = θ n + 1 n + 2 θ n+1 -θ n .

Case with unbounded gradient

In this section, we focus on the case where C 2 = 0 or C ′ 2 = 0. The following theorem gives a first rate of convergence of the averaged estimates.

Theorem 4.1. Suppose Assumptions (A1) to (A4) hold. Then

λ min E θ n -θ 2 ≤ √ C 1 √ n + 1 + L δ 2 1/2+2α σc γ √ a 0 (1 -α) 1 (n + 1) α + 2 1+α 2 5 √ C 1 √ c γ √ λ min 1 (n + 1) 1-α/2 + √ C 2 2 1/4+α √ σ √ c γ a 1/4 0 √ 1 -α(n + 1) 1/2+α/2 + 2 1+4α σL δ √ a 0 λ min ln(n + 1) n + 1 + A ∞ + D ∞ + L δ B ∞ + √ C 2 √ B ∞ + c -1/2 γ v 0 n + 1 + √ A c γ e -1 8 λ min c γ n 1-α (n + 1) 1-α + √ 2 √ c 1 L δ c γ λ min e -1 16 a 0 c γ n 1-α (n + 1) 1-α with A ∞ := √ A c γ ∑ +∞ n=0 e -1 8 λ min c γ n 1-α , B ∞ := ∑ +∞ n=0 e -1 8 c γ a 0 n 1-α e a 1 c 2 γ 2α 2α-1 +a 2 c 3 γ 3α 3α-1 √ u 0 + σc 3/2 γ 3α 3α-1 , and D ∞ := √ 2 √ c 1 L δ λ min c γ ∑ +∞ n=0 e -1 16 a 0 c γ n 1-α .
The main conclusion of this theorem is that we achieve the usual rate of convergence

√ C 1 √
n+1 while the two main rest terms converge at rates 1 (n+1) α and 1 (n+1) 1-α/2 which seems to suggest that the best choice of α could be α = 2/3. Nevertheless, in a recent work and in the special case where ∇g is uniformly bounded, [START_REF] Gadat | Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity[END_REF] give upper bound for each the best rate of convergence should be achieve for α = 3/4. Furthermore, in the particular case of linear regression for which L δ can be chosen equal to 0 and the two main rest terms are so of order 1 (n+1) 1-α/2 and 1 (n+1) 1/2+α/2 which suggests to take α close to 1 2 . Nevertheless, our bounds as the ones given in [START_REF] Gadat | Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity[END_REF] or [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)[END_REF] can be considered as quite rough, that complicates to answer definitely and generally on the best choice of α.

In order to get a (quasi) optimal rate of convergence, let us suppose from now that the variance of the gradient of g is lipschitz, i.e that the following assumption is fulfilled:

(A5) The functional Σ : h -→ Σ(h) = E ∇ h g (X, h) ∇ h g (X, h) T is L Σ lipschitz with
respect to the spectral norm.

Remark that this assumption is already present in Godichon-Baggioni (2019b) and is analogous to Assumption (H S ) in [START_REF] Gadat | Optimal non-asymptotic bound of the ruppert-polyak averaging without strong convexity[END_REF]. The following theorem ensures that, up to rest terms, the averaged estimates achieve the "Cramer-Rao bound".

Theorem 4.2. Suppose Assumptions (A1) to (A5) hold. Then,

E θ n -θ 2 ≤ Tr (H -1 ΣH -1 ) √ n + 1 + L δ 2 1/2+2α σc γ √ a 0 (1 -α) 1 λ min (n + 1) α + 2 1+α 2 5 √ C 1 √ c γ λ 3/2 min 1 (n + 1) 1-α/2 + 2 1/2+α/2 √ C 1 √ L Σ √ c γ λ 3/2 min √ 1 -α(n + 1) 1/2+α/2 + 2 1+4α σL δ √ a 0 λ 2 min ln(n + 1) n + 1 + A ∞ + D ∞ + L δ B ∞ + √ L Σ + c -1/2 γ √ v 0 + √ L Σ c γ A ∞ + √ L Σ c γ D ∞ + 2 1+4α √ L Σ σc γ L δ √ 2αa -1/2 0 λ min √ 2α-1 λ min (n + 1) + √ A c γ e -1 8 λ min c γ n 1-α λ min (n + 1) 1-α + √ 2 √ c 1 L δ c γ e -1 16 a 0 c γ n 1-α λ 2 min (n + 1) 1-α
Remark 4.1. Note that we speak about Cramer Rao bound in the sens that under regularity assumptions, any estimate θn should verify for almost any θ ∈ H,

lim inf n nE θn -θ 2 ≥ Tr H -1 Σ(θ)H -1

Case where ∇G is bounded

We now focus on the case where

C 2 = C ′ 2 = 0.
The following theorem gives the rate of convergence of averaged estimates in this case.

Theorem 4.3. Suppose Assumptions (A1) to (A4) hold and that C 2 = C ′ 2 = 0. Then,

λ min E θ n -θ 2 ≤ √ C 1 √ n + 1 + L δ σc γ √ M 0 (1 -α) 1 (n + 1) α + 2 α 2 5 √ C 1 √ c γ √ λ min 1 (n + 1) 1-α/2 + σL δ √ M 0 λ min (n + 1) ln(n + 1) n + 1 + σL δ √ M 0 λ -1 min + A ′ ∞ + D ′ ∞ + L δ B ′ ∞ n + 1 + √ A ′ c γ e -1 2 λ min c γ n 1-α (n + 1) 1-α + c n ′ 0 L δ c γ λ min e -1 8 a 0 c γ n 1-α (n + 1) 1-α with A ′ ∞ := √ A ′ c γ ∑ +∞ n=0 e -1 2 λ min c γ n 1-α , B ′ ∞ = c n ′ 0 + √ u 0 ∑ n≥0 exp -1 4 a 0 c γ n 1-α and D ′ ∞ := √ c n ′ 0 L δ λ min c γ ∑ +∞ n=0 e -1 8 a 0 c γ n 1-α .
Considering from now that Assumption (A5) is fulfilled, we can now prove that the averaged estimates also achieve, unsurprisingly, the "Cramer-Rao bound" in the case where the gradient of G is bounded.

Theorem 4.4. Suppose Assumptions (A1) to (A5) hold and that

C 2 = C ′ 2 = 0. Then, E θ n -θ 2 ≤ Tr (H -1 ΣH -1 ) √ n + 1 + L δ σc γ √ M 0 (1 -α) 1 λ min (n + 1) α + 2 α 2 5 √ C 1 √ c γ 1 λ 3/2 min (n + 1) 1-α/2 + √ L Σ 2 α/2 √ C 1 √ 1 -α 1 λ 3/2 min (n + 1) 1/2+α/2 + σL δ √ M 0 λ min (n + 1) ln(n + 1) (n + 1)λ min + σ + √ L Σ c γ 2α 2α-1 L δ √ M 0 λ -1 min + A ′ ∞ + D ′ ∞ + L δ B ′ ∞ + √ L Σ √ v 0 + √ L Σ c γ A ′ ∞ + √ L Σ c γ D ′ ∞ (n + 1)λ min + √ A ′ c γ e -1 2 λ min n 1-α λ min (n + 1) 1-α + c n ′ 0 L δ c γ e -1 8 a 0 c γ n 1-α λ 2 min (n + 1) 1-α

Conclusion

In this paper, we provide explicit upper bounds of the quadratic mean error of the online stochastic gradient estimates as well as of their averaged version, and so under very weak assumptions. A first extension of this work could be the obtaining of precise (via concentration inequalities) and calculable confidence balls or ellipse for θ with the help of averaged estimates. A second extension of this work could be to focus on the non-asymptotic rate of convergence of online adaptive stochastic gradient algorithms, such that Adagrad [START_REF] Duchi | Adaptive subgradient methods for online learning and stochastic optimization[END_REF], or stochastic Newton algorithms [START_REF] Boyer | On the asymptotic rate of convergence of stochastic newton algorithms and their weighted averaged versions[END_REF].

Finally since the averaged estimates are known to be sensitive to a bad initialization, a last perspective could be to extend this work to the Weighted Averaged Stochastic Gradient estimates [START_REF] Mokkadem | A generalization of the averaging procedure: The use of two-time-scale algorithms[END_REF].

5 Proofs of Section 3

Some properties on the functionnal G

First remark that with the help of a Taylor's expansion of G, for all h ∈ H,

G(h) = G(θ) + (h -θ) T 1 0 (1 -t)∇ 2 G(θ + t(h -θ))dt(h -θ).
Then, thanks to Assumption (A3),

G(h) -G(θ) ≤ 1 2 L ∇G h -θ 2 .
(2)

Furthermore, thanks to Assumption (A4), for all h ∈ B (θ,

r λ 0 ), (h -θ) T 1 0 (1 -t)∇ 2 G(θ + t(h -θ))dt(h -θ) T ≥ 1 2 λ 0 h -θ 2 . If h / ∈ B (θ, r λ 0 ), i.e if h -θ > r λ 0 , one has (h -θ) T 1 0 (1 -t)∇ 2 G(θ + t(h -θ))dt(h -θ) T ≥ (h -θ) T r λ 0 h-θ 0 (1 -t)∇ 2 G(θ + t(h -θ))dt(h -θ) ≥ 1 2 λ 0 r λ 0 h -θ .
Then,

G(h) -G(θ) ≥ λ 0 2 h -θ 2 1 h-θ ≤r λ 0 + λ 0 2 r λ 0 h -θ 1 h-θ >r λ 0 (3)

Proof of Lemma 3.1

First, thanks to a Taylor's decomposition of G coupled with assumption (A3), we have

G (θ n+1 ) -G(θ) = G (θ n ) -G(θ) + ∇G (θ n ) , θ n+1 -θ n + (θ n+1 -θ n ) T 1 0 (1 -t)∇ 2 G (θ n+1 + t (θ n -θ n+1 )) dt (θ n+1 -θ n ) ≤ G (θ n ) -G(θ) -γ n+1 ∇G (θ n ) , ∇ h g (X n+1 , θ n ) + 1 2 γ 2 n+1 L ∇G ∇ h g (X n+1 , θ n ) 2 . Denoting V n := G (θ n ) -G(θ) and g ′ n+1 = ∇ h g (X n+1
, θ n ), and thanks to Cauchy-Schwartz inequality, it comes

V 2 n+1 ≤ V 2 n + γ 2 n+1 ∇G (θ n ) 2 g ′ n+1 2 + 1 4 γ 4 n+1 L 2 ∇G g ′ n+1 4 + γ 3 n+1 L ∇G g ′ n+1 3 ∇G (θ n ) + γ 2 n+1 V n g ′ n+1 2 -2γ n+1 V n ∇G (θ n ) , g ′ n+1
Then, since

g ′ n+1 3 ∇G (θ n ) ≤ L ∇G γ n+1 4 g ′ n+1 4 + 1 L ∇G γ n+1 g ′ n+1 2 ∇G (θ n ) 2 it comes V 2 n+1 ≤ V 2 n + 2γ 2 n+1 ∇G (θ n ) 2 g ′ n+1 2 + 1 2 γ 4 n+1 L 2 ∇G g ′ n+1 4 + γ 2 n+1 V n g ′ n+1 2 -2γ n+1 V n ∇G (θ n ) , g ′ n+1 .
Taking the conditional expectation and thanks to assumption (A2),

E V 2 n+1 |F n ≤ V 2 n + 2γ 2 n+1 ∇G (θ n ) 2 (C 1 + C 2 V n ) + 1 2 γ 4 n+1 L 2 ∇G C ′ 1 + C ′ 2 V 2 n + γ 2 n+1 (C 1 + C 2 V n ) V n -2γ n+1 ∇G (θ n ) 2 V n (4)
Remark that thanks to Assumption (A3),

∇G (θ n ) 2 ≤ 2L ∇G (G (θ n ) -G(θ))
Then, one can rewrite inequality (4) as

E V 2 n+1 |F n ≤ 1 + C 2 (4L ∇G + 1) γ 2 n+1 + 1 2 γ 4 n+1 L 2 ∇G C ′ 2 V 2 n + C 1 (4L ∇G + 1) γ 2 n+1 V n -2γ n+1 ∇G (θ n ) 2 V n + 1 2 γ 4 n+1 L 2 ∇G C ′ 1 . (5)
Let us now give a lower bound of ∇G (θ n ) 2 . Thanks to a Taylor's decomposition of the gradient,

∇G (θ n ) 2 ≥ 1 0 λ min ∇ 2 G (θ + t (θ n -θ)) dt 2 θ n -θ 2 Let us denote η n := 2 L ∇G G(θ n )-G(θ)
θ n -θ 2 min {1, r λ 0 }. Thanks to inequality (2), η n ≤ min {1, r λ 0 }, so that, with the help of Assumption (A4), it comes

∇G (θ n ) 2 ≥ η n 0 λ min ∇ 2 G (θ + t (θ n -θ)) dt 2 θ n -θ 2 ≥ 2λ 2 0 L ∇G min 1, r 2 λ 0 V n (6)
and one can rewrite inequality (5) as

E V 2 n+1 |F n ≤ 1 - 4λ 2 0 L ∇G min 1, r 2 λ 0 γ n+1 + C 2 (4L ∇G + 1) γ 2 n+1 + L 2 ∇G C ′ 2 2 γ 4 n+1 V 2 n + C 1 (4L ∇G + 1) γ 2 n+1 V n + 1 2 γ 4 n+1 L 2 ∇G C ′ 1 (7)
Finally, since

γ 2 n+1 C 1 (4L ∇G + 1) V n ≤ 3λ 2 0 L ∇G min 1, r 2 λ 0 γ n+1 V 2 n + γ 3 n+1 C 2 1 (4L ∇G + 1) 2 L ∇G 12λ 2 0 min 1, r 2 λ 0
, one can rewrite inequality (7) as

E V 2 n+1 |F n ≤ 1 -γ n+1 λ 2 0 L ∇G min 1, r 2 λ 0 + C 2 (4L ∇G + 1) γ 2 n+1 + L 2 ∇G C ′ 2 2 γ 4 n+1 V 2 n + γ 3 n+1 C 2 1 (4L ∇G + 1) 2 L ∇G 12λ 2 0 min 1, r 2 λ 0 + 1 2 γ 4 n+1 L 2 ∇G C ′ 1 (8)
Let us denote a 0 =

λ 2 0 min 1,r 2 λ 0 L ∇G , a 1 = max λ 4 0 4L 2 ∇G , C 2 (4L ∇G + 1) , a 2 = 1 2 L 2 ∇G C ′ 2 , σ 2 = C 2 1 (4L ∇G +1) 2 L ∇G 12λ 2 0 min 1,r 2 λ 0 + c γ L 2 ∇G C ′ 1 2
, and u n = E V 2 n , one can rewrite inequality (8) as

u n+1 ≤ 1 -a 0 γ n+1 + a 1 γ 2 n+1 + a 2 γ 3 n+1 u n + σ 2 γ 3 n+1 Let n 0 = inf n, a 0 ≥ 2a 1 γ n+1 + 2a 2 γ 2 n+1 .
Then, one can rewrite inequality (8) as

u n+1 = 1 + a 1 γ 2 n+1 + a 2 γ 3 n+1 u n + σ 2 γ 3 n+1 if n < n 0 1 -1 2 a 0 γ n+1 u n + σ 2 γ 3 n+1 if n ≥ n 0 Remark that if n ≥ n 0 , by definition of a 1 , 1 2 a 0 γ n+1 ≤ λ 4 0 4a 1 L 2 ∇G ≤ 1. (9)
We now consider two distinct cases: n ≤ n 0 and n > n 0 .

Case where n ≤ n 0 : With the help of an induction, one can check that for all n ≤ n 0 ,

u n ≤ n ∏ i=1 1 + a 1 γ 2 i + a 2 γ 3 i u 0 =:U 1,n + n ∑ k=1 n ∏ i=k+1 1 + a 1 γ 2 i + a 2 γ 3 i σ 2 γ 3 n =:U 2,n
As in Bach and Moulines (2013), remark that by definition of n 0 and since 1 + x ≤ e x , for all n ≤ n 0 ,

U 1,n ≤ u 0 exp n ∑ k=1 a 1 γ 2 k + a 2 γ 3 k ≤ u 0 exp - 1 2 a 0 n ∑ k=1 γ k exp 2 n ∑ k=1 a 1 γ 2 k + a 2 γ 3 k (10)
In a same way, one can check that for all n ≤ n 0 ,

U 2,n ≤ n ∏ k=1 1 + a 1 γ 2 k + a 2 γ 3 k n ∑ k=1 σ 2 γ 3 k ≤ exp n ∑ k=1 a 1 γ 2 k + a 2 γ 2 k n ∑ k=1 σ 2 γ 3 k ≤ exp - 1 2 a 0 n ∑ k=1 γ k exp 2 n ∑ k=1 a 1 γ 2 k + a 2 γ 3 k n ∑ k=1 σ 2 γ 3 k (11)
Case where n > n 0 : With the help of an induction, one can check that for all n > n 0 ,

u n ≤ n ∏ i=n 0 +1 1 - 1 2 a 0 γ i u n 0 =:U 3,n + n ∑ k=n 0 +1 n ∏ i=k+1 1 - 1 2 a 0 γ i σ 2 γ 3 k =:U 4,n
Furthermore, since

u n 0 ≤ U 1,n 0 + U 2,n 0 ≤ exp - 1 2 n 0 ∑ k=1 γ k exp 2 n 0 ∑ k=1 a 1 γ 2 k + a 2 γ 3 k u 0 + σ 2 n 0 ∑ k=1 γ 3 k one can obtain U 3,n ≤ exp - 1 2 a 0 n ∑ k=1 γ k exp 2 n ∑ k=1 a 1 γ 2 k + a 2 γ 3 k u 0 + σ 2 n 0 ∑ k=1 γ 3 k (12)
Let us now bound U 4,n and differentiate two cases: n 0 < ⌈n/2⌉ -1 and n 0 ≥ ⌈n/2⌉ -1.

Case where n > n 0 ≥ ⌈n/2⌉ -1: Since γ k is decreasing,

U 4,n ≤ σ 2 γ 2 n 0 +1 n ∑ k=n 0 +1 n ∏ i=k+1 1 - 1 2 a 0 γ i γ k = 2σ 2 a 0 γ 2 n 0 +1 n ∑ k=n 0 +1 n ∏ i=k+1 1 - 1 2 a 0 γ i - n ∏ i=k 1 - 1 2 a 0 γ i ≤ 2σ 2 a 0 γ 2 n 0 +1 1 - n ∏ i=n 0 +1 1 - 1 2 a 0 γ i ( 13
)
and thanks to inequality (9) and since γ k is decreasing,

U 4,n ≤ 2σ 2 a 0 γ 2 n 0 +1 ≤ 2σ 2 a 0 γ 2 ⌈n/2⌉
Case where n 0 < ⌈n/2⌉ -1: As in Bach and Moulines (2013), for all m = n 0 + 1, . . . , n, one has

U 4,n ≤ exp - 1 2 a 0 n ∑ k=m+1 γ k m ∑ k=n 0 +1 σ 2 γ 3 k + 2σ 2 a 0 γ 2 m .
Taking m = ⌈n/2⌉ -1, leads to

U 4,n ≤ exp - 1 2 a 0 n ∑ k=⌈n/2⌉ γ k ⌈n/2⌉ ∑ k=n 0 +1 σ 2 γ 3 k + 2σ 2 a 0 γ 2 ⌈n/2⌉-1 .
Final bound of U 4,n : Since γ k is decreasing,

U 4,n ≤ exp - 1 2 a 0 n ∑ k=⌈n/2⌉ γ k ⌈n/2⌉ ∑ k=n 0 +1 σ 2 γ 3 k + 2σ 2 a 0 γ 2 ⌈n/2⌉-1 . ( 14
)
Lower bound of ∑ n k=1 γ k : Remark that since γ k is decreasing, for all n ≥ 1,

n ∑ k=1 γ k ≥ n ∑ k=⌈n/2⌉ γ k ≥ n 2 γ n = c γ 2 n 1-α .

Conclusion:

Thanks to inequalities (10) to ( 14), it comes

u n ≤ exp - 1 2 a 0 n ∑ k=⌈n/2⌉ γ k exp 2 n ∑ k=1 a 1 γ 2 k + a 2 γ 3 k u 0 + n ∑ k=1 σ 2 γ 3 k + 2σ 2 a 0 γ ′ n (15) with γ ′ n =        γ 2 ⌈n/2⌉-1 if ⌈n/2⌉ > n 0 + 1 γ 2 ⌈n/2⌉ if ⌈n/2⌉ ≤ n 0 + 1 and n ≥ n 0 + 1 0 else
Then, using integral tests for convergence,

u n ≤ exp - 1 4 c γ a 0 n 1-α exp 2a 1 c 2 γ 2α 2α -1 + 2a 2 c 3 γ 3α 3α -1 u 0 + σ 2 c 3 γ 3α 3α -1 + 2 1+4α σ 2 c 2 γ a 0 n -2α =:v n (16)

Proof of Theorem 3.1

We have, since θ n is F n -measurable,

E θ n+1 -θ 2 |F n = θ n -θ 2 -2γ n+1 θ n -θ, ∇G (θ n ) + γ 2 n+1 E ∇ h g (X n+1 , θ n ) 2 |F n .
Then, linearizing the gradient, we obtain

E θ n+1 -θ 2 |F n = θ n -θ 2 -2γ n+1 θ n -θ, H (θ n -θ) + 2γ n+1 θ n -θ, δ n + γ 2 n+1 E ∇ h g (X n+1 , θ n ) 2 |F n .
with δ n = H (θ nθ) -∇G (θ n ). Thanks to Assumption (A1) and (A2) as well as Cauchy- Schwarz inequality,

E θ n+1 -θ 2 |F n ≤ (1 -γ n+1 λ min ) θ n -θ 2 + γ 2 n+1 C 1 + γ n+1 λ min δ n 2 + γ 2 n+1 C 2 (G (θ n ) -G(θ))
leading, thanks to inequality (2), to

E θ n+1 -θ 2 ≤ 1 -γ n+1 λ min + 1 2 γ 2 n+1 C 2 L ∇G E θ n -θ 2 + γ 2 n+1 C 1 + γ n+1 λ min E δ n 2 (17)
Remark that in order to have a usual induction relation on the quadratic mean error, we need to have a rate of convergence of E δ n 2 . Here is the main difference with Godichon-Baggioni (2019a): remarking that thanks to assumption (A3), δ n ≤ L ∇G θ nθ , with the help of (A4), it comes

δ n = δ n 1 θ n -θ ≤r λ 0 + δ n 1 θ n -θ >r λ 0 ≤ C λ 0 θ n -θ 2 1 θ n -θ ≤r λ 0 + L ∇G θ n -θ 1 θ n -θ >r λ 0
Then, thanks to inequality (3), it comes

δ n ≤ 2C λ 0 λ 0 (G (θ n ) -G(θ)) 1 θ n -θ ≤r λ 0 + 2L ∇G λ 0 r λ 0 (G (θ n ) -G(θ)) 1 θ n -θ >r λ 0 ≤ L δ (G (θ n ) -G(θ)) (18) with L δ = max 2C λ 0 λ 0 , 2L ∇G λ 0 r λ 0
. Then, one can rewrite inequality ( 17) as

E θ n+1 -θ 2 ≤ 1 -γ n+1 λ min + 1 2 γ 2 n+1 C 2 L ∇G E θ n -θ 2 + γ 2 n+1 C 1 + γ n+1 λ min L 2 δ v n ( 19
)
with v n defined in equation ( 16). Let us denote b 1 = L ∇G 2 max C 2 , λ 2 min 2L ∇G , and let n 1 = inf {n, λ min ≥ 2γ n+1 b 1 }. Then, denoting w n = E θ nθ 2 , one can rewrite inequality (19) as

w n+1 ≤ 1 + b 1 γ 2 n+1 w n + C 1 γ 2 n+1 + γ n+1 λ min L 2 δ v n if n < n 1 1 -1 2 λ min γ n+1 w n + C 1 γ 2 n+1 + γ n+1 λ min L 2 δ v n if n ≥ n 1 Furthermore, by definition of b 1 , remark that for all n ≥ n 1 , 1 2 λ min γ n+1 ≤ λ 2 min 4b 1 ≤ 1. ( 20
)
Case where n ≤ n 1 : With the help of an induction, one can check that for all n ≤ n 1 ,

w n ≤ n ∏ i=1 1 + γ 2 i b 1 =:A 1,n w 0 + n ∑ k=1 n ∏ i=k+1 1 + b 1 γ 2 i C 1 γ k + L 2 δ λ min γ k v k-1 =:B 1,n
Remark that by definition of n 1 and since 1

+ x ≤ e x , A 1,n ≤ exp n ∑ k=1 b 1 γ 2 k ≤ exp - 1 2 λ min n ∑ k=1 γ k exp 2b 1 n ∑ k=1 γ 2 k
Furthermore, by definition of n 1 , one can check that

B 1,n ≤ n ∏ k=1 1 + b 1 γ 2 k n ∑ k=1 C 1 γ 2 k + L 2 δ λ min γ k v k-1 ≤ exp b 1 n ∑ k=1 γ 2 k n ∑ k=1 C 1 γ 2 k + L 2 δ λ min γ k v k-1 ≤ exp - 1 2 λ min n ∑ k=1 γ k exp 2b 1 n ∑ k=1 γ 2 k n ∑ k=1 C 1 γ 2 k + L 2 δ λ min γ k v k-1
Then, if n ≤ n 1 , one have

w n ≤ exp - 1 2 λ min n ∑ k=1 γ k exp 2b 1 n ∑ k=1 γ 2 k w 0 + n ∑ k=1 C 1 γ 2 k + L 2 δ λ min γ k v k-1 (21)
Case where n > n 1 : With the help of an induction, one can check that for all n > n 1 ,

w n = n ∏ i=n 1 +1 1 - 1 2 λ min γ i w n 1 =:A 2,n + n ∑ k=n 1 +1 n ∏ i=k+1 1 - 1 2 λ min γ i γ 2 k C 1 + L 2 δ λ min γ k v k-1 =:B 2,n
Thanks to inequality ( 20), one has

∏ n i=n 1 +1 1 -1 2 λ min γ i ≤ exp -1 2 λ min ∑ n i=n 1 +1 γ i ,

and with the help of inequality (21), it comes

A 2,n ≤ exp - 1 2 λ min n ∑ k=1 γ k exp 2b 1 n 1 ∑ k=1 γ 2 k w 0 + n 1 ∑ k=1 γ 2 k C 1 + L 2 δ λ min γ k v k-1
Let us now bound B 2,n and differentiate two cases: ⌈n/2⌉ -1 > n 1 and ⌈n/2⌉ -1 ≤ n 1 .

Case where n > n 1 ≥ ⌈n/2⌉ -1: Since γ k and v k are decreasing, and since

B 2,n ≤ γ n 1 +1 C 1 + L 2 δ λ min v n 1 n ∑ k=n 1 +1 n ∏ i=k+1 1 - 1 2 λ min γ i γ k = γ n 1 +1 C 1 + L 2 δ λ min v n 1 2 λ min n ∑ k=n 1 +1 n ∏ i=k+1 1 - 1 2 λ min γ i - n ∏ i=k 1 - 1 2 λ min γ i
With the help of inequality (20) and since γ k and v k are decreasing,

B 2,n ≤ γ n 1 +1 C 1 + L 2 δ λ min v n 1 2 λ min 1 - n ∏ i=n 1 +1 1 - 1 2 λ min γ i ≤ γ ⌈n/2⌉ C 1 + L 2 δ λ min v ⌈n/2⌉-1 2 λ min
Case where n 1 < ⌈n/2⌉ -1: As in Bach and Moulines (2013), since γ k and v k are decreasing, one can check that for all m

= n 1 + 1, . . . , n B 2,n ≤ exp - 1 2 λ min n ∑ k=m+1 γ k m ∑ k=n 1 +1 γ 2 k C 1 + L 2 δ λ min γ k v k-1 + γ m 2C 1 λ min + 2L 2 δ λ 2 min v m-1
Taking m = ⌈n/2⌉ -1, it comes by definition of n 1 ,

B 2,n ≤ exp - 1 2 λ min n ∑ k=⌈n/2⌉ γ k ⌈n/2⌉ ∑ k=n 1 +1 γ 2 k C 1 + L 2 δ λ min γ k v k-1 + γ ⌈n/2⌉-1 2C 1 λ min + 2L 2 δ λ 2 min v ⌈n/2⌉-2 Final bound of B 2,n : For all n ≥ n 1 , B 2,n ≤ exp - 1 2 λ min n ∑ k=⌈n/2⌉ γ k ⌈n/2⌉ ∑ k=n 1 +1 γ 2 k C 1 + L 2 δ λ min γ k v k-1 + r n with r n =          γ ⌈n/2⌉-1 2C 1 λ min + 2L 2 δ λ 2 min v ⌈n/2⌉-2 if n 1 < ⌈n/2⌉ -1 γ ⌈n/2⌉ 2C 1 λ min + 2L 2 δ λ 2 min v ⌈n/2⌉-1 if ⌈n/2⌉ -1 ≤ n 1 and n > n 1 0 else Final bound of w n : Let us recall that ∑ n k=1 γ k ≥ ∑ n k=⌈n/2⌉ γ k ≥ n 2 γ n = c γ
2 n 1-α , so that, with the help of integral tests for convergence,

w n ≤ exp - 1 4 λ min c γ n 1-α exp 2b 1 c 2 γ 2α 2α -1 w 0 + c 2 γ C 1 2α 2α -1 + 2 L 2 δ λ min n ∑ k=1 γ k v k-1 + r n
Let us recall that for all n ≥ 1,

v n ≤ exp - 1 4 a 0 c γ n 1-α exp 2a 1 c 2 γ 2α 2α -1 + 2a 2 c 3 γ 3α 3α -1 v 0 + σ 2 c 3 γ 3α 3α -1 =:c 1 + 2 1+4α σ 2 c 2 γ a 0 n -2α
With the help of integral tests for convergence,

n ∑ k=1 γ k v k-1 ≤ u 0 c γ + c 1 + c 1 n 1 c γ t -α exp - 1 4 a 0 c γ t 1-α dt + 2 1+4α σ 2 c 3 γ a 0 3α 3α -1 ≤ u 0 c γ + c 1 - 4c 1 a 0 (1 -α) exp - 1 4 a 0 c γ t 1-α n 1 + 2 1+4α σ 2 c 3 γ a 0 3α 3α -1 ≤ u 0 c γ + c 1 + 4c 1 a 0 (1 -α) exp - 1 4 a 0 c γ + 2 1+4α σ 2 c 3 γ a 0 3α 3α -1
Finally, thanks to inequality (15)

r n ≤ c 1 exp - 1 8 a 0 c γ n 1-α + 2 1+8α σ 2 c 2 γ a 0 n -2α 2L 2 δ λ 2 min + 2 1+α C 1 λ min c γ n -α it comes w n ≤ e -1 4 λ min c γ n 1-α e 2b 1 c 2 γ 2α 2α-1 w 0 + c 2 γ C 1 2α 2α -1 + 2L 2 δ λ min u 0 c γ + c 1 + 4c 1 a 0 (1 -α) e -1 4 a 0 c γ + 2 1+4α σ 2 c 2 γ a 0 3α 3α -1 + c 1 exp - 1 8 a 0 c γ n 1-α + 2 1+8α σ 2 c 2 γ a 0 n -2α 2L 2 δ λ 2 min + 2 1+α C 1 λ min c γ n -α i.e E θ n -θ 2 ≤ Ae -1 4 λ min c γ n 1-α + c 1 e -1 8 a 0 c γ n 1-α + 2 1+8α σ 2 c 2 γ a 0 n -2α 2L 2 δ λ 2 min + 2 1+α C 1 λ min c γ n -α with A = e 2b 1 c 2 γ 2α 2α-1 w 0 + 2αc 2 γ C 1 2α -1 + 2 L 2 δ λ min u 0 c γ + c 1 + 4c 1 a 0 (1 -α) e -1 4 a 0 c γ + 2 1+4α σ 2 c 3 γ a 0 3α 3α -1 5.4 Proof of Lemma 3.2 If C 2 = C ′ 2 = 0, one can rewrite inequality (8) as u n+1 ≤ (1 -a 0 γ n+1 ) u n + σ 2 γ 3 n+1 with u n = E V 2 n , a 0 = λ 2 0 min 1,r 2 λ 0 L ∇G
, and

σ 2 = C 2 1 (4L ∇G +1) 2 L ∇G 12λ 2 0 min 1,r 2 λ 0 + c γ L 2 ∇G C ′ 1 2 . Let n ′ 0 = inf {n, a 0 γ n+1 ≤ 1}.
One can rewrite previous inequality as

u n+1 ≤ σ 2 γ 3 n+1 if n < n ′ 0 (1 -a 0 γ n+1 ) u n + σ 2 γ 3 n+1 if n ≥ n ′ 0 .
Then, we just have to study the case where n > n ′ 0 . With the help of an induction, one has

u n ≤ n ∏ i=n ′ 0 +1 (1 -a 0 γ i ) u n 0 =:U ′ 3,n + n ∑ k=n ′ 0 +1 n ∏ i=k+1 (1 -a 0 γ i ) σ 2 γ 3 k =:U ′ 4,n
We now bound each term on the right-hand side of previous inequality.

Bounding U ′ 3,n : By definition of n ′ 0 , and since 1

+ x ≤ e x , U ′ 3,n ≤ exp   -a 0 n ∑ k=n ′ 0 +1 γ k   σ 2 γ 3 n ′ 0
With the help of an integral test for convergence,

U ′ 3,n ≤ exp -a 0 c γ n n ′ 0 +1 t -α dt σ 2 γ 3 n ′ 0 = exp -a 0 c γ 1 1 -α n + 1) 1-α -n ′ 0 + 1 1-α σ 2 γ 3 n ′ 0 ≤ exp - 1 2 a 0 c γ n + 1) 1-α -n ′ 0 + 1 1-α σ 2 γ 3 n ′ 0 ( 22
)
Bounding U ′ 4,n : As in the proof of Lemma 3.1, we will consider two cases:

n ′ 0 < ⌈n/2⌉ -1 and n ′ 0 ≥ ⌈n/2⌉ -1.
Case where n ′ 0 ≥ ⌈n/2⌉ -1: With calculus analogous to (13), one can obtain

U ′ 4,n ≤ σ 2 a 0 γ 2 ⌈n/2⌉ . ( 23
)
Case where n ′ 0 < ⌈n/2⌉ -1: As in [START_REF] Bach | Non-strongly-convex smooth stochastic approximation with convergence rate o (1/n)[END_REF], for all m = n ′ 0 + 1, . . . , n,

U ′ 4,n ≤ exp -a 0 n ∑ k=m+1 γ k m ∑ k=n 0 +1 σ 2 γ 3 k + σ 2 a 0 γ 2 m .
Taking m = ⌈n/2⌉ -1 and with the help of an integral test for convergence, it comes

U ′ 4,n ≤ exp -a 0 n ∑ k=⌈n/2⌉ γ k ⌈n/2⌉-1 ∑ k=n 0 +1 σ 2 γ 3 k + σ 2 a 0 γ 2 ⌈n/2⌉-1 ≤ exp - 1 2 a 0 c γ n 1-α σ 2 c 3 γ 3α 3α -1 + σ 2 a 0 γ 2 ⌈n/2⌉-1 (24)
Bounding u n : Thanks to inequalities ( 22),( 23) and ( 24), we have

u n ≤ exp - 1 2 a 0 c γ n 1-α σ 2 max exp 1 2 a 0 c γ n ′ 0 + 1 1-α γ 3 n ′ 0 , c 3 γ 3α 3α -1 + r ′ n with r ′ n =        σ 2 γ 3 n if n ≤ n ′ 0 σ 2 a 0 γ 2 ⌈n/2⌉ if n > n ′ 0 ≥ ⌈n/2⌉ -1 σ 2 a 0 γ 2 ⌈n/2⌉-1
else which can be also writen as

u n ≤        σ 2 γ 3 n if n ≤ n ′ 0 e -1 2 a 0 c γ n 1-α e 1 2 a 0 c γ (n ′ 0 +1) 1-α σ 2 γ 3 n ′ 0 + σ 2 a 0 γ ⌈n/2⌉ if n > n ′ 0 ≥ ⌈n/2⌉ -1 e -1 2 a 0 c γ n 1-α σ 2 c 3 γ 3α 3α-1 + σ 2 a 0 γ 2 ⌈n/2⌉-1 else or as u n ≤ exp - 1 2 a 0 c γ n 1-α σ 2 exp 1 2 a 0 c γ n ′ 0 + 1 1-α γ 3 n ′ 0 + c 3 γ 3α 3α -1 + σ 2 M 0 c 2 γ n -2α =:v ′ n ( 25
)
with M 0 = max 2 4α a 0 , c γ .

Proof of Theorem 3.2

If C 2 = 0, by definition of v ′ n (see equation ( 25)), one can rewrite inequality ( 19) as

E θ n+1 -θ 2 ≤ (1 -γ n+1 λ min ) E θ n -θ 2 + γ 2 n+1 C 1 + γ n+1 λ min L 2 δ v ′ n . ( 26
)
Let us denote n ′ 1 = min {n, λ min γ n+1 ≥ 1}. One can rewrite inequality (26) as

w n+1 ≤ γ 2 n+1 C 1 + γ n+1 λ min L 2 δ v ′ n if n < n ′ 1 (1 -γ n+1 λ min ) w n + γ 2 n+1 C 1 + γ n+1 λ min L 2 δ v ′ n if n ≥ n 1 with E θ n -θ 2 .
We now focus on the case where n > n 1 . First, remark that with the help of an induction, one can obtain

w n ≤ n ∏ i=n ′ 1 +1 (1 -λ min γ i ) w n ′ 1 =:A ′ 1,n + n ∑ k=n ′ 1 +1 n ∏ i=k+1 (1 -λ min γ i ) γ 2 k C 1 + γ k λ min L 2 δ v ′ k-1 =:A ′ 2,n
and we now bound each term on the right-hand side of previous inequality.

Bounding A ′ 1,n : By definition of n ′ 1 and with the help of an integral test for convergence, one can check that

A ′ 1,n ≤ exp -λ min c γ (n + 1) 1-α -n ′ 1 + 1 1-α γ 2 n ′ 1 C 1 + γ n ′ 1 λ min L 2 δ v ′ n ′ 1 -1 (27) Bounding A ′ 2,n : As we did in previous calculus, since γ k and v ′ k are decreasing, one can check that if n ′ 1 ≥ ⌈n/2⌉ -1, A ′ 2,n ≤ C 1 λ min γ ⌈n/2⌉ + L 2 δ λ 2 min v ′ ⌈n/2⌉-1 and if n ′ 1 < ⌈n/2⌉ -1, A ′ 2,n ≤ exp -λ min n ∑ k=⌈n/2⌉ γ k C 1 c 2 γ 2α 2α -1 + L 2 δ λ min n ∑ k=1 γ k v ′ k-1 + C 1 λ min γ ⌈n/2⌉-1 + L 2 δ λ 2 min v ′ ⌈n/2⌉-2
Then,

A ′ 2,n ≤ exp -λ min n ∑ k=⌈n/2⌉ γ k C 1 c 2 γ 2α 2α -1 + L 2 δ λ min n ∑ k=1 γ k v ′ k-1 + r ′′ n (28) with r ′′ n =          C 1 λ min γ ⌈n/2⌉-1 + L 2 δ λ 2 min v ′ ⌈n/2⌉-2 if n 1 ′ < ⌈n/2⌉ -1 C 1 λ min γ ⌈n/2⌉ + L 2 δ λ 2 min v ′ ⌈n/2⌉-1 if ⌈n/2⌉ -1 ≤ n 1 and n > n 1 0 else Let us denote c n ′ 0 := σ 2 exp 1 2 a 0 c γ (n ′ 0 + 1) 1-α γ 3 n ′ 0 + c 3 γ 3α 3α-1 , i.e one can bound v ′ n as (with v ′ n defined in (25)) v ′ n ≤ c n ′ 0 exp - 1 2 a 0 c γ n 1-α + σ 2 M 0 c 2 γ n -2α
Then, with the help of an integral test for convergence, one can check that

n ∑ k=1 γ k v ′ k-1 ≤ c n ′ 0 + c γ u 0 + 2c n ′ 0 a 0 (1 -α) exp - 1 2 a 0 c γ + σ 2 c 3 γ M 0 3α 3α -1 Furthermore, one can check that r ′′ n ≤ c n ′ 0 exp - 1 4 a 0 c γ n 1-α + σ 2 c 2 γ M 0 n -2α L 2 δ λ 2 min + 2 α C 1 λ min c γ n -α . ( 29
)
Final bound of E θ nθ 2 : As a conclusion, thanks to inequalities ( 27), ( 28) and ( 29),

E θ n -θ 2 ≤ A ′ e -λ min c γ n 1-α + c n ′ 0 e -1 4 a 0 c γ n 1-α + σ 2 c 2 γ M 0 n -2α L 2 δ λ 2 min + 2 α C 1 c γ λ min n -α with A ′ = e λ min c γ (n ′ 1 +1) 1-α C 1 c 2 γ 2α 2α -1 + c n ′ 0 + c γ u 0 + 2c n ′ 0 a 0 (1 -α) e -1 2 a 0 c γ + σ 2 c 3 γ M 0 3α 3α -1 .

Proofs of Section 4

In order to prove theorems of Section 4, let us first give some usual decompositions of the estimates. First, remark that one can rewrite θ n+1 as

θ n+1 -θ = θ n -θ -γ n+1 ∇G (θ n ) + γ n+1 ξ n+1 ( 30
)
where ξ n+1 := ∇G (θ n ) -∇ h g (X n+1 , θ) is a martingale difference adapted to F n . Furthermore, denoting H = ∇ 2 G(θ) and linearizing the gradient, one has

θ n+1 -θ = (I d -γ n+1 H) (θ n -θ) + γ n+1 ξ n+1 -γ n+1 δ n (31)
where δ n := ∇G (θ n ) -H (θ nθ) is the remainder term in the Taylor's expansion of the gradient. This inequality can be rewrite as

H (θ n -θ) = θ n -θ n+1 γ n+1 + ξ n+1 -δ n .
Summing these equalities, dividing by n + 1 and applying an Abel's transform (see [START_REF] Pelletier | Asymptotic almost sure efficiency of averaged stochastic algorithms[END_REF] for more details), it comes

H θ n -θ = θ 0 -θ γ 1 (n + 1) - θ n+1 -θ γ n+1 (n + 1) + 1 n + 1 n ∑ k=1 (θ k -θ) 1 γ k+1 - 1 γ k + 1 n + 1 n ∑ k=0 ξ k+1 - 1 n + 1 n ∑ k=0 δ k (32)

Proof of Theorem 4.1

In order to prove Theorem 4.1, let us bound each term on the right hand-side of equality (32).

Bounding E θ n+1 -θ γ n+1 (n+1) 2 : Thanks to Theorem 3.1, one has E θ n+1 -θ γ n+1 (n + 1) 2 ≤ √ Ae -1 8 λ min c γ n 1-α c γ (n + 1) 1-α + √ 2 √ c 1 L δ λ min c γ (n + 1) 1-α exp - 1 16 a 0 c γ n 1-α + 2 1+4α σ √ a 0 L δ λ min (n + 1) + 2 1+α 2 √ C 1 √ λ min 1 √ c γ (n + 1) 1-α/2 (33) Bounding R n := 1 n+1 E ∑ n k=1 (θ k -θ) 1 γ k+1 -1 γ k 2 . First remark that 1 γ k+1 -1 γ k ≤ αc -1 γ k α-1 ≤ c -1 γ k α-1 , so that, thanks to Minkowski's inequality, R n ≤ 1 n + 1 n ∑ k=1 E θ k -θ 2 1 γ k+1 - 1 γ k ≤ αc -1 γ n + 1 n ∑ k=1 E θ k -θ 2 k α-1 Denoting A ∞ := √ A c γ +∞ ∑ n=0 e -1 8 λ min c γ n 1-α and D ∞ := √ 2 √ c 1 L δ λ min c γ +∞ ∑ n=0 e -1 16 a 0 c γ n 1-α it comes R n ≤ A ∞ + D ∞ n + 1 + 2 1+4α σL δ √ a 0 λ min 1 n + 1 n ∑ k=1 k -1 + 2 1+α 2 √ C 1 √ c γ √ λ min α n + 1 n ∑ k=1 k α/2-1 ≤ A ∞ + D ∞ n + 1 + 2 1+4α σL δ √ a 0 λ min ln(n + 1) n + 1 + 2 3+α 2 √ C 1 √ c γ √ λ min 1 (n + 1) 1-α/2 (34) Bounding R ′ n = 1 n+1 E ∑ n k=0 δ k 2 .
First remark that thanks to Minkowski's inequality coupled with inequality (18), one has

R ′ n ≤ 1 n + 1 n ∑ k=0 E δ n 2 ≤ L δ √ u 0 n + 1 + L δ n + 1 n ∑ k=1 E (G (θ n ) -G(θ)) 2
Then, applying Lemma 3.1 and denoting

B ∞ := +∞ ∑ n=0 e -1 8 c γ a 0 n 1-α e a 1 c 2 γ 2α 2α-1 +a 2 c 3 γ 3α 3α-1 √ u 0 + σc 3/2 γ 3α 3α -1 , one has R ′ n ≤ ≤ L δ B∞ n+1 L δ √ u 0 n + 1 + L δ n + 1 n ∑ k=1 e -1 8 c γ a 0 k 1-α e a 1 c 2 γ 2α 2α-1 +a 2 c 3 γ 3α 3α-1 √ u 0 + σc 3/2 γ 3α 3α -1 + L δ 2 1/2+2α σc γ √ a 0 1 n + 1 n ∑ k=1 k -α ≤ L δ B ∞ n + 1 + L δ 2 1/2+2α σc γ √ a 0 (1 -α) 1 (n + 1) α (35) Bounding M n := 1 n+1 E ∑ n k=0 ξ k+1 2 .
Remark that by definition of ξ n+1 and thanks to Assumption (A1), one has

E ξ n+1 2 |F n = E ∇ h g (X n+1 , θ n ) 2 |F n -∇G (θ n ) 2 ≤ E ∇ h g (X n+1 , θ n ) 2 |F n ≤ C 1 + C 2 (G (θ n ) -G(θ))
Furthermore, since (ξ n+1 ) is a sequence of martingale differences adapted to the filtration (F n ) and applying Hölder inequality, one has

M n = 1 n + 1 n ∑ k=0 E ξ k+1 2 ≤ √ C 1 √ n + 1 + √ C 2 n + 1 √ u 0 + n ∑ k=1 E [(G (θ n ) -G(θ)) 2 ].
Thanks to Lemma 3.1, it comes

M n ≤ √ C 1 √ n + 1 + √ C 2 n + 1 ≤ √ B ∞ √ u 0 + n ∑ k=1 e -1 8 c γ a 0 n 1-α e a 1 c 2 γ 2α 2α-1 +a 2 c 3 γ 3α 3α-1 √ u 0 + σc 3/2 γ 3α 3α -1 + √ C 2 n + 1 n ∑ k=1 2 1/2+2α σc γ √ a 0 k -α
Finally, it comes

M n ≤ √ C 1 √ n + 1 + √ C 2 √ B ∞ n + 1 + √ C 2 2 1/4+α √ σ √ c γ a 1/4 0 √ 1 -α 1 (n + 1) 1/2+α/2
(36)

Conclusion: Thanks to inequalities (33) to ( 35), one has

λ min E θ n -θ 2 ≤ √ C 1 √ n + 1 + L δ 2 1/2+2α σc γ √ a 0 (1 -α) 1 (n + 1) α + 2 1+α 2 5 √ C 1 √ c γ √ λ min 1 (n + 1) 1-α/2 + √ C 2 2 1/4+α √ σ √ c γ a 1/4 0 √ 1 -α(n + 1) 1/2+α/2 + 2 1+4α σL δ √ a 0 λ min ln(n + 1) n + 1 + A ∞ + D ∞ + L δ B ∞ + √ C 2 √ B ∞ + c -1/2 γ √ v 0 n + 1

Proof of Theorem 4.2

In order to prove Theorem 4.2, we just have to give a better bound of the martingale term

1 n+1 ∑ n k=0 H -1 ξ k . First, let us recall that E   n ∑ k=0 H -1 ξ k+1 2   ≤ n ∑ k=0 E H -1 ∇ h g (X k+1 , θ k ) 2 ≤ n ∑ k=0 E Tr H -1 ∇ h g (X k+1 , θ k ) ∇ h g (X k+1 , θ k ) T H -1 = n ∑ k=0 E     Tr     H -1 E ∇ h g (X k+1 , θ k ) ∇ h g (X k+1 , θ k ) T |F k =Σ(θ k ) H -1        
Since the functional Σ(.) is L Σ -lipschitz and denoting Σ = Σ(θ), one has

E   n ∑ k=0 H -1 ξ k+1 2   = (n + 1)Tr H -1 ΣH -1 + n ∑ k=0 E Tr H -1 (Σ (θ k ) -Σ (θ)) H -1 ≤ (n + 1)Tr H -1 ΣH -1 + L Σ λ 2 min n ∑ k=0 E θ k -θ 2 (37)
Then, thanks to Theorem 3.1, it comes

E   n ∑ k=0 H -1 ξ k+1 2   ≤ Tr (H -1 ΣH -1 ) √ n + 1 + √ L Σ √ v 0 λ min + √ L Σ λ min A n ∑ k=1 e -1 4 λ min c γ k 1-α + √ 2 √ L Σ √ c 1 L δ λ 2 min n ∑ k=1 exp - 1 8 a 0 c γ k 1-α + 2 1+4α √ L Σ σc γ L δ √ a 0 λ 2 min n ∑ k=1 k -2α + 2 1/2+α/2 √ C 1 √ L Σ √ c γ λ 3/2 min n ∑ k=1 k -α
Then, thanks to Minkovski's inequality and by definition of A ∞ and D ∞ ,

1 n + 1 E   n ∑ k=0 H -1 ξ k+1 2   ≤ Tr (H -1 ΣH -1 ) √ n + 1 + √ L Σ √ v 0 λ min (n + 1) + √ L Σ c γ A ∞ λ min (n + 1) + √ L Σ c γ D ∞ λ min (n + 1) + 2 1+4α √ L Σ σc γ L δ √ 2α √ a 0 λ 2 min √ 2α -1(n + 1) + 2 1/2+α/2 √ C 1 √ L Σ √ c γ λ 3/2 min √ 1 -α(n + 1) 1/2+α/2 ,
which concludes the proof.

Proof of Theorem 4.3

In order to prove Theorem 4.3, let us bound each term on the right hand-side of equality (32).

Bounding E

θ n+1 -θ γ n+1 (n+1) 2 : Thanks to Theorem 3.2, one has

E θ n+1 -θ γ n+1 (n + 1) 2 ≤ √ A ′ e -1 2 λ min c γ n 1-α c γ (n + 1) 1-α + c n ′ 0 L δ c γ λ min (n + 1) 1-α exp - 1 8 a 0 c γ n 1-α + σL δ √ M 0 λ min (n + 1) + 2 α 2 √ C 1 √ λ min 1 √ c γ (n + 1) 1-α/2 Bounding R n := 1 n+1 E ∑ n k=1 (θ k -θ) 1 γ k+1 -1 γ k 2 . Recalling that R n ≤ c -1 γ n + 1 n ∑ k=1 E θ k -θ 2 k α-1 Denoting A ′ ∞ := √ A ′ c γ +∞ ∑ n=0 e -1 2 λ min c γ n 1-α and D ′ ∞ := c n ′ 0 L δ λ min c γ +∞ ∑ n=0 e -1 8 a 0 c γ n 1-α it comes R n ≤ A ′ ∞ + D ′ ∞ n + 1 + σL δ √ M 0 λ min (n + 1) n ∑ k=1 k -1 + 2 α 2 √ C 1 √ λ min √ c γ 1 n + 1 n ∑ k=1 k α/2-1 ≤ A ′ ∞ + D ′ ∞ n + 1 + σL δ √ M 0 λ min (n + 1) ln(n + 1) n + 1 + 2 1+ α 2 √ C 1 α √ λ min √ c γ 1 (n + 1) 1-α/2 Bounding R ′ n = 1 n+1 E ∑ n k=0 δ k 2 . Let us recall that R ′ n ≤ 1 n + 1 n ∑ k=0 E δ n 2 ≤ L δ √ u 0 n + 1 + L δ n + 1 n ∑ k=1 E (G (θ n ) -G(θ)) 2 .
Furthermore, denoting

B ′ ∞ = c n ′ 0 + √ u 0 ∑ n≥0 exp - 1 4 a 0 c γ n 1-α
and with the help of Lemma 3.2, one has

R ′ n ≤ ≤ L δ B ′ ∞ n+1 L δ √ u 0 n + 1 + L δ c n ′ 0 n + 1 n ∑ k=1 exp - 1 4 a 0 c γ k 1-α +L δ σc γ M 0 1 n + 1 n ∑ k=1 k -α ≤ L δ B ′ ∞ n + 1 + L δ σc γ √ M 0 (1 -α)(n + 1) α Bounding M n : Recalling that M n ≤ √ C 1 √ n + 1 + √ C 2 n + 1 √ u 0 + n ∑ k=1 E [(G (θ n ) -G(θ)) 2 ].
and since C 2 = 0, one has

M n ≤ √ C 1 √ n + 1
which concludes the proof.

Proof of Theorem 4.4

In order to prove Theorem 4.4, we just have to give a better bound of the martingale term 1 n+1 ∑ n k=0 H -1 ξ k+1 . Thanks to inequality (37) couple with Theorem 3.2, it comes

E   n ∑ k=0 H -1 ξ k+1 2   ≤ Tr (H -1 ΣH -1 ) √ n + 1 + √ L Σ √ v 0 λ min + √ L Σ λ min A ′ n ∑ k=1 e -λ min c γ n 1-α + √ L Σ c n ′ 0 L δ λ 2 min n ∑ k=1 e -1 8 a 0 c γ n 1-α + √ L Σ L δ c γ λ 2 min M 0 n ∑ k=1 k -2α + √ L Σ 2 α 2 √ C 1 λ 3/2 min n ∑ k=1 k -α .
Then, by Minkowski's inequality, it comes

E   n ∑ k=0 H -1 ξ k+1 2   ≤ Tr (H -1 ΣH -1 ) √ n + 1 + √ L Σ √ v 0 λ min + √ L Σ λ min c γ A ′ ∞ + √ L Σ λ min c γ D ′ ∞ + √ L Σ L δ c γ λ 2 min M 0 2α 2α -1 + √ L Σ 2 α 2 √ C 1 λ 3/2 min 1 √ 1 -α (n + 1) 1-α 2 .

Acknowledgments

The author would like to thank Pierre Tarrago for the many fruitful discussions that enable to deeply improve this work.


Sébastien Bubeck
email: sebastien.bubeck@inria.fr

Rémi Munos
email: remi.munos@inria.fr

Gilles Stoltz
email: gilles.stoltz@ens.fr

Csaba Szepesvári
email: szepesva@cs.ualberta.ca

Online Optimization in X -Armed Bandits

We consider a generalization of stochastic bandit problems where the set of arms, X , is allowed to be a generic topological space. We constraint the mean-payoff function with a dissimilarity function over X in a way that is more general than Lipschitz. We construct an arm selection policy whose regret improves upon previous result for a large class of problems. In particular, our results imply that if X is the unit hypercube in a Euclidean space and the mean-payoff function has a finite number of global maxima around which the behavior of the function is locally Hölder with a known exponent, then the expected regret is bounded up to a logarithmic factor by √ n, i.e., the rate of the growth of the regret is independent of the dimension of the space. Moreover, we prove the minimax optimality of our algorithm for the class of mean-payoff functions we consider.

Introduction and motivation

Bandit problems arise in many settings, including clinical trials, scheduling, on-line parameter tuning of algorithms or optimization of controllers based on simulations. In the classical bandit problem there are a finite number of arms that the decision maker can select at discrete time steps. Selecting an arm results in a random reward, whose distribution is determined by the identity of the arm selected. The distributions associated with the arms are unknown to the decision maker whose goal is to maximize the expected sum of the rewards received.

In many practical situations the arms belong to a large set. This set could be continuous [1; 8; 4; 2; 9], hybrid-continuous, or it could be the space of infinite sequences over a finite alphabet [START_REF] Coquelin | Bandit algorithms for tree search[END_REF]. In this paper we consider stochastic bandit problems where the set of arms, X , is allowed to be an arbitrary topological space. We assume that the decision maker knows a dissimilarity function defined over this space that constraints the shape of the mean-payoff function. In particular, the dissimilarity function is assumed to put a lower bound on the mean-payoff function from below at each maxima. We also assume that the decision maker is able to cover the space of arms in a recursive manner, successively refining the regions in the covering such that the diameters of these sets shrink at a known geometric rate when measured with the dissimilarity.

Our work generalizes and improves previous works on continuum-armed bandit problems: Kleinberg [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF] and Auer et al. [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF] focussed on one-dimensional problems. Recently, Kleinberg et al. [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF] considered generic metric spaces assuming that the mean-payoff function is Lipschitz with respect to the (known) metric of the space. They proposed an interesting algorithm that achieves essentially the best possible regret in a minimax sense with respect to these environments.

The goal of this paper is to further these works in a number of ways: (i) we allow the set of arms to be a generic topological space; (ii) we propose a practical algorithm motivated by the recent very successful tree-based optimization algorithms [10; 7; 5] and show that the algorithm is (iii) able to exploit higher order smoothness. In particular, as we shall argue in Section 7, (i) improves upon the results of Auer et al. [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF], while (i), (ii) and (iii) improve upon the work of Kleinberg et al. [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF]. Compared to Kleinberg et al. [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF], our work represents an improvement in the fact that just like Auer et al. [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF] we make use of the local properties of the mean-payoff function around the maxima only, and not a global property, such as Lipschitzness in the whole space. This allows us to obtain a regret which scales as O( √ n)1 when e.g. the space is the unit hypercube and the mean-payoff function is locally Hölder with known exponent in the neighborhood of any maxima (which are in finite number) and bounded away from the maxima outside of these neighborhoods. Thus, we get the desirable property that the rate of growth of the regret is independent of the dimensionality of the input space. We also prove a minimax lower bound that matches our upper bound up to logarithmic factors, showing that the performance of our algorithm is essentially unimprovable in a minimax sense. Besides these theoretical advances the algorithm is anytime and easy to implement. Since it is based on ideas that have proved to be efficient, we expect it to perform well in practice and to make a significant impact on how on-line global optimization is performed.

Problem setup, notation

We consider a topological space X , whose elements will be referred to as arms. A decision maker "pulls" the arms in X one at a time at discrete time steps. Each pull results in a reward that depends on the arm chosen and which the decision maker learns of. The goal of the decision maker is to choose the arms so as to maximize the sum of the rewards that he receives. In this paper we are concerned with stochastic environments. Such an environment M associates to each arm x ∈ X a distribution M x on the real line. The support of these distributions is assumed to be uniformly bounded with a known bound. For the sake of simplicity, we assume this bound is 1. We denote by f (x) the expectation of M x , which is assumed to be measurable (all measurability concepts are with respect to the Borel-algebra over X ). The function f : X → R thus defined is called the mean-payoff function. When in round n the decision maker pulls arm X n ∈ X , he receives a reward Y n drawn from M Xn , independently of the past arm choices and rewards.

A pulling strategy of a decision maker is determined by a sequence ϕ = (ϕ n ) n≥1 of measurable mappings, where each ϕ n maps the history space H n = X × [0, 1] n-1 to the space of probability measures over X .

By convention, ϕ 1 does not take any argument. A strategy is deterministic if for every n the range of ϕ n contains only Dirac distributions.

According to the process that was already informally described, a pulling strategy ϕ and an environment M jointly determine a random process (X 1 , Y 1 , X 2 , Y 2 , . . .) in the following way: In round one, the decision maker draws an arm X 1 at random from ϕ 1 and gets a payoff Y 1 drawn from M X1 . In round n ≥ 2, first, X n is drawn at random according to ϕ n (X 1 , Y 1 , . . . , X n-1 , Y n-1 ), but otherwise independently of the past. Then the decision maker gets a rewards Y n drawn from M Xn , independently of all other random variables in the past given X n .

Let f * = sup x∈X f (x) be the maximal expected payoff. The cumulative regret of a pulling strategy in environment

M is R n = n f * - n t=1 Y t , and the cumulative pseudo-regret is R n = n f * - n t=1 f (X t ).
In the sequel, we restrict our attention to the expected regret E [R n ], which in fact equals E[ R n ], as can be seen by the application of the tower rule.

3 The Hierarchical Optimistic Optimization (HOO) strategy

Trees of coverings

We first introduce the notion of a tree of coverings. Our algorithm will require such a tree as an input.

Definition 1 (Tree of coverings). A tree of coverings is a family of measurable subsets (P h,i ) 1≤i≤2 h , h≥0 of X such that for all fixed integer h ≥ 0, the covering ∪ 1≤i≤2 h P h,i = X holds. Moreover, the elements of the covering are obtained recursively: each subset P h,i is covered by the two subsets P h+1,2i-1 and P h+1,2i .

A tree of coverings can be represented, as the name suggests, by a binary tree T . The whole domain X = P 0,1 corresponds to the root of the tree and P h,i corresponds to the i-th node of depth h, which will be referred to as node (h, i) in the sequel. The fact that each P h,i is covered by the two subsets P h+1,2i-1 and P h+1,2i corresponds to the childhood relationship in the tree. Although the definition allows the childregions of a node to cover a larger part of the space, typically the size of the regions shrinks as depth h increases (cf. Assumption 1).

Remark 1. Our algorithm will instantiate the nodes of the tree on an "as needed" basis, one by one. In fact, at any round n it will only need n nodes connected to the root.

Statement of the HOO strategy

The algorithm picks at each round a node in the infinite tree T as follows. In the first round, it chooses the root node (0, 1). Now, consider round n + 1 with n ≥ 1. Let us denote by T n the set of nodes that have been picked in previous rounds and by S n the nodes which are not in T n but whose parent is. The algorithm picks at round n + 1 a node (H n+1 , I n+1 ) ∈ S n according to the deterministic rule that will be described below. After selecting the node, the algorithm further chooses an arm X n+1 ∈ P Hn+1,In+1 . This selection can be stochastic or deterministic. We do not put any further restriction on it. The algorithm then gets a reward Y n+1 as described above and the procedure goes on: (H n+1 , I n+1 ) is added to T n to form T n+1 and the children of (H n+1 , I n+1 ) are added to S n to give rise to S n+1 . Let us now turn to how (H n+1 , I n+1 ) is selected.

Along with the nodes the algorithm stores what we call B-values. The node (H n+1 , I n+1 ) ∈ S n to expand at round n + 1 is picked by following a path from the root to a node in S n , where at each node along the path the child with the larger B-value is selected (ties are broken arbitrarily). In order to define a node's B-value, we need a few quantities. Let C(h, i) be the set that collects (h, i) and its descendants. We let

N h,i (n) = n t=1 I {(Ht,It)∈C(h,i)}
be the number of times the node (h, i) was visited. A given node (h, i) is always picked at most once, but since its descendants may be picked afterwards, subsequent paths in the tree can go through it. Consequently, 1 ≤ N h,i (n) ≤ n for all nodes (h, i) ∈ T n . Let µ h,i (n) be the empirical average of the rewards received for the time-points when the path followed by the algorithm went through (h, i):

µ h,i (n) = 1 N h,i (n) n t=1 Y t I {(Ht,It)∈C(h,i)} .
The corresponding upper confidence bound is by definition

U h,i (n) = µ h,i (n) + 2 ln n N h,i (n) + ν 1 ρ h ,
where 0 < ρ < 1 and ν 1 > 0 are parameters of the algorithm (to be chosen later by the decision maker, see Assumption 1). For nodes not in T n , by convention, U h,i (n) = +∞. Now, for a node (h, i) in S n , we define its B-value to be B h,i (n) = +∞. The B-values for nodes in T n are given by

B h,i (n) = min U h,i (n), max B h+1,2i-1 (n), B h+1,2i (n) .
Note that the algorithm is deterministic (apart, maybe, from the arbitrary random choice of X t in P Ht,It ). Its total space requirement is linear in n while total running time at round n is at most quadratic in n, though we conjecture that it is O(n log n) on average.

Assumptions made on the model and statement of the main result

We suppose that X is equipped with a dissimilarity ℓ, that is a non-negative mapping ℓ :

X 2 → R satisfying ℓ(x, x) = 0.
The diameter (with respect to ℓ) of a subset A of X is given by diam A = sup x,y∈A ℓ(x, y). Given the dissimilarity ℓ, the "open" ball with radius ε > 0 and center c ∈ X is B(c, ε) = { x ∈ X : ℓ(c, x) < ε } (we do not require the topology induced by ℓ to be related to the topology of X .) In what follows when we refer to an (open) ball, we refer to the ball defined with respect to ℓ. The dissimilarity will be used to capture the smoothness of the mean-payoff function. The decision maker chooses ℓ and the tree of coverings. The following assumption relates this choice to the parameters ρ and ν 1 of the algorithm: Assumption 1. There exist ρ < 1 and ν 1 , ν 2 > 0 such that for all integers h ≥ 0 and all i = 1, . . . , 2 h , the diameter of P h,i is bounded by ν 1 ρ h , and P h,i contains an open ball P ′ h,i of radius ν 2 ρ h . For a given h, the P ′ h,i are disjoint for 1 ≤ i ≤ 2 h . Remark 2. A typical choice for the coverings in a cubic domain is to let the domains be hyper-rectangles. They can be obtained, e.g., in a dyadic manner, by splitting at each step hyper-rectangles in the middle along their longest side, in an axis parallel manner; if all sides are equal, we split them along the first axis. In this example, if X = [0, 1] D and ℓ(x, y) = xy α then we can take ρ = 2 -α/D , ν 1 = ( √ D/2) α and ν 2 = 1/8 α .

The next assumption concerns the environment. Definition 2. We say that f is weakly Lipschitz with respect to ℓ if for all x, y ∈ X ,

f * -f (y) ≤ f * -f (x) + max f * -f (x), ℓ(x, y) . (1)
Note that weak Lipschitzness is satisfied whenever f is 1-Lipschitz, i.e., for all x, y ∈ X , one has |f (x)f (y)| ≤ ℓ(x, y). On the other hand, weak Lipschitzness implies local (one-sided) 1-Lipschitzness at any maxima. Indeed, at an optimal arm x * (i.e., such that f (x * ) = f * ), (1) rewrites to f (x * )f (y) ≤ ℓ(x * , y). However, weak Lipschitzness does not constraint the growth of the loss in the vicinity of other points. Further, weak Lipschitzness, unlike Lipschitzness, does not constraint the local decrease of the loss at any point. Thus, weak-Lipschitzness is a property that lies somewhere between a growth condition on the loss around optimal arms and (one-sided) Lipschitzness. Note that since weak Lipschitzness is defined with respect to a dissimilarity, it can actually capture higher-order smoothness at the optima. For example, f (x) = 1x2 is weak Lipschitz with the dissimilarity ℓ(x, y) = c(xy) 2 for some appropriate constant c.

Assumption 2. The mean-payoff function f is weakly Lipschitz.

Let f * h,i = sup x∈P h,i f (x) and ∆ h,i = f * -f * h,i be the suboptimality of node (h, i). We say that a node (h, i) is optimal (respectively, suboptimal) if ∆ h,i = 0 (respectively, ∆ h,i > 0). Let X ε def = { x ∈ X : f (x) ≥ f * -ε }
be the set of ε-optimal arms. The following result follows from the definitions; a proof can be found in the appendix. Lemma 1. Let Assumption 1 and 2 hold. If the suboptimality ∆ h,i of a region is bounded by cν 1 ρ h for some c > 0, then all arms in P h,i are max{2c, c + 1}ν

1 ρ h -optimal.
The last assumption is closely related to Assumption 2 of Auer et al. [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF], who observed that the regret of a continuum-armed bandit algorithm should depend on how fast the volume of the sets of ε-optimal arms shrinks as ε → 0. Here, we capture this by defining a new notion, the near-optimality dimension of the mean-payoff function. The connection between these concepts, as well as the zooming dimension defined by Kleinberg et al. [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF] will be further discussed in Section 7.

Define the packing number P(X , ℓ, ε) to be the size of the largest packing of X with disjoint open balls of radius ε with respect to the dissimilarity ℓ. 2 We now define the near-optimality dimension, which characterizes the size of the sets X ε in terms of ε, and then state our main result. Definition 3. For c > 0 and ε 0 > 0, the (c, ε 0 )-near-optimality dimension of f with respect to ℓ equals

inf d ∈ [0, +∞) : ∃ C s.t. ∀ε ≤ ε 0 , P X cε , ℓ, ε ≤ C ε -d (2)
(with the usual convention that inf ∅ = +∞). Theorem 1 (Main result). Let Assumptions 1 and 2 hold and assume that the (4ν 1 /ν 2 , ν 2 )-near-optimality dimension of the considered environment is d < +∞. Then, for any d ′ > d there exists a constant

C(d ′ ) such that for all n ≥ 1, E R n ≤ C(d ′ ) n (d ′ +1)/(d ′ +2) ln n 1/(d ′ +2) .
Further, if the near-optimality dimension is achieved, i.e., the infimum is achieved in [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF], then the result holds also for d ′ = d. Remark 3. We can relax the weak-Lipschitz property by requiring it to hold only locally around the maxima.

In fact, at the price of increased constants, the result continues to hold if there exists ε > 0 such that (1) holds for any x, y ∈ X ε . To show this we only need to carefully adapt the steps of the proof below. We omit the details from this extended abstract.

Analysis of the regret and proof of the main result

We first state three lemmas, whose proofs can be found in the appendix. The proofs of Lemmas 3 and 4 rely on concentration-of-measure techniques, while that of Lemma 2 follows from a simple case study. Let us fix some path (0, 1), (1, i * 1 ), . . . , (h, i * h ), . . . , of optimal nodes, starting from the root.

Lemma 2. Let (h, i) be suboptimal node. Let k be the largest depth such that (k, i * k ) is on the path from the root to (h, i). Then we have

E N h,i (n) ≤ u+ n t=u+1 P N h,i (t) > u and U h,i (t) > f * or U s,i *
s ≤ f * for some s ∈ {k+1, . . . , t-1} .

Lemma 3. Let Assumptions 1 and 2 hold. Then, for all optimal nodes and for all integers n ≥ 1,

P U h,i (n) ≤ f * ≤ n -3 .
Lemma 4. Let Assumptions 1 and 2 hold. Then, for all integers t ≤ n, for all suboptimal nodes (h, i) such that ∆ h,i > ν 1 ρ h , and for all integers u ≥ 1 such that u ≥

8 ln n (∆ h,i -ν1ρ h ) 2 , one has P U h,i (t) > f * and N h,i (t) > u ≤ t n -4 .
Taking u as the integer part of (8 ln n)/(∆ h,iν 1 ρ h ) 2 , and combining the results of Lemma 2, 3, and 4 with a union bound leads to the following key result. Lemma 5. Under Assumptions 1 and 2, for all suboptimal nodes (h, i) such that ∆ h,i > ν 1 ρ h , we have, for all n ≥ 1,

E[N h,i (n)] ≤ ln n (∆ h,i -ν 1 ρ h ) 2 + 2 n .
We are now ready to prove Theorem 1.

Proof. For the sake of simplicity we assume that the infimum in the definition of near-optimality is achieved.

To obtain the result in the general case one only needs to replace d below by d ′ > d in the proof below.

First step. For all h = 1, 2, . . ., denote by I h the nodes at depth h that are 2ν 1 ρ h -optimal, i.e., the nodes

(h, i) such that f * h,i ≥ f * -2ν 1 ρ h .
Then, I is the union of these sets of nodes. Further, let J be the set of nodes that are not in I but whose parent is in I. We then denote by J h the nodes in J that are located at depth h in the tree. Lemma 4 bounds the expected number of times each node (h, i)

∈ J h is visited. Since ∆ h,i > 2ν 1 ρ h , we get E N h,i (n) ≤ 8 ln n ν 2 1 ρ 2h + 2 n .
Second step. We bound here the cardinality |I h |, h > 0. If (h, i) ∈ I h then since ∆ h,i ≤ 2ν 1 ρ h , by Lemma 1 P h,i ⊂ X 4ν1ρ h . Since by Assumption 1, the sets (P h,i ), for (h, i) ∈ I h , contain disjoint balls of radius ν 2 ρ h , we have that

|I h | ≤ P ∪ (h,i)∈I h P h,i , ℓ, ν 2 ρ h ≤ P X (4ν1/ν2) ν2ρ h , ℓ, ν 2 ρ h ≤ C ν 2 ρ h -d
, where we used the assumption that d is the (4ν 1 /ν 2 , ν 2 )-near-optimality dimension of f (and C is the constant introduced in the definition of the near-optimality dimension).

Third step. Choose η > 0 and let H be the smallest integer such that ρ H ≤ η. We partition the infinite tree T into three sets of nodes, T = T 1 ∪ T 2 ∪ T 3 . The set T 1 contains nodes of I H and their descendants, T 2 = ∪ 0≤h<H I h , and T 3 contains the nodes ∪ 1≤h≤H J h and their descendants. (Note that T 1 and T 3 are potentially infinite, while T 2 is finite.)

We denote by (H t , I t ) the node that was chosen by the forecaster at round t to pick X t . From the definition of the forecaster, no two such random variables are equal, since each node is picked at most once. We decompose the regret according to the element T j where the chosen nodes (H t , I t ) belong to:

E R n = E n t=1 (f * -f (X t )) = E R n,1 + E R n,2 + E R n,3 ,
where for all i = 1, 2, 3,

R n,i = n t=1 (f * -f (X t ))I {(Ht,It)∈Ti} .
contribution from T 1 is easy to bound. By definition any node in I H is 2ν 1 ρ H -optimal. Hence, by Lemma 1 the corresponding domain is included in X 4ν1ρ H . The domains of these nodes' descendants are of course still included in X 4ν1ρ H . Therefore, E[R n,1 ] ≤ 4nν 1 ρ H . For h ≥ 1, consider a node (h, i) ∈ T 2 . It belongs to I h and is therefore 2ν 1 ρ h -optimal. By Lemma 1, the corresponding domain is included in X 4ν1ρ h . By the result of the second step and using that each node is played at most once, one gets

E R n,2 ≤ H-1 h=0 4ν 1 ρ h |I h | ≤ 4ν 1 C ν -d 2 H-1 h=0 ρ h(1-d) .
We finish with the contribution from T 3 . We first remark that since the parent of any element (h, i) ∈ J h is in I h-1 , by Lemma 1 again, we have that P h,i ⊂ X 4ν1ρ h-1 . To each node (H t , I t ) played in T 3 , we associate the element (H ′ t , I ′ t ) of some J h on the path from the root to (H t , I t ). When (H t , I t ) is played, the chosen arm X t belongs also to P H ′ t ,I ′ t . Decomposing R n,3 according to the elements of ∪ 1≤h≤H J h , we then bound the regret from T 3 as

E R n,3 ≤ H h=1 4ν 1 ρ h-1 i : (h,i)∈J h E N h,i (n) ≤ H h=1 4ν 1 ρ h-1 |J h | 8 ln n ν 2 1 ρ 2h + 2 n
where we used the result of the first step. Now, it follows from that fact that the parent of J h is in

I h-1 that |J h | ≤ 2|I h-1 |.
Substituting this and the bound on

|I h-1 |, we get E R n,3 ≤ 8ν 1 C ν -d 2 H h=1 ρ h(1-d)+d-1 8 ln n ν 2 1 ρ 2h + 2 n .
Fourth step. Putting things together, we have proved

E Rn ≤ 4nν 1ρ H + 4ν1C ν -d 2 H-1 h=0 ρ h(1-d) + 8ν1C ν -d 2 H h=1 ρ h(1-d)+d-1 8 ln n ν 2 1 ρ 2h + 2 n = O nρ H + (ln n) H h=1 ρ -h(1+d) = O nρ H + ρ -H(1+d) ln n = O n (d+1)/(d+2) (ln n) 1/(d+2)
by using first that ρ < 1 and then, by optimizing over ρ H (the worst value being ρ H ∼ ( n ln n ) -1/(d+2) ).

Minimax optimality

The packing dimension of a set X is the smallest d such that there exists a constant k such that for all ε > 0, P X , ℓ, ε ≤ k ε -d . For instance, compact subsets of R d (with non-empty interior) have a packing dimension of d whenever ℓ is a norm. If X has a packing dimension of d, then all environments have a near-optimality dimension less than d. The proof of the main theorem indicates that the constant C(d) only depends on d, k (of the definition of packing dimension), ν 1 , ν 2 , and ρ, but not on the environment as long as it is weakly Lipschitz. Hence, we can extract from it a distribution-free bound of the form O(n (d+1)/(d+2) ).

In fact, this bound can be shown to be optimal as is illustrated by the theorem below, whose assumptions are satisfied by, e.g., compact subsets of R d and if ℓ is some norm of R d . The proof can be found in the appendix.

Theorem 2. If X is such that there exists c > 0 with P(X , ℓ, ε) ≥ c ε -d ≥ 2 for all ε ≤ 1/4 then for all n ≥ 4 d-1 c/ ln(4/3), all strategies ϕ are bound to suffer a regret of at least

sup E R n (ϕ) ≥ 1 4 1 4 c 4 ln(4/3) 2/(d+2) n (d+1)/(d+2) ,
where the supremum is taken over all environments with weakly Lipschitz payoff functions.

Discussion

Several works [1; 8; 2; 9] have considered continuum-armed bandits in Euclidean or metric spaces and provided upper-and lower-bounds on the regret for given classes of environments. Cope [4] derived a regret of O( √ n) for compact and convex subset of R d and a mean-payoff function with unique minima and second order smoothness. Kleinberg [START_REF] Kleinberg | Nearly tight bounds for the continuum-armed bandit problem[END_REF] considered mean-payoff functions f on the real line that are Hölder with degree 0 < α ≤ 1. The derived regret is Θ(n (α+1)/(α+2) ). Auer et al. [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF] extended the analysis to classes of functions with only a local Hölder assumption around maximum (with possibly higher smoothness degree α ∈ [0, ∞)), and derived the regret Θ(n 1+α-αβ 1+2α-αβ ), where β is such that the Lebesgue measure of ε-optimal states is O(ε β ). Another setting is that of [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF] who considered a metric space (X , ℓ) and assumed that f is Lipschitz w.r.t. ℓ. The obtained regret is O(n (d+1)/(d+2) ) where d is the zooming dimension (defined similarly to our near-optimality dimension, but using covering numbers instead of packing numbers and the sets X ε \ X ε/2 ). When (X , ℓ) is a metric space covering and packing numbers are equivalent and we may prove that the zooming dimension and near-optimality dimensions are equal.

Our main contribution compared to [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF] is that our weak-Lipschitz assumption, which is substantially weaker than the global Lipschitz assumption assumed in [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF], enables our algorithm to work better in some common situations, such as when the mean-payoff function assumes a local smoothness whose order is larger than one. In order to relate all these results, let us consider a specific example: Let X = [0, 1] D and assume that the mean-reward function f is locally equivalent to a Hölder function with degree α ∈ [0, ∞) around any maxima x * of f (the number of maxima is assumed to be finite):

f (x * ) -f (x) = Θ(||x -x * || α ) as x → x * . (3) This means that ∃c 1 , c 2 , ε 0 > 0, ∀x, s.t. ||x -x * || ≤ ε 0 , c 1 ||x -x * || α ≤ f (x * ) -f (x) ≤ c 2 ||x -x * || α .
Under this assumption, the result of Auer et al. [START_REF] Auer | Improved rates for the stochastic continuum-armed bandit problem[END_REF] shows that for D = 1, the regret is Θ( √ n) (since here β = 1/α). Our result allows us to extend the √ n regret rate to any dimension D. Indeed, if we choose our dissimilarity measure to be ℓ α (x, y) def = ||x -y|| α , we may prove that f satisfies a locally weak-Lipschitz condition (as defined in Remark 3) and that the near-optimality dimension is 0.

Thus our regret is O( √ n),
i.e., the rate is independent of the dimension D.

In comparison, since Kleinberg et al. [START_REF] Kleinberg | Multi-armed bandits in metric spaces[END_REF] have to satisfy a global Lipschitz assumption, they can not use ℓ α when α > 1. Indeed a function globally Lipschitz with respect to ℓ α is essentially constant. Moreover ℓ α does not define a metric for α > 1. If one resort to the Euclidean metric to fulfill their requirement that f be Lipschitz w.r.t. the metric then the zooming dimension becomes D(α -1)/α, while the regret becomes O(n (D(α-1)+α)/(D(α-1)+2α) ), which is strictly worse than O( √ n) and in fact becomes close to the slow rate O(n (D+1)/(D+2) ) when α is larger. Nevertheless, in the case of α ≤ 1 they get the same regret rate.

In contrast, our result shows that under very weak constraints on the mean-payoff function and if the local behavior of the function around its maximum (or finite number of maxima) is known then global optimization suffers a regret of order O( √ n), independent of the space dimension. As an interesting sidenote let us also remark that our results allow different smoothness orders along different dimensions, i.e., heterogenous smoothness spaces.

A Proof of Lemma 1

Proof. We denote by x * h,i (δ) an element of P h,i such that f x * h,i (δ) ≥ f * h,iδ . By the weakly Lipschitz property, it then follows that for all y ∈ P h,i ,

f * -f (y) ≤ f * -f x * h,i (δ) +max f * -f x * h,i (δ) , ℓ x * h,i (δ), y ≤ ∆ h,i +δ+max ∆ h,i +δ, diam P h,i .
δ → 0 and substituting the bounds on the suboptimality and on the diameter of P h,i concludes the proof.

B Proof of Lemma 2

Proof. We consider a given round t ∈ {1, . . . , n}. If (H t , I t ) ∈ C(h, i), then this is because the child of (k, i * k ) on the path to (h, i) had a better B-value than its brother (k + 1, i * k+1 ). Since by definition, Bvalues can only decrease on a path, this entails that B h,i (t) ≥ B k+1,i * k+1 (t). This is turns implies, again by definition of the B-values, that U h,i (t) ≥ B k+1,i * k+1 (t). Thus,

(H t , I t ) ∈ C(h, i) ⊂ U h,i (t) ≥ B k+1,i * k+1 (t) ⊂ U h,i (t) ≥ f * ∪ B k+1,i * k+1 (t) ≤ f * . But, once again by definition of B-values, B k+1,i * k+1 (t) ≤ f * ⊂ U k+1,i * k+1 (t) ≤ f * ∪ B k+2,i * k+2 (t) ≤ f *
, and the argument can be iterated. Since at round t not more than t nodes have been played (including the suboptimal (h, i)), we know that (t, i * t ) and its descendants have U -values and B-values equal to +∞. We thus have proved the inclusion

(H t , I t ) ∈ C(h, i) ⊂ U h,i (t) ≥ f * ∪ B k+1,i * k+1 (t) ≤ f * ∪ . . . ∪ B t-1,i * t-1 (t) ≤ f * .
The result follows by simply distinguishing whether N h,i (t) > u (which can only happen if t ≥ u) or not.

C Proof of Lemma 3

Proof. U h,i ≤ f * is not true when node (h, i) was never pulled (in this case, by definition, U h,i (n) = +∞).

We may thus conduct the study in the sequel on the event N h,i (n) ≥ 1 .

Lemma 1 with c = 0 gives that f *f (x) ≤ ν 1 ρ h holds for any arm x ∈ P h,i . Hence,

n t=1 f (X t ) + ν 1 ρ h -f * I {(Ht,It)∈C(h,i)} ≥ 0
and therefore,

P U h,i (n) ≤ f * and N h,i (n) ≥ 1 = P µ h,i (n) + 2 ln n N h,i (n) + ν 1 ρ h ≤ f * and N h,i (n) ≥ 1 = P N h,i (n) µ h,i (n) + N h,i (n) ν 1 ρ h -f * ≤ -N h,i (n) 2 ln n and N h,i (n) ≥ 1 ≤ P n t=1 f (X t ) -Y t I {(Ht,It)∈C(h,i)} ≥ N h,i (n) 2 ln n and N h,i (n) ≥ 1 .
We take care of the last term with a union bound and the Hoeffding-Azuma inequality for martingale differences. To do this properly we need to define a sequence of (random) times when arms in C(h, i) were pulled:

T j = min { t : N h,i (t) = j } , j = 1, 2, . . . .
Note that 1 ≤ T 1 T 2 < . . . and hence it holds that T j ≥ j. With these notation, X j = X Tj is the j-th arm pulled in a domain corresponding to C(h, i), Y j = Y Tj is the corresponding reward, and

P n t=1 f (X t ) -Y t I {(Ht,It)∈C(h,i)} ≥ N h,i (n) 2 ln n and N h,i (n) ≥ 1 = P    N h,i (n) j=1 f ( X j ) -Y j ≥ N h,i (n) 2 ln n and N h,i (n) ≥ 1    ≤ n t=1 P    t j=1 f ( X j ) -Y j ≥ √ 2 t ln n   
where we used a union bound to get the last inequality.

We now prove that

Z t = t j=1 f ( X j ) -Y j
is a martingale difference sequence (with respect to the filtration it generates). This follows, via optional skipping (see [START_REF] Doob | Stochastic Processes[END_REF], Theorem 2.3), from the fact that

n t=1 f (X t ) -Y t I {(Ht,It)∈C(h,i)}
is a martingale, with respect to the filtration F t = σ(X 1 , Y 1 , . . . , X t , Y t ), and that {T j = k} ∈ F k-1 .

Applying the Hoeffding-Azuma inequality (using the bounded ranges), we then get, for each t ≥ 1,

P    t j=1 f ( X j ) -Y j ≥ √ 2 t ln n    ≤ exp   - 2 √ 2 t ln n 2 t    = n -4 ,
which concludes the proof.

D Proof of Lemma 4

Proof. Remark that for the u mentioned in the statement of the lemma,

2 ln t u + ν 1 ρ h ≤ (∆ h,i + ν 1 ρ h )/2 , therefore, P U h,i (t) > f * and N h,i (t) > u = P µ h,i (t) + 2 ln t N h,i (t) + ν 1 ρ h > f * h,i + ∆ h,i and N h,i (t) > u ≤ P µ h,i (t) > f * h,i + ∆ h,i -ν 1 ρ h 2 and N h,i (t) > u ≤ P N h,i (t) µ h,i (t) -f * h,i > ∆ h,i -ν 1 ρ h 2 u and N h,i (t) > u = P t s=1 Y s -f * h,i I {(Hs,Is)∈C(h,i)} > ∆ h,i -ν 1 ρ h 2 u and N h,i (t) > u ≤ P t s=1 Y s -f (X s ) I {(Hs,Is)∈C(h,i)} > ∆ h,i -ν 1 ρ h 2 u and N h,i (t) > u .
Now it follows again by the optional skipping argument, the Hoeffding-Azuma inequality, and a union bound, that

P t s=1 Y s -f (X s ) I {(Hs,Is)∈C(h,i)} > ∆ h,i -ν 1 ρ h 2 u and N h,i (t) > u ≤ t s=u+1 exp - 2 s (∆ h,i -ν 1 ρ h ) u 2 2 ≤ t exp - 1 2 u ∆ h,i -ν 1 ρ h 2 ≤ t n -4
(where we used the stated bound on u to obtain the last inequality).

E Proof of Theorem 2

We only deal with the case of deterministic strategies. The extension to randomized strategies can be done using Fubini's theorem.

For η ∈ [0, 1/4] and x * ∈ X , we denote by f η,x * the mapping defined by

f η,x * (x) = max η -ℓ(x, x * ), 0
for all x ∈ X and by M η,x * the environment defined by

M η,x * (x) = Ber 1 2 + f η,x * (x)
for all x ∈ X . We consider K points x 1 , . . . , x K in X such that the balls B xj ,η with radius η centered at each of the x j are non-overlapping. Note that B xj ,η is the support of f η,x * . In addition, the mean functions of all the defined environments are 1-Lipschitz and thus are weakly Lipschitz.

We will also need to consider environments on a finite set of arms {1, . . . , K + 1}. We construct K different product-distributions ν 1 , ν 2 , . . . , ν K for the arms {1, . . . , K + 1} as follows. For a given ν j , the reward distribution associated to the i-th arm is ν j,i = Ber(1/2) for all i = j and ν j,j = Ber(1/2 + η).

To each (deterministic) strategy ϕ on X , we associate a random strategy ψ on the finite set of arms {1, . . . , K + 1} as follows. Let t ≥ 1. Since ϕ is deterministic it associates to each sequence of rewards {r 1 , .., r t-1 ∈ {0, 1} t-1 a unique sequence {x 1 , .., x t } ∈ X t of arms that ϕ would have pull under this sequence of rewards. With a slight abuse of notation we can write ϕ(r 1 , .., r t-1 ) = (x 1 , .., x t ). Now assume that the historic of ψ at time t is X 1 , R 1 , . . . , X t-1 , R t-1 and let (X ′ 1 , .., X ′ t ) = ϕ(R 1 , .., R t-1 ). We then define

ψ t = δ K+1 if X ′ t ∈ ∪ j B xj ,η , ψ t = 1 - ℓ(X ′ t ,xj ) η δ xj + ℓ(X ′ t ,xj ) η δ K+1 if X ′ t ∈ B xj ,η
, where δ j is a dirac distribution on j.

We now want to prove that the distributions of the regrets for ϕ under M η,xj and for ψ under ν j are equal for all j = 1, . . . , K. On the one hand, the expectations of the best arms are 1/2 + η under all these environments. On the other hand we can prove recursively that for any {r 1 , .., r t } ∈ {0, 1} t , P(R 1 = r 1 , .., R t = r t ) = P(R ′ 1 = r 1 , .., R ′ t = r t ). where R 1 , . . . , R t (respectively R ′ 1 , . . . , R ′ t ) is the sequence of rewards obtained by ϕ under M η,xj (respectively ψ under ν j ). The result is easy to check for t = 1 and for t > 1 it follows from P(R 1 = r 1 , .., R t = r t ) = P(R t = r t |R 1 = r 1 , .., R t = r t )P(R 1 = r 1 , .., R t-1 = r t-1 ) and the same calculation for R ′ t . As a consequence, the regrets R n (ϕ) and R n (ψ) have the same expectation, that is, for all j = 1, . . . , K,

E j R n (ϕ) = E ′ j R n (ψ) (4)
where E j denotes the expectation under M η,xj and E ′ j the one under ν j . But it can be extracted from the proof of the lower bound of [3, Section 6.9] that for all strategies ψ ′ , all η ∈ [0, 1/4], and all integers K, max j=1,...,K

E ′ j R n (ψ ′ ) ≥ ηn 1 - 1 K -η 4 ln(4/3) n K . (5)
By the assumption on packing dimension, there exists c > 0 such that K = c η -d ≥ 2 is a suitable choice. Substituting this value, we get The left-hand side is smaller than the maximal regret with respect to all weak-Lipschitz environments; the right-hand side can be optimized over η ≤ 1/4 to get the claimed bound, by taking η = 1 4 c 4 ln(4/3) 2/(d+2) n -1/(d+2) .

We write un = O(vu) when un = O(vn) up to a logarithmic factor.

Note that sometimes packing numbers are defined as the largest packing with disjoint open balls of radius ε/2, or, ε-nets.